# A Two-Stage Gradient Ascent-Based Superpixel Framework for Adaptive Segmentation
## 4 Experiment and Analysis
### Algorithm Complexity and Computational Efficiency  
Since superpixels are often generated to speed up the subsequent visual analysis, the algorithm should performs efficiently in various practical tasks. In the process of generating sSLIC superpixels, clustering regions without apparent changes are excluded from global iteration. For that reason, aggregation computation on a number of pixels can be reduced significantly.  
Figure 5 describes the dynamic iteration guided by local interruption criterion. As mentioned in Section 2, the algorithm is modified to adapt local difference, thus it is related to intrinsic image characteristics. Three images with different degrees of smoothness and homogeneity are chosen from BSDS500 to illustrate the improvement. As depicted in Figure 5, a small target is in front of a single background, which can be regarded one simple image. In that case, almost all superpixels are initialized with uniform information that are completely unnecessary to update. On the other hand, once neighboring superpixels contain intersecting information, there is a relatively long time to reach stabilization. Figure 5 counts the amount of changes of interrupted superpixels during iterating those three images with simple, normal, complex information respectively. In general, an increasing number of superpixels skip clustering during global iterating, which in turn reduces the elapsed time in the next iteration. When all regions stop updating, sSLIC terminates in advance, that is the reason why it could achieve higher efficiency than conventional SLIC.  
Figure 4: Quantitative evaluation of different algorithms in terms of boundary adherence. (**a**) Boundary recall; (**b**) Under-segmentation error.  
Figure 6 presents the comparison of runtime on different algorithms. Figure 5(a) illustrates the performance on BSDS500 dataset with respect to various superpixel sizes. In Figure 5(b), plenty of natural images are collected to measure the efficiency in different image scales together with BSDS500. The additions range from \(800\times 600\) to \(1600\times 1200\) with multiple characteristics, and started with approximately 200 pixels in each superpixel on average. As shown in Figure 6, the complexity of SLIC, watershed and LSC is all linearly associated with the number of pixels in images, as well as being irrespective of superpixel size. The proposed method maintains \(O(N)\) complexity, which can be high-efficiently performed by sSLIC in global and watershed in small amounts, the remaining time is mainly spent on determining under-segmentation and calculating the markers. But it still has comparable time efficiency to LSC and SLIC.  
Figure 5: Dynamic iteration guided by local interruption criterion in sSLIC processing with different image characteristics. (**a**) Simple image; (**b**) Normal image; (**c**) Complex image; (**d**) The amount of change of interrupted superpixels during iterating.  
Figure 6: Comparison of execution time for different algorithm to generate superpixels. (**a**) Time required for superpixels of increasing number (LSC is not plotted due to its relatively slow speed); (**b**) Time required for images of increasing size.