Algorithme SIFT

**yoannbred** · 14/08/2008, 10h47

Ba.... Tout est relatif

Sachant que celà dépend 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 désires implémenter (sift,matching,PCA-sift...)

Personnellement, sachant que je viens juste de valider mon BAC+2 à l'ESIEE (ingénieur électronique et informatique). J'ai un niveau suffisant en math et en informatique (mon implémentation est en C). Cependant je ne nie pas avoir eu des difficultés et en avoir toujours d'ailleurs pour comprendre Lowe.
En effet, son article est en anglais (ce qui ne me pose pas vraiment de problème, mais les subtilités sont importantes) et d'un niveau en traitement de l'image plutôt é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 résultats sont franchement médiocres...

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** · 14/08/2008, 10h50

Envoyé par 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 déposer 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'implémentation que tu en fais.
Donc en France tu peux implémenter SIFT et l'utiliser à des fins (*ortho?) commerciales.

**yoannbred** · 20/08/2008, 11h16

Juste comme sa au passage, quelqu'un connait la méthode 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 sérieux doute. Si quelqu'un peut m'aiguiller?!

**ArgusAzure** · 21/08/2008, 10h36

Envoyé par yoannbred

Juste comme sa au passage, quelqu'un connait la méthode 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 sérieux doute. Si quelqu'un peut m'aiguiller?!

Une simple règle de 3 doit répondre à tes attentes.
Tu as des valeurs de 0 à 255 que tu veux étaler de 0 à 2^32-1.
Espérons que le train n'a pas déja déraillé sur l'aiguillage.

**yoannbred** · 21/08/2008, 14h41

Jcrois qu'il est en bas de la falaise

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

**yoannbred** · 22/08/2008, 09h47

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

**mel84** · 16/06/2009, 16h06

Bonjour,
Je dois implémenter l'algo de sift pour faire une détection de point d'intérêt 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 représente 'sigma', 's' et 'k' ??

Envoyé par yoannbred

