# NICE: Superpixel Segmentation Using Non-Iterative Clustering with Efficiency
## 1 Introduction  
Superpixels perceptually group similar pixels into region-level features while heavily reducing the number of entities. Owing to the outstanding performance on region description, superpixel segmentation gradually becomes a fundamental pre-processing step in advanced visual tasks. Increasingly, many practical visual applications, such as image and video segmentation [1, 2], target tracking [3], saliency detection [4] and remote sensing classification [5], are developed based on superpixels instead of pixel-wise features to achieve better performance. Known as image over-segmentation [6], the target of superpixel segmentation is to generate a coherent grouping of pixels [7]. A growing number of superpixel algorithms have been put forward to improve the representative efficiency over the past two decades. Some prominent methods are incorporated into the state-of-the-art in this field. Meanwhile, several properties are commonly expected for good superpixels, such as accuracy, uniformity, compactness and efficiency [8]. Among them is Simple Linear Iterative Clustering (SLIC) [9], which typically provides an eligibly balanced trade-off between appearance homogeneity and shape regularity. Thanks to its concise yet enlightening principle, SLIC becomes more appropriate for deployment and expansion than other approaches in recent works [10, 11, 12, 13, 14, 15]. Whereas in fact, deficiencies and shortcomings are also exposed in SLIC and itsvariants for their iterative clustering framework. Firstly, redundant computations in overlapping local regions are repeated in more than an iteration. In addition, a split-and-merge heuristic is necessary for region connectivity [16]. What's worse, assignment and update steps within these methods are performed separately, leading to detrimental convergence. Theoretically, SLIC is an instructive approach that restricts k-means algorithm into small windows to simplify the calculation of Centroidal Voronoi Tessellation (CVT) [17] in a 5-dimensional Euclidean space. Combining 3-dimensional digital value and 2-dimensional space features as weighted vectors, all pixels are repeatedly assigned to the nearest seeds till they all satisfy the convergence condition. Similarly, Linear Spectral Clustering (LSC) [12] introduces weighted k-means into a 10-dimensional feature space based on an elaborate kernel matrix. By preserving the global image properties, LSC achieves more perceptually satisfactory segmentation results. [PERSON] et al., proposed Fast Linear Iterative Clustering (FLIC) [15], in which a novel active search mechanism and a back-and-forth traversal strategy based on neighboring continuity is applied. It takes the place of fixed search ranges in other variants of SLIC and realizes rapid convergence of linear clustering. Intrinsic manifold SLIC (IMSLIC) [16] extends SLIC by an elaborate distance measurement and a 2-dimensional manifold feature space mapping. The new framework can make superpixels sensitive to image content without post-processing to enforce connectivity. In [10], the deviation of cluster centers in each iteration is adopted as a homogeneity cue to guide the convergence of candidate regions. Wherein the updating step, only some instable SLIC superpixels are updated by the local k-means method. Therefore, much redundant searching computation can be avoided. Superpixel Sampling Network (SSN) [11] proposes a new differentiable model for SLIC that turns it into a differentiable algorithm by relaxing the nearest neighbor constraints. In this way, conventional hand-crafted features can be trained by deep networks, which shows a better development prospect for this field. More recently, to overcome the underlying limitations induced from the iterative k-means clustering within SLIC-like methods, [PERSON] et al., proposed simple non-iterative clustering (SNIC) [8] algorithm as an optimization. As the name suggests, SNIC performs in a non-iterative way and removes the limitations while it achieves desirable performance.