壓縮感知與單像素照相機(jī)

1、這是數(shù)學(xué)家陶哲軒在他自己的blog上寫的一篇科普文章，討論的是近年來在應(yīng) 用數(shù)學(xué)領(lǐng)域里最熱門的話題之一：壓縮感知（compressed sensing）。所謂壓縮 感知，最核心的概念在于試圖從原理上降低對一個信號進(jìn)行測量的成本。比如說， 一個信號包含一千個數(shù)據(jù)，那么按照傳統(tǒng)的信號處理理論，至少需要做一千次測 量才能完整的復(fù)原這個信號。這就相當(dāng)于是說，需要有一千個方程才能精確地解 出一千個未知數(shù)來。但是壓縮感知的想法是假定信號具有某種特點(diǎn)（比如文中所 描述得在小波域上系數(shù)稀疏的特點(diǎn)），那么就可以只做三百次測量就完整地復(fù)原 這個信號（這就相當(dāng)于只通過三百個方程解出一千個未知數(shù)）?？上攵@件 事

2、情包含了許多重要的數(shù)學(xué)理論和廣泛的應(yīng)用前景，因此在最近三四年里吸引了 大量注意力，得到了非常蓬勃的發(fā)展。陶哲軒本身是這個領(lǐng)域的奠基人之一（可 以參考陶哲軒：長大的神童一文），因此這篇文章的權(quán)威性毋庸諱言。另外， 這也是比較少見的由一流數(shù)學(xué)家直接撰寫的關(guān)于自己前沿工作的普及性文章。需 要說明的是，這篇文章是雖然是寫給非數(shù)學(xué)專業(yè)的讀者，但是也并不好懂，也許 具有一些理工科背景會更容易理解一些?！咀髡逿erence Tao；譯者山寨盲流，他的更多譯作在這，那；校對 木遙】最近有不少人問我究竟壓縮感知是什么意思（特別是隨著最近這個概念名聲大 噪），所謂“單像素相機(jī)”又是怎樣工作的（又怎么能在某些場合比

3、傳統(tǒng)相機(jī)有 優(yōu)勢呢）。這個課題已經(jīng)有了大量文獻(xiàn)，不過對于這么一個相對比較新的領(lǐng)域， 還沒有一篇優(yōu)秀的非技術(shù)性介紹。所以筆者在此小做嘗試，希望能夠?qū)Ψ菙?shù)學(xué)專 業(yè)的讀者有所幫助。具體而言我將主要討論攝像應(yīng)用，盡管壓縮傳感作為測量技術(shù)應(yīng)用于比成像廣泛 得多的領(lǐng)域（例如天文學(xué)，核磁共振，統(tǒng)計選取，等等），我將在帖子結(jié)尾簡單 談?wù)勥@些領(lǐng)域。相機(jī)的用途，自然是記錄圖像。為了簡化論述，我們把圖像假設(shè)成一個長方形陣 列，比如說一個1024x2048像素的陣列（這樣就總共是二百萬像素）。為了省略 彩色的問題（這個比較次要），我們就假設(shè)只需要黑白圖像，那么每個像素就可 以用一個整型的灰度值來計量其亮度（例如用八位

4、整型數(shù)表示0到255, 16位表 示 0 到 65535）。接下來，按照最最簡化的說法，傳統(tǒng)相機(jī)會測量每一個像素的亮度（在上述例子 中就是二百萬個測量值），結(jié)果得到的圖片文件就比較大（用8位灰度值就是 2MB，16位灰度就是4MB）。數(shù)學(xué)上就認(rèn)為這個文件是用超高維矢量值描繪的（在 本例中就是約二百萬維）。在我開始講“壓縮感知”這個新故事之前，必須先快速回顧一下“老式壓縮”的 舊故事。（已經(jīng)了解圖像壓縮算法的讀者可以跳過這幾段。）上述的圖片會占掉相機(jī)的很多存儲空間（上傳到計算機(jī)里還占磁盤空間），在各 種介質(zhì)之間傳輸?shù)臅r候也要浪費(fèi)時間。于是，相機(jī)帶有顯著壓縮圖像的功能就順 理成章了（通常能從2MB

5、那么大壓縮到十分之一一一200KB的一小坨）。關(guān)鍵是 盡管“所有圖片”所構(gòu)成的空間要占用2MB的“自由度”或者說“熵”，由“有 意義的圖片”所構(gòu)成的空間其實(shí)要小得多，尤其是如果人們愿意降低一點(diǎn)圖像質(zhì) 量的話。（實(shí)際上，如果一個人真的利用所有的自由度隨機(jī)生成一幅圖片，他不 大可能得到什么有意義的圖像，而是得到相當(dāng)于電視熒屏上的靜電雪花那樣的隨 機(jī)噪聲之類。）怎么樣壓縮圖像？方式多種多樣，其中有些非常先進(jìn)，不過我來試試用一種不太 高科技的（而且也不太精確的）說法來描述一下這些先進(jìn)技術(shù)。圖像通常都含有 大片無細(xì)節(jié)部分一比如在風(fēng)景照里面，將近一半的畫面都可能被單色的天空背景 占據(jù)。我們假設(shè)提取一個大方

