Introduction à la détection de caractéristiques

Pour déterminer si deux zones d'une image représentent la même chose, il est plus efficace de comparer des indices précis et facilement identifiables que de comparer l'image entière. Le processus de sélection de ces indices est appelé détection de caractéristiques. Il constitue le point d'entrée de tout processus nécessitant une correspondance entre images : estimation du mouvement de la caméra, assemblage de panoramas, reconstruction 3D, recherche d'images, inspection visuelle. Cet article distingue la sélection des points de référence de leur mise en correspondance et expose le raisonnement sous-jacent aux algorithmes classiques, tant du point de vue de l'équation que de celui de l'implémentation.

Intel RealSense D435

Image : Intel Caméra de profondeur RealSense D435 (Marc Auledas, CC BY-SA 4.0), Wikimedia Commons. Caméra représentative, et non un appareil de détection de caractéristiques uniquement.

Résumé en 30 secondes

• Placez les points caractéristiques non pas sur des murs plats, mais aux angles avec des variations d'intensité dans plusieurs directions, ou sur des zones dont la luminosité diffère de leur environnement. La répétabilité (redétection au même endroit après une légère transformation de l'image) est essentielle.

La détection de coins exploite la bidirectionnalité des gradients locaux ; la détection de blobs repère une zone de luminosité distincte à une certaine échelle. DoG recherche rapidement des blobs candidats à partir de la différence de plusieurs images floues.

FAST détecte rapidement les coins en comparant uniquement les pixels d'un cercle. ORB combine FAST avec une pyramide d'images, une estimation d'orientation et un descripteur binaire BRIEF pivoté, ce qui le rend adapté à une utilisation en temps réel.

SIFT sélectionne l'échelle via DoG, normalise l'orientation avec un histogramme de direction de gradient et construit un descripteur de 128 dimensions. Le coût de calcul et de mémoire augmente, mais il est robuste aux changements d'échelle et de rotation.

La détection seule ne détermine pas la correspondance. La distance entre descripteurs, le test de ratio et la vérification géométrique basée sur RANSAC doivent être évalués conjointement. Récemment, des méthodes de détection et de correspondance basées sur l'apprentissage, telles que SuperPoint, ALIKED et LightGlue, sont également devenues pratiques.

Qu'est-ce qu'un point caractéristique ? — Non pas « un point qui se démarque », mais « un point que l'on retrouve facilement »

Soit les coordonnées de pixel \mathbf{x}=(x,y)^\mathsf{T} et l'image I(\mathbf{x}). Un point caractéristique est un emplacement dont la zone voisine peut être détectée de manière stable comme étant la même position physique, même après une légère translation, rotation ou mise à l'échelle, et qui peut être distingué des autres points par le motif environnant. Le premier est appelé détecteur, et ce qui transforme le second en un vecteur numérique ou une chaîne de bits est appelé descripteur.

Ces deux éléments sont distincts. FAST est, en principe, un détecteur ; BRIEF est un descripteur ; ORB est un mécanisme qui combine les deux. SIFT est la combinaison d'un détecteur DoG et d'un descripteur d'histogramme de gradient. Comparer uniquement les noms peut prêter à confusion ; c'est pourquoi nous considérerons désormais ce processus en trois étapes : « sélection des points », « représentation de l'environnement » et « appariement des points ».

Figure : créée par Duskcoil. La qualité du système dépend non pas du nombre de détections, mais du nombre de correspondances géométriquement correctes. Cohérent.

Coins : Sélection des zones de variation bidirectionnelle

La caractéristique la plus intuitive est le coin. Exprimez la variation apparente lorsqu'une portion d'image W est légèrement décalée \mathbf{u}=(u,v)^\mathsf{T} sous la forme de la SSD (somme des carrés des différences) :

