[1] Tao Min,. Fast alternating direction method of multipliersfor total-variation-based image restoration [J]. Journal of Southeast University (English Edition), 2011, 27 (4): 379-383. [doi:10.3969/j.issn.1003-7985.2011.04.007]

Copy

Fast alternating direction method of multipliersfor total-variation-based image restoration()

Share：

Journal of Southeast University (English Edition)[ISSN:1003-7985/CN:32-1325/N]

Volumn:

27

Issue:

2011 4

Page:

379-383

Research Field:

Mathematics, Physics, Mechanics

Publishing date:

2011-12-31

Info

Title:

Fast alternating direction method of multipliersfor total-variation-based image restoration

Author(s):

Tao Min

School of Science, Nanjing University of Posts and Telecommunications, Nanjing 210046, China

Keywords:

total variation;  deconvolution;  alternating direction method of multiplier

PACS:

O221.2

DOI:

10.3969/j.issn.1003-7985.2011.04.007

Abstract:

A novel algorithm, i.e. the fast alternating direction method of multipliers(ADMM), is applied to solve the classical total-variation(TV)-based model for image reconstruction. First, the TV-based model is reformulated as a linear equality constrained problem where the objective function is separable. Then, by introducing the augmented Lagrangian function, the two variables are alternatively minimized by the Gauss-Seidel idea. Finally, the dual variable is updated. Because the approach makes full use of the special structure of the problem and decomposes the original problem into several low-dimensional sub-problems, the per iteration computational complexity of the approach is dominated by two fast Fourier transforms. Elementary experimental results indicate that the proposed approach is more stable and efficient compared with some state-of-the-art algorithms.

References:

[1] Tikhonov A, Arsenin V. Solution of ill-posed problems[M]. Washington, DC: Winston, 1977.
[2] Rudin L I, Osher S, Fatemi E. Nonlinear total variation based noise removal algorithms[J]. Physica D, 1992, 60(1/2/3/4): 259-268.
[3] Mumford D, Shah J. Optimal approximations by piecewise smooth functions and associated variational problems[J]. Communications on Pure and Applied Mathematics, 1989, 42(5): 577-685.
[4] Shah J. A common framework for curve evolution, segmentation and anisotropic diffusion[C]//Proceedings of the 1996 Conference on Computer Vision and Pattern Recognition. San Francisco, CA, USA, 1996: 136-142.
[5] Bioucas-Dias J M, Figueiredo M A T. A new TwIST: two-step iterative shrinkage/thresholding algorithms for image restoration[J]. IEEE Transactions on Image Processing, 2007, 16(12): 2992-3004.
[6] Dobson D, Santosa F. Recovery of blocky images from noisy and blurred data[J]. SIAM Journal on Applied Mathematics, 1996, 56(4): 1181-1198.
[7] Rudin L I, Osher S. Total variation based image restoration with free local constraints[C]//Proceedings of the First International Conference on Image Processing. Budapest, Hungary, 1994, 1: 31-35.
[8] Elad M. Why simple shrinkage is still relevant for redundant representations?[J].IEEE Transactions on Information Theory, 2006, 52(12): 5559-5569.
[9] Elad M, Matalon B, Zibulevsky M. Image denoising with shrinkage and redundant representations[C]//Proceedings of the 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. New York, USA, 2006, 2: 1924-1931.
[10] Starck J L, Candès E, Donoho D. Astronomical image representation by the curvelet transform[J]. Astronomy and Astrophysics, 2003, 398(2): 785-800.
[11] Vogel C R, Oman M E. Iterative methods for total variation denoising[J]. SIAM Journal on Scientific Computing, 1996, 17(1): 227-238.
[12] Vogel C R, Oman M E. Fast, robust total variation based reconstruction of noisy, blurred images[J]. IEEE Transactions on Image Processing, 1998, 7(6): 813-824.
[13] Beck A, Teboulle M. A fast iterative shrinkage-thresholding algorithm for linear inverse problems[J]. SIAM Journal on Image Sciences, 2009, 2(1): 183-202.
[14] Wang Y, Yang J, Yin W, et al. A new alternating minimization algorithm for total variation image reconstruction[J]. SIAM Journal on Image Sciences, 2008, 1(3): 948-951.
[15] Hestenes M R. Multiplier and gradient methods[J]. Journal of Optimization Theory and Applications, 1969, 4(5): 303-320.
[16] Gabay D, Mercier B. A dual algorithm for the solution of nonlinear variational problems via finite-element approximations[J]. Computers and Mathematics with Applications, 1976, 2(1): 17-40.
[17] Glowinski R. Numerical methods for nonlinear variational problems[M]. New York: Springer-Verlag, 1984.
[18] Glowinski R, Tallec P L. Augmented Lagrangian and operator-splitting methods in nonlinear mechanics[M]. Philadelphia: SIAM, 1989.
[19] He B S, Yang H. Some convergence properties of method of multipliers for linearly constrained monotone variational in-equalities[J]. Operations Research Letters, 1999, 23(3/4/5): 151-161.
[20] Ng M K, Chan R H, Tang W C. A fast algorithm for deblurring models with Neumann boundary conditions[J]. SIAM Journal on Scientific Computing, 1999, 21(3): 851-866.

Memo

Memo:

Biography: Tao Min(1979—), female, graduate, lecturer, taomin0903@gmail.com.
Foundation item: The Scientific Research Foundation of Nanjing University of Posts and Telecommunications(No.NY210049).
Citation: Tao Min. Fast alternating direction method of multipliers for total-variation-based image restoration[J].Journal of Southeast University(English Edition), 2011, 27(4):379-383.[doi:10.3969/j.issn.1003-7985.2011.04.007]

Common functions