基于壓縮感知的OMP圖像重構(gòu)算法改進(jìn)

馬小薇

(西安電子科技大學(xué) 生命科學(xué)技術(shù)學(xué)院,陜西 西安 710071)

基于壓縮感知的OMP圖像重構(gòu)算法改進(jìn)

馬小薇

(西安電子科技大學(xué) 生命科學(xué)技術(shù)學(xué)院,陜西 西安 710071)

闡述了壓縮感知相關(guān)理論以及信號(hào)的重構(gòu)算法,圍繞其中的匹配追蹤系列算法展開(kāi)研究,同時(shí)在正交匹配追蹤算法(OMP算法)的基礎(chǔ)上引入了幾種改進(jìn)算法,并結(jié)合OMP算法本身耗時(shí)長(zhǎng)、速度慢的問(wèn)題,給出了一種OMP的改進(jìn)方案,該方案將圖像進(jìn)行分塊再處理,從而大幅降低了OMP算法迭代的矩陣規(guī)模。在相同條件下該算法的主客觀重建效果均優(yōu)于原來(lái)的算法。

壓縮感知;重構(gòu)算法;匹配追蹤;圖像重構(gòu)

目前,壓縮感知的研究多數(shù)集中在信號(hào)或圖像的重構(gòu)及相關(guān)問(wèn)題上。提出了一種基于匹配追蹤(Matching Pursuit,MP)的壓縮感知信號(hào)檢測(cè)算法,從壓縮感知信號(hào)獲取的采樣值中直接提取特征量,但由于其在已選定原子集合上投影的非正交性使得每次迭代的結(jié)果都是次優(yōu)的,因此為獲得收斂需要經(jīng)過(guò)多次迭代。OMP仍沿用了MP算法中的原予選擇準(zhǔn)則,但是通過(guò)遞歸地對(duì)已選擇原子集合進(jìn)行正交化以保證迭代的最優(yōu)性,從而減少了達(dá)到收斂的迭代次數(shù)。但其正交化過(guò)程引入了新的計(jì)算開(kāi)銷(xiāo),特別是對(duì)于圖像信號(hào),計(jì)算量仍然巨大。為更加快速準(zhǔn)確的進(jìn)行信號(hào)與圖像的重構(gòu),對(duì)OMP算法進(jìn)行了改進(jìn)研究,提出了幾種有效的改進(jìn)算法。

1 匹配追蹤算法

1.1 信號(hào)重構(gòu)

在壓縮感知理論中,由于觀測(cè)數(shù)量M遠(yuǎn)小于信號(hào)長(zhǎng)度N,因此必須求解欠定方程組Y=ACSX。表面上看,求解欠定方程組似乎是無(wú)望的,但由于信號(hào)X是稀疏或可壓縮的,這個(gè)前提從根本上改變了問(wèn)題,使得問(wèn)題可解,而觀測(cè)矩陣具有RIP性質(zhì)也為從M個(gè)觀測(cè)值中精確恢復(fù)信號(hào)提供了理論保證[1]。

為更清晰地描述壓縮感知理論的信號(hào)重構(gòu)問(wèn)題,首先定義向量X={X1,…,Xn}的p—范數(shù)為

(1)

當(dāng)p=0時(shí)得到0—范數(shù),它實(shí)際上表示X中非零項(xiàng)的個(gè)數(shù)。于是,在信號(hào)X稀疏或可壓縮的前提下,求解欠定方程組Y=ACSX的問(wèn)題轉(zhuǎn)化為最小0—范數(shù)問(wèn)題

(2)

1.2MP算法

次迭代以后的殘余信號(hào)。首先按照某種規(guī)則設(shè)定了一個(gè)向量ak0∈D,則可將b0分解成沿著 方向的分量和與它垂直分量的迭加

b0=〈b0,ak0〉ak0+b1

(3)

重復(fù)上述的分解過(guò)程,直到分解的項(xiàng)數(shù)達(dá)到預(yù)先設(shè)定值,或者余項(xiàng)的能量小于預(yù)先設(shè)定的值時(shí)才停止迭代。經(jīng)過(guò)m次迭代,信號(hào)b被分解為

