Mesh Segmentation by Diffusion
Sujet de DEA 20092010  Cyril Soler
The idea is to leverage from an existing image segmentation technique
called Diffusion Segmentation, to be able to segment meshes. The image method works in three steps:
 operate an antigeometric diffusion in the image (i.e. diffuse in the direction of the gradient)
 classify pixels into 3 categories according to the direction of diffusion (significantly diffused up, significantly diffused down, undefined).
 merge regions recursively down to the target number of regions.
The images below show the various step in this algorithm for a slice of tomographic data:




Original image
 Diffused (antigeometrically)
 Categories
 Segmented

Adapting this technique to meshes poses specific problems. We review them step by step:
Step 1
For step 1, one needs a proper function to diffuse on the mesh. This function must have the following properties:
 have different diffusion directions across large edges
 be small far from edges
 be large close to edges
A possible startup solution is to operate normal diffusion
(bilateral averaging, laplacian smoothing, etc) and to compute for each
vector:
where Dn(x) is the diffused normal at x. The vector field v has the property to
 be of higher intensity in regions with non stable normal
 abruptly change directions accross surface features
Step 2
We build connectivity regions according to the scalar product between field vectors v of candidate pairs of neighbors vertices.
The classification is:
 vertices with small values of v are undetermined
 vertices with large values are compatible if the scalar product is close to 1
This needs implementing a connex component analysis on the mesh' surface.
Step 3
This step is straightforward as soon as you have a 2D implementation of the region merging step. The regions are merged hiearchically according to a criterion that depends on the regions' shape and similarity with their neighbors.
Specific meshrelated problems:
 Can we perform 'antigeometric' diffusion on normals ?
 handle topology correctly (regions should have a disclike topology).
 properly distinguish large scale edges from small geometric details
Potential applications
Mesh segmentation methods have many applications. We want to focus specifically on the case of treating surfaces obtained through contour extraction on tomography data. This means that meshes have additional (good and bad) properties: roughly constant size of faces, conservative topology properties such as manifoldness, but also surface and topological noise.
The student will use the existing mesh representation, handling and drawing code existing in the ARTIS team.
References
Contact: Cyril.Soler (at) imag.fr