行程長度編碼

rle行程長度編碼概述

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

1 RLE 壓縮演演算法的基本原理

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

2 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 的位元組來區別表示。通過這樣的改進, 並不會增加壓縮和解壓縮太多的複雜性, 卻改善了壓縮的效率。

探 討 RLE特點

從前面所給的例子中我們不難看出RLE所能獲得的壓縮比有多大，這主要是取決於圖像本身的特點。如果圖像中具有相同顏色的圖像塊越大，圖像塊數目越少，獲得的壓縮比就越高。反之， RLE對顏色豐富的自然圖像就顯得力不從心，在同一行上具有相同顏色的連續像素往往很少，而連續幾行都具有相同顏色值的連續行數就更少。如果仍然使用RLE編碼方法，不僅不能壓縮圖像數據，反而可能使原來的圖像數據變得更大。因此，具體實現時，需要和其它的壓縮編碼技術聯合應用。

重複次數即行程(Run-Length)

一種可行的方案是，將數據流中各數值分為兩類：其中一類數值行程小於

或等於128,按原值輸出；另一類數值行程大於128,此類

數值加上128后輸出。綜上所述，改進后的行程編

碼演演算法如下:

①對行程小於或等於2的數值按原值輸出;

②對行程大於2的數值，將其加上128后輸

出，並在其後相鄰位置輸出行程大小。

RLE演演算法的局限性

在RLE數據壓縮中，只有當重複的位元組數大於

3時才可以起到壓縮作用，並且還需要一個特殊的

字元用作標誌位，因此在採用RLE壓縮方法時，必

須處理以下幾個制約壓縮比的問題[8]。

(1)在原始圖像數據中，除部分背景圖像的像素

值相同外，沒有更多連續相同的像素。因此如何提

高圖像中相同數據值的問題是提高數據壓縮比的關

鍵;

(2)如何尋找一個特殊的字元，使它在處理的圖

像中不用或很少使用的問題;

(3)在有重複位元組的情況下，如何提高重複位元組

數(最多為255)受限的問題。