Précédent

Sommaire

Suivant

Une autre approche

Modèle mathématique :

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.

Avant de passer à la mise en oeuvre, il nous faut fixer un modèle mathèmatique, du « coin ». Les coins peuvent alors être interprétés comme les maximums locaux de courbures.

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.

• Dans le cas d'un coin simple, on peut alors remarquer que les deux maxima se déplacent sur une droite avec le facteur d'échelle, et que cette droite est la "bissectrice" du coin. Ce dernier se trouve donc quelque part sur la droite qui relie les deux extremums qui en sont issus. On pourra alors utiliser la propriété que l'emplacement réel du coin correspond aussi à un zero-crossing du Laplacien, et que les zeros-crossing sont eux des invariants par rapport au facteur d'échelle.

• 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 :

  
  Ici on voit l'image filtrée, d'où son aspect "floue".

  
  Ici, l'image de la courbure, avec les extremums de courbure positifs (croix rouges) et négatifs (croix blanches). On note les dédoublements des extremums négatifs, qui peuvent poser des problèmes de couplage.

  
  Ici on a l'image originale (non filtrée), avec la position reconstruite des coins. On voit que certains sont bien placés, mais que la méthode ne fonctionne pas bien pour les angles aigus, alors que l'on a raté un coin ayant un angle assez faible.

Explications :

• 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.

Ici on voit l'image filtrée, d'où son aspect "floue".

Ici, l'image de la courbure, avec les extremums de courbure positifs uniquement. Maintenant, les croix rouges désignent les maximums au premier facteur d'échelle, les croix vertes au deuxième. On a plus les problèmes de dédoublements. Comme on le verra plus tard, des maximums peuvent cependant fusionner quand le facteur d'échelle augmente, ce qui peut amener à la perte de coins, mais pas à une mauvaise localisation.

Ici on a l'image originale (non filtrée), avec la position reconstruite des coins. Il y a toujours un coin qui manque, mais tous les autres coins sont bien placés.

Enfin, voyons maintenant ce que donne la méthode sur une images réelle :

Une image d'architecture, catégorie qui se prête bien à ce type de traitement.

Méthode de détection

L'image de courbure d'une image naturelle est très bruité. C'est à dire qu'il y a beaucoup d'extremums locaux. Cela est dû au fait que le bruit de l'image naturelle est amplifié par le calcul de la courbure. Il est donc nécessaire de filtrer les images naturelles par un filtre passe-bas afin d'en diminuer le bruit. Cependant, le filtrage passe-bas diminue la qualité de la localisation des extremums de courbure. En effet, ceux-ci s'éloignent du coin en fonction de l'importance du filtrage. Il est donc nécessaire d'utiliser un algorithme qui est capable de retrouver l'emplacement du coin à partir des extremums de courbure.

Dans le modèle idéal d'échelon, le maximum et le minimum de courbure sont quasi confondus, il n'y a pas de problèmes de localisation du coin

Après le filtrage gaussien, le maximum et le minimum de courbure se retrouvent de part et d'autre du coin à détecter

En effet, les maximum de courbure sont eloignés du coin d'une distance proportionnelle à la variance de la gausienne du filtrage passe-bas mais reste toujours sur la bissectrice du coin. Ainsi on pourrait détecter le maximum et le minimum de courbure, de part et d'autre du coin puis chercher à détecter le coin sur le segment qui les lient.
Une méthode pour détecter le coin serait de trouver le maximum et le minimum de courbure associé au coin. Ainsi, en prenant le centre du segment délimité par ces deux points nous aurions une bonne approximation de l'emplacement du coin.
Cependant, la détection des minimums de courbure est nettement plus difficile que la détection des maximums. Cela est du au calcul de la courbure gaussienne, qui donne un maximum plus prononcé que le minimum.
Nous utilisons donc une méthode plus complexe afin de détecter l'emplacement des coins. Tout d'abord nous calculons deux images de courbure obtenues par deux filtrages gaussiens différents. Ensuite nous recherchons sur ces images de courbure les deux maxima semblant être associés au même coin. Enfin nous recherchons le zero-crossing du laplacien sur la demi-droite commençant par le point maximum de courbure obtenue par le filtrage gaussien d'écart-type le plus élevé (et donc celui le plus éloigné du coin) et passant par le second maximum de courbure. Nous utilisons le zero-crossing du laplacien parce que les coins appartiennent à un contour de l'image et que le laplacien s'annule sur les contours.

L'algorithme peut donc être découpés en cinq étapes:

1. Filtrage gaussien pour deux variances différentes de l'image d'origine (obtention de deux images floues)
2. Estimation des dérivées jusqu'au second ordre pour les deux images
3. Calcul des deux images de courbure, à partir de la formule du II
4. Détection des maxima locaux importants sur chacune des deux images de courbure
5. Appariemment des maxima entre les deux images, sur un critère de proximité
6. Pour chaque paire, détecter un zéro-crossing du laplacien sur la demi-droite des deux maxima

Les parties 1) et 2) peuvent être effectuées simultanément ou non, comme expliqué au IV ci-dessous.
La partie 4) détecte les points de l'image de courbure qui sont supérieur à un fonction linéaire de leur huit voisins, ainsi lorsque l'on désire une détection très stricte, on peut utiliser les fonctions 2x ou même 5x afin de ne conserver que les maxima locaux qui se dégagent nettement de leur voisins.
La partie 5) consiste à prendre deux maxima correspondant à deux filtrages gaussiens différents, suffisemment proches, distance inférieure à la différence entre les deux variances des gaussiennes, mais distincts et à les apparier.
Enfin dans la partie 6), pour chaque paire trouvée, on suit la direction deux deux maxima, à partir de celui correspondant à la plus petite variance et en dans le sens opposé au second maximum, et à s'arrêter au premier changement de signe du laplacien, si celui-ci est à une distance du maximum de départ proche de la plus petite des deux variances.

Liens :http://www.tsi.enst.fr/tsi/enseignement/ressources/mti/pts_carac/index.htm