Mémoire de fin d’étude

Fouille de graphes et Classification de graphes
Application au "Symbol Spotting"

Réalisé par : Nguyen Quoc Toan
Responsable du stage : Jean-Marc Ogier
Jean-Christophe Burie
Romain Raveaux

Ce stage a été réalisé au département Pascal de Laboratoire Informatique, Image et
Interaction, Université de la Rochelle

La Rochelle, France, Novembre 2009


Table des matières
1 Introduction............................................................................................................................. 8
1.1 Problématique.................................................................................................................. 8
1.2 Objectif et contribution du stage...................................................................................... 8
1.3 Environnement de stage................................................................................................... 8
1.4 Plan du document............................................................................................................. 8
2 Conceptions........................................................................................................................... 10
2.1 Définition de graphe.......................................................................................................10
2.2 Correspondance de Graphe............................................................................................ 10
2.3 Graphe de distance......................................................................................................... 11
2.3.1 Distance d'édition.................................................................................................... 12
2.3.2 Distance entre signatures de graphe «graph probing » .......................................... 15
2.4 Symbol spotting............................................................................................................. 17
3 Etat de l'art............................................................................................................................ 19
3.1 Les méthodes de construction de graphe ...................................................................... 19

3.2 Les methodes de mise en correspondances des graphes................................................ 22
3.3 Récaputulation des méthodes ........................................................................................ 24
4 Une méthode de mise en correspondance de graphes fondée sur l’assignement de sousgraphes...................................................................................................................................... 25
4.1 Définition : Décomposition en sous-graphes................................................................. 25
4.2 La correspondance de sous-graphes............................................................................... 26
4.3 Le coût de fonction (c) pour la correspondance des signatures..................................... 26
4.4 Sous graphe de longueur ι.............................................................................................. 27
4.5 Construction de matrice de coûts................................................................................... 28
5 Représentation de l’information contenue dans une image.................................................. 30
5.1 Constitution de l'ensemble des nœuds........................................................................... 30
5.2 Extraction des composantes connexes........................................................................... 31
5.3 Étiquetage des composantes connexes............................................................................ 31
5.3.1 Extraction de caractéristiques ................................................................................ 32
5.3.2 Statistique de la forme ............................................................................................33
5.3.3 Classification non supervisée des caractéristiques morphologiques....................... 34
5.4 Organisation de l’information : Construction d’un Graphe de voisinage...................... 34
5.4.1 Relations d'Allen bidimensionnelles....................................................................... 34
5.4.2 Intervalle basé sur les distances entre deux régions................................................ 35
6 Application............................................................................................................................ 36
6.1 Protocole........................................................................................................................ 36
6.1.1 Test en classification............................................................................................... 36
6.1.2 Symbol Spotting...................................................................................................... 37
6.2 Bases de tests................................................................................................................. 42
6.2.1 Pour la classification............................................................................................... 42
6.2.2 Pour le Symbol Spotting......................................................................................... 43
6.3 Résultat...........................................................................................................................44
6.3.1 Test en classification .............................................................................................. 44
6.3.2 Symbol Spotting...................................................................................................... 45
6.4 Complexité algorithmique..............................................................................................51
Symbol spotting....................................................................................................................... 51

Conclusions.............................................................................................................................. 53
Références................................................................................................................................ 54

NGUYEN Quoc Toan – Promotion 13

Page 2


REMERCIEMENTS
Je voudrais tout d'abord remercier professeur Jean-Marc Ogier, Jean-Christophe Burie,
mes responsables de stage, de m'avoir accueillie au sein de l’équipe du projet ALPAGE du
Laboratoire L3i (Laboratoire Informatique, Image et Interaction) de l’Université de la Rochelle
et de m’a donné l’environnement de travail très chaleureuse pendant toute la durée du
stage.
Je remercie également Romain Raveaux pour ses conseils, son explication très clairement
des nouveaux concepts, ses aides, ses commentaires et ses discussions qui ont fait
progresser mon travail. Je lui suis reconnaissant d’avoir toujours été disponible et agréable.
Je voudrais remercier tout le personnel du laboratoire L3I et particulièrement l’équipe du
projet ALPAGE pour leur accueil chaleureux.
Je voudrais aussi adresser mes sincères remerciements à tous les professeurs de
l’IFI pour leurs enseignements et les cours intéressants qu’ils m’ont donné pendant
mes études au niveau master.
Finalement, je voudrais remercier ma famille, mes parents et mes amis qui sont
toujours près de moi et m’ont apporté le courage dans les moments difficiles de ma scolarité
à l’IFI.

NGUYEN Quoc Toan – Promotion 13

Page 3



Résumé
Reconnaissance des symboles est un domaine de recherche visant le développement
d'algorithmes et de techniques et il y a une nombreuse méthode de reconnaissance de
graphiques ont été développées pour la reconnaissance des symboles graphiques. Le
problème « Symbole Spotting » est comme la localisation d'un ensemble de régions d'intérêt
d'un document image, qui sont susceptibles de contenir une instance d'un certain symbole
demandé sans le reconnaître explicitement.
Nous présentons donc dans ce mémoire un processus d’extraction et d’organisation de
l’information contenue dans une image afin de la structurer sous forme d’un graphe pour
tenir compte de la spécificité que contiennent les documents techniques. Chaque nœud du
graphe représente une composante connexe dans l’image de document, ces nœuds sont
étiquetés automatiquement par l’algorithme de clustering « k-Mean ». Ce dernier utilise des
descripteurs de formes extraits des composantes connexes. La relation entre deux
composantes connexes est matérialisée dans un graphe de « voisinage » par un arc étiqueté
automatiquement en utilisant les relations d'Allen bidimensionnelles ou la distance entre
composantes connexes.
Nous proposons une méthode de mise en correspondance de graphes fondée sur
l’assignement de sous-graphes de longueur l. Nous proposons aussi une définition de sousgraphe de longueur l. Le problème de reconnaissance des symboles devient donc de trouver
les sous-graphes les plus similaires au graphe symbole donné en requête. Nous extrayons le
graphe de plan en des sous-graphes de longueur l. Le résultat de notre application est
ensemble de sous-graphes isomorphisme que la distance entre les sous-graphes et le
graphe de symbole est inférieur une valeur seuil.
Afin d’évaluer la classification de graphes, nous utilisons un classifieur de type K-NN pour
évaluer la performance de notre méthode de mise en correspondance de graphes fondée
sur l’assignement de sous-graphes.

NGUYEN Quoc Toan – Promotion 13

Page 4



