||Many fundamental problems in image processing and computer vision, such as image filtering, segmentation, registration, and stereo vision, can naturally be formulated as optimization problems.
In this talk, I will present some recent results on optimizing binary labeling problems where the objective function is defined as the max-norm over a set of variables. It is well known that, for a limited subclass of such problems, globally optimal solutions can be found via watershed cuts, i.e., cuts by optimum spanning forests. Here, we propose a new algorithm for optimizing a broader class of such problems. We prove that the proposed algorithm returns a globally optimal labeling, provided that the objective function satisfies certain given conditions, analogous to the submodularity conditions encountered in min-cut/max-flow optimization. The proposed method is highly efficient, with quasi-linear computational complexity.