基于平行坐标下降法的图像修复

江 平， 张 锦

(合肥工业大学数学学院，安徽 合肥 230009)

基于平行坐标下降法的图像修复

江 平， 张 锦

(合肥工业大学数学学院，安徽 合肥 230009)

以压缩传感和稀疏表示为理论依据，提出了一种基于平行坐标下降法的图像修复模型。该模型用小波变换作为图像的稀疏表示，以稀疏性作为正则化项；同时基于松弛阈值来标记函数实现全局优化，并采用该模型算法得到全局最优解。从峰值信噪比、收敛速度和视觉效果等3个方面验证了算法的有效性。结果表明新的模型无论是在客观还是视觉主观上都有更好的效果，同时算法具有更快的收敛速度。

稀疏表示；图像修复；平行坐标下降法；阈值

数字图像修复是由Bertalmio等[1]于2000年提出，指利用图像中已有的信息，根据一定的算法或规则对破损区域进行修复或者目标物体的去除，以达到良好的视觉效果。近年来，数字图像修复技术得到快速发展，并广泛应用于文物的保护、多余物的剔除、影视特技的制作、图像压缩、视频图像差错隐藏等领域，已成为数字图像处理领域的一个重要分支。

现有的图像修复可分为基于偏微分方程(partial differential equation，PDE)的修复算法、基于样本块的纹理合成修复算法、混合方法以及基于稀疏表示的方法。文献[2-4]采用非线性偏微分方程的方法，将待修复区域周围的已知信息通过逐渐扩散来修复图像中的待修复区域，该类算法考虑的是图像的几何结构信息，本质上都是一种扩散过程，但是修复大面积区域时效果明显变差；文献[5]提出的Criminisi算法，以基于块的纹理合成技术来修复破损区域，首先待修复区域分块，然后按照优先级公式计算出修补顺序，最后在图片中寻找与待修复区域块最相近的块将其填补，以达到修复的目的，对大面积破损图像的修复效果较好；文献[6-8]将图像分解为几何结构分量与纹理分量，分别对这两个分量进行修补和合成，在一定程度上改善了图像的修复效果，但是仍不可避免的存在结构模糊或块效应等缺点；文献[9-11]是基于稀疏重构和迭代去噪技术在图像修复上的应用，在迭代过程中使用经典的去噪理论，估计图像修复区域的最优解，该方法理论上可获得局部最优解，具有一定的鲁棒性；Elad等[7]以压缩理论为基础，采用形态成分分析(morphological component analysis，MCA)将图像分解为结构和纹理两部分，通过分别重构图像的结构和纹理部分来实现修复，最后将两部分重建结果相加得到修复图像。

近年来，迭代收缩方法正在逐步建立，对于处理最优化问题非常有效，它扩展了信号去噪的经典的 Donoho-Johnston[12]收缩方法，并且 Elad等[13]证明了这个算法的收敛性，保证了这个算法的解对于凸面的整体最小化。在迭代收缩算法中分 离 代 理 函 数 算 法 (separableSurrogate functionals，SSF)和平行坐标下降法(paralle coordinate descent，PCD)彼此很接近，不同的是SSF算法中的有个常量c，PCD算法用了同样的方式但是用的是重要矩阵 (ATA)-1所提出的对角元素，因此，PCD算法的效果较好。本文把SSF算法和PCD算法分别用于图像修复，希望PCD算法对修复效果仍然较好。

鉴于稀疏理论在图像处理领域的优势，本文把稀疏表示、PCD算法与图像修复结合起来，使得修复的过程是一个迭代收缩的过程，每迭代一次进行一次线性收缩，直到缺失区域修复结果趋于稳定。

1 稀疏表示

设信号 x ∈Rn可由预定原子的线性组合表示，则x的稀疏表示问题为[7]：

2 基于PCD的图像修复算法

图像修复是将图像中丢失的信息(像素)进行补全的过程。在有噪声的情况下，图像修复还伴随着噪声的去除。噪声情况下，原图像(信息完整图像)与观测图像(待修复图像)关系描述如下[14]：

假设已经知道第k次迭代值 zk，想要更新其第j个值 zk(j)，保持其余的不变。因此，得到一个1- D的优化形式：

