Sandrine Augais - Richard Chevalier - Vincent Domurado

Projet Méthodes de Base d'Analyse des Images

Comparaison des critères de Canny, Spacek, Tagare et Figueiredo pour l’évaluation des performances des détecteurs de contours

Sommaire :

I. Une approche commune aux auteurs, celle de Canny : définition de critères numériques d’évaluation des performances des détecteurs

        La détection de contours en traitement de l’image est essentielle car elle permet une réduction drastique de la quantité d’information relative à une image, tout en préservant des informations structurelles comme les contours et les frontières des images.

        Pour évaluer et comparer les performances relatives des divers détecteurs de contours existant, Canny a publié en 1986 trois critères numériques à optimiser pour obtenir la réponse impulsionnelle d’un filtre linéaire mono-dimensionnel qui soit le meilleur détecteur de contours possibles, selon ces critères, et qu’il adapte ensuite en 2 dimensions. Suivi par Spacek, Tagare et Figueiredo, Canny établit les bases de travail et définit un cadre dans lequel ses critères prennent un sens.

        Il s’agit de pouvoir détecter dans une image un contour constitué par l’addition d’une marche d’escalier (le contour le plus simple et le plus courant) et d’un bruit blanc gaussien. Un tel contour est détecté au niveau des maxima locaux présents dans l’image en sortie du filtre linéaire.

        Mais ces auteurs diffèrent quant au choix des critères à optimiser, quant à l’importance relative à accorder à chacun de ces critères, quant aux conditions aux limites à adopter et les filtres optimaux qu’ils proposent ne sont pas toujours identiques, du moins ont des performances différentes selon les critères retenus.

        Canny constate à quel point il est difficile de comparer différents opérateurs de détection entre eux. Il est en effet toujours possible de trouver une image pour laquelle les résultats d’un auteur donné seront mauvais. Dépendamment de l’image, des critères comme :

• l’interaction entre des contours trop proches ou formant des coins
• la variabilité des profils de luminance le long du contour
• la sensibilité de la position des contours détectés au bruit

peuvent faire différer des résultats de façon conséquente et conduire à la mauvaise appréciation d’un détecteur comparativement à un autre.

        Cependant, Canny établit trois critères quantitatifs numériques destinés à évaluer les performances des détecteurs de contours les uns par rapport aux autres.

I.1. Formulation mono-dimensionnelle du problème

        Pour simplifier le problème de la détection de contours, Canny se place d’abord dans le cadre mono-dimensionnel. Cela revient à considérer que les contours en 2 dimensions ont localement une section constante dans leur direction. Ceci s’applique très bien aux contours de type marche d’escalier, rampe ou toit, mais pas aux coins.



        Dans sa formulation mono-dimensionnelle, il s’agit de trouver la réponse impulsionnelle f d’un filtre avec laquelle convoluer la luminance de l’image dans une direction x. f caractérise la forme spatiale de l’opérateur et détermine le poids pondérant chaque pixel situé à une distance x du centre de l’opérateur. L’opérateur de " pondération-convolution " agit dans une fenêtre [-W ;W]. Un point sera détecté comme étant le centre du contour si la réponse de l’image en sortie du filtre de convolution est maximale pour ce point.

        Soit g(x) le profil d’intensité observé de notre image mono-dimensionnelle. Il est supposé constitué d’une marche d’escalier idéale d’amplitude A, centrée en x=0, et d’un bruit blanc gaussien n(x), de densité spectrale de puissance n₀ :

g(x)=A u(x) + n(x), avec :



        Définir un détecteur de contours revient à déterminer un filtre linéaire dont la réponse impulsionnelle f(x) est telle que la localisation du contour dans g(x) correspond au maximum de la réponse y(x), en sortie du filtre :

y(x)=g(x)*f(x)

        Canny choisit un filtre correspondant à une première dérivée spatiale afin de présenter une réponse nulle pour un signal d’entrée constant : f(x) doit être une fonction antisymétrique.

I.2. Critères de performance

Les performances d’un détecteur de contours sont évalués par Canny à partir des critères suivants :

