Discussion :

[dseguret]

Bonjour,

étant donnée une courbe (un signal obtenu d'un capteur quelconque), je cherche à faire un lissage linéaire : à trouver une succession de segments de droite qui approche cette courbe. Par contre, je ne voudrais pas me recoder ça étant donné que ça a dû être fait de nombreuses fois déjà.

Est-ce que quelqu'un aurait des références d'algorithmes pour ce type de problèmes ? J'ai déjà fait de nombreuses recherches sur le web sans rien trouver de vraiment utilisable.

Petite précision : je ne veux pas fixer par avance le nombre de segments, mais plutôt me baser sur des critères de distance (par exemple moindres carrés). Et si un algo existant intègre le problème de l'élimination des points aberrants, alors mon bonheur est complet.

Merci beaucoup d'avance !

[progfou]

Je ne pourrais pas répondre directement à ce problème, mais il est amusant de constater qu'il est de niveau 1ère S.
Je ne te descends pas du tout, je vais expliquer .

En fait, j'ai expliqué, à un 1ère S donc, les dérivées, et les tangentes. Puis est venue la notion d'approximation affine. Et là, j'ai montré, en 1h sur un papier (donc peu de temps sur un PC) qu'il est possible d'approcher la fonction sinus (c'était l'exemple) par y=x autour de 0. Tout ça pour ?
Tout ça pour montrer qu'on pouvait le faire en tout point, et que donc, avec 5 segments, on a déjà quelque chose de potable.

Au final, ton problème est juste un problème d'approximation affine, le pas étant déterminé par le nombre de segments que tu veux (ou l'erreur que tu acceptes)...

[dseguret]

Je ne suis pas sûr que tu aies bien compris le problème (mais il est probable que je me sois mal exprimé) : on parle ici de transformer une succession de mesures, évidemment bruitées, en une ligne brisée approchante, charge à l'algorithme de positionner les segments.

Comme j'ai fini par résoudre le problème (avec un collègue), je vais tout de suite donner la solution adoptée :

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...

[souviron34]

euh...

j'avoue que ça me semble compliqué...

Pourquoi ne pas bêtement faire soit une moyenne glissante soit un moindre carré pour avoir une courbe moyenne, puis éliminer les points abherrants, refaire la courbe moyenne, et ensuite approximer chaque morceau de courbe (un spline est une cubique) par une droite ????

(mais j'ai toujours été rébarabtif aux mots "techniques" comme heuristique, recuit simulé, ou optimisation englobante.... )...

[dseguret]

euh...

j'avoue que ça me semble compliqué...

Pourquoi ne pas bêtement faire soit une moyenne glissante soit un moindre carré pour avoir une courbe moyenne, puis éliminer les points abherrants, refaire la courbe moyenne, et ensuite approximer chaque morceau de courbe (un spline est une cubique) par une droite ????

(mais j'ai toujours été rébarabtif aux mots "techniques" comme heuristique, recuit simulé, ou optimisation englobante.... )...

Pourquoi ? Et bien parce qu'il me semble qu'il manque au moins une étape dans ta solution, la plus difficile, celle qui permet de déterminer les points de changements de segments. Ceci dit, je ne prétend pas avoir la seule solution possible, mais je ne vois pas trop comment faire sans optimisation numérique.

Puisque je crois que tu me taquines sur les termes que j'emploie, un peu de précision :

• recuit simulé : technique standard d'optimisation (voir la définition dans Wikipedia)
• optimisation englobante : pas du tout un terme "technique", mais un essai de ma part pour décrire de façon imagée ce que je fais...
• heuristique : comprendre "bricolage qui a l'air de marcher"

[pseudocode]

Pourquoi ? Et bien parce qu'il me semble qu'il manque au moins une étape dans ta solution, la plus difficile, celle qui permet de déterminer les points de changements de segments.

Bah les points de changements tu les determines au cours de ton approximation. Quand la tangeante s'eloigne trop de ta courbe lissée, tu créé un nouveau point sur la courbe, qui devient ton nouveau point de depart/arrivé de segment ...

[progfou]

Ma solution, quoique naïve et certainement mal exprimée, est proche cette optimisation.
Seulement, j'ai une forte tendance à me dire que plus c'est simple, mieux ça fonctionne .
Si j'avais le temps, je la mettrais en oeuvre, mais bon, il y a sûrement un truc qui poserait problème (le type de donnée par exemple)...

[pseudocode]

Inutile de reinventer la roue. Y a deja des algo qui permettent de faire cela.

Le plus connu est celui de Douglas-Peucker, largement dispo sur google.

[Zavonen]

Pour l'approximation d'un nuage de points par une droite il existe un procédé standard, la "regression linéaire". c'est un truc de stats basé sur les moindres carrés, cela se trouve partout.
Pour la mesure de la qualité de l'approximation il existe une mesure également standard le "coefficient de correlation linéaire". Les formules se trouvent partout.
Donc, étant fixée au départ une marge d'erreur par un encadrement du c.c.l. (doit être proche des extrêmités du segment [-1;1]), on peut travailler comme suit:
Je prends les deux premiers points le ccl est forément OK, puis j'incorpore le suivant, si le ccl calculé est dans une limite acceptable, j'incorpore le quatrième and so on..
Quand le ccl 'décolle', je commence tout simplement une nouvelle série avec les deux points suivants, jusqu'à épuisement.