Détection des maxima dans une fct d'autocorrélation [Résolu]

[Rosa2008]

bonjour;
Je suis débutante en Matlab. Je cherche à extraire le motif dans une texture sonore. J'ai calculé la fct d'autocorrélation qui présente des maximum au niveau de début de chaque motifs. Le problème c'est que je dois faire un algorithme efficace de détections de ces maximum. sachant que les maximum sont un peut flous
càd que le deuxième maxima recherché ne doit pas etre celui qui est juste près du premier.
J'espère que mon pb est bien clair.
Merci de me répondre.
Bonne journée

[FR119492]

Salut !

La recherche d'extrema consiste en fait à trouver les passages par zéro de la dérivée. Si la dérivation est une chose assez simple en calcul formel, en revanche en calcul numérique, c'est une autre paire de manches, à cause du bruit, qui est inévitable et dont la dérivation donne n'importe quoi. Personnellement, j'interpolerais la fonction étudiée par un spline cubique que je dériverais ensuite.

Jean-Marc Blanc

[pseudocode]

Une autre méthode plus basique:
- filtrage par moyenne mobile
- chercher tous les extrema locaux (passage par 0 de la derivée)
- utiliser une fenêtre glissante pour ne garder que les plus grands extrema locaux.

Moins efficace que la derivation formelle de la courbe d'approximation, mais assez simple a mettre en oeuvre.

[Rosa2008]

Bonjour;
Merci bien pour vos réponses. Je vais essayer d'appliquer la 2ème méth. J'ai trouvé la description de la méthode des moyennes mobiles dans le forum algo. Mais, j'ai pas bien saisis la 3ème étape (utiliser une fenêtre glissante pour ne garder que les plus grands extrema locaux)? Je suis informaticienne et j'ai des petites notions sur le traitement de signal.
Bonne journée et merci d'avance pour les eclaircissements.
Rosa.

[pseudocode]

Envoyé par Rosa2008

Mais, j'ai pas bien saisis la 3ème étape (utiliser une fenêtre glissante pour ne garder que les plus grands extrema locaux)? Je suis informaticienne et j'ai des petites notions sur le traitement de signal

Pas besoin de grandes compétences en traitement du signal. Le principe c'est de trouver un maximum local... donc forcement on ne s'intéresse qu'a des petits "morceaux" du signal. Dans chaque morceau on prend la valeur la plus grande => on obtient les maximum locaux.

Sauf que, si on fait un pré-découpage "fixe" des morceaux, on risque de trouver 2 maximum dans 2 morceaux consécutifs... alors qu'en fait il n'en faudrait qu'un seul.

Imaginons un signal avec 8 échantillons dans lequel on cherche les maximum locaux sur un voisinage de 4.

Si on fait un découpage de 8 échantillons en 2 paquets de 4, on obtient:

Code :

1
2
3
4
5
6
7
8

          |
      |   |     |
  |   |   | |   |
  | | | | | | | |
 -----------------> (t)
  [  1  ] [  2  ]

- un maximum dans le morceau 1 ( t=3, valeur=3 )
- un maximum dans le morceau 2 ( t=5, valeur=4 )

Hum... la distance sur l'axe "t" entre les 2 maximums est donc de 3-5=2, alors qu'on cherchait le maximum local sur un voisinage de 4. Problème.

Donc l'idée c'est de déplacer progressivement la fenêtre de taille 4 et de relever à chaque fois le maximum dans cette fenêtre: si le maximum est à la 1ere position de fenêtre => c'est un maximum local.

Voila, j'espère que ce que j'ai dit est clair.

[fatenov]

Salut Rosa,

Je pense pouvoir t'aider un peu. Il s'agit de ces trois méthodes de calcul avec des petits modifs:
1- Tu dois absolument faire un lissage de ta fonction (à toi de voir comment le faire )
2- En ce qui concerne la detection des maximas locaux, je pense que tu n'as pas besoin de faire avec des fenetres glissantes: tu peux consulter ce lien http://www.developpez.net/forums/sho...d.php?t=472142 : une réponse à la même problématique.
3- Une fois tu as saisie cette méthode, tu mets l'amplitude de tes pics dans un tableau et tu peux tout faire avec (cherdeux deux max successifs et chercher la distance)

Plus simple non?

Bon travail et à bientôt.

[edfed]

la recherche de maxima locaux n'a pas besoin de filtrage ni de derivation.
les instructions des µP sont capables de fournir des solutions mois lourdes.
comme une comparaison, une detection de passage par 0, une detection de pente longue, tout ça c'est possible.
et nul besoin de deriver ou filtrer.
juste mettre au point l'algorythme jusqu'a obtention de resultats satisfaisants.

[FR119492]

Salut !

En fait, il n'y a pas besoin de dériver parce que le microprocesseur le fait à ta place. La question est seulement de savoir comment.

Jean-Marc Blanc

[fatenov]

Salut,

La question est seulement de savoir comment.

Si ça a une relation avec comment detecter les maximums, la solution est présentée dans le lien que fournit là-dessus.

Bonne journée.

[Rosa2008]

Bonjour;
Merci à tous! Je vais commencer à implémenter la méthode ss Matlab. Je vous parviendrais lorsque ça roule.
Tous mes encouragements pour vous tous.
Bonne journée.

[Contact2012]

