SQL: Superpixels via quaternary labeling by Dengfeng Chai

Superpixels have become an effective alternative to pixels since superpixels have two prime advantages over pixels. One is their perceptual meaning, the other is the complexity. Although many superpixel segmentation methods are available, few produce superpixels that conform to a regular lattice, which is a prerequisite for some models such as Markov Random Field (MRF) and Convolutional Neural Network (CNN).

In this study, Chai (2019) formulated superpixel segmentation as a pixel labeling problem and proposed a quaternary labeling algorithm to efficiently generate superpixel lattice for any input image. Superpixel segmentation is achieved by seaming overlapped patches regularly placed on the image plane as shown in Fig. 1b. Patch seaming is formulated as a pixel labeling problem, where each label indexes one patch. Once the optimal seaming is completed, all pixels covered by one retained patch constitute one superpixel. Further, four kinds of patches are distinguished and assembled into four layers as shown in Fig. 1c, and the patch indexes are mapped to the quaternary layer indexes. Furthermore, an objective function is developed to achieve optimal segmentation. Lattice structure is guaranteed by fixing patch centers to be superpixel centers, compact superpixels are assured by horizontal and vertical constraints enforced on the smooth terms, and coherent superpixels are achieved by iteratively refining the data terms.

Compared with the existing strip seaming (Fig. 1a) and patch seaming (Fig. 1b), the proposed layer seaming (Fig. 1c) significantly reduces the number of labels. Since the computational complexity is O(N) (N is the number of labels), the proposed superpixel via quaternary labeling (SQL) algorithm greatly improves labeling efficiency. Extensive experiments on Berkeley Segmentation Dataset (BSDS) dataset demonstrate that SQL algorithm significantly improves labeling efficiency, outperforms the other superpixel lattice methods.

Dengfeng Chai (2019): SQL: Superpixels via Quaternary Labeling, Pattern Recognition, 92(8):52-63.

Fig. 1. Three types of seaming for superpixel segmentation. (a) and (b) depict strip-based seaming and patch-based seaming respectively, (c) illustrates the proposed layer-based seaming. In (c), all non-overlapped patches are integrated as one layer, and all layers are assembled into 4 layers.