Superpixel segmentation has become an important research problem in image processing. In this paper, we propose an Iterative Spanning Forest (ISF) framework, based on sequences of Image Foresting Transforms, where one can choose i) a seed sampling strategy, ii) a connectivity function, iii) an adjacency relation, and iv) a seed pixel recomputation procedure to generate improved sets of connected superpixels (supervoxels in 3D) per iteration. The superpixels in ISF structurally correspond to spanning trees rooted at those seeds. We present five ISF methods to illustrate different choices of its components. These methods are compared with approaches from the state-of-the-art in effectiveness and efficiency. The experiments involve 2D and 3D datasets with distinct characteristics, and a high level application, named sky image segmentation. The theoretical properties of ISF are demonstrated in the supplementary material and the results show that some of its methods are competitive with or superior to the best baselines in effectiveness and efficiency.
Most superpixel segmentation approaches adopt a clustering algorithm and or a graph-based algorithm to address the problem in one or multiple iterations of seed estimation. Several of these methods cannot guarantee connected superpixels: SLIC (Simple Linear Interative Clustering) @cite_4 , LSC (Linear Spectral Clustering) @cite_5 , Vcells (Edge-Weighted Centroidal Voronoi Tessellations) @cite_10 , LRW (Lazy Random Walks) @cite_20 , ERS (Entropy Rate Superpixels) @cite_40 , and DBSCAN (Density- based spatial clustering of applications with noise) @cite_49 . Connected superpixels in these methods are usually obtained by merging regions, as a post-processing step, which can reduce the number of desired superpixels.
@cite_4 @cite_40 @cite_49 @cite_5 @cite_10 @cite_20
2118246710 2135431554 2529970009 2573546209 2108424265
Computer vision applications have come to rely increasingly on superpixels in recent years, but it is not always clear what constitutes a good superpixel algorithm. In an effort to understand the benefits and drawbacks of existing methods, we empirically compare five state-of-the-art superpixel algorithms for their ability to adhere to image boundaries, speed, memory efficiency, and their impact on segmentation performance. We then introduce a new superpixel algorithm, simple linear iterative clustering (SLIC), which adapts a k-means clustering approach to efficiently generate superpixels. Despite its simplicity, SLIC adheres to boundaries as well as or better than previous methods. At the same time, it is faster and more memory efficient, improves segmentation performance, and is straightforward to extend to supervoxel generation. We propose a new objective function for superpixel segmentation. This objective function consists of two components: entropy rate of a random walk on a graph and a balancing term. The entropy rate favors formation of compact and homogeneous clusters, while the balancing function encourages clusters with similar sizes. We present a novel graph construction for images and show that this construction induces a matroid — a combinatorial structure that generalizes the concept of linear independence in vector spaces. The segmentation is then given by the graph topology that maximizes the objective function under the matroid constraint. By exploiting submodular and mono-tonic properties of the objective function, we develop an efficient greedy algorithm. Furthermore, we prove an approximation bound of ½ for the optimality of the solution. Extensive experiments on the Berkeley segmentation benchmark show that the proposed algorithm outperforms the state of the art in all the standard evaluation metrics. In this paper, we propose a real-time image superpixel segmentation method with 50 frames s by using the density-based spatial clustering of applications with noise (DBSCAN) algorithm. In order to decrease the computational costs of superpixel algorithms, we adopt a fast two-step framework. In the first clustering stage, the DBSCAN algorithm with color-similarity and geometric restrictions is used to rapidly cluster the pixels, and then, small clusters are merged into superpixels by their neighborhood through a distance measurement defined by color and spatial features in the second merging stage. A robust and simple distance function is defined for obtaining better superpixels in these two steps. The experimental results demonstrate that our real-time superpixel algorithm (50 frames s) by the DBSCAN clustering outperforms the state-of-the-art superpixel segmentation methods in terms of both accuracy and efficiency. In this paper, we present a superpixel segmentation algorithm called linear spectral clustering (LSC), which is capable of producing superpixels with both high boundary adherence and visual compactness for natural images with low computational costs. In LSC, a normalized cuts-based formulation of image segmentation is adopted using a distance metric that measures both the color similarity and the space proximity between image pixels. However, rather than directly using the traditional eigen-based algorithm, we approximate the similarity metric through a deliberately designed kernel function such that pixel values can be explicitly mapped to a high-dimensional feature space. We then apply the conclusion that by appropriately weighting each point in this feature space, the objective functions of the weighted K-means and the normalized cuts share the same optimum points. Consequently, it is possible to optimize the cost function of the normalized cuts by iteratively applying simple K-means clustering in the proposed feature space. LSC possesses linear computational complexity and high memory efficiency, since it avoids both the decomposition of the affinity matrix and the generation of the large kernel matrix. By utilizing the underlying mathematical equivalence between the two types of seemingly different methods, LSC successfully preserves global image structures through efficient local operations. Experimental results show that LSC performs as well as or even better than the state-of-the-art superpixel segmentation algorithms in terms of several commonly used evaluation metrics in image segmentation. The applicability of LSC is further demonstrated in two related computer vision tasks. We present a novel image superpixel segmentation approach using the proposed lazy random walk (LRW) algorithm in this paper. Our method begins with initializing the seed positions and runs the LRW algorithm on the input image to obtain the probabilities of each pixel. Then, the boundaries of initial superpixels are obtained according to the probabilities and the commute time. The initial superpixels are iteratively optimized by the new energy function, which is defined on the commute time and the texture measurement. Our LRW algorithm with self-loops has the merits of segmenting the weak boundaries and complicated texture regions very well by the new global probability maps and the commute time strategy. The performance of superpixel is improved by relocating the center positions of superpixels and dividing the large superpixels into small ones with the proposed optimization algorithm. The experimental results have demonstrated that our method achieves better performance than previous superpixel approaches.