Segmentation Algorithms in scikits-image

Recently some segmentation and superpixel algorithms I implemented were merged into scikits-image. You can see the example here.

I reimplemented Felzenszwalb's fast graph based method, quickshift and SLIC.
The goal was to have easy access to some successful methods to make comparison easier and encourage experimenting with the algorithms.

Here is a a comparison of my implementations against the original implementations on Lena (downscaled by a factor of 2). The first row is my implementation, the second the original.

For the comparison, I used my python bindings of vl_feat's quickshift, my SLIC bindings and used the executable provided for Felzsenzwalb's method.

In general, I think this looks quite good. The biggest visual difference is for SLIC, where my implementation clearly does not a s good as the original one. I am quite sure this is a matter of using the right color space transform.

For the fast graph based approach, the result looks qualitatively similar, but is actually different. The reason is that I implemented a "per channel" approach, as advocated in the paper: Segment each RGB channel separately, then combine the segments using intersection.
Reading the code later on, I saw the algorithm that is actually implemented works directly on the RGB image - which is what I first implemented, but then revised after reading the paper :-/
It should be fairly easy to change my implementation to fit the original one (and not do what is said in the paper).

Here are some timing comparisons - they are just on this image, so to be taken with a grain of salt. But I think the general message is clear:

	Fast Graph Based	SLIC	Quickshift
mine	910ms	589ms	5470ms
original	166ms	234ms	5130ms

So the original implementation of the Fast Graph Based approach is much faster than mine, though as said above, it implements a different approach. I would expect a speedup of roughly 3x by using theirs, which would make my code still half as slow. For SLIC, my code is also about half as slow, while for Quickshift it is insignificantly faster somewhat slower. I am a bit disappointed with the outcome, but I think this is at least a reasonable place to start for further improvements. My first priority would be to qualitatively match the performance of SLIC.

While working on the code, I noticed that using the correct colorspace (Lab) is really crucial for this algorithm to work. For quickshift, it did not make much of a difference. One problem here is that the quickshift code, the SLIC code and scikits-image all use different transformations from RGB to Lab.

I will have to play with these to get a feeling on how much they influence the outcome. As the code is now included in scikits-image, you can find it in our (I recently gained commit rights :) github repository.

During this quite long project, I really came to love Cython, which I used to write all of the algorithms. The workflow from a standard Python program for testing to a implementation with C-speed is seamless!  The differences in speed between my and the original implementation is quite certainly due to some algorithmic issues, rather than that "Python is slow". The C-Code generated by Cython is really straight-forward and fast.
I want to point out the

cython -a

command, as it took me some time to discover it. It is simply brilliant. It gives a html output of your cython code, highlighting lines in which Python API is called (and that are therefore slow).

If you want to implement an algorithm from scratch for Python, and it must be fast, definitely use Cython!

That's all :)