Rooted Spanning Superpixels

Three types of formulations can be distinguished in the existing literature: graph partitioning, boundary evolution and feature space analysis.

Graph partitioning is the most common formulation for superpixel boundary determination. A vertex denotes a pixel, an edge links two neighboring pixels, and all the vertices and edges constitute a graph representing an image. Superpixel segmentation is achieved by partitioning the graph into a set of connected subgraphs, each of which denotes one superpixel. The pioneering work is based on Normalized Cut (NC) (Ren and Malik 2003). It measures both the total dissimilarity between the different subgraphs as well as the total similarity within the subgraphs by a criterion based on normalized cut, and solves a generalized eigenvalue system to find the optimal cut partitioning the graph (Shi and Malik 2000). It produces uniform, compact and coherent superpixels. However, its computational and memory requirements are high and its boundary adherence is relatively poor. Some methods such as Superpixel Lattice (SL) (Moore et al. 2008), Lattice Cut (LC) (Moore et al. 2010) Superpixels via Pseudo-Boolean Optimization (SPBO) and Superpixels via Quaternary Labeling (SQL) (Chai 2019) find both horizontal and vertical boundaries to produce a regular grid of superpixels. However, the segmentation performance is sacrificed by these constraints. Compact Superpixels (CS), Variable Patch Superpixels (VPS), and Constant Intensity Superpixels (CIS) work similarly but generate superpixels without lattice structure (Veksler et al. 2010). These approaches optimize an objective function to find the graph cuts. The objective function consists of a data term and a smooth term. The data term favors coherent superpixels and the smooth term encourages the boundaries to align with intensity edges. Their computation costs are high and their performances are not good. Entropy Rate Superpixels (ERS) result from greedy optimization of an objective function consisting of entropy rate of random walk on graph and a balancing term (Liu et al. 2011). The entropy rate favors compact and homogeneous superpixels, while the balancing function encourages uniform superpixels. It achieves good segmentation performance with a relatively high computational cost. Minimum spanning tree is an alternative to graph cut. Graph Based Superpixels (GBS) (Felzenszwalb and Huttenlocher 2004) performs an agglomerative clustering such that each cluster is the minimum spanning tree of the constituent nodes. The generated superpixels adhere well to image boundaries. The clustering is very fast. However, the size and number of superpixels cannot be controlled explicitly, and the shapes of superpixels are arbitrary. The locality, compactness and uniformity are poor.

Boundary evolution is an alternative to graph partitioning for boundary determination. Two ways of evolution have been developed for superpixel segmentation. One is growing superpixels from some given centers, the other is adjusting some given boundaries. Turbopixel (TP) is a representative of the first category (Levinshtein et al. 2009). Originating from the given centers, Turbopixels grow with their boundaries evolving step by step. Boundary evolution is driven by geometric flow calculated from grown regions and the rest regions. In this framework, geodesic distance is introduced as a measure of structure and layout of superpixels, and centers are relocated to generate structure-sensitive superpixels (Wang et al. 2013). The main drawback of these methods is very high computational cost, restricting practical applications. Superpixel Extracted via Energy-Driven Sampling (SEEDS) falls into the second category (Van den Bergh et al. 2015). Starting from an initial partitioning, it adjusts the boundaries by exchanging pixels or blocks of neighboring superpixels. An objective function based on superpixel colors and boundary shapes is defined to favor coherent superpixels. A simple hill-climbing approach is employed to optimize the objective function efficiently. However, it may not converge to optimal segmentation in some cases, and it lacks adaptivity between compactness and adherence. By constructing an objective function based on boundary and topology preserving Markov Random Fields, Efficient Topology Preserving Segmentation (ETPS) achieves excellent performance (Yao et al. 2015). But it is not fast enough to support realtime applications.

