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

黃亞飛,梁昔明,樊紹勝

(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.