Le détecteur de coins de Harris est un algorithme fondamental en vision par ordinateur pour identifier les points de coin dans une image. Il a été introduit par Chris Harris et Mike Stephens en 1988 dans un article intitulé « A Combined Corner and Edge Detector ». Le détecteur est conçu pour localiser les points où l'intensité de l'image présente de grandes variations dans plusieurs directions, ce qui est utile pour des tâches telles que la correspondance de caractéristiques, la reconnaissance d'objets et le suivi de mouvement. C'est une technique de base dans le domaine, antérieure à de nombreuses approches modernes de apprentissage automatique, mais encore largement utilisée dans les pipelines classiques et comme référence pour les détecteurs de caractéristiques appris.
L'algorithme fonctionne sur des images en niveaux de gris et calcule une mesure de réponse basée sur la structure locale des gradients. Pour chaque pixel, il construit une matrice de second moment (également appelée tenseur de structure) qui résume la distribution des gradients de l'image dans un petit voisinage. Les valeurs propres de cette matrice indiquent la force des changements d'intensité le long de deux directions orthogonales. Un coin est détecté lorsque les deux valeurs propres sont grandes, ce qui signifie que la région de l'image présente une variation significative dans toutes les directions. La fonction de réponse, souvent notée R, combine le déterminant et la trace de la matrice pour éviter le calcul explicite des valeurs propres, en utilisant un paramètre ajustable k (généralement entre 0,04 et 0,06).
Formulation mathématique
Le détecteur de Harris définit la matrice de second moment M pour un pixel (x, y) comme une somme sur une fenêtre W, généralement un voisinage pondéré par une gaussienne :
M = somme sur W de [Ix^2, IxIy ; IxIy, Iy^2]
où Ix et Iy sont les gradients de l'image dans les directions x et y, calculés à l'aide d'opérateurs de Sobel ou similaires. La réponse R est donnée par :
R = det(M) - k * trace(M)^2
où det(M) = λ1 * λ2 et trace(M) = λ1 + λ2, avec λ1 et λ2 les valeurs propres. Un pixel est classé comme coin si R dépasse un seuil, et une suppression non maximale est appliquée pour ne conserver que les maxima locaux, produisant un ensemble clairsemé de points d'intérêt.
Propriétés et avantages
Le détecteur de coins de Harris est invariant à la rotation de l'image, ce qui signifie qu'un coin détecté dans une orientation sera détecté après rotation de l'image. Il est également partiellement invariant aux changements d'éclairage car il repose sur les magnitudes des gradients plutôt que sur les intensités absolues. Cependant, il n'est pas invariant à l'échelle ; un coin peut disparaître ou changer lorsque l'image est mise à l'échelle, ce qui a conduit à des développements ultérieurs comme la transformée de caractéristiques invariantes à l'échelle (SIFT) et d'autres détecteurs multi-échelles. Le détecteur est efficace en termes de calcul, ce qui le rend adapté aux applications en temps réel, surtout à l'ère précédant l'apprentissage profond.
Applications en vision par ordinateur
Les coins de Harris sont utilisés dans de nombreuses tâches classiques de vision par ordinateur. Dans la augmentation de données et l'assemblage d'images, ils servent de points clés pour la correspondance entre des images qui se chevauchent. Dans le suivi de mouvement, ils fournissent des points stables à suivre à travers les trames vidéo. Le détecteur est également un élément de base pour des descripteurs de caractéristiques plus complexes, comme le détecteur de Harris-Laplace, qui ajoute la sélection d'échelle. En robotique et en conduite autonome, les coins de Harris aident à l'odométrie visuelle et à la localisation et cartographie simultanées (SLAM), bien que les systèmes modernes utilisent souvent des caractéristiques apprises à partir de modèles de réseaux de neurones.
Relation avec les approches modernes
Avec l'essor des méthodes basées sur l'apprentissage profond et les réseaux de neurones convolutifs, le détecteur de coins de Harris a été largement supplanté par des détecteurs de points d'intérêt appris qui peuvent s'adapter à des tâches et des données spécifiques. Cependant, il reste un outil pédagogique important et une référence pour évaluer de nouveaux algorithmes. De nombreuses bibliothèques, comme OpenCV, fournissent des implémentations intégrées, et il est encore utilisé dans des scénarios où les ressources de calcul sont limitées ou lorsque l'interprétabilité est souhaitée. Les principes de détection de coins basés sur les gradients influencent également les couches d'extraction de caractéristiques modernes dans les architectures de réseaux résiduels et autres.
Limitations et extensions
Une limitation clé est le manque d'invariance à l'échelle, que les détecteurs de Harris-Laplace et de Hessian-Laplace corrigent en intégrant une analyse de l'espace d'échelle. Le détecteur est également sensible au bruit, bien que le lissage gaussien atténue ce problème. Des extensions comme le détecteur de coins de Shi-Tomasi, qui utilise la valeur propre minimale comme réponse, améliorent la robustesse pour les applications de suivi. En pratique, le détecteur de Harris est souvent combiné avec une suppression non maximale et un raffinement sous-pixel pour obtenir une localisation précise des points clés.
Contexte historique
Le détecteur de coins de Harris est issu de travaux menés au Xerox PARC et dans d'autres laboratoires de recherche dans les années 1980, s'appuyant sur des méthodes antérieures de détection de coins par Moravec. Il a constitué une avancée significative car il fournissait une réponse plus stable et plus répétable que les techniques précédentes. La simplicité et l'efficacité de l'algorithme en ont fait un outil standard dans les programmes de vision par ordinateur et les applications industrielles. Même si l'intelligence artificielle et l'IA générative ont transformé le domaine, le détecteur de coins de Harris reste un témoignage de la valeur durable des méthodes géométriques et statistiques classiques.
Notes d'implémentation
En pratique, le détecteur nécessite de sélectionner la taille de la fenêtre, le sigma de la gaussienne et le seuil pour R. Les choix courants incluent une fenêtre de 3x3 ou 5x5, un sigma autour de 1, et un seuil basé sur une fraction de la réponse maximale. L'algorithme est implémenté dans des bibliothèques populaires comme OpenCV, scikit-image et MATLAB, ce qui le rend accessible pour le prototypage. Pour les grandes images, le calcul peut être vectorisé à l'aide d'opérations de convolution, ce qui est efficace sur le matériel moderne.