(4)

如果迭代在第m步停止計(jì)算,并且記錄下來(lái)二元序列{ak;lk;k=0,1,…,m-1},就可以恢復(fù)出x的近似值,其逼近誤差為bm[3]。

1.3OMP算法

OMP算法[4]的本質(zhì)是:以貪婪迭代的方法選擇傳感矩陣的列,使在每次迭代中所選擇的列與當(dāng)前的冗余向量最大程度地相關(guān),從測(cè)量向量中減去相關(guān)部分并反復(fù)迭代,直到迭代次數(shù)達(dá)到稀疏度K,強(qiáng)制迭代停止。

步驟2 更新索引集Λt=Λt-1∪{λt},記錄找到的傳感矩陣中的重建原子集合Φt=[Φt-1,φλt]。

步驟5 判斷是否滿(mǎn)足t>K,若滿(mǎn)足,則停止迭代;若不滿(mǎn)足,則執(zhí)行步驟l。

OMP算法保證了每次迭代的最優(yōu)性,減少了迭代次數(shù)。但是它在每次迭代中僅選取一個(gè)原子來(lái)更新原子集合,這樣必然會(huì)付出巨大的重建時(shí)間代價(jià)。迭代次數(shù)與稀疏度K或采樣個(gè)數(shù)M密切相關(guān),隨其增大,耗時(shí)也將大幅增加,因此后來(lái)出現(xiàn)了許多改進(jìn)的匹配追蹤算法,如ROMP、STOMP、CoSaMP等。但OMP作為最早的貪婪迭代算法之一,它的思想影響了其他算法,有著不容忽視的意義[5]。

2 OMP算法改進(jìn)研究

2.1 OMP改進(jìn)算法

算法改進(jìn)主要從兩個(gè)方向?qū)ζ溥M(jìn)行改進(jìn),OMP算法由于每次只選取一個(gè)原子,使得重建過(guò)程緩慢。隨著迭代次數(shù)的增加,耗時(shí)也將大幅增加,可以考慮減小單次運(yùn)算規(guī)模以提高速度,首先考慮將圖像進(jìn)行分塊,這樣在不大幅降低算法性能的前提下提高速度,其次在向量選取方法上進(jìn)行改進(jìn)。OMP算法是在字典中尋找與信號(hào)最匹配的向量,即與信號(hào)內(nèi)積最大的向量。這種選取方法的缺陷就是前后選取的向量沒(méi)有關(guān)聯(lián),要達(dá)到要求的重建效果,所需的迭代次數(shù)就很大。在向量選取方法上進(jìn)行改進(jìn)就是每一次迭代過(guò)程同時(shí)選擇L向量來(lái)代替OMP算法中的一個(gè)向量,這樣比OMP算法在同樣次數(shù)下的重建效果有所改善[6]。

2.2 實(shí)現(xiàn)步驟

步驟1 對(duì)原始測(cè)試圖像X進(jìn)行分塊,X像素大小為I=n×n,均勻分成互不覆蓋的大小為A×A的子塊,每個(gè)子塊記為Xi,(i=1,…,s,s=I/A2)。選取的測(cè)試圖像為256×256,分塊為8×8,實(shí)驗(yàn)表明,當(dāng)塊大小<8時(shí)被測(cè)信號(hào)的長(zhǎng)度過(guò)小不適于CS框架正確的處理,同時(shí)當(dāng)塊過(guò)大時(shí)計(jì)算也會(huì)過(guò)于復(fù)雜[7]。

步驟2 對(duì)每個(gè)子塊Xi選取相同的觀測(cè)矩陣ΦA(chǔ),ΦA(chǔ)是MA×A2的正交獨(dú)立同分布高斯矩陣,其中MA的大小為(MA×A2)/I,這樣整幅圖像的觀測(cè)矩陣Φ便是基于ΦA(chǔ)的一個(gè)塊對(duì)角矩陣。可以清楚地看到在該算法中無(wú)需存儲(chǔ)M×N的觀測(cè)矩陣Φ,而需大小為MA×A2的塊觀測(cè)矩陣ΦA(chǔ),這樣降低了存儲(chǔ)空間,并能快速有效地實(shí)現(xiàn)。

