Université Abdelhamid Ibn Badis mostaganem

Faculté des sciences et technologie

Département de génie Electrique

Traitement d’image

Binome :
Derdour mohamed
Belkheir med ouael
Berkane farouk
 1

TABLE DES MATIÈRES

Table des matières

1 L’image : caractéristiques, représentations 4
2 Couleur 5
3 Amélioration d’images 8
3.1 Réhaussement de contraste . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.2 Réduction du bruit, lissage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
4 Classification 12
4.1 Binarisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
4.2 Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
5 Régions 14
5.1 Étiquetage en composantes connexes . . . . . . . . . . . . . . . . . . . . . . . . 14
5.2 Segmentation après une classification . . . . . . . . . . . . . . . . . . . . . . . . 14
5.3 Croissance de régions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
5.4 Ligne de Partage des Eaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
6 Contours 17
6.1 À partir du gradient image . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
6.2 À partir du Laplacien . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
6.3 Lissage et dérivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
6.4 Autres détecteurs ................................... 20
7 Morphologie mathématique 21
7.1 Dilatation et érosion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
7.2 Ouverture et fermeture ................................ 22
7.3 Gradients morphologiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

7.4 Transformation en tout ou rien (Hit or Miss) . . . . . . . . . . . . . . . . . . . . . 22

7.5 Squelette morphologique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

7.6 Reconstruction géodésique et seuillage par hystérésis ................ 23
7.7 Morphologie fonctionnelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

2
8 Points d’intérêt 25
8.1 Détecteur de Harris . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
8.2 Descripteurs de points d’intérêt . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
9 Descripteurs de texture 27
9.1 Statistiques ...................................... 27
9.2 Motifs binaires locaux (LBP) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
9.3 Méthodes fréquentielles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
9.4 Méthodes spatiofréquentielles ............................ 29
10 Descripteurs de forme 30
10.1 Descripteurs classiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
10.2 Signature et descripteurs de Fourier . . . . . . . . . . . . . . . . . . . . . . . . . 30
10.3 Codage de Freeman . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
10.4 Moments ....................................... 31
10.5 Transformée de Hough . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
TABLE DES MATIÈRES

11 Mouvement 33
11.1 Détection du mouvement par soustraction du fond . . . . . . . . . . . . . . . . . . 33
11.2 Flot optique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
11.3 Algorithme de Horn et Schunck ........................... 34
11.4 Algorithme de Lucas-Kanade . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
12 Compression d’images 36
13 Quelques références 37
1 L’IMAGE : CARACTÉRISTIQUES, REPRÉSENTATIONS

1 L’image : caractéristiques, représentations

L’image numérique est ici une matrice de picture elements ou pixels, chacun d’entre eux
codant une nuance de couleur ou de niveau de gris. Cette image est acquise par un capteur relié
à une carte d’acquisition disposant d’un convertisseur analogique numérique.
Une image est notamment caractérisée par ses résolutions spatiales et tonales. La première,
appelée également définition, correspond tout simplement aux dimensions de l’image (hauteur
ou nombre de lignes, largeur ou nombre de colonnes). La seconde résolution est liée au codage

3
binaire de chaque pixel (en général 8 bits dans le cas d’une image en niveaux de gris et 24 dans le
cas d’une image couleur).
Comme nous le verrons dans la section suivante, même si la plupart des images sont
représentées dans l’espace couleur RGB, il existe différents modèles de représentation des
couleurs. Quant au format d’enregistrement des images (dont .jpg, .png, .gif, etc), il s’agit d’un
type de représentation de l’image, éventuellement avec compression, associée à des
métadonnées (date, taille).
Une image peut-être vue comme un signal à deux dimensions. Alors qu’un signal évolue en
fonction du temps (ou en fonction de la fréquence), l’image est une fonction de deux variables
spatiales, qui peuvent être notées x et y, comme l’indique la figure 1 (gauche), et dont l’origine
est placée en haut à gauche.
Comme tout signal, il existe une représentation fréquentielle de l’image, obtenue par
transformée de Fourier, dont le calcul rapide s’appelle FFT pour Fast Fourier Transform (voir figure
1 (droite)). La FFT n’est possible que pour des images dont les dimensions sont des puissances de
2. Dans ce domaine fréquentiel, chaque point représente une fréquence particulière contenue
dans le domaine spatial de l’image. Les axes u et v correspondent aux variables fréquentielles,
représentant respectivement les variations suivant les axes vertical et horizontal.

Figure 1 – Domaines spatial et fréquentiel de l’image.

La figure 2 d) montre un exemple de FFT calculée à partir de l’image 2 a). Les figures 2 b) et
c) illustrent le filtrage passe-bas, tandis que les figures 2 e) et f) illustrent le filtrage passe-haut.
Parmi les représentations d’image, nous pouvons également ajouter l’histogramme h(n), qui
compte le nombre d’occurrences de chaque niveau de gris n d’une image (voir figure 3), et
l’histogramme cumulé hc(n) qui compte de nombre d’occurrences des pixels de niveau inférieur
ou égal à n. Ces deux représentations s’avèrent très utiles pour analyser les statistiques de
l’images, améliorer le contraste de l’image (voir section 3), réaliser une classification ou une
binarisation (voir dans la section 4). Les probabilités d’occurrence des niveaux de gris p(n) se
déduisent de l’histogramme en divisant chaque valeur par le nombre total de pixels de l’image
(l’histogramme est normalisé).

4
 Figure 2 – La transformation de Fourier (FFT) d’une image. a) Image initiale dans sa représentation
spatiale et d) son spectre d’amplitude (représentation fréquentielle), b) représentation
fréquentielle de l’image avec filtrage passe-bas (les fréquences hautes sont atténuées). c) image
après filtrage passe-bas. e) filtrage passe-haut (les fréquences basses sont atténuées). f) image
après filtrage passehaut.

2 Couleur
Trois couleurs, appelées primaires, sont suffisantes pour reproduire la quasi-totalité des
couleurs visibles. Les 3 primaires sont choisies de manière à ce qu’aucune des 3 ne puisse être
reproduite par un mélange des 2 autres. Un vecteur couleur est obtenu par une combinaison
linéaire des 3 vecteurs de base :
C = αC1 + βC2 + γC3
Il est possible de déterminer expérimentalement la quantité des 3 primaires permettant une
égalisation de chacun des rayonnements monochromatiques du visible. Les expériences
d’égalisation ont ainsi permis de définir les sensibilités colorées : les fonctions trichromatiques r,¯

g,¯ ¯b de l’observateur standard 1931. Ces expériences ont été menées par la Commission
Internationale de l’Éclairage à partir d’un échantillon représentatif de la population.
L’égalisation est un procédé visant à reproduire visuellement, à partir d’un mélange pondéré
de trois faisceaux de couleurs primaires, un stimulus chromatique de référence de longueur
d’onde donnée. Les courbes de sensibilités r,¯ g,¯ ¯b correspondent aux proportions de rouge, vert
et bleu nécessaires pour reproduire l’ensemble des couleurs du visible, c’est-à-dire l’ensemble
des couleurs monochromatiques sur la plage allant de 380 nm à 780nm (voir figure 4(a)).
À partir de ces fonctions trichromatiques, les composantes RGB proviennent de l’intégration,
suivant les longueurs d’ondes du visible, du produit entre :

5
1. les fonctions trichromatiques, c’est-à-dire l’observateur. Pour un capteur artificiel (caméra),
les fonctions trichromatiques sont remplacées par les courbes de sensibilité spectrales de
ce capteur (très variables d’un capteur à l’autre).

6
2 COULEUR

Figure 3 – Histogramme et histogramme cumulé d’une image de 400 pixels, avec une dynamique de
16 (on suppose que 4 bits sont utilisés pour le codage).

(a) (b)

Figure 4 – Fonctions trichromatiques (a) r,¯ g,¯ ¯b (b) x,¯ y,¯ z¯.

