Algorithme recherche d'extremum

[invite3f53d719]

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

[invitedebe236f]

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

[invite3f53d719]

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

[invitedebe236f]

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 ?

[A voir en vidéo sur Futura]

[invite4793db90]

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.

[invitec314d025]

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.

[invitec314d025]

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

[invite3f53d719]

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

[invite3f53d719]

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

[invitedebe236f]

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 ?

[inviteeecca5b6]

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

++

[invite4793db90]

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.

[invite4793db90]

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.

[inviteeecca5b6]

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 !

[invite4793db90]

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!

[inviteeecca5b6]

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

Ah oui en effet, j'avais mal lu
Je sais pas d'ou ca vient alors... Autant pour moi !

[inviteeecca5b6]

En regardant mieux le graph, je me demande si c'est pas des dizaines de Hz qu'on voit en bas... Parce que le maximum est de 2000, donc 20 kHz me semblerait plus logique non ?
Il fadrait que l'interessé nous dise quelle échelle c'est...

[invitedebe236f]

En regardant mieux le graph, je me demande si c'est pas des dizaines de Hz qu'on voit en bas... Parce que le maximum est de 2000, donc 20 kHz me semblerait plus logique non ?
Il fadrait que l'interessé nous dise quelle échelle c'est...

surement parce qu une note a 200 Hz c est hyper grave

[invite4793db90]

surement parce qu une note a 200 Hz c est hyper grave

Je suis pas si sûr: le la3 est à 220Hz...

[invite3f53d719]

C'est échellonné en Hz. D'ailleurs les petites boites en bas de l'écran donne les fondamentales (81,75Hz, 109,3Hz etc), ce qui correspond bien aux cordes à vide théorique. J'ai résolu mon problème en rajoutant divers tests supplémentaires pour la séléction des maximums: Par exemple, s'il y en a deux très proches, on prend le plus grand, ainsi que d'autres petits bricolages pas très éleguants mais bon... et j'ai aussi élevé la valeur de seuil, mais cela m'enlève des harmoniques...

Maintenant le programme arrive à retrouver correctement toutes les fondamentales, et classe les harmoniques correspondantes, donc j'ai atteint mon but Merci pour vos idées diverses! Si vous en avez d'autres concernant l'évolution de mon programme je suis ouvert.

Eric

[invite4793db90]

Salut,

par curiosité, tu as essayé avec un accord?

[inviteeecca5b6]

Tu pourrais déja passer en échelle logarithmique, ce qui te permettrais de garder les harmoniques...

[invite3f53d719]

par curiosité, tu as essayé avec un accord?

Bah bien sur, le spectre que vous voyez est un "accord": les six cordes à vide de ma gratte:

(en théorie)
f(Hz)
mi: 82,4
la: 110
re: 146,8
sol: 196
si: 246,9
mi: 329,5

Pour Evil.Saien: Je ne pense pas que ca soit bien de passer en échelle log: La guitare n'emmet pas vraiment au dessus de 2KHz, ou alors c'est vraiment très faible. De plus, c'est pratique de rester à echelle linéaire pour distinger à l'oeil nu les harmoniques (situés à des distance double, triples... de la fondamentale ). Et puis de toute façon, le programme traite toutes les données, y compris celles non affichés, donc jusqu'à 22KHz (celles au dessus n'on pas de sens à cause de shannon).

[inviteeecca5b6]

Salut,
en fait c'est pas des fréquences que je voulais parler, mais de l'amplitude. Souvent c'est commode de les exprimer en dB parce que une grande différence d'amplitude dans les mesure se traduit par des différences moins grandes pour l'oreille (vu que l'oreille agit un peu de manière logarithmique).
D'ailleurs dans les diagrames de Bode l'amplitude est en dB, l'oeil entrainé voit tout de suite le comportement de la fonction...

[invite3f53d719]

Ha oui effectivement c'est pas bête! Surtout que ca m'embettait de me trimbaler des valeurs genre 12545612312... Je vais changer ca tout de suite. Merci

[invitee824ff2d]

Un truc béte et méchant,
Déjà tu précise pas comment du passe du temporel vers fréquenciel. Suivant la technique que tu utilise ya différentes solution, perso je pense que ca serai pas mal de dérivé, chaque point ou la derivé s'anulle et un extremum, et dans ton cas, les extremums s'alternent mini/maxi, ta des solution de moyennage pour rendre un résultat plus compréhenssible a l'écran.
suivant comment du fait ta correspondance temps/fréquence c'est pas possible donc plus d'info seraient utiles (genre ton code)