Segmentation hiérarchique de textures à l'aide d'une décomposition en ondelettes

différe des précedentes par le mode de caractérisation des textures et par le processus de

segmentation employé. A chaque niveau de résolution, des attributs de textuee appelésfacteezm

d e J i m e sont ddteminb en combinant les informations des diffkrents niveaux de résolution.

Une classification de type flou est ensuite effectuée au niveau de r6solution le plus Blevb (le

nombre c de classes est supposé a priori connu). Au terme de

cette étape les "meilleurs"

prototypes de chaque classe sont obtenus. On classe par la suite les pixels de l'image du niveau

de rksolution courant en réalisant une mesure de distance dans l'espace des attributs de texture.

Une image partitionnés en c classes est ainsi obtenue. Une analyse de voisinage permet de

determiner un ensemble de pixels ambigus (pixels isolks ou frontaliers). La classification de

ces pixels ambigus est reportie au niveau de résolution inf6eieur. Ce processus est itkré

jusqu'au niveau de eésolution le plus bas de la décomposition.

Nous présentons tout d'abord lefacteur de forme avant de décrire l'algorithme de segmentaiion

mis en oeuvre.

La Transformée en Ondelettes (T.O.) permet de reprksenteer une image B différents niveaux de

résolutions. E l b fournit au niveau de résolutionj :

une approximation 1-j de l'image de départ, et

a trois images de détail Dlj, D2+ D3+ privilégiant chacune une

orientation particulikre:

horizontale (indice l), verticale (indice 2), et diagonale (indice 3). Ces images renferment

les informations perdues lors du passage du niveau de résolution précédentj-l au niveauj.

La mise en oeuvre pratique de la T.O. est gbn6ralement rkalisée au moyen de deux filtres PI

(passe-bas) et G (passe-haut) conjuguks

en quadrature, domt les sorties sont sous-

6chaniillomBes (un échantillon sur deux est conservé) 133. Le filtrage réalid par ces filtres est

d'abord effectué suivant les lignes puis les colonnes de l'image. Ce qui permet d'obtenir dans un

premier temps deux sous-images inteemédiaires, puis les quatre

sous-images résultats de la

transformation. La décomposition est orthogonale, complète et s'effectue sans redondance

d'informations.

Le processus de base peut dtre appliquk de façon r6cursive

aux images d'approximation

successives. Il conduit alors i une eeprésentation hiéraeckique pyramidale de l'image originale.

• 488 -

La décomposition en ondelettes sur J niveaux d'une image originale discrète Io supposée de

niveau de résolution O, s'écrit :

Si les coefficients de l'image d'approximation I.J et de l'image de détail

d'orientation Z

(1=1,2 et 3) sont désignés respectivement par i-J,& et d-j,k, alors, le facteur de forme associé au

pixel k du niveau de résolution J e s t défini par [4]:

I

J

b - J , k ) 2 +

(d!j,,)2

FFj(k) =

j = 1 b a V j ( k )

li-J,C/

où j est l'indice de résolution et Q(k) le voisinage du pixel k correspondant au niveau de

résolutionj. Pourj fixé, Vj(k) correspond à un voisinage de taille 2J%2J-j (Figure 1).

j=J

........

....'O .... ..\

, *

~ .................... .. "1 p J-1

....... /4...

..... .\

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

j=J-Z

: Jikemple de voisinages c(k)

Il est interessant de remarquer que :

0 Le facteur de forme s'obtient par combinaison des informations des différents niveaux de

résolutions de la décomposition. Ce qui constitue la particularité de cet attribut par rapport à

ceux utilisés dans les méthodes précédentes, qui ne prennent en compte pour leurs calculs

que les informations d'un seul niveau de résolution.

0 Les différentes directions préférentielles de la T.O. permettent de calculer à chaque niveau

de résolution trois facteurs de forme. Ces facteurs de forme directionnels sont utiles pour la

discrimination des textures. Le pouvoir discriminant de ces facteurs a été éprouvé dans un

travail antérieur [4].

• 489 -

La m6thode de segmentation que nous proposons s'articule autour de trois points essentiels : la