Feature space analysis is another formulation for superpixel segmentation. Working in feature space, it determines a superpixel by finding its pixels instead of its boundary. There are two ways to achieve this goal. One is mode seeking, and the other is k-means clustering. Mean Shift (MS) and Quick Shift (QS) are two techniques for searching modes of a density function (Comaniciu and Meer 2002; Vedaldi and Soatto 2008). Once modes in the image feature space are found, pixels converging to same mode constitute one superpixel. They are slow. The size and number of superpixels cannot be controlled explicitly and the shapes of superpixels are usually irregular. Simple Linear Iterative Clustering (SLIC) is a constrained k-means clustering (Achanta et al. 2012), which searchs pixels in a limited region instead of the whole image to generate compact superpixels efficiently. VCell is also built upon k-means clustering (Wang and Wang 2012). Edge-Weighted Centroidal Voronoi Tessellations is developed to constrain superpixel boundary. The weak point of k-means clustering is no guarantee of connectivity. SLIC relies on post-processing to repair connectivity whereas VCell relies on two special mechanisms to maintain connectivity. As an improved SLIC, Simple Non-Iterative Clustering (SNIC) updates clusters by incorporating pixels connected to the clusters (Achanta and Süsstrunk 2017). It is faster than SLIC since no iteration is involved. The k-means clustering is based on the color difference and spatial distance between pixels and cluster centers, which facilitates shape regularization. However, only mean value of the superpixels are referred in clustering, more cues can be utilized to improve performance.

Superpixel has been extended to supervoxel, which is a three-dimensional version and has many applications in volumetric image segmentation (Lucchi et al. 2012) and video preprocessing (Xu and Corso 2012). Some methods treat video as a series of images, and segment them frame by frame. The others treat video as volumetric image. An evaluation of supervoxel methods for video processing is presented in Xu and Corso (2012), where, Mean Shift (MS) (Comaniciu and Meer 2002), Graph Based (GB) (Felzenszwalb and Huttenlocher 2004), Hierarchical Graph Based (GBH) (Grundmann et al. 2010), and NC (Shi and Malik 2000), Segmentation by Weighted Aggregation (SWA) (Sharon et al. 2000) and Temporal Superpixels (TSP) (Chang et al. 2013) have been evaluated and compared.

The above formulations have both positive and negatives. For examples, GBS is fast but does not allow number and shape controlling, k-means clustering based methods allow such controlling but needs advanced measures for the differences between pixels and superpixel centers.

This paper adapts minimum spanning tree and proposes a formulation similar to image foresting transform (Falcão et al. 2004) to integrate the positives of different formulations. First, it adapts the underlying graph to represent vertex values instead of edge weights. Second, it selects some vertices to serve as roots of trees in spanning forest. Third, it introduces a path-cost function to measure both color similarity and spatial closeness between the seeds and the remaining pixels. Fourth, superpixel segmentation is formulated as searching a rooted spanning forest of the underlying graph with respect to the roots and path-cost function. Finally, a set of first-in-first-out (FIFO) queues are introduced to maintain the candidates to search the forest efficiently.

Based on this formulation, superpixel segmentation is achieved via region growing as depicted in Fig. 1. Starting from the evenly distributed seeds, the superpixels are guided by a path-cost function to grow uniformly in homogeneous regions and adaptively when they touch object boundaries, the superpixels grow pixel by pixel until they cover the whole image. The number of superpixels is controlled by the number of seeds. Good performances are assured by connecting each pixel to the similar seed, which are dominated by the path-cost function. Benefiting from the FIFO queues, superpixels grow efficiently and the proposed algorithm is much faster than the other superpixel and supervoxel methods.

The rest of this paper is organized as follows: background and adaptation of rooted spanning forest are presented in Sect. 2, rooted spanning superpixels are formulated in Sect. 3, experiments with evaluations and comparisons are presented in Sect. 4, and conclusions are drawn in Sect. 5.

Our formulation is based on an undirected graph, which is called as a graph for simplicity. A graph is an ordered pair \(G=(V_G,E_G)\), where \(V_G\) is a nonempty set and E is a set of unordered pairs of elements of \(V_G\), i.e. \(E_G \subseteq V_G\times V_G\). Elements of \(V_G\) and \(E_G\) are called the vertices and the edges respectively. Each edge \(e=(s,t) \in E_G\) links two vertices \(s\in V_G\) and \(t\in V_G\). If two or more edges link the same two vertices, the edges are called multiple edges. If an edge links a vertex with itself, the edge is called a loop. A graph is simple if it has no loops and no multiple edges. A weighted graph associates a weight with every edge in the graph.

