行程長度編碼

行程長度編碼(RLE)定義:

行長度編碼是一種與資料性質無關的無損數據壓縮技術。

變動長度編碼法為一種“使用固定長度的碼來取代連續重複出現的原始資料”的壓縮技術。

舉例來說，一組資料串"AAAABBBCCDEEEE"，由4個A、3個B、2個C、1個D、4個E組成，經過變動長度編碼法可將資料壓縮為4A3B2C1D4E(由14個單位轉成10個單位)。

簡言之，其優點在於將重複性高的資料量壓縮成小單位；然而，其缺點在於─若該資料出現頻率不高，可能導致壓縮結果資料量比原始資料大，例如：原始資料"ABCDE"，壓縮結果為"1A1B1C1D1E"(由5個單位轉成10個單位)。

行長度編碼，在同一行上出現重複的像素點是記錄一個像素及像素的重複數量，而不對每個像素進行記錄，該壓縮比率和特定的圖象內容有關；

RLE行程長度編碼概述

目前, 壓縮技術已經廣泛套用於各種軟體、聲音、影像格式等領域。總的來說, 有兩種截然不同的圖像格式壓縮類型: 有損壓縮和無損壓縮[1]。有損壓縮利用視覺識別的原理可以大大地壓縮檔案的數據, 但是會影響圖像質量。無損壓縮的基本原理是相同的顏色信息只需保存一次, 可以刪除一些重複數據, 大大減少要在磁碟上保存的圖像的容量。無損壓縮方法的優點是能夠比較好地保存圖像的質量, 但是相對有損壓縮來說這種方法的壓縮率是比較低的。常用的無損壓縮算法有 RLE、LZW等。

RLE 壓縮算法的基本原理

RLE(Run- Length Encoding 行程長度編碼)壓縮算法是Windows 系統中使用的一種圖像檔案壓縮方法, 其基本思想是: 將一掃描行中顏色值相同的相鄰像素用兩個位元組來表示, 第一個位元組是一個計數值, 用於指定像素重複的次數; 第二個位元組是具體像素的值[2]。主要通過壓縮除掉數據中的冗餘位元組或位元組中的冗餘位,從而達到減少檔案所占空間的目的。例如, 有一表示顏色像素值的字元串RRRRRGGBBBBBB,用 RLE 壓縮方法壓縮後可用 5R2G6B 來代替,顯然後者的串長度比前者的串長度小得多。解碼時按照與編碼時採用的相同規則進行, 還原後得到的數據與壓縮前的數據完全相同。因此, RLE 是無損壓縮技術。

RLE 壓縮算法的改進

RLE 壓縮算法對於數據重複量大的情況是非常高效率的。但是, 當圖像像素的顏色值出現每個相鄰像素的顏色值均不同的特殊情況時, 如顏色字元串GBR, 則經此方法壓縮後變成了 1G1B1R, 反而會使數據串的長度增加一倍, 這是一種“病態”情況。為了儘量避免“病態”情況的出現, 需要對 RLE 的基本方法進行改進。改進的方法是在具體實施時對計數位元組和圖像像素位元組進行了區分, 利用計數位元組的高兩位作為壓縮的標誌。對每個相鄰像素的顏色值均不同的單個像素數據, 只有當計數位元組高 2位全1( 即 C0) 時才加 1 計數, 否則直接輸出該像素值, 因此避免了壓縮後長度增加一倍的情況。這樣就使得計數位元組本身的高 2 位也是全 1, 即計數位元組為 C0H+n( 像素數據連續相同的位元組數)。當單個圖像數據的值大於或等於C0 時, 則先輸出 C1, 再輸出該圖像數據值, 否則直接輸出該數據。如有以下一系列數據: D2,20,30,30,30,C0,C1,C1,E2,E2,E2,…,E2(132個),E0,E0,D4,經壓縮後數據為 : C1,D2,20,C3,30,C1,C0,C2,C1,FF,E2,FF,E2,C6,E2,C2,E0,C1,D4,從這個壓縮過程可以看到,單個的圖像數據 D2、C0、D4 前面帶有計數位元組 C1, 而 20 前沒有。這樣可以有效避免壓縮後膨脹的異常情況。在上述改進的基礎上, 我們發現, 由於一個位元組最大只能為 FFH, 因此 n 最大只能為 FFH- C0H=3FH=(63)10, 故當 n>63 時, 則需要分多次壓縮。例如132個數據 E2 用了 6個位元組 (FF,E2,FF,E2,C6,E2)來表示。為了減少大批量重複數據所需的位元組數, 我們對其進行更進一步的改進: 規定緊跟 FF 後的位元組, 依然是計數位元組。如上述數據: D2,20,30,30,30,C0,C1,C1,E2,E2,E2,…,E2(132個),E0,E0,D4,經壓縮後數據為:C1,D2,20,C3,30,C1,C0,C2,C1,FF,45,E2,C2,E0,C1,D4。比較兩組數據, 現在 132個數據 E2 用了 3個位元組(FF,45,E2)就可以表示了, 有效地減少了數據量。一種極端的情況是某個數據剛好重複的次數是 FF 次, 對於這種特殊情況, 我們在 FF 位元組後增加一個 00 的位元組來區別表示。通過這樣的改進, 並不會增加壓縮和解壓縮太多的複雜性, 卻改善了壓縮的效率。

行程長度編碼

基本介紹