-
行程編碼
鎖定
行程編碼(Run Length Encoding,RLE),又稱遊程編碼、行程長度編碼、變動長度編碼等,是一種統計編碼。主要技術是檢測重複的比特或字符序列,並用它們的出現次數取而代之。比較適合於二值圖像的編碼,但是不適用於連續色調圖像的壓縮,例如日常生活中的照片。為了達到較好的壓縮效果,有時行程編碼和其他一些編碼方法混合使用。
[1]
該壓縮編碼技術相當直觀和經濟,運算也相當簡單,因此解壓縮速度很快。RLE壓縮編碼尤其適用於計算機生成的圖形圖像,對減少存儲容量很有效果。
- 中文名
- 行程編碼
- 外文名
- Run-Length Encoding(RLE)
- 又 稱
- 遊程編碼、行程碼、行程長度編碼
- 應 用
- 計算機圖形圖像
- 特 點
- 無失真編碼
行程編碼基本介紹
行程編碼(Run-length Coding)是相對簡單的編碼技術,主要思路是將一個相同值的連續串用一個代表值和串長來代替。例如,有一個字符串“aaabccddddd”,經過行程編碼後可以用“3a1b2c5d”來表示。對圖像編碼來説,可以定義沿特定方向上具有相同灰度值的相鄰像素為一輪,其延續長度稱為延續的行程,簡稱為行程或遊程。例如,若沿水平方向有一串M個像素具有相同的灰度N,則行程編碼後,只傳遞2個值(N,M)就可以代替M個像素的M個灰度值N。
[2]
在此方式下每兩個字節組成一個信息單元。第一個字節給出其後面相連的象素的個數。第二個字節給出這些象素使用的顏色索引表中的索引。例如:信息單元03 04,03表示其後的象素個數是3個,04表示這些象素使用的是顏色索引表中的第五項的值。壓縮數據展開後就是04 04 04 。同理04 05 可以展開為05 05 05 05。信息單元的第一個字節也可以是00,這種情況下信息單元並不表示數據單元,而是表示一些特殊的含義。這些含義通常由信息單元的第二個字節的值來描述。
行程編碼基本原理
行程編碼也叫作RLE壓縮編碼,其中RLE是Run-Length-Encoding的縮寫,這種壓縮方法是最簡單的圖像壓縮方法。
行程編碼的基本原理是在給定的數據圖像中尋找連續的重複數值,然後用兩個字符取代這些連續值。例如,一串字母表示的數據為“aaabbbbccccdddeeddaa”,經過遊程編碼處理可表示為“3a4b4c3d2e2d2a”。
對於數字圖像而言,同一幅圖像某些連續的區域顏色相同,即在這些圖像中,許多連續的掃描都具有同一種顏色,或者同一掃描行中許多連續的像素都具有同樣的顏色值。在這種情況下,只要存儲一個像素的顏色值、相同顏色像素的位置以及相同 顏色的像素數目即可,對數字圖像的這種編碼稱為行程編碼,把具有相同灰度值(顏色值)的相連像素序列稱為一個行程。
[3]
對於簡單的灰度圖像,行程編碼的數據結構如表6.2-1所列。
行程長度隱藏在起始座標中,不必單獨列出。
行程編碼分類
行程編碼分為定長行程編碼和變長行程編碼兩種。定長行程編碼是指編碼的行程所使用的二進制位數固定。如果灰度連續相等的個數超過了固定二進制位數所能表示的最大值,則進行下一輪行程編碼。變長行程編碼是指對不同範圍的行程使用不同位數的二進制位數進行編碼,需要增加標誌位來表明所使用的二進制位數。
[2]
行程編碼一般不直接應用於多灰度圖像,但比較適合於二值圖像的編碼。為了達到較好的壓縮效果,有時行程編碼與其他一些編碼方法混合使用。例如,在JPEG中,行程編碼和DCT及哈夫曼編碼一起使用,先對圖像分塊處理,然後對分塊進行DCT,量化後的頻域圖像數據做Z形掃描,再做行程編碼,對行程編碼的結果再進行哈夫曼編碼。
[2]
行程編碼技術特點
RLE是一種壓縮技術,而且這種編碼技術相當直觀,也非常經濟。RLE所能獲得的壓縮比有多大,這主要是取決於圖像本身的特點。如果圖像中具有相同顏色的圖像塊越大,圖像塊數目越少,獲得的壓縮比就越高。反之,壓 縮比就越小。
[4]
譯碼時按照與編碼時採用的相同規則進行,還原後得到的數據與壓縮前的數據完全相同。因此,RLE是無損壓縮技術。
RLE壓縮編碼尤其適用於計算機生成的圖像。對減少圖像文件的存儲空間非常有效,然而RLE對顏色豐富的自然圖像顯得力不從心,在同一行上具有相同顏色的連續像素往往很少,而連續幾行都具有相同顏色值的連續行數就更少。如果仍然使用RLE編碼方法,不僅不能壓縮圖像數據,反而可能使原來的圖像數據變得更大,注意,這並不是説RLE編碼方法不適用於自然圖像的壓縮,相反,在自然圖像的壓縮中還少不了RLE,只不過是不能單獨使用RLE—種編碼方法,需要和其他的壓縮編碼技術聯合應用。
[4]
行程編碼三維行程編碼
所謂三維行程編碼就是將三維表示轉換成一維表示,從而實現數據壓縮的方法。在壓縮過程中對屬性值相同的連續編碼進行壓縮,同時保證空間關係沒有任何損失。在三維行程編碼中,葉節點採用與線性八叉樹相同的地址碼,即Morton碼。十進制的Morton碼是使用最廣泛的一種方法,它具有線性八叉樹編碼的功能,但比常規八叉樹和基於八進制的線性八叉樹更有優勢。由於十進制是一組連續的自然數,其中的順序是一種空間最近關係。當採用自然數編碼時,可以直接用Morton碼作為域性值數組的下標。按照地址碼的大小進行排序,得到的序列可以看成是一組子序列的集合,其中的每一個子序列對應於一組屬性值相同的葉節點。對於每一個子序列只保留其第一個元素,刪除其他元素,即可得到八叉樹的三維行程編碼表示。三維行程編碼是線性八叉樹的進一步壓縮,其壓縮的元素可以通過相鄰兩個三維行程編碼的元素進行恢復。
[5]
三維行程編碼具有以下優點:
②由於它和線性八叉樹一樣不需要記錄中間節點,從而省去了大量的中間節點指針的存儲空間;合併過程按照這種自然數的順序節省了排序工作,在存儲空間上更節省。
行程編碼應用實例
行程編碼的M語言實現如例程6.2-1所示。
【例程6.2-1】
clear
讀入圖像並進行灰度轉換
I=imread('pears.png');
imshow(I)
IGRAY=rgb2gray(I)
[m n]=size(IGRAY)
建立數組RLEEcod,其中元素排列形式為[行程起始行座標、行程列座標、灰度值]
c=I(1,1);RLEcode(1,1:3)=[1 1 c];
t=2;
進行行程編碼
for k=1:m
for j=1:n
if(not(and(k = =1,j= =1)))
if(not(I(k,j)= =c))
RLEcode(t,1:3)=[k j I(k,j)]
c=I(k,j);
t=t+1;
end
end
end
end
對例程6.2-1分析可知,待壓縮的灰度圖像大小為486×732=355754個字節,而輸出行程編碼的數組為925719個字節,比原來圖像佔用的儲存空間還要大,可見對該幅圖像採用行程編碼的效果並不好。
[3]
對6.2-1稍作修改,使得待壓縮編碼的圖像為二值圖像,如例程6.2-2所示,再來看行程編碼的壓縮效果。
【例程6.2-2】
clear
讀入圖像並轉換成二值圖像
I=imread('pears.png');
imshow(I)
IBW=im2bw(I);
[m n]=size(IBW);
建立數組RLEEcod,其中元素排列形式為[行程起始行座標、行程列座標、灰度值]
c=I(1,1);RLEcode(1,1:3)=[1 1 c];
t=2;
進行行程編碼
for k=1:m
for j=1:n
if(not(and(k = =1,j= =1)))
if(not(IBW(k,j)= =c))
RLEcode(t,1:3)=[k j IBW(k,j)]
c=IBW(k,j);
t=t+1;
end
end
end
end
對二值化圖像進行行程編碼。壓縮後的輸出行程編碼的數組為31170,為原來存儲圖像所需空間的8.8%,取得了良好的壓縮效果。