Superpixel segmentation partitions an image into perceptually coherent segments of similar size, namely, superpixels. It is becoming a fundamental preprocessing step for various computer vision tasks because superpixels significantly reduce the number of inputs and provide a meaningful representation for feature extraction. We present a pixel-related Gaussian mixture model (GMM) to segment images into superpixels. GMM is a weighted sum of Gaussian functions, each one corresponding to a superpixel, to describe the density of each pixel represented by a random variable. Different from previously proposed GMMs, our weights are constant, and Gaussian functions in the sums are subsets of all the Gaussian functions, resulting in segments of similar size and an algorithm of linear complexity with respect to the number of pixels. In addition to the linear complexity, our algorithm is inherently parallel and allows fast execution on multi-core systems. During the expectation-maximization iterations of estimating the unknown parameters in the Gaussian functions, we impose two lower bounds to truncate the eigenvalues of the covariance matrices, which enables the proposed algorithm to control the regularity of superpixels. Experiments on a well-known segmentation dataset show that our method can efficiently produce superpixels that adhere to object boundaries better than the current state-of-the-art methods.

Extended from superpixel segmentation by adding an additional constraint on temporal consistency, supervoxel segmentation is to partition video frames into atomic segments. In this work, we propose a novel scheme for supervoxel segmentation to address the problem of new and moving objects, where the segmentation is performed on every two consecutive frames and thus each internal frame has two valid superpixel segmentations. This scheme provides coarse-grained parallel ability, and subsequent algorithms can validate their result using two segmentations that will further improve robustness. To implement this scheme, a voxel-related Gaussian mixture model (GMM) is proposed, in which each supervoxel is assumed to be distributed in a local region and represented by two Gaussian distributions that share the same color parameters to capture temporal consistency. Our algorithm has a lower complexity with respect to frame size than the traditional GMM. According to our experiments, it also outperforms the state-of-the-art in accuracy.