Gestion des données géographiques : Propositions des modèles et un prototype d’interrogation par croquis

Télécharger le fichier pdf d’un mémoire de fin d’études

Modes de représentation

La perception de l’information géographique est double. Elle peut être discrète ou continue. La vue discrète permet généralement de décrire les objets géographiques ayant un contour bien délimité, alors que la vue continue se prête plus à la description de phénomènes dont la limite est parfois mal définie.
De ces deux vues de l’espace découlent deux modes de représentation (en anglais « vector » et « raster »). Ces deux modes présentent de grandes différences, en ce qui concerne leurs caractéristiques. Malgré cela, beaucoup de SIG disposent d’algorithmes de conversion d’un mode à l’autre [Demers 1997]. Une présentation de ces deux modes se retrouve dans l’annexe A.
Ces deux modes de représentation sont complémentaires. Une même information localisée à une position géographique pourrait être traduite dans les deux modes. Ses différentes représentations se superposent, laissant à l’utilisateur le soin de choisir en fonction de son usage la représentation qui lui convient le mieux.
Malgré l’importance et la quantité des données géographiques qui sont représentées selon le mode matriciel, nous nous intéressons dans notre recherche aux données représentées selon le mode vectoriel. La raison de ce choix est liée au fait que nous cherchons à faciliter l’accès à l’information pour des utilisateurs non experts. Le raisonnement de ces derniers assimile plus facilement la représentation vectorielle, plus proche de la réalité puisqu’elle se base sur une projection directe du monde réel sur la carte, que la représentation matricielle, plus adéquate aux personnes familiarisées aux concepts de SIG puisqu’elle nécessite des capacités d’interprétations spécifiques des paramètres techniques tels que la couleur.
Par ailleurs, l’accès à l’information doit généralement être simple, rapide et efficace [Lewis 1995], ce qui exige une adaptation de l’interface utilisateur pour ce type de données. Par conséquent, la recherche dans l’interaction entre l’homme et la machine est cruciale dans ce contexte. Dans la section suivante nous présentons un état de l’art de l’interaction avec les SIG, et la possibilité d’améliorer celle-ci afin de permettre à l’utilisateur d’atteindre facilement l’information nécessaire.

Interaction avec les SIG

Le dialogue entre l’utilisateur et l’ordinateur est réalisé par l’intermédiaire d’une interface qui gère l’aller-retour de l’information entre le monde mental du premier et le monde technique du second [Knob 2005].
Les méthodes d’interaction avec les SIG ne diffèrent pas de celles qui sont utilisées dans d’autres domaines. Tandis que ces méthodes sont adaptées à la plupart des applications, telles que le traitement de texte et d’autres applications bureautiques, elles sont souvent vues comme des opérations fastidieuses dans les SIG [Egenhofer et al. 1993]. Les utilisateurs dépensent beaucoup d’efforts pour interagir avec ces applications, puisque les principes fondamentaux sur lesquels les SIG ont été conçus ne sont pas à l’origine spatiaux [Blaser et al. 2000]. Cela rend leurs interfaces très spécialisées et complique leurs modes d’interaction qui nécessitent des compétences particulières. Cette situation est devenue inacceptable et nécessite une solution pertinente pour plusieurs raisons.
Les données spatiales sont de plus en plus employées dans une variété de nouveaux domaines, telles que la biologie ou la géolocalisation. Dans ces domaines, les utilisateurs sont souvent peu familiarisés avec les concepts de SIG. Cette diversification conduit à des nouveaux besoins pour des utilisateurs de différents milieux professionnels. Si une interface est très spécialisée, la probabilité est élevée que peu de personnes soient en mesure de l’utiliser, sans la nécessite d’apprendre le mode d’utilisation spécifique de ce système. Par conséquent, les applications de SIG bénéficieront particulièrement du développement d’une interface plus simple et plus puissante qui permet aux utilisateurs de choisir le type d’interaction en fonction de leur connaissance et de leur préférence.
Par ailleurs, les tendances à la miniaturisation des dispositifs de calcul, de mobilité, et d’intégration de « l’intelligence » se poursuivront à l’avenir. La recherche dans le domaine des IHM évolue car il est impossible d’interagir avec tous ces dispositifs avec un clavier et une souris (par exemple le GPS d’une voiture) [Weiser 1998]. L’utilisation croissante de ces appareils exige que leurs interfaces soient plus simples et plus intuitives, de sorte qu’elles puissent être exploitées par des personnes ayant différents niveaux de compétences. Les utilisateurs devraient pouvoir librement choisir et changer leur manière d’interaction en fonction de leurs capacités et leurs situations.
Dans la section suivante, nous présentons les différentes méthodes d’interaction, en mettant l’accent sur leur adaptation avec les systèmes de recherche d’information spatiale.

