Dérivée d'une image : gradients et filtre de Sobel

Version imprimable

20/12/2010, 13h48
betsprite

1 pièce(s) jointe(s)

Dérivée d'une image : gradients et filtre de Sobel

Bonjour,

L'implémentation du détecteur de Harris nécessite le calcul des dérivées en x et y de l'image I.

Pour se faire, j'ai cru comprendre que les masques de convolution permettaient de simuler cette "dérivée" ou plutôt ces gradients en x et y comme le filtre de Sobel. Est-ce vrai ?

Si c'est exacte, le filtre de Sobel peut alors être utilisé afin d'avoir les dérivées en x et y de l'image pour commencer le détecteur de Harris. Seulement, comme doit-on s'y prendre dans l'implémentation ? Vu qu'on doit bien distinguer la dérivée en x et y de l'image, j'imagine qu'il ne faut pas appliquer le masque de convolution de Sobel à chaque pixel de l'image ? Il faut pour Ix (dérivée selon x) d'abord parcourir les x puis pour y, parcourir les y ? (autrement dit, au lieu de faire une boucle sur l'ensemble des pixels, on fait une boucle sur les pixels selon les colonnes puis selon les lignes ?)

Je vous remercie ;)

edit : Ou alors, au lieu de parcourir les lignes puis les colonnes, j'ai l'impression qu'on peut tout simplement reparcourir toute l'image avec un masque de convolution adaptée à la dérivée en x et dérivée en y (deux masques de convolutions différents). Mais comment savoir quel masque va permettre de dériver selon x et selon y ?

J'ai mis en pièce-jointe une image qui reprend cette idée mais je ne comprends pas très bien le raisonnement fait pour différencier la dérivée selon x de celle selon y, notamment à partir de l'approximation simple de la dérivée discrète.
20/12/2010, 19h17
pseudocode

Citation:

Envoyé par betsprite

Pour se faire, j'ai cru comprendre que les masques de convolution permettaient de simuler cette "dérivée" ou plutôt ces gradients en x et y comme le filtre de Sobel. Est-ce vrai ?

Oui, en considérant que la dérivée est la limite du taux de variation

df(x)/dx = limite (f(x+e)-f(x-e)) / 2e, lorsque 'e' tend vers 0

Dans le cas discret, on prend e=1.

Citation:

Si c'est exacte, le filtre de Sobel peut alors être utilisé afin d'avoir les dérivées en x et y de l'image pour commencer le détecteur de Harris. Seulement, comme doit-on s'y prendre dans l'implémentation ? Vu qu'on doit bien distinguer la dérivée en x et y de l'image, j'imagine qu'il ne faut pas appliquer le masque de convolution de Sobel à chaque pixel de l'image ? Il faut pour Ix (dérivée selon x) d'abord parcourir les x puis pour y, parcourir les y ? (autrement dit, au lieu de faire une boucle sur l'ensemble des pixels, on fait une boucle sur les pixels selon les colonnes puis selon les lignes ?)

Il y a effectivement deux masques, correspondant chacun à une variable de dérivation.

dI(x,y)/dx = ( I(x+1,y)-I(x-1,y) ) /2 = 1/2 . (I*SobelX) (x,y)
dI(x,y)/dy = ( I(x,y+1)-I(x,y-1) ) /2 = 1/2 . (I*SobelY) (x,y)
21/12/2010, 10h24
betsprite

Merci pseudocode pour ton aide ;)

En fait, la matrice de convolution proposée par Sobel permet apparemment à la fois de faire une Gaussienne et une dérivée. Mais si on ne prend que la partie de la matrice permettant de faire une dérivée en x et y on aurait quelle matrice de convolution et pourquoi ? (-1 0 1) ?

Aussi, bien que je connaisse la formule générale de la convolution et que j'arrive sans problème à l'appliquer avec deux matrices carrés de même taille, j'ai du mal à voir comment se fait le produit entre une image I de taille 10 sur 8 et une matrice 2x2 par exemple. On découpe la matrice représentant les pixels de l'image en bloc et on fait le produit de convolution de chaque bloc avec le masque ?

Enfin, la dérivée, bien qu'étant réalisée à l'aide d'un masque avec un produit de convolution, ne vais-je pas rencontrer des problèmes aux bords de l'image avec le I(x+1) à droite de l'image et le I(x-1) à gauche (même problème pour les y) ?

Merci ;)
21/12/2010, 12h29
pseudocode

Citation:

Envoyé par betsprite

