李 琪，張 欣，張平康，張 航

(貴州大學(xué) 大數(shù)據(jù)與信息工程學(xué)院，貴陽 550025)

1 引 言

圖像重構(gòu)作為圖像處理領(lǐng)域中關(guān)鍵步驟之一，其重構(gòu)精度決定了圖像恢復(fù)質(zhì)量的好壞，重構(gòu)算法計算復(fù)雜度限制了圖像重構(gòu)的局限性.對于奈奎斯特采樣定律對高頻圖像數(shù)據(jù)采樣時，存在計算復(fù)雜度高、硬件成本大等局限，面對海量的圖像數(shù)據(jù)，奈奎斯特采樣定律顯得力不從心.近年來，基于壓縮感知框架下的圖像重構(gòu)得到廣大學(xué)者研究[1-3].壓縮感知理論[4,5]指出，當(dāng)信號在某一域中呈現(xiàn)稀疏特性，則可通過采集少量的觀測數(shù)據(jù)來實(shí)現(xiàn)對信號的精確重構(gòu).

常見的重構(gòu)算法主要有3類：貪婪類算法、范數(shù)類算法、組合類算法[6].其中貪婪類算法最為常見，其優(yōu)勢在于原理簡單、運(yùn)算量小、易實(shí)現(xiàn)，其中大多數(shù)貪婪算法以正交匹配追蹤算法(Orthogonal Matching Pursuit, OMP)為基礎(chǔ)改進(jìn)得到.文獻(xiàn)[7]提出一種基于回溯思想的正交匹配追蹤算法(Backtracking-Based Adaptive Orthogonal Matching Pursuit, BAOMP)，此算法采用原子選擇與刪除規(guī)則來尋找信號的近似系數(shù)，在一定程度上提高了算法的運(yùn)行速度，但在重構(gòu)精度提升上存在較大的不足.文獻(xiàn)[8]提出一種改進(jìn)的正交匹配追蹤算法，該算法對向量選取的方式進(jìn)行改進(jìn)，但是重構(gòu)圖像存在明顯的人為噪聲.文獻(xiàn)[9]提出一種變步長SAMP算法，在一定的程度上提高了重構(gòu)精度，但算法復(fù)雜度仍較高.

本文對BAOMP算法的原子篩選規(guī)則進(jìn)行研究，結(jié)合稀疏度自適應(yīng)匹配追蹤 (Sparsity Adaptive Matching Pursuit, SAMP)算法，將BAOMP算法中的添加原子與刪除原子思想融入到SAMP算法的原子選擇部分，從而在圖像重構(gòu)精度以及算法運(yùn)行時間上做出改進(jìn).基于此思想，本文提出來一種基于閾值控制的稀疏自適應(yīng)匹配追蹤的圖像重構(gòu)算法(Based on Threshold Sparsity Adaptive Matching ,T-SAMP)，通過仿真驗(yàn)證，該算法合理可行.

2 壓縮感知理論

基于奈奎斯特采樣定律的圖像處理中，其采樣速率受圖像帶寬的限制(要求采樣頻率大于2倍的帶寬).且圖像在壓縮過程中所需的存儲空間較大，在進(jìn)行大規(guī)模圖像數(shù)據(jù)處理時，對系統(tǒng)設(shè)計及硬件成本要求過高.鑒于上述問題，壓縮感知理論應(yīng)運(yùn)而生，在采樣的同時將數(shù)據(jù)進(jìn)行壓縮，即融合采樣壓縮于一體，大大降低了圖像采樣頻率要求并減少了壓縮圖像所需的存儲空間，最后可通過較低復(fù)雜度的重構(gòu)算法重構(gòu)出原始圖像.

2.1 壓縮感知基本框架

壓縮感知理論流程如圖1所示.

圖1 壓縮感知基本框架

壓縮感知理論前提是信號是可壓縮的，然后將采樣與壓縮過程進(jìn)行了合并，采用自適應(yīng)線性投影來保持原始信號的特征(即得到稀疏信號)，最后通過重構(gòu)算法以較少的觀測值準(zhǔn)確的重構(gòu)出原始信號[10].

假設(shè)信號x∈RN可以用一組正交基[φ1,φ2,…,φN]線性表示：

(1)

