《壓縮感知極度欠采樣數(shù)據(jù)的重建》由會員分享，可在線閱讀，更多相關(guān)《壓縮感知極度欠采樣數(shù)據(jù)的重建（8頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、壓縮感知極度欠采樣數(shù)據(jù)的重建 壓縮感知一極度欠采樣數(shù)據(jù)的重建2011-03-15 14： 37壓縮感知是近年來 極為熱門的研究前沿，在若干應用領(lǐng)域中都引起矚目。關(guān)于這個題目，松鼠會 已經(jīng)翻譯了兩篇文章，一篇來自于壓縮感知技術(shù)最初的研究者陶哲軒（），一篇 來自威斯康辛大學的數(shù)學家艾倫伯格（本文正文）。這兩篇文章都是普及性的， 但是由于作者是專業(yè)的研究人員，所以事實上行文仍然偏于晦澀。因此我不揣 冒昧，在這里附上一個畫蛇添足的導讀，以幫助更多的讀者更好了解這個新穎 的研究領(lǐng)域在理論和實踐上的意義。 壓縮感知從字面上看起來，好像是數(shù)據(jù)壓縮的意思，而實則出于完全不同 的考慮。經(jīng)典的數(shù)據(jù)壓縮技術(shù)，無

2、論是音頻壓縮（例如mp3），圖像壓縮（例如 jpeg），視頻壓縮（mpeg），還是一般的編碼壓縮（zip），都是從數(shù)據(jù)本身的特性 出發(fā)，尋找并剔除數(shù)據(jù)中隱含的冗余度，從而達到壓縮的目的。這樣的壓縮有 兩個特點：第一、它是發(fā)生在數(shù)據(jù)已經(jīng)被完整采集到之后；第二、它本身需要 復雜的算法來完成。相較而言，解碼過程反而一般來說在計算上比較簡單，以 音頻壓縮為例，壓制一個mp3文件的計算量遠大于播放（即解壓縮）一個mp3文 件的計算量。 稍加思量就會發(fā)現(xiàn)，這種壓縮和解壓縮的不對稱性正好同人們的需求是相 反的。在大多數(shù)情況下，采集并處理數(shù)據(jù)的設(shè)備，往往是廉價、省電、計算能 力較低的便攜設(shè)備，例如傻瓜相機、

3、或者錄音筆、或者遙控監(jiān)視器等等。而負 責處理（即解壓縮）信息的過程卻反而往往在大型計算機上進行，它有更高的計 算能力，也常常沒有便攜和省電的要求。也就是說，我們是在用廉價節(jié)能的設(shè) 備來處理復雜的計算任務，而用大型高效的設(shè)備處理相對簡單的計算任務。這 一矛盾在某些情況下甚至會更為尖銳，例如在野外作業(yè)或者軍事作業(yè)的場合， 采集數(shù)據(jù)的設(shè)備往往曝露在自然環(huán)境之中，隨時可能失去能源供給或者甚至部 分喪失性能，在這種情況下，傳統(tǒng)的數(shù)據(jù)采集-壓縮-傳輸-解壓縮的模式就基本 上失效了。 壓縮感知的概念就是為了解決這樣的矛盾而產(chǎn)生的。既然采集數(shù)據(jù)之后反 正要壓縮掉其中的冗余度，而這個壓縮過程又相對來說比較困難

4、，那么我們?yōu)?什么不直接「采集」壓縮后的數(shù)據(jù)?這樣采集的任務要輕得多，而且還省去了壓 縮的麻煩。這就是所謂的「壓縮感知」，也就是說，直接感知壓縮了的信息。 可是這看起來是不可能的事情。因為壓縮后的數(shù)據(jù)并不是壓縮前的數(shù)據(jù)的 一個子集，并不是說，本來有照相機的感光器上有一千萬個像素，扔掉其中八 百萬個，剩下的兩百萬個采集到的就是壓縮后的圖像，一這樣只能采集到不 完整的一小塊圖像，有些信息被永遠的丟失了而且不可能被恢復。如果要想采 集很少一部分數(shù)據(jù)并且指望從這些少量數(shù)據(jù)中「解壓縮」出大量信息，就需要 保證：第一：這些少量的采集到的數(shù)據(jù)包含了原信號的全局信息，第二：存在 一種算法能夠從這些少量的數(shù)據(jù)