Étude de l’adéquation des modalités d’utilisation d’un SIG

Les modalités comprennent tout type de sensation, y compris la vision et l’audition, et les différents modes d’expression tels que l’écriture, la parole ou les gestes que les gens utilisent pour communiquer entre eux [Wexelblat 1995]. Dans la suite, nous mettons l’accent sur les deux modalités les plus adéquates qui permettent à un utilisateur d’émettre et recevoir l’information spatiale. Une présentation plus détaillé qui couvre toutes les modalités possibles se trouve dans l’annexe B.

Bilan sur des modalités d’utilisateur

L’interaction entre l’utilisateur et l’ordinateur est assez limitée par rapport à la richesse de formes de la communication entre les êtres humains. La plupart des systèmes informatiques ne permettent aux utilisateurs que de pointer par la souris ou de taper du texte pour exprimer leurs intentions ou leurs problèmes. Bien que beaucoup d’utilisateurs aient accepté cette situation, ils sont souvent insatisfaits.
Afin de trouver une solution à cette insatisfaction pour les systèmes de recherche d’information spatiale, nous avons présenté les modalités d’interaction et étudié leur capacité à décrire ce type d’information. Nous avons justifié le fait que le croquis est une modalité universellement comprise et bien adaptée pour décrire les scènes spatiales. De plus sa capacité à transmettre implicitement une quantité importante d’information aide à diminuer l’effort de l’utilisateur pour exprimer ses besoins.
Par conséquent, permettre à l’utilisateur de griffonner un croquis afin d’exprimer ses besoins d’information peut être une solution à cette insatisfaction dans ces systèmes. Dans la section suivante nous présentons les intérêts d’utiliser les croquis dans l’interrogation spatiale et les différents types de requêtes qui peuvent s’exprimer par cette modalité.

L’intérêt d’utiliser les croquis dans l’interrogation spatiale

Un utilisateur doit avoir une première idée de ce qu’il recherche, afin de pouvoir formuler sa question. Contrairement à des « questions » ordinaires (entre humains), les requêtes de bases de données doivent être exprimées dans des langages bien définis. Ces derniers ont des syntaxes fixes, ce qui les rend incompatibles avec le modèle mental d’interrogation de l’être humain. Le fossé entre ces deux modèles est élargi lorsque des composantes spatiales sont introduites dans les questions. Afin de combler cet espace, il faut trouver une autre méthode d’interrogation qui se rapproche de la manière dont les gens pensent.
L’intégration du croquis dans l’interface d’interrogation de SIG est une excellente proposition à cette fin. En effet, l’utilisation de dessins est la meilleure façon de décrire une configuration spatiale ciblée. L’intégration du croquis permet de couvrir tout le spectre d’interrogation spatiale, parce que l’utilisateur a la possibilité de choisir la modalité (soit verbale soit par croquis) qui lui convient pour exprimer sa question. Les expressions verbales sont utilisées pour décrire des attributs non spatiaux tels que les noms ou les fonctionnalités, alors que le croquis est approprié lorsque l’idée initiale est « orientée » spatiale dans le modèle mental de l’utilisateur.

Interfaces utilisateur basées sur le croquis

Dans les systèmes informatiques, les croquis à main levée sont généralement utilisés soit dans l’étape de conception soit dans les systèmes de recherche d’information. Dans le premier cas, chaque objet dessiné doit être transformé en un symbole appartenant à un ensemble prédéfini. Ces applications sont très efficaces lorsque le nombre des symboles est limité. La conception des circuits électroniques [Gross 1996] ou d’une interface utilisateur [Landay et al. 2001] par croquis sont des bons exemples.
Dans les systèmes de recherche d’information, les croquis sont utilisés comme des requêtes pour interroger des bases d’images. Chaque croquis est une expression visuelle décrivant un seul objet recherché ou une configuration spatiale (qui regroupe plusieurs objets). Un tour d’horizon sur les systèmes les plus importants sera présenté dans ce qui suit.
À l’université de Munich Oettingenstr, en Allemagne, [Berchtold et al. 1997] a présenté un prototype d’un système de recherche d’information « S3 » pour une base de dessins industriels. Ce prototype supporte trois types d’interrogation : 1) par exemple en choisissant un dessin de la base, 2) par croquis en dessinant l’objet ou une partie de l’objet désiré, 3) par thématique en spécifiant certains attributs de l’objet. La figure I. 2 montre un exemple d’interrogation par croquis. La fenêtre gauche présente la requête de l’utilisateur, alors que la fenêtre droite présente les résultats obtenus pour ce croquis.

