Discussion :

[ToTo13]

Bonjour,

je souhaitais utiliser la FFT pour accélérer mes filtrages par convolution.
Je fais donc la procédure suivante :
- Transformation de la taille de mon image en puissance de 2 supérieure
- Padding de mon image (centrage) sur les nouvelles dimensions.
- FFT sur l'image.
- Padding et FFT sur mon masque de convolution (avec les nouvelles dimensions de l'image).
- Multiplication de mes deux résultats dans l'espace de Fourier.
- FFT inverse du résultat.
- Unpadding pour tout remettre dans mon image résultat.

Malheureusement, cela ne fonctionne pas pour des images non carrées ou non dyadiques :-(
J'ai testé deux algorithmes différents (Butterfly et Fast Hartley Transform de ImageJ), mais j'ai les même problèmes.

Y a t-il une solution pour gérer ce problème ?
Ou connaitriez vous des algorithmes qui gèrent correctement les images non dyadiques ?

Merci par avance

[pseudocode]

Malheureusement, cela ne fonctionne pas pour des images non carrées ou non dyadiques :-(
J'ai testé deux algorithmes différents (Butterfly et Fast Hartley Transform de ImageJ), mais j'ai les même problèmes.

Hum...

Pour les images non carrées et étant donné que la FFT 2D est séparable en deux FFT 1D, il n'y a normalement pas de problèmes.

Pour ce qui est des dimensions non dyadiques, le padding est censé régler le problème. Pour ma part, je fais du padding d'un seul coté de l'image (pas de centrage). De plus, la taille du padding doit non seulement permettre d'obtenir une dimension dyadique, mais doit aussi etre plus grande que la taille du masque (afin d'éviter les echos au bords de l'image).

[Nebulix]

Pourquoi ne pas définir le filtre dans l'espace de Fourier ? C'est plus "physique" et ça peut éviter des erreurs.
Qu'entends-tu par "celà ne fonctionne pas" ?
Qu'obtiens tu si tu ne fais pas de filtrage, juste les FT ?

[ToTo13]

Hum...

Pour les images non carrées et étant donné que la FFT 2D est séparable en deux FFT 1D, il n'y a normalement pas de problèmes.

Pour ce qui est des dimensions non dyadiques, le padding est censé régler le problème. Pour ma part, je fais du padding d'un seul coté de l'image (pas de centrage). De plus, la taille du padding doit non seulement permettre d'obtenir une dimension dyadique, mais doit aussi etre plus grande que la taille du masque (afin d'éviter les echos au bords de l'image).

Merci... je vais vérifier que mes décompositions sont bonnes.

Par curiosité, quel algorithme utilises tu ?
J'ai testé deux algorithmes différents et il y a des écarts.

[pseudocode]

Merci... je vais vérifier que mes décompositions sont bonnes.

Par curiosité, quel algorithme utilises tu ?
J'ai testé deux algorithmes différents et il y a des écarts.

Outre mes routines perso ( parfois en brut-force O(n²) ), j'utilise souvent JTransforms. Cette librairie gère le 1D, 2D, 3D, implémente la DFT, DCT/DST, DHT et s'occupe de faire le padding.

[ToTo13]

Merci, je vais tester cette librairie pour être certain d'avoir quelque chose de fiable. On verra à quel point je peux m'interfacer ;-)

Sinon, j'aimerai quand même comprendre ce qui ne fonctionne pas dans mes deux algorithmes.
- j'ai bien la bijection => FFTinv(FFT(image)) = image.
- pour une convolution (simple filtre moyenne) par un grand masque (51), j'ai un écart moyen de 2 niveaux de gris par pixel pour la FHT et 4 pour l'algorithme Butterfly.
- mais lorsque je réduis la taille du masque à 5, j'ai ce souci.
- et lorsque l'image n'est pas dyadique, cela devient l'horreur.

[pseudocode]

- mais lorsque je réduis la taille du masque à 5, j'ai ce souci.
- et lorsque l'image n'est pas dyadique, cela devient l'horreur.

hum... questions bêtes, mais sait-on jamais:

- Est-ce que les données de ton masque sont bien centrées autour de (0,0). Ou a l'inverse, est ce que tu as bien recentré ton image dans l'espace de fourier ?

- Est ce que tu as bien fait une multiplication 'complexe' dans l'espace de fourier ?