Implémentation d'un algorithme de FFT.

Version imprimable

03/12/2008, 20h54
Mp-X.

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 !
03/12/2008, 21h07
gorgonite

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/
03/12/2008, 22h11
InOCamlWeTrust

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.
04/12/2008, 07h08
Mp-X.

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.
04/12/2008, 09h09
gasche

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.
04/12/2008, 19h45
InOCamlWeTrust

Citation:

Envoyé par Mp-X.

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.
06/12/2008, 16h11
Mp-X.

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...
31/12/2008, 12h55
Mp-X.

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.
31/12/2008, 19h48
InOCamlWeTrust
Citation:

Envoyé par Mp-X.

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:

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.
02/01/2009, 15h48
Mp-X.

Merci pour ta réponse...
Quand tu dis :

Citation:

Envoyé par InOCamlWeTrust

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.
02/01/2009, 20h47
InOCamlWeTrust

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

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:

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:

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 ?

11/06/2009, 19h54
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 !
12/06/2009, 07h54
Cacophrene
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:

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
12/06/2009, 09h50
gasche

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.
12/06/2009, 11h07
Cacophrene

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

Cordialement,
Cacophrène
13/06/2009, 16h42
Mp-X.

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... :)
13/06/2009, 21h35
gasche

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.
15/06/2009, 10h18
InOCamlWeTrust

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.
15/06/2009, 14h12
Cacophrene

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
17/06/2009, 20h39
InOCamlWeTrust

A quoi bon faire de l'ananlyse lexicale sur des fichiers WAV ?
18/06/2009, 08h49
Cacophrene

Salut !

Citation:

Envoyé par InOCamlWeTrust

A quoi bon faire de l'ananlyse lexicale sur des fichiers WAV ?

J'en sais rien, moi, je ne connais pas la structure des fichiers WAV. Je sais cependant que certains types de fichiers ont des systèmes de balises qui sont bien sympas à récupérer/découper avec un peu d'analyse lexicale.

Cordialement,
Cacophrène

Citation:

Envoyé par bluestorm

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.

Salut BlueStorm,

Hm... Oui, finalement, je voulais surtout construire un programme très général, qui se comporte aussi bien avec n'importe quel type de fichier au niveau de l'acquisition. Du coup... J'ai préféré suivre la remarque de pur bon sens de Cacophrène et d'adapter mon algorithme de base en utilisant open_in_bin au lieu de open_in. Et là, bien sûr... Tout roule. Ah là là... Tous ces soucis à cause de ça... :?

Aussi, j'ai corrigé une erreur absolument stupide mais surtout énorme sur la fonction de FFT... Du coup, elle est à nouveau rapide (Sortie quasi-instantanée pour une FFT sur un tableau à 1024 éléments.).

Donc finalement, j'en ai profité pour écrire toutes les fonctions qui m'intéressaient au départ, afin d'utiliser la FFT pour un programme de reconnaissance des notes de Musique composant un fichier sonore encodé en wav 8 bits. Calcul de la position relative d'une fréquence par rapport au la440 et renvoi de note en conséquence...

Je vous poste le résultat final.

Code:

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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
(* Définitions. *)
 
let pi = 4.*.atan 1. ;;
 
let la1024 = Array.make 1024 0. ;;
for i=0 to 1023 do
  la1024.(i) <- sin (2.*.pi*.110.*.(float_of_int i)/.500.)
done
;;
 
(* On calcule exponentielle(2i*Pi/1024), utile pour les tableaux à 1024 éléments. *)
let e1024 = Complex.exp {Complex.re = 0. ; Complex.im = 2.*.pi/.1024.} ;;
 
let complexifie tab =
  let n = Array.length tab
  in
    let res = Array.make n Complex.zero
    in
      for i = 0 to n-1 do
        res.(i) <- {Complex.re = tab.(i) ; Complex.im = 0.}
      done ;
      res
;;
 
 
(* Fonction renvoyant l'indice correspondant à l'élément maximal de la première moitié du tableau. *)
(*
let ind_max t =
  let l = Array.length t
  in
    let ind = ref (5)
    in
      for i = 5 to l/2-1 do
        if t.(i) > t.(!ind) then
          ind := i ;
      done ;
      !ind
;;
*)
 
(* Version limitée aux fréquences comprises entre 130 Hz - k = 16 - et 2000 Hz - k = 256 *)
 
