Chapitre 6

Segmentation et extraction d’attributs

Sommaire
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
6.2 Segmentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
6.2.1 Détecteurs d’éléments géométriques particuliers . . . . . . . . . . . . . . . . 82
6.2.2 Seuillage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
6.2.3 Segmentation en régions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
6.3 Extraction et représentation d’attributs . . . . . . . . . . . . . . . . . . . . . . . . . . 90
6.3.1 Attributs des objets binaires . . . . . . . . . . . . . . . . . . . . . . . . . . 90
6.3.2 Descripteur de contours . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
6.3.3 Attributs basés sur l’histogramme . . . . . . . . . . . . . . . . . . . . . . . 97
6.3.4 Attributs de texture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98

81
 CHAPITRE 6. SEGMENTATION ET EXTRACTION D’ATTRIBUTS

6.1 Introduction
La segmentation permet d’isoler certaines parties de l’image qui présentent une forte corrélation
avec les objets contenus dans cette image, généralement il s’agit d’un post-traitement. On considère
principalement deux types de segmentation :
1. la segmentation par contours qui permet de délimiter les différentes régions par leurs frontières.
Cette partie a été traité dans le chapitre précédent.
2. la segmentation par régions qui permet de caractériser les régions d’une image présentant une
structure homogène et qui fait appel la plupart du temps à des outils statistiques.
La deuxième partie sera consacré à l’extractions des attributs. C’est une étape critique dans la plupart
des solutions de vision par ordinateur et de traitement d’images.

6.2 Segmentation
6.2.1 Détecteurs d’éléments géométriques particuliers
I1 arrive qu’on ait besoin d’identifier des éléments géométriques particuliers dans une image, par
exemple des droites ou des Cercles. Nous présentons deux détecteurs adaptés a la recherche d’éléments
spécifiques : les coins, qui permettent par exemple des mises en correspondances d’images dans une
problématique de stéréographie ou de classifications et les droites.

Détecteur de coin de Harris

Le détecteur de coin de Harris est (comme le détecteur de Canny) basé sur une analyse des gradients
de l’image.
L’algorithme de détecteur de coin de Harris s’écrit de la manière suivante :
1. Calculer le gradient discret ∇I = (Ix , Iy ) sur toute l’image.
2. Pour chaque pixel :
 P P 
Ix Ix Ix Iy
 V V 
(a) Calculer sur un voisinage V du pixel la matrice suivante : P P 
Ix Iy Iy Iy
V V
(b) Calculer les valeurs propres λ1 et λ2 (avec λ2 < λ1 )
(c) Si la valeur propre minimale λ2 > seuil, Conserver les coordonnées du pixel dans une liste
L (ce sont les coins).
278 CH 10 IMAGE SEGMENTATION
(d)

Figure 10.7 Left: the Harris response function to an image comprising a dark star on a plain
Figure 6.1: (a) : la fonction de réponse
background. de Harris
Right: the significant à une
local maximum image
points comprenant
are shown une
superimposed on the étoile sombre sur fond uni.
original
(b) : les points maximaux image
locaux significatifs sont affichés superposés à l’image d’origine

Example 10.4
3. Trier L en ordre décroissant
Matlab code
de λ2 . What is happening?
I¼imread(‘zener [Link]’); %Read in image and convert to
I¼double(rgb2gray(I)); %intensity
wdth¼5; sdvn¼2; %Fix smoothing parameters
82 k¼0.04; %Fix Harris constant
hsmall¼fspecial(‘gaussian’,[wdth wdth],sdvn); %Define Gaussian filter
[Fx,Fy]¼gradient(I); %Calculate gradient
Fx sq¼Fx.^2; Fy sq¼Fy.^2; Fx Fy¼Fx. Fy; %Define terms in Harris function
CHAPITRE 6. SEGMENTATION ET EXTRACTION D’ATTRIBUTS

4. Balayer la liste L de haut en bas, pour chaque pixel pi et éliminer les autres pixels qui appar-
tiennent au voisinage de pi .
La liste finale contient les points saillants pour lesquels λ2 > seuil et dont les voisinages ne se che-
vauchent pas. Ce sont les pixels les plus faciles a suivre. La Figure 6.1 présente le résultat de l’appli-
cation du détecteur de Harris sur une image.

La transformation de Hough

La transformée de Hough est une méthode mathématique conçue pour trouver des lignes dans
les images. Il peut être utilisé pour relier les résultats de la détection des bords, transformant les
bords potentiellement clairsemés, cassés ou isolés en lignes utiles qui correspondent aux bords réels
de l’image. Soit (x, y) les coordonnées d’un point dans une image binaire. La transformée de Hough
calcule et enregistre dans un tableau toutes les paires (a, b) qui satisfaisant l’équation y = ax + b. Le
tableau (a, b) est appelé
350 tableau de transformation. Par exemple, le point (x, y) = (1, 3) dans l’image
EDGE DETECTION