Étude analytique des comportements d’utilisateurs

Bien que les habitudes des personnes qui griffonnent diffèrent considérablement de l’une à l’autre, la plupart des gens sont capables de dessiner un croquis ou de comprendre celui dessiné par quelqu’un d’autre. La raison de cette interprétation commune peut être l’utilisation de structures, symboles ou stratégies identiques lorsque les gens font leurs dessins. Il est également courant que les croquis qui sont générés dans le même domaine d’application aient une forte corrélation. Pour ces raisons, nous nous basons sur une étude analytique des croquis faite dans le domaine géographique [Blaser 2000]. La principale motivation de cette analyse est de comprendre les habitudes des utilisateurs quand ils font leurs dessins. Cette compréhension est une étape nécessaire afin de développer des techniques d’interprétation automatique des croquis.
L’étude a été menée sur des croquis dessinés par 32 participants. Il est demandé à chacun de dessiner trois croquis en se basant sur des descriptions écrites. Afin de réduire la complexité de l’étude, l’analyse se concentre sur les structures élémentaires des croquis (les objets dessinés, les relations binaires entre les composants et l’annotation). D’un point de vue abstrait, un croquis est un ensemble de coups de pinceau. Ces coups ne sont généralement pas considérés individuellement, mais ils sont regroupés pour former des objets. En se basant sur les géométries de ces objets et leurs configurations spatiales, il est possible de définir les concepts topologiques, métriques et directionnels d’un croquis.
Cette information est totalement suffisante pour comparer les configurations spatiales entre elles et évaluer leur similarité. Toutefois, l’expressivité d’un croquis peut être augmentée si l’aspect sémantique est pris en compte. Les gens ont souvent recours à des annotations écrites afin d’ajouter un sens spécifique à un objet.
Les trois sous-sections suivantes décrivent les résultats de l’analyse de ces éléments constitutifs d’un croquis.

Objets dessinés

Le terme « objet dessiné » correspond à une multitude de représentations, car il n’existe pas de règles strictes régissant la démarche utilisée pour représenter les objets du monde réel dans un croquis. Par exemple, une maison dans un croquis pourrait être présentée par un cercle, un carré ou par sa façade. Donc, il n’est pas trivial de comprendre le sens d’un objet dessiné sans savoir la démarche utilisée par les gens pour dessiner leurs croquis. D’autre part, il existe certainement des modèles communs pour faire les croquis, parce que sinon personne ne pourrait interpréter un croquis dessiné par quelqu’un d’autre. Dans la suite nous présentons les observations obtenues par l’étude de [Blaser 2000] concernant les objets dessinés et les règles qui peuvent être construites en se basant sur ces observations.
Observation 1 : La plupart des objets dessinés sont représentés par des formes simples telles que des lignes ou des rectangles.
Cette observation montre que les gens ont une tendance à garder leurs croquis simples et les objets dessinés abstraits. Elle indique également que le contexte et la configuration d’un croquis sont plus importants que la représentation de chaque objet.
Observation 2 : Les deux classes les plus utilisées (les bâtiments et les routes) couvrent 53% de tous les objets dessinés et les neuf premières classes les plus fréquentes représentent 90% de tous les objets.
Il est clair que ces classes varieront avec le changement du domaine d’application. Cependant, on peut estimer que pour un champ d’application spécifique, il y a un nombre limité de classes d’objets nécessaires pour interpréter une scène dessinée.

Relations spatiales

