壓縮感知重構(gòu)算法研究

張永立　黃芳　范志勇

【摘 要】壓縮感知是一種全新的信號(hào)采樣重構(gòu)方法，和傳統(tǒng)的方法相比，它不再要求信號(hào)的采樣率達(dá)到信號(hào)帶寬的兩倍以上，這樣就克服了資源浪費(fèi)，效率低下等缺陷，本文研究了壓縮感知理論，并在此基礎(chǔ)上研究了多種重構(gòu)算法，并應(yīng)用五種典型的壓縮感知重構(gòu)算法來(lái)重構(gòu)二維彩色圖片和二維灰度圖片，客觀的對(duì)比了兩種算法的實(shí)驗(yàn)效果。

【關(guān)鍵詞】壓縮感知;重構(gòu)算法

中圖分類號(hào)： TN911.7 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 2095-2457（2019）10-0046-002

DOI：10.19694/j.cnki.issn2095-2457.2019.10.017

Research on Compression Perception Reconstruction Algorithm

ZHANG Yong-li HUANG Fang FAN Zhi-yong

（Jiaozuo Teachers College，Department of Mathematics， Institute of Applied Mathematics， Jiaozuo HeNan 454002，China）

【Abstract】Compressed sensing is a new method of signal sampling and reconstruction. Compared with the traditional method， it no longer requires the sampling rate of signal to be more than twice the bandwidth of signal， which overcomes the shortcomings of waste of resources and inefficiency. This paper studies the theory of compressed sensing， and on this basis， studies a variety of reconstruction algorithms， and applies five typical compressed sensing reconstruction algorithms to reconstruct. A two-dimensional color image and a two-dimensional gray image objectively compare the experimental results of the two algorithms.

【Key words】Compressed Sensing; Reconstruction Algorithms

0 引言

隨著信息技術(shù)的發(fā)展，信息傳輸量越來(lái)越大，信息存儲(chǔ)、傳輸和重構(gòu)問(wèn)題成為研究熱點(diǎn)。傳統(tǒng)Shannon-Nyquist采樣理論要求采樣率須達(dá)到信號(hào)帶寬的兩倍以上，資源使用率高.而在實(shí)際中，除了想高精度重構(gòu)該信號(hào)外，也想降低存儲(chǔ)和傳輸成本.為解決此問(wèn)題，基于泛函分析、信號(hào)逼近和稀疏逼近的理論，統(tǒng)計(jì)學(xué)專家Donoho、華裔數(shù)學(xué)家陶哲軒、Romberg、Candes、Baraniuk等科學(xué)家提出了壓縮感知理論[1-3]。

本文在壓縮感知理論的基礎(chǔ)上，總結(jié)多種重構(gòu)算法，并采用五種典型壓縮感知重構(gòu)算法來(lái)重構(gòu)一個(gè)二維彩色圖片和一個(gè)二維灰度圖片，在考慮時(shí)間效率和重構(gòu)效果的雙重前提下，比較各算法對(duì)不同類型圖片的重構(gòu)效果。

1 壓縮感知重構(gòu)算法

壓縮感知重構(gòu)算法大致可分為三類基本方法，第一類是貪婪算法，首先選取合適的原子，再逐步進(jìn)行遞增，進(jìn)而逼近信號(hào)矢量，利用這種過(guò)程進(jìn)行重構(gòu)的方法統(tǒng)稱作匹配追蹤算法（MP）。MP算法中，具有代表性的有正交匹配追蹤算法[4]（OMP），正則正交匹配追蹤算法[5]（ROMP），壓縮采樣匹配追蹤算法[6]（CoSaMP），稀疏自適應(yīng)匹配追蹤算法[7]（SAMP）。

另一類是凸松弛類算法，它將非凸問(wèn)題轉(zhuǎn)化為凸問(wèn)題進(jìn)行求解，即l0范數(shù)轉(zhuǎn)化成l1范數(shù)并采用線性規(guī)劃來(lái)求解，有代表性的包括同倫算法（HA），原始-對(duì)偶內(nèi)點(diǎn)發(fā)（PDIPA），對(duì)偶增廣拉格朗日乘數(shù)算法（DALM），原始增廣拉格朗日乘數(shù)算法（PALM），迭代收縮閥算法（IST）等。

第三類是組合算法，該類算法一般要求信號(hào)的采樣支持通過(guò)分組測(cè)試來(lái)實(shí)現(xiàn)原始信號(hào)的快速高精度重建。組合算法包括鏈?zhǔn)阶粉櫵惴ā⒏道锶~采樣算法等。

2 仿真實(shí)驗(yàn)

本節(jié)對(duì)二維彩色圖片和二維灰度圖片，采用BP、PALM、DALM、PAIPA以及Homotopy五種壓縮感知重構(gòu)算法對(duì)兩類圖片進(jìn)行重構(gòu)，使用的評(píng)價(jià)標(biāo)準(zhǔn)是峰值性噪比的大小，即：

其中MSE為均方誤差。實(shí)驗(yàn)所采用的電腦配置是Intle酷睿i3 8100T（3.1GHz），內(nèi)存為4GB，采用的軟件為Matlab R2018a。

