Scale-invariant feature transform

La détection s'effectue dans un espace discret que l'on appelle espace des échelles (scale space) qui comporte trois dimensions : les coordonnées cartésiennes ${\displaystyle x}$ et ${\displaystyle y}$ et le facteur d'échelle ${\displaystyle \sigma }$. On appelle gradient de facteur d'échelle ${\displaystyle \sigma }$ (noté ${\displaystyle L}$) le résultat de la convolution d'une image ${\displaystyle I}$ par un filtre gaussien ${\displaystyle G}$ de paramètre ${\displaystyle \sigma }$, soit[19] :

${\displaystyle L\left(x,y,\sigma \right)=G\left(x,y,\sigma \right)*I\left(x,y\right)}$

Pyramide de gradients : 3 octaves de 6 gradients.

Cette convolution a pour effet de lisser l'image originale ${\displaystyle I}$ de telle sorte que les détails trop petits, c'est-à-dire de rayon inférieur à ${\displaystyle \sigma }$[note 1], sont estompés. Par conséquent, la détection des objets de dimension approximativement égale à ${\displaystyle \sigma }$ se fait en étudiant l'image appelée différences de gaussiennes (en anglais difference of gaussians, DoG) définie comme suit :

${\displaystyle D\left(x,y,\sigma \right)=L\left(x,y,k\sigma \right)-L\left(x,y,\sigma \right)}$,

où ${\displaystyle k}$ est un paramètre fixe de l'algorithme qui dépend de la finesse de la discrétisation de l'espace des échelles voulue[19].

Dans cette image ne persistent plus que les objets observables dans des facteurs d'échelle qui varient entre ${\displaystyle \sigma }$ et ${\displaystyle k\sigma }$. De ce fait, un point-clé candidat ${\displaystyle (x,y,\sigma )}$ est défini comme un point où un extremum du DoG est atteint par rapport à ses voisins immédiats, c'est-à-dire sur l'ensemble contenant 26 autres points défini par :

${\displaystyle \{D\left(x+\delta _{x},y+\delta _{y},s\sigma \right),\delta _{x}\in \{-1,0,1\},\delta _{y}\in \{-1,0,1\},s\in \{k^{-1},1,k\}\}}$

L'utilisation d'une pyramide est préconisée pour optimiser le temps de calcul des images floutées à un grand nombre d'échelles différentes. La base de la pyramide est en général l'image originale et un niveau donné – on parle d'octave par analogie avec la musique – est obtenu à partir du précédent en divisant la résolution de l'image par 2, ce qui revient à doubler le facteur d'échelle. Au sein d'une même octave, le nombre de convoluées à calculer est constant. Le facteur fixe ${\displaystyle k}$ dans les formules ci-dessus est calculé pour qu'au final, l'espace discrétisé des facteurs d'échelles considérés corresponde à une progression géométrique ${\displaystyle \{\sigma _{0},k\sigma _{0},k^{2}\sigma _{0},...\}}$, avec à chaque changement d'octave une valeur ${\displaystyle k^{p}\sigma _{0}}$ qui devient égale à une quantité de la forme ${\displaystyle 2^{t}\sigma _{0}}$. Ce détail – la progression géométrique des facteurs d'échelle – est important pour que les valeurs des DoG à différentes échelles soient comparables entre elles et il évite, observe Lowe, d'avoir à utiliser un facteur de normalisation dans leur calcul[20].

Construction de la pyramide de différences de gaussiens (DoG) à partir de la pyramide de gradients.

L'étape de détection des points-clés candidats décrite ci-dessus est une variante de l'une des méthodes de blob detection (détection de zones) développée par Lindeberg, qui utilise le laplacien normalisé par le facteur d'échelle[21] au lieu des DoG. Ces derniers peuvent être considérés comme une approximation des laplaciens et présentent l'avantage d'autoriser l'utilisation d'une technique pyramidale[22].

Exemple de détection d'extremums dans l'espace des échelles.

Après la détection des extremums dans l'espace des échelles (leurs positions sont indiquées sur l'image du haut), l'algorithme élimine les points de faible contraste (les points restants apparaissent sur l'image du milieu), puis les points situés sur les arêtes. Les points restants sont indiqués sur l'image du bas.

