基于壓縮感知的圖像重構(gòu)GUI系統(tǒng)

呂 軍，陳 爍，李秀梅

（杭州師范大學(xué)信息科學(xué)與工程學(xué)院，浙江 杭州311121）

0 引言

傳統(tǒng)采樣中，依據(jù)Nyquist采樣定理，采樣頻率不能低于信號(hào)最高頻率的兩倍.隨著人們對(duì)信息需求量的增加，攜帶信息的信號(hào)帶寬越來(lái)越寬，以此為基礎(chǔ)的信號(hào)處理框架對(duì)采樣速率、傳輸速度和存儲(chǔ)空間的要求也越來(lái)越高.

壓縮感知［1-3］通過(guò)遠(yuǎn)低于Nyquist采樣率的方式對(duì)稀疏的或可壓縮的信號(hào)進(jìn)行采樣，同時(shí)能以高概率精確恢復(fù)出原信號(hào).該理論突破了Nyquist采樣定理的限制，在信息論、圖像處理、醫(yī)療成像、模式識(shí)別等很多領(lǐng)域受到廣泛關(guān)注［4］.

壓縮感知把自然信號(hào)經(jīng)過(guò)變換基轉(zhuǎn)化為稀疏信號(hào)，經(jīng)過(guò)測(cè)量矩陣獲得測(cè)量值，在重構(gòu)算法下重建原始信號(hào).即當(dāng)信號(hào)在某個(gè)變換域上是稀疏的或可壓縮的，就可以用一個(gè)與變換基不相關(guān)的測(cè)量矩陣將變換所得的高維信號(hào)投影到一個(gè)低維空間上，然后利用信號(hào)的稀疏先驗(yàn)信息，通過(guò)一定的線性或非線性的重構(gòu)算法，從這些少量的投影中精確或近似精確地重構(gòu)出原始信號(hào).

文章利用Matlab構(gòu)建了基于壓縮感知的圖像重構(gòu)GUI系統(tǒng)，采用兩種稀疏變換基（即小波變換基和離散余弦變換基）、四種測(cè)量矩陣（即高斯矩陣、貝努利矩陣、哈達(dá)瑪矩陣和托普利茲矩陣）、兩種重構(gòu)算法（即正交匹配追蹤算法和壓縮采樣匹配追蹤算法）的不同組合對(duì)圖像進(jìn)行重構(gòu)，并利用峰值信噪比PSNR作為指標(biāo)，分析比較各種組合的重建性能.

1 圖像的采樣和重構(gòu)的過(guò)程簡(jiǎn)介

壓縮感知理論［2-3］主要包括三個(gè)部分：信號(hào)的稀疏表示，測(cè)量編碼和重構(gòu)算法.

1.1 信號(hào)的稀疏表示

當(dāng)一個(gè)信號(hào)只有少量的元素是非零的，則該信號(hào)是稀疏的.但現(xiàn)實(shí)生活中，很多信號(hào)不是稀疏的，需要將其進(jìn)行稀疏表示.信號(hào)的稀疏表示是將信號(hào)投影到變換基上，使投影后的變換系數(shù)絕大部分是很小或接近于零，從而滿足稀疏性.常用的變換基有離散余弦變換基和小波變換基［3，5］.

根據(jù)調(diào)和分析理論［6-7］，一個(gè)長(zhǎng)度為N的一維離散時(shí)間信號(hào)f，可以表示為一組標(biāo)準(zhǔn)正交基的線性組合

其中，Ψ＝［Ψ1｜Ψ2｜…｜ΨN］是N×N的變換基，N×1的列向量x是f在Ψ變換基上的變換向量，x可等價(jià)表示信號(hào)f.如果x中只有K個(gè)元素是非零的，那么就稱(chēng)x是K稀疏的.

1.2 測(cè)量編碼

已知某一個(gè)測(cè)量矩陣Φ∈R M×N（M?N）以及某未知信號(hào)f在該矩陣下的線性測(cè)量值y∈R M×1，即［8］

其中f是原始信號(hào)，x是f的稀疏表示，Θ＝ΦΨ稱(chēng)為M×N的信息算子，y是稀疏信號(hào)x關(guān)于Θ的測(cè)量值，如圖1所示.坎迪斯等人指出，若要精確地重構(gòu)出K稀疏信號(hào)x，測(cè)量的次數(shù)M必須滿足M＝O（Kln（N）），測(cè)量矩陣Θ和變換基Ψ必須滿足約束等距性條件.

