When can l_p-norm objective functions be minimized via graph cuts?

DOI10.1007/978-3-030-05288-1_9MaRDI QIDQ6165904zbMATH OpenOpenAlexFDO

Authors Filip Malmberg, Robin Strand

Publication date 2 August 2023

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1802.00624

zbMATH Keywords

\(l_p\) normminimal graph cutssubmodularity

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Machine vision and scene understanding (68T45) Computing methodologies for image processing (68U10) Combinatorial optimization (90C27) Applications of mathematical programming (90C90)

Abstract: 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 $pgeq1$, thereby identifying a large class of $l_p$-norm objective functions that can be minimized via minimal graph cuts.

Recommendations

• scientific article; zbMATH DE number 2062604
• A Laplacian approach to _1-norm minimization
• Minimizing \(L_1\) over \(L_2\) norms on the gradient
• Cutting plane oracles to minimize non-smooth non-convex functions
• scientific article; zbMATH DE number 883260
• Generalized \(\gamma\)-valid cut procedure for concave minimization

Cited in

(4)

• Two polynomial time graph labeling algorithms optimizing max-norm-based objective functions
• scientific article; zbMATH DE number 2062604 (Why is no real title available?)
• Graph cuts with interacting edge weights: examples, approximations, and algorithms
• Optimization of max-norm objective functions in image processing and computer vision

This page was built for publication: When can \(l_p\)-norm objective functions be minimized via graph cuts?

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6165904)