基于壓縮感知的正交匹配算法圖像重建_畢業(yè)設(shè)計(jì)論文

1、基于壓縮感知的正交匹配算法圖像重建摘要：壓縮感知理論是由Donoho和Candes提出的一種充分利用信號(hào)稀疏性的全新的信號(hào)采樣理論。該理論說(shuō)明，用遠(yuǎn)低于Nyquist采樣定理要求的頻率對(duì)信號(hào)進(jìn)行采樣也能實(shí)現(xiàn)信號(hào)的精確重構(gòu)。該理論突破了傳統(tǒng)的以Nyquist定理為基準(zhǔn)的信號(hào)處理方法，實(shí)現(xiàn)了在獲取數(shù)據(jù)的同時(shí)對(duì)其進(jìn)行適當(dāng)?shù)膲嚎s，克服了采樣數(shù)據(jù)量大，采樣時(shí)間長(zhǎng)及數(shù)據(jù)存儲(chǔ)空間浪費(fèi)嚴(yán)重的問(wèn)題，因此進(jìn)一步降低了信號(hào)處理的時(shí)間和器件本錢(qián)。壓縮感知理論有三個(gè)核心方面：1稀疏變換，即對(duì)一個(gè)非稀疏的信號(hào)，找到一個(gè)適宜的正交基使該信號(hào)在它上可以稀疏表示；2測(cè)量矩陣，與變換基不相干且平穩(wěn)的矩陣；3重構(gòu)算法，利用數(shù)學(xué)算法

2、完成對(duì)信號(hào)的精確重構(gòu)，該過(guò)程可看為求解一個(gè)優(yōu)化問(wèn)題。本文介紹了主要介紹了壓縮感知原理和目前最為成熟的壓縮感知重建算法正交匹配追蹤算法，通過(guò)MATLAB平臺(tái)設(shè)計(jì)實(shí)現(xiàn)了根本的正交匹配追蹤算法，對(duì)一維、二維信號(hào)進(jìn)行了重建仿真。關(guān)鍵詞：壓縮感知；稀疏變換；正交匹配；圖像重建Based On Compressed Sensing Of Orthogonal Matching Algorithm Image RecoveryAbstract：Compressed sensing is a novel sampling theory which is proposed by Donoho and Cands

3、. This theory is under the condition that the signal is compressible or sparse. In this case, using far less than the required sampling frequency of the Nyquist theory to sample the signal is able to accurately reconstruct the signal.Compressed theory breaks though the traditional Nyquist sampling t

4、heory, which overcomes a lot of problems such as a great number of sampling data, time wasting, data storage space wasting and so on. As a result, it reduces signal processing cost and device cost.The compressed theory has three key sides: (1) Sparse transformation, for a non- sparse signal, we need

5、 to find a proper orthogonal basis on which the signal has a sparse representation; (2) Observation matrix, it is irrelevant with the orthogonal basis; (3) reconstruction algorithms, using a reconstruction algorithm to ensure the accuracy of the signal reconstruction, the whole process can be consid

6、ered as the solve to a optimization problem.This paper introduces CS and most mature compression perception algorithm at present-Orthogonal matching algorithm. Through the MATLAB design realize basic orthogonal matching algorithms, Through the MATLAB design realize basic orthogonal matching algorith

7、m of one-dimensional, two-dimensional signal processing simulation.Key words：Compressed sensing; Sparse transform; Orthogonal matching; Image recovery.目 錄 TOC o 1-3 u 第一章 緒論 PAGEREF _Toc357415638 h 21.1選題的背景及意義 PAGEREF _Toc357415639 h 21.2本課題在國(guó)內(nèi)外的開(kāi)展現(xiàn)狀 PAGEREF _Toc357415640 h 21.3 本論文的結(jié)構(gòu)安排 PAGEREF _T

8、oc357415641 h 3第二章 壓縮感知理論相關(guān)知識(shí) PAGEREF _Toc357415642 h 42.1壓縮感知理論框架 PAGEREF _Toc357415643 h 42.2壓縮感知的根本理論及核心問(wèn)題 PAGEREF _Toc357415644 h 52.2.1 信號(hào)的稀疏表示 PAGEREF _Toc357415645 h 62.2.2 信號(hào)的觀(guān)測(cè)矩陣 PAGEREF _Toc357415646 h 82.2.3 信號(hào)重構(gòu) PAGEREF _Toc357415647 h 92.3.壓縮感知的應(yīng)用 PAGEREF _Toc357415648 h 112.4 壓縮感知有待研究的

9、幾個(gè)問(wèn)題 PAGEREF _Toc357415649 h 13第三章 正交匹配追蹤重建算法 PAGEREF _Toc357415650 h 163.1最小L0范數(shù)模型 PAGEREF _Toc357415651 h 163.2匹配追蹤算法 PAGEREF _Toc357415652 h 163.3正交匹配追蹤算法(OMP) PAGEREF _Toc357415653 h 173.3.1 OMP算法原理 PAGEREF _Toc357415654 h 173.3.2 OMP算法實(shí)現(xiàn)步驟 PAGEREF _Toc357415655 h 173.3.3 OMP算法的Matlab語(yǔ)言實(shí)現(xiàn) PAGERE

10、F _Toc357415656 h 17第四章 基于MATLAB的壓縮感知圖像重建仿真 PAGEREF _Toc357415657 h 204.1不同采樣率下的仿真結(jié)果 PAGEREF _Toc357415658 h 20一維信號(hào)在不同采樣率下的OMP仿真 PAGEREF _Toc357415659 h 20二維信號(hào)在不同采樣率下的OMP仿真 PAGEREF _Toc357415660 h 224.2OMP算法與多種壓縮感知算法的仿真比擬 PAGEREF _Toc357415661 h 244.3結(jié)論 PAGEREF _Toc357415662 h 26結(jié)束語(yǔ) PAGEREF _Toc3574

11、15663 h 27致謝 PAGEREF _Toc357415664 h 28參考文獻(xiàn) PAGEREF _Toc357415665 h 29附錄一 源程序清單 PAGEREF _Toc357415666 h 30附錄二 英文文獻(xiàn)翻譯 PAGEREF _Toc357415667 h 37第一章 緒論1.1選題的背景及意義眾所周知，傳統(tǒng)的信號(hào)采樣以奈奎斯特Nyquist采樣定理為根底。為了不喪失信號(hào)的信息，精確重構(gòu)信號(hào)，在獲取信號(hào)時(shí)，采樣頻率要大于信號(hào)中最高頻率的兩倍。但是隨著各種信號(hào)處理系統(tǒng)獲取能力的不斷增強(qiáng)，需要后期處理的數(shù)據(jù)量也快速增加，奈奎斯特定理的局限性給系統(tǒng)的處理能力提出了更高的要求，

12、同時(shí)也給相應(yīng)的硬件設(shè)施的設(shè)計(jì)帶來(lái)了極大的挑戰(zhàn)。如何高效處理這些數(shù)據(jù)并且最大限度的節(jié)省存儲(chǔ)空間及傳輸本錢(qián)已成為目前信息領(lǐng)域進(jìn)一步向前開(kāi)展的主要瓶頸之一。實(shí)際上，奈奎斯特采樣定理是信號(hào)精確重構(gòu)的充分條件而不是必要條件，奈奎斯特采樣定理并不是唯一、最優(yōu)的采樣理論。因此研究如何突破以奈奎斯特采樣定理為根底的信息的提取、處理、融合、存儲(chǔ)、及傳輸是推動(dòng)信息領(lǐng)域開(kāi)展的關(guān)鍵。在2004年Donoho等人針對(duì)稀疏性信號(hào)，提出了壓縮感知Compressive sensing,簡(jiǎn)稱(chēng)CS理論。在隨后的幾年間該理論迅速開(kāi)展，為解決上述問(wèn)題奠定了根底。與傳統(tǒng)信號(hào)處理方式不同，壓縮感知理論以空間變換為根底，隨機(jī)觀(guān)測(cè)矩陣作為