Sous une approximation de Taylor du premier ordre, la matrice de structure locale (moment d'ordre deux) \mathbf{M} devient :

où I_x,I_y représentent les gradients de l'image et w un poids, tel qu'une fenêtre gaussienne. Soient \lambda_1,\lambda_2 les valeurs propres de \mathbf{M} ; un point est un coin où même la plus petite valeur propre est grande. Sur une arête, où le gradient est grand dans une seule direction, une valeur propre reste petite. Dans les régions planes, Les deux restent de petite taille. Le détecteur de Harris ne calcule pas explicitement les valeurs propres à chaque pixel ; il sélectionne plutôt les maxima locaux de la valeur de réponse suivante :

k est généralement compris entre 0,04 et 0,06. Le détecteur de Harris est relativement robuste à la rotation, mais comme il analyse une fenêtre de taille fixe, il ne dispose d'aucun mécanisme pour sélectionner le même point lorsque le sujet est considérablement agrandi ou réduit. Le critère \min(\lambda_1,\lambda_2) de Shi-Tomasi est également largement utilisé pour sélectionner les coins adaptés au suivi.

Blobs : Un « Blob », même sans coin, est un indice utile

Les coins seuls ne permettent pas de détecter correctement les logos ronds, les points, les zones sombres ou le centre d'un reflet lumineux. Un détecteur de blobs repère donc des zones de luminosité localement distinctes par rapport à leur environnement, à une certaine échelle. Représentez l'espace d'échelle lissé par une gaussienne. G(\mathbf{x};\sigma) comme

où * représente la convolution et \sigma représente « la taille que nous observons ». La réponse normalisée à l'échelle du laplacien du gaussien (LoG),

réagit fortement à un cercle sombre sur un fond clair, ou à un cercle clair sur un fond sombre. La recherche des extrema non seulement en position, mais aussi dans l'espace tridimensionnel (x,y,\sigma), y compris la direction \sigma, permet de déterminer simultanément le centre et la taille caractéristique d'une tache. On peut également interpréter cela comme l'échelle correspondant à une tache circulaire dont le rayon est approximativement \sqrt{2}\sigma.

LoG est une excellente idée, mais le calcul de la dérivée seconde exacte à chaque échelle est coûteux. Cette approximation et l'accélération qui en découle mènent à DoG, puis à SIFT.

DoG : Recherche de candidats invariants d'échelle à partir d'une différence de flous

La différence de gaussiennes (DoG) est la différence entre deux images floues adjacentes :

où k>1 est le rapport entre les échelles adjacentes. À un facteur constant près, la DoG approxime la LoG normalisée par l'échelle ; ainsi, la recherche de candidats blob ne nécessite qu'une convolution supplémentaire. Concrètement, on construit une pyramide gaussienne en floutant progressivement l'image, puis on compare chaque pixel DoG à ses 8 voisins à la même échelle, plus 9 voisins à l'échelle supérieure et 9 voisins à l'échelle inférieure (26 au total). Un maximum ou un minimum en fait un candidat.

Les candidats ne sont pas utilisés tels quels. Les extrema faibles sont considérés comme du bruit et sont rejetés, de même que les extrema situés le long de bords allongés. L'interpolation d'une fonction quadratique 3D autour d'un extremum DoG fournit la position et l'échelle au niveau du sous-pixel. Pour la matrice hessienne :

Une valeur élevée de \mathrm{Tr}(\mathbf{H})^2/\det(\mathbf{H}) indique une réponse de bord où une seule courbure principale est marquée, et ces points sont exclus. Ceci résout le même problème que pour la détection des coins : un point sur un bord semble similaire même déplacé le long de celui-ci, il est donc impossible de déterminer sa correspondance avec précision.

FAST : Détection rapide des coins par analyse d'un cercle

Features from Accelerated Segment Test (FAST) utilise les 16 pixels d'un cercle de Bresenham de rayon 3 centré sur le pixel p. Pour un seuil t donné, si n pixels consécutifs (généralement 9 ou 12) sont tous plus clairs que I_p+t, ou tous plus sombres que I_p-t, p est considéré comme un coin.

Car il calcule Sans gradients ni matrices — un petit nombre de comparaisons de pixels et un rejet précoce —, sa rapidité est exceptionnelle. La clé de cette rapidité réside dans sa conception : elle vérifie d'abord les pixels aux positions 1, 5, 9 et 13 heures sur le cercle, et s'arrête immédiatement si une séquence continue de pixels clairs/foncés ne peut se former. En revanche, FAST classique ne fournit ni échelle ni orientation, et a tendance à réagir à de nombreux points le long des contours. Ce n'est qu'après avoir calculé la différence d'intensité par rapport à l'environnement, appliqué la suppression des non-maxima (NMS) et combiné les résultats avec une pyramide d'images qu'il devient un détecteur multi-échelle pratique.

ORB : FAST n'est plus un simple outil « rapide mais difficile à utiliser »

ORB (Oriented FAST and Rotated BRIEF) est une construction qui renforce FAST et BRIEF, conçue pour la mise en correspondance d'images en temps réel. Elle exécute d'abord FAST sur une pyramide d'images à chaque taux de réduction s, en conservant les points les plus élevés de chaque niveau. Ceci assure, sinon une précision absolue, une robustesse à l'échelle. Changement.

Ensuite, le centroïde d'intensité de la zone autour du point p est calculé. À partir des moments

l'angle \theta=\operatorname{atan2}(m_{01},m_{10}) entre le centre p et le centroïde \mathbf{c} devient l'orientation dominante. Le descripteur BRIEF est une chaîne binaire comparant les paires de pixels (\mathbf{a}_i,\mathbf{b}_i) au sein de la zone :

répété environ 256 fois. Dans ORB, les coordonnées des paires de points sont pivotées de \theta avant la comparaison, de sorte que le même motif binaire tend à être obtenu même après rotation. rBRIEF, qui apprend à sélectionner les paires de comparaison à faible corrélation, est une autre façon de préserver le contenu informationnel des bits. La distance entre les chaînes binaires peut être calculée rapidement comme la distance de Hamming — le nombre de bits à 1 après XOR.

Le point fort d'ORB réside dans sa rapidité et son efficacité mémoire sur les processeurs et les systèmes embarqués, ce qui explique son utilisation répandue en SLAM visuel. Cependant, en cas de grandes différences d'échelle, de flou important ou de changements significatifs de point de vue, SIFT ou des descripteurs basés sur l'apprentissage avec des descriptions de gradient plus riches peuvent s'avérer avantageux.

SIFT : Normalisation cohérente de l'échelle, de l'orientation et de la description

SIFT (Scale-Invariant Feature Transform) détecte les extrema de (x,y,\sigma) via DoG et supprime les points à faible contraste et les réponses de bord. Autour de chaque point, il calcule l'amplitude et la direction du gradient et construit un histogramme d'orientation pondéré par une gaussienne. Le pic le plus important devient l'orientation dominante utilisée pour normaliser la rotation de la zone, et les pics secondaires dépassant 80 % du maximum se voient également attribuer leur propre orientation. C'est le principe fondamental de sa robustesse à la rotation.

Pour le descripteur, une fenêtre normalisée d'environ 16\times16 est divisée en 4\times4. Chaque cellule reçoit un histogramme de gradient à 8 directions. La dimensionnalité est donc 4\times4\times8=128. Le vecteur \mathbf{d} est normalisé L2, et les éléments supérieurs à 0,2 sont écrêtés et renormalisés, ce qui atténue la sensibilité aux variations locales d'éclairage.

Autrement dit, l'« invariance » de SIFT n'est pas magique. Il s'agit d'une conception explicite qui traite chaque source de variation individuellement : sélection de l'échelle via la pyramide d'images, rotation du repère selon l'orientation dominante et absorption du contraste par normalisation. Elle n'est pas totalement insensible aux déformations affines ni aux grandes différences de points de vue, qui nécessitent toujours l'utilisation de RANSAC ou d'une géométrie multi-vues en aval.

Pseudocode d'implémentation minimale

Le traitement des points caractéristiques ne doit pas s'arrêter à l'extraction ; il doit être implémenté jusqu'à la vérification de la correspondance. Voici un squelette applicable à ORB et à SIFT.

function match_images(imageA, imageB, method):
    grayA, grayB = to_gray(imageA), to_gray(imageB)
    detector = create(method)        # ORB: FAST+pyramid+rBRIEF / SIFT: DoG+gradient
    keyA, descA = detector.detect_and_compute(grayA)
    keyB, descB = detector.detect_and_compute(grayB)

    metric = HAMMING if method == ORB else L2
    tentative = []
    for each descriptor a in descA:
        b1, b2 = two_nearest(a, descB, metric)
        if distance(a, b1) < 0.75 * distance(a, b2):
            tentative.append((a.keypoint, b1.keypoint))

    H, inlier_mask = RANSAC_HOMOGRAPHY(tentative, reproj_threshold=3px)
    return tentative[inlier_mask], H

En ne considérant que le seul L'algorithme du plus proche voisin laisse des points ambigus, tels que les cadres de fenêtres, les grilles et les motifs répétitifs, dans le résultat. Le test du ratio de Lowe utilise le rapport entre la meilleure distance (d_1) et la deuxième meilleure (d_2), en éliminant les candidats lorsque l'écart avec la deuxième meilleure distance est insuffisant. RANSAC estime ensuite une homographie (\mathbf{H}) ou matrice fondamentale à partir de petits sous-ensembles aléatoires de correspondances, et sélectionne l'hypothèse qui explique le plus grand nombre de correspondances (points pertinents) avec une faible erreur de reprojection. Si l'objet est plan ou si la caméra a simplement pivoté sur place, la cohérence peut être vérifiée à l'aide de l'homographie.

(

Pour une scène 3D générale, la matrice fondamentale/essentielle est utilisée à la place. Le nombre de points pertinents et le ratio qui subsistent à ce stade représentent la quantité de caractéristiques réellement utilisables.

Robustesse face à l'éclairage, à l'échelle et à la rotation, et dans quelle mesure

Face aux variations d'éclairage, Un simple décalage de luminosité (I'(x,y)=I(x,y)+b) supprime les différences entre pixels, mais a peu d'effet sur les relations relatives dans les gradients ou les comparaisons binaires. Une variation uniforme de contraste (I'=aI+b) est également bien gérée par la normalisation des descripteurs SIFT. Cependant, lorsque la structure locale elle-même change (saturation d'exposition, limites des ombres, reflets, jour/nuit), les méthodes classiques seules n'offrent aucune garantie. Lors de la capture, il est essentiel de corriger ou de gérer précisément l'exposition et, si nécessaire, d'appliquer une correction de contraste locale telle que CLAHE dans les mêmes conditions aux deux images. Une surcorrection risque de transformer le bruit en caractéristiques parasites ; il convient donc d'être prudent.

Les méthodes Harris et FAST à résolution unique sont intrinsèquement sensibles aux changements d'échelle. La méthode ORB, qui recherche des candidats dans une pyramide d'images, présente une tolérance acceptable, bien que sa normalisation soit différente de celle de SIFT, qui sélectionne les extrema d'échelle continus via DoG. Si la texture disparaît à une échelle réduite, aucune méthode ne peut trouver de correspondance. La résolution d'entrée, la profondeur de la pyramide et la taille minimale des patchs doivent être déterminées en fonction de la plage de variation attendue de la distance de capture.

Concernant la rotation, la réponse de la méthode Harris elle-même est relativement stable, mais la mise en correspondance nécessite également la rotation du repère du descripteur. ORB attribue l'orientation via le centroïde d'intensité, SIFT via l'histogramme de direction du gradient. Cette normalisation angulaire continue est plus efficace qu'un descripteur ne gérant que des rotations de 90 degrés. Par ailleurs, une vue oblique marquée ne correspond pas à une rotation et une mise à l'échelle, mais à une déformation affine/projective, nécessitant des données multivues, des caractéristiques covariantes affines ou des caractéristiques issues de l'apprentissage, combinées à une vérification géométrique.

Métriques d'évaluation : Mesurer les correspondances utilisables, et non le nombre de points

Pour une paire d'images dont l'homographie est connue H, projetez le point \mathbf{x}_i de l'image A sur l'image B. Si un point situé à une distance inférieure à \epsilon existe dans l'ensemble de points détectés K_B, considérez-le comme une re-détection réussie. La répétabilité est conceptuellement

Mais trouver le même La localisation est inutile si les descripteurs ne permettent pas de la distinguer. Il est donc important de fournir également la précision de la correspondance (fraction de correspondances correctes), le nombre de correspondances correctes, le taux d'inliers post-RANSAC, l'erreur de rotation/translation de la pose estimée, le temps de traitement et la mémoire utilisée. HPatches est un benchmark représentatif qui dissocie les variations d'éclairage des changements de point de vue afin d'évaluer la mise en correspondance de patchs, les détecteurs et l'estimation d'homographie. À moins d'effectuer vos mesures avec des données correspondant à la géométrie de votre application (planes ou 3D à large base), il est déconseillé d'adopter un classement basé uniquement sur un seul score.

Les symboles ○ et ◎ du tableau ne représentent pas des valeurs absolues, mais des points de repère relatifs pour les implémentations typiques et les plages de valeurs attendues. Même SIFT peut être ambigu lorsque le même motif de grille remplit l'image, et même ORB peut obtenir suffisamment de points correspondants dans des conditions modérées.

Place de cette fonctionnalité dans les bibliothèques actuelles et les produits réels

Pour un premier prototype, les modules cv::ORB::create(), cv::SIFT::create() et cv::FastFeatureDetector::create() d'OpenCV sont faciles à utiliser. ORB est compatible avec BFMatcher(NORM_HAMMING) ; SIFT avec un module de distance L2 BFMatcher ou un module basé sur FLANN. Même si vous souhaitez séparer le détecteur et le descripteur, l'API Feature2D d'OpenCV vous permet de conserver le même flux de travail. Pour l'expérimentation basée sur l'apprentissage et le traitement GPU, Kornia sur PyTorch fournit SIFT, ORB, DISK, KeyNet/HardNet, etc. LightGlue, et bien d'autres, comme éléments de base.

En photogrammétrie et en reconstruction 3D, COLMAP est l'outil de référence ; sa documentation officielle actuelle prend en charge SIFT et ALIKED (avec ONNX activé). SIFT et ALIKED étant compatibles avec la mise en correspondance par force brute ou par LightGlue, il est aisé de comparer les approches classiques et celles basées sur l'apprentissage automatique au niveau de la reconstruction. Lors du choix d'un produit ou d'une bibliothèque, il est préférable de déterminer d'abord s'il doit fonctionner exclusivement sur le processeur, la latence admissible, si une mise en correspondance hors ligne intensive est envisageable et si un épinglage de version reproductible est nécessaire, plutôt que de se fier à la nouveauté du nom du modèle.

Recherches récentes : Optimisation conjointe de la détection, de la description et de la mise en correspondance

SuperPoint a marqué un tournant pour les approches basées sur l'apprentissage automatique. Un réseau entièrement convolutif génère simultanément une carte de probabilité des points d'intérêt et une carte de descripteurs, apprenant de manière auto-supervisée, via l'adaptation homographique, à reproduire les points malgré les transformations géométriques. L'idée est d'apprendre à partir des données pour identifier les emplacements utiles à la mise en correspondance, plutôt que de se fier uniquement à une approche basée sur l'apprentissage automatique. Notion de « zone d'angle » conçue manuellement.

DISK résout le problème de la sélection et de la mise en correspondance de points épars, processus discrets et difficiles à différencier, en optimisant la détection et la description de bout en bout grâce à des gradients de politique qui récompensent le nombre de correspondances correctes. ALIKED utilise une tête de descripteur déformable éparse qui apprend des emplacements de support déformables autour de chaque point clé, dans le but d'équilibrer expressivité et efficacité en extrayant les descripteurs aux points épars plutôt que de l'ensemble de la carte de caractéristiques dense.

Les systèmes de mise en correspondance s'éloignent également de la recherche indépendante du plus proche voisin. LightGlue estime les correspondances entre deux ensembles de caractéristiques locales à l'aide d'un mécanisme d'attention, avec un calcul adaptatif qui s'arrête prématurément lorsqu'une paire d'images est facile à apparier. Il ne s'agit pas d'un détecteur de caractéristiques à proprement parler, mais d'un rappel important : une bonne distance du descripteur par rapport au détecteur ne garantit pas à elle seule de bonnes correspondances finales. Actuellement, il est pertinent de comparer une configuration utilisant des caractéristiques classiques avec un système de mise en correspondance léger à une configuration faisant correspondre des caractéristiques apprises comme SuperPoint/ALIKED avec LightGlue, dans des conditions identiques. Paramètres RANSAC sur vos données cibles.

Liste de vérification pour la sélection et l'optimisation

• Commencez par enregistrer le nombre de détections, le nombre de passages au test de ratio, le nombre d'éléments RANSAC pertinents, le ratio d'éléments RANSAC pertinents et le temps de traitement sur des paires d'images réelles. Augmenter uniquement le nombre de détections peut s'avérer contre-productif si le nombre d'erreurs d'appariement augmente également.

• Pour un suivi de courte durée près d'une caméra fixe, commencez par FAST/ORB et ajustez nfeatures, le seuil FAST et les niveaux de la pyramide. En cas de faible texture, vérifiez le flou, l'exposition et la mise au point avant de réduire le seuil.

• Pour la mise en correspondance d'images fixes présentant d'importantes variations de distance de capture ou de rotation, utilisez SIFT comme référence. Il est impératif de toujours vérifier si une méthode plus rapide surpasse SIFT sur les mêmes données et avec la même vérification géométrique.

• La nuit, en cas de fort contre-jour, de changement de saison ou de différences importantes de point de vue, envisagez également l'utilisation de caractéristiques basées sur l'apprentissage. Toutefois, tenez compte de l'écart entre les données d'entraînement et l'environnement cible, des mises à jour du modèle et de la disponibilité du GPU dans l'évaluation des performances.

• Les motifs répétitifs, les surfaces spéculaires, les objets en mouvement et le flou de mouvement extrême sont Il s'agit moins d'un problème de détection de caractéristiques que d'une ambiguïté d'observation. On peut la compenser par le masquage, le suivi temporel, la fusion de capteurs et la planification de la capture.

La détection de caractéristiques n'est pas une méthode de classification universelle pour la compréhension d'images. Cependant, elle demeure une technologie fondamentale efficace pour sélectionner, avec un faible coût de calcul, les pixels capables de représenter une géométrie. Comprendre les concepts de coins, de blobs, d'espace d'échelle et de normalisation d'orientation permet d'identifier les causes des erreurs de mesure, que ce soit pour l'optimisation des algorithmes ORB/SIFT classiques ou l'évaluation de caractéristiques issues de l'apprentissage automatique.

Références

• [Lowe, Distinctive Image Features from Scale-Invariant Keypoints (article original SIFT)] IJCV 2004)](https://www.cs.ubc.ca/~lowe/papers/ijcv04.pdf)
• Rublee et al., ORB : une alternative efficace à SIFT ou SURF (ICCV 2011)
• Référence de la classe OpenCV Feature2D / ORB
• Référence de la classe OpenCV SIFT
• Tutoriel sur le détecteur de caractéristiques FAST d'OpenCV
• HPatches : analyse comparative et évaluation de descripteurs locaux manuels et appris (CVPR 2017)
• SuperPoint (Ateliers CVPR 2018)

• DISK (NeurIPS 2020)

• ALIKED (arXiv 2023)

• LightGlue (ICCV 2023)

• Documentation COLMAP sur l'extraction et la mise en correspondance de caractéristiques

• Documentation du module de caractéristiques Kornia

Dans le laboratoire d’extraction, faites pivoter une image synthétique et comparez les détections Harris et Shi–Tomasi.