Discussion :

[pseudocode]

salut

je suis entrain de comprendre l'algorithme SIFT, mais comme un débitant j'ai pas compris des choses: c'est quoi space scale??? et octave???, s'il vous plait aidez moi

c'est que j'ai compris qu'on obtient space scale a l'aide de la pyramide gaussienne et il y a plusieurs scale dans un octave.
mais j'ai pas compris la notion d'octave????

Un "octave" c'est un ensemble d'étages consecutifs dans la pyramide (= les 'scale'). Chaque étage dans cet octave est calculé a partir de la même image de départ.

Quand on change d'octave, on calcule une nouvelle image de départ en reduisant par 2 les dimensions de l'image de l'octave précédant.



Dans cet exemple, on a 4 octaves (constitués chacun de 3 scales)

[NaguiM0]

Un "octave" c'est un ensemble d'étages consecutifs dans la pyramide (= les 'scale'). Chaque étage dans cet octave est calculé a partir de la même image de départ.

Quand on change d'octave, on calcule une nouvelle image de départ en reduisant par 2 les dimensions de l'image de l'octave précédant.



Dans cet exemple, on a 4 octaves (constitués chacun de 3 scales)

Merci pseudocode, c'est clair maintenant la notion octave et scale, je suis entrain de lire l'article de Low, et j'espère que je poserai d'autres questions, encore merci

[NaguiM0]

salut ,helllllp me, j'ai beaucoup des questions pour mieux comprendre l'algorithme de SIFT,

Quand on change d'octave, on calcule une nouvelle image de départ en reduisant par 2 les dimensions de l'image de l'octave précédant.


en fait , quelle est l'image qui sera utiliser pour le deuxième octave et reduire en taille, est ce que l'image originale ou l'image lissée par 2sigma????

et d'après ce lien: http://s1.e-monsite.com/2009/09/20/76584046lufimpu-luviya-yannick-caracterisation-d-images-par-descripteurs-locaux-invariants-pdf.pdf[/URL]

et dans la partie: Localisation des points d’intérêt, j'ai pas bien compris cette phase, (interpolation de Taylor et l'annulation de la dérivée de D(X)).??????

est ce que ça concerne les extremums d'une seule DoG ou tous les extremums de tout les DoGs ???
encore X=[x,y,sigma], X c'est un extremum???

je trouve encore dans ce papier que: Si la valeur de X est telle que |x|>1/2, ou |y|>1/2, ou bien |σ|> kσ0 /2 alors cela signifie que l'extremum se situe dans un plus proche voisinage d'un des points voisins du point d'intérêt.

si x et y sont les coordonnées d'un extremum, comment x et y sont réel???

merci pour vos réponses

[pseudocode]

Quand on change d'octave, on calcule une nouvelle image de départ en reduisant par 2 les dimensions de l'image de l'octave précédant.
en fait , quelle est l'image qui sera utiliser pour le deuxième octave et reduire en taille, est ce que l'image originale ou l'image lissée par 2sigma????

La théorie des scale-space nous dit qu'il faut réduire par 2 l'échelle de départ (sigma). Mais si on se contente de réduire en prenant un point sur 2, on perd beaucoup d'info, c'est logique.

L'idéal est donc de faire un "resampling", par exemple en prenant la moyenne gaussienne locale au voisinnage d'un pixel. Or, ce moyennage par gaussienne est déjà fait si on prend directement les valeurs dans l'image 2*sigma !!

Donc la réponse est : il faut "resampler" l'image de départ, ce qui est peut être fait en prenant un point sur deux dans l'image 2*sigma.

dans la partie: Localisation des points d’intérêt, j'ai pas bien compris cette phase, (interpolation de Taylor et l'annulation de la dérivée de D(X)).??????

est ce que ça concerne les extremums d'une seule DoG ou tous les extremums de tout les DoGs ???
encore X=[x,y,sigma], X c'est un extremum???

