Mesh Segmentation by Diffusion

Sujet de DEA 2009-2010 - 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:

  1. operate an anti-geometric diffusion in the image (i.e. diffuse in the direction of the gradient)
  2. classify pixels into 3 categories according to the direction of diffusion (significantly diffused up, significantly diffused down, undefined).
  3. 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:

Image:diff1.png Image:diff2.png Image:diff3.png Image:diff4.png
Original image Diffused (anti-geometrically) 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:

  1. have different diffusion directions across large edges
  2. be small far from edges
  3. 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:

v(x) = n(x) \times Dn(x)

where Dn(x) is the diffused normal at x. The vector field v has the property to

Step 2

We build connectivity regions according to the scalar product between field vectors v of candidate pairs of neighbors vertices. The classification is:

  1. vertices with small values of v are undetermined
  2. 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 mesh-related problems:

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