SEEDS: Superpixels Extracted via Energy-Driven Sampling
Superpixel algorithms aim to over-segment the image by grouping pixels that belong to the same object. Many state-of-the-art superpixel algorithms rely on minimizing objective functions to enforce color homogeneity. The optimization is accomplished by sophisticated methods that progressively build the superpixels, typically by adding cuts or growing superpixels. As a result, they are computationally too expensive for real-time applications. We introduce a new approach based on a simple hill-climbing optimization. Starting from an initial superpixel partitioning, it continuously refines the superpixels by modifying the boundaries. We define a robust and fast to evaluate energy function, based on enforcing color similarity between the boundaries and the superpixel color histogram. In a series of experiments, we show that we achieve an excellent compromise between accuracy and efficiency. We are able to achieve a performance comparable to the state-of-the-art, but in real-time on a single Intel i7 CPU at 2.8GHz.
New: Video SEEDS paper and source code available now: [full paper]. Fixed version 1.1 of SEEDS also available for download.
New: Have a look at our extended journal paper with optimized algorithm, improved benchmark results and an extended discussion on controlling the superpixel shape through the boundary term: [full paper].
Van den Bergh M., Boix X., Roig G. and Van Gool L. (2013). "SEEDS: Superpixels Extracted via Energy-Driven Sampling". In arXiv. [PDF]
Van den Bergh M., Roig G., Boix X., Manen S. and Van Gool L. (2013). "Online Video Superpixels for Temporal Window Objectness". In International Conference on Computer Vision (ICCV). [PDF]
Van den Bergh M., Boix X., Roig G., de Capitani B. and Van Gool L. (2012). "SEEDS: Superpixels Extracted via Energy-Driven Sampling". In European Conference on Computer Vision (Vol. 7, pp. 13-26). [PDF]
Van den Bergh M., Carton D. and Van Gool L. (2013). "Depth SEEDS: Recovering Incomplete Depth Data using Superpixels". In IEEE Workshop on Applications of Computer Vision (WACV). [PDF]
We provide C++ source code and a Matlab MEX file. Download version 1.1 of SEEDS which fixes crashing here.
We are also providing a beta version of Video SEEDS here.
Code for controlling the shape of the superpixels will be added soon.
The Algorithm in a Nutshell
his figure shows an example of the evolution of the superpixel boundaries while going through the iterations of the SEEDS algorithm (in the case of 12 superpixels). From left to right: The first image shows the initialization as a grid. The subsequent images show the block updates from large to small. The last image shows the pixel-level update of the superpixel boundaries.
The following graphs show the performance of SEEDS (shown in red) on the typical superpixel benchmarks, compared to the state-of-the-art superpixel methods.
Control over Superpixel Shape
Thanks to the boundary-updating property of the SEEDS algorithm, we can introduce different shape priors on the shape of the superpixel boundaries. The following image how different shapes of superpixels can be produced by using different priors (smoothness, compactness, etc.)
Details on this topic can be found in the SEEDS journal paper [full paper].
Online Video Segmentation with SEEDS
We have developed a clever new way to run SEEDS on video. This is achieved by propagating the rough block-level segmentation of each frame rather than the detailed pixel-level segmentation. This is combined with a clever superpixel creation and termination algorithm and lets us achieve real-time superpixel tubes.
Additionally, we have developed Randomized SEEDS, which allows for the generation of several slightly different SEEDS segmentations at the same time. One of the applications of Video SEEDS combined with Randomized SEEDS is temporal window objectness. This means we predict object bounding boxes over time, resulting in tubes of bounding boxes which are likely to contain an object.
This work has been accepted to ICCV 2013 and will be published here soon. We are excited to show quite good results on the Chen Xiph.org supervoxel benchmark, considering that our method is orders of magnitude faster than the competing methods and works online in real-time.