基于局部字典搜索和多原子匹配追踪的图像逼近算法*

黄亚飞,梁昔明,樊绍胜

(1.中南大学信息科学与工程学院，湖南 长沙 410083； 2.长沙理工大学智能电网运行与控制湖南省重点实验室，湖南 长沙 410114)

1 引言

以小波分析为基础，Mallat等[1]提出了信号在冗余字典中的稀疏表示和稀疏分解思想，此后该思想被推广到二维信号，并已应用于图像处理的许多方面，如图像去噪[2]、图像重建[3]、图像表示[4,5]、人脸识别[6]等。稀疏分解问题是一个NP-hard组合搜索问题，直接求解十分困难，现有方法分为三类：(1)贪婪算法，其特点是每次迭代选取一个最能匹配残差信号的原子，如匹配追踪MP(Matching Pursuit)算法[1];(2)松弛算法，其特点是将l0优化问题松弛为易求解的lp(p≥1)优化问题，如BP(Basis Pursuit)算法[7];(3)函数逼近法，其特点是利用构造的特殊函数序列来逼近l0范数，如SL0(Smoothed L0 Norm)算法[8]。上述方法的共同特点是计算量巨大，造成图像稀疏分解实际应用发展缓慢。

Gribonval等[9]对MP算法在理论上做出收敛证明，使其有了充分的理论依据，MP算法相对较低的计算复杂度使它成为稀疏分解方法中最常用的一种。为降低运算复杂度，MP的众多改进算法已被提出。快速傅里叶变换FFT(Fast Fourier Transform)的引入实现了内积的批量计算[10,11]，大大提高了稀疏分解速度。由于FFT实际上是复数运算，对于虚部为0的实信号来说，增加了不必要的计算开销。为此，基于快速哈特莱变换FHT(Fast Hartley Transform)的图像稀疏分解算法被提出[12]。以上算法由于每次迭代只搜索一个最佳原子，速度提升有限。M项追踪MTP(M-Term Pursuit)算法将冗余字典划分成若干非相干子字典，然后从子字典中一次并行选择多个原子，使稀疏分解速度得到极大提高[13]。AMMP(Approximate M-fold Matching Pursuit)算法基于原子间互相关信息的估计进行多原子选择，在损失微小精度的情况下大幅降低了稀疏分解运算复杂度[14]。然而，多原子选择算法采用全局字典搜索方式，仍浪费了很多运算时间。

本文首先介绍基于二维FHT(2D-FHT)的内积批量计算方法；然后分析MP算法相邻代核原子的排序规律，提出基于局部字典搜索和多原子匹配追踪LMMP(Local dictionary searching and Multi-atom Matching Pursuit)的图像逼近算法；接着对LMMP算法的收敛性和时间复杂度进行理论推导；最后通过实验对LMMP算法参数进行讨论，并与其他全局搜索算法作性能比较。理论分析和实验结果表明，相比其他算法，本文算法的运算速度有明显提升且逼近精度接近MP算法。

2 LMMP算法原理与实现

2.1 基于2D-FHT的内积批量计算

Φ(u,v)=Fe(u,v)Ge(u,v)+

Fo(u,-v)Go(u,-v)-

Fe(u,-v)Go(u,v)+Fo(u,v)Ge(u,-v)

(1)

(2)

2.2 局部字典搜索和多原子匹配追踪

其中,sup表示取上确界，Rt为当前残差图像。

对Rt作如下分解后进入第t+1代：

(3)

从图1可以看出，在400次的迭代中，位序为1的核原子(最佳原子由其平移得到)在前一代的位序有397次未超过50，余下3次都未超过150。用K值来衡量，则位序为1的核原子在前一代的位序均未超过数值0.2K。由图1还可看出，位序为100和200的核原子在前一代的位序绝大部分仍在100和200附近，表明核原子在MP算法相邻代中的位序基本稳定。对其他图像实验所得结果类似，从而间接验证了前面的推断。

Figure 1 Statistical results of Lena(256×256) for P(t-1,(t,k))图1 对Lena(256×256)实验统计的P(t-1,(t,k))情况

多原子匹配追踪以原子的互不相干性为前提[13,14]，如果一次局部字典搜索选择多个互不相干的普通原子，应不会对逼近质量造成较大影响，却能更多地节省图像稀疏分解时间，为此提出结合局部字典搜索的多原子匹配追踪方法。

(4)

(5)

(6)

与文献[14]中累加投影后更新残差一次的方式不同，式(6)是按下式逐原子依次更新残差Mt次。

(7)

(8)

2.3 LMMP算法步骤

3 LMMP算法性能分析

3.1 逼近误差分析

