乔田田,王际朝,李维国,吴勃英

(1.中国石油大学理学院,山东青岛 266580；2.哈尔滨工业大学数学系,黑龙江哈尔滨 150001)

一种基于线性化Bregman迭代的图像去模糊新方法

乔田田1,2,王际朝1,李维国1,吴勃英2

(1.中国石油大学理学院,山东青岛 266580；2.哈尔滨工业大学数学系,黑龙江哈尔滨 150001)

基于线性化Bregman迭代法带有软阈值算子的A+算法,结合广义逆迭代格式,提出一个新的混乱迭代方法求解图像的去模糊问题。在算法上充分考虑对细节信息的有效利用,以弥补在每步迭代过程中为了去模糊而过滤掉的图像细节特征的损失,达到有效滤波的效果。同时在计算时间和恢复效果之间取得平衡。数值试验结果表明,新方法在提高计算效率的同时还能得到很好的图像恢复效果,特别是细节特征和稀疏纹理的恢复。

线性化Bregman迭代法；图像去模糊；混乱迭代法；广义逆

图像恢复是图像处理的基本问题之一。图像去模糊问题主要是沿着模型和算法两个方面发展的。模型的改进和建立以变分法[1-2]、正则化方法[2-3]、和PDE方法[4-5]为基础；而在算法上就较为广泛,例如原-对偶方法[6]、混合梯度下降法[7]、求解PDE方程的数值解法等。近年来l1-优化模型应用范围十分之广,尤其是在信号的稀疏优化方面[8-10]。将其用于图像去模糊问题,也得到了较好的结果。Osher等[11-13]将优化中的Bregman方法用于图像处理中l1-优化模型的求解,得到了快速的具有显著效果的一系列算法。在Bregman算法的基础上结合软阈值算子,将其应用于图像去模糊处理中的l1-优化模型[14-16],取得了突破性的进展。笔者以Bregman算法为基础结合广义逆的迭代技术,将其应用于求解l1-优化模型,提出一个新的混乱迭代算法来解决图像去模糊问题。

1 背景介绍

1.1 研究问题

设Ω⊂R2是有界开区域,u∈Ω表示真实图像,观测的模糊图像为

式中,A为线性模糊算子；n为噪音。事实上,由于线性算子的性质,这里可以忽略n,而仅考虑Au=f。

从f中将u恢复出来,最简单的方法就是Tikhonov正则化方法[2-3]:

随之,出现了很多针对ROF模型的减少“梯子现象”的改进模型。而近年来,由于研究者将l1-稀疏优化的方法应用到图像处理中取得了较好的效果,以及l1-范数本身的特点结合优化思想,使得将其用以解决图像去模糊问题也引起了广泛的关注[8]:

本文就是针对模型(4),提出了新的有效算法来解决图像去模糊问题。

1.2 广义逆

定义1:[17]:设A∈Cm×n,若X∈Cn×m满足下面性质,即Moore-Penrose条件:

则称X为A的伪逆,也称作Moore-Penrose广义逆,记作A+。

定义2[18]:设A,B∈Cn×m,称

这是最为熟悉的优化模型。该模型对于图像恢复具有一定的效果,但由于其中l2-范数的光滑性,对于细节和边界的恢复欠佳。而总变差模型利用TV范数克服了l2-范数过度光滑的缺点,能够很好地恢复边界特征,但却带来了“梯子现象”。TV模型[1]为

是(A,B)的值域。

引理1[18]:设A∈Cm×n≠0,如果初始值V0∈Cn×m满足:

这里I是和A同维数的单位矩阵,则由

产生的序列{Vq}q∈N收敛到A+.

1.3 线性化Bregman迭代法

Osher等将优化的经典算法用于图像恢复TV模型的求解中,得到了Bregman迭代正则化方法、线性化Bregman迭代法和分裂Bregman迭代法,并将其应用于公式(4)中的模型。因为l1-范数的非光滑性,导致求解上较为困难。但在实际算法中,引入了软阈值算子的线性化Bregman算法就很好地解决了这个问题。模型(4)对应的线性化Bregman方法的迭代格式[8]为

与之相对应的带有软阈值算子的迭代算法[9]为

其中u0=v0=0,且软阈值算子定义为

考虑到A的性质,约束条件Au=f很难被满足,就需要利用其最小二乘解。于是,文献[8]中提出了有关A是行满秩情况下的式(11)等价AT算法:

很显然,式(14)是满足约束条件ATAu=ATf,即为Au=f的最小二乘解。同时考虑到方程条件数对计算的影响,在A是行满秩情况下等价的A+算法[8]

