Comprendre le Descripteur SIFT

[ibnensi]

Bonjour à tous,


Je suis une débutante en analyse d'images.

Je viens de commencer mon projet de recherche. Comme première étape, je dois comprendre le déroulement du descripteur SIFT.

J'ai lu une partie de l'article de David Lowe. Cependant, je trouve une difficulté à décortiquer son contenu (sauf la première partie de la différence de Gaussiennes).

Dois je me documenter avant sur quelques points généraux de l'analyse d'images?

En fait, j'ai cherché une autre source documentaire sur le net mais je n'ai pas trouvé,

Merci de m'aider SVP,

Bon travail à tous,

[romanzo]

Salut,

Tu trouveras tout ce dont tu as besoin ici
http://www.developpez.net/forums/d52...gorithme-sift/

[ibnensi]

Envoyé par romanzo

Salut,

Tu trouveras tout ce dont tu as besoin ici
http://www.developpez.net/forums/d52...gorithme-sift/

Bonjour,

Merci beaucoup,

Bonne journée,

[ibnensi]

Bonjour,

J'ai bien vu la discussion du lien http://www.developpez.net/forums/d52...gorithme-sift/. Ce lien m'a beaucoup aidé et m'a éclairci plusieurs points flous surtout dans la première partie de l'article de David Lowe "Detection of scale-space extrema". Je vous remercie :-).

Cependant, il reste quelques parties que je n'ai comprises:

• Pourquoi LOWE a utilisé la méthode de pyramide (octave) et appliqué successivement la différence de gaussienne ?
  
• Est ce que si on choisit 3 niveaux de pyramides par exemple, faut-il avoir 3 DOGs par octave?
  
• Pourquoi on calcule l'interpolation de taylor pour la fonction DOGs? que représente l'offset transposé((x,y,sigma))? en fait, ce que j'ai compris à partir de ce forum que les coordonnées entières d'un point clé sont déterminés en comparant chaque point avec ses 26 voisins, ensuite, les coordonnées réelles sont obtenues en interpolant chaque DOG par Taylor. Je n'ai pas encore saisi le lien entre ses deux étapes.
  
• Je n'ai encore compris ce que David Lowe cherche à prouver dans les deux sections "Frequency of sampling in scale" et "Frequency of sampling in the spatial domain".
  
• "For the experiments in this paper, all extrema with a value of |D(ˆx)| less than 0.03 were discarded (as before, we assume image pixel values in the range [0,1])", pourquoi David lowe a opté pour ce choix?
  
• Dans l'étape d'élimination des points se trouvant sur les arêtes, je n'ai compris comment David Lowe procède?

Merci d'avance,

[pseudocode]

Envoyé par ibnensi

Pourquoi LOWE a utilisé la méthode de pyramide (octave) et appliqué successivement la différence de gaussienne ?

C'est une approximation rapide pour le calcul du Laplacien, afin de détecter les blobs.

Est ce que si on choisit 3 niveaux de pyramides par exemple, faut-il avoir 3 DOGs par octave?

Le nombre d'octaves et le nombre de niveau par octave ne sont pas liés.

Pourquoi on calcule l'interpolation de taylor pour la fonction DOGs? que représente l'offset transposé((x,y,sigma))? en fait, ce que j'ai compris à partir de ce forum que les coordonnées entières d'un point clé sont déterminés en comparant chaque point avec ses 26 voisins, ensuite, les coordonnées réelles sont obtenues en interpolant chaque DOG par Taylor. Je n'ai pas encore saisi le lien entre ses deux étapes.

Lors de la recherche de maximum, on trouve un point qui est en fait un pixel sur un des niveaux. Ce n'est qu'une approximation de l'endroit où se trouve réellement le point-clé. Pour avoir l'endroit exact il faudrait une résolution infiniment précise = une infinité de niveaux et de pixels.

L'interpolation de taylor permet d'avoir une approximation plus précise de cet endroit exact à partir des niveaux et pixels dont on dispose.

Je n'ai encore compris ce que David Lowe cherche à prouver dans les deux sections "Frequency of sampling in scale" et "Frequency of sampling in the spatial domain".

Lowe a fait des essais et conclu que les meilleures valeurs pour lui étaient 3 DOGs par octave et sigma=1.6

"For the experiments in this paper, all extrema with a value of |D(ˆx)| less than 0.03 were discarded (as before, we assume image pixel values in the range [0,1])", pourquoi David lowe a opté pour ce choix?

