隨著信息量的不斷增多，數(shù)據(jù)的采集、傳輸和存儲(chǔ)設(shè)備正面臨著日益嚴(yán)峻的壓力;同時(shí)數(shù)據(jù)處理過(guò)程中也會(huì)伴隨著信息泄露的風(fēng)險(xiǎn)，一部分?jǐn)?shù)據(jù)的丟失都有可能威脅生命和財(cái)產(chǎn)的安全，而如今數(shù)據(jù)泄露已經(jīng)屢見(jiàn)不鮮。因此在大數(shù)據(jù)時(shí)代，人們亟需尋找一種新的數(shù)據(jù)處理方式來(lái)降低信息處理過(guò)程中數(shù)據(jù)泄露風(fēng)險(xiǎn)，同時(shí)也釋放內(nèi)存、傳感器等硬件設(shè)備的壓力。

壓縮感知理論是在這樣的背景下產(chǎn)生的一種新興的信號(hào)采集和編解碼理論。該理論指出，不管是何種類型的信號(hào)，其在原始域或者某些變換域中，總是存在稀疏或者可壓縮的表示，在傳輸過(guò)程中可用遠(yuǎn)低于傳統(tǒng)奈奎斯特采樣的線性投影值，實(shí)現(xiàn)對(duì)信號(hào)的準(zhǔn)確或者高概率重建。

這一理論帶來(lái)了信號(hào)采樣理論的變革，對(duì)于信息安全也有重要的意義。學(xué)者將壓縮感知應(yīng)用至圖像的加密與傳輸、信息的安全編碼技術(shù)、信息的安全存儲(chǔ)、無(wú)線傳感器網(wǎng)絡(luò)的數(shù)據(jù)采集之中，有很多的信息處理以及信息安全領(lǐng)域?qū)W者對(duì)壓縮感知產(chǎn)生了較濃厚的研究興趣。本文首先簡(jiǎn)單介紹壓縮感知的誕生，然后扼要地介紹一下理論內(nèi)容和一些應(yīng)用方法，結(jié)合實(shí)際談一談目前一些比較成功的應(yīng)用。

一.壓縮感知的起源

“壓縮感知”思想最早出現(xiàn)在一篇2000年左右的博士論文《Near-Optimal Signal Recovery From Random Projections》[1]中。它的發(fā)現(xiàn)可以說(shuō)是一次意外，當(dāng)時(shí)加州理工學(xué)院教授Emmanuel Candès在研究名叫Shepp-Logan Phantom的圖像，這種標(biāo)準(zhǔn)圖像常被計(jì)算機(jī)科學(xué)家和工程師用來(lái)測(cè)試圖像還原算法。檢查的圖像質(zhì)量非常差，充滿了噪聲，他使用了L-1范數(shù)最小化的數(shù)學(xué)算法來(lái)去除噪聲條紋，結(jié)果算法真的起了作用。這種算法是將一個(gè)NP難問(wèn)題轉(zhuǎn)化為一個(gè)凸優(yōu)化問(wèn)題，也將壓縮感知的思想充分的體現(xiàn)：通過(guò)對(duì)信號(hào)不完備觀測(cè)后通過(guò)優(yōu)化算法來(lái)高概率還原信號(hào)(如圖1所示)。“就像給出10位銀行卡賬號(hào)的前三位，我就能猜出后七位一樣，并且，屢試不爽?！边@就是壓縮感知思想的開(kāi)端。

、

后來(lái)，Candès與陶哲軒進(jìn)行了交流，陶哲軒也開(kāi)始思考這個(gè)問(wèn)題，上述交流成為一篇關(guān)于壓縮感知論文的基礎(chǔ)。另外一位奠基人是Donoho，他的一篇代表作《Compressed sensing》[2]可以說(shuō)是一篇較為完整系統(tǒng)地闡述壓縮感知原理以及推導(dǎo)的論文。

以上這些都是壓縮感知的起源。

二.壓縮感知理論內(nèi)容以及獲取和求解方法

壓縮感知理論本身的含義為“通過(guò)對(duì)信號(hào)的高度不完備線性測(cè)量的高精確重建[3]”，在該理論框架下，采樣速率不再取決于信號(hào)的帶寬，而在很大程度上取決于兩個(gè)基本準(zhǔn)則：稀疏性和非相關(guān)性。

