宋長明， 惠慶磊

(中原工學(xué)院， 鄭州 450007)

?

壓縮感知中圖像重構(gòu)的模型綜述

宋長明， 惠慶磊

(中原工學(xué)院， 鄭州 450007)

分別從稀疏表示、編碼測量以及重構(gòu)算法等方面闡述了壓縮感知的基本原理?；诟怕省⑼箖?yōu)化等詳細(xì)介紹了圖像重構(gòu)模型的理論框架和發(fā)展?fàn)顩r，并從字典學(xué)習(xí)和低秩表示的角度展望了圖像重構(gòu)模型進(jìn)一步研究的方向。

壓縮感知；圖像重構(gòu)；凸優(yōu)化；低秩

隨著科學(xué)技術(shù)的發(fā)展，海量數(shù)據(jù)在帶給人們各種便利的同時(shí)，也給數(shù)據(jù)分析和處理帶來了極大的困難。如何有效采集和處理高維數(shù)據(jù)，成為信號處理領(lǐng)域一個(gè)亟待解決的問題。2006年，Donoho D L和Candès E等提出一種新穎的信號采樣和處理理論，即壓縮感知(Compressive Sensing)理論[1-3]。該理論將信號采樣和壓縮合并進(jìn)行，提高了信號采集、信息處理能力，突破了香農(nóng)-奈奎斯特采樣定理的瓶頸，大大緩解了數(shù)據(jù)采集、存儲(chǔ)、傳輸和分析的壓力。

壓縮感知理論指出，當(dāng)信號在某個(gè)變換域下可壓縮或稀疏時(shí)，通過采集少量的信號非自適應(yīng)線性投影值，構(gòu)建數(shù)學(xué)重構(gòu)模型并利用重構(gòu)算法求解，可以較精確地重構(gòu)原信號。其研究內(nèi)容主要包括稀疏表示、編碼測量和重構(gòu)算法三方面。稀疏表示是壓縮感知理論的先驗(yàn)條件。從正交基、組合正交基、多尺度幾何分析再到字典學(xué)習(xí)的發(fā)展，稀疏表示理論愈加豐富。編碼測量是壓縮感知理論硬件實(shí)現(xiàn)的關(guān)鍵，但并非直接測量信號本身，而是經(jīng)過測量矩陣將其投影到低維空間，并保持信號原本的結(jié)構(gòu)信息。重構(gòu)算法是壓縮感知理論的核心，指利用盡量少的測量值，快速、魯棒、精確地重構(gòu)原信號。

一般地，信號重構(gòu)過程可轉(zhuǎn)化為一個(gè)求解最小l0范數(shù)的模型。統(tǒng)計(jì)學(xué)、計(jì)算機(jī)領(lǐng)域的研究者從組合算法[4]角度解決稀疏信號重構(gòu)問題，此類方法比壓縮感知理論更早地被提出來?？紤]到非確定性因素，Ji S等提出了貝葉斯壓縮感知模型[5]，這類模型構(gòu)建了壓縮感知和機(jī)器學(xué)習(xí)的橋梁，為深層次研究提供了新的思路。通過逐步迭代的方法逼近待重構(gòu)稀疏信號的支撐集，從而引出一大類匹配追蹤算法[6]?？紤]到l0范數(shù)的高度非凸性屬于NP問題，研究者從多個(gè)角度入手，提出了多種近似等價(jià)的重構(gòu)模型。目前主流的研究模型是凸優(yōu)化模型，即采用凸函數(shù)代替非凸函數(shù)，并采用凸優(yōu)化的方法求解。Candès E等采用l1范數(shù)代替l0范數(shù)，提出最小l1范數(shù)模型[3]，隨后又提出了加權(quán)的最小l1范數(shù)模型[7]。在Candès E等結(jié)合二維圖像梯度場稀疏性提出全變分模型[3]的基礎(chǔ)上，Lou Y等提出了加權(quán)全變分模型[8]。Chartrand R等以犧牲計(jì)算復(fù)雜度為代價(jià)，用lp(0

1　稀疏表示

1959年，Hubel等在研究貓的簡單細(xì)胞感受野時(shí)，發(fā)現(xiàn)位于主觀視覺皮層V1區(qū)的細(xì)胞能夠?qū)σ曈X信息進(jìn)行稀疏表示[14]。生物學(xué)家指出，哺乳動(dòng)物的視覺神經(jīng)系統(tǒng)是一個(gè)非常有效的系統(tǒng)，當(dāng)觀察某個(gè)特定畫面時(shí)，只有有限個(gè)視覺神經(jīng)元被激活，即用較少的神經(jīng)元表現(xiàn)所觀察物體的特征，這是其長期進(jìn)化的結(jié)果。隨著人們對稀疏表示理論的深入研究，這一理論被廣泛應(yīng)用于信號處理等領(lǐng)域。

