Mise en correspondance de Graphes

Les graphes sont des outils mathématiques utilisés dans de nombreux domaines pour modéliser les problèmes à résoudre. S’il l’on devait donner une origine à cette théorie, ce serait celle introduite par Euler au 18ème siècle avec le problème des ponts de Königsberg. Depuis, elle a donné naissance à de multiples techniques dans de nombreux domaines, en mathématique, automatique, algorithmique, biologie, chimie, etc. et plus récemment en reconnaissance des formes. Cette théorie a deux principaux objectifs. Le premier est d’orir un modèle pour représenter le problème, généralement l’ensemble des possibilités. Dans notre contexte, le problème est la mise en correspondance d’éléments dans les images. Dans ce cas, le graphe est une représentation des diérents éléments et de leurs relations binaires entre eux, par exemple l’ensemble des régions de l’image et les relations d’adjacence.

Le deuxième objectif de cette théorie est d’orir des outils pour permettre de trouver les meilleures possibilités dans le but de résoudre un problème. Dans notre contexte, nous nous intéressons aux outils qui permettent de comparer deux ensembles de possibilités (i.e. les graphes). Par exemple, rechercher les combinaisons de régions les plus similaires entre deux images. Dans ce chapitre, nous commencerons par présenter les diérentes Définitions et notations qui sont nécessaires pour la bonne compréhension des techniques présentées dans cette thèse. Puis, nous présenterons deux grandes familles de méthodes de comparaison de graphes. Enn, nous nous appuierons sur ces présentations an de motiver nos choix pour la recherche d’images.

Théorie des Graphes

 Nous présentons dans cette section des Définitions et notations couramment utilisées dans la littérature sur la base des travaux de Berge[1].

Définition 2.1.1. Graphe non orienté. Un graphe non orienté G = (V, E) est constitué d’un ensemble de sommets V et d’un ensemble d’arêtes E ⊆ V × V . Une arête est une paire non ordonnée de deux sommets. Un exemple de graphe non orienté est présenté en Figure 2.1(a).

Définition 2.1.2. Graphe orienté. Un graphe orienté G = (V, E) est constitué d’un ensemble de sommets V et d’un ensemble d’arcs E ⊆ V × V . Un arc est un couple ordonné de deux sommets. Un exemple de graphe orienté est présenté en Figure 2.1(b). Les arcs d’un graphe orienté, sont représentés sous forme de èche et ne permettent le déplacement que dans un seul sens. On les appelle arcs pour les distinguer des arêtes non orientées. On utilise les parenthèses (,) pour écrire le couple de sommet. Définition 2.1.3. Ordre. L’ordre d’un graphe G est le nombre de sommets de ce graphe. L’ordre du graphe de la Figure 2.1(b) est 3.

Définition 2.1.4. Complétude. Un graphe est complet si tous ses sommets sont reliés deux à deux. Définition 2.1.5. Boucle. Une arête ou un arc (v,v) est appelée boucle. L’arête en bas à gauche du graphe en Figure 2.1(b) est une boucle.

Définition 2.1.6. Adjacence. Deux sommets sont dits adjacents s’il existe dans le graphe une arête (ou un arc) les reliant. Les sommets 1 et 2 de la gure 2.1(c) sont adjacents. 12 2.1 Théorie des Graphes Définition 2.1.7. Chaîne. Une chaîne est dénie par une suite de sommets adjacents. La suite de sommets (2, 1, 3) du graphe de la gure 2.1(c) constitue une chaîne. La chaîne (3, 1, 2) est une écriture diérente de la même chaîne.

Définition 2.1.8. Chemin. Un chemin est une chaîne orientée. Les chemins h = (2, 1, 3) et h 0 = (3, 1, 2) du graphe de la gure 2.1(c) sont deux chemins diérents. On notera |h| la longueur d’un chemin h, i.e son nombre d’arêtes, par exemple |h 0 | = 2. Définition 2.1.9. Cycle. Un cycle est une chaîne dont les deux sommets extrémités sont identiques. La chaîne h = (2, 1, 3, 2) et h 0 = (2, 1, 2) sont des cycles. Définition 2.1.10. Connexité. Un graphe est connexe lorsque, pour tout couple de sommets, il existe une chaîne qui les relie. Les graphes des gures 2.1.1 sont connexes. Définition 2.1.11. Arbre. Un arbre est un graphe non orienté, connexe et sans cycle. Les graphes des gures 2.1(b) et 2.1(c) sont des arbres. Définition 2.1.12. Graphe valué (ou étiqueté). Les graphes valués ont leurs sommets ou leur arêtes qui portent de l’information