基于非线性动态阈值FISTA的图像修复算法

张家林，曹津国，余义斌，张玉兰

（五邑大学 信息工程学院，广东 江门 529020）

基于非线性动态阈值FISTA的图像修复算法

张家林，曹津国，余义斌，张玉兰

（五邑大学 信息工程学院，广东 江门 529020）

快速迭代收缩阈值算法（FISTA）因其快速、有效特性被广泛应用在图像复原领域.但此算法采用固定阈值，不能自适应更新中的复原图像水平，进而不能更有效地收敛，因此本文对其进行改进，提出非线性动态阈值（NLDT）方法，选取小波变换作为稀疏先验项.图像修复的仿真实验表明，当总迭代次数大于20，NLDT能产生比其他实验方法更高的PSNR，说明了本文算法能快速得到更精确的解.本文方法可用于图像去噪、图像去模糊、图像超分辨率等，也可用于计算机视觉和机器学习等大规模优化问题.

快速迭代收缩阈值；小波变换；非线性动态阈值；图像修复

照片受污损、刮擦和遮挡等缘故都会造成图像退化，数字图像修复是一项有效的图片修复技术.对于一张部分内容缺失的图像，数字图像修复技术利用已有的图像信息可重建缺失的部分，其已成为图像复原研究中的一个重要课题，许多学者进行了多方面的探索和研究，主要有以下几类：

第一类修复算法是基于扩散的方法，它是在像素层次上对已知图像区域进行扩散来填充缺失区域[1-2].其后，Chan和Shen等人提出了一种基于全变差模型的变分框架模型来修复缺失信息[3].基于扩散的图像修复算法对于较小缺失且非纹理区域的已取得了很好的效果，然而，对于较大缺失区域或纹理区域则会产生平滑效应.

第二类修复算法是基于样例的图像修复算法.此类方法基于图像块层次，将已知图像区域信息扩散到缺失区域.典型的有：Wu等[4]提出的基于交叉等照度线样例算法以及Wong等[5]提出的基于样本例非局部均值的图像修复算法.与基于扩散的图像修复算法相比，基于样例的图像修复算法可以对较大缺失区域有很好的恢复效果.

最近，基于稀疏表示模型被应用到图像修复算法中.稀疏表示的基本思想是用一组过完备变换的组合稀疏地表示图像，缺失的像素可通过自适应地更新稀疏表示系数来填充.Guleryuz等[6]提出的自适应稀疏表示模型.Elad等[7]提出利用两个不相关的过完备变换来稀疏表示图像的卡通层和纹理层.基于稀疏表示模型的图像修复算法同基于扩散方法一样，能对较小缺失非纹理区域产生高质量的复原效果，而对较大缺失区域或纹理区域不能产生高质量的复原效果.

本文选用小波变换作为稀疏的正则化项，属于基于稀疏表示模型.快速迭代收缩阈值算法（Fast Iterative Shrinkage Thresholding Algorithm，FISTA）因其快速、有效特性被广泛应用在图像复原领域[8].针对FISTA的固定阈值不能自适应更新图像复原水平，进而不能更有效地收敛，为此本文提出改进的阈值方法，即非线性动态阈值（Non-Linear Dynamic Thresholding，NLDT）.

1 理论基础

图像复原是一种病态的线性逆问题.退化图像的一般模型为:

其中A表示有界的线性算子，x表示原始图像，y表示退化图像，n表示方差为2s的附加噪声.式（1）中，当A为单位矩阵，则是去噪模型，当A为掩模算子，则是修复模型，当A为模糊核，则是去卷积模型.式（1）是一病态的线性逆问题，为此，需对真实解空间进行正则化约束.下面将讨论正则化模型.

1.1 常用模型

自然图像的先验模型可以对真实解空间进行正则化约束，从而将具有不适定性的图像复原病态问题转换为适定问题，获得符合人眼视觉特性的稳定解.为此，需添加正则化项到数据拟合项f(x)中.

