Détection de contours

Le but de la détection de contours est de repérer les points d'une image numérique qui correspondent à un changement brutal de l'intensité lumineuse. Ces changements de propriétés de l'image traduisent en général des événements importants ou des changements dans les propriétés du monde. Ils incluent des discontinuités dans la profondeur, dans l'orientation d'une surface, dans les propriétés d'un matériau et dans l'éclairage d'une scène. La détection de contour est un champ de la recherche qui appartient au traitement d'image et à la vision par ordinateur, particulièrement dans le domaine de l'extraction de caractéristiques.

La détection des contours d'une image réduit de manière significative la quantité de données et élimine les informations qu'on peut juger moins pertinentes, tout en préservant les propriétés structurelles importantes de l'image. Il existe un grand nombre de méthodes de détection de l'image mais la plupart d'entre elles peuvent être regroupées en deux catégories. La première recherche les extremums de la dérivée première, en général les maximums locaux de l'intensité du gradient. La seconde recherche les annulations de la dérivée seconde, en général les annulations du laplacien ou d'une expression différentielle non-linéaire.

Exemple de détection de contours (Sobel)

Généralités

Dans une image en niveaux de gris, un contour est caractérisé par un changement brutal de la valeur. Le but de l'opération est de transformer cette image en une autre dans laquelle les contours apparaissent par convention en blanc sur fond noir.

Dans une section horizontale (ou verticale) de l'image rectangulaire, les variations de la valeur sont décrites par une courbe. Sur celle-ci un point d'un contour est associé à un maximum de la pente, c'est-à-dire à un extremum (maximum ou minimum) de la dérivée première. Cet extremum peut aussi s'interpréter comme un zéro de la dérivée seconde.

Dans une image numérisée, à chaque pixel est associée une valeur qui est en général différente de la valeur des pixels voisins. La notion de dérivée correspondant à une variation infiniment petite doit donc être remplacée par l'approximation différence finie utilisée en calcul numérique. Le problème est simplifié car on ne s'intéresse ici qu'aux comparaisons entre dérivées indépendamment de leurs valeurs. Ainsi la dérivée première au niveau d'un pixel se réduit à la différence entre les valeurs des deux pixels voisins, la dérivée seconde étant la différence entre les dérivées moyennées aux frontières des pixels.

Si on considère maintenant l'image rectangulaire, les dérivées premières dans les deux directions perpendiculaires s'écrivent pour le pixel centre en fonction des valeurs des pixels aux quatre points cardinaux :

D_x = E - W    D_y = N - S

Les dérivées secondes sont données par

D_2x = E - 2C + W    D_2y = N - 2C + S

Enfin, il faut remarquer qu'en considérant classiquement les fonctions comme des sommes de sinusoïdes, la dérivation multiplie leur amplitude par leur pulsation : c'est donc un filtre passe-haut qui introduit un bruit haute fréquence à l'origine de faux contours. Les dérivées ne sont donc en principe pas utilisées telles quelles mais associées à des filtres passe-bas (voir Lissage de l'image). L'utilisateur peut effectuer lui-même un prétraitement avec un filtre gaussien par exemple. Des méthodes plus élaborées incluent ce prétraitement dans le filtre.

Filtrage optimal

Les opérations décrites précédemment se traduisent par des filtres à appliquer à l'image. Trois critères ont été défini afin d'obtenir un filtre optimal pour la détection de contour^[1] :

1. bonne détection : détecter un maximum de contours ;
2. bonne localisation : les points détectés doivent être les plus proches possibles du vrai contour ;
3. réponse unique : minimiser le nombre de contours détectés plusieurs fois.

Ces critères se traduisent par des conditions sur la réponse impulsionnelle du filtre et débouchent sur des détecteurs de contours très performants.

Dérivée première

Méthode de base

L'opérateur de Roberts décrit dans une image rectangulaire, ayant un contour rampe, les dérivées premières elles-mêmes sont d'un intérêt limité car la pente maximale a peu de chances de se trouver sur l'une des deux directions considérées. Ce qui importe c'est la longueur du vecteur gradient dont elles sont les composantes. Cette longueur se calcule en principe par le théorème de Pythagore au prix d'un calcul sur les réels et on l'accélère considérablement en utilisant une approximation entière :

