Discussion :

[Invité]

Salut!

Je souhaiterai analyser le spectre d'un signal sonore.
J'ai cru comprendre qu'il fallait utiliser la "transformation de fourier" (FFT).
Malheureusement, j'ai un peu oublié mes cours de maths
Et je me pose plusieurs question :

Est-ce rapide de coder un algorithme moi même?
Je n'ai besoin que d'analyser certaines fréquences bien précises.
Connaissez vous une bibliothèque adaptée?

Pourquoi a t-on besoin de fournir un nombre d'échantillons qui soit une puissance de 2?

Mon application étant "temps réel", je reçois mes échantillons au fur et à mesure. Je dois donc les grouper par paquet dont la taille est une puissance de 2?

Merci!

[Invité]

Ha, et aussi :
Comme je bosse sur Android, je dois faire un algo assez léger...
Il faut éviter (voir pas du tout) d'allouer des objets.
C'est pour ça que je cherche à faire ma propre implémentation

[sinok]

http://www.cs.princeton.edu/introcs/.../FFT.java.html

[Invité]

Ok merci!
J'étais déjà tombé dessus, mais comme j'ai vu que ça employait la classe "Complex", j'ai vite laissé tombé
Mais je vais quand même essayer de travailler avec cet algo

[sinok]

Il te suffit de créer le classe Complex associée, elle ne doit pas être super difficile à trouver

A peu près deux secondes pour ce faire: http://www.cs.princeton.edu/introcs/...plex.java.html

[Invité]

oui, mais je ne peux pas l'utiliser
d'après ce que je vois, ça nécessite de créer un grand nombre d'objets de ce type.
Et mon programme fonctionnant sur Android, ce n'est pas recommandé...

J'ai donc supprimé tout ce qui était relatif à cette classe, en gardant juste la partie réelle.
Est ce que c'est une bonne manière de procéder?

[sinok]

Commence par coder quelque chose qui marche, tu t'occuperas des soucis d'optimisation par la suite (autrement dit "premature optimization is the root of all evil", Donald Knuth).

Tu ne sais pas d'avance ce que va donner ce code sous android. De fait les objets créés ici ne sont que temporaires et seront très vite détruits...

Les téléphones sous Android sont capable de faire de la 3D, une pauvre transformée de fourrier, même en nombres complexes devrait être relativement faisable.

Il ne faut pas avoir peur de créer des objets, juste éviter les créations inutiles.

[Invité]

Normalement... je devrais avoir quelque chose qui marche...
Malheureusement, je n'ai pas l'impression que ça marche bien

Pour tester mon code, j'ai "fait écouter" à mon téléphone un son/signal sinusoïdal "pur" assez fort.
J'ai essayé de déterminer la fréquence de ce son.
Normalement, il me suffit de parcourir mon tableau calculé grâce à FFT, et de trouver l'index ayant la valeur absolue la plus haute. (c'est bon?)
J'ai cru comprendre qu'il ne fallait parcourir que la premiere moitié du tableau, car la seconde est un "miroir"...

Le problème, c'est que l'index trouvé ne semble pas correspondre à la fréquence que je "fais écouter"...
Je me suis peut être planté dans la conversion de l'algo, pour utiliser des doubles à la place des Complex...
Je réessayerai demain avec cette classe.

Un autre soucis qui est lié cette fois à Android :
Lorsque je lis le son (c'est du temps réel), j'utilise un buffer.
Si FFT est trop lent, j'ai des avertissement "buffer overflow" au niveau de la classe d'enregistrement. (il n'y a pas de plantage)
Ce qui je pense, est assez ennuyeux, car cela veut dire qu'une partie de mon signal n'est pas traitée...
Agrandir le buffer ne fait que retarder les avertissements.
De plus, si je ne fait que lire le son (sans appliquer FFT), je n'ai pas ces avertissements.

Deuxième soucis lié à Android :
J'ai de nombreux messages du GC, ce qui ralentit mon programme.
Quand je regarde les allocations effectuées, je vois que c'est l'algo FFT qui est en cause.
Dans mon cas, il alloue des centaines de tableaux de double (ou de Complex).
Cet algo étant récursif, ça peut tout expliquer...

J'ai essayé le code fournit par Apache, dans la library "math common", mais j'obtiens sensiblement les mêmes résultats...

Merci

[Rei Ichido]

Je me suis peut être planté dans la conversion de l'algo, pour utiliser des doubles à la place des Complex...

Tu te doutes bien qu'on n'utilise pas des complexes juste pour le plaisir de faire joli.

Sinon, le code cité précise de lui même qu'il n'est vraiment pas optimal et qu'il est orienté "code compréhensible et accessible" plutôt que performance. Cela dit, comme le signale sinok, ça ne te coûterait pas cher de tester tel quel avant de dire "j'aurais forcément un problème de perf".

[Invité]

Je suis finalement revenu à un algo "sûr" : j'utilise la librairie "Math" fournie par Apache.
Même si elle est lente, ça me permet de valider le reste de mon code...
(Mais l'algo n'est pas assez rapide, ce qui "plante" mon programme au bout de quelques secondes à cause d'un buffer overflow...)

@Rei Ichido : dans mon cas, j'ai l'impression qu'utiliser des complexes n'est pas très utile
Quand je regarde les résultats obtenus, la partie imaginaire est toujours à 0.
Je suppose donc qu'il doit être possible d'avoir un algo travaillant uniquement avec des réels, non?