其他的正则化模型包括全变差（Total variation，TV）正则化[9]、Tikhonov正则化[10]、Mumford-Shah正则化[11-12]等.这些正则化模型在图像复原和压缩感知领域[13-14]备受关注.由于小波具有很好的时频局部化特性，其稀疏的正则化已被广泛地用在图像复原中.

另外的正则化方法就是分析法，它是基于分析图像自身，而不是它的表示系数.在分析法的图像复原里，最广泛且常用的正则化是TV范数[9,14].把TV正则化项添加到数据拟合项里，得到了一个非平滑的凸优化模型

1.2 算法基础

式（4）和（5）类型问题受到大量研究人员的广泛关注，一些先进的算法属于迭代阈值算法[8,17-19]等，这些算法可有效地解决问题（4）和（5）.

尽管上述复原算法处理式（4）和（5）问题比较成功，但在图像复原质量和速度上仍有待提高.本文基于邻近算子理论，提出非线性动态阈值方法（NLDT），它可以被用来解决所有基于阈值的算法，例如迭代收缩阈值算法（ISTA）[8-9]，快速迭代收缩阈值算法（FISTA）等.为简便起见，基于FISTA的NLDT算法就记为NLDT-FISTA.

2 迭代阈值算法

2.1 阈值函数

阈值函数是迭代算法的一个重要组成部分.经典的阈值包括硬阈值、软阈值、半软阈值、stein阈值等.常用的阈值有硬阈值和软阈值.硬阈值函数的计算为：

软阈值函数的计算为

图1 阈值函数

硬阈值可保护图像的边界和其他局部特征，但复原图像产生视觉上的振铃效应和伪吉布斯现象.软阈值产生更平滑的复原图像，同时造成边界模糊失真.

2.2 迭代收缩阈值算法（ISTA）

迭代收缩阈值算法（ISTA）可有效地解决式（8）的问题，它是一种基于梯度的简便算法.在信号处理领域，或称为期望最大法（Expectation Maximization，EM）[17]或最大最小法（Majorization-Minimization，MM）算法[20]以及邻近分裂法[19].ISTA可用于解决式（8），通过生成序列

3 非线性动态阈值（NLDT）函数

在迭代去噪过程中，阈值需自适应噪声的水平.准确地来说，在迭代的起始阶段，更大一点的阈值是必要的.随着迭代次数的增加，由于噪声水平变得越来越低，相应的阈值应越来越小.在参考文献[21]，作者提出了线性动态阈值函数

可用通用的阈值[22]，或Minimax description length（MDL）[23]去计算

基于FISTA，本文提出了NLDT-FISTA，它可用来解决式（4）的问题.算法1总结了FISTA-NLDT，它要快于ISTA-NLDT.为方便起见，NLDT-FISTA就简称为NLDT.如算法1所示，NLDT包括关键的两个步骤：梯度下降和软阈值操作

图2 动态阈值函数（N=20，对于NLDT，=1）

NLDT满足收敛的条件因它满足利普兹条件.事实上，这个算法可被用于任何基于收缩阈值的问题中，例如在，范数计算方面的优化.算法1（基于FISTA的NLDT）如下：

4 实验结果与分析

实验在HzIntel CPU2.20 G、内存4 GB的计算机上进行，在MATLAB R2014A上测试相同的图像，对迭代硬阈值算法（IHTA）、快速迭代硬阈值算法（FIHTA）与本文提出的NLDT算法在修复图像上进行了比较.比较结果如图3、4、5所示.

4.1 非线性动态阈值的修复（NLDT）

在这部分，本文考虑了一类经典的掩模算子：随机像素缺失的掩模.关于修复实验，设置了2个缺失率，分别是60%和70%，并在IHTA、FIHTA及NLDT算法设置总迭代次数N=50.本文选择小波变换作为稀疏表示的方法，即，.对于IHTA，.为了客观评价修复质量，用峰值信噪比（PSNR）作为评价标准.参数的选择，原则上是基于最大化PSNR值.

