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).

Comments

  1. GaëlMay 6, 2012 at 8:19 PM

    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. thouisMay 12, 2012 at 6:15 PM

    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
    Replies
    1. UnknownMay 9, 2014 at 2:03 PM

      On your suggestion in the last paragraph. It is not enough to perturb boundary pixels. In some cases the boundaries stabilize, but there might be detail within a cluster that should be assigned to a nearby cluster. I know this because I am working on a new algorithm, similar to SLIC, but using a density estimation approach. Also, to represent these boundary positions programmatically is more complex than working with 2Sx2S rectangles centered on the cluster centers. The edges might move with every iteration, possibly requiring a new scan of cluster allocation transitions for adjacent pixels over the whole image after every iteration.

      Delete
    2. Alex TaylorOctober 9, 2015 at 7:47 PM

      The original paper(s) for slic describe an "enforce connectivity" phase that follows the k-means clustering where regions are merged or relabeled to result in separate, contiguous connected regions for each label. The scikit-image implementation provides a parameter for turning on/off this enforce connectivity phase of the algorithm.

      The 2Sx2S search localized about each cluster center isn't something they "have to do". It's done to make the algorithm O(N). By constraining the search neighborhood about each superpixel center, the algorithm is much faster.

      Delete
  3. thouisMay 12, 2012 at 9:41 PM

    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. Andreas MuellerMay 12, 2012 at 11:41 PM

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

      Delete
  4. Andreas MuellerMay 12, 2012 at 11:43 PM

    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. samirAugust 8, 2012 at 7:41 AM

      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. Czel LitimcoSeptember 17, 2012 at 9:59 AM

    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. AnonymousSeptember 23, 2012 at 1:48 PM

    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. AnonymousSeptember 23, 2012 at 4:32 PM

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

      Delete
  7. Andreas MuellerSeptember 23, 2012 at 6:30 PM

    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. AnonymousSeptember 24, 2012 at 3:42 AM

      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. Andreas MuellerSeptember 24, 2012 at 10:35 AM

      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. AnonymousApril 18, 2013 at 2:28 PM

    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. Andreas MuellerApril 18, 2013 at 3:26 PM

      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. AnonymousApril 19, 2013 at 5:27 PM

      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. thouisApril 18, 2013 at 3:52 PM

    These might help track it down:

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

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

    ReplyDelete
  10. PoppyJanuary 30, 2014 at 7:05 AM

    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

Post a Comment

Popular posts from this blog

Machine Learning Cheat Sheet (for scikit-learn)

Image
As you hopefully have heard, we at scikit-learn are doing a user survey (which is still open by the way). One of the requests there was to provide some sort of flow chart on how to do machine learning. As this is clearly impossible, I went to work straight away. This is the result: [edit2] clarification: With ensemble classifiers and ensemble regressors I mean random forests , extremely randomized trees, gradient boosted trees , and the soon-to-be-come weight boosted trees (adaboost). [/edit2] Needless to say, this sheet is completely authoritative.
Read more

A Wordcloud in Python

Image
Last week I was at Pycon DE , the German Python conference. After hacking on scikit-learn a lot last week, I decided to to something different on my way back, that I had planned for quite a while: doing a wordl -like word cloud . I know, word clouds are a bit out of style but I kind of like them any way. My motivation to think about word clouds was that I thought these could be combined with topic-models to give somewhat more interesting visualizations. So I looked around to find a nice open-source implementation of word-clouds ... only to find none. (This has been a while, maybe it has changed since). While I was bored in the train last week, I came up with this code . A little today-themed taste:
Read more

MNIST for ever....

Image
[update] This post is a bit old, but many people still seem interested. So just a short update: Nowadays I would use Python and scikit-learn to do this. Here is an example of how to do cross-validation for SVMs in scikit-learn. Scikit-learn even downloads MNIST for you. [/update] MNIST is, for better or worse, one of the standard benchmarks for machine learning and is also widely used in then neural networks community as a toy vision problem. Just for the unlikely case that anyone is not familiar with it: It is a dataset of handwritten digits, 0-9, in black on white background. It looks something like this: There are 60000 training and 10000 test images, each 28x28 gray scale. There are roughly the same number of examples of each category in the test and training datasets. I used it in some papers myself even though there are some reasons why it is a little weird. Some not-so-obvious (or maybe they are) facts are: - The images actually contain a 20x20 patch of digi...
Read more

Python things you never need: Empty lambda functions

Ever wanted to create an empty Python function in-line? No? Me neither. But my coworker does... We found the answer: <pre> x = lambda : None </pre> If you ever needed this, please tell me ;) [Edit] Apparently some people do need it :) Btw, most people seem to try Most people try lambda: pass first. But you have to remember, the thing at the right side of the colon is the return value of the function, not the body! So an expression is needed, not a statement. [\Edit]
Read more