TY - CONF
T1 - Entropy rate superpixel segmentation
T2 - 2011 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)
Y1 - 2011
A1 - Ming-Yu Liu
A1 - Tuzel, O.
A1 - Ramalingam, S.
A1 - Chellapa, Rama
KW - balancing function
KW - Berkeley segmentation benchmark
KW - Complexity theory
KW - Entropy
KW - entropy rate
KW - graph construction
KW - graph theory
KW - graph topology
KW - greedy algorithm
KW - Greedy algorithms
KW - homogeneous clusters
KW - Image edge detection
KW - Image segmentation
KW - matrix algebra
KW - matroid constraint
KW - measurement
KW - pattern clustering
KW - Random variables
KW - standard evaluation metrics
KW - superpixel segmentation
KW - vector spaces
AB - We propose a new objective function for superpixel segmentation. This objective function consists of two components: entropy rate of a random walk on a graph and a balancing term. The entropy rate favors formation of compact and homogeneous clusters, while the balancing function 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 vector 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 efficient greedy algorithm. Furthermore, we prove an approximation bound of ½ for the optimality of the solution. Extensive experiments on the Berkeley segmentation benchmark show that the proposed algorithm outperforms the state of the art in all the standard evaluation metrics.
JA - 2011 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)
PB - IEEE
SN - 978-1-4577-0394-2
M3 - 10.1109/CVPR.2011.5995323
ER -