Détection de contours

En traitement d'image et en vision par ordinateur, on appelle détection de contours les procédés permettant de repérer les points d'une image matricielle qui correspondent à un changement brutal de l'intensité lumineuse. Ces changements de propriétés de l'image numérique indiquent en général des éléments importants de structure dans l'objet représenté. Ces éléments 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 des contours dans une image réduit de manière significative la quantité de données en conservant des informations qu'on peut juger plus pertinentes. Il existe un grand nombre de méthodes de détection des contours 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 changement brutal de la valeur caractérise un contour. Le but de l'opération est de transformer cette image en une autre de mêmes dimensions 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

$\mathrm {D} _{x}=E-W,$

$\mathrm {D} _{y}=N-S.$

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

$\mathrm {D} _{x}^{2}=(E-C)-(C-W)=E+W-2C,$

$\mathrm {D} _{y}^{2}=(N-C)-(C-S)=N+S-2C.$

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. Canny a défini trois critères pour obtenir un filtre optimal pour la détection de contours :

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

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

Filtre 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 sont pas aussi compétitives que celles du premier ordre évoquées précédemment^{[réf. souhaitée]}.

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, etc.

Articles connexes

• Connectivité (géométrique)
• Modèle de contour actif
• Segmentation d'image

Références

• (en) J. Canny, « A Computational Approach to Edge Detection », IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 8, n^o 6,‎ novembre 1986, p. 679–714
• Henri Maître, « La détection de contour dans les images »
• Henri Maître, « 10. La détection de contour dans les images », dans Henri Maître (dir.), Le traitement des images, Hermès Sciences, 2003 (lire en ligne)
• S. Mavromatis, O. Coulon, Analyse d'image, [1]
• F. Devernay, Détection de contour, [2]
• Image Processing Fundamentals, [3]