Détection de contours dans les images

Séverine Dubuisson

Détection de contours dans les images – p. 1/7

Caractérisation d’un contour

Discontinuité de la fonction d’intensité des images

Discontinuité de la fonction de réflectance (texture,
ombre, ...)
Discontinuité de profondeur (bords des objets)

Détection de contours dans les images – p. 2/7

Définitions d’un contour

Définition spatiale :
Lieu de variations significatives de l’information de niveaux de gris (il
existe peu de travaux sur les contours dans les images couleurs ou
multi-spectrales) : rupture d’intensité
Définition fréquentielle : haute fréquence du spectre d’amplitude de la
transformée de Fourier de l’image

Détection de contours dans les images – p. 3/7

Détection d’un contour

Détection de contours dans les images – p. 4/7

Les méthodes dérivatives

Dérivée première d’un contour : gradient

Opérateurs dérivatifs du premier ordre
Recherche d’un passage par un maximum, ou
extrama local
Dérivée seconde d’un contour : laplacien
Opérateurs dérivatifs du second ordre
Recherche d’un passage par zéro

Détection de contours dans les images – p. 5/7

Travail sur la dérivée première : principe (1/

Un contour d’orientation ϕ au point de coordonnées (x, y) est détecté par

un maximum de la dérivée première, dans la direction φ du gradient
 
cos φ
# (x, y)#n
g(φ) = ∇f #n =  
sin φ

Détection de contours dans les images – p. 6/7

Travail sur la dérivée première : principe (2/

∂f ∂f
On a donc g(φ) = ∂x cos φ + ∂y sin φ
En dérivant par rapport à φ et en annulant on obtient
% &
∂f
∂y π
φ = arctan ∂f
ϕ=φ+
∂x
2

La norme du gradient est donnée par :

'
( )2 ( )2
$ (x, y" = ∂f ∂f
"∇f +
∂x ∂y

Détection de contours dans les images – p. 7/7

Gradient d’une image : interprétations

Gradient : vecteur des dérivées horizontales et

verticales de l’intensité
La dérivée directionnelle est maximisée dans la
direction du gradient
La dérivée de f (x, y) dans une direction d$ donnée
$ (x, y) · d$
s’écrit ∇f
L’amplitude (i.e module) du gradient est liée à la quantité
de variation locale de l’intensité : plus le module est
grand, plus le contour est fort
Argument du gradient : direction de la plus grand pente

Détection de contours dans les images – p. 8/7

Cas discret (1/3)

On estime le gradient en calculant une variation monodimensionnelle

dans une direction φ donnée

Gφ (x, y) = (I $ Wφ ) (x, y)
*m *n
= I(x + i, y + j) · Wφ (i, j)
i=−m j=−n

La taille de l’opérateur (autour de la position (x, y)) est donnée par le

couple (m, n)
Pour estimer le gradient, on choisit deux directions privilégiées
orthogonales (les lignes et les colonnes) sur lesquelles on le projette
Gx est le gradient vertical
Gy est le gradient horizontal

Détection de contours dans les images – p. 9/7

Cas discret (2/3)

La norme du gradient peut être calculée de trois

manières :
$ (x, y)
G(x, y) = ∇f
+
= (Gx (x, y))2 + (Gy (x, y))2
G(x, y) = max (|Gx (x, y)|, |Gy (x, y)|)
G(x, y) = |Gx (x, y)| + |Gy (x, y)|

La direction du gradient en un point est donnée par :

( )
Gy (x, y)
φ(x, y) = arctan
Gx (x, y)

Détection de contours dans les images – p. 10/7

Cas discret (3/3)

On approche les dérivées directionnelles en utilisant les

opérateurs anisotropes :

Gx (i, j) ≈ $x I(i, j) = I(i + 1, j) − I(i, j)

Gy (i, j) ≈ $y I(i, j) = I(i, j + 1) − I(i, j)

La norme du gradient peut être obtenue de trois

manières :
+
G(i, j) = (I(i + 1, j) − I(i, j))2 + (I(i, j + 1) − I(i, j))2
G(i, j) = max (|I(i + 1, j) − I(i, j)|, |I(i, j + 1) − I(i, j)|)
G(i, j) = |I(i + 1, j) − I(i, j)| + |I(i, j + 1) − I(i, j)|

Détection de contours dans les images – p. 11/7

Filtres dérivatifs du premier ordre

Un filtre est composé de deux masques :

Hx détecte les contours verticaux
Hy détecte les contours horizontaux
Dans le domaine spatial : convolution linéaire de l’image avec les
filtres
Image des contours verticaux, ou gradient vertical : Gx = I $ Hx
Image des contours horizontaux, ou gradient horizontal :
Gy = I $ Hy
+
Module du gradient : G = G2x + G2y ou G = max(|Gx |, |Gy |)
Filtres courants : Roberts, Prewitt, Sobel, Kirch

Détection de contours dans les images – p. 12/7

Opérateurs du premier ordre

Opérateur de Roberts : approche les dérivées

directionnelles suivant les axes orientés à 45◦ (contours
obliques)
% & % &
0 1 −1 0
Filtres : Hx = Hy =
−1 0 0 1
π
Direction ϕ du contour : ϕ = 4 +φ
Opérateurs de Sobel (c = 2) et Prewitt (c = 1)
   
1 0 −1 −1 −c −1
   
Filtres : Hx =  c 0 −c  Hy =  0 0 0 
1 0 −1 1 c 1
π
Direction ϕ du contour : ϕ = 2 +φ

Détection de contours dans les images – p. 13/7

Compléments sur Prewitt et Sobel

Ces masques opèrent tout d’abord un lissage de

l’image, suivi d’une opération de dérivation : ils sont dits
séparables
   
1 . / 1 . /
   
Hx =  c  · 1 0 −1 Hy =  0  · 1 c 1
1 −1
Le lissage permet d’atténuer le bruit dans l’image,
pouvant être interprété comme un contour :
Prewitt : filtre moyenneur
Sobel : filtre gaussien

Détection de contours dans les images – p. 14/7

Exemple de filtrage : Sobel

Détection de contours dans les images – p. 15/7

Résultats comparatifs

Détection de contours dans les images – p. 16/7

Opérateur de Kirch (1/2)

Opérateur à 8 masques, chacun correspondant à une

direction préférentielle obtenue par rotations de π8
successives
   
5 5 5 −3 5 5
   
H0 = 
 −3 0  
−3  H1 =  −3 0 5 

−3 −3 3 −3 −3 −3
   
−3 −3 5 −3 −3 −3
   
H2 = 
 −3 0  
5  H3 =  −3 0 5 
−3 −3 5 −3 5 5
   
−3 −3 −3 −3 −3 −3
   
H4 = 
 −3 0  
−3  H5 =  5 0 −3 
5 5 5 5 5 −3

Détection de contours dans les images – p. 17/7

Opérateur de Kirch (2/2)
   
5 −3 −3 5 5 −3
   
H6 = 
 5 0 −3  H7 = 
 5 0 −3 

5 −3 −3 −3 −3 −3

Le gradient retenu est celui correspondant à la valeur

maximum, donnée par maxi=0,··· ,7 {|I & Hi |}
L’orientation retenue est celle du masque ayant
maximisé le gradient
Cet opérateur est aussi appelé gradient boussole ou
gradient compas

Détection de contours dans les images – p. 18/7

Opérateur de MDIF

Combinaison d’un filtre moyenneur et de l’opérateur de

Prewitt  
0 1 0 −1 0
     
0 1 0 1 0 −1  1 2 0 −2 −1 
 
     
Hx = 
 1 1 1
 $  1 0 −1  =  1 3
    0 −3 −1 

 
0 1 0 1 0 −1  1 2 0 −2 −1 
 
0 1 0 −1 0
 
0 1 1 1 0
     
0 1 0 1 1 1  1 2 3 2 1 
 
     
Hy = 
 1 1 1
$ 0
  0 0  
= 0 0 0 0 0 
 
0 1 0 −1 −1 −1  −1 −2 −3 −2 −1 
 
0 −1 −1 −1 0

Détection de contours dans les images – p. 19/7

Taille des filtres

Les masques les plus couramment utilisés sont de taille 3 × 3

(m = n = 1)
On peut généraliser : cas du Sobel (Asfar) pour une taille de
voisinage quelconque

Wx (i, j) = i/(|i| · (|i| + |j|))

Wy (i, j) = j/(|j| · (|i| + |j|))

Quelle taille choisir pour un opérateur ?

Plus le masque est grand moins le gradient est sensible au bruit
(bruit atténué par le lissage)
Plus le masque est grand, moins bonne est la localisation des
contours (le lissage rend l’image floue)

Détection de contours dans les images – p. 20/7

Du gradient au contour

Pour détecter les contours d’une image, il faut procéder

de la sorte :
1. Mesure en chaque point de l’image de l’amplitude et
de la direction du gradient
2. Détermination des seuils d’amplitude
3. Suppression directionnelle des non-maxima locaux
4. Extraction des éléments essentiels
5. Reconstruction des contours par hysteresis

Détection de contours dans les images – p. 21/7

Détermination des seuils d’amplitude

Technique de Voorhees et Poggio

Seuillage basé sur la validation de deux seuils, un seuil
bas Sb et un seuil haut Sh , avec Sb < Sh , de la manière
suivante :
si G(x, y) < Sb alors on est sur que (x, y) n’est pas un
point de contour
si G(x, y) > Sh alors on est sur que (x, y) est un point
de contour
si Sb < G(x, y) < Sh alors l’appartenance à un contour
dépend du contexte

Détection de contours dans les images – p. 22/7

Suppression directionnelle des non maxima locaux (1/2)

Extraction des maxima locaux dans la direction du

gradient
Opération sur un voisinage de l’image de la norme du
gradient
On compare le gradient d’un point avec celui de ses
deux voisins M1 et M2 dans la direction
perpendiculaire au contour
Un point M est un maximum local si :
$ M " > "∇
"∇ $M " et $ M " ≥ "∇
"∇ $M "
1 2

Détection de contours dans les images – p. 23/7

Suppression directionnelle des non maxima locaux (2/2)

Les modules de gradient en M1 et M2 doivent être interpolés

"∇ # j − 1)" + ui −uj "∇(i
# M " = uj "∇(i, # + 1, j)"
1 ui ui
"∇ # j + 1)" + ui −uj "∇(i
# M " = uj "∇(i, # − 1, j)"
2 ui ui
avec ui = Gx (i, j) et uj = Gy (i, j)

Détection de contours dans les images – p. 24/7

Extraction des éléments essentiels

Points pour lesquels on est sûr de l’appartenance à un

contour
(x, y) : G(x, y) > Sh
Points de départ pour l’étape de reconstitution des
contours

Détection de contours dans les images – p. 25/7

Reconstitutions des points par hystérésis

On part des points M (x, y) déterminés éléments essentiels

On utilise deux seuils Sb et Sh , avec Sb < Sh , et pour chaque
point M , on peut procéder des deux manières suivantes :
Procédure 1 : on ne valide que les ensembles connexes de
points présentant au moins un point dont la norme de
gradient est supérieure à Sh
Procédure 2 : on valide tous les pixels connexes aux points
détectés et possédant une norme de gradient supérieure à Sb
On répète la procédure pour tous les nouveaux points validés

Détection de contours dans les images – p. 26/7

Travail sur la dérivée seconde : principe (1/2

Un changement linéaire d’amplitude d’une fonction f

correspond au passage par zéro de sa dérivée seconde
Dans le cas d’une image, il n’existe pas une dérivée seconde
unique, mais 4 dérivées partielles (selon x2 , y 2 , xy et yx)
En pratique, on a recours au laplacien faisant la somme des
deux dérivées partielles principales
2 2
2 ∂ I ∂ I
∇ = 2
+ 2
∂x ∂y

Un passage par zéro est caractérisé par une pente positive

dans le cas d’une frontière ayant une amplitude augmentant
de gauche à droite ou de bas en haut dans l’image
Détection de contours dans les images – p. 27/7
Travail sur la dérivée seconde : principe (2/2

Pour limiter les réponses dues au bruit, on filtre l’image

par g
∇2 (I & g) = (∇2 I) & g = I & (∇2 g)
En général on utilise un filtre gaussien g
1 r2 0
g(r) = √ e− 2σ2 où r= x2 + y 2
2πσ

dont le laplacien est :

( )
2 1 r2 r2
− 2σ2
∇ g(r) = − 4 1− e
πσ 2σ 2

Détection de contours dans les images – p. 28/7

Laplacien classique : cas discret

On approche le laplacien par les différences finies

∂2f
∂x2
1 23 4
L(i, j) = − [I(i, j − 1) − 2I(i, j) + I(i, j + 1)]
− [I(i − 1, j) − 2I(i, j) + I(i + 1, j)]
3 41 2
∂2f
∂y 2

Dans le domaine spatial, on calcule le laplacien par convolution

entre
 l’image et un
 masque,
 dont les deux
 plus courants sont :
0 −1 0 −1 −1 −1
   
   
 −1 4 −1   −1 8 −1 
   
0 −1 0 −1 −1 −1

Détection de contours dans les images – p. 29/7

Avantages/Inconvénients du laplacien

Avantages :
Un seul paramètre est nécessaire (variance de la
gaussienne)
Pas de seuil significatif : les points remarquables sont
détectés par un critère de changement de signe au
niveau d’un passage par zéro
Les contours sont fermés
Inconvénients :
Plus grande sensibilité au bruit
Aucune information sur l’orientation du contour

Détection de contours dans les images – p. 30/7

Approche DOG

DOG : Difference of Gaussians

Lissage à l’aide d’un filtre gaussien g(x, y) puis calcul de
la dérivée seconde dans la direction du gradient

Iz = $ (I & g(x, y)) = I & $g(x, y)

La dérivée seconde d’une gaussienne s’approche par la

différence de deux gaussiennes
Recherche des passages par zéro

Détection de contours dans les images – p. 31/7

Filtre optimum

Principe du filtrage : trouver la réponse impulsionnelle

d’un filtre susceptible d’extraire les points de contour tout
en réduisant le bruit
Introduire un filtre à réponse impulsionnelle séparable
h(x, y) = h1 (x)h2 (y)
Réduction du temps de calcul
Prise en compte de caractéristiques différentes
suivant les directions
Généralisation à des dimensions quelconques

Détection de contours dans les images – p. 32/7

Principe du filtrage

Soit un filtre séparable

I(x, y)&h(x, y) = I(x, y)&(h1 (x)h2 (y)) = (I(x, y) & h1 (x))&h2 (y)

Calcul de la dérivée première :

( )
∂(I(x, y) & h(x, y)) ∂h1 (x)
= I(x, y) & h2 (y)
∂x ∂x

Calcul de la dérivée seconde (laplacien) :

( )
∂ 2 h1 (x) 2
∂ h2 (y)
$(I(x, y) & h(x, y)) = I(x, y) & 2
h2 (y) + h1 (x)
∂x ∂y 2

Détection de contours dans les images – p. 33/7

Modèles du signal et du bruit (1/3)

Un contour est un seuil d’amplitude A auquel on ajoute

un bruit n(x) gaussien blanc de variance σ02 (modèle
additif) :
5
0 si x < 0
I(x) = AY (x) + n(x) avec Y (x) = U (x) =
1 si x ≥ 0

Le bruit est un bruit blanc additif

E(n(x)) = 0
E(n2 (x)) = σ02 ∀x

Détection de contours dans les images – p. 34/7

Modèles du signal et du bruit (2/3)

I(x) O(x)
! h(x) !

6 +∞
O(x) = I(x − u)h(u)du
−∞
6 +∞ 6 +∞
O(x) = AY (x − u)h(u)du + n(x − u)h(u)du
−∞ −∞

Supposons le contour placé en x = 0, la sortie du filtre s’écrit :

6 x 6 +∞
O(x) = A h(u)du + n(x − u)h(u)du
−∞ −∞
6 0 6 +∞
O(0) = A h(u)du + n(−u)h(u)du
−∞ −∞
Détection de contours dans les images – p. 35/7
Modèles du signal et du bruit (3/3)

Rechercher la réponse impulsionnelle d’un filtre

séparable susceptible de diminuer le bruit et appliquer
les opérateurs de dérivée
1. Modéliser le signal à extraire et le bruit de l’image
2. Transformer le problème d’extraction des points de
contour en problème d’optimisation
3. Résoudre et trouver une solution approchée
! on souhaite que la sortie présente un maximum
lorqu’il y a une arête : un contour optimal est situé en
x=0

Détection de contours dans les images – p. 36/7

Modèle analytique de Canny

Canny propose en 1986 un étude sur la détection de contours

Etude dans le cas 1D de signal bruité
A formalisé trois critères que doivent valider un détecteur
de contours :
Détection : robustesse au bruit
Localisation : précision de la localisation du point de
contour
Unicité : une seule réponse par contour
A chaque critère est associée une formule mathématique
La maximisation de ces critères conduit à la résolution d’une
équation différentielle dont la solution est le filtre f
permettant de détecter le contour
Détection de contours dans les images – p. 37/7
Critère de détection

But : maximiser le rapport signal sur bruit, ou SNR (Signal

Noise Ratio)
76 +∞ 6 +∞ 8
E(N 2 ) = E n(−u)h(u)du n(−v)h(v)dv
−∞ −∞
6 +∞
E(N 2 ) = σ02 h2 (u)du
−∞

On cherche le maximum du critère :

90
A | −∞ h(u)du| A
C1 = SNR = +9 = Σ(h)
σ0 ∞
h2 (u)du σ0
−∞

Détection de contours dans les images – p. 38/7

Critère de localisation (1/3)

But : rechercher l’écart entre le maximum de la sortie en

x0 et 0 : O$ (x0 ) = 0
6 +∞ 6 +∞
O $ (x) = AY (x − u)h$ (u)du + n(x − u)h$ (u)du
3 −∞ 41 2 3 −∞ 41 2
Contribution S(x) du signal Contribution N (x) du bruit

S(x) = Ah(x)
6 +∞
N (x) = n(x − u)h$ (u)du
−∞

Détection de contours dans les images – p. 39/7

Critère de localisation (2/3)

6 +∞ !
2
E(N (x)) = σ02 h 2 (u)du
−∞

Supposons x0 proche de 0, on a :

S(x0 ) ≈ Ah(0) + x0 Ah$ (0) + o(x20 )

h est impaire :

S(x0 ) ≈ x0 Ah$ (0)

Détection de contours dans les images – p. 40/7

Critère de localisation (3/3)

O $ (x0 ) = S(x0 ) + N (x0 ) ≈ Ax0 h$ (0) + N (x0 )

D’où :
9 +∞ $2
N (x0 ) 2
σ0 −∞ h (u)du
x0 = − $ et E(x20 ) =
Ah (0) A2 h$2 (0)

On obtient le critère de localisation :

1 A |h$ (0)| A
C2 = + = +9 = Λ(h)
E(x20 ) σ0 +∞ $2
h (u)du σ0
−∞

Détection de contours dans les images – p. 41/7

Critère d’unicité de la réponse (1/3)

But : réduire les réponses multiples

Le détecteur de contour ne doit pas identifier de
mutiples pixels de contours quand un seul existe
On veut que la distance entre les pics de la réponse au
bruit soit approximativement la largeur de bande de la
réponse du filtre à un seul contour.

Détection de contours dans les images – p. 42/7

Critère d’unicité de la réponse (2/3)

Rice a montré que la distance moyenne d entre deux

passages par zéro d’un processus gaussien, obtenu par
filtrage d’un bruit blanc g(x), est donnée par :
%' &
−R(0)
d=π !!
R (0)
9 +∞
où R(τ ) = −∞ g(x + τ )g(x)dx est la fonction
d’auto-corrélation de g
On cherche l’intervalle moyen entre deux passages par
zéro de h$

Détection de contours dans les images – p. 43/7

Critère d’unicité de la réponse (3/3)

!! 9 +∞ !!
On a R (τ ) = −∞ g (x + τ )g(x)dx
!! 9 +∞ !
Soit R (0) = − −∞ g 2 (x)dx
7 R +∞ 2
8 1
2
g (x)dx
Et ainsi d = π R −∞
+∞
g ! 2 (x)dx
−∞

Dans notre problème, g = h$ , et on obtient ainsi le critère

d’unicité :
: 9 +∞ ! ; 12
h 2 (x)dx
C3 = 2d = 2π 9 −∞
+∞ !!
−∞ h 2 (x)dx

Détection de contours dans les images – p. 44/7

Résolution : approche de Canny (1/3)

Canny a proposé de majorer ΣΛ avec d = kW

h est impaire, de support fini [−W, W ]
90
On cherche à minimiser −W h2 (y)dy
Avec les trois contraintes :
6 0
h(y)dy = D1
−W
6 0
h$2 (y)dy = D2
−W
6 0
!!
h 2 (y)dy = D3
−W

Détection de contours dans les images – p. 45/7

Résolution : approche de Canny (2/3)

D’où la fonction critère :

6 0 . /
!!
φ= h2 (y) + λ1 h(y) + λ2 h$2 (y) + λ3 h 2 (y) dy
−W

Ce qui conduit à l’équation :

!!
C = 2h + λ1 − 2λ2 h + 2λ3 h(4) = 0

Dont la solution générale est :

λ1
h(x) = e−αx
(a1 sin ωx + a2 ) cos ωx) + e αx
(a3 sin ωx + a4 cos ωx) −
2

λ22 λ2 4λ4 −λ2

Avec λ1 − 4 > 0, α2 − ω = 2λ4 et 4α2 ω 2 = 4λ24

Détection de contours dans les images – p. 46/7

Résolution : approche de Canny (3/3)

Avec les conditions aux limites :

h(0) = h(−W ) = h$ (W ) = 0
h$ (0) = c3

En utilisant une technique d’optimisation numérique

sous contrainte, Canny a trouvé les valeurs optimales
suivantes :

ΣΛ = 1, 12
k = 0, 58

Détection de contours dans les images – p. 47/7

Résolution : approche de Dériche (1/2)

Dériche a proposé d’utiliser un filtre à réponse

impulsionnelle infinie (RII)

h2 (x) = a3 e−α|x| sin ωx

On calcule ainsi les expressions :

<
√ 2α
Λ = 2α Σ=
α2 + ω 2
<
2α α2 + ω 2
ΣΛ = 2 k=
α + ω2 5α2 + 6α2 ω 2 + ω 4
On pose α = ωm

Détection de contours dans les images – p. 48/7

Résolution : approche de Deriche (2/2)
+
2α
Pour m * 1, on a Σ + α2 /m2 ⇒ ΛΣ ≈ 2m donc k + 1
k excellent
ΛΣ est très petit car m faible : aucun intérêt
+ √
1
Pour m = 1, on a Σ + α ⇒ ΛΣ ≈ 2 donc k + 0, 58
k identique à celui de Canny
ΛΣ meilleur de 25% par rapport à celui de Canny
+
Pour m - 1, on a Σ + α2 ⇒ ΛΣ ≈ 2 donc k + 0, 44
Ce cas correspond à la limite de l’opérateur pour
ω → 0 (sin ωx ≈ ωx)

Détection de contours dans les images – p. 49/7

Pour résumer

La valeur SNR doit être la plus grande possible : on veut

beaucoup de signal et peu de bruit
La valeur de la localisation représente l’inverse de la
distance du contour détecté au vrai contour : on la veut
la plus grande possible
Le critère d’unicité est une contrainte supplémentaire
pour éviter les réponses multiples et représente la
distance moyenne entre les passages par zéro de f $
Canny cherche le filtre qui maximise le produit du SNR
et de la localisation sujet à la contrainte d’unicité de la
réponse
! parfois compliqué à résoudre : on l’approche par la
dérivée première d’une fonction gaussienne.
Détection de contours dans les images – p. 50/7
Algorithme de Canny-Deriche simplifié

1. Lire l’image I
2. Créer un masque Gaussien 1D G pour convoluer I (σ à
paramétrer)
3. Créer un masque 1D pour la dérivée première de G
dans les directions en x et y (Gx et Gy )
4. Convoluer I et G selon les lignes puis les colonnes (Ix et
Iy )
5. Convoluer Ix avec Gx (Ix$ ) et Iy avec Gy (Iy$ )
+
6. Calculer la magnitude M (x, y) = Ix$ (x, y)2 + Iy$ (x, y)2

Détection de contours dans les images – p. 51/7

Suivi de contour (1/2)

L’extraction de points de contour nous permet d’obtenir

une image binaire
Pixels blancs : points de contour
Pixels noirs : autres pixels de l’image
Problèmes à résoudre :
Certains points de contour n’ont pas été détectés
Certains pixels détectés comme points de contour
n’en sont pas
Nécessité d’obtenir les contours fermés des
objets/régions de l’image

Détection de contours dans les images – p. 52/7

Suivi de contour (2/2)

Grouper les points de contours en chaînes et relier ces

chaînes afin d’obtenir des “formes”
On peut ensuite obtenir des informations sur ces
formes : courbure, pente, coins, etc.
Procédure :
1. Affiner les composantes contour connectées à une
épaisseur de 1 pixel
2. Trouver des chemins simplement connectés
3. Les lier entre eux en utilisant une modélisation par
graphe de l’image des contours
4. Calculer les propriétés du contour obtenu

Détection de contours dans les images – p. 53/7

Affinage (thinning) (1/4)

On travaille sur l’image binaire contenant les points de

contour
La suppression d’un point de contour ne doit pas
changer le nombre de composantes connectées dans
l’image binaire
Un point final est un pixel blanc ayant exactement un
voisin
Si on considère un voisinage 3 × 3 avec comme point
central p un pixel blanc (point de contour), alors :
,→ p est un point simple si on peut le changer de
blanc en noir sans changer le nombre de
composantes connectées dans le voisinage

Détection de contours dans les images – p. 54/7

Affinage (thinning) (2/4)

1 1 1
Exemple 1 de voisinage : 0 1 1 ⇒ p est simple-8 mais pas simple-4
0 1 0

0 0 0
Exemple 2 de voisinage : 1 1 1 ⇒ p n’est ni simple-8 ni simple-4
0 0 0
Un 1-pixel blanc I(x, y) (ou point final) est un bord-N si son voisin de
coordonnée (x, y − 1) est noir (définitions similaires avec les directions S,
E et O)

Détection de contours dans les images – p. 55/7

Affinage (thinning) (3/4)

Un algorithme simple :
Pour D=N faire
Éliminer tous les bords-D qui sont simples et ne sont pas des
points finaux
Répéter pour les directions E, O et S

Chaque direction est traitée séparément afin d’éviter

l’élimination de composantes connexes entières
Le résultat dépend de l’ordre de traitement des
directions

Détection de contours dans les images – p. 56/7

Affinage (thinning) (4/4)

Exemple d’application N → E → O → S :
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 1 1 1 0 0 0 1 0 0 1 1 0 0
0 1 0 1 1 0 0 1 0 1 0 1 1 0 0 1
0 1 1 1 1 1 1 1 0 1 0 1 1 0 1 1
0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 0
0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 1 1 0 0 0 1 0 0 1 1 0 0
0 1 0 1 1 0 0 1 0 1 0 1 1 0 0 1
0 1 0 1 0 0 1 1 0 1 0 1 0 0 1 1
0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 0
0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Détection de contours dans les images – p. 57/7
Représentation par un graphe (1/3)

But : créer une représentation structurée en graphe de

l’image de contours
On part d’une image binaire E des contours
L’image est vue comme un maillage (i.e. graphe)
Un pixel “point de contour” est un sommet de ce graphe
Suivi de contour = recherche d’un chemin entre deux
sommets du graphe

Détection de contours dans les images – p. 58/7

Représentation par un graphe (2/3)

Exemple : on connaît l’orientation du gradient en chaque

point de contour
Deux pixels voisins détectés "points de contour" peuvent
être reliés si les directions de leur gradient sont proches
Application : pour relier le pixel a au pixel b, b doit être un
des huit voisins de a dans la direction du contour en a
(φ(a)), soit :
π
|(φ(a) − φ(b))mod2π| <
2

Détection de contours dans les images – p. 59/7

Représentation par un graphe (3/3)

Détection de contours dans les images – p. 60/7

Recherche heuristique (1/3)

Soient a et b deux extrémités d’un contour

Pour tout pixel p situé sur un chemin solution, on définit
une fonction d’évaluation :

f (p) = g(p) + h(p)

où :
g(p) est le coût du chemin de a à p
h(p) est le coût du chemin de p à b
Une solution : L’algorithme A∗

Détection de contours dans les images – p. 61/7

Recherche heuristique (2/3)

Principe de l’algorithme A∗ :
n=a
tant que n /= b faire
Placer les successeurs de n dans L
Déterminer p tel que f (p) = minq∈L (f (q))
n=q
Ajouter p à C
fin tant que
si C est vide alors échec
sinon C contient le chemin optimal de a vers b
Quelques valeurs intervenant dans le calcul de h :
Importance de l’arête : || maxp (∇I(p))|| − ||∇I(p)||
Courbure : φ(p) − φ(p$ )
Distance à l’objectif : d = dist(p, b)
Détection de contours dans les images – p. 62/7
Recherche heuristique (3/3)

Exemple d’illustration de fonction coût : somme (inverse)

des modules du gradient

Détection de contours dans les images – p. 63/7

Programmation dynamique (1/4)

Technique de résolution de problèmes d’optimisation

On veut résoudre :

max{h(x1 , x2 , . . . , xn )}
xi

On ne possède pas de connaissance a priori sur h

Seule technique : énumération exhaustive des solutions
possibles

Détection de contours dans les images – p. 64/7

Programmation dynamique (2/4)

Soit n = 4 et le problème maxxi {h(x1 , x2 , x3 , x4 )} à

résoudre
Si h(·) = h1 (x1 , x2 ) + h2 (x2 , x3 ) + h3 (x3 , x4 )
On a alors :

f1 (x2 ) = max{h1 (x1 , x2 )}

x1
f2 (x3 ) = max{f1 (x2 ) + h2 (x2 , x3 )}
x2
f3 (x4 ) = max{f2 (x3 ) + h3 (x3 , x4 )}
x3

Et finalement :

max{h(x1 , x2 , x3 , x4 )} = max{f3 (x4 )}

xi x4

Détection de contours dans les images – p. 65/7

Programmation dynamique (3/4)

En généralisant :

f0 (x1 ) = 0
fn−1 (xn ) = max{fn−2 (xn−1 ) + hn−1 (xn−1 , xn )}
xn−1
max{h(x1 , x2 , . . . , xn )} = max{fn−1 (xn )}
xi xn

Soit la fonction coût :

n
* n
* n
*
S(x1 , . . . , xn ) = |∇I(xi )| − α |φ(xi ) − φ(xi−1 )| − β d(xi , xi−1 )
i=1 i=2 i=2
S(x1 , . . . , xn ) = S(x1 , . . . , xn−1 ) + |∇I(xn )| − α|φ(xn ) − φ(xn−1 )|
−βd(xn , xn−1 )
S(x1 , . . . , xn ) = S(x1 , . . . , xn−1 ) + f (xn−1 , xn )

Détection de contours dans les images – p. 66/7

Programmation dynamique (4/4)

On a donc (en posant n = k ) :

S(x1 , . . . , xk ) = max{S(x1 , . . . , xk−1 ) + f (xk−1 , xk )}

xk−1

Avec : S(x1 ) = |∇I(x1 )|

Application de l’algorithme de Dijkstra sur le graphe
G(S, A), où :
S est l’ensemble des sommets du graphe, valués par
la valeur du gradient au pixel correspondant
A est l’ensemble des arêtes du graphe, valuées par la
distance entre les deux pixels de contour qu’elles
relient

Détection de contours dans les images – p. 67/7

La transformée de Hough (1/2)

Permet de rechercher des formes particulières et

simples dans l’image des points de contour :
Détection de lignes
Détection de cercles, ellipses
Les formes géométriques ont une forme paramétrique :
La droite : y = ax + b ou ρ = x cos θ + y sin θ
Le cercle : (x − a)2 + (y − b)2 = r2
La facette plane : ax + by + c = z
Les surfaces quadratiques, cubiques :
z = a00 + a10 x + a20 y + a11 xy + a20 x2 + a02 y 2 + a21 x2 y + . . .

Détection de contours dans les images – p. 68/7

La transformée de Hough (2/2)

Principe : changer d’espace de représentation

)→ Passer de l’espace de l’image à celui des paramètres I → 0p ,
soit (x, y) → (a1 · · · ap )t
Algorithme général :
1. En chaque point, calculer la(les) vecteur(s) de paramètres le(s) plus
probable(s)
2. Dans l’espace 0p , pour chaque point (vecteur de paramètres),
calculer le nombre de points ayant choisi ce vecteur de paramètres
3. Garder le vecteur de paramètres apparu le plus souvent dans le choix
des pixels de l’image
L’espace discret des paramètres est également appelé accumulateur

Détection de contours dans les images – p. 69/7

La transformée de Hough : détection de droites (1/3)

Soit P (x, y) un pixel détecté point de contour. Ce point appartient à toutes

les droites d’équation ρ = x cos θ + y sin θ
On a deux données (x et y) et deux inconnues (ρ et θ), avec une infinité
de solutions possibles
On doit utiliser une deuxième contrainte, un point de contour Q(x$ , y $ )

Détection de contours dans les images – p. 70/7

La transformée de Hough : détection de droites (2/3)

Soit une image I de taille N × N , alors les droites ayant une intersection
avec I sont caractérisées par :
√
ρ ∈ [0, 2N ]
π
θ ∈ ] − , π[
2
Si on utilise un accumulateur de taille N × N , alors la précision sur le
√ 3π
résultat sera au mieux (∆ρ, ∆θ) = ( 2, 2N )
Exemple d’une image de taille 512 × 512 : (∆ρ, ∆θ) = (1.4, 0.5)
)→ En fait toutes les valeurs de l’accumulateur ne correspondent
pas à une droite traversant l’espace image
Chaque élément (ρ, θ) de l’accumulateur A est un compteur incrémenté
par les sources d’information (pixel) votant pour la droite

Détection de contours dans les images – p. 71/7

La transformée de Hough : détection de droites (3/3)

Calcul de l’accumulateur A en utilisant une carte de contours

comme espace image I :
1. A ← 0
2. Pour tout couple de pixels p et q de I
Calculer les coordonnées (ρ, θ) de la droite passant par p et q
ρ
Convertir les paramètres en indices : (ρ̃, θ̃) = ( ∆ρ θ
, ∆θ )
Mise à jour de l’accumulateur : A(ρ̃, θ̃) ← A(ρ̃, θ̃) + 1
3. fin pour
4. Garder le couple (ρ∗ , θ∗ ) pour lequel A(ρ∗ , θ∗ ) est maximal
Si on a n pixels de contour, la complexité est en O(n2 )

Détection de contours dans les images – p. 72/7

La transformée de Hough : détection de cercles

Un cercle de centre (a, b) et de rayon r a pour équation :

(x − a)2 + (y − b)2 = r2

L’accumulateur A est un tableau à 3 dimensions (a, b, r)

La cellule A(a, b, r) est augmentée de 1 si le point (a, b)
est à une distance r du point de fort gradient considéré
(x, y)
Complexité en O(n3 )
Pour une ellipse, il faut rajouter deux paramètres : la
largeur et la hauteur de l’ellipse ⇒ complexité en O(n5 )

Détection de contours dans les images – p. 73/7