Friday, May 4, 2012

Superpixels for Python - pretty SLIC

Yesterday I wanted to try out a "new" superpixel algorithm that seemed quite successful: SLIC superpixels.
This is actually a very simple algorithm, basically doing KMeans in the color+(x,y) space. I'm a bit bummed that they named that, since I already tried the same approach a couple of years ago and didn't think it was very useful. Well, apparently it is.
The authors have a nice website with some examples. Unfortunately the linux binary didn't run on my box and building on linux seemed somewhat non-trivial.

So I did what I always do: wrote some Python wrappers. You can find them on github [update] I did an implementation for scikit-image which is now quite mature thanks to some other contributors. I would recommend using that instead if you want SLIC in python.[/update]. The whole thing is pretty small, easy to build and easy to use. Also damn fast (less than a second per image).

There are two variations, one where you can specify the number of superpixels and one where you can specify the number of pixels in a superpixel. Both have an additional parameter, the "compactness", which is a trade-off between the similarity in colorspace and (x,y) space.
Results for varying parameter settings look something like this:

Compare to my (former) favorite, quickshift:
Both are done in RGB colorspace and could probably benefit from going to Lab.
The SLIC implementation converts to Lab, while I didn't do the conversion for quickshift (which I probably should have done).

17 comments:

  1. It seems to be a bit more than KMeans, as it seems that the clusters are spatially contiguous. The clustering step must be imposing some connectivity. Could it be a KMedoids?

    ReplyDelete
  2. There's nothing in the code that seems to require contiguousness. Might just be the most common behavior.

    I don't understand why they only have to search 2Sx2S around each center. Couldn't a cluster be a region larger than diameter 2S if it were fairly homogenous in color?

    I was thinking that you could get similar behavior while guaranteeing contiguousness by only perturbing pixels at boundary edges, and only checking against the center of the region just over that boundary. I think to avoid hysteresis, you would want to do it this way:
    - compute cluster centers,
    - perturb boundary pixels until there are no changes,
    - recalculate cluster centers,
    - repeat until converged.
    Even that probably has some hysteresis, though perhaps less than perturbing the centers each time a pixel changes labels.

    ReplyDelete
  3. Also, the example code does not use exactly the same function as in the paper. The code uses sqrt(dist_xy^2 + dist_lab^2), instead.

    ReplyDelete
    Replies
    1. That is true. Weird, though it probably doesn't make much difference.

      Delete
  4. I must confess I haven't looked at the code in detail. In hindsight, it might have been better to wrap my own code.
    For the connectivity: As far as I understand it, this is more of a "cleanup" step. The clusters are not connected in the image space, but as a post-processing, each region in the image is assigned a label - so there can be more labels than clusters.

    Also, I noticed by default the edge perturbation is off. That doesn't seem like a good.

    I think the 2S is just a "good enough" approximation. It makes the superpixels even more compact (which is a desired property) and it makes the computations very efficient.

    ReplyDelete
    Replies
    1. Hello

      Reason for using 2Sx2S:

      Given N pixels in the image and k seeds. Typically, with the well known K-means clustering algorithm, K*N distances have to be evaluted. Using only pixels in the neighbouring area 2Sx2S, the number of comparison is reduced to 2Sx2S = 4S^2. As you know, S = sqrt(N/K), hence the total number of comparison is K*(4S^2) = K*4N/K =4N.
      Consequently, the complexity of the SLIC is only (o)N while kmeans algorithm has a complexity of (o)KN.

      In addition, prospecting in the 2Sx2S area around each cluster we allow us to guarantee that the spatial expand of each superpixel will never exceed 2Sx2S pixels (considered as compactness).

      ;-)

      Samir

      Delete
  5. Hi! Is there another way (e-mail?) I can contact you? I'd like to ask a few questions about this for our research project. Thank you!

    ReplyDelete
  6. Hi! If I use the python wrapper, am I supposed to still be able to edit the SLIC.spp code? I've only tried putting a cout on the cpp, but it doesn't output anything when I run the python code. Thanks!

    ReplyDelete
    Replies
    1. Just a follow-up question, do the region_labels pertain to the image data of a single superpixel?

      Delete
  7. Hey.
    Indeed, if you edit SLIC,cpp, the could should be executed. Are you sure you rebuild everything and the function is actually called?
    Btw, I reimplemented SLIC in cython, which might be a bit easier to play around with (although I'm not totally satisfied with it atm). Have a look here: http://peekaboo-vision.blogspot.de/2012/09/segmentation-algorithms-in-scikits-image.html

    IIRC region_labels is an image sized array of integers indicating the superpixel memberships.

    ReplyDelete
    Replies
    1. Aren't the cpp functions called in the _slic.pyx?
      If region_labels indicate superpixel memberships then is it correct if I use Image.fromstring(region_labels[i]) to save a single superpixel into an image? Actually that's what I've been trying to do - "extracting" a single superpixel and saving it as an image. Thank you so much. Sorry for asking a lot of questions.

      Delete
    2. 1) Some of the cpp functions are called.
      2) No. There are several problems with this expression. But first, it is not clear to me what you are trying to achieve. Superpixels are not rectangular, so I don't see how you want to save an superpixel to an image without computing the bounding box.
      Coud can easily get the pixels associated with a superpixel using image[region_labels == i], but this will be a flat vector.

      As these are rather general programming questions, may I suggest you try stackoverflow?

      Delete
  8. Hello, thanks for the Py binding! I experimented with it and it seems to work well and fast. But, when I run it on a list of several thousand images, the memory usage keeps increasing (memory leak somewhere) and eventually crashes (crashing the other memory demanding processes at the same time). This happened to me several times until I figured out the problem was due to a memory leak in slic-py. I haven't digged into the code to find out the problem yet. Do you have any idea or suggestion? Thanks a lot again.

    ReplyDelete
    Replies
    1. Did you use the newest version from github? I might have fixed something at some point. I don't have time to investigate now unfortunately. The algorithm is also implemented in scikit-image, but somehow the compactness there seems to be different than in the original implementation. Ultimately I'd rather make the scikit-image implementation as good as the original one.

      Delete
    2. Hello again!
      Yes I have downloaded it quite recently (one week or so). Right now, it is running and the memory usage increased to > 4GB for 400 images! Now, 6GB!.. So I also do not have time to find out right now, so what I do is to run it on smaller subsets of images instead of the whole dataset :)

      Delete
  9. These might help track it down:

    https://mg.pov.lt/objgraph/

    https://github.com/numpy/numpy/tree/master/tools/allocation_tracking

    ReplyDelete
  10. Thank you for your lovely software!
    This is just to let you know that the compile in Mac OS ended up in failure with the following error:
    _slic.cpp:5278:13: error: call to 'isspace' is ambiguous
    if (isspace(*ts))
    ^~~~~~~
    /Developer/SDKs/MacOSX10.6.sdk/usr/include/ctype.h:284:1: note: candidate function

    So I had to manually modify isspace(*ts) to std::isspace(*ts) in _slic.cpp, which now makes it work well.

    Thanks

    ReplyDelete