5、中還原出原先的信息來。 有趣的是，在某些特定的場合，上述第一件事情是自動得到滿足的。最典 型的例子就是醫(yī)學圖像成像，例如斷層掃描（CT ）技術(shù)和核磁共振（MRI）技術(shù)。對 這兩種技術(shù)稍有了解的人都知道，這兩種成像技術(shù)中，儀器所采集到的都不是 直接的圖像像素，而是圖像經(jīng)歷過全局傅立葉變換后的數(shù)據(jù)。也就是說，每一 個單獨的數(shù)據(jù)都在某種程度上包含了全圖像的信息。在這種情況下，去掉一部 分采集到的數(shù)據(jù)并不會導致一部分圖像信息永久的丟失（它們?nèi)耘f被包含在其它 數(shù)據(jù)里）。這正是我們想要的情況。 上述第二件事就要歸功于陶哲軒和坎戴的工作了。他們的工作指出，如果 假定信號（無論是圖像還是聲音還是其他別的種

6、類的信號）滿足某種特定的「稀 疏性」，那么從這些少量的測量數(shù)據(jù)中，確實有可能還原出原始的較大的信號 來，其中所需要的計算部分是一個復雜的迭代優(yōu)化過程，即所謂的「L1-最小化」 算法。 把上述兩件事情放在一起，我們就能看到這種模式的優(yōu)點所在。它意味著： 我們可以在采集數(shù)據(jù)的時候只簡單采集一部分數(shù)據(jù)（「壓縮感知」），然后把復 雜的部分交給數(shù)據(jù)還原的這一端來做，正好匹配了我們期望的格局。在醫(yī)學圖 像領(lǐng)域里，這個方案特別有好處，因為采集數(shù)據(jù)的過程往往是對病人帶來很大 麻煩甚至身體傷害的過程。以X光斷層掃描為例，眾所周知X光輻射會對病人 造成身體損害，而「壓縮感知」就意味著我們可以用比經(jīng)典方法少得多的

7、輻射 劑量來進行數(shù)據(jù)采集，這在醫(yī)學上的意義是不言而喻的。 這一思路可以擴展到很多領(lǐng)域。在大量的實際問題中，我們傾向于盡量少 地采集數(shù)據(jù)，或者由于客觀條件所限不得不采集不完整的數(shù)據(jù)。如果這些數(shù)據(jù) 和我們所希望重建的信息之間有某種全局性的變換關(guān)系，并且我們預先知道那 些信息滿足某種稀疏性條件，就總可以試著用類似的方式從比較少的數(shù)據(jù)中還 原出比較多的信號來。到今天為止，這樣的研究已經(jīng)拓展地非常廣泛了。 但是同樣需要說明的是，這樣的做法在不同的應用領(lǐng)域里并不總能滿足上 面所描述的兩個條件。有的時候，第一個條件（也就是說測量到的數(shù)據(jù)包含信號 的全局信息）無法得到滿足，例如最傳統(tǒng)的攝影問題，每個感光元

8、件所感知到的 都只是一小塊圖像而不是什么全局信息，這是由照相機的物理性質(zhì)決定的。為 了解決這個問題，美國Rice大學的一部分科學家正在試圖開發(fā)一種新的攝影裝 置（被稱為「單像素照相機」），爭取用盡量少的感光元件實現(xiàn)盡量高分辨率的 攝影。有的時候，第二個條件（也就是說有數(shù)學方法保證能夠從不完整的數(shù)據(jù)中 還原出信號）無法得到滿足。這種時候，實踐就走在了理論前面。人們已經(jīng)可以 在算法上事先很多數(shù)據(jù)重建的過程，但是相應的理論分析卻成為了留在數(shù)學家 面前的課題。 但是無論如何，壓縮感知所代表的基本思路：從盡量少的數(shù)據(jù)中提取盡量 多的信息，毫無疑問是一種有著極大理論和應用前景的想法。它是傳統(tǒng)信息論 的一

