Institut de la Francophonie
pour l’Informatique

Laboratoire Lorrain de Recherche en
Informatique et ses Applications

RAPPORT DE STAGE DE FIN D’ETUDES
Sujet :

Binarisation d’images
de documents graphiques

Etudiante :

Responsable :

NGUYEN Thi Oanh

Salvatore TABBONE

Promotion 8, IFI

Maître de conférences à Université de Nancy 2

Hanoi, Vietnam

Chercheur à l’équipe QGAR, INRIA Lorraine
Nancy, France

Nancy, juin - novembre 2004

REMERCIEMENTS

Je tiens tout d’abord à exprimer toutes mes reconnaissances sincères à Madame
Hélène Kirchner, Directrice du LORIA (Laboratoire Lorrain de Recherche en Informatique
et ses Applications) et de l’INRIA Lorraine, pour m’avoir accueillie chaleureusement au
sein de son laboratoire, et à Monsieur Karl Tombre, responsable de l’équipe QGAR
(Querying Graphics through Analysis and Recognition), qui m’a reçue dans son équipe de
recherche et m’a donné des conditions favorables pour travailler.
Je tiens à remercier profondément mon responsable, Monsieur Salvatore Tabbone,
professeur associé à l’Université de Nancy 2, chercheur au LORIA, qui a accepté de
diriger mon stage de fin d’études, a aussi consacré beaucoup de temps pour m’aider lors
de mon stage.
Je voudrais remercier particulièrement tous les professeurs à l’Institut de la
Francophonie pour l’Informatique (IFI) pour leur soutien, ce qui m'a permis de pouvoir
bien effectuer mon stage de fin d'études.
Je remercie également les membres de l’équipe QGAR qui m’ont beaucoup aidée
durant mon séjour à Nancy.
Un grand merci à tous mes amis à l’IFI et au LORIA pour leurs encouragements,
leurs aides et la sympathie qu'ils m’ont données tout au long de mon stage.
J'adresse, enfin, mes remerciements sincères à ma famille pour ses stimulations.

Page 2


RESUME

La binarisation des images a suscité beaucoup de travaux de recherche ces
dernières décennies. Cependant, il n’existe pas une solution idéale qui est affectée à
tous les différents types d’images. Durant mon stage, nous nous sommes intéressés à

définir une approche de binarisation qui s’applique à des documents graphiques. Après
avoir testé des solutions différentes, nous avons proposé une méthode de binarisation
pour l’image de documents à niveaux de gris. Cette méthode repose sur la coopération
entre une approche de seuillage global et une approche de seuillage local.
La méthode se compose de deux étapes. La technique de seuillage global est
affectée à la première étape et a pour but d’éliminer la partie du fond de l’image. La
deuxième est basée sur la segmentation hiérarchique floue de Gadi et Benslimane pour
rendre l’objet dans l’image plus net. Dans cette étape, les traitements sont effectués sur
les données des zones de tailles différentes du résultat intermédiaire en prenant le
principe de l’arbre quaternaire. La classification finale d’un pixel sera déterminée grâce à
la fonction d’agrégation à partir de ses différents degrés d’appartenance qui sont calculés
à tous les niveaux de l’arbre. La méthode proposée a donné des résultats intéressants en
appliquant sur l’ensemble des images de test. Son efficacité est démontrée par une étude
comparative avec d’autres méthodes et par des mesures de performance.
Mots clés : binarisation local adaptatif, binarisation coopérative, image de
documents, arbre quaternaire, sous-ensembles flous, fonction d’appartenance.

Page 3


ABSTRACT

Binarization of the images has been a subject of an intense research interest for a
long time. However, there is not a perfect solution, which can apply for all the various
kinds of images. Therefore, during my training course, we define a method working
effectively on image of graphic documents. After testing different solutions, we propose a
binarization method for the gray level image of documents. This method is considered to
be the cooperation between a global and a local thresholding technique.
The method presented is based on two stages. The global thresholding is used in
the first stage to give a preliminary result. Then, a second based on the fuzzy hierarchical

segmentation refines the result by analyzing local characteristics. In this stage, the
treatments are carried out on the data zones with different sizes by taking the quadtree
principle on the preliminary result. The classification of a pixel depends on its final degree
of membership calculated from its various degrees determined by the node local
information at all quadtree levels.
The method suggested gives remarkable results by applying it to a set of images
that be used tested. Its effectiveness is shown in comparing with other methods.
Keywords: adaptive local thresholding, cooperative binarization, document image,
quadtree, fuzzy set, membership function.

Page 4


TABLE DE MATIERES
REMERCIEMENTS....................................................................................................................2
RESUME.....................................................................................................................................3
ABSTRACT ................................................................................................................................4
LISTE DE FIGURES...................................................................................................................6
LISTE DE TABLEAUX ...............................................................................................................6
CHAPITRE 1 : INTRODUCTION ...............................................................................................7
1.1. PROBLEMATIQUE ...............................................................................................................7
1.2. OBJECTIF ...........................................................................................................................8
1.3. STRUCTURE DU RAPPORT ..................................................................................................8
1.4. LIEU DE STAGE ...................................................................................................................8
CHAPITRE 2 : ETAT DE L’ART ................................................................................................9
2.1. GENERALITE ......................................................................................................................9
2.1.1. Segmentation ............................................................................................................9
2.1.2. Binarisation ...............................................................................................................9
2.1.3. Sous-ensemble flou ................................................................................................11
2.2. METHODES DE SEUILLAGE GLOBAL ................................................................................... 13

