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:
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