圖1 利用測(cè)量矩陣對(duì)信號(hào)進(jìn)行壓縮采樣示意圖Fig.1 Schematic diagram of using measurement matrix to sample the signal with compressive sensing

目前常用的測(cè)量矩陣主要分成隨機(jī)矩陣和確定性矩陣［5］，隨機(jī)矩陣主要有高斯矩陣、貝努利矩陣等，確定性矩陣主要有哈達(dá)瑪矩陣、托普利茲矩陣等.兩類(lèi)測(cè)量矩陣各有優(yōu)缺點(diǎn)：隨機(jī)矩陣重建性能較好，但不易于硬件實(shí)現(xiàn)；確定性矩陣因?yàn)槠湔加玫拇鎯?chǔ)空間少，易于硬件實(shí)現(xiàn)，是未來(lái)測(cè)量矩陣的主要研究方向，普遍來(lái)說(shuō)確定性矩陣的重建精度沒(méi)有隨機(jī)矩陣高.

1.3 重構(gòu)算法

利用重構(gòu)算法求解最小L0范數(shù)優(yōu)化問(wèn)題：

得到稀疏信號(hào)x的精確或近似重構(gòu)，進(jìn)而重構(gòu)原始信號(hào).最小L0范數(shù)優(yōu)化問(wèn)題是N-P hard問(wèn)題，其主要近似求解方法有凸松弛法如基追蹤算法等，和貪婪追蹤算法如匹配追蹤算法等［6-8］.本文主要介紹正交匹配追蹤算法和壓縮采樣匹配追蹤算法.

1.3.1 正交匹配追蹤算法

匹配追蹤算法是一種貪婪迭代算法，其基本思路如下：在每一次的迭代過(guò)程中從過(guò)完備原子庫(kù)（測(cè)量矩陣）中選擇與信號(hào)最匹配的原子來(lái)構(gòu)建稀疏逼近，并且求出信號(hào)表示殘差，然后再繼續(xù)選擇與信號(hào)殘差最為匹配的原子，經(jīng)過(guò)一定次數(shù)的迭代，信號(hào)可以由一些原子線性表示.由于信號(hào)在已選定原子（測(cè)量矩陣的列向量）集合上投影的非正交性使每次迭代的結(jié)果可能是次最優(yōu)的，為獲得收斂可能需要較多次數(shù)的迭代.正交匹配追蹤算法（OMP算法）基本上克服這個(gè)問(wèn)題而且繼承了MP算法中的原子選擇準(zhǔn)則，通過(guò)遞歸地對(duì)已選擇原子集合進(jìn)行正交化保證迭代的最優(yōu)性，減少了迭代次數(shù).對(duì)K稀疏N維離散時(shí)間信號(hào)x，用一個(gè)M×N的高斯矩陣測(cè)量時(shí)，只需M＝O（Kln（N））.

匹配追蹤算法通過(guò)求余量r與測(cè)量矩陣Φ中各個(gè)原子之間內(nèi)積的絕對(duì)值，來(lái)計(jì)算相關(guān)系數(shù)u：

并采用最小二乘法進(jìn)行信號(hào)逼近以及余量更新：

OMP算法的具體步驟如下：

①初始余量r0＝Y(jié)，迭代次數(shù)n＝1，索引值集合Λ＝?，J＝?；

②計(jì)算相關(guān)系數(shù)u，并將u中最大值對(duì)應(yīng)的索引值存入J中；

③更新支撐集ΦΛ，其中ΦΛ∪J0；

④應(yīng)用式（6）得到，同時(shí)用式（7）對(duì)余量進(jìn)行更新；

⑤若‖rnew-r‖≥ε2，令r＝rnew，n＝n＋1轉(zhuǎn)步驟②；否則，停止迭代.

1.3.2 壓縮采樣匹配追蹤算法

OMP算法保證了每次迭代的最優(yōu)性，減少了迭代的次數(shù).但在每次迭代中僅選取一個(gè)原子來(lái)更新原子集合，這樣必然會(huì)付出巨大的重建時(shí)間代價(jià).因此出現(xiàn)了許多改進(jìn)的匹配追蹤算法，如壓縮采樣匹配追蹤算法（CoSa MP算法），在重建時(shí)間和重建質(zhì)量之間取得一個(gè)較好的平衡，保證重建質(zhì)量的同時(shí)提高重建效率.