let ind_max t =
  let ind = ref (16)
  in
    for i = 16 to 256 do
      if t.(i) > t.(!ind) then
        ind := i ;
    done ;
    !ind
;;
 
 
let modulise tab =
  let n = Array.length tab
  in
    let res = Array.make n 0.
    in
      for i = 0 to n-1 do
        res.(i) <- Complex.norm tab.(i)
      done ;
      res
;;
 
 
 
 
 
 
 
 
(* FFT récursive. Attention : tab est un tableau de complexes. *)
 
let rec fft_rec n tab exp res = match n with
  |1 -> res.(0) <- tab.(0)
  |_ ->
    let m = n/2
    in
      let tab_pair = Array.make m Complex.zero
      and tab_impair = Array.make m Complex.zero
      and res_pair = Array.make m Complex.zero
      and res_impair = Array.make m Complex.zero
      and exp2 = Complex.mul exp exp
      and coeff = ref Complex.one
      in
        for i = 0 to m-1 do
          tab_pair.(i) <- tab.(2*i) ;
          tab_impair.(i) <- tab.(2*i+1) ;
        done ;
        fft_rec m tab_pair exp2 res_pair ;
        fft_rec m tab_impair exp2 res_impair ;
        for i = 0 to m-1 do
          res.(i) <- Complex.add res_pair.(i) (Complex.mul !coeff res_impair.(i)) ;
          coeff := Complex.mul !coeff exp ;
        done ;
        for i = 0 to m-1 do
          res.(m+i) <- Complex.add res_pair.(i) (Complex.mul !coeff res_impair.(i)) ;
          coeff := Complex.mul !coeff exp ;
        done ;
;;
 
 
 
