Extraction de zones d’int´
erˆ
ets dans
une image de textures

Rapport de stage

Giap Nguyen ()

Encadrant :
Micka¨
el Coustaty ()
Jean-Marc Ogier ()

Laboratoire :
Laboratoire Informatique, Image et Interaction (L3I)
Universit´e de La Rochelle

30 aoˆ
ut 2009


Remerciements
Je tiens tout d’abord `
a remercier les professeurs d’informatiques et de fran¸cais
de l’Institut de la Francophonie pour l’Informatique (IFI) qui nous ont dispens´es les
cours pendant mes ann´ees de Master.
Je souhaite ´egalement remercier mes encadrants de stage, M. Jean-Marc Ogier
et M. Micka¨el Coustaty, pour leur aide pr´ecieuse et leurs encouragements.
Enfin, je voudrais remercier les personnes du L3i pour leur sympathie et leur
accueil.

i


R´
esum´
e
Ce travail se concentre sur l’extraction de zones d’int´erˆets dans les lettrines
(images de lettre d´ecor´ees), qui se trouvent dans les documents anciens conserv´es
dans des biblioth`eques, des mus´ees et des archives publiques. Notre objectif principal
est de d´evelopper une m´ethode de segmentation de textures dans les lettrines. Les
images que nous traitons sont obtenues par pression d’un tampon sur une feuille,
et sont donc compos´ees de traits. Pour cette raison, nous proposons une m´ethode
reposant sur l’extraction et l’analyse de traits. Pour cela, nous extrayons d’abord des
traits et les caract´erisons. Les caract´eristiques utilis´ees sont l’orientation, l’´epaisseur
et la courbure. Ensuite, une distance propre est pr´ecis´ee pour mesurer la similarit´e
entre des traits. Enfin, nous utilisons une classification hi´erarchique pour classer ces
traites. Les traits voisins similaires sont group´es dans un segment.
Mots-cl´
es: Reconnaissance des formes, indexation d’images, segmentation, signatures texturelles, signatures structurelles et topologiques.

Abstract
This work focuses on the extraction of interesting zones in drop caps (images
of decorated letter), which can be found in historical documents. These documents
are conserved by the libraries, the museums and the public archives. Our principal
objective is to develop a texture segmentation method for drop caps. Drop caps were
obtained by pressure of a stamp on paper, and therefore, contains strokes. Because of
that, we suggest a stroke base method for drop caps segmentation. Firstly, we extract
each stroke and get its features. The features used in our method are orientation,
thickness and curvature. After that, a distance is defined to measure the similarity

between the strokes extracted. Finally, we use the hierarchic classification to classify
the strokes. In our results, the neighbor similar strokes will be grouped in a segment.
Keywords: Pattern recognition, image indexing, segmentation, textural features,
structural and topological features

ii


Table des mati`
eres
Remerciements

i

R´
esum´
e

ii

Abstract

ii

Table des figures

v

Liste des tableaux


vii

1 Introduction

1

1.1

Probl´ematique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

1.2

Motivation

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2

1.3

Objective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

1.4

Contribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .


3

1.5

Environnement de stage . . . . . . . . . . . . . . . . . . . . . . . . .

4

´
2 Etat
de l’art

5

2.1

Texture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

2.2

Extraction de caract´eristiques de textures . . . . . . . . . . . . . . .

6

2.2.1

Matrice de co-occurrence . . . . . . . . . . . . . . . . . . . .


6

2.2.2

Fonction d’auto-corr´elation . . . . . . . . . . . . . . . . . . .

9

2.2.3

M´ethodes bas´ees mod`ele . . . . . . . . . . . . . . . . . . . . .

9

2.2.4

Filtrage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

10

2.2.5

Le diagramme de Vorono¨ı . . . . . . . . . . . . . . . . . . . .

12

Segmentation et classification de textures . . . . . . . . . . . . . . .

16


2.3.1

Segmentation de textures . . . . . . . . . . . . . . . . . . . .

16

2.3.2

Classification de textures . . . . . . . . . . . . . . . . . . . .

17

2.3

3 Segmentation de textures de lettrines
3.1

Caract´eristiques de lettrines . . . . . . . . . . . . . . . . . . . . . . .
iii

18
18


3.2

Proc´edure de la segmentation de textures de lettrines . . . . . . . . .

18


3.3

Pr´e-traitement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

18

3.3.1

Binarisation d’images . . . . . . . . . . . . . . . . . . . . . .

19

3.3.2

D´ebruitage . . . . . . . . . . . . . . . . . . . . . . . . . . . .

20

Extraction des traits . . . . . . . . . . . . . . . . . . . . . . . . . . .

20

3.4.1

D´etermination de couleur de traits . . . . . . . . . . . . . . .

20

3.4.2


Squelettisation . . . . . . . . . . . . . . . . . . . . . . . . . .

22

3.4.3

Transform´ee en distance . . . . . . . . . . . . . . . . . . . . .

23

Caract´erisation des traits . . . . . . . . . . . . . . . . . . . . . . . .
´
3.5.1 Epaisseur
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

25
27

3.5.2

Orientation . . . . . . . . . . . . . . . . . . . . . . . . . . . .

27

3.5.3

Courbure . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

32


Classification des traits . . . . . . . . . . . . . . . . . . . . . . . . . .

32

3.6.1

Distance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

33

3.6.2

Construction d’arbre de grappes . . . . . . . . . . . . . . . .

35

3.6.3

Inconsistance . . . . . . . . . . . . . . . . . . . . . . . . . . .

35

Segmentation des traits . . . . . . . . . . . . . . . . . . . . . . . . .

36

3.7.1

Voisinage . . . . . . . . . . . . . . . . . . . . . . . . . . . . .


36

3.7.2

Description de texture d’une image . . . . . . . . . . . . . . .

38

3.4

3.5

3.6

3.7

4 Exp´
erimentation

39

4.1

L’environnement d’impl´ementation . . . . . . . . . . . . . . . . . . .

