壓縮感知理論簡(jiǎn)介PPT課件

1、 壓縮感知理論簡(jiǎn)介壓縮感知理論簡(jiǎn)介 The Introduction of Compressed Sensing (CS) Theory 西安工程大學(xué)理學(xué)院西安工程大學(xué)理學(xué)院 李海洋李海洋1 1 背景介紹背景介紹 1.1：傳統(tǒng)采樣理論簡(jiǎn)介 1.2：壓縮感知理論的提出2 2 壓縮感知理論主要研究?jī)?nèi)容壓縮感知理論主要研究?jī)?nèi)容 2.1：信號(hào)的稀疏表示 2.2：觀測(cè)矩陣的設(shè)計(jì) 2.3：信號(hào)重構(gòu)3 3 壓縮感知應(yīng)用壓縮感知應(yīng)用- -單像素CS相機(jī) 1.1 傳統(tǒng)采樣理論簡(jiǎn)介傳統(tǒng)采樣理論簡(jiǎn)介 信信號(hào)號(hào)采采樣樣壓壓縮縮傳傳輸輸重重構(gòu)構(gòu)Nyquist-Shannon 采樣采樣定律定律JEPG等等傳統(tǒng)的信號(hào)處理過(guò)

2、程傳統(tǒng)的信號(hào)處理過(guò)程 傳統(tǒng)的基于Nyquist-Shannon 采樣定理指導(dǎo)下的信息采樣理論的不足主要表現(xiàn)在以下兩個(gè)方面：1、根據(jù) Nyquist-Shannon 采樣定律，采樣速率需達(dá)到信號(hào)帶寬的兩倍以上才能精確重構(gòu)信號(hào)。而現(xiàn)實(shí)生活中，隨著信息技術(shù)的高速發(fā)展，信息量的需求增加，攜帶信息的信號(hào)所占帶寬也越來(lái)越大，因此對(duì)采樣的硬件設(shè)備的要求也越來(lái)越高。2、另一方面，在實(shí)際應(yīng)用中，為了降低信號(hào)的存儲(chǔ)、處理和傳輸成本，人們又不得不經(jīng)由壓縮方式減少信號(hào)表示的比特?cái)?shù)，以此拋棄認(rèn)為不重要的數(shù)據(jù)，這種高速采樣再拋棄的過(guò)程顯然是對(duì)采樣資源的巨大浪費(fèi)。 1.2 壓縮感知理論的提出壓縮感知理論的提出 既然傳統(tǒng)方法

3、采樣的多數(shù)數(shù)據(jù)會(huì)被拋棄，那么，為什么還要獲取全部數(shù)據(jù)而不直接獲取需要保留的數(shù)據(jù)呢？ 采集很少一部分?jǐn)?shù)據(jù)并且期望從這些少量數(shù)據(jù)中解壓出大量信息，有無(wú)這種可能呢？D. Donoho, Candes，T. Tao 等人證明了如果信號(hào)具有稀疏性的特性，那么就可能存在一種算法能夠從這些少量的數(shù)據(jù)中還原出原先的信息。 信信號(hào)號(hào)壓縮壓縮感知感知傳傳輸輸重重構(gòu)構(gòu)信信號(hào)號(hào)采采樣樣壓壓縮縮2 2 壓縮感知理論主要研究?jī)?nèi)容壓縮感知理論主要研究?jī)?nèi)容 2.12.1：信號(hào)的稀疏表示：信號(hào)的稀疏表示 2.2 2.2：觀測(cè)矩陣的設(shè)計(jì)：觀測(cè)矩陣的設(shè)計(jì) 2.32.3：信號(hào)重構(gòu)：信號(hào)重構(gòu) 2.1 信號(hào)的稀疏表示信號(hào)的稀疏表示稀疏性

4、的定義稀疏性的定義： 一個(gè)實(shí)值有限長(zhǎng)的N維離散信號(hào) ，它可以用一個(gè)標(biāo)準(zhǔn)正交基 的線性組合來(lái)表示，其中 表示矩陣 的轉(zhuǎn)置，那么有 其中 ，若 在基 上僅有 個(gè)非零系數(shù) 時(shí)，稱 為信號(hào) 的稀疏基， 是 稀疏(K-Sparsity)的。1NxR12,TkK T1Nkkkx ,kkxxKKNkxxK 如圖是一個(gè)稀疏度為3的稀疏變換， , 向量 基本都是非零值， 但將其變換到 域 時(shí)，非零值就只有3 個(gè)了，數(shù)目遠(yuǎn)小于 原來(lái)的非零數(shù)目，實(shí) 現(xiàn)了信號(hào)的稀疏表 示。 xx 如何尋找信號(hào)的最佳稀疏域呢？如何尋找信號(hào)的最佳稀疏域呢？ 這是壓縮感知理論的基礎(chǔ)和前提，也是信號(hào)精確重構(gòu)的保證。對(duì)稀疏表示研究主要有兩個(gè)方