Abstract
Symbol Recognition is a research area for the development of algorithms and techniques, a
lot of method of graphics recognition are developed for the recognition of graphic symbols.
The problem "Symbol Spotting" aims to find the locations of a set of regions interest in a
document image, which may contain an instance of a symbol without explicitly recognize.
We therefore present in this paper a process for extracting and organizing information in an
image to the structure of a graph for the specificity technical documents. Each graph node is
a connected component. These nodes are labeled automatically by the clustering algorithm
"k-means”. We extract the connected components using shape descriptors. We use the
family of graph "Neighborhood based on k nearest neighbors" to build edges and they are
automatically labeled by the Bi-dimensional Allen Algebra or the distance between regions.
We propose a method for mapping graph-based assignment of subgraphs of length l. We
also propose a definition of subgraph of length l. The symbols recognition problem is like to
find subgraphs which are the nearest similar to the graph of symbol. We extract the graph of
technical documents in many subgraphs of length l. The recognition task consists of finding
all subgraphs isomorphism which the distance between sub-graphs and symbol graphs is
less than a certain threshold.
To test the classification of graphs based on graph prototypes, we use a K-NN classifier in
order to evaluate our method for mapping graph-based assignment of subgraphs of length l
by the rate of recognition.

NGUYEN Quoc Toan – Promotion 13

Page 5


Liste des figures
Figure 1: La distance entre signatures de graphe GP, (a) les graphes non orienté, sans

étiquetage, (b) les graphes orientés, sans étiquetage, (c) les graphes étiquetés, orientés..........16
Figure 2: La distance entre deux graphes selon ED et GP, (a) les graphes non orienté, sans
étiquetage, (b) les graphes orientés, sans étiquetage, (c) les graphes étiquetés, orientés..........17
Figure 3 : Graphiques attribués relationnelle, chaque nœud est comme une ligne segmentée,
un arcs établis la relation d’adjection entre deux segmentations (source[14])......................... 19
Figure 4: Chaque nœud est une région fermée. L’arc lie deux régions adjacentes (source[32])
...................................................................................................................................................19
Figure 5: Graphe transaction, source [33].................................................................................20
Figure 6: vectorisation de quadrilatères, source [45]................................................................ 20
Figure 7: La zone influence de quadrilatère et le graphe correspondant, source [45].............. 21
Figure 8: exemple de construction d’un graphe basé sur les relations topologique, source [35]
...................................................................................................................................................21
Figure 9: La décomposition en sous-graphes. p1, p2, p3, p4 est des sous-graphes d’extractions
de longueur 1 qui associés à chaque nœuds du graphe G....................................................... 25
Figure 10: à partir deux graphes G1, G2 (a), on extrait des sous-graphes de longueur 1 (a), (b).
Le graphe bipartite complet Gem obtenu par P1 et P2............................................................. 26
Figure 11: (a) un graph G(V, E), à partir du nœud 1, on extrait les sous graphes avec
(b)longueur=1, (c)longueur=2 ..................................................................................................28
Figure 12: un exemple de la correspondance de graphe, (a), (b) les sous-graphes d’extraction
de longueur 1, (c) la correspondance de sous-graphe selon distance d’édition (ED)............... 30
Figure 13: Analyse des composantes connexes........................................................................ 31
Figure 14: Mesure de l'élongation, comme le ratio de la longueur-largeur.............................. 33
Figure 15:Graphe des k plus proches voisins (a) les composantes connexes, (b) k=2, (c) k=134
Figure 16: Jeu restreint de relations d'Allen..............................................................................35
Figure 17: (a) deux composantes connesxes, (b) détermination du système de coordonnées lié
aux............................................................................................................................................. 35
Figure 18: L’image à gauche : représentation de la distance entre deux composantes connexes,
d-max = 39. Le graphe droit obtenu par n = 10 (n est le nombre d’intervalles). ................... 36
Figure 19: La vérité terrain pour un plan.................................................................................. 41
Figure 20: Les exemples de lettres A, M, K et Z: l'origine et la déformation des niveaux

faible, moyen et élevé (de gauche à droite).............................................................................. 42
Figure 21 : Illustration du composant d’une molécule ............................................................ 43
Figure 22:la comparaison le temps de calcul sur PMDED et PMDGP.................................... 45
Figure 23: La courbe de précision, rappel selon la méthode Hu_Dist...................................... 47
Figure 24: La courbe de précision, rappel selon la méthode Hu_ Allen...................................48
Figure 25: La courbe de précision, rappel selon la méthode Shape_Allen...............................49
Figure 26: La courbe de précision, rappel selon la méthode Shape_Dist................................. 50
Figure 27: Les meilleurs courbes de chaque méthode d'étiquetage.......................................... 51

NGUYEN Quoc Toan – Promotion 13

Page 6


Liste des tableaux
Table 1: Matrice des coûts de G1, G2.......................................................................................13
Table 2: étape 1 : réduction des lignes...................................................................................... 13
Table 3: étape 2 : réductions des colonnes................................................................................13
Table 4: étape 3 : déterminer le nombre minimal de lignes sur les lignes, colonnes pour
couvrir tous les zéros.................................................................................................................14
Table 5: étape 4 : Trouver la cellule de valeur minimum non-couverte par une ligne............. 14
Table 6: étape 4 : recaler la valeur pour les cellules basées sur cette valeur minimum ...........14
Table 7: étape 4 : déterminer le nombre minimal de lignes......................................................14
Table 8: étape 5 : déterminer la solution optimale....................................................................15
Table 9: le coût minimal de G1, G2..........................................................................................15
Table 10 : La matrice de coûts entre deux graphes G1, G2...................................................... 29
Table 11: Résumé des données de graphes des caractéristiques...............................................43
Table 12: Les taux de reconnaissance pour deux méthode PMDED et PMDGP..................... 45
Table 13: La valeur moyenne de précision, rappel selon la méthode Hu_Dist........................ 46
Table 14 : La valeur moyenne de précision, rappel selon la méthode Hu_Allen..................... 47

Table 15: La valeur moyenne de précision, rappel selon la méthode Shape_Allen................. 48
Table 16: La valeur moyenne de précision, rappel selon la méthode Shape_Dist....................49
Table 17: La comparaison des méthodes d'étiquetage des noeuds, des arcs.............................50
Table 18: Comparaison nos résultats avec les résultats de Marçal [51]................................... 51

NGUYEN Quoc Toan – Promotion 13

Page 7