步驟3 對(duì)塊進(jìn)行二維離散余弦變化并進(jìn)行Zigzag掃描得到圖像塊的稀疏量化表示,對(duì)每塊采用相同的觀測(cè)矩陣ΦA(chǔ)對(duì)其進(jìn)行采樣,得到觀測(cè)向量yi,對(duì)塊的采樣過(guò)程可以表示為

其中,T(Xi)是二維離散變換算子;γi是量化算子。

步驟4 在正交匹配追蹤算法(OMP)的基礎(chǔ)上進(jìn)行向量選取方式的改進(jìn),根據(jù)公式

(5)

3 實(shí)驗(yàn)與結(jié)果分析

3.1 圖像評(píng)價(jià)標(biāo)準(zhǔn)

(6)

式(6)中,f(x,y)代表圖像函數(shù);M和N分別表示圖像的行數(shù)和列數(shù)。通常來(lái)講,平均梯度越大,則表示重構(gòu)后所得結(jié)果圖像層數(shù)越多,圖像越清晰。

(2)標(biāo)準(zhǔn)差δ。圖像的標(biāo)準(zhǔn)差指標(biāo)反映了圖像中各像素點(diǎn)灰度相對(duì)于該圖像平均灰度的離散情況,可以根據(jù)標(biāo)準(zhǔn)差指標(biāo)的大小來(lái)衡量圖像所含信息豐富程度,圖像反差的大小也能通過(guò)標(biāo)準(zhǔn)差指標(biāo)來(lái)體現(xiàn),標(biāo)準(zhǔn)差計(jì)算公式如式(7)所示

(7)

(3)熵。熵值的大小反映了圖像中所含的平均信息量的多少,關(guān)于圖像評(píng)價(jià)指標(biāo)熵的定義如下

(8)

式(8)中,H代表圖像的熵;L表示圖像中的灰度級(jí)數(shù);ρi表示灰度值為i的像素?cái)?shù)Ni在圖像總像素?cái)?shù)N中所占的比例。圖像中所含的信息量越大,求得的熵值就越大,表示效果越好。

3.2 二維圖像的重建仿真

源圖像為256×256的Lena圖,如圖1所示,在選取觀測(cè)值M=150的情況下,分別基于OMP算法和改進(jìn)的OMP算法進(jìn)行恢復(fù)重構(gòu),其重構(gòu)結(jié)果如圖2和圖3所示,可見(jiàn)不同的重構(gòu)算法會(huì)產(chǎn)生不同的重構(gòu)效果。

圖1 原始圖像

圖2 OMP算法重構(gòu)圖像

圖3 OMP改進(jìn)算法重構(gòu)圖像

為更加直觀地對(duì)比在不同算法下的重構(gòu)圖像,在此給出了各重構(gòu)圖像的平均梯度,標(biāo)準(zhǔn)差,熵和PSNR值,通過(guò)所測(cè)數(shù)據(jù)可以直觀地比較兩幅圖像的重構(gòu)效果,如表1所示。

表1 兩個(gè)重構(gòu)圖像的重構(gòu)效果比較

通過(guò)仿真結(jié)果可以明顯看出,改進(jìn)后的重建效果比較好,圖像較清晰,說(shuō)明對(duì)圖像進(jìn)行分塊處理后重構(gòu)質(zhì)量明顯提高。從表1 中也可以看出,相比傳統(tǒng)的OMP重構(gòu)算法,本文算法在重構(gòu)圖像的平均梯度,標(biāo)準(zhǔn)差,熵上有顯著提高,而且隨著分塊的處理,PSNR值也有相應(yīng)提高,重建效果理想,但從實(shí)驗(yàn)中也可以得出隨著分塊 的處理,計(jì)算時(shí)間和計(jì)算復(fù)雜度會(huì)有所增加。而且在采樣率過(guò)低時(shí),重構(gòu)圖像會(huì)出現(xiàn)明顯的塊效應(yīng)和人為噪聲。