2. la réflectance du matériau R (qui exprime pour chaque longueur d’onde, la proportion

d’énergie réémise par la surface observée)
3. le spectre de l’illuminant E (qui indique pour chaque longueur d’onde la quantité d’énergie
émise).
On obtient alors les trois relations suivantes :
Z 780nm
R= r¯(λ)R(λ)E(λ)dλ
λ=380nm

Z 780nm
G= g¯(λ)R(λ)E(λ)dλ
λ=380nm

Z 780nm

B= ¯b(λ)R(λ)E(λ)dλ
λ=380nm

Comme l’indique la figure 4(a), il n’est pas possible d’égaliser l’ensemble des couleurs
monochromatiques à partir des composantes RGB. En effet, il n’est pas possible de produire les
signaux lumineux rouges négatifs (entre 450 et 550nm). Pour pallier ce problème, la CIE a défini de
nouvellesfonctionstrichromatiquesx,¯ y,¯ z¯,partransformationlinéairedesfonctionsr,¯ g,¯
¯[Link] de définir un nouvel espace couleur de primaires : XY Z.

7
 Par la suite, de nombreux espaces couleur ont été définis :
— les espaces perceptuels (par exemple HSV, HSI) qui offrent une représentation cohérente avec
la façon dont nous percevons et décrivons les couleurs, c’est-à-dire en trois composantes : la
teinte (rouge, vert, jaune), la saturation (une couleur perçue comme délavée est faiblement
saturée, une couleur dite vive est fortement saturée) et l’intensité ou luminance qui est liée
à la quantité de lumière perçue. (voir figure 5 (a))
— les espaces perceptuellement uniformes (CIELAB ou L∗a∗b∗ et CIELUV) définis de façon à ce
qu’une distance mesurée dans cet espace soit conforme à la distance perçue par le système
visuel humain. Ces espaces sont particulièrement utiles pour comparer des couleurs entre
elles. (voir figure 5 (b))
— des invariants couleur, invariants par rapport aux changements d’éclairage et aux ombres, par
exemple (voir figure 5 (c)) :

Notons que les espaces de type Teinte-Saturation-Luminance ainsi que CIELAB ou CIELUV
montrentl’avantagedeséparerlesinformationsdeluminance,susceptiblesdevarieraveclesconditions
d’éclairage, des informations de chrominance qui s’avèrent beaucoup plus stables vis-à-vis de ces
perturbations. Contrairement aux espaces de primaires (RGB ou XYZ), les composantes sont bien
moins corrélées.

(a)

(b)

(c)

Figure 5 – Exemples de conversion d’images. (a) HSV, (b) CIELAB, (c) Norme L1

8
3 AMÉLIORATION D’IMAGES

3 Amélioration d’images
3.1 Réhaussement de contraste
Certainesmodificationsd’histogrammespermettentd’améliorerlecontrasteglobald’uneimage ou
encore d’améliorer le contraste pour certaines plages de niveaux de gris. On part d’une image
I(x,y) codée sur 8 bits dont on peut calculer un histogramme h(n) où n correspond au niveau de gris
allant de 0 à 255. On peut également calculer l’histogramme cumulé :

Attention, les transformations d’histogrammes ne s’appliquent que pour des images suffisamment
riches en termes de contenu, comme des images naturelles (paysages par exemple). Dans le cas
contraire, c’est-à-dire pour des images présentant peu d’objets de luminance (ou de couleur) très
uniforme, les modifications d’histogrammes risquent d’introduire du bruit en créant des variations
artificielles de niveaux de gris.

3.1.1 Normalisation ou étirement d’histogramme

Elle consiste à exploiter toute la dynamique disponible (256 valeurs) par une simple normalisation
qui ramène la valeur maximale de l’image max à 255 et la valeur minimale min à 0 :

Toutefois, ce type de normalisation est très sensible au bruit. Par exemple, si l’image est très peu
contrastée mais présente quelques pixels de bruit de type «poivre et sel»(c’est-à-dire noir et blanc),
cette normalisation n’aura aucun effet. On préfère alors une normalisation qui exploite les
statistiques globales de l’image : la moyenne d’intensité µ et l’écart-type σ (qui devra ensuite être
suivie d’un nouvel étirement pour ramener les valeurs entre 0 et 255) :

La figure 6 a) montre une image et son histogramme. Après étirement de l’histogramme (figure
6 b)), la dynamique est effectivement plus grande, et le contraste de l’image en est amélioré.

3.1.2 Étirement non-linéaire d’histogramme

De façon plus générale, l’étirement d’histogramme consiste à appliquer une fonction J(x,y) =
f(I(x,y)) à chaque valeur de l’image I(x,y) pour former une image améliorée. Dans le cas de la
normalisation précédente, cette fonction était simplement une fonction linéaire (de la forme ax+b
c-a-d une droite). On peut choisir la forme de cette fonction pour réaliser une amélioration plus
adaptée à un problème donné, ou à un type d’image donné. Si f est définie comme une fonction
logarithmique (voir figure 6 c)), elle permet d’accentuer le contraste pour les valeurs de niveaux de

9
gris faibles. Si elle est de forme exponentielle (voir figure 6 d)), elle permet d’accentuer le contraste
pour les niveaux de gris élevés.

3.1.3 Égalisation d’histogramme

Comme son nom le laisse deviner, l’égalisation d’histogramme vise à obtenir un histogramme plat
où toutes les valeurs de niveau de gris sont équiprobables h(n) = N/256 soit p(n) = 1/256
3.1 Réhaussement de
contraste

avec N le nombre de pixels de l’image. L’histogramme cumulé après égalisation forme une droite
d’équation N/256 (ou 1/256 en termes de probabilités). L’égalisation consiste à transformer
l’histogramme cumulé vers cette équation de droite :

où N est le nombre de pixels de l’image I(x,y) et hc est l’histogramme cumulé. Cette transformation
permet de se ramener à une distribution équiprobable où chaque valeur de niveau de gris
possèdeuneprobabilitéde1/256.Lafigure6e)montreunexempled’égalisation.Lafigure7montre les
histogrammes de la figure 3 après égalisation.

Figure 6 – Histogrammes et transformations

10
Figure 7 – Histogramme et histogramme cumulé d’une image de 400 pixels, après égalisation des
histogrammes de la figure 3.
3 AMÉLIORATION D’IMAGES

3.2 Réduction du bruit, lissage

La réduction du bruit se fait par filtrage spatial, qui peut être linéaire (filtrage passe-bas) ou non-
linéaire (filtrage d’ordre par exemple, comme le filtrage médian).

3.2.1 Filtrage linéaire

Le filtrage linéaire est obtenu par convolution entre l’image initiale et un noyau (filtre)
généralement moyen, gaussien (figure 9) ou binômial. La force (ou niveau) de filtrage dépend
directement de la taille du noyau. Dans le cas du filtrage gaussien, la taille du noyau dépend
directement du paramètre σ (noyau de largeur > (2σ+1)). Le filtrage linéaire atténue l’amplitude du
bruit (gaussien ou impulsionnel) mais lisse également les contours, puisqu’il atténue les fréquences
hautes de l’image. Gaussienne 1D centrée sur m :
1 (x−m)2

Gaussienne 2D centrée sur

La figure 9 b) montre le résultat d’un filtrage passe-bas sur l’image de Lena bruitée avec du bruit
impulsionnel (figure 9 a)). Le bruit impulsionnel est effectivement lissé, mais également les contours.

11
 Figure 8 – Gaussiennes 1D et 2D.

3.2.2 Filtrage d’ordre

Le filtrage d’ordre le plus connu et le plus utilisé est le filtrage médian dont la force dépend là
aussi de la taille du filtre. Supposons un noyau de taille 3×3 centré sur le pixel à filtrer (ci-dessous le
pixel de valeur 7). L’ensemble des 9 valeurs sont triées (peu importe l’ordre, qu’il soit croissant ou
décroissant) puis la valeur médiane est affectée au pixel courant dans l’image résultat :