OMP算法每次只選擇一個(gè)與余量相關(guān)的原子，從原子的選擇方式上看實(shí)現(xiàn)了單個(gè)原子的精確選擇.而引入回溯思想的壓縮采樣匹配追蹤（CoSa MP）算法是從原子庫(kù)中選擇多個(gè)較相關(guān)的原子同時(shí)剔除部分原子，從而提高算法效率.CoSa MP算法保證了候選集合最多不會(huì)超過(guò)3K個(gè)原子，每次迭代支撐集擁有2K個(gè)原子，同時(shí)剔除的原子數(shù)目最多不超過(guò)K個(gè).CoSaMP算法具體算法如下：

①初始余量r0＝Y(jié)，估計(jì)信號(hào)稀疏度為K，迭代次數(shù)n＝1，索引值集合Λ＝?，J＝?；

②用式（5）計(jì)算相關(guān)系數(shù)u，并從u中尋找2K個(gè)最大值對(duì)應(yīng)的索引值存入J中；

③Λ∪J，應(yīng)用式（6）得到＾Z，取前K個(gè)最大元素對(duì)應(yīng)的原子放入支撐集ΦΛ；

④應(yīng)用式（6）得到＾X，同時(shí)用式（7）對(duì)余量進(jìn)行更新；

⑤若｜Λ｜≥2K，則停止迭代；否則令r＝rnew，n＝n＋1轉(zhuǎn)步驟②.

CoSa MP算法每次迭代中都要同時(shí)選中多個(gè)原子，而且最終用于重建的支撐集大小是確定的，這就需要在迭代過(guò)程中不斷選中原子的同時(shí)剔除一部分以前選中的原子.那么這種方式能否保證每輪迭代中至少選中一個(gè)最終用于信號(hào)重建的原子而不會(huì)被剔除，這是一個(gè)值得質(zhì)疑的問(wèn)題.研究證明即便剔除了己經(jīng)選定的部分原子依然可以保證留下的原子是最優(yōu)的從而精確重建信號(hào)［8］.

2 基于Matlab圖像的壓縮感知實(shí)現(xiàn)系統(tǒng)設(shè)計(jì)

MATLAB 是由Math Works公司開(kāi)發(fā)的高級(jí)技術(shù)計(jì)算語(yǔ)言和交互式環(huán)境，廣泛應(yīng)用于算法開(kāi)發(fā)、數(shù)據(jù)可視化、數(shù)據(jù)分析以及數(shù)值計(jì)算等領(lǐng)域.Matlab中圖形用戶(hù)界面GUI由窗口、光標(biāo)、按鍵、菜單和文本等對(duì)象（Object）構(gòu)成，可以通過(guò)編程控制各個(gè)控件之間協(xié)調(diào)工作.

本文將在Matlab開(kāi)發(fā)環(huán)境下，完成基于壓縮感知的圖像重構(gòu)GUI可視化系統(tǒng)，包括界面設(shè)計(jì)和算法程序設(shè)計(jì).利用該GUI可視化系統(tǒng)，用戶(hù)只需選擇所需處理的圖像，并選擇相應(yīng)的變換基、重構(gòu)的域、測(cè)量矩陣、重構(gòu)算法，即可以完成圖像重構(gòu)，并得到相應(yīng)重構(gòu)圖像的峰值信噪比.

2.1 系統(tǒng)框圖及說(shuō)明

系統(tǒng)的框架如圖2所示：

圖2 系統(tǒng)框架圖Fig.2 The system diagram

系統(tǒng)對(duì)應(yīng)的GUI界面如圖3：

圖3 系統(tǒng)GUI界面Fig.3 The GUI of the system

2.2 圖像重構(gòu)GUI系統(tǒng)演示

為了評(píng)價(jià)圖像重構(gòu)的性能，采用峰值信噪比PSNR 作為評(píng)價(jià)標(biāo)準(zhǔn)，其定義式為：

需要說(shuō)明的是，采用測(cè)量矩陣對(duì)圖像的系數(shù)進(jìn)行采樣時(shí)，可以在空間域中進(jìn)行采樣即針對(duì)空間的圖像進(jìn)行采樣，也可以在變換域即經(jīng)過(guò)變換基變換后的小波變換域或DCT 變換域進(jìn)行采樣.

