【ELT.ZIP】OpenHarmony啃論文俱樂部——輕翻那些永垂不朽的詩篇

語言: CN / TW / HK
  • 本文出自ELT.ZIP團隊,ELT<=>Elite(精英),.ZIP為壓縮格式,ELT.ZIP即壓縮精英。
  • 成員:
    • 上海工程技術大學大二在校生
    • 合肥師範學院大二在校生
    • 清華大學大二在校生
    • 成都資訊工程大學大一在校生
    • 黑龍江大學大一在校生
    • 山東大學大三在校生
  • 我們是來自6個地方的同學,我們在OpenHarmony成長計劃啃論文俱樂部裡,與華為、軟通動力、潤和軟體、拓維資訊、深開鴻等公司一起,學習和研究作業系統技術...

@[toc]

【往期回顧】

 2月23日 《老子到此一遊系列》之 老子為什麼是老子 —— 綜述視角解讀壓縮編碼 3月11日 《老子到此一遊系列》之 老子帶你看懂這些風景 —— 多維探祕通用無失真壓縮

【本期看點】

主題:《老子到此一遊系列》之 老子見證的滄海桑田

  • 塞繆爾·莫爾斯發明摩斯mi碼開創編碼領域先河
  • 夏農提出資訊熵,用數學語言闡明瞭概率與資訊冗餘度的關係
  • 用生活中的烹飪視角解析Huffman編碼過程
  • 小波係數的各類編碼方案大比拼
  • 計算機視覺中的女神 —— Lenna
  • 當代無線感測器型網路資料壓縮

【技術DNA】

the-history-of-data-compression_546d4087a9105_w1500

【智慧場景】

【脈動一下】

20220324152636.gif


資料壓縮理論緣起

起源

  • 資料壓縮概念的演變源於摩爾斯電碼,也即我們日常所說的摩斯mi碼(SOS就是其中一種),它是一種時通時斷的訊號程式碼,通過不同的排列順序來表達不同的英文字母、數字和標點符號,從而最小化訊息的大小和傳輸時間。由電報之父塞繆爾·莫爾斯於1837年發明,1838年正式用於壓縮電報中的信件image.png

發展

  • 1986年Richard W. Hamming編寫出版的《Coding and information theory》一書中提到:++編碼和資訊理論的概念起源久遠,但在資訊理論還未建立起一個堅實的基礎之時,人們對其的許多基礎性想法與理解其實都只停留在1948年之前。++image.png
  • 說到資訊理論,不得不提到一個人 —— Claude E. Shannon(克勞德·艾爾伍德·夏農)。夏農是美國數學家,也是資訊理論的創始人,他提出了資訊熵的概念,為資訊理論和數字通訊的發展奠定了基礎。從本質上講,資料壓縮的目的就是要消除資訊中的冗餘,而資訊熵及相關的定理恰恰用數學手段精確地描述了資訊冗餘的程度。利用資訊熵公式,人們可以計算出資訊編碼的極限,即在一定的概率模型下,無失真壓縮的編碼長度不可能小於資訊熵公式給出的結果。 於是後來,上述形勢被1948年夏農發表的兩篇名為《通訊的數學原理》的文章所打破,它們在資訊理論領域幾乎迅速地傳播並流行了起來。很快,另外一些資訊理論的文章出現在了相關期刊上,許多大學的電氣工程等相關部門也開始教授相關課程。

但由於資訊理論在當時是一個新領域,人們對其能做的事情以及能應用的方向還沒有一個確切的認識,漸漸地,人們對其的關注度愈發降低,相關課程的教授也隨之減少。

轉折

  • 資訊理論具有廣泛適用於遠離其原始靈感的情況的想法。好巧不巧的是,在資訊理論被創立的左右之時,編碼理論也誕生了。就編碼理論而言,其數學背景在一開始遠沒有資訊理論那麼複雜,而且在很長一段時間裡,它也沒有得到理論界的重視。但是,隨著時間的推移,各種數學工具如群論、有限域理論等慢慢被應用到編碼理論中。現在,編碼理論已成為數學研究中一個活躍的部分

從邏輯上講,編碼理論引出了資訊理論,資訊理論提供了對資訊進行適當編碼所能做的操作的界限。因此,這兩種理論是密切相關的。

  • 1948 年,夏農在提出資訊熵理論的同時,也給出了一種簡單的編碼方法—— Shannon 編碼,為壓縮演算法領域的發展奠定了專屬基調。 1952 年, R. M. Fano 又進一步提出了 Fano 編碼。這些早期的編碼方法揭示了變長編碼的基本規律,也確實可以取得一定的壓縮效果,但離真正實用的壓縮演算法還相去甚遠第一個實用的編碼方法是由 D. A. Huffman 在 1952 年的論文《最小冗餘度程式碼的構造方法( A Method for the Construction of Minimum Redundancy Codes )》中提出的。直到今天,許多《資料結構》教材在討論二叉樹時仍要提及這種被後人稱為 Huffman 編碼的方法。 Huffman 編碼在計算機界是如此著名,以至於連編碼的發明過程本身也成了人們津津樂道的話題。據說, 1952 年時,年輕的 Huffman 還是麻省理工學院的一名學生,他為了向老師證明自己可以不參加某門功課的期末考試,才設計了這個看似簡單,但卻影響深遠的編碼方法。 Huffman 編碼效率高,運算速度快,實現方式靈活,從 20 世紀 60 年代至今,在資料壓縮領域得到了廣泛的應用。例如,早期 UNIX 系統上一個不太為現代人熟知的壓縮程式 COMPACT 實際就是 Huffman 0 階自適應編碼的具體實現。 20 世紀 80 年代初, Huffman 編碼又出現在 CP/M 和 DOS 系統中,其代表程式叫 SQ 。今天,在許多知名的壓縮工具和壓縮演算法(如 WinRAR 、 gzip 和 JPEG )裡,都有 Huffman 編碼的身影。不過, Huffman 編碼所得的編碼長度只是對資訊熵計算結果的一種近似,還無法真正逼近資訊熵的極限。正因為如此,現代壓縮技術通常只將 Huffman 視作最終的編碼手段,而非資料壓縮演算法的全部。

