Superpixel Segmentation Based on Clustering by Finding Density Peaks

Superpixel segmentation has been widely used as a pre-processing procedure in many computer vision applications, such as object tracking, 3D reconstruction, visual saliency estimation, object detection, and medical image segmentation. In this paper, we present a novel superpixel segmentation algorithm, which is inspired by a new clustering method published in Science in 2014. Our algorithm produces superpixels through clustering pixels by searching and finding density peaks. This algorithm consists of five steps. Firstly, we estimate the density for each pixel in a local circular neighborhood in the image plane. Density is formulated as a weighted similarity between the central pixel and all the surrounding ones, while the radius of the neighborhood can be determined experientially by the superpixel number that we desired. Secondly, we search the nearest pixel with a larger density for each pixel and calculate the distance between them. For each pixel, the index of the nearest pixel and the distance to it are two attributes named as ascription and distance, respectively. In the third step, we construct an ascription relation tree and assemble all the pixels into the tree based on their distances and ascriptions. A leaf of the tree represents a pixel. A directed edge in the tree starts from a pixel and arrives at its ascription and is weighted by the corresponding distance. The tree reflects the ascription relationship among all the pixels in the input image. In the fourth step, we select several pixels with large densities and distances as the seeds of superpixels. Then we assign each seed a unique label in the tree. In the final step, by searching the tree, we find the closest superpixel seed for each pixel and assign the label of the seed to it. Our algorithm has many advantages. It is flexible because it can automatically select the seeds and accurately control the number and the size of the superpixels it produced. It is fast because no iterative optimization is involved in the algorithm. Its computational complexity does not rely on the number of superpixels. We compare our algorithm to nine state-of-the-art methods on two benchmark datasets, BSDS300 and BSDS500. The comparison methods are categorized into two main types: 5 classical methods (SLIC, QS, DB, NC, and GB) and 4 latest canonical ones (LSC, ERS, SEEDS, and FLIC). We conducted extensive experiments to confirm the performance of our algorithm. We start with qualitatively examine the superpixels of all the methods. The examination results reveal that the superpixels of our algorithm adhere to the ground-truth edges more accurately than the other methods. To confirm the superior performance of our algorithm, we further evaluate all the methods quantitatively by their scores on four widely used measures: the boundary recall rate, the under-segmentation error, the achievable segmentation accuracy, and the computational complexity. The evaluation results reveal that our algorithm significantly outperforms the 5 classical methods. It also achieves better or similar scores than the 4 latest canonical methods. The runtime of our algorithm does not rise as the number of superpixels increases. © 2020, Science Press. All right reserved.