SLIC Superpixel Segmentation Algorithm

blowekamp · June 18, 2018, 8:55pm

We have written an Insight Journal (IJ) article describing our implementation of the simple linear iterative clustering (SLIC) super pixel algorithm. Although the upload process to IJ does not appear to be working right now. I uploaded a copy to GitHub for your reading pleasure..

This article includes scalability analysis and threading performance. This is a hot topic in ITK these days with the exciting new TBB, and thread pool back ends. This implementation uses the older ITKv4 threading model for portability. However, with the clearly documented implementation, and the analysis framework provided in the repository, it is an opportunity to evaluate how the new threading model can be applied to a complex filter with multiple threading strategies.

I have also initiated a pull request for adding the filter to a new ITK module directly in ITK. This filter is a newer, and unique algorithm for ITK which I believe helps round out the selection of segmentation methods available in ITK. I hope that it will be welcomed addition to the ITKv5 release.

Enjoy.

fbudin · June 18, 2018, 9:08pm

That looks great! I had a problem for which I needed a superpixel implementation and I had to use a different library than ITK… Thanks for implementing this! Do you want to create a remote module? If you use the template module, that should also easily allow you to have the Python wrapping!

blowekamp · June 19, 2018, 2:07pm

Hi Francois,

The code and IJ paper are already in an ITK module. The module framework and CI is what allowed my Gerrit pull request to be initially green We already have the SimpleITK JSON to wrap this filter so we are good for many language bindings.

I am specifically requesting that this contribution be merged directly into ITK proper, for the following reasons:

ITK is missing a proper super pixel algorithm, this contribution adds one and helps to flush out our sparse segmentation group.
The contribution is well tested, documented, and as the IJ paper demonstrates its very scalable. We have put our best effort into the code and believe it is high quality.
With the current effort in improving threading, this class is a good opportunity to apply the new techniques and evaluate the results with the methods outlined in the IJ for scalability analysis.

Thanks for the consideration of my request.

fbudin · June 21, 2018, 12:15pm

That is true that such an algorithm is missing from ITK. As @jhlegarreta commented on gerrit, the code has been well tested. I +2 the review on Gerrit. Thanks for your contribution! Great work!

blowekamp · July 3, 2018, 8:17pm

The SLIC filter has been merged into ITK and has also been updated with the modern ITKv5 threading model. I took this as an opportunity to do a performance comparison of the various threading options now available in ITK.

I have updated the paper with an additional section about updating the threading.

The interesting results are summarized in these graphs which show the timing results for a [2048x1216] 2D image across the number of threads with the different threading backs ends. The top figure shows the time, and the bottom figure shows the speed up of ITKv4 compared to the original implementation. Details are in the paper.

Have a happy and safe 4th of July to those celebrating.

dzenanz · July 4, 2018, 10:43am

The paper reports minimum time out of 20 runs. Have you perhaps also calculated mean or median times?

It would be interesting to run this benchmark again once the refactoring is completed.

blowekamp · July 4, 2018, 11:32am

The minimum methodology is based on the task to being profiled is interrupted by system tasks and processes. The minimum is bounded. The mean is corrupted by outliers and the median while robust includes the meadian time of the system load. Hence, minimum is best to use to remove that variability of system tasks.

dzenanz · July 4, 2018, 11:51am

I understand the decision to go with minimum. I was just wondering whether TBB’s dynamic load balancing helps smooth out those unexpected interruptions.

blowekamp · July 5, 2018, 4:45pm

So you are invested in more the standard deviation or the robust median absolute deviation (MAD) then? I’ll be sure to save all the timing next time I run the benchmarks.

blowekamp · July 23, 2018, 3:22pm

The final Insight Journal publication in now available:
http://hdl.handle.net/10380/3596

Enjoy!

P.S. There appears to be some size limit on the PDF size for IJ article 11MB was too big, but 4.5MB was ok.