Le terme « relation » peut être défini comme « association naturelle, logique, ou virtuelle entre deux ou plusieurs entités qui sont liées l’une à l’autre ». L’interprétation d’une relation est généralement basée sur la perception d’une situation réelle par des êtres humains, ce qui la rend subjective. Pour décrire plus objectivement les relations, des théories ont été élaborées mettant l’accent sur les caractéristiques spécifiques de ces relations. Des théories au sujet des relations spatiales visent à décrire les relations entre les objets dans l’espace. Une relation spatiale binaire est un cas particulier où seulement deux objets sont impliqués. Ces dernières sont souvent les plus utilisées en raison de leur simplicité. Le nombre de relations binaires possibles dans une configuration spatiale est assez important. Il augmente de façon polynomiale avec le nombre d’objets et il est donné par l’équation [1] pour n objets : M = n * ( n – 1 ) / 2 [1]
Dans la suite nous présentons les observations obtenues par l’étude concernant les relations spatiales et les règles qui peuvent être construites en basant sur ces observations.
Observation 1 : Les objets dans un croquis sont généralement disjoints. Les relations non disjointes qui ont été enregistrées au cours de l’étude ne représente que 8,2% du nombre total possible des relations topologiques.
En fait, la topologie n’est pas assez expressive pour décrire les situations où les objets sont disjoints. Dans de tels cas, les relations métriques et directionnelles relatives peuvent être utilisées pour décrire et préciser les configurations spatiales.
Observation 2 : les relations métriques et directionnelles sont utilisées de manière implicite, ce qui les rend imprécises et approximatives.
L’utilisation de cette information pour décrire une configuration spatiale nécessite une étape de réduction de l’imprécision.

Concepts et termes de base

Un graphe fini G = (V, E) est défini par deux ensembles : un ensemble fini V = {v1, v2,…, vn} dont les éléments sont appelés noeuds, et un ensemble fini E = {e1, e2,…, em}  V × V, dont les éléments sont appelés arêtes. L’ordre du graphe est le nombre de noeuds dans ce graphe |V| = n. Si deux noeuds vi et vj  V sont liés par une arête e0 = (vi, vj)  E alors ils sont dits voisins ou adjacents. Les arêtes sont dites non orientées quand elles n’ont pas de direction. Un graphe G0 ne contenant que ce type d’arêtes est qualifié de « non orienté ». Lorsque les arêtes ont des directions, c’est-à-dire que (vi, vj) et (vj, vi) peuvent être distinguées, le graphe est dit orienté. Dans cette thèse nous nous intéressons aux graphes non orientés, mais notre méthode d’appariement peut être également appliquée aux graphes orientés. En outre, un graphe G0 = (V0, E0) est complet lorsque, pour toute paire de noeuds vk et vl  V0, il existe une arête ej = (vk, vl)  E0.
Les arêtes et les noeuds d’un graphe peuvent apporter des informations : lorsque cette information est une étiquette simple (par exemple un nom ou un numéro), le graphe est appelé « graphe étiqueté ». Dans l’autres cas (les arêtes et les noeuds portent d’autres informations), le graphe est appelé « graphe attribué ».
Un chemin entre deux noeuds vi et vj  V est une séquence non vide de k différents noeuds {u0, u1, …; uk} où (u0 = vi et uk = vj) et (ul-1, ul)  E, l = 1, …, k. Enfin, un graphe G0 est dit acyclique lorsqu’il n’y a pas de cycles entre ses noeuds, indépendamment du fait que ce graphe est orienté ou non.
Dans la section suivante nous présentons la justification de l’utilisation du graphe pour représenter les données spatiales, en particulier pour les systèmes de recherche d’information spatiale.

Représentation des données spatiales par graphes

Un noeud d’un graphe peut représenter tout type d’information. De plus, chaque noeud peut être décrit par un ensemble de caractéristiques. Les informations décrivant les relations entre ces noeuds sont exprimées par un ensemble d’arêtes, avec ou sans valeurs associées. Par exemple une arête peut exprimer une relation topologique, métrique, directionnelle ou temporelle. Les raisons menant à utiliser le graphe dans la présentation des données spatiales peuvent se résumer par les points suivants :
– le graphe est bien adapté pour présenter une configuration spatiale : analogie entre noeuds/arêtes et objets/relations ;
– les propriétés d’invariance. Par exemple, la présentation par graphe d’une configuration spatiale reste la même si elle est translatée, pivotée ou transformée en son image inversée.
Utiliser les graphes pour le stockage des informations spatiales est une proposition judicieuse. Toutefois, cela pose la question suivante : comment prendre en compte les besoins d’un utilisateur exprimant ses requêtes géographiques à l’aide d’un croquis ? En effet, un croquis symbolise une configuration géographique, par conséquent il peut être également représenté par un graphe. Ensuite, une méthode de comparaison entre graphes peut être utilisée afin d’identifier l’appartenance d’un croquis à un ensemble de structures déjà connues ou tout simplement pour trouver des structures semblables (c’est le cas dans notre travail). Ce type d’opération se nomme « méthode d’appariement entre graphes ». La question qu’il convient alors de se poser est : comment modéliser le concept de ressemblance ?
Dans la section suivante nous présentons une classification des méthodes d’appariement entre graphes issues de la littérature et un tour d’horizon pour les importantes méthodes utilisées.