的唯一解。因为(AAT)-21是可逆的,则式(16)等价于式(10),且当μ→∞时,式(15)收敛于式(4)的极小l2-范数解,而对于A不仅局限于行满秩为任意矩阵时,文献[19]将其推广为A-算法。从计算的角度,可以看到式(15)既能够得到合适的最小二乘解,也充分考虑方程条件数的作用,使得计算稳定性大大提高；但另一方面,由于A+的存在也使得计算量加大,如果将其取得平衡,使计算量不增加(甚至降低计算量)的情况下能很清楚地将信号恢复,则是要进一步探讨的问题。在下面的讨论中,只考虑被推广到A为任意矩阵时的A+算法式(15)。

2 新算法的提出

A为任意矩阵时的A+算法式(15),在每一步的迭代计算都是矩阵向量乘法运算,但是A+的计算却是占了绝大部分的工作量。结合引理1的迭代思想,可以得到:很明显,这是个内外层迭代的算法,仅仅是迭代求解A+,理论上显示出在精度和速度上并没有明显的优势。通过结合以往混乱迭代方法的思想,将内外层循环参数结合,提出了下面的新的混乱迭代法:

从式(19)、式(20)可知,式(17)是充分考虑了迭代求解广义逆和利用更多步的细节信息来恢复信号,同时计算量仍能保持仅有矩阵向量乘积的运算。

3 数值试验

细节图片的试验(图1)是在Intel(R)Core (TM)2 Duo CPU T8100@2.10GHz 2.10GHz 1.5GB的机器上进行的,而整体图片(图2)是在Intel(R)Core(TM)2 Quad CPU Q9500@2.83GHz 2.83GHz 2.0GB的环境下进行的,MATLAB7.1。算法选取相同的初始值:计算过程中,除了列出相对误差量级相同情况下的计算时间对比之外,还给出了信噪比,便于更直观地比较算法的恢复效果。信噪比(RSN)采用计算公式如下:

由图1可以看出,三种方法恢复的结果为A+和Chaotic效果较好。图中能看出新的混乱迭代法能够清楚的恢复图片的细节信息,纹理特征保留较好,其去模糊的效果接近A+恢复的效果,特别是在稀疏纹理部分及细节较多部分的恢复效果更为明显。同时,在时间上新的混乱迭代法和AT线性化算法的计算时间处于相同量级,远远快于A+线性化算法(表1)。也就是说,新的混乱迭代算法的优势在于平衡了其他两种方法的优势。另外,从信噪比的对比值也可以看出,新的混乱迭代方法具有很好的图像恢复能力,具有一定的实用价值。

图1 图像去模糊效果(细节)Fig.1 Deblurring results of images(detail)

图2 图像去模糊效果(整体)Fig.2 Deblurring results of images(entirety)

由图2可以看出,新的混乱迭代法的恢复效果是令人满意的,特别是在模糊程度大的情况下,其细节恢复效果更佳。而此时的A+方法没有列出恢复效果图,是因为在同样的运行软硬件条件下,其工作量之大已经难以负荷。很显然,在计算效率上A+方法和其他两种方法不是在一个量级上的,在存储空间和计算时间上的要求相对另外两种方法苛刻很多。综上分析,混乱迭代新算法在整体图片的去模糊过程中,其恢复效果和计算代价的性价比是最高的,在很多应用领域(雷达成像后的具体定位等)都需要快速的识别具体图片的细节目标(尤其在图片的数据非常之大,例如遥感图片压缩后图片数据存储的规模仍然很大),这时混乱迭代算法就是实际应用的最佳选择。

表1 计算时间和信噪比的对比Table 1 Comparison of computing time and signal-to-noise ratio

4 结束语

提出的基于线性化Bregman迭代方法和广义逆迭代技术的新算法,对图像去模糊问题是非常有效的。特别是在图像模糊程度大且细节特征恢复困难的情况下,更是具有稳定快速的性质,其优势是十分明显的。而在计算耗时和工作量上面不仅保留了线性化Bregman迭代法的全部优点,同时还大大提高了计算效率。特别适用于大规模的快速计算,例如机载、舰载图像要求快速恢复等等。从理论分析可知,该方法是更多的考虑数据信息细节丢失的影响,

进一步说明了该方法是在本质上增强了图像的恢复效果。此外,还可以结合“剔除”技术来提高混乱迭代法的效率,或者考虑A+规模和工作量的因素而采用并行技术来得到更好的算法,将是下一步需要努力的目标。

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

