FLIC: Fast linear iterative clustering with active search

Given the desired number of superpixels $K$ and an input image $I={\{I_i\}}_{i=1}^N$ , where $N$ is the number of pixels, our goal is to produce a series of disjoint small regions (or superpixels). Following most previous works [ 17 ], the original RGB color space is transformed to the more useful CIELAB color space. Thus, each pixel $I_i$ in an image $I$ can be represented in a five dimensional space:

(4) $$I_i=(l_i,a_i,b_i,x_i,y_i)$$

We first divide the original image into a regular grid containing $K$ elements ${\{G_k\}}_{k=1}^K$ with step length $\upsilon =\sqrt{N/K}$ as in Ref. [ 17 ], and the initial label for each pixel $I_i$ is assigned as

(5) $$L_i=k,\text{when}\mathit{\hspace{1em}}{I}_i\in G_k$$

We initialize the seed $S_k$ in $G_k$ at its centroid. Therefore, $S_k$ can also be defined as being in the same five dimensional space:

(6) $$S_k=\{l_k,a_k,b_k,x_k,y_k\}$$

In most natural images adjacent pixels tend to share the same labels, i.e., neighboring pixels havenatural continuity. Thus, we propose an active search method to leverage as much of this a priori information as possible. In our method, unlike most previous approaches [ 17 , 21 ], the label of each pixel is only determined by its neighbors. We compute the distances between the current pixel and the seeds of its four or eight adjacent pixels—see Fig. 1 . Specifically, for a pixel $I_i$ , our assignment principle is

(7) $$L_i={\arg \min }_{L_j}D(I_i,S_{L_j}),I_j\in A_i$$

where $A_i$ consists of $I_i$ and its four neighboring pixels, and $S_{L_j}$ is $I_j$ ’s corresponding superpixel seed. We use Eq. ( 1 ) to measure the distance $D(I_i,S_{L_j})$ .

Since each pixel can only be assigned to a superpixel containing at least one of its neighbors, local pixel continuity has a stronger effect in our proposed strategy, allowing each pixel to actively assign itself to one of its surrounding closely connected superpixel regions. The advantages of such a strategy are clear: firstly, the nearby assignment principle can avoid the occurrence of too many isolated regions, indirectly preserving the desired number of superpixels. Secondly, this assignment operation is not limited by a fixed range in space, resulting in better superpixel boundary compliance even when very complicated content leads to irregular superpixel shapes. Furthermore, during the assignment process, the superpixel centers are also self-adaptively modified, leading to faster convergence. Detailed demonstration and analysis are given in Section 4.5. It is worth mentioning that the neighbors of the internal pixels in a superpixel normally share the same labels, so it is unnecessary to process them further, allowing us to process each superpixel extremely quickly.

The traversal order plays a very important role in our approach: an appropriate scanning order may lead to a visually better segmentation. As explained in Section 3.2, the label of each pixel only depends on the seeds of its surrounding pixels. Thus, in a superpixel, the label of the current pixel is directly or indirectly related to those pixels that have already been processed. To better take advantage of this avalanche effect, we adopt a back-and-forth traversal order as in PatchMatch [ 23 ], in which the pixels that are processed later will benefit from updates to previously processed pixels. Figure 2 illustrates this process. In the forward pass, the label decision for each pixel considers the information from the top surrounding pixels of the superpixel, and similarly, the backward pass will provide the information from the bottom surrounding pixels of the superpixel. With such a scanning order, all the surrounding information can be taken into consideration, yielding better segments.

10.1007/s41095-018-0123-y.F2 Fig. 2Scanning order for each superpixel. Gray regions enclosed by blue lines represent superpixels. Red dashed rectangles denote their corresponding bounding boxes. We first scan the bounding box from left to right and top to bottom (b) and then in the opposite direction (c). The shape of each superpixel may change, whereupon we update the bounding box (d) if necessary.

While an arbitrary superpixel may have an irregular shape instead of a simple rectangle or square, we use a simple strategy to traverse the whole superpixel. We first find a minimum bounding box within which all its pixels are enclosed, as shown in Fig. 2 . We then perform the scanning process for all pixels in the corresponding minimum bounding box and only deal with those pixels that are within the superpixel.

