Rooted Spanning Superpixels

Superpixels have become effective alternative to pixels in the past decade. By grouping a set of neighboring pixels into one perceptually meaningful superpixel, the number of superpixels is much smaller than the number of pixels, and therefore facilitates image analysis such as machine learning.

In this study, Chai (2020) formulates superpixel segmentation as finding a rooted spanning forest of a graph with respect to some roots and a path-cost function. The underlying graph represents an image, the roots serve as seeds for segmentation, each pixel is connected to one seed via a path, the path-cost function measures both the color similarity and spatial closeness between two pixels via a path, and each tree in the spanning forest represents one superpixel. Originating from the evenly distributed seeds, the superpixels are guided by a path-cost function to grow uniformly and adaptively, the pixel-by-pixel growing continues until they cover the whole image as depicted in Fig. 1.

Rooted Spanning Superpixels (RSS) achieve good performance, which is ranked as the second among top performing state-of-the-art methods. Moreover, the RSS algorithm is much faster than the other superpixel methods.This new approach has been published online by prestigious International Journal of Computer Vision. 

Fig. 1. Rooted spanning superpixels. Starting from the seed pixels, the superpixels grow up pixel by pixel until they cover the whole image. The initial state, intermediate states, and final state are shown respectively from left to right. Their boundaries and constituting pixels are depicted as green lines and colored regions in the top and bottom images respectively.

Dengfeng Chai (2020): Rooted Spanning Superpixels, International Journal of Computer Vision, https://link.springer.com/article/10.1007/s11263-020-01352-9.