A simple path in a graph \(G(V_G,E_G)\) is an alternating sequence of distinct vertices and edges \(\pi =v_1 e_1 v_2 e_2\ldots v_{p-1} e_{p-1} v_p\), where \(e_i=(v_i,v_{i+1}) \in E_G, i=1,\ldots ,p-1\). \(v_1\) and \(v_p\) are the origin and the destination of the path, and they are denoted as \(v_1= org (\pi )\) and \(v_p= dst (\pi )\) respectively. When \(p=1\), the path is called a trivial path. The weight of a path is the sum of the weights of the traversed edges. A graph is connected if any two vertices are connected by one or more paths. If any two vertices are connected by exactly one path, the graph is called a tree. The weight of a tree is the sum of the weights of all its edges. A forest is a disjoint union of trees.

A spanning tree of a connected graph is a tree that connects all the vertices and each edge of the tree is an edge of the underlying graph. One graph usually has many different spanning trees. A minimum spanning tree of a weighted connected graph is a spanning tree whose weight is no more than the weight of every other spanning tree. A minimum spanning forest of a weighted disconnected graph is a union of minimum spanning trees for its connected components. As demonstrated in Fig. 2b, the minimum spanning forest consists of three trees; each is a minimum spanning tree of one connected component of the disconnected graph in Fig. 2a.

Minimum spanning forest has been applied to image segmentation (Felzenszwalb and Huttenlocher 2004). However, the graph representing an image is a connected graph as in Fig. 2c rather than a disconnected one as in Fig. 2a. It is partitioned into some components by removing all edges whose weights are above a weight threshold. Fig. 2d is a minimum spanning forest of the graph in Fig. 2c based on a weight threshold indicated by the thick edges. This approach deals with the edge weights derived from the pixel values. These derived values may introduce some extra errors in segmentation. Moreover, the number of segments and their coverages are not controlled explicitly but depend on the thresholds implicitly.

An intuitive picture of the above concepts is depicted in Fig. 2, where Fig. 2f, h are a rooted spanning tree and forest of the underlying graph Fig. 2e, g respectively. As indicated by the same thickness, no weights are assigned to the edges. Graph partitioning is based on the vertex values (colors).

A graph G(V, E) is employed to represent an image I(p). Each vertex \(v_p\in V\) represents a pixel p, and each edge \(e_{p,q}=(v_p,v_q)\in E\) links a pair of neighboring pixels p and q. It is not necessary to explicitly store the edges since they are recoverable based on a given neighborhood system. Therefore, no explicit graph is constructed and the image is dealt with directly. Each pixel is treated as a vertex and it is linked to its 8 nearest neighbors based on the second-order neighborhood system employed in this paper. When the underlying graph represents a volumetric data, each vertex represents one voxel and it has 26 neighbors.

A set of seed pixels are selected to serve as the roots of spanning forest to control the number and locality of superpixels. They are selected regularly and evenly on the image plane as shown by the initial state in Fig. 1. Given the expected number of superpixels K, the expected width of a superpixel is \(w=\sqrt{N/K}\), where N is the total number of pixels. Seeds are selected by sampling the rows and columns with an interval of w. A schema similar to that of SLIC can be adopted to adjust the seeds within their \(3\times 3\) windows, however, no performance gains are found in our experiments.

A path-cost function \(f(*)\) is developed to measure the color similarity and spatial closeness between a seed pixel and another pixel through a path. A general function for a path \(\pi =v_1 e_1 v_2 \ldots v_{p-1} e_{p-1} v_p\) iswhere the edges are excluded from the variable list since they have no weights as declared in Sect. 2.2.

An existing path-cost function is the geodesic distancewhere \(\Vert I(v_i)-I(v_{i-1})\Vert _2\) is the \(L_2\) norm of color difference between two successive pixels, and \(\Vert v_{i-1}v_i\Vert _2\) is their Euclidean distance. However, this color term fails to measure similarity between two ends of a path shown in Fig. 3a. The alternating values amount to a large geodesic distance for two ends of the same value.

