Efficient global minimization methods for variational problems in imaging and vision

Abstract

Energy minimization has become one of the most important paradigms for formulating image processing and computer vision problems in a mathematical language. Energy minimization models have been developed in both the variational and discrete optimization community during the last 20-30 years. Some models have established themselves as fundamentally important and arise over a wide range of applications. One fundamental challenge is the optimization aspect. The most desirable models are often the most difficult to handle from an optimization perspective. Continuous optimization problems may be non-convex and contain many inferior local minima. Discrete optimization problems may be NP-hard, which means algorithms are unlikely to exist which can always compute exact solutions without an unreasonable amount of effort. This thesis contributes with efficient optimization methods which can compute global or close to global solutions to important energy minimization models in imaging and vision. New insights are given in both continuous and combinatorial optimization, as well as a strengthening of the relationships between these fields. One problem that is extensively studied is minimal perimeter partitioning problems with several regions, which arise naturally in e.g. image segmentation applications and is NP-hard in the discrete context. New methods are developed that can often compute global solutions and otherwise very close approximations to global solutions. Experiments show the new methods perform significantly better than earlier variational approaches, like the level set method, and earlier combinatorial optimization approaches. The new algorithms are significantly faster than previous continuous optimization approaches. In the discrete community, max-flow and min-cut (graph cuts) have gained huge popularity because they can efficiently compute global solutions to certain energy minimization models. It is shown that new types of problems can be solved exactly by max-flow and min-cut. Furthermore, variational generalizations of max-flow and min-cut are proposed which bring the global optimization property to the continuous setting, while avoiding grid bias and metrication errors which are major disadvantages of the discrete models. Convex optimization algorithms are derived from the variational max-flow models, which are very efficient and are more parallel friendly than traditional combinatorial algorithms.