13、手段，優(yōu)化求解作為恢復(fù)信號(hào)的方法。壓縮感知理論在獲取信號(hào)的同時(shí)對(duì)數(shù)據(jù)進(jìn)行適當(dāng)?shù)膲嚎s，其采樣頻率低于奈奎斯特采樣頻率，減少了采樣數(shù)據(jù)，節(jié)省了存儲(chǔ)空間，同時(shí)又包含了足夠的信息量，能通過(guò)適宜的重建算法對(duì)特定的圖像或者信號(hào)進(jìn)行精確重構(gòu)。它將傳統(tǒng)的數(shù)據(jù)采集和壓縮合二為一，并且不需要復(fù)雜的數(shù)據(jù)編碼算法，非常適合于要求采用小型器件的實(shí)現(xiàn)場(chǎng)合。信號(hào)的稀疏重建與壓縮感知理論有重大的實(shí)用價(jià)值和應(yīng)用前景，已經(jīng)成為信號(hào)領(lǐng)域中一個(gè)新的研究方向1。1.2本課題在國(guó)內(nèi)外的開(kāi)展現(xiàn)狀1國(guó)外研究狀況及開(kāi)展趨勢(shì)目前，CS理論與應(yīng)用研究正在如火如荼地進(jìn)行：在美國(guó)、歐洲等許多國(guó)家的知名大學(xué)如麻省理工學(xué)院、萊斯大學(xué)、斯坦福大學(xué)、杜克大學(xué)

14、等都成立了專(zhuān)門(mén)課題組對(duì)CS進(jìn)行研究；2021年，貝爾實(shí)驗(yàn)室,Intel,Google等知名公司也開(kāi)始組織研究CS；2021年,美國(guó)空軍實(shí)驗(yàn)室和杜克大學(xué)聯(lián)合召開(kāi)了CS研討會(huì)，美國(guó)國(guó)防先期研究方案署(DARPA)和國(guó)家地理空間情報(bào)局(NGA)等政府部門(mén)成員與數(shù)學(xué)、信號(hào)處理、微波遙感等領(lǐng)域的專(zhuān)家共同探討了CS應(yīng)用中的關(guān)鍵問(wèn)題；第二次以?壓縮感知和高維數(shù)據(jù)分析?為主題的研討會(huì)也將在2021年的7月26至28日在杜克大學(xué)召開(kāi)2。2國(guó)內(nèi)研究狀況及開(kāi)展趨勢(shì)在國(guó)內(nèi)，一些高校和科研機(jī)構(gòu)也開(kāi)始跟蹤C(jī)S的研究,如清華大學(xué)、中科院電子所、西安交通大學(xué)和西安電子科技大學(xué)等。自從2006年CS的提出，在IEEE的信號(hào)處理

15、匯刊、信號(hào)處理快報(bào)匯刊、信號(hào)處理雜志、信息論匯刊等國(guó)際知名期刊上開(kāi)始涌現(xiàn)出上百篇關(guān)于CS理論與應(yīng)用方面的文獻(xiàn)。2021年，IEEE Journal of Selected Topics in Signal Processing專(zhuān)門(mén)出版了一期關(guān)于CS的專(zhuān)刊，促進(jìn)了CS理論在各個(gè)領(lǐng)域應(yīng)用成果的交流。2021年4月，第一本關(guān)于CS的專(zhuān)著?Compressed Sensing: Theory and Applications?出版，不僅系統(tǒng)的介紹了CS的概念，而且聚集了世界各國(guó)學(xué)者在CS理論和應(yīng)用上的觀(guān)點(diǎn)和成功范例。國(guó)家自然科學(xué)基金委也自2021年起資助了多項(xiàng)壓縮感知方法的研究，涉及認(rèn)知無(wú)線(xiàn)電、雷達(dá)成

16、像、信號(hào)稀疏表示、多媒體編碼、人臉識(shí)別等領(lǐng)域。1.3 本論文的結(jié)構(gòu)安排本文在對(duì)壓縮感知理論以及現(xiàn)有的重構(gòu)算法進(jìn)行系統(tǒng)的研究之后，圍繞正交匹配追蹤重建算法展開(kāi)研究來(lái)實(shí)現(xiàn)信號(hào)的重建，基于上述工作，本文內(nèi)容分為四章，具體結(jié)構(gòu)安排如下：第一章：緒論。首先介紹了壓縮感知理論的研究背景及意義，然后介紹了國(guó)內(nèi)外研究背景和現(xiàn)狀，最后整理出全文內(nèi)容的結(jié)構(gòu)安排。第二章：壓縮感知理論相關(guān)知識(shí)。首先介紹了壓縮感知的框架，進(jìn)而對(duì)信號(hào)的稀疏變換、觀(guān)測(cè)矩陣的設(shè)計(jì)以及信號(hào)的重構(gòu)三個(gè)主要方面的內(nèi)容展開(kāi)進(jìn)一步詳述，最后詳細(xì)介紹了壓縮感知理論在不同領(lǐng)域的應(yīng)用及有待解決的幾個(gè)問(wèn)題。第三章：正交匹配追蹤重建算法。這一章著重分析了正交匹

17、配追蹤算法的原理、實(shí)現(xiàn)步驟和Matlab的語(yǔ)言實(shí)現(xiàn)。第四章：基于MATLAB的壓縮感知圖像重建仿真。首先介紹了OMP算法的思想以及算法步驟，然后再matlab上進(jìn)行試驗(yàn)仿真，得出實(shí)驗(yàn)數(shù)據(jù)。最后將OMP算法與其他算法進(jìn)行比擬研究做出總結(jié)分析。第二章 壓縮感知理論相關(guān)知識(shí)2.1壓縮感知理論框架傳統(tǒng)的信號(hào)采集、編解碼過(guò)程如圖2.l所示。編碼端先對(duì)信號(hào)進(jìn)行采樣，再對(duì)所有采樣值進(jìn)行變換，并將其中重要系數(shù)的幅度和位置進(jìn)行編碼，最后將編碼值進(jìn)行存儲(chǔ)或傳輸：信號(hào)的解碼過(guò)程僅僅是編碼的逆過(guò)程，接收的信號(hào)經(jīng)解壓縮、反變換后得到恢復(fù)信號(hào)。采用這種傳統(tǒng)的編解碼方法，由于信號(hào)的采樣速率不得低于信號(hào)帶寬的2倍，使得硬件系

18、統(tǒng)面臨著很大的采樣速率的壓力。此外在壓縮編碼過(guò)程中，大量變換計(jì)算得到的小系數(shù)被丟棄，造成了數(shù)據(jù)計(jì)算和內(nèi)存資源的浪費(fèi)。圖2.1傳統(tǒng)編解碼理論的框圖壓縮感知理論對(duì)信號(hào)的采樣、壓縮編碼發(fā)生在同一個(gè)步驟如下列圖2.2所示，利用信號(hào)的稀疏性，以遠(yuǎn)低于Nyquist采樣率的速率對(duì)信號(hào)進(jìn)行非自適應(yīng)的測(cè)量編碼。測(cè)量值并非信號(hào)本身，而是從高維到低維的投影值，從數(shù)學(xué)角度看，每個(gè)測(cè)量值是傳統(tǒng)理論下的每個(gè)樣本信號(hào)的組合函數(shù)，即一個(gè)測(cè)量值已經(jīng)包含了所有樣本信號(hào)的少量信息。解碼過(guò)程不是編碼的簡(jiǎn)單逆過(guò)程，而是在盲源別離中的求逆思想下利用信號(hào)稀疏分解中已有的重構(gòu)方法在概率意義上實(shí)現(xiàn)信號(hào)的精確重構(gòu)或者一定誤差下的近似重構(gòu)。解碼

