IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Caml Discussion :

Implémentation d'un algorithme de FFT.


Sujet :

Caml

  1. #1
    Candidat au Club
    Profil pro
    Inscrit en
    Octobre 2008
    Messages
    11
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Octobre 2008
    Messages : 11
    Points : 2
    Points
    2
    Par défaut Implémentation d'un algorithme de FFT.
    Bonjour à tous,

    Actuellement étudiant en prépa Maths Spé, je prépare un sujet de recherche à présenter aux concours, à la fin de l'année.
    J'ai voulu m'orienter vers un projet physique/informatique... En particulier, j'aimerais implémenter un algorithme pouvant calculer une transformation de Fourier à partir d'un signal audio.
    Peut-être n'ai-je pas encore conscience de ce à quoi je m'attaque, me direz-vous... En fait, j'aimerais en profiter pour analyser du point de vue mathématique différentes méthodes algorithmiques pour approximer fourièrement (!) un signal qui n'est pas défini à tout instant, de moins l'infini à plus l'infini, ce qui fait que finalement, même si mon projet Caml n'aboutit pas.
    Pour être précis, voici ma principale question :
    Y a-t-il une possibilité d'acquisition d'un signal audio par Caml ? J'entends par là : puis-je lui faire analyser le contenu d'un fichier wav, dans l'optique de lui appliquer une FFT ?
    J'ai quelques mois pour m'en charger... Et certes que quelques jours pour abandonner.

    Merci de votre aide !

  2. #2
    Rédacteur/Modérateur

    Avatar de gorgonite
    Homme Profil pro
    Ingénieur d'études
    Inscrit en
    Décembre 2005
    Messages
    10 322
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 39
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur d'études
    Secteur : Transports

    Informations forums :
    Inscription : Décembre 2005
    Messages : 10 322
    Points : 18 679
    Points
    18 679
    Par défaut
    je pense qu'il n'y aura aucun soucis pour calculer une FFT, mais en revanche j'ai un doute pour l'acquisition depuis un WAV

    mieux faut utiliser une lib c pour l'import et interfacer avec OCaml
    http://anne-pacalet.developpez.com/t...-cpp-et-ocaml/
    Evitez les MP pour les questions techniques... il y a des forums
    Contributions sur DVP : Mes Tutos | Mon Blog

  3. #3
    Membre éprouvé
    Avatar de InOCamlWeTrust
    Profil pro
    Inscrit en
    Septembre 2006
    Messages
    1 036
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Septembre 2006
    Messages : 1 036
    Points : 1 284
    Points
    1 284
    Par défaut
    Tu peux bien-entendu analyser un WAV, mais uniquement si tu possèdes le format de fichier. Peut-être sur internet...

    D'un autre côté, pour avoir travaillé sur le sujet, laisse-moi te dire que la FFT n'est pas une reconstruction de la fonction sous-jacente. En fait, il faut voir la FFT comme un gros vecteur donnant certaines informations sur le signal ; mais en aucun cas, les coefficients calculés grâce à la FFT ne correspondent à de vrais coefficients de Fourier.

    En réalité, on utilise la FFT pour tirer des informations instantannées sur un certain signal, comme une mesure de l'amplitude de telle fréquence dans le signal à instant donné, et non la valeur de l'amplitude. D'ailleurs, il existe plusieurs définitions de FFT, aucune ne donnant le même résultat... et pour cause, elles sont toutes définies à une mesure près. Passer de l'une à l'autre revient à passer d'une mesure à une autre.

    Ca c'est pour le côté théorique.

    Pour le côté pratique... il faut savoir que :

    1- 99% des infos sur internet sont préparées par des physiciens... et ça, c'est pas rien de le dire...

    2- qu'il s'agit d'un sujet relativement bateau... donc il faudra vraiment que tu apportes un regard personnel pour convaincre

    3- la FFT, tout le monde croit maîtriser le sujet...

    4- tu perdras un temps fou à mouliner des infos de qualité ultra-médiocre, et les bons papiers sur le sujet ne sont vraiment pas légion

    5- il existe une pléthore d'algorithmes, mais en réalité seulement quelques uns qui soient vraiment utilisables, et leur implantation n'est pas gagnée d'avance, même si elle n'est pas insurmontable. En clair, il te faudra programmer beaucoup mieux que naïvement.
    When Colt produced the first practical repeating handgun, it gave rise to the saying God created men, but Colt made them equal.

  4. #4
    Candidat au Club
    Profil pro
    Inscrit en
    Octobre 2008
    Messages
    11
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Octobre 2008
    Messages : 11
    Points : 2
    Points
    2
    Par défaut
    D'abord un grand merci pour votre réactivité !
    En fait, ce que je voudrais vraiment faire, ce serait étudier différents types d'analyse spectrale et leur application sur un domaine particulier : la reconnaissance de notes... Par exemple, je sais qu'une foultitude de logiciels gratuits sur Internet font office d'accordeur de Guitare en passant une FFT au signal reçu par le micro. Le principe n'est pas d'une grande difficulté théorique : il ne s'agit que de déterminer la fréquence qui a la plus grande amplitude. Mon idée était d'aborder le problème en mettant en évidence certains problèmes, ou plutôt certaines limitations de la FFT, pour ensuite dériver vers un domaine assez récent en analyse spectrale, et qu'on ne voit pas du tout en prépa, la transformée en ondelettes...
    Grand InOCamlWeTrust, je n'ai pas compris ta première phrase : "posséder" un format de fichier ? Autrement, y a-t-il une autre forme de signal que je pourrais acquérir plus facilement ?
    Autrement, gorgonite me propose de passer par C et OCaml (Ça tombe bien, il existe déjà plein de programmes adaptés en C.), mais je n'y connais rien... À la limite, peut-être devrais-je essayer de travailler sous OCaml (Et je connais ton point de vue là dessus, modéro ^^), mais je crains de m'y perdre rapidement...
    Encore merci.

  5. #5
    Membre éprouvé
    Profil pro
    Inscrit en
    Avril 2007
    Messages
    832
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Avril 2007
    Messages : 832
    Points : 1 104
    Points
    1 104
    Par défaut
    Si c'est la question, utiliser OCaml au lieu de Caml light sera certainement une bonne idée, et comme c'est facile de passer de l'un à l'autre, tu ne devrais pas t'en priver.

    gorgonite a suggéré une interface C pour utiliser une lib de lecture des .wav. Je pense que tu n'en as en fait pas besoin, il existe une libsndfile-ocaml qui devrait répondre à tes besoins : http://www.mega-nerd.com/libsndfile/Ocaml/Sndfile.html.

    PS : par "posséder le format", il entend que tu dois avoir accès aux spécifications du format, pour savoir comment les informations y sont stockées.

  6. #6
    Membre éprouvé
    Avatar de InOCamlWeTrust
    Profil pro
    Inscrit en
    Septembre 2006
    Messages
    1 036
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Septembre 2006
    Messages : 1 036
    Points : 1 284
    Points
    1 284
    Par défaut
    Citation Envoyé par Mp-X. Voir le message
    D'abord un grand merci pour votre réactivité !
    En fait, ce que je voudrais vraiment faire, ce serait étudier différents types d'analyse spectrale et leur application sur un domaine particulier : la reconnaissance de notes... Par exemple, je sais qu'une foultitude de logiciels gratuits sur Internet font office d'accordeur de Guitare en passant une FFT au signal reçu par le micro. Le principe n'est pas d'une grande difficulté théorique : il ne s'agit que de déterminer la fréquence qui a la plus grande amplitude. Mon idée était d'aborder le problème en mettant en évidence certains problèmes, ou plutôt certaines limitations de la FFT, pour ensuite dériver vers un domaine assez récent en analyse spectrale, et qu'on ne voit pas du tout en prépa, la transformée en ondelettes...
    Grand InOCamlWeTrust, je n'ai pas compris ta première phrase : "posséder" un format de fichier ? Autrement, y a-t-il une autre forme de signal que je pourrais acquérir plus facilement ?
    Autrement, gorgonite me propose de passer par C et OCaml (Ça tombe bien, il existe déjà plein de programmes adaptés en C.), mais je n'y connais rien... À la limite, peut-être devrais-je essayer de travailler sous OCaml (Et je connais ton point de vue là dessus, modéro ^^), mais je crains de m'y perdre rapidement...
    Encore merci.
    En effet, pour ce que tu veux faire, il n'y a pas de problèmes.

    Le seul truc, c'est de savoir lire les .wav, mais je ne suis pas sûr que ce soit compliqué.

    Pour info, le "son", ça n'existe pas en informatique : il n'y a que des suites d'octets. Point. Pour faire ce que tu veux, tu peux acquérir ton "son" avec le logiciel de ton choix, et ensuite l'analyser avec OCaml.
    When Colt produced the first practical repeating handgun, it gave rise to the saying God created men, but Colt made them equal.

  7. #7
    Candidat au Club
    Profil pro
    Inscrit en
    Octobre 2008
    Messages
    11
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Octobre 2008
    Messages : 11
    Points : 2
    Points
    2
    Par défaut
    Merci pour vos réponses complètes... Je vais donc devoir essayer de comprendre la structure d'un fichier wav, mais je m'y attendais déjà.
    Au boulot, maintenant ^^
    On va faire joujou avec OCaml...

  8. #8
    Candidat au Club
    Profil pro
    Inscrit en
    Octobre 2008
    Messages
    11
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Octobre 2008
    Messages : 11
    Points : 2
    Points
    2
    Par défaut
    Hiho,

    Depuis mon dernier message, j'ai eu le temps de comprendre le fonctionnement de différentes méthodes d'analyse spectrale à présenter, et il est maintenant temps d'implémenter l'algorithme de FFT en question...
    Pour rappel, la FFT est le pendant algorithmique de la transformée de Fourier discrète, applicable à un signal sous forme d'échantillons (Donc non continu.), ce qui correspond parfaitement au format wav.
    Problème : interviennent dans la formule des calculs d'exponentielles, à l'intérieur des sommes... Comment les retranscrire sous Caml ? Enfin, j'imagine que les autres algorithmes, que ce soit en C ou autre, n'utilisent pas non plus de vraie fonction exponentielle, mais je n'arrive pas à trouver de source suffisamment commentée pour que je sois capable d'en comprendre le principe...

    Autrement, quant à la structure des fichiers wav... Je n'ai réussi à utiliser aucun des liens que vous m'avez proposé plus haut.
    Groumf.
    Mais c'était en fait très simple car... On code ce qu'on voit.
    Pour info : http://col2000.free.fr/vocal/formawav.htm
    En ouvrant un fichier wav avec un éditeur hexadécimal, on retrouve "l'en-tête" du fichier tel qu'il est décrit sur cette page... Sur le reste du fichier, chaque octet correspond en fait à un échantillon, codé entre 00h et FFh, avec pour valeur moyenne 80h, 128 en décimal (Donc en fait, ça correspond à tout décaler pour placer un "zéro imaginaire" en 128 et dire que les valeurs inférieures sont à considérer comme négatives, idem mut mut pour les valeurs supérieures.). Il suffira dès lors de considérer le fichier wav comme un tableau de données, auquel je pourrai appliquer ma FFT...

    Second problème : comment puis-je "importer" un fichier wav pour un traitement Caml ? Je veux dire : puis-je demander à Caml d'ouvrir un fichier et de lui dire par exemple de regarder l'octet n°2009 (En décimal, siouplaît.) et de m'en retourner la valeur, directement en décimal ? Évidemment, si Caml peut au moins me dire qu'il s'agit par exemple de FFh, il me suffira alors de créer un petit filtrage, mais pour gagner en complexité (Dans la mesure où j'aurai plusieurs milliers d'échantillons à traiter...), s'il pouvait directement me sortir un entier qui sera directement exploitable en calcul...

    J'oubliais... Pour ce que je veux faire, OCaml ne me semble pas un passage obligé... L'importation de fichier est-elle possible avec Caml Light ?

    Voilà voilà... Ne vous sentez pas obligé de répondre, mais je vous serais énormément reconnaissant de votre aide.

  9. #9
    Membre éprouvé
    Avatar de InOCamlWeTrust
    Profil pro
    Inscrit en
    Septembre 2006
    Messages
    1 036
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Septembre 2006
    Messages : 1 036
    Points : 1 284
    Points
    1 284
    Par défaut
    Citation Envoyé par Mp-X. Voir le message
    Voilà voilà... Ne vous sentez pas obligé de répondre, mais je vous serais énormément reconnaissant de votre aide.
    Vu le nombre de bêtises, oui un peu... Pourtant t'es en MP (* ?) ?

    Pour commencer, un nombre, c'est un nombre. Point. L'écrire en octal, binaire, morse ou hexadécimal, on s'en fout. Ce n'est qu'une représentation. C'est comme si je te montrais une chèvre en photo, et la même sur une deuxième photo. Ca reste la même chèvre, et on pourra regarder trente-six photos d'elle, rien n'y fera, ce sera toujours la même chèvre.

    Exercice intéressant Ecrire les théorèmes d'analyse vus en cours en octal.

    Ensuite, les fichiers WAV contiennent tous des données sur 16 bits. 16 bits, ça fait 2 octets, et ça veut surtout dire que tu peux coder environ 30 000 niveaux de pression atmosphérique, en positif comme en négatif. C'est pour celà que les lecteurs 16 bits déforment moins le signal que les lecteurs 1, 2 ou 24 bits, même si quelques "audiophiles" qui n'y connaissent rien continuent de croire en 2008 que plus il y a de bits, mieux c'est.

    Pour lire un fichier, je t'invite à lire la documentation de référence ici :
    http://caml.inria.fr/pub/docs/manual...ervasives.html
    General input/output functions

    La racine du document est là :
    http://caml.inria.fr/pub/docs/manual-ocaml/index.html

    Quand tu lis dans un fichier, tu le lis comme si c'était une grande chaîne de caractères. Dans ton cas à toi, il te faudra lire les octets un par un (donc caractère par caractère), les transformer en int grâce à int_of_char. Tu récupères deux octets (des int), o_b de poids faible et o_h de poids fort. Pour avoir ton entier n, tu fais...

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
     
    let n = (o_h lsl 8) lor o_b in
    ...
    Je te laisse méditer...

    Pour connaître lequel des deux est le poids faible ou fort, il faut lire les spécifications du format WAV.

    Attention Dû au fait que les fichiers WAV sont stéréo, en général, le signal que tu traiteras peut ne pas être du tout ce que tu crois. Je t'invite à te renseigner un peu plus sur le sujet. Ceci n'a rien à voir avec le fait que ton micro soit stéréo ou mono.

    Ensuite, les formules de FFT sont classiquement données en complexe. OCaml possède un module Complex.
    http://caml.inria.fr/pub/docs/manual...f/Complex.html

    Tu trouveras tout là-dedans, entre autres l'exponentielle. N'oublie pas d'en prendre la partie réelle, à la fin...

    Tu as aussi les fonctions réelles usuelles...
    http://caml.inria.fr/pub/docs/manual...ervasives.html

    Dernière chose, que je t'ai déjà dite dans un autre message. Programmer une FFT qui marche plus ou moins, ce n'est pas facile. Entre autres, si l'algorithme s'écrit très bien "à la main", surtout pour des physiciens, il se programme beaucoup moins aisément. Sois-en conscient.
    When Colt produced the first practical repeating handgun, it gave rise to the saying God created men, but Colt made them equal.

  10. #10
    Candidat au Club
    Profil pro
    Inscrit en
    Octobre 2008
    Messages
    11
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Octobre 2008
    Messages : 11
    Points : 2
    Points
    2
    Par défaut
    Merci pour ta réponse...
    Quand tu dis :
    Citation Envoyé par InOCamlWeTrust Voir le message
    Ensuite, les fichiers WAV contiennent tous des données sur 16 bits. 16 bits, ça fait 2 octets, et ça veut surtout dire que tu peux coder environ 30 000 niveaux de pression atmosphérique, en positif comme en négatif.
    Hm... Je ne l'ai dit nulle part, mea culpa... J'ai décidé de me limiter aux fichiers wav échantillonés sur 8 bits, à 8000 kHz, et en mono... La qualité sonore est résolument pourrie, mais d'une part, le codage d'un échantillon sur un octet me facilite la tâche, d'autre part, l'échantillonage à 8000 kHz limite le nombre de calculs à effectuer, et le mono me limite les surprises (Je te remercie d'ailleurs d'avoir pensé à me mettre en garde à ce propos.).
    En fait, j'avais l'impression que ma présentation du fichier wav était correcte, dans la mesure où à l'aide d'un éditeur hexadécimal et de la description du format wav dont j'ai donné le lien plus haut, j'ai pu manuellement représenter un sinus de période 1/400 s (Pour que cela tombe juste, au niveau de l'échantillonage à 8000 Hz.) en entrant une vingtaine d'échantillons, puis le recopier plusieurs fois afin d'écouter le résultat.
    Mais évidemment, quand on ne précise pas dans quelles conditions on se place, c'est faux... Désolé, sincèrement.
    Bon, j'espère ne plus déranger davantage, tous tes bons liens seront certainement plus que suffisants.
    Encore merci.

  11. #11
    Membre éprouvé
    Avatar de InOCamlWeTrust
    Profil pro
    Inscrit en
    Septembre 2006
    Messages
    1 036
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Septembre 2006
    Messages : 1 036
    Points : 1 284
    Points
    1 284
    Par défaut
    Effectivement, c'est plus clair comme ça.

    Il te faudra peut-être complier avec ocamlopt, si ton programme n'est pas assez rapide. Deux possibilités si t'es sous Windows (les autres, pas de problème) : ou t'installes MinGW et ça marche tout de suite, ou t'installes Linux (un Live CD sans installation, ça peut le faire aussi...) et ça marchera comme sur des roulettes...
    When Colt produced the first practical repeating handgun, it gave rise to the saying God created men, but Colt made them equal.

  12. #12
    Candidat au Club
    Profil pro
    Inscrit en
    Octobre 2008
    Messages
    11
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Octobre 2008
    Messages : 11
    Points : 2
    Points
    2
    Par défaut
    Salut à tous !

    Cinq mois plus tard...
    J'ai donc effectué toute mon étude théorique, terminé mes essais de différents algorithmes en les programmant sur le logiciel de calcul formel Mathematica, pour sa flexibilité et la possibilité de visualiser tous les résultats de manière quasi-immédiate. Par contre, pour le temps de calcul, c'est franchement pas ça (Dans les trente secondes pour une transformée de Fourier... rapide sur un échantillon de 1024 éléments.). Du coup, j'ai tout réécrit en OCaml (En fait, ça n'a pas été trop dur de migrer depuis Caml Light... Il n'y a que la notation Module.fonction qui surprend une minute au départ, c'est sympa !) et le temps de calcul passe à 3 secondes... Intéressant

    Au cas où quelqu'un serait intéressé par le sujet, je vous laisse là une partie de ce que j'ai écrit en OCaml :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
     
    (* On commence par introduire une valeur approchée de Pi, puis on crée deux tableaux de données de manière artificielle, de façon à simuler un enregistrement quelconque. *)
     
    let pi = 3.141592654 ;;
     
    let la1024 = Array.make 1024 0. ;;
    for i=0 to 1023 do
      la1024.(i) <- sin (2.*.pi*.110.*.(float_of_int i)/.500.)
    done
    ;;
     
    let la2048 = Array.make 2048 0. ;;
    for i=0 to 2043 do
      la2048.(i) <- sin (2.*.pi*.110.*.(float_of_int i)/.500.)
    done
    ;;
     
    (* Fonction renvoyant l'indice correspondant à l'élément maximal du tableau. *)
     
    let ind_max t =
      let l = Array.length t
      and ind = ref 0
      in
        for i = 0 to l-1 do
          if t.(i) > t.(!ind) then
            ind := i ;
        done ;
        !ind
    ;;
     
    (* Algorithme récursif de la FFT. *)
     
    let calcx t k =
      let l = Array.length t
      and m2ipik = {Complex.re = 0. ; Complex.im = -.2.*.pi*.(float_of_int k)}
      in
        let rec recx d p s =
          if p==l then
            {Complex.re = t.(d) ; Complex.im = 0.}
          else (
            let xp = recx d (2*p) (s/.2.)
            and xi = recx (d+p) (2*p) (s/.2.)
            and expk = Complex.exp (Complex.div m2ipik {Complex.re = s ; Complex.im = 0.})
            in
              Complex.add xp (Complex.mul expk xi) )
        in
          recx 0 1 (float_of_int l)
    ;;
     
     
    let creefft t =
      let l = Array.length t
      in
        let res = Array.make (l/2) 0.
        in
          for k = 0 to l/2-1 do
            res.(k) <- Complex.norm (calcx t k)
          done ;
          res
    ;;
     
    (* Finalement, quand on détermine l'indice où |calcX| est maximal, il faut multiplier ce nombre par (fréquence d'échantillonnage)/(taille du tableau). *)
     
    let note ech taille freq_ech = (ind_max (creefft ech))*freq_ech/taille ;;
     
    (* Test avec un la 880Hz *)
     
    let son = Array.make 1024 0. ;;
    for i=0 to 1023 do
      son.(i) <- sin (2.*.pi*.880.*.(float_of_int i)/.8000.)
    done
    ;;
     
    note son 1024 8000 ;;
     
    (* On reconnaît à peu de choses près un signal à 880 Hz... *)
    Du reste... J'ai une dernière fois besoin de votre aide.
    L'acquisition de fichiers extérieurs se fait de manière... facile en Mathematica (Il y a une fonction dédiée.), mais en OCaml...

    Pour résumer, l'algorithme que je souhaiterais programmer devrait, à partir d'une adresse type "C:/Test/Fichier.dev" placer dans un tableau créé pour l'occasion les entiers entre 0 et 255 associés à chaque octet du fichier.

    Voici ce que j'ai... tenté d'écrire :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
     
    let acquisition fichier taille =
      let echantillon = open_in fichier
      in
        let resultat = Array.make taille 0
        in
          for i = 0 to (taille-1) do
            resultat.(i) <- input_byte echantillon
          done ;
        resultat ;;
     
    (* Ce qui renvoie : val acquisition : string -> int -> int array = <fun> *)
    Par exemple, je m'attends à ce qu'en entrant
    acquisition "C:/40Hz.wav" 1000
    on me renvoie le tableau des mille premières valeurs dans le fichier 40Hz.wav...
    Problème, si en me limitant à des petites valeurs de "taille" comme 1, 2, et même 197... je me retrouve constamment avec cette erreur : "Exception: End_of_file.", dès que je tente 198 et au-delà, comme si... j'avais tout simplement atteint la fin du fichier en question. Et pourtant, mon fichier fait plusieurs milliers d'octets. Du coup, je n'arrive pas à comprendre pourquoi la fonction cesse tout simplement de tourner à partir d'un certain rang...

    Vous est-il déjà arrivé le même problème ?

  13. #13
    alex_pi
    Invité(e)
    Par défaut
    Je n'ai pas particulièrement suivi la discussion ni regardé le code, mais 3s pour calculer une FFT sur 1000 éléments, ça me semble *extrêmement* lent !

  14. #14
    Membre éprouvé
    Avatar de Cacophrene
    Homme Profil pro
    Biologiste
    Inscrit en
    Janvier 2009
    Messages
    535
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Royaume-Uni

    Informations professionnelles :
    Activité : Biologiste

    Informations forums :
    Inscription : Janvier 2009
    Messages : 535
    Points : 1 125
    Points
    1 125
    Par défaut
    Salut !

    Citation Envoyé par alex_pi
    Je n'ai pas particulièrement suivi la discussion ni regardé le code, mais 3s pour calculer une FFT sur 1000 éléments, ça me semble *extrêmement* lent !
    +1. Peut-être que c'est une mesure faite dans le toplevel ?

    Citation Envoyé par Mp-X.
    Pour résumer, l'algorithme que je souhaiterais programmer devrait, à partir d'une adresse type "C:/Test/Fichier.dev" placer dans un tableau créé pour l'occasion les entiers entre 0 et 255 associés à chaque octet du fichier.
    Dans tous les cas il faut que open_in soit suivi de close_in. Pour le format lui-même, est-ce un format binaire (diff. mode texte) ? Dans ce cas il faut remplacer open_in par open_in_bin. Tout ça dépend bien sûr des caractéristiques du format wav (que je ne connais mal).

    Autre remarque moins générale : je suis presque sûr que tu passeras plus de temps à lire le fichier qu'à le traiter par ton algo de FFT. En général il faut se méfier des entrées/sorties sur les fichiers parce qu'elles sont lentes. Il est souvent préférable de lire le fichier en blocs et non octet par octet. C'est pour ça (c'est un exemple, je ne pense pas qu'il te serve dans ce cadre-ci) qu'il vaut mieux utiliser Scanf.Scanning.from_file au lieu du classique Scanf.fscanf pour lire un fichier, surtout quand il est volumineux. M'est avis que c'est pareil avec input_byte.

    Voici un exemple vite fait en mode texte. Cette fonction renvoie un buffer que l'on peut ensuite transformer en tableau ou liste d'entiers. Attention ce code suppose que le fichier file existe. Pour les fichiers binaires il faut adapter un petit peu.
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    let read file =
      let ich = open_in file in
      let len = in_channel_length ich in
      let buf = Buffer.create len in
      Buffer.add_channel buf ich len;
      close_in ich;
      buf
    Cordialement,
    Cacophrène

  15. #15
    Membre éprouvé
    Profil pro
    Inscrit en
    Avril 2007
    Messages
    832
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Avril 2007
    Messages : 832
    Points : 1 104
    Points
    1 104
    Par défaut
    Une petite remarque qui saute aux yeux dans tes premières lignes de code : au lieu d'écrire pi à la main, tu peux utiliser l'expression (que je trouve plus fiable) "4. *. atan 1.".

    Pour lire des données dans un protocole binaire, tu peux essayer Bitstring, une bibliothèque doublée d'une extension syntaxique faite exactement pour cela. J'ai écrit un parser de fichiers MIDI avec il y a quelques jours et c'est assez agréable à utiliser (du fait du filtrage de motifs sur l'entrée de ton fichier).
    La documentation est bonne (API documentation en bas) mais ce n'est pas forcément très facile à installer/compiler si tu n'as pas l'habitude et/ou est sous Windows.

  16. #16
    Membre éprouvé
    Avatar de Cacophrene
    Homme Profil pro
    Biologiste
    Inscrit en
    Janvier 2009
    Messages
    535
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Royaume-Uni

    Informations professionnelles :
    Activité : Biologiste

    Informations forums :
    Inscription : Janvier 2009
    Messages : 535
    Points : 1 125
    Points
    1 125
    Par défaut
    Salut !

    Citation Envoyé par bluestorm
    Pour lire des données dans un protocole binaire, tu peux essayer Bitstring, une bibliothèque doublée d'une extension syntaxique faite exactement pour cela. J'ai écrit un parser de fichiers MIDI avec il y a quelques jours et c'est assez agréable à utiliser (du fait du filtrage de motifs sur l'entrée de ton fichier).
    Diable, oui, c'est fort sexy ça, et ça m'intéresse aussi pas mal.
    Merci pour l'info.

    Cordialement,
    Cacophrène

  17. #17
    Candidat au Club
    Profil pro
    Inscrit en
    Octobre 2008
    Messages
    11
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Octobre 2008
    Messages : 11
    Points : 2
    Points
    2
    Par défaut
    Merci beaucoup pour ce bon lien vers bitstring : en effet, il est possible que je perde beaucoup de temps, dans mon idée originale, à lire le fichier binaire...
    Merci aussi pour l'idée de multiplier par quatre Arctan(Pi)
    Bon, je vais devoir essayer de comprendre comment utiliser bitstring, maintenant...

  18. #18
    Membre éprouvé
    Profil pro
    Inscrit en
    Avril 2007
    Messages
    832
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Avril 2007
    Messages : 832
    Points : 1 104
    Points
    1 104
    Par défaut
    Si tu n'as pas envie de coder toi-même un parser à partir de la description du format, tu peux aussi utiliser libsndfile-ocaml qui propose une fonction de lecture vers un tableau, et pourrait te simplifier la tâche. Je crois l'avoir déjà mentionné dans une discussion en début d'année.

  19. #19
    Membre éprouvé
    Avatar de InOCamlWeTrust
    Profil pro
    Inscrit en
    Septembre 2006
    Messages
    1 036
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Septembre 2006
    Messages : 1 036
    Points : 1 284
    Points
    1 284
    Par défaut
    Citation Envoyé par Cacophrene
    +1. Peut-être que c'est une mesure faite dans le toplevel ?
    L'algorithme a été tout simplement mal programmé. Une FFT sur ce type de données, c'est du O(n ln n) et les bonnes implantations le font à la volée, en temps réel.

    Citation Envoyé par Cacophrene
    Autre remarque moins générale : je suis presque sûr que tu passeras plus de temps à lire le fichier qu'à le traiter par ton algo de FFT. En général il faut se méfier des entrées/sorties sur les fichiers parce qu'elles sont lentes. Il est souvent préférable de lire le fichier en blocs et non octet par octet. C'est pour ça (c'est un exemple, je ne pense pas qu'il te serve dans ce cadre-ci) qu'il vaut mieux utiliser Scanf.Scanning.from_file au lieu du classique Scanf.fscanf pour lire un fichier, surtout quand il est volumineux. M'est avis que c'est pareil avec input_byte.
    La façon la plus rapide, et portable qui plus est, est d'utiliser Unix.read / Unix.write. Cependant, les fonctions de Pervasives sont en général optimisées et faites de sorte à optimiser le read / write. L'utilisation directe de ces deux fonctions ne se justifie que lorsque la lecture se fait par très gros blocs ou lorsque l'on n'a pas accès aux fonctions standard.
    When Colt produced the first practical repeating handgun, it gave rise to the saying God created men, but Colt made them equal.

  20. #20
    Membre éprouvé
    Avatar de Cacophrene
    Homme Profil pro
    Biologiste
    Inscrit en
    Janvier 2009
    Messages
    535
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Royaume-Uni

    Informations professionnelles :
    Activité : Biologiste

    Informations forums :
    Inscription : Janvier 2009
    Messages : 535
    Points : 1 125
    Points
    1 125
    Par défaut
    Salut !

    Citation Envoyé par InOCamlWeTrust
    L'utilisation directe de ces deux fonctions ne se justifie que lorsque la lecture se fait par très gros blocs ou lorsque l'on n'a pas accès aux fonctions standard
    Autant que je sache les fichiers wav ont tendance à être très volumineux. Bien sûr rien de tout ça n'est vraiment indigeste pour nos ordis actuels... mais quand même. Quant à Unix, c'est certes portable et rapide (2 avantages non négligeables), mais ça ne change pas que Scanf.fscanf combiné à Scanning.from_file a aussi son intérêt quand on veut faire un chouia d'analyse lexicale (sans convoquer les flots, les regexp, les grammaires, etc.).

    Cordialement,
    Cacophrène

Discussions similaires

  1. Implémentation de l'algorithme ESPRIT
    Par elhaoud dans le forum Signal
    Réponses: 5
    Dernier message: 19/05/2008, 20h45
  2. Implémentation de l'algorithme de kmeans
    Par kevin2008 dans le forum C++
    Réponses: 0
    Dernier message: 18/04/2008, 11h29
  3. Implémentation d'un algorithme foireuse
    Par khazna dans le forum C++
    Réponses: 15
    Dernier message: 05/03/2008, 14h29
  4. Implémentation de l'algorithme FCM en C
    Par hoolaka dans le forum Algorithmes et structures de données
    Réponses: 1
    Dernier message: 11/02/2008, 22h57
  5. Réponses: 1
    Dernier message: 07/03/2007, 09h28

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo