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.
Has parts
Paper A: Egil Bae and Xue-Cheng Tai, Graph Cut Optimization for the Piecewise Constant Level Set Method Applied to Multiphase Image Segmentation. In Proc. Second International Conference on Scale Space and Variational Methods in Computer Vision (SSVM 2009), pages 1-13. Lecture Notes in Computer Science 5567, Springer, Berlin, 2009. Full-text not available in BORA. The published version is available at: http://dx.doi.org/10.1007/978-3-642-02256-2_1Paper B: Egil Bae and Xue-Cheng Tai, Efficient Global Minimization for the Multiphase Chan-Vese Model of Image Segmentation. In Proc. Seventh International Conference on EnergyMinimization Methods in Computer Vision and Pattern Recognition (EMMCVPR 2009), pg.28-41, Lecture Notes in Computer Science, Springer, Berlin, 2009. (An extended journal version is included). Full-text available in BORA: http://hdl.handle.net/1956/5018
Paper C: Egil Bae, Jing Yuan and Xue-Cheng Tai, Global Minimization for Continuous Multiphase Partitioning Problems Using a Dual Approach. International Journal of Computer Vision 92(1): pp. 112-129, 2010. Full-text available in BORA: http://hdl.handle.net/1956/5019
Paper D: Jing Yuan, Egil Bae and Xue-Cheng Tai, A Study on Continuous Max-Flow and Min-Cut Approaches. In Proc. IEEE Conference on Computer Vision and Pattern Recognition (CVPR) 2010. (An extended journal version is included). Full-text available in BORA: http://hdl.handle.net/1956/5020
Paper E: Egil Bae, Jing Yuan, Xue-Cheng Tai and Yuri Boykov, A Fast Continuous Max-Flow Approach to Non-Convex Multilabeling Problems. Submitted for journal publication. Full-text available in BORA: http://hdl.handle.net/1956/5021
Paper F: Egil Bae and Xue-Cheng Tai, Exact Convex Formulation of the Chan-Vese Model and a Tight Convex Relaxation of Pott’s Model with 4 Regions. Full-text not available in BORA
Paper G: Egil Bae, Juan Shi and Xue-Cheng Tai, Graph Cuts for Curvature based Image Denoising. IEEE Transactions on Image Processing 20(5), pp. 1199 - 1210 2010. Full-text not available in BORA. The published version is available at: http://dx.doi.org/10.1109/TIP.2010.2090533
Paper H: Jing Yuan, Egil Bae, Xue-Cheng Tai and Yuri Boykov, A Continuous Max-Flow Approach to Potts Model. In European Conference on Computer Vision (ECCV), Lecture Notes in Computer Science, Volume 6316/2010, pg. 379-392, 2010. Full-text not available in BORA. The published version is available at: http://dx.doi.org/10.1007/978-3-642-15567-3_28
Paper I: Jing Yuan, Egil Bae, Yuri Boykov and Xue-Cheng Tai, A Continuous Max-Flow Approach to Minimal Partitions with Label Cost Prior. To appear In Proc. Third International Conference on Scale Space and Variational Methods in Computer Vision (SSVM) 2011. Full-text available in BORA: http://hdl.handle.net/1956/5023
Paper J: Min Wan, Yu Wang, Egil Bae, Xue-Cheng Tai, Desheng Wang, Reconstructing Open Surfaces via Graph-Cuts. Submitted for journal publication. Full-text available in BORA: http://hdl.handle.net/1956/5024