5 4 2 5 4 2
5 7 1 → tri :1,2,2,4,4,5,5,5,7 → 5 4 1
5 4 2 5 4 2
3.2 Réduction du bruit,
lissage

Le filtrage médian est particulièrement adapté pour les images montrant du bruit impulsionnel ou
poivre et sel. Il préserve bien les contours mais rogne les coins. La figure 9 c) illustre la bonne qualité
du lissage médian sur l’image de Lena, dans le cas d’un bruit poivre et sel.

(a) (b) (c)

Figure 9 – Filtrage passe-bas. (a) image initiale avec bruit impulsionnel (poivre et sel). (b) résultat
après filtrage gaussien. (c) Résultat après filtrage médian.

12
4 CLASSIFICATION

4 Classification
La classification consiste à partitionner les données en groupes (ou classes) d’attributs
homogènes. Dans le cas d’une image, il s’agit généralement de classifier les couleurs ou les niveaux
de gris, ou encore des attributs tels que le mouvement, des attributs de texture, etc. La plupart des
méthodes de classification travaillent uniquement à partir des attributs des pixels sans considérer
leur distribution spatiale dans l’image ou encore leur connexité. Dans ce sens, les méthodes de
classification se distinguent des méthodes de segmentation qui partitionnent l’image en régions
disjointes de pixels connexes.

4.1 Binarisation
La binarisation peut être vue comme une classification en 2 classes. La plus simple des techniques
consiste à définir des seuils fixes. Toutes les valeurs inférieures, supérieures ou situées entre deux
seuils sont mises à 1 et le reste à 0. Comme il est souvent difficile de définir la ou les valeurs de seuils,
des méthodes de seuillage automatique sont préférables :
— Le seuillage au percentile supérieur ou inférieur. Un percentile correspond à chacune des 99
valeurs qui divisent les données triées en 100 parts égales. Le seuillage supérieur au pième
percentile consiste à mettre à 1 les pixels dont la valeur dépasse celle des p% de pixels les
plus faibles.
— Seuillage automatique de Otsu. Le seuil est calculé de façon à minimiser les variance
intraclasse et maximiser la variance inter-classe.
Le seuillage par hystérésis, décrit par l’algorithme 1 sort un peu du cadre de la classification dans
le sens où il exploite la connexité. On parle de seuillage local. Ce seuillage utilise deux seuils, un seuil
haut Sh et un seuil bas Sb. Les valeurs de pixels > Sh sont mises à 1. Les valeurs < Sb sont mises à 0.
Enfin, les valeurs intermédiaires sont mises à 1 lorsqu’elles forment une composante connexe qui est
elle-même connexe avec une composante > Sh. Ce type de seuillage est notamment utilisé pour la
sélection des contours à partir d’un calcul de gradient (voir la partie 6.1).

Algorithm 1 Exemple d’algorithme de seuillage par hystérésis

Entrée : image de niveaux de gris I, seuil haut Sh, seuil bas Sb
Sortie : image binaire B Ih ← {1
si I > Sh, 0 sinon} Ib ← {1 si I >
Sb, 0 sinon}
nchts ← 1 while nchts >
0 do
Itemp ← dilate (Ih)
Itemp ← Ib AND I_temp
nchts ←comptage_pixels_non_nuls(Ih − Itemp)
Ih ← Itemp end
while

13
4.2 Clustering
K-means. La méthode des nuées dynamiques (k-means) proposée par Forgy1 est l’approche la
plus courante (voir l’algorithme 2). Le critère d’arrêt est fondé sur la stabilisation des classes, qui peut
être détectée en scrutant le nombre de changements d’affectation de classe entre deux itérations
4.2
Clustering

ou en calculant la variance interclasses. L’algorithme s’arrête par exemple lorsque la variance

interclasses n’évolue plus significativement. La figure 10 donne un exemple de classification sur une
image de panneaux routiers, préalablement convertie dans l’espace rgb (composantes normalisées)
pour une meilleure qualité de résultat. Algorithm 2 Nuées dynamiques (k-means)
Initialisation : Tirer au hasard, ou sélectionner pour des raisons extérieures à la méthode, k points
dans l’espace des individus, en général k individus de l’ensemble, appelés centres ou noyaux. while
les classes ne sont pas stabilisées do
• Allouer chaque individu au centre (c’est-à-dire à la classe) le plus proche au sens de la
métrique euclidienne choisie; on obtient ainsi, à chaque étape, une classification en k classes,
ou moins si, finalement, une des classes devient vide.
• Calculer le centre de gravité de chaque classe : il devient le nouveau noyau; si une classe s’est
vidée, on peut éventuellement retirer aléatoirement un noyau complémentaire.
end while

Figure 10 – Exemple de classification couleur en 3 classes.

ISODATA. La méthode k-means nécessite de préciser le nombre de classes prévues. L’algorithme

ISODATA (pour Iterative Self-Organizing Data ANalysis Technique) proposé par Jensen en 1996
permet de pallier ce problème (mais des paramètres sont toutefois requis). https:
//[Link]/~mount/Projects/ISODATA/[Link]
Mean-Shift. L’algorithme de clustering mean-shift consiste à rechercher les modes dans une
distribution, c’est-à-dire les maxima locaux. Cet algorithme est bien illustré sur cette page https:

1
. R. Forgy, Cluster Analysis of Multivariate Data : Efficiency versus Inter-pretability of Classification, Biometrics (1965),
no21, 768–769

14
//[Link]/2015/05/26/mean-shift-clustering/. Comme ISODATA, le nombre de
classes n’est pas requis.
5 RÉGIONS

5 Régions
5.1 Étiquetage en composantes connexes
Il existe de très nombreuses variantes d’algorithmes d’étiquetage en composantes connexes. La
thèse de Laurent Cabaret 2 en fait un état de l’art détaillé. L’algorithme 3 donne une version qui
parcourt l’image binaire dans le sens du balayage vidéo classique. Dès qu’un pixel non nul est trouvé,
la composante connexe est reconstruite de proche en proche en agrégeant à la région l’ensemble
des pixels connexes et non-nuls. Une pile est utilisée pour stocker l’ensemble des pixels à agréger à
la région, afin que leurs voisinages soient analysés à leur tour (algorithme 3).
La figure 11 montre un exemple d’étiquetage en composantes connexes sur une image de
panneaux préalablement binarisée.

Algorithm 3 Étiquetage en composantes connexes E,n = ECC(I,e)

Entrée : image binaire I, étiquette initiale e
Sortie : image d’étiquettes E, nombre de régions n
Initialisation
ToDo ← I
E(x,y) ← 0 ∀(x,y) Liste de
pixels L ← 0 for x =0 to
rows do
for y =0 to cols do
if I(x,y) 6= 0 and ToDo(x,y) 6= 0 then L ←
(x,y)
e=e+1
E(x,y) = e //nouvelle composante connexe
ToDo(x,y) = 0 repeat
(u,v) ← pop(L) for i =-
1 to 1 do
for j = -1 to 1 do
if (i 6= 0 or j 6= 0) and (I(i + u,j + v) 6= 0 and ToDo(i + u,j + v) 6= 0) then

end if end
for end for
until L est non vide
n←e

2
. https ://[Link]/tel-01597903

15
 end if end
for end for

5.2 Segmentation après une classification

La segmentation peut être effectuée après une première étape de classification. Par exemple,
après l’algorithme k-means, k classes de pixels sont extraites. Pour chacune d’entre elles, on met à
5.3 Croissance de
régions

Figure 11 – Exemple de segmentation par étiquetage en composantes connexes.

1 l’ensemble des pixels associés à la classe puis l’on opère un étiquetage (algorithme 4).

Algorithm 4 Segmentation après classification

Entrée : image de K classes C
Sortie : image d’étiquettes E, nombre de régions n
Initialisation
E(x,y) ← 0 ∀(x,y) n = 0
for k = 1 to K do
I(x,y) ← 1 si C(x,y) == k ∀(x,y)
E,n ← ECC(I,n) end for

5.3 Croissance de régions