Bonjour,
Si je considère k=racine(2), j'aurais s=2 donc s+3=5 images par octave. Si j'ai bien compris les octaves sont divisées en parties égales.
Ainsi si je prend sigma=1 et que comme le dit Lowe l'avant dernière image de l'octave à un sigma doublée (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** · 16/06/2009, 17h32

Envoyé par mel84

Bonjour,
Je dois implémenter l'algo de sift pour faire une détection de point d'intérêt 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 représente 'sigma', 's' et 'k' ??

J'ai posté un code pour construire une pyramide gaussienne dans la rubrique "contribuez". C'est déjà un premier pas vers SIFT.

Comment fais-tu pour avoir ça??
Merci

Au départ, l'image est considérée comme ayant une échelle "sigma". A chaque changement d'octave, l'échelle double. Pour les niveaux dans un octave, les échelles doivent s'étaler uniformément entre sigma et 2*sigma, c'est a dire suivant une suite géométrique de raison K=2^(1/nombre de niveaux par octave)

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

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
 
=> K = 2^(1/3)
 
Image initiale  : échelle = sigma
-------------------
Octave 1, niveau 1 : échelle = (K)*sigma
Octave 1, niveau 2 : échelle = (K^2)*sigma 
Octave 1, niveau 3 : échelle = (K^3)*sigma = 2.0*sigma
-------------------
Octave 2, niveau 1 : échelle = 2.0*(K)*sigma
Octave 2, niveau 2 : échelle = 2.0*(K^2)*sigma
Octave 2, niveau 3 : échelle = 2.0*(K^3)*sigma = 4.0*sigma

Dans la pyramide de Lowe, on ajoute un niveau au début et deux à la fin de l'octave pour pouvoir calculer toutes les DoG sans changer d'octave.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
=> K = 2^(1/3)

Image initiale  : échelle = sigma
-------------------
Octave 1, niveau 0 : échelle = sigma
Octave 1, niveau 1 : échelle = (K)*sigma
Octave 1, niveau 2 : échelle = (K^2)*sigma 
Octave 1, niveau 3 : échelle = (K^3)*sigma = 2.0*sigma
Octave 1, niveau 4 : échelle = (K^4)*sigma 
Octave 1, niveau 5 : échelle = (K^5)*sigma
-------------------
Octave 2, niveau 0 : échelle = 2.0*sigma
Octave 2, niveau 1 : échelle = 2.0*(K)*sigma
Octave 2, niveau 2 : échelle = 2.0*(K^2)*sigma
Octave 2, niveau 3 : échelle = 2.0*(K^3)*sigma = 4.0*sigma
Octave 2, niveau 4 : échelle = 2.0*(K^4)*sigma
Octave 2, niveau 5 : échelle = 2.0*(K^5)*sigma

**mel84** · 17/06/2009, 08h48

Je te remercie de ta réponse, c'est déjà beaucoup plus clair maintenant!!
Cependant pourquoi on doit ajouter 2 niveau à la fin pour Lowe? un niveau je comprend, mais deux??

**pseudocode** · 17/06/2009, 09h50

Envoyé par mel84

Je te remercie de ta réponse, c'est déjà 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 consécutifs de la pyramide pour faire un niveau de Dog.

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

Code :

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

1
2
3
4
5
6
7
8
Octave 1, niveau 1 
                    >----> Dog(1,1)
Octave 1, niveau 2 
                    >----> Dog(1,2)
Octave 1, niveau 3 
                    >----> Dog(1,3)
Octave 1, niveau 4

On va également avoir besoin de comparer une DoG a la DoG précédente 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 supplémentaires. Soit au total 3 niveaux de pyramide de plus que le nombre de DoG.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
Octave 1, niveau 0 
                    >----> Dog(1,0)
Octave 1, niveau 1 
                    >----> Dog(1,1)
Octave 1, niveau 2 
                    >----> Dog(1,2)
Octave 1, niveau 3 
                    >----> Dog(1,3)
Octave 1, niveau 4 
                    >----> Dog(1,4)
Octave 1, niveau 5

**mel84** · 17/06/2009, 10h16

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

Merci beaucoup

**mel84** · 17/06/2009, 13h01

Encore moi,
C'est bon j'ai tout compris pour la différence de gaussienne (encore merci!) mais maintenant je bloque sur la recherche d'extrema!!
Pour rechercher les extréma, 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, sélectionner les réél points d'intérêt!!

Merci

**pseudocode** · 17/06/2009, 14h05

Envoyé par mel84

Mais pour chaque scale, on va avoir plein de points extrema, je ne comprend pas comment on fait pour, avec tous les scales, sélectionner les réél points d'intérêt!!

D'après le document de Lowe (figure 3), on obtient entre 2000 et 3000 extrema. Pour ne garder que les points d'intérêts, il faut continuer la méthode (chapitre 4 : Accurate keypoint localization + Eliminating edge responses).

**mel84** · 18/06/2009, 12h06

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

**pseudocode** · 18/06/2009, 14h39

Envoyé par mel84

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

D(X) est une fonction à 3 paramètres, car X=(x,y,s).

(NB : merci a Lowe d'avoir mis d, D, x et X dans la même équation

)

La dérivée première de D(X) est le vecteur:

Code :

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

1
2
3
4
 
           |dD(X)/dx|
dD(X)/dX = |dD(X)/dy|
           |dD(X)/ds|

La dérivée seconde de D(X) est la matrice hessienne:

Code :

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

1
2
3
4
 
             |d²D(X)/dx²  d²D(X)/dxdy d²D(X)/dxds|
d²D(X)/dX² = |d²D(X)/dydx d²D(X)/dy²  d²D(X)/dyds|
             |d²D(X)/dsdx d²D(X)/dsdy d²D(X)/ds² |

Reste à calculer les valeurs grace aux formules de différenciation discrètes:

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

et voila.

**mel84** · 18/06/2009, 17h35

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

**mel84** · 22/06/2009, 16h29

Bonjour, (encore moi!!)

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

Merci

**Morpheus42000** · 17/07/2009, 23h59

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

--------
L'implémentation 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 réouvre mes vieux fichiers tout poussiéreux et essaye de "finir" le travail ^^

Merci d'avance ...

**Morpheus42000** · 19/07/2009, 19h15

Dsl pour ce post inutile ^^
Pour ceux qui comme moi n'auraient pas pris la peine de "scanner" toutes les discussion, la réponse 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** · 28/12/2009, 15h25

salut

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

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

Algorithme SIFT

Traitement d'images

Discussions similaires

Partager

Partager