39

4.2

Impl´ementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .


39

4.3

R´esultat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

40

5 Conclusion

43

5.1

Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

43

5.2

Perspective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

43

Bibliographie

45

iv



Table des figures
1.1

Lettrine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.1
2.2
2.3
2.4
2.5
2.6
2.7
2.8

Matrice de co-occurrence . . .
Fractal . . . . . . . . . . . . .
La dimension fractale . . . .
Filtre de Gabor . . . . . . . .
Le diagramme de Voronoi . .
La triangulation de Delaunay
Divise and conquer . . . . . .
Balayage . . . . . . . . . . . .

.
.
.
.
.

.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.


.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.

.
.
.
.
.
.

.
.
.
.
.
.
.
.

7
10
11
12
13
13
14
15

3.1
3.2
3.3
3.4
3.5

3.6
3.7
3.8
3.9
3.10
3.11
3.12
3.13
3.14
3.15
3.16
3.17
3.18
3.19
3.20
3.21

Otsu . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Binarisation . . . . . . . . . . . . . . . . . . . . . . . .
Bruits . . . . . . . . . . . . . . . . . . . . . . . . . . .
La couleur de traits . . . . . . . . . . . . . . . . . . . .
La couleur de traits . . . . . . . . . . . . . . . . . . . .
Squelettisation . . . . . . . . . . . . . . . . . . . . . .
La transformation en distance . . . . . . . . . . . . . .
Les pixels de candidat . . . . . . . . . . . . . . . . . .
La longueur . . . . . . . . . . . . . . . . . . . . . . . .
L’´epaisseur . . . . . . . . . . . . . . . . . . . . . . . .
L’´epaisseur approximative . . . . . . . . . . . . . . . .
Transform´ee de Radon . . . . . . . . . . . . . . . . . .
Projection d’un angle Θ dans la transforme de Radon

Exemple d’orientation des traits . . . . . . . . . . . . .
La courbure de traits . . . . . . . . . . . . . . . . . . .
La vision humaine sur la longueur . . . . . . . . . . .
La longueur relative du trait . . . . . . . . . . . . . . .
La construction d’arbre . . . . . . . . . . . . . . . . .
Les distances de groupage . . . . . . . . . . . . . . . .
La territoire de traits . . . . . . . . . . . . . . . . . . .
Une cat´egorie de texture dans une image . . . . . . . .

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.


.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.

19
20
21
21
22
23
24
26
27
28
28
30
31
31
32
34
34
35
36
37
38

4.1
4.2
4.3

4.4

D´ecoupage de la lettre H .
Erreur de fusion des traits
Des points . . . . . . . . .
Des bruits . . . . . . . . .

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.

.

.
.
.
.

.
.
.
.

.
.
.
.

40
41
41
42

.
.
.
.

.
.
.

.

.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.


v

.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.


.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.

.
.

.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.

.
.

.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.


.
.
.
.

.
.
.
.

1


5.1
5.2

La r´ep´etition des primitives . . . . . . . . . . . . . . . . . . . . . . .
La r´ep´etition des graviers . . . . . . . . . . . . . . . . . . . . . . . .

44
44

vi


Liste des tableaux
2.1

Indices de matrice de co-occurrence . . . . . . . . . . . . . . . . . . .


8

3.1
3.2
3.3

Proc´edure de segmentation de textures de lettrines . . . . . . . . . .
La structure de donn´ees de texture d’images . . . . . . . . . . . . . .
L’exemple de la description de texture . . . . . . . . . . . . . . . . .

18
38
38

vii


Chapitre 1

Introduction
1.1

Probl´
ematique

Aujourd’hui, nous pouvons trouver facilement des applications de l’informatique
dans la plupart des domaines de la vie. Dans les domaines qui r´e-exploitent des
documents, en particulier, avec des grosses masses de document, l’informatique s’exprime comme un outil tr`es utilis´e. Dans ce contexte, le traitement d’image fait une
grande contribution. Il r´ealise automatiquement des traitements sur les images :

analyse, caract´erisation, d´etection des informations int´eressantes, segmentation des
zones homog`enes, . . . Ces r´esultats nous permettent de d´evelopper des applications
d’indexation ou celles de recherche bas´ees sur le contenu d’image.
Ce stage s’int`egre dans le projet NAVIDOMASS 1 . Le but de celui-ci est de cr´eer
un outil qui permette d’indexer des images par le contenu pour faciliter le travail
des historiens. Les images que nous traitons sont des lettrines (images de lettre d´ecor´ees) (les images de la figure 1.1) sont difficiles `a traiter et `a reconnaˆıtre de part
la masse d’informations qu’elles contiennent. Cette information est difficile `a isoler
et `a segmenter.

(a)

(b)

(c)

Fig. 1.1 – Lettrine
1

NAVigation Into DOcument MASSes - Navigation dans des masses de documents
(http ://l3iexp.univ-lr.fr/navidomass/)

1


1.2. Motivation
Pour indexer des images par le contenu, nous devons faire d’abord l’´etude du
contenu de l’image. Cette ´etude peut correspondre simplement `a l’extraction de caract´eristiques globales, comme l’histogramme des couleurs par exemple. Cependant,
ce type de caract´eristique n’est pas suffisant et l’indexation d’images ne donne pas
de r´esultats satisfaisant. C’est pourquoi nous avons pens´e `a extraire des caract´eristiques de diff´erentes zones de l’image. Cela pose encore une fois un autre probl`eme
qui n’est pas toujours facile `

a r´esoudre : la segmentation d’images.
Il est couramment utilis´e des crit`eres de similarit´e pour segmenter l’image en
zones. Par exemple, nous pourrions utiliser le niveau gris comme crit`ere. Dans le
cas d’images de documents anciens, le niveau gris de chaque zone segment´ee varie
faiblement et toutes les zones semblent homog`enes, ce qui ne donne pas de r´esultats
int´eressants. Pour am´eliorer la segmentation, nous avons cherch´e `a utiliser d’autres
caract´eristiques d’image, et en particulier, nous avons principalement ´etudi´e la texture puisqu’elle est une caract´eristique tr`es particuli`ere des diff´erentes zones.
Les textures pr´esentes sur des lettrines sont diff´erentes des textures classiques de
part la nature mˆeme des images. Elles sont des images obtenues par impression d’un
tampon sur une feuille, et sont donc compos´ees de traits. Il est donc n´ecessaire de
r´e-explorer les m´ethodes de la litt´erature, pour les adapter ou mˆeme de trouver des
nouvelles m´ethodes.

1.2

Motivation

Les m´ethodes de segmentation de textures propos´ees dans la litt´erature pr´esentent souvent des limitations. Parmi ces m´ethodes g´en´erales, nous pouvons citer
celles bas´ees sur la matrice de co-occurrence [Haralick 73, Marc Bartels 05], ou reposant sur des filtres de Gabor [Dunn 98, Teuner 95, Dunn 95]. D’autres m´ethodes
ont ´et´e ´elabor´ees pour des textures particuli`eres, comme les textures r´ep´etitives ou
naturelles. Bien que ces m´ethodes fonctionnent assez bien dans les exp´erimentations,
les r´esultats obtenus en application r´eelle sur nos images ne sont pas satisfaisants.
Chaque type de texture a des caract´eristiques particuli`eres, auxquels il faut associer
des m´ethodes adapt´ees.
Les lettrines sont des images compos´ees de traits (la figure 1.1). Pour les segmenter convenablement, il conviendra d’extraire les traits qui les composent. Ce
stage propose une m´ethode qui calcule des statistiques sur les traits qui composent
la texture des lettrines. Cette approche diff`ere des approches classiques qui op`erent
g´en´eralement au niveau des pixels. Les m´ethodes de segmentation `a base de calcul
de primitives sur des textures pr´esentent deux grands avantages :
– Analyse la texture de mani`ere similaire `a la vision humaine. Les op´erations

