A New Alternating Minimization Algorithm for Total Variation Image Reconstruction

作者：Wang Yilun^*; Yang Junfeng; Yin Wotao; Zhang Yin

来源：SIAM Journal on Imaging Sciences, 2008, 1(3): 248-272.

DOI：10.1137/080724265

• half-quadratic
• image deblurring
• isotropic total variation
• fast Fourier transform

We propose, analyze, and test an alternating minimization algorithm for recovering images from blurry and noisy observations with total variation (TV) regularization. This algorithm arises from a new half-quadratic model applicable to not only the anisotropic but also the isotropic forms of TV discretizations. The per-iteration computational complexity of the algorithm is three fast Fourier transforms. We establish strong convergence properties for the algorithm including finite convergence for some variables and relatively fast exponential (or q-linear in optimization terminology) convergence for the others. Furthermore, we propose a continuation scheme to accelerate the practical convergence of the algorithm. Extensive numerical results show that our algorithm performs favorably in comparison to several state-of-the-art algorithms. In particular, it runs orders of magnitude faster than the lagged diffusivity algorithm for TV-based deblurring. Some extensions of our algorithm are also discussed.

• 出版日期2008
• 单位南京大学