畢業(yè)設(shè)計(jì)（論文） 基于MATLAB的圖像壓縮感知算法的實(shí)現(xiàn)系： 電氣工程系 專業(yè)： 電子信息工程 目錄目錄I第1章 緒論31.1 研究背景和意義31.2 數(shù)據(jù)壓縮技術(shù)41.2.1 傳統(tǒng)數(shù)據(jù)壓縮技術(shù)41.2.2 壓縮感知理論（Compressed/Compressive Sensing/Sampling, CS）51.3 無(wú)線傳感器網(wǎng)絡(luò)71.3.1 無(wú)線傳感器網(wǎng)絡(luò)概述71.3.2 無(wú)線傳感器網(wǎng)絡(luò)數(shù)據(jù)壓縮的必要性91.4 本文主要工作和內(nèi)容安排10第2章 壓縮感知理論112.1壓縮感知的前提條件稀疏性和不相干性112.2 三個(gè)關(guān)鍵技術(shù)142.3信號(hào)的稀疏表示152.4 觀測(cè)矩陣設(shè)計(jì)172.5 稀疏信號(hào)的重構(gòu)192.6 重構(gòu)算法202.7 壓縮感知優(yōu)勢(shì)及不足212.8 壓縮感知在傳感網(wǎng)中的觀測(cè)方式22第3章 壓縮感知理論應(yīng)用概述243.1 壓縮成像243.2 模擬信息轉(zhuǎn)換243.3 生物傳感253.4 本章小結(jié)25第4章 CS在無(wú)線傳感網(wǎng)中的應(yīng)用264.1 研究背景264.1.1 基于感知數(shù)據(jù)相關(guān)性的壓縮264.1.2傳統(tǒng)壓縮重構(gòu)方法274.1.3 圖像壓縮重構(gòu)質(zhì)量的評(píng)價(jià)274.2 壓縮感知理論算法對(duì)一維信號(hào)的實(shí)現(xiàn)294.2.1 CS用于WSN的優(yōu)勢(shì)294.2.2 觀測(cè)重構(gòu)模型304.2.2 正交匹配追蹤算法（OMP）304.2.3 算法的實(shí)現(xiàn)及結(jié)果分析314.3 壓縮感知理論算法對(duì)二維圖像重構(gòu)的實(shí)現(xiàn)354.3.1 基于小波變換的分塊壓縮感知理論354.3.2 實(shí)現(xiàn)步驟364.3.3 重構(gòu)結(jié)果及分析394.4 本章小結(jié)42第5章 總結(jié)與展望435.1 工作總結(jié)435.2 后續(xù)展望43參考文獻(xiàn)44致謝46附錄47摘要數(shù)據(jù)壓縮技術(shù)是提高無(wú)線數(shù)據(jù)傳輸速度的有效措施之一。傳統(tǒng)的數(shù)據(jù)壓縮技術(shù)是基于奈奎斯特采樣定律進(jìn)行采樣，并根據(jù)數(shù)據(jù)本身的特性降低其冗余度，從而達(dá)到壓縮的目的。近年來(lái)出現(xiàn)的壓縮感知理論（Compressed Sensing,CS）則不受制于奈奎斯特采樣定律，它是采用非自適應(yīng)線性投影來(lái)保持信號(hào)的原始結(jié)構(gòu)，以直接采集壓縮后的數(shù)據(jù)的方式，從盡量少的數(shù)據(jù)中提取盡量多的信息。本文闡述了壓縮感知方法的基本原理，分析了CS理論框架及關(guān)鍵技術(shù)問(wèn)題，介紹了壓縮感知技術(shù)應(yīng)用于無(wú)線傳感的優(yōu)勢(shì)，并著重介紹了信號(hào)稀疏變換、觀測(cè)矩陣設(shè)計(jì)和重構(gòu)算法三個(gè)方面的最新進(jìn)展，對(duì)研究中現(xiàn)存的難點(diǎn)問(wèn)題進(jìn)行了探討。并運(yùn)用matlab軟件，在離散傅里葉變換（DFT）和離散余弦變換（DCT）分塊CS的基礎(chǔ)上，采用正交匹配追蹤算法（OMP）實(shí)現(xiàn)了對(duì)一維信號(hào)和二維圖像的高概率重構(gòu)。將重構(gòu)結(jié)果與原始信號(hào)對(duì)比，結(jié)果表明，只要采樣數(shù)M（遠(yuǎn)小于奈奎斯特定理所需要的采樣率）能夠包含圖像所需要的有用信息時(shí)，CS算法就能精確的完成對(duì)圖像的重構(gòu)，并且重構(gòu)效果也比較好。關(guān)鍵詞：壓縮感知 無(wú)線傳感 正交匹配 稀疏表示 觀測(cè)矩陣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 information. 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 information 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 difficult 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 original 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 sensing wireless sensor networks orthogonal matching pursuit sparse presentation measurement matri50第1章 緒論在當(dāng)今的信息社會(huì)，電腦、手機(jī)、傳感器、驅(qū)動(dòng)器等都要連接到因特網(wǎng)，這樣的無(wú)線通信系統(tǒng)中，將會(huì)產(chǎn)生并且傳播大量數(shù)據(jù)信息，從而對(duì)信號(hào)的采樣、存儲(chǔ)、傳輸和恢復(fù)造成巨大壓力，增加了通信設(shè)備的成本。對(duì)人們來(lái)說(shuō)，如何有效的處理這些數(shù)據(jù)，成為一個(gè)新的挑戰(zhàn)。近幾年來(lái)，在信號(hào)處理領(lǐng)域出現(xiàn)的壓縮感知理論（CS）打破了傳統(tǒng)采樣過(guò)程中信號(hào)采樣速率必須達(dá)到信號(hào)帶寬兩倍以上才能精確重構(gòu)原始信號(hào)的奈奎斯特采樣定理，使得信息存儲(chǔ)、處理和傳輸?shù)某杀敬蟠蠼档汀?.1 研究背景和意義隨著人們對(duì)信息需求量的增加，網(wǎng)絡(luò)通信、多媒體技術(shù)、存儲(chǔ)技術(shù)的發(fā)展越來(lái)越快，網(wǎng)絡(luò)的規(guī)模也越來(lái)越大，尋找高效的信息技術(shù)來(lái)降低數(shù)據(jù)量成為無(wú)線傳輸系統(tǒng)中急需處理的問(wèn)題之一。這是因?yàn)閿?shù)字化的各類信息的數(shù)據(jù)量十分龐大，若不對(duì)其進(jìn)行有效的壓縮就難以得到實(shí)際的應(yīng)用，因此，數(shù)據(jù)壓縮技術(shù)成為人們研究的一項(xiàng)重要技術(shù)。無(wú)線傳感器網(wǎng)絡(luò)是近來(lái)研究的熱點(diǎn)方向之一。它是由分布在監(jiān)測(cè)區(qū)域內(nèi)的大量微型傳感器節(jié)點(diǎn)通過(guò)無(wú)線電通信而形成的一個(gè)自組織網(wǎng)絡(luò)系統(tǒng)。這個(gè)系統(tǒng)的目的是協(xié)作的感知、采集和處理網(wǎng)絡(luò)覆蓋區(qū)域里被監(jiān)測(cè)對(duì)象的信息，并將結(jié)果發(fā)送給用戶。在一個(gè)傳感器網(wǎng)絡(luò)中，常常包含大量傳感器節(jié)點(diǎn)，每個(gè)傳感器都會(huì)采集大量的數(shù)據(jù)。這些數(shù)據(jù)將會(huì)被傳輸?shù)揭粋€(gè)控制中心,也會(huì)在各個(gè)節(jié)點(diǎn)之間傳輸，在這種分布式傳感網(wǎng)絡(luò)中，數(shù)據(jù)傳輸功耗和帶寬需求非常大，所以，如何對(duì)這樣的分布式信號(hào)進(jìn)行壓縮，從而減小通信開銷已經(jīng)成為非常緊迫的需求。壓縮感知理論與傳統(tǒng)奈奎斯特采樣定理不同，它指出，只要信號(hào)是可壓縮的或在某個(gè)變換域是稀疏的，那么就可以用一個(gè)與變換基不相關(guān)的觀測(cè)矩陣將變換所得高維信號(hào)投影到一個(gè)低維空間上，然后通過(guò)求解一個(gè)優(yōu)化問(wèn)題就可以從這些少量的投影中以高概率重構(gòu)出原信號(hào)，可以證明這樣的投影包含了重構(gòu)信號(hào)的足夠信息。 在該理論框架下，采樣速率不決定于信號(hào)的帶寬，而決定于信息在信號(hào)中的結(jié)構(gòu)和內(nèi)容。 事實(shí)上，壓縮感知理論的某些抽象結(jié)論源于Kashin創(chuàng)立的范函分析和逼近論， 最近由Cands，Romberg ，Tao和Donoho等人構(gòu)造了具體的算法并且通過(guò)研究表明了這一理論的巨大應(yīng)用前景。從信號(hào)分析角度來(lái)講，傅立葉變換是信號(hào)和數(shù)字圖像處理的理論基礎(chǔ)，小波分析將信號(hào)和數(shù)字圖像處理帶入到一個(gè)嶄新的領(lǐng)域。 多尺度幾何分析是繼小波分析后的新一代信號(hào)分析工具，它具有多分辨、局部化和多方向性等優(yōu)良特性，更適合于處理圖像等高維信號(hào)。 這些研究工作都為壓縮感知理論奠定了基礎(chǔ)。顯然，在壓縮感知理論中，圖像/信號(hào)的采樣和壓縮同時(shí)以低速率進(jìn)行，使傳感器的采樣和計(jì)算成本大大降低，而信號(hào)的恢復(fù)過(guò)程是一個(gè)優(yōu)化計(jì)算的過(guò)程。 因此，該理論指出了將模擬信號(hào)直接采樣壓縮為數(shù)字形式的有效途徑，具有直接信息采樣特性。 由于從理論上講任何信號(hào)都具有可壓縮性，只能找到其相應(yīng)的稀疏表示空間，就可以有效地進(jìn)行壓縮采樣，這一理論必將給信號(hào)采樣方法帶來(lái)一次新的革命。1.2 數(shù)據(jù)壓縮技術(shù)數(shù)據(jù)壓縮技術(shù)就是對(duì)原始數(shù)據(jù)進(jìn)行數(shù)據(jù)編碼或者壓縮編碼，從而用最少的數(shù)碼來(lái)表示信源發(fā)出的信號(hào)。數(shù)據(jù)壓縮的對(duì)象很廣泛，可以是通信時(shí)間、傳輸帶寬、存儲(chǔ)空間甚至發(fā)射能量。數(shù)據(jù)壓縮的作用是能夠快速地傳輸各種信號(hào)；在已有的一些通信干線并行開通更多的多媒體業(yè)務(wù)；緊縮數(shù)據(jù)存儲(chǔ)容量；降低發(fā)信機(jī)功率等等。1.2.1 傳統(tǒng)數(shù)據(jù)壓縮技術(shù)前較成熟的數(shù)據(jù)壓縮技術(shù)有許多種，按照壓縮后對(duì)信息的失真程度,主要分為無(wú)損壓縮和有損壓縮。 無(wú)損壓縮是利用數(shù)據(jù)中的統(tǒng)計(jì)冗余進(jìn)行壓縮。數(shù)據(jù)中間存在的一些多余成分，稱之為冗余度。例如，在某一份計(jì)算機(jī)文件中，一些符號(hào)會(huì)反復(fù)出現(xiàn)、一些符號(hào)比其它的符號(hào)出現(xiàn)得更頻繁、一些符號(hào)總是出現(xiàn)在各數(shù)據(jù)塊中的可預(yù)見的位置上，以上講述的這些冗余部分便可在數(shù)據(jù)編碼中除去或者減少。這種無(wú)損壓縮機(jī)制可以完全恢復(fù)原始數(shù)據(jù)而不引起任何失真，但是壓縮率卻受到數(shù)據(jù)統(tǒng)計(jì)冗余度的理論限制，一般為2:1到5:1。這類方法可以廣泛用于文本數(shù)據(jù)、程序以及特殊應(yīng)用場(chǎng)景的圖像數(shù)據(jù)（如醫(yī)學(xué)圖像）的壓縮。它的主要壓縮機(jī)制包括Huffman編碼、算術(shù)編碼、游程編碼和字典編碼等系列。 有損壓縮是利用了人類對(duì)圖像或者聲音中的某些頻率成分不敏感的特殊性質(zhì)，允許壓縮過(guò)程中損失一定的信息；盡管不能完全恢復(fù)出原始數(shù)據(jù)，但是所缺失的數(shù)據(jù)部分對(duì)于我們理解原始圖像的影響很小，卻使得壓縮比大了許多。有損壓縮廣泛應(yīng)用于語(yǔ)音，圖像和視頻數(shù)據(jù)的壓縮。它一般有兩種基本的壓縮機(jī)制，一種是有損變換編解碼（如傅立葉變換、離散余弦變換、小波變換），即首先對(duì)圖像或者聲音進(jìn)行采樣、切成小塊、變換到一個(gè)新的空間、量化，接著對(duì)量化值進(jìn)行熵編碼；另外一種是預(yù)測(cè)編解碼（如脈沖編碼調(diào)制、差分脈沖編碼調(diào)制、自適應(yīng)差分脈沖編碼調(diào)制等），即利用先前的數(shù)據(jù)和隨后解碼的數(shù)據(jù)來(lái)預(yù)測(cè)當(dāng)前的聲音采樣或者圖像幀，并對(duì)預(yù)測(cè)數(shù)據(jù)與實(shí)際數(shù)據(jù)之間的誤差以及其它一些重現(xiàn)預(yù)測(cè)的信息進(jìn)行量化與編碼。 綜合無(wú)損壓縮和有損壓縮的優(yōu)點(diǎn)，還出現(xiàn)了第三類壓縮技術(shù)：混合壓縮。它主要是求取在壓縮效率、壓縮比以及保真度之間的最佳平衡，如靜止圖像壓縮標(biāo)準(zhǔn)JPEG和活動(dòng)圖像壓縮標(biāo)準(zhǔn)MPEG就是采用混合編碼的壓縮方法。1.2.2 壓縮感知理論（Compressed/Compressive Sensing/Sampling, CS）在傳統(tǒng)理論的指導(dǎo)下，信號(hào)主要的一些壓縮方法都要基于奈奎斯特采樣定律進(jìn)行采樣，即信息采樣速率至少為信號(hào)帶寬的兩倍。信號(hào)的編解碼過(guò)程如圖1.1所示：編碼端首先獲得X 的N點(diǎn)采樣值，經(jīng)變換后只保留其中K個(gè)最大的投影系數(shù)并對(duì)它們的幅度和位置編碼，最后將編得的碼值進(jìn)行存儲(chǔ)或傳輸。解壓縮僅是編碼過(guò)程的逆變換。實(shí)際上，采樣得到的大部分?jǐn)?shù)據(jù)都是不重要的，即K值很小，但由于奈奎斯特采樣定理的限制，采樣點(diǎn)數(shù)N可能會(huì)非常大，采樣后的壓縮是造成資源浪費(fèi)的根本所在。圖1.1 傳統(tǒng)編解碼理論框圖CS 理論的信號(hào)編解碼框架和傳統(tǒng)的框架大不一樣，如圖1.2 所示。CS 理論對(duì)信號(hào)的采樣、壓縮編碼發(fā)生在同一個(gè)步驟，利用信號(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)，解碼所需測(cè)量值的數(shù)目遠(yuǎn)小于傳統(tǒng)理論下的樣本數(shù)。壓縮感知的核心思想是壓縮和采樣合并進(jìn)行，并且測(cè)量值遠(yuǎn)小于傳統(tǒng)采樣方法的數(shù)據(jù)量，突破了香農(nóng)采樣定理的瓶頸，使高分辨率的信號(hào)采集成為可能。 壓縮感知理論主要包括信號(hào)的稀疏表示、隨機(jī)測(cè)量和重構(gòu)算法等三個(gè)方面。稀疏表示是應(yīng)用壓縮感知的先驗(yàn)條件，隨機(jī)測(cè)量是壓縮感知的關(guān)鍵過(guò)程，重構(gòu)算法是獲取最終結(jié)果的必要手段。圖1.2 CS理論下數(shù)據(jù)的編解碼過(guò)程壓縮感知關(guān)鍵要素包括稀疏表示、測(cè)量矩陣和重構(gòu)算法。信號(hào)在某種表示方式下的稀疏性，是壓縮感知應(yīng)用的理論基礎(chǔ)，經(jīng)典的稀疏化的方法有離散余弦變換（DCT）、傅里葉變換（FFT）、離散小波變換（DWT）等。最近幾年，對(duì)稀疏表示研究的另一個(gè)熱點(diǎn)是信號(hào)在冗余字典下的稀疏分解。 這是一種全新的信號(hào)表示理論：用超完備的冗余函數(shù)庫(kù)取代基函數(shù)，稱之為冗余字典，字典中的元素被稱為原子。目前信號(hào)在冗余字典下的稀疏表示的研究集中在兩個(gè)方面：一是如何構(gòu)造一個(gè)適合某一類信號(hào)的冗余字典，二是如何設(shè)計(jì)快速有效的稀疏分解算法。目前常用的稀疏分解算法大致可分為匹配追蹤（Matching Pursuit）和基追蹤（Basis Pursuit）兩大類。壓縮感知理論中，通過(guò)變換得到信號(hào)的稀疏系數(shù)后，需要設(shè)計(jì)壓縮采樣系統(tǒng)的觀測(cè)部分，它圍繞觀測(cè)矩陣展開。觀測(cè)器的設(shè)計(jì)目的是如何采樣得到M個(gè)觀測(cè)值，并保證從中能重構(gòu)出長(zhǎng)度為N的信號(hào)X或者稀疏基基下等價(jià)的稀疏系數(shù)向量。CandeS和Tao等證明:獨(dú)立同分布的高斯隨機(jī)測(cè)量矩陣可以成為普適的壓縮感知測(cè)量矩陣。2007年Candes等研究者建立了著名的約束等距性（RIP）理論，即要想使信號(hào)完全重構(gòu)，必須保證觀測(cè)矩陣不會(huì)把兩個(gè)不同的 K項(xiàng)稀疏信號(hào)映射到同一個(gè)采樣集合中，這就要求從觀測(cè)矩陣中抽取的每M個(gè)列向量構(gòu)成的矩陣是非奇異的。Donoho給出壓縮感知概念的同時(shí)定性和定量的給出測(cè)量矩陣要滿足三個(gè)特征：(1)由測(cè)量矩陣的列向量組成的子矩陣的最小奇異值必須大于一定的常數(shù)；(2)測(cè)量矩陣的列向量體現(xiàn)某種類似噪聲的獨(dú)立隨機(jī)性；(3)滿足稀疏度的解是滿足1范數(shù)最小的向量。目前常用的測(cè)量矩陣包括：（1）隨機(jī)高斯矩陣。矩陣每個(gè)元素獨(dú)立地服從均值為0，方差為的高斯分布。（2）隨機(jī)貝努利矩陣。矩陣的每個(gè)元素獨(dú)立地服從對(duì)稱的貝努利分布，等概率為或-。 （3）部分正交矩陣。先生成NN的正交矩陣U（如傅里葉矩陣），然后在矩陣U中隨機(jī)地選取M行向量，對(duì)MN矩陣的列向量進(jìn)行單位化得到測(cè)量矩陣。（4）部分哈達(dá)瑪矩陣。生成大小為NN的哈達(dá)瑪矩陣，然后在生成矩陣中隨機(jī)地選取M行向量，構(gòu)成一個(gè)MN的矩陣。（5）托普利茲和循環(huán)矩陣。首先生成一個(gè)向量u，由向量u生成相應(yīng)的輪換矩陣或托普利茲矩陣U，然后在矩陣U中隨機(jī)地選取其中的M行而構(gòu)造的矩陣。（6）稀疏隨機(jī)矩陣。首先生成一個(gè)零元素的矩陣，在矩陣的每一個(gè)列向量中，隨機(jī)地選取d個(gè)位置，然后在所選取的位置的值賦為1。 壓縮感知的重構(gòu)算法主要分為兩大類，一是貪婪算法，它是通過(guò)選擇合適的原子并經(jīng)過(guò)一系列的逐步遞增的方法實(shí)現(xiàn)信號(hào)矢量的逼近，此類算法主要包括匹配跟蹤算法、正交匹配追蹤算法、補(bǔ)空間匹配追蹤算法等。二是凸優(yōu)化算法，它是把0范數(shù)放寬到1范數(shù)通過(guò)線性規(guī)劃求解的，此類算法主要包括梯度投影法、基追蹤法、最小角度回歸法等。凸優(yōu)化算法算法比貪婪算法所求的解更加精確，但是需要更高的計(jì)算復(fù)雜度。 此外，迭代閾值法也得到了廣泛的應(yīng)用，此類算法也較易實(shí)現(xiàn)，計(jì)算量適中，在貪婪算法和凸優(yōu)化算法中都有應(yīng)用。但是，迭代閾值法對(duì)于迭代初值和閾值的選取均較敏感，且不能保證求出的解是稀疏的。就目前主流的兩種重建算法而言，基于1范數(shù)最小的重建算法計(jì)算量巨大，對(duì)于大規(guī)模信號(hào)無(wú)法應(yīng)用；貪婪算法雖然重建速度快，但是在信號(hào)重建質(zhì)量上還有待提高。目前，上述理論已經(jīng)應(yīng)用到各個(gè)領(lǐng)域，如傳感網(wǎng)、頻譜感知、雷達(dá)、醫(yī)學(xué)信號(hào)處理、信道預(yù)測(cè)等方面,取得了很好的效果。以上是關(guān)于壓縮感知理論與分布式壓縮感知理論的簡(jiǎn)單介紹，詳細(xì)闡述將在第二章和第三章進(jìn)行展開。 1.3 無(wú)線傳感器網(wǎng)絡(luò) 無(wú)線傳感器網(wǎng)絡(luò)是計(jì)算、通信和傳感器這三項(xiàng)技術(shù)相結(jié)合的產(chǎn)物，一開始在軍事應(yīng)用中收集數(shù)據(jù)，對(duì)戰(zhàn)場(chǎng)情況和威脅及其重要程度進(jìn)行適時(shí)的完整評(píng)價(jià)，后發(fā)展到民事運(yùn)用，如監(jiān)控大型設(shè)備，災(zāi)區(qū)臨時(shí)通信，衛(wèi)生保健等等。 1.3.1 無(wú)線傳感器網(wǎng)絡(luò)概述 無(wú)線傳感器網(wǎng)絡(luò)一般由若干傳感器節(jié)點(diǎn)組成，節(jié)點(diǎn)是組成無(wú)線傳感器網(wǎng)絡(luò)的基本單位，它負(fù)責(zé)完成采集信息、融合并傳輸數(shù)據(jù)的功能。每一個(gè)傳感器節(jié)點(diǎn)由數(shù)據(jù)采集模塊（傳感器、A/D轉(zhuǎn)換器）、數(shù)據(jù)處理和控制模塊（微處理器、存儲(chǔ)器）、通信模塊（無(wú)線收發(fā)器）和供電模塊（電池、DC/DC能量轉(zhuǎn)換器等）組成，如圖1-3所示。 圖1.3 無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)結(jié)構(gòu)圖 其中，數(shù)據(jù)采集模塊負(fù)責(zé)感知所需要的信息，數(shù)據(jù)處理和控制模塊負(fù)責(zé)對(duì)感知所得的信息和接收信息進(jìn)行處理，通信模塊負(fù)責(zé)與其他節(jié)點(diǎn)進(jìn)行通信，即發(fā)送或者接收信息，供電模塊則負(fù)責(zé)提供所需要的能量。 根據(jù)節(jié)點(diǎn)在傳感網(wǎng)網(wǎng)絡(luò)體系中所起作用的不同，節(jié)點(diǎn)在網(wǎng)絡(luò)中可以充當(dāng)數(shù)據(jù)采集者、數(shù)據(jù)處理中轉(zhuǎn)站或簇頭節(jié)點(diǎn)幾種角色： （1）數(shù)據(jù)采集者，這類節(jié)點(diǎn)的數(shù)據(jù)采集模塊專門采集周圍的環(huán)境數(shù)據(jù)（如溫度、壓力），然后通過(guò)通信路由協(xié)議直接或間接地將采集到的數(shù)據(jù)傳輸給遠(yuǎn)方基站（Base Station，BS）或匯聚節(jié)點(diǎn)（Sink）; （2）數(shù)據(jù)處理中轉(zhuǎn)站，這類節(jié)點(diǎn)不僅要完成采集的任務(wù)，還要接收鄰居節(jié)點(diǎn)的數(shù)據(jù)，一起轉(zhuǎn)發(fā)給距離基站更近的鄰居節(jié)點(diǎn)或者直接轉(zhuǎn)發(fā)到基站或匯聚節(jié)點(diǎn); （3）簇頭節(jié)點(diǎn)，這類節(jié)點(diǎn)負(fù)責(zé)收集節(jié)點(diǎn)采集的數(shù)據(jù)，經(jīng)數(shù)據(jù)融合后，發(fā)送到基站或匯聚節(jié)點(diǎn)。傳感器節(jié)點(diǎn)都分散在特定的感知區(qū)域，相互合作、實(shí)時(shí)監(jiān)測(cè)、感知和采集網(wǎng)絡(luò)周邊環(huán)境或監(jiān)測(cè)對(duì)象的溫度、聲波等各種信息。這些信息一經(jīng)采集，就將通過(guò)嵌入式系統(tǒng)進(jìn)行處理，最終通過(guò)隨機(jī)自組織無(wú)線通信網(wǎng)絡(luò)以多跳中繼方式將所感知信息傳送到用戶終端，使人們無(wú)論在何時(shí)、何地、何種情況下都能獲取大量詳實(shí)可靠的信息,實(shí)現(xiàn)人、物和事件之間的無(wú)縫連接，從而真正實(shí)現(xiàn)“無(wú)處不在的計(jì)算”理念。 與傳統(tǒng)的網(wǎng)絡(luò)不同的是，傳統(tǒng)網(wǎng)絡(luò)以傳輸數(shù)據(jù)為目的，而無(wú)線傳感器網(wǎng)絡(luò)則是以數(shù)據(jù)為中心；與傳統(tǒng)的Ad Hoc網(wǎng)絡(luò)相比，無(wú)線傳感器網(wǎng)絡(luò)具有以下幾點(diǎn)特征： （1）網(wǎng)絡(luò)節(jié)點(diǎn)密度高，傳感節(jié)點(diǎn)數(shù)量多 （2）傳感器節(jié)點(diǎn)由電池供電 （3）網(wǎng)絡(luò)拓?fù)渥兓l繁 （4）網(wǎng)絡(luò)具有容錯(cuò)能力 1.3.2 無(wú)線傳感器網(wǎng)絡(luò)數(shù)據(jù)壓縮的必要性 因?yàn)樵跓o(wú)線傳感器網(wǎng)絡(luò)中，每個(gè)傳感節(jié)點(diǎn)體積很小，而且分布非常密集，若是對(duì)所有采集的數(shù)據(jù)直接進(jìn)行傳輸，則所需傳輸?shù)臄?shù)據(jù)量將是非常驚人的，會(huì)導(dǎo)致網(wǎng)絡(luò)擁塞，也會(huì)導(dǎo)致網(wǎng)絡(luò)壽命縮短；又由于傳感器節(jié)點(diǎn)由電池供電， 所以節(jié)點(diǎn)能量有限，而且無(wú)線傳感器網(wǎng)絡(luò)所布置的地方一般為人們不便于到達(dá)的地方，因此傳感器節(jié)點(diǎn)中的的電池很難更換。為了節(jié)約能量，延長(zhǎng)傳感器網(wǎng)絡(luò)的壽命，需要采用能效高的網(wǎng)絡(luò)通信協(xié)議和數(shù)據(jù)局部處理策略（如數(shù)據(jù)融合技術(shù)、數(shù)據(jù)壓縮技術(shù)）。 在這里，我們將說(shuō)明利用壓縮技術(shù)來(lái)減少傳輸?shù)臄?shù)據(jù)量的必要性和可行性。相對(duì)于數(shù)據(jù)采集、數(shù)據(jù)壓縮這兩項(xiàng)功能，數(shù)據(jù)傳輸所需要的能量是最多的，所以，如果要節(jié)約傳感器節(jié)點(diǎn)的電池能量，必定要減少傳輸?shù)臄?shù)據(jù)量，因此在無(wú)線傳感器網(wǎng)絡(luò)中運(yùn)用數(shù)據(jù)壓縮技術(shù)來(lái)減少數(shù)據(jù)量一直是一個(gè)值得深入研究的問(wèn)題。無(wú)線傳感器網(wǎng)絡(luò)中的感知數(shù)據(jù)能夠進(jìn)行壓縮是因?yàn)樗邆鋽?shù)據(jù)壓縮的前提條件：首先，傳感器節(jié)點(diǎn)密度很大，節(jié)點(diǎn)之間感知的范圍相互重疊，這種高密度的節(jié)點(diǎn)分布一方面使得感知數(shù)據(jù)可靠性增強(qiáng)，另一方面也引起了數(shù)據(jù)冗余，使得相鄰節(jié)點(diǎn)之間所采集的數(shù)據(jù)具有高度相關(guān)性，稱為空間相關(guān)性；其次，由于傳感節(jié)點(diǎn)感知的物理數(shù)據(jù)大多數(shù)隨著時(shí)間變化很緩慢，所以同一個(gè)傳感器節(jié)點(diǎn)所感知的數(shù)據(jù)之間也有相關(guān)性，稱為時(shí)間相關(guān)性。利用這兩種相關(guān)性，可以對(duì)感知數(shù)據(jù)采取相應(yīng)的數(shù)據(jù)壓縮技術(shù)。 圖1-4中監(jiān)測(cè)區(qū)域中有大量的無(wú)線傳感節(jié)點(diǎn)，傳感節(jié)點(diǎn)可以感知各種物理環(huán)境，包括聲音、溫度、壓力、地震等。人們將傳感器節(jié)點(diǎn)采集的大量數(shù)據(jù)采用某種壓縮技術(shù)壓縮，壓縮后的少量數(shù)據(jù)傳送到sink節(jié)點(diǎn)(或者是融合中心)，再由sink節(jié)點(diǎn)按照對(duì)應(yīng)的恢復(fù)算法恢復(fù)出采集的數(shù)據(jù)。這樣，通過(guò)傳輸少量數(shù)據(jù)就可以得到整個(gè)監(jiān)測(cè)區(qū)域內(nèi)的詳細(xì)情況。 圖1.4 無(wú)線傳感網(wǎng)通信體系結(jié)構(gòu)1.4 本文主要工作和內(nèi)容安排 本文在介紹壓縮感知理論/分布式壓縮感知理論的基礎(chǔ)上，將它們應(yīng)用到無(wú)線傳感數(shù)據(jù)壓縮領(lǐng)域，用于壓縮傳感節(jié)點(diǎn)采集的信號(hào)，降低傳輸能耗，節(jié)約電池能量。 本文內(nèi)容安排如下： 第一章 簡(jiǎn)單介紹了課題的研究背景，包括現(xiàn)有的數(shù)據(jù)壓縮技術(shù)和有關(guān)無(wú)線傳感網(wǎng)絡(luò)的基本知識(shí)。 第二章 詳細(xì)闡述了壓縮感知理論，深入介紹了壓縮感知理論的核心思想 可壓縮信號(hào)（信號(hào)稀疏化）、測(cè)量矩陣和重構(gòu)算法,總結(jié)了壓縮感知理論的優(yōu)勢(shì)及不足。 第三章 進(jìn)一步介紹由壓縮感知理論發(fā)展而來(lái)的分布式壓縮感知理論，分別描述了三種聯(lián)合稀疏模型及其應(yīng)用范圍，最后，將其與壓縮感知理論作了仿真性能比較。 第四章 將傳感網(wǎng)中數(shù)據(jù)傳輸與壓縮感知理論結(jié)合，分別利用壓縮感知和分布式壓縮感知框架下的信號(hào)壓縮、重構(gòu)方法對(duì)實(shí)際的感知數(shù)據(jù)進(jìn)行處理，給出了實(shí)際的應(yīng)用效果，并重點(diǎn)研究了量化對(duì)于算法的影響。 第五章 對(duì)全文進(jìn)行總結(jié)并展望下一步的研究工作。 第2章 壓縮感知理論 傳統(tǒng)通信系統(tǒng)中的采樣遵循的是奈奎斯特抽樣定理，該定理指出，為防止在獲得信號(hào)時(shí)損失信息，抽樣速率必須大于信號(hào)帶寬的兩倍。在許多應(yīng)用中，包括數(shù)字圖像和視頻攝像中，奈奎斯特抽樣速率太高，不利于數(shù)據(jù)存儲(chǔ)和傳輸；在其他應(yīng)用，包括圖像系統(tǒng)（醫(yī)療瀏覽和雷達(dá)）、高速模數(shù)轉(zhuǎn)換中，增加抽樣速率代價(jià)也很昂貴。壓縮感知?jiǎng)t是保存原始信號(hào)結(jié)構(gòu)的線性投影，然后再?gòu)倪@些投影中將信號(hào)重構(gòu)出來(lái)，其速率遠(yuǎn)遠(yuǎn)低于奈奎斯特抽樣率。CS理論系統(tǒng)與傳統(tǒng)通信系統(tǒng)的類似關(guān)系如圖2-1所示：CS恢復(fù)CS測(cè)量 圖2.1 CS理論系統(tǒng)與傳統(tǒng)通信系統(tǒng)的類似關(guān)系 由圖2-1可知，在CS系統(tǒng)中，信源和信道編碼被CS測(cè)量（即一個(gè)矩陣與信號(hào)矢量相乘的形式）代替；信道和信源解碼則用CS恢復(fù)（即依賴于優(yōu)化準(zhǔn)則的恢復(fù)算法）替代。 壓縮感知理論主要由三部分構(gòu)成：稀疏信號(hào)、觀測(cè)矩陣和重構(gòu)算法。下面將從這三個(gè)方面詳細(xì)講述壓縮感知的關(guān)鍵技術(shù)。 2.1壓縮感知的前提條件稀疏性和不相干性CS隱含的兩個(gè)基本前提：稀疏性和不相關(guān)性。前者屬于信號(hào)的性質(zhì)，后者和感知（觀測(cè)）形式有關(guān)。稀疏性：稀疏性表達(dá)了這樣一個(gè)思想，一個(gè)連續(xù)時(shí)間信號(hào)的“信息速率”可能比由帶寬所決定的香農(nóng)采樣率要低很多，或者，一個(gè)離散時(shí)間信號(hào)所依賴的自由度數(shù)目遠(yuǎn)遠(yuǎn)低于它的長(zhǎng)度。更準(zhǔn)確地說(shuō)，CS利用了這樣一個(gè)事實(shí)，即許多自然信號(hào)在某個(gè)合適的基下具有簡(jiǎn)潔的表達(dá)。不相關(guān)性：不相關(guān)性說(shuō)明用于采樣信號(hào)的波在基下有很稠密的表達(dá)。不相關(guān)性表達(dá)了這樣的思想，正如時(shí)間域的Dirac或者沖擊信號(hào)可以在頻域展開那樣，在基下具有稀疏表示的信號(hào)一定可以在獲得它們的某個(gè)域中展開。1 稀疏性眾所周知，任意長(zhǎng)度為N 的離散信號(hào)X 都可以表示為一系列基函數(shù)的疊加，即可以在任何正交基下用下式表示：（式2.1）其中由一組基向量構(gòu)成的正交基，例如，sinusoids，尖峰spikes、B-splines，wavelets。為展開系數(shù)。展開系數(shù)大，說(shuō)明信號(hào)和基足夠相似。如果信號(hào)在基下的展開系數(shù)在很小的集合上有值，我們就說(shuō)該信號(hào)在域是稀疏的，如果有值序列集中在一個(gè)小范圍內(nèi)，那么我們就說(shuō)該信號(hào)是可以壓縮的。本章我們將集中研究具有稀疏表示的信號(hào)，其中X是K個(gè)基向量的線性組合，K<<N。也就是說(shuō)，中僅有K個(gè)非零，另外N -K個(gè)都是零。許多自然信號(hào)在一些基下有簡(jiǎn)潔的表達(dá)。圖3.3（a）是一幅具有N（N =512512）個(gè)像素點(diǎn)的coins圖像向量，我們?cè)?/7小波基下展開該向量，如（式3.4），其中是為列向量構(gòu)成的的矩陣，是正交基。圖3.3（b）是coins圖像的9/7小波系數(shù)在一維下的表示。圖2.3（c）展示了這樣一個(gè)事實(shí)：將圖像在9/7小波變換域丟掉93.75%的小系數(shù)后得到的逼近圖像盡管PSNR只有29.09dB，但肉眼很難察覺到失真。由此可見，盡管原圖中幾乎所有的像素都是非零值，它在9/7小波域中卻是稀疏的：大部分小波系數(shù)都很小，少數(shù)的大系數(shù)（1/16）就可以捕獲信號(hào)的大部分信息。本例中僅僅保留展開（式3.4）中的個(gè)大系數(shù)得到，其中表示系數(shù)向量的除K個(gè)大系數(shù)外其余置0的向量。該向量從嚴(yán)格意義上說(shuō)是稀疏的，因?yàn)镵<<N ，即除了極少數(shù)項(xiàng)外其余均為0?，F(xiàn)在稀疏的含義很清楚了：如果x在某個(gè)變換域下是稀疏或者可壓縮的，就意味著將x的系數(shù)按幅值大小排列衰減很快，那么x可以由K個(gè)大系數(shù)很好地逼近。圖3.3（c）所示告訴我們，可以丟棄除了少數(shù)幾個(gè)系數(shù)外的所有小系數(shù)而不會(huì)帶來(lái)視覺上的損失。我們稱至多有K個(gè)非零項(xiàng)的向量為K -稀疏，且有。稀疏性原理是大部分現(xiàn)代有損壓縮編碼算法和許多其它應(yīng)用的基礎(chǔ)。不過(guò)在傳統(tǒng)編碼中，這K個(gè)大系數(shù)的位置必須事先確定。更一般地，稀疏性是一個(gè)基本的建模工具，可以進(jìn)行信號(hào)的精確統(tǒng)計(jì)估計(jì)和分類、有效的數(shù)據(jù)壓縮等等。而近幾年來(lái)Cands等人提出的壓縮感知理論使得稀疏性有了更加令人驚奇的深遠(yuǎn)含義，即信號(hào)稀疏性對(duì)采樣本身有重要意義，稀疏性決定了我們可以擺脫奈奎斯特采樣頻率的約束，并可以做到高效地非自適應(yīng)地采樣信號(hào)。（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è)降維的投影集合包含了重構(gòu)稀疏信號(hào)的足夠信息。這就是壓縮感知（CS）理論的核心內(nèi)容。在CS中，假定信號(hào)在某個(gè)變換域的系數(shù)是K項(xiàng)稀疏的，我們不直接對(duì)K個(gè)重要的系數(shù)直接編碼，而是將信號(hào)的系數(shù)向量投影到另一個(gè)基函數(shù)集合上，觀測(cè)得到M (<<N)個(gè)投影然后再編碼。用矩陣表示，則有，。其中Y 是一個(gè)的列向量，觀測(cè)矩陣是一個(gè)以每個(gè)基向量作為行向量的矩陣。由于M<<N，從觀測(cè)向量y中重構(gòu)信號(hào)x是一個(gè)欠定問(wèn)題，然而信號(hào)稀疏的附加假設(shè)使得恢復(fù)成為可能也是可行的。CS理論告訴我們，當(dāng)滿足一定條件時(shí)，也即是基不能稀疏表示（該條件被稱為兩組基不相關(guān)）并且觀測(cè)值個(gè)數(shù)M足夠大，那么就可以從一個(gè)相似規(guī)模的集合中恢復(fù)大系數(shù)集合，繼而也就可以得到信號(hào)X。許多對(duì)基都滿足不相關(guān)性質(zhì)，例如，三角尖峰和傅里葉基中的正弦波不相關(guān)，傅里葉基和小波基不相關(guān)。重要的是，任意一個(gè)固定的基和一個(gè)隨機(jī)產(chǎn)生的基也以高概率滿足這種不相關(guān)。因此在CS理論中隨機(jī)矩陣被廣泛應(yīng)用于CS觀測(cè)中。在框架下或者基下可以找到稀疏表示的信號(hào)都可以以同樣的方式從不相關(guān)觀察中恢復(fù)。文獻(xiàn)3給出了相關(guān)性度量的具體定義，如下。定義3.2：觀測(cè)系統(tǒng)和表示系統(tǒng)之間的相關(guān)性度量用表示，則有如下式子成立： （式2.2）簡(jiǎn)單來(lái)講，相關(guān)性度量的是兩個(gè)矩陣和的元素之間的最大相關(guān)性。如果和包含了相關(guān)的元素，則相關(guān)性很大；否則，就很小。相關(guān)系數(shù)取值范圍為。壓縮采樣研究的是具有低相關(guān)性的兩個(gè)系統(tǒng)。下面給出一些例子。（1）是尖峰基，為傅立葉基，則有。進(jìn)一步講，尖峰信號(hào)和正弦信號(hào)不僅在一維而且在任何維，例如2D，3D空間都具有最大的不相關(guān)性。（2）為小波基，是noiselet。這里，noiselet和Haar小波基間的相關(guān)系數(shù)是，noiselet和Daubechies db4及db8小波基間的相關(guān)性分別是2.2和2.9。這也可以擴(kuò)展到高維情況。noiselets也和尖峰信號(hào)及傅立葉基高度不相關(guān)。人們對(duì)noiselets感興趣基于以下兩個(gè)事實(shí)：1）它們和為圖像數(shù)據(jù)和其它類型的數(shù)據(jù)提供稀疏表示的系統(tǒng)不相關(guān)；2）它們具有快速算法。noiselet變換的時(shí)間復(fù)雜度為O(N)，而且類似于傅立葉變換，noiselet矩陣不需要存儲(chǔ)。這一點(diǎn)對(duì)于高效的數(shù)字計(jì)算是至關(guān)重要的。如果沒(méi)有高效的計(jì)算，CS的實(shí)用性就會(huì)大打折扣。（3）為隨機(jī)矩陣，則可以是任何固定的基。此時(shí)它們之間具有極大不相關(guān)。例如，可以通過(guò)在單位球面上獨(dú)立均勻地采樣并做規(guī)范正交化得到，此時(shí)，和間的相關(guān)性以很高的概率為。各項(xiàng)服從獨(dú)立同分布的隨機(jī)波形，例如高斯分布或者，也表現(xiàn)出和任何固定基具有很小的相關(guān)性。研究者們通過(guò)大量的實(shí)驗(yàn)分析，得出如下結(jié)論：精確重構(gòu)所需要的觀測(cè)值個(gè)數(shù)依賴于稀疏變換基和觀測(cè)基之間的不相關(guān)性。不相關(guān)性越強(qiáng)，所需的個(gè)數(shù)越少；反之，相關(guān)性越強(qiáng)，例如，則需要采樣所有的系數(shù)才能保證精確重構(gòu)。2.2 三個(gè)關(guān)鍵技術(shù)從以上壓縮感知理論的介紹中我們可以看出，壓縮感知理論主要包括以下三個(gè)方面的內(nèi)容：（1）信號(hào)稀疏表示；（2）信號(hào)的編碼測(cè)量即觀測(cè)矩陣的設(shè)計(jì)；（3）信號(hào)重構(gòu)算法的設(shè)計(jì)。信號(hào)的稀疏表示是指當(dāng)將信號(hào)投影到某個(gè)正交變換基時(shí)，一般情況下絕大多數(shù)的變換系數(shù)的絕對(duì)值都是很小的，得到的變換向量也是稀疏的或者是近似稀疏的，這是原始信號(hào)的一種簡(jiǎn)潔的表達(dá)方式，也是壓縮傳感理論的先驗(yàn)條件。信號(hào)必須得在某種變換下才可以進(jìn)行稀疏表示。通常我們可以選取的變換基有離散傅里葉變換基（DFT）、離散余弦變換基（DCT）、離散小波變換基（DWT）、Curvelet 變換基、Gabor 變換基還有冗余字典等。在信號(hào)的編碼測(cè)量即觀測(cè)矩陣的設(shè)計(jì)過(guò)程中，要選擇穩(wěn)定的觀測(cè)矩陣，觀測(cè)矩陣的選取必須滿足受限等距特性(Restricted Isometry Property，RIP)準(zhǔn)則，才能保證信號(hào)的投影能夠保持原始信號(hào)的結(jié)構(gòu)特征。通過(guò)原始信號(hào)與觀測(cè)矩陣相乘我們可以獲得原始信號(hào)的線性投影值。最后設(shè)計(jì)合適的重構(gòu)算法從所得到的觀測(cè)值和原來(lái)的觀測(cè)矩陣來(lái)重構(gòu)原始始號(hào)。所以對(duì)壓縮感知理論的研究也主要是基于這三個(gè)方面的內(nèi)容：（1）信號(hào)的稀疏表示。即對(duì)于信號(hào) ，如何找到一個(gè)合適的正交基或者緊框架，以使得原始信號(hào)在上的表示是稀疏的。（2）觀測(cè)矩陣的設(shè)計(jì)。即如何設(shè)計(jì)一個(gè)平穩(wěn)且滿足受限等距特性條件或者與變換基 滿足不相關(guān)約束條件的M N 維觀測(cè)矩陣，以保證信號(hào)稀疏表示后的向量能從原來(lái)的N 維降到M 維時(shí)所包含的重要信息沒(méi)有受到破壞，從而保證原始信號(hào)的準(zhǔn)確重構(gòu)。這個(gè)過(guò)程也就是壓縮感知理論中信號(hào)的低速采樣過(guò)程。（3）重構(gòu)算法的設(shè)計(jì)。即如何設(shè)計(jì)快速有效且穩(wěn)定的重構(gòu)算法，從所得到的低維觀測(cè)向量中準(zhǔn)確地恢復(fù)原始信號(hào)。下面我們對(duì)壓縮感知理論的這三個(gè)關(guān)鍵技術(shù)做一個(gè)詳細(xì)的總結(jié)和分析，以為后文對(duì)壓縮感知理論在圖像重構(gòu)方面的研究打下基礎(chǔ)。2.3信號(hào)的稀疏表示從傅立葉變換到小波變換再到后來(lái)興起的多尺度幾何分析（Ridgelet，Curvelet，Bandelet，Contourlet），科學(xué)家們的研究目的均是為了研究如何在不同的函數(shù)空間為信號(hào)提供一種更加簡(jiǎn)潔、直接的分析方式，所有這些變換都旨在發(fā)掘信號(hào)的特征并稀疏表示它，進(jìn)一步研究用某空間的一組基函數(shù)表示信號(hào)的稀疏程度或分解系數(shù)的能量集中程度。文獻(xiàn)23給出稀疏的定義：信號(hào)X在正交基下的變換系數(shù)向量為，假如對(duì)于0<p<2和R> 0，這些系數(shù)滿足： （式2.3）則說(shuō)明系數(shù)向量在某種意義下是稀疏的。文獻(xiàn)34給出另一種定義：如果變換系數(shù)的支撐域的勢(shì)小于等于K，則可以說(shuō)信號(hào)X 是K -項(xiàng)稀疏。如何找到信號(hào)最佳的稀疏域？這是壓縮感知理論應(yīng)用的基礎(chǔ)和前提，只有選擇合適的基表示信號(hào)才能保證信號(hào)的稀疏度，從而保證信號(hào)的恢復(fù)精度。在研究信號(hào)的稀疏表示時(shí)，可以通過(guò)變換系數(shù)衰減速度來(lái)衡量變換基的稀疏表示能力。Cands 和Tao通過(guò)研究發(fā)現(xiàn)，滿足冪定律衰減的信號(hào)，可利用壓縮感知理論進(jìn)行恢復(fù)，并且重構(gòu)誤差滿足： （式2.4）其中r=1/p-1/2，0<p<1。文獻(xiàn)30指出光滑信號(hào)的Fourier系數(shù)、小波系數(shù)、有界變差函數(shù)的全變差范數(shù)、振蕩信號(hào)的Gabor系數(shù)及具有不連續(xù)邊緣的圖像信號(hào)的Curvelet系數(shù)等都具有足夠的稀疏性，可以通過(guò)壓縮感知理論恢復(fù)信號(hào)。如何找到或構(gòu)造適合一類信號(hào)的正交基，以求得信號(hào)的最稀疏表示，這是一個(gè)有待進(jìn)一步研究的問(wèn)題。Gabriel Peyr把變換基是正交基的條件擴(kuò)展到了由多個(gè)正交基構(gòu)成的正交基字典。即在某個(gè)正交基字典里，自適應(yīng)地尋找可以逼近某一種信號(hào)特征的最優(yōu)正交基，根據(jù)不同的信號(hào)尋找最適合信號(hào)特性的一組正交基，對(duì)信號(hào)進(jìn)行變換以得到最稀疏的信號(hào)表示。最近幾年，對(duì)稀疏表示研究的另一個(gè)熱點(diǎn)是信號(hào)在過(guò)完備字典下的稀疏分解。字典的選擇應(yīng)盡可能好地符合被逼近信號(hào)的結(jié)構(gòu)，其構(gòu)成可以沒(méi)有任何限制。從從過(guò)完備字典中找到具有最佳線性組合的K項(xiàng)原子來(lái)表示一個(gè)信號(hào)，稱作信號(hào)的稀疏逼近或高度非線性逼近。過(guò)完備庫(kù)下的信號(hào)稀疏表示方法最早由Mallat和Zhang于1993年首次提出， 并引入了MP算法。文獻(xiàn)以淺顯易懂的表達(dá)說(shuō)明了過(guò)完備字典對(duì)信號(hào)表示的必要性，同時(shí)還指出字典的構(gòu)成應(yīng)盡量符合信號(hào)本身所固有的特性。目前信號(hào)在過(guò)完備字典下的稀疏表示的研究集中在兩個(gè)方面：（1）如何構(gòu)造一個(gè)適合某一類信號(hào)的過(guò)完備字典；（2）如何設(shè)計(jì)快速有效的稀疏分解算法。這兩個(gè)問(wèn)題也一直是該領(lǐng)域研究的熱點(diǎn)，學(xué)者們對(duì)此已做了一些探索，其中，以非相干字典為基礎(chǔ)的一系列理論證明得到了進(jìn)一步改進(jìn)。從非線性逼近角度來(lái)講，信號(hào)的稀疏逼近包含兩個(gè)層面：一是根據(jù)目標(biāo)函數(shù)從一個(gè)給定的基庫(kù)中挑選好的或最好的基；二是從這個(gè)好的基中挑選最好的K項(xiàng)組合。從過(guò)完備字典的構(gòu)成角度來(lái)講，文獻(xiàn)38中提出使用局部Cosine基來(lái)刻畫聲音信號(hào)的局部頻域特性；利用bandlet基來(lái)刻畫圖像中的幾何邊緣。還可以把其它的具有不同形狀的基函數(shù)歸入字典，如適合刻畫紋理的Gabor基、適合刻畫輪廓的Curvelet基等等。從稀疏分解算法角度來(lái)講，在音視頻信號(hào)處理方面，基于貪婪迭代思想的MP算法表現(xiàn)出極大的優(yōu)越性，但不是全局最優(yōu)解。Donoho等人另辟蹊徑，提出了BP算法。BP算法具有全局最優(yōu)的優(yōu)點(diǎn)，但計(jì)算復(fù)雜度極高，例如對(duì)于長(zhǎng)度為8192的信號(hào)，采用小波字典分解，等價(jià)于求解一個(gè)長(zhǎng)度為8192*212992的線性規(guī)劃。MP算法雖然收斂速度較BP快，但不具備全局最優(yōu)性，且計(jì)算復(fù)雜度仍然很大。之后又出現(xiàn)了一系列同樣基于貪婪迭代思想的改進(jìn)算法，如正交匹配追蹤算法（OMP），樹形匹配追蹤（TMP），分段匹配追蹤（StOMP）算法等。2.4 觀測(cè)矩陣設(shè)計(jì)觀測(cè)部分的設(shè)計(jì)其實(shí)就是設(shè)計(jì)高效的觀測(cè)矩陣，換句話說(shuō)，就是要設(shè)計(jì)一個(gè)能捕捉稀疏信號(hào)中有用信息的高效的觀測(cè)（即采樣）協(xié)議，從而將該稀疏信號(hào)壓縮成少量的數(shù)據(jù)。這些協(xié)議是非自適應(yīng)的，僅僅需要用少量的固定波形和原信號(hào)聯(lián)系起來(lái)，這些固定波形和為信號(hào)提供簡(jiǎn)潔表示的基不相關(guān)。此外，觀測(cè)過(guò)程獨(dú)立于信號(hào)本身。進(jìn)一步講，使用優(yōu)化方法可以收集到的少量的觀測(cè)值中重構(gòu)信號(hào)。壓縮感知理論中，通過(guò)變換得到信號(hào)的稀疏系數(shù)向量后，需要設(shè)計(jì)觀測(cè)部分，它圍繞觀測(cè)矩陣展開。觀測(cè)器的設(shè)計(jì)目的是如何采樣得到M個(gè)觀測(cè)值，并保證從中能重構(gòu)出長(zhǎng)度為N的信號(hào)X或者基下等價(jià)的稀疏系數(shù)向量。顯然，如果觀測(cè)過(guò)程破壞了X中的信息，重構(gòu)是不可能的。觀測(cè)過(guò)程實(shí)際就是利用觀測(cè)矩陣的M個(gè)行向量對(duì)稀疏系數(shù)向量進(jìn)行投影，即計(jì)算和各個(gè)觀測(cè)向量之間的內(nèi)積，得到M個(gè)觀測(cè)值，記觀測(cè)向量，即 （式2.5）（b）（a） 圖2.3 觀測(cè)矩陣的圖形表示圖3.4（a）是（式3.7）的形象描述。這里，采樣過(guò)程是非自適應(yīng)的，也就是說(shuō)，無(wú)須根據(jù)信號(hào)X 而變化，觀測(cè)的不再是信號(hào)的點(diǎn)采樣而是信號(hào)的更一般的線性泛函。圖3.4（a）隨機(jī)高斯矩陣作為觀測(cè)矩陣，稀疏域選擇DCT變換域，對(duì)信號(hào)X進(jìn)行DCT變換后再進(jìn)行觀測(cè)。（b）是（a）圖的另一種表達(dá)，變換后的系數(shù)向量是稀疏的，K=3，觀測(cè)得到的Y是非零系數(shù)對(duì)應(yīng)的四個(gè)列向量的線性組合。對(duì)于給定的Y從（式3.7）中求出是一個(gè)線性規(guī)劃問(wèn)題，但由于M<< N，即方程的個(gè)數(shù)少于未知數(shù)的個(gè)數(shù)，這一欠定問(wèn)題一般來(lái)講無(wú)確定解。然而，如果具有K -項(xiàng)稀疏性（K<<M），則該問(wèn)題有望求出確定解。此時(shí)，只要設(shè)法確定出中的K個(gè)非零系數(shù)的合適位置，由于觀測(cè)向量Y是這些非零系數(shù)對(duì)應(yīng)的K個(gè)列向量的線性組合，從而可以形成一個(gè)的線性方程組來(lái)求解這些非零項(xiàng)的具體值。對(duì)此，有限等距性質(zhì)（restricted isometry property， RIP）給出了存在確定解的充要條件。這個(gè)充要條件和Cands、Tao等人提出的稀疏信號(hào)在觀測(cè)矩陣作用下必須保持的幾何性質(zhì)相一致。即，要想使信號(hào)完全重構(gòu)，必須保證觀測(cè)矩陣不會(huì)把兩個(gè)不同的K-項(xiàng)稀疏信號(hào)映射到同一個(gè)采樣集合中，這就要求從觀測(cè)矩陣中抽取的每M個(gè)列向量構(gòu)成的矩陣是非奇異的。從中可以看出，問(wèn)題的關(guān)鍵是如何確定非零系數(shù)的位置來(lái)構(gòu)造出一個(gè)可解的線性方程組。然而，判斷給定的是否具有RIP性質(zhì)是一個(gè)組合復(fù)雜度問(wèn)題。為了降低問(wèn)題的復(fù)雜度，能否找到一種易于實(shí)現(xiàn)RIP條件的替代方法成為構(gòu)造觀測(cè)矩陣F 的關(guān)鍵。文獻(xiàn)24指出如果保證觀測(cè)矩陣和稀疏基不相干，則在很大概率上滿足RIP性質(zhì)。不相干是指向量不能用稀疏表示。不相干性越強(qiáng)，互相表示時(shí)所需的系數(shù)越多；反之，相關(guān)性則越強(qiáng)。通過(guò)選擇高斯隨機(jī)矩陣作為即可高概率保證不相干性和RIP性質(zhì)。例如，可以生成多個(gè)零均值、方差為1/ N 的隨機(jī)高斯函數(shù)，將它們作為觀測(cè)矩陣的元素，使得以很高的概率具有RIP性質(zhì)。隨機(jī)高斯矩陣具有一個(gè)有用的性質(zhì)：對(duì)于一個(gè)的隨機(jī)高斯矩陣，可以證明當(dāng)時(shí)在很大概率下具有RIP性質(zhì)（其中c是一個(gè)很小的常數(shù)）。因此可以從M個(gè)觀測(cè)值中以很高的概率去恢復(fù)長(zhǎng)度為N的K-項(xiàng)稀疏信號(hào)?？傊?，隨機(jī)高斯矩陣與大多數(shù)固定正交基構(gòu)成的矩陣不相關(guān)，這一特性決定了選它作為觀測(cè)矩陣，其它正交基作為稀疏變換基時(shí)，滿足RIP性質(zhì)。為進(jìn)一步簡(jiǎn)化觀測(cè)矩陣，在某些條件下，以隨機(jī)為元素構(gòu)成的Rademacher矩陣也可以證明具有RIP性質(zhì)和普適性。 目前，對(duì)觀測(cè)矩陣的研究是壓縮感知理論的一個(gè)重要方面。在該理論中，對(duì)觀測(cè)矩陣的約束是比較寬松的，Donoho在文獻(xiàn)23中給出了觀測(cè)矩陣所必需具備的三個(gè)條件，并指出大部分一致分布的隨機(jī)矩陣都具備這三個(gè)條件，均可作為觀測(cè)矩陣，如：部分Fourier集、部分Hadamard集、一致分布的隨機(jī)投影（uniform Random Projection）集等，這與對(duì)RIP條件進(jìn)行研究得出的結(jié)論相一致。但是，使用上述各種觀測(cè)矩陣進(jìn)行觀測(cè)后，都僅僅能保證以很高的概率去恢復(fù)信號(hào)，而不能保證百分之百地精確重構(gòu)信號(hào)。對(duì)于任何穩(wěn)定的重構(gòu)算法是否存在一個(gè)真實(shí)的確定性的觀測(cè)矩陣仍是一個(gè)有待研究的問(wèn)題。文獻(xiàn)56則從信息論角度描述了信息論與CS之間的聯(lián)系。它指出，在模擬系統(tǒng)中，觀測(cè)噪聲也是影響觀測(cè)次數(shù)的重要因素，為說(shuō)明這一點(diǎn)，作者從信息論的角度研究了稀疏信號(hào)的率失真函數(shù)，給出了觀測(cè)噪聲對(duì)信號(hào)重建效果的影響。2.5 稀疏信號(hào)的重構(gòu)壓縮感知理論的核心問(wèn)題是從觀測(cè)得到的有限的M<<N個(gè)觀測(cè)樣本中重構(gòu)出N長(zhǎng)的原信號(hào)，即未知量個(gè)數(shù)比觀測(cè)量要多得多。由于觀測(cè)數(shù)量M 遠(yuǎn)小于信號(hào)長(zhǎng)度N，因此不得不面對(duì)求解欠定方程組的問(wèn)題，需要列舉出空間的個(gè)稀疏空間，在計(jì)算上是相當(dāng)復(fù)雜的。乍一看，我們幾乎不可能期望從Y 恢復(fù)每個(gè)。然而，文獻(xiàn)23-26，28的近期研究結(jié)果表明如果信號(hào)X 是稀疏的，那么（1）精確恢復(fù)是可能的；（2）真實(shí)信號(hào)實(shí)際上就是一個(gè)簡(jiǎn)單凸優(yōu)化問(wèn)題的解。但是，文獻(xiàn)30和23均指出由于信號(hào)X 是稀疏的或可壓縮的，這個(gè)前提從根本上改變了問(wèn)題，使得問(wèn)題可解，而觀測(cè)矩陣具有RIP性質(zhì)也為從M 個(gè)觀測(cè)值中精確恢復(fù)信號(hào)提供了理論保證。為更清晰地描述壓縮感知理論的信號(hào)重構(gòu)問(wèn)題， 首先定義向量的p-范數(shù)為 （式2.6）當(dāng)p=0時(shí)得到0-范數(shù)，它實(shí)際上表示X中非零項(xiàng)的個(gè)數(shù)。在信號(hào)X 稀疏或可壓縮的前提下，求解欠定方程組的問(wèn)題轉(zhuǎn)化為最小0-范數(shù)問(wèn)題： s.t. （式2.7） 但是，它需要列出X中所有非零項(xiàng)位置的種可能的線性組合，才能得到最優(yōu)解。因此，求解（式3.9）式的數(shù)值計(jì)算極不穩(wěn)定而且是NP難問(wèn)題?？梢姡瑝嚎s感知和稀疏分解問(wèn)題從數(shù)學(xué)意義上講是同樣的優(yōu)化問(wèn)題。于是稀疏分解的已有算法可以應(yīng)用到CS重構(gòu)中。Chen，Donoho和Saunders指出，求解一個(gè)更加簡(jiǎn)單的1-范數(shù)最小優(yōu)化問(wèn)題會(huì)產(chǎn)生同等的解（要求和不相關(guān)）： s.t. （式2.8）稍微的差別使得問(wèn)題變成了一個(gè)凸優(yōu)化問(wèn)題，于是可以方便地化簡(jiǎn)為線性規(guī)劃問(wèn)題，典型算法代表：BP算法。不過(guò)，1-范數(shù)最小化不是尋找稀疏解的唯一方法；其它方法，例如貪婪算法也已被提出。由以上討論我們可以得出結(jié)論：（1）相關(guān)性在CS中起著至關(guān)重要的作用：和相關(guān)性越小，需要采樣的數(shù)目就越少。（2）僅僅觀測(cè)比信號(hào)長(zhǎng)度小得多的任何M 個(gè)系數(shù)的集合，不會(huì)損失信息。（3）最小化帶線性方程約束的1-范數(shù)可以很容易地被轉(zhuǎn)化為線性規(guī)劃問(wèn)題，于是可以找到更高效的求解算法。已經(jīng)證明，如果，那么重構(gòu)成功的概率超過(guò)。2.6 重構(gòu)算法由前面的分析可知，過(guò)完備庫(kù)下的稀疏分解問(wèn)題和壓縮感知理論的重構(gòu)問(wèn)題都是線性約束下的0-范數(shù)求解問(wèn)題。因此這兩類問(wèn)題的求解本質(zhì)上是一樣的。于是用于過(guò)完備庫(kù)下稀疏分解的方法都可以用于求解壓縮感知理論的重構(gòu)計(jì)算。定理2已證明：對(duì)于一個(gè)K項(xiàng)-稀疏（K<<N）長(zhǎng)度為N的信號(hào)僅僅需要投影到另一個(gè)不相關(guān)基上的K+1個(gè)系數(shù)就可以以高概率被重構(gòu)。然而，求得最小的0-范數(shù)解需要進(jìn)行組合搜索，計(jì)算復(fù)雜度相當(dāng)高。Cands 和Donoho 近來(lái)提出一種可行的基于線性規(guī)劃的重構(gòu)方法，論證了只使用對(duì)信號(hào)的cK（c =3或者4）個(gè)觀測(cè)值，利用線性規(guī)劃的方法就可以得到和組合搜索相同的解。盡管BP算法可行，但在實(shí)際應(yīng)用中存在兩個(gè)問(wèn)題：第一，即使對(duì)常見的圖像尺寸，算法的計(jì)算復(fù)雜度也難以忍受，在采樣點(diǎn)個(gè)數(shù)滿足，時(shí)，重構(gòu)計(jì)算復(fù)雜度的量級(jí)在；第二，由于1-范數(shù)無(wú)法區(qū)分稀疏系數(shù)尺度的位置，所以盡管整體上重構(gòu)信號(hào)在歐氏距離上逼近原信號(hào)，但存在低尺度能量搬移到了高尺度的現(xiàn)象，從而容易出現(xiàn)一些人工效應(yīng)，如一維信號(hào)會(huì)在高頻出現(xiàn)振蕩。針對(duì)上述問(wèn)題，2005 年1 月Cands 和Romberg 提出了不同的信號(hào)恢復(fù)方法，該方法要求對(duì)原信號(hào)具有少量的先驗(yàn)條件，同時(shí)也可以對(duì)所求結(jié)果施加適當(dāng)?shù)南拗疲约s束重構(gòu)信號(hào)的特性。通過(guò)在凸集上交替投影（Projections onto Convex Sets）的方法，可以快速求解線性規(guī)劃問(wèn)題。另一類基于貪婪思想的迭代算法以更多的觀測(cè)數(shù)量作為代價(jià)達(dá)到了更加快速重構(gòu)的目的。J.Tropp和A.C.Gilbert提出利用匹配追蹤（MP）和正交匹配追蹤（OMP）算法來(lái)求解優(yōu)化問(wèn)題重構(gòu)信號(hào)，大大提高了計(jì)算的速度，且易于實(shí)現(xiàn)。樹形匹配追蹤（TMP）算法是2005年Chinh La 和Minh N.Do提出的。該方法針對(duì)BP、MP和OMP方法沒(méi)有考慮信號(hào)的多尺度分解時(shí)稀疏信號(hào)在各子帶位置的關(guān)系，將稀疏系數(shù)的樹型結(jié)構(gòu)加以利用，進(jìn)一步提升了重構(gòu)信號(hào)的精度和求解的速度。匹配追蹤類算法都是基于貪婪迭代算法，以多于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)題。E. Hale， W. Yin基于分裂算子和同倫算子提出了求解最小1-范數(shù)大規(guī)模問(wèn)題的方法，適合于糾錯(cuò)編碼、磁共振成像、NMR波譜研究等領(lǐng)域的大規(guī)模問(wèn)題求解。 在上述各種方法中，觀測(cè)矩陣中的所有值都非零，這樣信號(hào)采樣過(guò)程的計(jì)算量是O(MN)，在大規(guī)模的數(shù)據(jù)面前，這個(gè)量級(jí)還是非常大的。因此一類利用稀疏矩陣作為觀測(cè)矩陣進(jìn)行采樣的方法出現(xiàn)了。Graham Cormode等人，提出利用分組測(cè)試和隨機(jī)子集選取來(lái)估計(jì)稀疏信號(hào)的非零系數(shù)的位置和取值，該方法需要的采樣數(shù)為，信號(hào)重構(gòu)的計(jì)算復(fù)雜度為，得到重構(gòu)信號(hào)的速度更快。Gilbert等人在2006 年4 月提出了鏈?zhǔn)阶粉櫍–P，Chaining Pursuit）方法來(lái)恢復(fù)可壓縮信號(hào)。利用個(gè)采樣觀測(cè)重構(gòu)信號(hào)，需要計(jì)算量為，該方法對(duì)特別稀疏信號(hào)的恢復(fù)計(jì)算性能較高，但當(dāng)信號(hào)的稀疏度減少，需要的采樣點(diǎn)數(shù)會(huì)迅速增加，甚至超過(guò)信號(hào)本身的長(zhǎng)度，這就失去了壓縮采樣的意義。總之，目前為止出現(xiàn)的重構(gòu)算法都可歸入以下三大類：（1）貪婪追蹤算法：這類方法是通過(guò)每次迭代時(shí)選擇一個(gè)局部最優(yōu)解來(lái)逐步逼近原始信號(hào)。這些算法包括MP算法，OMP算法，分段OMP算法（StOMP）和正則化OMP（ROMP）算法。（2）凸松弛法：這類方法通過(guò)將非凸問(wèn)題轉(zhuǎn)化為凸問(wèn)題求解找到信號(hào)的逼近，如BP算法，內(nèi)點(diǎn)法，梯度投影方法和迭代閾值法。（3）組合算法：這類方法要求信號(hào)的采樣支持通過(guò)分組測(cè)試快速重建，如傅立葉采樣，鏈?zhǔn)阶粉櫤虷HS追蹤等。總之，每種算法都有其固有的缺點(diǎn)。凸松弛法重構(gòu)信號(hào)所需的觀測(cè)次數(shù)最少，但往往計(jì)算負(fù)擔(dān)很重。貪婪追蹤算法在運(yùn)行時(shí)間和采樣效率上都位于另兩種算法之間。由上面的分析可知，重構(gòu)算法和所需的觀測(cè)次數(shù)密切相關(guān)，當(dāng)前，壓縮感知理論的信號(hào)重構(gòu)問(wèn)題的研究主要集中在如何構(gòu)造穩(wěn)定的、計(jì)算復(fù)雜度較