分塊方案犧牲了少量的性能,但圖像清晰度提高了很多。采取該算法時(shí),性能和分塊大小的選取是一個(gè)權(quán)衡問(wèn)題。如何選用適合于所處理的圖像信號(hào)的分塊大小,是該算法效果優(yōu)劣的關(guān)鍵。

4 結(jié)束語(yǔ)

壓縮傳感原理在圖像重建領(lǐng)域的應(yīng)用,可以有效簡(jiǎn)化采集系統(tǒng)的復(fù)雜度,降低系統(tǒng)的成本,加快圖像的重建速度。雖然已經(jīng)提出了很多的壓縮傳感圖像重建系統(tǒng)和算法,但隨著現(xiàn)代科技的發(fā)展,對(duì)圖像重建速度和質(zhì)量提出了更高的要求。因此需要充分發(fā)揮壓縮傳感的優(yōu)勢(shì),使圖像重建所需的觀測(cè)值越少越好、圖像稀疏表示時(shí)越稀疏越好、重建算法越簡(jiǎn)單越快越好。

[1] Candès E.Compressive sampling[C].Madrid,Spain:Proceedings of the International Congress of Mathematicians,2006,3:1433-1452.

[2] Candès E,Romberg J,Terence Tao.Robust uncertainty principles:Exact signal reconstruction from highly incomplete frequency information[J].IEEE Transactions on Information Theory,2006,52(2):1289-1306.

[3] Donoho D L.Compressed sensing[J].IEEE Transactions on Informa2tion Theory,2006,52(4):72-82.

[4] Candès E J,Romberg J.Practical signal recovery from randomprojections[C].Proceedings of SPIE Computational ImagingⅢ:2006:76-86.

[5] Donoho D L,Tsaig Y.Extensions of compressed sensing[J].Signal Processing,2006,86(3):549-571.

[6] 劉丹華,石光明,周佳社.一種冗余字典下的信號(hào)稀疏分解新方法[J].西安電子科技大學(xué)學(xué)報(bào):自然科學(xué)版,2008,35(2):228-232.

[7] Osher S,Mao Y,Dong B,at el.Fast linearized bregman iteration for compressive sensing and sparse denoising[R].Nology,Rice USA:Department of Computational and Applied Mathematices,Rice University,2008.

[8] 謝志鵬.迭代式正交匹配追蹤及稀疏解[J].微電子學(xué)與計(jì)算機(jī),2009,26(10):53-56.

[9] 石光明,劉丹華,高大化,等.壓縮感知理論及其研究進(jìn)展[J].電子學(xué)報(bào),2009,37(5):1070-1081.

[10]方紅,章權(quán)冰,韋穗.基于非常稀疏隨機(jī)投影的圖像重建方法[J].計(jì)算機(jī)工程與應(yīng)用,2007,43(22):25-27.

[11]方紅,章權(quán)冰,韋穗.基于亞高斯隨機(jī)投影的圖像重建方法[J].計(jì)算機(jī)研究與發(fā)展,2008,45(8):1402-1407.

Improvement of OMP Image Reconstruction Algorithm Based on Compressed Sensing

MA Xiaowei

(School of Life Science and Technology,Xidian University,Xi’an 710071,China)

Compressed sensing(CS) theories and the reconstruction algorithm of signals are discussed.Research is done on the matching pursuit algorithms.An improvement scheme for OMP algorithm is given.To increase the convergence speed of the OMP algorithm,the image to be processed is divided into some blocks.The new scheme could significantly improve the computation efficiency.With identical conditions,the algorithm is better than the traditional one in both objective and subjective reconstruction.

compressed sensing;reconstruction algorithm;matching pursuit;image reconstruction

2014- 09- 04

馬小薇(1989—),女,碩士研究生。研究方向:軟件技術(shù)。E-mail:maxw1989@163.com

10.16180/j.cnki.issn1007-7820.2015.04.014

TN911.73;TP391.41

A

1007-7820(2015)04-051-04