# A Two-Stage Gradient Ascent-Based Superpixel Framework for Adaptive Segmentation
## 3 Proposed Two-Stage Adaptive Image Segmentation Framework
### Speeded-Up simple Linear Iterative Clustering  
Figure 1 illustrates the subjective comparison of SLIC and the proposed sSLIC by three images. In general, with the increasing of iterations, the segmentation performance becomes better. In fact, the cluster is updated by the local information of pixels in a certain region, the new center is displaced and more pixels are correctly classified. [PERSON] (1999) indicates that 10 iterations are sufficient for most natural images, and conventional SLIC uses it as a fixed parameter in its open source code. Practically, that work takes up most of the runtime, by statistical analysis, along with the iteration progressing, the proportion of updating step or iteration period also increases. For one \(321\times 481\) image, it even spends half of total time when iteration exceeds 8 times. Besides, it is obvious in the first two rows of Figure 1, the segmentation results change hardly when iterations increase from 5 to 10. Due to indiscriminately global termination criterion by (2) in SLIC, this drawback usually results in redundant revisiting for clusters without large changes. What's more, in many specific applications such as saliency detection, video compression and target recognition, it is reasonable to pay less attention on background, especially in the image border Sohn et al. (2018).  
Figure 1: \(Cont\).  
Therefore, the efficiency could be higher if the algorithm is adaptive for local difference. In this work, the deviation of cluster centers in each iteration is obtained as a local interruption criterion to guide the convergence of candidate regions. The only difference is that, in updating step, local k-means method would not be adopted in every search region of clusters, only some with instability repeat to calculate the spatial-color feature for the new center.  
In what follows the segmentation algorithm is described in more details. Before the second iteration, each cluster center has moved from its original grid center by initializing to a new position \(C^{\prime}_{k}\), which can be recorded and described as a feature set \(C^{\prime}=\left\{C^{\prime}_{i}\right\}_{i=1}^{k}\). After updating, all elements of \(C^{\prime}\) change in various degree and a new set \(C^{\prime\prime}\) is obtained, and the spatial offset of corresponding \(i\)th element from \(C^{\prime}\) to \(C^{\prime\prime}\) can be defined as \(\Delta C^{s\prime}_{i}=\left\|C^{s\prime}_{i}-C^{s\prime}_{i}\right\|\). Then in \(\Delta C^{s\prime}_{i}=\left\{\Delta C^{s\prime}_{i}\right\}_{i=1}^{k}\), a threshold parameter \(TH\) is adopted to control the subsequent iterations. If \(\Delta C^{s\prime}_{i}<TH\), cluster centered at \(C^{s\prime\prime}_{i}\) would be evaluated as a homogeneous region, and most pixels tend to belong to the cluster. Therefore, the subsequent iterations become unnecessary, which should be aborted to avoid redundant computation. This modified process is repeated 10 times or all clusters stop updating in advance, which eventually makes a difference among all clusters during updating and effectively avoids a mass of pixels being compared by (1). A visual evaluation of sSLIC superpixel segmentation is shown in the last two rows of Figure 1, it is obvious that segmentation performance dose not degrade badly. A quantitative analysis of speed improvement is described in Section 4.