r´ealis´ees au niveau des pixels ne collent pas directement `a la vision humaine,
contrairement `
a notre approche qui repose sur des calculs de statistiques et
des comparaisons au niveau de primitives textures.
– Diminuer le temps de calcul dans la phase de classification, puisqu’il n’est plus
2


1.3. Objective
n´ecessaire de comparer les pixels un-`a-un mais plutˆot des traits entre eux. De
plus, nous pouvons ˆetre sur que le nombre de primitives texture est beaucoup
plus petit que celui des pixels. Donc le nombre de comparaison, dans la phase
de classification ou de segmentation, est diminu´e.
Cette approche repose donc sur une ´etape clef, qui consiste tout d’abord `a extraire les primitives de texture.

1.3

Objective

Le but de ce stage est de chercher une m´ethode pour segmenter les textures dans
les lettrines. Une lettrine contient plusieurs textures r´eunies en plusieurs zones, et
ce stage consiste `
a trouver un plus petit nombre de zones satisfaisant la condition :
”une zone contient une seule cat´egorie de texture”. Le r´esultat de la segmentation
d’une image nous donnera donc un ensemble de zones homog`enes.
Pour arriver `
a notre objectif, nous devons identifier des caract´eristiques propres
aux textures des lettrines. La seconde ´etape consiste alors `a d´efinir une proc´edure
pertinente associ´ee `
a ces caract´eristiques. Enfin, ce stage doit ´egalement privil´egier

l’exactitude aux temps de calculs.
D’autre part, nous voulons proposer une structure qui repr´esente l’image par des
zones segment´ees, elle reprend seulement des informations int´eressantes des textures
contenues dans une image. Cette structure facilite la d´emarche d’indexation et de
recherche par le contenu.
Toutes les m´ethodes d´evelopp´ees ont ´et´e test´ees sur une base de 916 images
contenant des lettrines.

1.4

Contribution

La contribution de ce stage porte sur l’analyse et la segmentation des textures
dans les lettrines. Ce travail doit faciliter et acc´el´erer les travaux des historiens qui
travaillent sur les lettrines [CESR 09]. Notre analyse des textures repose sur une
nouvelle approche, bas´ee sur l’extraction de primitives textures. Dans le cas des lettrines, ces primitives sont des traits, puisque pr´esent dans toutes les lettrines. Notre
m´ethode pourrait ´egalement ˆetre utilis´ee sur d’autres types d’images contenant des
textures avec le d´esir d’am´eliorer les r´esultats de travaux pr´e-existants, par exemple,
nous pouvons utilisons la matrice de co-occurrence ou la fonction d’auto-corr´elation
pour faire la statistique sur des primitives.

3


1.5. Environnement de stage

1.5

Environnement de stage


Le stage est effectu´e au sein de l’´equipe Imedoc 2 du laboratoire L3i 3 `a l’universit´e de La Rochelle en France. Cr´e´e en 1993, le laboratoire L3i comporte 80 chercheurs dont 34 permanents travaillant sur les domaines de l’Informatique, l’Image
et leurs interactions.
Le L3i est le laboratoire de recherche du domaine STIC 4 de l’Universit´e de la
Rochelle associant tr`es efficacement les chercheurs de l’IUT 5 et du Pˆole Sciences en
informatique puisque la grande majorit´e des enseignants-chercheurs en Informatique
et en G´enie informatique de l’universit´e de la Rochelle se retrouvent au sein du L3I.
En terme de politique scientifique, le laboratoire L3i est r´esolument tourn´e vers
les r´eseaux de recherche r´egionaux (PRIDES 6 , ERT 7 ”Interactivit´e num´erique”),
nationaux et internationaux dans les secteurs de visibilit´e de son action scientifique, et notamment autour du flux vid´eo (cin´ema), de l’ing´enierie documentaire
et de l’interactivit´e num´erique. Ceci est consolid´e par une politique volontariste de
participation ou de pilotage de projets de recherche labellis´es (ANR 8 , PCRD 9 , . . . ).
Son action internationale est actuellement renforc´ee avec des liens privil´egi´es avec
les centres de recherche tels que le CVC 10 de Barcelone, le laboratoire Regim de
Sfax (Tunisie), le MSI 11 (Unit´e de l’IRD 12 ) et le MICA 13 (unit´e internationale du
CNRS 14 ) d’Hano¨ı (Vietnam) et l’Universit´e de Kuala Lumpur (Malaisie).
Le laboratoire poss`ede le label d’´equipe d’accueil du Minist`ere de la Recherche
´
(EA 2118) depuis 1997 et dispose par ailleurs du label d’Equipe
de Recherche Technologique (ERT) avec ses partenaires, label attribu´e par le minist`ere de la recherche.
Les points d’entr´ee scientifiques de l’´equipe Imedoc portent sur l’imagerie du visible `
a l’invisible, les s´equences d’images (de la pellicule au flux vid´eo) et les syst`emes
d’informations documentaires (du patrimoine au document num´erique).

