thumb|right|alt=Exemple de mise en correspondance de deux images par la méthode SIFT : des lignes vertes relient entre eux les descripteurs communs à un tableau et une photo de ce même tableau, de moindre qualité, ayant subi des transformations. |Exemple de résultat de la comparaison de deux images (le tableau original et une photo de l'écran de sa page Wikimedia Commons) par la méthode SIFT.

La (SIFT), que l'on peut traduire par « transformation de caractéristiques visuelles invariante à l'échelle », est un algorithme utilisé dans le domaine de la vision par ordinateur pour détecter et identifier les éléments similaires entre différentes images numériques (éléments de paysages, objets, personnes, etc.). Il a été développé en 1999 par le chercheur David Lowe.

L'étape fondamentale de la méthode proposée par Lowe consiste à calculer ce que l'on appelle les « descripteurs SIFT » des images à étudier. Il s'agit d'informations numériques dérivées de l'analyse locale d'une image et qui caractérisent le contenu visuel de cette image de la façon la plus indépendante possible de l'échelle (« zoom » et résolution du capteur), du cadrage, de l'angle d'observation et de l'exposition (luminosité). Ainsi, deux photographies d'un même objet auront toutes les chances d'avoir des descripteurs SIFT similaires, et ceci d'autant plus si les instants de prise de vue et les angles de vue sont proches. D'un autre côté, deux photographies de sujets très différents produiront selon toute vraisemblance des descripteurs SIFT très différents eux aussi (pouvoir discriminant). Cette robustesse, vérifiée dans la pratique, est une exigence fondamentale de la plupart des applications et explique en grande partie la popularité de la méthode SIFT.

Les applications de la méthode sont nombreuses et ne cessent de s'étendre ; elles couvrent au début du des domaines tels que la détection d'objet, la cartographie et la navigation, l'assemblage de photos, la modélisation tridimensionnelle, la recherche d'image par le contenu, le ou le .

Cet algorithme était protégé aux États-Unis jusqu'en 2020 par un brevet détenu par l’université de la Colombie-Britannique.

Origines de la méthode

thumb|alt=Exemple de caractéristiques SIFT sur une image. Sur cette image, des flèches représentent ces caractéristiques : leurs queues sont positionnées aux centre des points-clés correspondants, leurs normes sont proportionnelles aux facteurs d'échelle des caractéristiques et les directions correspondent aux directions principales associées.|Exemple de caractéristiques SIFT. Chaque point-clé est représenté par une flèche dont la direction correspond à la direction principale associée et la norme au facteur d'échelle (illustration : Fantasia, par Eugène Delacroix). C'est en 1999 que le chercheur canadien David G. Lowe, professeur à l’université de la Colombie-Britannique, présente lors de la conférence ICCV. une nouvelle méthode d'extraction de caractéristiques et de détection d'objets dans des images en niveaux de gris. Le nom de (SIFT) a été choisi car la méthode transforme les données d'une image en coordonnées invariantes à l'échelle et rapportées à des caractéristiques locales. Des améliorations et une description précise de la méthode sont proposées par Lowe en 2004 dans la revue International Journal of Computer Vision.. L’université de la Colombie-Britannique a demandé et obtenu la protection par brevet de cet algorithme aux États-Unis., « Method and apparatus for identifying scale invariant features in an image and use of same for locating an object in an image »..

L'idée d'utiliser des points d'intérêt locaux remonte aux travaux de Hans Moravec en 1981 sur la recherche de correspondance entre images stéréoscopiquesLowe (2004), .. et aux améliorations apportées en 1988 par Harris et Stephens.. À la suite de quoi, différents types de caractéristiques sont proposés, tels que des segments de lignes., des groupements d'arêtes.. ou de zones.. En 1992, l'intérêt de ce type de détecteur est confirmé par les travaux de Harris. et le descripteur de coins qu'il propose, améliorant la plupart des défauts du détecteur de Moravec, va connaître un important succès. Il faut cependant attendre 1997 et le travail précurseur de Cordelia Schmid et Roger Mohr pour établir l'importance, dans le domaine de la vision, des caractéristiques locales invariantes appliquées au problème général de détection et de recherche de correspondance.. Si le descripteur qu'ils développent (et qui s'appuie sur le détecteur de coins de Harris) apporte l'invariance à la rotation, il reste cependant sensible aux changements d'échelle, d'angle d'observation et d'expositionLowe (2004), .. Lowe comblera grandement ces défauts avec son descripteur SIFTLowe (2004), ..

Généralités

La méthode proposée par Lowe comprend deux parties (chacune ayant fait l'objet de recherches plus ou moins indépendantes par la suite) : un algorithme de détection de caractéristiques et de calcul de descripteurs ; un algorithme de mise en correspondance proprement dit. De ces deux aspects, le premier est sans doute celui qui a le plus assuré la popularité de la méthode., à tel point que le sigle SIFT fait plus souvent référence aux « descripteurs SIFT » qu'à la méthodologie globale. Il s'agit tout d'abord de détecter sur l'image des zones circulaires « intéressantes », centrées autour d'un point-clé et de rayon déterminé appelé facteur d'échelle. Celles-ci sont caractérisées par leur unité visuelle et correspondent en général à des éléments distincts sur l'image. Sur chacune d'elles, on détermine une orientation intrinsèque qui sert de base à la construction d'un histogramme des orientations locales des contours, habilement pondéré, seuillé et normalisé pour plus de stabilité. C'est cet histogramme qui sous la forme d'un vecteur à 128 dimensions (ou valeurs) constitue le descripteur SIFT du point-clé, et l'ensemble des descripteurs d'une image établissent ainsi une véritable signature numérique du contenu de celle-ci.

Ces descripteurs présentent l'avantage d'être invariants à l'orientation et à la résolution de l'image, et peu sensibles à son exposition, à sa netteté ainsi qu'au point de vue 3D. Ils possèdent ainsi des propriétés similaires à celles des neurones du cortex visuel primaire qui permettent la détection d'objet en intégrant les composantes de base comme les formes, la couleur ainsi que le mouvement.. Par exemple, ils décriront de façon très semblable les détails d'une image originale et ceux d'une image retouchée par l'application d'une rotation, d'un recadrage ou d'un lissage, par une correction de l'exposition, par occultation partielle ou encore par l'insertion dans une image plus grande.

Une fois le calcul des descripteurs effectué, l'algorithme de mise en correspondance recherche les zones de l'image qui contiennent des éléments visuellement similaires à ceux d'une bibliothèque d'images de référence, c'est-à-dire des descripteurs numériquement proches. Ceci ne peut fonctionner que parce que les descripteurs SIFT sont à la fois robustes (aux principales transformations affines et aux changements d'exposition ou de perspective) et discriminants (deux objets différents ont une grande probabilité d'avoir des descripteurs différents).

Détection des points-clés et calcul du descripteur SIFT

La première étape de l'algorithme est la détection des points d'intérêt, dits points-clés. Un point-clé est défini d'une part par ses coordonnées sur l'image ( et ) et d'autre part par son facteur d'échelle caractéristique (). En toute rigueur, il s'agit d'une zone d'intérêt circulaire, le rayon de la zone étant proportionnel au facteur d'échelle. Il s'ensuit une étape de reconvergence et de filtrage qui permet d'améliorer la précision sur la localisation des points-clés et d'en éliminer un certain nombre jugés non pertinents. Chaque point-clé restant est ensuite associé à une orientation intrinsèque, c'est-à-dire ne dépendant que du contenu local de l'image autour du point clé, au facteur d'échelle considéré. Elle permet d'assurer l'invariance de la méthode à la rotation et est utilisée comme référence dans le calcul du descripteur, qui constitue la dernière étape de ce processusLowe (2004), ..

Détection d’extrema dans l’espace des échelles

La détection s'effectue dans un espace discret que l'on appelle espace des échelles () qui comporte trois dimensions : les coordonnées cartésiennes et et le facteur d'échelle . On appelle gradient de facteur d'échelle (noté ) le résultat de la convolution d'une image par un filtre gaussien de paramètre , soitLowe (2004), . :

thumb|center|upright=2|alt=Illustration représentant la construction d'une pyramide de gradients|Pyramide de gradients : 3 octaves de 6 gradients. Cette convolution a pour effet de lisser l'image originale de telle sorte que les détails trop petits, c'est-à-dire de rayon inférieur à Ici comme dans la littérature scientifique en général, le facteur d'échelle – paramètre du filtre gaussien – est assimilé à une distance en pixels sur l'image, que l'on pourrait appeler rayon associé . En fait, ils sont proportionnels (), avec un facteur qui varie généralement entre 3 et 4 selon les auteurs. Il est tout simplement lié au nombre de coefficients au-delà duquel les valeurs de la gaussienne deviennent négligeables., sont estompés. Par conséquent, la détection des objets de dimension approximativement égale à se fait en étudiant l'image appelée différences de gaussiennes (en anglais , DoG) définie comme suit : , où est un paramètre fixe de l'algorithme qui dépend de la finesse de la discrétisation de l'espace des échelles voulue.

Dans cette image ne persistent plus que les objets observables dans des facteurs d'échelle qui varient entre et . De ce fait, un point-clé candidat 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 :

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 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 , avec à chaque changement d'octave une valeur qui devient égale à une quantité de la forme . 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 calculLowe (2004), ..

thumb|center|upright=2|alt=Schéma illustrant la construction d'une pyramide de différences de gaussiens (DoG) à partir de la pyramide de gradients. 3 octaves de 5 gradients sont représentées, et sous chaque octave, sont représentées les différences de gaussiennes issues de chaque paire d'images successives.|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 (détection de zones) développée par Lindeberg, qui utilise le laplacien normalisé par le facteur d'échelle. 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 pyramidaleLowe (2004), ..