5、面：（1）基函數(shù)字典下的稀疏表示：）基函數(shù)字典下的稀疏表示： 尋找一個(gè)正交基使得信號(hào)表示的稀疏系數(shù)盡可能的少。比較常用的基有：高斯矩陣、小波基、正（余）弦基、Curvelet基等。Candes和Tao經(jīng)研究發(fā)現(xiàn)光滑信號(hào)的Fourier 系數(shù)、小波系數(shù)、有界變差函數(shù)的全變差范數(shù)、振蕩信號(hào)的Gabor 系數(shù)及具有不連續(xù)邊緣的圖像信號(hào)的Curvelet 系數(shù)等都具有足夠的稀疏性,可以通過(guò)壓縮感知理論恢復(fù)信號(hào)。（2）超完備庫(kù)下的稀疏表示：）超完備庫(kù)下的稀疏表示： 用超完備的冗余函數(shù)庫(kù)來(lái)取代基函數(shù)，稱之為冗余字典，字典中的元素被稱之為原子，目的是從冗余字典中找到具有最佳線性組合的K項(xiàng)原子來(lái)逼近表示一個(gè)信

6、號(hào)，稱作信號(hào)的稀疏逼近或高度非線性逼近。 一是如何構(gòu)造這樣一個(gè)適合某一類(lèi)信號(hào)的冗余字典； 二是在已知冗余字典的前提下如何設(shè)計(jì)快速有效的分解方法來(lái)稀疏地表示某一個(gè)信號(hào)。2.2 觀測(cè)矩陣的設(shè)計(jì)觀測(cè)矩陣的設(shè)計(jì) 觀測(cè)器的目的是采樣得到 個(gè)觀測(cè)值，并保證從中能夠重構(gòu)出原來(lái)長(zhǎng)度為 的信號(hào) 或者稀疏基下的系數(shù)向量 。 觀測(cè)過(guò)程就是利用 觀測(cè)矩陣的 個(gè)行向量對(duì)稀疏系數(shù)向量進(jìn)行投影，得到 個(gè)觀測(cè)值，即MNxMNMM如果我們假設(shè)信號(hào)已經(jīng)是稀疏的，那么上面的方程就可以寫(xiě)作 ,TYx其中Yx觀測(cè)矩陣要滿足什么樣的條件呢？觀測(cè)矩陣要滿足什么樣的條件呢？ 從上式中求出 是一個(gè)線性方程組的求解問(wèn)題，但由于方程的個(gè)數(shù)遠(yuǎn)遠(yuǎn)少于

7、未知數(shù)的個(gè)數(shù)，即 ，因此，一般說(shuō)來(lái)，該方程組有無(wú)窮多個(gè)解 。 但如果 具有稀疏性，則有可能求出確定解。Candes、Tao等人提出必須保證觀測(cè)矩陣不會(huì)把兩個(gè)不同的 稀疏信號(hào)映射到同一個(gè)采樣幾何中，即上述線性方程組的稀疏解具有唯一性。 MNK 目前，關(guān)于測(cè)量矩陣的研究主要基于以下兩個(gè)方面： RIP條件條件：相干性相干性：222(1)(1)kkxAxx22,( )maxijijijA 隨機(jī)矩陣、結(jié)構(gòu)隨機(jī)矩陣與確定性矩陣. 雖然隨機(jī)矩陣能產(chǎn)生尺寸接近最優(yōu)的RIP 矩陣。 在工程實(shí)際中, 人們更希望構(gòu)造一個(gè)確定性RIP矩陣。因?yàn)榇_定性矩陣更利于工程設(shè)計(jì), 此外, 從構(gòu)造解碼算法角度來(lái)看, 確定性矩陣?yán)?/p>

8、于降低內(nèi)存、設(shè)計(jì)快速的恢復(fù)算法等。然而, 現(xiàn)在仍然缺少令人滿意的確定性RIP 矩陣構(gòu)造方法。結(jié)構(gòu)隨機(jī)矩陣. 與確定性矩陣相比, 結(jié)構(gòu)隨機(jī)矩陣多了些隨機(jī)性, 因而可以證明其具有較好的RIP 性質(zhì), 同時(shí), 結(jié)構(gòu)隨機(jī)矩陣的隨機(jī)性較弱, 一般僅具有行隨機(jī)性。 2.3 信號(hào)重構(gòu)信號(hào)重構(gòu) 首先介紹范數(shù)范數(shù)的概念。向量的p-范數(shù)范數(shù)為： 當(dāng)p=0時(shí)得到0-范數(shù)，它表示上式中非零項(xiàng)的個(gè)數(shù)。 由于觀測(cè)數(shù)量 ，不能直接求解，在信號(hào) 能稀疏表示的前提下，求解方程組的問(wèn)題轉(zhuǎn)化為最小0-范數(shù)問(wèn)題：11Nppipiss0min s.t. TTxYxMNx 對(duì)于0-范數(shù)問(wèn)題的求解是個(gè)NP問(wèn)題，在實(shí)際應(yīng)用中很難獲得問(wèn)題的可

