行程編碼（Run Length Encoding，RLE), 又稱遊程編碼、行程長度編碼、變動長度編碼 等，是一種統計編碼。主要技術是檢測重複的比特或字元序列，並用它們的出現次數取而代之。比較適合於二值圖像的編碼，但是不適用於連續色調閣像的壓縮，例如日常生活中的照 片。為了達到較好的壓縮效果，有時行程編碼和其他一些編碼方法混合使用。
該壓縮編碼技術相當直觀和經濟，運算也相當簡單，因此解壓縮速度很快。RLE壓縮編碼尤其適用於計算機生成的圖形圖像，對減少存儲容量很有效果。
基本介紹
- 中文名：行程編碼
- 外文名：Run-Length Encoding（RLE）
- 又稱：遊程編碼、行程碼、行程長度編碼
- 套用：計算機圖形圖像
- 特點：無失真編碼
概述,基本原理,分類,技術特點,三維行程編碼,套用實例,
概述
行程編碼（Rim-length Coding)是相對簡單的編碼技術，主要思路是將一個相同值 的連續串用一個代表值和串長來代替。例如，有一個字元串“aaabccddddd”，經過行程 編碼後可以用“3a1b2c5d”來表示。對圖像編碼來說，可以定義沿特定方向上具有相同灰度值的相鄰像素為一輪，其延續長度稱為延續的行程，簡稱為行程或遊程。例如，若沿水平方向有一串M個像素具有相同的灰度N，則行程編碼後，只傳遞2個值（N,M) 就可以代替M個像素的M個灰度值N.
在此方式下每兩個位元組組成一個信息單元。第一個位元組給出其後面相連的象素的個數。第二個位元組給出這些象素使用的顏色索引表中的索引。例如：信息單元03 04，03表示其後的象素個數是3個，04表示這些象素使用的是顏色索引表中的第五項的值。壓縮數據展開後就是04 04 04 .同理04 05 可以展開為05 05 05 05. 信息單元的第一個位元組也可以是00，這種情況下信息單元並不表示數據單元，而是表示一些特殊的含義。這些含義通常由信息單元的第二個位元組的值來描述。
行程編碼對傳輸差錯很敏感，如果其中一位符號發生錯誤，就會影響整個編碼序列的正確性，使行程編碼無法還原回原始數據，因此一般要用行同步、列同步的方法.把差錯控制 在一行一列之內。
基本原理
行程編碼也叫作RLE壓縮編碼，其中RLE是Run-Length-Encoding的縮寫， 這種壓縮方法是最簡單的圖像壓縮方法。
行程編碼的基本原理是在給定的數據圖像中尋找連續的重複數值，然後用兩個字元取代這些連續值。例如，一串字母表示的數據為“aaabbbbccccdddeeddaa”，經過 遊程編碼處理可表示為“3a4b4c3d2e2d2a”。
對於數字圖像而言，同一幅圖像某些連續的區域顏色相同，即在這些圖像中，許 多連續的掃描都具有同一種顏色，或者同一掃描行中許多連續的像素都具有同樣的 顏色值.在這種情況下，只要存儲一個像素的顏色值、相同顏色像素的位置以及相同 顏色的像素數目即可，對數字圖像的這種編碼稱為行程編碼，把具有相同灰度值（顏 色值）的相連像素序列稱為一個行程。
對於簡單的灰度圖像，行程編碼的數據結構如表6.2-1所列.
行程長度隱藏在起始坐標中，不必單獨列出。
分類
行程編碼分為定長行程編碼和變長行程編碼兩種。定長行程編碼是指編碼的行程 所使用的二進制位數固定。如果灰度連續相等的個數超過了固定二進制位數所能表示的最大值，則進行下一輪行程編碼。變長行程編碼是指對不同範圍的行程使用不同位 數的二進制位數進行編碼，需要增加標誌位來表明所使用的二進制位數。
行程編碼一般不直接套用於多灰度圖像，但比較適合於二值圖像的編碼。為了達到較好的壓縮效果，有時行程編碼與其他一些編碼方法混合使用.例如，在JPEG中， 行程編碼和DCT及哈夫曼編碼一起使用，先對圖像分塊處理，然後對分塊進行DCT，量化後的頻域圖像數據做Z形掃描，再做行程編碼，對行程編碼的結果再進行哈夫曼編碼。
技術特點
RLE是一種壓縮技術，而且這種編碼技術相當直 觀，也非常經濟。RLE所能獲得的壓縮比有多大，這主要是取決於圖像本身的特點.如 果圖像中具有相同顏色的圖像塊越大，圖像塊數目越少，獲得的壓縮比就越高.反之，壓 縮比就越小。
解碼時按照與編碼時採用的相同規則進行，還原後得到的數據與壓縮前的數據完全 相同.因此，RLE是無損壓縮技術.
RLE壓縮編碼尤其適用於計算機生成的圖像.對減少圖像檔案的存儲空間非常有 效，然而.RLE對顏色豐富的自然圖像顯得力不從心，在同一行上具有相同顏色的 連續像素往往很少，而連續幾行都具有相同顏色值的連續行數就更少.如果仍然使用RLE編碼方法，不僅不能壓縮圖像數據，反而可能使原來的圖像數據變得更大，注意，這並不是說RLE編碼方法不適用於自然圖像的壓縮，相反，在自然圖像的壓縮中還少不了 RLE,只不過是不能單獨使用RLE—種編碼方法，需要和其他的壓縮編碼技術聯合套用。
三維行程編碼
所謂三維行程編碼就是將三維表示轉換成一維表示，從而實現數據壓縮的方法。在壓縮過程中對屬性值相同的連續編碼進行壓縮，同時保證空間關係沒有任何損失。在三維行程編碼中，葉節點採用與線性八叉樹相同的地址碼，即Morton碼。十進制的Morton碼是現在使用最廣泛的一種方法，它具有線性八叉樹編碼的功能，但比常規八叉樹和基於八進制的線性八叉樹更有優勢。由於十進制是一組連續的自然數，其中的順序是一種空間最近關係。當採用自然數編碼時，可以直接用Morton 碼作為域性值數組的下標。按照地址碼的大小進行排序，得到的序列可以看成是一組子序列的集合，其中的每一個子序列對應於一組屬性值相同的葉節點。對於每一個子序列只保留其第一個元素，刪除其他元素， 即可得到八叉樹的三維行程編碼表示。三維行程編碼是線性八叉樹的進一步壓縮，其壓縮的元素可以通過相鄰兩個三維行程編碼的元素進行恢復。
三維行程編碼具有以下優點：
①由於採用自然數編碼排列，提高了檢索和査詢速度，對於插入、 刪除等操作更為簡便，而且它與線性八叉樹的轉換也十分方便。
②由於它和線性八叉樹一樣不需要記錄中間節點，從而省去了大量的中間節點指針的存儲空間；合併過程按照這種自然數的順序節省了排序工作，在存儲空間上更節省。
③它以十進制為編碼，比八進制更符合人們的使用習慣；在生成速度和使用習慣上，也表現得更快、更方便。
④當檢査相鄰柵格的屬性以判斷能否合併時，它不需要排序，從而節省了排序時間。Morton碼的建立過程類似於基於八進制的線性八叉樹編碼。
套用實例
行程編碼的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個位元組，比原來圖像占用的儲存空間還要大，可見對該幅圖像採用行程編碼的效果並不好。
對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%，取得了良好的壓縮效果。
通過對例程6.2-1和例程6.2-2的運行結果進行分析可知，行程編碼對於僅包含很少幾個灰度級的圖像，特別是二值圖像，壓縮效果好.特別地，該編碼方法對 單一顏色背景下物體的圖像.具有較高的壓縮比。對於其他情況下的圖像，其壓縮比較低，甚至在最壞的情況下，比如圖像的每一個像素都與周圍的像素不同，行程編碼甚至可將檔案的大小加倍，達不到壓縮編碼的目的。
