Axe médiant discret : propriétés arithmétiques et algorithmes
Institution:
Aix-Marseille 2Disciplines:
Directors:
Abstract EN:
The medial axis is a geometric tool widely used in image analysis. In discrete geometry, the medial axis of a shape is the set of centres of the maximal balls of the shape. Its properties and its computation depend on the considered metric. In this thesis, we propose theoretical and algorithmic contributions for the most popular metrics used in the domain, the Euclidean distance and the chamfer (or weighted) norms: we give a characterization of the chamfer norms; we study the test neighbourhood necessary and sufficient to compute the medial axis, for the Euclidean distance and the 5 × 5 chamfer norms; finally we prove that finding a minimum covering of a discrete shape with Euclidean balls is an NP-hard problem.
Abstract FR:
L’axe médian est un outil géométrique largement utilisé dans de nombreux domaines de l’analyse d’image. En géométrie discrète, l’axe médian d’une forme est l’ensemble des centres des boules maximales dans la forme. Ses propriétées ainsi que son calcul sont étroitement liés à la famille de distance utilisée pour définir les boules. Dans ce mémoire, nous proposons plusieurs contributions, théoriques et algorithmiques, pour les distances les plus utilisées dans le domaine, à savoir la distance euclidienne et les normes de chanfrein : nous donnons une caractérisation des normes de chanfrein ; nous étudions le voisinage de test nécessaire et suffisant pour le calcul de l’axe médian discret, pour la distance euclidienne et les normes de chanfrein 5 × 5 ; enfin, nous prouvons que trouver une couverture minimum d’un objet discret par des boules euclidiennes est NP-difficile.