基于MATLAB的圖像壓縮感知算法的實現(xiàn)畢業(yè)設(shè)計說明書

《基于MATLAB的圖像壓縮感知算法的實現(xiàn)畢業(yè)設(shè)計說明書》由會員分享，可在線閱讀，更多相關(guān)《基于MATLAB的圖像壓縮感知算法的實現(xiàn)畢業(yè)設(shè)計說明書（50頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、 畢業(yè)設(shè)計（論文） 基于MATLAB的圖像壓縮感知算法的實現(xiàn) 系： 電氣工程系 專業(yè)： 電子信息工程 目錄 目錄 I 第1章 緒論 3 1.1 研究背景和意義 3 1.2 數(shù)據(jù)壓縮技術(shù) 4 1.2.1 傳統(tǒng)數(shù)據(jù)壓縮技術(shù) 4 1.2.2 壓縮感知理論（Compressed/Compressive Sensing/Sampling, CS） 5 1.

2、3 無線傳感器網(wǎng)絡(luò) 7 1.3.1 無線傳感器網(wǎng)絡(luò)概述 7 1.3.2 無線傳感器網(wǎng)絡(luò)數(shù)據(jù)壓縮的必要性 9 1.4 本文主要工作和內(nèi)容安排 10 第2章 壓縮感知理論 11 2.1壓縮感知的前提條件—稀疏性和不相干性 11 2.2 三個關(guān)鍵技術(shù) 14 2.3信號的稀疏表示 15 2.4 觀測矩陣設(shè)計 17 2.5 稀疏信號的重構(gòu) 19 2.6 重構(gòu)算法 20 2.7 壓縮感知優(yōu)勢及不足 21 2.8 壓縮感知在傳感網(wǎng)中的觀測方式 22 第3章 壓縮感知理論應(yīng)用概述 24 3.1 壓縮成像 24 3.2 模擬信息轉(zhuǎn)換 24 3.3 生物傳感 25 3.4 本章小

3、結(jié) 25 第4章 CS在無線傳感網(wǎng)中的應(yīng)用 26 4.1 研究背景 26 4.1.1 基于感知數(shù)據(jù)相關(guān)性的壓縮 26 4.1.2傳統(tǒng)壓縮重構(gòu)方法 27 4.1.3 圖像壓縮重構(gòu)質(zhì)量的評價 27 4.2 壓縮感知理論算法對一維信號的實現(xiàn) 29 4.2.1 CS用于WSN的優(yōu)勢 29 4.2.2 觀測重構(gòu)模型 30 4.2.2 正交匹配追蹤算法（OMP） 30 4.2.3 算法的實現(xiàn)及結(jié)果分析 31 4.3 壓縮感知理論算法對二維圖像重構(gòu)的實現(xiàn) 35 4.3.1 基于小波變換的分塊壓縮感知理論 35 4.3.2 實現(xiàn)步驟 36 4.3.3 重構(gòu)結(jié)果及分析 39 4.4

4、 本章小結(jié) 42 第5章 總結(jié)與展望 43 5.1 工作總結(jié) 43 5.2 后續(xù)展望 43 參考文獻 44 致謝 46 附錄 47 摘要 數(shù)據(jù)壓縮技術(shù)是提高無線數(shù)據(jù)傳輸速度的有效措施之一。傳統(tǒng)的數(shù)據(jù)壓縮技術(shù)是基于奈奎斯特采樣定律進行采樣，并根據(jù)數(shù)據(jù)本身的特性降低其冗余度，從而達到壓縮的目的。近年來出現(xiàn)的壓縮感知理論（Compressed Sensing,CS）則不受制于奈奎斯特采樣定律，它是采用非自適應(yīng)線性投影來保持信號的原始結(jié)構(gòu)，以直接采集壓縮后的數(shù)據(jù)的方式，從盡量少的數(shù)據(jù)中提取盡量多的信息。 本文闡述了壓縮感知方法的基本原理，分析了CS理論框架及關(guān)

5、鍵技術(shù)問題，介紹了壓縮感知技術(shù)應(yīng)用于無線傳感的優(yōu)勢，并著重介紹了信號稀疏變換、觀測矩陣設(shè)計和重構(gòu)算法三個方面的最新進展，對研究中現(xiàn)存的難點問題進行了探討。并運用matlab軟件，在離散傅里葉變換（DFT）和離散余弦變換（DCT）分塊CS的基礎(chǔ)上，采用正交匹配追蹤算法（OMP）實現(xiàn)了對一維信號和二維圖像的高概率重構(gòu)。將重構(gòu)結(jié)果與原始信號對比，結(jié)果表明，只要采樣數(shù)M（遠小于奈奎斯特定理所需要的采樣率）能夠包含圖像所需要的有用信息時，CS算法就能精確的完成對圖像的重構(gòu)，并且重構(gòu)效果也比較好。 關(guān)鍵詞：壓縮感知 無線傳感 正交匹配 稀疏表示 觀測矩陣

6、 Abstract The data compression technology is one of the efficient measures for increasing the speed of wireless data communication. Traditional data compression technology is based on Nyquist sampling theorem, reaching the goal of compression by decreasing redundancy of infor

7、mation. In recent years, Compressed Sensing(CS) comes out as a new sampling theory, it does not have to obey Nyquist sampling theorem, and it can keep the original structure of signals by attaining the non-adaptive linear projections. So, CS can gather the compressed data directly and get more infor

8、mation from less data. This paper reviews the theoretical framework and the key technical problems of compressed sensing and introduces the latest developments of signal sparse representation, design of measurement matrix and reconstruction algorithm. Then this paper also discusses the existing di

9、fficult problems. Based on the discrete fourier transform (DFT) and discrete cosine transform (DCT), we use MATLAB software, realizes the accurate reconstruction of one-dimension signal two-dimension image by applying the OMP algorithm. Then make a comparison to the reconstruction of signal to origi

10、nal signals and make a conclusion. If only the sampling measurements M (far less than Nyquist sampling measurements ) contain the useful information of signals, CS algorithm can complete the accurate reconstruction, and the effect of reconstruction signal is good too. Key words: compressed sensi

11、ng wireless sensor networks orthogonal matching pursuit sparse presentation measurement matri 50 第1章 緒論 在當(dāng)今的信息社會，電腦、手機、傳感器、驅(qū)動器等都要連接到因特網(wǎng)，這樣的無線通信系統(tǒng)中，將會產(chǎn)生并且傳播大量數(shù)據(jù)信息，從而對信號的采樣、存儲、傳輸和恢復(fù)造成巨大壓力，增加了通信設(shè)備的成本。對人們來說，如何有效的處理這些數(shù)據(jù)，成為一個新的挑戰(zhàn)。近幾年來，在信號處理領(lǐng)域出現(xiàn)的壓縮感知理論（CS）打破了傳統(tǒng)采樣過程中信號采樣速率必須達到信號帶寬兩倍以上才能精確重構(gòu)

