OpenHarmony啃論文俱樂部—輕翻那些永垂不朽的詩篇
【本期看點】
主題：《老子到此一游系列》之 老子見證的滄海桑田。
- 塞繆爾·莫爾斯發(fā)明摩斯mi碼開創(chuàng)編碼領域先河。
- 香農提出信息熵，用數學語言闡明了概率與信息冗余度的關系。
- 用生活中的烹飪視角解析Huffman編碼過程。
- 小波系數的各類編碼方案大比拼。
- 計算機視覺中的女神 —— Lenna。
- 當代無線傳感器型網絡數據壓縮。
【技術DNA】
【智慧場景】
【脈動一下】
數據壓縮理論緣起
起源
數據壓縮概念的演變源于摩爾斯電碼，也即我們日常所說的摩斯mi碼(SOS就是其中一種)，它是一種時通時斷的信號代碼，通過不同的排列順序來表達不同的英文字母、數字和標點符號，從而最小化消息的大小和傳輸時間。由電報之父塞繆爾·莫爾斯于1837年發(fā)明，1838年正式用于壓縮電報中的信件。
發(fā)展
1986年Richard W. Hamming編寫出版的《Coding and information
theory》一書中提到：編碼和信息理論的概念起源久遠，但在信息理論還未建立起一個堅實的基礎之時，人們對其的許多基礎性想法與理解其實都只停留在1948年之前。
說到信息理論，不得不提到一個人 —— Claude E. Shannon(克勞德·艾爾伍德·香農)。香農是美國數學家，也是信息論的創(chuàng)始人，他提出了信息熵的概念，為信息論和數字通信的發(fā)展奠定了基礎。從本質上講，數據壓縮的目的就是要消除信息中的冗余，而信息熵及相關的定理恰恰用數學手段精確地描述了信息冗余的程度。利用信息熵公式，人們可以計算出信息編碼的極限，即在一定的概率模型下，無損壓縮的編碼長度不可能小于信息熵公式給出的結果。
于是后來，上述形勢被1948年香農發(fā)表的兩篇名為《通訊的數學原理》的文章所打破，它們在信息理論領域幾乎迅速地傳播并流行了起來。很快，另外一些信息理論的文章出現在了相關期刊上，許多大學的電氣工程等相關部門也開始教授相關課程。
但由于信息理論在當時是一個新領域，人們對其能做的事情以及能應用的方向還沒有一個確切的認識，漸漸地，人們對其的關注度愈發(fā)降低，相關課程的教授也隨之減少。
轉折
信息理論具有廣泛適用于遠離其原始靈感的情況的想法。好巧不巧的是，在信息理論被創(chuàng)立的左右之時，編碼理論也誕生了。就編碼理論而言，其數學背景在一開始遠沒有信息理論那么復雜，而且在很長一段時間里，它也沒有得到理論界的重視。但是，隨著時間的推移，各種數學工具如群論、有限域理論等慢慢被應用到編碼理論中。現在，編碼理論已成為數學研究中一個活躍的部分。
從邏輯上講，編碼理論引出了信息論，信息論提供了對信息進行適當編碼所能做的操作的界限。因此，這兩種理論是密切相關的。
1948 年，香農在提出信息熵理論的同時，也給出了一種簡單的編碼方法—— Shannon 編碼，為壓縮算法領域的發(fā)展奠定了專屬基調。 1952 年， R. M. Fano 又進一步提出了 Fano 編碼。這些早期的編碼方法揭示了變長編碼的基本規(guī)律，也確實可以取得一定的壓縮效果，但離真正實用的壓縮算法還相去甚遠。
第一個實用的編碼方法是由 D. A. Huffman 在 1952 年的論文《最小冗余度代碼的構造方法( A Method for the Construction of Minimum Redundancy Codes )》中提出的。直到今天，許多《數據結構》教材在討論二叉樹時仍要提及這種被后人稱為 Huffman 編碼的方法。 Huffman 編碼在計算機界是如此著名，以至于連編碼的發(fā)明過程本身也成了人們津津樂道的話題。據說， 1952 年時，年輕的 Huffman 還是麻省理工學院的一名學生，他為了向老師證明自己可以不參加某門功課的期末考試，才設計了這個看似簡單，但卻影響深遠的編碼方法。
Huffman 編碼效率高，運算速度快，實現方式靈活，從 20 世紀 60 年代至今，在數據壓縮領域得到了廣泛的應用。例如，早期 UNIX 系統上一個不太為現代人熟知的壓縮程序 COMPACT 實際就是 Huffman 0 階自適應編碼的具體實現。 20 世紀 80 年代初， Huffman 編碼又出現在 CP/M 和 DOS 系統中，其代表程序叫 SQ 。今天，在許多知名的壓縮工具和壓縮算法(如 WinRAR 、 gzip 和 JPEG )里，都有 Huffman 編碼的身影。不過， Huffman 編碼所得的編碼長度只是對信息熵計算結果的一種近似，還無法真正逼近信息熵的極限。正因為如此，現代壓縮技術通常只將 Huffman 視作最終的編碼手段，而非數據壓縮算法的全部。
Huffman碼
說到哈夫曼編碼或是霍夫曼編碼，熱愛自然科學、關注計算機科學的朋友們，或許曾聽過、研究過;若是第一次聽聞，或許會有一種像聽到相對論、量子力學等一般的緊張感，請不必擔心，我們接下來以一種老少皆宜、通俗有趣的方式傳播分享，通讀一遍說不定也能收獲滿滿，接下來讓我們進入正題吧：
先來感性地認識一下霍夫曼編碼，首先顧名思義，我們可以明確一個大前提，這是霍夫曼的作品，其次這是一種編碼技術。技術是用來解決問題的，那霍夫曼編碼是用來解決什么問題的呢?——信息壓縮問題。
現在大家心中已經對霍夫曼編碼建立起了一個最基本的概念，這是由霍夫曼創(chuàng)立的用于解決信息壓縮問題的編碼技術。但這個概念還是太籠統了，再詳盡一些是什么樣子的呢?(別緊張，接下來你不會看到滿屏的數學公式)。
我們用烹飪來舉個例子，大家或許做過，或者看別人做過飯，做飯首先就得明確目標，就是我要做什么菜，對于霍夫曼編碼來說就是目標壓縮文本是什么，然后你就得列個清單看看做這道菜需要哪些原材料，各種要多少;對于霍夫曼編碼來說就是一個統計構成文本的元素的種類和出現頻率的過程;料備齊了就要掌握如何搭配，以及掌握火候，這就是考驗一個人的廚藝的時候了;對于霍夫曼編碼來說就是建立一個高效的字典樹的過程。這一套流程下來我們可以獲得一個菜的菜譜，這就是一個成品菜的壓縮成果;對于霍夫曼來說我們就獲得了一個文本的字典樹：
在線體驗霍夫曼編碼生成過程：
??huffman.ooz.ie - Online Huffman Tree Generator (with frequency!)??
現代場景
1. 漢字字形壓縮
通俗些說就是把我們的中文文本進行識別和壓縮，這與英文文本有什么不同呢?中華文化博大精深，不像英文文本只有26個字母和一些標點符號，漢字千變萬化，無法通過傳統的方式統計編碼。但是萬變不離其宗，我們從小寫字就知道一點，我們的漢字是由筆劃再按照一定筆順寫成的，那么這時筆劃也就是我們前面所說的原材料模板：
而筆順就是我們建立字典的依據，我們的漢字通過這樣的處理就可以通過霍夫曼編碼進行壓縮編碼了。
2. 3D網格的編碼壓縮
說到3D網格大家腦海中最先會聯想到的可能會是3D動畫，沒錯這一項技術廣泛的應用于這一領域，下面一些圖片可供直觀感受：
那么如何讓這些精美的3D作品高效的壓縮存儲呢?霍夫曼編碼大顯身手的時侯。
到了，下面介紹相關場景并補充一項3D網格幾何壓縮的強大算法。
【征服三角形】
對未征服也就是未編碼之處圍繞其邊界插入三角形，進行擬合重構。
其中箭頭和數字給出了三角形征服的順序。三角形中填滿了不同圖案來代表不同的操作碼，當它們被征服時就會生成這些操作碼，再通過霍夫曼進行處理。
【kD-tree分解(強大的3D圖像處理算法)】
該方案特別適用于地形模型和密集采樣對象。
為便于理解我們用2D來表述。
每次將一個單元格細分為兩個小單元格，對頂點數量進行編碼。這種細。
分被重復地應用，直到每個單元格足夠小，可以只包含一個頂點，并能夠足夠精確地重建頂點位置。
動態(tài)Huffman碼的設計
動態(tài)哈夫曼編碼(Dynamic Huffman coding)，又稱適應性哈夫曼編碼(Adaptive Huffman coding)，是基于哈夫曼編碼的自適應編碼技術。它允許在符號正在傳輸時構建代碼，允許一次編碼并適應數據中變化的條件，即隨著數據流的到達，動態(tài)地收集和更新符號的概率(頻率)。一遍掃描的好處是使得源程序可以實時編碼，但由于單個丟失會損壞整個代碼，因此它對傳輸錯誤更加敏感。
摘要
文章介紹并分析了一種構造動態(tài)Huffman碼的單遍算法，同時還分析了由 Faller、Gallager和Knuth 三位學者得到的單遍算法。在每個算法中，發(fā)送器和接收器都保持等效的動態(tài)變化 Huffman 樹，并對其進行實時編碼。他們證明了新算法編碼包含 t 個字母的消息所占用的bit數小于t，遠遠優(yōu)于傳統的兩遍 Huffman 方案，并且與字母表的大小沒有關系。對于任何一種單遍 Huffman 算法來說，這是在最壞狀態(tài)下能做到的最佳可能情況。實驗表明，新算法生成的編碼長度比其他單遍算法的短，除了長消息外，也比兩遍算法的短。最后明確了該算法適用于數據網絡的在線編/解碼和文件壓縮場景。
介紹
由于傳統的靜態(tài) Huffman 算法存在一個缺點，即它需要對數據進行兩次遍歷：第一次是通過構造和傳輸 Huffman 樹到接收器，來收集消息中字母出現的頻率計數;然后第二次再基于第一次構造的靜態(tài)樹結構，來編碼和傳輸消息本身。那么，這會導致在將其用于網絡通信時產生延遲，或者在文件壓縮應用程序中產生額外的磁盤訪問從而減慢算法。所以，Faller 和 Gallager兩人各提出了一種一次遍歷方案，后來被 Knuth 大大改進，以構造動態(tài) Huffman 編碼。發(fā)送器用來編碼消息中第 t + 1 個字母的二叉樹(同時也是接收器用來重建第 t + 1 個字母的二叉樹)是消息前 t 個字母的二叉樹。這樣的話，發(fā)送器和接收器就都會從相同的初始樹開始，發(fā)送器永遠不需要將樹發(fā)送給接收器。很顯然，這與兩次遍歷算法的情況不同。
隨后，研究者設計并證明了一個所有單遍Huffman方案中，在最壞情況下表現仍然是最優(yōu)的算法A，它可以用于網絡通信的通用編碼方案，也可以作為基于文字的壓縮算法中的一種高效子例程。
實驗結論
算法A的優(yōu)點：
- 對于編碼效率差異相對較大的小消息，每個字母占用更少的位。
- 在 t 小于104時，相比所有兩遍算法都表現得更好。
- 能夠對消息進行實時編碼解碼，每個字母使用不到一個額外的比特位對消息進行編碼。
- 在文件壓縮、網絡通信和硬件實現方面有很大的應用潛力。
- 可用來增強其他壓縮方案。
小波系數圖像壓縮編碼
引言
由于多媒體信息和數字化的圖像表示形式所帶來的網絡流量的不斷增加，圖像壓縮已經成為一種剛需?；谛〔ǖ膱D像壓縮新算法被開發(fā)出來，這些方法取得了實際性進展，如：卓越的低比特率性能、連續(xù)音調和比特級壓縮、無損和有損壓縮、逐像素、精度和分辨率傳輸等。小波算法最成功的應用之一是基于變換的圖像壓縮，其重疊特性減輕了塊效應(馬賽克被放大的場景);而小波分解的多分辨率特性又使解壓后的圖像具有更好的感知質量。前期相關文章已經涉及到小波變換的部分內容，這里再繼續(xù)對其展開詳細描述。
基本原理
大多數圖像的共同特征是相鄰像素是相關的，所以便包含了很多冗余信息。然后，最重要的任務是找到圖像中不太相關的表示。壓縮的兩個基本組件就是冗余和無關性的減少：
- 冗余減少的目的是消除信號源(圖像/視頻)的重復。
- 無相性的減少則是忽略了信號接收器即人類視覺系統(HVS)通常不會注意到的部分信號。
另外，通常也有三種類型的冗余：
- 相鄰元素之間的空間冗余或相關性。
- 不同顏色平面或光譜帶之間的光譜冗余或相關性。
- 圖像序列相鄰幀之間的時間冗余或相關性(主要就是視頻應用)。
因此，圖像壓縮的目標就是希望盡可能地去除空間和光譜冗余以減少表示圖像所需的比特位數。其次，圖像壓縮還需保證一個基本目標：降低傳輸或存儲比特率的同時保持可接受的保真度或圖像質量。
高低頻分離&&量化
大多數自然圖像都有平滑的顏色變化，在平滑變化之間，精細的細節(jié)被表示為尖銳邊緣。從技術上講，顏色的平滑變化被稱為低頻變化，尖銳變化被稱為高頻變化。低頻成分構成了圖像的基礎，高頻成分則是為了細化圖像。因此，基礎比細節(jié)相對更重要。類似的，我們在聲樂領域也能找到相對應的概念 —— 基音與泛音，基音是波形里振幅最大，頻率最小的組成波，它決定了音高;而泛音頻率是基音的整數倍，跟基音疊加在一起后整體波形仍是基音的頻率，但加入泛音組成后波形的形態(tài)不再單純，可以理解為對基音作了一定的修飾，即決定了音色。
分離多數采用離散小波變換(DWT)，通過濾波器組對圖像進行一系列類似金字塔型的操作。基于小波的編碼在傳輸和解碼錯誤下具有更強的魯棒性，有利于圖像的漸進傳輸。此外，它們也更符合人類視覺系統的特點。
量化，是指用有限的、較小的值集來逼近圖像數據中連續(xù)的值集的過程。有兩種類型的量化，分別是標量量化和矢量量化。
度量指標
兩類用于比較各種圖像壓縮技術的指標是均方誤差(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不是傳統圖像壓縮算法的簡單擴展，它代表了該領域的一個里程碑式進展，具有以下性質：
- 圖像質量好，PSNR值高，尤其對于彩色圖像。
- 是優(yōu)化好的漸進式圖像傳輸。
- 生成一個完全嵌入的編碼文件。
- 簡單量化算法。
- 快速編/解碼(幾乎對稱分布)。
- 應用范圍廣、適應性強。
- 可用于無損壓縮。
- 可以編碼到精確的比特率或失真。
- 高效結合誤差保護。
SPIHT可以通過對輸出信息進行熵編碼來提高效率，但代價是增加了編/解碼的時間。同時為了減少此方案中使用的列表數量，需要形成下一個算法，稱為 SPECK。
設置分區(qū)嵌入式塊編碼(SPECK)
SPECK不同于上述的一些方案，它不使用跨越不同子帶的樹，而是以塊的形式使用集合。主要思想是利用變換后的圖像層次結構中頻率和空間能力的聚類，根源還是SPIHT中發(fā)展出來的思想。
特點：
SPECK具有標量量化顯著性測試方案的全部特性：
- 是完全嵌入的 — 為了實現最好的重建效果，一個編碼的比特流可用來解碼任何速率小于等于編碼速率的圖像。
- 采用遞進傳輸源樣本按其信息內容的降序編碼。
- 計算復雜度低 — 算法非常簡單，主要是比較，不需要任何復雜的計算。
- 較低的動態(tài)內存需求 — 在編碼過程中的任何給定時間，只有一個連接區(qū)域(完全位于子帶內)被處理。
- 快速的編/解碼 — 這是由于算法的低復雜度，對應了第3點。
- 高效的性能 — 其效率可與目前可用的其他低復雜度算法相媲美。
解碼器使用與編碼器相同的機制。它接收編碼位流的顯著性測試結果，并在算法執(zhí)行過程中建立相同的列表結構。因此，對于不同集合的顯著性測試，它能夠遵循相同的執(zhí)行路徑，并隨著算法的進行逐步重建圖像?？梢钥闯?，SPECK 具有更高的壓縮比。這顯示了以塊的形式處理集比空間方向樹的形式處理集的優(yōu)勢。與 SPIHT 相比，對于相同的分解級別和丟棄的位平面，這些壓縮比下的重建圖像具有可觀的分辨率。
結論：
- 在分解層次較少的情況下，SPECK重建圖像的分辨率即清晰度優(yōu)于 SPIHT。
- 優(yōu)化截斷的嵌入式塊編碼(EBCOT)。
EBCOT 將每個子帶劃分為相對較小的樣本塊，并生成一個獨立的高度可伸縮的比特流來表示每個所謂的代碼塊。該算法展示了最先進的壓縮性能，同時產生一個前所未有的特征集的比特流，包括分辨率和信噪比可伸縮性以及隨機訪問屬性。該算法具有適度的復雜性，非常適合于涉及遠程瀏覽大型壓縮圖像的應用。
可見，在最先進的壓縮算法方面，EBCOT顯著優(yōu)于SPIHT。
其他
此外，還有許多小波系數相關衍生編碼技術，如小波差約簡(WDR)、自適應掃描小波差約簡(ASWDR)、空頻量化(SFQ)、嵌入式預測小波圖像(EPWIC)、可逆嵌入小波壓縮(CREW)、堆棧運行(SR)等，這里不再一一贅述，各種編碼技術的優(yōu)缺點詳見下表：
第二代圖片壓縮技術
引言
在硬件受限的環(huán)境下，在視覺傳感器節(jié)點中實現圖像處理引擎一直是無線多媒體傳感器網絡發(fā)展的主要關注點。文章對8種常用的圖像壓縮技術進行了綜述。綜合評估后發(fā)現，基于層次樹集分塊(Set-Partitioning in Hierarchical tree, SPIHT)小波的圖像壓縮算法壓縮效率高，編碼過程簡單，是無線傳感器網絡中最適合硬件實現的圖像壓縮算法。
無線傳感器網絡(WSN)圖片壓縮
無線傳感器網絡(Wireless sensor network, WSN)是由多個傳感器設備通過無線信息進行通信的網絡，具有在傳感器節(jié)點上進行數據處理和計算的能力。近年來，人們對可靠、高效的無線多媒體傳感器網絡(Wireless multimedia sensor network, WMSN)研究和開發(fā)越來越感興趣。從攝像機節(jié)點收集的圖像和視頻幀等多媒體數據需要大量的處理，這使得WMSN的實現非常困難，特別是在硬件受限的環(huán)境中。高功耗、有限帶寬和內存限制是影響高效靈活WMSN開發(fā)的挑戰(zhàn)和制約因素。
多媒體內容，特別是高分辨率的圖像需要廣泛的帶寬傳輸。由于可用帶寬有限，傳感器節(jié)點捕獲的圖像在傳輸前需要進行處理和壓縮。通過圖像壓縮去除原始數據中的冗余信息，可以獲得一種更高效的傳輸方法。
最近的技術使得具有嵌入式處理能力的微型傳感設備的生產成為可能。由于空間限制和提供大量內存存儲的高成本，片上內存受到限制，并成為處理大型圖像的另一個主要約束。因此，需要開發(fā)一種更簡單、更經濟的系統，以滿足圖像處理中的高內存存儲需求。
圖像壓縮算法
利用圖像中相鄰像素高度相關這一事實，我們可以通過尋找相關度較低的圖像表示來丟棄這些冗余的信息，這是圖像壓縮算法背后的基本理論。下圖展示圖像編碼過程的基本組成，圖像編碼過程分為兩個階段，圖像變換階段和熵編碼階段。
圖像編碼可分為第一代和第二代：
- 第一代圖像編碼更強調如何有效地編碼轉換后的圖像所包含的信息。
- 第二代圖像編碼更重視如何從圖像中挖掘和提取有用的信息。
- 文章在第一代編碼中介紹了四種最流行的基于變換的圖像壓縮算法——JPEG、EZW、SPIHT和EBCOT，其中EZW、SPIHT和EBCOT在上一部分“小波系數圖像壓縮編碼”中已經做了詳細的介紹，在此不再展開。
- 著名的圖像壓縮標準JPEG使用了基于離散余弦變換(DCT)的圖像壓縮技術，將圖像分為多個8 x 8像素的子圖像塊，并對每個圖像塊獨立編碼。DCT不對原始數據造成損失，經過離散余弦變換后，每個64DCT系數被均勻量化。然后在8 x 8圖像塊中采用鋸齒狀掃描重新排列系數。下圖顯示了鋸齒狀掃描的過程：
基于DCT的圖像壓縮提供了令人滿意的壓縮效率，并且由于編碼是在小的單個圖像塊上完成的，實現時所需的內存很低。然而，圖像塊的平鋪會導致阻塞工件，從而導致性能下降。
第二代圖像編碼
金字塔/多分辨率編碼(Pyramidal/multiresolution coding)
金字塔編碼在圖像發(fā)展的早期階段就已經被引入，但是由于分層編碼的方式與人類視覺系統** (Human Visual Syatem, HVS) 中的神經系統類似，所以將其歸為第二代圖像編碼**。
通過使用適當的平滑濾鏡對圖像進行平滑處理，然后對平滑圖像進行子采樣(通常沿每個坐標方向按 2 倍)來生成低通金字塔。然后，對生成的圖像進行相同的過程，并重復多次循環(huán)。此過程的每個周期都會導致圖像變小，平滑度增加，但空間采樣密度降低(即圖像分辨率降低)。如果以圖形方式進行說明，則整個多尺度表示將看起來像一個金字塔，原始圖像位于底部，每個周期生成的較小圖像將一個堆疊在另一個之上：
上圖是金字塔編碼的形象化表示。
上圖為金字塔編碼的實例，其中各圖分別表示：
- 原始圖像“Lenna”。
- 高斯金字塔圖像。
- 高斯插值圖像。
- 拉普拉斯金字塔圖像。
高斯核和拉普拉斯核是兩種對圖像進行平滑處理的核函數。拉普拉斯金字塔算法基于空間頻率將圖像分解為多個分量，金字塔中每個節(jié)點的值代表兩類高斯函數與原始圖像卷積的差值(平滑處理)。
基于方向分解的編碼(Directional decomposition based coding)
從對HVS本質的研究和分析中發(fā)現，邊緣信息在圖像的感知中至關重要。然而采用傳統的變換編碼、子帶編碼和小波編碼等編碼方法對圖像進行編碼時，這些信息往往會發(fā)生畸變。定向濾波編碼更強調邊緣檢測，以實現高壓縮比。它基于人眼是由對方向敏感的神經元組成的事實，一個方向濾波器用于利用邊緣之間的關系及其對圖像光譜的貢獻。該濾波器被定義為“沿主方向進行高通濾波，沿正交方向進行低通濾波的濾波器”。
在方向濾波過程中，將原始圖像分解為一副低通圖像和若干幅高通圖像。每個高通圖像都包含一個主方向的邊緣信息，因此圖像中的邊緣信息得到很好的保存(相比于之前提到的傳統的變換編碼、子帶編碼和小波編碼等編碼方法)。低通圖像不包含邊緣信息，可以采用變換編碼，而高通圖像采用邊緣檢測和編碼。
基于分割的編碼(Segmentation based coding)
與基于方向分解的編碼類似，該編碼利用了人眼善于識別相似區(qū)域并將其分組為事實，根據圖像的紋理結構將圖像劃分為子區(qū)域。這些子區(qū)域被輪廓包圍，輪廓和紋理區(qū)域將分別進行編碼。下圖展示了基于分割的編碼過程：
- 基于對HVS的特征和分析，首先對圖像進行預處理，去除噪聲和無用區(qū)域。
- 在分割的過程中，采用一種基于區(qū)域增長的編碼方法，每個像素和它的相鄰像素根據灰度級別來判斷它們是否共享相同的屬性。重復這個區(qū)域增長過程，直到所有的像素都被分配某個區(qū)域，這樣會得到很多子區(qū)域。為了減少區(qū)域數，降低編碼復雜度，會將弱對比即相比差距不大的相鄰區(qū)域和小區(qū)域進行合并。
- 最后進分別對輪廓區(qū)域和紋理區(qū)域進行輪廓編碼和紋理編碼。
矢量量化(Vector quantization)
矢量量化，顧名思義就是利用矢量表示圖像。利用矢量量化對圖像編碼時，首先將高度相關的像素分組為樣本集的塊，每一個塊都可以找到一個最佳的近似向量來表示給定區(qū)域中的每個像素。對這些像素塊進行量化，然后每個塊獨立編碼，基于這個過程，矢量量化又被稱為塊量化或者模式匹配量化。下圖為矢量量化編碼的框圖：
編碼
- 圖像預處理，將圖像分割成像素塊。
- 為每個像素塊找到一個表示向量k。
- 將向量k與查找表(碼本)中預定義的向量集(碼字)進行比較，選擇最匹配的碼字。
- 為了獲得更高的壓縮比，傳輸的是碼字的索引而不是碼字本身，索引比碼字本身占用的位數更少。
解碼
- 根據接收到的索引值從碼本中選取碼字。
- 利用碼字重構圖像。
- 從矢量量化編碼的過程中我們可以看到，每幅圖片可以劃分成各種各樣的子區(qū)域，這些子區(qū)域對應的矢量是非常多的，將大量的矢量編碼成碼本中有限的碼字，會造成數據的損失，因此矢量量化提供了有損壓縮。
觀察和總結
表：第一代和第二代圖像壓縮算法分析總結
分析與對比
上表總結了八種圖像壓縮算法的特性和特點，并且選擇SPIHT為最適合在無線傳感器網絡中實現的圖像壓縮算法。選擇的標準是所選算法應具備運行在硬件受限的環(huán)境下的WSN的大多數首選特征，包括快速高效的圖像處理能力、低內存需求、高壓縮質量、低系統復雜度和低計算負載。
除此之外，我們還可以得出：
第一代圖像壓縮算法是利用圖像像素之間的相似性來消除圖像中的冗余，而第二代圖像壓縮算法結合了HSV的特性，識別圖像中的特征，并對這些特征進行處理。第二代圖像編碼強調探索圖像的“內容”，與第一代進行小波變換的圖像編碼相比，這一特性需要更復雜和更廣泛的圖像處理。
大多數第二代圖像壓縮算法提供有損壓縮，它們依賴于初始的分割。在分割過程中，首先將圖像像素劃分為輪廓區(qū)域和紋理區(qū)域，然后進行區(qū)域增長過程。整個圖像的預處理過程被存儲在內存中，在WSN節(jié)點中是很難實現的。此外，分割時所需的大量的計算增加編碼器的復雜性并且降低了處理速度，使其在實時環(huán)境中不可能實現。
計算機視覺中的女神 —— 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是她名字的瑞典語拼法。(在英語中，為了正確發(fā)音，Lena有時被拼做Lenna。)關于Lena Soderberg (ne Sjooblom)的報道說她居住在她的本國瑞典，有著幸福的婚姻并是三個孩子的媽媽，在liquor monopoly州有一份工作。1988年，她被某個瑞典計算機相關雜志采訪，因為她的照片而發(fā)生的一切令她很高興。這是她第一次得知她的照片在計算機領域被使用。
為何要使用Lenna圖像?
David C. Munson. 在“A Note on Lena” 中給出了兩條理由：首先，Lenna圖像包含了各種細節(jié)、平滑區(qū)域、陰影和紋理，這些對測試各種圖像處理算法很有用。它是一副很好的測試圖像!第二，Lena圖像里是一個很迷人的女子。所以不必奇怪圖像處理領域里的人(大部分為男性)被一副迷人的圖像吸引。
誰制作了Lenna圖像?
在1999年10月29日，一封來自Chuck McNanis的email，里面告訴我們這個曾經掃描了Lenna圖像的“不知名的科研人員”是William K. Pratt博士。下面是email：
我在圖像處理研究所的圖像處理實驗室作為一個系統程序員工作了5年('78-'83)，這個實驗室發(fā)布了Lenna圖像和其他一些被人們經常引用做“The baboon image”的圖像(包括Manril)。這個“不知名的科研人員”是William K. Pratt博士，在Sun Microsystems。他當時正在寫一本關于圖像處理的書，他需要幾張標準圖像。很長一段時間以來，折疊的折疊式折疊式折頁一直放在實驗室的文件柜中。1997年我回去參觀時，實驗室發(fā)生了許多變化，原來的圖像文件找不到了。最初的分發(fā)格式是1600BPI的9軌磁帶，每個色板單獨存儲。–Chuck McManis (USC Class of '83)。
原始圖像編輯
標準的數字Lena圖像只是原始圖像的臉和露肩特寫。曾在Chuck Rosenberg獲得了原始的《花花公子》雜志的圖像，并把它放在網上。
現在的Lenna
Lena女士居住在瑞典，并且已經是3個小孩的母親，過著快樂的生活。1997年，Lena被邀請參加了第50屆IS&T會議。
無線傳感器網絡數據壓縮
近年來，隨著電子設備的不斷發(fā)展，大家可能都意識到了自己身邊都多了一些可以聯網的智能電子設備，智慧農業(yè)，智慧交通等也不斷地發(fā)展，應用到相應地場景中;有關無線傳感器網絡的研究也越來越多，越來越多的人也逐漸意識到無線傳感器網絡的無限適用性。例如，傳感器網絡可用于環(huán)境監(jiān)測、生境檢測、結構檢測、設備診斷、災害管理和應急響應等情況下收集數據。
但是無線傳感器網絡(WSNs)在應用的時候有一些資源的限制：有限的電源供應、通信帶寬、處理速度和內存空間。最大限度地利用這些資源的一種可能的方法是對傳感器的數據進行數據壓縮。
++通常情況下，處理數據比在無線介質中傳輸數據消耗的能量要少很多，因此在傳輸數據前采用數據壓縮可以有效的降低傳感器節(jié)點的總功耗。++然而，現有的大部分壓縮算法對于處理能力非常弱的傳感器節(jié)點實在是過于龐大，以及每個傳感器節(jié)點都受到了電力等資源的限制。所以，怎么在傳感器節(jié)點這種資源限制非常大的情況下并設計我們的壓縮算法是最主要的問題。
分析能量在無線介質中的能量消耗
從功耗上看，無線傳感器節(jié)點的運行可分為 傳感、處理和傳輸三部分。在這三種操作中，已知能耗最大的任務是數據傳輸。每個傳感器節(jié)點約 80% 的功耗用于數據傳輸。
因此，如果我們能通過數據壓縮使數據的大小最小化，就會減少傳輸功率。然而，另一方面，通過數據壓縮，將需要更強大的處理能力來執(zhí)行壓縮算法。為了減少的總功耗，必須減少傳輸和處理的總功耗。將 “a” 位的數據字符串壓縮為 “b” 位的數據字符串所消耗的功耗，其中 a>b 。
實驗① 發(fā)送數據所消耗的能量實驗
這個實驗室通過執(zhí)行一個簡單的32位加法指令，發(fā)送1位來采集功耗數據。
結果表明，發(fā)送 1個 bit 的數據大約消耗 0.4μJ 的能量，執(zhí)行一條加法指令只想消耗 0.86nJ 的能量。通過無線電媒體傳輸一個 bit 的功耗至少是執(zhí)行一個額外指令的 480倍。
所以如果通過壓縮操作從原始數據位串中刪除一個以上的位(相當于 480條 加法指令)，將減少傳感器節(jié)點的總功耗。
實驗② 文本及網頁數據應用各種無損數據壓縮的總功耗
這個實驗測試的壓縮算法有 bzip2 (BWT 算法), compress (LZE 算法), LZO (LZ77), PPMd (PPM) 和 zlib (LZ77)。
實驗結果表明，對于大多數壓縮算法，在傳輸數據前壓縮數據可以減少總功耗。然而在某些情況下，應用數據壓縮會增加總功耗，這是由于在壓縮執(zhí)行期間訪問內存。訪問內存在能量消耗方面是昂貴的。
結論：
在無線介質中傳輸數據前采用數據壓縮是降低能耗的有效方法。然而，選擇一種數據壓縮算法是至關重要的，它在執(zhí)行期間需要較少的內存訪問。
數據壓縮技術
① 排序編碼
作為數據漏斗路由的一部分，引入了按順序編碼的數據壓縮方案。壓縮方案如下：
將數據從感興趣區(qū)域(Interested region)中的傳感器節(jié)點傳遞到收集器節(jié)點，如圖一所示。在數據漏斗路由中，一些傳感器節(jié)點作為數據匯聚節(jié)點工作。
例如:節(jié)點 A、節(jié)點 B、節(jié)點 D 為數據匯聚節(jié)點。在匯聚節(jié)點上，將其他節(jié)點收集到的傳感數據進行組合，并將聚合后的數據發(fā)送給其父節(jié)點。在圖 3 的節(jié)點 D 處，節(jié)點 E 收集的數據與節(jié)點 D 本身收集的數據相結合。
然后，將聚合的數據傳輸到節(jié)點 B。
結論：
該數據壓縮方法壓縮比比較低，算法簡單，有可能應用在無線傳感器網絡上。
使用該方案的一個困難是，由于沒有有效的算法將排列映射到數據值，因此它需要一個映射表。隨著聚集的傳感器節(jié)點的增加，表的大小呈指數增長。
② 流水線式網絡壓縮
這里討論了流水線式網絡壓縮方案。其基本思想是用高數據傳輸延遲換取低傳輸能耗。收集到的傳感器數據在聚合節(jié)點的緩沖區(qū)中存儲一段時間。在此期間，將數據包合并成一個數據包，消除數據包中的冗余，使數據傳輸最小化。
結論：
優(yōu)點：
這種簡單壓縮方案的一個優(yōu)點是，可以將共享前綴系統用于節(jié)點 id 和時間戳。通過這樣做，可以實現更多的數據壓縮。
數據壓縮的效率取決于共享前綴的長度。如果我們可以設置一個很長的共享前綴，并且測量值具有共性，壓縮比就會增加。
缺陷：
然而，測量的傳感器值沒有相似之處。即使設置一個很長的共享前綴，也會降低網絡內流水線壓縮的效率。
此外，如果我們要合并大量的數據包，那么就需要一個大的數據緩沖區(qū)來臨時存儲這些數據包。由于傳感器節(jié)點的內存空間有限，因此沒有足夠的緩沖區(qū)空間可用。
③ 低復雜度視頻壓縮
這里引入了低復雜度的視頻壓縮方案。由于目前的視頻編碼技術大多是利用運動估計和補償來設計的，因此需要較高的計算能力，而傳感器節(jié)點通常不具備這種能力。因此，該方法是基于塊變化檢測算法和 JPEG 數據壓縮的。
上圖給出了圖像數據處理流程的框圖。該算法是專門針對無線視頻監(jiān)控系統而設計的。該方法將每個視頻幀劃分為小塊，每個塊包含 8 個 8(64)像素。為了降低計算復雜度，在每一幀中只考慮塊的子集(本例中為所有的白色塊)。此外，在每個塊中，將檢查像素子集(分配的像素數目)的變化，如圖 7 所示。分配給像素的數字表示像素的重要性(1 =最重要，3 =最不重要)。
結論：
實驗結果表明，該算法處理后的圖像質量與MPEG-2 處理后的圖像質量相當，同時實現了一定的節(jié)能。
④ 分布式壓縮
分布式壓縮方案背后的基本思想是使用一個邊信息來編碼一個源信息。然后，解碼器在陪集中選擇一個與 Y 發(fā)送的碼向量值最接近的碼向量。
結論：
分布式壓縮方案不僅可以應用于如上述例子所示的離散源，也可以應用于連續(xù)源。此外，它可以用于無損和有損壓縮方案。
總結
近年來，人們對無線傳感器網絡的應用領域進行了廣泛的討論。未來隨著技術的發(fā)展，無線傳感器網絡的應用領域將比現在更加廣泛。人們將比現在更容易得到它們。然而，在這些日子到來之際，傳感器網絡的實際應用仍然存在許多障礙需要克服。其中一個障礙是無線節(jié)點資源有限。
本文已處理5種不同類型的數據壓縮方案：排序編碼、流水線網絡壓縮、JPEG200、低復雜度視頻壓縮和分布式壓縮。盡管這些壓縮方案仍處于開發(fā)階段，但實驗結果表明，它們的壓縮率和功率降低方式相當令人深刻。它們是無線傳感器節(jié)點資源約束的一種可行方法。
