Vous êtes ici : GIPSA-lab > Formation > Thèses en cours
Chargement
NGUYEN Tuong Bach

Unions finies de boules avec marges interne et externe

 

Directeur de thèse :     Dominique ATTALI

Co-encadrant :     Isabelle SIVIGNON

École doctorale : Electronique, electrotechnique, automatique, traitement du signal (eeats)

Spécialité : Signal, image, parole, télécoms

Structure de rattachement : UJF

Établissement d'origine : EURECOM Sophia Antipolis

Financement(s) : Contrat doctoral ; Contrat doctoral ; Sans financement

 

Date d'entrée en thèse : 01/10/2014

Date de soutenance : 27/03/2018

 

Composition du jury :
Olivier DEVILLERS, Directeur de Recherches, INRIA, Rapporteur
Xavier GOAOC, Professeur des Universités, UPEM, Rapporteur
David COEURJOLLY, Directeur de Recherches, CNRS, Examinateur
Boris THIBERT, Maître de Conférences HdR, UGA, Examinateur
André LIEUTIER, Ingénieur, Dassault Systèmes, Invité
Dominique ATTALI, Directrice de Recherches, CNRS, directrice de thèse
Isabelle SIVIGNON, Chargée de Recherches, CNRS, co-encadrante de thèse

 

Résumé : Représenter un objet géométrique complexe par un ensemble de primitives simples est une tâche souvent fondamentale, que ce soit pour la reconstruction et la réparation de données, ou encore pour faciliter la visualisation ou la manipulation des données. Le choix de la ou les primitives, ainsi que celui de la méthode d'approximation, impactent fortement les propriétés de la représentation de forme qui sera obtenue.
Dans cette thèse, nous utilisons les boules comme seule primitive. Nous prenons ainsi un grand soin à décrire les unions finies de boules et leur structure. Pour cela, nous nous reposons sur les faisceaux de boules. En particulier, nous aboutissons à une description valide en toute dimension, sans hypothèse de position générale. En chemin, nous obtenons également plusieurs résultats portant sur les tests d'inclusion locale et globale dans une union de boules.
Nous proposons également une nouvelle méthode d'approximation par union finie de boules, l'approximation par boules à (delta,epsilon)-près. Cette approche contraint l'union de boules à couvrir un sous-ensemble de la forme d'origine (précisément, un epsilon-érodé), tout en étant contenu dans un sur-ensemble de la forme (un delta-dilaté). En nous appuyant sur nos précédents résultats portant sur les unions de boules, nous démontrons plusieurs propriétés de ces approximations. Nous verrons ainsi que calculer une approximation par boules à (delta,epsilon)-près qui soit de cardinal minimum est un problème NP-complet. Pour des formes simples dans le plan, nous présentons un algorithme polynomial en temps et en espace qui permet de calculer ces approximations de cardinal minimum. Nous concluons par une généralisation de notre méthode d'approximation pour une plus large variété de sous-ensembles et sur-ensembles.


GIPSA-lab, 11 rue des Mathématiques, Grenoble Campus BP46, F-38402 SAINT MARTIN D'HERES CEDEX - 33 (0)4 76 82 71 31