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

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

2、完成對信號的精確重構(gòu)，該過程可看為求解一個(gè)優(yōu)化問題。本文介紹了主要介紹了壓縮感知原理和目前最為成熟的壓縮感知重建算法正交匹配追蹤算法，通過MATLAB平臺(tái)設(shè)計(jì)實(shí)現(xiàn)了根本的正交匹配追蹤算法，對一維、二維信號進(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本課題在國內(nè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壓縮感知的根本理論及核心問題 PAGEREF _Toc357415644 h 52.2.1 信號的稀疏表示 PAGEREF _Toc357415645 h 62.2.2 信號的觀測矩陣 PAGEREF _Toc357415646 h 82.2.3 信號重構(gòu) PAGEREF _Toc357415647 h 92.3.壓縮感知的應(yīng)用 PAGEREF _Toc357415648 h 112.4 壓縮感知有待研究的

9、幾個(gè)問題 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語言實(shí)現(xiàn) PAGERE

10、F _Toc357415656 h 17第四章 基于MATLAB的壓縮感知圖像重建仿真 PAGEREF _Toc357415657 h 204.1不同采樣率下的仿真結(jié)果 PAGEREF _Toc357415658 h 20一維信號在不同采樣率下的OMP仿真 PAGEREF _Toc357415659 h 20二維信號在不同采樣率下的OMP仿真 PAGEREF _Toc357415660 h 224.2OMP算法與多種壓縮感知算法的仿真比擬 PAGEREF _Toc357415661 h 244.3結(jié)論 PAGEREF _Toc357415662 h 26結(jié)束語 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)的信號采樣以奈奎斯特Nyquist采樣定理為根底。為了不喪失信號的信息，精確重構(gòu)信號，在獲取信號時(shí)，采樣頻率要大于信號中最高頻率的兩倍。但是隨著各種信號處理系統(tǒng)獲取能力的不斷增強(qiáng)，需要后期處理的數(shù)據(jù)量也快速增加，奈奎斯特定理的局限性給系統(tǒng)的處理能力提出了更高的要求，

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

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

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

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

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

17、配追蹤算法的原理、實(shí)現(xiàn)步驟和Matlab的語言實(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)的信號采集、編解碼過程如圖2.l所示。編碼端先對信號進(jìn)行采樣，再對所有采樣值進(jìn)行變換，并將其中重要系數(shù)的幅度和位置進(jìn)行編碼，最后將編碼值進(jìn)行存儲(chǔ)或傳輸：信號的解碼過程僅僅是編碼的逆過程，接收的信號經(jīng)解壓縮、反變換后得到恢復(fù)信號。采用這種傳統(tǒng)的編解碼方法，由于信號的采樣速率不得低于信號帶寬的2倍，使得硬件系

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

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

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

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

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

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

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

25、個(gè)給定的基庫中挑選好的或最好的基；二是從這個(gè)好的基中挑選最正確的K項(xiàng)組合。因此，目前信號在冗余字典下的稀疏表示的研究集中在兩個(gè)方面：(1)如何構(gòu)造一個(gè)適合某一類信號的冗余字典；(2)如何設(shè)計(jì)快速有效的稀疏分解算法。在構(gòu)造冗余字典方面，文獻(xiàn)7中提出使用局部Cosine基來刻畫聲音信號的局部頻域特性；利用bandlet基來刻畫圖像中的幾何邊緣；還可以把其它的具有不同形狀的基函數(shù)歸入字典，如適合刻畫紋理的Gabor基、適合刻畫輪廓的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 信號的觀測矩陣如何設(shè)計(jì)一個(gè)平穩(wěn)的、與變換基不相關(guān)的維的觀測矩陣，保證稀疏向量從維降到維時(shí)重要信息不遭破壞，是第二步要解決的問題，也就是信號低速采樣問題。壓縮感知理論中，通過變換得到信號的稀疏系數(shù)向量后，需要設(shè)計(jì)壓縮采樣系統(tǒng)的觀測局部，它圍繞觀測矩陣展開。觀測器的設(shè)計(jì)目的是如何采樣得到個(gè)觀測值，并保證從中能重構(gòu)出長度為的信號或者基下等價(jià)的稀疏系數(shù)向量。顯然，如果觀測過程破壞

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

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

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

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

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

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

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

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

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

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

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

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)是未來重要的研究方向。圖2.4單像素相機(jī)2圖像融合圖像融合是信息融合范疇內(nèi)以圖像為對象的研究領(lǐng)域。圖像融合將多個(gè)成像傳感器或同一成像傳感器在不同模式下獲取的同一場景的圖像信息加以綜合，獲取更為精確、全面、可靠的圖像描述。圖像融合技術(shù)在自動(dòng)目標(biāo)識(shí)別、計(jì)算機(jī)視覺、遙感、機(jī)器人、自動(dòng)小車、復(fù)雜智能制造系統(tǒng)、醫(yī)學(xué)圖像處理以及軍事應(yīng)

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

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

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

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

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

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

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

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

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

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

