Version imprimable
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.Citation:
Envoyé par NaguiM0
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.
http://xphilipp.developpez.com/contr...scalespace.png
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 merciCitation:
Envoyé par pseudocode
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
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.Citation:
Envoyé par NaguiM0
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.
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.Citation:
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???
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.
Comme dit juste avant, les coordonnées de l'extremum local sont réelles.Citation:
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???
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
:koi: ? Je ne comprend pas bien la question.Citation:
Envoyé par NaguiM0
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).Citation:
2. c'est quoi la fonction d'analyse D utilisée dans la fonction de taylor??
Merci pseudocode, c mieux et plus claire maintenant.Citation:
Envoyé par pseudocode
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:
http://s2.e-monsite.com/2010/01/23/0..._550/Image.jpg
après la transformation pyramidale et le DoG sont présentées comme suit:
http://s2.e-monsite.com/2010/01/23/0...50_550/DOG.jpg
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.
http://s2.e-monsite.com/2010/01/23/0...0/equation.jpg
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.
Je n'ai pas vraiment envie de calculer a la main les différentiation et les calculs de matrice sur ton exemple :aie:. 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 :
On calcule les coefficients de H et G en utilisant les formules de différentiation discrètes (cf post précédents). Par exemple :Code:
2
3
4
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...
Salut pseudocode, merci pour vos réponses :ccool:,
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
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,σ) : c'est le point de coordonnée (x+1,y) dans la Dog d'echelle σCitation:
Envoyé par NaguiM0
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)
oui.Citation:
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 ??
L'axe des ordonnés représente l'angle thêta.Citation:
- Est comment je peux crée un histogramme d'orientation en fonction de rho, theta, (l’axe des ordonnés représente quoi ??)
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
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?? 8O
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 ?
Je suppose que c'est parce que le voisinage est un nombre pair que ca te pose problème ?Citation:
Envoyé par NaguiM0
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:
2
3
4
5
6
7
8
9
Il faut augmenter l'accumulateur de l'histogramme correspondant au "theta" du gradient de chaque pixel du voisinage.Citation:
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 ?
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*σ )
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.Citation:
3) Après la détermination de l’angle Thetamax, comment on va travailler sur un voisinage 16x16 tourné d'un angle Thetamax ?
Ainsi, dans une région d'orientation THETAREGION, un pixel du voisinage aura une orientation "corrigée" de : theta-THETAREGION
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 ?
"l'interpolation de la taille de l'extrema" ? Que veux-tu dire ?Citation:
Envoyé par OujAA
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°)Citation:
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 ?
Idem. Cette pondération sert à lisser les valeurs (atténuer progressivement les valeurs des pixels qui sont loin du centre)Citation:
Enfin, concernant le descripteur lui-même, j'ai le même problème avec la pondération du voisinage 16*16.
Merci de ta réponse.
1)
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.Citation:
"l'interpolation de la taille de l'extrema" ? Que veux-tu dire ?
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)
D'accord, donc chaque amplitude du gradient sera pondéré par une fonction du type exp(-(x²+y²)/σ²) avec un sigma bien choisi.Citation:
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°)
Dans la documentation de Lowe, il est dit :
Je ne comprend pas quel σ utiliser. Quel valeur faut-il ?Citation:
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.
3)
Puis, pour le descripteur :
Il faudrait choisir pour un voisinage de 16*16 pixels un sigma de 16*1.5 = 24 ?Citation:
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.
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.
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.Citation:
Envoyé par OujAA
Le passage dit qu'il faut prendre 1.5*echelle du keypoint = 1.5*(σ+Δσ)Citation:
Je ne comprend pas quel σ utiliser. Quel valeur faut-il ?
Citation:
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 "one half the width", c'est à dire la moitié de la taille du voisinage --> 8Citation:
Il faudrait choisir pour un voisinage de 16*16 pixels un sigma de 16*1.5 = 24 ?Citation:
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.
Oui, c'est ca.Citation:
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 beaucoup ! :ccool:
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:oops:
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.Citation:
Envoyé par fzied
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