Efficient Graph Based Image Segmentation by Felzenszwalb and Huttenlocher


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:

Screen Shot 2014-04-24 at 20.25.38

Original Image

Screen Shot 2014-04-24 at 20.25.42

With fake random colours for each cluster

Screen Shot 2014-04-24 at 20.25.45

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:


You can get my OpenCV port of it over here: https://github.com/subokita/Sandbox/tree/master/EfficientGraphBasedImageSegmentation

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s