j’ai le plaisir et l’honneur de vous inviter à ma soutenance de thèse qui s’intitule “Développement de modèles graphiques probabilistes pour analyser et remailler les maillages triangulaires 2-variétés”.

Elle aura lieu le vendredi 9 décembre 2011 à 9h30 à la salle de réunion du LIRIS du bâtiment Blaise Pascal (3ème étage, 501 301) de l’INSA de Lyon, et vous êtes aussi chaleureusement invités au pot qui suivra vers 15h30 à la salle de réunion du LIRIS du bâtiment Jules Verne (1er étage) de l’INSA de Lyon.

Le Jury sera composé de :
M. Pierre ALLIEZ, Directeur de Recherche, INRIA Sophia-Antipolis (rapporteur)
M. Georges-Pierre BONNEAU, Professeur des Universités, INRIA Rhône-Alpes (rapporteur)
M. Loïc DENIS, Maître de Conférences, Université de Saint-Étienne (examinateur)
M. Frédéric PAYAN, Maître de Conférences, Université de Nice – Sophia Antipolis (examinateur)
M. William PUECH, Professeur des Universités, Université de Montpellier 2 (examinateur)
M. Florent DUPONT, Professeur des Universités, Université Lyon 1 (directeur de thèse)
M. Christian WOLF, Maître de Conférences, INSA de Lyon (co-directeur de thèse)

Résumé :
Ce travail de thèse concerne l’analyse structurelle des maillages triangulaires surfaciques, ainsi que leur traitement en vue de l’amélioration de leur qualité (remaillage) ou de leur simplification.
Dans la littérature, le repositionnement des sommets d’un maillage est soit traité de manière locale, soit de manière globale mais sans un contrôle local de l’erreur géométrique introduite, i.e. les solutions actuelles ne sont pas globales ou introduisent de l’erreur géométrique non-contrôlée. Les techniques d’approximation de maillage les plus prometteuses se basent sur une décomposition en primitives géométriques simples (plans, cylindres, sphères etc.), mais elles n’arrivent généralement pas à trouver la décomposition optimale, celle qui optimise à la fois l’erreur géométrique de l’approximation par les primitives choisies, et le nombre et le type de ces primitives simples.
Pour traiter les défauts des approches de remaillage existantes, nous proposons une méthode basée sur un modèle global, à savoir une modélisation graphique probabiliste, intégrant des contraintes souples basées sur la géométrie (l’erreur de l’approximation), la qualité du maillage et le nombre de sommets du maillage. De même, pour améliorer la décomposition en primitives simples, une modélisation graphique probabiliste a été choisie. Les modèles graphiques de cette thèse sont des champs aléatoires de Markov, ces derniers permettant de trouver une configuration optimale à l’aide de la minimisation globale d’une fonction objectif.
Nous avons proposé trois contributions dans cette thèse autour des maillages triangulaires 2-variétés : (i) une méthode d’extraction statistiquement robuste des arêtes caractéristiques applicable aux objets mécaniques, (ii) un algorithme de segmentation en régions approximables par des primitives géométriques simples qui est robuste à la présence de données aberrantes et au bruit dans la position des sommets, (iii) et finalement un algorithme d’optimisation de maillages qui cherche le meilleur compromis entre l’amélioration de la qualité des triangles, la qualité de la valence des sommets, le nombre de sommets et la fidélité géométrique à la surface initiale.

Mots-clé́s : Maillages triangulaires – 2-variété – Optimisation de maillage – Remaillage – Extraction de caractéristiques – Segmentation de maillage – Modèles graphiques probabilistes – Optimisation discrète – Coupure de graphe (graph cuts)

Abstract :
The work in this thesis concerns structural analysis of 2-manifold triangular meshes, and their processing towards quality enhancement (remeshing) or simplification.
In existing work, the repositioning of mesh vertices necessary for remeshing is either done locally or globally, but in the latter case without local control on the introduced geometrical error. Therefore, current results are either not globally optimal or introduce unwanted geometrical error. Other promising remeshing and approximation techniques are based on a decomposition into simple geometrical primitives (planes, cylinders, spheres etc.), but they generally fail to find the best decomposition, i.e. the one which jointly optimizes the residual geometrical error as well as the number and type of selected simple primitives.
To tackle the weaknesses of existing remeshing approaches, we propose a method based on a global model, namely a probabilistic graphical model integrating soft constraints based on geometry (approximation error), mesh quality and the number of mesh vertices. In the same manner, for segmentation purposes and in order to improve algorithms delivering decompositions into simple primitives, a probabilistic graphical modeling has been chosen. The graphical models used in this work are Markov Random Fields, which allow to find an optimal configuration by a global minimization of an objective function.
We have proposed three contributions in this thesis about 2-manifold triangular meshes : (i) a statistically robust method for feature edge extraction for mechanical objects, (ii) an algorithm for the segmentation into regions which are approximated by simple primitives, which is robust to outliers and to the presence of noise in the vertex positions, (iii) and lastly an algorithm for mesh optimization which jointly optimizes triangle quality, the quality of vertex valences, the number of vertices, as well as the geometrical fidelity to the initial surface.

Key-words : Triangular meshes – 2-manifold – Mesh optimization – Remeshing – Feature extraction – Mesh segmentation – Probabilistic graphical models – Discrete optimization – Graph cuts

Bien cordialement,

Vincent Vidal

La soutenance aura lieu le Lundi 24 Octobre 2011 à 14h dans la salle C5, Bâtiment Nautibus, Lyon 1.

Vous êtes également conviés au pot qui suivra dans la même salle.

Cordialement,

Stéphane Gosselin.

Composition du jury:

M. Bruno Crémilleux, Professeur, Univ. Caen, GREYC Rapporteur
M. Pascal Lienhardt, Professeur, Univ. Poitier, XLIM-SIC Rapporteur
M. Florent Dupont, Professeur, Univ. Lyon 1, LIRIS Examinateur
M. Jean-Christophe Janodet, Professeur, Univ. Evry, IBISC Examinateur
Mme. Christine Solnon, Professeure, INSA Lyon, LIRIS Directrice de thèse
M. Guillaume Damiand, Chargé de Recherches HDR, CNRS, LIRIS Co-Directeur de thèse

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 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.
À 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.