Algorithme de Canny

Un article de Wikipédia, l'encyclopédie libre.

Cet article est une ébauche concernant la photographie.

Vous pouvez partager vos connaissances en l’améliorant. (Comment ?).

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 :

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

[modifier] Mise en œuvre

[modifier] 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 :

$\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.

[modifier] Gradient d'intensité

Après le filtrage, l'étape suivante est d'appliquer un gradient qui retourne l'intensité des contours. L'opérateur de Sobel est utilisé, il est composé d'une paire de deux masques de convolution 3×3, un par direction spatiale :

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

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

| G | = | G x | + | G y |

[modifier] Direction des contours

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

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

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

[modifier] 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.

[modifier] 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.

[modifier] 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