6、塊，比方說100 x100像素，其中完全是同一顏色的 假設(shè)是全白的吧。無壓縮時，這個方塊要占10000字節(jié)存儲空間（按照8 位灰度算）；但是我們可以只記錄這個方塊的維度和坐標(biāo)，還有填充整個方塊的 單一顏色;這樣總共也只要記錄四五個字節(jié)，省下了可觀的空間。不過在現(xiàn)實(shí)中， 壓縮效果沒有這么好，因?yàn)楸砻婵磥頉]有細(xì)節(jié)的地方其實(shí)是有著細(xì)微的色差的。 所以，給定一個無細(xì)節(jié)方塊，我們記錄其平均色值，就把圖片中這一塊區(qū)域抽象 成了單色色塊，只留下微小的殘余誤差。接下來就可以繼續(xù)選取更多色彩可見的 方塊，抽象成單色色塊。最后剩下的是亮度（色彩強(qiáng)度）很小的，肉眼無法察覺 的細(xì)節(jié)。于是就可以拋棄這些剩余的細(xì)節(jié)，只需

7、要記錄那些“可見”色塊的大小， 位置和亮度。日后則可以反向操作，重建出比原始圖像質(zhì)量稍低一些，占空間卻 小得多的復(fù)制圖片。其實(shí)上述的算法并不適合處理顏色劇烈變動的情況，所以在實(shí)際應(yīng)用中不很有效。 事實(shí)上，更好的辦法不是用均勻色塊，而是用“不均勻”的色塊一一比方說右半 邊色彩強(qiáng)度平均值大于左半邊這樣的色塊。這種情況可以用（二維）Haar小波 系統(tǒng)來描述。后來人們又發(fā)現(xiàn)一種更平滑的小波系統(tǒng)更能夠避免誤差，不過這 都是技術(shù)細(xì)節(jié)，我們就不深入討論了。然而所有這些系統(tǒng)的原理都是相同的：把 原始圖像表示為不同“小波（類似于上文中的色塊）”的線性疊加，記錄顯著的 （高強(qiáng)度的）小波的系數(shù)，放棄掉（或者用閾值排

8、除掉）剩下的小波系數(shù)。這種 “小波系數(shù)硬閾值”壓縮算法沒有實(shí)際應(yīng)用的算法（比如JPEG 2000標(biāo)準(zhǔn)中所定 義的）那么精細(xì)，不過多少也能描述壓縮的普遍原理。總體來講（也是非常簡化的說法），原始的1024x2048圖像可能含有兩百萬自由 度，想要用小波來表示這個圖像的人需要兩百萬個不同小波才能完美重建。但是 典型的有意義的圖像，從小波理論的角度看來是非常稀疏的，也就是可壓縮的： 可能只需要十萬個小波就已經(jīng)足夠獲取圖像所有的可見細(xì)節(jié)了，其余一百九十萬 小波只貢獻(xiàn)很少量的，大多數(shù)觀測者基本看不見的“隨機(jī)噪聲”。（這也不是永 遠(yuǎn)適用：含有大量紋理的圖像一比如毛發(fā)、毛皮的圖像用小波算法特別難壓 縮，也是

9、圖像壓縮算法的一大挑戰(zhàn)。不過這是另一個故事了。）接下來呢，如果我們（或者不如說是相機(jī)）事先知道兩百萬小波系數(shù)里面哪十萬 個是重要的，那就可以只計量這十萬個系數(shù)，別的就不管了。（在圖像上設(shè)置一 種合適的“過濾器”或叫“濾鏡”，然后計量過濾出來的每個像素的色彩強(qiáng)度， 是一種可行的系數(shù)計量方法。）但是，相機(jī)是不會知道哪個系數(shù)是重要的，所以 它只好計量全部兩百萬個像素，把整個圖像轉(zhuǎn)換成基本小波，找出需要留下的那 十萬個主導(dǎo)基本小波，再刪掉其余的。（這當(dāng)然只是真正的圖像壓縮算法的一個 草圖，不過為了便于討論我們還是就這么用吧。）那么，如今的數(shù)碼相機(jī)當(dāng)然已經(jīng)很強(qiáng)大了，沒什么問題干嗎還要改進(jìn)？事實(shí)上， 上述