On ne s'interesse qu'aux points ayant un fort laplacien : les point avec des valeurs trop basses sont éliminés. Je ne sais pas pourquoi il a choisi spécifiquement 0.03.

Dans l'étape d'élimination des points se trouvant sur les arêtes, je n'ai compris comment David Lowe procède?

Les vecteurs propres de la Hessienne nous donne les 2 principales directions du blob. Les 2 valeurs propres associées nous donne l'influence de chaque direction.

Si les 2 valeurs propres sont grandes, le blob est fortement attiré dans 2 directions différentes => c'est donc un coin.

Si une seule valeur propre est grande, le blob est fortement attiré dans une seule direction => c'est donc une arête.

[ibnensi]

Envoyé par pseudocode

C'est une approximation rapide pour le calcul du Laplacien, afin de détecter les blobs.



Le nombre d'octaves et le nombre de niveau par octave ne sont pas liés.



Lors de la recherche de maximum, on trouve un point qui est en fait un pixel sur un des niveaux. Ce n'est qu'une approximation de l'endroit où se trouve réellement le point-clé. Pour avoir l'endroit exact il faudrait une résolution infiniment précise = une infinité de niveaux et de pixels.

L'interpolation de taylor permet d'avoir une approximation plus précise de cet endroit exact à partir des niveaux et pixels dont on dispose.



Lowe a fait des essais et conclu que les meilleures valeurs pour lui étaient 3 DOGs par octave et sigma=1.6



On ne s'interesse qu'aux points ayant un fort laplacien : les point avec des valeurs trop basses sont éliminés. Je ne sais pas pourquoi il a choisi spécifiquement 0.03.



Les vecteurs propres de la Hessienne nous donne les 2 principales directions du blob. Les 2 valeurs propres associées nous donne l'influence de chaque direction.

Si les 2 valeurs propres sont grandes, le blob est fortement attiré dans 2 directions différentes => c'est donc un coin.

Si une seule valeur propre est grande, le blob est fortement attiré dans une seule direction => c'est donc une arête.

Je vous remercie beaucoup pour votre réponse,

[ibnensi]

Bonjour à tous,

En fait, je suis maintenant à l'étape "assignation d'orientation" et "descripteur du point clé".
Comme je suis très débutante dans ce domaine, je n'ai pas compris grande chose, malgré que j'ai bien feuillé la discussion du lien "http://www.developpez.net/forums/d52...gorithme-sift/". J'ai vu d'autres liens qui définissent plusieurs notions en imagerie tel que l'histogramme des orientations, notion de gradient, etc. Mais, cette partie reste encore floue.

j'ai quelques questions à vous poser:

j'ai compris que l'étape d'assignation d'orientation est nécessaire pour l'invariance en rotation. Elle se fait pour chaque pixel du voisinage du point clé correspondant. On calcule le gradient en fait pour chaque pixel (i,j) au voisinage du point clé. Or, d'après l'étape précédente, les points clés restants sont de coordonnées réelles Pc(x,y). Comment est défini le voisinage de Point clé cad pour quels coordonnées des points le gradiant est calculé?

Pourquoi on divise l'histogramme en 36 intervalles? Est ce que l'histogramme se calcule pour toute la zone couvrant le voisinage?

J'ai pas compris globalement tout le processus, pourquoi Lowe a choisi le gradient/ histogramme pour garantir l'invariance par rotation?

Pourquoi il a divisé après la zone entourant le point clé en 4 zones dont chacune est subdivisé en 16 parties?

Pourquoi il a divisé chaque histogramme de la plus petite zone en 8 intervalles?

Pourquoi chaque fois qu'on calcule un histogramme, il est doublement pondéré?

Je sais que mes questions sont assez simples. Mais, votre aide sera très bénéfique pour moi.

En fait, je ne vois pas l'aspect pratique de toutes les opérations du descripteur SIFT depuis la convolution de l'image initiale jusqu'à la dernière étape.

Merci de m'aider SVP,

[pseudocode]

Envoyé par ibnensi

j'ai compris que l'étape d'assignation d'orientation est nécessaire pour l'invariance en rotation. Elle se fait pour chaque pixel du voisinage du point clé correspondant. On calcule le gradient en fait pour chaque pixel (i,j) au voisinage du point clé. Or, d'après l'étape précédente, les points clés restants sont de coordonnées réelles Pc(x,y). Comment est défini le voisinage de Point clé cad pour quels coordonnées des points le gradiant est calculé?