Huffman碼

  • 說到哈夫曼編碼或是霍夫曼編碼,熱愛自然科學、關注電腦科學的朋友們,或許曾聽過、研究過;若是第一次聽聞,或許會有一種像聽到相對論、量子力學等一般的緊張感,請不必擔心,我們接下來以一種老少皆宜、通俗有趣的方式傳播分享,通讀一遍說不定也能收穫滿滿,接下來讓我們進入正題吧:
  • 先來感性地認識一下霍夫曼編碼,首先顧名思義,我們可以明確一個大前提,這是霍夫曼的作品,其次這是一種編碼技術。技術是用來解決問題的,那霍夫曼編碼是用來解決什麼問題的呢?——資訊壓縮問題。
  • 現在大家心中已經對霍夫曼編碼建立起了一個最基本的概念,這是由霍夫曼創立的用於解決資訊壓縮問題的編碼技術。但這個概念還是太籠統了,再詳盡一些是什麼樣子的呢?(別緊張,接下來你不會看到滿屏的數學公式)。
  • 我們用烹飪來舉個例子,大家或許做過,或者看別人做過飯,做飯首先就得明確目標,就是我要做什麼菜,對於霍夫曼編碼來說就是目標壓縮文字是什麼,然後你就得列個清單看看做這道菜需要哪些原材料,各種要多少;對於霍夫曼編碼來說就是一個統計構成文字的元素的種類和出現頻率的過程;料備齊了就要掌握如何搭配,以及掌握火候,這就是考驗一個人的廚藝的時候了;對於霍夫曼編碼來說就是建立一個高效的字典樹的過程。這一套流程下來我們可以獲得一個菜的菜譜,這就是一個成品菜的壓縮成果;對於霍夫曼來說我們就獲得了一個文字的字典樹: 20220324231949.png

線上體驗霍夫曼編碼生成過程: huffman.ooz.ie - Online Huffman Tree Generator (with frequency!)

現代場景

1. 漢字字形壓縮

  • 通俗些說就是把我們的中文文字進行識別和壓縮,這與英文文字有什麼不同呢?中華文化博大精深,不像英文文字只有26個字母和一些標點符號,漢字千變萬化,無法通過傳統的方式統計編碼。但是萬變不離其宗,我們從小寫字就知道一點,我們的漢字是由筆劃再按照一定筆順寫成的,那麼這時筆劃也就是我們前面所說的原材料模板:

而筆順就是我們建立字典的依據,我們的漢字通過這樣的處理就可以通過霍夫曼編碼進行壓縮編碼了。

2. 3D網格的編碼壓縮

  • 說到3D網格大家腦海中最先會聯想到的可能會是3D動畫,沒錯這一項技術廣泛的應用於這一領域,下面一些圖片可供直觀感受:

那麼如何讓這些精美的3D作品高效的壓縮儲存呢?霍夫曼編碼大顯身手的時侯 到了,下面介紹相關場景並補充一項3D網格幾何壓縮的強大演算法。

【征服三角形】

  • 對未征服也就是未編碼之處圍繞其邊界插入三角形,進行擬合重構

  • 其中箭頭和數字給出了三角形征服的順序。三角形中填滿了不同圖案來代表不同的操作碼,當它們被征服時就會生成這些操作碼,再通過霍夫曼進行處理

【kD-tree分解(強大的3D影象處理演算法)】

  • 該方案特別適用於地形模型和密集取樣物件

  • 為便於理解我們用2D來表述

  • 每次將一個單元格細分為兩個小單元格,對頂點數量進行編碼。這種細 分被重複地應用,直到每個單元格足夠小,可以只包含一個頂點,並能夠足夠精確地重建頂點位置。

動態Huffman碼的設計

  • 動態哈夫曼編碼(Dynamic Huffman coding),又稱適應性哈夫曼編碼(Adaptive Huffman coding),是基於哈夫曼編碼的自適應編碼技術。它允許在符號正在傳輸時構建程式碼,允許一次編碼並適應資料中變化的條件,即隨著資料流的到達,動態地收集和更新符號的概率(頻率)。一遍掃描的好處是使得源程式可以實時編碼,但由於單個丟失會損壞整個程式碼,因此它對傳輸錯誤更加敏感

摘要

  • 文章介紹並分析了一種構造動態Huffman碼單遍演算法,同時還分析了由 Faller、Gallager和Knuth 三位學者得到的單遍演算法。在每個演算法中,傳送器和接收器都保持等效的動態變化 Huffman 樹,並對其進行實時編碼。他們證明了新演算法編碼包含 t 個字母的訊息所佔用的bit數小於t,遠遠優於傳統的兩遍 Huffman 方案,並且與字母表的大小沒有關係。對於任何一種單遍 Huffman 演算法來說,這是在最壞狀態下能做到的最佳可能情況。實驗表明,新演算法生成的編碼長度比其他單遍演算法的短,除了長訊息外,也比兩遍演算法的短。最後明確了該演算法適用於資料網路的線上編/解碼和檔案壓縮場景

介紹

  • 由於傳統的靜態 Huffman 演算法存在一個缺點,即它需要對資料進行兩次遍歷:第一次是通過構造和傳輸 Huffman 樹到接收器,來收集訊息中字母出現的頻率計數;然後第二次再基於第一次構造的靜態樹結構,來編碼和傳輸訊息本身。那麼,這會導致在將其用於網路通訊時產生延遲,或者在檔案壓縮應用程式中產生額外的磁碟訪問從而減慢演算法。所以,Faller 和 Gallager兩人各提出了一種一次遍歷方案,後來被 Knuth 大大改進,以構造動態 Huffman 編碼。傳送器用來編碼訊息中第 t + 1 個字母的二叉樹(同時也是接收器用來重建第 t + 1 個字母的二叉樹)是訊息前 t 個字母的二叉樹。這樣的話,傳送器和接收器就都會從相同的初始樹開始,傳送器永遠不需要將樹傳送給接收器。很顯然,這與兩次遍歷演算法的情況不同。
  • 隨後,研究者設計並證明了一個所有單遍Huffman方案中,在最壞情況下表現仍然是最優的演算法A,它可以用於網路通訊的通用編碼方案,也可以作為基於文字的壓縮演算法中的一種高效子例程

實驗結論

演算法A的優點:

  1. 對於編碼效率差異相對較大的小訊息,每個字母佔用更少的位
  2. 在 t 小於10^4^時,相比所有兩遍演算法都表現得更好
  3. 能夠對訊息進行實時編碼解碼,每個字母使用不到一個額外的位元位對訊息進行編碼
  4. 在檔案壓縮、網路通訊和硬體實現方面有很大的應用潛力
  5. 可用來增強其他壓縮方案

小波係數影象壓縮編碼

引言

  • 由於多媒體資訊和數字化的影象表示形式所帶來的網路流量的不斷增加,影象壓縮已經成為一種剛需。基於小波的影象壓縮新演算法被開發出來,這些方法取得了實際性進展,如:卓越的低位元率效能、連續音調和位元級壓縮、無損和有失真壓縮、逐畫素、精度和解析度傳輸等。小波演算法最成功的應用之一是基於變換的影象壓縮,其重疊特性減輕了塊效應(馬賽克被放大的場景);而小波分解的多解析度特性又使解壓後的影象具有更好的感知質量。前期相關文章已經涉及到小波變換的部分內容,這裡再繼續對其展開詳細描述。

基本原理

  • 大多數影象的共同特徵是相鄰畫素是相關的,所以便包含了很多冗餘資訊。然後,最重要的任務是找到影象中不太相關的表示。壓縮的兩個基本元件就是冗餘和無關性的減少
    • 冗餘減少的目的是消除訊號源(影象/視訊)的重複
    • 無相性的減少則是忽略了訊號接收器即人類視覺系統(HVS)通常不會注意到的部分訊號
  • 另外,通常也有三種類型的冗餘:
    • 相鄰元素之間的空間冗餘或相關性
    • 不同顏色平面或光譜帶之間的光譜冗餘或相關性
    • 影象序列相鄰幀之間的時間冗餘或相關性(主要就是視訊應用)

因此,影象壓縮的目標就是希望儘可能地去除空間和光譜冗餘以減少表示影象所需的位元位數。其次,影象壓縮還需保證一個基本目標:降低傳輸或儲存位元率的同時保持可接受的保真度或影象質量。

高低頻分離&&量化

  • 大多數自然影象都有平滑的顏色變化,在平滑變化之間,精細的細節被表示為尖銳邊緣。從技術上講,顏色的平滑變化被稱為低頻變化,尖銳變化被稱為高頻變化。低頻成分構成了影象的基礎,高頻成分則是為了細化影象。因此,基礎比細節相對更重要。類似的,我們在聲樂領域也能找到相對應的概念 —— 基音與泛音,基音是波形裡振幅最大,頻率最小的組成波,它決定了音高;而泛音頻率是基音的整數倍,跟基音疊加在一起後整體波形仍是基音的頻率,但加入泛音組成後波形的形態不再單純,可以理解為對基音作了一定的修飾,即決定了音色。
  • 分離多數採用離散小波變換(DWT),通過濾波器組對影象進行一系列類似金字塔型的操作。基於小波的編碼在傳輸和解碼錯誤下具有更強的魯棒性,有利於影象的漸進傳輸。此外,它們也更符合人類視覺系統的特點。
  • 量化,是指用有限的、較小的值集逼近影象資料中連續的值集的過程。有兩種型別的量化,分別是標量量化和向量量化

度量指標

  • 兩類用於比較各種影象壓縮技術的指標是均方誤差(MSE)和峰值信噪比(PSNR),MSE值越小,誤差越小;PSNR值越大,信噪比越高,其中,“訊號”是原始影象,“噪聲”是重建時的誤差。因此,具有較低MSE和較高PSNR的壓縮方案可被認為是較好的壓縮方案。

小波係數的各類編碼方案

嵌入式零樹小波編碼(EZW)

  • EZW是最早展現基於小波影象壓縮的全部能力的演算法之一,其編碼器基於漸進式編碼,將影象壓縮成一個bit流。因為漸進編碼又叫做嵌入式編碼,所以即EZW中的E。下面是EZW演算法對大小為512 × 512影象的壓縮比和PSNR值的結果:

下一個方案稱為 SPIHT,是 EZW 的一種改進形式,比 EZW 有著更好的壓縮效能。