其中， aj表示A的第j列，Azk-ajzk(j )用当前的值来更新所有的系数，第j个值用z来代替。因为这是一个1-D优化问题，相对还是比较容易解决的。如设，对式(2)中的z求导得到：

进而可得：

类似这样的收缩过程，ρ (⋅)可以选择任意函数，本文取：

它的一阶导和二阶导分别为：

所以，ρ (⋅)是一个二阶可导且严格凸的函数，其有着类似平滑的功能。

上述的过程每次沿不同的方向更新一个系数，循环更新，直到得到满意解，称之为坐标下降法(coordinate descent algorithm，CD算法)。

由于CD算法更新缓慢，而且要用到字典的单个原子 aj，计算效率低下，所以Elad等[13]提出在已知当前值 zk的情况下，用上面的算法并行更新所有的系数，代替一次次的更新。

首先，使v(A,y,zj,j )，成一个向量形式，一次更新所有系数，即：

ATA的对角阵的提取是由矩阵A的列向量的标准基所组成的。然而 CD算法每个方向都保证了下降，它的非负线性组合也是下降的，因此，考虑它的一个线性搜索：

μ沿线性搜索：

这里 hk是可计算的向量，得到计算μ的方程[15]：

这种方法可以解决式(1)的问题，每一次迭代，同时也是一次收缩。定义第k次迭代值为通过计算λ⋅diag-1{ATA}⋅1和沿线性下降方向来更新[16]。

3 算法步骤

综上分析，用PCD算法求解稀疏化的图像修复模型算法流程如下：

步骤1. 读入一幅待修复图像y，提取掩膜信息M；

步骤2. 利用小波变换得到冗余字典，并对图像进行稀疏化；

步骤3. 初始化迭代次数 k=1， zk=0线性收缩系数 μ= 0.1，阈值 threshold= 0.1，参数 s=1、λ= 0.1及算法终止参数ε；

步骤4. 通过对图像的小波变换稀疏化阈值threshold；

步骤5. 计算 v(A,y,zj,j )，下降方向 hk，系数μ；

步骤6. 代入 zk+1= zk+μhk中，计算得到 zk+1；

步骤7. 阈值松弛threshold=threshold×0 .7；

步骤 9. 输出，将会得到最优系数 zopt，代入xopt=Azopt，即可得到修复后的图像。

4 数值实验与分析

本文实验用Matlab 2009 b作为工具，在Intel酷睿5处理器(2.67 GHz)，4 G内存的PC机上实现的。

为了验证算法的有效性，以Lena、Peppers 两幅图为例进行性能测试。引入SSF算法，增加线性搜索的SSF算法[13](记为：SSF-LS算法)和固定μ的PCD算法(μ=0.5)与本文算法进行比较，从峰值信噪比(peakSignal to noise ratio，PSNR)、迭代次数和视觉效果3个方面进行。

图 1为修复刮痕损坏的 Lena图像效果图，图1(d)~(f)从视觉效果上看相差无几，但是达到算法的迭代终止条件图1(f)只需迭代23次，而图1(d)需迭代25次，图1(e)需迭代26次，而且图1(f)的PSNR高于其他算法，说明线性搜索的PCD算法收敛速度较快，效果较好。具体数据见表1。

图1 Lena修复效果图

表1 Lena图像各修复算法迭代次数和PSNR比较

图2 peppers修复效果图

图2为去除Peppers图像中的英文字母，从表2中可以看出，虽然SSF算法和PCD算法达到终止条件时的迭代次数一样，但是PCD算法修复得到的图像比SSF-LS算法修复得到的图像PSNR高出0.31 dB，说明PCD算法的修复效果较好。具体数据见表2。

表2 pepperes图像各修复算法迭代次数和PSNR比较

5 结 束 语

本文提出基于PCD算法来修复图像，该算法用小波变换作为图像的稀疏表示，通过阈值收缩确定下降方向，用线性搜索的方法来确定每次下降的步长，然后进行迭代求解。采用不同的图像进行实验验证，结果表明本文算法能够较好地修复图像，获得较好的视觉效果。本文算法对小缺损图像进行修复时能取得较好的修复效果，但是对修复区域较大的图像效果较差，需要继续研究。

