Filtre de Canny

Image originale

Image résultante de l'application du filtre de Canny

Le filtre de Canny (ou détecteur de Canny) est utilisé en traitement d'images pour la détection des contours. L'algorithme a été conçu par John Canny en 1986 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

Image obtenue après application d'un flou gaussien 5x5.

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 l'article Lissage d'images), dont voici l'opérateur de convolution :

$\mathrm {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 renvoie l'intensité des contours. L'opérateur utilisé permet de calculer le gradient suivant les directions X et Y, il est composé de deux masques de convolution, un de dimension 3 × 1 et l'autre 1 × 3 :

$\mathrm {G} _{x}={\begin{bmatrix}-1&0&1\end{bmatrix}}\qquad ;\qquad \mathrm {G} _{y}={\begin{bmatrix}1\\0\\-1\end{bmatrix}}$

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

$|\mathrm {G} |=|\mathrm {G} _{x}| |\mathrm {G} _{y}|$

et la valeur exacte est :

$|\mathrm {G} |={\sqrt {\mathrm {G} _{x}^{2} \mathrm {G} _{y}^{2}}}$

Direction des contours

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

$\theta =\pm \arctan \left({\frac {\mathrm {G} _{y}}{\mathrm {G} _{x}}}\right)$

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 selon les lignes de champs du gradient s'annule.

Seuillage des contours

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

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. Toutefois, il existe des méthodes statistiques permettant d'obtenir automatiquement une valeur du seuil haut convenable (Ch Ho) , la valeur du seuil bas étant un pourcentage du seuil haut.

Bibliographie

• [Canny 1986] (en) J. Canny, « A Computational Approach To Edge Detection », IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 8,‎ 1986, p. 679-698.

Références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Canny_edge_detector » (voir la liste des auteurs).

Voir aussi

Articles connexes

• Transformée de Hough

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