Lorsqu'on trouve un extremum local (en coordonnées entieres) dans une image réduite, la position de cette extremum dans l'image de départ n'est pas tres précise.

Si on trouve un extremum en (10,10) dans l'image divisée par 16, alors dans l'image originale cet extremum est quelque part dans le carré (160,160)-(175,175).

L'idée c'est donc de calculer les coordonnées de l'extremum local avec des coordonnées réelles, afin d'avoir une meilleure précision dans l'image originale.

je trouve encore dans ce papier que: Si la valeur de X est telle que |x|>1/2, ou |y|>1/2, ou bien |σ|> kσ0 /2 alors cela signifie que l'extremum se situe dans un plus proche voisinage d'un des points voisins du point d'intérêt. si x et y sont les coordonnées d'un extremum, comment x et y sont réel???

Comme dit juste avant, les coordonnées de l'extremum local sont réelles.

[NaguiM0]

encore moi,

merci j'ai bien compris la notion de resampling.

mais les questions que je veux vous poser:

1. est ce qu'on fait l'interpolation de les extremums de chaque DoG (c a d on parcourt DoG par DoG)??

2. c'est quoi la fonction d'analyse D utilisée dans la fonction de taylor??


merci encore

[pseudocode]

1. est ce qu'on fait l'interpolation de les extremums de chaque DoG (c a d on parcourt DoG par DoG)??

? Je ne comprend pas bien la question.

En premier lieu, on cherche les points (x,y,s) (en coordonnées entières) qui sont des extrema locaux, c'est à dire plus grands que leurs 26 voisins.

Ensuite on raffine ces extrema locaux en calculant leurs coordonnées réelles.

2. c'est quoi la fonction d'analyse D utilisée dans la fonction de taylor??

Heu, c'est la valeur la Dog pour n'importe quelle coordonnées réelles (x,y,s).

[NaguiM0]

? Je ne comprend pas bien la question.

En premier lieu, on cherche les points (x,y,s) (en coordonnées entières) qui sont des extrema locaux, c'est à dire plus grands que leurs 26 voisins.

Ensuite on raffine ces extrema locaux en calculant leurs coordonnées réelles.



Heu, c'est la valeur la Dog pour n'importe quelle coordonnées réelles (x,y,s).

Merci pseudocode, c mieux et plus claire maintenant.

[NaguiM0]

je suis entrain de déterminer l'algorithme de SIFT, je trouve des difficultés au niveau de la localisation des points d'intérêts. pour cela j'ai préparé un petit exemple pour le mieux comprendre lorsque vous me répondez à quelques questions.

si je pose l'image originale est la suivante:


après la transformation pyramidale et le DoG sont présentées comme suit:


Les extremas : ces sont les pixels avec le couleur rouge

Pour la localisation des points d’intérêts, on va commencer par Re-déplacement : c à d on utilise l’interpolation de Taylor pour passer d’une coordonnée entière à une coordonnée réelle.




Et
dD(x)/dx = ( D(x+1) - D(x-1) )/2 : alors si je prend 2 cas :
a) X(2,4,k*σ)= 0.9911
b) X(1,1,k* k*σ)= 0.0339
A quoi égale , D(x), D,dD(x)/dx et ^x.
En faite, comment je peux calculer l’interpolation de Taylor selon mon exemple.

Merci pour vos réponses.

[pseudocode]

Je n'ai pas vraiment envie de calculer a la main les différentiation et les calculs de matrice sur ton exemple . Mais je vais essayer d'expliquer le principe.

On cherche X (noté X chapeau dans le papier de Lowe) tel que : H.X=-G

ou H est la matrice hessienne (derivées secondes) et G le gradient (dérivées premières). C'est à dire, en explicitant les termes :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
|d²D(x,y,s)/dx²   d²D(x,y,s)/dxdy  d²D(x,y,s)/dxds|   |x|     |dD(x,y,s)/dx|
|d²D(x,y,s)/dydx  d²D(x,y,s)/dy²   d²D(x,y,s)/dyds| . |y| = - |dD(x,y,s)/dy|
|d²D(x,y,s)/dsdx  d²D(x,y,s)/dsdy  d²D(x,y,s)/ds² |   |s|     |dD(x,y,s)/ds|