• Critère de bonne détection : la probabilité de ne pas détecter un vrai contour ou de détecter un contour là où il n’y en a pas doit être minimisée, pour un rapport signal sur bruit donné en entrée du filtre. Or cette probabilité est fonction décroissante du rapport signal sur bruit en sortie du filtre détecteur. Un bon détecteur doit maximiser ce rapport.
   
• Critère de bonne localisation de la réponse : les points x₀ détectés comme points de contour par l’opérateur doivent être situés aussi près que possible du centre du véritable contour (ici en l’occurrence x=0). Plus la variance de la distance x₀ du maximum de la réponse y(x) au centre réel du contour est faible, plus le détecteur assure une localisation correcte du contour . Un bon détecteur doit maximiser l’inverse de cette variance.
   
• Critère d’unicité de la réponse à un contour unique : un point du contour ne doit être détecté qu’un seule fois par le filtre mis en œuvre. Ce critère est inclus implicitement dans le premier critère puisque si l’on détecte deux contours là où il n’y en a qu’un, une des deux réponses doit être considérée comme fausse. Cependant, la forme mathématique choisie pour le premier critère ne met pas en évidence cette condition : elle ne mesure que la capacité du filtre à distinguer le signal du bruit au centre du contour. Elle ne prend pas en compte le comportement du filtre dans son voisinage. Les auteurs choisissent donc d’écarter au maximum la distance entre les maxima de la réponse du filtre au bruit, pour limiter le nombre de réponses multiples lorsqu’il y a un unique contour réel.

        Nous allons maintenant détailler la formulation mathématique de ces trois critères telle qu’elle a été faite par Canny. C’est en effet cette formulation qui a servi de base et de support principal aux travaux de Spacek et Tagare et Figueiredo.

I.2.1. Critère de bonne détection

La sortie de notre filtre au centre du contour est donnée par :



Le rapport signal sur bruit en sortie est donné par la valeur de la réponse au centre du contour (en x=0), sur la réponse au bruit seul :



Canny choisit alors un critère indépendant des puissances de la marche d’escalier et du bruit :

I.2.2. Critère de bonne localisation

Le produit de convolution en sortie du filtre s’écrit:

(1)

où v (x) est la réponse à la marche d’escalier et z (x) la réponse au bruit seul.

        La démarche de Canny est la suivante : en supposant que nous avons détecté un contour en x₀ (maximum de la réponse en sortie du filtre), nous avons : y’(x₀)= v ’(x₀ )+ z ’(x₀) = 0.

Or v ’(x₀) = -A f(x₀) =A f(-x₀).

        De plus, la réponse du filtre à la marche d’escalier non bruitée est nulle par hypothèse en x=0, et le contour détecté est supposé proche du centre du contour réel (x=0). D’après la formule de Taylor au voisinage de 0 :

-f(x₀) » -f(0) -x₀f’(0) = - x₀ f’(0)

puis (3)

Finalement,

(4)

et comme :

(5)

Canny obtient ainsi la variance de x₀ :

(6)

        La mesure de bonne localisation proposée est l’inverse de l’écart-type de x₀, en supprimant les effet de la puissance du bruit et du signal d’entrée pour que cette mesure ne caractérise que l’opérateur f(x) :

I.2.3. Critère d’unicité de la réponse à un contour unique

        La forme analytique de la réponse au signal, dans le premier critère de Canny, ne prend en compte que la sortie du filtre au centre du contour, sans s’intéresser aux contributions d’autres réponses, éventuellement également localement maximales, dans le voisinage du centre du contour. Or ces maxima peuvent être très proches les uns des autres sans qu’il soit possible de savoir lequel est associé à la réponse de la marche d’escalier, ou lequel est dû au bruit.

        C’est pourquoi Canny instaure un troisième critère dans le but de limiter le nombre de pics non pertinents dans la réponse. Pour cela, il calcule la distance moyenne x_max entre deux maxima de la réponse impulsionnelle du filtre (égale au double de la distance moyenne entre deux zéros de la dérivée première de la réponse du filtre) à un bruit blanc gaussien :



        Idéalement cette distance devrait être de l’ordre de grandeur de la taille de la réponse du filtre à une marche seule pour ne pas confondre deux réponses adjacentes. En pratique, Canny impose que cette distance soit une fraction k de la taille spatiale de l’opérateur. Le nombre N de maxima dus au bruit dans une région de taille 2W est alors fixé à :