L'étape de détection d’extremums[20] produit en général un grand nombre de points-clés candidats, dont certains sont instables ; de plus, leur localisation, en particulier aux échelles les plus grandes (autrement dit dans les octaves supérieures de la pyramide où la résolution est plus faible) reste approximative. De ce fait, des traitements supplémentaires sont appliqués, pour un objectif double : d'une part, reconverger la position des points pour améliorer la précision sur ${\displaystyle x}$, ${\displaystyle y}$ et ${\displaystyle \sigma }$ ; d'autre part, éliminer les points de faible contraste ou situés sur des arêtes de contour à faible courbure et donc susceptibles de « glisser » facilement.

Visant à augmenter de façon significative la stabilité et la qualité de la mise en correspondance ultérieure[23], cette étape, qui est une amélioration de l'algorithme original, s'effectue dans l'espace des échelles à trois dimensions, où ${\displaystyle D(x,y,\sigma )}$, qui n'est connu que pour des valeurs discrètes de ${\displaystyle x}$, ${\displaystyle y}$ et ${\displaystyle \sigma }$, doit être interpolé.

Cette interpolation s'obtient par un développement de Taylor à l'ordre 2 de la fonction différence de gaussiennes ${\displaystyle D(x,y,\sigma )}$, en prenant comme origine les coordonnées du point-clé candidat[23]. Ce développement s'écrit comme suit :

${\displaystyle D({\textbf {x}})=D+{\frac {\partial D}{\partial {\textbf {x}}}}^{\rm {T}}{\textbf {x}}+{\frac {1}{2}}{\textbf {x}}^{\!{\rm {T}}}\,{\frac {\partial ^{2}D}{\partial {\textbf {x}}^{2}}}{\textbf {x}}}$

où ${\displaystyle D}$ et ses dérivées sont évaluées au point-clé candidat et où ${\displaystyle {\textbf {x}}=(x,y,\sigma )^{\!{\rm {T}}}}$ est un delta par rapport à ce point. Les dérivées sont estimées par différences finies à partir des points voisins connus de façon exacte. La position précise de l'extremum ${\displaystyle {\hat {\textbf {x}}}}$ est déterminée en résolvant l'équation annulant la dérivée de cette fonction par rapport à ${\displaystyle {\textbf {x}}}$ ; on trouve ainsi[23] :

${\displaystyle {\hat {\textbf {x}}}=-{\frac {\partial ^{2}D}{\partial {\textbf {x}}^{2}}}^{-1}{\frac {\partial D}{\partial {\textbf {x}}}}}$

Un delta ${\displaystyle {\hat {\textbf {x}}}}$ supérieur à ${\displaystyle 0,5}$ dans l'une des trois dimensions signifie que le point considéré est plus proche d'un des voisins dans l'espace des échelles discret. Dans ce cas, le point-clé candidat est mis à jour et l'interpolation est réalisée à partir des nouvelles coordonnées. Sinon, le delta est ajouté au point candidat initial qui gagne ainsi en précision[24].

Un algorithme de reconvergence similaire a été proposé dans l'implémentation temps-réel basée sur les pyramides hybrides de Lindeberg et Bretzner[25].

La valeur de ${\displaystyle D({\textbf {x}})}$ aux coordonnées précises ${\displaystyle {\hat {\textbf {x}}}}$ du point-clé peut être calculée à partir du développement de Taylor de cette fonction, et constitue donc un extremum local. Un seuillage absolu sur cette valeur permet d'éliminer les points instables, à faible contraste[23] - [note 2].

Les points situés sur les arêtes (ou contours) doivent être éliminés car la fonction DoG y prend des valeurs élevées, ce qui peut donner naissance à des extremums locaux instables, très sensibles au bruit : si l'image devait subir un changement numérique même imperceptible, de tels points-clés peuvent se retrouver déplacés ailleurs sur la même arête, ou même simplement disparaître[26].

Un point candidat à éliminer, si l'on considère les deux directions principales à sa position, est caractérisé par le fait que sa courbure principale le long du contour sur lequel il est positionné est très élevée par rapport à sa courbure dans la direction orthogonale[26]. La courbure principale est représentée par les valeurs propres de la matrice hessienne ${\displaystyle {\textbf {H}}}$ :

