superpixels extracted via energy-driven sampling (SEEDS)

Question

I am interested in superpixels extracted via energy-driven sampling (SEEDS) which is a method of image segmentation using superpixels. This is also what OpenCV uses to create superpixels. I am having troubles finding documentation behind the SEEDS algorithm. OpenCV gives a very general description which can be found here.

I am looking for a more in depth description on how SEEDS functions (either a general walk through or a mathematical explanation). Any links or thoughts concerning the algorithm would be much appreciated! I can't seem to find any good material. Thanks!

Answer 1

I will first go through some general links and resources and then try to describe the general idea of the algorithm.

SEEDS implementations:

You obviously already saw the documentation here. A usage example for OpenCV's SEEDS implementation can be found here: Itseez/opencv_contrib/modules/ximgproc/samples/seeds.cpp, and allows to adapt the number of superpixels, the number of levels and other parameters live - so after reading up on the idea behind SEEDS you should definitely try the example. The original implementation, as well as a revised implementation (part of my bachelor thesis), can be found on GitHub: davidstutz/superpixels-revisited/lib_seeds and davidstutz/seeds-revised. The implementations should be pretty comparable, though.

Publication and other resources:

The paper was released on arxiv: arxiv.org/abs/1309.3848. A somewhat shorter description (which may be easier to follow) is available on my website: davidstutz.de/efficient-high-quality-superpixels-seeds-revised. The provided algorithm description should be easy to follow and -- in the best case -- allow to implement SEEDS (see the "Algorithm" section of the article). A more precise description can also be found in my bachelor thesis, in particular in section 3.1.

General description:

Note that this description is based on both the above mentioned article and my bachelor thesis. Both offer a mathematically concise description.

Given an image of with width W and height H, SEEDS starts by grouping pixels into blocks of size w x h. These blocks are further arranged into groups of 2 x 2. This schemes is repeated for L levels (this is the number of levels parameter). So at level l, you have blocks of size

w*2^(l - 1) x h*2^(l - 1).

The number of superpixels is determined by the blocks at level L, i.e. letting w_L and h_L denote the width and height of the blocks at level L, the number of superpixels is

S = W/w_L * H/h_L

where we use integer divisions.

The initial superpixel segmentation which is now iteratively refined by exchanging blocks of pixels and individual pixels between neighboring superpixels. To this end, color histograms of the superpixels and all blocks are computed (the histograms are determined by the number of bins parameter in the implementation). This can be done efficiently by seeing that the histogram of a superpixel is just the sum of the histograms of the 2 x 2 blocks it consists of, and the histogram of one of these blocks is the sum of the histograms of the 2 x 2 underlying blocks (and so on). So let h_i be the histogram of a block of pixels belonging to superpixel j, and h_j the histogram of this superpixel. Then, the similarity of the block j to superpixel j is computed by the histogram intersection of h_i and h_j (see one of the above resources for the equation). Similarly, the similarity of a pixel and a superpixel is either the Euclidean distance of the pixel color to the superpixel mean color (this is the better performing option), or the probability of the pixel's color belonging to the superpixel (which is simply the normalized entry of the superpixel's histogram at the pixel's color). With this background, the algorithm can be summarized as follow:

initialize block hierarchy and the initial superpixel segmentation
for l = L - 1 to 1 // go through all levels
    // for level l = L these are the initial superpixels
    for each block in level l
        initialize the color histogram of this block
        // as described this is done using the histograms of the level below
// now we start exchanging blocks between superpixels
for l = L - 1 to 1
    for each block at level l
        if the block lies at the border to a superpixel it does not belong to
            compute the histogram intersection with both superpixels
            assign the block to the superpixel with the highest intersection
// now we exchange individual pixels between superpixels
for all pixels
    if the pixel lies at the border to a superpixel it does not belong to
        compute the Euclidean distance of the pixel to both superpixel's mean color
        assign the pixel to the closest superpixel

In practice, the block updates and pixel updates are iterated more than ones (which is the number of iterations parameter), and often twice as many iterations per level are done (which is the double step parameter). In the original segmentation, the number of superpixels is computed from w, h, L and the image size. In OpenCV, using the above equations, w and h is computed from the desired number of superpixels and number of levels (which are determined by the corresponding parameters).

One parameter remains unclear: the prior tries to enforce smooth boundaries. In practice this is done by considering the 3 x 3 neighborhood around a pixel which is going to be updated. If most of the pixels in this neighborhood belong to superpixel j, the pixel to be updated is also more likely to belong to superpixel j (and vice versa). OpenCV's implementation as well as my implementation (SEEDS revised), allow to consider larger neighborhoods k x k with k in {0,...,5} in the case of OpenCV.