I.3. Propriétés de changement d’échelle

        Notons w>1 le facteur de changement d’échelle spatiale et K le facteur de changement d’amplitude tels que :
x_w = w x et f_w (x_w) = K f(x)

        Alors il y a invariance des deux premiers critères de Canny par changement d’échelle en amplitude mais une variation avec le changement d’échelle spatial en   ou  :

I.4. Récapitulatif des critères combinés de Canny

        Le détecteur optimal de Canny est celui qui permet de maximiser les deux premiers critères de Canny , tout en gardant une valeur constante (déterminée par k fixé), pour le troisième critère de limitation du nombre de réponses multiples. La façon la plus simple, adoptée par Canny pour maximiser chacun de ces deux critères est d’en maximiser le produit S * L, qui a cette fois la propriété d’invariance par changement d’échelle spatiale.

I.5. Résolution de l’optimisation des critères de Canny

Canny recherche la fonction f qui maximise :


où P_i est une fonction positive lorsque la i^ème contrainte est non vérifiée. Toutes les intégrales (isopérimétriques) intervenant dans la combinaison des critères sont fixées égales à une valeur constante indéterminée, sauf une. La méthode des multiplieurs de Lagrange est employée, une fonction composite est ensuite créée, faisant intervenir x, f, f’, f’’, à laquelle on peut appliquer le calcul variationnel (équation d’Euler Lagrange).

La solution générale obtenue dans [-W ;0] est de la forme :



a1, a2, a3, et a4 sont déterminés à partir des conditions limites, en fonction de a, b, w, qui sont les 3 paramètres déterminant le filtre détecteur de contour de Canny.

Remarque : , où f’(0)=s.

Le choix des paramètres a, b, w conditionnent les performances S (f)*L(f) et x_max du filtre détecteur.

        Canny estime que le choix d’un filtre dont la réponse impulsionnelle serait la dérivée d’une gaussienne ne détériore les performances du filtre optimal trouvé que de 20 %. Or ce filtre est plus facilement implantable en 2 dimensions (c’est d’ailleurs le seul que Canny a implémenté, se contentant seulement de calculer la valeur de son critère d’optimisation pour les véritables filtres optimaux qu’il a obtenus dépendamment de a, b , w ).

I.6. Passage en deux dimensions

        Nous avons montré plus haut quelle était l’approche commune des auteurs pour la définition d’un filtre de détection des contours en dimension 1, et donné en particulier les critères de Canny (base de ceux de Spacek, et Tagare et Figueiredo). Le passage au contexte réel des images, c’est-à-dire au travail en 2 dimensions est fait de façon très similaire par Canny et Spacek. C’est ce que nous voulons détailler dans cette partie.

I.6.1. Approche de Canny

        Canny propose de créer un filtre qui corresponde à son filtre mono-dimensionnel dans la direction orthogonale au contour que l’on cherche à détecter et à un filtre passe-bas dans la direction du contour, afin d’assurer la continuité de celui-ci. Pour simplifier les calculs, il choisit pour ce filtre passe-bas une gaussienne de même largeur que la dérivée de gaussienne utilisée pour détecter les contours. Cette opération est effectuée grâce à une convolution de l’image par une gaussienne en 2 dimensions (ce qui est aisé à faire car la gaussienne est séparable et a de plus le mérite d’être une opération isotrope) dont il dérive le résultat dans la direction orthogonale au contour. En effet : .

        Dans la pratique, il n’est pas nécessaire d’effectuer cette dérivation dans toutes les directions de l’image pour détecter les contours dans chacune d’entre elles : il suffit de l’appliquer dans deux directions orthogonales. Cela se résume donc à appliquer un filtre gaussien bi-dimensionnel à l’image puis à dériver le résultat dans deux directions orthogonales. Les maxima de ces deux nouvelles images correspondent aux contours dans deux directions orthogonales.

