閾值稀疏自適應匹配追蹤圖像重構算法

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

(貴州大學 大數據與信息工程學院，貴陽 550025)

1 引 言

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

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

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

2 壓縮感知理論

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

2.1 壓縮感知基本框架

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

圖1 壓縮感知基本框架

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

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

(1)

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

y=Φx=ΦΨs=Θs

(2)

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

2.2 壓縮感知圖像重構

壓縮感知圖像重構流程如圖2所示.

圖2 壓縮感知圖像重構流程

重構信號的數學模型如式(3)所示：

y=Φx=ΦΨs=Θs

(3)

將(3)式轉換成0范數最優化模型如下：

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

(4)

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

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

(5)

常見的貪婪類算法就是基于此模型進行信號重構.

3 基于閾值控制的稀疏自適應匹配追蹤重構算法

3.1 稀疏度自適應匹配追蹤算法

SAMP算法流程如下：

輸入參數：測量矩陣P，觀測矩陣Y，步長s

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

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

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

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

3.2 基于閾值匹配追蹤算法

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

(6)

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

|Ct|≤M-|Λ|

(7)

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

(8)

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

3.3 基于門限稀疏自適應匹配追蹤算法

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

輸入參數：測量矩陣P，觀測矩陣Y，步長s，閾值μ1

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

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

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

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

4 仿真結果分析

4.1 圖像評價指標

(9)

(10)

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

4.2 仿真結果分析

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

圖3 Lena圖像重構性能比較

圖4 Barbara圖像重構性能比較

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

表1 三種算法的重構時間及重構性能對比

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

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

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

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

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

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

圖7 不同采樣率下的算法運行時間對比

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

5 結 論

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