Implémentation d'un algorithme de FFT.

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

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 !

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.

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 !

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

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 !

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:

Très bon résultat.

Félicitations.