12、原始信號的奈奎斯特采樣定理，使得信息存儲、處理和傳輸?shù)某杀敬蟠蠼档汀? 1.1 研究背景和意義 隨著人們對信息需求量的增加，網(wǎng)絡(luò)通信、多媒體技術(shù)、存儲技術(shù)的發(fā)展越來越快，網(wǎng)絡(luò)的規(guī)模也越來越大，尋找高效的信息技術(shù)來降低數(shù)據(jù)量成為無線傳輸系統(tǒng)中急需處理的問題之一。這是因為數(shù)字化的各類信息的數(shù)據(jù)量十分龐大，若不對其進行有效的壓縮就難以得到實際的應(yīng)用，因此，數(shù)據(jù)壓縮技術(shù)成為人們研究的一項重要技術(shù)。無線傳感器網(wǎng)絡(luò)是近來研究的熱點方向之一。它是由分布在監(jiān)測區(qū)域內(nèi)的大量微型傳感器節(jié)點通過無線電通信而形成的一個自組織網(wǎng)絡(luò)系統(tǒng)。這個系統(tǒng)的目的是協(xié)作的感知、采集和處理網(wǎng)絡(luò)覆蓋區(qū)域里被監(jiān)測對象的信息，并將結(jié)果發(fā)送

13、給用戶。在一個傳感器網(wǎng)絡(luò)中，常常包含大量傳感器節(jié)點，每個傳感器都會采集大量的數(shù)據(jù)。這些數(shù)據(jù)將會被傳輸?shù)揭粋€控制中心,也會在各個節(jié)點之間傳輸，在這種分布式傳感網(wǎng)絡(luò)中，數(shù)據(jù)傳輸功耗和帶寬需求非常大，所以，如何對這樣的分布式信號進行壓縮，從而減小通信開銷已經(jīng)成為非常緊迫的需求。 壓縮感知理論與傳統(tǒng)奈奎斯特采樣定理不同，它指出，只要信號是可壓縮的或在某個變換域是稀疏的，那么就可以用一個與變換基不相關(guān)的觀測矩陣將變換所得高維信號投影到一個低維空間上，然后通過求解一個優(yōu)化問題就可以從這些少量的投影中以高概率重構(gòu)出原信號，可以證明這樣的投影包含了重構(gòu)信號的足夠信息。 在該理論框架下，采樣速率不決定于信號的

14、帶寬，而決定于信息在信號中的結(jié)構(gòu)和內(nèi)容。 事實上，壓縮感知理論的某些抽象結(jié)論源于Kashin創(chuàng)立的范函分析和逼近論， 最近由Cands，Romberg ，Tao和Donoho等人構(gòu)造了具體的算法并且通過研究表明了這一理論的巨大應(yīng)用前景。從信號分析角度來講，傅立葉變換是信號和數(shù)字圖像處理的理論基礎(chǔ)，小波分析將信號和數(shù)字圖像處理帶入到一個嶄新的領(lǐng)域。 多尺度幾何分析是繼小波分析后的新一代信號分析工具，它具有多分辨、局部化和多方向性等優(yōu)良特性，更適合于處理圖像等高維信號。 這些研究工作都為壓縮感知理論奠定了基礎(chǔ)。顯然，在壓縮感知理論中，圖像/信號的采樣和壓縮同時以低速率進行，使傳感器的采樣和計算成本

15、大大降低，而信號的恢復(fù)過程是一個優(yōu)化計算的過程。 因此，該理論指出了將模擬信號直接采樣壓縮為數(shù)字形式的有效途徑，具有直接信息采樣特性。 由于從理論上講任何信號都具有可壓縮性，只能找到其相應(yīng)的稀疏表示空間，就可以有效地進行壓縮采樣，這一理論必將給信號采樣方法帶來一次新的革命。 1.2 數(shù)據(jù)壓縮技術(shù) 數(shù)據(jù)壓縮技術(shù)就是對原始數(shù)據(jù)進行數(shù)據(jù)編碼或者壓縮編碼，從而用最少的數(shù)碼來表示信源發(fā)出的信號。數(shù)據(jù)壓縮的對象很廣泛，可以是通信時間、傳輸帶寬、存儲空間甚至發(fā)射能量。數(shù)據(jù)壓縮的作用是能夠快速地傳輸各種信號；在已有的一些通信干線并行開通更多的多媒體業(yè)務(wù)；緊縮數(shù)據(jù)存儲容量；降低發(fā)信機功率等等。 1.2.

16、1 傳統(tǒng)數(shù)據(jù)壓縮技術(shù) 前較成熟的數(shù)據(jù)壓縮技術(shù)有許多種，按照壓縮后對信息的失真程度,主要分為無損壓縮和有損壓縮。 無損壓縮是利用數(shù)據(jù)中的統(tǒng)計冗余進行壓縮。數(shù)據(jù)中間存在的一些多余成分，稱之為冗余度。例如，在某一份計算機文件中，一些符號會反復(fù)出現(xiàn)、一些符號比其它的符號出現(xiàn)得更頻繁、一些符號總是出現(xiàn)在各數(shù)據(jù)塊中的可預(yù)見的位置上，以上講述的這些冗余部分便可在數(shù)據(jù)編碼中除去或者減少。這種無損壓縮機制可以完全恢復(fù)原始數(shù)據(jù)而不引起任何失真，但是壓縮率卻受到數(shù)據(jù)統(tǒng)計冗余度的理論限制，一般為2:1到5:1。這類方法可以廣泛用于文本數(shù)據(jù)、程序以及特殊應(yīng)用場景的圖像數(shù)據(jù)（如醫(yī)學(xué)圖像）的壓縮。它的主要壓縮機制包括

17、Huffman編碼、算術(shù)編碼、游程編碼和字典編碼等系列。 有損壓縮是利用了人類對圖像或者聲音中的某些頻率成分不敏感的特殊性質(zhì)，允許壓縮過程中損失一定的信息；盡管不能完全恢復(fù)出原始數(shù)據(jù)，但是所缺失的數(shù)據(jù)部分對于我們理解原始圖像的影響很小，卻使得壓縮比大了許多。有損壓縮廣泛應(yīng)用于語音，圖像和視頻數(shù)據(jù)的壓縮。它一般有兩種基本的壓縮機制，一種是有損變換編解碼（如傅立葉變換、離散余弦變換、小波變換），即首先對圖像或者聲音進行采樣、切成小塊、變換到一個新的空間、量化，接著對量化值進行熵編碼；另外一種是預(yù)測編解碼（如脈沖編碼調(diào)制、差分脈沖編碼調(diào)制、自適應(yīng)差分脈沖編碼調(diào)制等），即利用先前的數(shù)據(jù)和隨后解碼的

18、數(shù)據(jù)來預(yù)測當(dāng)前的聲音采樣或者圖像幀，并對預(yù)測數(shù)據(jù)與實際數(shù)據(jù)之間的誤差以及其它一些重現(xiàn)預(yù)測的信息進行量化與編碼。 綜合無損壓縮和有損壓縮的優(yōu)點，還出現(xiàn)了第三類壓縮技術(shù)：混合壓縮。它主要是求取在壓縮效率、壓縮比以及保真度之間的最佳平衡，如靜止圖像壓縮標(biāo)準(zhǔn)JPEG和活動圖像壓縮標(biāo)準(zhǔn)MPEG就是采用混合編碼的壓縮方法。 1.2.2 壓縮感知理論（Compressed/Compressive Sensing/Sampling, CS） 在傳統(tǒng)理論的指導(dǎo)下，信號主要的一些壓縮方法都要基于奈奎斯特采樣定律進行采樣，即信息采樣速率至少為信號帶寬的兩倍。信號的編解碼過程如圖1.1所示：編碼端首先獲得X