19、所需測(cè)量值的數(shù)目遠(yuǎn)小于傳統(tǒng)理論下的樣本數(shù)。圖2.2縮感知理論的編解碼框圖2.2壓縮感知的根本理論及核心問(wèn)題壓縮感知，也被稱(chēng)為壓縮傳感或壓縮采樣，是一種利用稀疏的或可壓縮的信號(hào)進(jìn)行信號(hào)重構(gòu)的技術(shù)3。或者可以說(shuō)是信號(hào)在采樣的同時(shí)被壓縮，從而在很大程度上降低了采樣率。壓縮感知跳過(guò)了采集個(gè)樣本這一步驟，直接獲得壓縮的信號(hào)的表示。CS理論利用到了許多自然信號(hào)在特定的基上具有緊湊的表示。即這些信號(hào)是“稀疏的或“可壓縮的。由于這一特性，壓縮感知理論的信號(hào)編解碼框架和傳統(tǒng)的壓縮過(guò)程大不一樣，主要包括信號(hào)的稀疏表示、編碼測(cè)量和重構(gòu)算法等三個(gè)方面。對(duì)于一個(gè)實(shí)值的有限長(zhǎng)一維離散時(shí)間信號(hào)，可以看作為一個(gè)空間1的維的列

20、向量，元素為，,=1，2，?？臻g的任何信號(hào)都可以用1維的基向量的線(xiàn)性組合表示。為簡(jiǎn)化問(wèn)題，假定這些基是標(biāo)準(zhǔn)正交的。把向量作為列向量形成的基矩陣=,，于是任意信號(hào)都可以表示為： (式2.1)其中是投影系數(shù)，=構(gòu)成的1的列向量。顯然，和是同一個(gè)信號(hào)的等價(jià)表示，是信號(hào)在時(shí)域的表示，那么是信號(hào)在域的表示。如果的非零個(gè)數(shù)比小很多，那么說(shuō)明該信號(hào)是可壓縮的。一般而言，可壓縮信號(hào)是指可以用個(gè)大系數(shù)很好地逼近的信號(hào)，即它在某個(gè)正交基下展開(kāi)的系數(shù)按一定量級(jí)呈現(xiàn)指數(shù)衰減，具有非常少的大系數(shù)和許多小系數(shù)。這種通過(guò)變換實(shí)現(xiàn)壓縮的方法稱(chēng)為變換編碼。在數(shù)據(jù)采樣系統(tǒng)中，采樣速率高但信號(hào)是可壓縮的，采樣得到點(diǎn)采樣信號(hào)；通過(guò)變

21、換后計(jì)算出完整的變換系數(shù)集合；確定個(gè)大系數(shù)的位置，然后扔掉個(gè)小系數(shù)；對(duì)個(gè)大系數(shù)的值和位置進(jìn)行編碼，從而到達(dá)壓縮的目的。由Candes、Romberg、Tao和Donoho等人在2004年提出的壓縮感知理論說(shuō)明，可以在不喪失逼近原信號(hào)所需信息的情況下，用最少的觀(guān)測(cè)次數(shù)來(lái)采樣信號(hào)，實(shí)現(xiàn)信號(hào)的降維處理，即直接對(duì)信號(hào)進(jìn)行較少采樣得到信號(hào)的壓縮表示，且不經(jīng)過(guò)進(jìn)行次采樣的中間階段，從而在節(jié)約采樣和傳輸本錢(qián)的情況下，到達(dá)了在采樣的同時(shí)進(jìn)行壓縮的目的4。Candes證明了只要信號(hào)在某一個(gè)正交空間具有稀疏性，就能以較低的頻率采樣信號(hào)，而且可以以高概率重構(gòu)該信號(hào)。即，設(shè)長(zhǎng)度為的信號(hào)在某正交基或框架上的變換系數(shù)是稀

22、疏的，如果我們可以用一個(gè)與變換基不相關(guān)的觀(guān)測(cè)基：對(duì)系數(shù)向量進(jìn)行線(xiàn)性變換，并得到觀(guān)測(cè)集合。那么就可以利用優(yōu)化求解方法5從觀(guān)測(cè)集合中精確或高概率地重構(gòu)原始信號(hào)。圖2.3是基于壓縮感知理論的信號(hào)重構(gòu)過(guò)程框圖?？蓧嚎s信號(hào)稀疏變換觀(guān)測(cè)得到的維向量重構(gòu)信號(hào)滿(mǎn)足圖2.3 基于壓縮感知理論的信號(hào)重構(gòu)過(guò)程2.2.1 信號(hào)的稀疏表示壓縮感知的第一步，即對(duì)于信號(hào)，如何找到某個(gè)正交基或緊框架，使其在上的表示是稀疏的，即信號(hào)的稀疏表示問(wèn)題。所謂的稀疏，就是指信號(hào)在正交基下的變換系數(shù)向量為，假設(shè)對(duì)于和，這些系數(shù)滿(mǎn)足： (式2.2)那么說(shuō)明系數(shù)向量在某種意義下是稀疏的。如何找到信號(hào)最正確的稀疏域？這是壓縮感知理論應(yīng)用的根底

23、和前提，只有選擇適宜的基表示信號(hào)才能保證信號(hào)的稀疏度，從而保證信號(hào)的恢復(fù)精度。在研究信號(hào)的稀疏表示時(shí)，可以通過(guò)變換系數(shù)衰減速度來(lái)衡量變換基的稀疏表示能力。Candes和Tao研究說(shuō)明，滿(mǎn)足具有冪次速度衰減的信號(hào)，可利用壓縮感知理論得到恢復(fù)，并且重構(gòu)誤差滿(mǎn)足： (式2.3)其中r=1/p1/2，0p1.文獻(xiàn)6指出光滑信號(hào)的Fourier系數(shù)、小波系數(shù)、有界變差函數(shù)的全變差范數(shù)、振蕩信號(hào)的Gabor系數(shù)及具有不連續(xù)邊緣的圖像信號(hào)的Curvelet系數(shù)等都具有足夠的稀疏性，可以通過(guò)壓縮感知理論恢復(fù)信號(hào)。如何找到或構(gòu)造適合一類(lèi)信號(hào)的正交基，以求得信號(hào)的最稀疏表示，這是一個(gè)有待進(jìn)一步研究的問(wèn)題。Peyr

24、e把變換基是正交基的條件擴(kuò)展到了由多個(gè)正交基構(gòu)成的正交基字典。即在某個(gè)正交基字典里，自適應(yīng)地尋找可以逼近某一種信號(hào)特征的最優(yōu)正交基，根據(jù)不同的信號(hào)尋找最適合信號(hào)特性的一個(gè)正交基，對(duì)信號(hào)進(jìn)行變換以得到最稀疏的信號(hào)表示。對(duì)稀疏表示研究的另一個(gè)熱點(diǎn)是信號(hào)在冗余字典下的稀疏分解。這是一種全新的信號(hào)表示理。用超完備的冗余函數(shù)庫(kù)取代基函數(shù)，稱(chēng)之為冗余字典，字典中的元素被稱(chēng)為原子。字典的選擇應(yīng)盡可能的符合被逼近信號(hào)的結(jié)構(gòu)，其構(gòu)成可以沒(méi)有任何限制。從冗余字典中找到具有最正確線(xiàn)性組合的項(xiàng)原子來(lái)表示一個(gè)信號(hào)，稱(chēng)作信號(hào)的稀疏逼近或高度非線(xiàn)性逼近。從非線(xiàn)性逼近角度來(lái)講，信號(hào)的稀疏逼近包含兩個(gè)層面：一是根據(jù)目標(biāo)函數(shù)從一

25、個(gè)給定的基庫(kù)中挑選好的或最好的基；二是從這個(gè)好的基中挑選最正確的K項(xiàng)組合。因此，目前信號(hào)在冗余字典下的稀疏表示的研究集中在兩個(gè)方面：(1)如何構(gòu)造一個(gè)適合某一類(lèi)信號(hào)的冗余字典；(2)如何設(shè)計(jì)快速有效的稀疏分解算法。在構(gòu)造冗余字典方面，文獻(xiàn)7中提出使用局部Cosine基來(lái)刻畫(huà)聲音信號(hào)的局部頻域特性；利用bandlet基來(lái)刻畫(huà)圖像中的幾何邊緣；還可以把其它的具有不同形狀的基函數(shù)歸入字典，如適合刻畫(huà)紋理的Gabor基、適合刻畫(huà)輪廓的Curvelet基等等。在稀疏分解算法的設(shè)計(jì)方面，基于貪婪迭代思想的MP(Matching Pursuit)算法表現(xiàn)出極大的優(yōu)越性，但不是全局最優(yōu)解。Donoho等人之后

