Graph-cut optimization of the ratio of functions and its application to image segmentation

Optimizing the ratio of two functions of binary variables is a common task in many image analysis applications. In general, such a ratio is not amenable to graph-cut based optimization. In this paper, we show that if the numerator and the denominator of a ratio are individually graph- representable functions, then their ratio can be optimized via graph-cut based technique. As an example of such a ratio function we choose Yezzi et al.´s energy function (A. Yezzi et al., 1999), minimization of which produces a binary labeling of an image. Through examples, we illustrate the advantage of working with graph-cut-based optimization for the aforementioned ratio in finding a global solution as opposed to the local solutions found by level set methods proposed in (A. Yezzi et al., 1999).