19、的N點采樣值，經(jīng)變換后只保留其中K個最大的投影系數(shù)并對它們的幅度和位置編碼，最后將編得的碼值進行存儲或傳輸。解壓縮僅是編碼過程的逆變換。實際上，采樣得到的大部分?jǐn)?shù)據(jù)都是不重要的，即K值很小，但由于奈奎斯特采樣定理的限制，采樣點數(shù)N可能會非常大，采樣后的壓縮是造成資源浪費的根本所在。 圖1.1 傳統(tǒng)編解碼理論框圖 CS 理論的信號編解碼框架和傳統(tǒng)的框架大不一樣，如圖1.2 所示。CS 理論對信號的采樣、壓縮編碼發(fā)生在同一個步驟，利用信號的稀疏性，以遠低于Nyquist采樣率的速率對信號進行非自適應(yīng)的測量編碼。測量值并非信號本身，而是從高維到低維的投影值，從數(shù)學(xué)角度看，每個測量

20、值是傳統(tǒng)理論下的每個樣本信號的組合函數(shù)，即一個測量值已經(jīng)包含了所有樣本信號的少量信息。解碼過程不是編碼的簡單逆過程，而是在盲源分離中的求逆思想下，利用信號稀疏分解中已有的重構(gòu)方法在概率意義上實現(xiàn)信號的精確重構(gòu)或者一定誤差下的近似重構(gòu)，解碼所需測量值的數(shù)目遠小于傳統(tǒng)理論下的樣本數(shù)。 壓縮感知的核心思想是壓縮和采樣合并進行，并且測量值遠小于傳統(tǒng)采樣方法的數(shù)據(jù)量，突破了香農(nóng)采樣定理的瓶頸，使高分辨率的信號采集成為可能。 壓縮感知理論主要包括信號的稀疏表示、隨機測量和重構(gòu)算法等三個方面。稀疏表示是應(yīng)用壓縮感知的先驗條件，隨機測量是壓縮感知的關(guān)鍵過程，重構(gòu)算法是獲取最終結(jié)果的必要手段。

21、圖1.2 CS理論下數(shù)據(jù)的編解碼過程 壓縮感知關(guān)鍵要素包括稀疏表示、測量矩陣和重構(gòu)算法。 信號在某種表示方式下的稀疏性，是壓縮感知應(yīng)用的理論基礎(chǔ)，經(jīng)典的稀疏化的方法有離散余弦變換（DCT）、傅里葉變換（FFT）、離散小波變換（DWT）等。 最近幾年，對稀疏表示研究的另一個熱點是信號在冗余字典下的稀疏分解。 這是一種全新的信號表示理論：用超完備的冗余函數(shù)庫取代基函數(shù)，稱之為冗余字典，字典中的元素被稱為原子。目前信號在冗余字典下的稀疏表示的研究集中在兩個方面：一是如何構(gòu)造一個適合某一類信號的冗余字典，二是如何設(shè)計快速有效的稀疏分解算法。目前常用的稀疏分解算法大致可分為匹配追蹤（M

22、atching Pursuit）和基追蹤（Basis Pursuit）兩大類。 壓縮感知理論中，通過變換得到信號的稀疏系數(shù)后，需要設(shè)計壓縮采樣系統(tǒng)的觀測部分，它圍繞觀測矩陣展開。觀測器的設(shè)計目的是如何采樣得到M個觀測值，并保證從中能重構(gòu)出長度為N的信號X或者稀疏基基下等價的稀疏系數(shù)向量。 CandeS和Tao等證明:獨立同分布的高斯隨機測量矩陣可以成為普適的壓縮感知測量矩陣。2007年Candes等研究者建立了著名的約束等距性（RIP）理論，即要想使信號完全重構(gòu)，必須保證觀測矩陣不會把兩個不同的 K項稀疏信號映射到同一個采樣集合中，這就要求從觀測矩陣中抽取的每M個列向量構(gòu)成的矩陣是非奇異的

23、。 Donoho給出壓縮感知概念的同時定性和定量的給出測量矩陣要滿足三個特征：(1)由測量矩陣的列向量組成的子矩陣的最小奇異值必須大于一定的常數(shù)；(2)測量矩陣的列向量體現(xiàn)某種類似噪聲的獨立隨機性；(3)滿足稀疏度的解是滿足1范數(shù)最小的向量。 目前常用的測量矩陣包括： （1）隨機高斯矩陣。矩陣每個元素獨立地服從均值為0，方差為的高斯分布。 （2）隨機貝努利矩陣。矩陣的每個元素獨立地服從對稱的貝努利分布，等概率為或-。 （3）部分正交矩陣。先生成NN的正交矩陣U（如傅里葉矩陣），然后在矩陣U中隨機地選取M行向量，對MN矩陣的列向量進行單位化得到測量矩陣。 （4）部

24、分哈達瑪矩陣。生成大小為NN的哈達瑪矩陣，然后在生成矩陣中隨機地選取M行向量，構(gòu)成一個MN的矩陣。 （5）托普利茲和循環(huán)矩陣。首先生成一個向量u，由向量u生成相應(yīng)的輪換矩陣或托普利茲矩陣U，然后在矩陣U中隨機地選取其中的M行而構(gòu)造的矩陣Φ。 （6）稀疏隨機矩陣。首先生成一個零元素的矩陣Φ，在矩陣Φ的每一個列向量中，隨機地選取d個位置，然后在所選取的位置的值賦為1。 壓縮感知的重構(gòu)算法主要分為兩大類，一是貪婪算法，它是通過選擇合適的原子并經(jīng)過一系列的逐步遞增的方法實現(xiàn)信號矢量的逼近，此類算法主要包括匹配跟蹤算法、正交匹配追蹤算法、補空間匹配追蹤算法等。二是凸優(yōu)化算法，它是把0范數(shù)放

25、寬到1范數(shù)通過線性規(guī)劃求解的，此類算法主要包括梯度投影法、基追蹤法、最小角度回歸法等。凸優(yōu)化算法算法比貪婪算法所求的解更加精確，但是需要更高的計算復(fù)雜度。 此外，迭代閾值法也得到了廣泛的應(yīng)用，此類算法也較易實現(xiàn)，計算量適中，在貪婪算法和凸優(yōu)化算法中都有應(yīng)用。但是，迭代閾值法對于迭代初值和閾值的選取均較敏感，且不能保證求出的解是稀疏的。 就目前主流的兩種重建算法而言，基于1范數(shù)最小的重建算法計算量巨大，對于大規(guī)模信號無法應(yīng)用；貪婪算法雖然重建速度快，但是在信號重建質(zhì)量上還有待提高。 目前，上述理論已經(jīng)應(yīng)用到各個領(lǐng)域，如傳感網(wǎng)、頻譜感知、雷達、醫(yī)學(xué)信號處理、信道預(yù)測等方面,取得了很好