49、上的分量和余量，然后用相同方法分解余量。在每一步分解中，所選原子均滿足一定條件，因此余量隨著分解過程迅速減小。通過遞歸地對已選擇原子集合進(jìn)行正交化保證了迭代的最優(yōu)性，從而有效克服了匹配追蹤算法為獲得較好的收斂效果往往需要經(jīng)過較多的迭代次數(shù)的問題。OMP的重建算法是在給定迭代次數(shù)的條件下重建，這種強(qiáng)制迭代過程停止的方法使得OMP需要非常多的線性測量來保證精確重建。總之，它以貪婪迭代的方法選擇的列，使得在每次迭代中所選擇的列與當(dāng)前的冗余向量最大程度地相關(guān)，從測量向量中減去相關(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中最大值對應(yīng)的索引值存入中；(3)更新支撐集，其中；(4)應(yīng)用(式3.4)得到，同時(shí)用(式3.5)對余量進(jìn)行更新；(5)假設(shè)，令，轉(zhuǎn)步驟(2)；否那么，停止迭代。3.3.3 OMP算法的Matlab語言實(shí)現(xiàn)因?yàn)镺MP算法只能對稀疏信號進(jìn)行精確重構(gòu)，所以為了實(shí)現(xiàn)對OMP的仿真，首先需要將圖片轉(zhuǎn)換為稀疏信號，如FFT、DCT、小波變換等，在本文中采取小波變換，然后將得到的稀疏信號與測量矩陣相乘得到測量值Y，然后通過OMP算法，根據(jù)Y精確重建出原始信號最后經(jīng)過小波反變換得到原始圖像。由于在Matlab平臺(tái)上對圖像的處理、小波變換、矩陣的求逆合并等

51、運(yùn)算的實(shí)現(xiàn)較為方便，因此本文首先選擇在Matlab上實(shí)現(xiàn)OMP算法并對其進(jìn)行仿真。具體流程圖如圖3.1所示開始：讀入圖片文件x獲取圖片的大小a*b對圖片進(jìn)行小波變換得到稀疏信號x1產(chǎn)生隨機(jī)測量矩陣，并與x1相乘得到測量值Y對Y按列處理i=1i=K*log(N/K),至少40,但有出錯(cuò)的概率)f1=50; % 信號頻率1f2=100; % 信號頻率2f3=200; % 信號頻率3f4=400; % 信號頻率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); % 完整信號plot(x,r) % 原始信號程序2：一維重建信號的生成clc;clear% 1. 時(shí)域測試信號生成K=7; % 稀疏度(做FFT可以看出來)N=256; % 信號長度M=64; % 測量數(shù)(M=K*log(N/K),至少40,但有出錯(cuò)的概率)f1=50; % 信號頻率1f2=100; % 信號頻率2f3=200; % 信號頻率3f4=400; % 信號頻率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); % 完整信號% 2. 時(shí)域信號壓縮傳感Phi=randn(M,N); % 測量矩陣(高斯分布白噪聲)s=Phi*x.; % 獲得線性測量 % 3. 正交匹配追蹤法重構(gòu)信號(本質(zhì)上是1-范數(shù)最優(yōu)化問題)m=2*K; % 算法迭代次數(shù)(m=K)Psi=fft(eye(N,N)/sqrt(N); % 傅里葉正變換矩陣T=Phi*Psi; % 恢復(fù)矩陣(測量矩陣*正交反變換矩陣)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ù)對應(yīng)的位置 Aug_t=Aug_t,T(:,pos); % 矩陣擴(kuò)充 T(:,pos)=zeros(M,1); % 選中的列置零實(shí)質(zhì)上應(yīng)該去掉，為了簡單我把它置零 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í)域信號% 4.恢復(fù)信號和原始信號比照figure(1)hold on;plot(hat_x,k.-) % 重建信號plot(x,r) % 原始信號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; % 測量% 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-測量；T-觀測矩陣；N-向量大小function hat_y=omp(s,T,N)Size=si

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

59、M,1); % 選中的列置零實(shí)質(zhì)上應(yīng)該去掉，為了簡單我把它置零 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