下面对LMMP算法的收敛性进行分析。为简明，暂不考虑迭代次数t，讨论ρ=1时迭代一次选择M个原子的逼近误差。

引理1设Η为有限Hilbert空间，f∈Η，令R1=f，GΛ是满足式(4)和式(5)的原子集，则∀gm∈GΛ(m=1,…,M)，有:

(9)

其中,Rm由式(7)得到。

(10)

|〈R2,g2〉|≥|〈R1,g2〉|-

(11)

|〈R3,g3〉|≥|〈R2,g3〉|-

按上述过程不断递推，可得式(9)。

□

定理1设f∈Η，则∀M>0，LMMP算法迭代一次选择M个原子的逼近误差为:

(12)

证明由引理1可知，GΛ中的原子gm满足:

于是∀M>0，迭代一次选择M个原子的逼近误差如式(12)。

□

(13)

3.2 时间复杂度分析

4 实验结果

为验证LMMP算法的有效性，采用Gabor多成份字典对多幅标准图像进行实验，分析LMMP算法参数对算法性能的影响，并与FSMP算法[10]、MTP算法[13]、AMMP算法[14]的逼近性能和运算速度作比较。

对五幅标准测试图像，用LMMP算法的单原子搜索方式(即Mt=1)选取400个原子重构图像。表1给出不同ρ值对应的重构图像峰值信噪比PSNR(Peak Signal to Noise Ratio)，以此说明ρ值对LMMP算法逼近性能的影响。由表1可看出，当ρ=0.2时已能保证局部字典搜索与全局字典搜索(ρ=1)所得重构图像的PSNR相同，此时单原子局部搜索速度是单原子全局搜索速度的5倍；当ρ=0.1时，LMMP算法重构图像的PSNR至多减少0.01 dB。该结果验证了2.2节提出的局部字典搜索方法是可行的。

Table 1 Approximation performance ofthe LMMP for different ρ

图2是以Barbara(256×256)为测试图像时LMMP算法与FSMP算法逼近性能的比较。因为FSMP算法和MP算法都是全局单原子搜索方法，二者的逼近性能相同，而运行速度相差N/(2log2N)倍，故实验以FSMP算法结果作为参考。由图2a可看出，ρ=0.2,δ=0.01时，LMMP算法重构图像的PSNR随着逼近原子数的增加逐渐提高，α越大，LMMP算法与FSMP算法的逼近性能越接近。特别地，当α=0.8、逼近原子数为3 000时，LMMP算法仅比FSMP算法的重构图像PSNR低0.14 dB，显示出了良好的性能。由图2b可看出，ρ=0.2,α=0.8时，LMMP算法的逼近性能随δ的减小而越加接近FSMP算法的逼近性能。因为当δ很小时，每代选取的原子间相干性很小，张成的空间大从而使得投影大，故稀疏逼近性能好。

图2表明，LMMP算法好的逼近性能需设置较大的α和较小的δ。

Figure 2 Approximation performance comparison between the LMMP and FSMP图2 LMMP算法与FSMP算法逼近性能的比较

给定PSNR条件下，设LMMP算法的ρ=0.2,α=0.8,δ=0.01，MTP算法、AMMP算法的参数分别同文献[13]和文献[14]，比较LMMP算法与其他算法的运算时间。由图3可看出，随PSNR增大，FSMP算法的运算时间成幂级数增长，MTP算法和AMMP算法的运算时间增长比FSMP算法慢。相比于其他算法，LMMP算法的耗时增长缓慢，且在迭代后期，因满足式(4)的原子越来越多，每代选取的不相干原子数也越多，LMMP算法的运算速度优势越明显。用上述各算法搜索800个原子重构Lena(256×256)图像，并与原图像作比较。观察图4的细节放大图可看出，MTP算法和AMMP算法重构图中的帽子羽毛和眼睛比较模糊，而LMMP算法更为完整地重构了轮廓纹理等细节，视觉效果更接近原图像。

Figure 3 Complexity comparison among the LMMP,FSMP,MTP and AMMP图3 LMMP与FSMP、MTP、AMMP算法稀疏分解耗时比较

Figure 4 Comparison of reconstruction results among the three algorithms图4 三种算法的重构结果对比

表2是四种算法对512×512标准图像重构逼近时的实验结果，其中的时间单元是在相同软硬件条件下，以FSMP算法的运算时间为基准折算所得。正如理论分析那样，与FSMP算法相比，LMMP算法在损失微小精度的情况下具有显著的速度优势，且随着逼近原子数的增多该优势迅速增强；与MTP算法和AMMP算法相比，LMMP算法的运算时间更少、逼近质量更高。但是，由于原子排序及不相干性判断等附加运算，LMMP运算速度的提升比3.2节的分析值稍低。

