La transformée en caractéristiques invariantes à l'échelle (SIFT) est un algorithme de vision par ordinateur permettant de détecter, décrire et mettre en correspondance des caractéristiques locales dans des images, inventé par David Lowe en 1999. Il permet une reconnaissance d'objets robuste face aux changements d'échelle, de rotation et d'illumination, avec des applications telles que la reconnaissance d'objets, la cartographie et la navigation robotiques, l'assemblage d'images, la modélisation 3D, la reconnaissance de gestes, le suivi vidéo, l'identification individuelle de la faune et le suivi de mouvement.
SIFT extrait des points clés d'images de référence et les stocke dans une base de données. Pour reconnaître un objet dans une nouvelle image, chaque caractéristique est comparée à la base de données en utilisant la distance euclidienne des vecteurs de caractéristiques, et des grappes cohérentes de correspondances sont identifiées via une implémentation efficace de table de hachage de la transformée de Hough généralisée. Les grappes de trois caractéristiques ou plus sont vérifiées, et la probabilité de correspondances correctes est calculée. L'algorithme a été développé par Lowe sur une décennie de bricolage ; son brevet a expiré en 2020.
Aperçu
Pour tout objet dans une image, des points importants peuvent être extraits pour fournir une description de caractéristiques. Cette description, tirée d'une image d'entraînement, peut localiser l'objet dans une nouvelle image contenant d'autres objets. Les caractéristiques doivent être détectables malgré les changements d'échelle, de bruit et d'illumination, et se situent souvent sur des régions à fort contraste comme les bords. Les positions relatives entre les caractéristiques doivent rester cohérentes entre les images ; par exemple, utiliser uniquement les coins de porte fonctionne quelle que soit la position, mais les points sur le cadre échouent si la porte bouge. SIFT utilise de nombreuses caractéristiques, réduisant l'impact des variations locales sur les erreurs de correspondance.
SIFT identifie robustement les objets dans des environnements encombrés et avec occlusion partielle car son descripteur est invariant aux changements d'échelle uniforme, d'orientation et d'illumination, et partiellement invariant à la distorsion affine. Le descripteur est basé sur des mesures d'image en termes de champs récepteurs, avec des cadres de référence locaux invariants à l'échelle établis par sélection d'échelle.
Types de caractéristiques
Les caractéristiques SIFT sont locales, basées sur l'apparence aux points d'intérêt, et invariantes à l'échelle et à la rotation. Elles sont robustes aux changements d'illumination, au bruit et aux légers changements de point de vue. Elles sont hautement distinctives, faciles à extraire, et permettent une identification correcte avec une faible probabilité de fausses correspondances. La mise en correspondance avec de grandes bases de données utilise des algorithmes probabilistes comme les arbres k-d avec recherche du meilleur bin en premier en raison de la haute dimensionnalité. Aussi peu que trois caractéristiques SIFT peuvent calculer la localisation et la pose d'un objet, permettant une reconnaissance quasi en temps réel sur du matériel moderne.
Étapes
Détection de caractéristiques invariantes à l'échelle
La méthode de Lowe transforme une image en une collection de vecteurs de caractéristiques invariants à la translation, à l'échelle et à la rotation, partiellement invariants à l'illumination, et robustes à la distorsion géométrique. Ces caractéristiques ressemblent aux neurones du cortex visuel primaire qui encodent des formes de base pour la détection d'objets dans la vision des primates. Les emplacements clés sont les maxima et minima de la fonction de différence de gaussiennes dans l'espace d'échelle, appliquée à des images lissées et rééchantillonnées. Les candidats à faible contraste et les réponses de bords sont écartés, et des orientations dominantes sont assignées. Des descripteurs robustes à la distorsion affine sont obtenus en floutant et rééchantillonnant des plans d'orientation locaux autour des emplacements clés.
Mise en correspondance et indexation des caractéristiques
L'indexation stocke les clés SIFT et identifie les correspondances à partir de nouvelles images. Lowe a utilisé la recherche du meilleur bin en premier, un algorithme d'arbre k-d modifié qui trouve les voisins les plus proches avec une haute probabilité en utilisant un calcul limité, en recherchant les bins dans l'ordre de distance par rapport à la requête via une file de priorité basée sur un tas. Pour chaque point clé, le voisin le plus proche dans la base de données est trouvé par distance euclidienne minimale. Les candidats sont conservés si le rapport de la distance à la caractéristique la plus proche d'une classe différente est suffisamment grand, garantissant que les classes d'objets distinctes n'encombrent pas les correspondances. Les grappes cohérentes sont ensuite vérifiées.
Applications et impact
SIFT a été largement adopté en vision par ordinateur, influençant des domaines comme intelligence artificielle et apprentissage automatique. Sa robustesse en a fait une norme pour la reconnaissance d'objets avant que les approches d'apprentissage profond comme apprentissage profond et réseaux de neurones ne deviennent prédominantes. L'expiration de la protection par brevet de l'algorithme en 2020 a facilité une utilisation plus large dans les applications commerciales et de recherche.
Les principes de SIFT ont également inspiré des descripteurs de caractéristiques ultérieurs et ont contribué aux avancées en vision par ordinateur et en robotique, en particulier dans Waymo et autopilote Tesla pour la navigation. Sa capacité à gérer l'occlusion partielle et l'encombrement reste précieuse dans des scénarios comme l'identification de la faune et le suivi de mouvement dans la production cinématographique.
Héritage
Malgré l'essor des caractéristiques apprises à partir de modèles d'apprentissage profond, SIFT reste une technique fondamentale, souvent utilisée comme référence dans les benchmarks de mise en correspondance de caractéristiques. Sa base théorique dans la théorie de l'espace d'échelle continue d'informer la recherche en analyse d'images. Le développement de l'algorithme sur dix ans illustre le raffinement itératif en vision par ordinateur, et l'expiration de sa protection par brevet a encouragé l'innovation dans des domaines connexes.