In this paper we present optimization algorithms for image restoration based on the total variation (TV) minimization framework of L. Rudin, S. Osher and E. 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.
Citation
CORC Report TR-2004-05, Department of Industrial Engineering and Operations Research, Columbia University