2.2.1. Méthode de Otsu ....................................................................................................14
2.2.2. Méthodes se basant sur l’entropie .........................................................................15
2.3. SEGMENTATION HIERARCHIQUE FLOUE............................................................................. 17
CHAPITRE 3 : METHODE PROPOSEE..................................................................................20
3.1. PRINCIPE DE LA METHODE ................................................................................................ 20
3.2. ETAPE DE SEUILLAGE GLOBAL .......................................................................................... 20
3.3. ETAPE DE RAFFINAGE ...................................................................................................... 21
3.3.1. Construction de l’arbre quaternaire ........................................................................22
3.3.2. Calcul des degrés d'appartenance de chaque pixel ..............................................25
3.3.3. Décision de degré d'appartenance final .................................................................26
CHAPITRE 4 : EVALUAT IONS ...............................................................................................28
4.1. RESULTATS EXPERIMENTAUX ........................................................................................... 28
4.2. MESURES DE PERFORMANCE ........................................................................................... 34
4.2.1. Mesure de contraste...............................................................................................34
4.2.2. Mesure d’homogénéité ...........................................................................................35
4.3. AVANTAGES ET INCONVENIENTS ....................................................................................... 35
CHAPITRE 5 : CONCLUSIONS ..............................................................................................37
REFERENCES..........................................................................................................................38

Page 5


LISTE DE FIGURES
Figure 2.1 : Fonction d’appartenance linéaire .....................................................................13
Figure 2.2 : Fonction S de Zadeh........................................................................................13
Figure 2.3 : Un problème de la méthode de Gadi et Benslimane.......................................18
Figure 2.4 : Le résultat de la méthode [Gadi,2000] avec h = min(…).................................19
Figure 3.1 : Principe de la méthode proposée ....................................................................20
Figure 3.2 : Image originale – jaures_patie1.tif...................................................................21
Figure 3.3 : Image intermédiaire de jaures_patie1.tif..........................................................21

Figure 3.4 : Image binaire de jaures_patie1.tif après la première étape ............................21
Figure 3.5 : Structure tridimensionnelle de l’arbre quaternaire...........................................23
Figure 3.6 : Quadrillage de l’image intermédiaire ...............................................................25
Figure 3.7 : Résultat final de la méthode proposée sur l’image jaures_partie1.tif .............27
Figure 4.1 : Image originale jaures.tif .................................................................................28
Figure 4.2 : Image originale harchure.tif..............................................................................28
Figure 4.3 : Image originale plan2.tif ...................................................................................28
Figure 4.4 : Image originale extraire_1.tif ............................................................................28
Figure 4.5 : Résultats de l’image jaures.tif en appliquant : a) la méthode proposée ; b) la
méthode de Cheng et Chen ; c) la méthode de Gadi et Benslimane ..........................30
Figure 4.6 : Résultats de l’image harchure.tif en appliquant : a) la méthode proposée ; b)
la méthode de Cheng et Chen ; c) la méthode de Gadi et Benslimane ......................31
Figure 4.7 : Résultats de l’image plan2.tif en appliquant : .................................................32
Figure 4.8 : Résultats de l’image extrait_1.tif en appliquant : a) la méthode proposée ; b)
la méthode de Cheng et Chen ; c) la méthode de Gadi et Benslimane ......................33

LISTE DE TABLEAUX
Tableau 4.1 : Performances quantitatives ...........................................................................35
Tableau 4.2 : Comparaison du temps de calculs................................................................36

Page 6


CHAPITRE 1 : INTRODUCTION
1.1. Problématique
Au sein de développements forts de la science, on ne peut pas nier le rôle de
l’image numérique, un support important des applications dans de très nombreux
domaines tels que la médecine, le multimédia, la robotique... Parmi une série d’opérations
effectuées sur les images, le traitement d’images est considéré comme une étape de
base et indispensable dans toutes ces applications et a suscité de nombreuses

recherches. Il peut être vu comme préalable à la reconnaissance de formes, à l’analyse
de scènes, à l’intelligence artificielle... La segmentation, un traitement de base ayant pour
but de partitionner l’image en des régions homogènes qui représentent normalement les
objets, est un problème classique mais très considéré. C’est évident qu’il n’existe pas
toujours une solution idéale pour tous les cas. Plusieurs solutions ont été proposées pour
résoudre ce problème de segmentation d’images du plus général au plus particulier.
Cependant, chaque méthode a ses avantages et ses inconvénients tels que la
manipulation des paramètres [Trier,1995a], la complexité de calcul [Cheng,1999b]
[Tao,2003].
Problème
Dans l’analyse d’images de documents et la reconnaissance de symboles, la
binarisation est toujours une des premières étapes utilisées avant l’étape de
reconnaissance. Elle a donc une grande influence sur la performance des étapes
suivantes et sur le résultat final. C’est une technique importante dans les applications de
traitement d’images.
Une image de documents graphiques contient généralement du graphique mais
également du texte qui sont quelques fois assez proches. Le texte risque donc de
fusionner des différentes parties du graphique à cause du changement faible d’intensité
des pixels du fond et ceux de l’objet. Recherchant des solutions pour l’image de
documents graphiques, nous essayons de trouver une méthode automatique de
binarisation simple et efficace qui sépare le fond et l’objet dans des images aux niveaux
de gris.
Remarque
Travaillant avec l’image de documents graphiques, nous supposons toujours que
l’image contient l’objet noir (des lignes, des textes) sur le fond blanc.

Page 7


1.2. Objectif

Ce stage se situe dans la problématique de la segmentation d’images et de
chercher une méthode simple mais efficace pour l’image de documents graphiques afin
de séparer clairement le fond et l’objet. Autrement dit, il s’agit de trouver une méthode de
binarisation qui peut déterminer automatiquement et efficacement le seuil pour chaque
point de l’image.

1.3. Structure du rapport
Mon rapport se compose de cinq parties. Quelques mots d’introduction de mon
stage sont dans la première partie. La deuxième est consacrée à une présentation
générale des techniques de segmentation d’images surtout la binarisation. Des brèves
descriptions de quelques méthodes y sont aussi présentées. La troisième partie est
dédiée à la description détaillée de la méthode proposée. L’analyse de résultats et les
mesures d’évaluations sont abordées dans la quatrième. Ce rapport se termine par la
conclusion (cinquième partie).

