This work proposes guaranteed approximation bound algorithms (generalization of a-expansion and uncapacitated facility location techniques) to minimize general energy functionals combining data term, spatial smoothness, and label/category costs (new high-order term). Many generic applications are demonstrated: geometric model fitting, rigid motion detection, MDL-based segmentation, compression, FMM. Our approach is juxtaposed with classical K-means and EM. Efficient C++/MATLAB implementation is provided. This implementation includes dramatic speedups for two separate special cases: (1) when no smooth costs are used, and (2) when each label is only feasible for a sparse subset of data points.

This work establishes a link between two standard approaches to image segmentation: combinatorial methods based on graph-cuts and geometric methods based on level-sets. We study cut metrics on regular grid-graphs and show that discrete topology of graph-cuts can approximate any continuous Riemannian metric space. Consequently, efficient algorithms from combinatorial optimization can be applied to interesting problems in integral and differential geometry. Click on images on the left for larger size video.

[ICCV slides (477KB), real time screen capture demo (38MB), and talk video]

The main idea of this paper is to reduce stereo vision to a multiway cut problem on a certain graph. You can compare the output of our algorithm with a correlation based method. The "Head Image" is obtained from the Computer Vision Lab at the University of Tsukuba (Japan). You can find more data in the stereo vision section of the image gallery. You can also access my power point presentation (.ppt file) for CVPR'98.