多級樹集合分裂編碼(SPIHT)

  • SPIHT編碼器是EZW編碼的一個高度精細化版本,同樣可產生嵌入的bit流。對於各類影象,SPIHT可獲得最佳結果 —— 給定壓縮比下,PSNR值最高。所以,它是影象壓縮中最先進的基準演算法。SPIHT不是傳統影象壓縮演算法的簡單擴充套件,它代表了該領域的一個里程碑式進展,具有以下性質:
  1. 影象質量好,PSNR值高,尤其對於彩色影象
  2. 是優化好的漸進式影象傳輸
  3. 生成一個完全嵌入的編碼檔案
  4. 簡單量化演算法
  5. 快速編/解碼(幾乎對稱分佈)
  6. 應用範圍廣、適應性強
  7. 可用於無失真壓縮
  8. 可以編碼到精確的位元率或失真
  9. 高效結合誤差保護

SPIHT可以通過對輸出資訊進行熵編碼來提高效率,但代價是增加了編/解碼的時間。同時為了減少此方案中使用的列表數量,需要形成下一個演算法,稱為 SPECK。

設定分割槽嵌入式塊編碼(SPECK)

  • SPECK不同於上述的一些方案,它不使用跨越不同子帶的樹,而是以塊的形式使用集合。主要思想是利用變換後的影象層次結構中頻率和空間能力的聚類,根源還是SPIHT中發展出來的思想。

特點:

  • SPECK具有標量量化顯著性測試方案的全部特性:

    1. 是完全嵌入的 —— 為了實現最好的重建效果,一個編碼的位元流可用來解碼任何速率小於等於編碼速率的影象
    2. 採用遞進傳輸源樣本按其資訊內容的降序編碼
    3. 計算複雜度低 —— 演算法非常簡單,主要是比較,不需要任何複雜的計算
    4. 較低的動態記憶體需求 —— 在編碼過程中的任何給定時間,只有一個連線區域(完全位於子帶內)被處理
    5. 快速的編/解碼 —— 這是由於演算法的低複雜度,對應了第3點
    6. 高效的效能 —— 其效率可與目前可用的其他低複雜度演算法相媲美
  • 解碼器使用與編碼器相同的機制。它接收編碼位流的顯著性測試結果,並在演算法執行過程中建立相同的列表結構。因此,對於不同集合的顯著性測試,它能夠遵循相同的執行路徑,並隨著演算法的進行逐步重建影象。可以看出,SPECK 具有更高的壓縮比。這顯示了以塊的形式處理集比空間方向樹的形式處理集的優勢。與 SPIHT 相比,對於相同的分解級別和丟棄的位平面,這些壓縮比下的重建影象具有可觀的解析度

結論: 在分解層次較少的情況下,SPECK重建影象的解析度即清晰度優於 SPIHT。

優化截斷的嵌入式塊編碼(EBCOT)

  • EBCOT 將每個子帶劃分為相對較小的樣本塊,並生成一個獨立的高度可伸縮的位元流來表示每個所謂的程式碼塊。該演算法展示了最先進的壓縮效能,同時產生一個前所未有的特徵集的位元流,包括解析度和信噪比可伸縮性以及隨機訪問屬性。該演算法具有適度的複雜性,非常適合於涉及遠端瀏覽大型壓縮影象的應用

  • 可見,在最先進的壓縮演算法方面,EBCOT顯著優於SPIHT。

其他

  • 此外,還有許多小波係數相關衍生編碼技術,如小波差約簡(WDR)、自適應掃描小波差約簡(ASWDR)、空頻量化(SFQ)、嵌入式預測小波影象(EPWIC)、可逆嵌入小波壓縮(CREW)、堆疊執行(SR)等,這裡不再一一贅述,各種編碼技術的優缺點詳見下表:
型別 特性 不足
EZW 採用漸進和嵌入式傳輸 / 使用零樹概念 / 用單個符號編碼樹 / 使用預定義的掃描順序 / 良好的結果反饋 係數位置的傳輸丟失 / 沒有真正壓縮 / 依賴於算數編碼器
SPIHT 廣泛使用 —— 對於各類影象都有較高PSNR值 / 四叉樹或層次樹被設定為分割槽樹 / 採用空間定向樹狀結構 / 通過三個列表跟蹤索引集的狀態:LSP、LIS、LIP / 採用漸進和嵌入式傳輸 / 在感知影象質量和PSNR值上優於JPEG 僅隱式定位有效係數的位置 / 由於三個列表致使記憶體需求更多 / 傳輸資訊只由單個bit組成 / 適合各種自然影象 / 感知質量不是最優的
SPECK 不使用樹 / 使用矩形塊區域 / 利用頻率和空間的能量聚集 / 採用漸進和嵌入式傳輸 / 低計算複雜度 / 採用四叉樹和倍頻帶劃分 / 由於兩個列表致使記憶體需求低 / PSNR值優於SPIHT
EBCOT 支援資料包分解 / 基於塊的方案 / 適度複雜性 / 位元流由質量層集合組成 / 信噪比具備可伸縮性 / 出色的紋理表現 / 保留SPIHT中丟失的邊 效能隨層數的增加而降低 / 適合遠端瀏覽大型壓縮影象
WDR 採用ROI概念 / 對重要小波變換值的位置進行編碼 / 感知影象質量相比SPIHT更好 / 不用像SPIHT那樣在四叉樹中搜索 / 適合低位元率的低解析度醫學影象 / 低複雜度 / 高邊緣相關性 / 高邊緣保護性 PSNR值沒有SPIHT高
ASWDR 與WDR相比更改了掃描順序 / 可預測新關鍵值的位置 / 動態適應邊緣細節的位置 / 相比WDR能編碼更多關鍵值 / PSNR值優於SPIHT和WDR / 感知影象質量優於SPIHT、略優於WDR / 邊緣相關性略優於WDR / 保留更多細節 / 適合如偵察或醫療類的高壓縮率影象
SFQ 其量化模式直接利用了高頻係數的空間聚類 / 均勻量化+熵編碼提供了幾乎最優的效率
CREW 適合於需要高質量的靈活性應用如醫療影象、固定速率大小的程式(ATM)、印前影象、連續色調傳真、影象檔案、全球資訊網影象、衛xing影象等
SR 通過光柵掃描工作從而定址複雜度相比其他演算法較低