下面以變換基選擇小波變換基、測(cè)量矩陣選擇高斯隨機(jī)矩陣、重構(gòu)算法選擇正交匹配追蹤算法OMP為例，在小波變換變換域中利用測(cè)量矩陣對(duì)樣本點(diǎn)進(jìn)行測(cè)量，進(jìn)而完成圖像重構(gòu).如圖4所示，點(diǎn)擊“選擇原始圖像”按鈕，選擇lena.jpg圖像并顯示在原始圖像框中，選擇“變換基”下拉菜單中的小波變換基，點(diǎn)擊“稀疏化”按鈕，顯示稀疏化后的圖像，再選擇“選擇重構(gòu)域”下拉菜單中的“變換域”，選擇“高斯隨機(jī)矩陣”，再選擇“正交匹配追蹤算法”，點(diǎn)擊“重構(gòu)”按鈕，完成圖像的重構(gòu)并顯示，并在PSNR 顯示框中顯示計(jì)算的PSNR值.圖5則顯示了變換基選擇小波變換基、測(cè)量矩陣選擇哈達(dá)瑪矩陣、重構(gòu)算法選擇壓縮采樣匹配追蹤算法CoSa MP時(shí)在變換域上進(jìn)行測(cè)量后所獲得的重構(gòu)圖像GUI系統(tǒng).

圖4 利用小波變換基、高斯隨機(jī)矩陣、正交匹配追蹤算法OMP的圖像重構(gòu)結(jié)果Fig.4 The image reconstruction result with wavelet transform basis，Gaussian random matrix and OMP algorithm

圖5 利用小波變換基、哈達(dá)瑪矩陣、壓縮采樣匹配追蹤算法CoSa MP的圖像重構(gòu)結(jié)果Fig.5 The image reconstruction result with wavelet transform basis，Hadamard matrix and CoSaMP algorithm

同樣，利用該系統(tǒng)可以針對(duì)圖像實(shí)現(xiàn)在小波變換基和離散余弦變換基下的稀疏化，再在空間域或者變換域上選擇不同的觀測(cè)矩陣和不同的重構(gòu)算法實(shí)現(xiàn)圖像的重構(gòu)演示.各種不同組合情況下所得到的實(shí)驗(yàn)結(jié)果如表1-表4所示，其中表1為采用隨機(jī)矩陣時(shí)在變換域中進(jìn)行測(cè)量的重構(gòu)效果，表2為采用隨機(jī)矩陣時(shí)在空間域中進(jìn)行測(cè)量的重構(gòu)效果.從表1和表2中可以看出：在小波變換基和離散余弦變換基下，OMP重構(gòu)算法的性能都優(yōu)于CoSa MP重構(gòu)算法的性能；當(dāng)采用同一重構(gòu)算法時(shí)，采用高斯隨機(jī)矩陣和貝努利矩陣作為測(cè)量矩陣可以得到相近的圖像重構(gòu)性能；當(dāng)采用同一重構(gòu)算法和測(cè)量矩陣時(shí)，在變換域進(jìn)行測(cè)量和在空間域進(jìn)行測(cè)量，可以得到相近的圖像重構(gòu)性能；在其他條件相同的情況下，基于小波變換基的圖像重構(gòu)效果要優(yōu)于在離散余弦變換基的重構(gòu)效果.

其中表3為采用確定矩陣時(shí)在變換域中進(jìn)行測(cè)量的重構(gòu)效果，表4為采用確定矩陣時(shí)在空間域中進(jìn)行測(cè)量的重構(gòu)效果.從表3和表4中可以看出：當(dāng)采用確定矩陣時(shí)，在小波變換基和離散余弦變換基下，在變換域進(jìn)行測(cè)量的重構(gòu)效果都要好于在空間域中進(jìn)行測(cè)量的重構(gòu)效果，原因在于利用確定矩陣從空間域進(jìn)行測(cè)量時(shí)無(wú)法保證所選樣本的隨機(jī)性，當(dāng)有些非零的系數(shù)沒(méi)有被測(cè)量到時(shí)，對(duì)最終的重構(gòu)效果影響比較大；在小波變換基下，在變換域進(jìn)行測(cè)量時(shí)，采用托普利茲矩陣得到的重構(gòu)效果要略好于采用哈達(dá)瑪矩陣的效果.此外，圖像經(jīng)過(guò)變換基后得到的變換域稀疏，有時(shí)并不是理想的稀疏，需要進(jìn)行加閾值處理，得到稀疏系數(shù)，然后再進(jìn)行重構(gòu).