1.4. Lieu de stage
Laboratoire
Le LORIA (Laboratoire Lorraine de Recherche en Informatique et ses Applications)
est une Unité Mixte de Recherche - UMR7503 – constituée par plusieurs établissements :
Centre National de Recherche Scientifique (CNRS), Institut National Polytechnique de
Lorraine (INPL), Institut National de Recherche en Informatique et en Automatique
(INRIA), Université Henri Poincaré Nancy 1 (UPH), Université Nancy 2.
Equipe
Mon stage, qui a duré six mois, s’est déroulé au sein de l’équipe QGAR (Querying
Graphics through Analysis and Recognition) de l’INRIA lorraine sous la responsabilité de
Salvatore Tabbone (Maître de conférences à l’université de Nancy 2). C’est une équipe
spécialisée dans l’analyse de documents à forte composante graphique. Les objectifs
sont l’indexation et la recherche d’informations dans le contexte de la documentation
technique.
Le site vous fournira des informations plus détaillées sur le

laboratoire. La présentation plus détaillée de l’équipe se trouve dans les sites webs
et />
Page 8


CHAPITRE 2 : ETAT DE L’ART
2.1. Généralité
2.1.1. Segmentation
La segmentation, un traitement essentiel des images, consiste à créer une partition
de l’image en des sous-ensembles appelés régions Ri. Une région est un ensemble de
pixels qui possèdent des propriétés communes telles que l’intensité, la texture, etc. Le but
de la segmentation est d’extraire de l’image originale un certain nombre d’entités
différentes appelées objets ou régions. Comme c’est extrêmement difficile d’avoir un
algorithme idéal qui fonctionne correctement dans tous les cas, des nombreuses
méthodes sont proposées. En bref, on peut les classifier en deux grandes approches,
l’approche « frontière » et l’approche « région » [Horaud,1993].
La première, l’approche « frontière », est basée sur la forte variation d’intensité ou
sur la discontinuité des propriétés de deux ensembles connexes de points. Elle regroupe
les techniques de détections de contours. En général, cette approche ne conduit pas
directement à une segmentation de l’image à cause de la continuité rare des contours. Il
faut donc procéder à une fermeture de contours si on souhaite une partition complète de
l’image. Les régions sont définies comme l’intérieur d’une ligne fermée.
Par contre, des méthodes appartenant à l’approche « région » sont construites
grâce à la similarité des points en évaluant des critères prédéfinis pour les regrouper
directement en régions. Le seuillage, la croissance de région, la division-fusion sont des
exemples de méthodes différentes de segmentation région.
Il existe également des méthodes qui se basent à la fois sur les propriétés des
frontières et sur les propriétés de la région, on les appelle approche collaboration
« région-frontière ».
Pour des images de documents graphiques, la valeur d’intensité des pixels

appartenant à l’objet est assez différente de la valeur d’intensité des pixels appartenant
au fond. Donc, la technique de seuillage est devenue un outil simple mais efficace dans
les applications de traitement d’images de documents. Il a attiré de nombreuses
recherches ayant pour but de trouver un algorithme qui optimise le seuil tels que les
approches dans [Otsu, 1978] [Trier, 1995a] [Cheng,1999b] [Cheriet,1998]…

2.1.2. Binarisation
Définition : la binarisation (le seuillage) est la technique de classification la plus
simple où les pixels de l’image sont partagés par un seul seuil s en deux classes : ceux
qui appartiennent au fond et ceux qui appartiennent à la scène (l’objet). L’image est alors

Page 9


séparée en deux classes de façon à ce que l’information comprise entre 0 et s est retenue
et l’autre non, ou vice-versa.
Soit l’image I (M x N), supposons que f(x, y) représente le niveau de gris du pixel
aux coordonnées (x, y), 0 ≤ x ≤ M ,0 ≤ y ≤ N et s est le seuil choisi, les pixels de l’objet
sont ceux ayant le niveau de gris inférieur à s et les autres ayant le niveau de gris
supérieur à s sont des pixel du fond. Alors, l’image binarisée G est déterminée par les
pixels (x, y) dont la valeur est :

1 si
g ( x, y) = 
0 si

f ( x, y ) > s
f ( x, y ) ≤ s

Selon [Horaud,1993], il existe trois grandes techniques de sélection du seuil s :

global, local et dynamique. Comme il y a des différentes façons de déterminer le seuil s, il
peut être considéré comme une fonction sous forme de s = t (( x, y ), p( x, y ), f ( x, y )) où
p(x, y) représente des propriétés locales du point (x, y). Si s ne dépend de que la valeur
f(x, y) du point, le seuil est global, s’il dépend en plus de p(x, y), s est un seuil local. Et si
s dépend à la fois de (x, y), de p(x, y) et de f(x, y), on dit le seuil dynamique ou bien
adaptatif.
Dans la méthode de binarisation globale un seuil unique est calculé à partir d’une
mesure globale sur toute l’image. Il nous permet de décider l’appartenance d’un pixel à
l’objet ou au fond. Les méthodes de Otsu [Otsu,1978], de Kapur [Kapur,1985], de Pun
[Pun,1980], ou de Cheng et Chen [Cheng, 1998b] peuvent être tenues comme des
représentants de cette approche. Chacun a de différentes stratégies pour atteindre leur
but. Par exemple, la méthode décrite dans [Otsu,1978] essaie de maximiser la variance
entre deux classes, tandis que d’autres méthodes dans [Kapur,1985] [Pun,1980]
[Cheng,1998b] [ Mello,2000] se basent sur la théorie de maximum d’entropie ou
d’entropie floue.
Pour la binarisation locale, la classification d’un pixel dépend non seulement du
pixel soi-même mais aussi de ses informations locales. Dans [Cheng,1999b], c’est la
moyenne des pixels du voisinage qui est prise en compte lorsqu’on construit
l’histogramme de deux dimensions. Dans [Cheng,1998a], les informations locales sont
inclues dans le homogramme qui indique le degré d’homogénéité correspondant à
chaque niveau de gris dans l’image. La détermination du seuil se base sur cet
homogramme. Sachant l’importance des informations du voisinage pour la classification,
Sue Wu et Adnan Amin [Wu,2003] proposent une méthode de seuillage en deux étapes
pour l’image de documents. Après l’étape de seuillage global sur l’image entière, le
seuillage sur des sous-images qui contiennent des composants connectées est effectué.
La méthode donne de bons résultats sur l’ensemble des images d’enveloppe postale.

