遊程長度編碼

信息時代，人們對使用計算機獲取信息、處理信息的依賴性越來越高。多媒體計算機系統面臨的是數值、文字、語言、音樂、圖形、動畫、靜圖像、電視視頻圖像等多種媒體承載的由模擬量轉化成數字量信息的吞吐、存儲和傳輸的問題。數字化了的視頻和音頻信號的數量之大是驚人的，與硬件技術所能提供的計算機存儲資源和網絡帶寬之間有很大差距。這樣，對多媒體信息的存儲和傳輸造成了很大困難，成為阻礙人們有效獲取和利用信息的一個瓶頸問題。多媒體信息使用的前提是進行有效的壓縮。例如一段時間長度為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)就是用二進制碼字給出這些信息的一類方法 ^[1]  。

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

長度編碼只用了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，再決定其下一字符的含義，如圖1所示例如：設一幅二維黑白圖像F(i，j)的各像素的灰度值如下所示，規定沿水平方向從左到右掃描，則掃描後得到的遊程為右邊的13個二元組。由上例可見：

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

(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)