Discussion :

[Décembre]

Bonjour,

Je souhaiterais squelettiser un volume 3D d'une structure vasculaire en utilisant les diagrammes de Voronoi, le problème c'est que je ne sais pas ce qu'il faut faire exactement et à chaque fois que je lis un document qui en parle je ne comprends rien !!

est ce que vous pouvez me dire qu'elle sont les étapes à suivre pour obtenir un squelette avec les diagrammes de Voronoi?

Merci d'avance

[Kangourou]

salut,

tu as deux grandes approches pour les squelettes : discrète et géométrique.

Pour le squelette discret, on travaille dans l'espace image, et on cherche l'ensemble des pixels ou voxels équidistants a plusieurs points de la frontière. C'est souvent basé sur des fonctions distance, et c'est ce qui me semble le plus robuste.

Pour le squelette géométrique, c'est plus complexe. Faisable en 2D, mais en 3D je sais pas.
L'idée (comme je la comprends de ce que j'ai pu voir) : on a des points sur la frontière de la forme. On calcule le diagramme de Voronoi 3D avec ces points comme germes. Le résultats est une structure de complexe cellulaire, avec des faces et des arêtes qui sont équidistantes à 2 ou 3 germes. On a par contre beaucoup de faces/arêtes qui sont séparent des germes proches sur la frontière, et il faudrait les filtrer. C qu'il faut ensuite, c'est arriver à isoler les sommets/arêtes/faces du diagramme qui se trouvent à l'intérieur de la structure d'origine, ce qui donne une première approche du squelette.

Je suis pas sur d'être tres clair... Mais a priori ce n'est pas forcement évident. Pour l'implémentation, c'est pas gagné non plus.. regarder vers CGAL ?

a++

[Décembre]

Salut,

tu as deux grandes approches pour les squelettes : discrète et géométrique

Je ne le savais pas !! quelle est la différence entre les deux approches ?

On calcule le diagramme de Voronoi 3D avec ces points comme germes. Le résultats est une structure de complexe cellulaire, avec des faces et des arêtes qui sont équidistantes à 2 ou 3 germes.

J'ai pu calculer le diagramme de Voronoi avec Matlab (Dieu merci, il y a une fonction toute prête) mais je n'arrive toujours pas à interpreter le résultat que j'ai trouvé, les points obtenus sont loin du centre de la forme et la topologie n'est pas conservée. je me dis qu'il certainement un truc à faire avant ou après le calcul du diagramme de Voronoi...je suis perdue

[Kangourou]

salut,

Par "approche discrète" je parlais d'approche 'image' (2D ou 3D). Le résultat donné par la squletisation sera une autre image, contenant les pixel ou voxels du squelette.

Par "approche géométrique", je pensais à des structures de données de type "nuage de points", ou maillages surfaciques. Dans ce cas le squelette consiste a calculer des hyper-plans (droites, plans...) entre les points, et à les combiner pour refaire une forme. D'après ce que j'en ai vu, ce type d'approche n'est pas forcément simple à mettre en oeuvre.

De plus, en 3D la notion de squelette est multiple :

• squelette filaire, composé de plusieurs courbes
• squelette surfacique, composé de morceaux de surfaces.

A voir lequel est le plus adapté, ou lequel il est possible de calculer...

Dans le cas où les données de départ sont un ensemble de points (les "germes") situés à la surface de la structure d'intérêt, une idée est effectivement de passer par Voronoi.
On obtient un ensemble de cellules (des polyèdres), chaque cellule correspondant à un germe. Sous Matlab, ces cellules sont représentées par un tableau N*3 de coordonnées de sommets, et une série d'indices de sommets pour chaque cellule.

Une proposition de traitement :

1. trouver les sommets qui sont "a l'intérieur" de la structure
2. pour chaque cellule, calculer le polyèdre convexe équivalent (fonction convhulln) -> on obtient un ensemble de faces triangulaires
3. ne garder que les faces dont les sommets sont à l'intérieur, c'est à dire dont les indices correspondent avec les indices des sommets trouvés à la première étape
4. afficher un patch ou équivalent des triangles qu'on a gardés.
5. si on essaie de trouver les arêtes communes à 3 triangles intérieurs, j'imagine qu'on trouve un squelette filaire... mais à vérifier.

Sinon un problème avec Voronoi est qu'on a des cellules avec un point à l'infini. C'est casse-pied... Une solution simple est de rajouter des germes artificiels autour de la structure. Du coup, les cellules correspondantes aux points de la structure seront bornées.

bon courage...

[Décembre]

salut,

Par "approche discrète" je parlais d'approche 'image' (2D ou 3D). Le résultat donné par la squletisation sera une autre image, contenant les pixel ou voxels du squelette.

Par "approche géométrique", je pensais à des structures de données de type "nuage de points", ou maillages surfaciques. Dans ce cas le squelette consiste a calculer des hyper-plans (droites, plans...) entre les points, et à les combiner pour refaire une forme. D'après ce que j'en ai vu, ce type d'approche n'est pas forcément simple à mettre en oeuvre.

De plus, en 3D la notion de squelette est multiple :

• squelette filaire, composé de plusieurs courbes
• squelette surfacique, composé de morceaux de surfaces.

A voir lequel est le plus adapté, ou lequel il est possible de calculer...

Dans le cas où les données de départ sont un ensemble de points (les "germes") situés à la surface de la structure d'intérêt, une idée est effectivement de passer par Voronoi.
On obtient un ensemble de cellules (des polyèdres), chaque cellule correspondant à un germe. Sous Matlab, ces cellules sont représentées par un tableau N*3 de coordonnées de sommets, et une série d'indices de sommets pour chaque cellule.

Une proposition de traitement :

1. trouver les sommets qui sont "a l'intérieur" de la structure
2. pour chaque cellule, calculer le polyèdre convexe équivalent (fonction convhulln) -> on obtient un ensemble de faces triangulaires
3. ne garder que les faces dont les sommets sont à l'intérieur, c'est à dire dont les indices correspondent avec les indices des sommets trouvés à la première étape
4. afficher un patch ou équivalent des triangles qu'on a gardés.
5. si on essaie de trouver les arêtes communes à 3 triangles intérieurs, j'imagine qu'on trouve un squelette filaire... mais à vérifier.

Sinon un problème avec Voronoi est qu'on a des cellules avec un point à l'infini. C'est casse-pied... Une solution simple est de rajouter des germes artificiels autour de la structure. Du coup, les cellules correspondantes aux points de la structure seront bornées.

bon courage...

Wow...je n'aurais jamais compris tout ça toute seule

Merci beaucoup, je vais suivre les étapes que tu viens de m'expliquer et je t'informerai du résultat.

Merci encore