图3 PSNR值的比较（缺失率：60%）

为了进一步说明修复效果，本文对复原图像也进行了主观视觉的比较，图4、图5和图6表明了NLDT修复的图像更加清晰.由IHTA处理的修复图像缺失的像素还未能完全恢复.也就是说，与FISTA相比，NLDT更快速得到更精确的解.对于一些应用，比如说大规模的机器学习，要求快速适宜的解，NLDT将是更好的选择.

图4 不同算法下修复图像的视觉比较（Girl，缺失率：60%）

图5 不同算法下修复图像的视觉比较（Cameraman，缺失率：60%）

图6 不同算法下修复图像的视觉比较（Girl，缺失率：70%）

5 结论

受线性收缩阈值函数启发，基于小波稀疏正则化模型，通过理论分析，对FISTA算法的固定阈值进行了改进，提出了NLDT-FISTA.通过仿真实验比较和分析，发现在相同的迭代次数下，NLDT-FISTA比其他实验方法得到更高的PSNR.从主观而言，NLDT-FISTA修复效果更好，具有很强的竞争力.同时，NLDT-FISTA快速有效，可应用于大规模的优化当中.本文把NLDT改进阈值算法应用在ISTA和FISTA算法上，把NLDT应用到其他阈值算法中将是下一步研究的方向.

[1] BERTALMIO M, SAPIRO G, CASELLES V, et al.Image inpainting [C]//Conference on Computer Graphics and Interactive Techniques，SIGGRAPH 2000, New Orleans, LA USA: ACM Press Addison- Wesley Publishing, 2000: 417-424.

[2] BERTALMIO M, BERTOZZI A L, SAPIRO G.Navier-stokes, fluid dynamics, and image and video Inpainting [C]//Computer Vision and Pattern Recognition, CVPR 2001, Dec 8-14, 2001, [S.l.]: IEEE Computer Society.2001: 355-362.

[3] CHAN T, SHEN J.Local inpainting models and TV inpainting [J].SIAM JAppl Math, 2001, 62(3): 1019-1043.

[4] WU J, RUAN Q.Object removal by cross isophotes exemplar-based inpainting [C]//International Conference on Pattern Recognition, ICPR, 2006, Aug 20-24, 2006, Washington, DC, USA: IEEE Computer Society 2006: 810-813.

[5] WONG A, ORCHARD J.A nonlocal-means approach to exemplar-based inpainting [C]//International Conference on Image Processing, ICIP 2008, October 12-15, 2008, San Diego, California, USA: DBLP, 2008: 2600-2603.

[6] GULERYUZ O G.Nonlinear approximation based image recovery using adaptive sparse reconstructions and iterated denoising-part II: adaptive algorithms [J].IEEE Transactions on Image Processing, 2006, 15(3): 555-571.

[7] ELAD M, STARCK J L, QUERRE P, et al.Simultaneous cartoon and texture image inpainting using morphological component analysis (MCA) [J].Applied & Computational Harmonic Analysis, 2005, 19(3): 340-358.

[8] BECK A, TEBOULLE M.A fast iterative shrinkage-thresholding algorithm for linear inverse problems [J].Siam Journal on Imaging Sciences, 2009, 2(1): 183-202.

[9] RUDIN L I, OSHER S, FATEMI E.Nonlinear total variation based noise removal algorithms [J].Physica D Nonlinear Phenomena, 1992, 60(1-4): 259-268.

[10] TIKHONOV A N, ARSENIN V Y.Solution of Ill-posed problems [J].Mathematics of Computation, 1978, 32(144): 491-491.

[11] SEDLAK J, MORAVEK J.Optimal approximations by piecewise smooth functions and associated variational problems [J].Communications on Pure & Applied Mathematics, 1989, 42(5): 577-685.

