We propose a simple and fast superpixel segmentation algorithm based on constrained label propagation with minimax path. In our algorithm, a grid-style graph is constructed from an input image, and the dissimilarity between a pair of pixels is given by their minimax distance. The segment labels of individual pixels are propagated along the minimax paths, where a pixel is supposed to have the label of the seed node from which the minimax distance is minimized. Since the original minimax label propagation may generate spatially disconnected superpixels, we add a constraint on label updates to avoid the situation, which constitutes our constrained minimax label propagation algorithm. The proposed algorithm employs structured edge map in addition to color or intensity feature to compute distances between adjacent pixels, and introduces a two-stage seed selection technique to identify better seed locations. Our algorithm achieves outstanding accuracy and speed compared with the state-of-the-art methods, and presents superior performance in the applications of object proposal generation and image saliency detection.