En fait, la matrice de convolution proposée par Sobel permet apparemment à la fois de faire une Gaussienne et une dérivée. Mais si on ne prend que la partie de la matrice permettant de faire une dérivée en x et y on aurait quelle matrice de convolution et pourquoi ? (-1 0 1) ?

I(x+1,y)-I(x-1,y) = (I(x-1,y) I(x-1,y) I(x+1,y)) x (-1 0 1)

Citation:

Aussi, bien que je connaisse la formule générale de la convolution et que j'arrive sans problème à l'appliquer avec deux matrices carrés de même taille, j'ai du mal à voir comment se fait le produit entre une image I de taille 10 sur 8 et une matrice 2x2 par exemple. On découpe la matrice représentant les pixels de l'image en bloc et on fait le produit de convolution de chaque bloc avec le masque ?

Effectivement on applique le filtre sur une partie de l'image de meme taille que la matrice du filtre. J'ai essayé d'expliquer cela ici.

Citation:

Enfin, la dérivée, bien qu'étant réalisée à l'aide d'un masque avec un produit de convolution, ne vais-je pas rencontrer des problèmes aux bords de l'image avec le I(x+1) à droite de l'image et le I(x-1) à gauche (même problème pour les y) ?

Tout a fait. Mais ce problème n'est pas lié au masque, c'est juste que la valeur de l'image n'est pas définie en dehors des bords. L'idée consiste donc à "étendre" les valeurs de l'image au delà des bords. C'est aussi expliqué dans le lien que j'ai donné.
21/12/2010, 13h16
betsprite

Merci pseudocode !

Citation:

I(x+1,y)-I(x-1,y) = (I(x-1,y) I(x-1,y) I(x+1,y)) x (-1 0 1)

Ici le "x" c'est un produit simple ou de convolution ? parce que il me semble que pour la convolution on multiplie le dernier élément du masque par le premier de l'image etc... (a(i,j)*b(n-i, p-j)) donc se serait plutôt (I(x-1,y) I(x-1,y) I(x+1,y)) x (1 0 -1) non?

Merci ;)
21/12/2010, 19h15
pseudocode

Citation:

Envoyé par betsprite

Ici le "x" c'est un produit simple ou de convolution ? parce que il me semble que pour la convolution on multiplie le dernier élément du masque par le premier de l'image etc... (a(i,j)*b(n-i, p-j)) donc se serait plutôt (I(x-1,y) I(x,y) I(x+1,y)) x (1 0 -1) non?

Merci ;)

Mathématiquement parlant oui, car le produit de convolution croise les termes.

Pourtant, en pratique, on utilise une multiplication terme à terme, donc sans croiser. Surement parce que les ordinateurs sont très performant pour faire ce genre de calculs vectoriels.
22/12/2010, 11h12
betsprite

Citation:

Mathématiquement parlant oui, car le produit de convolution croise les termes.

Pourtant, en pratique, on utilise une multiplication terme à terme, donc sans croiser. Surement parce que les ordinateurs sont très performant pour faire ce genre de calculs vectoriels.

Hum d'accord mais comment l'ordinateur fait la différence alors entre un produit matriciel(multiplication terme à terme) et un produit de convolution ?
22/12/2010, 12h41
pseudocode

Citation:

Envoyé par betsprite

Hum d'accord mais comment l'ordinateur fait la différence alors entre un produit matriciel(multiplication terme à terme) et un produit de convolution ?

L'ordinateur fait ce qu'on lui dit de faire. Il faut donc faire attention à l'opérateur qu'on utilise (convolution, multiplication terme à terme, ...) et en conséquences aux paramètres utilisés (valeurs croisées ou décroisées du filtre)
22/12/2010, 12h53
betsprite

Citation:

L'ordinateur fait ce qu'on lui dit de faire. Il faut donc faire attention à l'opérateur qu'on utilise (convolution, multiplication terme à terme, ...) et en conséquences aux paramètres utilisés (valeurs croisées ou décroisées du filtre)

Je suis d'accord mais dans ce cas la syntaxe ne doit pas être la même non ? Pour une multiplication terme à terme de deux matrices c'est le "x" et pour la convolution c'est une méthode(ou fonction) précise du langage utilisé ?

Du coup je me pose une autre question : Quand tu dis que l'ordinateur fait lui même la convolution et donc sait comment il doit multiplier les matrices même si on n'a pas préparé le masque (pas de croisement), cette "intelligence" ne dépend-t-elle pas du langage et donc de la méthode utilisée ?

Merci encore pseudocode pour ces informations ;)
22/12/2010, 19h13
pseudocode