壓縮感知理論

主要包括三部分：

(1)信號(hào)的稀疏表示;

(2)設(shè)計(jì)測(cè)量矩陣，要在降低維數(shù)的同時(shí)保證原始信號(hào)x的信息損失最小;

(3)設(shè)計(jì)信號(hào)恢復(fù)算法，利用M個(gè)觀測(cè)值無(wú)失真地恢復(fù)出長(zhǎng)度為N的原始信號(hào)。

理論依據(jù)[4](主要由陶哲軒以及Candès推導(dǎo)和證明)

(1)設(shè)長(zhǎng)度為N的信號(hào)X在某個(gè)正交基Ψ上是K-稀疏的(即含有k個(gè)非零值);

(2)如果能找到一個(gè)與Ψ不相關(guān)(不相干)的觀測(cè)基Φ;

(3)用觀測(cè)基Φ觀測(cè)原信號(hào)得到長(zhǎng)度M的一維測(cè)量值M個(gè)觀測(cè)值Y，K

(4)那么就可以利用各種優(yōu)化方法從觀測(cè)值Y中高概率恢復(fù)X。

壓縮感知高概率重構(gòu)信號(hào)方法流程如下圖2所示：

??

圖2 壓縮感知信號(hào)恢復(fù)流程圖

數(shù)學(xué)表達(dá)

壓縮感知方程為：y=Φx=ΦΨs=Θs。(圖3)

其中設(shè)x為長(zhǎng)度為N的一維信號(hào)，稀疏度為k(即含有k個(gè)非零值)，y為長(zhǎng)度為M的一維測(cè)量值，Φ為觀測(cè)矩陣，Ψ為稀疏基，s為稀疏系數(shù)。

然后將原來(lái)的測(cè)量矩陣Φ變換為Θ=ΦΨ，解出s的逼近值s’，則原信號(hào)x’ = Ψs’。

??

圖3 壓縮感知方程表示圖

壓縮感知獲取和求解方法

壓縮感知在應(yīng)用時(shí)主要存在兩個(gè)問(wèn)題：

問(wèn)題1：如何設(shè)計(jì)觀測(cè)矩陣和信號(hào)的稀疏基從而獲取到較好地觀測(cè)值，求解方法如下表1：

??

表1 壓縮感知獲取策略表

問(wèn)題2：如何有效地進(jìn)行信號(hào)的重構(gòu)即求出壓縮感知方程中信號(hào)x的近似解。求解方法如下圖4所示：

??

圖4 壓縮感知信號(hào)重構(gòu)方法

三.壓縮感知的應(yīng)用領(lǐng)域和應(yīng)用事例

壓縮傳感技術(shù)是壓縮感知理論的應(yīng)用之一。它是一種抽象的數(shù)學(xué)概念，最初用在圖像處理之中，并逐步擴(kuò)展應(yīng)用到成像以外的許多領(lǐng)域。

要說(shuō)到壓縮感知較為成功的應(yīng)用事例，首當(dāng)其沖的那就是美國(guó)Rice大學(xué)發(fā)明的單像素相機(jī)[14]。在整套系統(tǒng)中，被拍攝物體的圖像經(jīng)過(guò)鏡頭打在DMD(數(shù)字微鏡芯片，Digital Micromirror Device)上，而經(jīng)過(guò)DMD反射的圖像又經(jīng)過(guò)二次鏡頭聚焦在只有一個(gè)像素的傳感器上，形成一個(gè)光信號(hào)。而在拍攝過(guò)程中，DMD上每個(gè)鏡片反射的明暗矩陣以偽隨機(jī)碼的形式快速變換，每變化一次形成一個(gè)像素的信號(hào)。經(jīng)過(guò)對(duì)每次的信號(hào)和偽隨機(jī)碼綜合進(jìn)行計(jì)算，就得到了物體的影像。相機(jī)的模型與結(jié)構(gòu)如下圖5所示:

??

圖5 單像素相機(jī)結(jié)構(gòu)圖

