# Gnral Dveloppement > Algorithme & Mathmatiques > Traitement d'images >  Algorithme SIFT

## MohEllayali

Bonjour, 

je suis en train de lire la publication de Lowe et j'ai quelques points obscurs, si quelqu'un pouvait les claircir :

On utilise des diffrences de convolus avec des Gaussiennes pour extraire des minima, maxima selon x, y et sigma ... mais d'un autre cot il parle d'octave, et de re-chantillonnage (re-chantilllonn c'est faire un zoom arrire ?? ) avec une interpolation bilinaire,... mais je vois pas l'intret ... en gros je m'embrouille entre la convolution avec des gaussiennes  diffrentes chelles (sigma croissant) et le zoom arrire arrir , je ne vois pas le lien.

Apres nttoyage des outliers, a j'ai compris.

Aprs il cre un histogramme ( si j'ai bien compris, pour assigner une orientation  chaque keypoint), donc si j 'ai bien compris, pour chaque keypoint, il met un masque gaussien, ( mais il dit pas de quelle largeur ), en chaque point de ce voisinage, il calcule l'orientation du gradient, cette orientation a un poid qui est fonction de l'amplitude du gradient et du masque ( mais il dit pas comment on calcule cette fonction), aprs il prend pour orientation le pique de l'histogramme.


ensuite il prends un descripteur de 128 composantes, mais j'ai pas compris ce que reprsente chaque composantes (4*4*8) 

Merci de votre d'avance

----------


## pseudocode

A quel document et  quelle page/ligne fais-tu allusion ?

celui la --> http://citeseer.ist.psu.edu/viewdoc/...10.1.1.14.4931  ?

----------


## paradize3

> Bonjour, 
> 
> je suis en train de lire la publication de Lowe et j'ai quelques points obscurs, si quelqu'un pouvait les claircir :
> 
> On utilise des diffrences de convolus avec des Gaussiennes pour extraire des minima, maxima selon x, y et sigma ... mais d'un autre cot il parle d'octave, et de re-chantillonnage (re-chantilllonn c'est faire un zoom arrire ?? ) avec une interpolation bilinaire,... mais je vois pas l'intret ... en gros je m'embrouille entre la convolution avec des gaussiennes  diffrentes chelles (sigma croissant) et le zoom arrire arrir , je ne vois pas le lien.


Le but c'est de dtecter les points d'intrts a diffrentes chelles. Intuitivement tu peux voir qu'un flou gaussien te permet d'liminer les 'petites' features, tout en conservant les grandes (donc 'dezoomer' lorsque sigma augmente). Un rsultat grosso-modo similaire pourrait tre achev en redimensionnant l'image avec une interpolation - mais cela serait moins efficace. Par contre des que l'octave est atteinte il suffit (en gros) de considrer un pixel sur deux de l'image originale! (en resume: pour dezoomer d'un facteur 1 < s < 2 (chaque estape est appelle scale), il utilise un flou gaussien, lorsque s = 2 (octave) il ne considere qu'un pixel sur deux, etc.).

Apres cette tape, chaque point d'intrt a une position et un 'scale' s. 




> Apres nttoyage des outliers, a j'ai compris.
> 
> Aprs il cre un histogramme ( si j'ai bien compris, pour assigner une orientation  chaque keypoint)


absolument, c'est l'tape cruciale qui permet de rendre le descripteur invariant aux rotations.




> , donc si j 'ai bien compris, pour chaque 
> keypoint, il met un masque gaussien, ( mais il dit pas de quelle largeur ),


sigma proportionnel a s (de combien doit tre indique dans le papier non?...)



> en chaque point de ce voisinage, il calcule l'orientation du gradient, cette orientation a un poids qui est fonction de l'amplitude du gradient et du masque ( mais il dit pas comment on calcule cette fonction),


sigma proportionnel a s?



> aprs il prend pour orientation le pique de l'histogramme.
> 
> ensuite il prends un descripteur de 128 composantes, mais j'ai pas compris ce que reprsente chaque composantes (4*4*8)


Ces composantes reprsentent le voisinage du point d'intrt. Plus precisemment c'est l'ensemble des histogrammes d'orientation du voisinage de ton point d'intrt. Chaque histogramme tant sur 8 composants, et puisque le voisinage est divise en 4x4 rgions, a te donne 8x4x4 = 128 composantes.

----------


## MohEllayali

Bonjour, Merci pour vos rponses,  j'y vois plus claire  ::king:: 

Le papier se trouve ici : 

http://www.cs.ubc.ca/~lowe/papers/ijcv04.pdf




> Le but c'est de dtecter les points d'intrts a diffrentes chelles. Intuitivement tu peux voir qu'un flou gaussien te permet d'liminer les 'petites' features, tout en conservant les grandes (donc 'dezoomer' lorsque sigma augmente). Un rsultat grosso-modo similaire pourrait tre achev en redimensionnant l'image avec une interpolation - mais cela serait moins efficace. Par contre des que l'octave est atteinte il suffit (en gros) de considrer un pixel sur deux de l'image originale! (en resume: pour dezoomer d'un facteur 1 < s < 2 (chaque estape est appelle scale), il utilise un flou gaussien, lorsque s = 2 (octave) il ne considere qu'un pixel sur deux, etc.).
> 
> Apres cette tape, chaque point d'intrt a une position et un 'scale' s.


Merci, maintenant , je vois la dmarche , en effet , il floue l'image 

http://pegasus.cc.ucf.edu/~ja709267/...e construction

et une fois le sigma atteint 2 fois sa valeur initiale ( ici c'est le troisme carre  partir du dessous) , il cre un nouvel octave en r-chantillonant ( en prenant un pixel sur 2) l'image, mais ma question est quand il explore la pyramide il extrait les maxima / minima uniquement du 1er octave (auquel cas  quoi servirait un 2me octave) , ou bien ils entasse tout les octaves les uns sur les autres, en cherchant le maxima . Mais dans ce cas l, comment fait-il ? puisque les images n'ont pas la mme taille d'un octave  un autre ? 





> sigma proportionnel a s (de combien doit tre indique dans le papier non?...)


Oui, en effet dsol  ::oops:: 




> Ces composantes reprsentent le voisinage du point d'intrt. Plus precisemment c'est l'ensemble des histogrammes d'orientation du voisinage de ton point d'intrt. Chaque histogramme tant sur 8 composants, et puisque le voisinage est divise en 4x4 rgions, a te donne 8x4x4 = 128 composantes.


Tout  fait , mais ce qui me parrait bizzare , c'est la dimension paire de la fentre :
http://pegasus.cc.ucf.edu/~ja709267/...,19,Descriptor

le plus logique , pour que la fentre soit symtrique c'est qu'il soit impaires, autant de pixel  droite qu' gauche

----------


## paradize3

> et une fois le sigma atteint 2 fois sa valeur initiale ( ici c'est le troisme carre  partir du dessous) , il cre un nouvel octave en r-chantillonant ( en prenant un pixel sur 2) l'image, mais ma question est quand il explore la pyramide il extrait les maxima / minima uniquement du 1er octave (auquel cas  quoi servirait un 2me octave) , ou bien ils entasse tout les octaves les uns sur les autres, en cherchant le maxima . Mais dans ce cas l, comment fait-il ? puisque les images n'ont pas la mme taille d'un octave  un autre ?


Chaque octave est divise en N scales (disons N=5 par exemple). Dans un certain octave, pour chercher un point d'interets, tu prends 3 scales conscutifs et pour chaque pixel tu testes s'il est un extrema, si oui -> possible point d'interet.

La mthode s'applique a tous les octaves... Et je ne pense pas qu'il considre les maximas entre le dernier scale d'un octave avec le premier de l'octave suivant.




> Tout  fait , mais ce qui me parrait bizzare , c'est la dimension paire de la fentre :
> http://pegasus.cc.ucf.edu/~ja709267/...,19,Descriptor
> 
> le plus logique , pour que la fentre soit symtrique c'est qu'il soit impaires, autant de pixel  droite qu' gauche


Premirement, n'oublie pas qu'un point d'intrt a une prcision plus prcise qu'un pixel. Thoriquement je ne pense pas qu'il y ait a pas de raison pour que ta fentre soit aligne sur un pixel, on pourrait s'en sortir avec des interpolations. Dans la pratique je pense que la fentre est suffisamment grande pour que a ne cause pas de problme de l'aligner sur le pixel le plus proche du point d'intrt (la description du point d'intrt ne sera peut-tre 'exacte', mais la localisation calcule prcdemment l'est, c'est l'important). 

Salutations,

Greg

----------


## MohEllayali

Merci beaucoup Greg, tout est claire pour moi maintenant  ::ave::  ::): 

Salutation ,

----------


## yoannbred

Bonjour,
Je voudrais juste savoir si l'on est oblig de parcourir plusieurs octaves pour traiter les images ou si une seule suffit.
Si on doit en parcourir plusieurs, pourriez vous m'expliquer pourquoi? combien faut-il en parcourir? comment mettre les donnes en commun?
Merci d'avance pour toutes les rponses.

J'ai oubli de demander une petite chose en plus.
Si je considre k=racine(2), j'aurais s=2 donc s+3=5 images par octave. Si j'ai bien compris les octaves sont divises en parties gales.
Ainsi si je prend sigma=1 et que comme le dit Lowe l'avant dernire image de l'octave  un sigma double (ici 2) alors j'aurais dans l'ordre des images avec comme indice:
2,5sigma
2sigma
1,5sigma
1sigma
0,5sigma

Merci pour les rponses...

----------


## MohEllayali

salut,

d'aprs ce que j'ai compris, plus t'as d'octave , plus t'as de features, dans la publication de Lowe, il donne un nombre optimal d'octave, mais t'es pas oblig d'utiliser le mme

----------


## yoannbred

Merci pour ta rponse, je commencais  deseprer!

Je n'ai pas trouv ce nombre d'octaves dans l'article de Lowe, mais aprs avoir surf sur le vague du Web, j'ai compris comment marche les principes dit de "pyramide".

En ce qui concerne les valeurs de sigma, il faut commencer  une valeur jusqu' obtenir le double. Une fois cette valeur atteinte, on "divise" l'image pas deux et on commence une nouvelle octave en reprenant la valeur initiale de sigma.

J'ai pas mal avanc dans mon code, malgrs plusieurs points obscurs, les rsultats pour le moment semblent satisfaisant.

Cependant si quelqu'un  compris l'utilisation de l'expansion de Taylor et comment implmenter cette formule, je suis preneur car je m'embrouille l'esprit et j'avoue avoir des difficults  la comprendre.

Bon j'ajoute des questions au fur et  mesure au cas ou un bonne me passerait par l!

Pour la cration des DOG, je pense qu'il faut faire la diffrence et ne pas prendre la valeur absolue.

Aprs pour la dtection des extremas, je compare chaque pixel avec ses 28 voisins (8 sur le mme DOG et 9 sur chacun des 2 autres DOG). Est ce que je dois faire ma comparaison en strictement positif ou strictement ngatif?

Up! Bon pour ceux que sa intresse, j'ai pas mal de rponses  mes questions et j'ai bien avanc sur l'algo SIFT, si sa peut en aider quelques uns.

See you soon!

----------


## ArgusAzure

> Apparement SIFT ne passionne pas!


Si si, je trouve a trs intressant  :;):

----------


## PRomu@ld

> Bon pour ceux que sa intresse, j'ai pas mal de rponses  mes questions et j'ai bien avanc sur l'algo SIFT, si sa peut en aider quelques uns.


Et bien tu peux nous faire une petite contribution ?  :;):

----------


## yoannbred

Bien sur! Pose ta question et si je le peux, je serai ravi de pouvoir y rpondre.

----------


## ArgusAzure

> Cependant si quelqu'un  compris l'utilisation de l'expansion de Taylor et comment implmenter cette formule, je suis preneur car je m'embrouille l'esprit et j'avoue avoir des difficults  la comprendre.


Je n'ai pas trop compris non plus, mais il doit y avoir moyen de faire plus simple pour un rsultat similaire. 




> Pour la cration des DOG, je pense qu'il faut faire la diffrence et ne pas prendre la valeur absolue.


Je pense aussi




> Aprs pour la dtection des extremas, je compare chaque pixel avec ses 28 voisins (8 sur le mme DOG et 9 sur chacun des 2 autres DOG). Est ce que je dois faire ma comparaison en strictement positif ou strictement ngatif?


Ben je dirais les 2. Tu gardes le keypoint si c'est le maximum ou minimum le tous ses voisins.

----------


## yoannbred

> Citation:
> Envoy par yoannbred Voir le message
> Pour la cration des DOG, je pense qu'il faut faire la diffrence et ne pas prendre la valeur absolue.
> 
> *Je pense aussi*


C'est sur!




> Citation:
> Envoy par yoannbred Voir le message
> Aprs pour la dtection des extremas, je compare chaque pixel avec ses 28 voisins (8 sur le mme DOG et 9 sur chacun des 2 autres DOG). Est ce que je dois faire ma comparaison en strictement positif ou strictement ngatif?
> *
> Ben je dirais les 2. Tu gardes le keypoint si c'est le maximum ou minimum le tous ses voisins.*


Ma question portait sur le *strictement*. Et la rponse est non!
Il suffit que le point ait une valeur maximum ou minimum avec celle de ses voisins, mme si d'autres points ont la mme valeur.




> Citation:
> Envoy par yoannbred Voir le message
> Cependant si quelqu'un  compris l'utilisation de l'expansion de Taylor et comment implmenter cette formule, je suis preneur car je m'embrouille l'esprit et j'avoue avoir des difficults  la comprendre.
> 
> *Je n'ai pas trop compris non plus, mais il doit y avoir moyen de faire plus simple pour un rsultat similaire.*


En dfinitif, ce n'est pas trs compliqu. Ni pour le calcul de l'offset, ni pour le contraste, ni pour les rponses de bord. Il suffit de calculer la matrice suivante:
| Dxx Dxy Dxs |
| Dxy Dyy Dys |
| Dxs Dys Dss |

Le x la coordonne horizontale, le y la verticale et le s correspondant  l'chelle ou au scale.

Pour les calculs exacts, je peux toujours vous les donner si vous voulez.

Moi ce qui me chagrine vraiment c'est de savoir comment j'applique les sigmas celon les chelles.

Pour moi on a vraiment par octave:
k^0*sigma
k^1*sigma
...
k^n*sigma

soit n le nombre d'chelle -1 par octave.

Et si je suis le rsonnement mathmatique de Lowe, j'atteinds ma valeur 2*sigma pour k^(n-2)*sigma.
Donc pour moi, il faut prendre cette image floute et la diviser par deux pour obtenir l'image de base de l'octave suivante.
Un autre point obscur reste  savoir si  cette nouvelle image obtenue, on doit appliquer encore un sigma (k^0*sigma pour la base de l'octave).

Voila si quelqu'un peut m'aider... !!!!

Au fait pour le nombre d'octaves il faut le dfinir en fonction des dimensions de l'image et du filtre gaussien que l'on applique.

----------


## ArgusAzure

> Ma question portait sur le *strictement*. Et la rponse est non!
> Il suffit que le point ait une valeur maximum ou minimum avec celle de ses voisins, mme si d'autres points ont la mme valeur.


Pour le strictement ou non, peut importe, cela n'a pas d'importance. J'aurais mme tendance  tre plus strict en ne gardant un keypoint que si c'est un maximum (ou mininum) et avec assez de diffrence avec le second maximum (ou minimum) atteint par un de ses voisins. Quant on est en limite de seuil, on a de l'instabilit.  Si tu mets des non stricts, il suffit d'un chouilla de bruit pour que ton keypoint ne soit pas retenu car un de ses voisins aura grimp (ou descendu) de 1. Si tu mets une petite marge (du style, je ne garde un keypoint que s'il a un maximum suprieur  110% du second maximum) certes tu auras moins de keypoints, mais ils seront plus robustes.

----------


## yoannbred

Bon alors j'ai compris, un point peu tre gal  un ou deux autres points (keypoint possible) ou  plusieurs points (rgion plane, pas de variation d'intensit). Ce qu'il faut donc faire, c'est dans un premier temps, considr ce point comme un candidat puis le virer lors des tests de contraste si on se trouve dans le second cas.

----------


## PRomu@ld

> Je fais les tests et je te dis sa dans 20 minutes


Juste pour info tu as une implmentation simple ?

----------


## yoannbred

J'ai une implmentation, mais je bosse pour une entreprise sur cette algo... donc je ne peux pas divulguer mon code. Cependant je peux divulguer mon algo  :;): ... Normal c'est celui de Lowe !

----------


## PRomu@ld

> Normal c'est celui de Lowe !


Oui, c'est vident.

Sinon, c'est pas grave pour l'implmentation. Sinon comme a  titre d'information, a prend combien de temps pour l'implmenter ( une poque a m'a intress et a pourrait me reprendre un de ces quatre)

----------


## ArgusAzure

"The University of British Columbia has applied for a patent on the SIFT algorithm in the United States. Commercial applications of this software may require a license from the University of British Columbia. "
C'est possible au usa de dposer un brevet sur un algo publi dans la presse scientifique? C'est impossible en france en tout cas. 
Y aurait-il des choses qu'on nous aurait pas dit ?  :;):

----------


## yoannbred

Ba.... Tout est relatif  :;): 

Sachant que cel dpend de:
-ton niveau en math
-ton niveau en info
-ton niveau en anglais
-la qualit de tes recherches
-la qualit finale que tu attends
-ce que tu dsires implmenter (sift,matching,PCA-sift...)

Personnellement, sachant que je viens juste de valider mon BAC+2  l'ESIEE (ingnieur *lectronique* et informatique). J'ai un niveau suffisant en math et en informatique (mon implmentation est en C). Cependant je ne nie pas avoir eu des difficults et en avoir toujours d'ailleurs pour comprendre Lowe.
En effet, son article est en anglais (ce qui ne me pose pas vraiment de problme, mais les subtilits sont importantes) et d'un niveau en traitement de l'image plutt volu.
Pour ma part j'ai du tout apprendre, du traitement d'un PGM  l'application d'un filtre Gaussien...

Cel fait un mois et demi que je suis dessus et les rsultats sont franchement mdiocres...

A mon avis, la ou les erreurs que j'ai commises ne doivent pas tre normes, mais il reste du boulot.

En tout cas si tu te lances la dedans, compte sur moi pour te filer un coup de main.

----------


## yoannbred

> "The University of British Columbia has applied for a patent on the SIFT algorithm in the United States. Commercial applications of this software may require a license from the University of British Columbia. "
> C'est possible au usa de dposer un brevet sur un algo publi dans la presse scientifique? C'est impossible en france en tout cas. 
> Y aurait-il des choses qu'on nous auraient pas dit ?


Hey hey!!!!

Je me suis renseign justement. En france, un algo ne peut pas appartenir  quelqu'un. Ce qui est personnel c'est l'implmentation que tu en fais.
Donc *en France* tu peux implmenter SIFT et l'utiliser  des fins (*ortho?) commerciales.

----------


## yoannbred

Juste comme sa au passage, quelqu'un connait la mthode pour passer d'un codage sur 8 bits  un codage sur 32 bits pour les niveaux de gris. Je serais tent de multipli toutes mes valeurs par 2^24 mais j'ai un srieux doute. Si quelqu'un peut m'aiguiller?!

----------


## ArgusAzure

> Juste comme sa au passage, quelqu'un connait la mthode pour passer d'un codage sur 8 bits  un codage sur 32 bits pour les niveaux de gris. Je serais tent de multipli toutes mes valeurs par 2^24 mais j'ai un srieux doute. Si quelqu'un peut m'aiguiller?!


Une simple rgle de 3 doit rpondre  tes attentes.
Tu as des valeurs de 0  255 que tu veux taler de 0  2^32-1.
Esprons que le train n'a pas dja draill sur l'aiguillage.

----------


## yoannbred

Jcrois qu'il est en bas de la falaise  :;): 

Merci c'est bien ce que je me disais...

----------


## yoannbred

Personne ne sait exactement comment on calcul le sigma  appliquer  chaque chelle??

----------


## mel84

Bonjour,
Je dois implmenter l'algo de sift pour faire une dtection de point d'intrt mais je n'y comprend pas grand chose! ::calim2:: 
Je me sert de la documentation 'Distinctive Image Features from Scale-Invariant Keypoints'  de Lowe.

Pouvez-vous m'expliquer ce que reprsente 'sigma', 's' et 'k' ??




> Bonjour,
> Si je considre k=racine(2), j'aurais s=2 donc s+3=5 images par octave. Si j'ai bien compris les octaves sont divises en parties gales.
> Ainsi si je prend sigma=1 et que comme le dit Lowe l'avant dernire image de l'octave  un sigma double (ici 2) alors j'aurais dans l'ordre des images avec comme indice:
> 2,5sigma
> 2sigma
> 1,5sigma
> 1sigma
> 0,5sigma


Salut, 
Comment fais-tu pour avoir a??
Merci

----------


## pseudocode

> Bonjour,
> Je dois implmenter l'algo de sift pour faire une dtection de point d'intrt mais je n'y comprend pas grand chose!
> Je me sert de la documentation 'Distinctive Image Features from Scale-Invariant Keypoints'  de Lowe.
> 
> Pouvez-vous m'expliquer ce que reprsente 'sigma', 's' et 'k' ??


J'ai post un code pour construire une pyramide gaussienne dans la rubrique "contribuez". C'est dj un premier pas vers SIFT.  ::D: 




> Comment fais-tu pour avoir a??
> Merci


Au dpart, l'image est considre comme ayant une chelle "sigma". A chaque changement d'octave, l'chelle double. Pour les niveaux dans un octave, les chelles doivent s'taler uniformment entre sigma et 2*sigma, c'est a dire suivant une suite gomtrique de raison K=2^(1/nombre de niveaux par octave)

Par exemple, pour 2 octaves et 3 niveaux par octaves:



```

```

Dans la pyramide de Lowe, on ajoute un niveau au dbut et deux  la fin de l'octave pour pouvoir calculer toutes les DoG sans changer d'octave.  :;): 



```

```

----------


## mel84

Je te remercie de ta rponse, c'est dj beaucoup plus clair maintenant!!
Cependant pourquoi on doit ajouter 2 niveau  la fin pour Lowe? un niveau je comprend, mais deux??

----------


## pseudocode

> Je te remercie de ta rponse, c'est dj beaucoup plus clair maintenant!!
> Cependant pourquoi on doit ajouter 2 niveau  la fin pour Lowe? un niveau je comprend, mais deux??


Ca s'explique un peu plus loin dans le document de Lowe. Dans SIFT, on va calculer des DoG (difference of gaussians) et pour cela on a besoin de 2 niveaux conscutifs de la pyramide pour faire un niveau de Dog.

Donc pour avoir 3 niveaux de DoG, il nous faut 4 niveaux de pyramide:



```

```

On va galement avoir besoin de comparer une DoG a la DoG prcdente et la Dog suivante. Donc, dans mon exemple, on a besoin de la DoG(1,0) et la DoG (1,4). Donc on a besoin de 2 niveaux de pyramide supplmentaires. Soit au total 3 niveaux de pyramide de plus que le nombre de DoG.



```

```

----------


## mel84

Ok!
En fait on en a besoin pour calculer les extrema!

Merci beaucoup

----------


## mel84

Encore moi,
C'est bon j'ai tout compris pour la diffrence de gaussienne (encore merci!) mais maintenant je bloque sur la recherche d'extrema!!
Pour rechercher les extrma, on prend un pixel de l'image et on le compare avec les 26 points autour de lui ( jusque l, a va!)
Mais pour chaque scale, on va avoir plein de points extrema, je ne comprend pas comment on fait pour, avec tous les scales, slectionner les rl points d'intrt!!

Merci

----------


## pseudocode

> Mais pour chaque scale, on va avoir plein de points extrema, je ne comprend pas comment on fait pour, avec tous les scales, slectionner les rl points d'intrt!!


D'aprs le document de Lowe (figure 3), on obtient entre 2000 et 3000 extrema. Pour ne garder que les points d'intrts, il faut continuer la mthode (chapitre 4 : Accurate keypoint localization + Eliminating edge responses).

----------


## mel84

Merci pour ton aide!!
Je suis arrive  ce chapitre 4 et l, de nouveau, je bloque (quelle nulle!!!)
Comment on fait pour calculer la drive selon x et celle par rapport  x^2??

----------


## pseudocode

> Merci pour ton aide!!
> Je suis arrive  ce chapitre 4 et l, de nouveau, je bloque (quelle nulle!!!)
> Comment on fait pour calculer la drive selon x et celle par rapport  x^2??


D(X) est une fonction  3 paramtres, car X=(x,y,s).

(NB : merci a Lowe d'avoir mis d, D, x et X dans la mme quation  ::aie:: )

La drive premire de D(X) est le vecteur:


```

```

La drive seconde de D(X) est la matrice hessienne:


```

```

Reste  calculer les valeurs grace aux formules de diffrenciation discrtes:

df(x)/dx = ( f(x+1) - f(x-1) )/2
df(x)/dx = ( f(x+1) - 2*f(x) + f(x-1) )/4
df(x,y)/dxdy = d( df(x,y)/dx )/dy

et voila.  ::D:

----------


## mel84

Bah oui, en fait c'est pas trop compliqu, je te remercie!!

----------


## mel84

Bonjour, (encore moi!!)

Quelqu'un peut-il m'expliquer l'algorithme de kdtree et me dire  quoi il sert dans shift?

Merci

----------


## Morpheus42000

Bonjour  tous !
Je viens de tomber sur le topic et, comme Ml, je bloque sur un point qui fait capoter toute la partie "description" de mon code ^^.
Lowe calcule le descripteur sur une zone qui dpend de l'chelle du point. Ma question est : Comment dtermine-t-il le rayon de cette zone ?
Je sais que cette zone est ensuite normalise (diamtre de 41 pixels) autour du keypoint, afin d'avoir une invariance en chelle...

--------
L'implmentation de l'algo SIFT sous matlab tait le sujet de mon stage l'an dernier. Vu que j'ai un peu de temps pendant les grandes vacances, je rouvre mes vieux fichiers tout poussireux et essaye de "finir" le travail ^^

Merci d'avance ...

----------


## Morpheus42000

Dsl pour ce post inutile ^^
Pour ceux qui comme moi n'auraient pas pris la peine de "scanner" toutes les discussion, la rponse se trouve sur cette discussion :

http://www.developpez.net/forums/d70...ints-dinteret/

Je pense qu'il faut utiliser la meme region que pour le detecteur de Harris...

----------


## NaguiM0

salut

je suis entrain de comprendre l'algorithme SIFT, mais comme un dbitant 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????

----------


## pseudocode

> salut
> 
> je suis entrain de comprendre l'algorithme SIFT, mais comme un dbitant 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 mme image de dpart. 

Quand on change d'octave, on calcule une nouvelle image de dpart en reduisant par 2 les dimensions de l'image de l'octave prcdant.



Dans cet exemple, on a 4 octaves (constitus 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 mme image de dpart. 
> 
> Quand on change d'octave, on calcule une nouvelle image de dpart en reduisant par 2 les dimensions de l'image de l'octave prcdant.
> 
> 
> 
> Dans cet exemple, on a 4 octaves (constitus 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'espre 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 dpart en reduisant par 2 les dimensions de l'image de l'octave prcdant.


en fait , quelle est l'image qui sera utiliser pour le deuxime octave et reduire en taille, est ce que l'image originale ou l'image lisse par 2sigma????  ::?: 

et d'aprs 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 dintrt, j'ai pas bien compris cette phase, (interpolation de Taylor et l'annulation  de la drive 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'intrt.

si x et y sont les coordonnes d'un extremum, comment x et y sont rel???

merci pour vos rponses

----------


## pseudocode

> Quand on change d'octave, on calcule une nouvelle image de dpart en reduisant par 2 les dimensions de l'image de l'octave prcdant.
>  en fait , quelle est l'image qui sera utiliser pour le deuxime octave et reduire en taille, est ce que l'image originale ou l'image lisse par 2sigma????


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

L'idal 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 dj fait si on prend directement les valeurs dans l'image 2*sigma !! 

Donc la rponse est : il faut "resampler" l'image de dpart, ce qui est peut tre fait en prenant un point sur deux dans l'image 2*sigma.




> dans la partie: Localisation des points d’intrt, j'ai pas bien compris cette phase, (interpolation de Taylor et l'annulation  de la drive 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 coordonnes entieres) dans une image rduite, la position de cette extremum dans l'image de dpart n'est pas tres prcise.

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

L'ide c'est donc de calculer les coordonnes de l'extremum local avec des coordonnes relles, afin d'avoir une meilleure prcision 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'intrt. si x et y sont les coordonnes d'un extremum, comment x et y sont rel???


Comme dit juste avant, les coordonnes de l'extremum local sont relles.

----------


## 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 utilise 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)??


 ::koi::  ? Je ne comprend pas bien la question. 

En premier lieu, on cherche les points (x,y,s) (en coordonnes entires) qui sont des extrema locaux, c'est  dire plus grands que leurs 26 voisins.

Ensuite on raffine ces extrema locaux en calculant leurs coordonnes relles.




> 2. c'est quoi la fonction d'analyse D utilise dans la fonction de taylor??


Heu, c'est la valeur la Dog pour n'importe quelle coordonnes relles (x,y,s).

----------


## NaguiM0

> ? Je ne comprend pas bien la question. 
> 
> En premier lieu, on cherche les points (x,y,s) (en coordonnes entires) qui sont des extrema locaux, c'est  dire plus grands que leurs 26 voisins.
> 
> Ensuite on raffine ces extrema locaux en calculant leurs coordonnes relles.
> 
> 
> 
> Heu, c'est la valeur la Dog pour n'importe quelle coordonnes relles (x,y,s).


Merci pseudocode, c mieux et plus claire maintenant.

----------


## NaguiM0

je suis entrain de dterminer l'algorithme de SIFT, je trouve des difficults au niveau de la localisation des points d'intrts. pour cela j'ai prpar un petit exemple pour le mieux comprendre lorsque vous me rpondez  quelques questions.

si je pose l'image originale est la suivante:


aprs la transformation pyramidale et le DoG sont prsentes comme suit:


Les extremas : ces sont les pixels avec le couleur rouge

Pour la localisation des points dintrts, on va commencer par Re-dplacement : c  d on utilise linterpolation de Taylor pour passer dune coordonne entire  une coordonne relle.




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 linterpolation de Taylor selon mon exemple.

Merci pour vos rponses.

----------


## pseudocode

Je n'ai pas vraiment envie de calculer a la main les diffrentiation 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 (derives secondes) et G le gradient (drives premires). C'est  dire, en explicitant les termes :



```

```

On calcule les coefficients de H et G en utilisant les formules de diffrentiation discrtes (cf post prcdents). Par exemple :

dD(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 systme 3x3. Par exemple par la mthode d'elimination de Gauss, ou l'inversion de la matrice H, ou autre...

----------


## NaguiM0

Salut pseudocode, merci pour vos rponses  ::ccool:: ,

 cest plus claire la partie localisation des points dintrt, mais juste une petite question : que reprsente D ?? est ce quon peut considrer D comme un tableau de 3 colonnes (x, y, σ) et n lignes (n : nombre de points dintrts) ?? 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, σ ) reprsente quoi ?? les voisins dun pixel de point dintrt dans DoG, ou les points dintrts suivant et prcdent ??


Je me suis bloqu aussi dans la partie suivante pour la cration dun descripteur, en faite:

-	Pour calculer (rho, theta ), je dois connatre L(x,y). est ce que L(x,y) reprsente la convolution de limage originale par filtre de gauss c a d la premire tape avant de passer  la diffrence gaussien ??
-	Est comment je peux cre un histogramme d'orientation en fonction de rho, theta, (laxe des ordonns reprsente quoi ??)

Remerci encore pour les rponses

----------


## pseudocode

I : c'est l'image de dpart --> c'est un tableau 2D
I(x,y) : c'est le point de coordonne (x,y) dans l'image I

L(σ) : c'est l'image  l'echelle σ = floute avec une gaussienne de variance σ --> c'est un tableau 2D
L(x,y,σ) : c'est le point de coordonne (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 coordonne (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, σ ) reprsente quoi ?? les voisins d’un pixel de point d’intrt dans DoG, ou les points d’intrts suivant et prcdent ??


D(x+1,y,σ) : c'est le point de coordonne (x+1,y) dans la Dog d'echelle σ
D(x-1,y,σ) : c'est le point de coordonne (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 cration d’un descripteur, en faite:
> -	Pour calculer (rho, theta ), je dois connatre L(x,y). est ce que L(x,y) reprsente la convolution de l’image originale par filtre de gauss c a d la premire tape avant de passer  la diffrence gaussien ??


oui.




> -	Est comment je peux cre un histogramme d'orientation en fonction de rho, theta, (l’axe des ordonns reprsente quoi ??)


L'axe des ordonns reprsente l'angle thta. 

C'est  dire qu'on va crer un tableau 1D (l'histogramme) qui a pour index la valeur de thta. On limite thta 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 dterminer  Theta et lamplitude du gradient, il faut travailler avec un voisinage 16x16 centr sur le point-cl. 
 Comment je peux dterminer un voisinage 16*16 ? c a d je peux dterminer un voisinage 3*3 mais 16*16??  :8O: 

2)	Un histogramme des orientations du gradient est alors calcul  partir des pixels de la rgion autour du  keypoint , chaque contribution tant pondre par la magnitude de son gradient et par une gaussienne avec σ gale  1.5 fois lchelle du point cl.
En faite, je nai pas compris ce paragraphe ? 

3)	Aprs la dtermination de langle Thetamax, comment on va travailler sur un voisinage 16x16 tourn d'un angle Thetamax ?

----------


## pseudocode

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


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

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



```

```




> 2)	Un histogramme des orientations du gradient est alors calcul  partir des pixels de la rgion autour du  keypoint , chaque contribution tant pondre 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 dpend 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)	Aprs la dtermination de l’angle Thetamax, comment on va travailler sur un voisinage 16x16 tourn d'un angle Thetamax ?


Dans la thorie, il faut faire une rotation des coordonnes des pixels du voisinage. Personnellement, je garde le meme voisinage (non tourn) et je dcale juste la valeur "theta" du gradient des pixels.

Ainsi, dans une rgion d'orientation THETAREGION, un pixel du voisinage aura une orientation "corrige" de : theta-THETAREGION

----------


## OujAA

Bonjour,

J'ai quelques questions concernant les descripteurs sift.

Un voisinage doit tre dfinit une premire fois autour du point d'intrt sur l'image de notre pyramide gaussienne la plus proche de l'extrema dtect 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 dfinir un voisinage de taille totalement relative au point ?

Puis, si on se place  la gaussienne correspondante avec un voisinage pondr 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 pondration puisque l'on est dj plac  la gaussienne correspondante. Ou bien faut-il utiliser σ = 1.5 puisque l'on est dj plac sur la bonne gaussienne ?

Enfin, concernant le descripteur lui-mme, j'ai le mme problme avec la pondration du voisinage 16*16.

Pourriez-vous m'aider s'il vous plat ?

----------


## pseudocode

> Mais ne serait-il pas judicieux de prendre en compte l'interpolation de la taille de l'extrema afin de dfinir 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 pondr 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 pondration puisque l'on est dj plac  la gaussienne correspondante. Ou bien faut-il utiliser σ = 1.5 puisque l'on est dj plac sur la bonne gaussienne ?


Il n'y a pas de rapport avec l'chelle du keypoint. Cette pondration est utilise 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-mme, j'ai le mme problme avec la pondration du voisinage 16*16.


Idem. Cette pondration sert  lisser les valeurs (attnuer progressivement les valeurs des pixels qui sont loin du centre)

----------


## OujAA

Merci de ta rponse.

1)



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


On trouve le point d'intrt (x, y, σ) en le comparant aux 26 points dans la pyramide, puis on utilise Taylor afin de trouver plus prcisment la position du keypoint dans le scale space. On trouve alors des x+Δx, y+Δy, σ+Δσ rels et assez prcis.

Je pensais utiliser ce σ+Δσ afin de non seulement me placer  l'image floute la plus proche du point, mais aussi afin de dfinir un voisinage en fonction de ce Δσ. Par exemple, un Δσ lev serait reprsent par un voisinage dfini plus grand sur l'image floute.

2)



> Il n'y a pas de rapport avec l'chelle du keypoint. Cette pondration est utilise 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 pondr 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 pondration de exp(-8/24)=0,895 sur les bords du voisinage, ce qui ne ressemble pas  une vrai pondration.
Encore une fois, je fais appel  votre savoir.


4)
Sinon, si j'ai compris le processus, globalement il faut :
 Se placer  l'chelle adapte.
 Calculer le gradient sur un voisinage assez grand.
 Trouver l'orientation maximale en remplissant 36 bins avec l'amplitude du gradient pondr par la gaussienne.
 Dfinir un voisinage de 16*16 comportant 4*4 sous-rgions tournes en fonction de l'orientation trouve.
 Remplir les 8 bins (en tenant compte du changement d'orientation) de chaque sous-rgion en pondrant avec un gaussienne et le facteur 1-d o d est la distance au centre de la sous-rgion.

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 floute la plus proche du point, mais aussi afin de dfinir un voisinage en fonction de ce Δσ. Par exemple, un Δσ lev serait reprsent par un voisinage dfini plus grand sur l'image floute.


Ah. Oui ca serait une possibilit, pour avoir des valeurs plus prcises. Mais je en sais pas si le rsultat sera notable, car l'algo de Lowe fait beaucoup de simplifications, approximations, etc. Je ne sais pas si ton amlioration 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 adapte.
>  Calculer le gradient sur un voisinage assez grand.
>  Trouver l'orientation maximale en remplissant 36 bins avec l'amplitude du gradient pondr par la gaussienne.
>  Dfinir un voisinage de 16*16 comportant 4*4 sous-rgions tournes en fonction de l'orientation trouve.
>  Remplir les 8 bins (en tenant compte du changement d'orientation) de chaque sous-rgion en pondrant avec un gaussienne et le facteur 1-d o d est la distance au centre de la sous-rgion.


Oui, c'est ca.

----------


## OujAA

Merci beaucoup !  ::ccool::

----------


## fzied

pseudocode :

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

Cette augmentation dpend 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 trs bnfique.
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 mme 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 trs bnfique.
> 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 mme 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'intrt de 256 pixels (16x16) est divise en 16 carrs (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 carrs voisins. La valeur distribut dpend 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 trilinaire. C'est  dire que le coefficient d'attnuation varie linairement pour chaque composante : i, j et theta

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

- Pour i et j, c'est une interpolation bilinaire entre les centres des carrs les plus proches

----------


## pseudocode

Je viens de trouver ce lien l qui explique bien les dtails d'implmentation :

http://www.vlfeat.org/api/sift.htmll

 ::D:

----------


## fzied

> Je viens de trouver ce lien l qui explique bien les dtails d'implmentation :
> 
> http://www.vlfeat.org/api/sift_8h.html


Bonjour,
ah merci bcp  ::mouarf::

----------


## fzied

Bonjour,

c'est encore moi ::oops:: 
ok j'ai compris la construction de l'histogramme juste un point flou, o intervient cette phrase dans qu'elle etape 
"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."
j'ai cru au debut que c'etait en relation avec la construction de l'histogramme du descripteur pour ponderer la magnitude. d'o la gaussienne hors c'est pas le cas d'aprs votre reponse.

Merci

----------


## fzied

> Bonjour,
> 
> c'est encore moi
> ok j'ai compris la construction de l'histogramme juste un point flou, o intervient cette phrase dans qu'elle etape 
> "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."
> j'ai cru au debut que c'etait en relation avec la construction de l'histogramme du descripteur pour ponderer la magnitude. d'o la gaussienne hors c'est pas le cas d'aprs votre reponse.
> 
> Merci


j'ai encore relu le doc de Low.
je ne sais pas si c'est juste ou pas.
pour la construction du descripteur tout d'abord nous avons :
1- la valeur du gradient en chaque point du voisinage du keypoint (la sous rgion 4*4) c a d magnitude et orientation (dja calcul  l'etape orientation assignement m et theta).
2- on assigne une pondration  la magnitude soit m1 cette nouvelle valeur donc 
m1=gaussi(m,8) avec 8=sigma
3-hist(theta)=hist(theta)+(1-d)*m1

est ce que les etapes sont correctes ? ::roll:: 

Merci

----------


## pseudocode

> j'ai encore relu le doc de Low.
> je ne sais pas si c'est juste ou pas.
> pour la construction du descripteur tout d'abord nous avons :
> 1- la valeur du gradient en chaque point du voisinage du keypoint (la sous rgion 4*4) c a d magnitude et orientation (dja calcul  l'etape orientation assignement m et theta).
> 2- on assigne une pondration  la magnitude soit m1 cette nouvelle valeur donc 
> m1=gaussi(m,8) avec 8=sigma
> 3-hist(theta)=hist(theta)+(1-d)*m1
> 
> est ce que les etapes sont correctes ?
> ...


Hum... je formulerais plutot ca comme cela

1. le pixel de coordonnes (i,j)  pour valeur de gradient (theta, norm)

avec [-8,-8] <= i,j <= [+8,+8]
et theta orient par rapport a la direction principale la zone

2. On assigne une valeur pondre de la magnitude du gradient aux histogrammes des carrs voisins. Cette valeur vaut

v =  norm * W_win(i,j) * W_carre(i,j)

W_win(i,j) = gauss2D(i,j,8), la ponderation d'attnuation globale  la zone

W_carr(i,j) = max(0,1-dx) * max(0,1-dy) avec dx,dy = distance normalise au centre du carr considr. C'est  dire dx=abs(i-ci)/8 et dy=abs(j-cj)/8, avec ci,cj le centre du carr.

3. Comme les histogrammes n'ont que 8 bins, on repartit la valeur de 'v' entre les 2 bins les plus proches : t0 <= theta <= t1

hist[t0] +=  v  * (t1-theta)/(t1-t0)  

hist[t1] +=  v  * (theta-t0)/(t1-t0)

----------


## stick25

Bonjour  tous,

je suis pleinement dbutant en matire de programmation, j'avoue alors que je comprend vraiment pas grand chose  cette discussion !

Je compte utiliser SIFT sous Matlab. SIFT permet de trouver des points communs entre deux photos, mais est-il possible d'adapter le code pour trouver les points communs entre trois photos ? Si oui je pense que cela est loin d'tre vident, donc est-ce que quelqu'un s'est dj pencher sur cette problmatique ?

Merci d'avance.

----------


## Koelo

Je dirais qu'il suffirait d'appliquer l'algo sur chacun des 3 duplets d'image (1 2), (1 3), (2 3)...
Ensuite comparer les points trouvs lors du traitement (1 2) et (1 3) avec ceux trouvs lors du traitement (2 3)...?
Vu le nombre de points et surtout les 3 traitements, a risque d'tre assez lourd, il existe certainement de meilleures solutions...  :;):

----------


## fzied

Bonjour,

je dsire coder SIFT en C. 
en faite j'aimerai savoir combien est la taille du masque gaussien.
je prcise :
par exemple si on considre le cas d'une gaussienne d'chelle 2sigma il faut considrer un masque gaussien de taille 4sigma*4sigma que nous allons convoluer aprs avec l'image source.

Merci

----------


## rzouguinho

Bonsoir  tout le monde.

Est-ce quelqu'un peut m'expliquer comment peut-on effectuer une interpolation sur sigma?

En effet, pour la discrtisation de la drive, on utilise la formule suivante:
dD(x)/dx = ( D(x+1) -D(x-1) )/2 .

Est-ce qu'on considre les DOG de scale sigma-1 et sigma+1, ou bien les DOG prcdente et suivante utilises pour le calcul des minimas et des maximas?

Merci de me rpondre.

----------


## pseudocode

> Est-ce quelqu'un peut m'expliquer comment peut-on effectuer une interpolation sur sigma?


Pourquoi faire ? Tu cherches a calculer des images intermdiaires dans la pyramide ? 




> Est-ce qu'on considre les DOG de scale sigma-1 et sigma+1, ou bien les DOG prcdente et suivante utilises pour le calcul des minimas et des maximas?


 ::koi::  ? Que veux tu dires par "considrer" ?

----------


## rzouguinho

Ma question porte sur la phase d'interpolation des keypoints pour trouver les coordonnes rels en x, y et sigma de l'extrmum.

Mon problme rside dans le calcul de la drive de D par rapport  sigma.

Est ce que c'est gal  (D(sigma+1)-D(sigma-1))/2 
ou bien (D(sigma2)-D(sigma1))/2
avec sigma1 est le scale de la DOG prcdente et sigma2 est le scale de la DOG suivante  la DOG d'tude.

----------


## pseudocode

> Mon problme rside dans le calcul de la drive de D par rapport  sigma.
> 
> Est ce que c'est gal  (D(sigma+1)-D(sigma-1))/2 
> ou bien (D(sigma2)-D(sigma1))/2
> avec sigma1 est le scale de la DOG prcdente et sigma2 est le scale de la DOG suivante  la DOG d'tude.


C'est le second cas : (D(sigma2)-D(sigma1))/2

Cf le post #49  :;):

----------


## rzouguinho

Merci beaucoup de m'avoir rpondu.

Cependant je demande, s'il vous plait, quelques clarifications sur certains points:

1- lorsqu'on cherche des minimas est des maximas pour une image DOG (en la comparant avec l'image DOG prcdente et suivante), ils peuvent ne pas tre ni minima ni maxima pour une autre image DOG?

2- pour le calcul de la magnitude et l'orientation du gradient au niveau du keypoint, est-ce que le sigma du L(sigma) utilis est gal au sigma de l'image DOG de laquelle nous avons extrait le keypoint, ou bien gal  sigma+delta_sigma qui correspond au scale rel du keypoint. Si c'est la 2me rponse, doit-on donc construire un L(sigma+delta_sigma) pour chaque keypoint?

3- est-ce que le thta_max trouv est gale  une valeur ou un intervalle de 10?

Merci d'avance.

----------


## pseudocode

> 1- lorsqu'on cherche des minimas est des maximas pour une image DOG (en la comparant avec l'image DOG prcdente et suivante), ils peuvent ne pas tre ni minima ni maxima pour une autre image DOG?


Si. C'est le cas pour les formes qui sont invariantes  l'echelle. Par exemple le coin d'un carr. On a alors des points d'intrets au meme endroit mais avec des echelles diffrentes.




> 2- pour le calcul de la magnitude et l'orientation du gradient au niveau du keypoint, est-ce que le sigma du L(sigma) utilis est gal au sigma de l'image DOG de laquelle nous avons extrait le keypoint, ou bien gal  sigma+delta_sigma qui correspond au scale rel du keypoint. Si c'est la 2me rponse, doit-on donc construire un L(sigma+delta_sigma) pour chaque keypoint?


D'aprs le papier de Lowe, on utilise L(sigma). 

La valeur "sigma+delta_sigma" n'est utilise que pour dcrire le keypoint, par exemple dans la phase de matching.




> 3- est-ce que le thta_max trouv est gale  une valeur ou un intervalle de 10?


Si tu parles de l'orientation du keypoint, c'est une valeur. Elle est calcule en cherchant le sommet de la parabole passant par les 3 bins voisins dans l'histogramme.

----------


## rzouguinho

Bonsoir  tout le monde.

J'ai 3 questions  propos du SIFT:

1- est-ce qu'il faut dupliquer la taille de l'image initiale avant de lui appliquer la convolution avec la gaussienne (pour la premire octave)?

2- aprs la recherche des minimas et maximas dans une image DOG de la deuxime octave, est-ce qu'il faut dupliquer la taille de cette image pour interpoler la position du keypoint?

3- pour le problme de bord dans les images, affront lors du balayage du voisinage d'un pixel, est-ce qu'on ajoute des lignes et des colonnes  l'image par effet miroir?

Merci de me rpondre.

----------


## pseudocode

> 1- est-ce qu'il faut dupliquer la taille de l'image initiale avant de lui appliquer la convolution avec la gaussienne (pour la premire octave)?


C'est prconis par Lowe si je me souviens bien. Mais ce n'est pas obligatoire. Ca permet juste de trouver des keypoints a des echelles plus petites que la taille originale de l'image, ce qui pourra etre utile dans la phase de matching.




> 2- aprs la recherche des minimas et maximas dans une image DOG de la deuxime octave, est-ce qu'il faut dupliquer la taille de cette image pour interpoler la position du keypoint?


heu... non. L'interpolation se fait avec les images de l'octave, quelles que soient leurs "tailles".




> 3- pour le problme de bord dans les images, affront lors du balayage du voisinage d'un pixel, est-ce qu'on ajoute des lignes et des colonnes  l'image par effet miroir?


C'est plus simple de ne pas se proccuper des pixels sur les bords. De toutes facons, ca sera difficile de savoir si un point sur un bord est un extrema, sans connaitre les pixels voisins.

----------


## tayeb1

Bonjour tous le monde, 

  Je voudrais savoir quels sont les types d 'algorithmes de dtection de point d 'intrt qui sont aussi performant que l' algorythmes SIFT, y 'en a t-il qui sont plus prcis ou qui utilise une diffrentes mthode 

  Je vous remercie d 'avance.

----------


## pseudocode

> Bonjour tous le monde, 
> 
>   Je voudrais savoir quels sont les types d 'algorithmes de dtection de point d 'intrt qui sont aussi performant que l' algorythmes SIFT, y 'en a t-il qui sont plus prcis ou qui utilise une diffrentes mthode 
> 
>   Je vous remercie d 'avance.


L'algo SURF est une version approxime de SIFT qui est plus rapide, et (parait-il) plus robuste.

Sinon il y a l'algo FAST que j'aime bien, mais qui ne gre pas vraiment le multi-echelle.

----------


## tayeb1

> L'algo SURF est une version approxime de SIFT qui est plus rapide, et (parait-il) plus robuste.
> 
> Sinon il y a l'algo FAST que j'aime bien, mais qui ne gre pas vraiment le multi-echelle.


merci speudocode. En fait je dois faire un rapport sur les diffrentes mthode et justement je ne connaissais pas le FAST. Je vais regarder ca en profondeur et si j 'ai des questions je reviendrai les poss , merci encore.

----------


## tayeb1

bonjour, je veux seulement dtecteur les point d 'intrt d 'une image, je pense que je n 'ai donc pas besoin de calculer le gradient ?? je souhaite avoir une confirmation, svp.

Edit : j 'ai oubli de prciser que c'est avec l 'algorithm de SIFT.

----------


## pseudocode

> bonjour, je veux seulement dtecteur les point d 'intrt d 'une image, je pense que je n 'ai donc pas besoin de calculer le gradient ?? je souhaite avoir une confirmation, svp.
> 
> Edit : j 'ai oubli de prciser que c'est avec l 'algorithm de SIFT.


Effectivement, le calcul du laplacien est suffisant.

(enfin dans SIFT c'est remplac par la diffrence de Gaussiennes).

----------


## T_Lara

De ma part j'ai trouv deux implmentation de l'algo SIFT de Lowe et dans les deux cas pour construire la pyramide gaussienne ( sans prendre le cas special Py[0] et aprs interprtation du code)

Py[i] = gaussien ( P[i-1] , sqrt ( ( sigma0 K^i )^2  -   ( sigma0 K^i-1 )^2  ) avec sigma0= 1,6 K  et K= 2^(1/s)

ce qui donne apres quelques simplification:
Py[i] = gaussien ( P[i-1] ,  1,6 *K^(i) * Sqrt(1 -1/K^2) ) ( pour i>=1  pour i=0 c'est tjrs diff.)

En relisant le papier de Lowe au long et travers j'ai pas trouv d'ou viens ce Sqrt  !!

qui peut m'expliquer ?? 
( gaussien est dans la premiere implementation avec matlab c'est "imsmooth" qui est utilise et avec le C : "cvSmooth" )

De meme je trouve pas d'ou viens nombre d'ovctave = log2( MIN(hauteur_image_initial, largeur_image_initial ) - 2;

----------


## pseudocode

> De ma part j'ai trouv deux implmentation de l'algo SIFT de Lowe et dans les deux cas pour construire la pyramide gaussienne ( sans prendre le cas special Py[0] et aprs interprtation du code)
> 
> Py[i] = gaussien ( P[i-1] , sqrt ( ( sigma0 K^i )^2  -   ( sigma0 K^i-1 )^2  ) avec sigma0= 1,6 K  et K= 2^(1/s)
> 
> ce qui donne apres quelques simplification:
> Py[i] = gaussien ( P[i-1] , sqrt ( 1,6 *K^(i) * Sqrt(1 -1/K^2) ) ( pour i>=1  pour i=0 c'est tjrs diff.)
> 
> En relisant le papier de Lowe au long et travers j'ai pas trouv d'ou viens ce Sqrt  !!


J'ai dj abord ce point dans d'autres discussions. Dans son papier, Lowe raisonne avec les valeurs de "sigma", alors que la thorie des scale-space utilise des valeurs qui sont en fait des "sigma". 

scale-space :   G(t1)*G(t2) = G(t1+t2)Lowe: Gaussian(σ1)*Gaussian(σ2) = Gaussian(σ3) avec σ1+σ2=σ3

Moralit, quand on veut monter d'un cran dans la pyramide, on cherche "w" tel que :

Gaussian( σ0 . K^i-1 ) * Gaussian( w ) =  Gaussian( σ0 . K^i ) 

alors on a 

(σ0 . K^i-1) + w = (σ0 . K^i)

et donc

w = racine( (σ0 . K^i) - (σ0 . K^i-1) )

----------


## T_Lara

Conclusion ??:

Lowe s'est tromp dans son papier ? ou bien ca influence pas trop ? 
Ie si je suis amener a implemente l'algo de Lowe je peux garder 1,6 K^i ??

----------


## pseudocode

> Conclusion ??:
> 
> Lowe s'est tromp dans son papier ? ou bien ca influence pas trop ? 
> Ie si je suis amener a implemente l'algo de Lowe je peux garder 1,6 K^i ??


Non, Lowe ne s'est pas tromp. J'expliquais juste qu'il utilise une notation diffrente de celle des scale-space, et c'est pour cela qu'on arrive a une formule du genre racine( (σ0 . K^i) - (σ0 . K^i-1) ).

Par contre, il y a effectivement une erreur dans la "simplification" (il y a une racine en trop)

w=racine( (σ0 . K^i) - (σ0 . K^i-1) )
 =racine( (σ0 . K^i) - (σ0 . K^i/K) )
 =racine( (σ0 . K^i) . (1-1/K) )
 =(σ0 . K^i).racine(1-1/K)

----------


## T_Lara

oui oui faute de frappe de ma part je l'avais rectifier avant meme que vous poster  :;):  

Merci alors faut peut tre que je revois cette theorie de space scale plus en details si je veux mieux comprendre mais pour l'implementation je vois..sinon pour le nombre d'octave vous avez une idee??

----------


## pseudocode

> oui oui faute de frappe de ma part je l'avais rectifier avant meme que vous poster  
> 
> Merci alors faut peut tre que je revois cette theorie de space scale plus en details si je veux mieux comprendre mais pour l'implementation je vois..sinon pour le nombre d'octave vous avez une idee??


Le nombre d'octave, c'est le nombre de fois o l'on peut rduire l'image par 2

500x500 --> 250x250 --> 125x125 --> 62x62 --> 31x31 --> 15x15 --> 7x7 --> 3x3 --> 1x1

ici, 8 rductions successives, donc 8 octaves.

C'est donc li au Log_2, c'est  dire le nombre de puissance de 2 dans les dimensions de dpart. En effet, on a  2^8=256 < 500 < 512=2^9.

Le "-2" au bout de la formule c'est pour s'arrter avant d'atteindre des dimensions trop ridicules du genre 1x1.  ::aie::

----------


## T_Lara

mais c'est pas trop aller jusqu la fin ?? est ce que le nombre d'octave influence sur la methode? ou bien suis libre de choisir le nombre d'octave ??

----------


## pseudocode

> mais c'est pas trop aller jusqu la fin ??


Le descripteur dans SIFT a besoin d'un voisinage 16x16, donc il ne faut pas que l'image soit plus petite que cela.




> est ce que le nombre d'octave influence sur la methode? ou bien suis libre de choisir le nombre d'octave ??


Non, ca n'influence pas le calcul, mais ca influence le nombre de descripteur que l'on peut trouver. Il faut avoir suffisamment d'images  diffrentes chelles pour trouver des descripteurs intressants.

----------


## T_Lara

pourquoi le seuillage par rapport a 0.5*thr_contr/ S avant la detection des extremum ( je trouve pas dans le papier de low ce qui indique ca et surtout que thr_contr= 0.04 )

et pourquoi ils ont fait un seuillage apres interpolation par rapport a th_contr/S au lieu de 0.03 de low ( d'ou vient ce /S tjrs )

----------


## pseudocode

> pourquoi le seuillage par rapport a 0.5*thr_contr/ S avant la detection des extremum ( je trouve pas dans le papier de low ce qui indique ca et surtout que thr_contr= 0.04 )
> 
> et pourquoi ils ont fait un seuillage apres interpolation par rapport a th_contr/S au lieu de 0.03 de low ( d'ou vient ce /S tjrs )


Je ne sais pas, il faut demander aux "ils".  ::D:

----------


## T_Lara

lool oki cela veut dire que dans Low y a pas a c'est ce qui m'importe 

Dans leur implmentation lors du calcul de l'orientation du point dintrt et aprs la creation de l'histogramme ils procdent a une phase de lissage ( qui se fait 2 fois ) et qui se fait comme suit :

h[i]= 0.25 h[i-1] + 0.5 h[i] + 0.25 h[i+1] ( en manipulant h d'une maniere circulaire)

Je trouve pas une indication dans le papier de Low qui parle de a.. 
Est ce que cette phase parrait quelques part dans le papier de Low car ca m'arrive a echapper des ptit details dans le papier

----------


## pseudocode

> Est ce que cette phase parrait quelques part dans le papier de Low car ca m'arrive a echapper des ptit details dans le papier


Heu, non. Ca n'apparait pas dans l'implmentation de Lowe

----------


## T_Lara

Bonjour Pseudocode je vais vous embeter encore une fois la je plante je vois pas dans ce code d'ou vient ces calcule la pour la creation du discripteur

Voici le code


```

```


Je suppose que ca

hist_width = 3* scl;
radius = hist_width * sqrt(2) * ( d + 1.0 ) * 0.5 + 0.5;

est relatif a la taille des 4*4 carree dans le cas de Low on va prendre directement radius= 7 ( je sai pas si on peut se permettre ca vu que c et r c'est des entiers)

mais j'arrive pas a voir ces c_rot ,r_rot ,rbin  et cbin 

d'apres vos posts j avais compris qu une simplification par rapport a Low va etre la suivante:


```

```

Ce code est il juste 

d'un autre part cette faon de faire avec la distribution sur les deux Bins les plus proche est elle utilise mme lors de la cration du premier histogramme pour la dtection de l'orientation

car dans le mme code que jtudie il utilise plutt Hist [36*(Ori+pi)/2pi]=w*Mag 

( par contre comme je l'avais mentionn il procde a un certain lissage de l'histogramme aprs sa construction )

----------


## pseudocode

> Je suppose que ca
> 
> hist_width = 3* scl;
> radius = hist_width * sqrt(2) * ( d + 1.0 ) * 0.5 + 0.5;
> 
> est relatif a la taille des 4*4 carree dans le cas de Low on va prendre directement radius= 7 ( je sai pas si on peut se permettre ca vu que c et r c'est des entiers)


oui, je le suppose aussi. Je ne vois pas trop ce que vient faire le "3*scl" dans l'histoire, mais passons.




> mais j'arrive pas a voir ces c_rot ,r_rot ,rbin  et cbin


a mon avis : c= column, r=row

c_rot = colonne aprs rotation (pour aligner avec l'orientation)
r_rot = ligne aprs rotation

rbin  et cbin, ca a l'air d'tre les coordonnes du pixels, en bidouillant c_rot et r_rot pour tomber "au milieu" des cases.




> d'apres vos posts j avais compris qu une simplification par rapport a Low va etre la suivante


Hum... je ne me souvient pas avoir dit qu'on pouvait simplifier quoi que ce soit.  ::?: 




> w = exp( -(i * i + j* j) / exp_denom );  // la est le pb est ce qu'il faut garder i et j ?


i+j ca reprsente la distance (au carr) du pixel au centre du patch. Ce n'est donc pas sensible a l'orientation. Tu peux donc garder i et j.




> Ce code est il juste


J'en sais rien.  ::aie::  

Je ne vois pas trop o est pass la rotation pour aligner le patch avec l'orientation dominante.




> d'un autre part cette faon de faire avec la distribution sur les deux Bins les plus proche est elle utilise mme lors de la cration du premier histogramme pour la dtection de l'orientation


*EDIT:* Oui, il faut distribuer la valeur de l'orientation sur les 2 bins les plus proches dans l'histogramme 36 bins.

(je n'avais pas compris la question.)

----------


## T_Lara

> c_rot = colonne aprs rotation (pour aligner avec l'orientation)
> r_rot = ligne aprs rotation
> 
> rbin et cbin, ca a l'air d'tre les coordonnes du pixels, en bidouillant c_rot et r_rot pour tomber "au milieu" des cases.


La suis daccord mais c'est la formule que je vois pas comment elle est faite avec un / width_hist




> Hum... je ne me souvient pas avoir dit qu'on pouvait simplifier quoi que ce soit.


Non non j'ai pas parler non plus de simplifier Lowe c'est simplifier le code que j'ai pour coincider avec Lowe




> Je ne vois pas trop o est pass la rotation pour aligner le patch avec l'orientation dominante.


 
Cela ve dire qu'il faut prendre la fenetre de 16*16 par rapport a l'axe lier a l'orientation ?? ( chose que j'ai pas pris en compte)
et l'orientation des pixel autour du point d'interet va etre ori_pixelt - ori_pointd'interet

Est ce que ca rentre ailleur aussi ??

----------


## pseudocode

> La suis daccord mais c'est la formule que je vois pas comment elle est faite avec un / width_hist


L, je ne sais pas non plus.





> Cela ve dire qu'il faut prendre la fenetre de 16*16 par rapport a l'axe lier a l'orientation ?? ( chose que j'ai pas pris en compte)
> et l'orientation des pixel autour du point d'interet va etre ori_pixelt - ori_point d'interet


Oui, c'est ca.

----------


## T_Lara

Une derniere question pour le discripteur ( esperons lool :p)

Pour la disatance d 
each entry into a bin is multiplead by a weiight of 1-d for each dimension where d is the disatance of the sample from the central value of the bin as measured in units of the histogram bin spacing

c'est la distance entre le pixel et le centre du carr qui le contient parmi les 16 carr ?

la magnitude du pixel ne diffre toujours pas aprs rotation c'est celle liee a l'image sans rotation sans rien 
SQRT  ((L(x+1,y)- L(x-1,y ))^2 +( L(x,y+1)-L(x,y-1))^2 ))

----------


## pseudocode

> c'est la distance entre le pixel et le centre du carr qui le contient parmi les 16 carr ?


C'est la distance entre le pixels et le centre d'un des 4 patchs (4x4) adjacent. 

Une petite image pour que ca soit plus clair.



 rpter pour les 3 autres patchs : noirs, bleu et vert.


PS : ne pas oublier de pr-multiplier la norme du gradient par la gaussienne centre sur le patch 16x16.

----------


## T_Lara

suis trs reconnaissante pour l'illustration super bien faite la vrit j tais loin de comprendre a Je croyais que le pixel orange n'allais influencer que l'histogramme du patch noir chose qui a l'air compltement fausse aparament et ce qui m'embete le plus c'est que j'arrive pas a voir ca dans le papier de Lowe directement.


 juste une autre question




> C'est la distance entre le pixels et le centre d'un des 4 patchs (4x4) adjacent.


1-qu'est ce que vous appelez adjacent ? j'ai essaye d'analyser votre raisonnement  et comment avoir que 4 patch adjacent je n'est trouvee qu'une seule interpretation ..le pixel influence sur les histogrammes des patch dont sa distance horisontal et vertical de leurs centre est inferieure a 4 

cela est il vrai ? dans ce cas est ce que l image illustrative est juste?

2-cette manipulation se fait pour tout les pixel pas seuls dans les patch des frontieres ??




> PS : ne pas oublier de pr-multiplier la norme du gradient par la gaussienne centre sur le patch 16x16.


3- ie : exp( -(i * i + j* j) /( 4*4*0.5))    ( ou i et j sont pris par rapport au point d'interet ) ??

4- Pour la normalisation du vecteur discripteur "to unit length"  cela veut dire ca ??:: ( enfin moi j'avais pas compris qu'est ce que ca veut dire unit length mais d'apres le code c'est la racine des somme des carres  )



```

```

PS: je reviens sur un petit point pour l'assurer concernant le calcul de l'orientation du point dintrt ..lors de la cration de l'histogramme si  0<tetha<10   c'est hist[0] qui reoit le mag n'est-ce pas 

Vraiment dsl pour tous ce derrangement 

Voici l'image : http://www.imagup.com/data/1121684450.html

----------


## pseudocode

> 1-qu'est ce que vous appelez adjacent ? j'ai essaye d'analyser votre raisonnement  et comment avoir que 4 patch adjacent je n'est trouvee qu'une seule interpretation ..le pixel influence sur les histogrammes des patch dont sa distance horisontal et vertical de leurs centre est inferieure a 4 
> 
> cela est il vrai ? dans ce cas est ce que l image illustrative est juste?


oui.  ::ccool:: 




> 2-cette manipulation se fait pour tout les pixel pas seuls dans les patch des frontieres ??


oui, ca se fait pour tous les pixels de la region 16x16.




> 3- ie : exp( -(i * i + j* j) /( 4*4*0.5))    ( ou i et j sont pris par rapport au point d'interet ) ??


Bah l, ca dpend des interprtations. Moi ce que j'ai compris du papier de Lowe, c'est :

"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"

G(i,j,sigma) = 1/(2.pi.sigma).exp( -(i+j) / ( 2*sigma) )

avec sigma = 16/2 = 8, 
et  -8<= i,j <= +8




> 4- Pour la normalisation du vecteur discripteur "to unit length"  cela veut dire ca ??:: ( enfin moi j'avais pas compris qu'est ce que ca veut dire unit length mais d'apres le code c'est la racine des somme des carres  )


il faut effectivement diviser chaque composante du vecteur par la norme du vecteur.



```

```




> PS: je reviens sur un petit point pour l'assurer concernant le calcul de l'orientation du point dintrt ..lors de la cration de l'histogramme si  0<tetha<10   c'est hist[0] qui reoit le mag n'est-ce pas


Non, je m'tais tromp dans ma rponse la dernire fois (je n'avais pas compris de quoi tu parlais  ::aie:: ). Il faut distribuer la valeur "mag" sur les 2 bins les plus proches, de la meme manire que dans le dessin.

pour 0<tetha<10,

dinf  = (theta-0)/10
dsup  = (10-theta)/10

hist[0]  += (1-dinf)*mag
hist[10] += (1-dsup)*mag




> Voici l'image : http://www.imagup.com/data/1121684450.html


oui, c'est bien ca.  ::ccool::

----------


## T_Lara

Comme suis embtante lool je reviens poser d'autres questions

pour la norme et theta de chaque pixel daprs Lowe on les calcule pour chaque pixel de l'image concern de la pyramide  sans aucune rotation

SQRT ((L(x+1,y)- L(x-1,y ))^2 +( L(x,y+1)-L(x,y-1))^2 ))

la difficult est alors dans detecter les bornes des patchs et les pixels de chacun vu que c'est lie a l'orientation du point d'interet ( pour ce faire on va convertir les coordonne de chaque pixel dans les 16*16 pixels)

La question qui se pose ..si on procde a une rotation de l image  (par matlab) et  on dfinie les nouvelles coordonnes du point d'interet ..la manipulation apres ca se facilite et on aura juste le probleme de redefinir la norme et theta de chaque pixel ..en analysant la formule de la norme on peut la definir a nouveau suivant l'orientation pour qu'elle soit : 
SQRT ((L(x+1,y)- L(x-1,y ))^2 +( L(x,y+1)-L(x,y-1))^2 )) si   0<orientation<22.5 ou  67.5<orientation<112.5  ou 157.5<orientation<202.5 ou 247.5<orientation<292.5  ou 337.5< orientation

SQRT ((L(x+1,y-1)- L(x-1,y+1 ))^2 +( L(x+1,y+1)-L(x-1,y-1))^2 ))  sinon

Par la mme logique on peut calculer theta ( pour y soustraire orientation par la suite )

----------


## pseudocode

Je dois dire que je n'ai pas compris grand chose.  ::koi:: 

1. La norme ne dpend pas de l'orientation
2. On oriente les 16x16 pixels du patch, pas ceux de l'image

Pour la fin, je suis d'accord. L'orientation relative du gradient dans patch se calcule en prenant l'orientation absolue du gradient de l'image, en y retranchant l'orientation (theta) du patch.

----------


## T_Lara

Si I1 est l'image principale
suppose avec moi que t'as obtenu une nouvelle image tourne de I1 par 45 degree qui va tre I2

Pour un certain pixel P reprsent dans  I1(x1,y1)  et I2(x2,y2)
le pixel adjacent I1(X1-1,y1) va tre reprsent dans I2(x2-1,y2-1)

C'est pourquoi je parle de changement de la norme

----------


## pseudocode

> Si I1 est l'image principale
> suppose avec moi que t'as obtenu une nouvelle image tourne de I1 par 45 degree qui va tre I2
> 
> Pour un certain pixel P reprsent dans  I1(x1,y1)  et I2(x2,y2)
> le pixel adjacent I1(X1-1,y1) va tre reprsent dans I2(x2-1,y2-1)
> 
> C'est pourquoi je parle de changement de la norme


Oui, je vois ce que tu veux dire, mais dans la pratique on ne tourne pas l'image originale. A l'inverse, on cherche quel est le pixel de l'image correspondant aux cases du patch 16x16.

Dans un patch non orient, si P(px,py) est le point d'intret dans l'image, la case en haut  gauche du patch a pour coordonne (px-8,py-8). 

Mais comme le patch est orient d'un angle thta=45, le pixel qui correspond  la case en haut  gauche est en ralit aux coordonnes :

px + (-8)*cos(45) - (-8)*sin(45) = px 
py + (-8)*sin(45) + (-8)*cos(45) = py - 8*sqrt(2)



Il suffit d'aller regarder la norme "N" et l'orientation "T" du pixel a cette position, et de retrancher theta  T pour avoir l'orientation relative.

----------


## T_Lara

Ok Meeeeeeeeeerci  ..cela correspond a ce que j'ai dit au dpart bien que c'etait mal dit...




> pour la norme et theta de chaque pixel daprs Lowe on les calcule pour chaque pixel de l'image concern de la pyramide sans aucune rotation
> 
> SQRT ((L(x+1,y)- L(x-1,y ))^2 +( L(x,y+1)-L(x,y-1))^2 ))
> 
> la difficult est alors dans detecter les bornes des patchs et les pixels de chacun vu que c'est lie a l'orientation du point d'interet ( pour ce faire on va convertir les coordonne de chaque pixel dans les 16*16 pixels)



Ce que j'ai dit apres c'etait une question pour dire si la 2 iem proposition peut faire l'affaire ..et a ce qu'il parait la reponse est NON  ::D:

----------


## azertyuio

> Ces composantes reprsentent le voisinage du point d'intrt. Plus precisemment c'est l'ensemble des histogrammes d'orientation du voisinage de ton point d'intrt. Chaque histogramme tant sur 8 composants, et puisque le voisinage est divise en 4x4 rgions, a te donne 8x4x4 = 128 composantes.







> Envoy par MohEllayali
> 
> 
> Tout  fait , mais ce qui me parrait bizzare , c'est la dimension paire de la fentre :
> http://pegasus.cc.ucf.edu/~ja709267/...,19,Descriptor
> 
> le plus logique , pour que la fentre soit symtrique c'est qu'il soit impaires, autant de pixel  droite qu' gauche
> 
> 
> ...



Salut, 

ce que j'ai pas bien compris pourquoi  l'histogramme tant sur 8 composants, et je ne comprend pas encore pourquoi la taille de la fentre 4*4 un nombre paire car comme a le point d'intrt ne soit pas centr ??!!

----------


## pseudocode

> Salut, 
> 
> ce que j'ai pas bien compris pourquoi  l'histogramme tant sur 8 composants, et je ne comprend pas encore pourquoi la taille de la fentre 4*4 un nombre paire car comme a le point d'intrt ne soit pas centr ??!!


Aucune ide pour les 2 questions.  ::D: 

Je suppose que Lowe a fait des tests pour aboutir  choisir une quantification sur un histogramme de 8 bins. Et c'est vrai qu'utiliser un nombre impair de cases aurait simplifi la slection des pixels. D'un autre cot, un nombre pair permet de dcouper la zone en 4. Bref, je ne sais pas.  ::aie::

----------


## azertyuio

> Aucune ide pour les 2 questions. 
> 
> Je suppose que Lowe a fait des tests pour aboutir  choisir une quantification sur un histogramme de 8 bins. Et c'est vrai qu'utiliser un nombre impair de cases aurait simplifi la slection des pixels. D'un autre cot, un nombre pair permet de dcouper la zone en 4. Bref, je ne sais pas.


 ::lol::  
au moins tu m as rpondu merci  ::): 
si jai bien compris les 8 bins signifie qu'un histogramme de 8 dimension ?  :8O: 
jai voulu juste comprendre le fonctionnement du SIFT car j'ai lu l article du D.Lowe mais j'ai eu quelques obscurits !!


rellement je pense pas que je vais l'utiliser ce SIFT car je travaille sur des images mdicales symtriques
et je fais juste une comparaison entre la partie gauche et la partie droite de la mme image pour retrouver l'anomalie !!

et j'ai voulu utiliser diffrentes mthodes d'extraction des points d intrt et diffrents descripteurs 
et comparer les rsultats.

----------


## azertyuio

> si jai bien compris les 8 bins signifie qu'un histogramme de 8 dimension ?


alors l je dis du n importe quoi  ::aie::  
8 represente les 8 directions !!

----------


## pseudocode

> alors l je dis du n importe quoi  
> 8 represente les 8 directions !!


Oui. Ca veut juste dire que l'histogramme est un tableau avec 8 cases.  ::D:

----------


## azertyuio

salut, 

aprs avoir lu l'article de Lowe 
j'ai pas bien compris comment je peux crer le descripteur SIFT
je part d'une zone 16*16 o le point d'intrt est centr 
ensuite je calcule la gradient dI/dx et dI/dy pour chaque pixel 
ensuite je calcule la somme des gradients des pixels horizontaux, verticaux et diagonaux chacun  part .. jobtiendrai 8 valeurs qui reprsente les 8 bins ?? 
c juste ?

----------


## pseudocode

> salut, 
> 
> aprs avoir lu l'article de Lowe 
> j'ai pas bien compris comment je peux crer le descripteur SIFT
> je part d'une zone 16*16 o le point d'intrt est centr 
> ensuite je calcule la gradient dI/dx et dI/dy pour chaque pixel 
> ensuite je calcule la somme des gradients des pixels horizontaux, verticaux et diagonaux chacun  part .. jobtiendrai 8 valeurs qui reprsente les 8 bins ?? 
> c juste ?


heu... non.

Pour chaque pixel :
1. On calcule le vecteur gradient (dI/dx,dI/dy)
2. On convertit le vecteur en cordonnes polaires (rho,theta)
3. On calcule l'index correspondant  "theta" dans l'histogramme : idx = theta*8/360
4. On rpartit la valeur "rho" dans les 2 bins les plus proches

----------


## azertyuio

> heu... non.
> 
> Pour chaque pixel :
> 1. On calcule le vecteur gradient (dI/dx,dI/dy)
> 2. On convertit le vecteur en cordonnes polaires (rho,theta)
> 3. On calcule l'index correspondant  "theta" dans l'histogramme : idx = theta*8/360
> 4. On rpartit la valeur "rho" dans les 2 bins les plus proches


merci mais je suis dsole pour le drangement j'ai compris uniquement la premire tape  ::oops::

----------


## pseudocode

> merci mais je suis dsole pour le drangement j'ai compris uniquement la premire tape


 ::D:  Ah, c'est pas gagn alors. C'est un traitement assez basique.

En pseudo java ca ferait quelque chose comme cela



```

```

----------


## azertyuio

> Ah, c'est pas gagn alors.


maintenant c'est gagn  ::ccool::  
merci pseudocode j'ai compris le principe  ::):

----------


## pseudocode

> maintenant c'est gagn  
> merci pseudocode j'ai compris le principe


Comme quoi, mon code est plus clair que mes explications.  ::aie::

----------


## azertyuio

> Comme quoi, mon code est plus clair que mes explications.


lol  ::lol::  
euuh...enfait ton code et tes explications sont plutt complmentaires.

----------


## azertyuio

bonjour, 


est ce que je peut utiliser le detecteur SIFT pour des images n'ayant pas de changement d'chelle??

et je veux savoir est ce que je peut utiliser le descripteur SIFT avec des points dtects par Harris?

----------


## pseudocode

> est ce que je peut utiliser le detecteur SIFT pour des images n'ayant pas de changement d'chelle??
> 
> et je veux savoir est ce que je peut utiliser le descripteur SIFT avec des points dtects par Harris?


On peut toujours calculer le descripteur SIFT autour de n'importe quel pixel,  n'importe quel chelle. Ca nous donnera toujours un vecteur de 128 valeurs.

Maintenant, il faut bien voir que l'intrt de calculer ce descripteur c'est de pourvoir le comparer  d'autres descripteurs dans le but de trouver des correspondances. Et pour cela, il y a intrt  ce que les deux descripteurs soient calculs sur le mme pixel  la mme chelle.  ::D:

----------


## azertyuio

> On peut toujours calculer le descripteur SIFT autour de n'importe quel pixel,  n'importe quel chelle. Ca nous donnera toujours un vecteur de 128 valeurs.
> 
> Maintenant, il faut bien voir que l'intrt de calculer ce descripteur c'est de pourvoir le comparer  d'autres descripteurs dans le but de trouver des correspondances. Et pour cela, il y a intrt  ce que les deux descripteurs soient calculs sur le mme pixel  la mme chelle.


Salut mon sauveur  ::D:  
si j'ai bien compris (c'est pas toujours la cas  ::D:  ) le descripteur SIFT peut tre appliqu  n'importe quel pixel et on s'en fou de la faon de son extraction (Harris, moravec, Sift..)

mais si on a pas un changement d'chelle je veux dire des images de mme taille est ce que le Dtecteur SIFT peut tre utiliser ou bien c'est pas la peine car son plus est de trouver les points stables pour diffrentes chelles. 
j'epre tre claire  ::):

----------


## pseudocode

> mais si on a pas un changement d'chelle je veux dire des images de mme taille est ce que le Dtecteur SIFT peut tre utiliser ou bien c'est pas la peine car son plus est de trouver les points stables pour diffrentes chelles. 
> j'epre tre claire


L'chelle dont ont parle n'est pas une histoire de taille, de grossissement ou de zoom.

L'chelle dans SIFT (et dans la thorie des scale-spaces) est une valeur de "flou". Il faut avoir la mme valeur de flou aux voisinages des 2 points d'intrts que l'on souhaite comparer via les descripteurs.

----------


## azertyuio

> L'chelle dont ont parle n'est pas une histoire de taille, de grossissement ou de zoom.


mais gnralement quand on fait un zoom il peut y arriv une pixelisation ce qui rend l'image flou !! 





> L'chelle dans SIFT (et dans la thorie des scale-spaces) est une valeur de "flou". Il faut avoir la mme valeur de flou aux voisinages des 2 points d'intrts que l'on souhaite comparer via les descripteurs.


oui je sais qu'il faut avoir le mme degr de flou qui est reprsent par Sigma (je pense) pour pouvoir comparer 2 vecteurs !!

mais dans mon cas j'ai 2 images de mme caractristiques (intensit, taille, degr de flou ...) quel est le plus d'utiliser un *dtecteur SIFT* ? 
autrement dit la constitution de la pyramide gaussienne sert  quoi si je compare 2 images de mme caractristiques.
car si j'ai bien compris SIFT sert  comparer des images de diffrentes caractristiques (je parle du dtecteur et non du descripteur) ::koi::  

est ce que tu peux me le confirmer ?

----------


## pseudocode

> autrement dit la constitution de la pyramide gaussienne sert  quoi si je compare 2 images de mme caractristiques.
> car si j'ai bien compris SIFT sert  comparer des images de diffrentes caractristiques (je parle du dtecteur et non du descripteur) 
> 
> est ce que tu peux me le confirmer ?


La pyramide gaussienne sert  trouver le niveau de flou "idal" pour le descripteur, c'est  dire "idal" pour la fentre de taille 16x16 utilise dans le calcul du descripteur.

Ce niveau de flou n'est pas forcment celui de l'image d'origine. Pour tre plus prcis, il s'agit du niveau de flou qui maximise la norme du laplacien (wikipedia : blob detection)

----------


## azertyuio

ah d'accord merci pseudocode a me semble plus clair maintenant  ::):  

mais peut tre je reviendrai avec d'autres questions  ::D:

----------


## romanzo

Salut

J'essaie d'implmenter l'algo SIFT et il y a pour moi un point pas clair du tout.

Donc imaginons que j'ai 4 octaves avec 5 scales pour chaque octaves.
Je calcul les DoG entre les diffrents scales pour chaque octaves (sauf entre pour 1er et le dernier). J'obtiens donc 4 DoG par octave.
Ensuite je calcule les maxima et minima en comparant les 26 neighbours pour chaque DoG.
Et c'est la  ou je ne comprends pas. Comment met on en relation les keypoints de chaque DoG??

Merci!

----------


## pseudocode

> Et c'est la  ou je ne comprends pas. Comment met on en relation les keypoints de chaque DoG??


Mettre en "relation" les keypoints ? De quelle relation parles-tu ?

----------


## romanzo

En fait je ne comprends  pas ce que l'on fait avec tous les DoG.
On va avoir des keypoints sur chaque DoG mais ils correspondront  des images qui n'ont pas la mme dimension (vu qu'on diminue la rsolution par 2).
Donc  la fin il faut bien mettre ses donnes en commun? (je sais pas si c'est clair) Ou alors il y a quelque chose que n'ai pas compris dans le principe!

----------


## pseudocode

> En fait je ne comprends  pas ce que l'on fait avec tous les DoG.
> On va avoir des keypoints sur chaque DoG mais ils correspondront  des images qui n'ont pas la mme dimension (vu qu'on diminue la rsolution par 2).
> Donc  la fin il faut bien mettre ses donnes en commun? (je sais pas si c'est clair) Ou alors il y a quelque chose que n'ai pas compris dans le principe!


A chaque Keypoint on va associer un descripteur : c'est un peu l'quivalent de l'empreinte digitale du keypoint. Concrtement, il s'agit d'un vecteur compos de 128 valeurs. 

Les donnes de ce vecteur sont indpendantes de l'chelle ou de l'orientation du keypoint. Il suffit donc de trouver 2 vecteurs a peu prs identiques dans 2 images diffrentes pour associer les keypoints entre eux.

----------


## romanzo

Merci pour ton aide, c'est clair! ::ccool::

----------


## romanzo

J'ai une autre question finalement!!

Quand on rsout le systeme H.X=G (avec X pour x chapeau dans le papier de Lowe) pour l'interpolation des extremums, on calcul la drive

D''(x,y,s)/dsds=0.25*(D(x,y,s+2)-2*D(x,y,s)+D(x,y,s-1)) en prennant s-1 et s+1 les sigmas de la DoG du dessous et du dessus.

Mais pour s-2 et s+2 il faut prendre 2 DoG en dessous et 2 DoG au dessus. 
Donc il y a un probleme dans le cas ou l'on qu'un seul DoG en dessous et/ou un seul au dessus!

Comment faire dans ce cas?? ::calim2:: 

Merci

----------


## pseudocode

> J'ai une autre question finalement!!
> 
> Quand on rsout le systeme H.X=G (avec X pour x chapeau dans le papier de Lowe) pour l'interpolation des extremums, on calcul la drive
> 
> D''(x,y,s)/dsds=0.25*(D(x,y,s+2)-2*D(x,y,s)+D(x,y,s-1)) en prennant s-1 et s+1 les sigmas de la DoG du dessous et du dessus.
> 
> Mais pour s-2 et s+2 il faut prendre 2 DoG en dessous et 2 DoG au dessus. 
> Donc il y a un probleme dans le cas ou l'on qu'un seul DoG en dessous et/ou un seul au dessus!


Il n'y a pas de 's+2' dans la formule des diffrences finies. c'est 's+1', 's,' et 's-1'.  :;):

----------


## romanzo

Ok merci j'ai bien vu le rsultat je l'avais juste mal calcul.

Voila ce que j'avais fait

D'(x,y,s)=0.5*(D(x+1,y,s)-D(x-1,y,s))

D''(x,y,s)=0.25*( D((x+1)+1,y,s)-D((x+1)-1,y,s) - (D((x-1)+1,y,s)-D((x-1)-1,y,s))
           = 0.25 (D(x+2,y,s)-2*D(x,y,s)+D(x-2,y,s))

Bon j'ai vu ensuite que finalement la drive seconde se calculait en addition les
dveloppement en sries de Taylor de D(x+h) et D(x-h) au 2e ordre, pour effectivement obtenir:

D''(x,y,s) = (1/h^2) * (D(x+1,y,s)-2*D(x,y,s)+D(x-1,y,s))

Mais j'ai du mal a voir quand mme pourquoi mon calcul pour passer de D'  D" est faux...

----------


## pseudocode

> Mais j'ai du mal a voir quand mme pourquoi mon calcul pour passer de D'  D" est faux...


Ce n'est pas faux. C'est simplement qu'il faut poser h=0.5, et pas h=1.  :;):  

D'(x,y,s)  = (D(x+h,y,s)-D(x-h,y,s))/(2h)
D''(x,y,s) = (D'(x+h,y,s)-D'(x-h,y,s))/(2h)

           = ( (D(x+2h,y,s)-D(x,y,s))/(2h) - (D(x,y,s)-D(x-2h,y,s))/(2h) )/(2h)

           = ( D(x+2h,y,s) - 2*D(x,y,s) + D(x-2h,y,s) ) / 4h
h=0.5 --->  D''(x,y,s) = ( D(x+1,y,s) - 2*D(x,y,s) + D(x-1,y,s) )

----------


## romanzo

Ha a me rassure!
Merci!  ::ccool::

----------


## romanzo

Hop encore moi!

J'ai plus une question d'ordre pratique concernant lintrt du SIFT dans mon cas. (J'ai vu que a avait dj t voqu mais finalement ce ntait pas trs clair)
Je souhaite comparer 2 images de mme taille, de mme chelle(zoom) et qui ont dj t recal (dont pas vraiment dintrt d'avoir l' invariance par rotation).
Comme le SIFT est un dtecteur qui permet d'identifier des images prises avec des angles de vue ou des zooms diffrents.

Donc est ce que dans mon cas:
1/ le dtecteur SIFT est-il intressant  utiliser?
2/ si oui est-il utile de calculer les histogramme orient sachant que les images ont t recal?

Merci encore!

----------


## pseudocode

> Donc est ce que dans mon cas:
> 1/ le dtecteur SIFT est-il intressant  utiliser?
> 2/ si oui est-il utile de calculer les histogramme orient sachant que les images ont t recal?


Il y a deux choses a considrer dans SIFT:

1. La dtection des keypoint : SIFT fait une dtection multi-echelle, en slectionant la "meilleure" chelle possible pour chaque keypoint.

2. Le descripteur des keypoint : SIFT calcule un descripteur invariant au rotations et robustes aux (petites) dformations gomtriques & d'clairage.

Si tu n'as besoin ni d'invariance d'chelle, ni d'invariance aux rotations, alors il y a d'autres mthodes possibles. Par exemple FAST qui utilise une detection et un descripteur totalement diffrent. Ou sinon on peut effectivement simplifier la mthode SIFT en supprimant le multi-echelle ou la rotation des rgions.

----------


## romanzo

D'accord merci.




> IOu sinon on peut effectivement simplifier la mthode SIFT en supprimant le multi-echelle ou la rotation des rgions.


Par contre si on simplifie le SIFT en supprimant le multi chelle et la rotation il ne reste plus grande chose non? 
D'ou SIFT n'est peut tre pas la mthode approprie dans mon cas.

Penses-tu que l'on peut quand mme obtenir de bon rsultat avec le SIFT dans mon cas en utilisant la totalit de l'algorithme ou est ce vraiment inutile de calculer les descripteurs si mes  images sont calibres?

----------


## pseudocode

> Par contre si on simplifie le SIFT en supprimant le multi chelle et la rotation il ne reste plus grande chose non? 
> D'ou SIFT n'est peut tre pas la mthode approprie dans mon cas.


Bah, il reste tout de meme le detecteur de keypoint et le calcul du descripteur. C'est dj pas mal.




> Penses-tu que l'on peut quand mme obtenir de bon rsultat avec le SIFT dans mon cas en utilisant la totalit de l'algorithme ou est ce vraiment inutile de calculer les descripteurs si mes  images sont calibres?


Sauf cas trs particulier, un descripteur est la mthode la plus rapide pour trouver des correspondances entre des nuages de points. SIFT a un trs bon descripteur, ca serait dommage de ne pas l'utiliser.

----------


## romanzo

Mais si tu supprime le multi chelle tu supprime aussi la dtection de keypoints non? Puisque le dtection de keypoints se fait grce  la pyramide gaussienne et donc le multi chelle.

----------


## pseudocode

> Mais si tu supprime le multi chelle tu supprime aussi la dtection de keypoints non? Puisque le dtection de keypoints se fait grce  la pyramide gaussienne et donc le multi chelle.


Tu limites la dtection des keypoints  une seule chelle (l'echelle courante de l'image). Bref, lors de la recherche de maxima, tu regardes seulement les 8 voisins d'un pixel (image courante), au lieu de regarder les 26 voisins (image courante+dessus+dessous).

----------


## romanzo

Ok d'accord!

----------


## romanzo

Bon en fait j'ai encore une question!

Je ne comprend pas trop lintrt d'utiliser plusieurs octaves.
J'ai fait pas mal de recherche mais rien qui ne rpondait vraiment  ma question.
Sur une mme octave on rduit dj la rsolution spatiale en augmentant sigma afin de supprimer les dtails insignifiants.
Pourquoi dans ce cas ne pas utiliser plus de scales sur une seule et mme octave plutt que plusieurs octaves?
Donc en gros ma question qu'elle est l'utilit du downsampling de l'image  par 2 et d'utiliser plusieurs octaves

Merci!

----------


## pseudocode

> Donc en gros ma question qu'elle est l'utilit du downsampling de l'image  par 2 et d'utiliser plusieurs octaves


downsampling par 2 <=> multiplier sigma par 2

Or, plus sigma est grand, plus il faut prendre un grand voisinage de pixels pour faire la convolution... et donc plus la convolution prend du temps. Il est donc beaucoup plus intressant de diviser la taille de l'image par deux, plutot que de doubler la valeur de sigma. En plus ca permet de rutiliser les memes noyaux de convolution pour tous les octaves.

Bon, pour SURF, le temps de convolution est constant, alors ca a moins d'importance sur les performances. Par contre, le downsampling permet d'adoucir l'image puisqu'on fait une moyenne des pixels. Cela supprime donc les hautes frquences dans l'image et rend les approximations de SURF (gaussienne/box) meilleures.

----------


## romanzo

Merci c'est trs clair, tu m'auras bien aid!
Plus qu'a faire marcher l'algo maintenant!

----------


## romanzo

> C'est la distance entre le pixels et le centre d'un des 4 patchs (4x4) adjacent. 
> 
> Une petite image pour que ca soit plus clair.
> 
> 
> 
>  rpter pour les 3 autres patchs : noirs, bleu et vert.


Salut Pseudocode j'ai encore une question  propos d'un point pas trop clair pour moi. J'ai vu que a avait dja t abord prcdemment mais c'est toujours flou.

_ In other words, each entry into a bin is multiplied by a
weight of 1 − d for each dimension, where d is the distance of the sample from the central value of the bin as measured in units of the histogram bin spacing_

Donc ce que je comprend c'est que pour chaque nouvelle entre dans l'histo de 8 bins on multiplie la norme par (1-d) pour chaque dimension (c'est a dire x,y theta?). Ou d est la distance du pixel du patch sur lequel on calcule l'histo ...
C'est le que ne comprends pas trop. Quand tu dis qu'il faut regarder les patchs adjacents, je ne vois pas ou a intervient de cette phrase de Lowe. J'aurai penser que c'etait plutot la distance avec le centre du patch ou se trouve le pixel.
Il parle de _central value of the bin_ et je ne vois pas ce que c'est non plus!

Merci d'avance.

----------


## romanzo

En fait je viens de voir que c'etait aussi ecrit _Therefore, trilinear interpolation is used to distribute the value of each gradient
sample into adjacent histogram bins_.

Donc pour moi si le theta=60 on calcule juste la distance de 60  45 et 60  90 ( pour le adjacent histogram bins) mais je ne vois pas ou il est question de  calculer la distance du pixel au centre des patchs adjacents.

----------


## pseudocode

> Donc pour moi si le theta=60 on calcule juste la distance de 60  45 et 60  90 ( pour le adjacent histogram bins) mais je ne vois pas ou il est question de  calculer la distance du pixel au centre des patchs adjacents.


Et bien, tu l'as dit toi mme dans le message prcdent.




> It is important to avoid all boundary affects in which the descriptor abruptly changes as a sample shifts smoothly from being within one histogram to another or from one orientation to another.


 ::arrow::  On doit s'assurer qu'il n'y a pas de changement brutal du descripteur lorsqu'un point d'intrt passe d'un patch  l'autre (discrtisation de la position spatiale) ou d'une orientation  l'autre (discrtisation de l'orientation = index dans le bin).




> Therefore, trilinear interpolation is used to distribute the value of each gradient sample into adjacent histogram bins. In other words, each entry into a bin is multiplied by a weight of 1 − d for each dimension, where d is the distance of the sample from the central value of the bin as measured in units of the histogram bin spacing.


 ::arrow::  Pour cela, la valeur est rpartie sur les patchs adjacents (position spatiale) et sur les orientations voisines (index dans le bin). Cela nous fait donc une pondration par 3 facteurs : dx, dy, et dtheta --> interpolation trilinaire.

----------


## romanzo

D'accord je vois merci.

Je voulais savoir aussi si je souhaite faire correspondre une seule image avec une autre image, c'est a dire que je n'ai pas plus plusieurs images dans ma database. Est ce qu'il est utile d'utiliser les autres tapes de Lowe( cluster par la transforme de Hough, mthodes des moindres carrs etc)?
Pour l'instant je fais juste la comparaison des deux plus proches voisins et ce n'est pas terrible terrible niveau matching!

----------


## pseudocode

> Pour l'instant je fais juste la comparaison des deux plus proches voisins et ce n'est pas terrible terrible niveau matching!


C'est curieux. Le descripteur de SIFT est gnralement un bon discriminant.




> Je voulais savoir aussi si je souhaite faire correspondre une seule image avec une autre image, c'est a dire que je n'ai pas plus plusieurs images dans ma database. Est ce qu'il est utile d'utiliser les autres tapes de Lowe( cluster par la transforme de Hough, mthodes des moindres carrs etc)?


Il faut d'abord que le matching des plus proches voisins soit bon. Les tapes suivantes sont l pour modliser la transformation, mais le matching initial est primordial.

----------


## romanzo

Ok de toute faon j'ai certainement du faire quelques erreurs.
L'image que j'utilise aussi n'a une faible rsolution et n'a que 3 niveaux de gris.
Pour une image avec beaucoup plus de textures et de dtails  (type Lena ) j'obtiens de bien meilleurs rsultats.
Dans mon cas j'ai des bonnes correspondances mais aussi pas mal de mauvaise, donc je vais tenter d'amliorer a!

galement tu as dis qu'il fallait prendre les 4 patchs adjacents les plus proches.
Pour les trouver on calcule la distance du pixel au centre de chaque patch.
Tu disais prcdemment que la distance pour qu'un patch soit considr adjacent devaient tre infrieur ou gale  4 pixels.
Or si l'on reprend le dessin du dessus, si le pixel que l'on considre se situe en (0,0) du patch noir alors il est  une distance verticale de 6 pixels jusqu'au centre du patch rouge et une distance horizontal de 6 pixels au centre du patch bleu.
Dans ce cas les considre t-on comme adjacents? Si oui la distance est suprieur  4, si non on a que 1 patch adjacent dans ce cas?

----------


## pseudocode

> Or si l'on reprend le dessin du dessus, si le pixel que l'on considre se situe en (0,0) du patch noir alors il est  une distance verticale de 6 pixels jusqu'au centre du patch rouge et une distance horizontal de 6 pixels au centre du patch bleu.
> Dans ce cas les considre t-on comme adjacents? Si oui la distance est suprieur  4, si non on a que 1 patch adjacent dans ce cas?


Non, dans ce cas l, les patchs rouge et bleu ne sont pas adjacents.

Si tu prends le pixels en (0,0), les 4 patchs adjacents sont:
- le patch noir (videmment)
- la patch au-dessus du patch noir
- la patch a gauche du patch noir
- la patch en diagonal haut/gauche du patch noir

----------


## romanzo

Oui a j'avais compris mais je voulais parler du cas ou l'on considrait le 1er patch de la fentre 16*16 (et le pixel (0,0) dans le repre de la fentre)).Dans ce cas la il n'y aura qu' 1 patch adjacent (lui mme) non? Car on se limite bien  la fentre autour du keypoint.

----------


## pseudocode

> Oui a j'avais compris mais je voulais parler du cas ou l'on considrait le 1er patch de la fentre 16*16 (et le pixel (0,0) dans le repre de la fentre)).Dans ce cas la il n'y aura qu' 1 patch adjacent (lui mme) non? Car on se limite bien  la fentre autour du keypoint.


Ah. Oui, dans le cas des bords il n'y aura effectivement qu'un patch adjacent.

Cela dit, comme on pondre toutes les valeurs par une gaussienne centre sur le keypoint, alors on a des valeurs assez faibles sur les bords. Et donc l'absence des 3 autres patchs adjacents n'est pas vraiment grave.

----------


## romanzo

Ouais ok merci, j'avais retenu cette solution dans mon code.
Mais j'ai toujours un important taux de faux matching compar au taux de vrai matching (environ une 20 aine de points en tout). Pourtant j'ai l'impression d'avoir bien tout fait. Je pense que mes images ne sont pas optimales pour cette solution  ::(:

----------

