Pour le système visuel humain, l'essentiel de l'information pertinente dans une image est contenue dans ses singularités. Il nous est en effet très difficile de reconnaître une image dont on aurait coupé les hautes fréquences. Les singularités les plus fréquentes et les plus pertinentes sont les coins, c'est-à-dire les extrémités de secteurs angulaires homogènes. Dans le cas des images réelles, ceux-ci peuvent provenir de trois origines différentes :

• des singularités dans la teinte des textures appliquées sur les objets (les coins des carreaux d'une chemise par exemple)
• de la projection des coins des volumes contenus dans la scène
• des obstructions entre les différents objets, ou encore des ombres portées, qui induisent des secteurs angulaires plus sombres.

Les premiers et surtout les deuxièmes se révèlent particulièrement utiles :

• pour l'analyse de scènes
• pour l'analyse de mouvements : ce sont des structures stables au cours des déplacements. Idéalement, un appariement des coins détectés à des instants voisins permet de retrouver les différents objets qui composent la scène et leurs déplacements en utilisant les contraintes de rigidité entre coins provenant d'un même objet.
• pour le matching stéréoscopique : là encore, un appariement des coins détectés dans un couple d'images stéréoscopique aide à la reconstitution de la scène tridimensionnelle.

L'algorithme que nous avons implémenté est à peu de choses près celui qui est présenté dans l'article de Rachid Deriche et Gérard Giraudon "A computational approach for corner and vertex detection". Les coins, tels qu'ils y sont modélisés, induisent des maximums locaux de la courbure gaussienne de l'image -vue comme une nappe. Nous allons maintenant montrer comment ce critère est utilisé pour réaliser un détecteur.

• modèle mathématique :

Nous avons donc vu l'intérêt que présente la détection de coins dans une image. Avant de pouvoir passer a la mise en œuvre, il faut nous fixer un modèle mathématique du "coin".

Nous nous limitons ici au cas des images à niveau de gris. Une image est alors une fonction f(x,y) d'une partie de R² ou Z² dans R, ou Z, ou [0,255], selon la représentation choisie. On se place tout d'abord dans le cas continu : une image est alors une nappe dans R3. Les coins peuvent alors être interprétés comme les maximums locaux de courbures.

Dans le cas discret, on adoptera donc une mesure "d'angularité" d'un point de l'image, et les coins seront les maxima locaux de cette mesure. Suivant [1], nous choisirons donc comme mesure la courbure gaussienne, qui est aussi le produit des courbures principales :

La détection de coins sur une image se fait donc simplement par un calcul de dérivées à un certain ordre, puis par extraction des maxima locaux.

Image initiale	Image courbure	Image initiale avec localisation des coins
NB: On peut déjà remarquer qu'un coin de l'image se traduit par deux maximums de courbures, quasi confondus : un positif (en blanc) et un négatif (en noir)

Cette approche extrêmement simple, et hélas aussi extrêmement limitée. En effet, pour une image non synthétique, le bruit présent dans l'image nous force à effectuer un filtrage préliminaire à la recherche de maximums locaux de courbure, sous peine de voir apparaître partout des coins sans aucune signification.

Nous effectuons donc un filtrage gaussien. Cette opération de filtrage est caractérisée par l'écart-type sigma de la gaussienne utilisée pour la convolution. Pour différents facteurs sigma, on obtient une succession d'images issues de l'original. On parle alors de représentation à différentes échelles, ou de facteur d'échelle.

Une telle opération de filtrage se traduit par un lissage de l'image en général, et des coins en particulier. Les angles nets deviennent doux, et les coins ne sont plus aussi bien localisés. On observe notamment que les maximums de courbures positifs et négatifs ne sont plus confondus, mais s'éloignent l'un de l'autre. Les figures ci-dessous donnent une interprétation simple de ce phénomène à une dimension, et le résultat sur notre image "d'école".

Sur l'échelon d'origine, les deux maxima de courbure sont bien confondus, et donc le sommet bien localisé.

Après filtrage gaussien, l'échelon est devenu une "pente douce", on a deux maxima de courbure bien séparés, et l'emplacement du vrai coin (avant filtrage) se trouve quelque part entre ces deux maximums.

Après le filtrage, les coins sont arrondis.

On retrouve cela sur l'image de courbure, avec des zones dilatées de courbure positive et négative, et des maxima éloignés.

Sur l'image d'origine, pour un seul coin, on se retrouve avec deux maximums de courbures, délocalisés.

 On a donc deux problèmes issus de ceux phénomène :

• Pour un coin "réel" de l'image initiale, on a maintenant deux extremums locaux de courbure bien distants (un positif et un négatif). Une première solution et de ne prendre en compte qu'un seul type d'extremum. Il ne se pose alors aucun problème de couplage, mais en contrepartie l'information obtenue sur l'emplacement réel du point caractéristique de l'image est très imprécise, et dépend du facteur d'échelle.
• Cette information peut être très précieuse, et l'on désire donc obtenir une localisation aussi précise que possible des coins.

• Une première tentative :

Une première approche algorithmique consiste donc à trouver les extremums de la courbure gaussienne, à reformer les couples issus d'un même coin, puis à rechercher le coin sur le segment de droite qui joint ces deux points grâce au Laplacien.

Le problème essentiel est celui du matching : comment identifier correctement les couples d'extremums issus d'un même coin ? Un simple critère de distance s'avère insuffisant. En effet, l'extremum de signe opposé le plus proche conduit très souvent à un mauvais matching. Pour améliorer les résultats, on est amené a mettre en place des conditions de distances minimale entre les deux maxima en fonction du facteur d'échelle, puis à comparer leur valeur respective que l'on peut contraindre à un certain rapport. Voici quelques résultats.

Tout d'abord avec une image de synthèse bruitée :

• Tout d'abord la difficulté du couplage et son manque de robustesse force a un seuillage fort lors de la détection des extremums, pour limiter les parasitages par effet de discrétisation (voir plus bas). Cela peut aussi nous faire perdre des vrais coins obtus, qui donne des courbures plus faibles. Sans un seuillage assez important, on aboutit à un détecteur de contour : pour s'en convaincre, il suffit de noter tous les petits extremums de la courbures le long des contours de la figures initiales que l'on repère facilement sur l'image de la courbure.
• Ensuite, la démultiplication des extremums négatifs conduits encore à des mauvais couplages, et à des recherches de coins dans de mauvaises directions. Lorsque l'on ne trouve pas de zero-crossing, on place alors le coin sur l'extrema positif, ce qui conduit à une mauvaise localisation.

Du fait de cette difficulté de matching, nous ne sommes pas parvenus à des résultats satisfaisants sur les images réelles avec cette méthode. En effet, dans les images réelles, le nombre et la densité des coins sont généralement beaucoup plus élevés que sur les images vues jusqu'à présent (les superpositions d'objet dans l'espace, les ombres, les textures donnent naissance à de nombreux "coins").

• Matching sur deux facteurs d'échelle :

Comme remarqué précédemment, les maximums se déplacent sur une même droite avec les changements d'échelle. Une deuxième idée consiste donc à coupler les maximums d'un même signe à deux niveaux d'échelle différents pour en déduire la direction de la bissectrice, puis rechercher encore une fois la position du coin d'origine sur cette droite grâce au zero-crossing du Laplacien.

Cette méthode possède l'avantage d'un matching beaucoup plus robuste : en effet, les maximums se déplacent continûment en fonction du facteur d'échelle. Le compromis devient alors d'avoir un écartement assez important pour avoir une indication fiable sur la direction de la droite de recherche.

Voici tout d'abord les résultats obtenus sur la même image de synthèse, avec un bruit de même importance.

L'écart delta entre les deux valeurs de l'écart-type utilisées donne l'éloignement standard entre les deux maxima de courbure correspondant à un même coin (celui-ci dépend également de l'acuité du coin). Plus delta est grand, plus le risque d'erreurs dans l'appariement des maxima est grand. D'un autre côté, si delta est trop petit, on aura à cause de la discrétisation de l'image une grande imprécision sur la direction de la droite joignant les deux maxima. Le coin détecté risque donc d'être mal localisé, voire totalement erroné. Le réglage de delta implique donc de trouver un bon compromis. Les résultats montrent que delta doit être supérieur à 2. Par conséquent, la grande échelle est au moins égale à 3. Il en résulte que les maxima trouvés à grande échelle peuvent provenir de la "fusion" de maxima induits par des coins trop proches, comme le montre l'exemple suivant :

