基于结构字典的图像修复算法

刘春荣

(北京工业大学计算机学院，北京 100124)

0 引言

2003年，Elad等人最早提出了基于图像签名字典[1](Image-Signature-Dictionary，ISD)的稀疏冗余表示模型[2-3]。ISD字典又名结构字典，与传统的字典学习模型相比，这种新颖的字典结构具有尺度灵活特性[4]、占用更少的内存以及计算能力的需求更低等优势。

2011年，Julien Mairal等人在基于图像签名字典的基础上又提出了基于缩略图的稀疏表示模型[5]，结构字典可以从缩略图中获得，该模型具有平移不变特性[6-7]、尺度灵活性、占用内存少等优点。目前，结构字典已经应用在图像处理和机器的很多领域，本文研究基于结构字典的图像修复算法。

图像修复[8]是对图像中破损区域进行信息填充，从而减少图像破损所带来的信息损失。图像修复的目的是采用最适合的方法将受损图像修复到尽可能接近原始图像的状态。图像修复的对象包括受污染的图像、带有文字的图像、去除不想要的目标等。

图像修复技术主要包括3类:基于纹理的图像修复技术[9-10]、基于偏微分方程(Partial Differential E-quation，PDE)[11-12]的图像修复技术和基于稀疏表示的图像修复技术[13]。基于纹理的图像修复技术的主要方法以基于样本的图像修复技术为代表，该算法的核心思想是以未受损图像为样本，在其中寻找与丢失像素或丢失模块最匹配的修复模型并对受损区域进行填充，从而实现对图像的修复。基于偏微分方程的图像修复技术的核心思想是利用待修复区域的边缘信息从区域边界向图像内部进行各向异性扩散，从而实现对图像的修复。

基于纹理的图像修复技术和基于偏微分方程的图像修复技术存在的问题是需要依赖图像的具体结构来制定相应的图像修复算法，随着稀疏表示理论的成熟，利用信号的稀疏性来对图像进行修复得到广泛应用。

基于稀疏表示的图像修复方法的代表为Elad[13]等人提出的KSVD算法和局部MCA相结合的方法，可以实现对图像的破损区域进行修复，首先利用MCA将图像分解成卡通和纹理部分，接着利用KSVD算法分别对卡通图像和纹理图像训练各自的字典，然后利用训练得到的字典对图像进行修复。该方法具有自适应性并且修复效果好等优点。

本文在基于稀疏表示的图像修复技术的基础上，提出基于结构字典的图像修复技术。

1 算法的提出

本文提出基于结构字典的图像修复算法，具体算法可以分为以下2个步骤:

1)首先从原始图像中提取所有重叠块并采用基于结构字典图像训练算法进行字典训练。其中稀疏编码阶段采用LASSO算法，字典更新阶段采用投影梯度下降算法。

2)字典训练完成后，针对去除丢失像素块的图像块进行稀疏编码，采用基于误差控制的OMP算法，最后通过把重构的图像块加权平均后放在恢复图像的对应位置。

对于给定的信号X∈Rm×n，可以建立结构字典学习算法:

其中字典 D∈Rm×p，D=[d1，…，dp]为 p 个字典原子的集合，稀疏表示系数 A∈Rp×n，X=[x1，…，xn]为 n个训练信号的集合，xi，j指 X的第i行 j列的元素，X的F范数为n个稀疏表示系数的集合，另外定义向量x∈Rm上的lq范数为，xj指 x 的第 j个坐标，q＞1。对于大小为的结构字典，即向量形式 E∈RM，线性操作算子可以提取结构字典中所有重叠的块并把其重新排列成字典D的列，其中指字典D的原子个数。φ(E)可以看成从结构字典E到传统字典D的映射算子，引入lm(φ)可以实现φ(E)到D的快速投影，φ是可逆的，φ和φ*是一对逆操作。

对于式(1)的求解，根据结构字典E到传统字典D的映射，可以将其转化为传统字典的求解，即:

式(2)的求解包括字典更新和稀疏编码2个阶段。

2 算法的求解

2.1 结构字典与传统字典的映射

假定 Ri∈{0，1}m×M，可以从结构字典 E 中提取第i图像块，R=[R1T，…，RpT]T，φ(E)=[R1E，…，RpE]表示摘要图E到传统字典D的映射算子，φ*(D)表示字典 D∈Rm×p到摘要图 E∈RM的映射算子

因地制宜，宜林植树，选择当地适宜的树种种植。从提高生态效应、景观效果、经济效益出发，成片造林力度明显提高。造林建设以发展经济林、生态景观林等林地为主。采用多样化的以林养林方式，以发展苗木养林，经济果林养林，采取林苗结合、林禽结合、林果结合等方式提高林地产出和经济效益。

进一步推导φ*(D)=(RTR)－1RTvec(D)，因此vec(φ(E))=RE，vec(lmφ)=lmR，vec(φ(φ*(D)))=R(RTR)－1RTvec(D)，根据上面的推导可以得到以下3个特性:

1)φ*是φ的逆变换:φ*◦φ=Id;

2)φ*是φ◦φ*在lmφ上的正交投影;

3)∏lmp=φ◦φ*。

通过建立结构字典E到传统字典D的映射，可以将其转化为传统字典的求解。

2.2 稀疏编码阶段

固定字典D更新稀疏表示系数A。通过固定字典D，对于稀疏表示矩阵A的更新可以看成是解关于αi的n个独立的优化问题。对于每一个优化问题又可以看成是解加权l1优化问题。对矩阵A的列αi的更新，定义矩阵 Γ =diag[‖d1‖2，…，‖dp‖2]及D'=DΓ－1，如果 Γ 是非奇异的，则有，则有式(3)和式(4):