1 Introduction
1.1 Problématique
Reconnaissance de symbole est une des applications importantes dans le domaine de la
reconnaissance de formes qui est appliqué dans plusieurs domaines comme l'architecture, la
cartographie, l'électronique, la mécanique etc. En raison des types de documents graphiques
sont trop large, chacune d’entre eux possèdent un ensemble caractéristique de symboles
propres, il n'est pas facile de trouver une définition précise d'un symbole. Dans une manière
très générale, un symbole peut être défini comme une entité graphique avec un sens
particulier dans le contexte d'un domaine d'application spécifique. Il y a un grand nombre
d'approches ont été proposées pour la reconnaissance des symboles. Chacune d’entres
elles possèdent des propriétés qui lui sont propres et ne peut s’appliquer qu’à certains
contextes, réunissant certaines conditions.
Dans notre cas, nous utilisons la méthode basées sur le graphe pour représenter les images
de documents techniques et de symbole demandé en des graphes. Chaque nœud du
graphe représente une composante connexe dans l’image de document. La relation entre
deux composantes connexes est matérialisée dans un graphe de « voisinage ». Le problème
de la reconnaissance de symbole est tourné en une question d’isomorphisme de sous
graphe, afin de trouver les sous-graphes qui correspondent à des symboles graphiques.

1.2 Objectif et contribution du stage

L'objectif de stage est dans un premier temps d'étudier le problème de la correspondance de
graphes « Graph Matching », les mesures de calculer la distance entre deux graphes. Et
puis, nous proposons une méthode de mise en correspondance de graphes fondée sur
l’assignement de sous-graphes de longueur l. Ensuite nous construisons un protocole de test
en classifications basé sur les prototypes de graphes en utilisant la méthode K plus proche
voisins (K-NN) basé sur notre méthode de mise en correspondance de graphes. Enfin, nous
créons une application de type reconnaissance de symbole basé sur le graphe pour trouver
toutes les localisations d’un symbole dans un plan donné.

1.3 Environnement de stage
Ce stage s’intègre dans le contexte d’un projet appelé : « ALPAGE »1 de Laboratoire L3I,
Université de La Rochelle, France. Ce projet traite des plans cadastraux couleurs de
l’espace urbain parisien suivant différentes époques, allant du 14 ème au 19 ème
siècle en intégrant réellement la dimension spatiale. Les travaux de ce projet ont concernant
les domaines telles que la vision par ordinateur, la géométrie, l’archéologie et
reconnaissance des formes. La contribution du stage est une nouvelle approche dans le
domaine de reconnaissance de forme basé sur le graphe.

1.4 Plan du document
Le reste du document est organisé de la manière suivante.
La deuxième partie, nous présentons des conceptions fondamentales. Dans la troisième
partie, nous présentons un état de l’art des méthodes à base de graphe pour la
reconnaissance des symboles graphiques. Alors, la quatrième partie présente une nouvelle
méthode de mise en correspondance de graphes fondée sur l’assignement de sous-graphe
de longueur l en utilisant la matrice de coûts. La cinquième partie fournit la façon de
construire un graphe basé sur l’information contenue dans une image, dans ce chapitre nous
proposons des méthodes d’étiquetage des nœuds et des arcs pour avoir des types de
graphe différent. Dans la sixième partie, nous présentons la contribution de notre stage à
1




NGUYEN Quoc Toan – Promotion 13

Page 8


construire deux protocoles : Test en classification et Symbol Spotting, nous présentons aussi
la méthode d’évaluation que nous avons utilisée pour notre système, ainsi que les résultats
obtenus. La dernière partie présente la conclusion, ainsi que les perspectives.

NGUYEN Quoc Toan – Promotion 13

Page 9


2 Conceptions
2.1 Définition de graphe
Soient deux fonctions d'étiquetage LV (V) et LE(E) qui associent à chacun des éléments de V,
respectivement de E, une étiquette. Un graphe étiqueté G est un 4-tuple G = (V, E, µ, ξ),
avec :
V est un ensemble de nœuds
E ⊆ V × V : un ensemble d’arcs
µ : V → LV : la fonction d’étiquetage de nœud
ξ : E → LE : la fonction d’étiquetage d’arcs

2.2 Correspondance de Graphe
Les graphes constituent un mode de représentation fréquemment utilisé dans le domaine
des sciences et technologies de l'information qui permettent à la description de données
structurées. Un graphe G est un ensemble V de nœuds et un ensemble E d'arcs, G = (V,

E). Les outils de classification supervisée sont de plus en plus nécessaires dans de
nombreuses applications telles que la reconnaissance des formes [1], la CBR (Case Based
Reasoning) [2], l’analyse des composantes chimiques [3], …Pour lancer le sujet de la mise
en correspondance de graphe « graph matching », nous rappelons qu'il existe une étude
approfondie sur les techniques de la correspondance de graphes apparues au cours de ces
30 dernières années dans [4].
Dans le cas du problème de reconnaissance des formes, étant donné deux graphes : le
graphe de modèle GM et le graphe de données GD, la procédure de comparaison implique
de vérifier si ils sont similaires ou non. De manière générale, nous pouvons représenter le
problème de la correspondance de graphe comme suit : Etant donné deux graphes GM =
(VM, EM) et GD = (VD, ED), avec | VM | = | VD |, le problème est de trouver une fonction de
correspondance f: VD → VM, tel que (u, v) ∈ ED Si et seulement si (f (u), f (v)) ∈ EM.
Lorsqu’une telle fonction de correspondance f existe, nous somme en présente d’un
isomorphisme, et GD est dit d'être isomorphe à GM et ce type s’appelle « correspondance
exacte ». D'autre part, le terme « inexact » appliquée aux problèmes de la correspondance
de graphe, indique qu'il n'est pas possible de trouver un isomorphisme entre les deux
graphiques. C'est le cas lorsque le nombre de sommets ou le nombre d’arcs sont différents à
la fois dans le graphe modèle et graphe de données. Dans ce cas là, on peut trouver la
meilleure correspondance entre eux en trouvant une correspondance non-bijective entre le
graphe de données et le graphe de modèle.
Le problème de la correspondance de graphe a été prouvé être le NP-complet [5]. Lorsque
le nombre de nœuds dans les deux graphes sont différents, le problème de la
correspondance de graphe devient plus difficile que dans le cas de la correspondance de
graphe exact. De même, la complexité du problème de sous-graphe inexact est équivalente
à la complexité du problème de la plus grand sous graphe commun, qui est aussi connu pour
être NP-complet. Plusieurs techniques ont été proposées pour résoudre ce problème, par
exemple, la relaxation probabiliste, l'algorithme EM [6], [7], les réseaux de neurones [8], [9],
des arbres de décision [10] et un algorithme génétique [11], [12].
Toutes les méthodes énoncées antérieurement ont comme point commun l'utilisation d'un
algorithme d'optimisation pour adapter un graphe dans un autre et une fonction « qualité »