定義1稀疏：信號x在變換基Ψ下的變換系數(shù)向量Θ=ΨTx，假如對于00，這些系數(shù)滿足：

(1)

說明系數(shù)向量Θ在某種意義下是稀疏的[1]。如果Θ中只有少數(shù)元素是非零的，則稱Θ是稀疏的，那么信號x是可壓縮或稀疏的。若只有k個(gè)非零元素，則稱Θ是信號x的k稀疏表示。

需要指出的是，很少有信號是真正稀疏的。當(dāng)認(rèn)為某個(gè)信號稀疏時(shí)，更確切地說，是這個(gè)信號可以通過稀疏信號近似表達(dá)。傳統(tǒng)上，信號稀疏表示主要基于正交基和組合正交基，如傅里葉變換、小波變換等；之后，為解決高維空間數(shù)據(jù)稀疏表示問題，提出了多尺度幾何分析。根據(jù)哺乳動(dòng)物視覺神經(jīng)系統(tǒng)接收場的特性，Kondo S提出了更為有效的冗余字典學(xué)習(xí)[15]。目前，冗余字典的設(shè)計(jì)和學(xué)習(xí)是研究的熱點(diǎn)和難點(diǎn)。字典可以有效表示信號中的階躍、紋理、振蕩等高維特征信息，其原子不再是單一的基函數(shù)，而是通過構(gòu)造和學(xué)習(xí)的冗余原子庫，增加原子的個(gè)數(shù)，提高變換系數(shù)的冗余性，來增強(qiáng)逼近信號的靈活性，進(jìn)而提高復(fù)雜信號的稀疏表示能力。其中具有非零系數(shù)的原子體現(xiàn)了信號的主要結(jié)構(gòu)及特征信息。更形象地說，利用字典中的原子庫，采用線性組合方式，可“拼”出最逼近原圖像的圖像。當(dāng)然，這個(gè)拼圖游戲相當(dāng)復(fù)雜。

2　測量矩陣

測量矩陣是壓縮感知理論能否成功實(shí)現(xiàn)的關(guān)鍵。如果原始信號充分稀疏并且測量值是精確的，則某些條件可以確保重構(gòu)解是唯一的。這些條件(如零空間性質(zhì)或約束等距條件等)保證了存在多種矩陣滿足壓縮感知的要求，如二值隨機(jī)矩陣、局部傅里葉矩陣、隨機(jī)Toeplitz矩陣等。

定義2零空間性質(zhì)：對于矩陣Φ，如果對于非零向量h和所有|S|≤K的坐標(biāo)集合S?{1,2,…,n}都滿足:

‖hs‖1<‖hsc‖1

(2)

則Φ滿足K階零空間性質(zhì)(NullSpaceProperty)[16]。其中:h∈N(Φ){0}，N(Φ)表示矩陣Φ的零空間；S={i|xi≠0};Sc={i|xi=0}，表示S的余集。

零空間特性表明屬于矩陣Φ的零空間向量的非零元素應(yīng)該是均勻分布的，不會(huì)集中在任意K個(gè)元素中。K階零空間特性確保測量矩陣不會(huì)出現(xiàn)歧義，即如果Φx=Φx′，則必有x=x′或x≈x′。