I.6.2. Approche de Spacek

        L’opérateur f(x) de détection des contours mono-dimensionnel de Spacek étant antisymétrique, il est impossible de le généraliser au cas bi-dimensionnel par simple rotation. Sa primitive h(x) est quant à elle symétrique, il est donc possible de la remplacer par h(r) pour traiter le cas 2D, r étant la distance du point considéré au centre du filtre. Cette fonction h(r) remplace la gaussienne proposée par Canny, de la même manière que la fonction f(x) remplace la dérivée de gaussienne. Le traitement est le même par la suite : on effectue la convolution de l’image originale par cet opérateur, puis on cherche les maxima de la dérivée dans deux directions orthogonales de la réponse de ce filtrage. Ceux-ci correspondent aux contours.

I.6.3. Conclusion

        Il n’y a donc pas d’autre différence dans les approches adoptées par Canny et Spacek pour le passage d’un opérateur mono-dimensionnel à un opérateur bi-dimensionnel que le choix préalable de la fonction optimale qui corresponde à leurs critères. Ce sont ces divergences de critères que nous donnons dans la deuxième partie.

        L’approche générale suivie par Canny, Tagare et Figueiredo, et enfin par Spacek est similaire (volonté de quantifier les performances des détecteurs de contours), mais ils retiennent différents critères au final. Nous allons examiner en quoi il y a divergence entre ces auteurs, en nous positionnant par rapport aux critères de Canny décrits dans la première partie, et en utilisant les mêmes notations.

Retour au sommaire

II.1. Critère de Tagare et Figueiredo

        Tagare et Figueiredo prennent pour filtre la dérivée d’une gaussienne et montrent qu’il est possible que la dérivée de la sortie du filtre, y’(x), s’annule non pas une seule mais plusieurs fois. Ils rejettent le critère de localisation de Canny en estimant que celui-ci ne tient compte que d’une seule annulation et qu’il n’y a priori pas de raison que les autres zéros de y’ ne puissent pas contribuer à une meilleure localisation du contour. De plus le choix de la mesure de bonne localisation ne peut reposer sur le calcul de la variance moyenne de la distance au carré entre le centre réel (x=0) du contour et le centre détecté (x=x₀), car d’une réalisation à l’autre du processus gaussien x ’(x), la valeur de x₀ change et on ne peut donc pas substituer systématiquement (5) dans (6).

        Selon eux, pour pouvoir définir un critère de localisation réellement pertinent il faut s’intéresser de plus près à la distribution des zéros de y’.

Retour au sommaire

II.1.1. Distribution des maxima de y(x)

        Partant de la remarque que si y’(x)>0 et y’(x+dx)<0 et si dx est suffisamment petit, y’ ne s’annule qu’une seule fois entre x et x+dx, Tagare et Figueiredo estiment la probabilité P d’avoir effectivement un maximum de y sur [x ; x+dx] :

P = P{y’(x)>0 et y’(x+dx) <0}
   = P{v ’(x)+ z ’(x)>0 et v ’(x+dx)+ z ’(x+dx)<0}

P » P{v ’(x)+ z ’(x)>0 et v ’(x)+ z ’(x+dx)<0}
   = ½ P{[z ’(x)-v ’(x)][z ’(x+dx)-v ’(x)]<0}

        z (x) étant un processus gaussien, z ’(x) et z ’(x+dx) sont également deux processus gaussiens de moyenne nulle et de même variance. Tagare et Figueiredo obtiennent après quelques calculs :

(7)

où Rz _’ est la fonction d’auto-corrélation de z ’.

Soit m (x) la densité de maxima de y(x). Alors :

        L’équation (7) montre que la densité spatiale de maxima décroît lorsque f²(x) augmente et qu’elle atteint son maximum lorsque x=0. La densité relative de maxima m _rel(x) est définie comme le rapport de m (x) et de m _max.

Retour au sommaire

II.1.2. Nouveau critère de localisation selon Tagare et Figueiredo

        Le filtre recherché ayant une bande spatiale limitée, par hypothèse, la densité de maxima s’annule également en dehors de cette bande (lorsque f(x) s’annule). Ceci ne pose en fait pas vraiment de problème car la détection de contours n’est effectuée par Tagare et Figueiredo que dans une région limitée pour laquelle la sortie du filtre dépasse un seuil fixé.

        Le filtre f(x) présente une densité de maxima maximale en x=0, c’est à dire au centre du vrai contour. Plus on s’éloigne de ce centre, plus la densité de maxima diminue. C’est pourquoi Tagare et Figueiredo proposent comme nouvelle mesure du critère de localisation :