第二代圖片壓縮技術

引言

  • 在硬體受限的環境下,在視覺感測器節點中實現影象處理引擎一直是無線多媒體感測器網路發展的主要關注點。文章對8種常用的影象壓縮技術進行了綜述。綜合評估後發現,基於層次樹集分塊(Set-Partitioning in Hierarchical tree, SPIHT)小波的影象壓縮演算法壓縮效率高,編碼過程簡單,是無線感測器網路中最適合硬體實現的影象壓縮演算法。

無線感測器網路(WSN)圖片壓縮

  • 無線感測器網路(Wireless sensor network, WSN)是由多個感測器裝置通過無線資訊進行通訊的網路,具有在感測器節點上進行資料處理和計算的能力。近年來,人們對可靠、高效的無線多媒體感測器網路(Wireless multimedia sensor network, WMSN)研究和開發越來越感興趣。從攝像機節點收集的影象和視訊幀等多媒體資料需要大量的處理,這使得WMSN的實現非常困難,特別是在硬體受限的環境中。高功耗、有限頻寬和記憶體限制是影響高效靈活WMSN開發的挑戰和制約因素。
  • 多媒體內容,特別是高解析度的影象需要廣泛的頻寬傳輸。由於可用頻寬有限,感測器節點捕獲的影象在傳輸前需要進行處理和壓縮。通過影象壓縮去除原始資料中的冗餘資訊,可以獲得一種更高效的傳輸方法。
  • 最近的技術使得具有嵌入式處理能力的微型感測裝置的生產成為可能。由於空間限制和提供大量記憶體儲存的高成本,片上記憶體受到限制,併成為處理大型影象的另一個主要約束。因此,需要開發一種更簡單、更經濟的系統,以滿足影象處理中的高記憶體儲存需求。

影象壓縮演算法

  • 利用影象中相鄰畫素高度相關這一事實,我們可以通過尋找相關度較低的影象表示來丟棄這些冗餘的資訊,這是影象壓縮演算法背後的基本理論。下圖展示影象編碼過程的基本組成,影象編碼過程分為兩個階段,影象變換階段和熵編碼階段

影象編碼可分為第一代和第二代:

  • 第一代影象編碼更強調如何有效地編碼轉換後的影象所包含的資訊

  • 第二代影象編碼更重視如何從影象中挖掘和提取有用的資訊

  • 文章在第一代編碼中介紹了四種最流行的基於變換的影象壓縮演算法——JPEG、EZW、SPIHT和EBCOT,其中EZW、SPIHT和EBCOT在上一部分“小波係數影象壓縮編碼”中已經做了詳細的介紹,在此不再展開。

  • 著名的影象壓縮標準JPEG使用了基於離散餘弦變換(DCT)的影象壓縮技術,將影象分為多個8 x 8畫素的子影象塊,並對每個影象塊獨立編碼。DCT不對原始資料造成損失,經過離散餘弦變換後,每個64DCT係數被均勻量化。然後在8 x 8影象塊中採用鋸齒狀掃描重新排列係數。下圖顯示了鋸齒狀掃描的過程:

基於DCT的影象壓縮提供了令人滿意的壓縮效率,並且由於編碼是在小的單個影象塊上完成的,實現時所需的記憶體很低。然而,影象塊的平鋪會導致阻塞工件,從而導致效能下降。

第二代影象編碼

金字塔/多解析度編碼(Pyramidal/multiresolution coding)

  • 金字塔編碼在影象發展的早期階段就已經被引入,但是由於分層編碼的方式與人類視覺系統** (Human Visual Syatem, HVS) 中的神經系統類似,所以將其歸為第二代影象編碼**。
  • 通過使用適當的平滑濾鏡對影象進行平滑處理,然後對平滑影象進行子取樣(通常沿每個座標方向按 2 倍)來生成低通金字塔。然後,對生成的影象進行相同的過程,並重復多次迴圈。此過程的每個週期都會導致影象變小,平滑度增加,但空間取樣密度降低(即影象解析度降低)。如果以圖形方式進行說明,則整個多尺度表示將看起來像一個金字塔,原始影象位於底部,每個週期生成的較小影象將一個堆疊在另一個之上:

上圖是金字塔編碼的形象化表示。

上圖為金字塔編碼的例項,其中各圖分別表示:

  1. 原始影象“Lenna”
  2. 高斯金字塔影象
  3. 高斯插值影象
  4. 拉普拉斯金字塔影象
  • 高斯核和拉普拉斯核是兩種對影象進行平滑處理的核函式。拉普拉斯金字塔演算法基於空間頻率將影象分解為多個分量,金字塔中每個節點的值代表兩類高斯函式與原始影象卷積的差值(平滑處理)。

