Entropy Rate Superpixel Segmentation

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 monotonic properties of the objective function, we develop an efficient greedy algorithm. Furthermore, we prove an approximation bound of $\frac{1}{2}$ 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.

Code: We provide an implementation of the entropy rate superpixel segmentation algorithm for the academic community. The code is released as a Matlab wrapper and made compatible to most of the c compilers. To compile the code, simply type make in Matlab console. To see the usage, please check the demo program in the released package.
Version 0.1 : MATLAB Wrapper [ers_matlab_wrapper_v0.1.zip]
This is the implementation used for reporting the performance in the CVPR paper.
Version 0.2.1 : MATLAB Wrapper [ers_matlab_wrapper_v0.2.1.zip]
New features: (1) Superpixel segmentation on RGB image and (2) Support 4-connected image grid structure.

Related Publications

  • Entropy Rate Superpixel Segmentation
    Ming-Yu Liu, Oncel Tuzel, Srikumar Ramalingam, and Rama Chellappa
    Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR'11) , Colorado Spring, June 2011.

 

Fast Object Localization and Pose Estimation in Heavy Clutter for Robotic Grasping

Abstract: We present a practical vision-based robotic bin-picking system that performs detection and 3D pose estimation of objects in an unstructured bin using a novel camera design, picks up parts from the bin, and performs error detection and pose correction while the part is in the gripper. Two main innovations enable our system to achieve real-time robust and accurate operation. First, we use a multi-flash camera that extracts robust depth edges. Second, we introduce an efficient shape-matching algorithm called fast directional chamfer matching (FDCM), which is used to reliably detect objects and estimate their poses. FDCM improves the accuracy of chamfer matching by including edge orientation. It also achieves massive improvements in matching speed using line-segment approximations of edges, a 3D distance transform, and directional integral images. We empirically show that these speedups, combined with the use of bounds in the spatial and hypothesis domains, give the algorithm sublinear computational complexity. We also apply our FDCM method to other applications in the context of deformable and articulated shape matching. In addition to significantly improving upon the accuracy of previous chamfer matching methods in all of the evaluated applications, FDCM is up to two orders of magnitude faster than the previous methods.

Code: We provide an implementation of the fast directional chamfer matching algorithm for the academic community. From Version 0.2, the code is released as a Matlab wrapper and made compatible to most of the c compilers. To compile the code, simply type make in Matlab console. To see the usage, please check the demo program in the released package.
Version 0.2 : MATLAB Wrapper [fdcm_matlab_wrapper_v0.2.zip] You might find PB edge detector useful in retrieving an edge map.

Related Publications