(8)

        Q est une moyenne de la distance x au carré séparant un point du centre réel du contour, pondérée par la probabilité 1-m _rel(x) (quantité toujours comprise entre 0 et 1) que ce point soit ou non un maximum de la sortie du filtre détecteur appliquée à l’image, donc par la probabilité que ce point soit le centre observé du contour, contribuant ainsi plus ou moins fortement à sa localisation.

        En supposant que le rapport signal sur bruit en entrée du filtre est petit, ce qui revient à dire que f²(x)/2s ^2z _’ est très petit devant 1, il vient alors :

(9)

        Q dépendant de la densité spectrale n₀ du bruit, Tagare et Figueiredo défissent leur nouveau critère de localisation (critère à maximiser) comme le rapport :

Retour au sommaire

II.1.3. Filtre optimal de Tagare et Figueiredo

        Il s’agit de trouver une filtre à réponse impulsionnelle finie f(x) maximisant le critère de localisation de Tagare et Figueiredo, à bande spatiale finie et tel que f(x) soit une fonction antisymétrique. Tagare et Figueiredo, s’appuyant sur les travaux de V.Torre et T.Poggio, montrent que le filtre maximisant L_TF est la dérivée de gaussienne.

Retour au sommaire

II.1.4. Divergences entre Canny  et Tagare et Figueiredo

        Il y a principalement deux différences avec l’approche de Canny. Tout d’abord Tagare et Figueiredo définissent un nouveau critère de localisation de contours basé sur une approche probabiliste de la densité de zéros de la dérivée en sortie du filtre. La deuxième différence vient du fait que la recherche du filtre optimal se fait par rapport à cet unique critère de localisation et non plus par rapport aux trois critères combinés de Canny (bonne localisation, bonne détection, limitation du nombre de réponses multiples).

        Cependant, aussi bien Canny que Tagare et Figueiredo préconisent au final l’usage d’un filtre détecteur de réponse impulsionnelle égale à la dérivée d’une gaussienne. Canny réalise cependant que ce filtre, pas plus que le filtre optimal trouvé avec une combinaison de paramètres a , b , w judicieusement choisie, "  ne doivent être considérés comme ce qui existe de mieux dans le domaine des filtres détecteurs de contours ", alors que Tagare et Figueiredo présentent le filtre dérivée de gaussienne comme l’unique filtre maximisant leur critère, s’appuyant sur une preuve mathématique.

Retour au sommaire

II.2. Critères de Spacek

        Spacek reprend tels quels les deux premiers critères de bonne détection et de bonne localisation de Canny. Il insiste cependant sur la nécessité de choisir un filtre à réponse impulsionnelle finie (dans [-W ;W]), et sur le choix des conditions limites (voir II.3.). Il insiste également particulièrement sur les propriétés de changement d’échelle des critères. La divergence avec Canny concerne l’examen du troisième critère.

        Dans le but d’avoir le moins possible de maxima détectés dans la réponse en sortie du filtre mais ne correspondant pas au centre d’un contour réel, et d’éviter des problèmes tels que le regroupement de lignes voisines, Spacek recherche une mesure lui permettant de discriminer au mieux un contour réel par rapport au bruit.

II.2.1. Nouveau critère de limitation des réponses multiples à un contour simple

        Canny chercher à limiter le nombre de maxima locaux N dus au bruit dans une région de taille 2W c’est-à-dire le nombre de pics en sortie du filtre détecteur, en imposant que la distance x_max entre deux maxima soit une fraction k de la taille W de la fenêtre spatiale du filtre, fixant ainsi le nombre de maxima détectés à N=2W/x_max . Plutôt que de limiter à une quantité fixée à l’avance ce nombre de maxima, Spacek souhaite le minimiser et pour cela maximiser la distance x_max . L’expression déjà donnée trouvée par Canny pour la distance x_max est :



        Cette expression avait été obtenue en utilisant un résultat de Rice concernant la distance moyenne entre deux zéros de la dérivée de la sortie d’un filtre due uniquement à un bruit gaussien. Compte tenu de la volonté d’obtenir un filtre RIF, Spacek adapte l’expression de x_max en changeant les bornes d’intégration et en utilisant la symétrie de f’² et f’’².