Bonjour;
J’ai le meme pb que Rosa. J’ai besoin de calculer la taille d’un motif dans un signal 1D. J’ai créé sous Matlab la fct suivante pour calculer la fct d’autocorrelation et la taille du motif.

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function [cor,motif]= motifLength1 (S)
%calcul de la fct d'autocorrelation d'un signal mono
X = xcorr(S);
Z= xcov(S);
%maxX = mean(X);
% detection des maxima
% calcul de la dérivee ( la derivee s'annule au maxima )
Y = diff(X);
b = length(Y);
zeroY = [];
for i=2:b-1
    if(Y(i)<0)&&((Y(i+1)==0)||(Y(i+1)>0))
           zeroY= [zeroY;i];
    end
end
x= length(zeroY);
pattern = [];
for i=1:x-1
    length1=zeroY(i+1)-zeroY(i);
    pattern=[pattern,length1];
end;
motif=max(pattern);
cor=X;

Mais, ca me donne des résultats erronés : théoriquement, la taille d’un motif est la distance entre 2 maxima de la fonction d’auto-corrélation. La fonction me donne 234px (au lieu de 0.9 10e4 d’après la courbe)

Je pense que je dois faire le lissage de la fct d’auto-corrélation. Mais comment ? Est-ce quelqu’un peut me donner les cmd Matlab à faire (application d'un filtre,...)?

Merci d’avance.

Salut;
J'ai réalisé un filtrage avec fenetre glissante. Ca m'a donné des résultats satisfaisants pour le signal surlequel je teste , voir :
http://www.developpez.net/forums/d62...o/#post3697458
Mais pas avec d'autres signaux, ca donne des résultats erronés. Donc, ca ne marche pas parfaitememnt.
Merci pour toute suggestion.

[bru.antoine]

Envoyé par pseudocode

Donc l'idée c'est de déplacer progressivement la fenêtre de taille 4 et de relever à chaque fois le maximum dans cette fenêtre: si le maximum est à la 1ere position de fenêtre => c'est un maximum local.

donc si je comprends bien cela veut dire que si toutes les valeurs qui suivent le maximum sont toutes décroissantes respectivement dans la fenêtre alors elle seront toutes considérées comme un maximum local ??? étrange non ou j'ai mal compris l'algorithme décrit dans la réponse de pseudocode.

Quelqu'un peut'il me confirmer que j'ai bien compris l'algo?

Mon problème par des exemple simples :

Exemple 1 :
une courbe sinusoïdale : tous les points après un maximum seront considérés comme des maximums locaux quasiment jusqu'au minimum (dépendant de la taille de la fenêtre ...)

Autre exemple :

Code :

1
2
3
 échantillons   6  8  7  6  5  4  3  2
 idx            1  2  3  4  5  6  7  8

Dans ce cas de figure, les valeurs 8, 7, 6, 5 seront considérées comme des valeurs maximales locales si l'on garde la taille de la fenêtre à 4 comme dans l'exemple de pseudocode. Alors que la réponse attendue était plutôt uniquement 8.

Es-ce bien cela? probablement une des limites des cet algo très simpliste qui peut surement convenir pour certaines courbes mais pas dans mon cas.

Peux-etre devrais-je utiliser une autre méthode comme la fonction findpinks de matlab mais j'ai comme contrainte de devoir faire l'algo en langage C et je sais pas si c'est très simple et/ou possible de faire appel à des fonctions de matlab en C via une interface...

[pseudocode]

Envoyé par bru.antoine

donc si je comprends bien cela veut dire que si toutes les valeurs qui suivent le maximum sont toutes décroissantes respectivement dans la fenêtre alors elle seront toutes considérées comme un maximum local ??? étrange non ou j'ai mal compris l'algorithme décrit dans la réponse de pseudocode.

Quelqu'un peut'il me confirmer que j'ai bien compris l'algo?

Ce n'était pas un algo mais juste une explication du principe de fenêtre glissante.

Effectivement, si on applique seulement le principe que j'ai décrit, ca ne fonctionne pas. Pour que ca fonctionne, il faut appliquer ce principe deux fois : une fois en parcourant les données de gauche à droite puis une fois de droite à gauche. Les points qui sont détectés dans les 2 configurations sont les extrema locaux.

exemple d'implémentation

[bru.antoine]

ton exemple d'algo me semble très bien pour ce que je veux faire ... merci.
par contre j'ai du mal à relier la théorie des fenêtres glissantes avec cet exemple d'implémentation que tu nous fourni...

Juste pour que je comprenne la théorie, dans ton exemple quelle est la dimension de la fenêtre ?
Dim 1 car tu prends la valeur postérieure, puis dim 1 dans l'autre sens avec la valeur antérieure?

[pseudocode]

Envoyé par bru.antoine

ton exemple d'algo me semble très bien pour ce que je veux faire ... merci.
par contre j'ai du mal à relier la théorie des fenêtres glissantes avec cet exemple d'implémentation que tu nous fourni...

Juste pour que je comprenne la théorie, dans ton exemple quelle est la dimension de la fenêtre ?
Dim 1 car tu prends la valeur postérieure, puis dim 1 dans l'autre sens avec la valeur antérieure?

Oui, dans l'exemple c'est une fenêtre de taille 2 : on compare 2 valeurs consécutives pour détecter un extrema. L'avantage c'est qu'avec 2 valeurs il est assez facile de déterminer où est le max/min

Avec une fenêtre plus grande, il faudrait chercher dans la fenêtre ou se situe le max/min comme je le disais dans les posts précédents.