基於方向分解的編碼(Directional decomposition based coding)

  • 從對HVS本質的研究和分析中發現,邊緣資訊在影象的感知中至關重要。然而採用傳統的變換編碼、子帶編碼和小波編碼等編碼方法對影象進行編碼時,這些資訊往往會發生畸變。定向濾波編碼更強調邊緣檢測,以實現高壓縮比。它基於人眼是由對方向敏感的神經元組成的事實,一個方向濾波器用於利用邊緣之間的關係及其對影象光譜的貢獻。該濾波器被定義為“沿主方向進行高通濾波,沿正交方向進行低通濾波的濾波器”
  • 在方向濾波過程中,將原始影象分解為一副低通影象和若干幅高通影象。每個高通影象都包含一個主方向的邊緣資訊,因此影象中的邊緣資訊得到很好的儲存(相比於之前提到的傳統的變換編碼、子帶編碼和小波編碼等編碼方法)。低通影象不包含邊緣資訊,可以採用變換編碼,而高通影象採用邊緣檢測和編碼

基於分割的編碼(Segmentation based coding)

  • 與基於方向分解的編碼類似,該編碼利用了人眼善於識別相似區域並將其分組為事實,根據影象的紋理結構將影象劃分為子區域。這些子區域被輪廓包圍,輪廓和紋理區域將分別進行編碼。下圖展示了基於分割的編碼過程:
  1. 基於對HVS的特徵和分析,首先對影象進行預處理,去除噪聲和無用區域。
  2. 在分割的過程中,採用一種基於區域增長的編碼方法,每個畫素和它的相鄰畫素根據灰度級別來判斷它們是否共享相同的屬性。重複這個區域增長過程,直到所有的畫素都被分配某個區域,這樣會得到很多子區域。為了減少區域數,降低編碼複雜度,會將弱對比即相比差距不大的相鄰區域和小區域進行合併
  3. 最後進分別對輪廓區域和紋理區域進行輪廓編碼和紋理編碼。

向量量化(Vector quantization)

  • 向量量化,顧名思義就是利用矢量表示影象。利用向量量化對影象編碼時,首先將高度相關的畫素分組為樣本集的塊,每一個塊都可以找到一個最佳的近似向量來表示給定區域中的每個畫素。對這些畫素塊進行量化,然後每個塊獨立編碼,基於這個過程,向量量化又被稱為塊量化或者模式匹配量化。下圖為向量量化編碼的框圖:

  • 編碼

  1. 影象預處理,將影象分割成畫素塊
  2. 為每個畫素塊找到一個表示向量k
  3. 將向量k與查詢表(碼本)中預定義的向量集(碼字)進行比較,選擇最匹配的碼字
  4. 為了獲得更高的壓縮比,傳輸的是碼字的索引而不是碼字本身,索引比碼字本身佔用的位數更少。
  • 解碼
  1. 根據接收到的索引值從碼本中選取碼字
  2. 利用碼字重構影象
  • 從向量量化編碼的過程中我們可以看到,每幅圖片可以劃分成各種各樣的子區域,這些子區域對應的向量是非常多的,將大量的向量編碼成碼本中有限的碼字,會造成資料的損失,因此向量量化提供了有失真壓縮。

觀察和總結

表:第一代和第二代影象壓縮演算法分析總結

分析與對比

  • 上表總結了八種影象壓縮演算法的特性和特點,並且選擇SPIHT為最適合在無線感測器網路中實現的影象壓縮演算法。選擇的標準是所選演算法應具備執行在硬體受限的環境下的WSN的大多數首選特徵,包括快速高效的影象處理能力、低記憶體需求、高壓縮質量、低系統複雜度和低計算負載
  • 除此之外,我們還可以得出:
  1. 第一代影象壓縮演算法是利用影象畫素之間的相似性來消除影象中的冗餘,而第二代影象壓縮演算法結合了HSV的特性,識別影象中的特徵,並對這些特徵進行處理。第二代影象編碼強調探索影象的“內容”,與第一代進行小波變換的影象編碼相比,這一特性需要更復雜和更廣泛的影象處理。
  2. 大多數第二代影象壓縮演算法提供有失真壓縮,它們依賴於初始的分割。在分割過程中,首先將影象畫素劃分為輪廓區域和紋理區域,然後進行區域增長過程。整個影象的預處理過程被儲存在記憶體中,在WSN節點中是很難實現的。此外,分割時所需的大量的計算增加編碼器的複雜性並且降低了處理速度,使其在實時環境中不可能實現。

計算機視覺中的女神 —— Lenna

在數字影象處理中,Lena(Lenna)是一張被廣泛使用的標準圖片,特別在影象壓縮的演算法研究中。

  • 萊娜·瑟德貝里(瑞典文:Lena Soderberg),1951年3月31日出生於瑞典,在1972年11月期的《花花公子》雜誌中,她化名為萊娜·舍布洛姆,成為了當期的玩伴女郎。她的中間摺頁照片由Dwight Hooker拍攝。她的照片(即萊娜圖)後來被數字影象處理領域所廣泛使用。1997年,在影象科學和技術協會(英語:Society for Imaging Science and Technology)的第50屆會議上,她被邀為貴賓出席。在會議上,她忙於簽名、拍照以及介紹自我。 熟悉影象處理或者壓縮的工程師、研究人員和學生經常在他們的實驗或者專案任務裡使用“Lenna”或者“Lena”的影象。Lenna影象已經成為被廣泛使用的測試影象。今天,Lenna影象的使用被認為是數字影象歷史上最重要的事件之一。然而,很少有人看過原始的影象並知道完整的關於Lenna的故事。

