# NICE: Superpixel Segmentation Using Non-Iterative Clustering with Efficiency
## 2 Simple Non-Iterative Clustering  
Since the proposed improvements mainly works on SNIC, the conventional principle is reviewed at the beginning, as well as some notations and definitions in this paper. The basic idea of SNIC is demonstrated as follows:  
* An input 3-channel Lab image \(\{I_{i}\}_{i=1}^{N}\) is uniformly partitioned by a set of evenly distributed seeds \(\{S_{k}\}_{k=1}^{K}\), where \(I_{i}\) represents the \(i\) th pixel in the image plane with \(N\) elements, \(S_{k}\) means \(k\) th centroid of mass in grids with a step of \(s=\sqrt{N/K}\) and \(K\) is user-specified to expect the number of superpixels;
* For a pixel \(I_{i}\) in the image plane, it can be represented as a 5-dimensional Euclidean feature vector \(E(I_{i})=[l(I_{i}),a(I_{i}),b(I_{i}),x(I_{i}),y(I_{i})]\). Specifically, \(E(I_{i})\) is composed of a vector of the 3-channel Lab digital values \(C(I_{i})=[l(I_{i}),a(I_{i}),b(I_{i})]\) and image position coordinates \(P(I_{i})=[x(I_{i}),y(I_{i})]\);
* In the initialization step each element of \(\{S_{k}\}_{k=1}^{K}\) with unique labels are initialized on the uniform grid in the image plane as original cluster centers. A priority queue \(Q\) with increasing order is introduced which always returns the element \(Q_{\min}\) with the minimum key value while it is not empty. For each element \(I_{i}\in\{I_{i}\}_{i=1}^{N}\), \(Q(I_{i})\) is adopted to represent the distance to corresponding cluster center, and then recorded as the key value for sorting in \(Q\). Specially, for each seed \(S_{k}\), all information is included in a vector node \([E(S_{k}),\;k,\;Q(S_{k})]\) with \(Q(S_{k})=0\). Then all seed vectors are pushed on \(Q\). * In the joint assignment and updating step, \(\{S_{k}\}_{k=1}^{K}\) is updated using online averaging of all clusters. For an unlabeled neighboring pixel \(I_{i}\), inspected by the currently popped pixel whose cluster centered at \(S_{k}\), the distance \(Q(I_{i})\) is calculated by Equation (1) where it is identical to \(D(I_{i},S_{k})\). Then \(I_{i}\) is pushed on \(Q\). \[D(I_{i},S_{k})=\sqrt{\|C(I_{i})-C(S_{k})\|_{2}^{2}+\lambda^{2}\|P(I_{i})-P(S_ {k})\|_{2}^{2}},\] (1) where \(\lambda\) is the quotient of maximal \(C(I_{i})\) and \(P(I_{i})\) within this cluster to normalize color and spatial proximity, and \(\|\|_{2}\) represents the Euclidean metric;
* Followed by all neighboring pixels pushed around the frontier pixel, secondly, \(Q_{\min}\) is acquired by popping the top-most element from \(Q\), which corresponds to a pixel \(I_{m}\) containing the global minimum distance in Equation (2) \[I_{m}=\arg\min D(I_{i},S_{k}),\;i\in[1,N],k\in[1,K],\] (2) that is, \(Q_{\min}=Q(I_{m})\). Then a new label is assigned to \(I_{m}\) in accordance with its nearest cluster center, and \(I_{m}\) turns into the frontier of its cluster. Meanwhile, the feature vector of the cluster centroid is updated by \[E\Big{(}\widetilde{S_{k}}\Big{)}=\sum\
olimits_{i\in\Omega_{k}}[C(I_{i}),P( I_{i})]\;/\;|\Omega_{k}|,\] (3) where \(\Omega_{k}\) means the cluster which is centered at \(S_{k}\), and \(|\Omega_{k}|\) means the number of pixels in \(\Omega_{k}\). * The latter two procedures are repeated till \(Q\) is empty. For further illustrating the principle of NICE vividly, as well as explaining the distinction from SNIC, a dynamic segmentation procedure on one \(10\times 10\) polychrome map fragment is partitioned in Figure 1. To keep it simple, four-quadrant initialization is adopted in following schematic diagrams. As shown in Figure 1b, four pixels are firstly pushed on the priority queue \(Q\) as initial seeds. Since they are identical to the original cluster centers, all seeds share the same priority. According to the order of entry, they are denoted by A, B, C and D from top to bottom, respectively. After that is popping the top-most element A, which becomes the current frontier pixel and then clockwise inspects its 4-neighbor elements. Similarly, the other three seeds execute popping and inspecting successively.