L’algorithme de croissance de régions est assez similaire à celui de l’étiquetage expliqué
précédemment (algorithme 3). Ici nous ne raisonnons pas à partir d’une image binaire, mais d’une
image en niveaux de gris ou en couleur. La différence se porte sur le test à réaliser pour agréger un
nouveau pixel à la région en cours de formation, le test souligné dans l’algorithme 3, qui devient : if
(i 6= 0 ou j 6= 0) and (similarity(I(i + u,j + v),I(u,v)) and ToDo(i + u,j + v) 6= 0)

16
 La fonction similarity renvoie 1 si les deux valeurs image sont suffisamment proches, par exemple
si la distance euclidienne entre les 2 couleurs est inférieure à un seuil.

5.4 Ligne de Partage des Eaux

Cet algorithme réalise une segmentation en régions, en partant généralement d’une image de
gradient. L’image est considérée comme un relief topographique, avec des bassins versants séparés
par une ligne de partage des eaux. Ce type d’algorithme aboutit généralement à une
sursegmentation, c’est-à-dire que chaque objet réellement présent dans l’image est constitué de
plusieurs régions dans l’image. Ces régions peuvent ensuite être fusionnées entre elles pour
constituer des régions plus cohérentes avec le contenu image. On distingue entre autre trois types
d’approches :
— Les approches par immersion (voir figure illustrative 12)
5 RÉGIONS

— Les approches par inondation simulent une montée progressive du niveau d’eau à partir des
minima du relief (minima de l’image de gradient) (voir figure 13 qui provient de la thèse de
Jean Cousty3)
— Les approches par ruissellement suivent, à partir de chaque pixel de l’image, la ligne de plus
grande pente jusqu’à atteindre un minimum. On définit ainsi un ensemble de bassins versants
qui correspondent aux régions de l’image

Figure 12 – Illustration de l’algorithme de LPE par immersion d’un relief.

(a) (b) (c)

Figure 13 – Illustration de l’algorithme de LPE par inondation d’une image en 4-connexité. (a) : Une
image F; (b) : les minima de F sont étiquetés A, B et C; (c) : les bassins versants (obtenus par LPE par

3
. https ://[Link]/tel-00321885/document

17
inondation) sont étiquetés en fonction du minimum de F qui leur est associé; la LPE par inondation
correspondante est constituée des points sans étiquette.
6 Contours
Les contours de l’image correspondent à des pixels de fort gradient d’intensité. Détecter les
contours peut donc être faire en calculant le gradient image et en sélectionnant les valeurs de fort
gradient par seuillage (seuillage simple comme sur la figure 14 b) ou seuillage par hystérésis (figure
14 (c)) décrit à la section 4.1) ou en détectant les maxima locaux (voir paragraphe 6.1).
Les contours peuvent être extraits à partir des dérivées secondes de l’image (le Laplacien). Dans
ce cas, on détecte les passages par zéro du laplacien (voir paragraphe 6.2 et figure 14 (d)).

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

Figure 14 – Détection de contours. (a) Image initiale. (b) Contours par seuillage simple de la norme
du gradient. (c) seuillage par hystérésis. (d) Détection des contours par détection des passages par
zéro du Laplacien.

6.1 À partir du gradient image

Le gradient est un vecteur à deux composantes, soit (Gx,Gy) où Gx et Gy sont les deux dérivées de
l’image suivant les deux directions x et y, soit (n,θ) où n est la norme (le module du vecteur) et θ
l’orientation :

Le calcul de gradient le plus simple se calcule par simple différence :

Gx = I(x + 1,y) − I(x,y) et Gy = I(x,y + 1) − I(x,y)

.
Ce calcul s’avère assez sensible au bruit. On préfère donc les détecteurs par convolution (filtrage
linéaire).
Détecteur par filtrage linéaire. L’image est convoluée (opérateur *) par un noyau ou filtre passe-
haut par direction Gx = I ∗Kx et Gy = I ∗Ky. La plupart d’entre eux combinent un filtrage passe-bas avec
un filtrage passe-haut de façon à atténuer les gradients liés au bruit. Le filtre le plus courant est celui
de Sobel :

18
6 CONTOURS

Le détecteur de Prewitt fait appel à 4 filtres (pour 4 directions). La norme du gradient est
finalement calculée comme le maximum des 4 réponses des convolutions avec les 4 noyaux suivants
:

Détecteur de Canny4 Il se fonde sur quatre étapes :

1. Filtrage Gaussien de l’image avec un paramètre σ

2. Calcul du gradient (|G|,θ) en utilisant les noyaux Kx = [−1,0,1] et Ky = [−1,0,1]>
3. Détection des maxima locaux
4. Seuillage par hystérésis, qui nécessite deux seuils (voir section 4)

6.2 À partir du Laplacien

6.2.1 Laplacien
Le laplacien (calculé à partir des dérivées secondes) de l’image est défini comme suit :

Ce laplacien est nul lorsque les deux dérivées secondes (en x et y) sont nulles. L’opérateur est linéaire
et symétrique en rotation. Une façon dite naïve de le calculer est la suivante :

I00x ' I0x − I0x−1

' (I(x + 1) − I(x)) − (I(x) − I(x − 1))
' I(x + 1) − 2I(x) + I(x − 1)

Le filtre Laplacien peut être défini en 4 ou 8 connexité :

4 connexité : 8 connexité :

6.2.2 Laplacien de la Gaussiennce : LOG et DOG La convolution étant associative : (I ∗g)∗f = I ∗(g
∗f), il est possible de réaliser un lissage et une dérivation à l’aide d’un même filtre au lieu de réaliser
2 filtrages successifs. Ce noyau de lissage-laplacien est obtenu en calculant la dérivée seconde du
filtre de lissage : le laplacien du filtre gaussien (voir figure 15)

4
. Canny, J., A Computational Approach To Edge Detection, IEEE Transactions on Pattern Analysis and Machine
Intelligence, 8 :679-698 (1986).

19
 Le laplacien de la gaussienne centré sur 0 et d’écart-type σ s’exprime par :

Il s’agit d’un opérateur anisotropique pour lequel on ne peut pas calculer la direction du contour
(contrairement au gradient).
6.3 Lissage et
dérivation

Figure 15 – Gaussienne et Laplacien de la gaussienne.

