INTRODUCTION :

SIFT est l’une des méthodes de détection de points d’intérêt les plus populaires dans le

domaine de vision par ordinateur. Elle transforme une image en entrée en collection de vecteurs, où

chaque vecteur représente un point d’intérêt. Les points d’intérêts extraits par cette méthode ont

plusieurs propriétés intéressantes, en plus d’être très robuste au bruit, ils sont invariants aux

changements d’échelle, changements de point de vue, transformations affines,… etc. Dans ce présent

rapport, nous détaillons les différentes étapes de la méthode.

LA METHODE SIFT : Généralités

La méthode SIFT extrait un nombre important de points d’intérêt très stable et robuste. Le

coût de l’extraction de ces points est minimisé en adoptant une approche de filtre en cascade. Les

opérations les plus coûteuses sont exécutés en avale de l’algorithme, cette approche permet d’éliminer

le plus grand nombre de points sous différents critères au début de l’algorithme.

La méthode SIFT se divise en plusieurs étapes que nous détaillons ci-dessous :

1. Détection des extrema de l’espace échelle :

Cette étape initiale extrait de l’image des points clés invariants aux changements

d’échelles en utilisant les différences de gaussiennes et l’espace échelle.

a) Notion d’espace échelle :

Les objets d’une scène du monde réel sont visibles sous un intervalle d’échelle bien

définie. Prenant l’exemple classique d’une branche d’arbre dans une forêt. A l’échelle des

centimètres, nous pourrons bien voir une branche mais à l’échelle des mini-mètres la branche

devient invisible. A l’échelle des mètres, nous pourrons voir un arbre et à l’échelle des

kilomètres c’est la forêt qui est visible.

- Représentation multi-échelles d’un signal :

Une représentation multi-échelles d’un signal est un ensemble ordonné de signaux

dérivés représentant un signal original à différentes échelles. Le but d’une représentation

multi-échelle d’un signal est de représenter l’aspect multi-échelle d’une scène du monde réel

et simplifier le traitement d’un signal en supprimant les détails.

1

Figure 1 : Représentation multi échelle d’un signal, les signaux sont lissé avec une

gaussienne.

On appelle espace échelle une représentation multi échelle construite par le produit de

convolution du signal avec une fonction gaussienne g(x , y , σ ) avec σ croissant. L’espace

échelle est définie par la fonction l(x , y , σ ) définie comme suit :

L ( x , y , σ )=g ( x , y , σ )∗f (x , y )

AvecG ( x , y , σ )= 12π σ 2 e

−( x2+ y2)2σ 2

, σ Paramètre échelle.

L’idée principale derrière la construction d’un espace échelle est que les informations

à échelles petites dans une image seront supprimées au fur et à mesure que σ croit. Ces

informations seront mises en évidence au fur et à mesure que σ décroit. Lors de la

convolution d’un signal par une fonction gaussienne avec comme paramètreσ , le résultat de

cette opération est de supprimer certaine structure du signal avec une longueur caractéristique

inférieure àσ .

Figure 2 : Différents niveaux de représentation d’une image dans un espace d’échelle ainsi que les différentes

régions de gris indiquant les minima et les maximas sous différents échelles.

2

La détection des positions invariantes aux changements d’échelle de l’image peut être

accomplit en cherchant des points stables à travers toutes les échelles possibles en utilisant

l’espace échelle.[LOWE 1999] a proposé une méthode de détection de points clés se basant

sur le calcul des maximums et des minimums des différences de gaussiennes DoG appliquées

à l’espace échelle.

Une différence de gaussienneD(x , y , σ ) est définit comme suit :

D ( x , y , σ )=L ( x , y , kσ )−L ( x , y , σ ).

Figure 3 : Soustraction des images gaussiennes adjacentes appartenant à une même octave d’un

espace d’échelle pour produire les différences de gaussiennes.

L’image initiale est consécutivement convoluée avec des différences de gaussiennes