Jigabytes · September 29, 2019, 8:40pm

Thanks Bradley for implementation of scalable SLIC algo. From my research I found this algo is very suitable for the problem I am solving in Medical imaging space. After reading paper I was able to tweak the results with 2 parameters exposed to user, however is there provision to specify the number of threads to the algo or does it deduce the number of threads automatically from available hardware resources?

blowekamp · September 29, 2019, 11:17pm

Hello Jigabytes,

Glad to hear the algorithm works for you.

SLIC follows the standard ITK conventions of threading by using the itkMultiThreaderBase class. By default ITK will set the number of threads to the number of virtual cores on your system. The number of “work units” is configurable on the filter with the SetNumberOfWorkUnits method.

Jigabytes · September 30, 2019, 6:19am

Thanks Bradley for your precise response. The default number of threads should suffice. I will checkout on different hardware config.

Thanks much!
Jiten

Jigabytes · September 30, 2019, 6:41am

Hi Bradley,

One more question in my next steps I want to analyze each segment (superpixel) from the image. Is there way I can get info on each superpixel and do my further processing by iterating over it?

Thanks,
Jiten

blowekamp · September 30, 2019, 1:43pm

You can get some basic information about each label with the LabelStatisticsImageFilter. You can also transform the labels into a RLE LabelMap and compute additional statistics. This can be done with the LabelImageToStatisticsLabelMapFilter and the LabelImageToShapeLabelMapFilter.

In SimpleITK you can do something like:

In [1]: import SimpleITK as sitk
In [3]: img = sitk.ReadImage("cthead1.png", sitk.sitkUInt8)   
In [4]: label_img = sitk.SLIC(img)                                                                                                                                                                                             
In [5]: stats = sitk.LabelIntensityStatisticsImageFilter()      
In [9]: stats.Execute(label_img, img)   
In [10]: for label in stats.GetLabels(): 
    ...:     print("label: {0} mean: {1} stddev: {2}".format(label, stats.GetMean(label), stats.GetStandardDeviation(label))) 
                                                                                                                                                                      
label: 1 mean: 68.96668685645064 stddev: 70.7053260510559
label: 2 mean: 12.441130906274205 stddev: 5.867930161247463
label: 3 mean: 13.03177512985029 stddev: 5.521150026218238
label: 4 mean: 0.05821623171780901 stddev: 0.5543294639538547
label: 5 mean: 12.485638699924413 stddev: 7.503822699914821
label: 7 mean: 151.2949321517585 stddev: 49.298010886412946
label: 8 mean: 158.65245478036175 stddev: 61.29964359104075
label: 9 mean: 16.95241840346048 stddev: 9.873177761674237
label: 10 mean: 11.864980711530219 stddev: 6.391074021980228
...

Jigabytes · October 1, 2019, 2:50am

Thanks Bradley!

I just realized that the superpixel I get by applying SSLIC on 3D image are also in 3D so the superpixels (each label) is 3D which is very useful.

Using intensity and shape stats I get bounding box info and mean intensity which is what I was looking for.

Just one more naive q What is RLE LabelMap? Is there link where I can dig more to get concrete understanding on it?

Thanks,
Jiten

blowekamp · October 1, 2019, 1:53pm

The label maps/label objects were originally contributed to ITK via this Insight Journal submission: https://www.insight-journal.org/browse/publication/176

Jigabytes · October 13, 2019, 10:38pm

Hi Bradley, I had one question while using SSLIC algo, are there any guidelines to keep in mind while providing superpixel grid size to the algorithm? I did trail and error and I get varying results based on superpixel grid size. I am not able to evaluate which size is optimal for use case I am solving. Thanks,
Jiten

blowekamp · October 15, 2019, 2:04pm

The general guidelines is to adjust the size/number of super pixels so that the contours of your objects are preserved while the size of super pixels is maximized.

Jigabytes · October 16, 2019, 12:09am

Thanks Bradley makes sense !