As illustrated in Fig. 3b, this paper utilizes global characteristics of a path instead of sum of local ones to measure color similarity of path ends, and proposes two novel path-cost functions.

Without loss of generality, assume that the image has a single channel. Let I(v) be the value of v, the maximal difference between the origin and rest pixels on path is calculated asand the range of values of all pixels on path is calculated asThe maximal difference acts as a barrier between the origin and destination. It reflects the cost of going from origin to destination along the path. Similarly, the range of values also reflects such cost. They are more robust than geodesic distance since they avoid summing local derivatives. Moreover, they outperform a simple difference between origin and destination, which does not take the intermediate pixels into account.

For images of multiple channels, the pixel value is a vector, the differences in Eqs. 3 and 4 are replaced by their \(L_{\infty }\) norms. Since only comparisons are involved, it is quite efficient. Moreover, by experiments, it is found to outperform alternative norms such as \(L_2\) norm, which need floating-point operations.

Spatial closeness is measured in the same way by treating pixel coordinates as extra channels:where x(v), y(v), z(v) are three coordinates of v, \(I_{M{+}1}, I_{M{+}2}, I_{M+3}\) are three additional channels, \(\lambda \) and \(\lambda '\) are two scaling factors. \(I_{M+3}(v)\) is employed only in supervoxel segmentation. Usually, the third dimension has different meaning (e.g. time in video), and it needs a different scaling factor \(\lambda '\).