La mesure à maximiser selon Spacek est alors définie de la manière suivante : C₁(f)=x_max / p .

Par un changement d’échelle f_w(x_w) = K f(x), on obtient : C₁(f_w) = w C₁(f)

        Or seules les propriétés de limitation du nombre de réponses indépendantes de la taille spatiale du filtre f doivent être prises en compte (il est en effet normal qu’un opérateur plus large, donnant lieu à une réponse plus étalée, permette d’améliorer la mesure C₁). La mesure finale définit par Spacek, à maximiser, et indépendante de la taille spatiale de l’opérateur est choisie égale à :

C(f_w) = C₁(f_w) / w = C₁(f)

II.2.2. Filtre optimal de Spacek

        Avec ce nouveau critère C(f_w) et les deux premiers critères similaires à ceux de Canny, Spacek définit une contrainte plus générale à vérifier pour le filtre optimal. Il s’agit de maximiser les trois critères à la fois, en particulier Spacek cherche à maximiser le produit P(f) des trois critères :

P(f) = S (f)L(f)C(f)

Il est intéressant de remarquer :

• que P(f_w)=P(f) (invariance du critère combiné à optimiser par changement d’échelle spatiale). La maximisation du produit P(f_w) ne dépend que de la forme de l’opérateur f canonique tel que f_w(x_w) = K f(x) et non pas de sa demie largeur spatiale w.
• qu’il y a simplification de l’intégrale par la mise en produit des trois critères, ce qui n’était pas le cas lors de la mise en produit par Canny de ses deux premiers critères seulement. Cela facilite la résolution de l’optimisation par Spacek.

Résolution de l’optimisation des critères de Spacek :

        La démarche est la même que celle décrite ci –dessus pour la résolution de l’optimisation de Canny. La fonction composite créée à partir des multiplieurs de Lagrange ne fait plus intervenir que f_w², f_w’’² et f_w, puisque l’intégrale en f_w’² est simplifiée. L’équation d’Euler-Lagrange qui en résulte est elle aussi plus simple et la forme de la solution générale à laquelle aboutit Spacek est alors :

        Un choix simplificateur des constantes arbitraires, c=1/w et K₅=k, permet de se ramener de f_w à f canonique telle que :

        Il nous faut ici faire remarquer que Canny et Spacek obtiennent bien deux formes de solution générale distinctes car les arguments de l’exponentielle et des fonctions trigonométriques est ici similaire, ce qui n’est pas le cas pour la forme de la solution générale de Canny.

        A l’aide des conditions limites (voir II.3.) , Spacek détermine les constantes C₁, C_2, C_3, C₄. Il est alors en mesure de chiffrer pour ce filtre optimal les valeurs de chacun des critères qu’il a définis ainsi que de son critère combiné.

        Spacek implémente réellement son filtre optimal. Il fournit cependant également une fonction pour réponse impulsionnelle du filtre détecteur, très simple, sous forme de spline cubique dont les performances atteignent 99,9% de celles de son filtre optimal, pour le critère combiné qu’il a défini.

Retour au sommaire

II.3. Conditions aux limites

        Lors de la recherche du filtre linéaire optimal vérifiant leurs critères d’optimalité, Canny et Spacek débouchent tout deux sur une équation différentielle d’ordre 4. Une nouvelle différence entre Canny et Spacek se situe alors au niveau de la détermination des quatre constantes d’intégration, car elle se fait à l’aide de conditions aux limites différentes.

Canny utilise les conditions aux limites suivantes :

-         f(0)=0

-         f(-W)=0 

-         f’(-W)=0 

-         f’(0)=s où s est une constante prédéfinie, égale à la pente à l’origine du filtre   

        Spacek quant à lui reprend les 3 premières conditions aux limites de Canny et utilise en plus le fait que le maximum d’amplitude de f(x) est égal à 1. Soit x_m le point ou l’amplitude est maximale, on a alors :