Définition et classification des méthodes d’appariement entre graphes

L’appariement entre graphes est le processus qui consiste à rechercher d’une correspondance entre les noeuds et les arêtes de deux graphes, tout en assurant la satisfaction des certaines contraintes.
Généralement, les méthodes d’appariement sont divisées en deux grandes catégories : la première contient les méthodes d’appariement exact qui nécessitent une correspondance stricte entre les deux graphes ou au moins entre des sous-parties. La deuxième catégorie définit les méthodes d’appariement inexact, où une mise en correspondance peut se produire entre deux graphes même s’ils sont différents dans une certaine mesure.
Dans les deux sous-sections suivantes, nous présentons respectivement la définition de chacune de ces catégories et un état de l’art des méthodes associées regroupées selon leurs algorithmes de base.

Appariement exact

L’appariement exact est caractérisé par le fait que la connexité entre les noeuds doit être préservée : si deux noeuds (du premier graphe) sont liés par une arête, ils correspondent à deux noeuds (du deuxième graphe) qui sont aussi liés par une arête.
Nous détaillons les méthodes d’appariement exact de la forme la plus stricte à la plus relâchée. Dans la première, le « graphe isomorphe », la condition de connexité doit être vérifiée dans les deux sens (l’application doit être bijective). En d’autres termes, une correspondance « un à un » doit exister pour chaque noeud du premier graphe et chaque noeud du deuxième graphe. Une forme moins exigeante est le « sous-graphe isomorphe » qui correspond à un isomorphe entre l’un des deux graphes et un sous-graphe de l’autre. Certains auteurs comme [Wong et al. 1990] ont utilisé le dernier terme dans un sens plus faible, en relâchant la contrainte de la préservation de connexité dans les deux sens. Ce type d’appariement est appelé par d’autres auteurs le « monomorphe » [Ghahraman et al. 1980]. Ceci exige que chaque noeud et chaque arête du premier graphe soit associé respectivement à un noeud et une arête distincts du second. Cependant, le deuxième graphe peut avoir des noeuds et des arêtes supplémentaires. Une forme encore plus faible de l’appariement exact est « homomorphe », qui relâche la contrainte concernant le fait que les noeuds du premier graphe doivent être projetés sur des noeuds distincts du second, par conséquent la correspondance peut être du type « plusieurs à un ». Enfin, un autre type d’appariement cherche une isomorphe d’un sous graphe du premier avec un sous graphe du second. Telle correspondance n’est pas définie de façon unique, le but de l’algorithme est de trouver le plus grand sous-graphe pour lequel une telle correspondance existe. Par conséquent, ce problème est connu dans la littérature sous la désignation « rechercher le sous-graphe commun maximal » (SCM) entre deux graphes. En fait, il existe deux manières de définir le maximum : dans la première, le maximum fait référence au nombre de noeuds, alors que dans la seconde, c’est le nombre d’arêtes qui est pris en compte.
La plupart des algorithmes d’appariement exact sont basés sur une certaine forme d’arbre de recherche. D’autres techniques sont également utilisées comme la théorie des groupes, l’arbre de décision, etc. Dans la suite nous présentons les travaux les plus connus qui ont abordé l’appariement exact. Ils sont regroupés en deux catégories : la première pour les algorithmes qui sont basés sur l’arbre de recherche et la seconde pour les autres techniques.

Arbre de recherche