2

Image, M´edia Num´eriques et Documents
Laboratoire Informatique, Image et Interaction - http ://l3i.univ-larochelle.fr/
4
sciences et technologie de l’information et de la communication
5

Institut Universitaire de Technologie de La Rochelle - http ://www.iut-larochelle.com/
6
Pˆ
ole R´egional de Recherche en Images, Donn´ees et Syst`emes
7´
Equipe de Recherche Technologique
8
Agence nationale de la recherche - http ://www.agence-nationale-recherche.fr/
9
Programme Cadre de Recherche et D´eveloppement
10
Centre de vision par ordinateur
11
Mod´elisation et Simulation Informatique
12
’Institut de recherche pour le d´eveloppement
13
Multim´edia, information, communication et application
14
Centre national de la recherche scientifique
3

4


Chapitre 2

´
Etat
de l’art

2.1

Texture

La texture est une propri´et´e de la surface, elle d´epend l’asp´erit´e ou la distribution
des couleurs des surfaces. Elle est une composante riche en information d’une image,
elle devient donc un param`etre tr`es important pour la compr´ehension et l’interpr´etation d’image. Son importance dans l’interpr´etation d’images explique l’int´erˆet que
l’on lui porte dans l’analyse d’images et le nombre de m´ethodes d’analyse d’images
qu’elle est prise en compte.
Si on utilise la texture comme crit`ere pour diff´erencier des r´egions, une zone avec
l’homog´en´eit´e texturelle est limit´ee par le contour qui est la variation d’intensit´e
texturelle. Nous pouvons reconnaˆıtre la texture par des sens tactiles ou par la vision [Chen 00]. Une texture peut ˆetre fine ou grosse. Ou bien, elle est retrouv´ee par
la distribution des couleurs. Elle est peut-ˆetre d´etect´ee par sa primitive - le textel
(texture element), dans ce cas, la texture est une r´ep´etition des textels.
Cependant, on n’a pas pu trouver une d´efinition formelle de ce qu’est la texture
et c’est la raison pour l’abondance des m´ethodes pour d´eterminer ou diff´erencier des
textures. On se contente donc de trouver un mod`ele ad´equat pour l’´etude `a mener.
En cons´equence, les d´efinitions de texture propos´ees varient selon les domaines de
recherche et les conceptions des auteurs. Les caract´eristiques utilis´ees souvent pour
la conception des mod`eles sont :
– Une texture peut ˆetre p´eriodique ou elle est une r´ep´etition d’un motif de base
– Mais, une texture peut quand-mˆeme ˆetre non p´eriodique, elle est d´esordonn´ee.
Dans le premier cas, on essaie de trouver le motif de base de la texture. Ensuite,
on cherche `
a extraire des caract´eristiques du motif et la fr´equence des motifs. Ces
caract´eristiques vont repr´esenter la texture. C’est un bon mod`ele pour les textures
artificielles r´ep´etitives mais il est difficile d’appliquer ce mod`ele pour les autres types
de texture. Par exemple, des textures naturelles sont par hasard form´ees, c’est difficile `
a d´efinir le motif et la fr´equence.
Le deuxi`eme cas est juste pour la plupart des textures, pourtant, il ne sugg`ere

pas de d´eterminer l’orientation de la texture. Pour cela, on peut essayer de trouver la

5


2.2. Extraction de caract´eristiques de textures
distribution, la corr´elation des couleurs. De fa¸con plus avanc´ee, on essai d’appliquer
le premier mod`ele `
a ces textures en g´en´eralisant le concept de motif.
L’analyse de texture est tr`es utile dans la vision par ordinateur, elle a plusieurs
application dans la vie r´eelle, par exemple, l’analyse d’image m´edicale, l’analyse de
document, l’analyse d’empreinte digitale, . . . Les textures diff´erentes nous aident
`a distinguer diff´erentes surfaces, en cons´equence, elles facilitent la distinction des
objets dans les images.
Pour reconnaˆıtre la texture, nous avons deux types op´erations principaux : la
classification de texture et la segmentation de texture. La classification de texture
s´electionne une classe de texture (pr´e-d´efinie) pertinente `a chaque r´egion de texture dans une image. La segmentation de texture cherche des contours des r´egions
de texture. Pour r´esoudre ces probl`emes, nous pouvons diviser ces probl`emes en
sous-probl`emes comme l’extraction de caract´eristiques de texture, l’extraction de
primitives et le partitionnement de donn´ees. Pour ces deux op´erations, nous devons
r´ealiser la phase commune : extraction de caract´eristiques de texture.

2.2

Extraction de caract´
eristiques de textures

Bien que les textures soient des informations difficiles `a extraire, on a trouv´e
quelques m´ethodes pour extraire des caract´eristiques de textures. Pourtant, ces m´ethodes n’ont pas donn´e des r´esultats parfaits.
L’extraction de caract´eristiques de texture est la phase ´el´ementaire de la classification et la segmentation de texture. De bon r´esultat `a cette ´etape facilitent les

´etapes suivantes.
Dans cette section, nous supposons que nous travaillons avec des images homog`enes d’un point de vue texturelle, les caract´eristiques extraites vont proprement
repr´esent´ees la texture. Nous consid´erons aussi que les images de textures sont d´efinies par une fonction qui se r´efl´echit sur le niveau de gris des pixels.
Les m´ethodes repr´esent´ees dans ce qui suit sont des m´ethodes connues pour la
texture et elles peuvent ˆetre profitables ou ´evoquent des id´ees int´eressantes pour les
textures des lettrines.

