[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(
)
快速交替方向乘子法求解基于全变分的图像重建问题
)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
- 陶敏
- 南京邮电大学理学院, 南京 210046
- 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.
- 采用一种快速的新型算法, 即交替方向乘子法求解图像重建的全变分模型.首先, 对全变分模型进行等价变形, 使之转化成带有等式约束的可分的凸优化问题.然后, 通过引入增广拉格朗日函数, 并采用Gauss-Seidel迭代的思想, 对问题中2块变量交替极小化, 最后更新乘子.因为该方法充分利用了问题的特殊结构, 将原问题分解成一系列容易求解的低维子问题, 所以每步的计算工作量主要是由2次快速傅立叶变换决定.初步的数值结果表明所提出的快速方法比一些经典的方法更加稳定、有效.
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]