式(1)中，si是相應(yīng)正交基的投影系數(shù).若投影系數(shù)矩陣s中只有K(K<

y=Φx=ΦΨs=Θs

(2)

式(2)中y是M×1的向量.稀疏信號s可采用相應(yīng)的重構(gòu)算法，從獲取的觀測值y中恢復(fù)出來，然后通過稀疏反變換則可得到原始信號x.由于觀測值y的維數(shù)M遠(yuǎn)小于信號x的維數(shù)N，上式是一個非確定性多項(xiàng)式問題(NP-hard)，無法直接求解.由于式(2)中系數(shù)s是K稀疏的(K

2.2 壓縮感知圖像重構(gòu)

壓縮感知圖像重構(gòu)流程如圖2所示.

圖2 壓縮感知圖像重構(gòu)流程

重構(gòu)信號的數(shù)學(xué)模型如式(3)所示：

y=Φx=ΦΨs=Θs

(3)

將(3)式轉(zhuǎn)換成0范數(shù)最優(yōu)化模型如下：

min‖s‖l0s.t.Θs=y

(4)

但是利用0范數(shù)來求解(4)式是一個NP難題，研究者指出當(dāng)s滿足一定條件時可以用p(0

min‖s‖lps.t.Θs=y

(5)

常見的貪婪類算法就是基于此模型進(jìn)行信號重構(gòu).

3 基于閾值控制的稀疏自適應(yīng)匹配追蹤重構(gòu)算法

3.1 稀疏度自適應(yīng)匹配追蹤算法

SAMP算法流程如下：

輸入?yún)?shù)：測量矩陣P，觀測矩陣Y，步長s

初始化：殘差r0=Y，候選集Λ0=?，支撐集大小L=s，迭代次數(shù)t=1；

Step1.計算u=abs[PTrt-1]，選擇u中L個最大值，將這些值對應(yīng)P的列序列號j構(gòu)成集合St，即St=arg max{,L};

Step2.更新候選集合Ct=Λt-1∪St；

Step6.判斷是否滿足條件‖rt‖≤ε，是則停止迭代；如果‖rnew‖2≥‖rt-1‖2，則更新步長L=L+s返回step 1繼續(xù)迭代；否則，rt=rnew，t=t+1 ；

3.2 基于閾值匹配追蹤算法

基于回溯的匹配追蹤(Backtracking-Based Adaptive Orthogonal Matching Pursuit, BAOMP)算法[7]算法在SP算法的基礎(chǔ)上對添加原子和刪除原子階段做了改進(jìn).在原子選擇階段通過設(shè)置門限μ1，

(6)

即通過(6)式來添加原子，且滿足條件：

|Ct|≤M-|Λ|

(7)

其中C為候選集，Λ為估計支撐集；同時通過設(shè)置門限μ2，

(8)

即通過式(8)來刪除原子，其中μ1，μ2取值范圍為[0,1][7].相對于SP算法有更好的靈活性，在稀疏度未知的情況下，通過門限來選擇和刪除原子，大大提高了重構(gòu)的概率.基于BAOMP算法的原子選擇與原子刪除思想，本文提出了一種基于閾值控制的稀疏度自適應(yīng)匹配追蹤算法(Based on Threshold Sparsity Adaptive Matching,T-SAMP)算法將BAOMP算法的原子添加思想運(yùn)用到SAMP算法中，提高了重構(gòu)精度及縮短了算法迭代時間.文獻(xiàn)[7]提到了μ1的最佳取值分別為0.6.

3.3 基于門限稀疏自適應(yīng)匹配追蹤算法

基于T-SAMP算法的信道估計流程如下：

輸入?yún)?shù)：測量矩陣P，觀測矩陣Y，步長s，閾值μ1

初始化：殘差r0=Y，候選集Λ0=?，支撐集大小L=s，迭代次數(shù)t=1；

Step2.更新候選集合Ct=Λt-1∪St；

Step6.判斷是否滿足條件‖rt‖≤ε,是則停止迭代;如果‖rnew‖2≥‖rt-1‖2,則更新步長L=L+s返回step 1繼續(xù)迭代;否則，rt=rnew,t=t+1;

上述步驟1，2是原子的初步篩選，過濾掉一部分原子，尋找信號的最大近似系數(shù)，從而減小誤差.后述步驟為SAMP算法迭代步驟.

4 仿真結(jié)果分析

4.1 圖像評價指標(biāo)

(9)

(10)

其中，數(shù)字255表示數(shù)字圖像的最大閾值.由公式(9)可知，PSNR值越大，圖像重構(gòu)質(zhì)量越好.

4.2 仿真結(jié)果分析

在迭代次數(shù)均為500時，圖3與圖4為采樣率為中間值0.5時，三種算法的圖像重構(gòu)效果對比.從主觀角度講，BAOMP算法重構(gòu)效果最差，SAMP算法強(qiáng)于BAOMP，T-SAMP算法重構(gòu)效果最佳.但在算法運(yùn)行時間上，SAMP算法由于稀疏度自適應(yīng)調(diào)整引起算法復(fù)雜度增加，故SAMP算法運(yùn)行時間最長，而BAOMP算法由于原子篩選與刪除，排除了大量原子，故所需時間最短，而本文所提出的T-SAMP算法結(jié)合BAOMP算法的原子選擇特點(diǎn)，在SAMP算法基礎(chǔ)上大大降低了SAMP算法的迭代時間.故在主觀角度，與SAMP算法相比，本文所提出的T-SAMP算法在重構(gòu)性能上有較大提升.