2.2.1

Matrice de co-occurrence

La matrice de co-occurrence est largement utilis´ee dans l’analyse de texture. Elle
est tr`es facile `
a mettre en œuvre et donne de bons r´esultats sur plusieurs types de
texture. Dans la plupart des applications, les images utilis´ees sont repr´esent´ee en
niveaux de gris et la matrice de co-occurrence est connue sous le nom GLCM (Gray
Level Co-occurrence Matrix).

6


2.2. Extraction de caract´eristiques de textures
La matrice de co-occurrence C d’un vecteur de d´eplacement (∆x, ∆y) d’une
image I de la taille (m ∗ n) est d´efinie par la formule 2.1
n

m

C∆x,∆y (x, y) =
p=1 q=1


1, if I(p, q) = i and I(p + ∆x, q + ∆y) = j
0,
otherwise

(2.1)

Pour am´eliorer la performance de la m´ethode, nous pouvons r´eduire la taille de
la matrice. Pour le faire, nous pouvons grouper des niveaux gris de l’image par les
techniques de partitionnement de donn´ees (clustering).
L’image 2.1 montre la fa¸con dont est calcul´ee la matrice de co-occurrence du
vecteur de d´eplacement (1,0)

Fig. 2.1 – Calcul de la matrice de co-occurrence d’une image
Le choix du vecteur de d´eplacement est toujours tr`es important pour la r´eussite
de la m´ethode. Normalement, nous voulons obtenir des matrices de co-occurrence
de plusieurs vecteurs de d´eplacement sur des directions et des distances diff´erentes.
Le probl`eme est la combinaison des indices des matrices pour que nous pussions
` cˆot´e de ce
utiliser cette m´ethode avec des orientations et des ´echelles diff´erentes. A
probl`eme, nous voulons r´eduire le nombre de matrice de co-occurrence matrice calcul´e. Pour faire cela, nous devons ´evaluer l’importance des vecteurs de d´eplacement
par rapport des types de textures. Plusieurs ´etudes ont ´et´e men´ees pour d´eterminer
une distance ou une orientation optimale. En pratique, une distance courte donne
g´en´eralement de bons r´esultats [Karathanassi 00, Iftene 04].
La masse d’informations sur cette matrice est trop grande et nous ne pouvons
pas retirer directement des remarques utiles pour l’analyse de texture. Quatorze indices interm´ediaire (Table 2.1) sont propos´e par Haralick en 1973 [Haralick 73]. Ces
indices r´eduisent l’information contenue dans la matrice de co-occurrence et permettent une meilleure discrimination entre les diff´erents types de textures.
En outre, nous pouvons r´eduire le nombre d’indice utilis´e dans 14 caract´eristiques
de Haralick. Pour l’ind´ependance de la taille d’image et pour l’expression en termes
de probabilit´e, nous utilisons la matrice de co-occurrence normalis´ee pour calculer

7


2.2. Extraction de caract´eristiques de textures

Tab. 2.1 – Quatorze indices de matrice de co-occurrence propos´e par Haralick

8


2.2. Extraction de caract´eristiques de textures
des indices.

2.2.2

Fonction d’auto-corr´
elation

Du fait que la grossi`eret´e (ou la finesse) soit une propri´et´e facilement reconnaissable de la texture, cette mesure est utile pour l’analyse de texture. Dans des images
de texture, des pixels voisins sont connexes ou d´ependants, toutefois, des distances
du voisinage sont diff´erentes, elles d´ependent de la grossi`eret´e de la texture. Bas´e
sur cette propri´et´e, nous pouvons utiliser la fonction d’auto-corr´elation pour analyser des textures. Le r´esultat de la fonction d’auto-corr´elation d’une image I(x, y) de
taille (m, n) est une matrice A donn´ee par la formule 2.2.

A(u, v) =

m
x=0

n

y=0 I(x, y) ∗ I(x + u, y
n
m
2
y=0 I(x, y)
x=0

+ v)

(2.2)

Plus la texture est grossi`ere, plus sa matrice d’auto-corr´elation diminue doucement.
Pour calculer enti`erement l’auto-corr´elation, nous devons d’abord r´eduire proprement la taille de l’image car la taille de la matrice est ´egale celle de l’image.
Sinon, nous calculons seulement des ´el´ements importants de la matrice.

2.2.3

M´
ethodes bas´
ees mod`
ele

Les m´ethodes bas´ees mod`ele supposent que la texture est form´ee par un mod`ele
et on consid`ere que les param`etres de ce mod`ele sont des caract´eristiques de la texture.
Par exemple, si on utilise un champ al´eatoire de Markov 15 comme mod`ele, en
consid´erant que l’image est un champ al´eatoire de Markov. La probabilit´e qu’un
pixel re¸coive une intensit´e doit ˆetre positive et markovienne. La caract´eristique markovienne ´emet l’hypoth`ese que la distribution d’intensit´e des pixels d´epende uniquement de ses voisins, elle est ind´ependante du reste de l’image. Ce mod`ele vise
`a capturer des statistiques de ces voisinages et de les repr´esenter comme des param`etres du mod`ele. Dans quelques mod`eles bas´es sur le champ al´eatoire de Markov,
on utilise l’´equivalent entre le champ al´eatoire de Markov et celui de Gibbs pour
extraire des param`etres avec la formule (2.3) de probabilit´e de Gibbs [Cross 83,

Besag 74, Derin 87].
1 −U (x)
e
(2.3)
Z
O`
u U (x) est une fonction d’´energie et Z une constante de normalisation appel´ee
la fonction de partition. La fonction d’´energie est g´en´eralement calcul´ee sur la clique
form´ee par des pixels voisins. La fonction d’´energie est ensuite exprim´ee en terme
P (X = x) =

15

Markov Random Field - MRF

9


2.2. Extraction de caract´eristiques de textures
de fonction potentielle Vc (x) dans l’ensemble des cliques Q : U (x) =

c∈Q Vc (x).

Un autre exemple de mod`ele repose sur le mod`ele fractal. Un objet fractal (2.2)
est une forme g´eom´etrique complexe qui pr´esente une auto-similarit´e `a diff´erentes
´echelles, il s’inscrit donc dans une hi´erarchie de structures g´eom´etriques.

