Approximation de courbe par des segments

par **dys** » 26 Fév 2007, 11:39

Hello,
je suis sûr qu'il existe des tas d'algos pour transformer des données discrêtes issues d'un capteur en une série de segments. Le problème, c'est que je n'arrive pas à en trouver.

Quelqu'un aurait-il ça ?

Merci beaucoup d'avance !

par **Dominique Lefebvre** » 26 Fév 2007, 13:11

dys a écrit:Hello,
je suis sûr qu'il existe des tas d'algos pour transformer des données discrêtes issues d'un capteur en une série de segments. Le problème, c'est que je n'arrive pas à en trouver.

Quelqu'un aurait-il ça ?

Merci beaucoup d'avance !

Bonjour,

Tu peux transformer ta série de mesures en une courbe polynomiale(ou autre si besoin) en faisant une régression linéaire.
Tu trouveras sur google une description de laméthodes des moindres carrés, la plus simple à mettre en oeuvre.

Et comble de la paresse, si tu as un Excel sous la main, il existe une fonction qui te fait ça toute seule... Regarde par exemple: www-physique.u-strasbg.fr/~udp/articles/www-clepsydre/Excel-how-to-II.pdf

par **dys** » 26 Fév 2007, 13:20

Merci pour ta réponse. Mais je crains qu'elle ne me suffise pas : mon problème n'est pas d'avoir une régression linéaire de ma courbe mais plutôt d'en avoir une série : je voudrais ainsi transformer ma courbe en une série de segments de droite.

La minimisation pourrait être celle des moindres carrés mais le problème est de déterminer le nombre de segments et la position des points. Je suppose qu'à partir de là je pourrais faire une optimisation numérique standard mais j'espère qu'il existe des algorithmes "intégrés" pour ce type d'opération qui ne me semble pas franchement exotique...

EDIT : juste une précision : évidemment, ma courbe contient de nombreux extrema...

par **andros06** » 26 Fév 2007, 16:13

Interpolation linéaire entre chaque point ... Tu calcules les coefficients de la droite entre les deux points voisins et tu traces les droites sur chaque intervalle... Sinon tu peux interpoler avec la méthodes des splines cubiques (Google is your friend) ce qui a l'avantage d'être plus jloi qu'une pauvre courbe brisée.

par **dys** » 26 Fév 2007, 16:26

Heu... l'un de nous n'a probablement pas compris l'autre.

Mon problème n'est pas un problème d'interpolation : je ne connais pas les points à conserver. Je cherche à trouver un ensemble de segments de droite (par exemple 10) qui approximent un ensemble discret de points (courbe à pas régulier, par exemple 500 points).

(les splines d'ordre supérieur ne m'intéressent pas, il est fondamental pour moi d'obtenir des segments)

par **Dominique Lefebvre** » 26 Fév 2007, 19:05

dys a écrit:Heu... l'un de nous n'a probablement pas compris l'autre.

Mon problème n'est pas un problème d'interpolation : je ne connais pas les points à conserver. Je cherche à trouver un ensemble de segments de droite (par exemple 10) qui approximent un ensemble discret de points (courbe à pas régulier, par exemple 500 points).

(les splines d'ordre supérieur ne m'intéressent pas, il est fondamental pour moi d'obtenir des segments)

Est-ce que c'est toi qui décide des extréma des segments ou bien attends-tu que ce soit l'algo?
Je me pose autrement ma question: veux-tu un algo qui approxime ta suite de points par une ligne brisée?

par **dys** » 26 Fév 2007, 19:27

Ta dernière formulation est presque parfaite : je veux "un algo qui approxime ma suite de points par une ligne brisée" (mais sans imposer la continuité sur la ligne brisée). Et c'est bien à l'algorithme de trouver les extrema des segments.

Heureusement que tu es là pour formuler ma question... J'ai l'impression que je n'étais pas vraiement clair...

Par contre, là je suis en train de tester une solution avec un collègue. Je suis intéressé par des références supplémentaires mais je ne pourrai pas forcément tester. Evidemment, si notre solution marche, j'en dirai quelques mots ici avant de clore le sujet !

par **Dominique Lefebvre** » 27 Fév 2007, 11:36

Bonjour,

Je suis curieux! Si tu nous expliquais de quel capteur il s'agit, de quel type de mesure et ce que tu veux faire de ces segments...

par **dys** » 28 Fév 2007, 10:41

Les capteurs en question sont dans le monde du procédé industriel continu (fabrication d'acier, de verre, de papier, etc.). Il s'agit de mesures de forces, de températures, d'épaisseurs, etc. Donc généralement des données non fréquentielles, mesurées avec des résolutions assez faibles (on travaille sur des signaux contenant environ 500 points).

La transformation en segments permet de faire automatiquement des analyses qualitatives multi-signal ("si le signal A monte beaucoup et le signal B baisse, alors il y a un phénomène C"), de façon simple et lisible pour les experts en usine.

J'avais dit que j'avais une solution, voici en gros comment nous procédons :

Nous utilisons une optimisation à deux niveaux. Pour un nombre de segments donné, on fait une optimisation numérique à peu près standard (avec du recuit simulé) pour choisir les points (séparations entre les segments).
A ce stade, la fonction de coût est essentiellement basée sur les "moindres carrés" (somme des carrés des écarts entre le signal d'origine et son approximation par la ligne brisée).

Et on a une optimisation englobante (pas tout à fait séparée en réalité, itérative) pour déterminer le nombre de segments.

Après ça, le reste du problème n'est qu'un amas d'heuristiques pour que l'optimisation converge vite en évitant les minima locaux et pour que le nombre de segments soit adapté à l'usage que l'on en fait ensuite...

Approximation de courbe par des segments

approximation de courbe par des segments

Qui est en ligne