當(dāng)信號真正稀疏時(shí)，矩陣的零空間性質(zhì)足以完整描述在什么條件下才可以重構(gòu)原始信號。然而，對于近似稀疏信號，需要對矩陣引入一些更為嚴(yán)格的條件，以確保零空間N(Φ)中既不包含稀疏的向量，也不包含近似稀疏的向量。更為嚴(yán)格的條件是約束等距條件(RestrictedIsometryProperty，RIP)。

定義3約束等距條件(RIP)：如果存在δK∈(0,1)，使得:

(3)

對所有的x∈∑K{x:‖x‖0≤K}都成立，則稱矩陣Φ滿足K階約束等距特性[17]。其中，δK稱為矩陣Φ的約束等距常數(shù)。

3　重構(gòu)算法與模型

重構(gòu)算法是壓縮感知模型求解的保證，需要考慮多種因素，如少量的測量值、測量噪聲和模型噪聲以及重構(gòu)穩(wěn)定性等。大量研究表明，重構(gòu)算法和模型設(shè)計(jì)多種多樣，不同的算法和模型在運(yùn)算時(shí)間、重構(gòu)精度和穩(wěn)定性等方面都有各自的特點(diǎn)。

3.1組合算法

組合算法由統(tǒng)計(jì)學(xué)、計(jì)算機(jī)科學(xué)領(lǐng)域的研究者開發(fā)，用于解決稀疏信號重構(gòu)問題[4]。其本質(zhì)思想是針對信號進(jìn)行高度結(jié)構(gòu)化采樣，由群測試快速獲得信號的支撐集。組合算法主要包括稀疏傅里葉描述法、鏈追蹤等。組合算法需要的測量次數(shù)較少，但是沒有給出確定性測量矩陣的約束條件，這為新的測量矩陣的提出帶來了困難。

3.2貝葉斯模型

(4)

貝葉斯模型提供了一個(gè)可以將壓縮感知和機(jī)器學(xué)習(xí)連接起來的橋梁。這一思想為更多類型的信號重構(gòu)算法及模型研究提供了一些有益思路。

3.3匹配追蹤算法

匹配追蹤算法又稱貪婪算法，其基本思想是通過逐步迭代來逼近待重構(gòu)稀疏信號的支撐集[7]。該算法的種類有很多，其中，匹配追蹤(MP)算法、正交匹配追蹤(OMP)算法能夠以極大的概率重構(gòu)原信號，但是缺乏相應(yīng)重構(gòu)正確性的保證。隨后改進(jìn)的算法有逐步匹配追蹤(StOMP)、子空間追蹤(SP)、壓縮匹配追蹤(CoOMP)和正則匹配追蹤(ROMP)等，在一定程度上兼顧重構(gòu)的通用性和復(fù)雜性，并提供了理論支撐。對于低維度的小尺度信號重構(gòu)，貪婪算法的速度快，但是對于含噪聲的大尺度重構(gòu)問題，該算法不具有魯棒性。

3.4凸優(yōu)化模型

目前，在壓縮感知問題求解中應(yīng)用最多的是凸優(yōu)化模型。其基本思想是采用凸函數(shù)代替l0范數(shù)，并利用凸優(yōu)化的方法求解。假設(shè)J(x)是凸的且促進(jìn)稀疏性的目標(biāo)函數(shù)，在信號x稀疏性的約束下，求解J(x)，使其很小。這類模型是在N空間中一個(gè)凸集中優(yōu)化未知變量x的凸函數(shù)J(x)。

