Déplacement des contours par passage par zéro du laplacien à l'aide de divers paramètres
Par Loris GUILBAUD et Philippe LACOUR
Etape 1 : Qu'est ce que le déplacement des contours ?
Etape 2 : Illustration sur des images
Etape 3 : Explications dans le cas monodimensionnel
On se place dans le cadre général de la détection de contours. Le sujet de ce cours (tentative de cours serait plus juste) est d'illustrer le déplacement des contours d'une image par les passages par zéro du laplacien de cette image à l'aide de divers paramètres. Ce cours est divisé en deux parties.
La première partie expose le problème général de la détection de contours, cite les méthodes classiques utilisées et décrit la méthode du laplacien de Deriche. Elle donne aussi le détail des calculs permettant une mise en oeuvre de cette méthode.
La deuxième partie illustre d'une part le phénomène de déplacement du contour dans le cas monodimensionnel qui est plus facile à maîtriser et illustre d'autre part le déplacement des contours sur des images.
Les méthodes de détection de contour sont nombreuses. Elles sont regroupées en 2 familles : d'une part les méthodes privilégiant une approche par frontières (méthodes dérivatives, surfaciques, morphologiques et markoviennes) à laquelle on donne le nom de segmentation; d'autre part celles privilégiant une approche par régions (méthodes markoviennes et structurales).
Intuitivement, dans une image numérique, les contours se situent entre les pixels appartenant à des régions ayant des intensités moyennes différentes; il s'agit de contours de type "saut d'amplitude". Un contour peut également correspondre à une variation locale d'intensité présentant un maximum ou un minimum, il s'agit alors de contour en "toit". En fait, sur des images réelles on pourra avoir des contours symétriques ou non symétriques. Il faut noter que ces descriptions de contours ne s'appliquent pas aux frontières séparant des régions de textures différentes (concerne l'approche par régions).
Les méthodes les plus immédiates permettant de détecter les variations locales d'intensité sont les méthodes dérivatives. Les contours peuvent être obtenus par extraction des maxima locaux de la dérivée première ou bien par extraction des passages par zéro de la dérivée seconde directionnelle, ou encore par extraction des passages par zéro du laplacien.
Ci-dessous est modélisé l'aspect des dérivées premières et dérivées secondes pour une transition de type saut d'amplitude.
Si vous voulez plus de détails sur la problématique de la détection de contours notamment pourquoi le laplacien permet effectivement de détecter les contours.
Dans la pratique, dès lors qu'on utilise une méthode dérivative du second ordre, c'est le laplacien qui est utilisé plutôt que la dérivée seconde directionnelle car il permet de simplifier les calculs et donc il est moins coûteux en temps de calcul.
On peut ainsi résumer les différentes étapes pour extraire les contours en utilisant le laplacien :
Au travers de ces différentes étapes, on voit alors les paramètres sur lesquels on va pouvoir influer pour détecter voire déplacer les contours. Il s'agit du paramètre alpha du filtre de lissage et des deux paramètres du seuillage par hystérésis. En fait les deux paramètres du seuillage par hystérésis joueront beaucoup sur la détection des contours : plus le seuil bas sera faible et le seuil haut élevé, plus il y aura de contours détectés; en contrepartie l'image sera plus bruitée. Il faudra donc adopter un compromis. Le seul paramètre qui va réellement produire un déplacement des contours sera le paramètre alpha du filtre de lissage. On devra observer une délocalisation d'autant plus perceptible que le paramètre alpha sera petit. Par la suite nous ne parlerons plus que de ce paramètre alpha, le seul intervenant effectivement dans le déplacement des contours.
Différentes techniques de calcul du laplacien existent. Laquelle choisir? Certaines méthodes réalisent le lissage dans le calcul même du laplacien. Regardons les diverses méthodes en présence :
| 0 | -1 | 0 |
| -1 | 4 | -1 |
| 0 | -1 | 0 |
Plus généralement on peut dire que le laplacien est convenablement réalisé par la différence de deux filtres passe-bas dont on règle judicieusement les fréquences de coupure en jouant.
I.3. Opérateur laplacien de Deriche
Les calculs dans le cadre continu menés par Deriche, notamment pour la dérivée première, lui ont permis de montrer que le laplacien d'une image A est égal à la différence de deux images traitées. L'image A est tout d'abord lissée par un filtre passe-bas avant l'application d'un opérateur différentiel pour mettre en évidence les transitions. Plus précisément Deriche obtient :
Nous avons choisi d'utiliser la méthode de l'opérateur laplacien de Deriche car :
Le contour est un concept essentiellement basé sur la capacité du système visuel humain à distinguer plusieurs zones connexes d'aspect homogène, pour lesquelles la ligne de séparation sera appelé un contour ou une frontière. Il n'y a donc pas de définition précise et on peut dire qu'il y a des contours là où le système visuel humain en voit.
Par exemple sur l'image ci-dessus, on peut distinguer plusieurs types de contours:
Les méthodes de détection de contours par passage par zéro du laplacien (comme celle de Deriche) donne des contours qui peuvent être différents suivant un paramètre (qu'on appellera alpha) caractérisant le lissage appliqué à l'image avant calcul du laplacien:
C'est ce qu'on appelle le déplacement des contours.
Le paramètre alpha (positif strictement) caractérise la largeur de transition d'une frontière entre deux zones. En effet, avant le calcul du laplacien sur l'image à traiter, il y a lissage de l'image par le filtre de réponse impulsionel h(x) = cx.exp(-alpha |x|).
Donc si alpha est grand, h(x) se rapproche d'une impulsion et le laplacien sera calculé sur l'image telle quelle. Par contre quand alpha décroît il y a un filtrage passe-bas de plus en plus fort. Il y a donc modification suivant alpha de l'image sur laquelle on applique réellement le laplacien et donc variation des passages par zéro du laplacien.
Visite guidée: étape suivante.
Cette partie peut être sautée lors d'une première lecture (Partie suivante: illustrations).
On peut mettre en oeuvre ces opérateurs à l'aide de filtres à réponse impulsionnelle infinie. Pour trouver les relations de filtrage on utilise la transformée en Z. On obtient alors des filtres ayant une passe causale et une anti-causale.
Dans les deux paragraphes qui suivent I représente l'image de départ, J l'image après filtrage, J+ l'image après la passe causale du filtrage et J- l'image après la phase anti-causale.
Le calcul du gradient se fait par un filtrage de réponse impulsionnelle suivante:
hx(x,y) = -b alpha*alpha x exp(-alpha |x|).b(alpha |y|+1).exp(-alpha |y|), suivant x
hy(x,y) = -b alpha*alpha y exp(-alpha |y|).b(alpha |x|+1).exp(-alpha |x|), suivant y
Il y a donc deux filtres à mettre en oeuvre, celui de dérivation du type cx.exp(-alpha |x|) et celui de lissage du type b(alpha |x|+1).exp(-alpha |x|).
Le filtre dérivateur est calculé par les équations aux différences suivantes:
J+(n) = a1.I(n-1) + b1.J+(n-1) + b2.J+(n-2)
J-(n) = a2.I(n+1) + b1.J-(n+1) + b2.J-(n+2)
et J(n) = -(J+(n)+J-(n))
où:
a1 = (1-exp(-alpha))**2
a2 = -(1-exp(-alpha))**2
b1 = 2.exp(-alpha)
b2 = -exp(-2.alpha)
Le filtre de lissage est calculé par les équations aux différences suivantes:
J+(n) = k.I(n) + a1.I(n-1) + b1.J+(n-1) + b2.J+(n-2)
J-(n) = a1.I(n+1) + a2.I(n+2) + b1.J-(n+1) + b2.J-(n+2)
et J(n) = (J+(n)+J-(n))
où:
k = ((1-exp(-alpha))**2)/(1+2 alpha exp(-alpha)-exp(-2 alpha))
a1 = k.exp(-alpha)(alpha-1)
a2 = -k.exp(-2.alpha)
b1 = 2.exp(-alpha)
b2 = -exp(-2.alpha)
I.5.b Laplacien
La réponse impulsionnelle du filtre à mettre en oeuvre est:
h(x) = c.(exp(-alpha |x|) - alpha |x|.exp(-alpha |x|)) où c est une constante.
I étant l'image de de départ et J l'image finale, les relations de récursions obtenues sont donc les suivantes:
J+(n) = I(n) + a1.I(n-1) + b1.J+(n-1) + b2.J+(n-2)
J-(n) = a2.I(n+1) + b2.I(n+2) + b1.J-(n+1) + b2.J-(n+2)
et J(n) = -(J+(n)+J-(n))
où:
k = (1-exp(-2.alpha))/(2.alpha.exp(-alpha))
a1 = -(1+k.alpha).exp(-alpha)
a2 = (1-k.alpha).exp(-alpha)
b1 = 2.exp(-alpha)
b2 = -exp(-2.alpha)
Vous pouvez lire le programme réalisé pour créer l'image des passages par zéro du laplacien affectés de la norme du gradient en consultant les fichiers main.c et deriche.c (l'exécutable correspondant est appelé deriche).
Ce cas est intéressant car il permet de visualiser plus facilement le comportement du déplacement des contours, les conclusions pouvant s'appliquer directement aux images bidimensionnelles. On va mettre en évidence deux types de comportement:
Pour illustrer cela nous avons considéré des signaux monodimensionnels discrétisés en temps. Par exemple une transition du type sigmoide a l'aspect suivant:
Chaque palier représente l'espace d'un pixel, ce qui donne une representation similaire à celles des images, pour lesquelles on utilise une interpolation d'ordre 0 lorsqu'on les affiche.
On a alors calculé le laplacien de plusieurs signaux pour voir où se trouvait le passage par 0. On observe alors que pour toutes les transitions symétriques le 0 du laplacien est rigoureusement au milieu de la transition: il n'y a donc pas de déplacement.
Ceci est illustré dans le cas de la sigmoïde sur les figures suivantes où on a tracé le laplacien pour différentes valeurs de alpha :
alpha = 1,0 |
alpha = 0,2 |
Puis nous avons étudié la transition non symétrique suivante qui est composée d'une plage constante et d'une exponentielle:
Nous avons calculé le laplacien pour plusieurs valeurs de alpha:
alpha = 1,0 |
alpha = 0,5 |
alpha = 0,3 |
alpha = 0,2 |
On voit d'une part que le zéro ne tombe pas sur la transition. De plus en fonction du paramètre alpha, ce zéro se déplace d'autant plus que alpha est petit et donc que le filtrage passe-bas est plus fort.
(Remarque: on a sur les bords des effets indésirables dus au filtre numérique utilisé. Bien que dans ce cas précis, qui est très simple, ils ne provoquent pas de passages par 0 supplémentaires, cela pourrait arriver dans un cas réel. Il ne faudra donc pas prendre une valeur de seuillage trop faible.)
Cela s'explique bien par le fait que lorsque le paramètre alpha est grand on ne détecte que les transitions franches et celles-ci se trouvent bien sûr à la rupture de pente. Par contre quand le paramètre alpha diminue, il y a un filtrage passe-bas plus accentué et donc symétrisation de la transition avant le calcul du laplacien. Il y a donc un déplacement du contour vers le milieu de cette zone de transition.
On sait donc qu'il y aura déplacement des contours dans une image dès lors qu'il y aura des transitions non symétriques du type précédent.
Visite guidée: dernière étape.
Les images qui vont suivre pour illustrer nos propos ont été obtenues en utilisant l'exécutable deriche (création de l'image des passages par zéro du laplacien), puis un post traitement est effectué avec le logiciel Khoros (seuillage par hystérésis et ou logique avec l'image originale); enfin un dernier traitement est effectué avec xv (réduction des images, conversion au format .gif, choix de la palette de couleurs).
Présentons plusieurs images pour lesquelles il y a déplacement du contour en fonction du paramètre alpha. Dans chaque cas on présentera l'image sur laquelle on a calculé les contours, les différences (obtenues avec une opération de ou-exclusif) entre 2 contours calculés pour 2 alphas différents et l'image originale superposée avec chaque contour calculé. Cela permet d'estimer objectivement le déplacement des contours. Afficher seulement l'image originale superposée avec les contours obtenus dépend en effet fortement du système psychovisuel.
Le déplacement des contours est perceptible pour des transitions non symétriques. Typiquement, celles-ci peuvent apparaître soit sur des photos de sujets tridimensionnels dont l'ombrage est convenable, soit sur des photos qui ne représentent pas des objets tridimensionnels comme les radiographies et des images médicales qui sont des coupes 2D (coupe axiale du cerveau par exemple).
Sur des objets 3-D photographiés, la plupart du temps on a des transitions symétriques : on passe graduellement d'un éclairage fort à un éclairage faible (typiquement le nez ou l'épaule de lena). Cependant ce n'est pas toujours le cas.
Par exemple sur la photo Tifany, au niveau du doigt qui est contre le menton, on a un sillon sombre qui devient très rapidement clair dès qu'on s'en écarte mais qui continue de s'éclaircir jusqu'au centre du doigt (ou de l'autre coté à l'intérieur du menton). Au niveau du début de l'ongle, il y a un écart de 6 pixels entre alpha = 0,2 et alpha = 1.
Image originale |
alpha = 1 (cyan) et 0,2 (jaune) |
alpha = 1,0 |
alpha = 0,2 |
La photo suivante qui est une radiographie est un exemple d'objet non 3-D. Elle illustre bien la différence entre un contour pour lequel il y a déplacement et un où il n'y en a pas. Sur la partie supérieure droite de la photo (au niveau de la transition entre les parties blanches et noires), on voit nettement 2 contours différents qui ont une différence maximun au centre de cette partie. Cette différence diminue et devient nulle sur les bords de cette partie. Or sur la photo originale on constate que lorsque les deux contours sont à la même position la transition est beaucoup plus franche (ce n'est pas très visible sous Netscape mais bien visible avec xv lorsqu'il a toutes les couleurs néceessaires).
Ce cas est typiquement le type de transition décrite dans les explications des illustrations monodimensionnelles.
Image originale |
alpha = 0,4 (cyan) et 0,15 (jaune) |
|
alpha = 0,4 |
alpha = 0,15 |
Autre image de radiographie. On voit qu'en bas de la lettre 'C' il y a un fort déplacement du contour qui ne se produit pas sur la lettre 'o' qui est à coté. Il nous semble que ce déplacement soit du au fait qu'en dessous de la lettre 'o' le niveau se stabilise rapidement (une vingtaine de pixels) a un niveau uniforme. La largeur de la transition n'est donc pas trés grande. Par contre pour le 'C', il y a augmentation du niveau sur une zône nettement plus grande qui va presque jusqu'en bas de l'image présentée ci-dessous.
|
Image originale |
alpha = 0,4 et 0,15 |
alpha = 0,4 |
alpha = 0,15 |
Voici maintenant un exemple d'image médicale, en l'occurence une coupe sagittale de cerveau (brain) où on observe un déplacement visible du contour de l'ordre de 5 pixels dans la partie supérieure de l'image pour un alpha de 0,15. Le laplacien a du mal a suivre le contour quand celui-ci est courbé trop fortement. Et même il a tendance à relier des contours qui n'ont rien de commun pour assurer la fermeture des contours.
|
Image originale |
alpha = 0,6 (jaune) et 0,15 (cyan) |
alpha = 0,6 |
alpha = 0,15 |
Enfin un dernier exemple, une image de scène naturelle, l'image d'une corbeille de fruits. On voit que lorsqu'on lisse fortement l'image, c'est-à-dire avec un alpha faible, les contours arrondis autour des fruits se déplacent notablement : de 2 à 3 pixels sur le haut de la pomme de droite, ce qui confirme la remarque précédente; les contours courbes avec des transitions non symétriques provoquent des déplacements importants. Ce déplacement sur les contours courbés est probablement dû à l'approximation de la dérivée seconde directionnelle par le laplacien (on a négligé le terme relatif à la courbure pour le calcul du laplacien). On note par ailleurs que le rebord inférieur droit du panier s'est déplacée de 2 pixels.
Image originale |
alpha = 0,6 (cyan) et 0,15 (jaune) |
alpha = 0,6 |
alpha = 0,15 |
Visite guidée: étape suivante.