-         f(x_m) =1

-         f’(x_m) =0

        Pour une nouvelle inconnue, deux équations supplémentaires sont introduites ce qui permet à Spacek de lever toutes les indéterminations de sa solution générale.

Retour au sommaire

Nos conclusions

        Le but de notre sujet était de comparer la pertinence des critères utilisés par les auteurs pour définir un détecteur optimal. Les divergences de critères que nous avons extraites plus haut sont, en résumé :

• Pour Tagare et Figueiredo : un filtre optimisant un unique critère de localisation L_TF qui tient compte d’une distribution probabiliste de la densité de maxima observés en sortie du filtre détecteur.

• Pour Canny : un filtre qui optimise le produit combiné du critère de bonne détection S et du critère de bonne localisation L, tout en imposant un nombre de réponses multiples fixé à l’avance.

• Pour Spacek : un filtre qui optimise un critère encore plus général, produit combiné de trois critères : bonne détection , bonne localisation, nombre de réponses multiples minimal pour un contour réel unique.

        Notre démarche n'avait pas pour objectif de comparer les résultats fournis, pour une même image initiale, par des filtres optimisant les critères de chacun des auteurs. De toute façon, si nous avions voulu faire cela, encore aurait-il fallu que chacun de ces filtres optimaux soient facilement implémentables. Ce n’était pas le cas. En effet, Canny implémente uniquement un filtre (de réponse impulsionnelle égale à la dérivée de gaussienne) approchant les performances de son filtre optimal à 80%. Il se trouve que ce filtre dérivée gaussienne est LE filtre optimal préconisé par Tagare et Figueiredo, et il devient dès lors difficile de pouvoir comparer expérimentalement la pertinence de leurs deux critères si nous ne disposons que de deux filtres identiques dans la pratique. La seule comparaison expérimentale possible est donc la comparaison entre les résultats fournis par le filtre optimal de Spacek (implémenté par nos camarades des années précédentes) et le filtre dérivée de gaussienne tronqué, de Canny, dont nous avons trouvé une version sur le web, que nous avons adapté au format d’images de l’ENST " .ima " (voir en Annexe). Dans la pratique, cette deuxième implémentation donne de bien meilleurs résultats que la première car elle utilise un seuillage par hystérésis qui supprime du bruit et conserve la continuité des contours.

        En résumé, il nous a semblé que l’implémentation pratique présentait déjà de tels écarts avec les spécifications théoriques optimales préconisées par les auteurs (particulièrement Canny) qu’il devenait très difficile de pouvoir juger avec une étude pratique des petites divergences théoriques concernant le choix des critères. Ces écarts sont dus à diverses choses : les filtres sont à réponse impulsionnelle finie, et il faut donc, dans le cas de la dérivée de gaussienne choisir une troncature adéquate au delà de laquelle la valeur de la fonction tombe au dessous d’une certaine fraction de sa valeur crête. Or les valeurs des intégrales intervenant dans les mesures des critères de Canny appliqués au filtre dérivée de gaussienne sont calculées avec des bornes infinies. Il y a là un décalage entre mise en œuvre pratique du filtre et performances théoriques qui lui sont faussement attribuées. Il en est de même pour le filtre (également dérivée de gaussienne) préconisé par Tagare et Figueiredo, optimal pour leur critère de localisation, à condition qu’il s’agisse d’une gaussienne non tronquée (la preuve mathématique qu’ils exhibent tient en effet compte de bornes infinies dans les intégrales de L_TF). Il ne nous est pas dit que le filtre dérivée de gaussienne tronqué soit réellement optimal pour ce critère de localisation. De plus, les paramètres intervenant dans la mise en œuvre du filtre dérivée de gaussienne pour Canny et du filtre optimal de Spacek sont très dépendants des images et il est difficile de se placer dans un contexte de comparaison rigoureuse.

        Avant de faire tourner ces deux implémentations sur quelques images, dans le but de justifier le choix des auteurs quant à leurs critères (éviter les effets de rebond, de confusion de contours proches ...), il nous semble important de revenir sur l’étude comparative qu’a menée Spacek dans son article entre son filtre et les filtres dérivées de gaussienne : pour le filtre dérivée de gaussienne de Canny et Tagare et Figueiredo, tronqué de telle sorte que seules les valeurs de la gaussienne inférieures à un millième de la valeur crête ne soient pas prises en compte, la valeur de P(f) n’atteint que 47 % de la valeur correspondante pour le filtre optimal de Spacek. Même pour une troncature de la gaussienne moins sévère (pour s = w/ 3) et donc a priori plus avantageuse, ce filtre n’atteint que 82,7% de la valeur de P(f) obtenue pour le filtre optimal de Spacek Enfin, même pour le critère de performance de Canny lui-même, le filtre optimal de Spacek donne lieu à une valeur de S L meilleure.

        Pour montrer les effets que Canny, Spacek et Tagare et Figueiredo ont voulu éviter en définissant leurs critères, nous allons tout d'abord utiliser les contours simples suivants :

                       

        Un réglage optimal des paramètres, que ce soit avec la dérivée de gaussienne ou avec le filtre de Spacek donne bien évidemment des résultats parfaits. Les contours sont tous détectés et sont bien localisés. On n'observe ni de bruit ni d'apparition de nouveaux contours :