On calcule les coefficients de H et G en utilisant les formules de différentiation discrètes (cf post précédents). Par exemple :

d²D(x,y,s)/dydx
= d( dD(x,y,s)/dy )/dx
= d( 0.5*(D(x,y+1,s)-D(x,y-1,s)) )
= 0.25*(D(x+1,y+1,s)-D(x+1,y-1,s)-D(x-1,y+1,s)+D(x-1,y-1,s))

(idem pour les autres coefs)

Reste à trouver (x,y,s) qui est solution de ce système 3x3. Par exemple par la méthode d'elimination de Gauss, ou l'inversion de la matrice H, ou autre...

[NaguiM0]

Salut pseudocode, merci pour vos réponses ,

c’est plus claire la partie localisation des points d’intérêt, mais juste une petite question : que représente D ?? est ce qu’on peut considérer D comme un tableau de 3 colonnes (x, y, σ) et n lignes (n : nombre de points d’intérêts) ?? c a d lorsque si je calcule :

dD/dx= D(x+1,y, σ )-D(x-1,y, σ )/2

D(x+1,y, σ ) et D(x-1,y, σ ) représente quoi ?? les voisins d’un pixel de point d’intérêt dans DoG, ou les points d’intérêts suivant et précédent ??


Je me suis bloqué aussi dans la partie suivante pour la création d’un descripteur, en faite:

- Pour calculer (rho, theta ), je dois connaître L(x,y). est ce que L(x,y) représente la convolution de l’image originale par filtre de gauss c a d la première étape avant de passer à la différence gaussien ??
- Est comment je peux crée un histogramme d'orientation en fonction de rho, theta, (l’axe des ordonnés représente quoi ??)

Remerci encore pour les réponses

[pseudocode]

I : c'est l'image de départ --> c'est un tableau 2D
I(x,y) : c'est le point de coordonnée (x,y) dans l'image I

L(σ) : c'est l'image à l'echelle σ = floutée avec une gaussienne de variance σ² --> c'est un tableau 2D
L(x,y,σ) : c'est le point de coordonnée (x,y) dans l'image d'echelle σ

D(σ) : c'est la DoG d'echelle σ = L(kσ)-L(σ) --> c'est un tableau 2D
D(x,y,σ) : c'est le point de coordonnée (x,y) dans la DoG d'echelle σ


l'image I, les images L(σ) et les D(σ) sont donc tous des tableaux à deux dimensions.

D(x+1,y, σ ) et D(x-1,y, σ ) représente quoi ?? les voisins d’un pixel de point d’intérêt dans DoG, ou les points d’intérêts suivant et précédent ??

D(x+1,y,σ) : c'est le point de coordonnée (x+1,y) dans la Dog d'echelle σ
D(x-1,y,σ) : c'est le point de coordonnée (x-1,y) dans la Dog d'echelle σ

C'est à dire qu'on prend le tableau 2D correspondant a D(σ) et on regarde les deux points (x+1,y) et (x-1,y)

Je me suis bloqué aussi dans la partie suivante pour la création d’un descripteur, en faite:
- Pour calculer (rho, theta ), je dois connaître L(x,y). est ce que L(x,y) représente la convolution de l’image originale par filtre de gauss c a d la première étape avant de passer à la différence gaussien ??

oui.

- Est comment je peux crée un histogramme d'orientation en fonction de rho, theta, (l’axe des ordonnés représente quoi ??)

L'axe des ordonnés représente l'angle thêta.

