A primal-dual active-set algorithm for bilaterally constrained total variation deblurring and piecewise constant Mumford-Shah segmentation problems

Abstract

In this paper, we propose a fast primal-dual algorithm for solving bilaterally constrained total variation minimization problems which subsume the bilaterally constrained total variation image deblurring model and the two-phase piecewise constant Mumford-Shah image segmentation model. The presence of the bilateral constraints makes the optimality conditions of the primal-dual problem semi-smooth which can be solved by a semi-smooth Newton's method superlinearly. But the linear system to solve at each iteration is very large and difficult to precondition. Using a primal-dual active-set strategy, we reduce the linear system to a much smaller and better structured one so that it can be solved efficiently by conjugate gradient with an approximate inverse preconditioner. Locally superlinear convergence results are derived for the proposed algorithm. Numerical experiments are also provided for both deblurring and segmentation problems. In particular, for the deblurring problem, we show that the addition of the bilateral constraints to the total variation model improves the quality of the solutions. © 2008 Springer Science+Business Media, LLC.