9、個延伸，但是又超越了傳統(tǒng)的壓縮理論，成為了一門嶄新的子分支。它從 誕生之日起到現(xiàn)在不過五年時間，其影響卻已經(jīng)席卷了大半個應用科學。 譯者：Armeny原文校對：擬南芥、剃刀、木遙 擴展閱讀：數(shù)字圖像的壓縮與恢復/奧卡姆剃刀 2009年早春，斯坦福大學露西爾?帕卡德兒童醫(yī)院的一組醫(yī)生把一名兩歲 男孩送進磁共振成像掃描儀。這個將被我稱為布賴斯的男孩身處巨洞般的金屬 儀器中，看上去是那么弱小無助。他被施以全身麻醉，一根彎彎曲曲的管子從 他的咽喉聯(lián)接到掃描儀傍的呼吸機上。十個月前，布賴斯接受了肝臟移植術(shù)， 來自捐獻者的部分肝臟取代了他自己的已壞死的肝臟。他的康復情況一度不錯。 但是，最近的實驗室

10、測試結(jié)果令人擔憂，他的身體出現(xiàn)了問題一可能一條或者 全部的兩條膽管被堵住了。 帕卡德醫(yī)院的兒童放射科醫(yī)生施里亞斯（校對者注：這個first name有多 種翻譯方法，請編輯注意）?瓦薩納瓦拉需要高精度的掃描結(jié)果來告訴他問題出 在哪，但是這將意味著他的小病人在掃描過程中不得不保持絕對靜止。哪怕布 賴斯只是呼吸了一次，成像結(jié)果都會變得模糊。要避免上述情況，就需要進行 足夠深的麻醉讓病人停止呼吸。進行一次標準的磁共振成像檢測需要兩分鐘時 間，但如果麻醉師真的讓布賴斯在這么長時間里停止呼吸，那么帶來的問題將 遠遠超過他肝臟的小毛病。 不過，瓦薩納瓦拉和他的電子工程師同事邁克爾?勒斯蒂格打算使用一種

11、 快得多的新掃描方法，名曰〃壓縮感知〃。這種技術(shù)可能是當今應用數(shù)學界最熱 門的話題了。未來，它可能會改變我們尋找遙遠星系的方式。而現(xiàn)在，這種技 術(shù)使得瓦薩納瓦拉和勒斯蒂格只需要40秒就可以采集到精確重建布賴斯肝臟圖 像所需的數(shù)據(jù)。 壓縮感知的發(fā)現(xiàn)純屬偶然。2004年2月，伊曼紐爾?坎迪斯正在自己的電 腦上看著Shepp-Logan圖像（譯注：這是醫(yī)學圖像處理領(lǐng)域用來進行仿真測試的 標準模擬圖像，由一些大大小小的橢圓模擬生物器官）打發(fā)時間。這幅通常被計 算機科學家和工程師用于測試成像算法的標準圖像，看起來就像《第三類接觸》 里那個搞笑地將眉毛揚起的外星人。坎迪斯，斯坦福大學教授，曾在加州理工

12、學院工作過，打算用一個嚴重失真的模型圖像作為磁共振成像儀不能精確掃描 而產(chǎn)生的非清晰圖像來進行實驗。他想到一種名為L1（校對注：這里雖然原文 用的是小寫，但是在中文上下文中用小寫則極易同11混淆，而數(shù)學上這里大小 寫都可以用）范數(shù)極小化的數(shù)學技術(shù)可能有助于清除小部分斑痕。他按下一個鍵， 算法運行起來了。 坎迪斯希望屏幕上的模型圖像變得稍微清晰一些。但是，他突然發(fā)現(xiàn)用殘 缺的數(shù)據(jù)渲染出來的圖像是那么細膩完美，對每個細節(jié)而言都是如此，這簡直 就像變魔術(shù)一樣。太不可思議了，他認為。〃這就好像，你給了我十位銀行賬號 的前三位，然后我能夠猜出接下來的七位數(shù)字?！ㄋf。他嘗試在不同類型的模 型圖像上重新

