Algorithme De Canny

Algorithme de Canny

L'algorithme de Canny (1986) est utilisé en traitement ou en analyse d'image pour la détection des contours. L'auteur l'a conçu pour être optimal suivant trois critères clairement explicités :

1. bonne détection : faible taux d'erreur dans la signalisation des contours,
2. bonne localisation : minimisation des distances entre les contours détectés et les contours réels,
3. clarté de la réponse : une seule réponse par contour et pas de faux positifs

Mise en œuvre

Réduction du bruit

La première étape est de réduire le bruit de l'image originale avant d'en détecter les contours. Ceci permet d'éliminer les pixels isolés qui pourraient induire de fortes réponses lors du calcul du gradient, conduisant ainsi à de faux positifs.

Un filtrage gaussien 2D est utilisé (voir Lissage de l'image), dont voici l'opérateur de convolution :

$G(x,y)=\frac{1}{2\pi\sigma^2}e^{-\frac{x^2+y^2}{2\sigma^2}}$

et un exemple de masque 5×5 discret avec σ=1,4 :

$h=\frac{1}{159}\begin{bmatrix} 2 & 4 & 5 & 4 & 2\\ 4 & 9 & 12 & 9 & 4\\ 5 & 12 & 15 & 12 & 5\\ 4 & 9 & 12 & 9 & 4\\ 2 & 4 & 5 & 4 & 2 \end{bmatrix}$

Usuellement, un filtre est de taille plus réduite que l'image filtrée. Plus le masque est grand, moins le détecteur est sensible au bruit et plus l'erreur de localisation grandit.

Gradient d'intensité

Après le filtrage, l'étape suivante est d'appliquer un gradient qui retourne l'intensité des contours. L'opérateur utilisé permet de calculer le gradient suivant les direction X et Y, il est composé d'une paire de deux masques de convolution, un de dimmension 3×1 et l'autre 1×3:

$G_x = \begin{bmatrix} -1 & 0 & 1 \end{bmatrix}\qquad;\qquad G_y = \begin{bmatrix} 1 \\ 0 \\ -1 \end{bmatrix}$

La valeur du gradient en un point est approximée par la formule :

| G | = | G_x | + | G_y |

Direction des contours

Les orientations des contours sont déterminés par la formule :

$\theta = arctan(\frac{G_x}{G_y})$

Nous obtenons finalement une carte des gradients d'intensité en chaque point de l'image accompagnée des directions des contours.

Suppression des non-maxima

La carte des gradients obtenue précédemment fournit une intensité en chaque point de l'image. Une forte intensité indique une forte probabilité de présence d'un contour. Toutefois, cette intensité ne suffit pas à décider si un point correspond à un contour ou non. Seuls les points correspondant à des maxima locaux sont considérés comme correspondant à des contours, et sont conservés pour la prochaine étape de la détection.

Un maximum local est présent sur les extrema du gradient, c'est-à-dire là où sa dérivée s'annule.

Seuillage des contours

La différenciation des contours sur la carte générée se fait par seuillage à hysteresis.

Cela nécessite deux seuils, un haut et un bas; qui seront comparés à l'intensité du gradient de chaque point. Le critère de décision est le suivant. Pour chaque point, si l'intensité de son gradient est:

• Inférieur au seuil bas, le point est rejeté;
• Supérieur au seuil haut, le point est accepté comme formant un contour;
• Entre le seuil bas et le seuil haut, le point est accepté s'il est connecté à un point déjà accepté.

Une fois ceci réalisé, l'image obtenue est binaire avec d'un côté les pixels appartenant aux contours et les autres.

Paramètres

Les deux paramètres principaux déterminant le temps de calcul et l'acuité de l'algorithme sont la taille du filtre gaussien et les deux seuils.

• Taille du filtre: le filtre utilisé lors de la réduction du bruit a une influence directe sur le comportement de l'algorithme. Un filtre de petite taille produit un effet de flou moins prononcé, ce qui permet la détection de petites lignes bien marquées. Un filtre de taille plus grande produit un effet de flou plus important, ce qui permet de détecter des contours moins nets, par exemple celui d'un arc-en-ciel.

• Seuils: l'utilisation de deux seuils au lieu d'un améliore la flexibilité mais certains problèmes propres au seuillage demeurent. Ainsi, un seuil trop bas peut conduire à la détection de faux positifs. Inversement, un seuil trop haut peut empêcher la détection de contours peu marqués mais représentant de l'information utile.

Il n'existe pas actuellement de méthode générique pour déterminer des seuils produisant des résultats satisfaisants sur tous les types d'images.

Une démonstration en ligne (anglais) peut être utilisée pour étudier l'influence des paramètres: http://matlabserver.cs.rug.nl

Références

• Canny, J., A Computational Approach To Edge Detection, IEEE Trans. Pattern Analysis and Machine Intelligence, 8:679-714 (1986).

Liens externes

• Une démonstration en images : http://robotics.eecs.berkeley.edu/~sastry/ee20/cademo.html
• Une application en ligne permettant d'expérimenter l'algorithme : http://matlabserver.cs.rug.nl

• (en) Cet article est partiellement ou en totalité issu d’une traduction de l’article de Wikipédia en anglais intitulé « Canny ».

Ce document provient de « Algorithme de Canny ».