Lenna/Lena是誰?

  • 從comp.compression FAQ中, 我們知道Lenna/Lena是一張數字化了的1972年12月份的《花花公子》摺頁。Lenna這個單詞是在《花花公子》裡的拼法,Lena是她名字的瑞典語拼法。(在英語中,為了正確發音,Lena有時被拼做Lenna。)關於Lena Soderberg (ne Sjooblom)的報道說她居住在她的本國瑞典,有著幸福的婚姻並是三個孩子的媽媽,在liquor monopoly州有一份工作。1988年,她被某個瑞典計算機相關雜誌採訪,因為她的照片而發生的一切令她很高興。這是她第一次得知她的照片在計算機領域被使用

為何要使用Lenna影象?

  • David C. Munson. 在“A Note on Lena” 中給出了兩條理由:首先,Lenna影象包含了各種細節、平滑區域、陰影和紋理,這些對測試各種影象處理演算法很有用。它是一副很好的測試影象!第二,Lena影象裡是一個很迷人的女子。所以不必奇怪影象處理領域裡的人(大部分為男性)被一副迷人的影象吸引。

誰製作了Lenna影象?

  • 在1999年10月29日,一封來自Chuck McNanis的email,裡面告訴我們這個曾經掃描了Lenna影象的“不知名的科研人員”是William K. Pratt博士。下面是email: 我在影象處理研究所的影象處理實驗室作為一個系統程式設計師工作了5年('78-'83),這個實驗室釋出了Lenna影象和其他一些被人們經常引用做“The baboon image”的影象(包括Manril)。這個“不知名的科研人員”是William K. Pratt博士,在Sun Microsystems。他當時正在寫一本關於影象處理的書,他需要幾張標準影象。很長一段時間以來,摺疊的摺疊式摺疊式摺頁一直放在實驗室的檔案櫃中。1997年我回去參觀時,實驗室發生了許多變化,原來的影象檔案找不到了。最初的分發格式是1600BPI的9軌磁帶,每個色板單獨儲存。–Chuck McManis (USC Class of '83)

原始影象編輯

  • 標準的數字Lena影象只是原始影象的臉和露肩特寫。曾在Chuck Rosenberg獲得了原始的《花花公子》雜誌的影象,並把它放在網上。

現在的Lenna

  • Lena女士居住在瑞典,並且已經是3個小孩的母親,過著快樂的生活。1997年,Lena被邀請參加了第50屆IS&T會議。

無線感測器網路資料壓縮

  • 近年來,隨著電子裝置的不斷髮展,大家可能都意識到了自己身邊都多了一些可以聯網的智慧電子裝置,智慧農業,智慧交通等也不斷地發展,應用到相應地場景中;有關無線感測器網路的研究也越來越多,越來越多的人也逐漸意識到無線感測器網路的無限適用性。例如,感測器網路可用於環境監測、生境檢測、結構檢測、裝置診斷、災害管理和應急響應等情況下收集資料。 但是無線感測器網路(WSNs)在應用的時候有一些資源的限制:有限的電源供應、通訊頻寬、處理速度和記憶體空間。最大限度地利用這些資源的一種可能的方法是對感測器的資料進行資料壓縮
  • ++通常情況下,處理資料比在無線介質中傳輸資料消耗的能量要少很多,因此在傳輸資料前採用資料壓縮可以有效的降低感測器節點的總功耗。++然而,現有的大部分壓縮演算法對於處理能力非常弱的感測器節點實在是過於龐大,以及每個感測器節點都受到了電力等資源的限制。所以,怎麼在感測器節點這種資源限制非常大的情況下並設計我們的壓縮演算法是最主要的問題。

分析能量在無線介質中的能量消耗

  • 從功耗上看,無線感測器節點的執行可分為 感測、處理和傳輸三部分。在這三種操作中,已知能耗最大的任務是資料傳輸。++每個感測器節點約 80% 的功耗用於資料傳輸。++ 因此,如果我們能通過資料壓縮使資料的大小最小化,就會減少傳輸功率。然而,另一方面,通過資料壓縮,將需要更強大的處理能力來執行壓縮演算法。為了減少的總功耗,必須減少傳輸和處理的總功耗。將 “a” 位的資料字串壓縮為 “b” 位的資料字串所消耗的功耗,其中 a>b 。

實驗① 傳送資料所消耗的能量實驗

  • 這個實驗室通過執行一個簡單的32位加法指令,傳送1位來採集功耗資料。
  • 結果表明,傳送 1個 bit 的資料大約消耗 0.4µJ 的能量,執行一條加法指令只想消耗 0.86nJ 的能量。通過無線電媒體傳輸一個 bit 的功耗至少是執行一個額外指令的 480倍。 所以如果通過壓縮操作從原始資料位串中刪除一個以上的位(相當於 480條 加法指令),將減少感測器節點的總功耗。

實驗② 文字及網頁資料應用各種無損資料壓縮的總功耗

  • 這個實驗測試的壓縮演算法有 bzip2 (BWT 演算法), compress (LZE 演算法), LZO (LZ77), PPMd (PPM) 和 zlib (LZ77).
  • 實驗結果表明,對於大多數壓縮演算法,在傳輸資料前壓縮資料可以減少總功耗。然而在某些情況下,應用資料壓縮會增加總功耗,這是由於在壓縮執行期間訪問記憶體。訪問記憶體在能量消耗方面是昂貴的。

結論:

  • 在無線介質中傳輸資料前採用資料壓縮是降低能耗的有效方法。然而,選擇一種資料壓縮演算法是至關重要的,它在執行期間需要較少的記憶體訪問。

資料壓縮技術

① 排序編碼

作為資料漏斗路由的一部分,引入了按順序編碼的資料壓縮方案。壓縮方案如下:

  1. 將資料從感興趣區域(Interested region)中的感測器節點傳遞到收集器節點,如圖一所示。在資料漏斗路由中,一些感測器節點作為資料匯聚節點工作。 例如:節點 A、節點 B、節點 D 為資料匯聚節點。在匯聚節點上,將其他節點收集到的感測資料進行組合,並將聚合後的資料傳送給其父節點。在圖 3 的節點 D 處,節點 E 收集的資料與節點 D 本身收集的資料相結合。
  2. 然後,將聚合的資料傳輸到節點 B

結論:

  1. 該資料壓縮方法壓縮比比較低,演算法簡單,有可能應用在無線感測器網路上。
  2. 使用該方案的一個困難是,由於沒有有效的演算法將排列對映到資料值,因此它需要一個對映表。隨著聚集的感測器節點的增加,表的大小呈指數增長

② 流水線式網路壓縮

這裡討論了流水線式網路壓縮方案。其基本思想是用高資料傳輸延遲換取低傳輸能耗。收集到的感測器資料在聚合節點的緩衝區中儲存一段時間。在此期間,將資料包合併成一個數據包,消除資料包中的冗餘,使資料傳輸最小化

結論:

  • 優點: 這種簡單壓縮方案的一個優點是,可以將共享字首系統用於節點 id 和時間戳。通過這樣做,可以實現更多的資料壓縮。 資料壓縮的效率取決於共享字首的長度。如果我們可以設定一個很長的共享字首,並且測量值具有共性,壓縮比就會增加。
  • 缺陷: 然而,測量的感測器值沒有相似之處。即使設定一個很長的共享字首,也會降低網路內流水線壓縮的效率。 此外,如果我們要合併大量的資料包,那麼就需要一個大的資料緩衝區來臨時儲存這些資料包。由於感測器節點的記憶體空間有限,因此沒有足夠的緩衝區空間可用。

③ 低複雜度視訊壓縮

這裡引入了低複雜度的視訊壓縮方案。由於目前的視訊編碼技術大多是利用運動估計和補償來設計的,因此需要較高的計算能力,而感測器節點通常不具備這種能力。因此,該方法是基於塊變化檢測演算法和 JPEG 資料壓縮的。

上圖給出了影象資料處理流程的框圖。該演算法是專門針對無線視訊監控系統而設計的。該方法將每個視訊幀劃分為小塊,每個塊包含 8 個 8(64)畫素。為了降低計算複雜度,在每一幀中只考慮塊的子集(本例中為所有的白色塊)。此外,在每個塊中,將檢查畫素子集(分配的畫素數目)的變化,如圖 7 所示。分配給畫素的數字表示畫素的重要性(1 =最重要,3 =最不重要)。

結論:

  • 實驗結果表明,該演算法處理後的影象質量與MPEG-2 處理後的影象質量相當,同時實現了一定的節能

④ 分散式壓縮

分散式壓縮方案背後的基本思想是使用一個邊資訊來編碼一個源資訊。然後,解碼器在陪集中選擇一個與 Y 傳送的碼向量值最接近的碼向量。

結論:

  • 分散式壓縮方案不僅可以應用於如上述例子所示的離散源,也可以應用於連續源。此外,它可以用於無損和有失真壓縮方案。

總結

  • 近年來,人們對無線感測器網路的應用領域進行了廣泛的討論。未來隨著技術的發展,無線感測器網路的應用領域將比現在更加廣泛。人們將比現在更容易得到它們。然而,在這些日子到來之際,感測器網路的實際應用仍然存在許多障礙需要克服。其中一個障礙是無線節點資源有限。
  • 本文已處理5種不同型別的資料壓縮方案:排序編碼、流水線網路壓縮、JPEG200、低複雜度視訊壓縮和分散式壓縮。儘管這些壓縮方案仍處於開發階段,但實驗結果表明,它們的壓縮率和功率降低方式相當令人深刻。它們是無線感測器節點資源約束的一種可行方法。

參考文獻

[1] Vitter, Scott J . Design and analysis of dynamic Huffman codes[J]. Journal of the Acm, 1987, 34(4):825-845. [2] Peng J , Kim C S , Kuo C C J . Technologies for 3D mesh compression: A survey[J]. Journal of Visual Communication & Image Representation, 2005, 16(6):688-733. [3] Holtz K . The evolution of lossless data compression techniques[C]// Wescon/93 Conference Record. IEEE, 1993. [4] Kimura N , Latifi S . A survey on data compression in wireless sensor networks[C]// International Conference on Information Technology: Coding and Computing (ITCC'05) - Volume II. IEEE, 2005. [5] Sudhakar R , Karthiga M R , Jayaraman S . Image compression using coding of wavelet coefficients–a survey[J]. A Survey”, ICGST-GVIP Journal, Volume (5), Issue, 2005(6):25-38. [6] Li W C , Ang L M , Seng K P . Survey of image compression algorithms in wireless sensor networks[C]// International Symposium on Information Technology. 2008. [7] Hamming R W . Coding and information theory (2. ed.)[M]. DBLP, 1986. [8] 高銳智, 華成英. 漢字字形結構式壓縮方法的研究和實現[J]. 電腦科學, 2003, 30(005):78-81. [9] Zhang C N , Wu X . A hybrid approach of wavelet packet and directional decomposition for image compression[J]. Wiley Subscription Services, Inc. A Wiley Company, 2002, 12(2):51-55. [10] Kunt, M, Ikonomopoulos, et al. Second-generation image-coding techniques[J]. Proceedings of the IEEE, 1985.