Segmentation d'objets 3D
par étude de la fonction distance
Projet de Fin d’Etudes de
diplôme d'ingénieur ENSIMAG-ENSERG (dpt
Télécommunications) réalisé dans le cadre
d’une collaboration entre Total et le LIS
(Laboratoire Image et Signal, Grenoble). Au cours de ce stage,
j’ai développé en C++ un algorithme
capable de découper une surface aux niveaux de ses
rétrécissements. Cet algorithme est innovant, il
s’appuie sur la tetrahédrisation de Delaunay de
l’objet. L’application pour Total est de segmenter
les poches de pétrole reliées entre elles par de
petits canaux. Ce stage m’a permis de travailler 6 mois sur
des algorithmes de traitement de données 3D.
ALGORITHME
Sans rentrer
dans le détail de l'algorithme, on peut le
résumer ainsi :
Calcul
de la tetrahédrisation de Delaunay et de son dual
le graph. de Voronoï de l'objet à segmenter
Détection
des points critiques d'index 3,2 et 1 de la fonction
distance* ( comme intersection entre Voronoï et Delaunay)
Calcul
des variétés stables des points critiques d'index
2 ( portion de surface frontière entre deux maxima
de la fonction distance, c'est à dire entre deux sous
objets). Cette variété est définie par
la liste des points critiques d'index 1 dont le segment de Delaunay
porteur compose la frontière.
Calcul
des variétés stables des points critiques d'index
3 ( portion de la surface qui définie un
sous-objet). Cette variété est définie
par la liste des points critiques d'index 2 dont la
variété stable compose la frontière.
Filtrage
des points critiques d'index 3 ( les maxima c'est
à dire les sous-objets) qui sont à
l'extérieur de la surface.
Fusion
des sous-objets selon un seuil Certains sous-objets ne sont pas pertinent, c'est
à dire qu'on a détecté des
rétrécissements très
légers. Dans ce cas, on fusionne les sous-objets
séparés par ces coupures peu marquées.
Elimination
des petits sous-objets Certains sous-objets non souhaitables sont encore
présent. Ils sont caractérisés par une
toute petite taille, on les élimine en calculant la taille
de leur boite englobante.
fonction
distance : en tout point de l'espace, c'est la distance minimale aux
points de l'objet. La fonction tend à l'infini quand on
s'éloigne de l'objet. Elle tend vers des valeurs finies (
des maxima, ou encore point critique d'index 3) dans l'objet.
ILLUSTRATIONS
On voit ici un objet que l'on
désire segmenter. Dans ce cas, le résultat
attendu est simple : on veut couper la surface en deux, au niveau du
rétrécissement central. Les points noirs sont les
points de l'objet.
On a ici mis en rouges les deux
maxima de la fonction distance détectés par
l'algorithme. Ces deux maxima sont deux points critiques d'index 3 de
la fonction distance.
La surface verte
représente la variété stable d'un
point critique d'index 2. Le point critique est en vert vif au centre.
Il est à l'intersection entre un triangle de Delaunay et son
segment de Voronoi dual. Le chemin bleu est la descente de gradient de
la fonction distance entre le point critique d'index 2 et ses deux
maxima associés.
De même, la surface
verte est la variété stable d'un point critique
d'index 2. Cette variété est limitée
à un seul triangle de Delaunay qui intersecte son segment de
Voronoï dual ( en rouge). De même, le chemin bleu
part de ce point critique d'index 2 en faisant augmenter la fonction
distance. D'un coté, on part vers le maximum au centre de la
boule. De l'autre, on part à l'infini.
La variété
stable de l'un des deux maxima. On voit que l'on a bien
isolé un des deux sous-objets dans ce cas simple.
En rouge, les maxima. En bleu les
points critique d'index 1 ( ceux-ci sont situés sur la
surface). Pour un objet plus complexe, on détecte beaucoup
plus de maxima. Chacun des maxima ne correspond pas à un
véritable sous-objet.
Un objet encore plus
compliqué.
Ses maxima ( beaucoup trop nombreux
);
Exemple de sur-segmentation ( seuil
élevé de filtrage).
La bonne segmentation obtenue
après filtrage.
Ca marche.
On remarque que les coupures
pourrait être mieux placées, par exemple au niveau
du cou. Mais globalement, c'est ce que l'on désirait.
ASPECT LOGICIEL
Au fil du stage, pour progresser dans l'étude du
comportement de la fonction distance et pour illustrer l'algorithme
final, j'ai développé une interface utilisateur.
Celle-ci permet de sélectionner tout
élément de l'algorithme ( un point critique de la
fonction distance, un élément de
Delaunay/Vonoï...) et d'afficher les
données liées. Par exemple, si l'on
sélectionne un point critique d'index 2, on peut choisir
d'afficher sa variété stable ( la surface de
coupure), le segment de Voronoi/ le triangle de Delaunay source, les
chemins de descente de gradient...
Le programme est codé en C/C++ sous Linux ( avec le
compilateur GNU ). L'interface est réalisée sous FLTK. L'affichage 3D
se fait via une librairie équivalente à
OpenInventor. On utilise aussi quelques notions d'OpenGL. Le calcul des
structures de Delaunay/Voronoï sont
réalisés grâce à la
librairie CGAL (
librairie de géométrie algorithmique) .