基于信號的稀疏性，壓縮感知理論從M個(gè)測量值y=Φx中重構(gòu)出原始稀疏信號x∈￡N，其中，Φ∈￡M×N(M

(5)

其中‖·‖0表示零范數(shù)，是指非零元素的個(gè)數(shù)。由于l0范數(shù)的非凸性，不易求解，因此研究者將該模型轉(zhuǎn)化為易于求解的重構(gòu)模型，大致有以下四類。

3.4.1lp重構(gòu)模型

當(dāng)p=1時(shí)，CandèsE等[3]采用l1范數(shù)代替原來的l0范數(shù)，將重構(gòu)模型重寫為：

(6)

式(6)相應(yīng)的線性規(guī)劃問題被稱為基追蹤。為進(jìn)一步減小噪聲對模型的影響，CandèsE等[7]提出了加權(quán)最小l1模型，即：

(7)

對于0

(8)

3.4.2全變分重構(gòu)模型

相對于一維信號重構(gòu)的最小l1范數(shù)模型，考慮二維自然圖像，Candès E等[3]利用圖像離散梯度的稀疏性，提出了更適合自然圖像重構(gòu)的最小全變分模型，即：

minTV(x),s.t.y=Φx

(9)

然而，對于邊緣紋理信息豐富的區(qū)域，其梯度并非1-稀疏，單一的全變分正則項(xiàng)效果并不理想，會(huì)產(chǎn)生階梯效應(yīng)。針對這種非稀疏的梯度向量，結(jié)合各向同性與各向異性，LouY等[8]提出了加權(quán)的全變分模型，即：

(10)

3.4.3平滑l0范數(shù)重構(gòu)模型

(11)

3.4.4低秩重構(gòu)模型

圖像信息包含了大量的自相關(guān)結(jié)構(gòu)，具有高度結(jié)構(gòu)化的稀疏性和低秩性。利用這種非局部相似特性，Dong W等[12-13]提出了非局部低秩重構(gòu)模型：

(12)

其中：X=L+W；L是低秩矩陣；W是高斯噪聲矩陣;X是按照聚類思想將圖像分塊后生成的數(shù)據(jù)矩陣，用于體現(xiàn)圖像的自相關(guān)結(jié)構(gòu)。文獻(xiàn)[13]采用行列式代替秩，rank(L)=log det(L+εI)(ε是很小的正常數(shù)，I是單位矩陣)，以避免矩陣行列式為零。模型(12)可重寫為：

(13)

其中,η、λ均是平衡低秩項(xiàng)和保真項(xiàng)的正參數(shù)。

凸優(yōu)化模型有較強(qiáng)的重構(gòu)正確性，所需觀測的次數(shù)較少，但其最大的缺點(diǎn)在于重建速度慢，對于大尺度的重構(gòu)問題實(shí)現(xiàn)困難。因此，研究對測量值要求較少、計(jì)算復(fù)雜度低、適用大尺度且穩(wěn)健的重構(gòu)算法及模型，仍然是壓縮感知的關(guān)鍵問題。

4　壓縮成像應(yīng)用

壓縮感知理論為許多領(lǐng)域帶來了革新，在計(jì)算機(jī)科學(xué)、電子工程和信號處理等領(lǐng)域具有廣闊的應(yīng)用前景。

成像是一個(gè)傳統(tǒng)的信號處理領(lǐng)域，圖像在整個(gè)數(shù)字信號處理領(lǐng)域占有舉足輕重的地位，壓縮感知理論在成像領(lǐng)域得到了極大的認(rèn)可。RICE大學(xué)成功研制的單像素相機(jī)[20]成像靈活，光敏二極管量子效率達(dá)90%，能夠極大地降低圖像失真和噪聲，為低像素相機(jī)拍攝高質(zhì)量圖像提供了可能。激光雷達(dá)[21]取消了機(jī)械掃描裝置，可避免直接對原始信號的采樣，減輕構(gòu)建地面三維模型時(shí)數(shù)據(jù)處理的壓力，增加載荷靈活性。國內(nèi)的相關(guān)研究也在積極進(jìn)行中。醫(yī)學(xué)成像，尤其是核磁共振成像[22]，利用MR圖像在小波域的稀疏性和空間域的變分約束，通過高度欠采樣數(shù)據(jù)重構(gòu)原始圖像，將壓縮感知理論成功應(yīng)用于心臟成像、腦成像和快速三維血管造影等，大大提高了成像速度。

此外，壓縮感知理論還可應(yīng)用于模擬數(shù)字轉(zhuǎn)換、生物傳感、稀疏誤差糾錯(cuò)、信號檢測和分類以及地球物理數(shù)據(jù)分析等眾多領(lǐng)域。最新研究表明，基于自然成像的壓縮感知模型更具有實(shí)用價(jià)值[23]。隨著現(xiàn)代通信技術(shù)的飛速發(fā)展，壓縮感知理論必將大放光彩。

5　結(jié)　語

壓縮感知理論的提出不僅豐富了信號采樣和處理理論，也為其他相關(guān)領(lǐng)域的研究提供了新思路。2006年至今，經(jīng)過十年的研究發(fā)展，壓縮感知理論框架不斷完善。但是，不可否認(rèn)的是壓縮感知理論不具有普適性，如對于隨機(jī)信號或噪聲信號等非結(jié)構(gòu)信號，壓縮感知理論仍然存在不能克服的局限性。

壓縮感知理論具有旺盛的生命力，發(fā)展日新月異，對應(yīng)用數(shù)學(xué)、電子光學(xué)工程、信號處理等領(lǐng)域?qū)a(chǎn)生重要影響。今后的研究方向主要有以下幾個(gè)方面：

