CV détaillé - enseignements et recherche (pdf)

Thèse de Doctorat effectuée au LIF

Titre : "Axe Médian Discret : Propriétés Arithmétiques et Algorithmes"

Soutenue : le 20 novembre 2009 à Marseille

Jury :

- Eric Andres, professeur à l'université de Poitiers (rapporteur) ;
- Victor Chepoi, professeur à l'université de la Méditerranée (examinateur) ;
- Michel Couprie, professeur à l'université Paris-Est (rapporteur) ;
- Jacques-Olivier Lachaud, professeur à l'université de Savoie (examinateur) ;
- Edouard Thiel, professeur à l'université de la Méditerranée (directeur).

Résumé :

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 S⊆ℤⁿ est l'ensemble des centres des boules maximales de S, une boule étant maximale dans S si elle n'est incluse dans aucune autre boule incluse dans S. Les propriétés de l'axe médian 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.

Mots-clés : axe médian, boule, distance euclidienne, normes de chanfrein.

Document de thèse (pdf)
Transparents de la soutenance (pdf)

Publications

Revues internationales

J. Hulin et E. Thiel.
Visible Vectors and Discrete Euclidean Medial Axis.
Discrete and Computational Geometry, 42(4), pp. 759-773, 2009 [pdf] [résumé].

We denote by Mⁿ(R) the test neighbourhood sufficient to extract the Euclidean Medial Axis of any n-dimensional discrete shape whose inner radius is no greater than R. In this paper, we study properties of discrete Euclidean disks overlappings so as to prove that in any given dimension n, Mⁿ(R) tends to the set of visible vectors when R tends to infinity.

D. Coeurjolly, J. Hulin and I. Sivignon.
Finding a Minimum Medial Axis of a Discrete Shape is NP-hard.
Theoretical Computer Science, 406(1-2), pp. 72-79, 2008. [pdf] [résumé].

The medial axis is a classical representation of digital objects widely used in many applications. However, such a set of balls may not be optimal: subsets of the medial axis may exist without changing the reversivility of the input shape representation. In this article, we first prove that finding a minimum medial axis is an NP-hard problem for the Euclidean distance. Then, we compare two algorithms which compute an approximation of the minimum medial axis, one of them providing bounded approximation results.

Conférences internationales

J. Hulin et E. Thiel.
Farey Sequences and the Planar Euclidean Medial Axis Test Mask.
In proceedings of IWCIA'09, 13th International Workshop on Combinatorial Image Analysis,
Lecture Notes in Computer Science, pp. 82-95, 2009. [pdf] [résumé] [annex with source code].

The Euclidean test mask T(r) is the minimum neighbourhood sufficient to detect the Euclidean Medial Axis of any discrete shape whose inner radius does not exceed r. We establish a link between T(r) and the well-known Farey sequences, which allows us to propose two new algorithms. The first one computes T(r), in time O(r⁴) and space O(r²). The second one computes for any vector v the smallest r for which v∈T(r), in time O(r³) and constant space.

J. Hulin et E. Thiel.
Appearance Radii in Medial Axis Test Mask for Small Planar Chamfer Norms.
In proceedings of DGCI 2009, 15th International Conference on Discrete Geometry for Computer Imagery.
Lecture Notes in Computer Science, pp. 434-445, 2009. [pdf] [résumé] [annex with proofs].

The test mask T_M is the minimum neighbourhood sufficient to extract the medial axis of any discrete shape, for a given chamfer distance mask M. We propose an arithmetical framework to study T_M in the case of chamfer norms. We characterize T_M for 3×3 and 5×5 chamfer norm masks, and we give an algorithm to compute the appearance radius of the vector (2,1) in T_M.

J. Hulin et E. Thiel.
Chordal Axis on Weighted Distance Transforms.
In proceedings of DGCI 2006, 13th International Conference on Discrete Geometry for Computer Imagery.
Lecture Notes in Computer Science, pp. 271-282, 2006. [pdf] [résumé].

Chordal Axis (CA) is a new representation of planar shapes introduced by Prasad in 1997, useful for skeleton computation, shape analysis, characterization and recognition. The CA is a subset of chord and center of discs tangent to the contour of a shape, derivated from Medial Axis (MA). Originally presented in a computational geometry approach, the CA was extracted on a constrained Delaunay triangulation of a discretely sampled contour of a shape. Since discrete distance transformations allow to efficiently compute the center of distance balls and detect discrete MA, we propose in this paper to redefine the CA in the discrete space, to extract on distance transforms in the case of chamfer norms, for which the geometry of balls is well-known, and to compare with MA.

Cursus universitaire

2005-2009	Doctorant en Informatique à l'Université Aix-Marseille II. Allocataire-Moniteur. Sujet : "Axe Médian Discret : Propriétés Arithmétiques et Algorithmes". Sous la direction d'Edouard Thiel. Soutenue le 20 novembre 2009.
2004-2005	Master 2 recherche en Informatique à l'Université Aix-Marseille II. Filière Combinatoire et Recherche Opérationnelle. Mémoire intitulé "Caractérisation de l'axe cordal sur une image de distance". Encadrant : Edouard Thiel.
1999-2002	Ecole Supérieure d'Ingénieurs de Luminy, spécialité Informatique (Université Aix-Marseille II).

Coordonnées

LaBRI 351, cours de la Libération F-33405 Talence cedex, France. Tél. (+33) 5 40 00 35 11 Fax. (+33) 5 40 00 66 69 Mél.  Jerome.Hulin[at]labri.fr