pour produire des images séparées par un facteur constant k dans l’espace échelle. On divise

chaque octave de l’espace échelle (Octave est l’équivalent de deux foisσ ) en s intervalles avec

k=21s , on aura ainsi le même nombre d’images lissé (convoluée avec des gaussiennes) par

octave.

Pour chaque octave, l’image initiale est convoluée avec des gaussiennes pour produire

s images gaussiennes de l’espace échelle appartenant à une octave. Les images gaussiennes de

3

la même octave sont soustraites pour produire les différences de gaussiennes. Apres chaque

Octave, l’échelle de l’image gaussienne est divisée par un facteur de 2.

Figure 5: Représentation d’une image dans un espace échelle avec 5 images pour chaque

octave. On remarque qu’après chaque octave l’échelle de l’image gaussienne initiale est

divisée par un facteur de 2.

Les points clés sont localisés par les extremums des différences de gaussiennes. Afin

de détecter les maximums et les minimums des différences de gaussiennesD(x , y , σ ) , chaque

point est comparé à ses 8 voisins de la même image et ses 18 voisin dans les images

adjacentes (images gaussiennes inférieures et supérieures). Un point est sélectionné comme

un point clé s’il est plus grand ou plus petit que ses voisins.

4

Figure 5 :Les extremums d’une différences de gaussiennes sont détectés en comparant un

pixel x avec ses 26 voisins dans l’échelle courants et dans les deux échelles adjacents.

Figure 6: A droite, l’image initiale 233x189 pixels. A gauche, les 832 points d’intérêts initiaux

extrait avec les maxima et les minimas des différences de gaussiennes, représentés sous forme de

vecteur indiquant l’échelle et la position ainsi que l’orientation.

2. Localisation des points :

L’approche initiale de la détection des extremums se contente de localiser les

extremums et de reconnaitre l’échelle du point clé. [BROWN, LOWE, 1999] ont développé

une méthode qui utilise le développement de Taylor au second ordre de la différence de

gaussienne, Cette approche améliore la stabilité des points extrait et leur mise en

correspondance avec des points d’autres images.

5

Le développement de Taylor des différences de gaussiennes est donné par la formule qui suit :

D ( x )=D+d DT (x)

dx+1

2XT ∂2 y

∂ x

D et ses dérivés sont évaluées au point clé détecté par l’approche initiale et XTest le décalage

à partir de ce point.

La localisation de l’extremum se fait en dérivant D(x) par rapport à x. Ensuite, On résout

l’équationD ( x )=0, la solution de cette équation X̂ donne la position exacte de l’extremum par

rapport au point clé détecté initialement.

X̂=d2 D−1

dx2

dDdx

.

Si toutes les dimensions de X̂ sont plus grandes que 0,5, cela veut dire que l’extremum

appartient à un autre point de l’image à proximité du point initiale. Dans ce cas, le point clé

initial sera remplacé, X̂ sera additionné à X (point initiale) pour donner la position exacte du

nouveau point clé.

Elimination des points à faible contraste :

Pour éliminer les points à faible contraste, on calcule la valeur du développement de

taylor D(X) pourX=X̂ . Si la valeur de |D( X̂ )| est inférieure à 0,03 alors le point clé est

éliminé.

Elimination des points se trouvant sur un contour :

Pour éliminer les points clés se trouvant sur un contour, en utilise le fait qu’une large courbure

principale se trouve tout le long du contour. Tandis que, Dans la direction perpendiculaire

d’un contour se trouve une étroite courbure principale.

Une courbure principale est détectée à partir d’une Matrice HESSIAN 2x2, H, calculée à

partir de la position du point clé et son échelle.

H=[ d2 Ddx2

d2 Ddx dy

d2 Ddxdy

d2 Ddy2 ]

Les valeurs propres de H sont proportionnelles aux courbures principales de D. Soit a et b

les deux valeurs propres de H, telle que a>b. nulle besoin de calculer les deux valeurs propres