10、的算法，需要收集大量數(shù)據(jù)，但是只需要存儲一部分，在消費(fèi)攝影中是沒有 問題的。尤其是隨著數(shù)據(jù)存儲變得很廉價，現(xiàn)在拍一大堆完全不壓縮的照片也無 所謂。而且，盡管出了名地耗電，壓縮所需的運(yùn)算過程仍然算得上輕松。但是， 在非消費(fèi)領(lǐng)域的某些應(yīng)用中，這種數(shù)據(jù)收集方式并不可行，特別是在傳感器網(wǎng)絡(luò) 中。如果打算用上千個傳感器來收集數(shù)據(jù)，而這些傳感器需要在固定地點(diǎn)呆上幾 個月那么長的時間，那么就需要盡可能地便宜和節(jié)能的傳感器這首先就排除 了那些有強(qiáng)大運(yùn)算能力的傳感器（然而這也相當(dāng)重要一一我們在接收處理數(shù) 據(jù)的接收端仍然需要現(xiàn)代科技提供的奢侈的運(yùn)算能力）。在這類應(yīng)用中，數(shù)據(jù)收 集方式越“傻瓜”越好（而且這樣的系統(tǒng)

11、也需要很強(qiáng)壯，比如說，能夠忍受10% 的傳感器丟失或者各種噪聲和數(shù)據(jù)缺損）。這就是壓縮傳感的用武之地了。其理論依據(jù)是：如果只需要10萬個分量就可以 重建絕大部分的圖像，那何必還要做所有的200萬次測量，只做10萬次不就夠 了嗎？（在實(shí)際應(yīng)用中，我們會留一個安全余量，比如說測量30萬像素，以應(yīng) 付可能遭遇的所有問題，從干擾到量化噪聲，以及恢復(fù)算法的故障。）這樣基本 上能使節(jié)能上一個數(shù)量級，這對消費(fèi)攝影沒什么意義，對傳感器網(wǎng)絡(luò)而言卻有實(shí) 實(shí)在在的好處。不過，正像我前面說的，相機(jī)自己不會預(yù)先知道兩百萬小波系數(shù)中需要記錄哪十 萬個。要是相機(jī)選取了另外10萬（或者30萬），反而把圖片中所有有用的信息 都

12、扔掉了怎么辦？ 解決的辦法簡單但是不太直觀。就是用非小波的算法來做30萬個測量盡管 我前面確實(shí)講過小波算法是觀察和壓縮圖像的最佳手段。實(shí)際上最好的測量其實(shí) 應(yīng)該是（偽）隨機(jī)測量一一比如說隨機(jī)生成30萬個“濾鏡”圖像并測量真實(shí)圖 像與每個濾鏡的相關(guān)程度。這樣，圖像與濾鏡之間的這些測量結(jié)果（也就是“相 關(guān)性”）很有可能是非常小非常隨機(jī)的。但是這是關(guān)鍵所在一一構(gòu)成圖像的 2百萬種可能的小波函數(shù)會在這些隨機(jī)的濾鏡的測量下生成自己特有的“特征”， 它們每一個都會與某一些濾鏡成正相關(guān)，與另一些濾鏡成負(fù)相關(guān)，但是與更多的 濾鏡不相關(guān)?？墒牵ㄔ跇O大的概率下）2百萬個特征都各不相同；更有甚者，其 中任意十萬個的

13、線性組合仍然是各不相同的（以線性代數(shù)的觀點(diǎn)來看，這是因?yàn)?一個30萬維線性子空間中任意兩個10萬維的子空間極有可能互不相交）。因此， 基本上是有可能從這30萬個隨機(jī)數(shù)據(jù)中恢復(fù)圖像的（至少是恢復(fù)圖像中的10 萬個主要細(xì)節(jié)）。簡而言之，我們是在討論一個哈希函數(shù)的線性代數(shù)版本。然而這種方式仍然存在兩個技術(shù)問題。首先是噪聲問題：10萬個小波系數(shù)的疊 加并不能完全代表整幅圖像，另190萬個系數(shù)也有少許貢獻(xiàn)。這些小小貢獻(xiàn)有可 能會干擾那10萬個小波的特征，這就是所謂的“失真”問題。第二個問題是如 何運(yùn)用得到的30萬測量數(shù)據(jù)來重建圖像。我們先來關(guān)注后一個問題。如果我們知道了 2百萬小波中哪10萬個是有用的，

14、 那就可以使用標(biāo)準(zhǔn)的線性代數(shù)方法（高斯消除法，最小二乘法等等）來重建信號。（這正是線性編碼最大的優(yōu)點(diǎn)之一一一它們比非線性編碼更容易求逆。大多數(shù)哈 希變換實(shí)際上是不可能求逆的這在密碼學(xué)上是一大優(yōu)勢，在信號恢復(fù)中卻不 是。）可是，就像前面說的那樣，我們事前并不知道哪些小波是有用的。怎么找 出來呢？ 一個單純的最小二乘近似法會得出牽扯到全部2百萬系數(shù)的可怕結(jié)果， 生成的圖像也含有大量顆粒噪點(diǎn)。要不然也可以代之以一種強(qiáng)力搜索，為每一組 可能的10萬關(guān)鍵系數(shù)都做一次線性代數(shù)處理，不過這樣做的耗時非?？植溃?共要考慮大約10的17萬次方個組合！），而且這種強(qiáng)力搜索通常是NP完備的（其中有些特例是所謂的“

