What metrics can be approximated by geo cuts or global optimization of length area and flux

V. Kolmogorov, Y. Boykov, in:, IEEE, 2005, pp. 564–571.

Download
No fulltext has been uploaded. References only!

Conference Paper | Published
Author
Abstract
In the work of the authors (2003), we showed that graph cuts can find hypersurfaces of globally minimal length (or area) under any Riemannian metric. Here we show that graph cuts on directed regular grids can approximate a significantly more general class of continuous non-symmetric metrics. Using submodularity condition (Boros and Hammer, 2002 and Kolmogorov and Zabih, 2004), we obtain a tight characterization of graph-representable metrics. Such "submodular" metrics have an elegant geometric interpretation via hypersurface functionals combining length/area and flux. Practically speaking, we attend 'geo-cuts' algorithm to a wider class of geometrically motivated hypersurface functionals and show how to globally optimize any combination of length/area and flux of a given vector field. The concept of flux was recently introduced into computer vision by Vasilevskiy and Siddiqi (2002) but it was mainly studied within variational framework so far. We are first to show that flux can be integrated into graph cuts as well. Combining geometric concepts of flux and length/area within the global optimization framework of graph cuts allows principled discrete segmentation models and advances the slate of the art for the graph cuts methods in vision. In particular we address the "shrinking" problem of graph cuts, improve segmentation of long thin objects, and introduce useful shape constraints.
Publishing Year
Date Published
2005-12-05
Volume
1
Page
564 - 571
Conference
ICCV: International Conference on Computer Vision
IST-REx-ID

Cite this

Kolmogorov V, Boykov Y. What metrics can be approximated by geo cuts or global optimization of length area and flux. In: Vol 1. IEEE; 2005:564-571. doi:10.1109/ICCV.2005.252
Kolmogorov, V., & Boykov, Y. (2005). What metrics can be approximated by geo cuts or global optimization of length area and flux (Vol. 1, pp. 564–571). Presented at the ICCV: International Conference on Computer Vision, IEEE. https://doi.org/10.1109/ICCV.2005.252
Kolmogorov, Vladimir, and Yuri Boykov. “What Metrics Can Be Approximated by Geo Cuts or Global Optimization of Length Area and Flux,” 1:564–71. IEEE, 2005. https://doi.org/10.1109/ICCV.2005.252.
V. Kolmogorov and Y. Boykov, “What metrics can be approximated by geo cuts or global optimization of length area and flux,” presented at the ICCV: International Conference on Computer Vision, 2005, vol. 1, pp. 564–571.
Kolmogorov V, Boykov Y. 2005. What metrics can be approximated by geo cuts or global optimization of length area and flux. ICCV: International Conference on Computer Vision vol. 1. 564–571.
Kolmogorov, Vladimir, and Yuri Boykov. What Metrics Can Be Approximated by Geo Cuts or Global Optimization of Length Area and Flux. Vol. 1, IEEE, 2005, pp. 564–71, doi:10.1109/ICCV.2005.252.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar