Scale-Invariant Feature Transform (SIFT)

La transformation de caractéristiques invariante à l’échelle (SIFT) est un algorithme classique de vision par ordinateur qui détecte des points clés locaux distinctifs dans une image et décrit chacun d’eux à l’aide d’un vecteur de 128 nombres qui reste largement inchangé lorsque l’image est mise à l’échelle ou tournée. La mise en correspondance de ces descripteurs permet aux logiciels de relier deux photos d’une même scène prises depuis des distances et des angles différents, ce qui permet d’assembler des photos qui se chevauchent pour créer un panorama. SIFT est une forme d’extraction de caractéristiques conçue manuellement, contrairement aux cartes de caractéristiques apprises d’un réseau neuronal convolutif.

Origine et idée fondamentale#

David Lowe, de l’Université de la Colombie-Britannique, a présenté SIFT dans l’article de l’ICCV de 1999 Reconnaissance d’objets à partir de caractéristiques locales invariantes à l’échelle, puis en a donné une description complète dans « Caractéristiques distinctives des images à partir de points clés invariants à l’échelle », publié en 2004 dans l’International Journal of Computer Vision. Les caractéristiques SIFT sont invariantes à l’échelle et à la rotation, et restent robustes sur une plage importante de distorsions affines, de changements de point de vue en 3D, de bruit et de variations d’éclairage. La méthode a été brevetée, et le brevet a expiré en 2020. OpenCV a déplacé SIFT de son dépôt contrib vers la bibliothèque principale dans la version 4.4.0.

Un objet n’a pas de taille fixe sur une photo ; un détecteur doit donc rechercher des structures à toutes les échelles. SIFT construit un espace d’échelles en appliquant à plusieurs reprises un flou gaussien de plus en plus marqué et en sous-échantillonnant l’image par groupes appelés octaves.

Fonctionnement de SIFT#

L’algorithme s’exécute en quatre étapes :

1. Détection des extrémums dans l’espace d’échelles : Les différences entre les niveaux de flou voisins (différences de gaussiennes) servent d’approximation à un détecteur de blobs. Un pixel est retenu comme candidat s’il constitue un maximum ou un minimum parmi ses 26 voisins dans l’espace et à différentes échelles.
2. Localisation des points clés : Les candidats sont affinés à une précision sous-pixel. Les points à faible contraste et ceux situés le long des contours sont éliminés, car ils sont instables.
3. Attribution de l’orientation : Un histogramme des directions des gradients locaux autour de chaque point clé détermine une orientation dominante, par rapport à laquelle toutes les mesures suivantes sont effectuées. Cela confère l’invariance à la rotation.
4. Construction du descripteur : Le voisinage est divisé en une grille de 4 x 4, et chaque cellule contient un histogramme de gradients à 8 intervalles. On obtient ainsi 4 x 4 x 8 = 128 valeurs, normalisées pour réduire la sensibilité à l’éclairage.

La mise en correspondance compare les descripteurs à l’aide de la distance euclidienne. Le test du rapport de Lowe ne conserve une correspondance que si le voisin le plus proche est nettement plus proche que le deuxième voisin. Une recherche des k plus proches voisins avec k = 2 fournit les deux distances.

import cv2
from ultralytics.utils import ASSETS

# Load a sample image in grayscale and a half-size copy
img = cv2.imread(str(ASSETS / "bus.jpg"), cv2.IMREAD_GRAYSCALE)
small = cv2.resize(img, None, fx=0.5, fy=0.5)

# Detect keypoints and compute 128-dimensional descriptors
sift = cv2.SIFT_create()
kp1, des1 = sift.detectAndCompute(img, None)
kp2, des2 = sift.detectAndCompute(small, None)

# Match half-size descriptors to full-size ones, then apply Lowe's ratio test
pairs = cv2.BFMatcher().knnMatch(des2, des1, k=2)
good = [m for m, n in pairs if m.distance < 0.8 * n.distance]
print(f"{len(good)} of {len(kp2)} half-size keypoints matched at full size")

Le nombre affiché indique combien de points clés détectés à la moitié de la taille sont à nouveau reconnus dans l’image en taille réelle, ce qui illustre l’invariance à l’échelle.

Applications#

SIFT est devenu la méthode par défaut pour les caractéristiques locales dans les tâches de vision géométrique :

• Assemblage de panoramas : La méthode d’assemblage automatique de panoramas de Brown et Lowe (IJCV 2007) met en correspondance les caractéristiques SIFT entre des photos qui se chevauchent et estime une homographie pour les aligner, une étape d’alignement appelée recalage d’images.
• Reconstruction 3D : Photo Tourism (Snavely, Seitz et Szeliski, 2006) met en correspondance les caractéristiques SIFT dans des photos touristiques et utilise la géométrie épipolaire pour retrouver les poses des caméras et une structure 3D éparse.
• Localisation de robots : Se, Lowe et Little (2001) ont utilisé des repères SIFT pour la localisation et la cartographie de robots mobiles, précurseurs du SLAM visuel moderne.
• Reconnaissance d’instances : Dans son article de 2004, Lowe reconnaît un train jouet et une grenouille dans une scène encombrée et partiellement occultée à partir de seulement 3 caractéristiques mises en correspondance.

Dans le suivi d’objets d’Ultralytics YOLO, BoT-SORT compense le mouvement de la caméra entre les images, et le paramètre gmc_method: sift dans la configuration du suiveur permet d’utiliser les correspondances SIFT pour cette estimation à la place du flux optique clairsemé utilisé par défaut.

Comparaison de SIFT avec des méthodes apparentées#

SIFT met en correspondance les mêmes points physiques d’une vue à l’autre, ce qui convient à la correspondance et à la géométrie. La détection d’objets prédit plutôt la catégorie et l’emplacement des objets. La mise en correspondance de modèles fait glisser une portion d’image fixe et échoue lorsque l’échelle ou la rotation change.

SIFT est lent par rapport à ORB, un descripteur binaire présenté par Rublee et ses collègues en 2011 comme une alternative à SIFT et SURF. Il fonctionne aussi mal sur les surfaces sans texture et lors de très grands changements de point de vue, et les modèles appris l’ont largement remplacé pour la reconnaissance au niveau des catégories.

Dans les tests de Lowe de 2004, le rejet des correspondances dont le rapport des distances dépassait 0,8 a éliminé 90 % des fausses correspondances tout en écartant moins de 5 % des bonnes, sur des images présentant des changements aléatoires d’échelle et de rotation, une rotation en profondeur de 30 degrés et 2 % de bruit, mises en correspondance avec 40 000 points clés.