pour mesure la bonne similarité entre deux graphes. Cette fonction est conçue en tenant
compte du coût pour faire la correspondance VD → VM. Les auteurs sont convaincus qu‘une
correspondance convenable doit conduire à une distance entre graphe précise. Selon cette
hypothèse, le problème est tourné en une question de distance entre graphes. De plus, ce
point de vue sur le problème de la correspondance de graphe permettra de lancer un banc
de tests sur notre approche et de fournir une étude comparative.

NGUYEN Quoc Toan – Promotion 13

Page 10


2.3 Graphe de distance
Dans cette section, nous présentons une étude de différentes mesures permettant de
comparer des graphes. Cette étude, prenant en considération les contraintes de coût de
calcul, permet de justifier notre orientation vers une mesure basée sur les signatures de
graphe.
Une mesure de dissimilarité (ou indice de dissimilarité) d est une fonction à valeur numérique
permettant de mesurer le lien entre des individus d'un même ensemble X. Le lien est
d'autant plus fort que la mesure de dissimilarité est faible

d:X× X → ℜ

Une mesure de dissimilarité dispose des propriétés suivantes :
Non-négativité :

d ( x, y ) ≥ 0

(1)


Unicité :

d ( x, y ) = 0 ⇔ x = y

(2)

Symétrie :

d ( x, y ) = d ( y , x )

(3)

Les mesures de dissimilarité peuvent être transformées en mesure de similarité en inversant
la relation d'ordre (par exemple s(x, y) = k − d(x, y) où k est une constante). Une métrique est
une mesure de dissimilarité qui respecte l'inégalité triangulaire (4).
d ( x, y ) ≤ d ( x, z ) + d ( z , y )
(4)
Les pseudo-métriques sont un autre type de fonctions permettant de comparer des objets.
Elles respectent les propriétés de non-négativité, de symétrie et l'inégalité triangulaire mais
ne respectent pas nécessairement la propriété d'unicité.
Des pseudo-métriques peuvent être obtenues par des transformations qui, appliquées à des
mesures de dissimilarité, respectent la relation d'ordre.
Ainsi, par exemple, si d(x, y) est une mesure de dissimilarité, alors D(x, y) définie par

D ( x, y ) =

d ( x, y )
+1
1 + d ( x, y )


est une pseudo-métrique [12]

L'inégalité triangulaire est une propriété souvent exploitée pour optimiser la recherche de
similarité dans les espaces métriques [13] [14], avec des applications directes en
classification par k-NN [15] ou en recherche d'information.
Lorsque les objets à comparer sont des graphes, la propriété d'unicité transforme l'égalité en
isomorphisme et peut donc s'énoncer de la façon suivante : une fonction f de deux graphes
G1 et G2 respecte la propriété d'unicité si f (G1, G2) = 0 est équitant à G1 est isomorphe à G2.
La recherche d'isomorphisme entre graphes est réputée être un problème NP-complet.
Cependant, la définition d'une mesure de dissimilarité dont la complexité la rend
computationnelement manipulable permettrait de rendre plus simple la recherche
d'isomorphisme. En d'autres termes, la propriété d'unicité rend équivalente la complexité de
la recherche d'isomorphisme et celle du calcul de dissimilarité.

NGUYEN Quoc Toan – Promotion 13

Page 11


2.3.1 Distance d'édition
La distance d'édition ed est une mesure de dissimilarité pour comparer des graphes qui
représente la séquence d'opérations élémentaires de coût minimum pour transformer un
graphe en un autre graphique par les opérations élémentaires de l'insertion, de la
suppression et de la substitution de nœuds ou d'arcs. Sous certaines conditions concernant
le coût des opérations élémentaires décrites dans [16], la distance d'édition entre graphes
est une métrique.
En pratique, le coût des opérations élémentaires est dépendant de l'application. Leur
détermination est en général effectuée soit par expertise humaine ou, plus rigoureusement,
par apprentissage artificiel comme cela est proposé dans [17].
En revanche, le calcul de la distance d'édition est réalisé par programmation dynamique et à

de ce fait, une complexité exponentielle dans le pire des cas, ceci interdit son usage pour la
recherche de plus proches voisins dans de grandes bases de données.
Une autre possibilité permettant d'évaluer la proximité entre objets complexes (ensembles,
séquences, graphes,. . .) pour comparer des objets ou des graphes.
Le coefficient de correspondance mc est la mesure la plus simple répondant à cette
définition et permettant de comparer des objets complexes o1 et o2

mc =

o1 ∧ o2
o1 ∨ o2

(5)

C'est en se basant sur ce concept que des mesures de dissimilarité exploitant le plus grand
sous-graphe commun (mcs) ont été proposées :

d (G1 , G2 ) = 1 −