L’idée de base de ces techniques est qu’un appariement partiel (initialement vide) est itérativement élargi en y ajoutant de nouvelles paires de noeuds appariés. Les nouvelles paires doivent :
– assurer leur compatibilité avec les contraintes imposées par le type d’appariement souhaité ;
– prendre en compte les paires déjà appariées dans l’appariement partiel ;
– élaguer le plus tôt possible les chemins infructueux.
En fin de compte, soit l’algorithme trouve un appariement complet, soit il atteint un point où l’appariement partiel ne peut plus être élargi. Dans le dernier cas, l’algorithme fait un marche arrière « retour sur trace » (en anglais « backtracking ») : annule les derniers ajouts jusqu’à trouver un appariement partiel pour lequel une extension alternative est possible. Si toutes les possibilités qui satisfaisons les contraintes ont été déjà essayées, l’algorithme s’arrête (l’appariement entre ces graphes n’est pas possible).
Plusieurs stratégies de mise en oeuvre de ce type d’algorithme ont été utilisées. La plus simple est « la recherche en profondeur d’abord » qui requiert moins de mémoire que d’autres. De plus, il convient très bien à une formulation récursive. Une propriété intéressante de cette stratégie est qu’il peut facilement prendre en compte les attributs des noeuds et des arêtes. Ceci est très important lorsque les attributs jouent un rôle dans la réduction du temps d’appariement.
L’algorithme d’Ullman [Ullman 1976] est le premier et le plus connu de cette famille. En dépit de son ancienneté, il est encore couramment employé. Cet algorithme aborde les problèmes d’isomorphe, du sous-graphe isomorphe et du monomorphe. L’auteur a suggéré également une manière de l’employer pour le problème de SCM, bien que sa nature le fasse moins adaptée à ce type de problème. L’auteur a proposé une procédure de raffinement qui utilise une matrice des futures paires possibles de noeuds à apparier afin d’élaguer les chemins infructueux. A chaque étape, les paires qui ne sont pas compatibles avec l’appariement partiel seront supprimées. [Ghahraman et al. 1980] a proposé un autre algorithme pour le cas du monomorphe. Les auteurs ont utilisé une technique semblable à celle de [Ullman 1976] pour élaguer l’espace de recherche. Dans cette technique, un « netgraphe » est obtenu à partir du produit cartésien des noeuds des deux graphes à apparier. Les auteurs ont prouvé que, si deux graphes sont monomorphe, leur « netgraphe » doit satisfaire deux conditions : une condition nécessaire forte et une condition nécessaire faible (mais plus facile à vérifier). De ces conditions dérivent deux versions d’algorithme (sur lesquelles les conditions sont utilisées pour détecter les solutions infructueuses). Un inconvénient majeur de cet algorithme est que le « netgraph » est représenté en utilisant une matrice de taille n2 * n2, où n est l’ordre du plus grand graphe. Par conséquent, cet algorithme ne peut être utilisé que pour des petits graphes.
Un algorithme plus récent pour le cas de l’isomorphe et du sous-graphe isomorphe est l’algorithme de VF [Cordella et al. 2000]. Les auteurs définissent une méthode basée sur l’analyse des ensembles de noeuds qui sont adjacents à ceux déjà pris dans l’appariement partiel. Selon [De Santo et al. 2003], cette méthode est assez rapide, ce qui a mené à une amélioration significative du temps d’appariement (dans des nombreux cas) par rapport aux autres algorithmes. Dans [Cordella et al. 2001] les auteurs ont proposé une modification de cet algorithme afin de réduire l’espace mémoire nécessaire. Cette amélioration rend cet algorithme intéressant pour travailler avec les grands graphes.
Enfin, l’arbre de recherche a aussi été utilisé pour le problème de SCM. Les algorithmes les plus célèbres sont cités dans [Bron et al. 1973] et [Balas et al. 1986]. La possibilité d’utiliser les algorithmes parallèles dans le problème de SCM a été étudiée dans [Shinano et al. 1998].

Autres techniques

