>>

Séminaire MIDI : John Chaussard

Titre du séminaire et orateur

Analyse de formes 3D à l'aide de squelettes.
John Chaussard, Centre de Morphologie Mathématique, Mines ParisTech.

Date et lieu

Jeudi 22 mars 2012, 14h.
ENSEA, salle 384.

Résumé

Le squelette d'une forme X est une représentation simplifiée de X, permettant parfois d'effectuer des mesures que l'on ne pourrait pas réaliser sur la forme originale. Par exemple, considérons comme objet 3D une pieuvre, et la simple question de savoir si cette dernière possède ses huit tentacules. Pour effectuer cette mesure par informatique, une stratégie possible serait de simplifier l'animal en un réseau de courbes, puis de compter le nombre d'arcs du résultat (chaque tentacule étant représenté par un arc). C'est typiquement ce que l'opération de squelettisation permet de faire.

Un "bon" squelette d'un objet X est un sous ensemble de X qui doit :

  1. posséder la même topologie que X (le même nombre de composantes connexes, de cavités, de tunnels, ...).
  2. être centré dans X.
  3. être fin, c'est à dire posséder une dimension de moins que l'espace dans lequel on se trouve (en 2D, un squelette doit être un ensemble de courbes, en 3D, ce doit être un ensemble de courbes et de surfaces).

Dans le domaine discret, les squelettes sont la plupart du temps calculés par un processus de suppression de points de l'objet : des points sont itérativement retirés de l'objet jusqu'à ce qu'une condition d'arrêt spécifique soit atteinte. L'ensemble de points restant forme le squelette de l'objet. Il est souvent nécessaire d'obtenir un squelette qui "ressemble" à l'objet original (qui possède le même aspect visuel que l'objet de départ - voir, par exemple, cette image ). Pour reprendre l'exemple précédent de la pieuvre, un simple point est un squelette valide de la pieuvre, mais il ne permettra pas d'effectuer une mesure correcte de son nombre de tentacules. Il faut obtenir, pour cet exemple, un squelette formé de courbes (chaque courbe représentant un tentacule). Il existe deux stratégies pour obtenir un squelette "ressemblant" à la forme de départ :

  1. On peut choisir, avant le processus de squelettisation, des points de l'objet qui ne seront par retirés par la squelettisation. Ces points sont généralement sélectionnés grâce à une fonction calculée sur l'objet (par exemple, la carte de distance de l'objet) et un seuil de cette fonction produit un ensemble de points à conserver (par exemple, conserver tous les centre de boules maximales de l'objet de rayon supérieur ou égal à un certain seuil). Cette stratégie permet d'obtenir de bons résultats en général, mais requiert une intervention de l'utilisateur, et le paramètre de filtrage est propre à un objet (il n'existe pas de paramètre universel fonctionnant pour tous les objets).
  2. On peut choisir, pendant le processus de squelettisation, les points à conserver en observant leur voisinage : par exemple, dans l'exemple de la pieuvre, si le voisinage d'un point commence à ressembler, pendant la squelettisation, à une courbe, alors ce point est peut-être au centre d'un tentacule et il faut le conserver. Cette stratégie ne requiert aucune intervention de l'utilisateur, mais produit souvent des squelettes bruités (qui possèdent trop d'éléments). Il faut alors ajouter une phase de filtrage du squelette afin d'enlever les éléments surnuméraires (phase qui requiert un paramètre de filtrage de la part de l'utilisateur).

Dans cet exposé, nous présenterons un algorithme de squelettisation produisant un squelette fin et "ressemblant" à l'objet original. L'algorithme ne nécessite pas de paramètre de filtrage de la part de l'utilisateur, et possède une très bonne robustesse au bruit par rapport aux autre algorithmes de squelettisation. Ce résultat est obtenu en mélangeant les deux stratégie citées précédemment. Le squelette peut ensuite être décomposé en éléments simples (courbes, surfaces) et être utilisé pour identifier les différentes partie de l'objet de départ.

Retour