When can $l_p$-norm objective functions be minimized via graph cuts?
This work addresses a theoretical bottleneck in computer vision and image processing for researchers and practitioners using graph cuts, offering incremental but useful conditions to extend applicability.
The paper tackles the problem of identifying when $l_p$-norm objective functions can be minimized via graph cuts, by providing conditions under which these functions are submodular for all $p \\geq 1$, thus enabling efficient optimization for a broad class of problems.
Techniques based on minimal graph cuts have become a standard tool for solving combinatorial optimization problems arising in image processing and computer vision applications. These techniques can be used to minimize objective functions written as the sum of a set of unary and pairwise terms, provided that the objective function is submodular. This can be interpreted as minimizing the $l_1$-norm of the vector containing all pairwise and unary terms. By raising each term to a power $p$, the same technique can also be used to minimize the $l_p$-norm of the vector. Unfortunately, the submodularity of an $l_1$-norm objective function does not guarantee the submodularity of the corresponding $l_p$-norm objective function. The contribution of this paper is to provide useful conditions under which an $l_p$-norm objective function is submodular for all $p\geq 1$, thereby identifying a large class of $l_p$-norm objective functions that can be minimized via minimal graph cuts.