détermination des prototypes, la segmentation primaire, et la localisation précise des contours.

Cette phase du traitement consiste h déterminer les "meilleurs" prototypes de

chaque classe.

de la pyramide de decomposition et requiert la

Elle se déroule au niveau le plus élev6

connaissance du nombre c de classes (nombre de textures prksentes dans l'image). C'est une

plnase importante puisque le choix de ces prototypes conditionnent les performances de la

segmentation.

Dans les techniques habituelles de classification, l'appartenance d'un pixel une

classe est

binaire. A In sortie de ces classifieurs, on ne dispose d'aucune mesure de degré d'appartenance

d'un pixel i une classe permettant de dire si ce pixel est ou n'est pas un bon prototype de la

classe. Les techniques de classification floue présentent l'avantage de considérer les classes

comme des ensembles flous de l'image. Ce& permet d'attribuer h un pixel donn6, un degré

d'appartenance aux différentes classes en présence. Ainsi dans une classe donnta, les pixels

ayant un degr6 d'appartenance élevé, peuvent être considirés comme les meilleurs prototypes

de la classe.

L'algorithme de classification floue que nous avons utilisé est celui des c-moyennes floues

F@M [5]. Cet algorithme prockde de façon itérative :

A chaque pixel xi est associé un vecteur d'atteibut formé des trois facteurs de fome et un

ui<'>, ...., ui<C>) où ~ i < ~ > , dCsigne le degr6 d'appartenance du

vecteur d'appartenance Q=(zt;'>,

pixel xi 21 la classe Ck, tel que :

E [O, 11

et

C

k=l

= 1

A chaque iteratîtion, le centre V , de la classe Ck, est calculBe A partir des pixels xi (avec

i=l, ...,tz) de l'image par :

où ni est un facteur de flou génhralement compris entre 1,5 et 2.

i-1

La détermination des centres des c classes permet d'actualiser le

vecteur de degré

d'appartenance associé au pixel xi. Les nouvelles composantes de ce vecteur s'obtiennent par :

L'itération est poursuivie jusqu'à ce que l'on converge vers un minimum.

A ce stade, une règle de décision (par coupe de niveaux ou par maximum d'appartenance) est

appliquée pour décider de l'appartenance d'un pixel à une classe.

Pour notre application, la détermination des meilleurs prototypes de chaque classe se fera par la

règle de décision par coupe de niveaux CL suivante :

xi estprototype de C k si ui >a avec O..5<a<l

<k>

3-2 Segmentation primaire

A l'aide des prototypes déterminés précédemment, on calcule le nouveau centre de chaque

classe. Ces centres permettent d'affecter aux différentes classes Ck, tous les pixels du niveau de

résolution courant par une mesure de distance dans l'espace des attributs.

Une analyse du voisinage de chaque pixel est ensuite effectuée afin de déterminer les pixels

ambigus. Un pixel est considéré comme ambigu, si il n'appartient pas à la même classe que la

majorité des pixels de

sont généralement

représentatifs de zones singulières ou des frontières. Leur classification est reportée à une

résolution supérieure.

son voisinage immédiat. Les pixels ambigus

Ce report permet d'analyser beaucoup plus finement les régions représentées par les pixels

ambigus. En effet, le passage d'un niveau

à celui qui lui est

immédiatement inférieur, revient à représenter selon la construction pyramidale un noeud par

ses quatre parents, et donc à scinder une région ambigüe en quatre sous-régions.

de résolution donnée

3-3 Localisation précise des contours

Au début de cette phase, on dispose : des prototypes de chaque classe, des pixels ambigus, et

d'une image résultat formée par des pixels affectés à une classe.

Seuls les pixels ambigus font l'objet d'une classification lors de cette phase. L'image résultat

obtenue est interpolée pour être ramenée au niveau de résolution inférieur. A ce niveau, les

facteurs de forme associés aux parents des pixels prototypes sont utilisés pour calculer les

• 491 -

nouveaux centres de classes. Une mesure de distance A ces centres permettent de classer les

pixels ambigus. Cette opkration permet d’affiner les contours.

Le processus est itkré jusqu’au niveau de résolution 1 sans que l’on ait i nouveau recours à

l’algorithme de classification floue pour la détermination des prototypes. A ce dernier niveau,

tous les pixels sont attribues i une classe. L’image rksultat du niveau 1 est ensuite interpol6e au

niveau O. Afin de lisser les frontières obtenus aprbs cette dernibre phase d’interpolation l’image

du niveau O est soumise Q un filtrage mkdian.

Le schkrna gkn6ral de l’algorithme est le suivant :

Etape 1. Rkalisation la dkcornposition en ondelette de l’image jusqu’au niveau de rhlution J.

Etape 2. Calcul des trois facteua de forme pour chaque niveau de rdsolution j (1 5j 2 J).

Etape 3. Au niveau de rbsolution J:

r

Classificationfloue (vecteur attribut : les trois facteurs deforme).

%le degrt d’appartenance d’un pixel à une classe q >a,

d.ms marquer ce pixel comme prototype de la classe (S.

donner à ce pixel le label de la classe q.

Iteitinlisation d e i (vanoble du niveau de résolution cowant) : j = J

Etape 4. Calcul du centre des prototypes de chaque classe au niveau j.

Etape 5. Affectation des pixels du niveau j = J ou des pixels ambigus de niveau j ;r J,

Mesure de distance d‘ut2 pixel au centre d’une classe

dam 1 ‘espace (tridimensionnel) des attributs de textzcre.

9 j = J,

pixels B coslsidiircr = pixels du niveau de rksolution j

pixels i considkrer = pixels ambigus

EQU chaque pixel à considdrer,

.Si la distance d’un pixel au centre d’une classe k est infkrieure

à la distance de ce pixel & tous les autres centres de classe,

g h s donner à ce pixel le label de la classe Ba.

Etape 6. Dktermination des pixels ambigus de l’image de rksolution courante.

Analyse du voisinage de chaque pixel de l’image de niveau de risolutionj.

Si j est diffkrent de 1,

&gus la classe du pixel consideri, n’est pas majoritaire dans le voisinage da ce pixel,

~ Q E marquer ce pixel comme ambigu.

Etape 7. Extension de l’image de niveau de rksolution j, au niveau de rksolution j-1.

chaque pixel de l’image de ekolution j,

donner à ses quatre parents l a meme Ctiquettc (classe, prototype,ambigus) que lui.

Décrhmerzter j

Etape 8. hklioration de la segmentation

Si j +O, retourner 5 I’Etape 4.

filtrer l’image du niveau O par un mCdian poue obtenir l’image segmentkc finale.

• 492 -

4 RESULTATS

La taille des images traitées est de 256x256 avec 256 niveaux de gris. La décomposition en

ondelettes a été effectuée jusqu'au niveau 5=4 qui correspond à un voisinage de taille 16x16 sur

l'image originale. L'ondelette utilisée est celle de Haar qui présente pour notre application le

double avantage d'être d'un coût faible en temps de calcul, et de conduire à un calcul des

attributs sur des régions qui ne se recouvrent pas. Ce qui implique une réduction de l'ambiguïté

sur la localisation exacte des contours. La valeur de a de l'algorithme de classification floue,

ét6 fixée i 0.96 pour l'ensemble des

qui permet de déterminer les meilleurs prototypes, a

expérimentations. L'analyse du voisinage est réalisée sur une fenêtre de taille 3x3 pour J>2 et

5x5 pour J12. Ce choix tient compte du nombre de pixels

des images des différentes

résolutions. Le filtre médian final est de taille 7x7. L'algorithme de segmentation a été implanté

enlangage C sur un micro-ordinateur de type PC, 486DX4,50 MHz.

Les résultats obtenus par l'algorithme sont satisfaisants. La figure 2 illustre les différentes

étapes de l'algorithme pour une image (figure 2.a) composée de deux textures. La classe de la

texture de gauche est dénommée classe 1.1, et celle de droite, classe 1.2. Toutes les images ont

été ramenées au niveau O pour faciliter leur lecture. On peut noter sur la figure 2.b, qui montre

le résultat de la classification floue, que très peu de pixels ne sont pas prototypes (pixels en

noir). Celà illustre le fort pouvoir discriminant du facteur

de forme. Le résultat de la

segmentation grossière est présenté B la figure 2.c. L'analyse de voisinage permet de déterminer

au niveau 1, la

les pixels ambigus (en blanc sur les figures 2.d' 2.f

localisation de la frontière des deux textures devient de plus en plus précise et il reste très peu

de pixels ambigus au niveau 1 (figure 2.h). Le résultat final de la segmentation est présenté à la

figure 2.j. On peut constater l'effet de lissage du filtre médian. Notons toutefois que bien que

utile, ce filtre introduit souvent une délocalisation légère des contours.

et 2.h). Du niveau 3

Les résultats de la segmentation de deux mosaïques de textures (figures 3.a et 4.a) sont

présentés aux figures 3.b et 4.b. La première

est constituée de pullover (classe 2.1), siège

(classe 2.2), tissu écossais (classe 2.3), et bois (classe 2.4). La seconde, des textures canevas

(classe 3.1) et (lierre 3.2) tirées de l'album de Brodatz [6].

Tous les résultats chiffrés sont indiqués dans le tableau 1.

Niveau de départ de la seginentatioion

Nombre de pixels flous

Tauxcorrectdeclassificution dela

1 Image 2

1

4

7

1 (1.1) 97.3

1 Image 2

4

14

1 (2.1) 98.6

1 Image 3

4

I

7

1 (3.1) 96.5

Durée de l'opération (s)

h

: Résultats de la segmentation des images test. La classe est indiquée entre parenthèsa

1 (2.4) 98.8

I

37

1

I

35

33.5

• 493 -

un algorithme de segmentation hiérarchique d'images

Dans cet article, nous avons dbcrit

texturies. Le processus propos8 consiste à efkctuer une segmentation grossière au niveau le

plus élevé de la dkcomposition, puis A affiner progressivement le risultat de la segmentation en

reconsidérant aux niveaux inférieurs, h classification d'un nombre n5duit de pixels. Ce procidé

amdiore les performances en temps de calcul de la segmentation. Las rksultats satisfaisants

obtenus prouvent l'efficacité du processus de clmification et la pertinence de l'attribut facteur

de forme utilis6. Le déroulement

certains rnkcanisrnes

d'analyse (dCcomposition muhicanaux) et de perception (pr6zittentive et focale) du système

visuel humain. L'évolution de l'algorithme propose vers un algorithme de segmentation nom

supervisée peut Gtre envisaghe.

de l'algorithme rappelle Cgalement

N.B. : Les pixels flous sont en noir? et les pixels ambigus en blanc.

• 494 -

NIWATT 3

NIVEAU 2

• 495 -

Fig11re 3 : Im;& originale [a], Résultat de la sepenkation [b]

: In&e originale [a], RémlIL1P de la segmentation [b]

BrnLIOG

using hiesarchical '~vavelet decomposition",

S.G.Mallat, "A theory of multiresolution signal decomposition

[Il T. Chang, C.-C. 9. Kuo, "A wavelet transfomm approach for hiemrchical texture

segmentation", Confernce Record ofThe Twenfv-sixth Asilomm 1992, Vol. 2, pp.816-820.

[2] E. Salari, Z. Ling, "Texture segmentation

Fatltern Recognitio~a 1995, Vol. 28, No. 12 pp. 18 19- 1 824.

[33

representation", IEEE T Q ~ S Patterpl Anal. ilfuchine Intell., Vol. PAMI 11, pp. 674-693, Juiy

1989.

[4] G. Loum, J.Lemoine, E. Petit, P.Provent, "An Application of Wavelet Transfom %O

Texture Analysis", 9th Conjerence on Image Analpis SCLA, Uppsala, Sweden, 6-9 Juin 1995,

pp.583-590.

[5] J.C.Bezdek, "Pattern recognition with fuq objective function algorithms",

Press, New York, 1981.

[6]

Dover, 1966.

P. Brodatz , "Textures - A Photographic Album for Artists and Designers", New York :

: the wavelet

Plenum

View publication stats

View publication stats

• 496 -