In [3] 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 [1,11], 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 extend ``geo-cuts'' algorithm [3] 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 [13] 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 state 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.