對(duì)比表1，表2以及表3，表4還可以看出，在相同的變換基下，采用確定矩陣在變換域上進(jìn)行測(cè)量時(shí)，采用COSAMP算法重構(gòu)的效果比隨機(jī)矩陣好.在其它條件下，隨機(jī)矩陣測(cè)量得到的重構(gòu)效果普遍好于確定矩陣測(cè)量得到的重構(gòu)效果.

需要說(shuō)明的是，本論文中圖表是以lena.jpg圖像為例進(jìn)行分析的，當(dāng)采用不同圖像時(shí)，圖表結(jié)果可能會(huì)有細(xì)微區(qū)別.

表1 采用隨機(jī)矩陣在變換域中進(jìn)行測(cè)量的重構(gòu)效果Tab.1 The reconstruction performance with random matrices in the transform domain

表2 采用隨機(jī)矩陣在空間域中進(jìn)行測(cè)量的重構(gòu)效果Tab.2 The reconstruction performance with random matrices in the spatial domain

表3 采用確定矩陣在變換域中進(jìn)行測(cè)量的重構(gòu)效果Tab.3 The reconstruction performance with deterministic matrices in the transform domain

表4 采用確定矩陣在空間域中進(jìn)行測(cè)量的重構(gòu)效果Tab.4 The reconstruction performance with deterministic matrices in the spatial domain

3 結(jié)論

本文利用Matlab設(shè)計(jì)了基于壓縮感知的圖像重構(gòu)GUI可視化系統(tǒng)，針對(duì)不同的變換基、不同的觀測(cè)矩陣和不同重構(gòu)算法下重構(gòu)效果進(jìn)行直觀對(duì)比.該GUI系統(tǒng)作為壓縮感知的實(shí)現(xiàn)平臺(tái)，能夠直觀分析圖像在不同條件下基于壓縮感知方法進(jìn)行重構(gòu)的效果以及更好地理解壓縮感知的過(guò)程.從結(jié)果分析可以看出，利用隨機(jī)矩陣進(jìn)行測(cè)量得到的重構(gòu)效果要好于利用確定矩陣進(jìn)行測(cè)量得到的重構(gòu)效果；利用確定矩陣在空間域上進(jìn)行測(cè)量所得到的重構(gòu)效果較差，不能完成較好的圖像重構(gòu)；基于小波變換基，利用隨機(jī)矩陣在變換域上進(jìn)行測(cè)量，并利用OMP算法進(jìn)行重構(gòu)的效果最好.鑒于隨機(jī)矩陣不易于硬件實(shí)現(xiàn)，為了便于硬件實(shí)現(xiàn)且保證較好的圖像重構(gòu)性能，可以利用確定矩陣，基于小波變換基在變換域上利用OMP算法進(jìn)行圖像重構(gòu).

［1］Candes E，Romberg J，Tao T.Robust uncertainty principles：Exact signal reconstruction from highly incomplete frequency information［J］.IEEE Transaction on Information Theory，2006，52（2）：489-509.

［2］邵文澤，韋志輝.壓縮感知基本理論：回顧與展望［J］.中國(guó)圖像圖形學(xué)報(bào)，2010，17（1）：1-12.

［3］尹宏鵬，劉兆棟，柴毅，等.壓縮感知綜述［J］.自動(dòng)化學(xué)報(bào)，2013，28（10）：1441-1445.

［4］侯金曼，何寧，呂科.基于壓縮感知的圖像快速重建方法［J］.計(jì)算機(jī)工程，2011，37（19）：215-217.

［5］焦李成，楊淑媛，劉芳，等.壓縮感知回顧與展望［J］.電子學(xué)報(bào)，2011，39（7）：1651-1658.

［6］Baraniuk R G.Compressive Sensing［J］.IEEE Signal Processing Magazine，2007，24（4）：118-121.

［7］Emamnuel J，Candes E，Michael B W.An Introduction to Compressive Sampling［J］.IEEE Signal Processing Magazine，2008，25（2）：21-30.

［8］趙玉朗.壓縮傳感在信號(hào)采集系統(tǒng)中的應(yīng)用研究［D］.天津：南開(kāi)大學(xué)，2010.