Page 10



La méthode de Trier et Taxt [Trier,1995a] et celle de Gadi et Benslimane
[Gadi,2000] peuvent être considérées comme deux exemples de technique de seuillage
locale adaptative. Dans [Trier,1995a], les auteurs ont appliqué des modifications sur la
méthode de White & Rohrer afin d’obtenir une bonne méthode de binarisation pour
l’image de documents. Une de leurs modifications est la façon de classifier des pixels ‘0’
dans l’image d’étiquettes à trois niveaux ‘+’, ‘-‘, ‘0’ qui est le résultat de l’opérateur
gradient. Le pixel étiqueté ’0’ sera classé dans la classe à la quelle la majorité de ses 8
pixels voisins appartiennent. Avec cette méthode, on peut obtenir des résultats
satisfaisants en essayant des différentes solutions des paramètres. Cependant, c’est la
difficulté de la manipulation de nombreux paramètres qui cause un grand inconvénient de
cette approche. Dans [Gadi,2000], a
l classification d’un pixel dépend de ses degrés
d’appartenance calculés dans des régions locales qui sont créées par le découpage de
l’image originale selon le principe de l’arbre quaternaire. En principe, il nous fournira un
résultat intéressant sur l’image de documents graphiques si il n’y a pas de problème de
sur-découpage.
Comme les informations spatiales et les informations du voisinage des points ne
sont pas prises en considération dans l’approche globale, cette approche possède un
avantage sur le temps d’exécution mais elle n’est appropriée qu’à des images simples.
Pour d’autres images, les deux approches locales sont toujours appréciées. Elles donnent
généralement de meilleurs résultats que l’approche globale mais au prix de la complexité.
Dans deux parties ci-dessous, des descriptions courtes des méthodes qui sont
abordées dans le chapitre trois sont présentées.

2.1.3. Sous-ensemble flou
Généralité
Dans la vie quotidienne, nous nous trouvons dans de nombreuses situations où les
informations dont nous disposons sont imprécises ou bien incertaines. Le sens des mots
dans la langue est un exemple : des mots tel que « cher » « pas trop cher » « tôt »
« tard » « possible »... ne donnent pas des informations exactes. L’être humain est

habitué à ces informations. Chacun analyse donc le contexte et prend sa propre décision.
Le monde scientifique n’est pas exceptionnel, plusieurs problèmes doivent travailler
sur les données incertaines, incomplètes tels que le système d’exploitation de bases de
connaissances, le système d’aide à la décision… Dans ces cas, ces types d’informations
sont représentés et traités grâce à la logique floue dont la théorie des sous-ensembles
flous.
Soit Ω un ensemble de n éléments, Ω = {x1 , x2 ,...., x n }. Supposons qu’on a besoin
de chercher des éléments satisfaisant une propriété quelconque α. L’ensemble Ω se
divise en deux sous-ensembles A et B. A contient des éléments possédant α, tant dis que
Page 11


les autres appartiennent au sous-ensemble B, le complément de A dans Ω. En vue de la
logique classique, un élément n’appartient à qu’un sous-ensemble, A ou B. Ça veut dire
qu’un élément n’a que deux possibilités, soit il a cette propriété, soit il ne la possède pas
absolument. Cependant, il est possible qu’il existe dans Ω des éléments qu’on ne sait pas
toujours s’ils satisfont α ou qu’ils ne la possèdent qu’avec un certain degré. Dans ce cas,
il vaut mieux prendre le sous-ensemble flou pour représenter ces informations.
Sous-ensemble flou :
Un sous-ensemble flou A de l’espace observée Ω est caractérisé par une fonction
d’appartenance µ A (x ) qui associent un élément x de Ω avec un nombre réel, µ A (x ) ,
dans l’intervalle [0, 1] et qui quantifie le degré d’appartenance de l’élément x au sousensemble A. Généralement, un sous-ensemble flou est définit comme une collection des
pairs en ordre ( µ A (x ) , x).

µ (x )
A =  A i x , i = 1, n 

i

Fonction d’appartenance :


µ A : x ∈ Ω → µ A ( x) ∈ [0,1]
Chaque élément dans un sous-ensemble A possède un degré qui estime dans
quelle mesure l’appartenance de l’élément dans le A. Ce degré est déterminé par la
fonction d’appartenance. Il existe des différentes fonctions. La plus simple est la fonction
linéaire :

0
x≤ a

x − a
µ A ( x) = 
c−a a< x
1
x≥c

et celle qui est la plus connue et la plus utilisée est la fonction S de Zadeh :

0

  x − a 2

 2
  c− a 
µ A ( x) = S Z ( x) = 
2
1 − 2 x − c 

c −a


1

x≤ a
a< x≤b
b< x≤c
x>c

où (a, c) la région floue, b un point au milieu de a et c, b = (a+c) /2.
La sélection de la fonction d’appartenance dépend de chaque application.

Page 12


S

1

0

x
a

c

Figure 2.1 : Fonction d’appartenance linéaire

S
1

0.5

0

x
a

b

c

Figure 2.2 : Fonction S de Zadeh