(1)設(shè)計(jì)性能更好的字典。稀疏字典適合人類視覺神經(jīng)系統(tǒng)，可充分利用圖像的先驗(yàn)信息，確保稀疏性，在減少測量的同時(shí)保證重構(gòu)精度。

(2)測量矩陣的構(gòu)造和優(yōu)化。測量矩陣與稀疏字典密切相關(guān)，應(yīng)統(tǒng)籌考慮，更重要的是滿足采樣成本低、存儲(chǔ)矩陣小等硬件易實(shí)現(xiàn)的特性要求。

(3)低秩流形符合圖像的本征結(jié)構(gòu)。結(jié)構(gòu)化稀疏有著優(yōu)異的重構(gòu)效果，低秩流形和結(jié)構(gòu)化字典相結(jié)合，重構(gòu)圖像將具有更豐富的結(jié)構(gòu)信息。

[1]DonohoDL.CompressedSensing[J].IEEETransactionsonInformationTheory, 2006, 52(4):1289-1306.

[2]CandèsE.CompressiveSampling[C]//ProceedingsofInternationalCongressofMathematiciansMadrid.Spain:EuropeanMathematicalSocietyPublishingHouse, 2006:1433-1452.

[3]CandèsE,RombergJ,TaoT.RobustUncertaintyPrinciples:ExactSignalReconstructionfromHighlyIncompleteFrequencyInformation[J].IEEETransactionsonInformationTheory, 2006, 52(2):489-509.

[4]GilbertAC,GuhaS,IndykP,etal.Near-optimalSparseFourierRepresentationsViaSampling[C]//Proceedingson34thAnnualACMSymposiumonTheoryofComputing.Canada:ACM, 2012:152-161.

[5]JiS,XueY,CarinL.BayesianCompressiveSensing[J].IEEETransactionsonSignalProcessing, 2008, 56(6):2346-2356.

[6]方紅, 楊海蓉. 貪婪算法與壓縮感知理論[J]. 自動(dòng)化學(xué)報(bào), 2011, 37(12):1413-1421.

[7]CandèsE,BraunN,WakinM.SparseSignalandImageRecoveryfromCompressiveSamples[C]//Proceedingsof4thIEEEInternationalSymposiumonBiomedicalImaging:fromNanotoMacro.Washington:IEEEE, 2007:976-979.

[8]LouY,YinP,HeQ,etal.ComputingSparseRepresentationinaHighlyCoherentDictionaryBasedonDifferenceofL1andL2 [J].JournalofScientificComputing, 2015, 64(1):178-196.

[9]ChartrandR.ExactReconstructionofSparseSignalsViaNonconvexMinimization[J].IEEESignalProcessingLetters, 2007, 14(10):707-710.

