Algorithme recherche d'extremum

[Eric78]

Bonjour

Je ne sait pas trop où poster ce message, donc libre aux modérateurs de le déplacer.

Je suis en train d'élaborer un programme (pour mon TIPE) qui doit retrouver les fondamentales et les harmoniques d'un son (par exemple un accord de guitare). Pour ca, je lis un fichier Wave (donc déja échantilloné), je lui applique la transformée de fourier, je l'affiche sous forme de diagramme. Jusque la pas de problèmes: on distingue parfaitement les pics. Maintenant, j'aimerais analyser les données pour extraire touts les pics, et ensuite déterminer les qui est fondamentale/harmonique. Pour cela, j'ai commencé par éliminer les valeurs en dessous d'un certain seuil, puis récupéré les maximums locaux: par exemple pour le tableau:

[5,8,3,6,15,20,50,25,3,6,12,15, 9,2], on prend un seuil de 10, ce qui donne les tableaux [15,20,50,25] et [12,15], puis je trouve les maximums en parcourant les deux tableaux: 50 et 15.

Cela marche relativement bien, mais malheureusement les valeurs sont souvent plus irrégulières: un exemple:

[5,8,3,15,20,9,25,12,3,2,12,15, 9,16,3]: la mon algo donne comme sous tableaux: [15,20] [25,12] [12,15] [16], mais le problème, c'est que 25 et 20 sont très proches, et correspondent donc au même pic, donc je ne voudrais que 25 comme maximum...

J'ai bien quelques idées, mais peu efficaces (il y a quand même autours de 65000 valeurs...), et pour mon TIPE, j'aimerais quelque chose de plus "éléguant", par exemple, il n'y aurait pas un algorithme de "lissage" des données, qui me donnerait des pics bien définis.

Si vous avez des idées, ca m'aiderais beaucoup!

Eric (n'hésitez pas à me demander des détails, je n'ai surement pas été très clair...)

[cricri]

il me semble que tu devrai lire les 65000 valeur dans l'ordre une par une
a chaque valeur
max=0
while des valeur
si valeur > max then
max =valeur
position= indice des 65000
else on redecend donc valeur d avant = maximum local
tableauresultat(j) =position
j=j+1
max=0
end if
wend

[Eric78]

Hé nan ca serait trop simple Déja, si je fait ca sans enlever des valeurs, je me retrouve avec 30000 maximums car pour les valeurs faibles(les 19/20 des vauleurs sont faibles), ca oscille tout le temps... Et sinon ca ne m'enlève pas le problème des maximums proches...

[cricri]

ok
faut rajouter un facteur de monter ? je m explique passer de 19 a 20 ca ne declenche pas un maximum
passer de 19 a 38 oui ?
normalement pour un vrai maximum le rapport entre le maximum et les points proche doit etre tres grande non ?

[martini_bird]

la mon algo donne comme sous tableaux: [15,20] [25,12] [12,15] [16], mais le problème, c'est que 25 et 20 sont très proches, et correspondent donc au même pic, donc je ne voudrais que 25 comme maximum...

Salut,
juste une question comme ça: est-ce que genre de phénomène peut se reproduire avec 2^16 valeurs?
Ce que je veux dire, c'est qu'échantillonné avec 16 bits, tu devrais avoir une séparation franche des harmoniques, non?

Bon, c'est une idée comme ça, je ne sais pas ce que ça donne sur le terrain.

Je pense aussi à un truc: est-ce que tu n'aurais pas intérêt à tester ton algo sur des signaux simples (somme finie de sinusoïdes) avant de t'attaquer à un accord de guitare dont le spectre est assez complexe?

Cordialement.

[matthias]