13、進行這個實驗，結(jié)果都非常好。 在博士后賈斯廷?龍伯格的幫助下，坎迪斯提出了一個粗略的理論。之后， 他在黑板上向加州大學洛杉磯分校的同事陶哲軒介紹了自己的理論?？驳纤乖?結(jié)束討論離開的時候覺得陶哲軒對此持懷疑態(tài)度，畢竟，圖像清晰度的提高也 太離譜了。然而，第二天晚上，陶哲軒給坎迪斯送去關(guān)于他們之前討論的問題 的一疊筆記。這疊筆記為他們共同發(fā)表的第一篇論文奠定了基礎(chǔ)。在隨后的兩 年中，他們寫了更多文章。 上面介紹的是壓縮感知技術(shù)的開端，這個數(shù)學界的全新領(lǐng)域改變了人們處 理大規(guī)模數(shù)據(jù)集的方式。僅僅六年時光，它為上千篇論文提供了靈感，吸引了 數(shù)百萬美元的聯(lián)邦基金。2006年，坎迪斯在這一領(lǐng)域內(nèi)的工

14、作為他贏得了獎金 值50萬美元的沃特曼獎，這是美國國家科學基金授予研究者的最高榮譽。其原 因是顯而易見的。想象一下，磁共振成像儀可以在幾秒鐘的時間里生成原本需 要花費一個小時才能生成的圖像；軍用軟件截獲敵方通信的能力得到極大加強; 傳感器能夠解析遙遠星際的無線電波。突然之間，數(shù)據(jù)的采集、操作以及解析 都變得容易了。 壓縮感知的原理是這樣的：你有一張圖片，假設(shè)是總統(tǒng)的腎臟圖片，這不 是關(guān)鍵。圖片由一百萬個像素構(gòu)成。對傳統(tǒng)成像來說，你不得不進行一百萬次 量度。而采用壓縮感知技術(shù)，你只需要量度一小部分，好比說從圖像的不同部 分隨機抽取十萬個像素。從這里開始，有大量的實際上是無窮多的方式填充那 剩余

15、的九十萬個像素點。 尋找那個唯一正確的表示方式的關(guān)鍵在于一種叫稀疏度的概念。所謂稀疏 度，是描述圖像的復雜性或者其中所缺的一種數(shù)學方法。一幅由少數(shù)幾個簡單、 可理解的元素（例如色塊或者波浪線構(gòu)成的圖片）是稀疏的；滿屏隨機、散亂的 點陣則不是稀疏的。原來在無限多的可能性中，最簡單、最稀疏的那幅圖像往 往就是正解，至少很接近正解。 但是，怎樣進行數(shù)字運算，才能快速獲得最稀疏的圖像呢?分析所有可能的 情況太費時間。然而，坎迪斯和陶哲軒知道最稀疏的圖像是用最少的成分構(gòu)成 的，并且，他們可以用L1范數(shù)極小化技術(shù)迅速找到它。 這樣，在輸入不完整的圖像后，算法開始試著用大色塊來填充空白區(qū)。如 果有一團