5 结束语

针对图像稀疏分解算法运算量过大的问题，本文提出一种结合局部字典搜索和多原子匹配追踪的新算法LMMP。LMMP算法利用2D-FHT实现内积的批量快速计算，在此基础上，从局部字典中搜索多个近似非相干原子，并采用逐原子依次更新残差的方式来逼近原图像，显著降低了运算复杂度。理论分析和实验结果表明，LMMP算法收敛且在逼近性能微小损失下时间复杂度比MP算法低数个数量级，与其他三种先进算法相比，LMMP算法在运算速度和逼近性能上都有优势，有利于下一步工程应用研究的开展。

[1] Mallat S G, Zhang Z F.Matching pursuits with time-frequency dictionaries[J].IEEE Transactions on Signal Processing,1993,41(12):3397-3415.

[2] Tang Y B, Chen Y,Xu N,et al.Image denoising via sparse coding using eigenvectors of graph Laplacian[J].Digital Signal Processing,2016,50(C):114-122.

Table 2 Comparison of run time and approximation performance

[4] Zhao W,Liu Z,Guan Z Y,et al.Orthogonal projective sparse coding for image representation[J].Neurocomputing,2016,173(P2):270-277.

[5] Shu Z Q,Zhou J,Huang P,et al.Local and global regularized sparse coding for data representation[J].Neurocomputing,2016,175(Part A):188-197.

[6] Ma Xiao-hu,Tan Yan-qi.Face recognition based on discriminant sparsity preserving embedding[J].Acta Automatica Sinica,2014,40(1):73-82.(in Chinese)

[7] Chen S,Donoho D,Saunders M.Atomic decomposition by basis pursuit[J].SIAM Journal Sciences Computation,2001,43(1):129-159.

[8] Mohammadi M R, Fatemizadeh E,Mahoor M H.Non-negative sparse decomposition based on constrained smoothedl0norm[J].Signal Processing,2014,100(6):42-50.

[9] Gribonval R, Vandergheynst P.On the exponential convergence of matching pursuits in quasi-incoherent dictionaries[J].IEEE Transactions on Information Theory,2006,52(1):6-18.

[10] Figueras V R, Divorra E O,Vandergheynst P.A matching pursuit full search algorithm for image approximations:No 31 CH-1015[R].Lausanne, Switzerland:Ecole Polytechnique Federale de Lausanne (EPFL),Lausanne:ITS-EPFL,2004.

[11] Yin Zhong-ke, Shao Jun,Vandergheynst P.MP based on signal sparse decomposition with FFT[J].Journal of Electronics & Information Technology,2006,28(4):614-618.(in Chinese)

[12] Wang Zai-lei,He Hong-jie,Wang Jian-ying,et al.Fast algorithm for image MP sparse decomposition based on FHT and core dictionary[J].Journal of the China Railway Society,2012,34(9):51-57.(in Chinese)

[13] Rahmoune A,Vandergheynst P,Frossard P.Sparse approximation using m-term pursuit and application in image and video coding[J].IEEE Transactions on Image Processing,2012,21(4):1950-1962.

[14] Gan T,He Y M,Zhu W L.Fast m-fold matching pursuit algorithm for image approximation[J].Journal of Systems Engineering and Electronics,2009,20(4):883-888.

[15] Gong Jun-bin, Ming De-lie,Liu De-kun,et al.Fast image template matching algorithm based on discrete hartley transform[J].Journal of Astronautics,2011,32(5):1115-1123.(in Chinese)

[16] Sun Yu-bao,Xiao Liang,Wei Zhi-hui,et al.Sparse representations of images by a multi-component gabor perception dictionary[J].Acta Automatica Sinica,2008,34(11):1379-1387.(in Chinese)

附中文参考文献：

[6] 马小虎,谭延琪.基于鉴别稀疏保持嵌入的人脸识别算法[J].自动化学报,2014,40(1):73-82.

[11] 尹忠科,邵君,Vandergheynst P.利用FFT实现基于MP的信号稀疏分解[J].电子与信息学报,2006,28(4):614-618.

[12] 王在磊,和红杰,王建英,等.基于核心原子库和FHT的图像MP稀疏分解快速算法[J].铁道学报,2012,34(9):51-57.

[15] 龚俊斌,明德烈,刘德坤,等.基于哈特莱变换的快速图像模板匹配算法[J].宇航学报,2011,32(5):1115-1123.

[16] 孙玉宝,肖亮,韦志辉,等.基于Gabor感知多成份字典的图像稀疏表示算法研究[J].自动化学报,2008,34(11):1379-1387.