圖3 Lena圖像重構(gòu)性能比較

圖4 Barbara圖像重構(gòu)性能比較

在與圖3圖4相同條件下，表1列出了3種算法具體的重構(gòu)時間及PSNR值.由主觀角度到客觀角度，T-SAMP算法PSNR值較SAMP算法有3.5dB的提升，在算法運(yùn)行時間上，T-SAMP算法較SAMP算法相比減少了約60%.結(jié)合圖3、圖4與表1數(shù)據(jù)，分別從主觀角度與客觀角度分析了本文所提出的T-SAMP算法在重構(gòu)精度與算法復(fù)雜度上的優(yōu)勢.

表1 三種算法的重構(gòu)時間及重構(gòu)性能對比

考慮不同采樣率情況下，以Lena圖像為例，圖5為3種算法的PSNR值對比.BAOMP算法在不同采樣率情況下，PSNR值變化幅度較小，產(chǎn)生這樣的原因，主要是BAOMP算

圖5 不同采樣率情況下的PSNR值比較

法在原子選擇規(guī)則上采取的是控制閾值的方式，有效的排除了錯誤原子，對于不同采樣率，每次迭代原子選擇影響不大；而SAMP算法與T-SAMP算法PSNR值隨著采樣率的增加而增大，主要原因是隨著采樣率的增加，稀疏度也會相應(yīng)增加，原始信號的更多特征保留了下來，故在重構(gòu)過程中能較為精確的恢復(fù)出原始信號.如圖5所示，本文所提出的T-SAMP算法較SAMP算法相比平均有約3dB的提升.

圖6 不同采樣率下的MSE對比

圖6為不同采樣率情況下3種算法的均方誤差(MSE)對比，雖然此指標(biāo)不能直觀看出重構(gòu)效果，但從側(cè)面可以反映原始圖像與重構(gòu)圖像之間誤差，誤差越小則可在一定程度上表示圖像的重構(gòu)效果越好.從圖6中可以觀察到T-SAMP算法較SAMP算法，MSE有明顯的降低，這是因?yàn)殚T限控制后的SAMP算法在選擇相關(guān)原子時避免了部分錯誤原子，使圖像的近似系數(shù)最大化，從而重構(gòu)圖像越接近原始圖像.

在相同迭代次數(shù)下，圖7為不同采樣率情況下3種算法運(yùn)行時間對比.如圖7所示，BAOMP算法因原子選擇規(guī)則對采樣率依賴不大，故在不同采樣率情況下算法運(yùn)行時間變化不大；而SAMP算法運(yùn)行時間稀疏度大小與，采樣率越大，圖像的稀疏度越大，故算法運(yùn)行時間越長.如圖7所示，本文所提出的T-SAMP算法較SAMP算法相比，算法運(yùn)行時間節(jié)省了5秒左右，即算法運(yùn)行時間平均減少了約60%.

圖7 不同采樣率下的算法運(yùn)行時間對比

通過以上分析驗(yàn)證，本文所提出的T-SAMP算法較SAMP算法相比，在圖像重構(gòu)精度上，平均有約3dB提升；在算法運(yùn)行時間上，能平均減少約60%.主要是因?yàn)锽AOMP算法中的"添加"原子思想，大大降低了原子選擇的錯誤率，有效提高了SAMP算法的重構(gòu)精度，并大大降低了算法復(fù)雜度.

5 結(jié) 論

本文研究了稀疏度自適應(yīng)匹配追蹤算法(SAMP)在進(jìn)行圖像重構(gòu)中存在算法重構(gòu)精度較低及算法復(fù)雜度較高問題，提出了一種基于閾值控制的稀疏度自適應(yīng)匹配追蹤算法(T-SAMP).考慮到SAMP算法運(yùn)行時間與初始選擇的原子有關(guān)，故結(jié)合BAOMP算法原子選擇階段的篩選與刪除思想，優(yōu)先選擇有用原子，將該步驟引入SAMP算法，以尋找到信號的最大近似系數(shù)，達(dá)到減小誤差以及降低算法復(fù)雜度的目的.仿真表明，本文所提出的T-SAMP算法能有效減少SAMP算法迭代時間并提高圖像重構(gòu)質(zhì)量.本文僅僅只是采用了經(jīng)典的原子選擇閾值0.6，后期可以深入研究不同閾值對圖像重構(gòu)的影響.