Fig. 2.2 – Fractal
En analyse de texture, la dimension fractale, qui est une mesure du degr´e d’irr´egularit´e d’un objet, d´ecrit une certaine propri´et´e de la texture. Le mod`ele fractal
de texture est bas´e essentiellement sur l’estimation par des m´ethodes spatiales de

la dimension fractale de la surface repr´esentant les niveaux de gris de l’image. La
dimension fractale d’un ensemble A est d´efinie par la formule 2.4

D=

log N
log (1/r)

(2.4)

Telle que N soit le nombre total de copies distinctes similaires `a A et 1/r correspond au facteur d’´echelle avec lequel A est divis´e.
Plusieurs m´ethodes ont ´et´e d´evelopp´ees pour calculer la dimension fractale dans
le cas auto-similaires. La plus utilis´ee est la m´ethode des ”boˆıtes”, qui est consid´er´ee
comme la plus simple pour le calcul de la dimension fractale. Les mesures consistent
dans le nombre de ”boˆıtes” n´ecessaires pour couvrir l’objet fractal ; les dimensions
des boˆıtes correspondent au pas de mesure.
Par exemple, dans l’illustration 2.3, la rectangle est divis´ee par 8 ∗ 14 = 112
boites (r = 1/112), et il y a 26 boites qui contiennent une partie de la courbe (en
gris) (N = 26). Donc,

D=

2.2.4

log 26
log 112

(2.5)

Filtrage


Les filtres sont tr`es utilis´es pour extraire des caract´eristiques de texture. Nous
pouvons trouver des exemples qui utilisent des filtres simples comme le filtre de Roberts, le filtre laplacien ou les filtres plus compliqu´es comme le filtre de Fourier ou
celui de Gabor.

10


2.2. Extraction de caract´eristiques de textures

Fig. 2.3 – La dimension fractale
Avec le filtre de Roberts ou le filtre laplacien, nous pouvons faire la convolution
et extraire des contours de l’image de texture. En suite, nous faisons directement
la segmentation bas´ee sur ces contours ou en calculant la densit´e de contours, qui
peuvent ˆetre utiles pour l’analyse de textures.
La transformation de Fourier permet de passer d’une repr´esentation de l’image
dans le domaine spatial `
a une repr´esentation dans le domaine fr´equentiel. On peut
ainsi analyser le contenu fr´equentiel de ce signal, et ensuite le travailler o`
u l’analyser
en profondeur.
L’extraction de param`etres de texture `a partir de la transform´ee de Fourier permet d’´etablir un mod`ele compact pour les textures p´eriodiques. Normalement, nous
choisissons quatre directions (0o , 45o , 90o , 135o ) et certaines fr´equences. Le nombre
de fr´equences d´epend de la taille de l’image. Typiquement, avec une image de taille
M ∗ N (M <= N ), les fr´equences choisies sont 20 , 21 , ..., 2t avec t = log M − 1.
Un filtre de Gabor est une sinuso¨ıde modul´ee par une gaussienne (la figure 2.4).
Dans le domaine fr´equentiel, il s’exprime comme ´etant une gaussienne centr´ee sur
une fr´equence d´etermin´ee. En 2D, un banc de filtres de Gabor va s’exprimer comme
´etant un ensemble de filtres, chacun s´electionnant une fr´equence particuli`ere dans
une dimension particuli`ere.

L’utilisation d’un banc de filtres de Gabor permet d’extraire de l’image consid´er´ee des informations pertinentes, `a la fois en espace et en fr´equence, relatives `a
la texture. Avec les filtres de Gabor, nous pouvons analyser la texture `a diff´erentes
´echelles et diff´erentes orientations.

11


2.2. Extraction de caract´eristiques de textures

Fig. 2.4 – Filtre de Gabor [AlainBoucher 08]

2.2.5

Le diagramme de Vorono¨ı

Le diagramme de Vorono¨ı et la relation avec la triangulation de Delaunay
Le diagramme de Vorono¨ı (la partition de Voronoi ou la pavage de Vorono¨ı) a
´et´e largement ´etudi´e dans le domaine de la g´eom´etrie et appliqu´e dans diff´erentes
disciplines. En ce qui concerne l’analyse de texture, elle r´ealise la division de mani`ere
dynamique par rapport `
a l’information image. Cette segmentation est tr`es utile si
tant est que la texture est al´eatoire. Ensuite de la phase de construction du diagramme de Vorono¨ı, nous pouvons extraire des param`etres par des statistiques des
caract´eristiques g´eom´etriques des diagonales dans le diagramme de Vorono¨ı.
Le diagramme de Vorono¨ı (la figure 2.5)consiste `a g´en´erer un partitionnement
du plan en polygones, ces polygones s’appellent des sites du diagramme. Pour faire
la g´en´eration, nous devons pr´eciser des germes, pour chaque germe, il y un site ´equivalent. Ces sites doivent satisfaire la condition suivante : les germes de deux sites
voisins sont ´equidistants `
a la fronti`ere (l’arˆete commune).
Nous pr´esentons ici aussi la triangulation de Delaunay, le graphe dual du diagramme de Voronoi, qui est utile pour la construction du diagramme de Voronoi. La
triangulation de Delaunay d’un ensemble P de points du plan est une triangulation

