遊程長度編碼

遊程長度編碼（run-length code）是柵格數據壓縮的重要編碼方法，它的基本思路是：對於一幅柵格圖像，常常有行（或列）方向上相鄰的若干點具有相同的屬性代碼，因而可採取某種方法壓縮那些重複的記錄內容。其編碼方案是，只在各行（或列）數據的代碼發生變化時依次記錄該代碼以及相同代碼重複的個數，從而實現數據的壓縮。

基本介紹

• 中文名：遊程長度編碼
• 外文名：run-length code
• 類型：科技術語
• 適用：信息

遊程長度

資訊時代，人們對使用計算機獲取信息、處理信息的依賴性越來越高。多媒體計算機系統面臨的是數值、文字、語言、音樂、圖形、動畫、靜圖像、電視視頻圖像等多種媒體承載的由模擬量轉化成數字量信息的吞吐、存儲和傳輸的問題。數位化了的視頻和音頻信號的數量之大是驚人的，與硬體技術所能提供的計算機存儲資源和網路頻寬之間有很大差距。這樣，對多媒體信息的存儲和傳輸造成了很大困難，成為阻礙人們有效獲取和利用信息的一個瓶頸問題。多媒體信息使用的前提是進行有效的壓縮。例如一段時間長度為1min，圖像尺寸為640×480 pixels，每秒播放30幀的非壓縮彩色(24位真彩色)視頻的信息量為：640×480×3×30×60=1658880000Bytes，約為1.6GB(未含音頻信息的容量)，如果用650MB的CD-R來存放，需要3張。由此可見，在視頻信息的處理及套用過程中壓縮及解壓縮技術是十分必要的[3]。數據壓縮技術主要採用兩種方法，一種是“保真率”較高的無損壓縮法；另一種是以損失信息細節而換取較高壓縮比的有損壓縮法。無損壓縮雖然壓縮比不是很高，但還原後的檔案與原數據檔案完全相同，從而保證了信息細節的不失真，常用的方法有統計式壓縮法和字典式壓縮法，統計式壓縮法的編碼方案主要是霍夫曼(Huffman)編碼、算術編碼(AC)和遊程長度編碼(RLC)。其中，遊程長度編碼是一種十分簡單的壓縮方法，編碼/解碼的速度也非常快，因此得到了廣泛的套用。許多圖形和視頻檔案，如BMPTIF及AVI等，都採用了這種壓縮方法，尤其適用於文本(檔案)數據壓縮，它主要是去除文本中的冗餘字元或位元組中的冗餘位以達到減少數據檔案所占的存儲空間的目的。

遊程長度RL(Run-Length)，簡稱遊程或游長，指的是由字元(或信號取樣值)構成的數據流中各個字元重複出現而形成的字元的長度。如果給出了形成串的字元，串的長度及串的位置，就能恢復出原來的數據流，遊程長度編碼(RLC)就是用二進制碼字給出這些信息的一類方法。

遊程長度編碼原理

遊程長度編碼的主要思想是將一個相同值的連續串用其值和串長(重複的個數)的數對二元組來替代。例如，在圖像編碼中，可以定義沿特定方向上具有相同灰度值的相鄰像素為一輪，其延續的長度稱之為延續的行程，即遊程。遊程終點位置由前一遊程終點的相對距離確定，這樣就可以由灰度遊程串來表示圖像數據。例如，若沿水平方向有一串M個像素具有相同的灰度N，則按遊程長度編碼後，只傳遞兩個值(N，M)就可以代替這M個像素的M個灰度值N。簡單來說，遊程長度編碼的主要任務是統計連續相同字元的個數，解碼時要根據字元及連續相同字元的個數，恢復原來的數據。

長度編碼只用了40個整數就可以表示，而如果用前述的直接編碼卻需要64個整數表示，可見遊程長度編碼壓縮數據是十分有效又簡便的。事實上，壓縮比的大小是與圖的複雜程度成反比的，在變化多的部分，遊程數就多，變化少的部分遊程數就少，圖件越簡單，壓縮效率就越高。

遊程長度編碼在柵格加密時，數據量沒有明顯增加，壓縮效率較高，且易於檢索，疊加合併等操作，運算簡單，適用於機器存貯容量小，數據需大量壓縮，而又要避免複雜的編碼解碼運算增加處理和操作時間的情況。

[font id="zoom" class="zoom"]遊程長度RL (Run—Length)，簡稱遊程或游長，指的是由字元(或信號取樣值)構成的數據流中各個字元重複出現而形成的字元的長度．如果給出了形成申的字元，申的長度及申的位置，就能恢復出原來的數據流，遊程長度編碼(RLC)就是用二進制碼字給出這些信息的一類方法。遊程長度編碼的主要思想是將一個相同值的連續申用其值和申長(重複的個數)的數對二元組來替代．例如，在圖像編碼中，可以定義沿特定方向上具有相同灰度值的相鄰像素為一輪，其延續的長度稱之為延續的行程，即遊程．遊程終點位置由前一遊程終點的相對距離確定，這樣就可以由灰度遊程串來表示圖像數據．例如，若沿水平方向有一申M 個像素具有相同的灰度N，則按遊程長度編碼後，只傳遞兩個值(N，M )就可以代替這M個像素的M個灰度值N。簡單來說，遊程長度編碼的主要任務是統計連續相同字元的個數，解碼時要根據字元及連續相同字元的個數，恢復原來的數據．在多媒體信息量激增、網路特性和速度都飛速提高的今天，遊程長度編碼是一種十分簡單的壓縮方法，編碼/解碼的速度也非常快，可廣泛套用於多媒體信息的存儲，傳輸。

遊程壓縮模型

在遊程長度編碼(RLC)中用3個位元組表示一個字元串：第一個位元組是壓縮指示字元Sc，第二個位元組記錄連續出現的字元，第三個位元組記錄重複字元出現的次數。可見，只有當RL>3時進行數據壓縮才有意義，因此，編碼時首先要判斷RL值，然後再決定是否進行遊程長度編碼(RLC)；解碼時則需根據每一字元後是否為Sc，再決定其下一字元的含義，如下圖所示例如：設一幅二維黑白圖像F(i，j)的各像素的灰度值如下所示，規定沿水平方向從左到右掃描，則掃描後得到的遊程為右邊的13個二元組。由上例可見：

1. 該圖像是由8行、8列共64個像素組成；
   
2. 像素的灰度值變化範圍是：0～8；由於是黑白圖，顏色過渡只是黑※灰※白，按人眼解析度，用8bit即可(28=256)。
   
3. 第一行8個像素灰度值相同，只傳(8，8)；第二行只傳(8，4)(7，4)；第三行只傳(7，8)；第四行只傳(6，4)(5，4)；第五行時只傳(5，5)(3，3)；第六行只傳(3，8)；第七行只傳(3，3)(2，5)；第八行只傳(1，4)(0，4)。這樣，64個像素只需傳13個數據對即可，比一個個像素傳送要節省很多時間。一般情況下，編碼時間=(2～4)解碼時間。
   

例子

對圖1所示的柵格數據，可沿行方向進行如下遊程長度編碼：

圖1:原始柵格數據

(9,4),(0,4),(9,3),(0,5),(0,1)(9,2),(0,1),(7,2),(0,2),(0,4),(7,2),(0,2),(0,4),(7,4),(0,4),(7,4) ,(0,4),(7,4) ,(0,4),(7,4)