26、提出了基追蹤(basis pursuit，BP)算法。BP算法具有全局最優(yōu)的優(yōu)點(diǎn)，但計(jì)算復(fù)雜度極高。之后又出現(xiàn)了一系列同樣基于貪婪迭代思想的改良算法，如正交匹配追蹤算法(OMP)，分段匹配追蹤(STOMP)算法等。2.2.2 信號(hào)的觀(guān)測(cè)矩陣如何設(shè)計(jì)一個(gè)平穩(wěn)的、與變換基不相關(guān)的維的觀(guān)測(cè)矩陣，保證稀疏向量從維降到維時(shí)重要信息不遭破壞，是第二步要解決的問(wèn)題，也就是信號(hào)低速采樣問(wèn)題。壓縮感知理論中，通過(guò)變換得到信號(hào)的稀疏系數(shù)向量后，需要設(shè)計(jì)壓縮采樣系統(tǒng)的觀(guān)測(cè)局部，它圍繞觀(guān)測(cè)矩陣展開(kāi)。觀(guān)測(cè)器的設(shè)計(jì)目的是如何采樣得到個(gè)觀(guān)測(cè)值，并保證從中能重構(gòu)出長(zhǎng)度為的信號(hào)或者基下等價(jià)的稀疏系數(shù)向量。顯然，如果觀(guān)測(cè)過(guò)程破壞

27、了中的信息，重構(gòu)是不可能的。觀(guān)測(cè)過(guò)程實(shí)際就是利用觀(guān)測(cè)矩陣的個(gè)行向量對(duì)稀疏系數(shù)向量進(jìn)行投影，即計(jì)算和各個(gè)觀(guān)測(cè)向量之間的內(nèi)積，得到個(gè)觀(guān)測(cè)值，記觀(guān)測(cè)向量，即 (式2.4)這里，采樣過(guò)程是非自適應(yīng)的，也就是說(shuō)，無(wú)須根據(jù)信號(hào)而變化，觀(guān)測(cè)的不再是信號(hào)的點(diǎn)采樣而是信號(hào)的更一般的線(xiàn)性泛函。對(duì)于給定的從式(2.4)中求出是一個(gè)線(xiàn)性規(guī)劃問(wèn)題，但由于，即方程的個(gè)數(shù)少于未知數(shù)的個(gè)數(shù)，這是一個(gè)欠定問(wèn)題，一般來(lái)講無(wú)確定解。然而，如果具有-項(xiàng)稀疏性()，那么該問(wèn)題有望求出確定解。此時(shí)，只要設(shè)法確定出中的個(gè)非零系數(shù)的適宜位置，由于觀(guān)測(cè)向量是這些非零系數(shù)對(duì)應(yīng)的個(gè)列向量的線(xiàn)性組合，從而可以形成一個(gè)的線(xiàn)性方程組來(lái)求解這些非零項(xiàng)的具

28、體值。對(duì)此，即有限等距性質(zhì)RIP給出了存在確定解的充要條件。這個(gè)充要條件和Candes、Tao等人提出的稀疏信號(hào)在觀(guān)測(cè)矩陣作用下必須保持的幾何性質(zhì)相一致。即，要想使信號(hào)完全重構(gòu)，必須保證觀(guān)測(cè)矩陣不會(huì)把兩個(gè)不同的-項(xiàng)稀疏信號(hào)映射到同一個(gè)采樣集合中，這就要求從觀(guān)測(cè)矩陣中抽取的每個(gè)列向量構(gòu)成的矩陣是非奇異的。從中可以看出，問(wèn)題的關(guān)鍵是如何確定非零系數(shù)的位置來(lái)構(gòu)造出一個(gè)可解的線(xiàn)性方程組。然而，判斷給定的是否具有RIP性質(zhì)是一個(gè)組合復(fù)雜度問(wèn)題。為了降低問(wèn)題的復(fù)雜度，能否找到一種易于實(shí)現(xiàn)RIP條件的替代方法成為構(gòu)造觀(guān)測(cè)矩陣的關(guān)鍵。文獻(xiàn)8指出如果保證觀(guān)測(cè)矩陣和稀疏基不相干，那么在很大概率上滿(mǎn)足RIP性質(zhì)。不

29、相干是指向量不能用稀疏表示。不相干性越強(qiáng)，互相表示時(shí)所需的系數(shù)越多；反之，相關(guān)性那么越強(qiáng)。通過(guò)選擇高斯隨機(jī)矩陣作為觀(guān)測(cè)矩陣即可高概率保證不相干性和RIP性質(zhì)。例如，可以生成多個(gè)零均值、方差為1/的隨機(jī)高斯函數(shù)，將它們作為觀(guān)測(cè)矩陣的元素，使得以很高的概率具有RIP性質(zhì)。隨機(jī)高斯矩陣具有一個(gè)有用的性質(zhì)：對(duì)于一個(gè)的隨機(jī)高斯矩陣，可以證明當(dāng)McKlog(NK)時(shí)在很大概率下具有RIP性質(zhì)(其中c是一個(gè)很小的常數(shù))。因此可以從個(gè)觀(guān)測(cè)值中以很高的概率去恢復(fù)長(zhǎng)度為的-項(xiàng)稀疏信號(hào)。總之，隨機(jī)高斯矩陣與大多數(shù)固定正交基構(gòu)成的矩陣不相關(guān)，這一特性決定了選它作為觀(guān)測(cè)矩陣，其它正交基作為稀疏變換基時(shí)，滿(mǎn)足RIP性質(zhì)。

30、為進(jìn)一步簡(jiǎn)化觀(guān)測(cè)矩陣，在某些條件下，以隨機(jī)為元素構(gòu)成的Rademacher矩陣也可以證明具有RIP性質(zhì)和普適性。對(duì)觀(guān)測(cè)矩陣的研究是壓縮感知理論的一個(gè)重要方面。Donoho給出了觀(guān)測(cè)矩陣所必需具備的三個(gè)條件9，并指出大局部一致分布的隨機(jī)矩陣都具備這三個(gè)條件，均可作為觀(guān)測(cè)矩陣，如：局部Fourier集、局部Hadamard集、一致分布的隨機(jī)投影(uniform Random Projection)集等，這與對(duì)RIP性質(zhì)進(jìn)行研究得出的結(jié)論相一致。但是，使用上述各種觀(guān)測(cè)矩陣進(jìn)行觀(guān)測(cè)后，都僅僅能保證以很高的概率去恢復(fù)信號(hào)，而不能保證百分之百地精確重構(gòu)信號(hào)。對(duì)于任何穩(wěn)定的重構(gòu)算法是否存在一個(gè)真實(shí)確實(shí)定性的

31、觀(guān)測(cè)矩陣仍是一個(gè)有待研究的問(wèn)題。2.2.3 信號(hào)重構(gòu)如何設(shè)計(jì)快速重構(gòu)算法，從線(xiàn)性觀(guān)測(cè)中恢復(fù)信號(hào)，是第三步要將解決的問(wèn)題，即信號(hào)的重構(gòu)問(wèn)題。在壓縮感知理論中，由于觀(guān)測(cè)數(shù)量遠(yuǎn)小于信號(hào)長(zhǎng)度，因此不得不面對(duì)求解欠定方程組的問(wèn)題。外表上看，求解欠定方程組似乎是無(wú)望的，但是，文獻(xiàn)10和11均指出由于信號(hào)是稀疏的或可壓縮的，這個(gè)前提從根本上改變了問(wèn)題，使得問(wèn)題可解，而觀(guān)測(cè)矩陣具有RIP性質(zhì)也為從個(gè)觀(guān)測(cè)值中精確恢復(fù)信號(hào)提供了理論保證。為更清晰地描述壓縮感知理論的信號(hào)重構(gòu)問(wèn)題，首先定義向量的范數(shù)為： (式2.5)當(dāng)時(shí)得到范數(shù)，它實(shí)際上表示中非零項(xiàng)的個(gè)數(shù)。于是，在信號(hào)稀疏或可壓縮的前提下，求解欠定方程組的問(wèn)題轉(zhuǎn)化