26、的效果。以上是關(guān)于壓縮感知理論與分布式壓縮感知理論的簡單介紹，詳細(xì)闡述將在第二章和第三章進行展開。 1.3 無線傳感器網(wǎng)絡(luò) 無線傳感器網(wǎng)絡(luò)是計算、通信和傳感器這三項技術(shù)相結(jié)合的產(chǎn)物，一開始在軍事應(yīng)用中收集數(shù)據(jù)，對戰(zhàn)場情況和威脅及其重要程度進行適時的完整評價，后發(fā)展到民事運用，如監(jiān)控大型設(shè)備，災(zāi)區(qū)臨時通信，衛(wèi)生保健等等。 1.3.1 無線傳感器網(wǎng)絡(luò)概述 無線傳感器網(wǎng)絡(luò)一般由若干傳感器節(jié)點組成，節(jié)點是組成無線傳感器網(wǎng)絡(luò)的基本單位，它負(fù)責(zé)完成采集信息、融合并傳輸數(shù)據(jù)的功能。每一個傳感器節(jié)點由數(shù)據(jù)采集模塊（傳感器、A/D轉(zhuǎn)換器）、數(shù)據(jù)處理和控制模塊（微處理器、存儲器）、通信模塊（無線

27、收發(fā)器）和供電模塊（電池、DC/DC能量轉(zhuǎn)換器等）組成，如圖1-3所示。 圖1.3 無線傳感器網(wǎng)絡(luò)節(jié)點結(jié)構(gòu)圖 其中，數(shù)據(jù)采集模塊負(fù)責(zé)感知所需要的信息，數(shù)據(jù)處理和控制模塊負(fù)責(zé)對感知所得的信息和接收信息進行處理，通信模塊負(fù)責(zé)與其他節(jié)點進行通信，即發(fā)送或者接收信息，供電模塊則負(fù)責(zé)提供所需要的能量。 根據(jù)節(jié)點在傳感網(wǎng)網(wǎng)絡(luò)體系中所起作用的不同，節(jié)點在網(wǎng)絡(luò)中可以充當(dāng)數(shù)據(jù)采集者、數(shù)據(jù)處理中轉(zhuǎn)站或簇頭節(jié)點幾種角色： （1）數(shù)據(jù)采集者，這類節(jié)點的數(shù)據(jù)采集模塊專門采集周圍的環(huán)境數(shù)據(jù)（如溫度、壓力），然后通過通信路由協(xié)議直接或間接地將采集到的數(shù)據(jù)傳輸給遠方基站（Base Stat

28、ion，BS）或匯聚節(jié)點（Sink）; （2）數(shù)據(jù)處理中轉(zhuǎn)站，這類節(jié)點不僅要完成采集的任務(wù)，還要接收鄰居節(jié)點的數(shù)據(jù)，一起轉(zhuǎn)發(fā)給距離基站更近的鄰居節(jié)點或者直接轉(zhuǎn)發(fā)到基站或匯聚節(jié)點; （3）簇頭節(jié)點，這類節(jié)點負(fù)責(zé)收集節(jié)點采集的數(shù)據(jù)，經(jīng)數(shù)據(jù)融合后，發(fā)送到基站或匯聚節(jié)點。 傳感器節(jié)點都分散在特定的感知區(qū)域，相互合作、實時監(jiān)測、感知和采集網(wǎng)絡(luò)周邊環(huán)境或監(jiān)測對象的溫度、聲波等各種信息。這些信息一經(jīng)采集，就將通過嵌入式系統(tǒng)進行處理，最終通過隨機自組織無線通信網(wǎng)絡(luò)以多跳中繼方式將所感知信息傳送到用戶終端，使人們無論在何時、何地、何種情況下都能獲取大量詳實可靠的信息,實現(xiàn)人、物和事件之間的無縫連接，從

29、而真正實現(xiàn)“無處不在的計算”理念。 與傳統(tǒng)的網(wǎng)絡(luò)不同的是，傳統(tǒng)網(wǎng)絡(luò)以傳輸數(shù)據(jù)為目的，而無線傳感器網(wǎng)絡(luò)則是以數(shù)據(jù)為中心；與傳統(tǒng)的Ad Hoc網(wǎng)絡(luò)相比，無線傳感器網(wǎng)絡(luò)具有以下幾點特征： （1）網(wǎng)絡(luò)節(jié)點密度高，傳感節(jié)點數(shù)量多 （2）傳感器節(jié)點由電池供電 （3）網(wǎng)絡(luò)拓?fù)渥兓l繁 （4）網(wǎng)絡(luò)具有容錯能力 1.3.2 無線傳感器網(wǎng)絡(luò)數(shù)據(jù)壓縮的必要性 因為在無線傳感器網(wǎng)絡(luò)中，每個傳感節(jié)點體積很小，而且分布非常密集，若是對所有采集的數(shù)據(jù)直接進行傳輸，則所需傳輸?shù)臄?shù)據(jù)量將是非常驚人的，會導(dǎo)致網(wǎng)絡(luò)擁塞，也會導(dǎo)致網(wǎng)絡(luò)壽命縮短；又由于傳感器節(jié)點由電池供電， 所以節(jié)點能量有限，而且無線傳感器

30、網(wǎng)絡(luò)所布置的地方一般為人們不便于到達的地方，因此傳感器節(jié)點中的的電池很難更換。為了節(jié)約能量，延長傳感器網(wǎng)絡(luò)的壽命，需要采用能效高的網(wǎng)絡(luò)通信協(xié)議和數(shù)據(jù)局部處理策略（如數(shù)據(jù)融合技術(shù)、數(shù)據(jù)壓縮技術(shù)）。 在這里，我們將說明利用壓縮技術(shù)來減少傳輸?shù)臄?shù)據(jù)量的必要性和可行性。相對于數(shù)據(jù)采集、數(shù)據(jù)壓縮這兩項功能，數(shù)據(jù)傳輸所需要的能量是最多的，所以，如果要節(jié)約傳感器節(jié)點的電池能量，必定要減少傳輸?shù)臄?shù)據(jù)量，因此在無線傳感器網(wǎng)絡(luò)中運用數(shù)據(jù)壓縮技術(shù)來減少數(shù)據(jù)量一直是一個值得深入研究的問題。無線傳感器網(wǎng)絡(luò)中的感知數(shù)據(jù)能夠進行壓縮是因為它具備數(shù)據(jù)壓縮的前提條件：首先，傳感器節(jié)點密度很大，節(jié)點之間感知的范圍相互重疊，這

31、種高密度的節(jié)點分布一方面使得感知數(shù)據(jù)可靠性增強，另一方面也引起了數(shù)據(jù)冗余，使得相鄰節(jié)點之間所采集的數(shù)據(jù)具有高度相關(guān)性，稱為空間相關(guān)性；其次，由于傳感節(jié)點感知的物理數(shù)據(jù)大多數(shù)隨著時間變化很緩慢，所以同一個傳感器節(jié)點所感知的數(shù)據(jù)之間也有相關(guān)性，稱為時間相關(guān)性。利用這兩種相關(guān)性，可以對感知數(shù)據(jù)采取相應(yīng)的數(shù)據(jù)壓縮技術(shù)。 圖1-4中監(jiān)測區(qū)域中有大量的無線傳感節(jié)點，傳感節(jié)點可以感知各種物理環(huán)境，包括聲音、溫度、壓力、地震等。人們將傳感器節(jié)點采集的大量數(shù)據(jù)采用某種壓縮技術(shù)壓縮，壓縮后的少量數(shù)據(jù)傳送到sink節(jié)點(或者是融合中心)，再由sink節(jié)點按照對應(yīng)的恢復(fù)算法恢復(fù)出采集的數(shù)據(jù)。這樣，通過傳輸少量數(shù)據(jù)

