Image reconstruction from incomplete convolution data via total variation regularization
Abstract
Variational models with Total Variation (TV) regularization have long been known to preserve image edges and produce high quality reconstruction. On the other hand, recent theory on compressive sensing has shown that it is feasible to accurately reconstruct images from a few linear measurements via TV regularization. However, in general TV models are difficult to solve due to the nondifferentiability and the universal coupling of variables. In this paper, we propose the use of alternating direction method for image reconstruction from highly incomplete convolution data, where an image is reconstructed as a minimizer of an energy function that sums a TV term for image regularity and a least squares term for data fitting. Our algorithm, called RecPK, takes advantage of problem structures and has an extremely low per-iteration cost. To demonstrate the efficiency of RecPK, we compare it with TwIST, a state-of-the-art algorithm for minimizing TV models. Moreover, we also demonstrate the usefulness of RecPK in image zooming.References
A. Beck, and M. Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM Journal on Imaging Sciences, vol. 2, no. 1, pp. 183–202, 2009.
J. Bioucas-Dias, and M. Figueiredo, A new TwIST: Two-step iterative thresholding algorithm for image restoration, IEEE Transactions on Image Processing, vol. 16, no. 12, pp. 2992–3004, 2007.
J. F. Cai, R. Chan and M. Nikolova, Two phase methods for deblurring images corrupted by impulse plus Gaussian noise, Inverse Problems and Imaging, vol. 2, no. 2, pp. 187–204, 2008.
E. Candés, and Y. Plan, Near-ideal model selection by L1 minimization, Annals of Statistics, vol. 37, pp. 2145–2177, 2008.
E. Candés, and J. Romberg, Practical signal recovery from random projections, Wavelet Applications in Signal and Image Processing XI, Proc. SPIE Conf. 5914, 2004.
E. Candés, and J. Romberg, Sparsity and incoherence in compressive sampling, Inverse Problems, vol. 23, pp. 969–985, 2006.
E. Candés, J. Romberg, and T. Tao, Stable signal recovery from incomplete and inaccurate information, Communications on Pure and Applied Mathematics, vol. 59, pp. 1207–1233, 2005.
E. Candés, J. Romberg, and T. Tao, Robust uncertainty rinciples: Exact signal reconstruction from highly incomplete frequency information, IEEE Transactions on Information Theory, vol. 52, no. 2, pp. 489–509, 2006.
A. Chambolle, An algorithm for total variation minimization and applications, Journal of Mathematical Imaging and Vision, vol.20, pp. 89–97, 2004.
A. Chambolle, and P. L. Lions, Image recovery via total variation minimization and related problems, Numerische Mathematik, vol. 76, pp. 167–188, 1997.
A. Chambolle, and T. Pock A First-Order Primal-Dual Algorithm for Convex Problems with Applications to Imaging, Journal of Mathematical Imaging and Vision, vol.40, pp. 120–145, 2011.
T. F. Chan, and S. Esedoglu, Aspects of total variation regularized ℓ1 function approximation, SIAM Journal on Applied Mathematics, vol. 65, pp. 1817–1837, 2005.
T. F. Chan, S. Esedoglu, F. Park, and A. Yip, Total variation image restoration: Overview and recent developments, in Handbook of Mathematical Models in Computer Vision, edited by N. Paragios, Y. Chen, and O. Faugeras, Springer-Verlag, New York, pp. 17–31,
D. Donoho, Compressed sensing, IEEE Transactions on Information Theory, vol. 52, no. 4, pp. 1289–1306, 2006.
J. Douglas, and H. Rachford, On the Numerical Solution of Heat Conduction Problems in Two and Three Space Variables, Transactions of the American mathematical Society, 82, pp. 421–439, 1956.
J. Eckstein, and D. Bertsekas, On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators, Mathematical Programming, 55, North-Holland, 1992.
M. Elad, Why simple shrinkage is still relevant for redundant representations? IEEE Transactions on Information Theory, vol. 52, pp. 5559–5569, 2006.
M. Elad, B. Matalon, and M. Zibulevsky, Image denoising with shrinkage and redundant representations, in Proc. IEEE Computer Society Conference on Computer Vision and Pattern Recognition, New York, 2006.
E. Esser, Applications of Lagrangian-Based Alternating Direction Methods and Connections to Split Bregman, CAM Report 09–31, UCLA, 2009.
M. Figueiredo, J. Bioucas-Dias, and M. V. Afonso, Fast frame-based image deconvolution using variable splitting and constrained optimization, IEEE Workshop on Statistical Signal Processing - SSP009, Cardiff, 2009.
D. Gabay, and B. Mercier, A dual algorithm for the solution of nonlinear variational problems via finite-element approximations, Computers and Mathematics with Applications, vol. 2, pp. 17–40, 1976.
R. Glowinski, Numerical Methods for Nonlinear Variational Problems, Springer-Verlag, New York, Berlin, Heidelberg, Tokyo,1984.
R. Glowinski, and P. Le Tallec, Augmented Lagrangian and Operatorsplitting Methods in Nonlinear Mechanics, SIAM Studies in Applied Mathematics, Philadelphia, PA, 1989.
R. Glowinski, and A. Marrocco, Sur lapproximation par elements finis dordre un, et la resolution par penalisation-dualite dune classe de problemes de Dirichlet nonlineaires, Rev. Francaise dAut. Inf. Rech. Oper., R-2, pp. 41-76, 1975.
T. Goldstein, and S. Osher, The split bregman method for l1regularized problems, SIAM Journal on Imaging Sciences, vol. 2, no. 2, pp. 323-343, 2009.
B. S. He, L.Z. Liao, D. Han, and H. Yang, A new inexact alternating directions method for monotone variational inequalities, Mathematical Programming, Ser. A, vol. 92, pp. 103–118, 2002.
M. R. Hestenes, Multiplier and gradient methods, Journal of Optimization Theory and Applications, vol. 4, pp. 303–320, 1969.
S. Osher, M. Burger, D. Goldfarb, J. Xu, and W. Yin, An iterated regularization method for total variation-based image restoration, SIAM: Multiscale Modeling and Simulation, vol. 4, pp. 460–489, 2005.
M. J. D. Powell, A method for nonlinear constraints in minimization problems, in Optimization, R. Fletcher, ed., Academic Press, New York, NY, pp. 283–298, 1969.
J. Romberg, Compressive sampling by random convolution, SIAM Journal on Imaging Sciences, vol. 2, no. 4, pp. 1098-1128, 2009.
L. Rudin, S. Osher, and E. Fatemi, Nonlinear total variation based noise removal algorithms, Physica D, pp. 259–268, 1992.
S. Setzer, Split Bregman Algorithm, Douglas-Rachford Splitting and Frame Shrinkage, Proceedings of the 2nd International Conference on Scale Space Methods and Variational Methods in Computer Vision, Lecture Notes in Computer Science, 2009.
J. L. Starck, E. Candés, and D. Donoho, Astronomical image representation by the curvelet transform, Astronomy and Astrophysics, vol. 398, pp. 785–800, 2003.
J. L. Starck, M. Nguyen, and F. Murtagh, Wavelets and curvelets for image deconvolution: a combined approach, Signal Processing, vol. 83, pp. 2279–2283, 2003.
C. R. Vogel and M. E. Oman, A fast, robust total variation based reconstruction of noisy, blurred images, IEEE Transactions on Image Processing, vol. 7, pp. 813–824, 1998.
C. R. Vogel and M. E. Oman, Iterative methods for total variation denoisin, SIAM Journal on Scientific Computing, vol. 17, pp.227–238, 1996.
Y. Wang, J. Yang, W. Yin and Y. Zhang, A new alternating minimization algorithm for total variation image reconstruction, SIAM Journal on Imaging Sciences, vol. 1, no. 3, pp. 248–272, 2008.
J. Yang, W. Yin, Y. Zhang, and Y. Wang, A fast algorithm for edge-preserving variational multichannel image restoration, SIAM Journal on Imaging Sciences, vol. 2, no. 2, pp. 569–592, 2009.
J. Yang, Y. Zhang, and W. Yin, An efficient TVL1 algorithm for deblurring of multichannel images corrupted by impulsive noise, SIAM Journal on Scientific Computing, vol. 31, no. 4, pp. 2842–2865, 2009.
J. Yang, Y. Zhang, and W. Yin, A fast alternating directionmethod for TVL1-L2 signal reconstruction from partial Fourier data, IEEE Journal of Selected Topics in Signal Processing, vol. 4, no. 2, pp. 288–297, 2010.
C. Ye, and X. Yuan, A descent method for structured monotone variational inequalities, Optimization Methods and Software, vol. 22, no. 22, pp. 329–338, 2007.
W. Yin, S. Morgan, J. Yang and Y. Zhang, Practical compressive sensing with Toeplitz and circulant matrices, Proceedings of SPIE, Visual Communications and Image Processing, 7744K, 2010.
W. Yin, S. Osher, D. Goldfarb, and J. Darbon, Bregman Iterative Algorithms for L1-Minimization with Applications to Compressed Sensing, SIAM Journal on Imaging Sciences, vol. 1, no. 1, pp. 143–168, 2008.
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