${\displaystyle {\textbf {H}}={\begin{bmatrix}D_{xx}&D_{xy}\\D_{xy}&D_{yy}\end{bmatrix}}}$

Les dérivées doivent être évaluées aux coordonnées du point d'intérêt ${\displaystyle (x,y,\sigma )}$ dans l'espace des échelles. Les valeurs propres de ${\displaystyle {\textbf {H}}}$ sont proportionnelles aux courbures principales de ${\displaystyle D}$, dont seul le rapport ${\displaystyle r}$ est intéressant. La trace de ${\displaystyle {\textbf {H}}}$ représente la somme de ces valeurs, le déterminant son produit. Par conséquent, en adoptant un seuil ${\displaystyle r_{\text{th}}}$ sur le ratio des courbures (${\displaystyle r_{\text{th}}=10}$ dans la méthode originale de Lowe[2]), un point-clé candidat va être retenu, selon le critère adopté par Lowe, si[26] :

${\displaystyle R={\frac {\operatorname {tr} ({\textbf {H}})^{2}}{\operatorname {det} ({\textbf {H}})}}={\frac {(r+1)^{2}}{r}}<{\frac {(r_{\text{th}}+1)^{2}}{r_{\text{th}}}}}$

La vérification de ce critère est rapide, ne nécessitant qu'une dizaine d'opérations flottantes seulement. Lorsque ce critère n'est pas vérifié, le point est considéré comme localisé le long d'une arête et il est par conséquent rejeté.

Cette étape est inspirée de la technique de détection de points d'intérêt par l'opérateur de Harris ; pour le seuillage, une matrice hessienne est utilisée au lieu de la matrice des moments d'ordre 2 (tenseur)[26].

L'étape d'assignation d’orientation consiste à attribuer à chaque point-clé une ou plusieurs orientations déterminées localement sur l'image à partir de la direction des gradients dans un voisinage autour du point. Dans la mesure où les descripteurs sont calculés relativement à ces orientations, cette étape est essentielle pour garantir l'invariance de ceux-ci à la rotation : les mêmes descripteurs doivent pouvoir être obtenus à partir d'une même image, quelle qu'en soit l'orientation[14].

Pour un point-clé donné ${\displaystyle (x_{0},y_{0},\sigma _{0})}$, le calcul s'effectue sur ${\displaystyle L(x,y,\sigma _{0})}$, à savoir le gradient de la pyramide dont le paramètre est le plus proche du facteur d'échelle du point. De cette façon, le calcul est également invariant à l'échelle. À chaque position dans un voisinage du point-clé, on estime le gradient par différences finies symétriques, puis son amplitude (c.-à-d. sa norme) ${\displaystyle m(x,y)}$, et son orientation ${\displaystyle \theta (x,y)}$[14] :

${\displaystyle m\left(x,y\right)={\sqrt {{\bigl (}L\left(x+1,y\right)-L\left(x-1,y\right){\bigr )}^{2}+{\bigl (}L\left(x,y+1\right)-L\left(x,y-1\right){\bigr )}^{2}}}}$

${\displaystyle \theta \left(x,y\right)=\tan ^{-1}\left({\frac {L\left(x,y+1\right)-L\left(x,y-1\right)}{L\left(x+1,y\right)-L\left(x-1,y\right)}}\right)}$

${\displaystyle \forall \left(x,y\right){\hbox{ dans un voisinage de }}\left(x_{0},y_{0}\right)}$.

Construction de l'histogramme des orientations.

Un histogramme des orientations sur le voisinage est réalisé avec 36 intervalles, couvrant chacun 10 degrés d'angle. Chaque voisin est doublement pondéré dans le calcul de l'histogramme : d'une part, par son amplitude ${\displaystyle m(x,y)}$; d'autre part, par une fenêtre circulaire gaussienne de paramètre égal à 1,5 fois le facteur d'échelle ${\displaystyle \sigma _{0}}$du point-clé. Les pics dans cet histogramme correspondent aux orientations dominantes. Toutes les orientations permettant d'atteindre au moins 80 % de la valeur maximale sont prises en considération, ce qui provoque si nécessaire la création de points-clés supplémentaires ne différant que par leur orientation principale[14].