32、就可以得到整個監(jiān)測區(qū)域內(nèi)的詳細(xì)情況。 圖1.4 無線傳感網(wǎng)通信體系結(jié)構(gòu) 1.4 本文主要工作和內(nèi)容安排 本文在介紹壓縮感知理論/分布式壓縮感知理論的基礎(chǔ)上，將它們應(yīng)用到無線傳感數(shù)據(jù)壓縮領(lǐng)域，用于壓縮傳感節(jié)點采集的信號，降低傳輸能耗，節(jié)約電池能量。 本文內(nèi)容安排如下： 第一章 簡單介紹了課題的研究背景，包括現(xiàn)有的數(shù)據(jù)壓縮技術(shù)和有關(guān)無線傳感網(wǎng)絡(luò)的基本知識。 第二章 詳細(xì)闡述了壓縮感知理論，深入介紹了壓縮感知理論的核心思想— 可壓縮信號（信號稀疏化）、測量矩陣和重構(gòu)算法,總結(jié)了壓縮感知理論的優(yōu)勢及不足。 第三章 進一步介紹由壓縮感知理論發(fā)展而來的分布式壓縮感知

33、理論，分別描述了三種聯(lián)合稀疏模型及其應(yīng)用范圍，最后，將其與壓縮感知理論作了仿真性能比較。 第四章 將傳感網(wǎng)中數(shù)據(jù)傳輸與壓縮感知理論結(jié)合，分別利用壓縮感知和分布式壓縮感知框架下的信號壓縮、重構(gòu)方法對實際的感知數(shù)據(jù)進行處理，給出了實際的應(yīng)用效果，并重點研究了量化對于算法的影響。 第五章 對全文進行總結(jié)并展望下一步的研究工作。 第2章 壓縮感知理論 傳統(tǒng)通信系統(tǒng)中的采樣遵循的是奈奎斯特抽樣定理，該定理指出，為防止在獲得信號時損失信息，抽樣速率必須大于信號帶寬的兩倍。在許多應(yīng)用中，包括數(shù)字圖像和視頻攝像中，奈奎斯特抽樣速率太高，不利于數(shù)據(jù)存儲和傳輸；在其他應(yīng)用，包括圖像系統(tǒng)

34、（醫(yī)療瀏覽和雷達）、高速模數(shù)轉(zhuǎn)換中，增加抽樣速率代價也很昂貴。壓縮感知則是保存原始信號結(jié)構(gòu)的線性投影，然后再從這些投影中將信號重構(gòu)出來，其速率遠遠低于奈奎斯特抽樣率。CS理論系統(tǒng)與傳統(tǒng)通信系統(tǒng)的類似關(guān)系如圖2-1所示： CS恢復(fù) CS測量 圖2.1 CS理論系統(tǒng)與傳統(tǒng)通信系統(tǒng)的類似關(guān)系 由圖2-1可知，在CS系統(tǒng)中，信源和信道編碼被CS測量（即一個矩陣與信號矢量相乘的形式）代替；信道和信源解碼則用CS恢復(fù)（即依賴于優(yōu)化準(zhǔn)則的恢復(fù)算法）替代。 壓縮感知理論主要由三部分構(gòu)成：稀疏信號、觀測矩陣和重構(gòu)算法。下面將從這三個方面詳細(xì)講述壓縮感知的

35、關(guān)鍵技術(shù)。 2.1壓縮感知的前提條件—稀疏性和不相干性 CS隱含的兩個基本前提：稀疏性和不相關(guān)性。前者屬于信號的性質(zhì)，后者和感知（觀測）形式有關(guān)。 稀疏性：稀疏性表達了這樣一個思想，一個連續(xù)時間信號的“信息速率”可能比由帶寬所決定的香農(nóng)采樣率要低很多，或者，一個離散時間信號所依賴的自由度數(shù)目遠遠低于它的長度。更準(zhǔn)確地說，CS利用了這樣一個事實，即許多自然信號在某個合適的基Ψ下具有簡潔的表達。 不相關(guān)性：不相關(guān)性說明用于采樣信號的波在基Ψ下有很稠密的表達。不相關(guān)性表達了這樣的思想，正如時間域的Dirac或者沖擊信號可以在頻域展開那樣，在基Ψ下具有稀疏表示的信號一定可以在獲得它們的某個域

36、中展開。 1 稀疏性 眾所周知，任意長度為N 的離散信號X 都可以表示為一系列基函數(shù)的疊加， 即可以在任何正交基下用下式表示： （式2.1） 其中由一組基向量構(gòu)成的正交基，例如，sinusoids，尖峰spikes、B-splines，wavelets。為展開系數(shù)。展開系數(shù)大，說明信號和基足夠相似。如果信號在基下的展開系數(shù)在很小的集合上有值，我們就說該信號在域是稀疏的，如果有值序列集中在一個小范圍內(nèi)，那么我們就說該信號是可以壓縮的。本章我們將集中研究具有稀疏表示的信號，其中X是K個基向量的線性組合，K<

37、在一些基下有簡潔的表達。圖3.3（a）是一幅具有N（N =512512）個像素點的coins圖像向量，我們在9/7小波基下展開該向量，如（式3.4），其中是為列向量構(gòu)成的的矩陣，是正交基。圖3.3（b）是coins圖像的9/7小波系數(shù)在一維下的表示。圖2.3（c）展示了這樣一個事實：將圖像在9/7小波變換域丟掉93.75%的小系數(shù)后得到的逼近圖像盡管PSNR只有29.09dB，但肉眼很難察覺到失真。由此可見，盡管原圖中幾乎所有的像素都是非零值，它在9/7小波域中卻是稀疏的：大部分小波系數(shù)都很小，少數(shù)的大系數(shù)（1/16）就可以捕獲信號的大部分信息。 本例中僅僅保留展開（式3.4）中的個大系數(shù)得

38、到，其中表示系數(shù)向量的除K個大系數(shù)外其余置0的向量。該向量從嚴(yán)格意義上說是稀疏的，因為K<

39、壓縮等等。而近幾年來Cands等人提出的壓縮感知理論使得稀疏性有了更加令人驚奇的深遠含義，即信號稀疏性對采樣本身有重要意義，稀疏性決定了我們可以擺脫奈奎斯特采樣頻率的約束，并可以做到高效地非自適應(yīng)地采樣信號。 （b）coins圖像的9/7小波系數(shù)在一維下的表示 （c）1/16系數(shù)重構(gòu)圖像（PSNR=29.09dB） (a)512x512的coins原始圖像 圖2.2稀疏重構(gòu)圖像案例 2 不相關(guān)性 Cands， Romberg等人已經(jīng)證明一個降維的投影集合包含了重構(gòu)稀疏信號的足夠信息。這就是壓縮感知（CS）理論的核心內(nèi)