Un algorithme de lissage bête et méchant, qui ne marche que dans des cas relativement simple:
remplacer chaque valeur par la moyenne des valeurs qui l'entourent (plus elle même bien sûr).
Cet algo se paramètre en configurant la taille de la fenêtre (prendre dans la moyenne toutes les valeurs dont l'indice est à une distance < d, avec d au choix), et éventuellement en pondérant les valeurs moyennées par leur éloignement.

Cet algo n'est pas mauvais en soi, quoiqu'on puisse faire bien mieux, mais il est rarement utile tout seul.

[matthias]

ah oui, et si tu utilises un algo de lissage, il faut bien faire attention à ce que tes pics réels ne se mélangent pas ....

[Eric78]

J'ai fait une copie d'écran pour que vous voyez un peu à quoi ca ressemble: http://spunky78.free.fr/Image%204.pdf Sur le spectre, tout est bien nette et nickel, mais en fait, c'est pas aussi propre à l'échelle d'une dizaine d'échantillons(c'est à dire du 1/4 de millimetre): surtout sur les "flancs" des pics, et c'est ca qui me fait pas mal de maximums parasites. Je vais essayer quelques lissages pour voir ce que ca donne, merci

[Eric78]

Salut,
juste une question comme ça: est-ce que genre de phénomène peut se reproduire avec 2^16 valeurs?
Ce que je veux dire, c'est qu'échantillonné avec 16 bits, tu devrais avoir une séparation franche des harmoniques, non?

Comme tu peux le voir sur ma copie d'écran, les harmoniques sont bien séparés c'est pas ca le problème: pour une raison obscure, au sein même d'un seul pic, j'ai de temps en temps des valeurs qui retombent (je sais pas trop pourquoi...).

[cricri]

je suis pas un super pro de la musique mais

essaye sur une fenetre glissante de 5hz a 10hz (je sais pas trop)
de trouver un seul max faut qu il depasse un certain seuil
la plus haute barre normalement = le nombre d echantillon non ?

ce qui est au dessus de 1000 hz c est les harmoniques non?
c est calculable en fonction des fondamentale non ?

[Evil.Saien]

Salut,
je comprend pas trop ou est le problème !
Ta fonction temporelle est discrète, donc ton spèctre de Fourier aussi. Tu te retrouve avec un nombre fini de valeurs dans un tableaux et t'aimerais trouver le maximum ! C'est bien ca ?
Si c'est le cas, suffit de faire une boucle sur les valeurs pour déterminer le maximum...
Maintenant je crois que tu cherches les pics locaux. Donc pour ca a moins d'émettre des hypothèses (par exemple prendre seulement une des 2 valeurs si les 2 pics trouvés sont éspacés de moins de 3 echantillons) tu te retrouves avec certains pics très proches en fréquence. Mais le problème c'est qu'en émettant certaines hypothèse de ce type tu peux éventuellement supprimer de vraies infos... De plus en supprimant toutes les valeurs inférieures a 10 tu risques de supprimer des pics locaux pas très intenses mais marquand une harmonique dans les hautes fréquence (et faut bien garder à l'ésprit que souvent les hautes fréquences sont atténuées par les appareils de mesure).
Donc selon moi le plus simple c'est de chercher tout les maximums locaux dans un premier temps, c'est-a-dire toutes les valeurs telles que A(f-1) < A(f) et A(f+1) < A(f). Puis a partir de toutes les fréquences obtenues, conserver uniquement les plus hautes dans un intervale reduit:
si A(f1) > A(f2) et A(f1) > A(f3) avec f1, f2, f3 consécutifs dans le tableau, et f2-f1 < intervale f3-f2 < intervalle alors supprimer f1 et f3.
Sinon f3 et f1 peuvent être des maximum locaux.
Voila

++

[martini_bird]

Comme tu peux le voir sur ma copie d'écran, les harmoniques sont bien séparés c'est pas ca le problème: pour une raison obscure, au sein même d'un seul pic, j'ai de temps en temps des valeurs qui retombent (je sais pas trop pourquoi...).

Salut,

Je vois en effet ton souci: coté algo, je laisse les pros te renseigner...

Mais une idée me passe par la tête: étant donné que c'est un accord de guitare, et que les cordes ne sont jamais accordées à la perfection (du point de vue mathématique), ne serait-ce pas une harmonique du mi grave qui viendrait côtoyer la fondamentale ou une harmonique du mi aigüe?

Je te joins un la de piano pour tester ton algo si tu le souhaites...

Juste une petite remarque encore: tu as enregistré ton accord avec les moyens du bord, ce qui explique qu'il n'y ait pas d'harmoniques >1kHz ?

Cordialement.

[martini_bird]

Hum, si tu veux ma note de piano, il faudra que je te la donne en mp ou par mail, car l'extension .wav n'est pas autorisée pour les pièces jointes.

[Evil.Saien]

Juste une petite remarque encore: tu as enregistré ton accord avec les moyens du bord, ce qui explique qu'il n'y ait pas d'harmoniques >1kHz ?

Pas forcement... Ca depend tout de l'échelle, si elle est logarithmique ou linéaire. J'ai bien l'impression qu'elle est linéaire donc forcément on voit des pics tout petits dans les hautes fréquences !

[martini_bird]

Pas forcement... Ca depend tout de l'échelle, si elle est logarithmique ou linéaire. J'ai bien l'impression qu'elle est linéaire donc forcément on voit des pics tout petits dans les hautes fréquences !

Heu 1kHz, c'est pas vraiment des HF... Une guitare avec un passe-bas à 1kHz, ça sonne vraiment sourd!