À l'issue de cette étape, un point-clé est donc défini par quatre paramètres ${\displaystyle (x,y,\sigma ,\theta )}$. Il est à noter qu'il est parfaitement possible qu'il y ait sur une même image plusieurs points-clés qui ne différent que par un seul de ces quatre paramètres (le facteur d'échelle ou l'orientation, par exemple).

Une fois les points-clés, associés à des facteurs d'échelles et à des orientations, détectés et leur invariance aux changements d'échelles et aux rotations assurée, arrive l'étape de calcul des vecteurs descripteurs, traduisant numériquement chacun de ces points-clés. À cette occasion, des traitements supplémentaires vont permettre d'assurer un surcroît de pouvoir discriminant en rendant les descripteurs invariants à d'autres transformations telles que la luminosité, le changement de point de vue 3D, etc. Cette étape est réalisée sur l'image lissée avec le paramètre de facteur d'échelle le plus proche de celui du point-clé considéré[27].

Construction d'un descripteur SIFT.

Autour de ce point, on commence par modifier le système de coordonnées local pour garantir l'invariance à la rotation, en utilisant une rotation d'angle égale à l'orientation du point-clé, mais de sens opposé. On considère ensuite, toujours autour du point-clé, une région de 16 × 16 pixels, subdivisée en 4 × 4 zones de 4 × 4 pixels chacune. Sur chaque zone est calculé un histogramme des orientations comportant 8 intervalles. En chaque point de la zone, l'orientation et l'amplitude du gradient sont calculés comme précédemment. L'orientation détermine l'intervalle à incrémenter dans l'histogramme, ce qui se fait avec une double pondération – par l'amplitude et par une fenêtre gaussienne centrée sur le point clé, de paramètre égal à 1,5 fois le facteur d'échelle du point-clé[28].

Ensuite, les 16 histogrammes à 8 intervalles chacun sont concaténés et normalisés. Dans le but de diminuer la sensibilité du descripteur aux changements de luminosité, les valeurs sont plafonnées à 0,2 et l'histogramme est de nouveau normalisé, pour finalement fournir le descripteur SIFT du point-clé, de dimension 128[29].

Cette dimension peut paraître bien élevée, mais la plupart des descripteurs de dimension inférieure proposés dans la littérature présentent de moins bonnes performances dans les tâches de mise en correspondance[29] pour un gain en coût de calculs bien modéré, en particulier quand la technique Best-Bin-First (BBF) est utilisée pour trouver le plus proche voisin. Par ailleurs, des descripteurs de plus grande dimension permettraient probablement d'améliorer les résultats, mais les gains escomptés seraient dans les faits assez limités, alors qu'à l'inverse augmenterait sensiblement le risque de sensibilité à la distorsion ou à l'occultation. Il a également été démontré que la précision de recherche de correspondance de points dépasse 50 % dans les cas de changement de point de vue supérieur à 50 degrés, ce qui permet d'affirmer que les descripteurs SIFT sont invariants aux transformations affines modérées. Le pouvoir discriminant des descripteurs SIFT a pour sa part été évalué sur différentes tailles de bases de données de points-clés ; il en ressort que la précision de mise en correspondance est très marginalement affectée par l'augmentation de la taille de la base de données, ce qui constitue une bonne confirmation du pouvoir discriminant des descripteurs SIFT[30].

L’indexation est l’opération de stockage des descripteurs SIFT des images de référence, d'une manière qui facilite l’identification des descripteurs correspondants de l'image question. Lowe utilise un arbre kd pour indexer les descripteurs puis une méthode de recherche dans cet arbre modifiée par rapport à l'approche classique, appelée Best bin first[32]. Cette dernière est capable de trouver les plus proches voisins d'un descripteur question avec une bonne probabilité de façon très économe en temps de calcul. Cet algorithme se fonde sur deux astuces. Tout d'abord, le nombre de boîtes (feuilles de l'arbre kd) à explorer pour trouver le plus proche voisin d'un descripteur question donné est limité à une valeur maximale fixée, par exemple à 200. Ensuite, les nœuds de l'arbre kd sont explorés dans l'ordre de leur distance au descripteur question, grâce à l'utilisation d'une file de priorité basée sur un tas binaire. Par distance d'un nœud à un descripteur, on entend distance euclidienne de la boîte englobante des feuilles sous-jacentes à ce descripteur. Dans la plupart des cas, ce procédé fournit la meilleure correspondance, et, dans les cas restants, un descripteur très proche de celle-ci[33].