DT (P ) telle qu’aucun point de P n’est `a l’int´erieur du cercle circonscrit d’un des
triangles de DT (P ) (la figure 2.6 (a)).
La triangulation de Delaunay d’un ensemble discret P de points est le graphe
dual du diagramme de Voronoi associ´e `a P , c’est `a dire les points de P sont des
germes pour construire le diagramme de Voronoi. Ces points sont reli´es entre eux
par une arˆete si les sites sont voisins. On remarquera que les arˆetes du diagramme
de Vorono¨ı sont sur les m´ediatrices des arˆetes de la triangulation de Delaunay (la
figure 2.6 (b)), alors nous pouvons construisons facilement le diagramme de Voronoi
si la triangulation de Delaunay ´equivalente a ´et´e construite.
Pour construire le diagramme de Voronoi, nous pouvons donc g´en´erer directement le diagramme de Voronoi ou r´ealiser d’abord la construction de la triangulation
de Delaunay. Plusieurs algorithmes ont ´et´e propos´es pour les faire, ces algorithmes
peut-ˆetre group´es dans trois classes principales : m´ethodes incr´ementales, m´ethodes

12


2.2. Extraction de caract´eristiques de textures

Fig. 2.5 – Le diagramme de Voronoi

(a)

(b)

Fig. 2.6 – La triangulation de Delaunay

13


2.2. Extraction de caract´eristiques de textures

”divide and conquer”, et m´ethodes de balayage.

Algorithmes du type ”divide and conquer”
Les algorithmes du type ”divide and conquer” consistent `a diviser le probl`eme
g´en´eral en sous-probl`emes de plus petites tailles. La division se fait de fa¸con r´ecursive
jusqu’`
a obtenir des probl`emes simples `a r´esoudre (lorsqu’il ne reste plus que trois
points par exemple). Chaque sous-probl`eme est trait´e de fa¸con ind´ependante, et une
´etape de fusion est n´ecessaire pour unifier les sous-probl`emes. L’image 2.7 est une
illustration pour la construction d’une triangulation de Delaunay du type ”divide
and conquer”.

Fig. 2.7 – Divise and conquer

Algorithmes de balayage
Les algorithmes de balayage construisent les structures g´eom´etriques en balayant
le plan par une droite suivant un axe privil´egi´e, et mettent `a jour la structure chaque
fois qu’un point est rencontr´e. Fortune a propos´e son algorithme de ce type. L’algorithme de balayage de Fortune est connu comme l’algorithme le plus efficace pour
construire le diagramme de Voronoi d’un ensemble fini S de points du plan. Cet algorithme consiste `
a balayer le plan avec une ligne horizontale (ou verticale, au choix)
en tenant `
a jour un certain nombre d’informations n´ecessaires `a la d´etermination
des sommets du diagramme de Voronoi. Remarquons d’abord que le lieu des points
´equidistants entre un site et la droite de balayage est une parabole.
En cons´equence, si i et j sont deux sites, D la droite de balayage, et d la fonction
distance, le point d’intersection p des deux paraboles est tel que d(i, p) = d(p,D) =
d(j, p). Donc l’intersection des deux paraboles est `a ´egale distance des deux sites,
et, lors du d´eplacement de la droite de balayage, cette intersection d´ecrira la m´ediatrice des deux sites, c’est-`
a-dire pr´ecis´ement la fronti`ere que l’on recherche entre
les zones associ´ees aux sites. Toutefois, toutes les m´ediatrices ne font pas partie du

diagramme de Voronoi. Il faut donc g´erer, pendant le balayage, les ´ev´enements de
cr´eation et de destruction des arcs de paraboles, dont on sait qu’ils g´en´ereront des
segments de m´ediatrice faisant partie du diagramme de Voronoi. L’enveloppe des
arcs de paraboles utiles `
a la mise `a jour du diagramme de Voronoi peut ˆetre vue
comme une ligne de ressac dont chacun des points de cassure g´en`ere une arˆete du
14


2.2. Extraction de caract´eristiques de textures

(a)

(b)
Fig. 2.8 – Balayage

diagramme de Voronoi, lorsque la ligne de balayage se d´eplace.
Un arc de parabole sera cr´e´e `a chaque fois que la ligne de balayage rencontre
un site et un arc de parabole disparaˆıtra lorsqu’il sera r´eduit `a un point. Dans ce
cas, les deux arcs de paraboles voisins de celui qui disparaˆıt s’intersectent au point
auquel se r´eduit ce dernier.

Algorithmes incr´
ementaux
Les algorithmes incr´ementaux consistent ins´erer les germes, les uns apr`es les
autres, et modifier la structure chaque it´eration. La modification ne se fait que de
fa¸con locale. Pour la triangulation de Delaunay incr´ementale, lors de l’insertion d’un
point p, seuls les triangles dit ”en conflit” avec p sont modifi´es.
Pour appliquer le diagramme de Voronoi, nous devons d´efinir une distance appropri´ee entre points de l’image et choisir un ensemble de sites. La distance est d´efinie
en consid´erant les attributs de bas niveau de l’image et, en particulier, l’information

fournie par le niveau gris. Une fois la distance d´efinie, le probl`eme suivant qui se
pose est la s´election d’un ensemble de sites ad´equats pour cette tˆache. D’une part, les
sites doivent ˆetre repr´esentatifs du contenu de l’image ; D’autre part, chaque structure significative doit en contenir au moins un. Dans le cas des images en niveaux de
gris, les maxima de niveaux gris s’av`erent ˆetre des candidats naturels pour les sites.
Extraction de caract´
eristiques des sites
Apr`es construction du digramme de Vorono¨ı, les caract´eristiques des sites de
Vorono¨ı vont ˆetre extraites pour les autres applications. Par exemple, dans la seg15


2.3. Segmentation et classification de textures
mentation de textures, les sites avec des caract´eristiques similaires sont regroup´es
pour construire des r´egions de texture uniforme. Les moments calcul´es sur les sites
de Vorono¨ı sont des caract´eristiques utiles, qui refl`etent `a la fois la distribution spatiale et la forme des sites dans l’image.
Les moments d’ordres (p + q)i`eme d’une r´egion R avec les coordonn´ees (x0 , y0 )
sont d´efinis par la formule 2.6.