Application dans la binarisation d’images
Pour le seuillage des images, le but principal est d’obtenir deux classes « blanc » et
« noir » à partir de l’image originale à niveaux de gris. Cependant, il n’y aucune assurance
pour une classification grâce à un seuil quelconque. La question se pose toujours si un
point est vraiment « noir » ou « blanc » ? La théorie de sous-ensembles flous est devenue
une solution. En définissant un intervalle flou, la fonction d’appartenance nous permet
d’obtenir deux sous ensembles flous représentant le « noir » et le « blanc » de l’image.

2.2. Méthodes de seuillage global
Le seuillage global consiste à partitionner l’image en deux classes grâce à un seuil
optimal qui est calculé à partir d’une mesure globale sur toute l’image. L’histogramme est
une mesure utilisée le plus souvent dans les méthodes de seuillage. Dans ce cas, le seuil
attendu est celui qui correspond à la vallée de l’histogramme, celui qui distingue le plus
possible les deux classes : fond et objet.

Page 13

Histogramme
Définition : On définit l’histogramme des niveaux de gris d’une image comme étant

la fonction h : [0...L −1] → Ν qui associe à chaque niveau de gris entre 0 et L-1 la quantité
de pixels de l’image qui possèdent cette intensité lumineuse [Braviano,1995].
L’histogramme d’une image peut être représenté par un vecteur dont chaque
composante est un nombre de pixels de niveau de gris correspondant à son indice. Il
permet de fournir effectivement une estimation de la densité de probabilité des valeurs
des pixels sur l’image observée.

h (i ) = ni , i = 0, L − 1 , où ni le nombre de pixels de niveau de gris i dans l’image.

2.2.1. Méthode de Otsu
Le principe de la méthode de Otsu est de trouver un seuil optimal qui maximise la
différence entre deux classes. Il est effectué en se basant sur la variance. Le seuil optimal
s optimal est celui qui maximise une des fonctions suivantes :

δ B2 (t )
δ W2 (t )

λ (t) =

η (t ) =

δ B2 (t )
δ T2

Si l’on choisit η (t ) , alors

k (t) =

δ T2 (t )
δW2 (t )

soptimal = arg max η (t )
t ∈[min, max ]

Où δ , δ , δ sont successivement la variance totale de l’image, la variance inter2
T

T
B

2
W

classes (between-class variance) et la variance intra-classes (within-class variance).

δ B2 (t ) = δ T2 (t ) − δ W2 ( t )

δ T (t ) =
2

max

∑ ( i − mT ) ,
2

i = min

mT =

max

∑i* p

: la moyenne totale de tous les points
i

i = min

dans l’image

2
δ B2 (t ) = Pfond ( t ) * δ 2fond (t ) − Pobjet (t ) * δ objet
(t )

Où :
•

pi : la probabilité d’occurrence du niveau de gris i dans l’image

pi =

nombre de pixels dont le niveau de gris = i
h(i )
=
nombre de pixels dans l ' image
M *N

• Pfond (t ), Pobjet (t ) : la somme des probabilités d’occurrence des niveaux de gris
des pixels du fond et celle de l’objet en prenant le seuil t.

Pobjet ( t ) =

t

∑ p ,P
i

fond

(t) =

i = min

•

max

∑p

i

= 1 − Pobjet ( t )

i =t +1

m fond , m objet : la moyenne des pixels appartenant au fond et celle des pixels

de l’objet.
Page 14


t

m objet (t ) =
•

∑i* p

i = min

max

i

Pobjet

, m fond ( t ) =

∑i* p

i = t +1

i

Pfond

2

δ 2fond (t ), δ objet
(t ) : la variance de la classe fond et la variance de la class

objet.
t

2
δ objet
(t ) =

•

∑ (i − m

i = min

max

objet

) 2 * pi

Pobjet

, δ 2fond ( t ) =

∑ (i − m

i = t +1

fond

)2 * p i

Pfond

[min, max] est l’intervalle dynamique de l’image.

Cette méthode est simple à implanter et donne de bons résultats en général.
Cependant, dans les cas des images de documents, les résultats ne sont pas nets, deux
différents objets peuvent être confondus.

2.2.2. Méthodes se basant sur l’entropie
Selon la théorie de l’information, l’entropie est une mesure de quantité d’information

d’un système. Soit un ensemble fini S = {s1 , s 2 ,..., s k } d’événements indépendants, et pi la
probabilité d’occurrence de chaque élément s i, l’entropie est définie par :
k

H ( p1, p2 ,..., pk ) = − ∑ pi * log pi
i =1

N

où

∑p

i

=1

i =1

Plus l’entropie est grande, plus on obtient des informations. Plusieurs méthodes de
segmentation d’images l’ont utilisée dans le but de maximiser la qualité de l’information
obtenue du résultat final. [Pun,1980]

[Kapur,1985] [Cheng,1998b] [Mello,2000]

[Braviano,1995].
Si l’ensemble S est considéré comme un ensemble flou avec le degré
d’appartenance correspondant à chaque élément dans S µ S ( si ), i = 1, k , appelé la
fonction d’appartenance (membership function), l’entropie floue de l’ensemble S est
définie par :
k

H floue ( S ) = ∑ µ S ( s i ) * pi * log pi
i =1

où 0 ≤ µ S ( si ) ≤ 1
Principe :
Le principe de ces méthodes est de chercher une partition de l’image dont l’entropie
est la plus grande. De nombreuses méthodes sont proposées en se basant sur des
variations de l’entropie d’une partition. On va voir ci-dessous trois exemples dans le cas
de binarisation.
Page 15


Méthode de Pun :

Le seuil est choisi tel que la fonction H = H objet + H fond est maximale.

soptimal

= max (H
t

objet

+ H fond

L−1

) = max (−∑ p * log p − ∑ p * log p )
t

i

t

i

i= 0

i

i

i = t +1

où p i est la probabilité d’occurrence du niveau de gris i dans l’image.
Méthode de Kapur :

soptimal = max (H objet + H fond ) = max ( − ∑
t

t

t

i =0

L−1
pi
p
p
pi
* log i − ∑ i * log
)
Pt
Pt i= t+11 − Pt
1 − Pt