[12] SHAH J.A common framework for curve evolution, segmentation and anisotropic diffusion [J].Proceedings IEEE Cvpr, 1996: 136.

[13] CANDES E J, ROMBERG J K, Tao T.Stable signal recovery from incomplete and inaccurate measurements [J].Communications on Pure & Applied Mathematics, 2006, 59(8): 1207-1223.

[14] CHAMBOLLE A.An algorithm for total variation minimization and applications [J].Journal of Mathematical Imaging and Vision, 2004, 20(1): 89-97.

[15] BIOUCASDIAS J M.Bayesian wavelet-based image deconvolution: a GEM algorithm exploiting a class of heavy-tailed priors [J].IEEE Transactions on Image Processing, 2006, 15(4): 937-951.

[16] ELAD M, MATALON B, ZIBULEVSKY M.Image denoising with shrinkage and redundant representations [C]//Computer Vision and Pattern Recognition, 2006, June 17-22, 2006, Washington, DC, USA.IEEE Computer Society, 2006: 1924-1931.

[17] FIGUEIREDO M A, Nowak R D.An EM algorithm for wavelet-based image restoration [J].IEEE Transactions on Image Processing A Publication of the IEEE Signal Processing Society, 2003, 12(8): 906-916.

[18] DAUBECHIES I, DEFRISE M, MOL De C.An iterative thresholding algorithm for linear inverse problems with a sparsity constraint [J].Communications on Pure & Applied Mathematics, 2003, 57(11): 1413-1457.

[19] WRIGHT S J, NOWAK R D, FIGUEIREDO M A T.Sparse reconstruction by separable approximation [J].IEEE Transactions on Signal Processing, 2009, 57(7): 2479-2493.

[20] CHAN T, ESEDOGLU S, PARK F, et al.Total variation image restoration: over view and recent developments [M]//Handbook of Mathematical Models in Computer Vision.New York: Springer, 2006: 17-31.

[21] PEYRE G.The numerical tours of signal processing-advanced computational signal and image processing [J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2011, 15(4): 377-384.

[22] DONOHO D L, Johnstone J M.Ideal spatial adaptation by wavelet shrinkage [J].Biometrika, 1994, 81(3): 425-455.

[23] KRIM H, SCHICK I C.Minimax description length for signal denoising and optimized representation [J].IEEE Transactions on Information Theory, 1999, 45(3): 898-908.

[责任编辑：韦 韬]

An Image Restoration Algorithm Based on Non-linear Dynamic Threshold of FISTA

ZHANG Jia-lin, CAO Jin-guo, YU Yi-bin, ZHANG Yu-lan
(School of Information Engineering, Wuyi University, Jiangmen 529020, China)

FISTA is widely used in the field of image restoration due to its fast and effective properties.But as this algorithm adopts the fixed thresholding, it cannot adapt to the level of restored image in updating, nor can it converge more effectively.In this paper, we propose a Non-linear Dynamic Thresholding (NLDT) method to improve FISTA and select the Wavelet transform as the sparse priors.Simulation experiments on image inpainting show that when the total number of iterations is greater than 20, NLDT always produces higher PSNR than other competing methods.It means that our method can speedily obtain more accurate solutions.Our method can be used in image denoising, image deblurring, and image super-resolution, etc.It can also be used in large scale optimization, such as computer vision and machine learning.

fast iterative shrinkage thresholding; wavelet transform; non-liner dynamic thresholding; image inpainting

TP391.41

A

1006-7302（2017）02-0033-07

2016-12-12

广东高校省级重点平台和重大科研项目特色创新项目（自然科学类）（2015KTSCX148）；浙江省信号处理重点实验室开放课题（ZJKL_4_SP-OP2014-05）

张家林（1990—），男，安徽六安人，在读硕士生，主要研究方向是图像处理；余义斌，副教授，博士，硕士生导师，通信作者，主要研究方向为机器视觉与图像处理.