32、為最小范數(shù)問(wèn)題： s.t. (式2.6)但是，它需要列出中所有非零項(xiàng)位置的種可能的線(xiàn)性組合，才能得到最優(yōu)解。因此，求解式2.6)的數(shù)值計(jì)算極不穩(wěn)定而且是NP難問(wèn)題。注意，這和稀疏分解問(wèn)題從數(shù)學(xué)意義上講是同樣的問(wèn)題。于是稀疏分解的已有算法可以應(yīng)用到CS重構(gòu)中。Chen，Donoho和Saunders指出，求解一個(gè)更加簡(jiǎn)單的優(yōu)化問(wèn)題會(huì)產(chǎn)生同等的解(要求和不相關(guān))： s.t. (式2.7)稍微的差異使得問(wèn)題變成了一個(gè)凸優(yōu)化問(wèn)題，于是可以方便地化簡(jiǎn)為線(xiàn)性規(guī)劃問(wèn)題，典型算法代表：BP算法盡管BP算法可行，但在實(shí)際應(yīng)用中存在兩個(gè)問(wèn)題：第一，即使是常見(jiàn)的圖像尺寸，BP算法的計(jì)算復(fù)雜度也難以忍受，在采樣點(diǎn)個(gè)數(shù)

33、滿(mǎn)足，時(shí)，重構(gòu)計(jì)算復(fù)雜度的量級(jí)在；第二，由于范數(shù)無(wú)法區(qū)分稀疏系數(shù)尺度的位置，所以盡管整體上重構(gòu)信號(hào)在歐氏距離上逼近原信號(hào)，但存在低尺度能量搬移到了高尺度的現(xiàn)象，從而容易出現(xiàn)一些人工效應(yīng)，如一維信號(hào)會(huì)在高頻出現(xiàn)振蕩?；谏鲜鰡?wèn)題，2005年1月Candes和Romberg提出了不同的信號(hào)恢復(fù)方法，該方法要求對(duì)原信號(hào)具有少量的先驗(yàn)知識(shí)，同時(shí)也可以對(duì)所求結(jié)果施加適當(dāng)?shù)钠谕匦裕约s束重構(gòu)信號(hào)的特性。通過(guò)在凸集上交替投影的方法，可以快速求解線(xiàn)性規(guī)劃問(wèn)題。Tropp和Gilbert提出利用匹配追蹤(MP)和正交匹配追蹤(OMP)算法來(lái)求解優(yōu)化問(wèn)題重構(gòu)信號(hào)，大大提高了計(jì)算的速度，且易于實(shí)現(xiàn)。樹(shù)形匹配追蹤(

34、TMP)算法是2005年La和NDo提出的。該方法針對(duì)BP、MP和OMP方法沒(méi)有考慮信號(hào)的多尺度分解時(shí)稀疏信號(hào)在各子帶位置的關(guān)系，是將稀疏系數(shù)的樹(shù)型結(jié)構(gòu)加以利用，進(jìn)一步提升了重構(gòu)信號(hào)的精度和求解的速度。匹配追蹤類(lèi)算法都是基于貪婪迭代算法，以多于BP算法需要的采樣數(shù)目換取計(jì)算復(fù)雜度的降低。例如OMP算法，需要，個(gè)采樣點(diǎn)數(shù)才能以較高的概率恢復(fù)信號(hào)，信號(hào)重構(gòu)的計(jì)算復(fù)雜度為。2006年Donoho等人提出了分段正交匹配追蹤(STOMP，Stagewise OMP)算法。它將OMP進(jìn)行一定程度的簡(jiǎn)化，以逼近精度為代價(jià)進(jìn)一步提高了計(jì)算速度(計(jì)算復(fù)雜度為O(N)，更加適合于求解大規(guī)模問(wèn)題。匹配追蹤類(lèi)方法為其

35、近似求解提供了有力工具，且該類(lèi)方法用于稀疏信號(hào)重建時(shí)具有一定的穩(wěn)定性。文獻(xiàn)12中提出的OMP算法延續(xù)了匹配追蹤算法中原子的選擇準(zhǔn)那么，但是實(shí)現(xiàn)了遞歸地對(duì)已選原子集合進(jìn)行正交化以保證迭代的最優(yōu)性，從而減少了迭代次數(shù)。此后，Needell和Vershynin等人在OMP算法的根底上將正那么化過(guò)程用于稀疏度的OMP算法中，提出了ROMP算法。ROMP算法與OMP算法的不同之處在于，該算法首先根據(jù)相關(guān)原子挑選多個(gè)原子作為候選集，然后從候選集中按照正那么化原那么挑選出局部原子，最后將其并入最終的支撐集，從而實(shí)現(xiàn)了原子的快速、有效選擇。最近出現(xiàn)的子空間匹配追蹤算法(Subspace Pursuit，SP)

36、和壓縮采樣匹配追蹤算法(Compressive Sampling Matching Pursuit，CoSaMP)引入了回退篩選的思想，這些算法的重建質(zhì)量與線(xiàn)性規(guī)劃方法相當(dāng)，同時(shí)重建復(fù)雜度低，但是這些算法都是建立在稀疏度的根底上。然而實(shí)際應(yīng)用中信號(hào)的稀疏度往往是未知的，由此出現(xiàn)了對(duì)稀疏度自適應(yīng)的稀疏自適應(yīng)匹配追蹤算法(Sparsity Adaptive Matching Pursuit,SAMP)，它通過(guò)設(shè)置一個(gè)可變步長(zhǎng)，逐步對(duì)信號(hào)稀疏度進(jìn)行估計(jì)，因此可以在K未知的情況下獲得較好的重建效果，速度也遠(yuǎn)快于OMP算法。基于ROMP算法和SAMP算法的突出優(yōu)勢(shì)。2.3.壓縮感知的應(yīng)用這里主要介紹CS

37、理論在成像系統(tǒng)、圖像融合、圖像跟蹤以及數(shù)據(jù)獲取等方面的應(yīng)用。1成像系統(tǒng)在成像方面，CS理論的出現(xiàn)激起了人們研究新型傳感器的熱情，CS采樣對(duì)昂貴的成像器件的設(shè)計(jì)產(chǎn)生了重大影響。在地震勘探和核磁共振成像中，對(duì)于目標(biāo)信號(hào)，將有望采用少量的隨機(jī)觀(guān)測(cè)次數(shù)就能獲得高精度重構(gòu)，取代傳統(tǒng)數(shù)碼相機(jī)拍照時(shí)采集大量像素的一種新型單像素CS相機(jī)已經(jīng)得到論證。相對(duì)于CS的理論研究進(jìn)展，美國(guó)Rice大學(xué)也已經(jīng)研制出單像素相機(jī)，如下列圖2.4所示。該相機(jī)具有一種全新的相機(jī)結(jié)構(gòu)，使用數(shù)字微鏡陣列完成圖像在偽隨機(jī)二值模型上線(xiàn)性投影的光學(xué)計(jì)算。它可利用單一的信號(hào)光子檢測(cè)器采樣得到比圖像像素點(diǎn)數(shù)少得多的點(diǎn)恢復(fù)圖像，并具有對(duì)圖像波長(zhǎng)

38、自適應(yīng)的能力，這種自適應(yīng)能力是傳統(tǒng)的CCD和CMOS成像器件所不具備的。ARI-ZONA大學(xué)Baheti和Neifeld設(shè)計(jì)了具有特定功能的結(jié)構(gòu)成像設(shè)備，DUCK大學(xué)研制了單景光譜成像裝置。然而由于壓縮重構(gòu)算法的計(jì)算量比擬大，難以到達(dá)實(shí)時(shí)性要求，因此實(shí)時(shí)高性能壓縮感知成像系統(tǒng)是未來(lái)重要的研究方向。圖2.4單像素相機(jī)2圖像融合圖像融合是信息融合范疇內(nèi)以圖像為對(duì)象的研究領(lǐng)域。圖像融合將多個(gè)成像傳感器或同一成像傳感器在不同模式下獲取的同一場(chǎng)景的圖像信息加以綜合，獲取更為精確、全面、可靠的圖像描述。圖像融合技術(shù)在自動(dòng)目標(biāo)識(shí)別、計(jì)算機(jī)視覺(jué)、遙感、機(jī)器人、自動(dòng)小車(chē)、復(fù)雜智能制造系統(tǒng)、醫(yī)學(xué)圖像處理以及軍事應(yīng)

39、用等領(lǐng)域有著廣泛的應(yīng)用潛力13。將不同模式下的融合圖像采用CS理論進(jìn)行稀疏表示，如下列圖2.5所示。使其在測(cè)量舉證的作用下，用遠(yuǎn)小于原圖像的數(shù)據(jù)量進(jìn)行計(jì)算得到融合結(jié)果復(fù)原為圖像表示，可節(jié)省中間融合所需的計(jì)算量，并且能夠更好地利用原圖像中像素間的內(nèi)在聯(lián)系，是一個(gè)非常值得研究的課題。圖2.5 CS用于圖像融合的流程框圖3目標(biāo)跟蹤視頻目標(biāo)跟蹤是使用可見(jiàn)、紅外等被動(dòng)式成像傳感器實(shí)現(xiàn)目標(biāo)測(cè)量的核心技術(shù)之一，是目標(biāo)識(shí)別、視頻圖像的壓縮編碼等高層次的視頻處理和應(yīng)用理解的根底，也是視頻監(jiān)控技術(shù)自動(dòng)化和實(shí)時(shí)應(yīng)用的關(guān)鍵。目標(biāo)跟蹤的實(shí)質(zhì)是通過(guò)對(duì)圖像傳感器拍攝到的視頻序列進(jìn)行分析，計(jì)算出目標(biāo)在每幀圖像中的位置、大小和

40、運(yùn)動(dòng)速度。CS理論自從被D.Donoho美國(guó)科學(xué)學(xué)院院士E.Candes(Ridgelet.Curvelet創(chuàng)始人)及T.Tao(華裔科學(xué)家，2006年菲爾茨獲獎(jiǎng)得主，2021年被評(píng)為世界上最聰明的科學(xué)家)等人提出后，在信息論、信號(hào)/圖像處理、醫(yī)療成像、模式識(shí)別、地質(zhì)勘探、光學(xué)/雷達(dá)成像、無(wú)線(xiàn)通信等領(lǐng)域受到高度關(guān)注，并被美國(guó)科技評(píng)論為2007年度10大科技進(jìn)展之一14?；贑S理論的目標(biāo)跟蹤。首先對(duì)目標(biāo)進(jìn)行建模，而后對(duì)后續(xù)幀圖像進(jìn)行相應(yīng)的模型建立，將求取兩模型最相似的問(wèn)題轉(zhuǎn)化為求取某相似參數(shù)的L1范數(shù)最小化問(wèn)題，對(duì)高維數(shù)據(jù)的特征信息處理有明顯優(yōu)勢(shì)，但是計(jì)算量大，復(fù)雜度高，是否對(duì)所有目標(biāo)都具有魯

41、棒的跟蹤效果有待于在目標(biāo)跟蹤方面做進(jìn)一步研究。4數(shù)據(jù)獲取在某些重要的情況下，完全采集模擬信號(hào)的N個(gè)離散時(shí)間樣本是困難的，而且也難以對(duì)其進(jìn)行壓縮。而運(yùn)用壓縮感知，可以設(shè)計(jì)物理采樣裝置，直接記錄模擬信號(hào)離散、低碼率、不相關(guān)的測(cè)量值，有效地進(jìn)行數(shù)據(jù)獲取?；赗IP理論，目前已研制出了一些設(shè)備，有萊斯大學(xué)研制的單像素相機(jī)和A/I轉(zhuǎn)換器，麻省理工學(xué)院研制的編碼孔徑相機(jī)，耶魯大學(xué)研制的超譜成像儀，麻省理工學(xué)院研制的MRI RF脈沖設(shè)備，伊利諾伊州立大學(xué)研制的DNA微陣列傳感器。2.4 壓縮感知有待研究的幾個(gè)問(wèn)題壓縮感知經(jīng)過(guò)近年來(lái)的迅猛開(kāi)展，已根本形成了自己的理論框架，包括根底理論、實(shí)現(xiàn)方法和實(shí)際應(yīng)用。但是

42、，壓縮感知理論還有很多亟待解決的問(wèn)題，為此本文列出了壓縮感知有待解決的幾個(gè)關(guān)鍵問(wèn)題。根底理論層面：1基于非正交稀疏字典的壓縮感知信號(hào)重建理論。在等距約束性準(zhǔn)那么驅(qū)動(dòng)的可壓縮信號(hào)壓縮感知定理中，關(guān)于稀疏字典和測(cè)量矩陣僅要求兩者乘積滿(mǎn)足RIP。但是，測(cè)量矩陣設(shè)計(jì)局部關(guān)于壓縮測(cè)量個(gè)數(shù)M的界定還額外附加了假設(shè)條件，即稀疏字典是正交基。當(dāng)測(cè)量矩陣依然通過(guò)三種方式生成，但是稀疏字典不再正交時(shí)，是否滿(mǎn)足RIP？壓縮測(cè)量個(gè)數(shù)M的下限是否不變？由于過(guò)完備的稀疏字典才能保證表示系數(shù)具有足夠的稀疏性或衰減性，進(jìn)而能夠在減少壓縮測(cè)量的同時(shí)保證壓縮感知的重建精度，所以需要設(shè)計(jì)魯棒的測(cè)量矩陣使之與過(guò)完備稀疏字典依然滿(mǎn)足R

43、IP，同時(shí)需要重新估計(jì)壓縮測(cè)量個(gè)數(shù)M的下限，這時(shí)所需的壓縮測(cè)量定會(huì)減少。2自然圖像的自適應(yīng)壓縮感知信號(hào)重建理論。雖然基于線(xiàn)性投影的壓縮感知理論能夠直接應(yīng)用于自然圖像這樣的復(fù)雜高維信號(hào)，但是由于沒(méi)有考慮到自然圖像的固有特性，諸如結(jié)構(gòu)多成分性、高階統(tǒng)計(jì)性等,對(duì)于自然圖像壓縮采樣本身沒(méi)有特殊的指導(dǎo)作用。事實(shí)上，相對(duì)于一維離散信號(hào),自然圖像的復(fù)雜性和高維性使之需要自適應(yīng)的壓縮采樣和重建算法。例如，基于圖像多成分性的特點(diǎn)能夠提高重建圖像的峰值信噪比和視覺(jué)效果。壓縮感知理論的大局部文獻(xiàn)中，測(cè)量矩陣都是線(xiàn)性的且設(shè)計(jì)好的，不需根據(jù)觀(guān)測(cè)信號(hào)自適應(yīng)地變化。對(duì)于自然圖像，假設(shè)能夠?qū)崿F(xiàn)非線(xiàn)性自適應(yīng)的壓縮測(cè)量，壓縮感知

