Local Submodularization for Binary Pairwise Energies.

Area of Science:

• Computer Vision
• Optimization Theory
• Machine Learning

Background:

• Many computer vision problems involve optimizing binary non-submodular energies.
• Existing methods like LP relaxation or gradient descent have limitations in handling these complex energies.

Purpose of the Study:

• To propose a general optimization framework for binary non-submodular energies.
• To introduce novel algorithms that overcome limitations of existing methods.

Main Methods:

• Developed a framework based on local submodular approximations (LSA).
• Introduced two specific algorithms: LSA-TR (trust region) and LSA-AUX (auxiliary function).
• These methods iteratively approximate energies locally using non-linear submodular approximations within integer domains.

Main Results:

• Achieved state-of-the-art results across diverse applications.
• Demonstrated effectiveness in binary deconvolution, curvature regularization, inpainting, and segmentation with repulsion.
• Showcased applicability to shape priors and potential for higher-order problems.

Conclusions:

• The proposed LSA framework offers a powerful and versatile approach for optimizing challenging energies in computer vision.
• LSA-TR and LSA-AUX provide efficient and effective solutions, outperforming existing methods.
• The framework is extensible to higher-order problems, indicating broad applicability.