Nauty [Mckay 1981] est probablement l’algorithme pour les graphes isomorphes le plus intéressant qui n’est pas basé sur l’arbre de recherche. Il est considéré par beaucoup d’auteurs comme l’algorithme pour les graphes isomorphes le plus rapide disponible jusqu’à présent. Il est basé sur la théorie des groupes. En fait, Il utilise certains résultats provenant de ce cadre théorique pour construire « le groupe automorphe » pour chaque graphe. À partir de ce group, un étiquetage est dérivé, qui introduit un ordre pour chaque noeud. Cet ordre est défini de façon unique pour chaque classe de graphe isomorphe. Ainsi, l’isomorphe de deux graphes peuvent être mesuré en vérifiant simplement l’égalité des matrices d’adjacence de leurs formes étiqueté. Cette vérification de l’égalité peut être faite en O(n2), mais la construction de l’étiquetage nécessite un temps qui est dans la plupart des cas exponentiel. D’ailleurs, cet algorithme a généralement une performance meilleure comparativement aux autres. En effet, il a été prouvé que, dans certaines conditions, il peut dépasser en performance d’autres algorithmes (comme le VF2) mentionnés ci-dessus [Foggia et al. 2001]. Par contre, il est malheureusement impossible d’exploiter les attributs des noeuds et des arêtes dans le processus d’appariement.
Un autre algorithme qui s’intéresse aux graphes isomorphes et au sous-graphe isomorphe a été présenté en [Messmer 1995]. Cette méthode est conçue afin de faire l’appariement entre un graphe et une base de graphes. Elle est basée sur une décomposition récursive de chaque graphe de la base dans des sous graphes plus petits, jusqu’à arriver à un niveau trivial (un noeud). Le processus d’appariement exploite le fait que certaines parties sont communes à plusieurs graphes dans la base, afin d’éviter la répétition de leur comparaison avec le graphe requête. De cette façon, le temps total d’appariement a une dépendance linéaire avec le nombre de graphes de la base.
Les auteurs de [Messmer et al. 1997] ont proposé un algorithme plus performant pour l’isomorphe et le sous-graphe isomorphe entre un graphe et une base de graphes. En phase de prétraitement, un arbre de décision est construit à partir des graphes de la base. En utilisant cet arbre, un graphe d’entrée peut être comparé à toute la base en O(n2) par rapport à la taille de ce graphe, et indépendamment du nombre de graphes dans la base. Une extension de cet algorithme pour SCM a été présentée dans [Shearer et al. 1997]. Plus récemment, les mêmes auteurs ont également proposé une extension de cette méthode dans [Shearer et al. 2001]. Cette extension permet de prendre en compte une séquence de graphes qui évoluent lentement au fil du temps. Il y a bien sûr un coût lié à la performance de cet algorithme :
– la phase de prétraitement nécessite un temps exponentiel par rapport au nombre de noeuds des graphes dans la base ;
– un autre problème concerne l’espace nécessaire pour stocker l’arbre de décision qui est aussi exponentiel par rapport au nombre de noeuds.
Pour ces raisons, cet algorithme n’est pratiquement applicable en pratique que pour des graphes de très petite taille.
Un autre article [Irniger et al. 2001] a proposé l’utilisation d’arbres de décision pour accélérer le processus d’appariement. Dans cet article, l’arbre de décision n’est pas utilisé dans le processus d’appariement, mais seulement pour filtrer une base de graphes, puis un algorithme d’appariement complet a été appliqué sur ceux qui subsistent.

Appariement inexact

Les contraintes strictes imposées par l’appariement exact sont généralement trop rigides pour la comparaison de deux graphes. D’une part, les données sont souvent soumis à des déformations dues à plusieurs causes (le manque d’information, le bruit dans le processus d’acquisition, etc.), ce qui rend leur représenation peu différente de leur modélisation (formes de représentation) idéale. Ainsi, le processus d’appariement doit être tolérant : il doit prendre en compte ces déformation en relaxant les contraintes d’appariement. D’autre part, la plupart des algorithmes d’appariement exact ont besoin d’un temps exponentiel. Pour cela, il s’avère plus adapté d’utiliser des algorithmes qui ne garantissent pas de trouver la meilleure solution, mais qui donnent une bonne solution approchée dans un délai raisonnable.
Ces deux besoins ont conduit au développement d’algorithmes d’appariement inexact. Habituellement, ces algorithmes n’exigent pas une correspondance exacte entre les graphes. Au lieu de cela, ils pénalisent la dissimilitude en attribuant un coût à chaque différence.
Deux catégories de tels algorithmes existent. Dans la première, les algorithmes estiment le coût global d’appariement et restituent les graphes dont ce coût est minimal. Cela implique que si la solution exacte existe, elle sera retrouvée par de tels algorithmes. Ce type d’algorithmes (qui sont appelés optimaux) permet de résoudre le problème de déformation mais ils n’assurent pas une amélioration en temps de calcul. Ils sont généralement plus coûteux que leurs homologues exacts. L’autre type d’algorithmes d’appariement inexact (qui sont appelés approximatifs) cherche seulement à minimiser les coûts locaux (au niveau de chaque noeud) dans le processus d’appariement. Les résultats obtenus ne sont pas généralement très différents de ceux obtenus par les algorithmes optimaux. L’inconvénient majeur de ces algorithmes est l’incapacité de garantir de trouver la solution exacte si elle existe. Par contre, cette perturbation dans le résultat est compensée par un gain du temps qui est généralement polynomial.
Pour définir ce coût, un nombre important d’algorithmes se base sur la détection des erreurs (déformations) qui se produisent (noeud manquant, etc.) et en attribuant un coût à chaque type d’erreur. Ces anomalies sont souvent identifiées comme des « erreurs-correction » ou « erreurs-tolérance ». Une autre manière de définir le coût consiste à introduire un ensemble d’opérations d’édition (insertion d’un noeud, suppression d’un noeud, etc.) et à attribuer un coût à chaque opération. Le coût de la liste des opérations nécessaires pour assurer la transformation d’un graphe à un autre est calculé. Ce coût est appelé le « coût d’édition »

