Entropy rate superpixel segmentation
Authors:
Top Cited Papers
- 1 June 2011
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10636919,p. 2097-2104
Abstract
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.Keywords
This publication has 16 references indexed in Scilit:
- Entropy rate superpixel segmentation2011
- Superpixel lattices2008
- Exact inference in multi-label CRFs with higher order cliques2008
- Learning a classification model for segmentation2003
- A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics2002
- Mean shift: a robust approach toward feature space analysisIEEE Transactions on Pattern Analysis and Machine Intelligence, 2002
- Elements of Information Theory2001
- Normalized cuts and image segmentationIEEE Transactions on Pattern Analysis and Machine Intelligence, 2000
- Watersheds in digital spaces: an efficient algorithm based on immersion simulationsIEEE Transactions on Pattern Analysis and Machine Intelligence, 1991
- An analysis of approximations for maximizing submodular set functions—IMathematical Programming, 1978