# NICE: Superpixel Segmentation Using Non-Iterative Clustering with Efficiency
## 3 Non-Iterative Clustering with Efficiency
### Elimination of Inspection Redundancy  
In the procedure depicted in Figure 1, a large number of pixels are inspected several times since they become 4-neighbor elements of frontier pixels more than once. For example, in the upper left of Figure 2b, 62 nd is newly inspected by 60 th of the cluster that grows from B in green. Whereas it would be checked again in the next step due to 61 st is the second-most prior element in that time. A different situation is boundary pixel such as 53 rd in the upper right of Figure 2a, which is inspected by 21 st, 22 nd and 70 th in different time. Particularly, in the orange regions of Figure 2c, 8 th is inspected fully four times (B, 25 th, 50 th and 78 th) from beginning to end. Generally, in conventional SNIC, a pixel in corners, boundaries and inner images is respectively inspected 2, 3 and 4 times, except it is labeled very early. Different from the first two situations, there are huge repetitions of inspection on the main internal pixels. It creates a large number of redundant elements in the priority queue that results in great computation and memory cost. Fundamentally, in the joint assignment and updating step of conventional SNIC, only the distance metric \(D\big{(}I_{j},S_{k}\big{)}\) in Equation (1) is adopted to sort priority of \(I_{j}\) in \(Q\). It neglects the connection relationship of \(I_{j}\) and its corresponding frontier \(I_{i}\). Afterwards, follow-up inspections on \(I_{j}\) may create other distance metrics as new elements of \(Q\). When \(I_{j}\) becomes the top-most, it pops the minimum distance and other identical elements in \(Q\) are then meaningless for their corresponding clusters. As a matter of fact, not the entire inspections on a neighboring element is necessary for its final attribution. In Figure 2, for example, based on the spatial label context, it is apparent by which cluster the isolated unlabeled pixels are eventually absorbed [20]. In other words, a newly inspected neighboring element would probably be assigned the same label as the corresponding frontier pixel, especially in some homogeneous regions. Thus, additional 1-3 inspections merely renew the minimum value of \(Q\big{(}I_{j}\big{)}\) so that, more or less, it advances the assignment order of \(I_{j}\) in \(Q\). Only in the controversial regions, such as the boundaries of objects in Figure 1f, multiple inspections may classify the pixels into clusters more reasonably. Based on the above analysis, this subsection proposes a simple yet effective inspection strategy to eliminate the redundant creation of neighboring elements. The inter-pixel correlation between  
Figure 2: Local inspecting processes of SNIC in detail. Three representative pixels are shown as examples of inspection redundancy when they are labeled for the first time. (**a**) Boundary pixel 53 rd; (**b**) corner pixel 62 nd; (**c**) internal pixel 8 th. Solid arrows stand for popping and labeling in corresponding label map. Notice that there are more than one identical elements with the top-most element in each priority queue. adjacent pixels is taken into consideration, along with the distance relationship of pixel inspection and cluster center. In what follows, the strategy referred to as Elimination of Inspection Redundancy (EIR) is described in more detail. Firstly in Figure 3a,b, the direction of 4-neighbor inspection is modified from clockwise rotation to cross where a frontier is the intersection. An intrinsic interaction on position is then enhanced for two pairs of partner pixels of unidirection (namely, left \(l_{l}\) to right \(l_{r}\) and up \(l_{u}\) to down \(l_{d}\)). As shown in Figure 3c, during the process of neighboring inspection on \(l_{n}\), if \(l_{l}\) is newly checked and then labeled the same as \(I_{n}\) before \(I_{r}\) is assigned, \(I_{r}\) would be checked only once when  
\[D_{c}(I_{l},I_{r})=\left\|C(I_{l})-C(I_{r})\right\|_{2}<\sigma Q(I_{n}), \tag{4}\]  
where the parameter \(\sigma\) is a threshold of color similarity.