(* Attention : Dans tout ce qui suit, on se place dans le cas d'un tableau de 1024 éléments. *)
 
(* Fonction renvoyant le tableau des modules des coefficients de Fourier. *)
 
let cree_fft tab =
  let n = Array.length tab
  in
    let aux = Array.make n Complex.zero
    in
      fft_rec n (complexifie tab) e1024 aux ;
      modulise aux
;;
 
(* Fonction complète, qui agit sur un échantillon de 1024 réels, en calcule la FFT, et en renvoie la fréquence correspondante. *)
 
let note tab freq_ech =
  (ind_max (cree_fft tab))*freq_ech/1024
;;
 
 
 
 
 
 
(* Acquisition d'un fichier binaire : on renvoie un tableau d'entiers. *)
 
let acquisition fichier =
  let echantillon = open_in_bin fichier
  in
    let n = in_channel_length echantillon
    in
      let resultat = Array.make n 0
      in
        for i = 0 to (n-1) do
          resultat.(i) <- input_byte echantillon
        done ;
        close_in echantillon ;
        resultat
;;
 
(* Fonction fractionnant un grand tableau d'entiers en un tableau de tableaux de 1024 réels. *)
 
let fractionne tab =
  let n = Array.length tab
  in
    let p = n/1024
    in
      let resultat = Array.make_matrix p 1024 0.
      in
        for i = 0 to p-1 do
          for j = 0 to 1023 do
            resultat.(i).(j) <- float_of_int tab.(i*1024+j)
          done ;
        done ;
        resultat
;;
 
 
 
 
 
(* À partir d'un tableau déjà fractionné. *)
 
let cree_notes tab freq_ech =
  let n = Array.length tab
  in
    let resultat = Array.make n 0
    in
      for i = 0 to n-1 do
        resultat.(i) <- note tab.(i) freq_ech
      done ;
      resultat
;;
 
 
 
(* Fonction complète : à partir du chemin vers un fichier binaire, on renvoie un tableau de fréquences. *)
 
let frequences chemin freq_ech =
  let echantillon = acquisition chemin
  in
    let decoupe = fractionne echantillon
    in
      cree_notes decoupe freq_ech
;;
 
 
 
(* Fonction de filtrage : fréquence -> position relative par rapport au La 440. *)
 
let position f =
  int_of_float (12.*.(log (float_of_int f /. 440.))/.(log 2.))
;;
 
(* Échelle des notes. *)
 
type musique = SousGrave|Do1|DoD1|Ré1|RéD1|Mi1|Fa1|FaD1|Sol1|SolD1|La1|LaD1|
Si1|Do2|DoD2|Ré2|RéD2|Mi2|Fa2|FaD2|Sol2|SolD2|La2|LaD2|Si2|Do3|
DoD3|Ré3|RéD3|Mi3|Fa3|FaD3|Sol3|SolD3|La3|LaD3|Si3|Do4|DoD4|Ré4|
RéD4|Mi4|Fa4|FaD4|Sol4|SolD4|La4|LaD4|Si4|SurAigu ;;
 
let echelle = [|Do1;DoD1;Ré1;RéD1;Mi1;Fa1;FaD1;Sol1;SolD1;La1;LaD1;Si1;
Do2;DoD2;Ré2;RéD2;Mi2;Fa2;FaD2;Sol2;SolD2;La2;LaD2;Si2;
Do3;DoD3;Ré3;RéD3;Mi3;Fa3;FaD3;Sol3;SolD3;La3;LaD3;Si3;
Do4;DoD4;Ré4;RéD4;Mi4;Fa4;FaD4;Sol4;SolD4;La4;LaD4;Si4|]
;;
 
(* Filtrage : position relative -> note. *)
 
let note_associee pos = 
  if pos < -21 then
    SousGrave
  else if pos > 26 then
    SurAigu
  else
    echelle.(21+pos)
;;
 
(* Fonction complète : fréquence -> note. *)
 
let freq_donne_note freq =
  note_associee (position freq)
;;
 
 
 
(* Fonction complète : à partir du chemin vers un fichier binaire, on renvoie un tableau de notes. *)
 
let notes chemin freq_ech =
  let aux = frequences chemin freq_ech
  in
    let n = Array.length aux
    in
      let resultat = Array.make n SousGrave
      in
        for i=0 to n-1 do
          resultat.(i) <- freq_donne_note aux.(i)
        done ;
        resultat
;;

Pour résumer ce qui peut être intéressant, si tab est un échantillon de 1024 éléments de type float, l'appel "cree_fft tab" renverra... Le tableau des modules des coefficients de Fourier correspondants.
Autrement, l'appel "notes chemin freq_ech" permet de renvoyer le tableau des notes d'une Musique au format wav. En pratique, cela ne marche évidemment que pour des sons plutôt... purs, dénués au maximum d'harmoniques... Pas terrible pour des sons non artificiels, bien sûr.

Bon, me reste plus qu'à préparer mes transparents pour ma présentation à l'oral... C'est pour dans deux semaines.

Merci à tous pour votre patience !

21/06/2009, 03h03
InOCamlWeTrust

Un conseil : prépare un exposé en béton armé car la FFT est un sujet très courant, que beaucoup traitent de façon banale. Si tu ne veux pas tomber dans cette dernière catégorie, potasse bien !

Bonne chance.
23/07/2009, 20h50
Mp-X.

Merci à tous !
Résultats des courses : les examinateurs semblent avoir apprécié le fait que j'aie mis l'accent non pas sur la FFT en elle-même mais sur son application à la reconnaissance d'un morceau de Musique (Faisant appel à des méthodes de profilage des Instruments...), puisqu'ils m'ont gratifié d'un 14.5/20 qui me satisfait assez...
Du coup, pour l'instant, au vu de mes rangs aux concours, je suis assuré d'avoir Lille sur celui de Centrale (Fait notable : je n'ai pas passé la barre d'admissibilité de Centrale Lyon, mais avec mon carton aux oraux, j'ai maintenant bien au-delà de la barre de classement... M'enfin, c'est les concours, il faut être bon à l'écrit et à l'oral...), et au moins Nancy sur celui des Mines (On croise les doigts pour l'ENSTA... Mais je me satisferai parfaitement de Nancy !).
Merci à vous tous pour m'avoir souvent remis dans la bonne direction !
23/07/2009, 21h07
gorgonite

Citation:

Envoyé par Mp-X.

(On croise les doigts pour l'ENSTA... Mais je me satisferai parfaitement de Nancy !).

envoies-moi un MP si tu intègres l'ENSTA... (les élèves de 1A ont vite appris à m'y détester :aie:)
01/08/2009, 18h26
Mp-X.

Citation:

Envoyé par gorgonite

envoies-moi un MP si tu intègres l'ENSTA... (les élèves de 1A ont vite appris à m'y détester :aie:)

Heh bien finalement, ce sera Supaero :D
Tant pis pour moi, hein !
01/08/2009, 19h13
gorgonite

Citation:

Envoyé par Mp-X.

Heh bien finalement, ce sera Supaero :D
Tant pis pour moi, hein !

ben c'est sans doute mieux... tu souffriras moins :mouarf:
02/08/2009, 15h55
InOCamlWeTrust

Très bon résultat.

Félicitations.