40、容。在CS中，假定信號在某個變換域的系數(shù)是K項稀疏的，我們不直接對K個重要的系數(shù)直接編碼，而是將信號的系數(shù)向量投影到另一個基函數(shù)集合上，觀測得到M (<

41、基中的正弦波不相關(guān)，傅里葉基和小波基不相關(guān)。重要的是，任意一個固定的基和一個隨機產(chǎn)生的基也以高概率滿足這種不相關(guān)。因此在CS理論中隨機矩陣被廣泛應(yīng)用于CS觀測中。在框架下或者基下可以找到稀疏表示的信號都可以以同樣的方式從不相關(guān)觀察中恢復(fù)。 文獻[3]給出了相關(guān)性度量的具體定義，如下。 定義3.2：觀測系統(tǒng)和表示系統(tǒng)之間的相關(guān)性度量用表示，則有如下式子成立： （式2.2） 簡單來講，相關(guān)性度量的是兩個矩陣和的元素之間的最大相關(guān)性。如果和包含了相關(guān)的元素，則相關(guān)性很大；否則，就很小。相關(guān)系數(shù)取值范圍為。壓縮采樣研究的是具有低相關(guān)性的兩個系統(tǒng)。下面給出一些例子。 （1）是尖峰基

42、，為傅立葉基，則有。進一步講，尖峰信號和正弦信號不僅在一維而且在任何維，例如2D，3D空間都具有最大的不相關(guān)性。 （2）為小波基，是noiselet。這里，noiselet和Haar小波基間的相關(guān)系數(shù)是，noiselet和Daubechies db4及db8小波基間的相關(guān)性分別是2.2和2.9。這也可以擴展到高維情況。noiselets也和尖峰信號及傅立葉基高度不相關(guān)。人們對noiselets感興趣基于以下兩個事實：1）它們和為圖像數(shù)據(jù)和其它類型的數(shù)據(jù)提供稀疏表示的系統(tǒng)不相關(guān)；2）它們具有快速算法。noiselet變換的時間復(fù)雜度為O(N)，而且類似于傅立葉變換，noiselet矩陣不需要存

43、儲。這一點對于高效的數(shù)字計算是至關(guān)重要的。如果沒有高效的計算，CS的實用性就會大打折扣。 （3）為隨機矩陣，則可以是任何固定的基。此時它們之間具有極大不相關(guān)。例如，可以通過在單位球面上獨立均勻地采樣并做規(guī)范正交化得到，此時，和間的相關(guān)性以很高的概率為。各項服從獨立同分布的隨機波形，例如高斯分布或者，也表現(xiàn)出和任何固定基具有很小的相關(guān)性。 研究者們通過大量的實驗分析，得出如下結(jié)論：精確重構(gòu)所需要的觀測值個 數(shù)依賴于稀疏變換基和觀測基之間的不相關(guān)性。不相關(guān)性越強，所需的個數(shù)越少；反之，相關(guān)性越強，例如，則需要采樣所有的系數(shù)才能保證精確重構(gòu)。 2.2 三個關(guān)鍵技術(shù) 從以上壓縮感知理論的介紹

44、中我們可以看出，壓縮感知理論主要包括以下三個方面的內(nèi)容： （1）信號稀疏表示； （2）信號的編碼測量即觀測矩陣的設(shè)計； （3）信號重構(gòu)算法的設(shè)計。 信號的稀疏表示是指當(dāng)將信號投影到某個正交變換基時，一般情況下絕大多數(shù)的變換系數(shù)的絕對值都是很小的，得到的變換向量也是稀疏的或者是近似稀疏的，這是原始信號的一種簡潔的表達方式，也是壓縮傳感理論的先驗條件。信號必須得在某種變換下才可以進行稀疏表示。通常我們可以選取的變換基有離散傅里葉變換基（DFT）、離散余弦變換基（DCT）、離散小波變換基（DWT）、Curvelet 變換基、Gabor 變換基還有冗余字典等。在信號的編碼測量即觀測矩陣的設(shè)計過

45、程中，要選擇穩(wěn)定的觀測矩陣，觀測矩陣的選取必須滿足受限等距特性(Restricted Isometry Property，RIP)準(zhǔn)則，才能保證信號的投影能夠保持原始信號的結(jié)構(gòu)特征。通過原始信號與觀測矩陣相乘我們可以獲得原始信號的線性投影值。最后設(shè)計合適的重構(gòu)算法從所得到的觀測值和原來的觀測矩陣來重構(gòu)原始始號。 所以對壓縮感知理論的研究也主要是基于這三個方面的內(nèi)容： （1）信號的稀疏表示。即對于信號 ，如何找到一個合適的正交基或者緊框架Ψ，以使得原始信號在Ψ上的表示是稀疏的。 （2）觀測矩陣的設(shè)計。即如何設(shè)計一個平穩(wěn)且滿足受限等距特性條件或者與變換基Ψ 滿足不相關(guān)約束條件的M N 維觀

46、測矩陣Φ，以保證信號稀疏表示后的向量Θ能從原來的N 維降到M 維時所包含的重要信息沒有受到破壞，從而保證原始信號的準(zhǔn)確重構(gòu)。這個過程也就是壓縮感知理論中信號的低速采樣過程。 （3）重構(gòu)算法的設(shè)計。即如何設(shè)計快速有效且穩(wěn)定的重構(gòu)算法，從所得到的低維觀測向量中準(zhǔn)確地恢復(fù)原始信號。 下面我們對壓縮感知理論的這三個關(guān)鍵技術(shù)做一個詳細(xì)的總結(jié)和分析，以為后文對壓縮感知理論在圖像重構(gòu)方面的研究打下基礎(chǔ)。 2.3信號的稀疏表示 從傅立葉變換到小波變換再到后來興起的多尺度幾何分析（Ridgelet，Curvelet，Bandelet，Contourlet），科學(xué)家們的研究目的均是為了研究如何在不同的函數(shù)

47、空間為信號提供一種更加簡潔、直接的分析方式，所有這些變換都旨在發(fā)掘信號的特征并稀疏表示它，進一步研究用某空間的一組基函數(shù)表示信號的稀疏程度或分解系數(shù)的能量集中程度。 文獻[23]給出稀疏的定義：信號X在正交基下的變換系數(shù)向量為，假如對于0 0，這些系數(shù)滿足： （式2.3） 則說明系數(shù)向量在某種意義下是稀疏的。文獻[34]給出另一種定義：如果變換系數(shù)的支撐域的勢小于等于K，則可以說信號X 是K -項稀疏。 如何找到信號最佳的稀疏域？這是壓縮感知理論應(yīng)用的基礎(chǔ)和前提，只有選擇合適的基表示信號才能保證信號的稀疏度，從而保證信號的恢復(fù)精度。在研究

48、信號的稀疏表示時，可以通過變換系數(shù)衰減速度來衡量變換基的稀疏表示能力。Cands 和Tao通過研究發(fā)現(xiàn)，滿足冪定律衰減的信號，可利用壓縮感知理論進行恢復(fù)，并且重構(gòu)誤差滿足： （式2.4） 其中r=1/p-1/2，0

49、交基構(gòu)成的正交基字典。即在某個正交基字典里，自適應(yīng)地尋找可以逼近某一種信號特征的最優(yōu)正交基，根據(jù)不同的信號尋找最適合信號特性的一組正交基，對信號進行變換以得到最稀疏的信號表示。 最近幾年，對稀疏表示研究的另一個熱點是信號在過完備字典下的稀疏分解。 字典的選擇應(yīng)盡可能好地符合被逼近信號的結(jié)構(gòu)，其構(gòu)成可以沒有任何限制。從 從過完備字典中找到具有最佳線性組合的K項原子來表示一個信號，稱作信號的稀疏逼近或高度非線性逼近。 過完備庫下的信號稀疏表示方法最早由Mallat和Zhang于1993年首次提出， 并引入了MP算法。文獻以淺顯易懂的表達說明了過完備字典對信號表示的必要性，同時還指出字典的構(gòu)

50、成應(yīng)盡量符合信號本身所固有的特性。 目前信號在過完備字典下的稀疏表示的研究集中在兩個方面：（1）如何構(gòu)造一個適合某一類信號的過完備字典；（2）如何設(shè)計快速有效的稀疏分解算法。這兩個問題也一直是該領(lǐng)域研究的熱點，學(xué)者們對此已做了一些探索，其中，以非相干字典為基礎(chǔ)的一系列理論證明得到了進一步改進。 從非線性逼近角度來講，信號的稀疏逼近包含兩個層面：一是根據(jù)目標(biāo)函數(shù)從一個給定的基庫中挑選好的或最好的基；二是從這個好的基中挑選最好的K項組合。 從過完備字典的構(gòu)成角度來講，文獻[38]中提出使用局部Cosine基來刻畫聲音信號的局部頻域特性；利用bandlet基來刻畫圖像中的幾何邊緣。還可以把其它

51、的具有不同形狀的基函數(shù)歸入字典，如適合刻畫紋理的Gabor基、適合刻畫輪廓的Curvelet基等等。 從稀疏分解算法角度來講，在音視頻信號處理方面，基于貪婪迭代思想的MP算法表現(xiàn)出極大的優(yōu)越性，但不是全局最優(yōu)解。Donoho等人另辟蹊徑，提出了BP算法。BP算法具有全局最優(yōu)的優(yōu)點，但計算復(fù)雜度極高，例如對于長度為8192的信號，采用小波字典分解，等價于求解一個長度為8192*212992的線性規(guī)劃。MP算法雖然收斂速度較BP快，但不具備全局最優(yōu)性，且計算復(fù)雜度仍然很大。之后又出現(xiàn)了一系列同樣基于貪婪迭代思想的改進算法，如正交匹配追蹤算法（OMP），樹形匹配追蹤（TMP），分段匹配追蹤（StO

52、MP）算法等。 2.4 觀測矩陣設(shè)計 觀測部分的設(shè)計其實就是設(shè)計高效的觀測矩陣，換句話說，就是要設(shè)計一個 能捕捉稀疏信號中有用信息的高效的觀測（即采樣）協(xié)議，從而將該稀疏信號壓 縮成少量的數(shù)據(jù)。這些協(xié)議是非自適應(yīng)的，僅僅需要用少量的固定波形和原信號 聯(lián)系起來，這些固定波形和為信號提供簡潔表示的基不相關(guān)。此外，觀測過程獨 立于信號本身。進一步講，使用優(yōu)化方法可以收集到的少量的觀測值中重構(gòu)信號。 壓縮感知理論中，通過變換得到信號的稀疏系數(shù)向量后，需要設(shè)計觀測部分，它圍繞觀測矩陣展開。觀測器的設(shè)計目的是如何采樣得到M個觀測值，并保證從中能重構(gòu)出長度為N的信號X或者基下等價的稀疏系數(shù)向量

53、。顯然，如果觀測過程破壞了X中的信息，重構(gòu)是不可能的。觀測過程實際就是利用觀測矩陣的M個行向量對稀疏系數(shù)向量進行投影，即計算和各個觀測向量之間的內(nèi)積，得到M個觀測值， ，記觀測向量，即 （式2.5） （b） （a） 圖2.3 觀測矩陣的圖形表示 圖3.4（a）是（式3.7）的形象描述。這里，采樣過程是非自適應(yīng)的，也就是說，無須根據(jù)信號X 而變化，觀測的不再是信號的點采樣而是信號的更一般的線性泛函。 圖3.4（a）隨機高斯矩陣作為觀測矩陣，稀疏域選擇DCT變換域，對信號X進行DCT變換后再進行觀測。（b）是（a）圖的另一種表達，變換后的

54、系數(shù)向量是稀疏的，K=3，觀測得到的Y是非零系數(shù)對應(yīng)的四個列向量的線性組合。 對于給定的Y從（式3.7）中求出是一個線性規(guī)劃問題，但由于M<< N，即方程的個數(shù)少于未知數(shù)的個數(shù)，這一欠定問題一般來講無確定解。然而，如果具有K -項稀疏性（K<

55、在觀測矩陣作用下必須保持的幾何性質(zhì)相一致。即，要想使信號完全重構(gòu)，必須保證觀測矩陣不會把兩個不同的K-項稀疏信號映射到同一個采樣集合中，這就要求從觀測矩陣中抽取的每M個列向量構(gòu)成的矩陣是非奇異的。從中可以看出，問題的關(guān)鍵是如何確定非零系數(shù)的位置來構(gòu)造出一個可解的線性方程組。 然而，判斷給定的是否具有RIP性質(zhì)是一個組合復(fù)雜度問題。為了降低 問題的復(fù)雜度，能否找到一種易于實現(xiàn)RIP條件的替代方法成為構(gòu)造觀測矩陣F 的關(guān)鍵。 文獻[24]指出如果保證觀測矩陣和稀疏基不相干，則在很大概率上滿足RIP性質(zhì)。不相干是指向量不能用稀疏表示。不相干性越強，互相表示時所需的系數(shù)越多；反之，相關(guān)性則越強。

56、通過選擇高斯隨機矩陣作為即可高概率保證不相干性和RIP性質(zhì)。例如，可以生成多個零均值、方差為1/ N 的隨機高斯函數(shù)，將它們作為觀測矩陣的元素，使得以很高的概率具有RIP性質(zhì)。隨機高斯矩陣具有一個有用的性質(zhì)：對于一個的隨機高斯矩陣，可以證明當(dāng)時在很大概率下具有RIP性質(zhì)（其中c是一個很小的常數(shù)）。因此可以從M個觀測值中以很高的概率去恢復(fù)長度為N的K-項稀疏信號。總之，隨機高斯矩陣與大多數(shù)固定正交基構(gòu)成的矩陣不相關(guān)，這一特性決定了選它作為觀測矩陣，其它正交基作為稀疏變換基時，滿足RIP性質(zhì)。為進一步簡化觀測矩陣，在某些條件下，以隨機為元素構(gòu)成的Rademacher矩陣也可以證明具有RIP性質(zhì)和普

57、適性。 目前，對觀測矩陣的研究是壓縮感知理論的一個重要方面。在該理論中，對 觀測矩陣的約束是比較寬松的，Donoho在文獻[23]中給出了觀測矩陣所必需具備的三個條件，并指出大部分一致分布的隨機矩陣都具備這三個條件，均可作為觀測矩陣，如：部分Fourier集、部分Hadamard集、一致分布的隨機投影（uniform Random Projection）集等，這與對RIP條件進行研究得出的結(jié)論相一致。但是，使用上述各種觀測矩陣進行觀測后，都僅僅能保證以很高的概率去恢復(fù)信號，而不能保證百分之百地精確重構(gòu)信號。對于任何穩(wěn)定的重構(gòu)算法是否存在一個真實的確定性的觀測矩陣仍是一個有待研究的問

58、題。文獻[56]則從信息論角度描述了信息論與CS之間的聯(lián)系。它指出，在模擬系統(tǒng)中，觀測噪聲也是影響觀測次數(shù)的重要因素，為說明這一點，作者從信息論的角度研究了稀疏信號的率失真函數(shù)，給出了觀測噪聲對信號重建效果的影響。 2.5 稀疏信號的重構(gòu) 壓縮感知理論的核心問題是從觀測得到的有限的M<

59、確恢復(fù)是可能的；（2）真實信號實際上就是一個簡單凸優(yōu)化問題的解。但是，文獻[30]和[23]均指出由于信號X 是稀疏的或可壓縮的，這個前提從根本上改變了問題，使得問題可解，而觀測矩陣具有RIP性質(zhì)也為從M 個觀測值中精確恢復(fù)信號提供了理論保證。 為更清晰地描述壓縮感知理論的信號重構(gòu)問題， 首先定義向量的p-范數(shù)為 （式2.6） 當(dāng)p=0時得到0-范數(shù)，它實際上表示X中非零項的個數(shù)。 在信號X 稀疏或可壓縮的前提下，求解欠定方程組的問題轉(zhuǎn)化為最小0-范數(shù)問題： s.t. （式2.7） 但是，

60、它需要列出X中所有非零項位置的種可能的線性組合，才能得到最優(yōu)解。因此，求解（式3.9）式的數(shù)值計算極不穩(wěn)定而且是NP難問題。可見，壓縮感知和稀疏分解問題從數(shù)學(xué)意義上講是同樣的優(yōu)化問題。于是稀疏分解的已有算法可以應(yīng)用到CS重構(gòu)中。 Chen，Donoho和Saunders指出，求解一個更加簡單的1-范數(shù)最小優(yōu)化問題會 產(chǎn)生同等的解（要求和不相關(guān)）： s.t. （式2.8） 稍微的差別使得問題變成了一個凸優(yōu)化問題，于是可以方便地化簡為線性規(guī)劃問題，典型算法代表：BP算法。 不過，1-范數(shù)最小化不是尋找稀疏解的唯一方法；其它方法，例如貪婪算法也已被提出

61、。 由以上討論我們可以得出結(jié)論：（1）相關(guān)性在CS中起著至關(guān)重要的作用：和相關(guān)性越小，需要采樣的數(shù)目就越少。（2）僅僅觀測比信號長度小得多的任何M 個系數(shù)的集合，不會損失信息。（3）最小化帶線性方程約束的1-范數(shù)可以很容易地被轉(zhuǎn)化為線性規(guī)劃問題，于是可以找到更高效的求解算法。已經(jīng)證明，如果，那么重構(gòu)成功的概率超過。 2.6 重構(gòu)算法 由前面的分析可知，過完備庫下的稀疏分解問題和壓縮感知理論的重構(gòu)問題都是線性約束下的0-范數(shù)求解問題。因此這兩類問題的求解本質(zhì)上是一樣的。于是用于過完備庫下稀疏分解的方法都可以用于求解壓縮感知理論的重構(gòu)計算。 定理2已證明：對于一個K項-稀疏（K<

62、為N的信號僅僅需要投影到另一個不相關(guān)基上的K+1個系數(shù)就可以以高概率被重構(gòu)。然而，求得最小的0-范數(shù)解需要進行組合搜索，計算復(fù)雜度相當(dāng)高。Cands 和Donoho 近來提出一種可行的基于線性規(guī)劃的重構(gòu)方法，論證了只使用對信號的cK（c =3或者4）個觀測值，利用線性規(guī)劃的方法就可以得到和組合搜索相同的解。盡管BP算法可行，但在實際應(yīng)用中存在兩個問題：第一，即使對常見的圖像尺寸，算法的計算復(fù)雜度也難以忍受，在采樣點個數(shù)滿足，時，重構(gòu)計算復(fù)雜度的量級在；第二，由于1-范數(shù)無法區(qū)分稀疏系數(shù)尺度的位置，所以盡管整體上重構(gòu)信號在歐氏距離上逼近原信號，但存在低尺度能量搬移到了高尺度的現(xiàn)象，從而容易出現(xiàn)一

63、些人工效應(yīng)，如一維信號會在高頻出現(xiàn)振蕩。 針對上述問題，2005 年1 月Cands 和Romberg 提出了不同的信號恢復(fù)方法，該方法要求對原信號具有少量的先驗條件，同時也可以對所求結(jié)果施加適當(dāng)?shù)南拗疲约s束重構(gòu)信號的特性。通過在凸集上交替投影（Projections onto Convex Sets）的方法，可以快速求解線性規(guī)劃問題。 另一類基于貪婪思想的迭代算法以更多的觀測數(shù)量作為代價達到了更加快速重構(gòu)的目的。 J.Tropp和A.C.Gilbert提出利用匹配追蹤（MP）和正交匹配追蹤（OMP）算法來求解優(yōu)化問題重構(gòu)信號，大大提高了計算的速度，且易于實現(xiàn)。樹形匹配追蹤（TMP）算

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

