PS 4 - Spectral Clustering

(Maks Ovsjanikov)

The goal of this practical session is to implement the basic version of
the spectral clustering algorithm, both on an undirected graph and on a triangle mesh.


        Example of a graph with nodes clustered according to the spectral clustering algorithm.

0. Getting started

Files to download today

Instructions

The zip package includes the following 3 directories:

Exercise 1 (Spectral Clustering on Graphs)

In today's practical session, you are expected to implement the basic version of the spectral clustering algorithm both on graphs and on triangle meshes. In first exercise, please use the basic structure of the given file spectral_clustering.m to get started. The file contains some instructions for steps you should complete. In particular, you should implement the following steps in this exercise:

Exercise 2 (Spectral Clustering on Triangle Meshes)

Follow the same basic procedure as in Exercise 1 but now to find vertex clusters (also known as segments) on triangle meshes. To get started please look at the template code in spectral_clustering_shape.m. The main difference of this exercise compared to the previous one is that you are expected to construct the cotangent Laplacian that we discussed during the lecture, as opposed to the uniform one on graphs. Recall that the cotangent Laplacian L = A^{-1} W, where A is the diagonal matrix of area weights for each vertex, whereas W is the matrix of cotangent weights: W_{i,j} = (cot(a) + cot(b))/2 opposite of each edge i,j.
Because the Laplacian matrix L is given as a product of two matrices, computing its eigenvalues and eigenvectors is more efficient by solving the Generalized Eigenvalue problem: W phi = lambda A phi, where (lambda, phi) are the eigenvalue, eigenvector respectively. Note that MATLAB has a very efficient solver to tackle this problem. You can call it by simply using: [v,e] = eigs(W, A, 5, -1e-5); The result that you are expected to obtain on these armadillo shapes should look like this:

Exercise 3 (BONUS)

In this exercise, you should use your implementation from the previous exercise to compute the Heat Kernel Signature that we discussed today during the lecture. Please look at the the following paper that discusses this signature in more detail and gives its basic properties. If you chose to do this exercise you should compute the signature, and run some basic tests to see if you can identify similar points on both the same shape (e.g. left vs. right hands) and across shapes (e.g. on the different deformations of the armadillos.

Exercise 4 (BONUS)

In this exercise, you should use your implementation from the exercise 2 to compare different shapes by comparing the eigenvalues of their Laplacian operators. We talked about this approach today during the lecture and it is called Shape-DNA. A good description of this method was given in this paper which also proposed an extension. You are not expected to implement the extension, but just use a basic version, which only uses the eigenvalues of the LB operator to compare shapes and find categories of shapes. To test your implementation, you will need some meshes in different categories. You can use the shapes from here to test your implementation. Namely, you will be expected to demonstrate that you can find similar shapes within the same category and to distinguish shapes in different categories (cats vs. dogs, etc.)