44、的壓縮性能勢(shì)必會(huì)獲得大幅度的提高。目前，自然圖像的自適應(yīng)壓縮感知信號(hào)重建理論根本空白。這項(xiàng)工作對(duì)壓縮感知的理論推廣和實(shí)際應(yīng)用都具有重要意義。實(shí)現(xiàn)方法層面：1基于學(xué)習(xí)的自然圖像過(guò)完備字典設(shè)計(jì)。目前，基于構(gòu)造方法的自然圖像過(guò)完備字典設(shè)計(jì)具有很好的理論支撐，正那么化幾何方法、幾何多尺度分析、基于信息論的“有效編碼假設(shè)為其奠定了堅(jiān)實(shí)廣闊的理論根底。但是，從國(guó)際上關(guān)于過(guò)完備字典設(shè)計(jì)的整體情況看，基于學(xué)習(xí)的自然圖像過(guò)完備字典設(shè)計(jì)的工作非常少，主要在于：設(shè)計(jì)難度大、性能要求高，同時(shí)缺乏嚴(yán)格的理論支撐。這項(xiàng)工作對(duì)于稀疏字典和壓縮感知都將是重要的理論完善。(2)硬件易實(shí)現(xiàn)確實(shí)定性測(cè)量矩陣設(shè)計(jì)。在等距約束性準(zhǔn)那么