mcs(G1 , G2
max( G1 , G2 )

(6)

d (G1 , G2 ) = 1 −

mcs(G1 , G2
G1 + G2 − mcs(G1 , G2

(7)


Dans les formules précédentes, |G| représente la taille du graphe G qui peut s'agir d'une
combinaison linéaire du nombre de nœuds et du nombre d'arcs du graphe G. Et mcs(G1,G2)
est le plus grand sous-graphe commun aux graphes G1 et G2, ce qui signifie que ce sousgraphe ne peut être étendu à un autre sous-graphe commun par quelque addition de nœud
ou d'arc que se soit.
La distance d'édition est liée au plus grand sous-graphe commun par la relation donnée par
l'équation

ed (G1 , G2 ) = G1 + G2 − 2 mcs(G1 , G2

(8)

Tant que le coût des fonctions associées à la distance d’édition qui respecté les conditions
présentées dans [16]. Cela signifie que la façon de calculer la taille de mcs de deux graphes
peuvent être utilisés pour calculer la distance d’édition le vice-versa. Ainsi, les deux calculs
ont la même complexité algorithmique. En raison de la difficulté à appliquer ces mesures car
leur complexité, plusieurs approches reposant sur des approximations ont été proposées
dans [19]. Trois autres groupes de techniques peuvent être employées pour évaluer la
similitude graphique, la théorie des graphes spectraux [19], les méthodes probabilistes [20]
ou des méthodes d'optimisation combinatoire [21], [22].

NGUYEN Quoc Toan – Promotion 13

Page 12


Parmi elles, [22] a proposé une méthode d'optimisation combinatoire offrant une distance
basée sur la mise en correspondance des arcs. Cette méthode approxime le maintien
topologique, induit par l'isomorphisme, par la recherche d'une mise en correspondance entre
les ensembles d'arcs de chacun des deux graphes en minimisant l’appariement de ces

ensembles.
Kriegel et Schönauer [22] montrent que, pour les graphes étiquetés, la distance de mise en
correspondance d'arcs respecte les propriétés de non-négativité (1), de symétrie (3) et
l'inégalité triangulaire (4). Récemment, Riesen et al proposait dans [24], une approximation
pour calculer la distance d’édition de graphes. Dans ce travail, la correspondance de deux
graphes s’appuie sur l’appariement d’un graphe bipartite.
La matrice des coûts pour les correspondants des étiquettes des nœuds différents qui sert
d'entrée pour l'algorithme hongrois [23] qui traite alors la matrice des coûts d'association des
nœuds et fournit la distance d'association des nœuds de G1 et G2 comme étant le coût de la
meilleure association avec une complexité en O(n3) dans le pire des cas, avec n le plus
grand nombre d'arcs.
Voici les étapes de la méthode hongroise qui traite la matrice des coûts pour trouver le coût
de la meilleure association des nœuds, nous proposons que deux graphes G1, G2 avec les
distances entre des nœuds de G1 et G2 sont comme dans le tableau 1
Table 1: Matrice des coûts de G1, G2

G2

Nœud 1
24
14
15
11

Nœud 1
Nœud 2
Nœud 3
Nœud 4

G1

Nœud 2
Nœud 3
10
21
22
10
17
20
19
14

Nœud 4
11
15
19
13

Étape 1: Réduction des lignes : créer une nouvelle matrice des coûts en choisissant le coût
minimal sur chaque ligne et en le soustrayant de chaque coût sur la ligne.
G1

G2

Nœud 1
Nœud 2
Nœud 3
Nœud 4

Nœud 1
14

4
0
0

Nœud 2
0
12
2
8

Nœud 3
11
0
5
3

Nœud 4
1
5
4
2

Réduit de
10
10
15
11

Table 2: étape 1 : réduction des lignes


Étape 2 : Réduction des colonnes : créer une nouvelle matrice des coûts en choisissant le
coût minimal dans chaque colonne et en le soustrayant de chaque coût dans la colonne.
G1

G2

Nœud 1
Nœud 2
Nœud 3
Nœud 4
Réduit de

Nœud 1
14
4
0
0

Nœud 2
0
12
2
8

Nœud 3
11
0
5
3


0
0
0
Table 3: étape 2 : réductions des colonnes

NGUYEN Quoc Toan – Promotion 13

Nœud 4
0
4
3
1
1

Page 13


Étape 3: Déterminer le nombre minimal de lignes nécessaires sur les lignes et les colonnes
pour couvrir tous les zéros. Si ce nombre est égal au nombre de lignes (ou colonnes), la
matrice est réduite; aller à l’étape 5. Si ce nombre est inférieur au nombre de lignes (ou
colonnes), aller à l’étape 4.
G1

G2

Nœud 1
Nœud 2
Nœud 3
Nœud 4
Réduit de


Nœud 1
14
4
0
0

Nœud 2
0
12
2
8

Nœud 3
11
0
5
3

Nœud 4
0
4
3
1

0
0
0
1
Table 4: étape 3 : déterminer le nombre minimal de lignes sur les lignes, colonnes pour couvrir tous les

zéros

Dans ce cas, le nombre minimal de lignes est de 3. Donc, on va à l’étape 4.
Étape 4:
- Trouver la cellule de valeur minimum non-couverte par une ligne.
- Soustraire cette valeur de toutes les cellules non-couvertes.
- Ajouter cette valeur aux cellules situées à l’intersection de deux lignes.
- Retourner à l’étape 3.
G1

G2

Nœud 1
Nœud 2
Nœud 3
Nœud 4

Nœud 1
14
4
0
0

Nœud 2
0
12
2
8

Nœud 3

11
0
5
3

Nœud 4
0
4
3
1

Table 5: étape 4 : Trouver la cellule de valeur minimum non-couverte par une ligne

Valeur minimum est 1

+1

G2

Nœud 1
Nœud 2
Nœud 3
Nœud 4

Nœud 1
15
4
0
0


-1

G1
Nœud 2
Nœud 3
0
12
11
0
1
5
7
3

Nœud 4
0
3
2
0

Table 6: étape 4 : recaler la valeur pour les cellules basées sur cette valeur minimum

Soustraire toutes les cellules non-couvertes par la valeur 1, Ajouter les cellules situées à
l’intersection de deux lignes par valeur 1
G1

G2

Nœud 1
Nœud 2

Nœud 3
Nœud 4

Nœud 1
15
4
0
0

Nœud 2
0
11
1
7

Nœud 3
12
0
5
3

Nœud 4
0
3
2
0

Table 7: étape 4 : déterminer le nombre minimal de lignes

Maintenant, le nombre minimal de lignes est de 4, Donc, on passe à l’étape 5


NGUYEN Quoc Toan – Promotion 13

Page 14


Étape 5 : Déterminer la solution optimale
G1

G2

Nœud 1
Nœud 2
Nœud 3
Nœud 4

Nœud 1
15
4
0
0

Nœud 2
0
11
1
7

Nœud 3
12

0
5
3

Nœud 4
0
3
2
0

Table 8: étape 5 : déterminer la solution optimale

Nœud 4, Nœud 1 ne pourrait pas être choisi car l’affectation de «O» ne serait pas de coût
minimal
Résultat:
G1
G2
Nœud 1
Nœud 2
10
Nœud 2
Nœud 3
10
Nœud 3
Nœud 1
15
Nœud 4
Nœud 4
13
Coût total

48
Table 9: le coût minimal de G1, G2

Donc le coût de la meilleure association des nœuds de G1 et G2 est 48
2.3.2 Distance entre signatures de graphe «graph probing »
Une technique plus rapide pour évaluer la similarité des graphes consiste à extraire une
description des graphes sous forme de vecteur de caractéristiques. Cette représentation,
appelée signature de graphe, proposée par [25], qui peut traiter des graphes contenant des
centaines de milliers de nœuds et d'arcs en un temps linéaire. Cette représentation permet
de décrire des graphes étiquetés et orientés.
Si G est un graphe étiqueté et orienté dont les étiquettes d'arcs appartiennent à l'ensemble
fini {l1, l2, . . ., la} de taille a, alors on appelle structure d'arc d'un nœud donné le 2a-uplet
d'entiers non négatifs {x1, . . ., xa, y1, . . ., ya} tel que le nœud possède exactement xi arcs
entrants étiquetés li, et yj arcs sortants étiquetés lj. Dans ce contexte, deux types de
signatures sont définies :
- Probe1(G) : un vecteur dont qui rassemble les nombres de sommets partageant
la même structure d’arcs, pour toutes les structures d'arcs rencontrées dans le
graphe
- Probe2(G) : un vecteur dont chaque composante est associé à une étiquette d'arc
qui représentant le nombre d'arcs ayant à une étiquette li

NGUYEN Quoc Toan – Promotion 13

Page 15


Figure 1: La distance entre signatures de graphe GP, (a) les graphes non orienté, sans étiquetage, (b) les
graphes orientés, sans étiquetage, (c) les graphes étiquetés, orientés

À partir de ces signatures et en se basant sur la norme L1, la distance entre signatures de

graphe « GP » (entre deux graphes G1, G2) est définie par :
GP (G1,G2) = L1(Probe1(G1), Probe1(G2)) +L1(Probe2(G1), Probe2(G2))
La distance entre signatures de graphe ne respecte que la non-négativité, la symétrie, et
l'inégalité triangulaire, mais pas l'unicité. En d'autres mots, GP est une pseudo-métrique et
deux graphes non isomorphes peuvent avoir les mêmes signatures.
D'autre part, Lopresti et Wilfong [25] présentent une relation intéressante liant la distance
d'édition et la distance entre signatures de graphe. À un facteur 4 près, la distance entre
signatures de graphe est un minorant de la distance d'édition quels que soient les graphes à
comparer
GP (G1, G2) ≤ 4.ED (G1, G2)

NGUYEN Quoc Toan – Promotion 13

(9)

Page 16


Figure 2: La distance entre deux graphes selon ED et GP, (a) les graphes non orienté, sans étiquetage, (b)
les graphes orientés, sans étiquetage, (c) les graphes étiquetés, orientés

Dans ce contexte, la topologie du graphe peut être en partie ignorée par compter le nombre
d'occurrences d'un ensemble de sous graphes (du nom d'empreintes digitales ou signatures
dans des contextes différents) de chaque graphe et de décrire les objets à comparer en tant
que vecteurs
A partir de l'idée originale dans [22] et [24], le coût minimum correspondant entre deux
ensembles d’éléments, les auteurs ont étendu ce modèle à des sous graphes, des objets
plus complexes et plus discriminants.

2.4 Symbol spotting

En générale, le problème « Symbole Spotting » peut être défini comme la localisation d'un
ensemble de régions d'intérêt d'un document image, qui sont susceptibles de contenir une
instance d'un certain symbole demandé sans le reconnaître explicitement. On parle alors de
localisation de symboles en contexte, ce terme s’oppose directement à la reconnaissance de
symboles pré-segmentés. La reconnaissance de symbole est plus que jamais un problème
qui est discuté dans la communauté scientifique [26]. Il y a un grand nombre d'approches ont
été proposées pour la reconnaissance des symboles. Parmi ces méthodes, on distinguera
celles fondées sur des descripteurs de formes [27-29]. Ils sont plutôt calculés sur le contour
de l’objet ou sur l'ensemble de l'objet. Ils sont robustes contre le bruit et les occlusions, mais
le document doit être clairement segmenté, ce qui est un problème, car les symboles sont
souvent intégrés à d'autres couches graphiques.
D'autres approches se basent sur la structure avec l’utilisation de graphe [30-35]. Parmi les
structures de données, les graphes sont généralement adaptés à la représentation des
symboles autorisant la restitution de la topologie des symboles. Fréquemment, un symbole
est décomposé en un ensemble de segments (ou de composantes connexes) et cet
ensemble d’éléments et leur relations spatiales entre ces composants sont représentés par
un graphe relationnel [voir section 5]. Le problème « Symbole Spotting » est maintenant
NGUYEN Quoc Toan – Promotion 13

Page 17


tourné en une question de mise en correspondance de graphes « Graph Matching » et
dépend de la manière de la construction de graphe.
Dans notre cas, nous proposons une méthode de type structurel pour la représentation des
symboles, c’est-à-dire, chaque nœud représente une composante connexe et il a été
étiqueté automatiquement par un algorithme de « clustering » appliqué sur un jeu de
descripteur de forme et les arcs représentent les relations spatiales entre des composantes
connexes (nous utilisons deux types d’étiquetage des arcs : les relations d'Allen
bidimensionnelles et les distances entre deux régions)


NGUYEN Quoc Toan – Promotion 13

Page 18


3 Etat de l'art
3.1 Les méthodes de construction de graphe
De nombreuses méthodes de reconnaissance de graphiques ont été développées pour la
reconnaissance des symboles graphiques, Ces approches sont catégorisées en plusieurs
familles : 2D HMM [36], Pixels Caractéristiques [37-38], à base de graphe [30-35], Signature
structurelle [39-40], Représentation hiérarchies de symbole [41-42]. Dans cette partie, nous
abordons les méthodes à base de graphe pour la reconnaissance des symboles graphiques.
D’abord, en 1996, B. T. Messmer and H. Bunke [31] proposent de representer les symboles
et les dessins par des graphiques attribués relationnelle. Les nœuds présentent les lignes
segmentées qui sont étiquetées par ses longueurs et les arcs établis entre les nœuds
signalent une relation d'adjacence entre les segmentations. Un arc est étiqueté par l’angle
entre deux segments.

Figure 3 : Graphiques attribués relationnelle, chaque nœud est comme une ligne segmentée, un arcs
établis la relation d’adjection entre deux segmentations (source[14])

Josep Liadós et al présentent dans [32] une méthode en utilisant des graphes d'adjacence
de régions (RAG). Dans ce cas, les auteurs utilisent des primitives de haut niveau extraits à
la suite d’un processus de segmentation. Une région fermée est identifiée à partir d’un
prototype de symbole qui est utilisé comme un nœud du graphe. L’arc lie deux régions
adjacentes. Le nœud est étiqueté en utilisant un descripteur de forme appliqué à la frontière
de la région concernée (chain code). L’arc est étiqueté par une chaîne commune entre deux
régions adjacentes. Une information sur la longueur et l’orientation de la région est aussi
intégrée dans le graphe.


Figure 4: Chaque nœud est une région fermée. L’arc lie deux régions adjacentes (source[32])

NGUYEN Quoc Toan – Promotion 13

Page 19


Dans l’article [33], les auteurs ont proposé un autre type pour créer des graphes, chaque
nœud est comme une composante connexe. Sur chaque composante connexe ils extraient
les caractéristiques de la rotation et de la translation invariante fonctionnalités basées sur
des moments de Zernike [43]. Les nœuds étiquettent automatiquement par l’algorithme de
clustering « k-medoids clustering » [44] basé des données de ces caractéristiques. Pour
construire des arcs, ils utilisent la famille de graphe « Voisinage basé sur un seuil de
distance », c’est-à-dire chaque couple de points (centres de boîte englobant de composante
connexe) se situant à une distance inférieure à un seuil t est liée par un arc dans le graphe
associé.

Figure 5: Graphe transaction, source [33]

Selon Rashid Jalal Qureshi et al [35] proposent une approche qui lie une méthode
structurelle et une méthode basée sur la capture des relations topologiques entre les
graphiques primitives. Après l’étape prétraitement on obtient une vectorisation en
quadrilatères qui représentent des lignes dans un dessin.

Figure 6: vectorisation de quadrilatères, source [45]

Chaque nœud du graphe correspond à un quadrilatère. Chaque quadrilatère a des
caractéristiques comme la longueur (l) de l'axe médian, les angles des deux vecteurs (v1,
v2), la largeur de chaque côté (w1, w2) et une zone d'influence. Tous les arcs sont

NGUYEN Quoc Toan – Promotion 13

Page 20


également associés à une étiquette en représentant le type de la relation topologique (Ljonction, S-jonction, jonction en T, X-intersection ou P-parallélisme) qui existe entre les deux
quadrilatères voisins.

Figure 7: La zone influence de quadrilatère et le graphe correspondant, source [45]

Et voici un exemple de construction d’un graphe à base cette approche

Figure 8: exemple de construction d’un graphe basé sur les relations topologique, source [35]

NGUYEN Quoc Toan – Promotion 13

Page 21


3.2 Les methodes de mise en correspondances des graphes
L’approche de Bunke
Cette approche permet de trouver un isomorphisme de sous-graphe à partir d'un symbole
pour un dessin sur une représentation compacte de la base de données du symbole.
L’idée principale de cette approche est de trouver les sous-structures communes entre les
symboles et afin de représenter les symboles en termes de sous-structures. De ce fait, le
symbole est divisé en composants. Le plus petit composant étant une simple ligne. Pour
chaque composant, on trouve des isomorphismes de sous-graphe entre ce composant et le
dessin. Le résultat de cette application est ensemble de sous-graphes isomorphes tel que
son cout d’édition soit inférieur une valeur seuil trecog
La fonction de coût pour des opérations d’édition est définie comme suit :

- Le coût de substitution d’un angle α1 à un angle α2 est (α1 – α2)2
- Le coût d’insertion d’un arc avec un angle α1 entre deux lignes avec la distance d
et angle α2 est (α1 – α2)2 ∗ d
- Le coût d’insertion d’un nœud dans le graphe de dessin est comme un variable
constante de 3
- Le coût de fusion de deux nœuds qui représente deux lignes segmentées en un
seul nœud (qui représente une segment de droite) est comme une variable
constante de zéro.
L’approche de Josep Liadós
Cette approche trouve des sous-graphes isomorphes tolérant à l’erreur entre le graphe
model et le graphe d’entrée. L'isomorphisme est calculé en fonction du coût minimum de
séquence d’édition pour transformer un RAG dans l'autre en définissant trois fonctions de
coût :
Le coût de substitution : substitution d'un noeud rM (région modèle) par un nœud rI (région
d’entrée), noté que rM → rI. Le coût de cette opération est calculée en fonction de la chaîne
de modifier la distance entre deux chaines.
Le coût de changement de structure (Shift cost) : pour mesurer la préservation de la
structure d’inter région.
Le coût d’échelle (scaling) : pour préserver le facteur d'échelle lorsque d’une nouvelle
région est intégrée dans la mise en correspondance.
L’avantage de cette approche est capable d’effectuer la correspondance entre les graphes
dégradés en un temps de calcul proche du polynomial malgré que la complexité théorique
reste exponentielle. On peut trouver la solution en quelques secondes pour les modèles
graphiques à moins de 10 régions et la contribution des graphes avec quelques centaines de
régions.
L’approche de Ramel
L'idée principale de cette méthode est de détecter les parties du graphique qui peuvent
correspondre à des symboles sans connaissance sur le type du document. De tels nœuds et
les arcs constituent le symbole de germe «symbol seeds ». Ensuite, les germes seront
analysés et regroupées pour générer des sous-graphes qui correspondent potentiellement à

des symboles dans le document image.
Pour comparer deux graphes étiquetés avec des attributs numériques sur les nœuds et des
arcs, ils proposent de calculer le score de similarité entre deux graphes (Mp) :

NGUYEN Quoc Toan – Promotion 13

Page 22


n
 m
ScMP =  ∑ (1 − ∆ Vi ) + ∑ (1 − ∆ E j ) −
j= 1
 i = 1

l
 k
∑ ωi+∑ ω

j= 1
 i= 1

'
j




 


Avec m est le nombre total de nœuds correspondants, n est le nombre total des arcs entre
eux. ωi, ω’j sont les poids associés à la division « split » de la i-ème et j-ème nœud dans le
graphe G et G' respectivement. ΔVi (ΔEj) correspond à la distance entre deux nœuds (arcs)
mappé, normalisées entre 0 et 1.
Il propose sept hypothèses (Les symboles sont composés des petits segments; Les
segments constituant un symbole ont des longueurs comparables; Deux segments
successifs avec un angle relatif loin de 90° ont une probabilité plus élevée de faire une partie
de symbole; Les symboles sont souvent composées de segments parallèles; Un symbole est
rarement liée à de plus de 3 autres segments; La plus courte des boucles sont souvent
correspondant à des symboles) [page 4, 33] pour construire le système de la
reconnaissance de symbole graphique. Il fonctionne bien seulement avec des documents
graphiques : circuits électroniques, la logique des diagrammes et des cartes d'architecture.
Les documents contenant des symboles qui ne respectent pas ces hypothèses ne peuvent
pas être analysées à l'aide du système proposé.
L’approche de Barbu
Cette approche utilise l'algorithme FSG [50] pour rechercher des sous-graphes fréquents.
Ces sous-graphes fréquents sont ensuite exploités pour construire une représentation des
images de document à base de sacs de symboles.
Il définie une distance permettant de comparer ces représentations. Considérons deux
images de documents A et B dont les représentations sont A = (a1, a2, . . ., at) et B = (b1, b2, .
. ., bt) où t est le nombre total de symboles du lexique constitué par l'étape de recherche des
sous-graphes fréquents. La mesure d (A, B) définie par

d ( A, B ) =

∑

∑

t


t

a

ab

i= 1 i i

2
i= 1 i

∑

t

2
i= 1 i

b

Représente une mesure de similarité basée sur le cosinus des deux représentations. En
effet, lorsque les vecteurs des représentations de A et B ont la même orientation, ce qui
signifie que les poids de chacun des symboles sont proportionnels, alors d (A, B) = 1. À
l'inverse, lorsque d(A,B) = 0, comme les poids sont positifs ou nuls, cela signifie que les deux
documents ne partagent aucun symbole en commun.
Ses travaux proposent une nouvelle approche pour la classification et l'indexation d'images
de document. Cette approche utilise des techniques de fouille de données pour l'extraction
de connaissances.
Les résultats sont assez bon et montrent également montré l'approche permettait de réaliser

une indexation des images à partir des symboles présents, alors même que ces symboles
sont connectés à d'autres éléments
Notre approche
Notre approche propose un autre type pour construire des graphes : « Voisinage basé sur k
plus proches voisins». Chaque nœud est comme une composante connexe. Sur chaque
composante connexe nous extrayons des caractéristiques basées sur les moments de Hu et
Shape Statistiques. Les nœuds étiquettent automatiquement par l’algorithme de clustering
« k-Mean » basé des données de ces caractéristiques. Les arcs sont étiquetés
automatiquement par les relations d'Allen bidimensionnelles ou la distance entre des
NGUYEN Quoc Toan – Promotion 13

Page 23


régions. Le problème reconnaissance de symbole est tourné en une question
d’isomorphisme de sous graphe, afin de trouver les sous-graphes qui correspondent à des
symboles graphiques. Nous extrayons le graphe de plan en des sous-graphes de longueur l.
Le résultat de notre application est ensemble de sous-graphes isomorphe en fonction de la
distance entre les sous-graphes et le graphe de symbole requête (si la distance est inférieur
une valeur seuil). Nous proposons une méthode de mise en correspondance de graphes
fondée sur l’assignement de sous-graphes de longueur l pour calculer la distance entre deux
graphes « voir la section suivante ».
L’avantage de notre : L'utilisation des moments de Hu et Shapes statistiques assurent que
deux composantes connexes (nœuds) situé dans le plan et le symbole sont même
morphologies ce qui doit être même étiquetage (à corriger cette phrase grammatiquement).
De plus, l’étiquetage des arcs basé sur les relations d'Allen bi-dimensionnelles adaptées
pour maintenir une invariance de la représentation aux transformations d'image.

3.3 Récaputulation des méthodes
Approche


Bunke

étiquetage
Nœud
- lignes
segmentées
- Longueurs
de linge
segmenté

Josep
Liadós

- région fermé
- chaîne de la
frontière de
région

Ramel

- composante
connexe
- des
moments de
Zernike

Barbu

Notre

approche

quadrilatères

- composante
connexe
- des
moments de
Hu, Shapes
statistique

Arc
- relation
d'adjacence entre
les
segmentations
- l’angle entre
deux
segmentations
- lié entre deux
régions
adjacentes
- chaîne commun
entre deux
régions
adjacentes
- seuil de
distance
- sans étiquetage
- relation

d'adjacence
- relation
topologique (Ljonction, Sjonction, jonction
en T, Xintersection ou Pparallélisme)
- Voisinage basé
sur k plus
proches voisins
- les relations
d'Allen
bidimensionnelles
ou la distance
entre des régions

NGUYEN Quoc Toan – Promotion 13

Distance

Application
specifique

Complexité

- coût d’édition :
substitution,
insertion, fusion

le dessin

Sous-linéaire


trois fonctions
de coût :
Substitution,
Shift cost, le
coût d’échelle

dessinés à la
main

Exponentielle

score de
similarité entre
deux graphes

circuits
électroniques,
la logique des
diagrammes
et des cartes
d'architecture

Exponentielle

mesure de
similarité basée
sur le cosinus
des deux
représentations


Electronique,
schémas
d'architecture,
cartes
d'ingénierie

Exponentielle

méthode de
mise en
correspondance
de graphes
fondée sur
l’assignement
de sousgraphes basée
sur la
« distance

Document
techniques,
schémas
d'architecture

n1.n23
- n1 est le
nombre de
composantes
connexes
- n2 est le
nombre de

nœuds des
sous-graphes

Page 24


d’édition »
PMDED et basée
sur le « Graphe
Probing »
PMDGP

En conclusion, dans cette partie, nous avons présenté des exemples de familles de graphes
qui sont dépendante du contexte dans lequel elles sont utilisées. Donc chaque
représentation est dédiée à une application particulière, il n'est pas possible de créer une
application dans le cas général. De plus, la façon d’établir relations spatiales entre ces
composants est différente, dans les cas de [31][35], les arcs établis entre les nœuds
signalent une relations topologiques entre les primitives graphiques, et [34] basé sur un seuil
de distance ou bien comme dans notre approche, le graphe est fondée sur un « Voisinage
basé sur k plus proches voisins». Dans la section suivante nous allons aborder le problème
de la correspondance de graphes fondée sur l’assignement de sous-graphes.

4 Une méthode de mise en correspondance de graphes fondée sur
l’assignement de sous-graphes
4.1 Définition : Décomposition en sous-graphes

Figure 9: La décomposition en sous-graphes. p1, p2, p3, p4 est des sous-graphes d’extractions de
longueur 1 qui associés à chaque nœuds du graphe G

Soit G est un graphe attribué et ses étiquettes d'arcs appartiennent à l'ensemble fini {l1, l2, ...,

la}. P est un ensemble de sous-graphes d’extractions de longeur l qui est associés à chaque
nœud du graphe G. Un sous graphe p est défini comme une paire <Vi, Hi>, où Hi est
l’ensemble des arcs où leurs sommets terminés correspondants à partir d’un sommet racine
Vri.
Dans ce sens, un sous-graphe représente une information locale, une structure « étoile »
d’un nœud racine. La correspondance de ces sous-graphes devrait conduire à un
rapprochement de la correspondance de graphe. Le sous-graphe d'extraction se fait par

NGUYEN Quoc Toan – Promotion 13

Page 25