Personal tools
Laboratoire d'InfoRmatique en Image et Systèmes d'information

Skip to content. | Skip to navigation

Laboratoire d'InfoRmatique en Image et Systèmes d'information
UMR 5205 CNRS / INSA Lyon / Université Claude Bernard Lyon 1 / Université Lumière Lyon 2 / École Centrale de Lyon
You are here: Home > publis

PhD thesis

Recherche de motifs fréquents dans une base de cartes combinatoires [PDF]
11/2011
Établissement : Université Claude Bernard Lyon 1
Soutenue le Oct 24, 2011
Jury
M. Cremilleux Bruno, GREYC, Caen, France Rapporteur
M. Lienhardt Pascal, XLIM-SIC, Poitier, France Rapporteur
M. Dupont Florent, LIRIS, Lyon, France Examinateur
M. Janodet Jean-Christophe, IBISC, Evry, France Examinateur
Mme Solnon Christine, LIRIS, Lyon, France Directeur
M. Damiand Guillaume, LIRIS, Lyon, France Co-directeur
Contact : stephane.gosselin@liris.cnrs.fr

TEL : tel-00838571

Résumé

Une carte combinatoire est un modèle topologique qui permet de représenter les subdivisions de l'espace en cellules et les relations d'adjacences et d'incidences entre ces cellules en n dimensions. Cette structure de données est de plus en plus utilisée en traitement d'images, mais elle manque encore d'outils pour les analyser. Notre but est de définir de nouveaux outils pour les cartes combinatoires nD. Nous nous intéressons plus particulièrement à l'extraction de sous-cartes fréquentes dans une base de cartes. Nous proposons deux signatures qui sont également des formes canoniques de cartes combinatoires. Ces signatures ont chacune leurs avantages et leurs inconvénients. La première permet de décider de l'isomorphisme entre deux cartes en temps linéaire, en contrepartie le coût de stockage en mémoire est quadratique en la taille de la carte. La seconde signature a un coût de stockage en mémoire linéaire en la taille de la carte, cependant le temps de calcul de l'isomorphisme est quadratique. Elles sont utilisables à la fois pour des cartes connexes, non connexes, valuées ou non valuées. Ces signatures permettent de représenter une base de cartes combinatoires et de rechercher un élément de manière efficace. De plus, le temps de recherche ne dépend pas du nombre de cartes présent dans la base. Ensuite, nous formalisons le problème de recherche de sous-cartes fréquentes dans une base de cartes combinatoires nD. Nous implémentons deux algorithmes pour résoudre ce problème. Le premier algorithme extrait les sous-cartes fréquentes par une approche en largeur tandis que le second utilise une approche en profondeur. Nous comparons les performances de ces deux algorithmes sur des bases de cartes synthétiques. Enfin, nous proposons d'utiliser les motifs fréquents dans une application de classification d'images. Chaque image est décrite par une carte qui est transformée en un vecteur représentant le nombre d'occurrences des motifs fréquents. A partir de ces vecteurs, nous utilisons des techniques classiques de classification définies sur les espaces vectoriels. Nous proposons des expérimentations en classification supervisée et non supervisée sur deux bases d'images.

Abstract

A combinatorial map is a topological model that represents the subdivisions of an nD space into cells and their adjacency relations in n dimensions. This data structure is increasingly used in image processing, but it still lacks tools for analysis. Our goal is to define new tools for combinatorial nD maps. We are particularly interested in the extraction of submaps in a database of maps. We define two combinatorial map signatures: the first one has a quadratic space complexity and may be used to decide of isomorphism with a new map in linear time whereas the second one has a linear space complexity and may be used to decide of isomorphism in quadratic time. They can be used for connected maps, non connected maps, labbeled maps or non labelled maps. These signatures can be used to efficiently search for a map in a database. Moreover, the search time does not depend on the number of maps in the database. We introduce the problem of finding frequent submaps in a database of combinatorial nD maps. We describe two algorithms for solving this problem. The first algorithm extracts the submaps with a breadth-first search approach and the second one uses a depth-first search approach. We compare these two algorithms on synthetic database of maps. Finally, we propose to use the frequent patterns in an image classification application. Each image is described by a map that is transformed into a vector representing the number of occurrences of frequent patterns. From these vectors, we use standard techniques of classification defined on vector spaces. We propose experiments in supervised and unsupervised classification on two image databases.

BibTex

Download

@PhDThesis{Liris-5220,
  title         = {{Recherche de motifs fréquents dans une base de cartes 
    combinatoires}},
  author        = {Stéphane {Gosselin}},
  year          = {2011},
  month         = nov,
  school        = {Université Claude Bernard Lyon 1},
  type          = {Thèse de Doctorat en Informatique},
   language      = {fr},
  url           = {http://liris.cnrs.fr/publis/?id=5220}
}