Spectral Clustering X SLIC Superpixels

Standard

Previously we talked about Spectral Clusterings [1] [2], which basically performs K-Means on eigenvectors of Laplacian matrix from a graph. While we could perform segmentation using normal K-Means by applying the algorithm on an image, the same thing cannot be said about Spectral Clusterings.

This is because spectral clustering (at least from what I know) requires the creation of Laplacian matrix first. For a m x n image with 3 channels, we need to create a (m x n x 3) x (m x n x 3) Laplacian matrix, and subsequently perform eigendecomposition and k-means on the eigenvectors. This can be very taxing and slow.

However, by leveraging our knowledge on superpixels [3], we can actually reduce the search space drastically. Rather than using all the pixels, we could first create, say 400 superpixels, and then create a Laplacian matrix (400 x 400) out of it, thus Spectral Clustering is much more feasible. In this case we’re viewing the superpixels as gross approximation of the more detailed image pixels.

The implementation goes like this:

  • After performing SLIC superpixels, we create a laplacian matrix using the SLIC superpixels cluster centers as the vertex for our graph. The important part here is to modify so that the distance measure of adjacency matrix utilizes the CIELab + X-Y space used in SLIC.
  • Apply eigendecomposition, and get the k-smallest eigenvectors
  • Perform k-means on the eigenvectors and get the corresponding clusters

Here’s the result:

Screen Shot 2014-05-07 at 12.25.52

400 superpixels, sigma = 1.0, and 2 clusters

Screen Shot 2014-05-07 at 12.25.56

200 superpixels, sigma = 2.0, and 2 clusters

The result of the segmentation depends on the superpixels, and sigma for the gaussian distance used in creating adjacency matrix. Higher number of superpixels means that spectral clustering part will be much slower too, and might be harder to segment the image too.

You can get the codes here: https://github.com/subokita/Sandbox/tree/master/SLICSuperpixelsAndSpectralCluster

Advertisements

2 thoughts on “Spectral Clustering X SLIC Superpixels

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s