le voisinage est un rectangle de 16x16 points centré sur le keypoint. Comme les coordonnées du keypoint (P) sont réelles, les coordonnées des 16x16 points du voisinage (Vi,j) sont également réelles.
Vi,j.x = P.x-8+16*i
Vi,j.y = P.y-8+16*j

En théorie, il faut dont calculer la calculer la valeur des points Vi,j par interpolations. Et ensuite on calcule le gradient.

En pratique, on calcule d'abord le gradient sur toute l'images... donc sur des coordonnées entières. Et on interpole la valeur du gradient.

Pourquoi on divise l'histogramme en 36 intervalles? Est ce que l'histogramme se calcule pour toute la zone couvrant le voisinage?

Oui, la recherche de l'orientation principale se fait sur toute la zone couvrant le voisinage. Je ne sais pas pourquoi Lowe a choisi spécifiquement de prendre 36 intervalles.

J'ai pas compris globalement tout le processus, pourquoi Lowe a choisi le gradient/ histogramme pour garantir l'invariance par rotation?

Ce qui garanti l'invariance, c'est qu'on oriente toujours le voisinage par rapport a la direction dominante = au vecteur gradient qui apparait le plus souvent dans le voisinage.

D'où le fait qu'on calcule un histogramme pour trouver l'orientation qui apparait la plus souvent.

Pourquoi il a divisé après la zone entourant le point clé en 4 zones dont chacune est subdivisé en 16 parties? Pourquoi il a divisé chaque histogramme de la plus petite zone en 8 intervalles?

Il a fait des tests et trouvé que c'était de bonnes valeurs.

Pourquoi chaque fois qu'on calcule un histogramme, il est doublement pondéré?

Je ne vois pas de quoi tu parles.

En fait, je ne vois pas l'aspect pratique de toutes les opérations du descripteur SIFT depuis la convolution de l'image initiale jusqu'à la dernière étape.

L'image qui résume le mieux l'idée, c'est celle là :


Pour chaque pixel de l'image, on peut calculer le vecteur gradient (image de gauche). Le gradient nous renseigne sur le contour local.

Les keypoint dans SIFT sont des "coins", c'est a dire des endroits ou le contour change brutalement d'orientation. Ce sont des point particulièrement intéressants car ils sont très spécifiques, il n'y en a pas trop, et ils sont assez invariants aux transformations (zoom, rotation, perspective, ...).

Un bon moyen de décrire ce qui se passe autour d'un keypoint, c'est de décrire les contours autour du keypoint. Donc de regarder les vecteurs gradient dans le voisinage : est-ce qu'ils vont tous dans la même direction, ou dans 2 directions principales, ou dans tous les sens, ...

Pour cela on construit un histogramme qui représente la répartition des vecteurs gradient dans les 8 directions cardinales (image de droite). Lowe a choisi de faire 16 histogrammes, chacun représentant un voisinage de 4x4 pixels.

En mettant bout a bout toutes ces informations, on obtient une "signature" composée de 16 histogrammes * 8 directions cardinales = 128 valeurs.

[ibnensi]

Je vous remercie beaucoup pour votre réponse,

Envoyé par pseudocode

le voisinage est un rectangle de 16x16 points centré sur le keypoint. Comme les coordonnées du keypoint (P) sont réelles, les coordonnées des 16x16 points du voisinage (Vi,j) sont également réelles.
Vi,j.x = P.x-8+16*i
Vi,j.y = P.y-8+16*j

En théorie, il faut dont calculer la calculer la valeur des points Vi,j par interpolations. Et ensuite on calcule le gradient.

En pratique, on calcule d'abord le gradient sur toute l'images... donc sur des coordonnées entières. Et on interpole la valeur du gradient.

D'accord,

Oui, la recherche de l'orientation principale se fait sur toute la zone couvrant le voisinage. Je ne sais pas pourquoi Lowe a choisi spécifiquement de prendre 36 intervalles.

La direction principale est-elle égale à la direction dominante de l'histogramme ?

Ce qui garanti l'invariance, c'est qu'on oriente toujours le voisinage par rapport a la direction dominante = au vecteur gradient qui apparait le plus souvent dans le voisinage.