Citation:

Envoyé par betsprite

Je suis d'accord mais dans ce cas la syntaxe ne doit pas être la même non ? Pour une multiplication terme à terme de deux matrices c'est le "x" et pour la convolution c'est une méthode(ou fonction) précise du langage utilisé ?

Du coup je me pose une autre question : Quand tu dis que l'ordinateur fait lui même la convolution et donc sait comment il doit multiplier les matrices même si on n'a pas préparé le masque (pas de croisement), cette "intelligence" ne dépend-t-elle pas du langage et donc de la méthode utilisée ?

Je n'ai pas dit que l'ordinateur sait comment faire, j'ai dit qu'il faisait ce qu'on lui demandait. Suivant les langages on dispose d'opérateur de multiplication simple, de multiplication terme à terme, de convolution, ou autre.

Classiquement, les langages disposent seulement de la multiplication simple (de 2 réels) et il faut coder soi-même des opérateurs plus compliqués.

Mais certains langages disposent déjà de certains de ces opérateurs. Par exemple en Matlab il y a l'opérateur ".*" qui fait une multiplication terme à terme de deux tableaux.
22/12/2010, 19h33
betsprite

Citation:

Je n'ai pas dit que l'ordinateur sait comment faire, j'ai dit qu'il faisait ce qu'on lui demandait. Suivant les langages on dispose d'opérateur de multiplication simple, de multiplication terme à terme, de convolution, ou autre.

Merci pseudocode pour la précision et désolé d'être un peu insistant sur ce point mais justement, quand tu dis :

Citation:

Pourtant, en pratique, on utilise une multiplication terme à terme, donc sans croiser. Surement parce que les ordinateurs sont très performant pour faire ce genre de calculs vectoriels.

Je ne comprends pas pourquoi tu dis qu'en pratique on utilise une multiplication terme à terme pour faire un produit de convolution. Car même en pratique, on va avoir soit la multiplication terme à terme déjà implémentée et la convolution aussi mais avec une syntaxe différente pour les deux opérateurs soit on aura les deux à implémenter mais ils seront quand même différents.

En gros, pourquoi l'ordinateur reconnaitrait dans la multiplication terme à terme le produit de convolution ? ^^ (je pense que je comprends mal ta phrase en fait)

Ou alors, quand tu dis on utilise une multiplication terme à terme pour faire la convolution, il faut d'abord préparer le masque au croisement...

Merci !
22/12/2010, 19h50
pseudocode

[quote=betsprite;5669617]Merci pseudocode pour la précision et désolé d'être un peu insistant sur ce point mais justement, quand tu dis :

Je ne comprends pas pourquoi tu dis qu'en pratique on utilise une multiplication terme à terme pour faire un produit de convolution. Car même en pratique, on va avoir soit la multiplication terme à terme déjà implémentée et la convolution aussi mais avec une syntaxe différente pour les deux opérateurs soit on aura les deux à implémenter mais ils seront quand même différents.

En gros, pourquoi l'ordinateur reconnaitrait dans la multiplication terme à terme le produit de convolution ? ^^ (je pense que je comprends mal ta phrase en fait)

Citation:

Ou alors, quand tu dis on utilise une multiplication terme à terme pour faire la convolution, il faut d'abord préparer le masque au croisement...

Oui, c'est ça. Il faut préparer le masque suivant l'opérateur utilisé.

Et comme on utilise généralement l'opérateur de multiplication terme à terme, le filtre est donc "décroisé" par rapport à un filtre de convolution. D'où mon message original :

I(x+1,y)-I(x-1,y) = (I(x-1,y) I(x-1,y) I(x+1,y)) x (-1 0 1)

ou "x" représente ici un opérateur de "convolution décroisé", c'est à dire la somme des multiplications terme à terme.
22/12/2010, 19h54
betsprite

Citation:

Oui, c'est ça. Il faut préparer le masque suivant l'opérateur utilisé.

Et comme on utilise généralement l'opérateur de multiplication terme à terme, le filtre est donc "décroisé" par rapport à un filtre de convolution. D'où mon message original :

I(x+1,y)-I(x-1,y) = (I(x-1,y) I(x-1,y) I(x+1,y)) x (-1 0 1)

ou "x" représente ici un opérateur de "convolution décroisé", c'est à dire la somme des multiplications terme à terme.

Ok je comprends mieux :p

Merci encore pseudocode ! je vais essayer d'implémenter ça déjà se sera un bon début pour lé détection de points d'intérêts avec la méthode de Harris.

Merci !