It is common in existing methods, such as SLIC [ 17 ], that the assignment and update steps are performed separately, leading to delayed feedback from pixel label changes to superpixel seeds. An obvious problem of such a strategy is that many (normally more than five) iterations are required before convergence. In our approach, based on the assignment principle in Eq. ( 7 ), we use a joint assignment and update strategy which performs these two steps at a finer granularity. This approach is able to adjust the superpixel seed center position on the fly, significantly reducing the number of iterations needed for convergence. Since most clustering-based superpixel methods use the centroidal Voronoi tessellation (CVT), we first briefly introduce the CVT and then describe our method.

Let $S={\{S_k\}}_{k=1}^K$ be the set of seeds in the image, where $K$ is the expected number of superpixels. The Voronoi cell ${𝒱}_{S_k}$ of a seed $S_k$ is denoted by

(8) $${𝒱}_{S_k}=\{I_i\in I|d(I_i,S_k)⩽d(I_i,S_j),\forall S_j\in S\}$$

where $d(I_i,S_k)$ is an arbitrary distance measure from pixel $I_i$ to the seed $S_k$ . The Voronoi diagram ${𝒱}_{\mathrm{D}}(S)$ is defined by

(9) $${𝒱}_{\mathrm{D}}(S)=\{{𝒱}_{S_k}\ne \mathrm{\varnothing }|\forall S_k\in S\}$$

A CVT is then defined as a Voronoi diagram whose generator point of each Voronoi cell is also its center of mass. The CVT is usually obtained by heuristic algorithms, such as Lloyd’s algorithm, iteratively performing updates after each assignment step until convergence is reached.

In our approach, on account of our novel label decision strategy as shown in Eq. ( 7 ), we are able to jointly perform the update step and the assignment step instead of separately. More specifically, after pixel $I_i$ is processed, if its label is changed to, say, $L_j$ , we immediately update the current seed $S_{L_i}$ using the following equation:

(10) $$S_{L_i}=\frac{S_{L_i}\left|{\zeta }_{L_i}\right|-I_i}{\left|{\zeta }_{L_i}\right|-1}$$

where $\left|{\zeta }_{L_i}\right|$ is the number of pixels in superpixel ${\zeta }_{L_i}$ , and update $S_{L_j}$ using the following equation:

(11) $$S_{L_j}=\frac{S_{L_j}\left|{\zeta }_{L_j}\right|+I_i}{\left|{\zeta }_{L_j}\right|+1}$$

The bounding box of ${\zeta }_{L_j}$ is also updated accordingly.

As the above updates only contain very simple arithmetic operations, they can be performed very quickly. Such an immediate update will help later pixels make a better choice during assignment, leading to better convergence. Figure 10 given later illustrates the speed of convergence of our approach.

In our method, superpixels are processed inde-pendently. Thus, the superpixel processing order will affect the performance of the method; label changes affect the surrounding pixels. However, we do not want current pixel changes to affect the superpixels we have already processed. Therefore, we give priority to those complex superpixels in which many pixels labels will be changed, processing them first and then simple superpixels later. Superpixels which have a uniform color are simple, and almost no pixels labels need to change.

We use color entropy to define the complexity of superpixels. We calculate it using the following formulation ( 15 ):

(12) $${\mathrm{Entropy}}_l=\frac{{\sum }_{p\in {\zeta }_{L_j}}{(p_l-\widehat{p_l})}^2}{\left|{\zeta }_{L_j}\right|}$$

(13) $${\mathrm{Entropy}}_a=\frac{{\sum }_{p\in {\zeta }_{L_j}}{(p_a-\widehat{p_a})}^2}{\left|{\zeta }_{L_j}\right|}$$

(14) $${\mathrm{Entropy}}_b=\frac{{\sum }_{p\in {\zeta }_{L_j}}{(p_b-\widehat{p_b})}^2}{\left|{\zeta }_{L_j}\right|}$$

(15) $${\mathrm{Entropy}}_{{\zeta }_{L_j}}=\frac{{\mathrm{Entropy}}_l+{\mathrm{Entropy}}_a+{\mathrm{Entropy}}_b}{3}$$

where $\left|{\zeta }_{L_i}\right|$ is the number of pixels in superpixel ${\zeta }_{L_i}$ , $p$ is a three-dimensional vector in lab color space, and $\hat{p}$ is the mean of $p$ in superpixel ${\zeta }_{L_i}$ .

After determining the entropy of all superpixels, we process them in descending order of entropy. We later demonstrate the benefits of this processing order.