SL0分类稀疏表示的图像修复算法

屠雅丽，唐向宏，张　东，蔡倩，任玉升

(1.杭州电子科技大学通信工程学院，浙江 杭州 310018；2.浙江水利水电学院电气工程学院，浙江 杭州 310018)



SL0分类稀疏表示的图像修复算法

屠雅丽1，唐向宏1，张东1，蔡倩1，任玉升2

(1.杭州电子科技大学通信工程学院，浙江 杭州 310018；2.浙江水利水电学院电气工程学院，浙江 杭州 310018)

将SL0算法应用于图像修复.在传统的SL0算法基础上，采用近似双曲正切函数去近似l0范数，利用共轭梯度法求解该函数，实现高精度的重构，提出一种利用SL0算法的分类稀疏表示图像修复算法.算法首先将图像分块，并根据图像块的梯度信息和局部方差依次对图像块进行分类；然后分别对每一类图像块样本用K-SVD字典训练得到相对应的过完备字典；最后利用改进的SL0算法进行图像修复.仿真实验结果表明，算法对图像修复后的质量有较大的提高，更符合人眼视觉效应.

SL0；K-SVD；梯度；局部方差；分类训练

0　引　言

数字图像修复是根据破损图像中的已知信息，利用算法对图像破损区域进行修复的过程.经典的修复算法有基于偏微分方程的图像修复算法[1]和基于样本块的图像修复算法[2].除此之外，基于稀疏表示理论的数字图像修复成为近年来研究的热点.文献[3]将待修复图像中的所有已知图像块作为字典，对待修复的图像块进行稀疏重构，但该算法字典的自适应性不足.为此，文献[4]采用聚类和分类相结合的方式对图像块进行特征分类，针对不同特征的样本图像块进行字典训练，提高了字典的自适应能力.

重构算法是基于稀疏表示的图像修复中至关重要的一环，由于正交匹配追踪(Orthogonal Matching Pursuit，OMP)算法[5]的原理简单且十分易于实现，因此成为主流的重构算法，并广泛应用于基于稀疏表示的图像修复算法中.但该算法在重构时往往需要预估信号的稀疏度，无论稀疏度估计过小或者过大都不能达到较好的重构效果.而平滑l0范数 ( Smoothedl0Norm，SL0)[6]则可以避免该问题，不需要事先估计信号的稀疏度.SL0算法是要寻求一个连续函数去逼近l0范数，并求解该函数的最小值.它是一种近似l0范数的稀疏重构算法，相比于OMP算法具有高重构率、不用预估信号稀疏度等优点，可以很好地应用于基于稀疏表示的图像修复中.因此，本文在传统的SL0算法的基础上，采用近似双曲正切函数去近似l0范数，并采用共轭梯度法求解该函数最小值以减少锯齿现象，从而实现高精度的重构.

1　稀疏表示的图像修复模型

假设信号x∈RN，其可用一组基线性表示，稀疏问题即找到一个最佳稀疏表示为[7]：

(1)

(2)

式中，ε≥0表示一定的误差容限.通过正则化方法和参数λ来平衡稀疏性和稀疏误差，得到稀疏问题的表达式为：

(3)

由于式(3)为NP难问题，计算量非常大，无法得到最优解，因此需要一个有效的编码算法来求解上述问题.

2　算法原理及实现

本算法的基本思路是：首先将图像分块，根据图像块的梯度信息和局部方差依次对图像块进行分类；然后分别对每一类图像块样本用K-SVD字典训练得到相对应的过完备字典；最后，实现SL0重构算法对图像的修复.

2.1图像块特征分类

为了增强学习字典的自适应能力，本文采用结合图像块梯度信息和局部方差的方法对图像进行特征分类.令图像中任意位置(x,y)的像素值为f(x,y)，其上下左右4个方向的梯度值分别为：

(4)

取这4个方向上的最大梯度值为该像素点的权值g(x,y)，将每个图像块(大小为n×n)内的每个像素进行梯度加权，其大小为：

(5)

设定一个阈值T，其中T为经验常数，一般取100.当uk

第k个图像块的局部方差为：

(6)

图1　图像分类结果

再根据K-SVD[8]算法，即可得到3种不同类别图像样本块所对应的自适应字典：不规则纹理字典Dt、平滑字典Ds和边缘结构字典De.

2.2SL0重构算法及其改进

重构算法在基于稀疏表示的图像修复中起着举足轻重的作用，重构效果的好坏直接影响图像修复的质量.SL0算法是近似l0范数的一种稀疏重构算法，其原理是寻找一个连续函数去近似l0范数，并采用一定的方式去逼近函数最优解，其数学模型如式(1)所示.

(7)

则

(8)

(9)

式中：σ表示高斯函数的标准差.但该连续函数的“陡峭性”不够明显，不能准确的逼近l0范数.因此本文利用下式的近似双曲正切函数作为近似估计l0范数的函数.

(10)

最速下降法的搜索方向为函数的负梯度方向，越接近目标值，步长越小，前进越慢，在求解过程中存在锯齿效应，使得l0范数估计的准确性降低.而共轭梯度法的搜索方向为负梯度方向与上一次迭代的搜索方向的线性组合，可以解决最速下降法带来的锯齿效应.两类方法迭代过程如图3所示.

图2　高斯函数和近似双曲正切函数比较

图3　最速下降法和共轭梯度法迭代过程示意图

利用SL0算法的分类稀疏表示图像修复流程如图4所示，其算法实现步骤如下：