Les quatre coins de la fenêtre donnent bien quatre maxima à petite échelle (les quatre points rouges), mais à grande échelle il n’en subsiste plus qu’un (le point vert). De ce fait, un seul coin est détecté, résultant de l’appariement du maximum à grande échelle avec le maximum à petite échelle le plus proche, en l’occurrence en bas à droite.

Une solution à ce problème serait de trouver les maxima de courbure pour une gamme d’échelles allant de la petite à la grande, et d’opérer un chaînage de ceux-ci. Si le pas définissant la gamme d’échelles est suffisamment petit, il est facile d’établir une filiation entre les maxima au différentes échelles. A partir de là, en appariant un père avec tous ses fils, on récupère les coins que l’on ne détectait pas précédemment. Cette méthode semble en fait régler tous les problèmes d’appariement de maxima.

Un autre problème est celui des coins très aigus ou très obtus. Les coins obtus donnent lieu à des maxima de faible amplitude, et donc trop facilement éliminés par l’étape de seuillage. D’autre part, les coins aigus fournissent des maxima éloignés, ce qui rend leur appariement difficile.

Enfin, les portions rectilignes de l’image peuvent, à cause de la discrétisation, présenter des sauts. Les maxima de courbure correspondants sont proches et d’intensité significative. Si on veut les éliminer par seuillage, on risque donc d’éliminer également certains coins obtus. Voici une illustration sur une image synthétique :

Toutefois, l’amplitude des maxima de courbure dûs à la discrétisation diminue plus vite que celle des maxima de courbure induits par des angles obtus lorsque l’échelle augmente. On pourrait donc résoudre le problème en chaînant les maxima et en ne conservant que les chaînes qui comportent des maxima à suffisamment grande échelle.

Pour conclure, nous pensons que notre implémentation d'un algorithme simple démontre l'intérêt et le potentiel du principe d'une analyse multi-échelles. Il devrait prendre tout son sens dans une mise en œuvre utilisant toute une gamme d'échelles plutôt que simplement deux.