Second-order Cone Programming Methods for Total Variation-Based Image Restoration
Authors:
- Donald GoldfarbDGDonald Goldfarb
- Wotao YinWYWotao Yin
- 1 January 2005
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Scientific Computing
- Vol. 27 (2) , 622-645
Abstract
In this paper we present optimization algorithms for image restoration based on the total variation (TV) minimization framework of Rudin, Osher, and Fatemi (ROF). Our approach formulates TV minimization as a second-order cone program which is then solved by interior-point algorithms that are efficient both in practice (using nested dissection and domain decomposition) and in theory (i.e., they obtain solutions in polynomial time). In addition to the original ROF minimization model, we show how to apply our approach to other TV models, including ones that are not solvable by PDE-based methods. Numerical results on a varied set of images are presented to illustrate the effectiveness of our approach.Keywords
This publication has 20 references indexed in Scilit:
- Image Sharpening by Flows Based on Triple Well PotentialsJournal of Mathematical Imaging and Vision, 2004
- Total Bounded Variation Regularization as a Bilaterally Constrained Optimization ProblemSIAM Journal on Applied Mathematics, 2004
- Noise removal using fourth-order partial differential equation with applications to medical magnetic resonance images in space and timeIEEE Transactions on Image Processing, 2003
- Second-order cone programmingMathematical Programming, 2003
- Mathematical Problems in Image Processing2002
- Oscillating Patterns in Image Processing and Nonlinear Evolution Equations2001
- An Efficient Primal-Dual Interior-Point Method for Minimizing a Sum of Euclidean NormsSIAM Journal on Scientific Computing, 2000
- A Nonlinear Primal-Dual Method for Total Variation-Based Image RestorationSIAM Journal on Scientific Computing, 1999
- Image recovery via total variation minimization and related problemsNumerische Mathematik, 1997
- Nested Dissection of a Regular Finite Element MeshSIAM Journal on Numerical Analysis, 1973