這款相機(jī)的關(guān)鍵部件是由德州儀器生產(chǎn)的數(shù)字微鏡芯片(DMD)，這款芯片主要用在數(shù)字背投或是投影機(jī)中。DMD由大量只有細(xì)菌大小的鏡片組成，每塊微型鏡片都一面反光一面不反光，并可以快速翻轉(zhuǎn)。

以下是其中幾個(gè)應(yīng)用：

• 圖像信息安全。壓縮感知具有同時(shí)采樣、壓縮和加密數(shù)據(jù)的良好特性,在圖像安全方面引起了研究人員的廣泛關(guān)注。目前融合壓縮感知，學(xué)者將其應(yīng)用到圖像加密、圖像哈希、數(shù)據(jù)隱藏和安全圖像檢索技術(shù)之中。例如一些基于壓縮感知的水印方法被提出來(lái)，它們可以用于有損信道的數(shù)據(jù)傳輸，將有用信息隱蔽傳輸。
• 無(wú)線傳感器網(wǎng)絡(luò)(WSN)。由于傳感器節(jié)點(diǎn)采集的數(shù)據(jù)有時(shí)空相關(guān)性，滿足壓縮感知理論應(yīng)用中信號(hào)是稀疏性和可壓縮性的條件，且傳感器節(jié)點(diǎn)資源有限，匯聚節(jié)點(diǎn)性能強(qiáng)大，正好適用于壓縮感知理論編碼簡(jiǎn)單、解碼復(fù)雜的特點(diǎn)，因此，基于壓縮感知的 WSN 數(shù)據(jù)收集的技術(shù)得到逐步深入和廣泛的研究和發(fā)展。比如Bajwa和Haupt等將壓縮感知理論應(yīng)用于無(wú)線傳感器網(wǎng)絡(luò)的數(shù)據(jù)采集[15]。
• 磁共振成像(MRI)。在醫(yī)學(xué)上，磁共振的工作原理是進(jìn)行許多次(但次數(shù)仍是有限的)測(cè)量(基本上就是對(duì)人體圖像進(jìn)行離散拉東變換—或稱為X光變換)，再對(duì)數(shù)據(jù)進(jìn)行加工來(lái)生成圖像。由于測(cè)量次數(shù)必須很多，整個(gè)過(guò)程對(duì)患者來(lái)說(shuō)太過(guò)漫長(zhǎng)。壓縮傳感技術(shù)可以顯著減少測(cè)量次數(shù)，加快成像(甚至有可能做到實(shí)時(shí)成像，也就是核磁共振的視頻而非靜態(tài)圖像)。此外我們還可以以測(cè)量次數(shù)換圖像質(zhì)量，即用與原來(lái)一樣的測(cè)量次數(shù)可以得到更高的圖像分辨率。
• 線性安全編碼。壓縮傳感技術(shù)提供了一個(gè)簡(jiǎn)單的方法，讓多個(gè)傳送者可以將其信號(hào)帶糾錯(cuò)地合并傳送，這樣即使輸出信號(hào)的一大部分丟失或毀壞，仍然可以恢復(fù)出原始信號(hào)。例如，可以用任意一種線性編碼把1000比特信息編碼進(jìn)一個(gè)3000比特的流。那么，即使其中300位被(惡意)毀壞，原始信息也能完全無(wú)損失地完整重建。這是因?yàn)閴嚎s傳感技術(shù)可以把破壞動(dòng)作本身看作一個(gè)稀疏的信號(hào)(只集中在3000比特中的300位)。

四.總結(jié)與展望

隨著壓縮感知理論及其技術(shù)的發(fā)展，信號(hào)處理的諸多領(lǐng)域發(fā)生了革命性變化，人們將其應(yīng)用至信號(hào)處理的諸多領(lǐng)域之中，例如視頻目標(biāo)追蹤[16]、無(wú)線傳感器網(wǎng)絡(luò)之中的數(shù)據(jù)安全傳輸與采集[17]、圖像的加密算法[18]等等，這些技術(shù)也都可以用于信息安全之中。壓縮感知已經(jīng)成為信號(hào)處理領(lǐng)域的利器。由于有嚴(yán)格的數(shù)學(xué)證明以及推導(dǎo)，壓縮感知具備較為深厚的理論基礎(chǔ)。壓縮感知的信號(hào)采集與重構(gòu)算法因信號(hào)而異，因此擁有一個(gè)通用的壓縮感知信號(hào)采集和重建策略將是非常有益的，這也將是所有研究者所追求的目標(biāo)。