t

où

Pt = ∑ pi
i= 0

Dans ce cas, la distribution de probabilité de l’objet Pt et la distribution de probabilité
du fond (1 - Pt ) sont prises en compte en déterminant l’entropie de la partition.
Méthode de Cheng et Chen [Cheng,1998b]:
Différant de ces deux méthodes précédentes, l’entropie d’une partition est calculée
en prenant des probabilités d’occurrence de sous-ensembles (objet et fond). La théorie de
sous-ensembles flous est comptée de plus dans son calcul. Alors, dans ce cas, l’entropie
d’une partition est :
2

H = − ∑ P( Ai ) * log P( Ai ) = − ( PObjet * log PObjet + Pfond * log Pfond )
i =1

L −1

où

PObjet = ∑ µ objet ( i ) * p i ,
i= 0

et

L −1

Pfond = ∑ µ fond ( i ) * pi
i =0

µ objet / fond (i ) est toujours la fonction d’appartenance du niveau de gris i à la

classe objet / fond.
Méthode de Mello et Lins [Mello,2000] :

C’est une méthode qui se spécialise pour l’image de documents historiques.
Supposons que t soit la couleur apparaissant le plus souvent dans l’image. Prenons
cette valeur comme le seuil initial de l’image, les valeurs d’entropie de l’objet Hb et du
fond Hw sont déterminées comme dans [Pun,1980]. Un pixel i dont la couleur est
couleur(i) sera classé comme le fond si :

couleur (i ) / 256 ≥ (mw * Hw + mb * Hb ) s inon il sera classé comme l’objet.
Les deux facteurs mw et mb sont déterminés par expériences en évaluant l’entropie
de l’image entière et dédiés particulièrement à un type d’images observé.

Page 16


2.3. Segmentation hiérarchique floue
Décrite dans [Gadi,2000], cette méthode est comme une représentante de
l’approche locale adaptative. Elle est basée sur un principe hiérarchique pour résoudre le
problème d’éclairage non uniforme. Sous l’hypothèse que l’image ne contient que deux
classes : l’objet et le fond, le principe de cette méthode est de récupérer le plus possible
des pixels à la classe objet.
La méthode se compose de 2 étapes :
♦ Fuzzification :
-

Construction

de

l’arbre

quaternaire :

l’image

originale

est

divisée

consécutivement en quatre sous images de taille de plus en plus petite en
évaluant le critère d’homogénéité. Chaque sous-image est associée à un
nœud de l’arbre quaternaire. Si une sous-image satisfait le critère
d’homogénéité, la division n’est plus nécessaire, elle devient un nœud
terminal dans l’arbre. Au cas contraire, cette sous-image est décomposée en
quatre. Le processus continue jusqu’à ce que tous les nœuds dans l’arbre
soient des terminaux.
La condition pour que le critère d’homogénéité soit satisfait sur une région,
c’est qu’il n’y a plus de « différence significative » entre cette région et ses
quatre filles. Cette condition est vérifiée par le test statistique de Fisher.

f ≤ F3α;4 (k −1) : sous-image est homogène
f > F3α;4( k −1) : sous-image est non homogène
f : l’estimation du critère d’homogénéité sur la sous-image évaluée (voir
partie 3.3 pour plus détaillé)

F3α; 4( k −1) : la valeur prédéfinie de la distribution F avec 3 et 4(k-1) degrés de
liberté.
-

Calcul des degrés d’appartenance : Les degrés d’appartenance de tous les

pixels sont calculés à chaque niveau de l’arbre.

µ (kx , y ) = S (( x , y ); moyenne − ecart _ type, moyenne, moyenne + ecart _ type )
où la moyenne et l’écart type sont déterminés dans la région contenant pixel
(x, y) au niveau k.
♦ Défuzzification :
-

Décision : Après avoir fait des différentes évaluations de l’appartenance de
chaque pixel à une des deux classes, la fonction d’agrégation t-conorme de
Zadeh est affectée à la détermination de la mesure d’appartenance finale à
la classe objet.
Page 17


(

µ Of ( x, y ) = h µ O0 ( x, y ), µ 1O ( x, y ),..., µ Ol −1 ( x , y )

(

)

= max µ O0 ( x, y ), µ 1O ( x, y ),..., µ Ol −1 ( x , y )

)

et le degré d’appartenance final au fond :

µ Ff ( x , y ) = 1 − µ Of ( x, y )

-

Défuzzification : il s’agit de mettre au point des pixels à deux classes.

µ Of ( x , y ) > µ Ff ( x, y ) ⇒ ( x , y ) ∈ classe objet
µ Of ( x , y ) ≤ µ Ff ( x, y ) ⇒ ( x , y ) ∈ classe fond
Evaluations :
Cette méthode est proposée pour résoudre le problème d’éclairage non uniforme
sur l’image. Mais elle ne fonctionne bien que sur l’image dont le fond est vraiment
uniforme. Au cas contraire, des pixels du fond sont mis facilement à l’objet.
Un autre problème réside au problème de découpage. En fait, le test statistique est
très sensible aux bruits, alors l’image est trop découpée. De plus, la fonction max utilisée
dans la partie de défuzzification accentue les bruits. En conséquence, les faux pixels sont
classés facilement comme les pixels de l’objet. L’affectation de cette méthode à l’image
jaures_partie1.tif (figure 3.2) donne un résultat inattendu (figure 2.3).

a) Le découpage

b) L’image binarisée, avec h = max(…)

Figure 2.3 : Un problème de la méthode de Gadi et Benslimane.

En considérant des images de documents graphiques, on constate que s’il n’y pas
de grande variation d’intensité des pixels appartenant à l’objet et pour diminuer l’effet
négatif du découpage, l’opérateur d’agrégation min(…) est plus convenable que
l’opérateur max (figure 2.4). Alors, quand on fait des tests sur l’image de documents,
l’opérateur d’agrégation min est pris au lieu de max à l’étape de décision.