(x − x0 )p (y − y0 )q dxdy

mpq =

(2.6)

R

2.3

Segmentation et classification de textures

Avec ces m´ethodes d’extraction des caract´eristiques de textures ou de mod´elisa`

tion de textures, nous pouvons trouver plusieurs travaux connexes `a la texture. A
cot´e des travaux de cr´eation de textures comme la synth`ese de texture ou la cr´eation de formes `
a partir des textures, nous avons la segmentation de textures et la
classification de textures. Ces applications servent `a la compr´ehension du contenu
des images.

2.3.1

Segmentation de textures

La segmentation de textures est un probl`eme difficile parce que g´en´eralement
l’on n’a pas de connaissances `a priori sur les types et le nombre de textures dans
l’image. En fait, aucune connaissance sur les textures existantes dans l’image n’est
n´ecessaire afin de faire la segmentation de texture. La seule chose n´ecessaire est une
mani`ere pour dire que deux textures sont diff´erentes.
Les deux approches g´en´erales de l’ex´ecution texture segmentation sont ´equivalentes aux m´ethodes de la segmentation d’images : l’approche de r´egion ou l’approche
de contour. Dans l’approche de r´egion, on essaie d’identifier les r´egions de l’image
qui ont une texture uniforme. Les pixels ou de petites r´egions sont fusionn´es en
raison de la similitude de certaines propri´et´es de texture. Les r´egions ayant diff´erentes textures sont alors consid´er´ees comme des r´egions segment´ees. Cette m´ethode
a l’avantage que les fronti`eres des r´egions sont toujours ferm´ees et, par cons´equent,
les r´egions contenant diff´erentes textures sont toujours bien s´epar´ees. Cependant, il
faut pr´eciser le nombre de textures diff´erentes pr´esentes dans l’image `a l’avance. En
outre, les seuils de similitude des valeurs sont n´ecessaires.
L’approche par contour cherche les diff´erentes textures dans les r´egions adjacentes. Ainsi, les fronti`eres (contour) sont d´etect´ees o`
u il existe des diff´erences dans
la texture. Dans cette m´ethode, nous n’avons pas besoin de connaˆıtre le nombre de
r´egions dans la texture de l’image `a l’avance. Toutefois, les trous qui apparaissent
sur les fronti`eres posent un probl`eme, les r´egions ne sont plus ferm´ees et ne sont plus
clairement s´epar´ees.


16


2.3. Segmentation et classification de textures
Ces deux approches reposent sur la recherche de diff´erences ou de similarit´e
de textures. Cependant, la comparaison entre les pixels ne peut pas mener `a un
bon r´esultat parce que l’intensit´e des pixels individuels ne repr´esente pas la nature
de la texture. Pour segmenter correctement, nous devons faire la comparaison sur
des autres objets, qui repr´esente mieux la nature de la texture. Par exemple, nous
pouvons extraire pour comparer des sous-fenˆetres en divisant l’image en plusieurs
fenˆetres. Cela cause un probl`eme, quelle taille de fenˆetres va ˆetre utilis´ee ? Cette
taille doit ˆetre assez petite pour d´etecter correctement la position des changements
de textures et elle doit aussi ˆetre assez grande pour que les caract´eristiques extraites
repr´esentent bien des textures.
Le diagramme de Vorono¨ı pr´esent´e pr´ec´edemment est aussi une solution, nous
pouvons faire la comparaison des textures dans les sites de Vorono¨ı. En outre, nous
pouvons faire une extraction des primitives ou des ´el´ements de textures. Pourtant,
cette solution n’est pas toujours facile `a r´ealiser.

2.3.2

Classification de textures

La classification de textures a pour but de d´eterminer la classe de chaque texture. Nous avons plusieurs techniques pour la faire, elles sont divis´ees en deux types
principaux, la classification supervis´ee et non supervis´ee. Cependant, appliquer la
classification supervis´ee sur les textures n’est pas pratique, parce que nous ne savons
par `
a l’avance le nombre de classes de textures de l’image.
Dans les m´ethodes de classification non supervis´ee, k-means est une m´ethode
tr`es connue. K-means est une m´ethode de partitionnement de donn´ees, qui vise `a

au partitionnement de n observations en k grappes (cluster) dans lesquels chaque
observation appartient `
a la grappe avec la moyenne la plus proche. Il y a aussi des
variations de cette m´ethode, qui supprime des grappes vides ou ajoute de fa¸con raisonnable des grappes. Dans ce cas, le nombre de grappes n’est pas toujours ´egal `a
k.
Pour appliquer cette m´ethode, il faut connaitre `a priori le nombre de classes ce
qui n’est pas pratique pour les textures. Nous devons donc estimer le nombre de
classes de textures en fonction des autres caract´eristiques d’images.
En outre, nous pouvons utiliser les m´ethodes hi´erarchiques pour la classification non supervis´ee. Dans ces m´ethodes, on construit d’abord un arbre de donn´ees,
puis on d´efinit des crit`eres pour couper cet arbre, les sous-arbres coup´es sont les
grappes de r´esultat. Plusieurs fa¸cons existent pour construire l’arbre de donn´ees.
Par exemple, on consid`ere au d´ebut que chaque observation est une grappe. Tant
que le nombre de grappes est sup´erieur `a 1, on groupe les deux grappes les plus
proches. En r´eit`ere cette ´etape afin d’arriver `a un nombre de grappes ´egal `a un.
Le crit`ere pour couper l’arbre de donn´ees peut ˆetre la hauteur de sous-arbres,
la distance minimale entres les grappes ou l’inconsistance maximales d’un sous-arbre.

17