65、. Hale， W. Yin基于分裂算子和同倫算子提出了求解最小1-范數(shù)大規(guī)模問題的方法，適合于糾錯編碼、磁共振成像、NMR波譜研究等領(lǐng)域的大規(guī)模問題求解。 在上述各種方法中，觀測矩陣中的所有值都非零，這樣信號采樣過程的計算量是O(MN)，在大規(guī)模的數(shù)據(jù)面前，這個量級還是非常大的。因此一類利用稀疏矩陣作為觀測矩陣進行采樣的方法出現(xiàn)了。Graham Cormode等人，提出利用分組測試和隨機子集選取來估計稀疏信號的非零系數(shù)的位置和取值，該方法需要的采樣數(shù)為，信號重構(gòu)的計算復(fù)雜度為，得到重構(gòu)信號的速度更快。 Gilbert等人在2006 年4 月提出了鏈?zhǔn)阶粉櫍–P，Chaining

66、Pursuit）方法來恢復(fù)可壓縮信號。利用個采樣觀測重構(gòu)信號，需要計算量為，該方法對特別稀疏信號的恢復(fù)計算性能較高，但當(dāng)信號的稀疏度減少，需要的采樣點數(shù)會迅速增加，甚至超過信號本身的長度，這就失去了壓縮采樣的意義。 總之，目前為止出現(xiàn)的重構(gòu)算法都可歸入以下三大類： （1）貪婪追蹤算法：這類方法是通過每次迭代時選擇一個局部最優(yōu)解來逐步逼近原始信號。這些算法包括MP算法，OMP算法，分段OMP算法（StOMP）和正則化OMP（ROMP）算法。 （2）凸松弛法：這類方法通過將非凸問題轉(zhuǎn)化為凸問題求解找到信號的逼近， 如BP算法，內(nèi)點法，梯度投影方法和迭代閾值法。 （3）組合算法：這類方法要求信號的采樣支持通過分組測試快速重建，如傅 立葉采樣，鏈?zhǔn)阶粉櫤虷HS追蹤等。 總之，每種算法都有其固有的缺點。凸松弛法重構(gòu)信號所需的觀測次數(shù)最少， 但往往計算負(fù)擔(dān)很重。貪婪追蹤算法在運行時間和采樣效率上都位于另兩種算法 之間。 由上面的分析可知，重構(gòu)算法和所需的觀測次數(shù)密切相關(guān)，當(dāng)前，壓縮感知 理論的信號重構(gòu)問題的研究主要集中在如何構(gòu)造穩(wěn)定的、計算復(fù)雜度較