C'est à dire qu'on va créer un tableau 1D (l'histogramme) qui a pour index la valeur de thêta. On limite thêta a 36 valeurs possibles, c'est à dire qu'on fait des "tranches" de 10°.

0°<=theta<10° --> index=0
10°<=theta<20° --> index=1
20°<=theta<30° --> index=2
...
350°<=theta<360° --> index=35

[NaguiM0]

salut pseudocode

1) Pour déterminer Theta et l’amplitude du gradient, il faut travailler avec un voisinage 16x16 centré sur le point-clé.
Comment je peux déterminer un voisinage 16*16 ? c a d je peux déterminer un voisinage 3*3 mais 16*16??

2) Un histogramme des orientations du gradient est alors calculé à partir des pixels de la région autour du « keypoint », chaque contribution étant pondérée par la magnitude de son gradient et par une gaussienne avec σ égale à 1.5 fois l’échelle du point clé.
En faite, je n’ai pas compris ce paragraphe ?

3) Après la détermination de l’angle Thetamax, comment on va travailler sur un voisinage 16x16 tourné d'un angle Thetamax ?

[pseudocode]

salut pseudocode

1) Pour déterminer Theta et l’amplitude du gradient, il faut travailler avec un voisinage 16x16 centré sur le point-clé.
Comment je peux déterminer un voisinage 16*16 ? c a d je peux déterminer un voisinage 3*3 mais 16*16??

Je suppose que c'est parce que le voisinage est un nombre pair que ca te pose problème ?

Dans ce cas, il ne faut pas oublier que les coordonnées du point-clé ne sont de toutes facons pas entières. Donc les coordonnées des pixels du voisinage ne seront pas entières non plus. Il faudra soit arrondir, soit faire une interpolation.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
// point-clé (x,y)
 
for(i=0;i<=7;i++)
  for(j=0;j<=7;j++) {
    // point du voisinage (xs,ys), arrondi au plus proche
    int xs = (int) (x-3.5+i);
    int ys = (int) (y-3.5+j);
  }
}

2) Un histogramme des orientations du gradient est alors calculé à partir des pixels de la région autour du « keypoint », chaque contribution étant pondérée par la magnitude de son gradient et par une gaussienne avec σ égale à 1.5 fois l’échelle du point clé.
En faite, je n’ai pas compris ce paragraphe ?

Il faut augmenter l'accumulateur de l'histogramme correspondant au "theta" du gradient de chaque pixel du voisinage.

Cette augmentation dépend de la magnitude du gradient et de la "distance" entre le pixel du voisinage et le point clé : plus le pixel est loin, moins il contribue (ce qui est logique).

histo[theta] += magnitude * gaussienne( distance(pixel,point-clé) , 1.5*σ )

3) Après la détermination de l’angle Thetamax, comment on va travailler sur un voisinage 16x16 tourné d'un angle Thetamax ?

Dans la théorie, il faut faire une rotation des coordonnées des pixels du voisinage. Personnellement, je garde le meme voisinage (non tourné) et je décale juste la valeur "theta" du gradient des pixels.

Ainsi, dans une région d'orientation THETAREGION, un pixel du voisinage aura une orientation "corrigée" de : theta-THETAREGION

[OujAA]

Bonjour,

J'ai quelques questions concernant les descripteurs sift.

Un voisinage doit être définit une première fois autour du point d'intérêt sur l'image de notre pyramide gaussienne la plus proche de l'extrema détecté afin de trouver l'orientation du point.
Mais ne serait-il pas judicieux de prendre en compte l'interpolation de la taille de l'extrema afin de définir un voisinage de taille totalement relative au point ?

Puis, si on se place à la gaussienne correspondante avec un voisinage pondéré par un noyau gaussien de σ = 1.5 * "l'échelle du keypoint", je ne voie pas bien le rapport entre l'échelle du keypoint et la pondération puisque l'on est déjà placé à la gaussienne correspondante. Ou bien faut-il utiliser σ = 1.5 puisque l'on est déjà placé sur la bonne gaussienne ?

Enfin, concernant le descripteur lui-même, j'ai le même problème avec la pondération du voisinage 16*16.