16、綠色的像素點聚集在一起，算法可能會用一個大的綠色矩形填充它們 之間的空間；而如果是一團黃色的像素點，那么就用黃色的矩形來填充。在不 同顏色交錯散布的區(qū)域，算法會使用越來越小的矩形或其他形狀填充各種顏色 之間的空間。算法會重復這樣的過程，最終，得到一幅由最少的可能的色塊構(gòu) 成的圖像，它的一百萬像素都已被彩色填滿。 并不能絕對保證這樣的圖像就是最稀疏的，或者正是你所試圖重建的那個。 但是坎迪斯和陶哲軒已經(jīng)從數(shù)學上證明了，它的錯誤率是無窮小的。算法運行 可能還是需要幾個小時，但是，讓電腦多跑一個小時，總好過讓孩子在額外的 一分鐘里停止呼吸。 壓縮感知已經(jīng)產(chǎn)生了令人驚嘆的科學影響。這是因為每一個

17、有趣的信號都 是稀疏的，只要你能夠正確定義它的稀疏性。例如，鋼琴和弦的樂音是一小組 不超過五個純音符的組合。在所演奏的音頻中，只有少部分頻率包含有效的音 樂信息，而其余大部分頻段是一片無聲地帶。因此，你可以用壓縮感知技術(shù)從〃 欠采樣〃的老舊唱片中重建出當時的樂章，而不用擔心失去了由特定頻率構(gòu)成的 聲波的信息。只需要你手頭的材料，就可以用L1范數(shù)極小化法以稀疏方式填補 空白，從而獲得與原音一般無二的旋律。 帶著建筑師式的眼睛，頂著略顯蓬松的頭發(fā)，坎迪斯散發(fā)著時尚極客的氣 息。這個39歲的法國人語氣溫和，但是面對他認為不達標的事情絕不妥協(xié)?！?不，不，他說的沒有道理?！ó斘姨岬綁嚎s感知領(lǐng)域某個和

18、他有些觀點有著細小 差別的專家的工作時，他如是說，〃不，不，不，不。那沒有道理，沒道理，是 錯的?！? 坎迪斯曾經(jīng)預見，將來會有大量應用技術(shù)是以他的研究成果作為理論基礎(chǔ) 的。他舉例說道，在未來，這項技術(shù)不會僅僅用在磁共振成像儀上。例如，數(shù) 碼相機收集了大量信息，然后壓縮圖像。但是，至少在壓縮感知技術(shù)可用的情 況下，壓縮是一種極大的浪費。如果你的相機記錄了大量的數(shù)據(jù)，卻在壓縮時 丟棄了其中的90%，那么為什么不在一開始就只記錄10%的數(shù)據(jù)從而節(jié)省電池電 量和內(nèi)存?對于您的孩子的數(shù)碼快照，費電可能沒什么大不了，你只要插上電源 為相機充電就可以了?！ǖ?，當廢電池多到可以環(huán)繞木星，〃坎迪斯說，〃結(jié)果

19、 就不是那么簡單了〃。同樣，如果你希望自己的相機能夠拍攝萬億像素的照片而 不是幾百萬像素，你就必須使用壓縮感知技術(shù)。 從信息的小樣本中收集有用數(shù)據(jù)的能力也引起了軍方的重視：比如，敵方 通信可能從一個頻率跳到另一個頻率。但是，還沒有一種硬件設(shè)備能以足夠快 的速度掃描整個頻域。但是無論在什么情況下，對手的信號都是稀疏的，是由 頻段內(nèi)極少數(shù)的某種簡單信號構(gòu)成的，出現(xiàn)在一些相對較小卻未知的頻段。這 意味著壓縮感知可以用來從〃噼?！曋袇^(qū)分來自任意波段的敵人的交談。所以 不出意外的，美國國防部先進計劃研究署正在支持壓縮感知技術(shù)的研究。 壓縮感知不僅可以用于解決現(xiàn)在的技術(shù)難題。將來，它還將幫助我們處理