Page 18

Figure 2.4 : Le résultat de la méthode [Gadi,2000] avec h = min(…)

Page 19


CHAPITRE 3 : METHODE PROPOSEE
3.1. Principe de la méthode
L’histogramme de l’image de document contient deux modes : une forte
correspondant au fond et une faible correspondant à l’objet. Cependant ce qui est
important est celui de l’objet. Une méthode de seuillage global peut éliminer facilement la
mode du fond mais cela ne veut pas dire qu’on a bien obtenu l’objet qui se compose de
lignes et aussi de caractères. La frontière entre l’objet et le fond n’est pas toujours claire
surtout dans les zones où les caractères et les lignes sont proches. Donc, obtenir l’objet
dont les composants sont clairs et nets est le but final de notre méthode.
La méthode proposée peut être considérée comme la combinaison de l’approche
globale et l’approche locale. Elle se compose de deux étapes. Utilisant la technique de
seuillage global, la première étape a pour but d’éliminer la plupart du fond qui domine
l’image observée et de garder la partie importante contenant l’objet. La deuxième étape
consiste à raffiner le résultat de l’étape précédente pour rendre l’objet plus net. Une
variation de la méthode de binarisation locale adaptative [Gadi,2000] est appliquée dans
cette étape.

Image originale
I

Seuillage global

Image intermédiaire
II

Binarisation
locale adaptative

Résultat final
IF

Figure 3.1 : Principe de la méthode proposée

Dans les parties ci-dessous, on va prendre ces notations suivantes :
g(x, y) : le niveau de gris du pixel (x, y) de l’image originale I.
gI (x, y) : le niveau de gris du pixel (x, y) de l’image intermédiaire II .
gF(x, y) : le niveau de gris du pixel (x, y) du résultat final IF.

3.2. Etape de seuillage global
Une méthode de seuillage global nous aide à chercher un seuil pour toute l’image.
En principe, n’importe quelle méthode de seuillage globale peut être appliquée à cette
étape. Toutefois, une méthode simple est toujours une bonne sélection à priori. Alors,
dans ce cas, nous avons choisi la méthode de Otsu comme une solution possible.
Page 20


soptimal

δ B2 ( t )
= arg max η ( t ) =
δ T2
t∈[min,max ]

Au lieu de mettre le résultat de cette étape comme une image noire et blanche, on
va garder la valeur originale des pixels appartenant à l’objet pour obtenir une image

intermédiaire. Si gI (x, y) est l’intensité lumineuse du pixel (x, y) de cette image, alors :

si
 255
g I (x , y ) = 
 g ( x, y) si

Figure 3.2 : Image originale – jaures_patie1.tif

g ( x, y ) > T
g ( x, y ) ≤ T

Figure 3.3 : Image intermédiaire de
jaures_patie1.tif

Figure 3.4 : Image binaire de jaures_patie1.tif après la première étape

3.3. Etape de raffinage
L'image obtenue après la première étape a bien gardé la partie qui nous intéresse.
Cependant, l'objet n'est pas vraiment net, les parties différentes de l'objet ne sont pas
clairement distinguées car une minorité des pixels qui aurait dû appartenir au fond sont
Page 21


attribués à l'objet. En général, ce sont des pixels aux frontières objet-fond. C'est pourquoi
on a besoin d'un autre traitement pour éliminer ces pixels. Dans cette deuxième étape,
l'opération n'est effectuée que sur l'objet obtenu à partir de la première étape, c.à.d, on
manipule sur l'image intermédiaire I I mais sans compter les pixels du fond (ceux dont le
niveau de gris est égal à 255).
Si l'on essaie de chercher un seuil à effectuer globalement sur II , il risque de perdre

des parties de l'objet dont les intensités sont moins fortes que ceux des autres. Cela vient
du fait que l’illumination n’est pas le forcément constante sur l’image. C'est la raison pour
laquelle on doit chercher une méthode de seuillage adaptatif qui permet de tenir compte
des informations locales pour diminuer l'effet ci-dessus. Cette méthode est basée sur le
principe de l'arbre quaternaire et la théorie de sous-ensembles flous. L'image à traiter
sera décomposée de plus en plus en sous-images de taille petite en évaluant le critère
d'homogénéité. Une image dont ce critère n’est pas satisfait sera divisée en 4 sousimages.
Le processus appliqué, afin de re-affecter un pixel qui est déjà classé comme l’objet
dans I I à la classe fond ou à la classe objet, se compose de 3 sous-étapes :
♦ Construction de l'arbre quaternaire.
♦ Calcul de degrés d'appartenance de chaque pixel à chaque niveau de l'arbre.
♦ Décision de degré final d'un pixel pour le classer au fond ou à l'objet.
Soit ORi l’ensemble des pixels portant la valeur originale d’une région rectangle (une
sous-image) quelconque Ri de l’image intermédiaire I I . On peut considérer Ri comme
un nœud de l’arbre et R0 comme la racine I I .

ORi = {( x , y ) ∈ Ri g I ( x, y ) ≠ 255}, Ri ⊂ I I
Parce qu’on ne s’intéresse que sur l’ensemble ORi , à partir de maintenant tous les
notions et les formules concernant la région Ri ne sont appliquées que sur les pixels
dans ORi .

3.3.1. Construction de l’arbre quaternaire
La hiérarchie associée à l'image I I de taille M x N est construite en divisant
successivement cette image en sous-images de taille de plus en plus petite.
-

L'image I I est pris e comme la racine de l'arbre qu'on va construire. Elle
correspondant à un noeud au niveau 0.

-

Les noeuds au niveau k sont créés par des noeuds décomposables au niveau k1. Les noeuds décomposables sont ceux qui ne satisfont pas le critère
d'homogénéité. Un noeud décomposable au niveau k est divisé en 4 noeuds au
Page 22