| G | = | E − W | + | N − S |

Indépendamment de la précision du calcul, il faut transformer ce résultat en un filtre numérique. La notion physique de filtre correspond à la notion mathématique de convolution. Lorsqu'il s'agit de données numérisées comme dans le cas du traitement d'images, la relation entre les valeurs des pixels de sortie et celle des pixels d'entrée est décrite par un tableau de nombres appelé matrice de convolution.

Filtre de Prewitt

La matrice qui correspond au filtrage horizontal, faisant ressortir essentiellement les contours verticaux, selon l'opérateur de Prewitt, s'écrit h_x = [-1 0 1] tandis que la matrice verticale h_y est sa transposée. Les deux convolutions avec le tableau de valeurs initiales créent deux tableaux G_x et G_y à l'origine du tableau G sur lequel on peut localiser les maximums.

Filtre de Sobel

Article détaillé : Algorithme de Sobel.

On obtient un meilleur résultat en remplaçant le filtre rectangulaire par un filtre triangulaire.

Filtre de Canny

Article détaillé : Algorithme de Canny.

Le filtre de Sobel est apprécié pour sa simplicité et sa rapidité d'exécution. Ces qualités posent des problèmes lorsqu'il s'agit de traiter une image complexe. Le filtre de Canny a été bâti autour de l'algorithme de Sobel pour améliorer ses résultats.

D'une part, les filtres triangulaires utilisés par Sobel étant peu efficaces face à une image fortement bruitée, un filtre gaussien est utilisé.

D'autre part, c'est là l'originalité de la méthode, elle permet d'éliminer des faux contours. En considérant non seulement l'intensité du gradient mais aussi sa direction, il est possible d'éliminer un pixel qui pointe vers deux pixels de valeur supérieure car ce n'est pas un maximum local. Il faut ensuite effectuer un seuillage par hystérésis. Pour cela on fixe deux seuils, un seuil haut s_h et un seuil bas s_b. On commence par sélectionner les points qui dépassent le seuil haut et on applique ensuite le seuil bas en ne conservant que les composantes connexes qui contiennent un point au-dessus de s_h. En d'autres termes à partir de chaque point au-dessus de s_h on "suit" un chemin constitué de points au-dessus de s_b, ce chemin est le contour recherché.

Dérivée seconde

A priori, l'utilisation des dérivées secondes est plus commode que celle des dérivées premières : au lieu de chercher les maximums de l'intensité du gradient, on cherche l'annulation du laplacien, somme des dérivées secondes dans deux directions, soit N + S + E + W - 4C. La contrepartie de la simplicité est l'amplification du bruit par la seconde dérivation. Ce bruit est atténué par l'adjonction d'un filtre gaussien mais les méthodes du second ordre ne semblent pas compétitives avec celles du premier ordre évoquées précédemment.

Applications

La détection de contour est très utile en traitement d'images, c'est par exemple une étape indispensable à la reconnaissance de formes. Ces algorithmes sont également utilisés en imagerie médicale, cartographie, ...

Voir aussi

• Connectivité (géométrique)
• Modèle de contour actif

Références

1. ↑ J. Canny, A Computational Approach to Edge Detection, IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol 8, No. 6, Nov 1986

• J. Canny, A Computational Approach to Edge Detection, IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol 8, No. 6, Nov 1986
• H. Maître, La détection de contour dans les images, http://www.tsi.enst.fr/~bloch/TDI/poly_contours.pdf
• S. Mavromatis, O. Coulon, Analyse d'image, http://pages-perso.esil.univ-mrs.fr/~ocoulon/cours/ESIL3A_contours.pdf
• F. Devernay, Détection de contour, http://devernay.free.fr/cours/vision/pdf/c3.pdf
• Image Processing Fundamentals, http://www.ph.tn.tudelft.nl/Courses/FIP/noframes/fip.html