15、子集合加總”問題）。不過還好，還是有兩種可行的 手段來恢復(fù)數(shù)據(jù)：-匹配追蹤：找到一個其標(biāo)記看上去與收集到的數(shù)據(jù)相關(guān)的小波；在數(shù)據(jù)中去除 這個標(biāo)記的所有印跡；不斷重復(fù)直到我們能用小波標(biāo)記“解釋”收集到的所有數(shù) 據(jù)。-基追蹤（又名L1模最小化）：在所有與錄得數(shù)據(jù)匹配的小波組合中，找到一 個“最稀疏的”，也就是其中所有系數(shù)的絕對值總和越小越好。（這種最小化的 結(jié)果趨向于迫使絕大多數(shù)系數(shù)都消失了。）這種最小化算法可以利用單純形法之 類的凸規(guī)劃算法，在合理的時間內(nèi)計算出來。需要注意到的是，這類圖像恢復(fù)算法還是需要相當(dāng)?shù)倪\(yùn)算能力的（不過也還不是 太變態(tài)），不過在傳感器網(wǎng)絡(luò)這樣的應(yīng)用中這不成問題，因?yàn)閳D像恢

16、復(fù)是在接收 端（這端有辦法連接到強(qiáng)大的計算機(jī)）而不是傳感器端（這端就沒辦法了）進(jìn)行 的?，F(xiàn)在已經(jīng)有嚴(yán)密的結(jié)果顯示，對原始圖像設(shè)定不同的壓縮率或稀疏性，這兩種算 法完美或近似完美地重建圖像的成功率都很高。匹配追蹤法通常比較快，而基追 蹤算法在考慮到噪聲時則顯得比較準(zhǔn)確。這些算法確切的適用范圍問題在今天仍 然是非常熱門的研究領(lǐng)域。（說來遺憾，目前還沒有出現(xiàn)對P不等于NP問題的 應(yīng)用；如果一個重建問題（在考慮到測量矩陣時）是NP完備的，那它剛好就不 能用上述算法解決。）由于壓縮傳感還是一個相當(dāng)新的領(lǐng)域（尤其是嚴(yán)密的數(shù)學(xué)結(jié)果剛剛出現(xiàn)），現(xiàn)在 就期望這個技術(shù)應(yīng)用到實(shí)用的傳感器上還為時尚早。不過已經(jīng)有概念

17、驗(yàn)證模型出 現(xiàn)了，其中最著名的是Rice大學(xué)研制的單像素相機(jī)。最后必須提到的是，壓縮傳感技術(shù)是一種抽象的數(shù)學(xué)概念，而不是具體的操作方 案，它可以應(yīng)用到成像以外的許多領(lǐng)域。以下只是其中幾個例子：-磁共振成像（MRI）。在醫(yī)學(xué)上，磁共振的工作原理是做許多次（但次數(shù)仍是有 限的）測量（基本上就是對人體圖像進(jìn)行離散拉東變換（也叫X光變換），再 對數(shù)據(jù)進(jìn)行加工來生成圖像（在這里就是人體內(nèi)水的密度分布圖像）。由于測量 次數(shù)必須很多，整個過程對患者來說太過漫長。壓縮傳感技術(shù)可以顯著減少測量 次數(shù)，加快成像（甚至有可能做到實(shí)時成像，也就是核磁共振的視頻而非靜態(tài)圖 像）。此外我們還可以以測量次數(shù)換圖像質(zhì)量，用與原來一樣的測量次數(shù)可以得 到好得多的圖像分辨率。-天文學(xué)。許多天文現(xiàn)象（如脈沖星）具有多種頻率震蕩特性，使其在頻域上是 高度稀疏也就是可壓縮的。壓縮傳感技術(shù)將使我們能夠在時域內(nèi)測量這些現(xiàn)象 （即記錄望遠(yuǎn)鏡數(shù)據(jù)）并能夠精確重建原始信號，即使原始數(shù)據(jù)不完整或者干擾 嚴(yán)重（原因可能是天氣不佳，上機(jī)時間不夠，或者就是因?yàn)榈厍蜃詡魇刮覀兊貌?到全時序的數(shù)據(jù)）。-線性編碼。壓縮傳感技術(shù)提供了一個簡單的方法，讓多個傳送者可以將其信號 帶