For each pixel, its color value is in \(\{0,1,\ldots ,255\}\), but its coordinates can be large when the size of an image is very large. By normalizing pixel coordinates using the expected width of a superpixel \(w=\sqrt{N/K}\), Eq. 5 is written as:where \({\hat{\lambda }},{\hat{\lambda }}'\) are two normalized scaling factors, \({\hat{x}}(v),{\hat{y}}(v), {\hat{z}}(v)\) are three normalized coordinates of v.

The unified cost functions for maximal difference and range of values areThe cost is calculated efficiently by comparisons and subtractions. When the path \(\pi \) extend to a new pixel \(v_{p+1}\), its maximal difference cost is calculated incrementally asSimilarly, the range of values can also be computed incrementally. The costs of all root-originated paths can be computed very efficiently based on the incremental computing.

The global objective function is defined as the sum of path-costs for all the vertices (pixels):where \(\pi (v_p)\) is a path connecting one root and \(v_p\), \(f(\pi )\) takes either \(f_{\infty }^d(\pi )\) or \(f_{\infty }^r(\pi )\). Unlike the variables in the existing objective functions for superpixel segmentation, the variables are paths. Therefore, a path connecting to a root denoting a superpixel need to be determined for each pixel. Based on the inductive definition in Sect. 2.2.2, the paths for all pixels must be determined progressively. In each step, the existing root-originated paths are extended one step to reach a new pixel \(v_p\) by:where \(\tau e v_p\) is an one-edge-extension of \(\tau \) to \(v_p\), \(\varPi \) is the set of existing root-originated paths, \(\tau \in \varPi \) means that \(\tau \) is an existing root-originated path.

The root-originated paths for a graph with two roots illustrated in Fig. 3c and a path-cost function in Eq. 4 are found as follows: First, \(\varPi =\{v_1,v_2\}\) as they are trivial. Second, since \(f^{r}(v_1e_1v_2)=1<2=f^r(v_3e_2v_2)\), \(\pi (v_2)=v_1e_1v_2\), \(\varPi =\{v_1,v_2,v_1e_1v_2\}\). Third, \(\pi (v_5)=\arg \min _{v_1e_1v_2e_6v_5}{f(v_1e_1v_2e_6v_5)}=v_1e_1v_2e_6v_5\), then \(\varPi =\{v_1,v_2,v_1e_1v_2e_6v_5\}\). Fourth, \(\pi (v_4){=}\arg \min _{v_1e_5v_4} {f(v_1e_5v_4)}=v_1e_5v_4\), then \(\varPi \) is updated to be \(\varPi =\{v_2,v_1e_1v_2e_6v_5,v_1e_5v_4\}\). Finally, \(\pi (v_6)=\arg \min _{v_3e_7v_6} {f(v_3e_7v_6)}=v_3e_7v_6\).

Without the requirement \(\tau \in \varPi \), a path \(\tau =v_3e_2v_2 \not \in \varPi \) can be extended to \(v_5\) such that \(f(v_3e_2v_2e_6v_5)=3<4= f(v_1e_1v_2e_6v_5)\). In this case, \(v_3e_2v_2e_6v_5\) has minimal cost but \(v_3e_2v_2\) is not a root-originated path. With this contradiction, the paths with optimal costs do not form a forest at all. The algorithms in Falcão et al. (2004) cannot deal with this contradiction. Instead, they accept only monotonic-incremental and smooth path-cost functions. By enforcing \(\tau \in \varPi \), the root-originated paths are extended step by step, and the above contradiction is resolved.

The inductive definition of root-originated paths allows the rooted spanning forest to be found progressively in a manner as Dijkstra’s algorithm (1959). In each step, it needs to sort all candidates to select the best one as Eq. 12. Although a balanced queue can be employed to store the candidates, the total time complexity of Dijkstra’s algorithm is \(O(m+n\log n)\), where m and n are the numbers of edges and vertices respectively.

The proposed solution is motivated by counting sort and bucket sort (Cormen et al. 2009). First, it divides the cost range into a set of equal-sized intervals (buckets) as bucket sort does. Second, it assigns an integer to each interval as required by counting sort. When only colors are considered, the proposed path-cost functions directly take integers in \(\{0,1,\ldots ,255\}\). When spatial coordinates are considered, real intervals need to be quantized into integers as the path-cost functions may take nonnegative real values. This quantization has little influence on segmentation.

A FIFO queue \(\omega _{y}\) is employed for a bucket to store the candidates whose costs are y. The candidates in one queue are served by FIFO schema, which resolves the sorting operation of bucket sort. The candidates in a queue \(\omega _{y_1}\) are served before those in \(\omega _{y_2}\) when \(y_1 < y_2\). Since one and only one FIFO queue is employed for each bucket (integer), the order of queues is fixed. Such fixed order resolves the sorting operation of counting sort. Based on these queues, the root-originated paths extend very efficiently since no sorting operation is needed. Since candidates with lower costs are served before those with higher costs, the existing root-originated paths always extend to their most similar pixels. In other words, all pixels are connected to their most similar seeds.

Multiple paths originated from different roots can extend simultaneously. Without loss of generality, let the seeds be partitioned into some groups indexed by \(0,1,\ldots ,X\) and the costs be quantized into \(0,1,\ldots ,Y\). Then, the number of seeds in x-th group is denoted as \(K_x\), the queue for cost y and xth group is denoted as \(\omega _{y,x}\). Path extending in the same group is carried out in serial while those in different groups can be carried out in parallel. As shown in Fig. 4, the simultaneous extending is synchronized by the path-cost. Such synchronization guarantees fair competition among different groups and assures coherent superpixels.

The seeds can be put into either one group or K groups. The former results in a serial algorithm. The latter requires a huge memory for the \(K*Y\) queues and is not useful in practice. Since 4 or 8 CPU cores are usually available in a personal computer, it is natural to partition the seeds into 4 or 8 groups, each being processed by one CPU core. A simple way is to group the seeds according to the 4 quadrants separating along central row and central column of the image. The key to achieve maximum speedup is the balanced groups in terms of the number of seeds.

Algorithm 1 describes the Rooted Spanning Superpixels (RSS) Algorithm based on the maximal difference. In this algorithm, line 1–5 initialize all variables, loop 6–12 labels the seed pixels, loop 13–33 propagates the labels to all the remaining pixels. It seems that the complexity depends on X and Y, however, many queues are usually empty. Actually, every pixel is labeled once and only once. It means that the complexity is O(N), where N is the total number of pixels. Therefore, the computation time is stable with respect to X, Y and K. The inner loop 14–32 can be carried out either in serial or in parallel. To adopt the range of values, it is necessary to record the maximum/minimum of each channel in \(\psi (*)\) and revise line 22 correspondingly. For supervoxels segmentation, line 20 need to loop over all 26 neighbors.

As in Fig. 1, different labels indicated by different colors are assigned to different seeds, they propagate pixel by pixel as the root-originated paths extend step by step, until all pixels are labeled. In a homogeneous region, all candidates have the same color as seeds and have a zero cost. The path extending and superpixel growing depends on the order of candidates pushed into the queue. It assures superpixels the uniform growing in homogeneous regions since the pixels close to seeds are served before the pixels far away. In a non-homogeneous region, they have different colors and costs. Pixels similar to seeds have lower costs and receive a priority. Therefore, they grow adaptively after they touch object boundaries. When the superpixel growing is parallelized, the order of service for candidates of the same cost may change. However, the final superpixels are influenced only by the boundary pixels in two narrow strips along the central row and central column respectively. Only a few of these pixels have the same cost with respect to neighboring seeds in different groups. Therefore, parallelization has little influence on the final superpixels.

RSS is scalable as it is capable to deal with different kinds of data in a unified way. On one hand, each pixel can take a gray value, a RGB vector, a RGBD vector, or even a vector of features. On the other hand, the data can be a 2-dimensional image, a 3-dimensional volumetric data, or a video.

Different path-cost functions can be adopted to define root-originated paths and to generate RSS. This experiment compares five cost functions: \(f^g(*)\) (Eq. 2), \(f^d_{\infty }(*)\) (Eq. 7), \(f^r_{\infty }(*)\) (Eq. 8), \(f^d_2(*)\) and \(f^r_2(*)\), where, \(f^d_2(*)\), \(f^r_2(*)\) are based on \(L_2\) instead of \(L_{\infty }\) norm.

The bare comparison is based on pixel colors but not pixel coordinates since the latter depend on a scaling factor \(\lambda \) whose effects will be analyzed in the following section. The overall performances on BSDS dataset are reported in Table 1. The geodesic distance is outperformed by the other four functions as lower AMR, AUE and AUV are better. Since the geodesic distance is a sum of derivatives, it is sensitive to local variations and noises. The other four functions are based on global characteristics, they overcome this shortcoming and significantly improve the performance.

One can observe that \(f^d(*)\) leads to lower AMR, lower AUV and higher AUE than \(f^r(*)\) does. It means that better boundary adherence and coherence is achieved by \(f^d(*)\) while higher segmentation accuracy is achieved by \(f^r(*)\). These two functions compensate for each other, however, \(f^d(*)\) outperforms \(f^r(*)\) for all five dataset except for Fash according to the sum of AMR and AUE.

Moreover, \(f^d_{\infty }(*)\) and \(f^r_{\infty }(*)\) perform a little better than \(f^d_2(*)\) and \(f^r_2(*)\) respectively except for EV, which is based on \(L_2\) norm. Red and white are as similar as red and black under \(L_\infty \) norm. In contrast, red is similar to black more than white under \(L_2\) norm since it averages the differences in three channels. It indicates that more coherent superpixels are assured by \(L_\infty \). Another advantage of \(L_{\infty }\) norm is its computational cost. The \(L_{\infty }\) norm only needs integer comparisons while the \(L_2\) norm needs floating-point computations. \(f^d_{\infty }(*)\) is employed in the rest experiments.

As shown in Fig. 5, the shapes of superpixels can be regularized by the scaling factor \({\hat{\lambda }}\) in Eq. 6. This factor balances the color similarity and spatial closeness. Given the expected number of superpixels K, \({\hat{\lambda }}\) is the only parameter to be specified for RSS algorithm.

When \({\hat{\lambda }}=0\), superpixel growing depends only on pixel colors and is sensitive to noises. The superpixels have irregular shapes. When \({\hat{\lambda }}>0\), superpixel growing depends on both colors and distances, superpixels are regularized to have regular shapes. As \({\hat{\lambda }}\) increases, the shapes become more regular. When \({\hat{\lambda }}\ge 512\), the superpixels are squares as superimposed on rightmost image. The maximal normalized coordinate difference between a pixels v at a square’s borders and its center \(v_c\) is 0.5, i.e., \(\max (|{\hat{x}}(v)-{\hat{x}}(v_c)|,|{\hat{y}}(v)-{\hat{y}}(v_c)|)=0.5\). The normalized coordinate difference between all the pixels outside a square and the center of this square are larger than 0.5. By multiplying a \({\hat{\lambda }}\ge 512\), their coordinate differences are larger than 256, which is the maximum value for color difference. Since the maximal difference is dominated by the pixel coordinates, the generated superpixels are squares.

Figure 6 reports Rec, UE, EV and CO of superpixels on BSDS dataset. The segmentations are carried out on a coarse, middle and fine level based on \(K=200, 1200, 6000\) respectively, and each is based on \({\hat{\lambda }}=0, 1,\ldots ,20\). As shown, finer segmentation outperforms coarser segmentation as blue lines are better than green lines and green lines are better than red lines. However, for a fixed K, \({\hat{\lambda }}\) has minor impacts on segmentation performance especially for fine segmentation. As \({\hat{\lambda }}\) increases, UE is stable while Rec and EV decrease slowly when \({\hat{\lambda }}\in [0,5]\). As indicated by their compactnesses, superpixel shapes are regularized by \({\hat{\lambda }}\) significantly.

The overall segmentation performance gets better as K increases. Given a K, it gets worse as \({\hat{\lambda }}\) increases since coherency and adherence receive less priority to uniformity and compactness. As performance is improved with the cost of increasing K, it is important to choose a well-balanced K. Given a K, it is convenient to select an \({\hat{\lambda }}\in [0,5]\). A smaller \({\hat{\lambda }}\) gives segmentation performance more priority to superpixel regularity. However, a large \({\hat{\lambda }}\) can be employed if uniform and compact superpixels are preferred.

ERS (Liu et al. 2011), ETPS (Yao et al. 2015), SEEDS (Van den Bergh et al. 2015), SNIC (Achanta and Süsstrunk 2017) and GBS (Felzenszwalb and Huttenlocher 2004) are employed for comparison. The former three are TOP 3 algorithms reported in Stutz et al. (2018). SNIC is an improved SLIC. Both SLIC and GBS are used very widely. Typical superpixels produced by these methods are demonstrated in Fig. 7.

GBS is based on minimum spanning forest of a graph whose edge weights measure the similarities of neighboring pixels. The segmentation is controlled by a threshold for the edge weights and a threshold for the segment sizes. It does not allow to control the number of superpixels directly, and it generates some widespread superpixels of arbitrary shapes. By introducing the roots of forest into the underlying graph, the number of superpixels can be easily controlled by RSS. Coupling the regularly and uniformly distributed seeds with the path-cost function, the manner of path extending and superpixel growing facilitates region competition and assures superpixels the expected characteristics as demonstrated by the examples. Each RSS covers a local, connected and coherent region. They adhere to the boundaries of flowers, face, shoulder, arms, white and black strips of shirt. Meanwhile, they are neither too large nor too small, and they appear to be compact or even square in homogeneous regions. They allow further regularization by a scaling factor.

As a method based on boundary evolution, SEEDS over-segments near object boundaries while under-segments in the homogeneous regions. ETPS and ERS overcome this shortcoming to some extent. However, noisy superpixel boundaries can still be observed in homogeneous areas. By clustering based on color and distance, SNIC produces compact superpixels with clean boundaries at the cost of sacrificing some segmentation performances. As shown in the last row, some white and black strips of the shirt are mixed in one superpixel. The advantages of RSS over SNIC is that superpixels grow along optimal paths, which assures better coherence and adherence.

The above methods are evaluated and ranked based on all five datasets. The optimal parameters for all methods are selected by the optimization schema employed in the benchmark. Firstly, for each method and each dataset, AMR, AUE and AUV based on thirteen \(K \in [200, 6000]\) are computed. Secondly, for each dataset, all six methods are ranked according to their AMR \(+\) AUE. Thirdly, for each method, an average rank is calculated by averaging its ranks over all five datasets. Fourthly, for each method, the average AMR, AUE, and AMR \(+\) AUE are also calculated by averaging them over all datasets. Finally, their overall performances are sorted based on their average ranks. As reported in Table 2, it results in an order same as that based on average AMR + AUE. According to the ranking, RSS outperforms all the methods except for ETPS.

The detailed reports for BSDS dataset are presented in Fig. 8. Rec, UE and EV along with their minimums/maximums and standard deviations are presented. In addition, CO and standard deviation of superpixel numbers are also presented. Four facts can be observed from these reports. First is the balance among metrics. Rec, UE and EV are well-balanced by RSS as all these metrics are ranked as the second or third among six. In contrast, SEEDS does not assure a good balance since it has the best Rec and almost the worst UE. The second concerns stability. RSS performs stably from coarse to fine segmentation as indicated by its smooth curves. It performs more stable than ETPS and SNIC. GBS and SEEDS perform unstably as their curves vary sharply. The third is that RSS generates more compact superpixels than SEEDS and ETPS. The last concerns the number of superpixels. Given an expected number, RSS generates a fixed number of superpixels for all images of the same size since it is fixed in segmentation. SNIC and ERS also guarantee a fixed number. But SEEDS and ETPS generate different number of superpixels for different images, which lead to nonzero std K. The number by GBS varies significantly since it depends on the other parameters indirectly.

RSS algorithm (serial version) is much faster than the other methods as depicted in Fig. 9. The time consumed by each method to segment all the images in each dataset is divided by the number of images to get the averaged time to segment one image of each dataset. For each method, the above averaged runtime is further averaged over all five datasets and presented in the last column. Details for the NYU dataset are illustrated in the figure, where the runtime with respect to the number of superpixels is depicted. As shown, the runtime of RSS is stable with respect to varying number of superpixels while those of ERS, ETPS, SEEDS and GBS are not.

The above reports are based on the optimal parameters including the number of iterations for ETPS and SEEDS. By reducing it to one, the averaged runtime over all five datasets by either SEEDS or ETPS is 0.102 s. It is still much slower than RSS. Besides, it significantly impairs SEEDS’s performance. Moreover, 40% computation time can be saved when 4 CPU cores are employed to parallelize RSS.

GBH (Grundmann et al. 2010), SWA (Corso et al. 2008), TSP (Chang et al. 2013) and GBS (Felzenszwalb and Huttenlocher 2004) are employed for comparison. The former three are top performing methods reported in (Xu and Corso 2016). GBH is based on GBS, which is called as GB in this benchmark. A same scaling factor is employed for both spatial and temporal dimensions, i.e. \({\hat{\lambda }}'={\hat{\lambda }}=3\). Their supervoxels on six successive frames in the ice video of the Chen xiph.org dataset are demonstrated in Fig. 10.

One can observe the adaptivity of RSS in Fig. 10. On one hand, RSS are uniform and compact in the homogeneous regions. On the other hand, they adhere to object boundaries and indicate the peoples’ outlines. GBS and GBH segment the videos into a set of nonuniform and irregular volumes, some cover large homogeneous areas while some others contain only a few boundary pixels. Although TSP are uniform and compact, their adherence to object boundaries are not good enough to indicate the peoples’ outlines. The overall appearance of supervoxels by SWA is similar to RSS.

Figure 11 reports their performances. RSS outperforms the other methods according to three metrics for segmentation performance. It achieves the best BRD (lower is better) and EV. Its UE3D is good, but its SA3D is low. It seems to contradict the correlation between SA3D and UE3D. Actually, SA3D also depends on the temporal dimension. When a supervoxel covers more frames, the size of correct segment increases and a higher accuracy is achieved. The other temporal metrics TEX and MSV are not good. Better SA3D, TEX and MSV can be achieved when the scaling factors \({\hat{\lambda }}, {\hat{\lambda }}'\) are optimized for the video. A better solution is to treat a video as a sequence of images instead of a volumetric data.

As demonstrated in Fig. 9, RSS is three times faster than GBS, which is almost an order of magnitude faster than GBH, SWA and TSP as reported in Xu and Corso (2016).