Discussion :

[amarion]

Bonjour à tous,
J'ai besoin d'optimiser un morceau d'algorithme faisant une convolution.
Codé en Matlab, la convolution (conv2) d'une matrice de taille 4000*1600 par un noyau de taille 105*81 est de l'ordre de 6s sur un P4 standard.
A priori, on ne sait pas comment Matlab convolue avec conv2. Je pense qu'il utilise la FFT.
J'aimerais réduire ce temps en passant en C ou C++. Je me penche donc sur l'utilisation de la FFT. En utilisant FFTW, on arrive à une quinzaine de seconde pour effectuer les FFT et IFFT sur une image de 4096*2048. On remarque également que la fonction FFT2 de Matlab mets à peur près 2 à 3 fois moins de temps que la librairie C FFTW.

Quelqu'un a-t-il une idée à proposer pour accélérer le processus de convolution? Je reste surpris de ne pas réussir à faire mieux en C.
J'ai vu rapidement les librairies MKL de chez Intel où une FFT est codée. Des idées quant à son efficacité?

Pensez-vous qu'il soit possible de réduire le temps de convolution par FFT (ou pas d'ailleurs) à 1 seconde environ pour les tailles données en début de post?

Merci d'avance pour vos avis,
Adrien

[themadmax]

Je ne comprend pas exactement, une convolution est bien differant pour moi d'une FFT ( http://docs.gimp.org/fr/plug-in-convmatrix.html ). Pour ce qui est de codé cela en C, c'est assez simple est très rapide. De plus de nombreuse lib de T.I. basic l'implémente. Pour avoir des temps de rendu encore plus rapide il est possible d'améliorer les algo de parcours d'image, ou descendre en ASM.

[Invité(e)]

Je ne comprend pas exactement, une convolution est bien differant pour moi d'une FFT

Une convolution dans l'espace image correspond à une multiplication dans l'espace fréquentiel.

[JolyLoic]

A priori, même si un programme écrit en langage matlab n'est pas très optimisé, les fonctions qui sont appelées par ces programmes le sont assez bien.

Pour ce qui est la version Intel, aucune idée, je n'ai pas essayé, mais ça me semblerait une option à tenter.

[poukill]

En effet, Matlab utilise LAPACK derrière. Pour tout ce qui est calcul matriciel, Matlab, ça carbure. Ce sont des fonctions C très bien optimisé derrière !
Par contre, dès qu'il y a des grosses boucles à la main, attention l'escargot !

Il est en effet fort probable que Matlab utilise la FTT, c'est plus rapide sur les grosses matrices. Matlab est vraiment beaucoup plus rapide que FFTW ?

[Invité]

Si le filtre est d'une longueur nettement plus faible que l'échantillon, des méthodes de type overlap-save ou overlap-add vont généralement aller plus vite que la FFT directe de l'échantillon complet.

Par ailleurs, il n'y a pas que la transformée de Fourier qui accélère la convolution. J'ai souvenir d'une transformation voisine évitant les complexes (et donc pas mal de calculs en plus), due à Nussbaumer (je crois me souvenir qu'elle est décrite dans un exercice du Knuth (chap 4.3.3.C).

Un excellent livre récent sur le sujet est Modern Computer Algebra, de von zur Gathen et Gerhard. Tu devrais y trouver ton bonheur au chapitre 8.



Themadmax, l'utilisation de la tranformée de Fourier est un "truc" mathématique. En fait, si "*" note la convolution de deux fonctions, "x" leur produit, et TF leur transformée de Fourier, on a

TF(f*g)=TF(f)xTF(g)

En appelant ITF la transformée inverse de fourier, on a donc

f*g = ITF( TF(f)xTF(g) )

Le "truc" consiste à remarquer que le calcul direct de f*g est quadratique (O(n^2) pour des matrices de taille n), et que la Transformée de Fourier et son inverse sont O(n Log n) (et le produit O(n)). Au global, le calcul via les Transformées va donc être O(n log n), pour de grandes valeurs de n, passer par la FFT ira plus vite.

Francois

[amarion]

Merci aux auteurs des réponses.
Je ne savais pas Matlab s'appuyait sur LAPACK, c'est bon à savoir.
Pour la différence entre la fft Matlab et fftw, il doit y avoir un rapport 2 à 3 donc je ne sais pas sur quoi s'appuie FFT2 de Matlab...

Sinon, je pense que FFT (et non FFT2) de Matlab utilise la multiplication polynomiale.

En ce qui concerne les méthodes de type overlap-save, c'est une piste intéressante à étudier. Je vais voir ça étant donné la grande taille des matrices utilisées. L'idée serait d'adapter la méthode dite overlap-save en calculant uniquement des morceaux de FFT avec FFTW?

Merci,
Adrien

[Invité]

En ce qui concerne les méthodes de type overlap-save, c'est une piste intéressante à étudier. Je vais voir ça étant donné la grande taille des matrices utilisées. L'idée serait d'adapter la méthode dite overlap-save en calculant uniquement des morceaux de FFT avec FFTW?

Oui, l'idée générale des méthodes overlap (save ou add) c'est que quand tu fait une convolution avec un filtre plus petit que tes données, des parties "éloignées" du résultat vont être indépendantes.

Donc tu fais plusieurs calcul de convolution sur des segments réduits de ton image d'entrée (qui se recoupent, d'où le terme d'overlap), et réassemble les résultats pour avoir le résultat final (en les additionnant dans le cas de la méthode add, en les supprimant partiellement dans le cas de la méthode save).

Ceci dit, je suis prêt à parier que Matlab utilise cela dans sa fonction de convolution, et comme ses fonctions bas niveau sont du C bien codé, il va être difficile à battre.

Francois

[Jerome Briot]

Il est en effet fort probable que Matlab utilise la FTT, c'est plus rapide sur les grosses matrices. Matlab est vraiment beaucoup plus rapide que FFTW ?

Je ne suis pas un spécialiste de ces questions... mais je me débrouille assez bien avec la doc de MATLAB

Pour la fonction CONV2 :

conv2 uses a straightforward formal implementation of the two-dimensional convolution equation in spatial form

Voir la section algorithme ici : http://www.mathworks.com/access/help...ref/conv2.html

Pour FFT2 :

fft2(X) can be simply computed as

fft(fft(X).').'

Voir encore une fois la section algorithme ici : http://www.mathworks.com/access/help.../ref/fft2.html

Et pour FFTW... cette bibliothèque est bien intégrée dans MATLAB.

On peut d'ailleur lire dans la documentation de la fonction FFT :

The FFT functions (fft, fft2, fftn, ifft, ifft2, ifftn) are based on a library called FFTW

La boucle est bouclée