L’opérateur DoG (Difference of Gaussians) est une variante plus rapide de l’opérateur LoG. Il
approxime le filtre LoG par la différence de deux gaussiennes de tailles différentes.
À partir de la réponse au filtre LoG ou DoG, les contours sont localisés en détectant les passages
par zéro. En effet, les maxima locaux du gradient se caractérisent par un passage par zéro de la
dérivée seconde. Cela peut se faire par exemple à l’aide de l’algorithme 5. Une autre méthode, qui
exploite la morphologie mathématique (voir section 7) consiste à détecter les ensembles de pixels
de valeurs < 0 puis de détecter le contours de ces ensembles (par un gradient morphologique).
Les zéros constituent un réseau de lignes fermées, ce qui permet d’éviter des post-traitements
de fermeture de contours, pour réaliser par exemple une analyse des formes. Algorithm 5
Localisation des contours à partir des dérivées secondes : passage par 0
Entrée : image de Laplacien L
Sortie : image binaire C de contours
C←0
for x =0 to rows -1 do
for y =0 to cols -1 do
if (L(x,y)×L(x+1,y) > S or (L(x,y)×L(x+1,y+1) > S or (L(x,y)×L(x,y+1) > S then
C(x,y) =1
end if end
for end for

20
 6.3 Lissage et dérivation
Si l’opérateur de dérivation est linéaire ⇒ opérateur associatif et commutatif (convolution). Soit
I(x,y) (l’image) et f(x,y) (un filtre de lissage) deux fonctions L2 dérivables avec l’opérateur Ox,y
(dérivation) alors :

Ox,y(I(x,y) ∗ f(x,y)) = Ox,y(I(x,y)) ∗ (x,y) = I(x,y) ∗ Ox,y(f(x,y))

Dans le cas d’un filtrage linéaire : l’ordre dans lequel se font le lissage et la dérivation n’a pas
d’importance (convolution). Dans le cas d’un filtrage non-linéaire il est préférable de faire le lissage
avant la détection des gradients.
6 CONTOURS

6.4 Autres détecteurs

Gradients morphologiques (voir la section 7) définis à l’aide de l’érosion et de la dilatation.

21
 7 Morphologie mathématique
La théorie de la morphologie mathématique s’appuie sur la théorie des ensembles. Elle regroupe
de nombreuses transformations non-linéaires à partir d’un objet de référence (élément structurant
B) permettant d’extraire différentes informations telles que la connexité, la taille, la forme,
l’orientation. Il s’agit d’étudier ou de traiter un ensemble (les objets dans les images) à l’aide d’un
autre ensemble, appelé élément structurant, qui sert de sonde. L’élément structurant est déplacé en
tout point de l’image à traiter. À chaque position on étudie sa relation avec l’image binaire X : « est
inclus dans l’ensemble », « intersecte l’ensemble », par exemple. Les transformations se déduisent
par composition ou différences d’opérations élémentaires : l’érosion et la dilatation.
Élément structurant. L’élément structurant peut avoir n’importe quelle forme et taille.
Néanmoins les plus utilisés sont la croix (pour l’analyse en 4-connexité) et le carré (8-connexité), mais
ce peut être une ligne, une colonne etc suivant l’objectif visé. L’élément structurant possède un
centre, qui est le point de référence pour l’analyse de la relation avec l’image binaire. C’est lui qui est
positionné sur chaque pixel de l’image à traiter.

B4 = B8 =

Considérons l’espace image à deux dimensions E = Z2 et B est un sous-ensemble de E. On appelle

X un ensemble dans l’image à analyser ∈ E . Le translaté de B à la position x s’écrit Bx = {b + x|b ∈ B}.

7.1 Dilatation et érosion

La dilatation permet d’étudier les relations « intersecte avec l’ensemble ». La dilatation
morphologique avec l’élément structurant B est définie comme la somme de Minkowski :
δB(X) = X ⊕ B = {x + b | b ∈ B,x ∈ X} = ∪x∈XBx

De manière plus intuitive : le centre de B est déplacé en chaque point de l’image. S’il y a intersection
entre un élément b de B et un élément x de l’ensemble X, le résultat est égal à 1 et 0 sinon. L’érosion
permet d’étudier les relations « est inclus dans l’ensemble »

De manière plus intuitive : le centre de B est déplacé en chaque point de l’image. Si B est totalement
inclus dans X alors le résultat est 1, sinon 0.
0 00 0 0 0 0 0
0 00 0 0
0 0 00
00 0 0
0 0 00
00 0 0
1 0 0
0 00 0 0 0 0 0
Image binaire initiale I

22
 0 00 0 0 0 0 0
0 00 0 0 0 0 00
00 0 0 0 0 0
0 00 0 0 0 0 0
7 MORPHOLOGIE MATHÉMATIQUE

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 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 0 0
0 0 0 0 0 00
0 0 1 0 0 0 0
0 0 0 0 00 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 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Érosion de I avec B8 Dilatation de I avec B8

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 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 0 0 0 0 0 0
1 0 0 0 0 0 0
0 0 00 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 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Érosion de I avec B4 Dilatation de I avec B4

7.2 Ouverture et fermeture

Ouverture. Érosion puis dilatation. . L’ouverture élimine les
ensembles de taille inférieure à celle de l’élément structurant.
Fermeture. Dilatation puis Érosion. . La fermeture élimine les trous
de taille inférieure à celle de l’élément structurant.

23
 0 0 0 0 0 0 0 0 00
0 0 0 0 0 0 0 00
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 00 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 01 0 0 0 0 0 0
0 0 0 0
1 0 0 0 0 0 0 0 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 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 0 0
Ouverture de I avec B8 Fermeture de I avec B8

7.3 Gradients morphologiques

— Gradient morphologique :
— Contours internes : (Image - image érodée).
— Contours externes : δB(X) − X (Image dilatée - image)

7.4 Transformation en tout ou rien (Hit or Miss)

La transformation en tout ou rien sert à détecter des configurations particulières de pixels, par
exemple des coins. Elle utilise 2 éléments structurants notés ici A et B. On vérifie que A est exclus
7.5 Squelette
morphologique

de X et que B est inclus dans X. Remarquons que vérifier que A est exclus de X revient à vérifier que

A est inclus dans le complémentaire de X, noté Xc.

η(X) = {x | Ax ⊂ Xc;Bx ⊂ X}
Par exemple, pour détecter des coins sortants situés en haut à gauche des objets, on peut utiliser
les deux éléments structurants suivants :
1 1 1
A =B 1 = 1 1
1 1

On remarquera qu’ici, le centre de l’élément structurant A est situé à l’extérieur.

7.5 Squelette morphologique

Lesquelettemorphologique(euclidien)estlaréuniondescentresdeboules(euclidiennes)maximales,
comme l’illustre la figure 16. On définit un élément structurant de type boule (le carré en est une

24
approximation) de rayon R (carré de taille 2R+1×2R+1), que nous notons BR. Considérons également
un élément structurant boule de rayon 1, que nous notons B1.

Pour des valeurs de R croissantes :

• On effectue l’érosion de
• Par ailleurs, on applique l’ouverture de E par B1 : O = γB1(E)
• Le squelette est défini comme l’ensemble des points appartenant à E et non à O :
S = {x ⊂ X|x ⊂ E and x 6⊂ O}

La valeur de R est augmentée progressivement. À chaque itération, les points qui satisfont les critères
(appartenance à E et non appartenance à O) sont conservés. L’algorithme s’arrête lorsque la largeur
de la boule (2R+1) devient supérieure à l’épaisseur maximale de l’objet.

Figure 16 – Principe de la construction d’un squelette morphologique à partir de la boule de rayon

maximale.

Référence : [Link]

7.6 Reconstruction géodésique et seuillage par hystérésis

On considère d’une part une image binaire I1 contenant plusieurs ensembles connexes de laquelle
nous voulons en sélectionner un sous-ensemble. Une seconde, I2 contient des marqueurs 7
MORPHOLOGIE MATHÉMATIQUE

(pixels à 1) positionnés sur les ensembles à sélectionner dans I1. La reconstruction géodésique
consiste à reconstruire les ensembles de I1 marqués par les pixels de I2. L’algorithme 6 en propose
une implémentation. Il s’agit de partir de l’image des marqueurs I2, de la dilater jusqu’à couvrir
l’ensemble des régions à sélectionner dans I1.
Le seuillage par hystérésis, évoqué dans la section 4, est un exemple de reconstruction
géodésique, où les marqueurs I2 sont les pixels supérieurs à un seuil haut et I1 les pixels supérieurs à
un seuil bas.

25
Algorithm 6 Reconstruction géodésique binaire
Entrée : image binaire I1, et image de marqueurs I2
Sortie : image binaire R
R ← I2 repeat
tmp ←Dilate (R) //dilatation avec élément carré 3 × 3 tmp ←
tmp AND I1
nchgt ← sum(tmp XOR R) //compte le nombre de changements
R ← tmp
until nchgt > 0

7.7 Morphologie fonctionnelle

Une image à niveaux de gris peut être modélisée comme une fonction de Z2 dans Z. Soit f une
fonction appartenant à cet ensemble.
L’érosion se définit comme . L’élément structurant est déplacé en
chaque point de l’image. En chaque position, la valeur minimale de l’image dans l’ensemble défini
par B est recherché et affecté à l’image résultat. De façon similaire, la dilatation consiste à affecter la
valeur maximale : δB(f) = sup{fb | b ∈ B}
8 Points d’intérêt
Les points d’intérêt (aussi appelés coins même s’ils ne se résument pas à cela) correspondent à
une double discontinuité (ou plus) de la luminance, dans deux directions différentes. Ce sont des
primitives visuelles très robustes aux changements d’éclairage et sont présentes dans la plupart des
images. Contrairement aux contours, les traitements fondés sur l’analyse de points d’intérêt
souffrent peu des occultations partielles, dans le sens où il reste toujours un nombre suffisant de
points non-occultés malgré l’occultation d’une partie de l’image. Les points d’intérêt peuvent être
extraits à partir de contours, ou directement à partir de l’intensité et de ses dérivées.

8.1 Détecteur de Harris

Le détecteur de points d’intérêt le plus connu est celui de Harris et Stephens (1980), qui ont
proposé une amélioration de l’idée développée initialement par Moravec (1979) et qui se déroule de
la façon suivante :

1. Filtrage linéaire gaussien de l’image d’origine I

2. Calcul des dérivées Ix et Iy de l’image
3. Calcul des images correspondant aux termes de la matrice de covariance M qui caractérise
localement le comportement de l’intensité :

M
Les valeurs propres λ1 et λ2 de cette matrice correspondent aux courbures principales :
— λ1 et λ2 faibles → zone uniforme;

26
 — λ1 << λ2 ou λ1 >> λ2 → zone de contour;

— λ1 et λ2 élevées → zone de coin.

4. Filtrage des images par filtrage linéaire Gaussien → Ix2 , Iy2 et IxIy 5. Calcul de
l’image du critère cornerness ou force du coin R en chaque pixel :

R = Det(M) − kTrace(M) = Ix2 × Iy2 − (IxIy)2 − k(Ix2 + Iy2)

6. Création de l’image des points d’intérêt en détectant les maxima locaux de R supérieurs à un
seuil.
Les points d’intérêt de Harris montrent une bonne robustesse vis-à-vis des changements de
rotation, d’échelle.

8.2 Descripteurs de points d’intérêt

Considérons deux images I1 et I2 qui montrent deux vues d’une même scène, ou bien deux vues
d’un même objet dans des contextes différents. À partir de ces deux vues, on peut par exemple
réaliser un recalage d’images (appelé couramment stitching) pour former une image panoramique à
partir de I1 et I2. On peut également retrouver un objet donné dans I2 à partir de l’objet montré dans
I1. Dans les deux cas il convient de comparer le contenu des deux images.
Cette comparaison consiste à réaliser un appariement (ou une mise en correspondance) entre les
primitives visuelles extraites dans I1 et les primitives visuelles extraites dans I2, c’est-à-dire à trouver
les paires de primitives visuelles similaires. Ainsi, il convient de définir une mesure de similarité entre
ces primitives visuelles. Par conséquent, il est nécessaire de définir des descripteurs 8 POINTS
D’INTÉRÊT

associés à ces primitives, qui sont généralement des vecteurs de paramètres. La mesure de similarité
se résume très souvent à l’inverse de la distance euclidienne entre ces vecteurs.
Le descripteur SIFT, pour Scale Invariant Feature Transform (David Lowe, 99) est un des
descripteurs les plus populaires du fait de leurs très bonnes performances. L’approche comprend
également la détection des points, à l’aide d’une approche de Harris multi-échelle. Ensuite, le point
est décrit par un ensemble d’histogrammes de gradients orientés (figure 17 5 .). Au total, le
descripteur est composé de 16 histogrammes de gradients orientés, chacun de ces histogramme
comprend 8 cases, donc le vecteur descripteur a une taille de 128 éléments. La variante SURF :
Speeded Up Robust Features6 utilise une approximation du filtre gaussien (une variante binaire du
filtre) pour réduire les temps de calcul.

5
. Par Indif – Travail personnel, CC BY-SA 3.0, https ://[Link]/w/[Link]?curid=11924669
6
. Herbert Bay, Tinne Tuytelaars et Luc Van Gool, SURF : Speeded Up Robust Features, Proceedings of the European
Conference on Computer Vision, 2006, p. 404-417.

27
 Figure 17 – Calcul de l’histogramme de gradient dans SIFT

Les descripteurs binaires se construisent à partir de comparaisons des valeurs de niveaux de gris
des points situés dans la zone à décrire, voir notamment :
• FAST : Features from Accelerated Segment Tests : [Link] [Link]
• BRIEF : Binary Robust Independent Elementary Features.
• ORB (Oriented FAST and Rotated BRIEF)7.
9 Descripteurs de texture
9.1 Statistiques
9.1.1 Statistiques du 1er ordre

Ces statistiques se déduisent de la probabilité p(n) du niveau de gris n ou de l’histogramme h(n)

' Np(n), avec N le nombre de pixels de l’image.

• Moments d’ordre
En particulier µ1 correspond à la moyenne des niveaux de gris

• Moments centrés d’ordre

Variance σ2 = η2 : écart des variations d’intensités par rapport à la moyenne.

Skewness γ1 = η3, nul lorsque l’histogramme est symétrique par rapport à la moyenne Kurtosis
(aplatissement) γ2 = η4

• Énergie W = Pn |p(n)|2

L’énergie est élevée pour une image homogène et minimale lorsque les probabilités des niveaux de
gris sont équiréparties.

7
. Rublee E., Rabaud V., Konolige K., Bradski G : ORB : An efficient alternative to SIFT or SURF. ICCV 2011 : 2564 - 2571

28
 • Entropie E = −Pn p(n)logp(n)

L’entropie est faible pour une image homogène et élevée pour un histogramme étiré.

• Contraste C = (max(n) − min(n))/(max(n) + min(n))

Le contraste est faible pour une image uniforme.

• Dynamique D = max(n) − min(n)

La dynamique est faible pour une image uniforme.

9.1.2 Matrice de cooccurrence et statistiques du 2e ordre

L’algorithme 7 décrit le calcul de la matrice de cooccurrence. On considère un voisinage V qui

peut être de forme variée (à choisir en fonction de la tâche visée) :
nnnnm n
nnnn m n m m
n m n n
n
n
Comme pour les statistiques
extraites à partir de l’histogramme, il est possible de décrire les matrices de cooccurrence à l’aide de
statistiques, où p(m,n) = M(m,n)/N où N est égal au nombre de pixels de l’image × le nombre de
voisins dans V .
9 DESCRIPTEURS DE TEXTURE

Algorithm 7 Matrice de cooccurrence M(m,n)

Input : image I
Output : matrice de cooccurrence M
for (x,y) ∈ I do for (u,v) ∈ V
(x,y) do
m ← I(x,y) n ←
I(u,v)
M(m,n) ← M(m,n) + 1
end for end for

Moyennes µm = Xmp(m,n) et µn = Xnp(m,n)

29
 Moments
centrés

Énergie

Entropie

Contraste

Homogénéité

9.2 Motifs binaires locaux (LBP)

Les LBP codent les différences locales entre niveaux de gris. On considère un voisinage de
formecirculairederayonR (uncercleconstituédeP points),autourdupointcentraldecoordonnées
(xc,yc) et de niveau de gris gc
P−1

LBP(xc,yc) = X2pδ(gp − gc)

p=0

où δ est la fonction de Heavyside, à savoir que δ(gp − gc) = 1 sir gp ≥ gc et 0 sinon. Pour un voisinage
de 8 points sur un rayon R = 1, les valeurs de LBP sont codées entre 0 et 255. Une texture peut êstre
caractérisée par l’histogramme de ces LBP.
20 21 22

0 0 0
g0=1 g1=3 g2=2 -3 -1 -2
27 1 0 23
g7=5 gc=4 g3=3 1 -1
→ LBP8,1= 224
1 1 1
g6=6 g5=7 g4=4 2 3 0
26 25 24
Image gp -gc s(gp -gc)

Figure 18 – Motifs binaires locaux.

LBP8
9.3 Méthodes
fréquentielles

9.3 Méthodes fréquentielles

Les textures présentant des motifs répétitifs peuvent être analysées à l’aide de la transformée de
Fourier. Elle fournit les information sur la période de répétition du motif ainsi que sur la direction de
répétition.

30
 9.4 Méthodes spatiofréquentielles
Filtres de Gabor. Un filtre de Gabor est un filtre linéaire dont la réponse impulsionnelle est une
sinusoïde modulée par une fonction gaussienne.
Le filtre de Gabor peut s’exprimer de la façon suivante :

avec xθ = xcosθ+y cosθ et yθ = y cosθ−xsinθ. Le filtrage de l’image par ces noyaux est réalisé par
convolution.

31
10 DESCRIPTEURS DE FORME

10 Descripteurs de forme
10.1 Descripteurs classiques
• Aire A, périmètre P, boîte englobante (calculés à partir des composantes connexes).
• Nombre d’angles droits, nombre de coins saillants ou entrants. • Circularité : A/P2, Compacité :
4π× circularité.
• Rectangularité = Aire/Aire rectangle exinscrit.
• Eccentricté = longueur axe majeur/ axe mineur
• Nombre d’Euler. Différence entre le nombre de composantes connexes et le nombre de trous.

10.2 Signature et descripteurs de Fourier

Représentation de la forme par une fonction de type y = f(x) (par exemple, distance par rapport
au centre de gravité). Une fois la signature calculée, elle peut être caractérisée par les descripteurs
de Fourier, c’est-à-dire la transformée de Fourier de la signature. La figure 19 montre un exemple de
signature définie par la distance des points de contours par rapport au centre de gravité.

Figure 19 – Illustration du calcul de la signature.

10.3 Codage de Freeman

Le codage de Freeman permet de coder un contour en ne codant que les déplacements relatifs.
On considère un contour fermé d’épaisseur 1 pixel. Ce contour est parcouru de proche en proche. En
chaque point, il y a soit 4 directions (en 4-connexité), soit 8 directions (8-connexité) possibles pour
passer au point suivant (voir figure 20). Chacune des directions est codée par 1 chiffre (de 0 à 3 ou
de 0 à 7).
Le code obtenu sur la figure 20 est : 11007764606544133442. Une rotation de la représentation
aboutit au même résultat. Ainsi, on privilégie une représentation par code minimal, c’est-à-dire que
le code subit des rotations jusqu’à atteindre la valeur minimale, ici : 00776460654413344211. Il est

32
possible de compresser le code en comptant les occurrences successives : par exemple
000000777777777 devient 6097 (6 zéros puis 9 septs).
Propriétés utiles pour la reconnaissance
— Agrandissement (×k) du contour en répétant k fois chaque descripteur.
— Rotation de k × 2π/n (n-connexité) en ajoutant ou retranchant k modulo n à la chaîne initiale.
10.4
Moments

Figure 20 – Illustration du codage de Freeman.

— Longueur du descripteur√ : en 4 connexité (=nb. de descripteurs) et en 8 connexité (nb

descripteurs pairs + 2 nb descripteurs impairs).
— Inversion d’un chemin : inversion des descripteurs (jinv = n/2 + j modulo n) puis inversion de
la séquence.
— Simplification d’un chemin : remplacer p descripteurs consécutifs par des descripteurs
équivalents reliant les mêmes points.

10.4 Moments
10.4.1 Moments géométriques

Aire : M00
Centre d’inertie : .

10.4.2 Moments gémétriques centrés

33
 10.4.3 Moments invariants de Hu
Les moments invariants de Hu8 correspond à un ensemble de 7 combinaisons d’invariants centrés
définis de façon à être invariants vis-à-vis de la translation, ou de l’échelle, ou de la rotation.

1962
10 DESCRIPTEURS DE FORME

10.5 Transformée de Hough

La méthode d’origine a été conçue pour détecter des lignes droites. La méthode se généralise
toutefois à tout type de forme paramétrée, comme des cercles, des ellipses, etc. En chaque point
(x,y) de l’image, peut passer une infinité de lignes droites dont l’équation peut s’écrire ρ = y cosθ +
xsinθ où θ est l’angle de la droite (dans un repère prédéfini) et ρ la distance de la droite à l’origine
du repère. Cette distance ρ est la longueur du segment passant par l’origine et perpendiculaire à la
droite. Un espace de votes H(θ,ρ) est construit. Chaque point (x,y) dans l’image vote pour un
ensemble de couples (θ,ρ) en incrémentant la case correspondante dans H(θ,ρ). Les couples (θ,ρ)
ayant obtenu un nombre significatif de votes sont susceptibles de correspondre aux paramètres
d’une droite présente dans l’image. La longueur de la ligne est donnée par le nombre de votes (voir
figure 21).

Figure 21 – Illustration de la transformée de Hough.

8
. M. K. Hu, Visual Pattern Recognition by Moment Invariants, IRE Trans. Info. Theory, vol. IT-8, pp.179–187,

34
 11 Mouvement
11.1 Détection du mouvement par soustraction du fond
Typiquement, dans le cas où la caméra est fixe, la détection du mouvement consiste à construire
uneimagederéférenceassociéeaufondsansmouvement(Background)etàlasoustrairedel’image
courante.
Il existe un grand nombre de méthodes qui diffèrent par les stratégies employées pour :
1. la construction de l’image de fond
2. le calcul de distance de l’image courante par rapport au fond permettant d’obtenir l’image des
pixels en mouvement, appelée également image d’avant-plan (Foreground)
3. éventuellement les primitives visuelles utilisées : même si ce sont généralement les valeurs
d’intensité des pixels qui sont généralement utilisées, certains traitements se basent sur
l’extraction des contours pour détecter le mouvement.
D’autre part, les méthodes s’avèrent plus ou moins robustes face aux différentes perturbations
susceptibles de se produire dans les vidéos : changements d’illumination plus ou moins brutaux, bruit
d’acquisition.
Ces approches supposent qu’une image du fond (que l’on appellera plus tard background B(x))
est disponible, c-à-d une image de la scène dans laquelle aucun objet ne bouge. Dans un premier
temps, nous supposons que l’image de référence est la première image de la vidéo, notée I0.
Appelons It l’image courante (à l’instant t). Il est possible de détecter les pixels en mouvement
(Foreground) F(x) en tout point x de l’image à l’aide de l’équation suivante :

1 si |I0(x) − It(x)| > Th

F
sinon

où Th est un seuil à définir.

Ici, l’image de référence est la première image de la séquence. Or, au cours du temps, à l’échelle
d’une journée ou d’une année, les conditions d’acquisition et la scène peuvent évoluer. Il est alors
nécessaire de mettre à jour continuellement l’image de référence, par exemple par une combinaison
linéaire entre l’image du fond et l’image actuelle, avec un paramètre α ∈ [0,1[. Cette mise à jour est
faite juste après la détection des objets en mouvement F(t).

B(x,y) = αB(x,y) + (1 − α)It(x,y)

Cela équivaut à réaliser une moyenne temporelle des images en utilisant une plage temporelle
dont la durée dépend de α. Si la valeur de α est proche de 1, la plage temporelle est grande et le fond
est mis à jour de façon très progressive. Si α est égal à 0, l’image de référence est directement l’image
précédente.

35
 11.2 Flot optique
Le flot optique correspond au champ des vecteurs de vitesse apparente des pixels dans l’image.
Ce mouvement est dit « apparent »car il ne correspond par forcément à un mouvement réel (dans
la scène 3D) projeté sur le plan 2D du capteur. L’exemple le plus illustratif est sans doute celui d’une
sphère (ou d’un cylindre) de couleur parfaitement uniforme qui tourne autour de son axe de
symétrie. Le mouvement devient apparent dès que l’objet est texturé. Ainsi, la perception du
mouvement dépend de la distribution spatiale des intensités lumineuses dans l’image.
Pour calculer le flot optique, il est nécessaire de poser des hypothèses quant au modèle de
variation photométrique. Le plus simple est de considérer que l’intensité des points en mouvement
11 MOUVEMENT

est conservée au cours du temps et que les intensités de deux images successives d’une séquence
sont reliées entre elles par l’expression suivante :

It(x,y) = It−1(x + u,y + v) (1)

où It et It−1 sont les images aux instants courant et précédent, u et v sont les coordonnées de
translation du pixel et v = (u,v) est le vecteur vitesse. L’équation (1) est appelée contrainte de
conservation de la luminance. Calculer le flot optique revient à calculer ce vecteur de
déplacement en tout point9.
Enfaisantl’hypothèsedepetitsdéplacementsinter-imageetdedifférenciabilitéspatio-temporelle
de l’intensité lumineuse (c-a-d que les dérivées existent), la contrainte de conservation de l’intensité
devient :

Ixu + Iyv + It = ∇I.v + It = 0 (2)

Cette équation est une approximation, obtenue après développement limité de (1). Ici, Ix et Iy
se réfèrent aux composantes du gradient spatial ∇I = (Ix,Iy). It est l’image de gradient temporel,
calculée comme la différence entre deux images successives.
L’équation (2) permet de calculer la projection du vecteur vitesse dans la direction du gradient
spatial (perpendiculaire aux contours). Ainsi, si le déplacement de l’objet est tangent à son
contour, le mouvement n’est pas perceptible.

11.3 Algorithme de Horn et Schunck

Le champ de vitesse peut être calculé en combinant la contrainte de conservation de la
luminance avec une régularisation globale dans l’image. v(p) = (u,v)(p). Il s’agit alors de
minimiser la fonction suivante :
Z
(∇I(p)v(p) + It(p))2 + α2(k∇u(p)k + k∇v(p)k)2dp
(p)∈I

9
. C’est un problème sous-estimé, car il faut déterminer 2 paramètres alors que nous n’avons que des informations
de luminance.

36
 α est un coefficient fixé par l’utilisateur pour donner plus ou moins de poids à la régularisation.
Le terme de régularisation force la vitesse à être lisse dans l’image (force les dérivées de vitesse
k∇uk et k∇vk à être faibles dans l’image). On minimise cette fonction de manière itérative à l’aide
des équations suivantes :

(3)

(4)

où k sont les itérations, u¯ et v¯ sont les cartes de vitesses en p lissées par un filtre passe-bas
pour réduire l’importance des artefacts. Il est nécessaire de fixer une condition d’arrêt qui peut
être soit un nombre d’itérations fixe, ou lorsque le vecteur de mouvement v n’évolue plus de
manière significative d’une itération k à l’autre k + 1.
11.4 Algorithme de Lucas-
Kanade

11.4 Algorithme de Lucas-Kanade

LucasetKanadeontproposéuneméthodequi,aulieudecalculerunvecteurvitesseindépendant en
chaque point, considère un voisinage V. Il s’agit alors de minimiser la fonction suivante :

XW(p)[∇I(p,t)v + It(p,t)]2 (5)

p∈V

où V est un voisinage spatial de l’image contenant N pixels, W représente une fonction de fenêtrage
permettant de donner plus d’influence aux pixels du centre plutôt qu’à sa périphérie. Typiquement,
il s’agit d’un noyau Gaussien.
La solution de (5) est celle qui permet d’annuler sa dérivée par rapport à v. Cela se résume à
calculer le produit matriciel suivant :

−1

W I
I
v

p∈V p∈V

37
 La matrice 2×2 est appelée tenseur de structure. Il peut arriver qu’elle ne soit pas inversible ou
mal conditionnée, ce qui rend le calcul du mouvement très sensible au bruit, instable. Pour améliorer
les résultats, il est possible de détecter au préalable les points pour lesquels la matrice est inversible.
Il s’agit du détecteur de coins de Shi et Tomasi [?], disponible dans OpenCV sous le nom
goodFeaturesToTrack10.

10
. http ://[Link]/modules/imgproc/doc/feature_detection.html#goodfeaturestotrack

38
12 COMPRESSION D’IMAGES

12 Compression d’images
Comprimer une image consiste à la coder de sorte qu’elle prenne moins de place en mémoire.
Pour gagner de la place, on exploite la redondance : spatiale liée aux zones de l’images uniformes,
temporelle, liée aux zones sans mouvement dans une vidéo. Une façon efficace de comprimer une
image consiste à comprimer de façon plus importante les hautes fréquences (contours, textures) car
elles sont peu visibles à l’œil.
Le codeur JPEG travaille sur des blocs de taille 8×8, notés b(i,j) pour i ∈ [0,7] et j ∈ [0,7].
Dans le cas d’images couleur, on effectue une conversion vers l’espace Y cbcr. La
compression suit quatre étapes successives :
1. Transformée DCT (passage dans le domaine fréquentiel)
2. Quantification
3. Parcours zig-zag et RLC (Run Length Code)
4. Codage de Huffman
Dans un premier temps, chaque bloc de l’image est transformé dans le domaine fréquentiel à
l’aide de la transformée en cosinus DCT (pour Direct Cosinus Transform) qui est une variante de la
transformée de Fourier. On obtient alors une représentation en bloc B(i,j) de taille 8 × 8. La DCT
consiste en une somme de fonctions cosinus oscillant à différentes fréquences. Elle permet une
représentation en amplitude et en fréquence, plus propice à la compression. En effet, à partir de
cette représentation B(i,j), les basses fréquences pourront être facilement conservées (dans la partie
en haut à gauche de chaque bloc) et les hautes fréquences sont regroupées en bas à droite. Afin
d’appliquer la DCT, les données sont préalablement centrées entre -128 et 127 : b(i,j) = b(i,j) −
128∀i,j.

Dans un deuxième temps, une quantification est effectuée pour chaque bloc B(i,j) par division
par une matrice de quantification . Les zones de S(i,j) correspondant aux
hautes fréquences vont être quantifiées avec un facteur plus important. Par exemple, pour une image
codée en 8 bits on peut avoir ce type de matrice :
11 10 16 24 40 51
16 61
12 14 19 26 58 60
12 13 16 24 40 57 69 55
17 22 29 51 87 80 56
14
22 37 56 68 109 103
62
35 55 64 81 104 113
14 64 78 87 103 121 120 77
Q= 18 92 95 98 112 100 103 92
101
99
24

49

39
 72

Ainsi, du fait de l’approximation round à la valeur entière inférieure, la plupart des coefficients
associés aux hautes fréquences sont annulées.
Enfin, chaque bloc est analysé le long d’un parcours en zigzag (comme décrit par la figure 22) et
le mot de 64 valeurs qui en découle est codé à l’aide d’un codage RLC ( pour Run Length Code). Les
coefficients associés aux hautes fréquences (et généralement nuls) sont tout simplement oubliés. De
ce fait, il n’est pas utile d’utiliser les 64 coefficients pour coder le bloc, mais bien souvent une dizaine
de coefficient suffit. Dans un bloc parfaitement uniforme où la DCT ne montre qu’une composante
continue, un seul coefficient suffit. On est donc effectivement passé d’un bloc de 64 valeurs
redondantes (car identiques) à un seule valeur. Dans le cas où certaines séquences de
0 persistent, on utilise le RLC pour compacter cette séquence : 00000000 devient huit0 (le huit est
codé en utilisant une plage de valeurs différente de [ -128, 127] de façon à le distinguer de la valeur
8.
Enfin, le codage de Huffmann permet d’affecter un code différent à chaque coefficient (voir par
exemple,https ://[Link]/science/jpg/).

Figure 22 – Zig-Zag

13 Quelques références
•QuelquesméthodesdefiltrageenTraitementd’[Link]ïtineBergounioux[Link]
fr/hal-00512280v1/document

• Digital Image Processing, by Rafael C. Gonzalez and Richard E. Woods, Prentice-Hall, 2002

• The Image Processing Handbook, by John Russ, CRC Press, 1998

• Morphological Image Analysis : Principles and Applications, by Pierre Soille, Springer-Verlag

40
Berlin Heidelberg, 1999

• Analyse d’images : Filtrage et Segmentation, Cocquerez and al., Ed. Dunod, 1995

• Le traitement des images, H. Maître, Hermes Science Publications , 2003

• Les cours d’Antoine Manzanera https ://[Link]/ manzaner/[Link]

41