1) 令初始值分别为X=DT(DDT)-1Y,σ1=2max(X)，k=1(k用于计算σk大小的循环变量)；

图4　本文算法流程图

(2)X←X+μdn，其中步长因子μ=1.5；

(4)n=n+1,j=j+1,如果j

3　实验结果及分析

为了验证所使用方法的性能，在计算机上对小面积和大面积破损区域修复进行了仿真实验，并将改进SL0算法的图像修复效果与传统SL0算法的图像修复效果、文献[3]、文献[4]的图像修复效果进行了比较分析.在对图像修复效果评价时，除了采用主观评价外，同时也采用峰值信噪比(PSNR)进行客观评价[4].

仿真实验在MATLAB环境中进行，其中图像块的大小取为7×7.在仿真实验中，利用BABOON、BARB、LENA等标准图像进行破损修复处理，下面给出部分仿真结果.

从图5，图6和图7可以看出，4种图像修复算法对平滑区域的修复效果均十分理想；前3种算法在对不规则纹理区域和边缘区域修复后产生了不同程度的模糊以及延伸现象，修复效果不自然，而本文算法在这两种区域的修复效果符合人眼视觉规律.

如图7所示，对LENA图像修复后，在其帽顶、眉毛和嘴角等部分(画黑圈部分)，4种算法在修复时均出现一定程度的不自然延伸或模糊现象，这些部分属于“弧形”边缘或纹理复杂区域，本文算法对这部分区域的修复不够理想.

图5　BABOON修复效果图

图6　BARB图修复效果图

图7　LENA修复效果图

表1给出了仿真实验中4种算法的PSNR值和耗时情况.从表1中可以看出，本文算法在修复时间上与传统SL0修复算法相比相差不大，却是文献[3]和文献[4]算法的2～3倍，这是由于文献[3]和文献[4]均采用OMP算法对图像进行修复，而OMP算法简单复杂度较低，使得修复时间较短；本文算法的PSNR 值相比传统SL0算法均提高1 dB左右，而相比文献[3]和文献[4]要提高1.5～2 dB左右，即本文算法在修复质量上有较大的提升.

表1　4种算法PSNR与消耗时长的比较

4　结束语

本文提出一种利用SL0分类稀疏表示的图像修复算法.仿真实验结果表明，本文方法综合性能较好，修复后的图像质量有较大的提升，可以有效修复图像结构边缘、不规则纹理和平滑区域的图像信息.但SL0算法在修复时耗时比较长对复杂纹理以及“弧形”边缘破损区域的修复不够理想，有待改进.

[1]BERTALMIO M,SAPIRO G, CASELLES V,et al.Image inpainting[J].Proceedings of Annual Conference on Computer Graphics & Interactive Techniques,2002,4(9):417-424.

[2]CRIMINISI A,PEREZ P,TOYAMA K.Object Removal by Exemplar-Based Inpainting[C]//IEEE Computer Society Conference on Computer Vision and Pattern Recognition,2003:721-728.

[3]XU Z,SUN J.Image inpainting by patch propagation using patch sparsity[J].IEEE Transactions on Image Processing,2010,19(5):1153-1165.

[4]康佳伦.基于FMM和稀疏表示图像修复算法的研究[D].杭州:杭州电子科技大学,2013.

[5]TROPP J A,GILBERT A C.Signal Recovery from partial information via orthogonal matching pursuit[J].IEEE Transactions on Information Theory,2007,53(12):4655-4665.

[6]MOHIMANI H,BABAIE-ZADEH M,JUTTEN C.A fast approach for overcomplete sparse decomposition based on smoothed l0norm[J].IEEE Transactions on Signal Processing, 2009,57(1):289-301.

[7]DONOHO D L,HUO X.Uncertainty principles and ideal atomic decomposition[J].IEEE Transactions on Information Theory,2001,47(7):2845-2862.

[8]AHARON M,ELAD M,BRUCKSTEIN A.K-SVD:An Algorithm for Designing Over-complete Dictionaries for Sparse Representation[J].IEEE Transaction on Signal Processing,2006,54(11):4311-4322.

Classified Sparse Representation of Image Inpainting by SL0 Algorithm

TU Yali1, TANG Xianghong1, ZHANG Dong1, CAI Qian1, REN Yusheng2

(1.SchoolofCommunicationEngineering,HangzhouDianziUniversity,HangzhouZhejiang310018,China;2.SchoolofElectricalEngineering,ZhejiangUniversityofWaterResourcesandElectricPower,HangzhouZhejiang310018,China)

This paper proposes a novel image inpainting algorithm by SL0 algorithm. Based on traditional SL0 algorithm, it takes use of approximate hyperbolic tangent function to approachl0norm and uses conjugate gradient to solve this function, which are helpful to improve the reconstructive accuracy. The proposed algorithm firstly divides the damaged image into blocks and classifies them in turn through the gradient information and local variance of image block; then trains the each type image block samples with K-SVD to get the corresponding over complete dictionary; finally, utilizes the modified SL0 algorithm to image inpainting. The experiment results show that the proposed algorithm in image inpainting is greatly improved the image quality and the images are more in accordance with visual effect.

SL0; K-SVD; gradient; local variance; classified train

10.13954/j.cnki.hdu.2016.01.007

2015-05-21

屠雅丽(1991-)，女，浙江宁波人，在读研究生，数字图像修复.通信作者：唐向宏教授，E-mail：tangxh@hdu.edu.cn.

TP391

A

1001-9146(2016)01-0032-05