DØtection de points d’intØrŒts - Mise en correspondance

Cet article traite de la détection de points d’intérêts dans les images et de leur mise en correspondance, un sujet fondamental en vision par ordinateur. Il s’adresse aux étudiants et chercheurs débutants souhaitant comprendre comment identifier des éléments clés dans une image et les associer entre plusieurs images pour des applications comme la reconnaissance, la reconstruction 3D ou le suivi d’objets.

La question

Le travail aborde le problème de la détection de points d’intérêts dans une image, c’est-à-dire des points particuliers comme des coins, des jonctions ou des variations de texture fortes, qui sont essentiels pour analyser et comprendre une scène visuelle. Ensuite, il s’agit de mettre en correspondance ces points entre différentes images d’une même scène, ce qui est crucial pour des tâches comme la reconstruction 3D, la reconnaissance d’objets ou la navigation autonome. Ce problème est complexe car il faut détecter des points stables, robustes aux variations d’éclairage, de point de vue, et gérer les ambiguïtés dans la correspondance.

Concepts de base

Les points d’intérêts correspondent à des doubles discontinuités dans la fonction d’intensité d’une image, par exemple des coins, des jonctions en T ou des points de forte variation de texture. Ces points sont préférés aux contours car ils fournissent plus d’informations, sont robustes aux occultations et ne nécessitent pas d’opérations de chainage.

Trois grandes approches existent pour détecter ces points :

• Approches par contours : on détecte d’abord les contours, puis on extrait les points d’intérêts comme les points de courbure maximale ou les intersections.
• Approches par intensité : on analyse directement la fonction d’intensité pour détecter les discontinuités.
• Approches basées sur des modèles : on identifie les points d’intérêts en comparant la fonction d’intensité locale à un modèle théorique.

Les approches par intensité sont généralement privilégiées pour leur stabilité et leur généralité.

Détecteur de Moravec

Le détecteur de Moravec analyse le voisinage d’un pixel en déplaçant une fenêtre dans différentes directions et en calculant la moyenne des changements d’intensité. La fonction étudiée mesure la variation moyenne lorsque la fenêtre se déplace. Trois cas apparaissent :

1. Zone d’intensité constante : faible variation dans toutes les directions.
2. Contour rectiligne : faible variation le long du contour, forte variation perpendiculairement.
3. Coin ou point isolé : forte variation dans toutes les directions.

Le détecteur recherche donc des pixels où la variation minimale dans toutes les directions est maximale, ce qui correspond à un coin.

Détecteur de Harris

Le détecteur de Moravec présente des limites, notamment une réponse anisotropique liée aux directions discrètes de déplacement et une sensibilité au bruit. Harris et Stephens ont proposé une amélioration en utilisant le développement de Taylor de la fonction d’intensité au voisinage d’un pixel :

E(u,v) ≈ [u v] M [u v]^T

avec M une matrice calculée à partir des dérivées partielles de l’intensité et pondérée par un filtre gaussien pour réduire le bruit.

Les valeurs propres de M correspondent aux courbures principales :

• Faibles valeurs propres : intensité constante.
• Une forte valeur propre : contour.
• Deux fortes valeurs propres : coin.

Harris propose un opérateur de détection basé sur :

R = det(M) - k * trace(M)^2

où R est positif au voisinage d’un coin, négatif près d’un contour et faible dans une région uniforme.

Approche

La méthode consiste d’abord à détecter des points d’intérêts robustes dans chaque image à l’aide des détecteurs présentés, principalement celui de Harris pour sa meilleure stabilité. Ensuite, la mise en correspondance entre images est réalisée en comparant ces points selon des mesures de similarité.

La mise en correspondance repose sur des contraintes géométriques pour réduire les ambiguïtés :

• Contrainte épipolaire : pour un point dans la première image, son correspondant dans la deuxième image doit se situer sur une droite épipolaire spécifique.
• Rectification d’images : transformation des images pour que les droites épipolaires soient horizontales, simplifiant la recherche de correspondants.
• Contrainte d’ordre : impose que les projections des points apparaissent dans le même ordre sur les droites épipolaires, limitant les correspondances impossibles.

Pour mesurer la similarité entre points, on utilise des méthodes de corrélation basées sur les intensités des pixels dans une fenêtre autour du point :

• Sum of Absolute Distances (SAD) : somme des différences absolues des intensités.
• Sum of Squared Distances (SSD) : somme des carrés des différences d’intensité.

Ces mesures sont souvent normalisées (ZSAD, ZSSD) pour limiter l’influence des caractéristiques propres aux caméras.

Enfin, des méthodes utilisant des invariants, comme des dérivées d’intensité, sont proposées pour améliorer la robustesse aux transformations géométriques et photométriques, car les corrélations classiques sont sensibles aux changements d’échelle, rotation ou illumination.

Résultats

Le détecteur de Harris améliore la détection de coins par rapport à Moravec en offrant une réponse isotrope et moins bruitée grâce à l’utilisation d’un filtre gaussien et à la prise en compte des deux courbures principales. La mise en correspondance basée sur la contrainte épipolaire et la corrélation normalisée permet de réduire de manière significative les ambiguïtés, bien que la contrainte d’ordre ne soit pas toujours vérifiée en pratique selon la taille des objets.

Les méthodes par invariants montrent un potentiel pour une meilleure robustesse aux transformations, mais restent plus complexes à mettre en œuvre.

Limites et questions ouvertes

Plusieurs limitations persistent :

• Les méthodes de corrélation supposent que les changements de point de vue n’altèrent pas l’aspect des surfaces (hypothèse de surfaces lambertiennes).
• Les occultations ne sont pas prises en compte lors de la recherche de correspondants.
• La correspondance suppose que les régions rectangulaires dans une image correspondent à des régions rectangulaires dans l’autre, ce qui n’est pas toujours vrai.
• La contrainte d’ordre n’est pas toujours vérifiée, notamment pour les objets de grande taille.

Ces limites soulignent la nécessité de méthodes plus sophistiquées pour gérer les variations d’échelle, d’orientation, d’occlusion et de photométrie.

Glossaire

• Point d’intérêts : point dans une image caractérisé par une forte variation locale d’intensité, comme un coin ou une jonction.
• Contour : ligne dans une image correspondant à une discontinuité d’intensité.
• Fenêtre : voisinage rectangulaire autour d’un pixel utilisé pour l’analyse locale.
• Détecteur de Moravec : méthode de détection de points d’intérêts basée sur la variation d’intensité lors du déplacement d’une fenêtre.
• Détecteur de Harris : méthode améliorée utilisant le développement de Taylor et une matrice de dérivées pour détecter les coins.
• Matrice M : matrice calculée à partir des dérivées d’intensité utilisée dans le détecteur de Harris.
• Contrainte épipolaire : contrainte géométrique limitant la recherche de correspondants à une droite dans l’image.
• Rectification d’images : transformation des images pour simplifier la géométrie épipolaire.
• Contrainte d’ordre : contrainte imposant que les projections des points conservent leur ordre sur les droites épipolaires.
• Sum of Absolute Distances (SAD) : mesure de distance basée sur la somme des différences absolues d’intensité.
• Sum of Squared Distances (SSD) : mesure de distance basée sur la somme des carrés des différences d’intensité.
• ZSAD, ZSSD : versions normalisées des mesures SAD et SSD pour limiter l’influence des caractéristiques des caméras.
• Invariants : caractéristiques d’une image ou d’une fonction qui restent constantes sous certaines transformations.