## 1 Introduction  
Dividing an image into several simple connected regions with perceptual meanings is called superpixels. Superpixels can represent images more concisely and efficiently than pixels, which can significantly reduce the complexity of subsequent image processing. After the concept of superpixels was proposed by [PERSON] and [PERSON] [1] in 2003, the simplified image expression became a key step in many computer vision tasks, such as segmentation [2; 3; 4; 5; 6], saliency detection [7; 8; 9], object recognition [10; 11], modelling [12; 13], 3D reconstruction [14], and other vision tasks [15; 16; 17]. For these applications, the high-quality superpixels are desired to meet the following properties:  
1. Each superpixel is a simple single connected area with the regular shape. 2. Superpixels should adhere well to the image boundaries and pixels inside the superpixels should have homologous characteristics. 3. The density of superpixels should be adaptive to local image content. 4. The superpixels algorithms should be fast to compute and memory efficient. The superpixel segmentation algorithms can be roughly divided into two categories: Graph-based methods and clustering-based methods. Graph-based methods treat each pixel as a vertex in the graph. The similarity between adjacent pixels is considered as the weight of the edge. The normalized cut (N-cut) algorithm [18] recursively partitions the pixel graph using contour and texture information in the image. [PERSON] and [PERSON] [19] proposed a superpixel generation method based on the minimum spanning tree (FH). [PERSON] et al. [20] generated superpixels (SL) by searching the minimum path from the horizontal and vertical directions. [PERSON] et al. [21] generated superpixels (Graph Cut) by half-overlapping square patches of the same size covered on the image. [PERSON] et al. [22] presented a graph-based approach (ERS), which combines the entropy rate of a random walk with and a balancing function for superpixel segmentation. SEEDS [23] generates superpixels by iteratively modifying the initial approximate boundaries of superpixels according to the energy function. The clustering-based methods define a distance measure to evaluate the similarity between pixels and generate superpixels by iteratively assigning pixels to the most similar seeds until some convergence criteria are reached. TurboPixels [24] is a geometric flow method (TP), which regularly places the seeds on images and grows the superpixels by level-set. This method can make the size of superpixels uniform, but it consumes more time than other superpixel methods. [PERSON] et al. [25] proposed structure-sensitive superpixels (SSS) according to the geodesic distance computed from geometric flows. SSS can effectively describe the nonhomogenous features in images by the superpixel size. However, the computational cost of SSS is even higher than that of TP. [PERSON] et al. [26] proposed an algorithm, simple linear iterative clustering (SLIC), to generate superpixels. SLIC uniformly places the initial cluster centers on the geometric center of the regular grids. By limiting the search range of the k-means algorithm, the computational complexity of the SLIC is greatly reduced. To further improve the performance of SLIC, [PERSON] and [PERSON] [27] proposed simple non-iterative clustering (SNIC) to compute superpixels with one iteration. [PERSON] et al. [28] proposed manifold SLIC (MSLIC), which expands SLIC to generate content-sensitive superpixels. MSLIC maps a five-dimensional image space to a two-dimensional manifold for computing restricted centroidal Voronoi tessellation under the Euclidean metric. As an improvement of MSLIC, the authors proposed intrinsic manifold SLIC [29] (IMSLIC) to compute a centroidal Voronoi tessellation under the geodesic distance instead of Euclidean distance on the image manifold. [PERSON] et al. [30] presented the lazy random walk (LRW) method to evaluate the probabilities between a seed and its neighbor pixels.