Table des matières

Introduction générale
1. Systèmes d’Information Géographique (SIG)
2. Interaction avec les SIG
3. Problématiques
4. Contributions
5. Organisation du mémoire
Partie 1 : État de l’art et contexte de l’étude
Chapitre I : Interrogation des données géographiques : Vers l’utilisation des croquis
I. 1. Introduction
I. 2. SIG
I. 2. 1. Données géographiques
I. 2. 2. Modes de représentation
I. 3. Interaction avec les SIG
I. 3. 1. Étude de l’adéquation des modalités d’utilisation d’un SIG
I. 3. 2. L’intérêt d’utiliser les croquis dans l’interrogation spatiale
I. 4. Interfaces utilisateur basées sur le croquis
I. 5. Étude analytique des comportements d’utilisateurs
I. 5. 1. Objets dessinés
I. 5. 2. Relations spatiales
I. 5. 3. Annotation
I. 6. Conclusion
Chapitre II : Comparaison des croquis : État de l’art sur les méthodes d’appariement de graphes
II. 1. Introduction
II. 2. Concepts et termes de base
II. 3. Représentation des données spatiales par graphes
II. 4. Définition et classification des méthodes d’appariement entre graphes
II. 4. 1. Appariement exact
II. 4. 2. Appariement inexact
II. 5. Conclusion
Partie 2 : Gestion des données géographiques : Propositions des modèles et un prototype d’interrogation par croquis
Chapitre III : Notre proposition : Vers la numérisation des croquis
III. 1. Introduction
III. 1. 1. Modèle générique de configuration spatiale
III. 1. 2. Utilisation du graphe pour instancier ce modèle
III. 1. 3. Discussion sur le type de graphe optimal pour représenter une configuration spatiale
III. 2. Méthodes de simplification du graphe
III. 2. 1. Minimisation du nombre de relations en utilisant la sémantique
III. 2. 2. Minimisation du nombre de relations en utilisant le contexte spatial
III. 2. 3. Discussion sur les méthodes de simplification du graphe
III. 3. Modèle de données géographiques
III. 3. 1. Modèle de réseau géographique
III. 3. 2. Modèle de couche de régions
III. 4. Méthodes d’appariement et mesures de similarité
III. 4. 1. Méthode d’appariement et mesures de similarité pour les réseaux géographiques
III. 4. 2. Méthode d’appariement et mesures de similarité pour les couches des régions
III. 4. 3. Mesures de similarité pour les requêtes multi-couches
III. 5. Conclusion
Chapitre IV : Validation : Proposition d’un outil d’interrogation par croquis
IV. 1. Introduction
IV. 2. Corpus de test
IV. 3. Prototype SIG-Croquis
IV. 3. 1. Architecture
IV. 3. 2. Exemples illustratifs
IV. 4. Évaluation
IV. 4. 1. Capacité à trouver les résultats retournés par l’approche classique
IV. 4. 2. Capacité à répondre aux requête à base de croquis
IV. 5. Conclusion
Conclusion générale
1. Bilan
2. Intérêt et originalité de notre approche
3. Limites et perspectives à nos travaux
Annexes
Annexe A : Modes de représentation
A. 1. Mode vectoriel (Vector)
A. 2. Mode matriciel (Raster)
Annexe B : Étude de l’adéquation des modalités d’utilisation d’un SIG
B. 1. Canaux de sortie de l’utilisateur
B. 2. Canaux d’entrée de l’utilisateur
B. 3. Bilan sur des modalités d’utilisateur

Télécharger le rapport complet