Algorithmique et Imagerie


Détection de contours : les opérateurs de Canny-Deriche

Dans son article [2], R. Deriche propose un schéma général d'algorithme récursif, qui permet moyennant un simple changement de paramètres d'obtenir des filtres lisseurs, dérivateurs et dérivateurs d'ordre 2.

La forme générale du filtre de Deriche est la suivante :

f : le signal à filtrer (de support [0...M-1]×[0...N-1])
g : le signal résultat
g-, g+, r : résultats intermediaires
p : paramètre du filtre (également noté alpha)
a1...8, b1...4 : paramètres calculés à partir de a, différents selon les applications

g-[m,n] = a1 f[m,n] + a2 f[m,n-1] + b1 g-[m,n-1] + b2 g-[m,n-2]
f[m,-1] = 0 ; g-[m,-2] = g-[m,-1] = 0
g+[m,n] = a3 f[m,n+1] + a4 f[m,n+2] + b1 g+[m,n+1] + b2 g+[m,n+2]
f[m,N] = f[m,N+1] = 0 ; g+[m,N] = g+[m,N+1] = 0
r[m,n] = g-[m,n] + g+[m,n]

g-[m,n] = a5 r[m,n] + a6 r[m-1,n] + b3 g-[m-1,n] + b4 g-[m-2,n]
r[-1,n] = 0 ; g-[-2,n] = g-[-1,n] = 0
g+[m,n] = a7 r[m+1,n] + a8 r[m+2,n] + b3 g+[m+1,n] + b4 g+[m+2,n]
r[M,n] = r[M+1,n] = 0 ; g+[M,n] = g+[M+1,n] = 0
g[m,n] = g-[m,n] + g+[m,n]

On voit par exemple qu'en choisissant les valeurs de paramètres suivantes :

k' = (1 - e-p)2
e-p
a1 = 1 ; a2 = a3 = a4 = b1 = b2 = 0
a5 = 0 ; a6 = k'e-p ; a7 = - k'e-p ; a8 = 0
b3 = 2 e-p ; b4 = - e-2p

on obtient le filtre dérivateur étudié en cours, agissant dans la direction x.

0) Récupérez le kit de développement grâce au lien que vous trouverez en bas de cette page. Vous y trouverez un "squelette" d'opérateur (fichier src/lib/lderiche.c) que vous devrez compléter. Lisez le tutoriel (tutorial.html) qui se trouve dans le répertoire doc.

1) Etudiez la fonction "derichegen" qui implémente le filtre général de Deriche. Vérifiez qu'elle implémente effectivement les opérateurs récursifs étudiés en cours.

2) Essayez sur une image le filtre dérivateur en x obtenu grâce au jeu de coefficients ci-dessus. Attention : pour visualiser le résultat, il faudra normaliser les valeurs de l'image de sortie, qui sont comprises entre -255 et 255, pour les ramener dans l'intervalle [0...255].

3) Implémentez de la même façon un filtre dérivateur en y, puis un opérateur calculant le module du gradient. Essayez cet opérateur sur des images.

4) On peut améliorer l'opérateur précédent en faisant agir, conjointement au filtre dérivateur en x, un filtre lisseur en y, et réciproquement. Cela correspond aux jeux de paramètres suivants :

k = (1 - e-p)2
1 + 2 pe-p - e-2p
 ; k' = (1 - e-p)2
e-p
a1 = k ; a2 = k e-p (p- 1) ; a3 = k e-p (p+ 1) ; a4 = - k e-2p
a5 = 0 ; a6 = k'e-p ; a7 = - k'e-p ; a8 = 0
b1 = b3 = 2 e-p ; b2 = b4 = - e-2p

et

a1 = 0 ; a2 = k'e-p ; a3 = - k'e-p ; a4 = 0
a5 = k ; a6 = k e-p (p- 1) ; a7 = k e-p (p+ 1) ; a8 = - k e-2p
b1 = b3 = 2 e-p ; b2 = b4 = - e-2p

Le module du gradient se calcule ensuite de la même façon qu'en 3. Comparez les résultats avec ceux obtenus précédemment. Etudiez l'impact du paramètre alpha.

5) On veut extraire les contours des objets dans une image (par exemple "/user/coupriem/Images/2d/Divers/buro.pgm"). Pour cela, on peut seuiller le module du gradient. Essayez de trouver, pour l'image en question, une valeur de seuil "convenable". On pourra utiliser l'opérateur "/user/coupriem/Pink/linux/bin/seuil".

6) John Canny a employé une méthode basée sur un double seuillage, dite aussi seuillage par hystérésis. Cette méthode revient à opérer la reconstruction géodésique d'un ensemble obtenu avec seuil "haut" dans un ensemble obtenu avec un seuil "bas". Essayez par cette méthode d'améliorer les résultats obtenus en 5). On pourra utiliser l'opérateur "/user/coupriem/Pink/linux/bin/reconsdilat".

Pour aller plus loin (traiter une question au choix)

7) En vous inspirant de l'opérateur de gradient, implémentez un opérateur de Laplacien. Utilisez-le pour le réhaussement d'images floues (par exemple "/user/coupriem/Images/2d/Bouchoucha/*.pgm").

8) En vous inspirant de l'opérateur de gradient 2D, implémentez un opérateur de gradient 3D. Utilisez-le pour extraire les contours d'une image IRM de cerveau (par exemple "/user/coupriem/Images/3d/Cerveau/cropmri.pgm").

References

[1]
J. Canny, ``A Computational Approach to Edge Detection'', IEEE PAMI, Vol. 8, No. 6, pp. 679-698, 1986.
[2]
R. Deriche, ``Fast Algorithms for Low-Level Vision'', IEEE PAMI, Vol. 12, No. 1, pp. 78-87, 1990.

A récupérer :

Après avoir sauvé ce fichier sur votre compte, tapez: 

  tar zxvf pinkdev.tgz
  cd Pinkdev
  make
et lisez le tutoriel (tutorial.html) qui se trouve dans le répertoire doc. Pour tester vos opérateurs, vous trouverez des images au format pgm dans /user/coupriem/Images/2d .

File translated from TEX by TTH, version 1.95.
On 8 Feb 1999, 07:22.