Spacek (W = 2)                                                           Canny (sigma = 7)

                       

        Cependant, si on choisit une taille du filtre trop importante par rapport à la dimension des contours (largeur de 1 pixel dans les 2 cas), on observe l'effet de rebond contre lequel le troisième critère de Canny tente de nous protéger, mais qui est amplifié par la nécessité de tronquer les réponses impulsionnelles des filtres (phénomène de Gibbs) :

Spacek (W = 10)                                                           Canny (s = 30)

                       

        On peut également observer que quand la dimension du filtre augmente, la localisation des contours se détériore et on a tendance à manquer des contours qui deviennent trop fins. Ci-dessous, nous avons appliqué le filtre de Canny à une mire en augmentant simplement la taille du filtre (le seuillage reste le même) :

Image originale                                                            Image des contours (s = 2)

                       

Image des contours (s = 4)                                                  Image des contours (s = 5)

                       

        Plus la taille du filtre augmente et moins on distingue de contours fins (Cf. le centre de la mire). Les contours s'écartent progressivement de leur position originale, comme on peut notamment le constater sur le quadrillage du pourtour de la mire.

        En présence de bruit, ces détecteurs ont une bonne robustesse. Nous avons testé ici le détecteur de Canny : 

Paramètres : s = 2, les deux seuils d'hystérésis sont à 0,99

                       

Paramètres : s = 5, les deux seuils d'hystérésis sont à 0,6 et 0,99

                       

        Même avec des seuils hauts, il est normal que les détecteurs de contours conservent des traces du bruit présent dans les images initiales. Dans le cas de la première image, on détecte de faux contours. La seule façon de les enlever serait d'augmenter le rapport signal sur bruit en entrée. Dans le cas de la deuxième image, le contour détecté n'est pas aussi franc et rectiligne qu'il devrait l'être.

        Et pour finir, à titre d'exemple, voyons l'action comparée de nos deux filtres sur deux images réelles :

Papillon                                                                        Opéra

                       

Canny

                       

Spacek

                         

        Les différences de qualité observées sont essentiellement dus aux post-traitements en sortie des filtres : l'implémentation de Spacek propose un seuillage brut de l'image de gradient, alors que l'implémentation de Canny dispose d'un seuillage à hystérésis.

Retour au sommaire

Bibliographie

John Canny, A computational approach to edge detection, IEEE Pami, vol. 8, n° 6, novembre 1986, pp 679-698

Libor A. Spacek, Edge detection and motion detection, Image and vision computing, vol. 4, n° 1, février 1986, pp 43-56

Henant D. Tagare et Rui J.P. de Figueiredo, On the localization performance measure and optimal edge detection, IEEE Transactions on pattern analysis and machine intelligence, vol. 12, n° 12, décembre 1990

J. Cocquerez et S. Philipp, Analyse d'images : filtrage et segmentation, Masson, 1996

Retour au sommaire

© Sandrine Augais - Richard Chevalier - Vincent Domurado
mars 2001