Algorithme de détection de montée

Bonjour à tous!

Dans le cadre d'un projet informatique à l'école, je travaille sur un algorithme de détection de montée.
J'ai un profil altimétrique que voici (courbe noire):

Pièce jointe 635098

On peut y remarquer globalement 4 montées. Mon objectif est de détecter ces montées, et de renvoyer des listes [(x1,y1), (x2,y2)] avec x1 l'abscisse du début de la montée, y1 son ordonnée, et x2 l'abscisse de la fin de la montée, et y2 son ordonnée.

Pour cela, j'ai décidé de procéder par étapes:

- Trouver un algorithme qui détecte les extremums de la fonction (que j'appellerai (max1, max2,...maxn).
- Considérer des segments entre deux extremums successifs: entre chaque extremum, il y a forcément un moment où la courbe décroît, atteint un minimum, puis remonte jusqu'à l'extremum suivant. Entre max1 et max2, il existe nécessairement un min1.
- Je trouve ce minimum en question. Ainsi, entre un minimum et l'extremum suivant, il s'agit forcément d'une pente ascendante. Donc on détecte une montée entre min1 et max2.

Donc, je suis censée trouver les montées grâce à cet algo assez simple. Cependant, mon algorithme de détection d'extremum est très peu robuste: je parcours la liste des ordonnées, et considère qu'il y a un extremum si l'ordonnée d'un point est supérieure à la précédente et à la suivante; ie si f(x2)>f(x1) et f(x2)>f(x3).

Le soucis, c'est que mon signal originel est très bruité, ce qui fausse énormément la détection de pics.

J'ai donc pensé à le filtrer. l'algorithme marche beaucoup mieux et détecte bien quatre pics. Le filtre crée cependant un déphasage que je suis incapable de quantifier (courbe rouge). De plus, on m'a conseillé de ne pas filtrer car cela engendrerait une perte de précision et l'objectif de l'exercice est justement celui-ci.


Auriez-vous des pistes pour régler le problème svp ? J'espère avoir été suffisamment claire.

Bonjour,
En gros il faut identifier une tendance avant de trouver le maximum. C'est l'historique de 1 seul élément que tu prends qui cause ton problème de bruit.
Je ne suis pas experte, mais je réduirai le bruit avec une moyenne mobile.
Après il faut définir un nombre de points dans ta moyenne mobile. (je dirais 5 au pifomètre, mais 10 serait peut être mieux).
mm(x) = f(x-4)+f(x-3)+f(x-2)+f(x-1)+f(x)/5. (tu adaptes la formule si tu prends un pas plus grand)
Au lieu de seulement tester (f(x)>f(x-1) et f(x)>f(x+1)) tu rajoutes et (mm(x)>mm(x-1) et mm(x)>mm(x+1))
Ca devrait réduire le bruit je pense (à toi de tester avec différent pas, pour trouver la meilleure valeur pour ta moyenne mobile)

Ajout : en fait en regardant à nouveau ton graphe je me suis dit la courbe filtrée ressemblait beaucoup à une moyenne mobile (d'où le décalage) il faut peut être que tu enlèves la 2eme partie de la condition ça donnerait : (f(x)>f(x-1) et f(x)>f(x+1)) et (mm(x)>mm(x-1))

2eme ajout : si ça laisse trop passer de faux maximum encore peut être jouer sur la dérivée de la moyenne mobile qui doit être positive et supérieure aux 2 qui l'entoure.

Je vais numéroter ton axe des abscisses de 0 à 400, pour avoir un support.
Tu parles de 4 montées, j'imagine que tu vois (30,80), (120,180), (190,20) et (320,350)
Mais la première montée, on pourrait la décomposer en 2 voire 3 montées. C'est assez subjectif de dire que cette partie est une et une seule montée.

Virginieh parle de moyenne mobile, mais la formule proposée entraine un décalage.

mm(x) =( f(x-2)+f(x-1)+f(x)+f(x+1)+f(x+2) ) /5 permettrait de lisser les données, sans générer de décalage.
Ici, vu la granularité, et vu l'objectif (faire en sorte que la partie de x=30 à x=80 apparaisse comme une seule montée), il faut un lissage assez violent, et donc répéter cette opération de lissage 3 ou 4 fois.

Attention, avec ces moyennes mobiles, on érode violemment les extrémums. Ces moyennes mobiles vont nous servir à déterminer les abscisses des début et fin de montées, mais pas les ordonnées correspondantes.
Pour les ordonnées, ce que je ferais, c'est :
- J'ai identifié un tronçon x0,x1 qui est une montée
- Je repars des données initiales sur ce segment, et je cherche la droite qui approche le mieux cette série de données, par la méthode des moindres carrés (la droite, ou peut-être la branche de parabole)
- Et je prends les 2 points de cette branche de parabole, d'abscisses x0 et x1.

Mais, soyons sérieux, ce que je propose, ça reste les bidouilles d'un bricoleur du dimanche qui essaie de réinventer la roue en se débrouillant avec ses maigres connaissances et qui ne sait pas ce qui existe en dehors de sa grotte. Il y a forcément des outils qui sont connus et reconnus pour ce genre de problème.

Citation:

---

Envoyé par tbc92

C'est assez subjectif de dire que cette partie est une et une seule montée.

---

il faudrait peut-être mieux définir la montée. par exemple une descente de moins de 2 unités en abscisse ou alors une descente de moins de 5 % de la hauteur reste dans la même montée.

Bonjour !

Virgineh:

J'ai utilisé une moyenne mobile (courbe rouge), j'ai oublié de le préciser !
Le problème est donc (je pense) ce que me reprochait mon prof, on trouve l'abscisse de l'extremum mais pas son ordonnée (et donc perte de précision). J'ai lissé énormément (moyenne mobile d'ordre 13) , donc je pense que c'est à éviter.

tbc92
Je n'avais pas du tout pensé à utiliser les moindres carrés. Le seul problème de la méthode, c'st justement l'identification du segment (x0,x1) dont tu parles justement, parce que j'aimerais l'automatiser au final (sur un nombre important de courbes).

mathieu
Oui, c'est vrai que je n'ai pas défini la montée. Je peux partir sur ce que tu disais, une descente de moins de 5% reste dans la même montée. Mais dans ce cas, est-ce que cela veut bien dire que je dois faire à chaque fois le test suivant: l'altitude[x] > 0,95*altitude[x+1] afin de d'identifier la montée?

Merci pour vos réponses!

PS: J'ai trouvé la fonction find_peaks en python qui permet d'identifier des extremums selon certains critères (hauteur minimale du pic, largeur etc) et cela m'a permis d'alléger mon code. Je passe donc à la deuxième étape de mon plan d'action expliqué plus haut.

Tu parles de moyenne mobile d'ordre 13, ça veut dire quoi ?
- On remplace chaque point par la moyenne des 13 dernières valeurs ? Dans ce cas, c'est sûr, on a un 'déphasage'.
- On remplace chaque point par la moyenne des 13 valeurs précédentes + la valeur courante + les 13 suivantes, et dans ce cas, tu ne devrais pas avoir ce déphasage.
Perso, je préfère refaire 2 passes successives, ou encore quelque chose comme ça
g(x)= ( f(x-8) + 2*f(x-7) + 3*f(x-6) .... + 8*f(x) + ... + f(x+8) ) / (1+2+3+...+8+7+...+1)

Avec ces moyennes mobiles, on identifie parfaitement les débuts et fin de chaque montée ou descente. Ensuite, on peut estimer chaque segment par la méthode des moindres carrés.
Avec peut-être un dernier raffinement de cruauté : Si la courbe est plus ou moins sinusoïdale, pour chaque montée, on a une montée lente puis une montée rapide, puis une montée lente. On doit pouvoir faire en sorte que la régression linéaire reflète ça correctement.

salut

passe par des filtres afin de lisser ta courbe et mettre en evidence
tes extremum

ensuite une simple boucle devrait te donner les extremun

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

MAX = TABPOINT[0]   POUR P DE 0 A n FAIRE DEBUT SI TABPOINT[P] > MAX ALORS // ICI ON MONTE DEBUT MAX = TABPOINT[P] TABPOINT[P-1] = 0 FIN SINON // ICI ON DECEND TABPOINT[P] = 0 MAX = 0 FINSI FIN FAIRE

---

PS : Plus serieusement c'est a l'aide de quel outil
une régression non paramétrique fortement connexe devrais t'aporter une solution plus que suffissante

Bonjour,

Un filtrage IIR (ou RII) apporte toujours un retard mais celui ci fait partie de ses caractéristiques. Pour les filtres de premier ordre, dits de type RC, rien n'empêche de retarder le signal d'origine (c'est une opération fictive qui suppose seulement de conserver des échantillons dans un tampon souvent circulaire avec 2ⁿ échantillons) pour qu'il soit en phase avec celui traité.

Mais il y a une autre possibilité à tester. Ne filtrer que la partie descendante. Par exemple, si X > Y^-1 alors Y = X sinon Y = Y^-1 + a.(X-Y^-1)[/C]. Selon a, ou plus généralement le filtre à la descente, les irrégularités locales seront plus ou moins absorbées et masqueront ou non les petits changements de pente. La détection est automatique : c'est quand on passe du mode croissant au mode filtré avec décroissance de la courbe (en général on travaille sur un signal amplifié - par exemple x256 - et on néglige un demi facteur - ici 128 - pour absorber le bruit). Pour les minima on peut procéder de même en intervertissant les critères.

Les filtres FIR (ou RIF) sont plus faciles à centrer sur la valeur courante mais moins sélectifs à ordre équivalent en IIR.

Salutations