D'où le fait qu'on calcule un histogramme pour trouver l'orientation qui apparait la plus souvent.

cad l'axe des abscisses de l'histogramme présente les intervalles de l'orientation: 1er intervalle: 0..10
2ème intervalle: 10..20
...
dernier intervalle: 350..360
L'axe d'ordonnées présente la fréquence d'apparition des points ayant une orientation du gradient appartenant à chaque intervalle de l'axe d'abscisses. On sélectionne après l'orientation dominante et on l'attribue au point clé.

Comme c'est cité sur Wikipédia: "À l'issue de cette étape, un point-clé est donc défini par quatre paramètres (x,y,σ,θ)" ==> θ: orientation dominante de l'histogramme??

Je ne vois pas de quoi tu parles.

Je veux dire pourquoi LOWE a choisi de multiplier l'histogramme à 36 intervalles lors de l'étape d'assignation d'orientation d'une part, par une fenêtre circulaire gaussienne de paramètre égal à 1,5 fois le facteur d'échelle du point-clé σ0 ; d'autre part, par l'amplitude de chaque point. Puis, il fait la même chose lors de l'étape de constitution du descripteur du point clé avec 8 intervalles.

L'image qui résume le mieux l'idée, c'est celle là :


Pour chaque pixel de l'image, on peut calculer le vecteur gradient (image de gauche). Le gradient nous renseigne sur le contour local.

Les keypoint dans SIFT sont des "coins", c'est a dire des endroits ou le contour change brutalement d'orientation. Ce sont des point particulièrement intéressants car ils sont très spécifiques, il n'y en a pas trop, et ils sont assez invariants aux transformations (zoom, rotation, perspective, ...).

Un bon moyen de décrire ce qui se passe autour d'un keypoint, c'est de décrire les contours autour du keypoint. Donc de regarder les vecteurs gradient dans le voisinage : est-ce qu'ils vont tous dans la même direction, ou dans 2 directions principales, ou dans tous les sens, ...

Pour cela on construit un histogramme qui représente la répartition des vecteurs gradient dans les 8 directions cardinales (image de droite). Lowe a choisi de faire 16 histogrammes, chacun représentant un voisinage de 4x4 pixels.

En mettant bout a bout toutes ces informations, on obtient une "signature" composée de 16 histogrammes * 8 directions cardinales = 128 valeurs.

D'accord, merci,

cad le descripteur décrit la direction de chaque pixel appartenant au voisinage du point clé en calculant le gradient de chacun et en définissant l'histogramme pour chaque zone de 4*4 pixels??

[pseudocode]

Envoyé par ibnensi

La direction principale est-elle égale à la direction dominante de l'histogramme ?

Oui.

Comme c'est cité sur Wikipédia: "À l'issue de cette étape, un point-clé est donc défini par quatre paramètres (x,y,σ,θ)" ==> θ: orientation dominante de l'histogramme??

Oui.

A noter qu'il peut y avoir plusieurs directions dominantes dans un histogramme. On crée alors un keypoint pour chaque direction dominante trouvée.

Je veux dire pourquoi LOWE a choisi de multiplier l'histogramme à 36 intervalles lors de l'étape d'assignation d'orientation d'une part, par une fenêtre circulaire gaussienne de paramètre égal à 1,5 fois le facteur d'échelle du point-clé σ0 ; d'autre part, par l'amplitude de chaque point. Puis, il fait la même chose lors de l'étape de constitution du descripteur du point clé avec 8 intervalles.