45、驅(qū)動(dòng)的可壓縮信號(hào)壓縮感知定理中，要求稀疏字典和測(cè)量矩陣的乘積=滿(mǎn)足RIP。其中，稀疏字典可以是正交的也可以是非正交的，測(cè)量矩陣可以是隨機(jī)的也可以是確定的。但是，面向應(yīng)用且硬件易實(shí)現(xiàn)的測(cè)量矩陣應(yīng)該具有以下根本特點(diǎn)：滿(mǎn)足等距約束性、壓縮測(cè)量個(gè)數(shù)少、采樣計(jì)算本錢(qián)低、存儲(chǔ)矩陣的空間小、以及測(cè)量矩陣最好是確定性的。設(shè)計(jì)出硬件容易實(shí)現(xiàn)的測(cè)量矩陣和快速穩(wěn)定的重建算法是將壓縮感知理論推向?qū)嵱玫年P(guān)鍵。3噪聲情形大尺度問(wèn)題的快速魯棒重建算法15設(shè)計(jì)?？焖俜€(wěn)定的信號(hào)重建算法是將壓縮感知理論推向?qū)嵱玫年P(guān)鍵技術(shù)之一，特別適用于糾錯(cuò)編碼、核磁共振成像、NMR波譜研究等大尺度問(wèn)題。通常，基于最小化松弛算法的計(jì)算復(fù)雜度相對(duì)較

46、高。因而，在最小化驅(qū)動(dòng)的壓縮感知理論完善工作的根底上，希望能夠基于稀疏性自適應(yīng)的貪婪迭代和基于多層超先驗(yàn)建模的非凸迭代思想設(shè)計(jì)適于噪聲情形大尺度問(wèn)題的快速魯棒重建算法。第三章 正交匹配追蹤重建算法3.1最小L0范數(shù)模型從數(shù)學(xué)意義上講，基于壓縮感知理論的信號(hào)重建問(wèn)題就是尋找欠定方程組(程的數(shù)量少于待解的未知數(shù))的最簡(jiǎn)單解的問(wèn)題，L0范數(shù)刻畫(huà)的就是信號(hào)中非零元素的個(gè)數(shù)，因而能夠使得結(jié)果盡可能地稀疏。通常我們采用下式描述最小L0范數(shù)最優(yōu)化問(wèn)題： s.t. (式3.1)實(shí)際中，允許一定程度的誤差存在，因此將原始的最優(yōu)化問(wèn)題轉(zhuǎn)化成一個(gè)較簡(jiǎn)單的近似形式求解，其中是一個(gè)極小的常量： s.t. (式3.2)但

47、是這類(lèi)問(wèn)題的求解數(shù)值計(jì)算極不穩(wěn)定，很難直接求解。匹配追蹤類(lèi)稀疏重建算法解決的是最小L0范數(shù)問(wèn)題，最早提出的有匹配追蹤(MP)算法和正交匹配追蹤(OMP)算法。3.2匹配追蹤算法匹配追蹤算法的根本思想是在每一次的迭代過(guò)程中，從過(guò)完備原子庫(kù)里(即感知矩陣)選擇與信號(hào)最匹配的原子來(lái)進(jìn)行稀疏逼近并求出余量，然后繼續(xù)選出與信號(hào)余量最為匹配的原子。經(jīng)過(guò)數(shù)次迭代，該信號(hào)便可以由一些原子線(xiàn)性表示。但是由于信號(hào)在已選定原子(感知矩陣的列向量)集合上的投影的非正交性使得每次迭代的結(jié)果可能是次最優(yōu)的，因此為獲得較好的收斂效果往往需要經(jīng)過(guò)較多的迭代次數(shù)。匹配追蹤類(lèi)算法通過(guò)求余量r與感知矩陣中各個(gè)原子之間內(nèi)積的絕對(duì)值，

48、來(lái)計(jì)算相關(guān)系數(shù)u： 式3.3并采用最小二乘法進(jìn)行信號(hào)逼近以及余量更新: 式3.4 式3.53.3正交匹配追蹤算法(OMP)正交匹配追蹤算法Orthogonal Matching Pursuit,OMP，是最早的貪婪迭代算法之一，是壓縮感知信號(hào)檢測(cè)的一種算法。本文后面的仿真就是采用基于壓縮感知的正交匹配追蹤算法來(lái)重建圖像的。本節(jié)將著重介紹此算法的原理、實(shí)現(xiàn)步驟以及Matlab的語(yǔ)言實(shí)現(xiàn)。3.3.1 OMP算法原理OMP算法實(shí)質(zhì)上還是沿用了匹配追蹤算法中的原子選擇準(zhǔn)那么，只是將所選原子利用Gram-Schmidt正交化方法進(jìn)行正交處理，再將信號(hào)在這些正交原子構(gòu)成的空間上投影，得到信號(hào)在各個(gè)已選原子

49、上的分量和余量，然后用相同方法分解余量。在每一步分解中，所選原子均滿(mǎn)足一定條件，因此余量隨著分解過(guò)程迅速減小。通過(guò)遞歸地對(duì)已選擇原子集合進(jìn)行正交化保證了迭代的最優(yōu)性，從而有效克服了匹配追蹤算法為獲得較好的收斂效果往往需要經(jīng)過(guò)較多的迭代次數(shù)的問(wèn)題。OMP的重建算法是在給定迭代次數(shù)的條件下重建，這種強(qiáng)制迭代過(guò)程停止的方法使得OMP需要非常多的線(xiàn)性測(cè)量來(lái)保證精確重建?？傊载澙返姆椒ㄟx擇的列，使得在每次迭代中所選擇的列與當(dāng)前的冗余向量最大程度地相關(guān)，從測(cè)量向量中減去相關(guān)局部并反復(fù)迭代，直到迭代次數(shù)到達(dá)稀疏度，強(qiáng)制迭代停止。3.3.2 OMP算法實(shí)現(xiàn)步驟OMP算法的具體步驟如下：(1)初始余量

50、，迭代次數(shù)，索引值集合，；(2)計(jì)算相關(guān)系數(shù)u,并將u中最大值對(duì)應(yīng)的索引值存入中；(3)更新支撐集，其中；(4)應(yīng)用(式3.4)得到，同時(shí)用(式3.5)對(duì)余量進(jìn)行更新；(5)假設(shè)，令，轉(zhuǎn)步驟(2)；否那么，停止迭代。3.3.3 OMP算法的Matlab語(yǔ)言實(shí)現(xiàn)因?yàn)镺MP算法只能對(duì)稀疏信號(hào)進(jìn)行精確重構(gòu)，所以為了實(shí)現(xiàn)對(duì)OMP的仿真，首先需要將圖片轉(zhuǎn)換為稀疏信號(hào)，如FFT、DCT、小波變換等，在本文中采取小波變換，然后將得到的稀疏信號(hào)與測(cè)量矩陣相乘得到測(cè)量值Y，然后通過(guò)OMP算法，根據(jù)Y精確重建出原始信號(hào)最后經(jīng)過(guò)小波反變換得到原始圖像。由于在Matlab平臺(tái)上對(duì)圖像的處理、小波變換、矩陣的求逆合并等