de H, On se contente d’utiliser les relations entre les deux valeurs propres a et b.

On commence par calculer la somme des deux valeurs propres à partir de la trace de la

matrice H :

6

Tr ( H )=d2 Ddx2 + d2 D

dy2 =a+b

Puis on calcule le produit des deux valeurs propres à partir du déterminant de la matrice H :

Det ( H )=d2 Ddx2 x

d2 Ddy2 − d2 D

dx dyx

d2 Ddx dy

=a x b

Soit r le ratio entre les deux valeurs propres a et b, on donne la fraction entre la trace de H

élevée au carré Tr(H) 2 et le déterminant de la matrice H Det(H) par la formule qui suit :

Tr (H )2

Det (H )=

(a+b)2

ab=

(rb+b)2

r b2 =(r+1)2

r≅ r

Cette fraction dépend uniquement du ratio entre les deux valeurs propres a et b. On vérifie

que le ratio des courbures principales est au dessous d’un seuilr , en testant l’égalité suivante :

Tr (H )2

Det (H )<(r+1)2

r

Une valeur du seuil r`=10, élimine les points clés ayant un ratio entre les deux courbures

principales plus grand que 10.

Figure 7 : La figure à gauche montre des points d’intérêts dans une image avant

l’élimination des points extrait du à une forte réponse des DoG aux contours (Courbures).La

figure de droite montre des points d’intérêts restant dans l’image après l’élimination des

réponses aux contours.

Assignement des orientations :

Afin d’extraire des points d’intérêt invariants à la rotation, on assigne à chaque point

clé candidat à devenir un point d’intérêt une orientation basé sur les propriétés locales du

7

point clé. La méthode SIFT utilise une approche basée sur le calcul des descripteurs

d’orientation invariants, introduite par [Schmid , Mohr (1997)].

Pour un point clé donné, on sélectionne l’image gaussienne L(x , y , σ1), avecσ 1échelle

correspondante au point clé. Nous calculons ensuite l’ampleur du gradient m(x , y ) et

l’orientation du gradientθ(x , y) au voisinage du point clé en utilisant les différences de

gaussiennes comme le montre les deux formules suivantes :

m ( x , y )=√( L ( x+1 , y )−L(x−1 , y))2+(L (x , y+1 )−L(x , y+1))2

θ ( x , y )=tan−1[ L (x , y+1 )−L(x , y−1)L (x+1 , y )−L(x−1 , y) ]

Un histogramme d’orientation est défini sur une région dont la taille dépend de l’échelle du

point clé considéré sur le quel la région est centré. L’histogramme contient 36 barres, chaque

une d’elle correspond à une orientation de la région. Sur un angle de 360°, chaque barre

couvre un angle de 100. Chaque point (x,y) est pondéré par l’ampleur du gradient et d’une

fenêtre gaussienne circulaire g(x0 , y0 ,σ ) avec σ égale à 3/2 l’échelle du point clé considéré

et (x0 , y0) coordonnées du point clé considéré. On prend les points (x, y) dont l’orientation 𝜃( x , y ) est assigné à une certaine barre, on somme leur pondération et on présente le résultat

sur l’histogramme.

Les piques de l’histogramme d’orientation correspondent aux directions dominantes

du gradient. Le plus haut pique représenté sur l’histogramme nous révèle l’orientation du

gradient pour le point clé considéré. Les autres piques dépassant les 80% du plus haut pique

nous révèlent l’existence d’autres points d’intérêt ayant la même position et la même échelle

que le point clé originale. Mais l’orientation du nouveau point est donnée par l’orientation du

pique considéré dans l’histogramme.

8

Figure 8 : Exemple d’un histogramme d’orientation, ou chaque barre couvre 10°. Le plus haut pique

de l’histogramme représente l’orientation du gradient autour du point clé. Le pique dépassant 80% la

longueur du plus haut pique révèle d’autres points candidats à devenir points d’intérêt.

Descripteur d’un point clé :

On construit un descripteur unique pour chaque point clé afin de l’identifier et le

distinguer parmi un ensemble de points clés. En premier, nous définissons une fenêtre de

16x16 pixels autour du point clé considéré. Pour chaque point de la fenêtre 16x16, on calcule

l’ampleur de son gradient et son orientation en utilisant les formules () et () après avoir

sélectionné une image gaussienneL(x , y , σ1), avec σ 1échelle du point clé considéré.

Pour chaque point du descripteur, on assigne un poids à l’ampleur de son gradient,

égale à la valeur de la fonction gaussienneg(x , y , σ 0) en ce point avec σ 0 égale à 3/2 la taille

de la fenêtre du descripteur. Le but des poids assigné à tous les points du descripteur est

d’éviter les brusques changements dans le descripteur avec les petits changements dans la

position de la fenêtre en donnant moins d’importance aux gradients des points qui sont loin

du centre

connus pour être les plus affectés par les erreurs de positionnement.

9

Figure 9 : Représentation graphique d’une fonction gaussienne. On remarque qu’une fonction

gaussienne prend des valeurs maximales autour d’un centre X0 , Y0. Les valeurs de la fonctionne

gaussienne décroient dés qu’on s’éloigne du centre. Cette propriété de la fonction gaussienne est

utilisée comme filtre pour donner plus d’importance aux points présents au centre plus que ceux

éloigné du centre.

Figure 10 : A gauche une représentation graphique d’une gaussienne à 3 dimensions. Les

valeurs de la fonction gaussienne sont pondérées à l’ampleur du gradient dans la fenêtre 4X4

pour affaiblir l’importance des points loin du centre.

On divise la fenêtre 16x16, avec les nouvelles valeurs du gradient, en plusieurs

fenêtres de 4x4. Pour chaque nouvelle fenêtre de 4x4, on construit un histogramme

d’orientation de 8 barres qui représentent l’orientation du gradient au tour du point clé.

Chaque une des barres de l’histogramme couvre un angle de 45° au sein de la fenêtre. Pour

Les points dont les orientations appartiennent à une même barre dans l’histogramme, on

calcule les sommes des ampleurs de leurs gradients et on représente le résultat sur la barre

correspondante.

10

Figure 11 : A gauche, la fenêtre initiale du descripteur de point clé en rouge au centre de la

fenêtre, La fenêtre initiale subdivisé en fenêtre de 4x4. A droite, construction d’un

histogramme d’orientation pour chaque fenêtre 4x4.

Afin de permettre d’ajuster le descripteur pour réduire l’effet de changement de luminosité,

celui-ci est normalisé en unité de longueur. Cette opération est faite de la même façon que la

normalisation d’un vecteur (Un descripteur est un vecteur) en calculant la racine des carrés.

Un changement de contraste, dans le quel chaque pixel est multiplié par une constante,

multipliera aussi le gradient par la même constante. L’effet de changement de contraste est

alors annulé par la normalisation du gradient.

Un changement dans la luminosité, dans le quel une constante est additionnée pour les

gradients de tous les pixels de l’image n’affectera pas le descripteur car les magnitudes des

gradients sont calculés avec la différence entre les pixels.

Des changements non linéaires dans l’illumination de l’image peuvent subvenir du à

la saturation de la caméra et aux changements d’effets de luminosité sur les objets 3D d’une

scène du monde réel. Ces effets peuvent causer des changements dans l’ampleur du gradient

mais ne peuvent affecter l’orientation du gradient. Cela a mène à réduire l’importance des

larges valeurs de l’ampleur du gradient en certain point en les seuillant avec 0,2 (La valeur

0,2 a été déterminé par expérimentation en utilisant des images contenant différents

illuminations du même objet ) et refaire la normalisation du vecteur. Ceci donne plus

d’importance à la distribution des orientations du gradient au lieu de la largeur de l’ampleur

gradient.

11