En fait, on accumule des "contributions". Chaque vecteur gradient apporte sa propre contribution à l'histogramme. Ces contributions dépendent de deux choses :
- la "force" du gradient (plus l'amplitude est grande, plus il contribue)
- la distance au keypoint (plus il est proche du keypoint, plus il contribue)

C'est pour cela que la contribution est un produit amplitude*gaussienne.

cad le descripteur décrit la direction de chaque pixel appartenant au voisinage du point clé en calculant le gradient de chacun et en définissant l'histogramme pour chaque zone de 4*4 pixels??

Oui.

Attention a prendre en compte l'orientation du keypoint. La zone 16*16 n'est pas alignée sur les bords de l'image.

[ibnensi]

D'accord,

c'est très clair,

Merci beaucoup pour votre aide,

[ibnensi]

Bonjour à tous,

Je reviens encore à cette discussion.

En fait, j'ai lu la deuxième partie de l'article de LOWE "utilisation du descripteur pour la recherche des objets dans des images". J'ai quelques questions à poser. Si quelqu'un peut m'aider, je serais très reconnaissante.

• Pourquoi Lowe cherche le premier plus proche voisin et le second plus proche voisin ?
  
• Dans la partie "indexation des descripteurs par l'arbre kd, il parle de distance euclidienne d'un descripteur à la base de données des descripteurs des images de référence -->"Par distance d’un nœud à un descripteur, on entend distance euclidienne de la boîte englobante des feuilles sous-jacentes à ce descripteur."
  J'ai pas compris de quelle boîte il parle?
  
• Pourquoi LOWE a utilisé la méthode de Hough Transform? J'ai compris que cette méthode sert à regrouper les correspondances cohérentes du point de vue orientation, échelle, location, etc c'est à dire celle correspondantes à des poses pour le même objet. Puis, LOWE identifier que les clusters contenant au moins 3 correspondances? Pourquoi il a opté pour ce choix?
  
• Dans l'article de LOWE, j'ai pas compris le paragraphe suivant:
  
  "Therefore, we use broad bin sizes of 30 degrees for orientation, a factor of 2 for scale, and 0.25 times the maximum projected training image dimension (using the predicted scale) for location. To avoid the problem of boundary effects in bin assignment, each keypoint match votes for the 2 closest bins in each dimension, giving a total of 16 entries for each hypothesis and further broadening the pose range."
  
  Comment on aura pour chaque hypothèse 16 entrée?
  
  Le 'bin' représente quoi?
  
• Dans la partie 'vérification du modèle par la méthode des moindres carrés', je n'ai pas compris comment obtenir les paramètres de transformation, que représente chaque matrice et vecteur utilisé, l'inconnu à rechercher par le système d'équations Ax=b, quelle est l'interprétation pour faire ceci.
  

Merci d'avance,

Cordialement,

[pseudocode]

Envoyé par ibnensi

Pourquoi Lowe cherche le premier plus proche voisin et le second plus proche voisin ?

C'est pour s'assurer que le descripteur de l'image est proche du descripteur de reference, tout en étant assez éloigné du 2nd plus proche descripteur.

On évite ainsi les faux positifs, car s'il y a une "vraie" correspondance alors le descripteur de reference est nettement plus proche que les autres descripteurs.

Dans la partie "indexation des descripteurs par l'arbre kd, il parle de distance euclidienne d'un descripteur à la base de données des descripteurs des images de référence -->"Par distance d’un nœud à un descripteur, on entend distance euclidienne de la boîte englobante des feuilles sous-jacentes à ce descripteur."
J'ai pas compris de quelle boîte il parle?

Je ne vois pas a quelle partie de l'article de Lowe tu fais référence.

Puis, LOWE identifier que les clusters contenant au moins 3 correspondances? Pourquoi il a opté pour ce choix?

Sans doute parce qu'il a fait des tests.
[*]Dans l'article de LOWE, j'ai pas compris le paragraphe suivant:

Comment on aura pour chaque hypothèse 16 entrée?

une marge de 2 bins pour l'orientation.
pour chaque orientation, une marge de 2 bins pour l'echelle.
pour chaque echelle, une marge de 2 bins pour la position Y
Pour chaque position Y, une marge de 2 bins pour la position X

Soit un total de 2*2*2*2 = 16 votes.

Dans la partie 'vérification du modèle par la méthode des moindres carrés', je n'ai pas compris comment obtenir les paramètres de transformation, que représente chaque matrice et vecteur utilisé, l'inconnu à rechercher par le système d'équations Ax=b, quelle est l'interprétation pour faire ceci.

On cherche la "meilleure" transformation T qui transforme les points du modèle (x1,y1), (x2,y2), ... en points de l'image (u1,v1), (u2,v2), ...

Chaque correspondance peut s'écrire sous forme d'une équation (u,v) = T(x,y). On cherche alors les paramètres de T qui satisfont toutes les équations à la fois.

La méthode des moindres carrés permet d'écrire l'ensemble de toutes ces équations sous forme d'un seul système matriciel Ax=b, et ainsi de trouver d'un coup les meilleurs paramètres pour toutes les équations.

[ibnensi]

Bonjour Monsieur,

Merci beaucoup pour vos réponses,

Cordialement,