20、 已存儲的大量信息。每天，全世界都要產(chǎn)生數(shù)不清的數(shù)據(jù)，我們希望這些數(shù)據(jù) 安全、有效、可恢復地保存起來。目前，我們大部分的視聽信息都是用復雜的 壓縮格式存儲起來的。如果有一天，這種格式被淘汰了，你不得不進行痛苦的 格式轉(zhuǎn)換。但是坎迪斯相信，在擁有壓縮感知技術(shù)的未來，對于采用高成本紅 外技術(shù)拍攝的天文圖像，只需要拍攝到20%的像素就可以了。因為我們一開始 就只記錄了極少部分的數(shù)據(jù)，所以不需要再進行壓縮。那么我們只需要逐步改 進數(shù)據(jù)的解析算法，而不是數(shù)據(jù)的壓縮算法，就可以精確地恢復出原始圖像了。 上面說的都是將來的事情。今天，壓縮感知技術(shù)已經(jīng)改寫了我們獲取醫(yī)學 信息的方式。在GE醫(yī)療集團的參與下，

21、威斯康辛大學的一個研究小組正在把壓 縮感知技術(shù)與HYPR和VIPR技術(shù)結(jié)合，以提高特定種類磁共振掃描的速度，在 某種情況下可以達到原來的幾千倍。（我是這所大學的教員，但是沒有參與這項 研究。）GE醫(yī)療集團還在實驗一種新的方法，有希望利用壓縮感知技術(shù)大大改 善對癌癥病人代謝動力學的觀測。同時，帕卡德醫(yī)院應用了壓縮感知技術(shù)，使 磁共振成像儀的圖像記錄速度提升為傳統(tǒng)掃描儀的三倍。 這對于兩歲的布賴斯來說恰好夠用。瓦薩納瓦拉在控制室發(fā)出工作信號， 麻醉師給男孩注射了一點鎮(zhèn)靜劑，然后關(guān)掉了呼吸機。男孩的呼吸立刻停止了。 瓦薩納瓦拉開始掃描，而麻醉師監(jiān)視著布賴斯的心率和血氧水平。40秒鐘之后， 掃描結(jié)束

22、，布賴斯沒有出現(xiàn)明顯的缺氧情況。當天晚些時候，壓縮感知算法從 粗略的掃描中生成了清晰的圖像，能讓瓦薩納瓦拉看清雙側(cè)膽管的堵塞情況。 一名介入放射科醫(yī)生將一根彎曲的導線依次插入雙側(cè)膽管中，輕輕清除淤塞， 并為男孩安裝了讓膽汁恰當流出的細小導管。正是數(shù)學與醫(yī)學的結(jié)合，才使得 布賴斯的檢測結(jié)果又恢復了正常。 原文作者: Jordan Ellenberg(ellenber@math.wisc.edu),是威斯康辛大學的數(shù)學副教 授。原文發(fā)表在《連線》雜志三月號上。 數(shù)學怎樣得出那些顆粒：壓縮感知技術(shù)是一種從低分辨率樣本中重建高精 度數(shù)據(jù)的數(shù)學工具。它可以用來重現(xiàn)古老的音樂錄音、尋找敵人的無線電信

23、號， 并更加迅速地完成磁共振成像。這里展示的是它如何處理照片。 堅持用'磁共振'的原因：1)MRI直譯就是磁共振成像；2)現(xiàn)代人談'核'色 變，而傳統(tǒng)'核磁共振’中的'核'其實指的是原子核。因為'核磁共振'這個名字 讓我們在招募fMRI實驗被試時困難重重…趕明兒打算寫個磁共振成像原理給大 家做科普，希望以后招被試容易些… 補充閱讀： 曾更生，《醫(yī)學圖像重建》，6.10節(jié)，〃利用l0極小化來重建極度欠采樣 數(shù)據(jù)〃 Trzasko J,Manduca A.Highly undersampled magnetic resonance image reconstruction via homotopic l0-minimization.IEEE Trans Med Imaging,2009,28： 106-121 Yu H,Wang G.Compressed sensing based interior tomography.Phys Med Biol,2009,54： 2791-2805 特別聲明： I ：資料來源于互聯(lián)網(wǎng)，版權(quán)歸屬原作者 2：資料內(nèi)容屬于網(wǎng)絡(luò)意見，與本賬號立場無關(guān) 3：如有侵權(quán)，請告知，立即刪除。