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.

We consider 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.