Objectif :
Ce projet a pour objet de trouver un algorithme original permettant un traitement rapide pour determiner certaines propriétés topologiques des points des images 3D.
En effet, les algorithmes actuels de traitements d'images 3D, comme pour la squelettisation d'image par exemple, souffrent de grande complexite de calcul ce qui entraine des temps d'execution important.
Pour mettre au point un algorithme efficace, on se propose d'utiliser des arbres de décisions binaires tels qu'ils ont été decrits par Randal E. Bryant pour représenter les fonctions booléennes. En effet, on peut, pour chaque propriété des points d'une image 3D, determiner la fonction booléenne correspondante, dont les variables sont la valeur des points voisins.
Pour ce projet, on s'interessera plus particulierement a une propriété : la simplicité des points. On dit qu'un point d'un objet d'une image 3D est simple si on peut le retirer sans modifier la topologie de l'image (nombre de composantes connexes, de trous et de cavites). Cette propriété est utilisée notamment pour determiner le squelette d'un objet.
Details du projet:
L'intéret de ces arbres de décisions binaires tient dans les possibilités de réductions qu'ils offrent. Ces réductions sont decrites dans l'article de R.E.Bryant. Pour illustrer, on peut, en partant du graphe comme celui de gauche, obtenir celui de droite.
Cependant, il existe quelques limites a ces réductions. En effet, l'ordre des variables dans l'arbre influence tres nettement les possibilites de reductions. Les deux arbres suivants representent la meme fonction f= ab+cd+ef (ab <=> a ET b; a+ b <=> a OU b). Dans le premier cas, l'ordre est a, b, c, d, e, f et dans le second a, c, e, b, d, f.
De plus toutes les fonctions booléennes ne permettent pas des réductions d'arbre significatives. Des exemples de ce problemes sont donnes dans l'article de R. E.Bryant.
Nous avons donc realisé une premiere étude en 2D pour tenter de degager des regles de priorités des points du voisinage du point, sans reel succes. Cependant nous avons utilisé un package de construction d'arbre a partir d'une fonction booleene qui propose un reordonnancement efficace des variables.
Apres avoir determiner la formule des points simples en 3D et l'avoir soumise au package, on obtient le graphe reduit et reordonnancé. Nous avons pu construire une fonction C permettant de determiner la simplicité d'un point en temps lineaire en fonction du nombre de points du voisinage. Nous avons ainsi pu reduire le temps d'execution d'un facteur 170 par rapport a un algorithme existant qui se base sur le calcul des nombres topologiques.
Grace a cette nouvelle approche, on peut maintenant imaginer ameliorer les algorithmes de determination d'autres propriétés des points d'images 3D, notamment la determination de la valeur des nombres topologiques permettant de caracteriser la topologie d'une image.
Contactez nous :
Denis Guyonnaud
David Perrault
Regis Vinciguerra
References :
Graph-Based Algorithms for Boolean
Function Manipulation,
Randal E. Bryant
IEEE Transactions on Computers, vol. c-35, NO. 8, August 1986