Efficient structure-preserving superpixel segmentation based on minimum spanning tree
Yu Bai, Xuejin Chen · 2016
We propose a novel superpixel algorithm based on Minimum Spanning Tree (MST), to generate superpixels efficiently while strictly adhere to object boundaries. The MST, which built by gradually removing strong edges of the image graph extracted from the image, is more sensitive to image local structures. Therefore, an efficient hierarchical clustering strategy is basically employed in our algorithm to segment the input image into superpixels based on the tree distance. To gradually merge the image pixels and remove texture noises, a multi-layer scheme with different resolutions of superpixels is proposed. In each layer, the graph is constructed from the lower layer and segmented into superpixels in a linear complexity with the node number in the graph. Because the node number in each layer is exponentially reduced, the computational time of our method mainly concentrates on the first few layers, which is linear with the number of image pixels. The experimental results conducted on the Berkeley Segmentation Dataset demonstrate that our method outperforms state-of-the-art methods both in terms of structure preservation and computational efficiency.