51、運(yùn)算的實(shí)現(xiàn)較為方便，因此本文首先選擇在Matlab上實(shí)現(xiàn)OMP算法并對(duì)其進(jìn)行仿真。具體流程圖如圖3.1所示開(kāi)始：讀入圖片文件x獲取圖片的大小a*b對(duì)圖片進(jìn)行小波變換得到稀疏信號(hào)x1產(chǎn)生隨機(jī)測(cè)量矩陣，并與x1相乘得到測(cè)量值Y對(duì)Y按列處理i=1i=K*log(N/K),至少40,但有出錯(cuò)的概率)f1=50; % 信號(hào)頻率1f2=100; % 信號(hào)頻率2f3=200; % 信號(hào)頻率3f4=400; % 信號(hào)頻率4fs=800; % 采樣頻率ts=1/fs; % 采樣間隔Ts=1:N; % 采樣序列x=0.3*sin(2*pi*f1*Ts*ts)+0.6*sin(2*pi*f2*Ts*ts)+0.1*

52、sin(2*pi*f3*Ts*ts)+0.9*sin(2*pi*f4*Ts*ts); % 完整信號(hào)plot(x,r) % 原始信號(hào)程序2：一維重建信號(hào)的生成clc;clear% 1. 時(shí)域測(cè)試信號(hào)生成K=7; % 稀疏度(做FFT可以看出來(lái))N=256; % 信號(hào)長(zhǎng)度M=64; % 測(cè)量數(shù)(M=K*log(N/K),至少40,但有出錯(cuò)的概率)f1=50; % 信號(hào)頻率1f2=100; % 信號(hào)頻率2f3=200; % 信號(hào)頻率3f4=400; % 信號(hào)頻率4fs=800; % 采樣頻率ts=1/fs; % 采樣間隔Ts=1:N; % 采樣序列x=0.3*sin(2*pi*f1*Ts*ts)+0

53、.6*sin(2*pi*f2*Ts*ts)+0.1*sin(2*pi*f3*Ts*ts)+0.9*sin(2*pi*f4*Ts*ts); % 完整信號(hào)% 2. 時(shí)域信號(hào)壓縮傳感Phi=randn(M,N); % 測(cè)量矩陣(高斯分布白噪聲)s=Phi*x.; % 獲得線(xiàn)性測(cè)量 % 3. 正交匹配追蹤法重構(gòu)信號(hào)(本質(zhì)上是1-范數(shù)最優(yōu)化問(wèn)題)m=2*K; % 算法迭代次數(shù)(m=K)Psi=fft(eye(N,N)/sqrt(N); % 傅里葉正變換矩陣T=Phi*Psi; % 恢復(fù)矩陣(測(cè)量矩陣*正交反變換矩陣)hat_y=zeros(1,N); % 待重構(gòu)的譜域(變換域)向量 Aug_t=; %

54、增量矩陣(初始值為空矩陣)r_n=s; % 殘差值for times=1:m; % 迭代次數(shù)(有噪聲的情況下,該迭代次數(shù)為K) for col=1:N; % 恢復(fù)矩陣的所有列向量 product(col)=abs(T(:,col)*r_n); % 恢復(fù)矩陣的列向量和殘差的投影系數(shù)(內(nèi)積值) end val,pos=max(product); % 最大投影系數(shù)對(duì)應(yīng)的位置 Aug_t=Aug_t,T(:,pos); % 矩陣擴(kuò)充 T(:,pos)=zeros(M,1); % 選中的列置零實(shí)質(zhì)上應(yīng)該去掉，為了簡(jiǎn)單我把它置零 aug_y=(Aug_t*Aug_t)(-1)*Aug_t*s; % 最小二

55、乘,使殘差最小 r_n=s-Aug_t*aug_y; % 殘差 pos_array(times)=pos; % 紀(jì)錄最大投影系數(shù)的位置endhat_y(pos_array)=aug_y; % 重構(gòu)的譜域向量hat_x=real(Psi*hat_y.); % 做逆傅里葉變換重構(gòu)得到時(shí)域信號(hào)% 4.恢復(fù)信號(hào)和原始信號(hào)比照f(shuō)igure(1)hold on;plot(hat_x,k.-) % 重建信號(hào)plot(x,r) % 原始信號(hào)legend(Recovery,Original)norm(hat_x.-x)/norm(x) % 重構(gòu)誤差程序3：二維圖像OMP重建function Wavelet_OM

56、Pclc;clearX=imread(lena256.bmp); % 讀文件X=double(X);a,b=size(X);ww=DWT(a); % 小波變換矩陣生成X1=ww*sparse(X)*ww; % 小波變換讓圖像稀疏化注意該步驟會(huì)消耗時(shí)間，但是會(huì)增大稀疏度X1=full(X1);M=190; % 隨機(jī)矩陣生成R=randn(M,a);Y=R*X1; % 測(cè)量% OMP算法X2=zeros(a,b); % 恢復(fù)矩陣for i=1:b % 列循環(huán) rec=omp(Y(:,i),R,a); X2(:,i)=rec;endfigure(1); % 原始圖像imshow(uint8(X);t

57、itle(原始圖像);figure(2); % 變換圖像imshow(uint8(X1);title(小波變換后的圖像);figure(3); % 壓縮傳感恢復(fù)的圖像X3=ww*sparse(X2)*ww; % 小波反變換X3=full(X3);imshow(uint8(X3);title(恢復(fù)的圖像);% 誤差(PSNR)errorx=sum(sum(abs(X3-X).2); % MSE誤差psnr=10*log10(255*255/(errorx/a/b) % PSNR% OMP的函數(shù)% s-測(cè)量；T-觀(guān)測(cè)矩陣；N-向量大小function hat_y=omp(s,T,N)Size=si

58、ze(T); % 觀(guān)測(cè)矩陣大小M=Size(1); % 測(cè)量hat_y=zeros(1,N); % 待重構(gòu)的譜域(變換域)向量Aug_t=; % 增量矩陣(初始值為空矩陣)r_n=s; % 殘差值for times=1:M/4; % 迭代次數(shù)(稀疏度是測(cè)量的1/4) for col=1:N; % 恢復(fù)矩陣的所有列向量 product(col)=abs(T(:,col)*r_n); % 恢復(fù)矩陣的列向量和殘差的投影系數(shù)(內(nèi)積值) end val,pos=max(product); % 最大投影系數(shù)對(duì)應(yīng)的位置 Aug_t=Aug_t,T(:,pos); % 矩陣擴(kuò)充 T(:,pos)=zeros(

59、M,1); % 選中的列置零實(shí)質(zhì)上應(yīng)該去掉，為了簡(jiǎn)單我把它置零 aug_y=(Aug_t*Aug_t)(-1)*Aug_t*s; % 最小二乘,使殘差最小 r_n=s-Aug_t*aug_y; % 殘差 pos_array(times)=pos; % 紀(jì)錄最大投影系數(shù)的位置 if (norm(r_n)9) % 殘差足夠小 break; endendhat_y(pos_array)=aug_y; % 重構(gòu)的向量程序4：BP、OMP、STOMP_FDR重建圖像x=imread(lena.bmp); %讀文件m,n=size(x);xrec_BP=size(x);xrec_OMP=size(x);x

60、rec_FDR=size(x);t_BP=0;t_OMP=0;t_FDR=0;for i=1:m x1=x(i,:); cA,cD=dwt(x1,db1); % 小波變換 c1=length(cD) Mdetail=c1; Ndetail=floor(c1*0.4);A=randn(Ndetail,Mdetail); % 隨機(jī)矩陣生成y=A*cD;q=0.5;S=10;tic;alpha=SolveBP(A,y,Mdetail); % BP算法處理圖像t_BP=t_BP+toc;rec1=idwt(cA,alpha,db1);xrec_BP(i,1:n)=rec1;tic;alpha,iter