niveau k + 1. Ceux qui ne sont pas décomposables représentent des noeuds
terminaux (des feuilles) de l'arbre. Ce processus est répété jusqu'à ce qu’il n'y a
plus de noeuds décomposables.
Quand le processus de subdivision s'arrête, l'image originale est représentée par
des noeuds terminaux.
Niveau 0

Niveau 1

Niveau 2

Figure 3.5 : Structure tridimensionnelle de l’arbre quaternaire

Dans ce processus, on doit vérifier s'il ne faut pas continuer à découper une image
en sous-images. Mais, comment détermine- t- on le critère d’arrêt ? Evidemment, on ne
décompose jamais une région Ri dont tous les pixels sont déjà classés comme le fond,
c’est à dire que l’ensemble ORi est vide. La région Ri sera représentée par un nœud
terminal. Pour d’autres régions, la décision dépend de la relation entre la région et ses
quatre filles correspondantes. En principe, on ne découpe plus une région s'il n'y a pas de
différence significative entre la moyenne de la région mère et celles de ses quatre filles,
ainsi que entre leurs variances. Alors, on doit prédéfinir un seuil e afin de définir la
« différence significative ». Pour éviter le problème de choisir le seuil, un test statistique
de Fisher est utilisé pour vérifier le critère d'arrêt [Gadi,2000]. Ce test nous permet de
comparer les moyennes et les écarts-types entre la mère Ri et les quatre filles Ri1, Ri2, Ri3,

Ri4.

 Hypothèse null H 0

Hypothèse alternativ e H 1

σ 1 = σ 2 = σ 3 = σ 4 = σ et m1 = m 2 = m 3 = m 4 = m 


∃j ∈ {1, 2, 3, 4} σ j ≠ σ ou m j ≠ m


o
où

σ j , j ∈ {1,2,3,4} et σ

sont successivement les écarts-types calculés sur les

données de 4 filles et de la mère.

m j , j ∈ {1, 2,3, 4} et m sont les moyennes correspondantes.
σ j , m j , j ∈ {1,2,3,4} et σ , m sont calculées sur O Rij , j ∈ {1,2,3,4} et O Ri .
Page 23


Supposons que les quatre sous-images filles de l'image mère sont indépendantes et
présentent des distributions des niveaux de gris normales et identiques, le test
d'homogénéité f de Fisher a une distribution Fαp;n -p -1
4

f =

K ∑ (m j − m ) 2 / 3
j =1

4

K

∑ ∑ (X

− m j ) /( 4 * ( K − 1))

où :

2

jk

j =1 k =1

K : le nombre de pixels dans chaque sous image
Xjk : le niveau de gris du k ème pixel de la sous-image j.
p : le degré de liberté, dans ce cas, p = 3 = le nombre de sous ensemble – 1
n : le nombre total de pixels de l'image mère = 4K
α : le niveau de confiance (confidence level)
Les valeurs de la distribution F sont indiquées dans un tableau de Fisher. La
décision d'homogénéité d'une région dépend de la comparaison f et Fαp; n -p -1

f ≤ Fpα;n− p−1 : L’hypothèse H0 est « vrai ». La région est homogène.
f > F pα;n− p−1 : L’hypothèse H1 est « vrai ». La région est hétérogène.
Il est bien évident qu’un test statistique n’apporte de signification que si la taille de
l’échantillon est suffisamment grande. Il faut donc déterminer la taille minimale de
l’échantillon pour appliquer le test. Il nous aide à évite le problème de sur-découpage.
En bref, la décomposition d’une région Ri s’arrête si une des deux conditions
suivantes est satisfaite. Ri deviendra un nœud terminal.
1) Card (ORi ) ≤ taille min ou bien
α

2) Card (ORi ) > taille min & f ≤ F3;n− 2

Card (ORi ) : la cardinalité de l’ensemble ORi

taille min : la taille minimale de l’échantillon pour l’application du test statistique. La
taille requise de l’échantillon dépend de quelques paramètres du test tel que le degré de
confiance α et même la variance de l’échantillon...[NIST,ehandbook]. A l’implémentation,
nous avons choisi 40 comme une valeur expérimentale de taille min .

Page 24


Figure 3.6 : Quadrillage de l’image intermédiaire

3.3.2. Calcul des degrés d'appartenance de chaque pixel
À chaque nœud de l’arbre, si la région correspondante n’est pas homogène, la
théorie de l’ensemble flou sera appliquée pour la classification de ses données en deux
sous-ensembles flous F (fond) & O (objet) en évaluant leurs degrés d’appartenance. Cela
signifie que ces degrés d’appartenance à la classe objet µ Ok ( x, y) et à la classe fond

µ Fk ( x, y) de chaque pixel sont calculés pour chaque niveau k de l’arbre.
Etant une fonction a
l plus souvent utilisée, la fonction S de Zadeh est prise à
calculer le degré d’appartenance à la classe fond d’un pixel. Supposons que µ F ( x, y) et

µ O ( x, y) sont successivement le degré d’appartenance à la classe objet et celui à la
classe fond du pixel (x, y) ayant le niveau de gris g I ( x, y) , ils sont déterminés comme
suivant :

0

2

(g ( x, y ) − a )

 2 I
( c − a ) 
 
µ F ( x, y ) = S Z ( g I ( x , y ); a, b, c ) = 
2

1 − 2 ( g I ( x, y ) − c )

( c − a )


1

µ O ( x , y ) = Z Z ( g I ( x, y ); a , b , c ) = 1 − S Z ( g I ( x , y ); a , b , c )

g I ( x, y ) ≤ a
a < g I ( x, y ) ≤ b
b < g I ( x, y ) ≤ c
c < g I ( x, y )

b = (a + c ) / 2
Pour les estimations des paramètres a, b, c, on prend des propriétés locales des
régions (des noeuds). Sur l’intervalle dynamique de la région, l’intervalle (moyenne –
écart-type, moyenne + écart-type) est considéré comme la bande d’incertitude. Alors, le

Page 25