Entropy Rate Superpixel Segmentation.pdf

Entropy Rate Superpixel Segmentation Ming-Yu Liu ? Oncel Tuzel ? Srikumar Ramalingam ? Rama Chellappa ? ? University of Maryland College Park ? Mitsubishi Electric Research Labs {mingyliu,rama}@ {oncel,ramalingam}@ Abstract We propose a new objective function for superpixel seg- mentation. This objective function consists of two compo- nents: entropy rate of a random walk on a graph and a balancing term. The entropy rate favors formation of com- pact and homogeneous clusters, while the balancing func- tion encourages clusters with similar sizes. We present a novel graph construction for images and show that this construction induces a matroid— a combinatorial structure that generalizes the concept of linear independence in vec- tor spaces. The segmentation is then given by the graph topology that maximizes the objective function under the matroid constraint. By exploiting submodular and mono- tonic properties of the objective function, we develop an ef- ficient greedy algorithm. Furthermore, we prove an approx- imation bound of 1 2 for the optimality of the solution. Exten- sive experiments on the Berkeley segmentation benchmark show that the proposed algorithm outperforms the state of the art in all the standard evaluation metrics. 1. Introduction Superpixel segmentation is an important module for many computer vision applications such as object recogni- tion [15], image segmentation [20, 8], and single view 3D reconstruction [7, 19]. A superpixel is commonly defined as a perceptually uniform region in the image. The major advantage of using superpixels is computa- tional efficiency. A superpixel representation greatly re- duces the number of image primitives compared to the pixel representation. For instance, in an L-label labeling prob- lem, the solution space for a pixel representation is Ln where n is the number of pixels— typically 106; in con- trast, the solution space for a superpixel representation is Lm where m is the number of superpixels— typically 102 (