# Gnral Dveloppement > Algorithme & Mathmatiques > Traitement d'images >  Acclrer un Filtre de gabor

## aminems

bonjour,
J'aimerai savoir comment je pourrai faire pour acclrer le filtrage de Gabor sur une image 2D ?
je suis en C++ , mon kernel est de 9*9 , et mon image est 680*680 , vous imaginez le temps que a peux prendre :-(

Une ide??

il y'a une piste qui dis qu'il faut pr-calculer les coefficients pour les diffrentes frquences , et les diffrentes orientations , mais mon problme c'est comment je pourrai faire pour les informations spatiales (les x, et y) ??

----------


## ToTo13

> je suis en C++ , mon kernel est de 9*9 , et mon image est 680*680 , vous imaginez le temps que a peux prendre


Une fraction de seconde... tu dois avoir un souci quelque part.

Une bonne solution pour acclrer tous les filtres de convolution est de passer par une FFT.

----------


## aminems

Une fraction de seconde  :8O:  , tu pourrais me rappeler comment on fait ?
moi je prend pour chaque pixel de l'image initiale et je le convolue avec mon filtre 9*9 , qui est compose de plusieurs multiplications: si on calcule le totale des oprations effectue c'est 9*9*680*680*N donc a fait beaucoup !

Es bien comme a?

----------


## pseudocode

> moi je prend pour chaque pixel de l'image initiale et je le convolue avec mon filtre 9*9 , qui est compose de plusieurs multiplications: si on calcule le totale des oprations effectue c'est 9*9*680*680*N donc a fait beaucoup !


Normalement, tu as pr-calcul les 81 valeurs de ton masque 9x9. Tu as donc 81 multiplications/additions a faire par pixel.

Si ca fait trop pour ta configuration, il vaut mieux effectivement passer dans l'espace de Fourier.

----------


## aminems

effectivement , j'ai pris une plus petite image , et j'ai aussi pr-calcul toutes les valeurs possibles de mon masque en fonction de la frquence ,et aussi de la position .
a prend un peu de temps au dbut mais je pense que a ira.
Je pense que l'espace de fourrier n'est pas ncessaire ici , car j'ai un masque qui n'est pas trop grand 9x9. 
Ma question est : dans mon cas , passer dans l'espace de fourrier donnera t-il de meilleurs performances??

----------


## souviron34

euh..

Montres-nous ton code, et ensuite on pourra dire si on est  la limite ou non..


L j'ai plus l'impression d'une erreur de programmation qu'autre chose..

----------


## ToTo13

J'ai fait quelques tests entre FFT et convolution classique (j'en ai aussi besoin pour mon travail).
Pour un masque de convolution 11x11 et sur une image 521x512, j'avais 0.1s par Fourier et 0.15 par convolution classique.
Ces temps sont trs grossiers car je n'ai pas ritr l'opration un grand nombre de fois.

----------


## aminems

Merci , je pense passer dans l'espace de fourrier question de gratter quelques millimes de secondes (pour chaque itration , car je fait plusieurs itrations du filtre de Gabor).

----------


## black_hole

Bonjour,
j'ai suivis cette conversation depuis un moment. Mais je ne comprend pas en quoi le fait de passer par une FFT peut dj amliorer le temps d'execution et d'autre part appliquer le filtre de Gabor?
Le filtre est bien du type:
G(x,y)=cos(ax+by)exp(-(x+y)/(2 sigma)) 

C'est ca la dfinition? Comment on peut passer par la FFT pour calculer ce filtre?

----------


## pseudocode

> Le filtre est bien du type:
> G(x,y)=cos(ax+by)exp(-(x+y)/(2 sigma)) 
> 
> C'est ca la dfinition? Comment on peut passer par la FFT pour calculer ce filtre?


Non, pas entirement. La dfinition du filtre de Gabor est une formule qui utilise les complexes. 

A * exp( i * B)

exp( i * B ) est la formulation d'Euler, qui peut se rcrire cos(B) + i*sin(B). On peut donc sparer la formule en deux parties "relle" et "imaginaire", effectuer deux fois un filtrage par convolution, puis recombiner les deux rsultats pour obtenir le rsultat "complexe".

Comme le filtre est complexe au dpart, on peut aussi directement effectuer la multiplication dans l'espace de Fourier.

----------


## black_hole

Qu'est ce que vous entendez par multiplier directement dans l'espace de Fourier?