Pourriez-vous m'aider s'il vous plaît ?

[pseudocode]

Mais ne serait-il pas judicieux de prendre en compte l'interpolation de la taille de l'extrema afin de définir un voisinage de taille totalement relative au point ?

"l'interpolation de la taille de l'extrema" ? Que veux-tu dire ?

Puis, si on se place à la gaussienne correspondante avec un voisinage pondéré par un noyau gaussien de σ = 1.5 * "l'échelle du keypoint", je ne voie pas bien le rapport entre l'échelle du keypoint et la pondération puisque l'on est déjà placé à la gaussienne correspondante. Ou bien faut-il utiliser σ = 1.5 puisque l'on est déjà placé sur la bonne gaussienne ?

Il n'y a pas de rapport avec l'échelle du keypoint. Cette pondération est utilisée pour lisser les valeurs de l'histogramme 36 bins (c'est la discretisation des orientations 360° -> 36 bins de 10°)

Enfin, concernant le descripteur lui-même, j'ai le même problème avec la pondération du voisinage 16*16.

Idem. Cette pondération sert à lisser les valeurs (atténuer progressivement les valeurs des pixels qui sont loin du centre)

[OujAA]

Merci de ta réponse.

1)

"l'interpolation de la taille de l'extrema" ? Que veux-tu dire ?

On trouve le point d'intérêt (x, y, σ) en le comparant aux 26 points dans la pyramide, puis on utilise Taylor afin de trouver plus précisément la position du keypoint dans le scale space. On trouve alors des x+Δx, y+Δy, σ+Δσ réels et assez précis.

Je pensais utiliser ce σ+Δσ afin de non seulement me placer à l'image floutée la plus proche du point, mais aussi afin de définir un voisinage en fonction de ce Δσ. Par exemple, un Δσ élevé serait représenté par un voisinage défini plus grand sur l'image floutée.

2)

Il n'y a pas de rapport avec l'échelle du keypoint. Cette pondération est utilisée pour lisser les valeurs de l'histogramme 36 bins (c'est la discretisation des orientations 360° -> 36 bins de 10°)

D'accord, donc chaque amplitude du gradient sera pondéré par une fonction du type exp(-(x²+y²)/σ²) avec un sigma bien choisi.

Dans la documentation de Lowe, il est dit :

Each sample added to the histogram is weighted by its gradient magnitude and by a Gaussian-weighted circular window with a σ that is 1.5 times that of the scale of the keypoint.

Je ne comprend pas quel σ utiliser. Quel valeur faut-il ?

3)
Puis, pour le descripteur :

A Gaussian weighting function with σ equal to one half the width of the descriptor window is used to assign a weight to the magnitude of each sample point.

Il faudrait choisir pour un voisinage de 16*16 pixels un sigma de 16*1.5 = 24 ?
Cela ferait une pondération de exp(-8²/24²)=0,895 sur les bords du voisinage, ce qui ne ressemble pas à une vrai pondération.
Encore une fois, je fais appel à votre savoir.


