【正文】 0。言樹之背，養(yǎng)育之恩，無以回報?；叵朐诖髮W(xué)求學(xué)的四年，心中充滿無限感激和留戀之情。 OMP 算法在原子的選取方面就存在缺陷，因此，在貪婪算法方面還需要繼續(xù)研究。該理論突破了傳統(tǒng)的以 Nyquist 定理為基準(zhǔn)的信號處理方法，實(shí)現(xiàn)了在獲取數(shù)據(jù)的同時對其進(jìn)行適當(dāng)?shù)膲嚎s，進(jìn)一步降低了信號處理的時間和器件成本。由此表明： OMP 算法能夠兼顧重構(gòu)時間和重構(gòu)質(zhì)量，是一種比較實(shí)用的重建算法。正交匹配追蹤算法（ OMP）在重構(gòu)時每次迭代得到 X? 的支撐集的一個原子，只是通過遞推對已經(jīng)選擇原子幾何進(jìn)行正交化以 保障迭代的最優(yōu)性，從而減少迭代次數(shù)。由實(shí)驗(yàn)結(jié)果可得出，原始圖像與重構(gòu)圖像之間的重構(gòu)誤差為 。由計算結(jié)果可知二者的相對誤差在 左 右。 OMP 算法實(shí)現(xiàn)步驟 OMP算法的具體步驟如下： (1)初始余量 Yr?0 ，迭代次數(shù) 1?n ，索引值集合 ?? ? ， ?J ? ； (2)計算相關(guān)系數(shù) u,并將 u中最大值對應(yīng)的索引值存入 J 中； (3)更新支撐集 ?? ，其中 0J???? ； (4)應(yīng)用 (式 )得到 ?X ，同時用 (式 )對余量進(jìn)行更新； (5)若 2???rrnew ，令 newrr? ， 1??nn ，轉(zhuǎn)步驟 (2)；否則，停止迭代。 匹配追蹤類算法通過求余量 r與感知矩陣 ? 中各個原子之間內(nèi)積的絕對值，來計算相關(guān)系數(shù) u： ? ?| , , 1 , 2 , Nj j ju u u r j?? ? ? … ， （式 ） 并采用最小二乘法進(jìn)行信號逼近以及余量更新 : 2m ina r g XYX Ri ??? ???? （式 ） 西安文理學(xué)院本科畢業(yè)設(shè)計（論文） 第 17 頁 ?r,new YX?? ? ? （式 ） 正交匹配追蹤算法 (OMP) 正交匹配追蹤算法（ Orthogonal Matching Pursuit,OMP），是最早的貪婪迭代算法之一，是壓縮感知信號檢測的一種算法。通常，基于最小化松弛算法的計算復(fù)雜度相對較高。這項(xiàng)工作對于稀疏字典和壓縮感知都將 是重要的理論完善。 例如，基于圖像多成分性的特點(diǎn)能夠提高重建圖像的峰值信噪比和視覺效果。但是，壓縮感知理論還有很多亟待解決的問題，為此本西安文理學(xué)院本科畢業(yè)設(shè)計（論文） 第 14 頁 文列出了壓縮感知有待解決的幾個關(guān)鍵問題。目標(biāo)跟蹤的實(shí)質(zhì)是通過對圖像傳感器拍攝到的視頻序列進(jìn)行分析，計算出目標(biāo)在每幀圖像中的位置、大小和運(yùn)動速度。 ARIZONA 大學(xué) Baheti和 Neifeld 設(shè)計了具有特定功能的結(jié)構(gòu)成像設(shè)備， DUCK 大學(xué)研制了單景光譜成像裝置。然而實(shí)際應(yīng)用中信號的稀疏度 K 往往是未知的，由此出現(xiàn)了對稀疏度 K 自適應(yīng)的稀疏自適應(yīng)匹配追蹤算法 (Sparsity Adaptive Matching Pursuit,SAMP)，它通過設(shè)置一個可變步長，逐步對信號稀疏度進(jìn)行估計，因此可以在 K未知的情況下獲得較好的重建效果，速度也遠(yuǎn)快于 OMP算法。例如 OMP算法，需要 M cK? ， 2ln( )cN?個采樣點(diǎn)數(shù)才能以較高的概率恢復(fù)信號，信號重構(gòu)的計算復(fù)雜度為 2()ONK 。于是稀疏分解的已有算法可以應(yīng)用到 CS重構(gòu)中。對于任何穩(wěn)定的重構(gòu)算法是否存在一個真實(shí)的確定性的觀測矩陣仍是一個有待研究的問題。例如，可以生成多個零均值、方差為 1/N 的隨機(jī)高斯函數(shù)，將它們作為觀測矩陣 ? 的元素 j? ，使得 CSA 以很高的概率具有 RIP性質(zhì)。即，要想使信號完全重構(gòu)，必須保證觀測矩陣不會把兩個不同的 K 項(xiàng)稀疏信號映射到同一個采樣集合中，這就要求從觀測矩陣中抽取的每 M 個列向量構(gòu)成的矩陣是非奇異的。觀測器的設(shè)計目的是如何采樣得到 M 個觀測值，并保證從中能重構(gòu)出長度為 N 的信號 X 或者基 ? 下等價的稀疏系數(shù)向量 ? 。因此，目前信號在冗余字典下的稀疏表示的研究 集中在兩個方面： (1)如何構(gòu)造一個適合某一類信號的冗余字典； (2)如何設(shè)計快速有效的稀疏分解算法。 Peyre把變換基是正交基的條件擴(kuò)展到了由多個正交基構(gòu)成的正交基字典。那么就可以利用優(yōu)化求解方法 [5]從觀測集合中精確或高概率地重構(gòu)原始信號 X 。顯然， X 和 ?是同一個信號的等價表示， X 是信號在時域的表示， ? 則是信號在 ? 域的表示。壓縮感知跳過了采集 N 個樣本這一步驟，直接獲得壓縮的信號的表示。采用這種傳統(tǒng)的編解碼方法，由于信號的采樣速率不得低于信號帶寬的 2 倍，使得硬件系統(tǒng)面臨著很大的采樣速率的 壓力。首先介紹了壓縮感知的框架，進(jìn)而對信號的稀疏變換、觀測矩陣的設(shè)計以及信號的重構(gòu)三個主要方面的內(nèi)容展開進(jìn)一步詳述，最后詳細(xì)介紹了壓縮感知理論在不同領(lǐng)域的應(yīng)用及有待解決的幾個問題。 2．國內(nèi)研究狀況及發(fā)展趨勢 在國內(nèi)，一些高校和科研機(jī)構(gòu)也開始跟蹤 CS 的研究 ,如清華大學(xué)、中科院電子所、西安交通大學(xué)和西安電子科技大學(xué)等。因此研究如何突破以奈奎斯特采樣定理為基礎(chǔ)的信息的提取、處理、融合、存儲、及傳輸是推動信息領(lǐng)域發(fā)展的關(guān)鍵。 (3) reconstruction algorithms, using a reconstruction algorithm to ensure the accuracy of the signal reconstruction, the whole process can be considered as the solve to a optimization problem. This paper introduces CS and most mature pression perception algorithm at presentOrthogonal matching algorithm. Through the MATLAB design realize basic orthogonal matching algorithms, Through the MATLAB design realize basic orthogonal matching algorithm of onedimensional, twodimensional signal processing simulation. Key words： Compressed sensing。 基于壓縮感知的正交匹配算法圖像重建 摘要： 壓縮感知理論是由 Donoho 和 Candes 提出的一種充分利用信號稀疏性的全新的信號采樣理論。 (2) Observation matrix, it is irrelevant with the orthogonal basis。 實(shí)際上，奈奎斯特采樣定理是信號精確重構(gòu)的充分條件而不是必要條件，奈奎斯特采樣定理并不是唯一、最優(yōu)的采樣理論。 本課題在國內(nèi)外的發(fā)展現(xiàn)狀 1．國外研究狀況及發(fā)展趨勢 目前， CS 理論與應(yīng) 用研究正在如火如荼地進(jìn)行：在美國、歐洲等許多國家的知名大學(xué)如麻省理工學(xué)院、萊斯大學(xué)、斯坦福大學(xué)、杜克大學(xué)等都成立了專門課題組對 CS 進(jìn)行研究； 20xx 年，貝爾實(shí)驗(yàn)室 ,Intel,Google 等知名公司也開始組織研究 CS；20xx 年 ,美國空軍實(shí)驗(yàn)室和杜克大學(xué)聯(lián)合召開了 CS 研討會，美國國防先期研究計劃署 (DARPA)和國家地理空間情報局 (NGA)等政府部門成員與數(shù)學(xué)、信號處理、微波遙西安文理學(xué)院本科畢業(yè)設(shè)計（論文） 第 3 頁 感等領(lǐng)域的專家共同探討了 CS應(yīng)用中的關(guān)鍵問題；第二次以《壓縮感知和高維數(shù)據(jù)分析》為主題的研討會也將在 20xx 年的 7月 26 至 28日在杜 克大學(xué)召開 [2]。 第二章：壓縮感知理論相關(guān)知識。 編碼端先對信號進(jìn)行采樣，再對所有采樣值進(jìn)行變換，并將其中重要系數(shù)的幅度和位置進(jìn)行編碼，最后將編碼值進(jìn)行存儲或傳輸：信號的解碼過程僅僅是編碼的逆過程，接收的信號經(jīng)解壓縮、反變換后得到恢復(fù)信號?；蛘呖梢哉f是信號在采樣的同時被壓縮，從而在很大程度上降低了采樣率。把向量? ?1iNi ?? 作為列向量形成 NN? 的 基矩陣 ? =[ 12,?? ?, N? ]，于是任意信號 X 都可以表示為： X??? (式 ) 其中 ? 是投影系數(shù)， ? =? ? ,iiX? ? ? ? ???構(gòu)成的 N 1的列向量。即，設(shè)長度為 N 的信號 X在某正交基或框架 ? 上的變換系數(shù)是稀疏的，如果我們可以用一個與變換基 ? 不相關(guān)的觀測基： MN? ? ?MN?? 對系數(shù)向量進(jìn)行線性變換，并得到觀測集合 :1YM? 。如何找到或構(gòu)造適合一類信號的正交基，以求得信號的最稀疏表示，這是一個有待進(jìn)一步研究的問題。從非線性逼近角度來講，信號的稀疏逼近包含兩個層面：一是根據(jù)目標(biāo)函數(shù)從一個給定的基庫中挑選好的或最好的基；二是從這個好的基中挑選最佳的 K項(xiàng)組合。 壓縮感知理論中，通過變換得到信號的稀疏系數(shù)向量 TX??? 后，需要設(shè)計壓縮采樣系統(tǒng)的觀測部分，它圍繞觀測矩陣 ? 展開。這個充要條件和 Candes、 Tao等人提出的稀疏信號在觀測矩陣作用下必須保持的幾何性 質(zhì)相一致。通過選擇高斯隨機(jī)矩陣 ? 作為觀測矩陣即可高概率保證不相干性和 RIP性質(zhì)。但是，使用上述各種觀測矩陣進(jìn)行觀測后，都僅僅能保證以很高的概率去恢復(fù)信號，而不能保證百分之百地精確重構(gòu)信號。注意，這和稀疏分解問題從數(shù)學(xué)意義上講是同樣的問題。匹配追蹤類算法都是基于貪婪迭代算法，以多于 BP算法需要的采樣數(shù)目換取計算復(fù)雜度的降低。最近出現(xiàn)的子空間匹配追蹤算法 (Subspace Pursuit， SP)和壓縮采樣匹配追蹤算法 (Compressive Sampling Matching Pursuit， CoSaMP)引入了回退篩選的思想，這些算法的重建質(zhì)量與線性規(guī)劃方法相當(dāng)，同時重建復(fù)雜度低，但是這些算法都是建立在稀疏度 K 已知的基礎(chǔ)上。它可利用單一的信號光子檢測器采樣得到比圖像像素點(diǎn)數(shù)少得多的點(diǎn)恢復(fù)圖像，并具有對圖像波長自適應(yīng)的能 力，這種自適應(yīng)能力是傳統(tǒng)的 CCD 和 CMOS 成像器件所不具備的。 西安文理學(xué)院本科畢業(yè)設(shè)計（論文） 第 13 頁 圖 CS 用于圖像融合的流程框圖 （ 3）目標(biāo)跟蹤 視頻目標(biāo)跟蹤是使用可見、紅外等被動式成像傳感器實(shí)現(xiàn)目標(biāo)測量的核心技術(shù)之一，是 目標(biāo)識別、視頻圖像的壓縮編碼等高層次的視頻處理和應(yīng)用理解的基礎(chǔ)，也是視頻監(jiān)控技術(shù)自動化和實(shí)時應(yīng)用的關(guān)鍵。 壓縮感知有待研究的幾個問題 壓縮感知經(jīng)過近年來的迅猛發(fā)展，已基本形成了自己的理論框架，包括基礎(chǔ)理論、實(shí)現(xiàn)方法和實(shí)際應(yīng)用。事實(shí)上，相對于一維離散信號 ,自然圖像的復(fù)雜性和高維性使之需要自適應(yīng)的壓縮采樣和重建算法。但是，從國際上關(guān)于過完備字典設(shè)計的整體情況看，基于學(xué)習(xí)的自然圖像過完備字典設(shè)計的工作非常少，主要在于：設(shè)計難度大、性能要求高，同時缺乏嚴(yán)格的理論支撐?？焖俜€(wěn)定的信號重建算法是將壓縮感知理論推向?qū)嵱玫年P(guān)鍵技術(shù)之一，特別適用于糾錯編碼、核磁共振成像、 NMR波譜研究等大尺度問題。但是由于信號在已選定原子 (感知矩陣的列向 量 )集合上的投影的非正交性使得每次迭代的結(jié)果可能是次最優(yōu)的，因此為獲得較好的收斂效果往往需要經(jīng)過較多的迭代次數(shù)?？傊载澙返姆椒ㄟx擇 ?的列，使得在 每次迭代中所選擇的列與當(dāng)前的冗余向量最大程度地相關(guān)，從測量向量中減去相關(guān)部分并反復(fù)迭代，直到迭代次數(shù)達(dá)到稀疏度 K ，強(qiáng)制迭代停止。 西安文理學(xué)院本科畢業(yè)設(shè)計（論文） 第 21 頁 重建信號生成圖如圖 ： 圖 M=64 時，原始信號、重構(gòu) 信號 對比圖 由圖 原始信號和重構(gòu)信號的效果對比圖 可看出，當(dāng) M=64 時， 能夠較好的恢復(fù)出原始信號。接下來就要對這個小波變換的信號進(jìn)行測量和重構(gòu)，當(dāng)它們重構(gòu)信號后，經(jīng)過小波逆變換后得到恢復(fù)的圖像（此過程中測量數(shù)選取的是 M=190）。它主要的目的是運(yùn)作此定方程的解。但從重建時間來看， OMP 算法次于 STOMP_FDR 但明顯優(yōu)于BP 算法。它利用原始圖像或信號的稀疏性先驗(yàn)知識，通過適當(dāng)?shù)膬?yōu)化算 法，可以由少量的觀測值或采樣值對信號進(jìn)行精確重建。 2）貪婪系列算法雖然計算簡單，實(shí)現(xiàn)方便，重建效果也較好，但是它不能直接求解原始的優(yōu)化 問題，在重構(gòu)質(zhì)量上還次于基于最小 L1 范數(shù)的算法。 西安文理學(xué)院本科畢業(yè)設(shè)計（論文） 第 28 頁 致謝 時間如梭，轉(zhuǎn)眼畢業(yè)在即。 另外，我必須感謝我的父母。 % 測量數(shù) (M=K*log(N/K),至少 40,但有出錯的概率 ) f1=50。 % 完整信號 plot(x,39。 % 信號頻率 2 f3=200。 % 獲得線性測量 %% 3. 正交匹配追蹤法重構(gòu)信號 (本質(zhì)上是 1范數(shù)最優(yōu)化問題 ) m=2*K。 % 恢復(fù)矩陣的所有列向量 product(col)=abs(T(:,col)39。 % 最小二乘 ,使殘差最小 r_n=sAug_t*aug_y。39。x)/norm(x) % 重構(gòu)誤差