參考文獻(xiàn)：

[1] E. J. Candès, Tao T . Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?[J]. IEEE Transactions on Information Theory, 2006, 52(12):5406-5425.

[2] Donoho D L . Compressed sensing[J]. IEEE Transactions on Information Theory, 2006, 52(4):1289-1306.

[3] E. J. Candès, Emmanuel & Romberg, Justin & Tao, Terence. Robust Uncertainty Principles:Exact Signal Frequency Information. [J] IEEE Transactions on Information Theory,2006, 52:489-509.

[4] E. J. Candès and M. B. Wakin,‘An introduction to compressive sampling’ IEEE Signal Process. Mag., vol. 25, no. 2, pp. 21–30, Mar. 2008.

[5] Laska J N , Kirolos S , Duarte M F , et al. Theory and Implementation of an Analog-to-Information Converter using Random Demodulation[C]// IEEE International Symposium on Circuits & Systems. IEEE, 1962.

[6] Mishali M , Eldar Y C . From Theory to Practice: Sub-Nyquist Sampling of Sparse Wideband Analog Signals[J]. IEEE Journal of Selected Topics in Signal Processing, 2010, 4(2):375-391.

[7] Yoo J , Becker S , Monge M , et al. Design and implementation of a fully integrated compressed-sensing signal acquisition system[C]// Acoustics, Speech and Signal Processing (ICASSP), 2012 IEEE International Conference on. IEEE, 2012.

[8] Tropp J A . Random Filters for Compressive Sampling[C]// Conference on Information Sciences & Systems. IEEE, 2006.

[9] Romberg, Justin. Compressive Sensing by Random Convolution[J]. SIAM Journal on Imaging Sciences, 2009, 2(4):1098-1128.

[10] Slavinsky J P , Laska J N , Davenport M A , et al. The compressive multiplexer for multi-channel compressive sensing[C]// IEEE International Conference on Acoustics. IEEE, 2011.

[11] Chen S S , Saunders D M A . Atomic Decomposition by Basis Pursuit[J]. SIAM Review, 2001, 43(1):129-159.

[12] S. G. Mallat and Z. Zhang, Matching pursuits with time-frequency dictionaries, [J]IEEE Trans. Signal Process, 1993.

[13] Y. C. Pati, R. Rezaiifar, and P. S. Krishnaprasad, Orthogonal matching pursuit: Recursive function approximation with applications to wavelet decomposition,[C] in Proc. 27th Asilomar Conf. Signals, Syst. Comput., vol. 1. Pacific Grove, CA, USA, 1993, pp. 40–44.

[14] Duarte M F , Davenport M A , Takhar D , et al. Single-Pixel Imaging via Compressive Sampling[J]. IEEE Signal Processing Magazine, 2008, 25(2):83-91.

[15] Bajwa W U Z , Haupt J , Sayeed A M , et al. Compressive wireless sensing[C]// Proceedings of the Fifth International Conference on Information Processing in Sensor Networks, IPSN 2006, Nashville, Tennessee, USA, April 19-21, 2006. ACM, 2006.

[16] Liu J, Han C, Han F. A novel compressed sensing based track before detect algorithm for tracking multiple targets.[C]// International Conference on Information Fusion. 2013.

[17] 包明杰, 張浩然, 王妃. 壓縮感知在無(wú)線傳感網(wǎng)絡(luò)的應(yīng)用綜述[J]. 微型機(jī)與應(yīng)用, 2016, 35(14):16-18.

[18] 王海嬌. 基于壓縮感知的圖像加密和檢索方法的研究[D].

??

【本文為51CTO專欄作者“中國(guó)保密協(xié)會(huì)科學(xué)技術(shù)分會(huì)”原創(chuàng)稿件，轉(zhuǎn)載請(qǐng)聯(lián)系原作者】

??戳這里，看該作者更多好文??