De façon à déconsidérer les descripteurs faiblement discriminants (parce qu'ils sont trop souvent présents dans la base de référence, comme par exemple ceux qui sont extraits de motifs d'arrière-plan souvent répétés dans les images), Lowe recherche à la fois le plus proche voisin et le second plus proche voisin de chaque descripteur question. Lorsque le rapport des distances est supérieur à 0,8, la correspondance est éliminée, car considérée comme ambiguës (« bruit »). Par ce critère, Lowe parvient à éliminer 90 % des fausses correspondances en perdant moins de 5 % de correspondances correctes[34].

On appelle pose d'un objet le point de vue sous lequel il est photographié, c'est-à-dire sa position dans l'espace par rapport à un repère absolu. En général, la base des images de référence contient différentes poses d'objets identiques. Chaque correspondance individuelle entre points-clés obtenue à l'étape précédente constitue une hypothèse quant à la pose de l'objet sur l'image question par rapport à l'image de référence concernée. Il s'agit donc maintenant de grouper les hypothèses cohérentes entre elles de façon à mettre en correspondance les objets des images et non plus seulement des points isolés. La transformée de Hough est utilisée pour cela. Elle identifie des groupes de correspondances, que l'on appelle clusters, par un système de vote[34].

Alors qu'un objet rigide possède en général six degrés de liberté dans l'espace (trois rotations, trois translations), une correspondance de points-clés entre deux images ne permet de relier que quatre paramètres (deux paramètres de position, l'angle et l'échelle) et constitue donc une approximation parmi toutes les poses possibles. Le sous-espace des poses ainsi paramétré est segmenté en boîtes de façon assez grossière : Lowe utilise des intervalles de 30 degrés pour l’orientation, un facteur de 2 pour l’échelle et 0,25 fois la dimension maximale de l’image de référence concernée (compte tenu du rapport d'échelles) pour la position[2]. Chaque correspondance vote pour la boîte associée. Les correspondances concernant les facteurs d'échelles les plus élevés, considérées comme plus pertinentes, se voient attribuer un poids double de celles concernant les facteurs les plus bas. En outre, pour éviter les effets de bord lors de l’assignation des boîtes, chaque correspondance vote pour les 2 plus proches intervalles dans chaque dimension, c'est-à-dire qu'elle vote 16 fois[34].

Lors de l'implémentation, Lowe recommande l'utilisation d'une table de hachage pour éviter de représenter toutes les boîtes possibles en mémoire dont seulement un petit nombre risque d'être non vide[34].

Lorsque plusieurs correspondances votent pour une même boîte, c'est-à-dire pour la même pose d’un objet, la probabilité que la correspondance soit correcte est largement supérieure à ce que pourrait donner une correspondance isolée. Ainsi, les boîtes contenant au moins trois entrées sont considérées comme des clusters fiables, et retenus pour la suite de l'analyse[34].

Les clusters obtenus sont soumis à une procédure de vérification par l’application de la méthode des moindres carrés aux paramètres de la transformation affine reliant le modèle (image de référence) à l’image question[35]. La transformation affine d’un point modèle ${\displaystyle [xy]^{\rm {T}}}$ en un point image ${\displaystyle [uv]^{\rm {T}}}$ peut s’écrire ainsi :

${\displaystyle {\begin{bmatrix}u\\v\end{bmatrix}}={\begin{bmatrix}m_{1}&m_{2}\\m_{3}&m_{4}\end{bmatrix}}{\begin{bmatrix}x\\y\end{bmatrix}}+{\begin{bmatrix}t_{x}\\t_{y}\end{bmatrix}}}$,

où ${\displaystyle [t_{x}t_{y}]^{\rm {T}}}$ est la translation du modèle, et où les paramètres ${\displaystyle m_{1}}$, ${\displaystyle m_{2}}$, ${\displaystyle m_{3}}$ et ${\displaystyle m_{4}}$ modélisent la transformation vectorielle (qui peut être une rotation à l'origine, une similitude, une distorsion, etc.) Pour obtenir les paramètres de la transformation, l’équation ci-dessus est réécrite de manière à regrouper les inconnues dans un vecteur-colonne :

${\displaystyle {\begin{bmatrix}x&y&0&0&1&0\\0&0&x&y&0&1\\\vdots &\vdots &\vdots &\vdots &\vdots &\vdots \end{bmatrix}}{\begin{bmatrix}m_{1}\\m_{2}\\m_{3}\\m_{4}\\t_{x}\\t_{y}\end{bmatrix}}={\begin{bmatrix}u\\v\\\vdots \end{bmatrix}}}$

Cette équation représente une seule correspondance. Pour obtenir les autres correspondances, il suffit de rajouter pour chacune d’elles deux lignes à la matrice et deux coefficients au second membre. Trois correspondances au minimum sont requises pour espérer une solution. Le système linéaire complet s’écrit alors :

${\displaystyle A\mathbf {x} \approx \mathbf {b} }$

où ${\displaystyle A}$ est une matrice ${\displaystyle m\times n}$ connue (vérifiant généralement ${\displaystyle m>n}$), ${\displaystyle \mathbf {x} }$ un vecteur inconnu de paramètres de dimension ${\displaystyle n}$ et enfin ${\displaystyle b}$ un vecteur connu de mesures de dimension ${\displaystyle m}$.

Ce système n'a en général pas de solution exacte puisqu'il est sur-dimensionné ; mais ce qui nous intéresse est qu'il est possible d'en trouver une pseudo-solution ${\displaystyle {\hat {\mathbf {x} }}}$ au sens des moindres carrés, c'est-à-dire un vecteur qui minimise l'erreur ${\displaystyle \|b-A\mathbf {x} \|_{2}}$, et qui est aussi solution de l’« équation normale » :

${\displaystyle A^{\rm {T}}\!A{\hat {\mathbf {x} }}=A^{\rm {T}}\mathbf {b} }$

La solution du système d’équations linéaires, qui s'exprime grâce à la matrice ${\displaystyle (A^{T}A)^{-1}A^{T}}$, dite pseudo-inverse de Moore-Penrose de ${\displaystyle A}$, est donnée par :

${\displaystyle {\hat {\mathbf {x} }}=(A^{\rm {T}}\!A)^{-1}A^{\rm {T}}\mathbf {b} }$

Elle minimise la somme des carrés des distances entre les positions des points-clés calculées à partir de la transformée des positions du modèle, et les positions correspondantes sur l'image cible[35].

Les données aberrantes peuvent ensuite être écartées en vérifiant la concordance de chaque correspondance avec la solution des moindres carrés. Sont éliminées les correspondances qui se situent au-delà de la moitié de l’intervalle d’erreur utilisé pour la discrétisation de l'espace des poses dans la transformée de Hough. Une nouvelle solution par la méthode des moindres carrés est calculée à partir des points restants, et le processus est itéré plusieurs fois. Il est également possible grâce à la transformation estimée par la méthode des moindres carrés de récupérer des correspondances qui avaient été manquées précédemment. À la fin du processus, s’il reste moins de 3 points après suppression des points aberrants, alors la correspondance est dite infructueuse et rejetée[36].

La décision finale d’admission ou de rejet d’une mise en correspondance d'objets (hypothèse) se fait sur la base d’un modèle probabiliste[37]. Cette méthode détermine en premier lieu le nombre attendu de fausses correspondances, connaissant la taille estimée du modèle, le nombre de points-clés dans la région et la précision de la correspondance. Une analyse par inférence bayésienne donne ensuite la probabilité que l’objet trouvé sur l'image de référence soit effectivement présent dans l'image question à partir du nombre de vraies correspondances trouvées. Une hypothèse est acceptée si cette probabilité est supérieure à 0,98. À l'exception d'images présentant de grands écarts de luminosité ou des objets ayant subi des transformations sévères ou non rigides, la détection d’objet au moyen de la méthode SIFT parvient ainsi à d'excellents résultats[36].

Le but de cette application est de fournir une solution robuste et fiable au problème de localisation de robots en environnement inconnu[42]. Un système de stéréoscopie trinoculaire est utilisé pour estimer les positions 3D des points-clés déterminés. Un point-clé n'est pris en compte que s'il apparaît simultanément sur les trois images du système trinoculaire, et à condition que les disparités entre ces images ne soient pas handicapantes, afin de générer le moins possible de données aberrantes[43]. En mouvement, le robot se localise en comparant les caractéristiques vues avec celles de la carte 3D qu'il a en mémoire ; il enrichit au fur et à mesure cette carte de nouvelles caractéristiques et met à contribution un filtre de Kalman pour mettre à jour leurs positions tridimensionnelles[43].

Exemple de détection de zones de recouvrement pour l'assemblage d'un panorama.

La mise en correspondance de points d'intérêt par la méthode SIFT peut être utilisée comme première étape d'un processus d'assemblage de photos entièrement automatisé. Cette application consiste à construire une image panoramique unique à partir de prises de vues successives d'un même sujet (souvent un paysage) décalées les unes des autres par un déplacement dans l'espace. La technique proposée par Brown et Lowe en 2003[44] a l'avantage de fonctionner sur une collection d'images, sans qu'aucune connaissance a priori ne soit nécessaire sur l'endroit précis de la prise de vue de chacune de ces images, ni même leur ordre ; elle peut aussi exclure de l'assemblage des images qui n'auraient rien à voir avec un panorama donné et même reconstituer en même temps plusieurs panoramas indépendants.

L'idée de l'application est la suivante[44]. Les descripteurs SIFT sont extraits de chacune des images à étudier et mis en correspondance les uns avec les autres (recherche des ${\displaystyle k}$ plus proches voisins comme dans la méthode SIFT générale). On construit ensuite un graphe dont les sommets sont les différentes images et l'on ajoute des arêtes entre les images qui ont le plus de points-clés en correspondance. Cela signifie qu'elles ont potentiellement des éléments du décor en commun. Pour en être sûr, on essaie de déterminer la transformation géométrique permettant de passer de l'une à l'autre, ou homographie, en utilisant un RANSAC entre les points. En cas de succès, la paire d'images est soumise à une vérification supplémentaire basée sur un modèle probabiliste et destinée à s'assurer que les correspondances ne sont pas dues au hasard. Seules sont conservées dans le graphe les arêtes qui passent le test. Les composantes connexes correspondent alors à autant de panoramas indépendants, qui sont assemblés séparément. Pour cela, une technique dite d'« ajustement de faisceaux » (bundle adjustment) est utilisée pour déterminer les paramètres objectifs de la caméra lors de la prise de vue de chaque image, par rapport au panorama global. Une fois que cet ajustement est fait, il est théoriquement possible d'obtenir la valeur de chacun des pixels du panorama global à partir des images de départ. Pour la construction finale, on applique une pondération et un lissage liés à la nécessité d'harmoniser l'exposition des images de départ, de telle sorte que les grandes étendues uniformes (cieux, etc.) ne présentent pas trop de variations dans leur luminosité tout en s'assurant que les détails ne seront pas perdus. Cette technique sophistiquée s'appelle assemblage multi-bande (multi band blending).

La technique a donné naissance au logiciel Autostitch[45].

Cette problématique consiste à déterminer la position exacte d'une caméra à partir des images qu'elle acquiert, simplement en analysant l'orientation et la position d'un objet précis apparaissant dans son champ de vision. Les applications en sont diverses ; la plus populaire étant sans doute la réalité augmentée, qui consiste à intégrer de nouveaux objets au sein d'une scène filmée, par exemple une bouteille sur une table dès que ladite table apparaît dans le champ de la caméra, et cela si possible en temps réel.

Une façon de traiter cette application a été proposée par Gordon et Lowe en 2006[46]. Elle comprend une phase d'apprentissage qui permet d'établir une modélisation 3D de l'objet témoin à partir de l'analyse de différentes prises de vues 2D de celui-ci. Les descripteurs SIFT sont utilisés pour mettre en relation les points-clés entre différentes images et construire un modèle 3D de l'objet (mise en correspondance dite « 2D-to-3D »). Une fois cette phase effectuée, on extrait de chaque image filmée les descripteurs SIFT et on les met en correspondance avec ceux des images de référence, de manière à obtenir les correspondances « 2D-to-3D » de l'image filmée. La position de la caméra est alors déterminée par une technique de RANSAC améliorée (Levenberg-Marquardt) qui minimise l'erreur de projection.

Des extensions au descripteur SIFT aux données spatio-temporelles de dimension 2+1, dans le contexte de reconnaissance de mouvements humains dans des séquences vidéo, ont été proposées dans la littérature scientifique[47] - [48] - [49]. Le calcul d'histogrammes dépendants de positions locales est étendu, dans l'algorithme SIFT, de 2 à 3 dimensions pour adapter les caractéristiques SIFT au domaine spatio-temporel. Pour réaliser une reconnaissance de mouvements humains dans une séquence vidéo, un échantillonnage de vidéos d'apprentissage est effectué soit à des points d'intérêt spatio-temporel, soit à des positions, instants et échelles aléatoirement choisis. Les régions spatio-temporelles autour de ces points d'intérêt sont décrites au moyen du descripteur SIFT 3D. Ces descripteurs sont enfin rangés en clusters formant un modèle de sac de mots spatio-temporel. Les descripteurs SIFT 3D extraits des vidéos de test sont enfin comparés à ces « mots ».

Les auteurs confirment l'obtention de meilleurs résultats grâce à cette approche à base de descripteur 3D que par les autres approches utilisant de simples descripteurs SIFT 2D ou les magnitudes de gradients[50].

La morphométrie basée sur des descripteurs d'image (FBM, feature based morphometry), est une technique d'analyse et de classification d'images 3D du cerveau humain obtenus par résonance magnétique[51]. Grâce à la technique SIFT, l'image est vue comme un assemblage géométrique de structures indépendantes (zones d'intérêt). En utilisant un modèle probabiliste assez fin et en se basant sur l'observation de différentes classes de sujets dûment étiquetés, par exemple des sujets sains d'un côté et des sujets atteints de la maladie d'Alzheimer de l'autre, la technique FBM parvient à regrouper les structures similaires d'une image à l'autre et à les classifier selon l’étiquetage. Un système ainsi entraîné devient capable d'étiqueter automatiquement une image étrangère : sur un ensemble de test constitué d'environ 200 images IRM du cerveau humain, la détection des cas sains et des cas atteints de la maladie d'Alzheimer est correcte dans 80 % des cas, précisent les auteurs.

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Scale-invariant feature transform » (voir la liste des auteurs).

• Autostitch
• Détection de zones d'intérêt
• Speeded Up Robust Features (SURF)

• (en) YuanBin Wang, Zhang Bin et Yu Ge, « The Invariant Relations of 3D to 2D Projection of Point Sets », Journal of Pattern Recognition Research, vol. 3, n^o 1,‎ 14 juin 2008, p. 14-23 (lire en ligne)
• (en) David G. Lowe, « Distinctive Image Features from Scale-Invariant Keypoints », International Journal of Computer Vision, vol. 60, n^o 2,‎ 2004, p. 91-110 (lire en ligne)
• (en) Krystian Mikolajczyk et Cordelia Schmid, « A performance evaluation of local descriptors », IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 27, n^o 10,‎ 2005, p. 1615-1630 (lire en ligne)
• (en) Svetlana Lazebnik, Cordelia Schmid et Jean Ponce, « Semi-Local Affine Parts for Object Recognition », Proceedings of the British Machine Vision Conference, vol. 2,‎ septembre 2004, p. 959-968 (lire en ligne)

• (en) Rob Hess, « SIFT Library », 2010 (consulté le 27 septembre 2010).
• (en) David G. Lowe, « Demo Software: SIFT Keypoint Detector », 2005 (consulté le 27 septembre 2010).
• (en) Yan Ke et Rahul Sukthankar, « PCA-SIFT: A More Distinctive Representation for Local Image Descriptors », 2004 (consulté le 27 septembre 2010).
• (en) Jean-Michel Morel et Guoshen Yu, « ASIFT: A New Framework for Fully Affine Invariant Comparison », 2009 (ISSN 2105-1232, consulté le 27 septembre 2010).
• (en) Andrea Vedaldi et Brian Fulkerson, « VLFeat.org », 2005 (consulté le 27 septembre 2010).
• (en) Wan-Lei Zhao, « Lip-vireo », 2010 (consulté le 27 septembre 2010).
• Depuis sa version 2.2 (décembre 2010), OpenCV intègre une implémentation de SIFT.