R´eseaux complexes : Nouvelle approche pourla mod´elisation et la caract´erisation de texturesThomasChalumeau1, Lucianoda F.
Costa2, OlivierLaligant1, FabriceMeriaudeau11Laboratoire Le2i - Universit´e de Bourgogne12 rue de la Fonderie, 71200 Le Creusot, France2IFSC - Universidade de S˜ao PauloCaixa postal 369 - CEP:13560-970, S˜ao Carlos, Brasilt.chalumeau@iutlecreusot.u-bourgogne.fr, luciano@ifsc.usp.bro.laligant@iutlecreusot.u-bourgogne.fr, f.meriaudeau@iutlecreusot.u-bourgogne.frR´esum´e -Cet article d´ecrit une nouvelle m´ethode et approche pour la caract´erisation de texture.
En utilisant une repr´esentationdes images en r´eseau complexe, les mesures classiques et d´eriv´ees (hi´erarchiques), nous pr´esentons comment obtenir de bonsr´esultats en classification de texture.
L"image est repr´esent´e par un r´eseau complexe : un pixel par un noeud.
Les calculs desdegr´es d"un noeud et des coefficients de cluster, utilis´es avec leurs mesures traditionnelles et ´etendues (hierarchiques), sont utilis´espour carract´eriser "l"organisation" des textures.Abstract -This article describes a new method and approch of texture characterization.
Using complex network representationof an image, classical and derived (hierarchical) measurements, we presente how to have good performance in texture classification.Image is represented by a complex networks : one pixel as a node.
Node degree and clustering coefficient, using with traditionnaland extended hierarchical measurements, are used to characterize "organisation"" of textures.
1) IntroductionL"analyse de texture joue un rˆole important dans denombreuses applications de traitement d"image.
Diversesm´ethodes existent pour l"extraction de caract´eristiques detextures, telles que les matrices de co-occurrence intro-duit par Haralick [1], les champs de Markov, les filtresde Gabor [2], le LBP [3].
Toutefois, l"analyse de textureest encore un sujet relativement ouvert pour lequel diverstravaux de recherches sont r´eguli`erement pr´esent´es.
Notreapproche est motiv´ee par les r´ecentes recherches faites surles r´eseaux complexes.
En effet, tel qu"ils sont pr´esent´es [4],les r´eseaux complexes et les outils de leur caract´erisationsemblent prometteur pour l"analyse des images.
Un R´e-seau complexe est une repr´esentation adapt´ee pour carac-t´eriser les relations et les interactions entre les diff´erents´el´ements qui le composent [5].
L"objet de cet article est depr´esenter une m´ethode simple de repr´esentation d"imagespar des r´eseaux complexes.
Puis de montrer les outils per-mettant de caract´eriser les r´eseaux complexes et d"appli-quer ceci `a la caract´erisation de texture.Dans un premier temps, un rappel sur les r´eseaux com-plexes, leurs caract´eristiques sera fait.
Puis la m´ethode deconversion d"une image en r´eseau complexe sera d´evelop-p´ee. Les m´ethodes utilis´ees pour comparer nos r´esultatsseront d´ecrites. Les r´esultats des diverses m´ethodes serontexpos´ees. Enfin, une conclusion et les perspectives termi-neront l"article. 2) R´eseaux complexes et repr´esen-tation de l"image2.
1) R´eseaux complexes et mesuresUn r´eseau est une collection d"entit´es qui sont reli´ees en-semble.
Un lien (connection) entre deux entit´es (noeuds)d´enote une interaction entre ces deux entit´es. Ces connec-tions peuventˆetre binaires (pr´esence ou absence de connec-tion) ou pond´er´ees.
Les r´eseaux complexes peuvent ˆetre re-pr´esent´es math´ematiquement par une matrice appel´eema-trice d"adjacence.
Pour un r´eseau complexe avecNnoeuds,la matrice d"adjacence (W) a une dimensionN×N.
Lepoids des connections de chaque noeudjet chaque noeudi(i,j= 1,2, ,N) est repr´esent´e parW(i,j), avec une valeurnulle signifiant une absence de connection.
Une secondematriceWt, binaire, est aussi d´efinie. Elle contient seule-ment les connections les plus significatives.
Par exemple,les connections ayant les poids les plus ´elev´es (seulementles ´el´ements deWqui sont plus grand ou ´egales `a un seuilTsont gard´ees).
Un exemple figure 1 peut ˆetre vu.La caract´erisation de la topologie et les propri´et´es desconnections d"un r´eseau complexe peuvent ˆetre d´etermi-n´ees par des mesures issues de la th´eorie des graphes [6]et de la recherche sur les r´eseaux complexes [7], incluant,mais ne se limitant pas `a :2.1.
1) Degr´eLe degr´e d"un noeud est ´egale au nombre de connec-tions qu"il poss`ede.
Dans le cas de connections pond´er´ees,Colloque GRETSI, 11-14 septembre 2007, Troyes473(a)0023000220013210(b)0011000110001100(c)Fig.1 - (a) : Micro r´eseau complexe pond´er´e (b) : matriced"adjacenceW, (c) : matriceWt(binaire) obtenue avec leseuilT= 2.il correspond `a la somme de tous les poids des connectionsrespectives.
Un exemple figure 2 permet d"illustrer.
L"his-togramme des fr´equences des degr´es donne une importantecaract´erisation de la connectivit´e du r´eseau.2.1.
2) Coefficient de clusterLe coefficient de cluster pour un noeud est d´efinit pourun noeudipar le nombre de connections entre les noeudsconnect´es `aidivis´e par le nombre de connections pos-sibles entre ces mˆemes noeuds.
Lorsque le num´erateur oule d´enominateur de ce quotient sont nuls, le coefficient decluster est nul.
On peut noter que la valeur est compriseentre 0 et 1 pour n"importe quel noeud.
Un exemple estdonn´e figure 2.Fig.2- Illustration du calcul du degr ´eet du co efficientde cluster pour le noeud repr´esent´e en noir :D= 4 etC=34×3\2=12.2.1.
3) Mesures hierarchiquesCertaines mesures de r´eseaux complexes, incluant le de-gr´e et le coefficient de cluster, peuvent ˆetre g´en´eralis´eespour tenir compte non pas seulement des voisins imm´e-diats mais ´egalement des voisins `a plusieurs distances pourun noeud sp´ecifique, comme l"illustre l"exemple figure 3.En particuler, le degr´e hierarchique d"un noeud `a une dis-tance correspond au nombre de liens connect´es les noeuds`a la distancei`a la distancei+ 1.
De mˆeme pour le coef-ficient de cluster.Pour toutes ces mesures, tous les noeuds du r´eseau com-plexe sont caract´eris´es.
Pour avoir une information globaledu r´eseau, la moyenne et l"´ecart type sont d´etermin´es `apartir de l"histogramme de fr´equence obtenu pour chaquemesure.Fig.3- Repr ´esentationhierarc hiqueou m ulti-´echelle(` agauche) du r´eseau complexe original (`a droite).2.
2) Repr´esentation d"une imagePour transformer une image d"une dimensionM×Men r´eseau complexe, nous d´efinissons que chaque pixel estrepr´esent´e par un noeud.
Pour chaque noeud, on d´efinitles connections avec les noeuds voisins (noeuds dont ladistance euclidienne par rapport au noeud courant est in-f´erieure `a un rayon fix´e) comme ayant un poids ´egale `a lavaleur absolue de la diff´erence de niveau de gris entre lespixels.
On obtient alors une matrice adjacenteW, de di-mensionN×NavecN=M2.
Dans ce cas l`a, une connec-tion ayant un poids faible d´efinit une connection tr`es forte,et une grande valeur signifie une connection pauvre.
Unexemple de construction des matricesWetWtest illustr´eFigure 4 et une repr´esentation en r´eseau complexe d"uneimage Figure 5.101228162531(a)x218615212x16413191816x12336412x915151339x621193156x(b)010100100100000011110000001001001010(c)Fig.4 - (a) : partie d"une image en niveau de gris (b) :matrice d"ajacence (W) de l"imagette, (c) : matriceWtavec un seuilT= 8 .Fig.5- Image de dimension 30 ×30 et sa repr´esentationgraphique en r´eseau complexe.
3) M´ethodes comparativesLes r´esultats obtenus utilisant la m´ethode utilisant lesr´eseaux complexes a ´et´e compar´ee avec la m´ethode des474matrices de co-occurence introduite par Haralick [8] et lesfiltres de Gabor [9, 2].3.
1) Les matrices de co-occurence :Les matrices de co-occurence consid`erent les r´ep´etitiond"apparition de plusieurs niveaux de gris .Les matrices de co-occurrence consid`erent des occur-rences r´ep´et´ees d"une certaine configuration de niveau grisdans la texture.
Une matrice de co-occurrence est construiteen observant des paires de pixels s´epar´es par une distancedet incr´emente la position de matrice correspondante auniveau gris des deux pixels.
La valeurp(i,j) repr´esentela fr´equence de l"occurence de la situationf(x1,y1) =i,f(x2,y2) =j,|x1-x2|=d.Diverses caract´eristiques peuvent ˆetre extraites `a partirde la matrice de co-occurrence : ´energie, contraste, cor-r´elation, dissimilitude, homog´en´eit´e.
Dans notre cas, cescaract´eristiques ont ´et´e d´etermin´ees avecd= 1 etd= 5[10].3.
2) Les filtres de Gabor :Les filtres de Gabor, utilisant une analyse de Fouriersont essentiellement sinus et cosinus (exponentiel com-plexe) modul´es par une fenˆetre gaussienne.
En espace com-plexe ces filtres sont exprim´es comme :h(x,y) =g(x?,y?).ej2π(Ux+Vy)(1)o`u g(x,y) =12πλσ .e-(x/λ)2+y22σ2et?x?y??=?x.cos(φ) +y.sin(φ)-x.sin(φ) +y.cos(φ)?φest une rotation dans le sens des aiguilles d"une montrele long de l"axe dex,UetVrepr´esentent les coordonn´eesde fr´equence.σest l"´ecart type de l"enveloppe gaussienne (qui d´efinit sataille) etαest le param`etre de forme de la gaussienne.La gaussienne a une forme circulaire pourα= 1.La fonction de transfert deh(x,y) est exprim´e comme :H(x,y) =G(u?-U?,v?-U?) (2)avec G(u,v) =e-2π2σ2(u2λ2+v2)et?u?v??=?u.cos(φ) +v.sin(φ)-u.sin(φ) +v.cos(φ)?H(u,v) est donc un filtre passe-bande gaussien, dontl"axe principal est orient´e au degr´e deφde l"axe deu.La fr´equence centraleFest d´efini par :F= (U+V)1/2,orient´ee selon l"angle polaireθ, comme d´ecrit dans la Fi-gure 6.
Dans notre cas, 3 fr´equences et 6 angles sont em-ploy´es, avecφ=deta.
Le param`etre extrait des resultatsest l"´energie :Energie=?pixel2;(3)Fig.6- : Represen tationd"un filtre de Gab ordans l"es- pace de Fourier avecθ?=φ.
4) R´esultatsL"´etude comparative a ´et´e r´ealis´ee tout en consid´erantdiff´erentes textures r´esultant de la base de donn´ee CU-ReT1.
Six diff´erentes textures, illustr´ees Figure 7, ont´et´e utilis´ees.
Pour toutes les textures, 20 "imagettes"sontconsid´er´ees.Fig.7- Exemple des 6 textures utilis ´ees.Deux diff´erents essais de classification ont ´et´e effectu´es.Le premier est un perceptron multicouche du logiciel TA-NAGRA [11], le second, un classificateur bay´esien.
Le per-ceptron multicouche a 25 neurones, avec 500 it´erationsmaximum et un taux d"aprentissage ´egale `a 0.25.Le classificateur bay´esien est bas´e sur le mod`ele normalde probabilit´e [12], dont l"´equaion est donn´ee par :p(-→x) =α exp?-12(-→x--→μ-→X)TK-1(-→x--→μ-→X)?(4)avec α=1(2π)N/2?Det{K}o`u-→xest un vecteur al´eatoire,-→μ-→Xcorrespond au vec-teur moyen, etKest la matrice de covariance.Les deux m´ethodes emploient 50% des "imagettes"pourl"apprentissage et 50% pour la classification.
Pour compa-rer nos r´esultats de classification aux m´ethodes compara-tives, le taux d"erreur est d´efini comme le nombre de mau-vaises classiifications divis´e par le nombre d"´echantillons.1http ://www1.cs.columbia.edu/CAVE/software/curet/Colloque GRETSI, 11-14 septembre 2007, Troyes4754.
1) M´ethode classique :La Table 1 montre le taux d"erreur de classification pournotre m´ethode (avec des seuils diff´erents), et pour la com-paraison, avec les r´esultats obtenus en utilisant la m´ethodedes matrices de co-occurrence et les filtres de Gabor.Tab.1 - Taux d"erreur (T.E.) des deux classifications(perceptron et methode bayesienne) pour la m´ethode uti-lisant les r´eseaux complexes et les measures simples, l"ap-proche d"Haralick et les filtres de Gabor.M´ethodedistanceseuilT.
E. percep.T.E. BayeGraphe520.190.10Graphe550.120.13Haralick1/0.230.17Haralick5/0.260.17Gabor//0.230.174.
2) M´ethode hierarchique :Le taux d"erreur est ´egalement d´etermin´e avec tous lesdiff´erents niveaux hi´erarchiques.
L"´evolution de ce tauxd"erreur prend en consid´eration successivement les diff´e-rents niveaux hierarchiques (abcisses), comme on peut levoir Figure 8.
Il faut ajouter que la valeur sur l"axe desabcisses indique l"utilisation de tous les niveaux hierar-chiques jusqu"au niveauk, et non pas seulement le niveauk.Fig.8- Ev olutiondu taux d"erreur en fonction des niv eauhierachiques utilis´es.
Ces r´esultats ont ´et´e obtenus `a l"aidedu perceptron.Avec ces r´esultats, il s"av`ere que l"utilisation des me-sures consid´erant les niveaux hi´erarchiques a un effet po-sitif en am´eliorant le taux de classification (taux d"erreurinf´erieur).
Le minimum du taux d"erreur n"est pas obtenupour les niveaux hi´erarchiques les plus ´elev´es utilis´es (3et 4).
Ce meilleur niveau hi´erarchique d´epend de la tailled"image, la r´egion circulaire, de la d´efinition des connec-tions et du seuil.
Si le niveau hi´erarchique est trop ´elev´e,les raccordements entre les noeuds sont pauvres (ou inexis-tants), et les param`etres d´etermin´es (degr´e et coefficent decluster) ne peuvent pas ˆetre adapt´es pour discriminer desr´eseaux.
5) ConclusionDeux m´ethodes pour la classification de texture em-ployant les r´eseaux complexes ont ´et´e pr´esent´ees et compa-r´ees.
Notre m´ethode simple, en utilisant les r´eseaux com-plexes avec des mesures de topologie et de connectivit´e,a une bonne capacit´e de repr´esenter et le caract´eriser lestextures.
L"int´erˆet des niveaux hi´erarchiques a ´et´e mis enavant par l"augmentation de l"efficacit´e de la classification.Des r´esultats encourageants ont ´et´e obtenus en utilisantdes param`etres de simples.
Nous travaillons actuellementpour am´eliorer les faiblesses de la m´ethode : avoir plusd"information sur les histogrammes d´eterminer (utilisationdes moments et des coefficients), avoir une d´eterminationautomatique du meilleur niveau hierachical et du meilleurseuil.R´ef´erences[1] J.
Haddon and J.
Boyce,"Co-occurrence matrices forimage analysis,"Electronics & Communication Engi-neering Journal5 (2), pp. 71-83, 1993.[2] P.
Kruizinga, N. Petkov, and S.
Grigorescu, "Com-parison of texture features based on gabor filters,"Proceding of the 10th Internationnal Conference onImage Analysis and Processing, pp. pp. 142-147,1999.[3] G. Zhao and M.
Pietikainen, "Local binary patterndescriptors for dynamic texture recognition,"PatternRecognition2, pp. 211 - 214, 2006.[4] L. da Fontoura Costa,"Complex networks, simple vi-sion,"cond-mat/0403346, 2004.[5] M.
E. J. Newman, "The structure and function ofcomplex networks,"cond-mat/0303516, 2003.[6] R. Diestel,Graph Theory, Springer, 2nd electronicedition ed., 2000.[7] R. Albert and A.-L. Barabasi, "Statistical mechanicsof complex networks,"cond-mat/0106096, 2001.[8] L.-K. Soh and C.
Tsatsoulis,"Texture analysis of sarsea ice imagery using gray level co-occurrence ma-trices,"IEEE Transactions on geoscience and remotesensing37(2), pp. 780-795, 1999.[9] C.
Palm and T. M.
Lehmann,"Classification of colortextures by gabor filtering,"Machine GRAPHICS &VISIONVol. 11, p. pp 195 - 219, 2002.[10] N.
Pican, E. Trucco, M. Ross, D. M. Lane, Y. Pe-tillot, and I.
Ruiz, "Texture analysis for sea-bed classification : Co-occurrence matrices vs self-organizingmaps.,"IEEE/OES OCEANS "98 Confe-rence Proceedings1, pp. 424-428, 1998.[11] R.
Rakotomalala, "Tanagra : un logiciel gratuitpour l"enseignement et la recherche,"in Actes deEGC"2005, RNTI-E-32, pp. 697-702, 2005.[12] L. da Fontoura Costa and R.
M. C. Junior,ShapeAnalysis and Classification : Theory and Practice,CRC Press, Inc, 2000.476