[1] BertalmioM,Sapiro G, Caselles V, et al. Image inpainting [C]//Proceedings ofSIGGRAPH. New York, USA, 2000:417-424.

[2] Chan T F,Shen Jianhong.MathematicalModels for local non-texture inpainting [J].SIAM Journal on AppliedMathematics, 2002, 62(3): 1019-1043.

[3] Rudin L I, OsherS, Faterni E. Nonlinear total variation based noise removal algorithms [J]. Physica D Nonlinear Phenomena, 1992, 60: 259-268.

[4] Chan T F,Shen Jianhong. Non-texture inpainting by curvature-driven diffusions (CDD) [J]. Journal of Visual Communication and Image Representation, 2001, 12(4):436-449.

[5] Criminisi A, Perez P, Toyam K. Region filling and object removal by exemplar-based image inpainting [J]. IEEE Transactions on Image Processing, 2004, 13(9): 1200-1212.

[6] BertalmioM, Vese L,Sapiro G, et al.SimultaneousStructure and texture image inpainting [J]. IEEE Transactions on Image Processing, 2003, 12(8): 882-889.

[7] EladM,Starck J-L, Querre P, et al.Simultaneous cartoon and texture image inpainting usingMorphological component analysis (MCA) [J]. Applied and Computational Harmonic Analysis, 2005, 19(3): 340-358.

[8] 黄江林, 刘 红, 陶少杰. 一种改进的基于K-SVD字典的图像修复算法[J]. 安徽大学学报：自然科学版, 2013, 37(3): 69-74.

[9] Guleryuz O G. Nonlinear approximation based image recovery using adaptiveSparse reconstructions and iterated denoising-part I: theory [J]. IEEE Transactions on Image Processing, 2006, 15(3): 539-554.

[10] FadiliM J,Starck J L,Murtagh F. Inpainting and zooming usingSparse representations [J]. The Computer Journal Advance Access, 2007, (6): 1-16.

[11]Mairal J, EladM,Sapiro G.Sparse representation for color image restoration [J]. IEEE Transactions on Image Processing, 2008, 17(1): 53-69.

[12] Donoho D L. De-noising bySoft thresholding [J]. IEEE Transactions on Information Theory, 1995,41(3): 613-627.

[13] EladM,Matalon B, ZibulevskyM. Coordinate andSubspace optimizationMethods for linear leastSquares with non-quadratic regularization [J]. Applied and Computational Harmonic Analysis, 2007, 23(3): 346-367.

[14] 邓承志, 刘娟娟, 汪胜前，等. 保留结构特征的稀疏性正则化图像修复[J]. 光学精密工程, 2013, 21(7): 1906-1913.

[15] Tropp J A, WrightS J. ComputationalMethods forSparseSolution of linear inverse problems [J]. Proceeding of the IEEE, 2010, 98(6): 948-958.

[16] EladM. WhySimpleShrinkage isStill relevant for redundant representations? [J]. IEEE Transactions on Information Theory, 2006, 52(12): 5559-5569.

Image Inpainting Based on Parallel Coordinate DescentMethod

Jiang Ping, Zhang Jin
(School ofMathematics, Hefei University of Technology, Hefei Anhui 230009, China)

Based on the compressedSensing andSparse representation theory, and on the parallel coordinate descent an image inpaintingModelMethod is proposed, which uses theMethod of wavelet transform for imageSparse representation, withSparse as the regularization term, and at theSame time, realizes global optimization based on the threshold of relaxation toMark function. The global optimalSolution can be obtained by using PCD. The proposed algorithm is verified from the peakSignal to noise ratio of convergenceSpeed and visual effect. The resultsShow that the newModel has better effect in both objective andSubjective, and at theSame time has faster convergenceSpeed.

Sparse representation; image inpainting; parallel coordinate descentMethod; threshold

TP 391

A

2095-302X(2015)02-0222-05

2014-10-08；定稿日期：2014-10-24

国家自然科学基金面上项目(11471093)；中央高校基本科研业务费专项资助项目(J2014HGXJ0077)

江 平(1972–)，女，安徽安庆人，副教授，博士。主要研究方向为CAGD、图像处理。E-mail：jiang_hfut@126.com