[2] VOGEL C R.Computational methods for inverse problems[M].SIAM Frontiers in Applied Mathematics Series,2002:59-82.

[3] 刘继军.不适定问题的正则化方法及应用[M].北京:科学出版社,2008:21-57.

[4] 王大凯,侯榆青,彭进业.图像处理的偏微分方程方法[M].北京:科学出版社,2008:110-141.

[5] 张亶,陈刚.基于偏微分方程的图像处理[M].北京:高等教育出版社,2004:40-59.

[6] CHAN T F,GOLUB G H,MULET P.A nonlinear primal-dual method for total variation-based image restoration[J].SIAM J Sci Comput,1999,20:1964-1977.

[7] ZHU M.Fast Numerical algorithms for total variation based image restoration[D].Los Angeles:University of California,Los Angeles,2008:15-50.

[8] YIN W,OSHER S,DONALD G,et al.Bregman iterative algorithms for l1-minimization with applications to compressed sensing[J].SIAM Journal of Imaging Science,2008(1):143-168.

[9] CAI J,OSHER S,SHEN Z.Linearized Bregman iterations for compressed sensing[J].Mathematics of Computation,2009,78(267):1515-1536.

[10] TSAIG Y,DONOHO D L.Extensions of compresssed sensing[J].Signal Processing,2005,86:533-548.

[11] CAI J,OSHER S,SHEN Z.Linear Bregman iterations for compressed sensing,UCLA-CAM-Report 2008-06 [R/OL].[2010-03-10].

[12] OSHER S,BURGER M,GOLDFARB D,et al.An iterative regularization method for total variation-based image restoration[J].SIAM Multiscale Model Simul, 2005,4:460-489.

[13] OSHER S,MAO Y,DONG B,et al.Fast linearized Bregman iteration for compressed sensing and sparse denoising,UCLA-CAM-Report2008-37[R/OL]. [2010-03-20].http://www.math.ucla.edu/applied/ cam/index.shtml.

[14] YANG Y,MÖLLER M,OSHER S.A dual split Bregman method for fast minimization,UCLA-CAM-Report 2011-57[R/OL].[2012-01-09].http://www.math. ucla.edu/applied/cam/index.shtml.

[15] BENNING M,BRUNE C,BURGER M,et al.Higerorder TV methods-enhancement via Bregman iteration, UCLA-CAM-Report 2012-04[R/OL].[2012-03-01]. http://www.math.ucla.edu/applied/cam/index.shtml.

[16] YIN W,OSHER S.Error forgetting of Bregman iteration,UCLA-CAM-Report 2012-08[R/OL].[2012-03-18].http://www.math.ucla.edu/applied/cam/index. shtml.

[17] WANG G,WEI Y,QIAO S.Generalized inverses:theory and computations[M].Beijing:Science Press, 2004:16-37.

[18] 王松桂,杨振海.广义逆矩阵及其应用[M].北京:北京工业大学出版社,1996:1-5,202-205.

[19] 张慧,成礼智.A-线性Bregman迭代算法[J].计算数学,2010,32:97-104.

ZHANG Hui,CHENG Li-zhi.A-linearized Bregman iteration algorithm[J].Mathmatica Numerica Sinica, 2010,32:97-104.

(编辑 修荣荣)

A new algorithm based on linearized Bregman iteration for image deblurring

QIAO Tian-tian1,2,WANG Ji-chao1,LI Wei-guo1,WU Bo-ying2
(1.College of Science in China University of Petroleum,Qingdao 266580,China；
2.Department of Mathematics,Harbin Institute of Technology,Harbin 150001,China)

A new chaotic iteration for image deblurring was proposed.The algorithm was obtained based on A+linearized Bregman iteration with soft thresholding operator,and combined with generalized inverse iterative formula.Taking full consideration of the effective use of detail information,the algorithm can compensate for the loss of image detail features which is filtered to deblur in each iteration,and achieve effectively filtering.At the same time,a balance between computation time and the recovery effect is considered.The numerical experiments furtherly show that the method can improve computation efficiency and image recovery effect,especially the recovery of the detail features and sparse texture.

linearized Bregman iteration；image deblurring；chaotic iteration；generalized inverse

TN 911

A

1673-5005(2013)02-0176-05

10.3969/j.issn.1673-5005.2013.02.029

2012-06-20

国家海洋局海洋遥测工程技术研究中心创新青年基金；国家自然科学基金( 60971132； 11126085；61101208)

乔田田(1983-),女,讲师,博士研究生,研究方向为图像处理、数值计算。E-mail:qtthsnxf@126.com。