【正文】 ogonal Matching Algorithm Image Recovery Abstract： Compressed sensing is a novel sampling theory which is proposed by Donoho and Cand232。該理論表明，用遠(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í)間和器件成本。s. This theory is under the condition that the signal is pressible 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 theory breaks though the traditional Nyquist sampling theory, which overes 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 pressed theory has three key sides: (1) Sparse transformation, for a non sparse signal, we need to find a proper orthogonal basis on which the signal has a sparse representation。 Orthogonal matching。如何高效處理這些數(shù)據(jù)并且最大限度的節(jié)省存儲(chǔ)空間 及傳輸成本已成為目前信息領(lǐng)域進(jìn)一步向前發(fā)展的主要瓶頸之一。在隨后的幾年間該理論迅速發(fā)展，為解決上述問(wèn)題奠定了基礎(chǔ)。信號(hào)的稀疏重建與壓縮感知理論有重大的實(shí)用價(jià)值和應(yīng)用前景，已經(jīng)成為信號(hào)領(lǐng)域中一個(gè)新的研究方向 [1]。 20xx 年， IEEE Journal of Selected Topics in Signal Processing 專門出版了一期關(guān)于 CS 的?？?，促進(jìn)了 CS 理論在各個(gè)領(lǐng)域應(yīng)用成果的交流。首先介紹了壓縮感知理論的研究背景及意義，然后介紹了國(guó)內(nèi)外研究背景和現(xiàn)狀，最后整理出全文內(nèi)容的結(jié)構(gòu)安排。這一章著重分析了正交匹配追蹤算法的原理、實(shí)現(xiàn)步驟和 Matlab 的語(yǔ)言實(shí)現(xiàn)。 西安文理學(xué)院本科畢業(yè)設(shè)計(jì)（論文） 第 4 頁(yè) 第二章 壓縮感知理論相關(guān)知識(shí) 壓縮感知理論框架 傳統(tǒng)的信號(hào)采集、編解碼過(guò)程如圖 所示 。 圖 傳統(tǒng)編解碼理論的框圖 壓縮感知理論對(duì)信號(hào)的采樣、壓縮編碼發(fā)生在同一個(gè)步驟 如下圖 所示 ，利用信號(hào)的稀疏性，以遠(yuǎn)低于 Nyquist 采樣率的速率對(duì)信號(hào)進(jìn)行非自適應(yīng)的測(cè)量編碼。 西安文理學(xué)院本科畢業(yè)設(shè)計(jì)（論文） 第 5 頁(yè) 圖 縮感知理論的編解碼框圖 壓縮感知的基本理論及核心問(wèn)題 壓縮感知，也被稱為壓縮傳感或壓縮采樣，是一種利用稀疏的或可壓縮的信號(hào)進(jìn)行信號(hào)重構(gòu)的技術(shù) [3]。即這些信號(hào)是“稀疏”的或“可壓縮”的。為簡(jiǎn)化問(wèn)題，假定這些基是規(guī)范正交的。一般而言，可壓縮信號(hào)是指可以用 K 個(gè)大系數(shù)很好地逼近的信號(hào)，即它在某個(gè)正交基下展開的系數(shù)按一定量西安文理學(xué)院本科畢業(yè)設(shè)計(jì)（論文） 第 6 頁(yè) 級(jí)呈現(xiàn)指數(shù)衰減，具有非常少的大系數(shù)和許多小系數(shù)。 Candes證明了只要信號(hào)在某一個(gè)正交空間具有稀疏性，就能以較低的頻率 ? ?MN?? 采樣信號(hào)，而且可以以高概率重構(gòu)該信號(hào)。 圖 基于 壓縮感知理論 的信號(hào)重構(gòu)過(guò)程 信號(hào)的稀疏表示 壓縮感知的第一步，即對(duì)于信號(hào) X ∈ NR ，如何找到某個(gè)正交基或緊框架 ? ，使其在 ? 上的表示是稀疏的，即信號(hào)的稀疏表示問(wèn)題。 Candes和 Tao研究表明，滿足具有冪次速度衰減的信號(hào)，可利用壓縮感知理論得到恢復(fù)，并且重構(gòu)誤差滿足： 62? ( / l o g ) rrE X X C K N ?? ? ? ? (式 ) 其中 r=1/p– 1/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)。 對(duì)稀疏表示研究的另一個(gè)熱點(diǎn)是信號(hào)在冗余 字典下的稀疏分解。從冗余字典中找到具有最佳線性組合的 K 項(xiàng)原子來(lái)表示一個(gè)信號(hào)，稱作信號(hào)的稀疏逼近或高度非線性逼近。在稀疏分解算法的設(shè)計(jì)方面，基于貪婪迭代思想的 MP(Matching Pursuit)算法表現(xiàn)出極大的優(yōu)越性，但不是全局最優(yōu)解。 西安文理學(xué)院本科畢業(yè)設(shè)計(jì)（論文） 第 8 頁(yè) 信號(hào)的觀測(cè)矩陣 如何設(shè)計(jì)一個(gè)平穩(wěn)的、與變換基 ? 不相關(guān)的 MN? 維的觀測(cè)矩陣 ? ，保證稀疏向量 ? 從 N 維降到 M 維時(shí)重要信息不遭破壞，是第二步要解決的問(wèn)題，也就是信號(hào)低速采樣問(wèn)題。觀測(cè)過(guò)程實(shí)際就是利用 MN? 觀測(cè)矩陣 ? 的 M 個(gè)行向量 ? ?1Mj j? ?對(duì)稀疏系數(shù)向量進(jìn)行投影，即計(jì)算? 和各個(gè)觀測(cè)向量 ??1Mjj?? 之間的內(nèi)積，得到 M 個(gè)觀測(cè)值? ?, 1 , 2 , Mjjyj??? ? ? ? … ,， 記觀測(cè)向量 12( , , y )MY y y? … ， ，即 T C SY X A X? ? ? ? ? ? ? (式 ) 這里，采樣過(guò)程是非自適應(yīng)的，也就是說(shuō)， ? 無(wú)須根據(jù)信號(hào) X 而變化，觀測(cè)的不再是信號(hào)的點(diǎn)采樣而是信號(hào)的更一般的 K 線性泛函。對(duì)此，kk ff ?? ????? 112222 即有限等距性質(zhì)（ RIP）給出了存在確定解的充要條件。 西安文理學(xué)院本科畢業(yè)設(shè)計(jì)（論文） 第 9 頁(yè) 然而，判斷給定的 CSA 是否具有 RIP性質(zhì)是一個(gè)組合復(fù)雜度問(wèn)題。不相干性越強(qiáng)，互相表示時(shí)所需的系數(shù)越多；反之，相 關(guān)性則越強(qiáng)。因此可以從 M 個(gè)觀測(cè)值 12( , , y )MY y y? … ， 中以很高的概率去恢復(fù)長(zhǎng)度為 N 的 K 項(xiàng)稀疏信號(hào)。 Donoho給出了觀測(cè)矩陣所必需具備的三 個(gè)條件 [9]，并指出大部分一致分布的隨機(jī)矩陣都具備這三個(gè)條件，均可作為觀測(cè)矩陣，如：部分 Fourier集、部分 Hadamard集、一致分布的隨機(jī)投影 (uniform Random Projection)集等，這與對(duì) RIP性質(zhì)進(jìn)行研究得出的結(jié)論相一致。 在壓縮感知理論中，由于觀測(cè)數(shù)量 M 遠(yuǎn)小于信號(hào)長(zhǎng)度 N ，因此不得不面對(duì)求解欠定方程組 CSY A X? 的問(wèn)題。因此，求解式（ )的數(shù)值計(jì)算極不穩(wěn)定而且是 NP難問(wèn)題。 基于上述問(wèn)題， 20xx年 1月 Candes和 Romberg提出了不同的信號(hào)恢復(fù)方法，該方法要求對(duì)原信號(hào)具有少量的先驗(yàn)知識(shí)，同時(shí) 也可以對(duì)所求結(jié)果施加適當(dāng)?shù)钠谕匦?，以約束重構(gòu)信號(hào)的特性。該方法針對(duì) BP、 MP和 OMP方法沒有考慮信號(hào)的多尺度分解時(shí)稀疏信號(hào)在各子帶位置的關(guān)系，是將稀疏系數(shù)的樹型結(jié)構(gòu)加以利用，進(jìn)一步提升了重構(gòu)信號(hào)的精度和求解的速度。它將 OMP進(jìn)行一定程度的簡(jiǎn)化，以逼近精度為代價(jià)進(jìn)一步提高了計(jì)算速度 (計(jì)算復(fù)雜度為 O(N))，更加適合于求解大規(guī)模問(wèn)題。 ROMP算法與 OMP算法的不同之處在于，該算法首先根據(jù)相關(guān)原子挑選多個(gè)原子作為候選集，然后從候選集中按照正則化 原則挑選出部分原子，最后將其并入最終的支撐集，從而實(shí)現(xiàn)了原子的快速、有效選擇。 這里主要介紹 CS 理論在成像系統(tǒng)、圖像融合、圖像跟蹤以及數(shù)據(jù)獲取等方面的應(yīng)用。該相機(jī)具有一種全新的相機(jī)結(jié)構(gòu)，使用數(shù)字微鏡陣列完成圖像在偽隨機(jī)二值模型上線性投影的光學(xué)計(jì)算。 圖 單像素相機(jī) （ 2）圖像融合 圖像融合是信息融合范疇內(nèi)以圖像為對(duì)象的研究領(lǐng)域。使其在測(cè)量舉證的作用下，用遠(yuǎn)小于原圖像的數(shù)據(jù)量進(jìn)行計(jì)算得到融合結(jié)果還原為圖像表示，可節(jié)省中間融合所需的計(jì)算量，并且能夠更好地利用原圖像中像素間的內(nèi)在聯(lián)系，是一個(gè)非常值得研究的課題。 基于 CS 理論的目標(biāo)跟蹤。基于 RIP理論，目前已研制出了一些設(shè)備，有萊斯大學(xué)研制的單像素相機(jī)和 A/I轉(zhuǎn)換器，麻省理工學(xué)院研制的編碼孔徑相機(jī)，耶魯大學(xué)研制的超譜成像儀，麻省理工學(xué)院研制的 MRI RF脈沖設(shè)備，伊利諾伊州立大學(xué)研制的 DNA微陣列傳感器。在等距約束性準(zhǔn)則驅(qū)動(dòng)的可壓縮信號(hào)壓縮感知定理中，關(guān)于稀疏字典 ? 和測(cè)量矩陣 ? 僅要求兩者乘積???? 滿足 RIP。雖然基于線性投影的壓縮感知理論能夠直接應(yīng)用于自 然圖像這樣的復(fù)雜高維信號(hào)，但是由于沒有考慮到自然圖像的固有特性，諸如結(jié)構(gòu)多成分性、高階統(tǒng)計(jì)性等 ,對(duì)于自然圖像壓縮采樣本身沒有特殊的指導(dǎo)作用。對(duì)于自然圖像，假如能夠?qū)崿F(xiàn)非線性自適應(yīng)的壓縮測(cè) 量，壓縮感知的壓縮性能勢(shì)必會(huì)獲得大 幅度的提高。目前，基于構(gòu)造方法的自然圖像過(guò)完備字典設(shè)計(jì)具有很好的理論支撐，正則化幾何方法、幾何多尺度分析、基于信息論的 “有效編碼假設(shè) ”為其奠定了堅(jiān)實(shí)廣闊的理論基礎(chǔ)。在等距約束性準(zhǔn)則驅(qū)動(dòng)的可壓縮信號(hào)壓縮感知定理中 ， 要求稀疏字典 Ψ和測(cè)量矩陣 Φ的乘積 Θ=ΦΨ滿足 RIP。 （ 3） 噪聲情形大尺度問(wèn)題的快速魯棒重 建算法 [15]設(shè)計(jì)。 西安文理學(xué)院本科畢業(yè)設(shè)計(jì)（論文） 第 16 頁(yè) 第三章 正交匹配追蹤重建算法 最小 L0范數(shù)模型 從數(shù)學(xué)意義上講，基于壓縮感知理論的信號(hào)重建問(wèn)題就是尋找欠定方程組 (程的數(shù)量少于待解的未知數(shù) )的最簡(jiǎn)單 解的問(wèn)題， L0范數(shù)刻畫的就是信號(hào)中非零元素的個(gè)數(shù)，因而能夠使得結(jié)果盡可能地稀疏。經(jīng)過(guò)數(shù)次迭代，該信號(hào)便可以由一些原子線性表示。 本節(jié)將著重介紹此算法的原理、實(shí)現(xiàn)步驟以及 Matlab 的語(yǔ)言實(shí)現(xiàn)。 OMP的重建算法是在給定迭代次數(shù)的條件下重建，這種強(qiáng)制迭代過(guò)程停止的方法使得 OMP需要非常多的線性測(cè)量來(lái)保證精確重建。 由于在 Matlab 平臺(tái)上對(duì)圖像的處理、小波變換、矩陣的求逆合并等運(yùn)算的實(shí)現(xiàn)較為方便，因此本文首先 選擇在 Matlab 上實(shí)現(xiàn) OMP 算法并對(duì)其進(jìn)行 仿真。 接下來(lái)，取 觀測(cè)向量 M 的長(zhǎng)度為 64，即采樣率 M/N= 對(duì)其進(jìn)行重建。為了進(jìn)一步說(shuō)明 OMP 算法的重構(gòu)效果，本文將用二維圖像繼續(xù)進(jìn)行仿真。原始信號(hào)進(jìn)行了小波變換后，變得更加稀疏，高頻段的信息基本沒了，這樣圖像縮小了很多，便于保存與傳輸。 接下來(lái)，我對(duì) Lena256*256 圖像在采樣率 （ M/N） 分別為 ， ， ， ， 況下 又做了仿真，恢復(fù)圖像如圖 所示 ： 原始圖像 恢復(fù)的圖像 ,采樣率 = 恢復(fù)的圖像 ,采樣率 = 恢復(fù)的圖像 ,采樣率 = 西安文理學(xué)院本科畢業(yè)設(shè)計(jì)（論文） 第 24 頁(yè) 圖 OMP 在不同采樣率下恢復(fù)圖像對(duì)比圖 為了更直觀的對(duì)比 OMP 算法在不同采樣率下的恢復(fù)效果，本文還給出了 OMP算法在采樣率位 ， ， ， ， 時(shí) 重建后的 PSNR 值， 如表 41所示： 表 41 不同 M/N 與 PSNR 實(shí)驗(yàn)結(jié)果值比較 M/N PSNR 由以上表格可以看出，隨著采樣率 M/N 值的逐漸增大， PSNR 值也逐漸增大?；粉櫵惴ň褪腔谝陨显韽亩_(dá)到重構(gòu)和對(duì)白噪聲去噪的目的。 恢復(fù)的圖像，采樣率 = 恢復(fù)的圖像 ,采樣率 = 西安文理學(xué)院本科畢業(yè)設(shè)計(jì)（論文） 第 25 頁(yè) 首先先選擇一張圖片，本文采用的圖片如圖 所示： 原始圖像 圖 原始圖像 選擇好原始圖片后，我們要對(duì)圖片進(jìn)行讀取數(shù)據(jù) x=imread(39。仿真如下圖 ： O r i g i n e i m a g e N = 6 5 5 3 6 B P , s a m p = 3 9 . 8 4 3 8 % t i m e = 5 7 . 0 3 8 s e cO M P , s a m p = 3 9 . 8 4 3 8 % t i m e = 1 . 8 0 1 s e c FD R , s a m p = 3 9 . 8 4 3 8 % t i m e = 0 . 7 0 5 s e c 圖 原始圖像與 BP、 OMP、 STOMP_FDR 恢復(fù)對(duì)比圖 西安文理學(xué)院本科畢業(yè)設(shè)計(jì)（論文） 第 26 頁(yè) 圖 從圖像的重構(gòu)質(zhì)量上可以看出， OMP 的重建效果次于 BP 算法 但優(yōu)于STOMP_FDR 算法。 （ 2） 對(duì)于二 維圖像信號(hào)，正交匹配算法（ OMP）的重構(gòu)不是最好，但它的重建時(shí)間比較短，雖然基追蹤（ BP）的還原圖像是最清晰的，但它的重建時(shí)間遠(yuǎn)遠(yuǎn)高于其它兩種算法。西安文理學(xué)院本科畢業(yè)設(shè)計(jì)（論文） 第 27 頁(yè) 結(jié)束語(yǔ) 近年來(lái)，信號(hào)處理領(lǐng)域出現(xiàn)了一種新的信息采樣理論 —— 壓縮感