9、行解。因此，尋求對(duì)以上問(wèn)題的松弛以獲得理想的逼近解，已成為稀疏信號(hào)重構(gòu)的重要手段。一種自然的想法是，用下面的模型來(lái)代替，我們稱之為p-范數(shù)優(yōu)化問(wèn)題（0p=1）：或者： 求解該最優(yōu)化問(wèn)題，得到稀疏域的系數(shù)，然后反變換即可以得到時(shí)域信號(hào)。 min. . pTTpxstYx2minpTTpYxx 目前出現(xiàn)的重構(gòu)算法主要有：目前出現(xiàn)的重構(gòu)算法主要有：1）第一類(lèi)貪婪算法）第一類(lèi)貪婪算法：這類(lèi)算法是通過(guò)每次迭代時(shí)選擇一個(gè)局部最優(yōu)解來(lái)逐步逼近原始信號(hào)，典型的貪婪算法-MP算法，貪婪算法是針對(duì)組合優(yōu)化提出, 目前已發(fā)展了多種變形，例如，OMP, OOMP, CosMP等。該類(lèi)重建算法速度快, 然而需要的測(cè)量數(shù)

10、據(jù)多且精度低。 2）第二類(lèi)凸優(yōu)化算法）第二類(lèi)凸優(yōu)化算法：即1-范數(shù)優(yōu)化問(wèn)題，這類(lèi)方法是將非凸問(wèn)題轉(zhuǎn)化為凸問(wèn)題求解找到信號(hào)的逼近，如BP算法，梯度投影方法等。該類(lèi)算法速度慢，然而需要的測(cè)量數(shù)據(jù)少且精度高。 但是基于 1-范數(shù)優(yōu)化問(wèn)題的信號(hào)重構(gòu)至少存在兩個(gè)方面的不足：（1）數(shù)據(jù)之間還可能存在很大的冗余難以去除； （2）無(wú)法區(qū)分稀疏尺度的位置（盡管重構(gòu)信號(hào)在歐式距離上逼近原始信號(hào), 但會(huì)出現(xiàn)低尺度的能量轉(zhuǎn)移到高尺度的現(xiàn)象, 因而易出現(xiàn)高頻震蕩現(xiàn)象）。）p-范數(shù)優(yōu)化問(wèn)題。范數(shù)優(yōu)化問(wèn)題。Xu 等人對(duì)1/2-范數(shù)優(yōu)化問(wèn)題的正則化問(wèn)題進(jìn)行了深入的研究，給出了問(wèn)題的解析解，并從數(shù)值實(shí)驗(yàn)的角度說(shuō)明了該問(wèn)題的解具

11、有較 1-范數(shù)重構(gòu)更好的稀疏性，且p越小，稀疏性越好。3 3 壓縮感知應(yīng)用壓縮感知應(yīng)用-單像素單像素CS相機(jī)相機(jī) 運(yùn)用壓縮感知原理，RICE大學(xué)成功研制了單像素CS相機(jī)。 傳統(tǒng)百萬(wàn)像素的相機(jī)需要百萬(wàn)個(gè)探測(cè)傳感器，而壓縮傳感數(shù)碼相機(jī)只使用一個(gè)探測(cè)器來(lái)采光，然后跟捕獲后的計(jì)算相結(jié)合來(lái)重構(gòu)圖像。這種樣機(jī)的鏡頭由兩部分組成：一個(gè)光電二極管和一個(gè)微鏡陣列。 該相機(jī)直接獲取的是M次隨機(jī)線性測(cè)量值而不是獲取原始信號(hào)的N 個(gè)像素值，為低像素相機(jī)拍攝高質(zhì)量圖像提供了可能?！皵?shù)字微鏡陣列”完成圖像在偽隨機(jī)二值模型上的線性投影的光學(xué)計(jì)算，其反射光由透鏡聚焦到單個(gè)光敏二極管上，光敏二極管兩端的電壓值即為一個(gè)測(cè)量值y，將此投影操作重復(fù)M次，即得到測(cè)量向量Y，然后用最小全變分算法構(gòu)建的數(shù)字信號(hào)處理器重構(gòu)原始圖像x。數(shù)字微鏡器件由數(shù)字電壓信號(hào)控制微鏡片的機(jī)械運(yùn)動(dòng)以實(shí)現(xiàn)對(duì)入射光線的調(diào)整，相當(dāng)于隨機(jī)觀測(cè)矩陣?，F(xiàn)為美國(guó)Stanford University 人文科學(xué)講座教授及統(tǒng)計(jì)學(xué)教授。他是美國(guó)人文與科學(xué)學(xué)院院士、美國(guó)工業(yè)與應(yīng)用數(shù)學(xué)學(xué)會(huì)(SIAM