Donc si j'ai bien compris, on a notre filtre g=A exp(i.B) = A(cos B +i sin B)
I*g = F-1(A(F(I).F(cos(B)+(i.F(I).F(sin(B)) Ou I est l'image et F,F-1 Tranforme de Fourier?

Je me suis tromp? et donc on fait tomber la comprexit de l'algo de n en 2*n?

----------


## pseudocode

> Qu'est ce que vous entendez par multiplier directement dans l'espace de Fourier?


Une simple multiplication des lments.

Dans l'espace de Fourier, un pixel de l'image est reprsent par une valeur complexe (x+i.y). La valeur du filtre correspondant a ce pixel est g(x,y).

Le rsultat du filtrage est la multiplication (complexe) des deux valeurs : (x+i.y)*g(x,y)





> Donc si j'ai bien compris, on a notre filtre g=A exp(i.B) = A(cos B +i sin B)
> I*g = F-1(A(F(I).F(cos(B)+(i.F(I).F(sin(B)) Ou I est l'image et F,F-1 Tranforme de Fourier?
> 
> Je me suis tromp? et donc on fait tomber la comprexit de l'algo de n en 2*n?


oui, sauf qu'il faut tout de meme calculer la FFT de l'image, puis la FFT-1 du rsultat, donc ca rajoute deux fois O(n.log(n)) oprations.

----------


## black_hole

Donc en fait si j'ai bien compris l'intret de passer par la FFT. Au lieu de faire une convolution de taille variable, par exemple n qui nous donne n muiltiplication et n addition, on passe par une simple multiplication dans le domaine frquentiel?

Mais cette mthode n'a d'avange qu'a partir du moment ou la taille du noyau est assez importante? Si cette taille de noyau est faible le temps de calcul est quasiment identique?

----------


## pseudocode

> Mais cette mthode n'a d'avange qu'a partir du moment ou la taille du noyau est assez importante? Si cette taille de noyau est faible le temps de calcul est quasiment identique?


Tout a fait. Ou alors si on a des convolutions a faire avec des noyaux diffrents, ce qui est gnralement le cas avec Gabor.

----------


## hkarim

salut tout le monde, je viens de commencer de travailler avec le filtre de Gabor, votre discussion m'intresse, si vous avez de court documents expliquant l'algorithme, merci de me les envoyer.

----------


## pseudocode

> salut tout le monde, je viens de commencer de travailler avec le filtre de Gabor, votre discussion m'intresse, si vous avez de court documents expliquant l'algorithme, merci de me les envoyer.


Comme je l'ai dit au psot #10, les formules sont sur le site de wikipedia. 

Il suffit de les utiliser pour construire les 2 masques de convolution (rel + complexe). Ensuite, pour chaque pixel de l'image on fait un convolution avec chacun des masques, ce qui nous donne la partie relle et la partie imaginaire du rsultat.



```

```


Rsultat sur l'image de test de wikipedia, avec les paramtres :

lambda=20.0, psi=0, sigma=5.0, gamma=1.0, RADIUS=9 et theta variant entre 0 et PI




(image montrant le module du rsultat)

----------


## hkarim

merci pseudocode pour ce code en java, j'ai lu l'article sur wikipdia, mon problme est de dvelopper un filtre 1d d'abord ensuite un filtre 2D pour comprendre, comme je suis dbutant en traitement d'images, je suis un peu perdu, je trouve beaucoup de termes qui sont pour moi nouveau, je veux des articles, des documents, des livres qui expliquent le filtre de gabor ainsi son algorithme : qu'est ce qu'on donne comme entrs au programme, qu'est ce qu'ils ne retourne comme rsultats, comment afficher les bancs de filtre sous forme de tableau,...etc, je compte le programmer sous C++ builder mais je ne sais pas comment commencer vu que je n'ai pas un algorithme dtaill, je rpte je veux suivre les tapes suivantes : 
Tracer le filtre de Gabor 1D
Programmer le filtre 1D (en entrs paramtres : sigma et gamma, en sortie : une table montrant des valeurs intressantes).
Tracer le filtre 2D
le programmer.
Maitre en eouvre la convolution sur une image 2D.

----------


## aminems

Bonjour,
Je vous expose mon problme :
J'ai une image 256x256 , je voudrais faire un filtrage avec un filtre de Gabor dessus, j'ai dans chaque pixel une orientation ( parmi 256 autres orientations possibles) ce qui me donne pour chaque pixel un masque de convolution diffrent 34x34 .
Ce que je n'arrive pas  comprendre c'est comment je pourrai faire pour convoluer dans l'espace de fourrier avec une configuration pareil ?

Si vous avez des ides , ou des corrections je suis preneur ,Merci

Que pensez vous de ce cas ?

----------


## pseudocode

> Bonjour,
> Je vous expose mon problme :
> J'ai une image 256x256 , je voudrais faire un filtrage avec un filtre de Gabor dessus, j'ai dans chaque pixel une orientation ( parmi 256 autres orientations possibles) ce qui me donne pour chaque pixel un masque de convolution diffrent 34x34 .
> Ce que je n'arrive pas  comprendre c'est comment je pourrai faire pour convoluer dans l'espace de fourrier avec une configuration pareil ?
> 
> Si vous avez des ides , ou des corrections je suis preneur ,Merci
> 
> Que pensez vous de ce cas ?


On ne fait pas de convolution dans l'espace de fourrier, simplement une multiplication.



```

```

----------


## aminems

> ```
> ComplexArray gabor = ...  // valeurs du filtre de gabor complexe
> ```


les valeurs du filtre de Gabor sont ici des valeurs ponctuels pour chaque pixel ? ou bien pour chaque pixel il y'a un masque de convolution ?

----------


## pseudocode

> les valeurs du filtre de Gabor sont ici des valeurs ponctuels pour chaque pixel ? ou bien pour chaque pixel il y'a un masque de convolution ?


Pour chaque pixel il y a une valeur "ponctuelle" comme tu dis. Attention, c'est une valeur complexe (partie relle et partie imaginaire)

----------


## pseudocode

Pour la postrit, un code java qui applique un filtre de Gabor en passant par une FFT (librairie Jtransforms)



```

```

----------


## aminems

Bonjour,
J'ai test la mthode de convolution dans l'espace de fourrier que vous avez dcrit, mais j'ai l'impression que le rsultat ressemble beaucoup  celui avec une convolution classique mais cette fois ci avec une taille de masque trop petite.

Je pense que j'ai loup un pisode ?  :8O:

----------


## pseudocode

> Bonjour,
> J'ai test la mthode de convolution dans l'espace de fourrier que vous avez dcrit, mais j'ai l'impression que le rsultat ressemble beaucoup  celui avec une convolution classique mais cette fois ci avec une taille de masque trop petite.
> 
> Je pense que j'ai loup un pisode ?


Attention, je n'ai pas mis les mme paramtres pour le filtre (lambda, sigma, ...)  :;): 

(en fait, j'ai mis les paramtres utiliss dans l'exemple de wikipedia)

----------


## aminems

Bonjour,
Merci pour votre rponse, mais une information mchappe :
Dans une convolution classique avec un filtre de Gabor : pour chaque pixel de l'image on fait une multiplication de la valeur du pixel avec le Kernel (qui a une certaine largeur W).
Dans le cas d'une convolution dans l'espace frquentiel (image carre 256*256 pour faire simple):
1-on fait une FFT(Image)
2-on fait une FFT(Kernel) ?????????? 
3-Ifft(1*2)

Mon problme c'est que mon Kernel est de type rel et pour chaque pixel j'ai une orientation diffrente , donc ce n'est plus vraiment un Kernel dans ce cas mais un ensemble de Kernel ???
Tout claircissement serais le bienvenu.
Merci encore.

----------


## pseudocode

> Dans le cas d'une convolution dans l'espace frquentiel (image carre 256*256 pour faire simple):
> 1-on fait une FFT(Image)
> 2-on fait une FFT(Kernel) ?????????? 
> 3-Ifft(1*2)


Oui, c'est ca.




> Mon problme c'est que mon Kernel est de type rel et pour chaque pixel j'ai une orientation diffrente , donc ce n'est plus vraiment un Kernel dans ce cas mais un ensemble de Kernel ???
> Tout claircissement serais le bienvenu.
> Merci encore.


Heu... je ne comprend pas ton problme.
Dja, le kernel de Gabor n'est pas rel mais complexe.
Ensuite son orientation est constante (theta) et ne dpend pas des pixels

----------


## aminems

> Heu... je ne comprend pas ton problme.
> Dja, le kernel de Gabor n'est pas rel mais complexe.
> Ensuite son orientation est constante (theta) et ne dpend pas des pixels


Effectivement je n'ai pas expos clairement mon problme, pour mon travail j'utilise le filtre de Gabor pour la gnration de motifs qui suivent une map d'orientation , cette Map dfinie pour chaque pixel une orientation diffrente , c'est pour cela que je dois utiliser des Kernel diffrents pour chaque pixel , j'ai fait a avec une convolution classique mais pour des raisons de performances je suis oblig de faire autrement.

Je vous remercie pour votre aide , et si vous avez des pistes je suis preneur.

----------


## aminems

Pensez vous que ce que je cherche  faire est possible ? 

NB: Pour information , le Multi-Kernel marche bien avec une convolution classique (mais c'est lent) .

Je connais pas d'autres mthodes de faire, j'ai essayer de le faire en utilisant la sparabilt du Filtre de Gabor mais vu que j'ai 256 orientations diffrentes, je n'ai pas pu le faire.

Si vous pensez que c'est possible sans donner de mthode , je suis preneur aussi.  :;):

----------


## pseudocode

Que ce soit dans le domaine spatial (convolution) ou dans le domaine de fourier (multiplication), je ne vois pas d'autre mthode que d'utiliser un kernel par orientation.

----------


## aminems

> Que ce soit dans le domaine spatial (convolution) ou dans le domaine de fourier (multiplication), je ne vois pas d'autre mthode que d'utiliser un kernel par orientation.


C'est bien ce qui est fait dans le domaine spatial, donc si j'ai bien compris pour pouvoir le faire dans le domaine frquentiel il faudrait que je fasse:
1-FFT(image)
2-FFT(padding(Kernel[du pixel i]))
3-IFFT(1*2)

et 2 est rpt pour tout les pixel , ce qui nous donne (W*H) FFT et IFFT .
Ce qui rend cette solution peu intressante.

es bien cela?

----------


## pseudocode

> C'est bien ce qui est fait dans le domaine spatial, donc si j'ai bien compris pour pouvoir le faire dans le domaine frquentiel il faudrait que je fasse:
> 1-FFT(image)
> 2-FFT(padding(Kernel[du pixel i]))
> 3-IFFT(1*2)
> 
> et 2 est rpt pour tout les pixel , ce qui nous donne (W*H) FFT et IFFT .
> Ce qui rend cette solution peu intressante.
> 
> es bien cela?


Je ne sais pas. Je n'ai toujours pas compris cette histoire d'orientation diffrente pour chaque pixel. 

Tout ce que je peux dire, c'est qu'un filtrage par convolution classique peut tre remplac par une multiplication dans l'espace de fourier.

----------


## aminems

En tout cas Merci beaucoup.

----------


## black_hole

Bonjour,
je suis en train d'appliquer ce filtre de gabor en C et je voudrais avoir quelques prcisions. La taille du noyau de gabor doit forcement etre de la meme taille que celui de l'image d'origine? 
Par exemple si je dois faire la convolution d'un noyau gaussien dans le domaine frquentielle et que mon image fait M*N, je dois crer un noyau gaussian de taille M*N  centr en (0,0) que je convolu  l'image de dpart. C'est  dire que dans le domaine frquentielle je vais faire une multiplication terme  terme?

C'est ca??

----------


## pseudocode

> Bonjour,
> je suis en train d'appliquer ce filtre de gabor en C et je voudrais avoir quelques prcisions. La taille du noyau de gabor doit forcement etre de la meme taille que celui de l'image d'origine?


En thorie oui. 

En pratique, les termes du noyau de gabor deviennent vite nuls quand on s'loigne du centre. Donc on peut limiter la multiplication terme  terme aux valeurs proche du centre.

On peut meme imaginer prendre un noyau plus petit que l'image. Mais il faut recalculer les paramtres lambda/sigma pour tenir compte de ce changement d'chelle (et attention aux artfacts qui vont apparaitre du fait de ce changement d'chelle).

Bref, pour avoir des rsultats optimum, je conseille plutot de rduire la taille de l'image AVANT de faire le traitement, et d'avoir toujours une image et un filtre de meme taille. Ca a entre autre l'avantage de pouvoir prcalculer tous les FFT des filtres de Gabor (par exemple en 256x256).




> Par exemple si je dois faire la convolution d'un noyau gaussien dans le domaine frquentielle et que mon image fait M*N, je dois crer un noyau gaussian de taille M*N  centr en (0,0) que je convolu  l'image de dpart. C'est  dire que dans le domaine frquentielle je vais faire une multiplication terme  terme?
> 
> C'est ca??


Oui.

----------


## black_hole

> En thorie oui. 
> 
> En pratique, les termes du noyau de gabor deviennent vite nuls quand on s'loigne du centre. Donc on peut limiter la multiplication terme  terme aux valeurs proche du centre.


Le centre de l'image que l'on parle est bien le coin en au  gauche?




> On peut meme imaginer prendre un noyau plus petit que l'image. Mais il faut recalculer les paramtres lambda/sigma pour tenir compte de ce changement d'chelle (et attention aux artfacts qui vont apparaitre du fait de ce changement d'chelle).


Qu'appelez-vous artfacts?





> Bref, pour avoir des rsultats optimum, je conseille plutot de rduire la taille de l'image AVANT de faire le traitement, et d'avoir toujours une image et un filtre de meme taille. Ca a entre autre l'avantage de pouvoir prcalculer tous les FFT des filtres de Gabor (par exemple en 256x256).


Pour reduire la taille de l'image, on prend un pixel sur deux de l'image? Et apres pour reconstruire on applique un zero-padding ou une interpolation?

----------


## pseudocode

> Le centre de l'image que l'on parle est bien le coin en au  gauche?


oui.




> Qu'appelez-vous artfacts?


Si le masque n'a pas la meme taille que l'image, le rsultat final fait apparaitre des "dformations". Visuellement, ca donne l'impression que l'image a t fortement interpole linairement.




> Pour reduire la taille de l'image, on prend un pixel sur deux de l'image? Et apres pour reconstruire on applique un zero-padding ou une interpolation?


L'idal c'est de resampler l'image, mais tout algorithme de redimensionnement d'image fera l'affaire.

----------


## T_Lara

Bon de ma part j'ai compris pourquoi passer par Fourier et tout mais a m chappe les details  ..J'ai trouver ce code l pour filtrer un block blk de taille 32*32 :




```

```

Je nz vois pas ou est pass le paramtre taille du Kernel qui est cens etre 11*11 ni les diviation de l'enveloppe de la guassienne qui sont divx=4 et divy=4

Ce code est cens implmenter la partie du code Hong_enhancement pour le fingerprint qui s'occupe de l'application du filtre de Gabor sur le block blk

http://read.pudn.com/downloads112/so...cement.m__.htm

Je vois toujours pas ces formules de Gabor ni leurs paramtres  ::cry::  ::cry:: 

De plus pourquoi gi n'est pas exploit ?

----------


## pseudocode

Je n'y connais pas grand chose en Matlab, mais il me semble que la fonction gabor_kernel() dfinit un noyau de taille 7*dx,7*dy. Ces deux paramtres dx,dy etant les deux "sigma" du filtre.

----------


## T_Lara

Et pour Fourier pourquoi il n'utilise que la partie reel de la fonction


```

```

et la partie imaginaire !!?

----------


## T_Lara

de meme pourquoi le 


```

```

si ce dernier fait l operation duivante   etant donnee une matrice M[A,B;C,D]

(A,B,C,D de meme taille) cette operation donne en resultat M[D,C;B,A]

----------


## pseudocode

> Et pour Fourier pourquoi il n'utilise que la partie reel de la fonction
> 
> 
> ```
> 
> ```
> 
> et la partie imaginaire !!?


Aucune ide. Je suppose que le signal de dpart est et qu'ils ne s'intressent qu'a la partie relle du rsultat.




> de meme pourquoi le 
> 
> 
> ```
> y       = fftshift(real(f(1:32,1:32)));
> ```


Je suppose que c'est pour prsenter le rsultat de la manire habituelle, avec la frquence "0" centre au milieu de l'image.

----------


## T_Lara

> Je suppose que c'est pour prsenter le rsultat de la manire habituelle, avec la frquence "0" centre au milieu de l'image


Pouvez vous m'expliquer cette phrase ..c'est quoi l'interet et l'effet??

----------


## pseudocode

> Pouvez vous m'expliquer cette phrase ..c'est quoi l'interet et l'effet??


Les forts coefficients sont habituellement tous regroupes autour de la frquence 0. 

Si on ne change pas de repre, ces forts coefficients sont donc autour du point (0,0) c'est  dire en haut  gauche => les valeurs dbordent alors sur les 4 coins de l'image.



En changeant de repre pour mettre cette frquence au centre de l'image, on visualise ces forts coefficients comme un "nuage" homogne.

----------


## T_Lara

Merci bcp pour l'explication  ::):  c'est gentil de votre part

----------


## charmeurga

slt pseudocode




> Pour la postrit, un code java qui applique un filtre de Gabor en passant par une FFT (librairie Jtransforms)


Base sur votre code jessai de  traiter une matrice 32*32
Jarrive pas a faire le FFT et le iFFt a cette matrice  ::arf:: 
Je cre  le classe ComplexArray


```

```

 Mais la FFT et le IFFT me retourne des fausse valeurs  ::nono:: 


Voila linstruction que jcris pour pour le fft


```

```

pour le IFFT aprs, cest


```

```

----------

