# NICE: Superpixel Segmentation Using Non-Iterative Clustering with Efficiency
## 3 Non-Iterative Clustering with Efficiency
### Accelerated Implementation Based on Recursion
In the above process, only 25 th and 48 th are involved in global priority sorting after enqueueing, while the other two pixels derive from 48 th and directly inherit its label without any additional computation. Figure 4: Detailed local inspecting and labeling processes from 48 th to 50 th sequentially of SNIC. Solid arrows stand for popping and labeling in corresponding label maps, while dotted arrows represent inspecting and pushing for the next step. Therefore, the main idea of AIR can be briefed as follows. In general, for a pixel \(I_{new}\) inspected by one of its 4-neighbor elements that previously becomes the frontier pixel \(I_{n}\), it can be directly assigned the same label \(k\) as the latter, only if  
\[D(I_{new},S^{\prime}{}_{k})\leq D(I_{n},S_{k}), \tag{5}\]  
where \(S_{k}\) and \(S^{\prime}{}_{k}\) is the cluster before and after updated by merging \(I_{n}\) in Equation (3), respectively. The above equation can also be simply denoted as \(Q(I_{new})\leq Q(I_{n})\). Recursively, for a subsequently inspected pixel \(I^{\prime}{}_{new}\) derived from \(I_{new}\), it can be directly assigned when \(Q(I^{\prime}{}_{new})<Q(I_{new})\), wherein  
Figure 5: Heap structure updating processes of the priority queue from 48 th to 50 th sequentially in SNIC. (**a**) Popping 48 th from \(Q\); (**b**) pushing 49 th on \(Q\); (**c**) a temporary state after sorting 49 th in \(Q\); (**d**) Popping 49 th from \(Q\); (**e**) pushing 50 th on \(Q\); (**f**) a temporary state after sorting 50 th in \(Q\). Solid elements indicate that they are newly inspected and pushed in the current step, and their storage location is redirected by solid arrows. Other hollow nodes represent the elements that are inspected before but not labeled. Note that 13 th is the last leaf node which recursively executes a sift-up or sift-down operation to modify the structure redirected by dotted arrows, as well as some of hollow nodes with dotted outlines. Figure 6: Array structure updating processes in the priority queue from 48 th to 50 th sequentially in SNIC. (**a**) Popping 43 rd from \(Q\) before pushing 25 th and 48 th; (**b**) pushing 49 th on \(Q\); (**c**) pushing 25 th and 49 th on \(Q\); (**d**) popping 48 th to 50 th from \(Q\) before pushing 8 th and 51 th. The sequence of elements is corresponding to the minimum heap in Figure 5. Solid elements indicate that they are newly inspected and pushed in the current and next step. A last-in-first-out (LIFO) stack with dotted arrows means that the elements are popped in the batch. Notice that there is more than one 25 th in each array that is inspected by different pixels. the cluster is updated after merging \(I_{new}\). The strategy also explains the reason why it fails to form a batch in Figure 6a (\(Q(I_{25 th})>Q(I_{48 th})>Q(I_{43 th})\)) and 6d (\(Q(I_{51 th})>Q(I_{8 th})>Q(I_{50 th})\)), respectively. In addition to the single chained derivation demonstrated in Figure 4, a more complex situation is multi-pixels inspection with very similar priorities. Assuming that \(Q(I_{8 th})<Q(I_{51 st})<Q(I_{50 th})\) in Figure 6d (actually, the inequations in this paragraph are not satisfied), both two elements 8 th and 51 st fit Equation (5), they must be treated separately. Otherwise, if these two elements are together pushed onto the stack, some pixels supposed to be derived from 8 th would be orphaned. Thus, only 8 th with a higher priority is selected into the stack. Furthermore, since \(Q(I_{51 st})<Q(I_{21 st})\), for maintaining the logic of priority queue in conventional SNIC, 51 st must be the new top-most element of \(Q\) before sorting the neighboring elements of 8 th. That is, AIR must run in a single chained recursion that at most one neighboring element can be pushed on the stack. When the recursion originated from 8 th is finished, 48 th, 49 th, 50 th and 8 th along with its derivations are all pushed in the batch with the label of 48 th. Thus, the question turns into sorting in a priority queue that the top-most element is 51 st.