[10]MohimaniH,BabaiezadehM,JuttenC.AFastApproachforOvercompleteSparseDecompositionBasedonSmoothedL0Norm[J].IEEETransactionsonSignalProcessing, 2009, 57(1):289-301.

[11]MairalJ,BachF,PonceJ,etal.Non-localSparseModelsforImageRestoration[J].IEEEInternationalConferenceonComputerVision, 2009,30(2):2272 - 2279.

[12]DongW,LiX,ZhangL,etal.Sparsity-basedImageDenoisingViaDictionaryLearningandStructuralClustering[J].IEEEConferenceonComputerVision&PatternRecognition,2011,42(7):457-464.

[13]DongW,ShiG,LiX,etal.CompressiveSensingViaNonlocalLow-rankRegularization[J].IEEETransactionsonImageProcessingaPublicationoftheIEEESignalProcessingSociety, 2014, 23(8):3618-3632.

[14]HubelDH,WieselTN.ReceptiveFieldsofSingleNeuronsintheCat’sStriateCortex[J].JournalofPhysiology, 1959, 148(3):574-591.

[15]KondoS.CompressedSensingandRedundantDictionaries[J].InformationTheoryIEEETransactionson, 2008, 54(5):2210-2219.

[6]文再文,印臥濤,劉歆,等.壓縮感知和稀疏優(yōu)化簡介[J].運(yùn)籌學(xué)學(xué)報(bào), 2012, 16(3):49-64.

[17]MoQ,LiS.NewBoundsontheRestrictedIsometryConstant[J].Applied&ComputationalHarmonicAnalysis, 2011, 31(3):460-468.

[18]BaraniukR,DavenportM,DevoreR,etal.ASimpleProoftheRestrictedIsometryforRandomMatrices[J].ConstructiveApproximation, 2015, 28(3):253-263.

[19]李春雷, 高廣帥, 劉洲峰,等. 基于L0范數(shù)視覺顯著性的織物疵點(diǎn)檢測算法研究[J]. 中原工學(xué)院學(xué)報(bào), 2015,26(6):1-5.

[20]DuarteMF,DavenportMA,TakbarD,etal.Single-pixelImagingViaCompressiveSampling[J].IEEESignalProcessingMagazine, 2008, 25(2):83-91.

[21]HowlandGA,DixonPB,HowellJC.Photon-countingCompressiveSensingLaserRadarfor3DImaging.[J].AppliedOptics, 2011, 50(31):5917-5920.

[22]AkakayaM,BashaTA,GodduB,etal.Low-dimensional-structureSelf-learningandThresholding:RegularizationBeyondCompressedSensingforMRIReconstruction[J].MagneticResonanceinMedicineOfficialJournaloftheSocietyofMagneticResonanceinMedicine, 2011, 66(3):756-767.

[23]LiutkusA,MartinaD,PopoffS,etal.ImagingwithNature:CompressiveImagingUsingaMultiplyScatteringMedium[J].ScientificReports, 2013, 4(4):5552.

(責(zé)任編輯：王長通)

The Review of Image Reconstruction in Compressive Sensing

SONG Chang-ming, HUI Qing-lei

(Zhongyuan University of Technology, Zhengzhou 450007,China)

In this paper, compressive sensing is systematically studied from the sparse representation, compressive measurement and reconstruction algorithm, and then the theoretical frame and the latest developments of the image reconstruction model are introduced in detail based on probability and convex optimization etc. Some further research directions is put forward from dictionary learning and low-rank represent.

compressive sensing; image reconstruction; convex optimization; low rank

2016-05-26

河南省基礎(chǔ)與前沿技術(shù)研究項(xiàng)目(152300410226)；河南省高等學(xué)校重點(diǎn)科研項(xiàng)目(15A110045)

宋長明(1965-)，男，河南鄭州人，教授，博士，主要研究方向?yàn)槠⒎址匠碳捌鋺?yīng)用。

1671-6906(2016)04-0080-05

TN911.7

A

10.3969/j.issn.1671-6906.2016.04.017