What metrics can be approximated by geo-cuts, or global optimization of length/area and flux
- 1 January 2005
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 1, 564-571 Vol. 1
- https://doi.org/10.1109/iccv.2005.252
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.Keywords
This publication has 10 references indexed in Scilit:
- An experimental comparison of min-cut/max- flow algorithms for energy minimization in visionPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2004
- What energy functions can be minimized via graph cuts?Published by Institute of Electrical and Electronics Engineers (IEEE) ,2004
- Flux invariants for shapePublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Statistical shape knowledge in variational motion segmentationImage and Vision Computing, 2003
- Regularized Laplacian Zero Crossings as Optimal Edge IntegratorsInternational Journal of Computer Vision, 2003
- Computing geodesics and minimal surfaces via graph cutsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Flux maximizing geometric flowsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Interactive graph cuts for optimal boundary & region segmentation of objects in N-D imagesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Pseudo-Boolean optimizationDiscrete Applied Mathematics, 2001
- Globally optimal regions and boundaries as minimum ratio weight cyclesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2001