Logo: to the web site of Uppsala University

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 sub-modular. This can be interpreted as minimizing the l1-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 lp-norm of the vector. Unfortunately, the submodularity of an l1-norm objective function does not guarantee the submodularity of the corresponding lp-norm objective function. The contribution of this paper is to provide useful conditions under which an lp-norm objective function is submodular for all p>= 1, thereby identifying a large class of lp-norm objective functions that can be minimized via minimal graph cuts.

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 l1l1-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 lplp-norm of the vector. Unfortunately, the submodularity of an l1l1-norm objective function does not guarantee the submodularity of the corresponding lplp-norm objective function. The contribution of this paper is to provide useful conditions under which an lplp-norm objective function is submodular for all p≥1p≥1, thereby identifying a large class of lplp-norm objective functions that can be minimized via minimal graph cuts.