Paper Info
Title
Global Minimization for Continuous Multiphase Partitioning Problems Using a Dual Approach
Abstract
This paper is devoted to the optimization problem of continuous multi-partitioning, or multi-labeling, which is based on a convex relaxation of the continuous Potts model. In contrast to previous efforts, which are tackling the optimal labeling problem in a direct manner, we first propose a novel dual model and then build up a corresponding duality-based approach. By analyzing the dual formulation, sufficient conditions are derived which show that the relaxation is often exact, i.e. there exists optimal solutions that are also globally optimal to the original nonconvex Potts model. In order to deal with the nonsmooth dual problem, we develop a smoothing method based on the log-sum exponential function and indicate that such a smoothing approach leads to a novel smoothed primal-dual model and suggests labelings with maximum entropy. Such a smoothing method for the dual model also yields a new thresholding scheme to obtain approximate solutions. An expectation maximization like algorithm is proposed based on the smoothed formulation which is shown to be superior in efficiency compared to earlier approaches from continuous optimization. Numerical experiments also show that our method outperforms several competitive approaches in various aspects, such as lower energies and better visual quality.
Year
DOI
Venue
2011
10.1007/s11263-010-0406-y
International Journal of Computer Vision
Keywords
Field
DocType
Convex relaxation,Image segmentation,Primal-dual methods,Total variation
Continuous optimization,Mathematical optimization,Computer science,Expectation–maximization algorithm,Smoothing,Duality (optimization),Minimisation (psychology),Principle of maximum entropy,Optimization problem,Potts model
Journal
Volume
Issue
ISSN
92
1
0920-5691
Citations 
PageRank 
References 
82
1.99
36
Authors
3
Name
Order
Citations
PageRank
Egil Bae139115.56
Jing Yuan223711.92
Xue-Cheng Tai32090131.53