Efficient Graph Based Image Segmentation by Felzenszwalb and Huttenlocher

Standard

Here’s another popular segmentation algorithm from Felzenszwalb and Huttenlocher (http://cs.brown.edu/~pff/papers/seg-ijcv.pdf), that I ported from their original code to OpenCV.

As usual, the original literature looks intimidating, however when you go through the code, it’s actually quite simple. Here’s the rough idea how it works:

First convolve the image with gaussian kernel for smoothing and noise reduction purposes. This is where the sigma value comes in.

Then for each neighbouring pixels, create edges between them, with the weight between edges calculated as the L2 norm of the sum of different intensities between those pixel channels.

Create a disjoint set forest data structure based on those edges. You can read more about disjoint set forest here: http://en.wikipedia.org/wiki/Disjoint-set_data_structure. At least get the rough idea behind the find and union operations.

For each two edges in the disjoint set forest, if both of their weights are below a given threshold, we union those edges together

For the final step, if there are small set of edges which are below another given threshold, merge them.

Here are the sample results of applying the algorithm:

Original Image

With fake random colours for each cluster

Recoloring based on the average colour of each cluster

And here’s a clip showing the result of applying the segmentation using various thresholding values: