Le hachage géométrique est une méthode utilisée en vision par ordinateur et en reconnaissance de formes pour identifier des objets dans une scène en comparant leurs caractéristiques géométriques à une base de données précalculée. Il a été développé à la fin des années 1980 par Yehezkel Lamdan et Haim J. Wolfson, et il est devenu influent dans le domaine de la reconnaissance d'objets basée sur des modèles. Cette technique est remarquable pour sa capacité à gérer les occlusions partielles et son invariance aux transformations géométriques courantes, ce qui en fait une alternative robuste aux approches antérieures de correspondance de modèles.
L'idée centrale du hachage géométrique est de représenter chaque modèle d'objet comme un ensemble de points caractéristiques (tels que des coins, des bords ou des points d'intérêt), puis d'encoder leurs relations spatiales dans une table de hachage. Lors de la reconnaissance, une scène requête est traitée en extrayant ses propres points caractéristiques, et la table de hachage est utilisée pour voter pour des modèles candidats. Ce processus de vote permet au système d'émettre rapidement des hypothèses sur le modèle potentiellement présent, même lorsque seule une sous-partie des caractéristiques de l'objet est visible.
Développement historique
Le hachage géométrique est issu de recherches en géométrie computationnelle et en vision par ordinateur durant les années 1980. Lamdan et Wolfson ont introduit le concept dans un article de 1988 intitulé « Geometric Hashing: A General and Efficient Model-Based Recognition Scheme », présenté à la conférence internationale IEEE sur la vision par ordinateur. Cette approche s'appuyait sur des travaux antérieurs en hachage et en correspondance géométrique, mais elle introduisait une nouvelle manière d'indexer les caractéristiques des modèles, rendant la reconnaissance à la fois rapide et tolérante au bruit.
La technique a gagné en popularité dans les années 1990, notamment dans des applications comme l'inspection de pièces industrielles, la robotique et l'imagerie médicale. Elle a également été adaptée pour une utilisation en biologie moléculaire pour la comparaison de structures protéiques, où l'arrangement géométrique des atomes ou des résidus pouvait être mis en correspondance entre différentes molécules. Au début des années 2020, le hachage géométrique reste un concept fondamental en vision par ordinateur, bien qu'il ait été largement supplanté par des méthodes basées sur l'apprentissage profond dans de nombreuses applications pratiques.
Aperçu de l'algorithme
L'algorithme de hachage géométrique fonctionne en deux phases : le prétraitement et la reconnaissance. Dans la phase de prétraitement, pour chaque modèle de la base de données, un ensemble de points caractéristiques est extrait. Pour chaque paire ordonnée de points (ou une base, typiquement deux points définissant un repère de coordonnées), l'algorithme calcule les coordonnées de tous les autres points par rapport à cette base. Ces coordonnées relatives sont ensuite stockées dans une table de hachage, avec la base et l'identifiant du modèle comme valeur associée.
Lors de la reconnaissance, les points caractéristiques de la scène sont extraits, et l'algorithme sélectionne une paire aléatoire de points comme base candidate. Il calcule les coordonnées relatives des points restants de la scène en utilisant cette base et les recherche dans la table de hachage. Chaque correspondance incrémente un vote pour le modèle et la base correspondants. Après avoir traité toutes les bases possibles (ou un sous-ensemble échantillonné), le modèle avec le nombre de votes le plus élevé est sélectionné comme meilleure correspondance. L'algorithme vérifie ensuite la correspondance en alignant le modèle sur la scène et en vérifiant la cohérence.
Cette approche est invariante à la translation, à la rotation et à la mise à l'échelle uniforme, car les coordonnées relatives sont calculées dans un repère normalisé. Elle gère également les occlusions partielles, car seule une sous-partie des caractéristiques du modèle doit être présente dans la scène pour qu'un nombre suffisant de votes s'accumule.
Applications en vision par ordinateur
Le hachage géométrique a été appliqué dans plusieurs domaines où une reconnaissance d'objets robuste est requise. Dans l'automatisation industrielle, il était utilisé pour localiser des pièces sur un tapis roulant, où les pièces pouvaient être tournées ou mises à l'échelle par rapport à une référence. En robotique, il aidait les robots à identifier et saisir des objets dans des environnements encombrés. La tolérance de la méthode aux occlusions la rendait adaptée à des tâches comme la reconnaissance d'objets partiellement cachés dans un tas.
En imagerie médicale, le hachage géométrique était utilisé pour aligner des structures anatomiques dans des images radiographiques ou IRM, facilitant des tâches comme le recalage d'images et la planification chirurgicale. En biologie moléculaire, il facilitait la comparaison de structures 3D de protéines, où l'objectif était de trouver des motifs de repliement similaires malgré des variations dans les séquences d'acides aminés. Ces applications tiraient parti de la capacité de la technique à faire correspondre des configurations géométriques sans nécessiter de correspondance explicite entre les points individuels.
Comparaison avec les approches modernes
Avec l'essor de l'apprentissage automatique et de l'apprentissage profond dans les années 2010, le hachage géométrique est devenu moins prédominant dans la vision par ordinateur grand public. Les méthodes basées sur des architectures de réseaux de neurones, en particulier les réseaux de neurones convolutifs et les modèles transformers, ont atteint une précision supérieure sur des tâches de reconnaissance à grande échelle. Ces approches modernes apprennent des représentations de caractéristiques directement à partir des données, tandis que le hachage géométrique repose sur des caractéristiques géométriques conçues manuellement et un indexage spatial explicite.
Cependant, le hachage géométrique offre encore des avantages dans certains scénarios. Il ne nécessite pas de données d'entraînement étendues, ce qui le rend utile lorsque seuls quelques exemples d'un objet sont disponibles. Il fournit également des résultats de correspondance interprétables, car le processus de vote révèle quelles caractéristiques ont contribué à la reconnaissance. En revanche, les modèles d'apprentissage profond agissent souvent comme des boîtes noires. Au milieu des années 2020, des approches hybrides combinant le hachage géométrique avec l'apprentissage automatique pour l'extraction de caractéristiques ont été explorées, mais elles restent marginales.
Limites et extensions
Une limite du hachage géométrique est sa sensibilité à la qualité de l'extraction des points caractéristiques. Si le détecteur de caractéristiques produit des points bruités ou incohérents, les recherches dans la table de hachage deviennent peu fiables. L'algorithme s'adapte également mal au nombre de modèles, car la table de hachage peut devenir volumineuse et gourmande en mémoire. Pour remédier à cela, des extensions ont été proposées, comme l'utilisation de bases aléatoires ou de hachage hiérarchique pour réduire l'espace de recherche.
Une autre extension implique l'utilisation de transformations affines ou projectives au lieu de simples transformations de similarité, ce qui élargit la gamme de scénarios applicables. Certaines variantes intègrent des informations de couleur ou de texture en plus des caractéristiques géométriques pour améliorer la discrimination. Malgré ces améliorations, le compromis fondamental entre vitesse et robustesse reste un défi, et la technique est souvent utilisée en combinaison avec d'autres méthodes, comme l'entraînement basé sur la augmentation de données dans les systèmes modernes.
Héritage et influence
Le hachage géométrique a influencé les développements ultérieurs en vision par ordinateur, notamment l'utilisation du hachage dans la recherche d'images à grande échelle et la conception de descripteurs de caractéristiques locales comme SIFT (Scale-Invariant Feature Transform). L'idée d'indexer des invariants géométriques dans une table de hachage se retrouve dans de nombreux algorithmes ultérieurs. Il a également contribué au domaine plus large de l'intelligence artificielle en démontrant comment le raisonnement géométrique pouvait être implémenté efficacement dans des systèmes computationnels.
Aujourd'hui, le hachage géométrique est enseigné dans les cours de vision par ordinateur comme un exemple classique de reconnaissance basée sur des modèles. Ses principes restent pertinents dans des applications spécialisées, comme la reconnaissance d'objets 3D dans des nuages de points et la correspondance de formes en conception assistée par ordinateur. Bien qu'il ne domine plus le domaine, ses contributions conceptuelles demeurent une partie importante de l'histoire de l'intelligence artificielle et de la reconnaissance de formes.