Shape Segmentation

Geometry processing mesh segmentation code using spectral clustering

Assignment Objective

• Practice using libigl to create shape decompositions using spectral clustering of various shape features
• Understand the limitations in traditional shape segmentation methods

(Fig. 1: results produced by the completed code with K=10 using SDF)

Compile the code

• use cmake on Linux/OSX systems

  mkdir build; cd build; cmake ..; make

• use cmake on Windows Visual Studio

  • the easiest way to compile the code on windows would be cmake_gui which creates solution files
  • Once the solution file and project files are created without errors, you should be ready to go

Run the code

Running the code is simple but get yourself familiar with the command line options first. The main parameter is a shape file. You can find a few in ./mesh folder. The number of segments is specified by -k flag followed by an integer. You can also turn on/off visualization. Shape features can be either Shape Diameter function (SDF) or Average Geodesic Distance. See the usage below for more details.

usage: ./build/segment [-g] [-k #] [-sdf|-geo] mesh_file (*obj or *off)
    -k #: number of segments (default is 5)
    -g: turn on visualization
    -sdf: segment using shape diameter function (default)
    -geo: segment using average geodesic distance

For example, try:

./build/segment -g -k 8 ./mesh/Centaur-1000.obj

You will see the following images with faces randomly clustered (note: faces with the same color are in the same cluster):

(Fig. 2: random clustering with K=8 )

Tasks

1. Compute shape features (20%)

1. Compute shape feature for each face. The feature is a number between 0 and 1
2. The first function is per_face_avg_geodesic in per_face_feature.h/cpp. You need to compute face-to-face geodesic distances between all faces and then determine the average geodesic distance for each face as the feature for that face.
3. The first function is per_face_SDF also in per_face_feature.h/cpp. Your objective is to determine the shape diameter function of the center of every face in the mesh. Note that this is the simplified version of the original shape diameter function which represents the features using a Gaussian Mixture Model. In our case, we simplified it to a single number, namely the average length of the shape diameter.

(Fig. 3: Simplified Shape diameter function features. )

2. Compute similarity matrix (30%)

1. Determine the similarity matrix of the faces. The matrix has the dimension of |F|X|F| where |F| is the number of faces in the mesh. - implement your code in the first function compute_similarity_maxtrix in similarity_maxtrix.cpp
2. A value of 0 means a pair of faces are very different and should be classified into different clusters.
3. A large value means a pair of faces have high similarity and should be classified into the same cluster.
4. The matrix should be symmetric
5. Use shape features computed in the previous step to determine the similarity
6. What factors other than shape features should be considered in computing the values in the similarity matrix

3. Cluster the faces using spectral clustering (10%)

1. Use the provided spectral clustering and K-means clustering methods to segment the faces into K components - implement your code in the first function spectral_clustering in spectral_clustering.cpp
2. Save the cluster into proper format

4. Post-processing to make sure that faces in the same cluster form a single connected component (30%)

1. A cluster created in Step #3 may contain multiple connected components. Your final task to reassign the faces so that each cluster only contains one component.

2. There are several ways you can do this. Here are some hints: - For each cluster C, identify the largest component M in C and mark the faces C that do not belong M as unassigned. - After the first step, each cluster now only has a single connected component. - Iteratively expand each cluster C if C is adjacent to an unassigned face. If an unassigned face f is adjacent to multiple clusters, f should be assigned to the cluster with faces most similar to f.

3. You might also want to optimize for the boundaries between clusters so they are as short as possible and pass through some important shape features, such as joints.

(Fig. 4: results produced by the completed code with K=12 using SDF; Notice that the boundaries in this example are not optimized.)

5. Report in PDF (10%)

1. Show examples with various K and shape decriptors.
2. Describe what you learned in this assignment.
3. Describe the limitations in your implementation or in the method. This can be bugs that you are aware of or limitations of the technique used.
4. Ideas on improving this work.