接下来证明式(3)和式(4)的等价转换:

定义 D'=DΓ－1，α'=Γα，则有:

通过以上推导，可以将有约束的算法求解问题转化为无约束的算法求解问题，从而可以采用常用的稀疏编码算法求解。可以使用LASSO[14－15]算法进行求解。

2.3 字典更新阶段

对于字典的更新可以采用投影梯度下降算法[16]。通过固定稀疏表示系数A更新字典D，得到目标函数:

式(7)中A是固定的，αj是A的第j列。函数f关于D是可微的，因此可以很容易地计算得到梯度:

3 实验结果与分析

实验设置:如图1所示，测试图像为Lena图像(128×128)和Peppers图像(128×128)，选取步长ρ=0.28，块的大小为10×10，结构字典的尺寸为24×24，平衡参数λ=0.15，为了保证实验的公平性，选择KSVD算法的字典原子数为256，另外，稀疏度为3。种算法都能够对图像进行同样稀疏表示的情况下，结构字典占用的内存小，因此具有较低的空间复杂度。

图1 测试图像

图2 KSVD算法对Peppers图像修复结果

实验过程与分析:分别测试Peppers图像在像素缺失率为20%的情况下采用KSVD算法[3]和本文提出的算法对图像进行修复，如图2和图3，通过对实验结果进行分析，2者都能比较理想地对图像进行修复。仔细观察图像的细节，基于结构字典的图像修复存在修复不彻底的现象，但是该算法计算简单，先是对图像样本训练得到字典然后对缺失的图像进行修复，对图像修复的效率较高。基于KSVD算法对字典原子的更新是逐列进行更新，基于结构字典的图像修复算法是基于整个字典进行更新，更新速度较快，且2

图3 结构字典算法对Peppers图像修复结果

4 结束语

本文在基于冗余字典的稀疏表示方法的基础上，结合结构字典的思想，围绕基于结构字典的稀疏表示方法展开研究并将其成功应用于图像修复任务中。结构字典克服了传统的字典原子之间结构不相关性问题，充分利用了原子之间的结构特性，而且结构字典具有平移不变性、尺度灵活性、占用内存少的特点。最后通过实验证明基于结构字典的稀疏表示算法能够训练字典更紧致地对图像进行表示，尤其在空间复杂度方面具有较大的优势。未来进一步的工作将主要着眼于基于结构字典的图像分解技术在图像修复问题上的研究。

[1] Aharon M，Elad M.Sparse and redundant modeling of image content using an image-signature-dictionary[J].SIAM Journal on Imaging Sciences，2008，1(3):228-247.

[2] Aharon M，Elad M，Bruckstein A.K-SVD:An algorithm for designing overcomplete dictionaries for sparse representation[J].IEEE Transactions on Signal Processing，2006，54(11):4311-4322.

[3] Elad M.Sparse and Redundant Representations:From The-ory to Applications in Signal and Image Processing[M].Springer，2010.

[4] Mairal J，Sapiro G，Elad M.Learning multiscale sparse representations for image and video restoration[J].SIAM Journal on Multiscale Modeling and Simulation，2008，7(1):214-241.

[5] Benoit L，Mairal J，Bach F，et al.Sparse image representation with epitomes[C]//Proceedings of the 2011 IEEE Conference on Computer Vision and Pattern Recognition.2011:2913-2920.

[6] Mailhe B，Lesage S，Gribonval R，et al.Shift-invariant dictionary learning for sparse representations:Extending KSVD[C]//Proceedings of the 16th European Signal Processing Conference.2008.

[7] Thiagarajan J J，Ramamurthy K N，Spanias A.Shift-invariant sparse representation of images using learned dictionaries[C]//Proceedings of the 2008 IEEE Workshop on Machine Learning for Signal Processing.2008:145-150.

[8] Bertalmio M，Sapiro G，Caselles V，et al.Image inpainting[C]//Proceedings of the 27th Annual Conference on Computer Graphics and Interactive Techniques.2000:417-424.

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

[10] Criminisi A，Perez P，Toyama K.Object removal by exemplar-based inpainting[C]//Proceedings of the 2003 IEEE Computer Society Conference on Computer Vision and Pattern Recognition.2003，2:721-728.

[11] Tschumperle D，Deriche R.Vector-valued image regularization with PDEs:A common framework for different applications[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2005，27(4):506-517.

[12] Aubert G，Kornprobst P.Mathematical Problems in Image Processing:Partial Differential Equations and the Calculus of Variations[M].Springer，2006.

[13] Elad M，Starck J L，Querre P，et al.Simultaneous cartoon and texture image inpainting using morphological component analysis(MCA)[J].Applied and Computational Harmonic Analysis，2005，19(3):340-358.

[14] Efron B，Hastie T，Johnstone I，et al.Least angle regression[J].The Annals of Statistics，2004，32(2):407-499.

[15] Tibshirani R.Regression shrinkage and selection via the lasso[J].Journal of the Royal Statistical Society，Series B(Methodological)，1996，58(1):267-288.

[16] Nesterov Y.Gradient Methods for Minimizing Composite Objective Function[DB/OL].http://www.optimizationonline.org/DB_HTML/2007/09/1784.html，2007-09-20.

[17] Bertsekas D P.Nonlinear Programming(2nd Edition)[M].Athena Scientific，1999.