d’entrée se traduira par l’équation b = −a + 3, qui peut être tracée comme une ligne qui représente
(a, b qui satisfont cette équation (Figure 6.2).
toutes les paires350 EDGE DETECTION

FIGURE 14.13 The Hough transform maps a point into a line.

Since each point in the image will map to a line in the transform domain, repeat-
ing the process for other points will result in many intersecting lines, one per point
FIGURE
(Figure 14.14). The14.13
Figure TheofHough
6.2:
meaning La ortransform
more linesmaps
twotransformation ade
point into
Hough.
intersecting a line.
in the transform do-
main is that the points to which they correspond are aligned in the image. The points
with the greatest number of intersections in the transform domain correspond to the
Étant donné que chaque
longest
Since point
lines
each point
in thede
in thel’image
image.
image will correspond
map to a line à une
in theligne dans domain,
transform le domaine de transformation,
repeat-
Describing lines using the equation y = ax + b (where a represents the gradient)
la répétition du processus
ing poses a pour
the process for
problem, d’autres
other points
points
since vertical linesentraı̂nera
will have infinite de
result in many nombreuses
intersecting
gradient. lines, lignes
This limitation one canqui
perbe se croisent, une par
point
(Figure 14.14). The by meaning the of two or more lines of
point (Figure ??. Lacircumvented
signification using
de deux normal
lignes ou plus seintersecting
representation a line, which
croisant in consists
dans the transform
of two do-de transformation
le domaine
main parameters:
is that the points to which they
ρ (the perpendicular correspond
distance from theareline
aligned in the and
to the origin) image. The
θ (the points
angle
est que les pointswith auxquels
between
the greatest elles
the line’s
number correspondent
perpendicular sont
and the in
of intersections alignés
horizontal axis). Indans
the transform l’image.
this new
domain Lesto points
representation
correspond the avec le plus
(Figure
longest lines14.15),
in the vertical
image. lines will have θ = 0. It is common to allow ρ to have negative
grand nombre d’intersections dans le domaine de transformation ◦ correspondent aux lignes les plus
values, therefore
Describing restricting
lines using y =−90
θ to the range
the equation ≤ 90◦ . a represents the gradient)
ax +<b θ(where
longues de l’image.
poses aLaproblem,
description des lignes
since vertical à l’aide
lines have infinitedegradient.
l’équation y = axcan
This limitation + bbe(où a représente
circumvented by using the normal representation of a line, which consists of two
parameters: ρ (the perpendicular distance from the line to the origin) and θ (the angle
between the line’s perpendicular and the horizontal axis). In this new representation
(Figure 14.15), vertical lines will have θ = 0. It is common to allow ρ to have negative
values, therefore restricting θ to the range −90◦ < θ ≤ 90◦ .

FIGURE 14.14 The Hough transform: intersections in the transform domain correspond to
Figure 6.3: La transformation de Hough : les intersections dans le domaine de transformation correspondent
aligned points in the image.
à des points alignés dans l’image.

le gradient) pose problème, car les lignes verticales ont un gradient infini. Cette limitation peut être
contournée en utilisant la représentation polaire d’une ligne, qui se compose de deux paramètres : ρ (la
distance perpendiculaire de la ligne à l’origine) et θ (l’angle entre la perpendiculaire de la ligne et l’axe
horizontal). Dans cette14.14
FIGURE nouvelle représentation
The Hough (Figure in6.4),
transform: intersections les lignes
the transform verticales
domain correspondauront
to θ = 0. Il est
aligned points in the image.

83
 CHAPITRE 6. SEGMENTATION ET EXTRACTION D’ATTRIBUTS

courant de permettre à ρ d’avoir des valeurs négatives, restreignant ainsi θ à la plage −90◦ < θ ≤ 90◦ .
EDGE LINKING AND BOUNDARY DETECTION 351

Figure
FIGURE 14.15 The Hough6.4: le système
transform: de coordonnées
a line polaires.
and its parameters in the polar coordinate
system.

La relation entre ρ ,θ et les coordonnées d’origine (x, y) est :

The relationship between ρ,ρθ,=and

x cos + y sincoordinates
theθoriginal θ (x, y) is

La transformée de Hough peut être implémentée avec les coordonnées polaires comme suit :
ρ = x cos θ + y sin θ (14.13)
— Créez un tableau 2D correspondant à un ensemble discret de valeurs pour ρ et θ.
Under
— Pour chaque the (x,
pixel newy)set of l’image
dans coordinates, the chaque
et pour Hough valeur
transform can de
choisie beθ,implemented as θ +y sin θ
calculez x cos
le résultat à la position correspondante (ρ, θ).
follows:
et écrivez

— Les valeurs les plus

1. Create élevées
a 2D (ρ, θ) correspondront
arraydecorresponding auxset
to a discrete lignes les plus
of values for pertinentes de l’image.
ρ and θ. Each
element in this array is often referred to as an accumulator cell.
2. For each pixel (x, y) in the image and for each chosen value of θ, compute
x cos θ + y sin θ and write the result in the corresponding position—(ρ, θ)—in
the accumulator array.
3. The highest values in the (ρ, θ) array will correspond to the most relevant lines
in the image.

IN MATLAB
Figure 6.5: Exemple de transformation de Hough : (a) image d’entrée ; (b) les résultats de la transformation
The IPTencontains
de Hough, mettant évidencea les
function for Hough
intersections transform calculations,
correspondant hough, which
aux lignes prédominantes takes
dans a d’entrée.
l’image
binary image as an input parameter, and returns the corresponding Hough transform
matrix and the arrays of ρ and θ values over which the Hough transform was calculated.
La Figure 6.5 montre
Optionally, l’image d’origine
the resolution et les résultats
of the discretized 2D arraydes calculs
for both de θtransformation
ρ and can be specified de Hough.
Vous remarquerez que certains
as additional des pics les plus élevés de l’image transformée (approximativement à
parameters.
θ = −60 et θ = 60 ) correspondent aux principales lignes diagonales de la forme des ciseaux.
◦ ◦

 EXAMPLE 14.6
In this example, we use the hough function to find the strongest lines in a bi-
6.2.2 Seuillage
nary image obtained as a result of an edge detection operator (BW), using the
Le seuillage est une procédure de transformation d’une image d’entrée en niveaux de gris en une
image binarisée, ou une image avec une nouvelle plage de niveaux de gris, en utilisant une valeur de
seuil particulière. L’objectif du seuillage est d’extraire certains pixels de l’image tout en en supprimant
d’autres. Le seuillage a pour but de marquer des pixels appartenant à des pixels de premier plan de
même intensité et des pixels d’arrière-plan d’intensités différentes.
Un seuil est fondamentalement une valeur ayant deux ensembles de régions de chaque côté, c’est-
à-dire au-dessus du seuil ou en dessous du seuil. La Figure 6.6 montre la sortie de segmentation avec
seuil local et global.

84
CHAPITRE 6. 58SEGMENTATION ET
A Beginner’s
EXTRACTION Guide toD’ATTRIBUTS
Image Preprocessing Techniques

(A) (B) (C) (D)

Figure 6.6: (A) FIGURE

Image 5.1
d’entrée avec un illumination non-homogène, (B) et (C) Résultat de seuillage global,
(A) Input image with uneven illumination, (B) and (C) Global thresholding result, (D) Local
(D) Résultat de thresholding
seuillage local.
result.

expensive. One comparatively simple technique is the iterative method to find

a specific
Seuillage basé sur image
la forme dethreshold, which is also robust against noise. The steps of the
l’histogramme
iterative method is as follows:
La méthode de l’histogramme suppose qu’il existe une certaine valeur moyenne pour les pixels et
Step 1: An
l’arrière-plan du premier initial
plan ou dethreshold
l’objet, (T)
maisis la
selected
réalitéarbitrarily
est que lesbyvaleurs
any other
réelles des pixels ont
desired method.
une certaine déviation autour de ces valeurs moyennes. Dans ce cas, la sélection d’une valeur de seuil
Step 2: The image I(x, y) is segmented into foreground or object pixels
d’image précise est difficile et coûteuse
and background en calcul. Une technique relativement simple est la méthode
pixels:
itérative pour trouver un seuil d’image spécifique, qui est également robuste contre le bruit. Les étapes
Object pixels (OP) ← {I ( x , y ) : I ( x , y ) ≥ T }
de la méthode itérative sont les suivantes : (5.1)
Background pixels (BP) ← {I(( x , y ) : I ( x , y ) < T }.
1. Étape 1 : Un seuil initial (T ) est sélectionné arbitrairement.
Step 3: The average of each pixel set is calculated.
2. Étape 2 : l’image I(x, y) est segmentée en pixels de avant plan ou d’objet et pixels d’arrière-plan
ou le fond : AOP ← Average of OP

(a) Pixels d’objet :P O ← {I(x, y)A: I(x, y) ≥ T }of BP

← Average
BP

(b) Pixels fond :P F ← {I(x, y) : I(x, y) < T }

Step 4: A new threshold is formed, which is the average of AOP and ABP:
3. Étape 3 : La moyenne de chaque ensemble de pixels est calculée.
( AOP + ABP )
(a) AP O ← M oyenne de P O Tnew ← . (5.2)
2
(b) AP F ← M oyenne de P F
Step 5: In step 2, use the new threshold obtained in step 4. Repeat till
4. Étape 4 : Un nouveau seuil est formé,
the new threshold matchesqui
theest
onelabefore
moyenne
it. de l’AP O et de l’AP F :

Assume that the gray level image = (A

TN ew I(x, +AP F )
y) PisOcomposed
2
of a light object in a
dark background, in such a way that background and object, or foreground
5. Étape 5 :gray level pixels,
À l’étape can be grouped
2, utilisez le nouveau into seuil
two dominant
obtenu àmodes.
l’étapeOne4. clear way to
Répétez jusqu’à ce que le
extract the object pixels from the background is to select a threshold T, which
nouveau seuil corresponde à celui qui le précède.
divides these two modes. Then any pixel (x, y) where I(x, y) ≥ T is called an
object
Supposons que pixel, otherwise,
l’image de niveau the de pixel is called
gris I(x, y) sea background
compose d’un pixel. Example:
objet clair sur fond sombre, de
If two dominant modes describe the image histogram, it is called a
telle sorte que le fond ethistogram.
bimodal l’objet, peuvent
Here, only être
oneregroupés
thresholden deux modes
is sufficient [Link] façon claire
for segmenting
partitioning
d’extraire les pixels the image.
de l’objet de du Figure
fond est 5.2 de
shows the bimodal
sélectionner unhistogram of an
seuil T , qui imageces deux modes.
divise
and the segmented image.
Ensuite, tout pixel (x, y) où I(x, y) ≥ T est appelé pixel objet, sinon, le pixel est appelé pixel fond.
Segmentation Techniques 59

FIGURE 5.2
The bimodal histogram and the segmented image.
Figure 6.7: Seuillage à l’aide d’un histogramme bimodal.
If for instance, an image is composed of two or more types of dark objects in
a light background, three or more dominant modes are used to characterize
Si deux modes dominantsimage
the histogram, l’histogramme
décrivent which is denoted as a multimodal histogram.
de l’image, Figure 5.3
il est appelé histogramme bimodal.
shows the multimodal histogram of an image and the segmented image.
Ici, un seul seuil suffit pour segmenter ou partitionner l’image. La Figure 6.7 montre l’histogramme
5.1.2  Clustering-Based Thresholding
bimodal d’une image et l’image segmentée.
K-means Thresholding Method: The steps of K-means algorithm for selecting the
threshold is as follows [10]:

Seuil basé sur le clustering Step 1: Class centers (K) are initialized:

 ( j − ( j / 2))(Gmax − Gmin ) 
Seuillage par K-means Les =G +
étapes de Cl’algorithme pour ,
sélectionner
j0 (5.3) sont les suivantes :
le seuil
min
 k 

1. Étape 1 : Les centres de classe

where (K) Csont
j = 1,2,…,k; is theinitialisés
first class center: of jth class; G and G
j0 min max
are the minimum and maximum gray value of the sample space.
h i
(j−(j/2))(G
Step 2: Assign every point of the sample space to its max
nearest min )center
−Gclass
based onC j0 = G
Euclidean min +
Distance: k
Dj , i = abs(Gi − C j ), (5.4)

where j = 1,2,…,k; i = 1,2,…,P; Dj,i is the distance from an ith point to 85

the jth class, and P is the total number of points in the sample space.
Step 3: Compute the (K) new class centers from the average of the points
that are assigned to it:
 CHAPITRE 6. SEGMENTATION ET EXTRACTION D’ATTRIBUTS

Où j = 1, 2, . . . , k ; Cj0 est le centre de première classe de la j ième classe ; Gmin et Gmax sont
les valeurs de gris minimale et maximale.
2. Étape 2 : Attribuez chaque point de l’espace échantillon à son centre de classe le plus proche en
fonction de la distance euclidienne :

Dj,i = abs (Gi − Cj )

Où j = 1, 2, . . . , k ; i = 1, 2, . . . , P ; Dj,i est la distance entre un ième point et la j ième classe, et

P est le nombre total de points.
3. Étape 3 : Calculez les (K) nouveaux centres de classe à partir de la moyenne des points qui lui
sont attribués :

1
P
CN ew = Pi Gj

Où j = 1, 2, . . . , k et Pi est le nombre total de points attribués à la ième classe à l’étape 2.

4. Étape 4 : Répétez l’étape 2 pour le changement dans le centre de classe ; sinon arrêtez l’itération.
5. Étape 5 : Le seuil est calculé par la moyenne du centre de classe k et du centre de classe (k − 1) :

60 T = 1Guide
A Beginner’s (Ck +toCImage
2 k−1 )
Preprocessing Techniques

FIGURE 5.4
Figure 6.8: Le résultat de la segmentation d’image avec différentes valeurs de k.
The output of image segmentation with different k values.

Le résultat de la segmentation
where estand
j = 1,2,…,k illustré à la
Pi is the Figure
total 6.8.
number of points that are assigned
to the ith class in step 2.
Step
Méthode de seuillage Otsu4: Repeat stepméthode
Cette 2 for change in the class
est utilisée center;
pour otherwise
sélectionner stop
une the seuil en minimi-
valeur
iteration.
sant les variances intra-classe de deux classes. La variance intra-classe peut être exprimée par l’équation
Step 5: The threshold is calculated by the mean of the kth class center
suivante : and (k − 1) class center:
2
σw (T ) = Pb (T ) ·1σ 2 (T ) + P (T ) · σf2 (T )
T = (bC + C ).f (5.6)
k k −1
2
Où Pf et Pb sont la probabilité d’occurrences de classe de l’objet et du fond ; T est la valeur seuil
The result of the image segmentation is shown in Figure 5.4.
initiale, qui est choisie arbitrairement par un algorithme, et σf2 et σb2 sont les variances des classes de
Otsu-Clustering Thresholding Method: This method is used to select a threshold
l’objet et du fond.
value by minimizing the within class variances of two clusters [11,12]. The
La probabilité d’occurrences de classe de l’objet et du fond peut être notée par l’équation suivante :
within-class variance can be expressed by Equation 5.7:
P
T
σw2 (T ) P (T
=bP ) =2 P (G) 2
b (T )σ b (T ) + Pf (T )σ f (T ), (5.7)
G=0
P
L−1
Pf (T ) = of foreground
where Pf and Pb are the probability P (G) and background class
occurrences; T is the initial threshold +1
G=Tvalue, which is randomly selected
by some algorithm, and σ 2f and σb2 are the variances of foreground and
Où G est les valeurs de niveau de gris 0, 1, . . . , L − 1 et p(G) est la fonction de masse de probabilité
background clusters.
de G. Les variances
Thedes classes deofl’objet
probability et duand
foreground fond sont définies
background par
class l’équationcan
occurrences suivante
be :
denoted by Equation 5.8:
P
T
2 p(G)
σb2 (T ) = (G −
T
Mb (T )) Pb (T )

∑ p(G)
G=0
b (T ) =
PL−1
P 2 p(G)
σf2 (T ) = (GG=−
0 Mf (T )) Pf (T )
G=T +1 L−1
(5.8)

Pf (T ) = ∑ p(G),
G=T +1
86
where G is the gray level values {0,1,…,L − 1} and p(G) is the probability mass
 where Mb and Mf are the means of background and foreground clusters
respectively and can be defined by Equation 5.10:
T
CHAPITRE 6. SEGMENTATION ETM
EXTRACTION
f (T ) = G × pD’ATTRIBUTS
(G) ∑G=0
L−1
(5.10)
Où Mb et Mf sont respectivement les M b (T ) = desG
moyennes classes ∑
× p(G).d’objet et du fond, et qui peuvent être
définis par l’équation suivante : G=T +1
A lot of computations are involved P in
T computing the within class variance
M (T ) = G × p(G)
for each of the two classes for every possible
b threshold. Thus, the between-
G=0
class variance is computed by subtracting
P
L−1 the within class variance from the
total variance: Mf (T ) = G × p(G)
G=T +1
2 2
σ between (T ) = σtotal (T ) − σw2 (T )
Ainsi, la variance inter-classe est calculée en soustrayant la variance intra-classe de la (5.11)
variance totale :
2 2
= Pb (T )[µ b (T ) − M total ] + P f (T )[µ f (T ) − M total ] .
2 2 2
σbetween (T ) = σtotal (T ) − σw (T )
2
σtotal and Mtotal can be expressed by = Pthe Equation 5.12: 2 2
b (T )[µb (T ) − Mtotal ] + Pf (T )[µf (T ) − Mtotal ]
L−1
2
σtotal 2
et Mtotal peuvent être exprimésσpar
total = ∑
(G − M
l’équation 2 :
total ) p(G)
suivante

2
PG=0
L−1
2 (5.12)
σtotal = L−(G
1 −M
total ) × p(G)

=
Mtotal G=0 ∑ G × p(G).
P
L−1
MtotalG==0 G × p(G)
G=0
The main advantage of this method is its simple computation.
La Figure 6.9Figure
montre5.5l’image
showssegmentée en utilisant
the segmented outputun nombre
using différent
a different de clusters.
number of clusters.

FIGURE 5.5
Figure 6.9: Segmentation à l’aide de la méthode de seuillage d’Otsu.
Segmented output using the Otsu clustering thresholding method.

Seuillage basé sur l’entropie

Cette méthode est créée sur la base de la distribution de probabilité de l’histogramme des niveaux
de gris. Deux entropies peuvent être calculées : une pour les pixels noirs et l’autre pour les pixels
blancs :
255
P
g(i) = 1
i=0  
P
t  g(i) 
Eb (t) = − Pt
g(i)
× log 
Pt


i=0 g(j) g(j)
j=0
j=0 
255
P  g(i) 
Ew (t) = − P
255
g(i)
× log 
 P
255


i=t+1 g(j) g(j)
j=t+1 j=t+1

Où g(i) est l’histogramme normalisé. La valeur de seuil optimale unique est sélectionnée en maxi-
misant l’entropie des pixels noirs et blancs, et elle est représentée par l’équation suivante :

T = Argmaxt=0..255 Eb (t) + Ew (t)

p valeurs de seuil optimales peuvent être trouvées par l’équation suivante :

{T1 , ..., Tp } = Argmaxt1 <..<tp E(−1, t1 ) + E(t1 , t2 ) + .. + E(tp , 255)

Où :

87
 tn+1
g (i ) g (i )
E(tn , tn+1 ) = − ∑ log .
∑ ∑
tn+1 tn+1
i=tn +1 g( j) g( j)
j=tn +1 j = t n +1
CHAPITRE 6. SEGMENTATION ET EXTRACTION D’ATTRIBUTS
Figure 5.6 shows the output of the segmented image using an entropy-
based method.

FIGUREFigure
5.6 6.10: Segmentation en utilisant un seuillage par l’entropie.
Segmented output using entropy-based method.

 
tP
n+1  
E(tn , tn+1 ) = − g(i)
× log 

g(i) 

i=tn +1 P
tn+1
P
tn+1

g(j) g(j)
j=tn +1 j=tn +1

La Figure 6.10 illustre le résultat obtenu par l’application la méthode seuillage basée sur l’entropie.

6.2.3 Segmentation en régions

Une région dans une image est définie comme un groupe de pixels connectés ayant des proprié-
tés similaires. En général, les objets peuvent également être interprétés comme un groupe de pixels
connectés de propriétés similaires. Par conséquent, les régions peuvent être utilisées comme clé pour
la segmentation de l’image.
Dans la segmentation par région, les pixels correspondant à un objet sont regroupés. Les tech-
niques de segmentation basées sur les régions intègrent deux mesures de similarité de base, à savoir
la similitude des valeurs (des pixels similaires à leurs voisins sont pris en compte dans la région) et
la proximité spatiale (des pixels spatialement proches sont pris en compte dans la région). Par consé-
quent, une région ou un objet dans n’importe quelle image se compose de pixels proches dans l’espace
avec des valeurs de gris similaires. Deux techniques principales de segmentation par région sont la
croissance et la division et la fusion de régions.

Croissance de régions

La méthode de segmentation basée sur la croissance des régions est une approche ascendante qui
part d’un ensemble de pixels initiaux (appelés germes). Ces germes poussent ensuite sur la base de
quelques mesures de similitude (niveau de gris, couleur, texture). Ces germes peuvent être sélectionnées
soit manuellement (sur la base de certaines connaissances préalables), soit automatiquement (selon
l’application particulière).
L’algorithme se compose de deux étapes :
1. Trouver les points de départ des régions : c’est la partie critique de l’algorithmie. En effet, l’étape
de croissance suivante va utiliser une mesure de similarité pour choisir les pixels à agglomérer.
Si le point de départ est situé dans une zone non homogène, la mesure de similarité Va produire
de fortes variations et la croissance va s’arrêter très tôt. Par conséquent, il convient de choisir
les points de départs (graines ou seeds en anglais) dans des zones les plus homogènes possibles.
2. Croissance : cette étape a pour objectif de faire grossir une région en agglomérant des pixels
voisins. Les pixels sont choisis afin de maintenir l’homogénéité de la région. Pour cela, il faut
définir un indicateur d’homogénéité. Les pixels voisins sont ajoutés la région si cet indicateur reste
vrai. La croissance s’arrête lorsqu’on ne peut plus ajouter de pixels sans briser l’homogénéité.
Les indicateurs d’homogénéité d’une région R dans une image f peuvent être les suivants :

88
CHAPITRE 6. SEGMENTATION ET EXTRACTION D’ATTRIBUTS

(a) (b) (c) (d)

Figure 6.11: Segmentation par croissance de régions

— le contraste sur la région : maxR f (x, y) − minR f (x, y) < σ.

5.6 Segmentation en regions 133
— l’écart-type de la région :
5. 6.4 Décomposition etPfusion (Split and merge)
1 2
N (f (x, y) − m) < σ 2
R
Les algorithmes de type décomposition/fusion exploitent les caractéris—
1
P
= |R| est
Où Ntiques le cardinal
propres de R et
de chaque m= N
région f (x, y)
(surface, la moyenne
intensité des niveaux
lumineuse, de gris de la région
colorimétrie,
R
R. texture, etc.). Cette technique enchaine les deux phases suivantes :
1. Décomposition (Split) on découpe itérativement l’image jusqu’a avoir
:

— les différences sur des voisinages :

des blocs contenant exclusivement des pixels similaires. Les critéres de
similarité ou d’hornogénéité sont analogues a ceux qu’on utilise pour la
∀(P1 , P2 ) ∈ R × R, voi sin s |f (P2 ) − f (P1 )| < σ
croissance de régions. La méthode couramment utilisée consiste a faire une
dichotomie par blocs de l’image. Pour cela, on commence par définir un
Où σ > 0 est un seuil fixé.
bloc de la taille de llimage, puis on examine le contenu de ce bloc. Si le bloc
La Figure 6.11 le résultat des’il
représente(c’est—a—dire
est homogene contient exclusivement
l’application des pixels
de la segmentation similaires)de régions.
par croissance
alors on arréte la décomposition. Sinon, on découpe le bloc en 4 sous-blocs
examine
Décompositionetetonfusion contenu
le and
(Split de chaque sous—bloc. On continue jusqu’a ce qu’il
merge)
n’y ait plus besoin de décomposer les blocs. Le résultat obtenu est donc
de typejointif
un ensemble
Les algorithmes de blocs de différentes
décomposition/fusion tailles
exploitent lesqui recouvre entiérement
caractéristiques propres de chaque
Pimage.
région (surface, intensité lumineuse, colorimétrie, texture, etc.). Cette technique enchaı̂ne les deux
Uimplémentation
phases suivantes : la plus simple pour cette méthode consiste a définir une
structure d’arbre appelée QuadTree. C’est un arbre dans lequel chaque
1. Décomposition (Split) : on
noeud représente undécoupe itérativement
bloc. Chaque l’image done
noeud posséde jusqu’à avoir des blocs
0 sous-noeud (bloc contenant
exclusivement des pixels
homogene) ou 4 similaires.
sous—noeudsLes(bloc
critères de similarité ou d’homogénéité sont analogues à
non—homogene).
ceux qu’on utilise pour la croissance de régions.

1.1 1.2
racine

1.3 1.4

Fig. 5.25 Quad Tree Figure 6.12: Quad Tree

La méthode couramment utilisée consiste à faire une dichotomie par blocs de l’image. Pour
cela, on La
commence par définir
décomposition un bloc
finale de la taille
est définie par de
les l’image, puis on aux
blocs associés examine le contenu
feuilles de de ce
l’arbre. On obtient ainsi liste blocs différentes tailles et
bloc. Si le bloc est homogène (c’est—a—dire s’il contient exclusivement des pixels similaires)
une de de posi-
arrêteSilaladécomposition.
alors on tions. Sinon, on permet
structure du QuadTree découpeune navigation
le bloc aisée entre
en 4 sous-blocs et bloc
on examine le
conteneur (parent) et sous-blocs (enfants), elle ne permet pas de naviguer
contenu de chaque sous—bloc. On continue jusqu’à ce qu’il n’y ait plus besoin de décomposer les
facilement entre des blocs Voisins. Pour cela, il est préférable de construire
blocs. Leetrésultat
d’utiliserobtenu est donc un ensemble jointif de blocs de différentes tailles qui recouvre
un graphe d’adjacence.

89
 CHAPITRE 6. SEGMENTATION ET EXTRACTION D’ATTRIBUTS

entièrement l’image. L’implémentation la plus simple pour cette méthode consiste a définir une
structure d’arbre appelée QuadTree(Figure 6.12). C’est un arbre dans lequel chaque nœud
représente un bloc. Chaque nœud possède donc 0 sous-nœud (bloc homogène) ou 4 sous—nœuds
(bloc non—homogène).
La décomposition finale est définie par les blocs associés aux feuilles de l’arbre. On obtient ainsi
une liste de blocs de différentes tailles et positions. Si la structure du QuadTree permet une
navigation aisée entre bloc conteneur (parent) et sous-blocs (enfants), elle ne permet pas de
naviguer facilement
Chapter [Link]
entre des blocs voisins. Pour cela, il est préférable de construire et d’utiliser
June 22, 2006 Page 245
un graphe d’adjacence.
2. Fusion (Merge) : on regroupe les blocs voisins s’ils sont similaires. On définit un critère de
similarité entre blocs. Le plus simple est d’étendre la définition de similarité entre pixels définie
IMAGE SEGMENTATION 245
lors de l’étape de décomposition.

FIGURE 6.16
Figure 6.13: Les étapes de l’algorithme de décomposition et de fusion
The steps of split and merge algorithm

Ainsi, on peut assimiler un bloc a un gros pixel en calculant sa valeur/couleur moyenne, et en

utilisant le graphe d’adjacence pour naviguer vers les blocs voisins. Cet algorithme construit les
Thresholding:
régions une par une, en regroupant progressivement
At this point lescan
several regions blocs jointifs autour
be merged with thed’un bloc de départ.
exception
Thresholding is an of two subquadrants that include some points of the object. In
L’algorithme
operation in fusionne
which a lesFigure
blocs6.16(c)
adjacents à la région, formant
R11 , R12 , R ainsi une région de plus en plus
the regions 21 , R22 , R23 , R33 , . . . , R14 satisfy the
reference gray
grande(Figure 6.13).level is predicate P (Ri ) = TRUE and all of them are merged to form a larger
selected using histo- region whereas the regions R13 and R42 do not satisfy the predicate
gram such that the P (Ri ). These two subquadrants do not satisfy the predicate and hence
object and back- they split further as in Figure 6.16(d). At this point all the regions satisfy
6.3 Extraction et représentation d’attributs
ground can be the predicate P and merging the appropriate region from the last split
separated. operation gives the final segmented region as in Figure 6.16(e).
L’extraction d’attribut est le processus par lequel certaines caractéristiques intéressantes d’une
image sont 6.7
détectées et représentées
SEGMENTATION pour un
USING traitement ultérieur. C’est une transition de la représen-
THRESHOLD
tation des données picturales vers des images quantitatives. La représentation résultante peut ensuite
Thresholding is one of the most important techniques used for image
être utilisée comme entrée poursegmentation.
un certain nombre de techniques
In this section we discuss de
thereconnaissance et de
various thresholding classification
tech-
niques for
de formes, qui étiquettent, classifient ou image segmentation.
reconnaissent Thelemerits
ensuite and sémantique
contenu demerits of various
de l’image ou de
techniques are also discussed.
ses objets.

6.3.1 Attributs des objets binaires

Un objet binaire est une région connectée au sein d’une image binaire f (x, y), qui sera notée Oi ,
avec i > 0. Mathématiquement, nous pouvons définir Oi (x, y) comme suit :

90
CHAPITRE 6. SEGMENTATION ET EXTRACTION D’ATTRIBUTS

(
1 si f (x, y) ∈ Oi
Oi (x, y) =
0 ailleurs

Différents attributs peuvent être calculer en opérant sur l’objet binaire.

L’aire (Surface)

L’aire du ième objet Oi , mesurée en pixels, est donnée par :

MP−1 NP
−1
Ai = Oi (x, y)
x=0 y=0

Centre de gravité

Les coordonnées du centre de gravité (également appelé centroı̈de de l’objet) de l’objet Oi , notées
− −
(xi , yi ), sont données par :

− 1
MP−1 NP
−1
xi = Ai x × Oi (x, y)
x=0 y=0
et
− 1
MP−1 NP
−1
yi = Ai y × Oi (x, y)
x=0 y=0

Où Ai est l’aire de l’objet Oi .

Moment d’inertie

C’est l’angle θ qui représente l’angle entre l’axe vertical et l’axe du moment d’inertie, mesuré dans
le sens antihoraire. La Figure 6.14 illustre ce concept. Notez que l’origine du système de coordonnées
a été déplacée vers OBJECT
BINARY le centre de la zone de l’objet. Mathématiquement, θ peut être calculé
FEATURES 451 à l’aide de

FIGURE 18.2
Figure 6.14:Axis
Le of least second
moment moment.
d’inertie.

l’équation suivante
18.3.3 : Axis of Least Second Moment
The axis of least second moment is used Mto P−1 NP
provide
−1 information about the object’s
xOi (x,y)
orientation relative to the coordinate plan ofx=0 they=0
image. It can be described as the axis
of least inertia,tan(2θ
that is,i )the
= 2line
× Mabout
P−1 NP which it takes
−1 MP−1the
P
N least amount of energy to
−1

rotate the object. x2 Oi (x,y)− y 2 Oi (x,y)

x=0 y=0 x=0 y=0
By convention, the angle θ represents the angle between the vertical axis and the
axis of least second moment, measured counterclockwise. Figure 18.2 illustrates this
Projections concept. Note that the origin of the coordinate system has been moved to the center
of area of the object.
Les projections horizontale hi (x) et verticale vi (y) d’un objet binaire sont obtenues par les équations
Mathematically, θ can be calculated using equation (18.6):
suivantes :
M−1 N−1
x=0 y=0 xOi (x, y)
tan (2θi ) = 2 × M−1 N−1 M−1 N−1 2 (18.6)
x=0 y=0 x Oi (x, y) −
2
x=0 y=0 y Oi (x, y)
91
 CHAPITRE 6. SEGMENTATION ET EXTRACTION D’ATTRIBUTS
452 FEATURE EXTRACTION AND REPRESENTATION

FIGURE
Figure 6.15:18.3 Horizontal and
Les projections vertical projections.
horizontale et verticale.

Projections are very useful

−1 and compact shape descriptors. For example, the
MP NP−1
height and width hi (x) = objectOwithout
of an i (x, y) holes
et vi (y)
can = Oi (x, y)
be computed as the maximum
value of the object’s vertical
x=0and horizontal projections,y=0 respectively, as illustrated in
Figure 18.3.
Les projections sont des descripteurs
The equations de formeoftrès
for the coordinates utiles ofetarea
the center compacts. Par (equations
of the object exemple, la hauteur et
la largeur d’un(18.4) andsans
objet (18.5)) can be
trous rewrittenêtre
peuvent as a calculées
function of comme
the horizontal and vertical
la valeur maximaleprojec-des projections
tions as follows:
verticales et horizontales de l’objet, respectivement, comme illustré à la Figure 6.15. Les équations des
M−1
 réécrites en fonction des projections horizontales
coordonnées du centre de l’aire de l’objet peuvent
1 être
x̄i = xhi (x) (18.9)
et verticales comme suit : Ai
x=0

and − 1
MP−1 − 1
NP
−1
xi = Ai x × hi (x) et yi = Ai y × vi (y)
x=0 N−1 y=0
1 
ȳi = yvi (y) (18.10)
Ai
y=0
Nombre d’Euler

Le nombre18.3.5
d’EulerEuler objet ou d’une image (E) est défini comme le nombre de composants
d’un Number
connectés (C) The
moins le number
Euler nombreofde object(H)
antrous :
or image (E) is defined as the number of connected
components (C) minus the number of holes (H):
E =C −H
E =C−H (18.11)

Alternativement, le nombre d’Euler peut être exprimé comme la différence entre le nombre de
convexités et le nombre de concavités dans l’image ou la région. Le nombre d’Euler est considéré
comme un descripteur topologique, car il n’est pas affecté par les déformations , à condition qu’ils ne
remplissent pas les trous ou ne séparent pas les composants connectés.
BINARY OBJECT FEATURES 453

FIGURE 18.4 Examples of two regions with Euler numbers equal to 0 and −1, respectively.
Figure 6.16: Exemples de deux régions avec des nombres d’Euler égaux à 0 et -1, respectivement.
Alternatively, the Euler number can be expressed as the difference between the
number of convexities and the number of concavities in the image or region. The
La Figure 6.16 montre des exemples
Euler number is considereddea topological
deux objets différents
descriptor, because et
it isleurs numéros
unaffected by d’Euler.
deformations (such as rubber sheet distortions), provided that they do not fill holes
or break connected components apart. Figure 18.4 shows examples of two different
92 objects and their Euler numbers.

18.3.6 Perimeter
CHAPITRE 6. SEGMENTATION ET EXTRACTION D’ATTRIBUTS

Périmètre

Le périmètre d’un objet binaire Oi peut être calculé en comptant le nombre de pixels d’objet (dont
la valeur est 1) qui ont un ou plusieurs pixels de fond (dont la valeur est 0) comme voisins. Une
méthode alternative consiste à extraire d’abord le bord (contour) de l’objet puis à compter le nombre
de pixels dans la bordure résultante.

Rapport d’épaisseur

Le rapport d’épaisseur Ti d’un objet binaire Oi est une valeur qui relie l’aire de l’objet et son
périmètre par l’équation suivante :

4πAi
Ti = Pi2

Où Ai est l’aire et Pi est le périmètre.

Le rapport d’épaisseur est souvent utilisé comme mesure de la rondeur. Étant donné que la valeur
maximale de Ti est 1 (ce qui correspond à un cercle parfait), pour un objet générique, plus son rapport
de d’épaisseur est élevé, plus il est rond. Cette valeur peut également être utilisée comme mesure de
inverse, 1/Ti est parfois appelé rapport
régularité et son454 d’irrégularité
FEATURE EXTRACTION ANDouREPRESENTATION
de compacité.

454 FEATURE EXTRACTION AND REPRESENTATION

FIGURE
Figure 18.5 Examples
6.17: Exemples of a compact
de régions (a) and a(a)
compactes noncompact (b) regions. (b).
et non compactes

La Figure 6.17 montre un exemple de région compacte et non compacte.

Excentricité

L’excentricité d’un objet est définie comme le rapport entre les axes majeurs et mineurs de l’objet
(Figure 6.18). FIGURE 18.5 Examples of a compact (a) and a noncompact (b) regions.

FIGURE 18.6 Eccentricity (A/B) of a region.

The thinness ratio is often used as a measure of roundness. Since the maximum
value for Ti is 1 (which corresponds to a perfect circle), for a generic object the
higher its thinness ratio, the more round it is. This figure of merit can also be used
as a measure of regularity and its inverse, 1/Ti is sometimes called irregularity or
compactness ratio. Figure 18.5 shows an example of a compact and a noncompact
region. FigureFIGURE 18.6 Eccentricity
6.18: Excentricité (A/B) ofd’une
(A/B) a region.
région.

18.3.8 The thinness ratio is often used as a measure of roundness. Since the maximum
Eccentricity
value for Ti is 1 (which corresponds to a perfect circle), for a generic object the
Allongement higher its thinness
The eccentricity of anratio,
objecttheismore roundasit the
defined is. This
ratiofigure of major
of the merit can
andalso be used
minor axes of
as a measure of regularity
the object (Figure 18.6). and its inverse, 1/T i is sometimes called irregularity or
compactness ratio. Figure 18.5 shows an example of a compact and a noncompact
L’Allongement mesure
region. la relation entre les dimensions du cadre de sélection d’un objet :
18.3.9 Aspect Ratio
xmax −xmin +1
18.3.8ratio
Eccentricity AL = ymax −ymin +1
The aspect (AR) is a measure of the relationship between the dimensions of the
bounding box of an object.
The eccentricity It is isgiven
of an object by as the ratio of the major and minor axes of
defined
the object (Figure 18.6). 93
xmax − xmin + 1
AR = (18.13)
18.3.9 Aspect Ratio ymax − ymin + 1
 CHAPITRE 6. SEGMENTATION ET EXTRACTION D’ATTRIBUTS
BINARY OBJECT FEATURES 455

FIGURE 18.7
Figure 6.19:Elongatedness (a/b)
Allongement (a/b) of arégion.
d’une region.

où (xmin , ymin ) et (xmax , ymax ) sont les coordonnées des coins supérieur gauche et inférieur droit du
where
cadre (xmin , yentourant
de contour min ) and un
(xmax max ) are the coordinates
, yrespectivement.
objet, of the top left and bottom
right cornersdeofnoter
Il convient the bounding box surrounding
que l’allongement an object,
n’est pas invariant respectively.
en rotation et ne peut pas être utilisé
It should be noted that the aspect ratio is not rotation invariant and cannot be used
pour comparer des objets en rotation les uns contre les autres à moins qu’il ne soit normalisé d’une
to compare rotated objects against one another unless it is normalized somehow, for
manière ou d’une autre, par exemple, en calculant l’AL après avoir aligné l’axe du moment d’inertie
example, by computing the AR after aligning the axis of least second moment to
dans la direction horizontale (Figure 6.19).
the horizontal direction. Such normalized representations of the aspect ratio are also
referred
Les momentsto as the elongatedness of the object (Figure 18.7).

Le moment 2D d’ordre (p + q) d’une image numérique f (x, y) est défini comme :

18.3.10 Moments MP−1 NP
−1
mpq xp · y q · f (x, y)
The 2D moment of order (p + q) ofx=0
a digital
y=0 image f (x, y) is defined as
Où M et N sont respectivement la hauteur et la largeur de l’image, et p et q sont des entiers positifs
 N−1
M−1 
non nuls.
pq m = xp yq f (x, y) (18.14)
Les moments centraux sont l’équivalent invariant par translation des moments :
x=0 y=0  q
MP−1 NP−1  
− p −
µpq x − x · y − y · f (x, y)
where M and N are the imagex=0
height
y=0 and width, respectively, and p and q are positive

nonzero
Où : integers.
Central moments are the translation-invariant
− − equivalent of moments. They are
x= mm10
et y = m 01
defined as 00 m 00

Les moments centraux normalisés sont

M−1
définis par :
 N−1 
μpq = ηpq−=x̄)µpq
(x µp (y − ȳ)q f (x, y)
γ (18.15)
00
456 x=0 y=0
Où γ = + 1,pour (p + q) > 1. Un ensemble de sept moments invariants RST, φ1 − φ7 , initialement
p+q FEATURE EXTRACTION AND REPRESENTATION
2
TABLE 18.1 RST-Invariant Moments
where
φ1 = η20 + η02
φ2 = (η20 − η02 )2 + 4η211
m m01
10
φ3 x̄ =
= (η30 − 3η12 )2 + (3η21 − η03 )2 and ȳ = (18.16)
φ4 2 m
= (η30 + η12 ) + (η2100 + η03 )2

m00 
φ5 = (η30 − 3η12 )(η30 + η12 ) (η30 + η12 )2 − 3(η21 + η03 )2
 
+(3η − η )(η + η ) 3(η + η ) − (η 2
+ η03 )2
The normalized central moments
 are definedas
21 03 21 03 30 12 21

φ6 = (η30 − η02 ) (η30 + η12 )2 − (η21 + η03 ) 2

+ 4η11 (η30 + η12 )(η21 + η03 )
 
φ7 = (3η21 − η03 )(η30 + η12 ) (η30 + η12 )2 − 3(η21 + η03 )2
μpq 
−(η30 − 3η12 )(η21
pq = + ηγ )
+ηη ) 3(η − (η21 + η03 )2
2
03 30 12 (18.17)
μ00
where Figure 6.20: Ensemble de moments invariants
p+q
γ= +1 (18.18)
proposé par Hu, peut être dérivé de moments centraux
2 normalisés du deuxième et du troisième ordre.
for (p +
Ils sont répertoriés dans laq)Figure
> 1. 6.20.
A set of seven RST-invariant moments, φ1 –φ7 , originally proposed by Hu in
1962 [Hu62], can be derived from second- and third-order normalized central mo-
94 ments. They are listed in Table 18.1.

In MATLAB
CHAPITRE 6. SEGMENTATION ET EXTRACTION D’ATTRIBUTS

6.3.2 Descripteur de contours

Les techniques de représentation et de description basées sur les contours supposent que le contour
d’un objet peuvent être représentés dans un système de coordonnées pratique (cartésien - le plus
courant, polaire ou tangentiel) et s’appuient exclusivement sur des pixels limites pour décrire la région
ou l’objet.

Code de chaı̂nage et code Freeman

Les codes de chaı̂nage sont des méthodes alternatives pour tracer et décrire un contour. Elle
est représenté par une séquence de segments de ligne droite de longueur et de direction spécifiées
(généralement 1). Le mécanisme de code de chaı̂ne le plus simple, consiste à attribuer un numéro à la
direction suivi d’un algorithme de suivi des points comme suit : droite (0), bas (1), gauche (2) et haut
(3). 460 FEATURE EXTRACTION AND REPRESENTATION

FIGURE 18.10 Chain code and Freeman code for a contour: (a) original contour;
Figure 6.21: Code de (b)chaı̂ne et version
subsampled code ofFreeman
the contour;pour uncode
(c) chain contour : a) (d)
representation; contour
Freeman d’origine
code ; b) version sous-
échantillonnée du contour ; (c) représentation du code de chaı̂ne ; (d) Représentation du code Freeman.
representation.

En supposant quenumber
le nombre totalfollowed
to the direction de points limites
by a bug tracking est p (le
algorithm périmètre
as follows: du contour), le tableau
right (0),
down (1), left (2), and up (3). Assuming that the total number of boundary points
C (de taille p), où C(p) = 0,
is p (the 1, 2, 3,
perimeter contient
of the contour), le
the code
array C de chaı̂ne
(of size du C(p)
p), where contour.
= 0, 1, 2,Une
3, version modifiée du
contains the chain code of the boundary. A modified version of the basic chain code,
code de chaı̂ne de base, connue
known sous le
as the Freeman nom
code, uses de
eightcode Freeman,
directions utilise
instead of four. huit
Figure 18.10directions
shows au lieu de quatre
(Figure 6.21). an example
emple de of a contour,
contour, son code its chain
de code, and its
chaı̂ne etFreeman code. Freeman.
son code
BOUNDARY DESCRIPTORS
Once the chain code for a boundary has been computed, it is possible to convert 461
the resulting array into a rotation-invariant equivalent, known as the first difference,

FIGURE
Figure 6.22: 18.11
Chaı̂neChain code,premières
de code, first differences, and shape
différences number.
et code de forme.

95
which is obtained by encoding the number of direction changes, expressed in multi-
ples of 90◦ (according to a predefined convention, for example, counterclockwise),
 CHAPITRE 6. SEGMENTATION ET EXTRACTION D’ATTRIBUTS

Une fois le code de chaı̂ne d’un contour est calculé, il est possible de convertir le tableau résultant
en un équivalent invariant en rotation, connu sous le nom de première différence, qui est obtenu en
codant le nombre de changements de direction, exprimé en multiples de 90đ ( selon une convention
prédéfinie, par exemple dans le sens antihoraire), entre deux éléments consécutifs du code Freeman.
La Figure ??ontre un exemple de contour, son code de chaı̂ne, les premières différences et le code de
forme.

Signatures

Une signature est une représentation 1D d’une frontière, généralement obtenue en représentant la
frontière dans un système de coordonnées polaires et en calculant la distance r entre chaque pixel le
long de la frontière et le centroı̈de de la région, et l’angle θ sous-tendu entre une ligne droite reliant le
pixel limite au centre de gravité et une référence horizontale (Figure 6.23, en haut).
462 FEATURE EXTRACTION AND REPRESENTATION

462 FEATURE EXTRACTION AND REPRESENTATION

FIGURE 18.12 Distance × angle signatures for two different objects. Redrawn from
[GW08]. Figure 6.23: Exemple de signature.

Le tracé résultant de toutes les valeurs calculées pour 0 ≤ θ ≤ 2π (Figure 6.23, en bas) fournit une
FIGURE
représentation concise de18.12 Distance ×
la frontière angle
qui est signatures
invariantefor par
two translation
different objects.
peutRedrawn from
être rendue invariante par
[GW08].
rotation (si le même point de départ est toujours sélectionné), mais n’est pas à l’échelle invariant.

FIGURE 18.13 Effect of noise on signatures for two different objects. Redrawn from
[GW08].

18.4.3 Fourier Descriptors

The idea behind Fourier descriptors is to traverse the pixels belonging to a boundary,
starting from an arbitrary point, and record their coordinates. Each value in the result-
ing list of coordinate pairs (x0 , y0 ), (x1 , y1 ), . . . , (xK−1 , yK−1 ) is then interpreted as
FIGUREa complex
18.13 number
Effect xof
k+ noise onk =
jyk , for signatures
0,du . . , Kfor
1, .bruit two
−sur
1. The differentFourier
objects. Redrawn from
Figure 6.24: Effet lesdiscrete
signatures. transform
[GW08].(DFT)6 of this list of complex numbers is the Fourier descriptor of the boundary.
The inverse DFT restores the original boundary. Figure 18.14 shows a K-point digital
boundary in the xy plane and the first two coordinate pairs, (x0 , y0 ) and (x1 , y1 ).
La Figure 6.24 illustre les effets du bruit sur la signature d’un contour.
6 The discrete Fourier transform was introduced in Chapter 11.
18.4.3 Fourier Descriptors
Descripteurs de The
Fourier
idea behind Fourier descriptors is to traverse the pixels belonging to a boundary,
starting from an arbitrary point, and record their coordinates. Each value in the result-
ingles
L’idée derrière listdescripteurs
of coordinate pairs (x0 , y0 ), (x
de Fourier 1, y
est 1 ),traverser
de . . . , (xK−1 ,les
yK−1 ) is then
pixels interpreted asà une frontière, à
appartenant
a complex number xk + jyk , for k = 0, 1, . . . , K − 1. The discrete Fourier transform
partir d’un point(DFT)
arbitraire,
6 of this et
listd’enregistrer leurs is
of complex numbers coordonnées. Chaqueofvaleur
the Fourier descriptor dans la liste résultante
the boundary.
de paires de coordonnées (x0 restores
The inverse DFT , y0 ), (xthe
1, y1 ), ..., boundary.
original (xK−1 , yFigure
K−1 ) 18.14
est alors
shows ainterprété comme un nombre
K-point digital
complexe xk + jyboundary
k , pour k = 0, 1, ..., K − 1.
in the xy plane and the first two coordinate pairs, (x0 , y0 ) and (x1 , y1 ).

La transformée
6 Thede Fourier
discrete discrètewas(DFT)
Fourier transform introducedde cette11.
in Chapter liste de nombres complexes est le descripteur
de Fourier du contour. La Figure 6.25 montre une frontière numérique du K points dans le plan xy
et les deux premières paires de coordonnées, (x0 , y0 ) et (x1 , y1 ).

96
CHAPITRE 6. SEGMENTATION ET EXTRACTION D’ATTRIBUTS
BOUNDARY DESCRIPTORS 463

FIGURE
Figure 6.25:18.14 Fourier descriptor
Descripteur de Fourierof a d’un
boundary.
contour.

La Figure 6.26 montre un exemple d’une frontière contenant 1467 points (partie (a)) et les résultats
In MATLAB
de sa reconstruction (en appliquant la DFT suivie par IDFT) en utilisant un nombre variable de termes.
The IPT does not have a built-in function for computing the Fourier descriptor of a
La partie (b) montre les résultats de la reconstruction avec le même nombre de points pour des raisons
boundary, but it is not too difficult to create your own function. The basic procedure
464
de vérification. FEATURE EXTRACTION AND REPRESENTATION
is to compute the boundaries of the region, convert the resulting coordinates into
complex numbers (e.g., using the complex function), and apply the fft function
to the resulting 1D array of complex numbers. Refer to Chapter 12 of [McA04] or
Chapter 11 of [GWE04] for possible implementations.
One of the chief advantages of using Fourier descriptors is their ability to represent
the essence of the corresponding boundary using very few coefficients. This property
is directly related to the ability of the low-order coefficients of the DFT to preserve
the main aspects of the boundary, while the high-order coefficients encode the fine
details.

 EXAMPLE 18.4
Figure 18.15 shows an example of a boundary containing 1467 points (part (a)) and
the results of reconstructing it (applying the DFT followed by IDFT) using a variable
number of terms. Part (b) shows the results of reconstructing with the same number
of points for the sake of verification. Parts (c)–(f) show the results for reconstruction
with progressively fewer points: 734, 366, 36, and 15, respectively. The chosen values
for parts (c)–(f) correspond to approximately 50%, 25%, 2.5%, and 1% of the total
number of points, respectively. A close inspection of the results shows that the image
reconstructed using 25% of the points is virtually identical to the one obtained with
50% or 100% of the points. The boundary reconstructed using 2.5% of the points still
preserves much of its overall shape, and the results using only 1% of the total number
of points can be deemed unacceptable.

Figure 6.26:FIGURE
Exemple18.15 Example of boundary
de reconstruction reconstruction
des limites using
utilisant des Fourier descriptors:
descripteurs de Fourier(a) original
: (a) image originale ;
(b – f) imageimage; (b–f) reconstructed
reconstruite image using 100%,
utilisant respectivement 50%,50%, 25%,
25%, 2.5%,
2, 5% et and
1% 1%du of the total
nombre number
total de points.
of points, respectively.

Les parties (c) - (f) montrent progressivement les résultats de la reconstruction avec moins de
points : 734,18.5 HISTOGRAM-BASED
366, 36 et 15, respectivement.(STATISTICAL) FEATURES
Les valeurs choisies pour les parties (c) - (f) correspondent
respectivement à environ 50%, 25%, 2, 5% et 1% du nombre total de points. Un examen attentif des
Histograms provide a concise and useful representation of the intensity levels in a
résultats montre que image.
grayscale l’imageInreconstruite
Chapter 9, weàlearned how25%
l’aide de des points
to compute est pratiquement
and display identique à celle
an image’s his-
50% ou
obtenue avectogram 100% des points. La frontière reconstruite en utilisant 2,
and we used histogram-based techniques for image enhancement. In Chapter 5% des points conserve
16, we extended
encore une grande partie dethat
sa discussion to color
forme globale, et images. In thisutilisant
les résultats section, we 1% du
are interested
seulement in nombre total
using histograms (or numerical descriptors that can be derived from them) as features7
de points peuvent être jugés inacceptables.
that describe an image (or its objects).
The simplest histogram-based descriptor is the mean gray value of an image,
6.3.3 Attributs basés
representing sur l’histogramme
its average intensity m and given by

Les histogrammes fournissent une représentation

 concise et utile des niveaux d’intensité dans une
L−1
m = rj p(rj )
image en niveaux de gris. Le descripteur basé sur l’histogramme le plus simple est(18.19)
la valeur moyenne
j=0

where rj is the jth gray level (out of a total of L possible values), whose probability 97
of occurrence is p(rj ).
 CHAPITRE 6. SEGMENTATION ET EXTRACTION D’ATTRIBUTS

des niveaux de gris d’une image m, donnée par :

P
L−1
m= rj p(rj )
j=0

Où rj est le j ième niveau de gris (sur un total de L valeurs possibles), dont la probabilité d’occur-
rence est p(rj ).
La valeur de gris moyenne peut également être calculée directement à partir des valeurs de pixels
de l’image d’origine f (x, y) de taille M × N par l’équation suivante :

1
MP−1 NP
−1
[m = M ·N f (x, y)
x=0 y=0

La moyenne est un descripteur qui fournit une mesure de la luminosité globale de l’image ou de
l’objet correspondant. Il est également invariant, mais, il n’est pas pertinent comme attribut. L’écart
type σ d’une image est donné par :
s
P
L−1
2
σ= (rj − m) p(rj )
j=0

Où m est la moyenne de l’image. Le carré de l’écart-type est la variance, également connue sous le nom
de moment de second ordre normalisé de l’image. L’écart type fournit une représentation concise du
contraste global. Semblable à la moyenne, il est compact et invariant RST, mais il est peu discriminant.
Le moment de troisième ordre d’un histogramme est une mesure de son asymétrie par rapport au
niveau moyen. Il est défini par :

1
P
L−1
3
skew = σ3 (rj − m) p(rj )
j=0

Où σ est l’écart type. Le signe de l’inclinaison indique si le sommet de l’histogramme se propage
vers la droite (asymétrie positive) ou vers la gauche (asymétrie négative). Si la valeur moyenne (m),
l’écart type (σ) et le mode de l’image (définis comme le pic le plus élevé de l’histogramme) sont connus,
l’asymétrie peut être calculée comme suit :
m − mode
skew =
σ
Le descripteur d’énergie fournit une autre mesure de la façon dont les valeurs de pixels sont
distribuées le long de la plage de niveaux de gris : les images avec une seule valeur constante ont une
énergie maximale (c’est-à-dire, énergie = 1) ; les images avec peu de niveaux de gris auront une énergie
plus élevée que celles avec beaucoup de niveaux de gris. Le descripteur d’énergie peut être calculé par
l’équation suivante :
P
L−1
2
energy = [p(rj )]
j=0

Les histogrammes fournissent également des informations sur la complexité de l’image, sous la forme
d’un descripteur d’entropie. Plus l’entropie est élevée, plus l’image est complexe. La formulation ma-
thématique de l’entropie est :
P
L−1
entropy = − p(rj )log2 (p(rj ))
j=0

6.3.4 Attributs de texture

La texture peut être un descripteur discriminant d’une image (ou de l’une de ses régions). Bien
qu’il n’y ait pas de définition universellement acceptée de la texture, les techniques de traitement
d’image associent généralement la notion de texture à des propriétés d’image (ou de région) telles que
le lissé (ou son opposé, la rugosité), la grossièreté et la régularité.

98
CHAPITRE 6. SEGMENTATION ET EXTRACTION D’ATTRIBUTS

(a) (b) (c)

(d) (e) (f)

Figure 6.27: Trois textures avec leurs histogrammes

La Figure 6.27 montre un exemple de texture ainsi que leurs histogrammes.

Il existe trois approches principales pour décrire les propriétés de texture dans le traitement
d’images : structurelle, spectrale et statistique. Nous nous concentrerons sur les approches statis-
tiques, en raison de leur utilité et leur facilité de calcul.
Parmi les descripteurs statistiques les plus simples pour la description de la texture se compose
des descripteurs d’histogramme de l’image (ou de la région) suivants : moyenne, variance (ou sa
racine carrée, l’écart-type), asymétrie, énergie (utilisée comme mesure de uniformité) et l’entropie. La
variance est parfois utilisée comme un descripteur normalisé de la rugosité (R), défini par :

1
R=1− 1+σ 2

où σ 2 est la variance normalisée (à un intervalle [0, 1]). R = 0 pour les zones d’intensité constante,
c’est-à-dire à texture lisse.

Tableau 6.1: Descripteurs de texture statistique pour les trois images de la Figure 6.27

Texture m σ R Asymétrie Uniformité Entropie

Lisse 147.1459 47.9172 0.0341 -0.4999 0.0190 5.9223
Grossière 138.8249 81.1479 0.0920 -1.9095 0.0190 5.8405
Régulière 79.9275 89.7844 0.1103 10.0278 0.1100 4.1181

Le Tableau 6.1 montre les valeurs des descripteurs de texture statistiques représentatifs pour les
trois images de la Figure 6.27.
Comme prévu, la texture régulière a l’uniformité la plus élevée (et l’entropie la plus faible) des
trois. De plus, la texture grossière présente une valeur de rugosité normalisée plus élevée que la texture
lisse, ce qui est également logique.
Les descripteurs de texture basés sur l’histogramme sont limités par le fait que l’histogramme ne
contient aucune information sur les relations spatiales entre les pixels. Une façon de contourner cette
limitation consiste à utiliser une représentation alternative des valeurs de pixels qui code leur position
relative les unes par rapport aux autres. Une telle représentation est la matrice de cooccurrence de
niveau de gris G, définie comme une matrice dont l’élément g(i, j) représente le nombre de fois où des
paires de pixels avec les intensités zi et zj se produisent dans l’image f (x, y) à la position spécifiée par
un opérateur d. Le vecteur d est appelé vecteur de déplacement :

99
 CHAPITRE 6. SEGMENTATION ET EXTRACTION D’ATTRIBUTS

d = (dx , dy )
468 FEATURE EXTRACTION AND REPRESENTATION

Figure
FIGURE 18.18 6.28: Matrice
An image (a) andde
its cooccurrence d’une
cooccurrence matrix for dimage
= (0, 1) (b).

Où dx et dy sont les déplacements, en pixels, le long des lignes et des colonnes de l’image, respec-
where dx and dy are the displacements, in pixels, along the rows and columns, of the
tivement. image, respectively.
Figure 18.18
La Figure 6.28 montre un shows
exemplean example of gray-level
de matrice cooccurrence de
de cooccurrence matrix for d =de
niveaux 1). pour d = (0, 1).
(0,gris
The array on the left is an image F (x, y) of size 4 × 4 and L = 8 (L is the total
La La Figure 6.28a est une
number image
of gray F (x,
levels). They) de on
array taille 4 × 4is et
the right = 8 (L cooccurrence
theLgray-level est le nombre total de niveaux de
matrix
gris). La Figure 6.28b
G, usingest la matrice
a convention 0 ≤dei, jcooccurrence de niveau
< L. Each element de gris G,
in G corresponds ennumber
to the utilisantof une convention
occurrences of a pixel of gray-level i occurs to the left of a pixel of gray-level j. For
0 ≤ i, j < L. Chaque élément de G correspond au nombre d’occurrences d’un pixel de niveau de gris
example, since the value 6 appears to the left of the value 3 in the original image four
i se produisant àtimes,
gauche d’unof pixel
the value g(6, 3)du to [Link] gris j. Par exemple, puisque la valeur 6 apparaı̂t
niveau
is equal
quatre fois à gaucheThe
decontents of G3clearly
la valeur dans depend
l’image on d’origine,
the choice [Link]
If we had g(6, 3)d =
dechosen 0) à 4.
est(1,égale
(which can be interpreted as “one pixel below”), the resulting gray-level cooccurrence
La matrice dematrix
cooccurrence
for the samede niveau
image de gris
in Figure peut
18.18a êtrebenormalisée
would comme
the one in Figure [Link] :

Ng (i, j) = P P
g(i,j)
g(i,j)
i j

Où Ng (i, j) est la matrice de cooccurrence de niveaux de gris normalisée. Puisque toutes les valeurs
de Ng (i, j) se situent entre 0 et 1, elles peuvent être considérées comme la probabilité qu’une paire de
points satisfaisant d aura des valeurs (zi , zj ).
Les matrices de cooccurrence peuvent être utilisées pour représenter les propriétés de texture d’une
image. Au lieu d’utiliser la matrice entière, des descripteurs plus compacts sont préférés. Ce sont les
caractéristiques basées sur la texture les plus populaires qui peuvent être calculées à partir d’une
matrice de cooccurrence de niveau de gris normalisée Ng (i, j) :

— Probabilité maximale : max Ng (i, j).

i,j
P P FIGURE
2 18.19 An image (a)P Pcooccurrence matrix for d = (1, 0) (b).
and its
— Énergie : i j Ng (i, j). Entropie : − i j Ng (i, j) · log2 (Ng (i, j)).
P P 2
— Contraste : i j (i − j) Ng (i, j).
P P Ng (i,j)
— Homogénéité : i j 1+|i−j| .
P P
(i−µi )(j−µj )Ng (i,j)
i j
— Corrélation : σi σj .
Où µi , µj sont les moyennes et σi , σj les écarts types des sommes de ligne et de colonne Ng (i)
et Ng (j), définies par :
P P
Ng (i) = i Ng (i, j) et Ng (j) = j Ng (i, j)

Le Tableau 6.2 montre les valeurs des descripteurs de texture statistiques représentatifs pour les
trois images de la Figure 6.27. Ces descripteurs ont été obtenus en calculant les matrices de cooccur-
rence de niveaux de gris normalisées avec d = (0, 1).
Comme prévu, la texture régulière a l’uniformité la plus élevée, l’homogénéité la plus élevée et
l’entropie la plus faible des trois. Bien que la distinction entre les textures grossières et lisses à l’aide de

100
CHAPITRE 6. SEGMENTATION ET EXTRACTION D’ATTRIBUTS

Tableau 6.2: Descripteurs de texture statistique pour les trois images de la Figure 6.27 basés sur la matrice
cooccurrence

Texture Max Prob. Corrélation Contraste Uniformié Homogénéité Entropie

Lisse 0.0013 0.5859 33.4779 0.0005 0.0982 7.9731

Grossière 0.0645 0.9420 14.5181 0.0088 0.3279 6.8345

Régulière 0.1136 0.9267 13.1013 0.0380 0.5226 4.7150

ces descripteurs soit possible (par exemple, l’image avec une texture grossière montre une corrélation,
une uniformité et une homogénéité significativement plus élevées que l’image avec une texture lisse),
ce n’est pas aussi intuitif.

101