4)
Sinon, si j'ai compris le processus, globalement il faut :
¤ Se placer à l'échelle adaptée.
¤ Calculer le gradient sur un voisinage assez grand.
¤ Trouver l'orientation maximale en remplissant 36 bins avec l'amplitude du gradient pondéré par la gaussienne.
¤ Définir un voisinage de 16*16 comportant 4*4 sous-régions tournées en fonction de l'orientation trouvée.
¤ Remplir les 8 bins (en tenant compte du changement d'orientation) de chaque sous-région en pondérant avec un gaussienne et le facteur 1-d où d est la distance au centre de la sous-région.

Merci par avance à tous ceux qui voudront bien consacrer un petit peu de leur temps à ce long message.

[pseudocode]

Je pensais utiliser ce σ+Δσ afin de non seulement me placer à l'image floutée la plus proche du point, mais aussi afin de définir un voisinage en fonction de ce Δσ. Par exemple, un Δσ élevé serait représenté par un voisinage défini plus grand sur l'image floutée.

Ah. Oui ca serait une possibilité, pour avoir des valeurs plus précises. Mais je en sais pas si le résultat sera notable, car l'algo de Lowe fait beaucoup de simplifications, approximations, etc. Je ne sais pas si ton amélioration aura beaucoup d'effet.

Je ne comprend pas quel σ utiliser. Quel valeur faut-il ?

Each sample added to the histogram is weighted by its gradient magnitude and by a Gaussian-weighted circular window with a σ that is 1.5 times that of the scale of the keypoint.

Le passage dit qu'il faut prendre 1.5*echelle du keypoint = 1.5*(σ+Δσ)

A Gaussian weighting function with σ equal to one half the width of the descriptor window is used to assign a weight to the magnitude of each sample point.

Il faudrait choisir pour un voisinage de 16*16 pixels un sigma de 16*1.5 = 24 ?

Le passage dit "one half the width", c'est à dire la moitié de la taille du voisinage --> 8

Sinon, si j'ai compris le processus, globalement il faut :
¤ Se placer à l'échelle adaptée.
¤ Calculer le gradient sur un voisinage assez grand.
¤ Trouver l'orientation maximale en remplissant 36 bins avec l'amplitude du gradient pondéré par la gaussienne.
¤ Définir un voisinage de 16*16 comportant 4*4 sous-régions tournées en fonction de l'orientation trouvée.
¤ Remplir les 8 bins (en tenant compte du changement d'orientation) de chaque sous-région en pondérant avec un gaussienne et le facteur 1-d où d est la distance au centre de la sous-région.

Oui, c'est ca.

[OujAA]

Merci beaucoup !

[fzied]

pseudocode :

Il faut augmenter l'accumulateur de l'histogramme correspondant au "theta" du gradient de chaque pixel du voisinage.

Cette augmentation dépend de la magnitude du gradient et de la "distance" entre le pixel du voisinage et le point clé : plus le pixel est loin, moins il contribue (ce qui est logique).

histo[theta] += magnitude * gaussienne( distance(pixel,point-clé) , 1.5*σ )


bonjour,
je commence à etudier l'algo de sift, cette discussion a été très bénéfique.
juste un point qui n'est pas clair pour moi
pour le calcul de l'histogramme du descripteur (c'est à dire apres avoir defini l'orientation dominante) est ce que on utilise la même formule pour accumuler les valeurs et si c'est le cas comment y integrer la distance "d"
Merci

[pseudocode]

bonjour,
je commence à etudier l'algo de sift, cette discussion a été très bénéfique.
juste un point qui n'est pas clair pour moi
pour le calcul de l'histogramme du descripteur (c'est à dire apres avoir defini l'orientation dominante) est ce que on utilise la même formule pour accumuler les valeurs et si c'est le cas comment y integrer la distance "d"
Merci

Non. Pour le calcul du descripteur on n'utilise pas le lissage par la gaussienne.

La zone d'intérêt de 256 pixels (16x16) est divisée en 16 carrés (4x4) de 16 pixels (4x4).

Pour chaque carré, on construit un histogramme de 8 orientations : 0°, 45°, 90°, 135°, 180°, 225°, 270° et 315°

Une valeur d'angle "theta" d'un pixel (i,j) est distribué sur l'histogramme du carré du pixel (i,j) ainsi que sur l'histogramme des 8 carrés voisins. La valeur distributé dépend de la distance entre le pixel (i,j) et le centre du carré (xc,yc), et également de la valeur de l'angle theta.

Le papier de Lowe indique qu'on doit utiliser une interpolation trilinéaire. C'est à dire que le coefficient d'atténuation varie linéairement pour chaque composante : i, j et theta

- Pour theta, c'est une interpolation linéaire entre les 2 bins les plus proches.

- Pour i et j, c'est une interpolation bilinéaire entre les centres des carrés les plus proches