壓縮感知技術(shù).doc

壓縮感知技術(shù)1. 壓縮感知概論壓縮感知（Compressive Sensing, or Compressed Sampling，簡(jiǎn)稱CS），是近幾年流行起來(lái)的一個(gè)介于數(shù)學(xué)和信息科學(xué)的新方向，由Candes、Terres Tao等人提出，挑戰(zhàn)傳統(tǒng)的采樣編碼技術(shù)，即Nyquist采樣定理。信號(hào)采樣是模擬的物理世界通向數(shù)字的信息世界之必備手段。多年來(lái)，指導(dǎo)信號(hào)采樣的理論基礎(chǔ)一直是著名的Nyquist 采樣定理。定理指出，只有當(dāng)采樣速率達(dá)到信號(hào)帶寬的兩倍以上時(shí)，才能由采樣信號(hào)精確重建原始信號(hào)?？梢?jiàn)，帶寬是Nyquist 采樣定理對(duì)采樣的本質(zhì)要求。但是，對(duì)于超寬帶通信和信號(hào)處理、核磁共振成像、雷達(dá)遙感成像、傳感器網(wǎng)絡(luò)等實(shí)際應(yīng)用，信號(hào)的帶寬變得越來(lái)越大，人們對(duì)信號(hào)的采樣速率、傳輸速度和存儲(chǔ)空間的要求也變得越來(lái)越高。為了緩解對(duì)信號(hào)傳輸速度和存儲(chǔ)空間的壓力，當(dāng)前常見(jiàn)的解決方案是信號(hào)壓縮，如基于小波變換的JPEG2000 標(biāo)準(zhǔn)。但是，信號(hào)壓縮實(shí)際上是一種嚴(yán)重的資源浪費(fèi)，因?yàn)榇罅康牟蓸訑?shù)據(jù)在壓縮過(guò)程中被丟棄了，而它們對(duì)于信號(hào)來(lái)說(shuō)是不重要的或者只是冗余信息。從這個(gè)意義而言，我們得到以下結(jié)論：帶寬不能本質(zhì)地表達(dá)信號(hào)的信息，基于信號(hào)帶寬的Nyquist 采樣機(jī)制是冗余的或者說(shuō)是非信息的。下圖是一個(gè)傳統(tǒng)方法采樣壓縮過(guò)程。 一個(gè)很自然的問(wèn)題是：是否存在或者能否提出一種基于信息的采樣理論框架，使得采樣過(guò)程既能保持信號(hào)信息，又能只需遠(yuǎn)少于Nyquist 采樣定理所要求的采樣數(shù)目就可精確或近似精確重建原始信號(hào)？簡(jiǎn)言之，能否同時(shí)實(shí)現(xiàn)信號(hào)的采樣與壓縮？與信號(hào)帶寬相比，稀疏性能夠直觀地而且相對(duì)本質(zhì)地表達(dá)信號(hào)的信息。事實(shí)上，稀疏性在現(xiàn)代信號(hào)處理領(lǐng)域一直起著至關(guān)重要的作用，例如基于稀疏性的逼近、基于稀疏性的估計(jì)、基于稀疏性的壓縮、基于稀疏性的降維等。不同于Nyquist 信號(hào)采樣機(jī)制。Cands、Tao、Romberg、Donoho 等人，近年來(lái)基于信號(hào)稀疏性提出一種稱為壓縮感知(compressed sensing)或壓縮采樣(compressivesampling)的新興采樣理論，成功實(shí)現(xiàn)了信號(hào)的同時(shí)采樣與壓縮。下面是一個(gè)壓縮感知的理論框架。簡(jiǎn)單地說(shuō)，壓縮感知理論指出：當(dāng)信號(hào)在某個(gè)變換域是稀疏的或可壓縮的，可以利用與變換矩陣非相干的測(cè)量矩陣將變換系數(shù)線性投影為低維觀測(cè)向量，同時(shí)這種投影保持了重建信號(hào)所需的信息，通過(guò)進(jìn)一步求解稀疏最優(yōu)化問(wèn)題就能夠從低維觀測(cè)向量精確地或高概率精確地重建原始高維信號(hào)。在該理論框架下，采樣速率不再取決于信號(hào)的帶寬，而在很大程度上取決于兩個(gè)基本準(zhǔn)則：稀疏性和非相干性，或者稀疏性和等距約束性。壓縮感知理論為信號(hào)采集技術(shù)帶來(lái)了革命性的突破，它采用非自適應(yīng)線性投影來(lái)保持信號(hào)的原始結(jié)構(gòu)，以遠(yuǎn)低于奈奎斯特頻率對(duì)信號(hào)進(jìn)行采樣，通過(guò)數(shù)值最優(yōu)化問(wèn)題準(zhǔn)確重構(gòu)出原始信號(hào)。當(dāng)前，壓縮感知理論主要涉及三個(gè)核心問(wèn)題：(1) 具有稀疏表示能力的過(guò)完備字典設(shè)計(jì)；(2) 滿足非相干性或等距約束性準(zhǔn)則的測(cè)量矩陣設(shè)計(jì)；(3) 快速魯棒的信號(hào)重建算法設(shè)計(jì)。目前，學(xué)者們已經(jīng)在模擬-信息采樣、合成孔徑雷達(dá)成像、遙感成像、核磁共振成像、深空探測(cè)成像、無(wú)線傳感器網(wǎng)絡(luò)、信源編碼、人臉識(shí)別、語(yǔ)音識(shí)別、探地雷達(dá)成像等諸多領(lǐng)域?qū)嚎s感知展開了廣泛的應(yīng)用研究。壓縮感知理論的相關(guān)工作尚有很多亟待解決的問(wèn)題，尤其是國(guó)內(nèi)關(guān)于壓縮感知理論的基礎(chǔ)研究基本處于空白。為此，本文圍繞稀疏字典設(shè)計(jì)、測(cè)量矩陣設(shè)計(jì)、重建算法設(shè)計(jì)三個(gè)核心問(wèn)題，對(duì)壓縮感知的基本理論和實(shí)現(xiàn)方法進(jìn)行了系統(tǒng)闡述，同時(shí)指出了壓縮感知有待解決的若干理論推廣和關(guān)鍵技術(shù)。在壓縮感知理論中，采樣速率不再取決于信號(hào)帶寬，而在很大程度上取決于兩個(gè)基本準(zhǔn)則，即稀疏性和非相干性，或者，稀疏性和等距約束性。2壓縮感知的核心問(wèn)題2.1 壓縮感知的稀疏字典設(shè)計(jì)信號(hào)的稀疏性或可壓縮性是壓縮感知的重要前提和理論基礎(chǔ)。因此，壓縮感知理論首要的研究任務(wù)就是信號(hào)的稀疏表示研究。稀疏字典設(shè)計(jì)是壓縮感知的核心問(wèn)題之一，在于：只有選擇合適的稀疏字典，才能保證表示系數(shù)具有足夠的稀疏性或衰減性，才能在減少壓縮測(cè)量的同時(shí)保證壓縮感知的重建精度。目前，稀疏字典主要包括正交基字典、緊框架字典、過(guò)完備字典。正交基字典主要是計(jì)算調(diào)和分析中的正交變換系統(tǒng)，如Wavelet 變換；緊框架字典主要是以Ridgelet、CurveletBandletContourlet 為代表的圖像幾何多分辨率表示或者稱Beyond Wavelet 變換；在過(guò)完備字典中，用于稀疏表示的不再是“單一基”，而是通過(guò)構(gòu)造或?qū)W習(xí)得到的冗余原子庫(kù)，通過(guò)提高變換系統(tǒng)的冗余性增強(qiáng)信號(hào)逼近的靈活性，提高對(duì)圖像等復(fù)雜信號(hào)的稀疏表示能力。1993 年，Mallat 和Zhang首次提出了基于過(guò)完備字典的稀疏分解思想，指出了過(guò)完備字典對(duì)于信號(hào)稀疏表示的必要性和重要性?；谶^(guò)完備字典的稀疏分解依然是當(dāng)前信號(hào)稀疏表示研究的熱點(diǎn)和難點(diǎn)。過(guò)完備字典由稱為過(guò)完備原子庫(kù)的冗余系統(tǒng)構(gòu)成，原子不必再是“單一基”函數(shù)。過(guò)完備字典的構(gòu)造或?qū)W習(xí)應(yīng)遵循基本準(zhǔn)則：字典中的原子應(yīng)能盡量匹配信號(hào)本身固有的各種不同特征。在這種準(zhǔn)則下，稀疏字典必定是非正交的且是冗余的，正是通過(guò)增加原子個(gè)數(shù)提高變換系統(tǒng)的冗余性來(lái)增強(qiáng)信號(hào)逼近的靈活性，進(jìn)而提高圖像等復(fù)雜信號(hào)的稀疏表示能力。當(dāng)字典中的原子個(gè)數(shù)大于信號(hào)維數(shù)N且包含N個(gè)線性無(wú)關(guān)向量張成整個(gè)信號(hào)空間時(shí)，字典稱為過(guò)完備的。基于過(guò)完備字典的稀疏分解使得信號(hào)能量集中在極少數(shù)原子上，正是這些具有非零系數(shù)的原子匹配了信號(hào)的不同特征。設(shè)計(jì)適合特定信號(hào)的過(guò)完備字典，目前主要包括人工構(gòu)造和訓(xùn)練學(xué)習(xí)兩大類方法?；跇?gòu)造方法的過(guò)完備字典設(shè)計(jì)是主流，主要包括：Wavelet 和局部Cosine 函數(shù)的級(jí)聯(lián)、各向同性的Gabor 字典、各向異性的Refinement-Gaussian 混合字典、各向異性的Gabor 感知多成份字典等。基于學(xué)習(xí)的過(guò)完備字典是過(guò)完備字典設(shè)計(jì)問(wèn)題的難點(diǎn)和熱點(diǎn)，涌現(xiàn)的典型學(xué)習(xí)算法主要有：其中，K-SVD 這類學(xué)習(xí)算法具有代表性，稀疏表示效果好，計(jì)算復(fù)雜度低，但不足之處是缺乏嚴(yán)格的理論支撐。基于過(guò)完備字典的稀疏表示的另一個(gè)方面是設(shè)計(jì)快速有效的稀疏分解算法。由于壓縮感知信號(hào)重建問(wèn)題追求的同樣是稀疏解，因此某種程度上這里的稀疏分解算法可以推廣應(yīng)用到壓縮感知問(wèn)題。為了避免重復(fù)，稀疏分解的相關(guān)算法將在下文予以介紹。國(guó)內(nèi)關(guān)于稀疏表示也展開了廣泛的理論和應(yīng)用研究。2.2 壓縮感知的測(cè)量矩陣設(shè)計(jì)測(cè)量矩陣設(shè)計(jì)是壓縮采樣理論的核心，直接決定了壓縮采樣理論是否能夠成功實(shí)現(xiàn)。由于壓縮測(cè)量個(gè)數(shù)和信號(hào)重建精度以及信號(hào)稀疏性有著密切的聯(lián)系，因此測(cè)量矩陣的設(shè)計(jì)應(yīng)該與稀疏字典的設(shè)計(jì)統(tǒng)籌考慮。從原理的角度看，測(cè)量矩陣的設(shè)計(jì)要以非相干性或等距約束性為基本準(zhǔn)則，既要減少壓縮測(cè)量個(gè)數(shù)又要確保壓縮感知的信號(hào)重建精度。從技術(shù)的角度看，測(cè)量矩陣的設(shè)計(jì)包括兩個(gè)方面：一是測(cè)量矩陣的元素，Cands 等人給出了隨機(jī)生成的設(shè)計(jì)策略；二是測(cè)量矩陣的維數(shù)，壓縮測(cè)量個(gè)數(shù)M 與信號(hào)稀疏性K 和信號(hào)長(zhǎng)度N 應(yīng)該滿足一定的關(guān)系。主要測(cè)量?jī)?nèi)容包括基于非相干性準(zhǔn)則的測(cè)量和基于等距約束性準(zhǔn)則的測(cè)量。2.3 壓縮感知的重建算法設(shè)計(jì)作為不適定的數(shù)學(xué)反問(wèn)題，壓縮感知信號(hào)重建在理論上存在著無(wú)數(shù)多個(gè)可行解。但是，上文壓縮感知相關(guān)定理指出，非相干性或等距約束性準(zhǔn)則為近似精確或精確重建提供了理論上的保證。壓縮感知的第三個(gè)核心問(wèn)題是重建算法的設(shè)計(jì)。重建算法的設(shè)計(jì)應(yīng)該遵循如下基本準(zhǔn)則：算法應(yīng)該利用盡可能少的壓縮測(cè)量快速、穩(wěn)定、精確或近似精確地重建原始信號(hào)。為此，學(xué)者們陸續(xù)提出了多種近似等價(jià)的信號(hào)重建算法。簡(jiǎn)單地說(shuō)，主要包括三類方法：松弛方法、貪婪方法、非凸方法。需要指出的是，由于稀疏表示追求的同樣是稀疏解，因此這三類算法也適用于信號(hào)的稀疏表示問(wèn)題。松弛方法最典型的就是基于范數(shù)最小化。貪婪方法，基本思想是通過(guò)每次迭代時(shí)進(jìn)行局部最優(yōu)化尋找各個(gè)非零系數(shù)。非凸方法。該類方法所需的壓縮測(cè)量個(gè)數(shù)、計(jì)算復(fù)雜度、信號(hào)重構(gòu)精度總體上介于松弛和貪婪兩類方法之間。3. 應(yīng)用直接信息采樣特性使得壓縮感知理論具有巨大吸引力和應(yīng)用前景。隨之出現(xiàn)的是相關(guān)的理論完善和實(shí)踐成果。應(yīng)用領(lǐng)域已涉及到眾多領(lǐng)域。如：CS雷達(dá)、DCS（Distributed Compressed Sensing）理論、無(wú)線傳感網(wǎng)絡(luò)、圖像采集技術(shù)的開發(fā)、醫(yī)學(xué)圖像處理、生物傳感、光譜分析、超譜圖像處理及遙感圖像處理等。在成像方面，壓縮感知理論的出現(xiàn)激起了人們研究新型傳感器的熱情。壓縮感知的采樣對(duì)昂貴的成像器件的設(shè)計(jì)產(chǎn)生重大影響。在地震勘探成像和核磁共振成像中，對(duì)目標(biāo)信號(hào)有望采用少量的隨機(jī)觀測(cè)次數(shù)就能獲得高精度重構(gòu)，取代傳統(tǒng)數(shù)碼相機(jī)拍照時(shí)采集大量像素的一種新型單像素CS相機(jī)已經(jīng)得到論證，美國(guó)Rice大學(xué)也已經(jīng)研制出“單像素相機(jī)”，如下圖。該相機(jī)是一種全新的相機(jī)結(jié)構(gòu)，使用數(shù)字微鏡陣列完成圖像在偽隨機(jī)二值模型上的線性投影的光學(xué)計(jì)算。塔克利用單一的信號(hào)光子檢測(cè)器采樣得到比圖像像素點(diǎn)數(shù)少得多的點(diǎn)恢復(fù)得到一幅圖像，并具有對(duì)圖像波長(zhǎng)自適應(yīng)的能力，這種自適應(yīng)能歷史傳統(tǒng)的CCD和CMOS成像器件所不具備的。 在寬帶無(wú)線頻率信號(hào)分析中，由于目前A/D轉(zhuǎn)換技術(shù)的限制，可以用遠(yuǎn)低于奈奎斯特采樣頻率的速率采集信號(hào)。在X射線和生物醫(yī)學(xué)中，可以通過(guò)采集遠(yuǎn)少于位置像素點(diǎn)數(shù)的觀測(cè)樣本來(lái)獲取感興趣的圖像信息?；虮磉_(dá)也開始使用壓縮感知理論，試圖從少量的觀測(cè)樣本中，例如幾十種來(lái)推斷成千上萬(wàn)種基因的表達(dá)。4總結(jié)壓縮感知最初由美國(guó)威斯康星大學(xué)的Mistretta 教授等人提出：能否通過(guò)減少采樣數(shù)據(jù)縮短核磁共振成像的時(shí)間并且能夠利用這些有限量的數(shù)據(jù)重建原始圖像。對(duì)于這個(gè)問(wèn)題，威斯康星大學(xué)的研究人員最初采用傳統(tǒng)圖像重建算法進(jìn)行實(shí)驗(yàn)。結(jié)果顯示，重建圖像的分辨率不僅低，而且邊緣模糊，人工效應(yīng)也很明顯。完全出乎意料地，加利福尼亞科技學(xué)院的Cands 教授及其團(tuán)隊(duì)僅僅基于懲罰的思想完美重建出了原始圖像，同時(shí)證明了：只需隨機(jī)選取信號(hào)M 2K個(gè)Fourier 表示系數(shù)，就能唯一精確重建原始圖像。正是這個(gè)意外的發(fā)現(xiàn)觸發(fā)了壓縮感知理論的思想來(lái)源。壓縮感知的誕生，堪稱世紀(jì)之作。在這里，向奠定壓縮感知基礎(chǔ)理論的三位科學(xué)家表示致敬，他們分別是：加利福尼亞科技學(xué)院應(yīng)用與計(jì)算數(shù)學(xué)系教授Emmanuel J. Cands、加利福尼亞大學(xué)數(shù)學(xué)系教授Terence Tao、喬治亞科技學(xué)院電子與計(jì)算機(jī)工程系的Justin Romberg！壓縮感知理論自誕生之日就有著極強(qiáng)的生命力，已經(jīng)對(duì)信號(hào)處理、理論數(shù)學(xué)、計(jì)算數(shù)學(xué)、計(jì)算機(jī)科學(xué)、信息論、概率論、電子工程、光學(xué)工程等諸多領(lǐng)域產(chǎn)生了重要影響。壓縮感知的新穎性在于：只需遠(yuǎn)少于傳統(tǒng)Nyquist 采樣定理所要求的采樣數(shù)就能精確或高概率精確重建原始信號(hào)。采樣速率不再取決于信號(hào)帶寬，而在很大程度上取決于稀疏性和非相干性準(zhǔn)則，或者稀疏性和等距約束性準(zhǔn)則。本文圍繞壓縮感知的稀疏字典設(shè)計(jì)、測(cè)量矩陣設(shè)計(jì)、重建算法設(shè)計(jì)三個(gè)核心問(wèn)題，對(duì)其基本理論和主要方法進(jìn)行了系統(tǒng)闡述。同時(shí)，在基礎(chǔ)理論和實(shí)現(xiàn)方法兩個(gè)層面提出了壓縮感知有待解決的若干理論問(wèn)題與關(guān)鍵技術(shù)，具體包括：(1) 基于非正交稀疏字典的壓縮感知信號(hào)重建理論；(2) 自然圖像的自適應(yīng)壓縮感知信號(hào)重建理論；(3) 基于學(xué)習(xí)的自然圖像過(guò)完備字典設(shè)計(jì)；(4) 硬件易實(shí)現(xiàn)的確定性測(cè)量矩陣設(shè)計(jì)；(5) 噪聲情形大尺度問(wèn)題的快速魯棒重建算法設(shè)計(jì)。總之，不管是基礎(chǔ)理論還是重建算法，都必須以把壓縮感知理論推向?qū)嵱脼闇?zhǔn)則。至于壓縮感知理論能否應(yīng)用于某種實(shí)際領(lǐng)域，要看是否有將大量信息蘊(yùn)含于少量采樣數(shù)據(jù)的迫切需要，例如：提高應(yīng)用系統(tǒng)的性能、縮短數(shù)據(jù)獲取的時(shí)間、降低數(shù)據(jù)獲取的耗能、減少數(shù)據(jù)的存儲(chǔ)空間、提高數(shù)據(jù)的傳輸速度等等。最后，需要指出的是：壓縮感知理論不是普適的。對(duì)于隨機(jī)信號(hào)或者噪聲信號(hào)等非結(jié)構(gòu)性的信號(hào)，壓縮感知理論肯定不適用。特別地，對(duì)于某些實(shí)際應(yīng)用，Nyquist 采樣還是首選有效的方法，因?yàn)槟壳皦嚎s感知理論可能存在某些暫時(shí)不能解釋也不能克服的局限性。參考文獻(xiàn)1