Répondre à la discussion
Affichage des résultats 1 à 26 sur 26

Algorithme recherche d'extremum



  1. #1
    Eric78

    Algorithme recherche d'extremum


    ------

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

    -----
    Pour un TPE sur la cryptographie ou les trous noirs, allez voir mon profil.

  2. Publicité
  3. #2
    cricri

    Re : Algorithme recherche d'extremum

    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

  4. #3
    Eric78

    Re : Algorithme recherche d'extremum

    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...
    Pour un TPE sur la cryptographie ou les trous noirs, allez voir mon profil.

  5. #4
    cricri

    Re : Algorithme recherche d'extremum

    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 ?

  6. #5
    martini_bird

    Re : Algorithme recherche d'extremum

    Citation Envoyé par Eric78
    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.

  7. A voir en vidéo sur Futura
  8. #6
    matthias

    Re : Algorithme recherche d'extremum

    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.

  9. Publicité
  10. #7
    matthias

    Re : Algorithme recherche d'extremum

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

  11. #8
    Eric78

    Re : Algorithme recherche d'extremum

    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
    Pour un TPE sur la cryptographie ou les trous noirs, allez voir mon profil.

  12. #9
    Eric78

    Re : Algorithme recherche d'extremum

    Citation Envoyé par martini_bird
    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...).
    Pour un TPE sur la cryptographie ou les trous noirs, allez voir mon profil.

  13. #10
    cricri

    Re : Algorithme recherche d'extremum

    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 ?

  14. #11
    Evil.Saien

    Re : Algorithme recherche d'extremum

    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

    ++
    Mon psychiatre, pour quinze mille francs, il m'a débarrassé de ce que j'avais : quinze mille francs

  15. #12
    martini_bird

    Re : Algorithme recherche d'extremum

    Citation Envoyé par Eric78
    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.

  16. Publicité
  17. #13
    martini_bird

    Re : Algorithme recherche d'extremum

    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.

  18. #14
    Evil.Saien

    Re : Algorithme recherche d'extremum

    Citation Envoyé par martini_bird
    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 !
    Mon psychiatre, pour quinze mille francs, il m'a débarrassé de ce que j'avais : quinze mille francs

  19. #15
    martini_bird

    Re : Algorithme recherche d'extremum

    Citation Envoyé par Evil.Saien
    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!

  20. #16
    Evil.Saien

    Re : Algorithme recherche d'extremum

    Citation Envoyé par martini_bird
    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 !
    Mon psychiatre, pour quinze mille francs, il m'a débarrassé de ce que j'avais : quinze mille francs

  21. #17
    Evil.Saien

    Re : Algorithme recherche d'extremum

    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...
    Mon psychiatre, pour quinze mille francs, il m'a débarrassé de ce que j'avais : quinze mille francs

  22. #18
    cricri

    Re : Algorithme recherche d'extremum

    Citation Envoyé par Evil.Saien
    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

  23. Publicité
  24. #19
    martini_bird

    Re : Algorithme recherche d'extremum

    Citation Envoyé par cricri
    surement parce qu une note a 200 Hz c est hyper grave
    Je suis pas si sûr: le la3 est à 220Hz...

  25. #20
    Eric78

    Re : Algorithme recherche d'extremum

    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
    Pour un TPE sur la cryptographie ou les trous noirs, allez voir mon profil.

  26. #21
    martini_bird

    Re : Algorithme recherche d'extremum

    Salut,

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

  27. #22
    Evil.Saien

    Re : Algorithme recherche d'extremum

    Tu pourrais déja passer en échelle logarithmique, ce qui te permettrais de garder les harmoniques...
    Mon psychiatre, pour quinze mille francs, il m'a débarrassé de ce que j'avais : quinze mille francs

  28. #23
    Eric78

    Re : Algorithme recherche d'extremum

    Citation Envoyé par martini_bird
    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).
    Pour un TPE sur la cryptographie ou les trous noirs, allez voir mon profil.

  29. #24
    Evil.Saien

    Re : Algorithme recherche d'extremum

    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...
    Mon psychiatre, pour quinze mille francs, il m'a débarrassé de ce que j'avais : quinze mille francs

  30. Publicité
  31. #25
    Eric78

    Re : Algorithme recherche d'extremum

    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
    Pour un TPE sur la cryptographie ou les trous noirs, allez voir mon profil.

  32. #26
    popoye

    Re : Algorithme recherche d'extremum

    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)

Sur le même thème :

Discussions similaires

  1. A la recherche d'un algorithme ...
    Par LocalStone dans le forum Mathématiques du supérieur
    Réponses: 4
    Dernier message: 14/11/2007, 17h59
  2. Recherche d’un algorithme
    Par Nac dans le forum Archives
    Réponses: 0
    Dernier message: 29/10/2007, 20h24
  3. Recherche d’un algorithme
    Par Nac dans le forum Mathématiques du supérieur
    Réponses: 0
    Dernier message: 29/10/2007, 15h57
  4. algorithme
    Par maribel dans le forum Logiciel - Software - Open Source
    Réponses: 9
    Dernier message: 25/06/2006, 17h29
  5. notion d'extremum (2 variable)
    Par nabbla dans le forum Mathématiques du supérieur
    Réponses: 3
    Dernier message: 29/08/2004, 10h21