在不存在測(cè)量噪聲的情況下，首先對(duì)原圖像做了80次學(xué)習(xí)，然后使用以上五種算法分別對(duì)它進(jìn)行重構(gòu)，表1的第三列分別顯示了五種算法所耗費(fèi)的時(shí)間和PSNR，從表1中可以看出，在考慮時(shí)間效率和重構(gòu)效果的雙重因素下，PDIPA算法的效果更好。

下面進(jìn)行有噪聲的測(cè)量，目的是為了考察這五種典型算法的魯棒性。首先對(duì)二維灰度圖片的原圖做80次學(xué)習(xí)，然后加入四種不同類型的噪聲，分別是高斯白噪聲（gaussian）、泊松噪聲（poisson）、椒鹽噪聲（salt&pepper）和斑點(diǎn)噪聲（speckle），然后應(yīng)用BP、PALM、DALM、PAIPA以及Homotopy這五種算法對(duì)加入噪聲的圖片進(jìn)行仿真實(shí)驗(yàn)。

表1的第四到七列分別顯示出這五種算法在加入四種噪音后的重構(gòu)結(jié)果和所耗時(shí)長(zhǎng)，從表中的對(duì)比結(jié)果可以看出，在考慮重構(gòu)效率和重構(gòu)效果的雙重前提下，Homotopy算法既考慮了時(shí)間因素，并且重構(gòu)結(jié)果最好。

接下來(lái)得實(shí)驗(yàn)，我們采用一幅256*256的彩色圖片。首先對(duì)彩色圖像進(jìn)行100次學(xué)習(xí)，選用小波基作為稀疏基去生成測(cè)量矩陣，用BP、PALM、DALM、PAIPA以及Homotopy這五種算法分別對(duì)其進(jìn)行了仿真實(shí)驗(yàn)，使用PSNR來(lái)評(píng)價(jià)重建圖像的質(zhì)量。不存在噪聲時(shí)，圖2-3給出了五種算法的比較結(jié)果。表2的第三列分別列出了五種算法所耗費(fèi)的時(shí)間和PSNR。從結(jié)果看出，同時(shí)考慮時(shí)間因素和重構(gòu)效果，PDIPA算法的效果更好。

下面考慮了有噪聲的測(cè)量，目的是為了考察這五種算法對(duì)彩色圖像的魯棒性。首先對(duì)原圖做100次學(xué)習(xí)，并對(duì)其加入高斯白噪聲（gaussian）、泊松噪聲（poisson）、椒鹽噪聲（salt&pepper）和斑點(diǎn)噪聲（speckle），然后應(yīng)用BP、PALM、DALM、PAIPA以及Homotopy五種算法對(duì)二維彩色圖片進(jìn)行仿真實(shí)驗(yàn).以斑點(diǎn)噪聲為例，在100次學(xué)習(xí)并存在斑點(diǎn)噪聲時(shí).這五種算法在四種噪聲下的耗時(shí)時(shí)間和重構(gòu)結(jié)果分別展示在表2的第四到七列.顯然，在考慮重構(gòu)效率和重構(gòu)效果的雙重前提下，PALM算法的效果較好。

3 結(jié)論

本文總結(jié)了一些壓縮感知的經(jīng)典重構(gòu)算法以及相互關(guān)系，并將BP、PALM、DALM、PAIPA以及Homotopy五種算法應(yīng)用到了二維灰度圖像和二維彩色圖像的重構(gòu)仿真實(shí)驗(yàn)當(dāng)中，實(shí)驗(yàn)結(jié)果顯示，若同時(shí)考慮時(shí)間效率和重構(gòu)效果的情況下，重構(gòu)灰度圖片時(shí)，Homotopy算法效果較好，對(duì)于彩色圖像，PALM算法效果較好。

【參考文獻(xiàn)】

[1]孫玉寶，肖亮，韋志輝，等.基于Gabor感知多成份字典的圖像稀疏表示算法研究[J].自動(dòng)化學(xué)報(bào)，2008，34（11）：1379-1387.

[2]李樹(shù)濤，魏丹.壓縮傳感綜述[J].自動(dòng)化學(xué)報(bào)，2009，35（11）：1369-1377.

[3]楊海蓉，張成，丁大為，等.壓縮傳感理論與重構(gòu)算法[J].電子學(xué)報(bào)，2011，39（1）：142-148.

[4]Muthukrishnan S.Data streams：Algorithms and applications[M].Now Publishers Inc，2005.

[5]Tropp J A，Gilbert A C.Signal recovery from random measu-

rements via orthogonal matching pursuit[J].IEEE Transactions on Information Theory， 2007，53（12）：4655-4666.

[6]Needell D，Vershynin R.Greedy signal recovery and uncerta-

inty principles[C].Electronic Imaging 2008.International Society for Optics and Photonics，2008：68140J-68140J-12.

[7]Needell D，Tropp J A.CoSaMP：Iterative signal recovery from incomplete and inaccurate samples[J].Applied and Computational Harmonic Analysis，2009，26（3）：301-321.