RLE圖像壓縮算法優(yōu)化研究與應(yīng)用

鄭靜 王騰

摘要：該文對比了傳統(tǒng)的RLE（游程編碼）算法，通過對RLE壓縮編碼的分析，得出RLE壓縮算法存在很大的優(yōu)化空間，并實(shí)現(xiàn)了優(yōu)化后的RLE圖像壓縮算法，且著重介紹了這種算法的優(yōu)缺點(diǎn)和優(yōu)化方向。

關(guān)鍵詞：RLE算法；圖像壓縮算法；算法優(yōu)化

中圖分類號：TP1 8 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2014）25-5981-04

RLE Image Compression Algorithm Optimization Research and Application

ZHENG Jing ， WANG Teng

（Yangtze University college of arts and sciences， Jingzhou， Hubei 434020， China）

Abstract： Compared to the traditional RLE algorithm， through analysis on compression coding of RLE ， the optimization space RLE compression algorithms exist， follow RLE image compression algorithm to achieve the optimized， and emphatically introduces the advantages and disadvantages of this algorithm and optimization direction.

Key words： RLE ； image compression algorithm； algorithm optimization

大數(shù)據(jù)量的圖像信息會給儲存器的儲存容量，通信信道的帶寬以及計算機(jī)的處理速度增加極大的壓力，單純靠增加儲存容量，提高信道帶寬以及計算機(jī)的處理速度等方法來解決這個問題是不現(xiàn)實(shí)的，只能從軟件方面著手，即壓縮。研究結(jié)果表明，選用合適的數(shù)據(jù)壓縮技術(shù)，有可能將原始數(shù)據(jù)量壓縮為原來的二分之一左右。

1 RLE編碼壓縮算法概述

RLE（Run-Length Encodeing）編碼是windows系統(tǒng)中使用的一種圖像文件壓縮方法，由于這種壓縮格式使用不廣泛，一般文獻(xiàn)中介紹得很少，且一般的圖像處理軟件也不支持這種壓縮格式。但是，WINDOWS 3.X和WINDOWS 95的啟動提示信息的圖像文件都是采用這種壓縮格式存儲的，而且，這種格式存儲的圖像文件讀取速度快，保真程度高，特別適合于信息量大、保真程度高的信息顯示系統(tǒng)中。RLE方法主要分為一般的RLE算法、RLE4算法和RLE8算法。

1.1 一般的RLE壓縮算法

當(dāng)圖像數(shù)據(jù)出現(xiàn)連續(xù)重復(fù)的數(shù)值時，在這兩個數(shù)值的前面，加上一個長度值，表示這個數(shù)值重復(fù)的次數(shù)。用這兩字節(jié)代表一串連續(xù)重復(fù)值的數(shù)據(jù)，第一個字節(jié)代表一串相同數(shù)據(jù)的個數(shù)；第二個字節(jié)代表這串字節(jié)的值。此外，在選定第一個字節(jié)時，還必須把最高位的兩個Bits當(dāng)作標(biāo)志，將這兩個Bits都設(shè)成1，即11000000（0xC0），其余6個Bits的值，才是代表相同數(shù)據(jù)的個數(shù)，所以其最大值只能到63，也就是說，這兩個字節(jié)最多能取代63個連續(xù)重復(fù)出現(xiàn)的字節(jié)。

例如，有下面一串圖像數(shù)據(jù)等待壓縮處理：

0x19 0x19 0x19 0x19 0x19 0x19 0x19 0x19 0x19 0x54

0x35 0x1C 0x27...（連續(xù)重復(fù)70個0x27） 0xD7 0xD5 0xE7

經(jīng)過壓縮處理后，圖像數(shù)據(jù)變?yōu)椋?/p>

0xC9 0x19 0x54 0x35 0xlC 0xFF 0x27 0xC7

0x27 0xCl 0xD7 0xCl 0xD5 0xCl 0xE7

0x19連續(xù)重復(fù)出現(xiàn)9次，以0xC9和0x19取代，而0x54， 0x35，0x1C三個值互不相同，只能保持原狀，接著連續(xù)重復(fù)70個0x27，這已經(jīng)超出最大值63，所以，必須用兩組壓縮碼來代表。最后三個數(shù)并不相同，卻用三組壓縮碼代替，是為了避免解壓縮數(shù)據(jù)時發(fā)生錯誤，誤將0xD7和0xD5譯為55個0xD5，因此，遇到圖像數(shù)據(jù)大于或等于0xC0 （192）時，即使不是連續(xù)重復(fù)出現(xiàn)的數(shù)據(jù)，也必須用一組壓縮碼來代表一個Byte值。

一般的RLE算法只能壓縮處理連續(xù)重復(fù)同一數(shù)值的數(shù)據(jù)串，若是遇到數(shù)值不同的連續(xù)數(shù)據(jù)，就只能將數(shù)據(jù)原封不動地存入圖像文件內(nèi)，也就是說，一般RLE無法壓縮處理不同值的數(shù)據(jù)串。在特殊情況下，經(jīng)過一般RLE壓縮算法處理的圖像數(shù)據(jù)，有時不但不減少，反而比壓縮前更多，所以，有必要對該算法進(jìn)行改進(jìn)。

1.2 RLE4壓縮算法

RLE4壓縮算法是在改進(jìn)一般的RLE壓縮算法的基礎(chǔ)上而產(chǎn)生的，它和一般的RLE有相同之處，它仍以兩個字節(jié)代表一串相同數(shù)值的圖像數(shù)據(jù)。但是，RLE4壓縮算法的計數(shù)方式和識別碼與一般的RLE有所不同。在RLE4中，第一個字節(jié)表示圖像數(shù)據(jù)的點(diǎn)數(shù)，而非字節(jié)數(shù)；RLE4的識別碼也有四種，每種識別碼的第一個字節(jié)必須為零，其表示方式如下：

1） 0x00 0x00表示一行圖像的結(jié)束，RLE4壓縮算法將一行視為一個壓縮單元，每行經(jīng)過壓縮后，都會在壓縮數(shù)據(jù)的末尾加入0x00 0x00兩個字節(jié)。

2） 0x00 0x01表示所有圖像數(shù)據(jù)的結(jié)束。

3） 0x00 0x02 X Y表示向右移動X點(diǎn)，向下移動Y點(diǎn)。這是當(dāng)背景畫面確定之后，想在背景的某塊區(qū)域加入圖像時，就先在這一塊圖像數(shù)據(jù)的前面，加上這段控制碼。

4） 0x00 N…表示有N點(diǎn)不同數(shù)值的圖像數(shù)據(jù)。如果不同數(shù)值的圖像數(shù)據(jù)為奇數(shù)個字節(jié)，必須在數(shù)據(jù)末端加入0x00，以維持壓縮數(shù)據(jù)的長度為偶數(shù)個字節(jié)。

如有以下原始數(shù)據(jù)：

第一列 0x36 0x36 0x36 0x32 0x83 0x51 0x27 0x27…0x27 0x27 0x27

第二列 0x96 0x98 0x42 0x17 0x77 0x77 0x77 0x77…0x62 0x62 0x81

經(jīng)過RLE4壓縮后變?yōu)椋?/p>

第一列 0x03 0x36 0x00 0x06 0x32 0x83 0x51 0x00 0x04 0x27… 0x06 0x27 0x00 0x00

第二列 0x00 0x0c 0x96 0x98 0x42 0x17 0x08 0x77…

0x04 0x77 0x02 0x81 0x00 0x00 0x00 0x0l

1.3 RLE8壓縮算法

RLE8壓縮算法與RLE4非常類似，只是計數(shù)方式不同。在RLE8中，壓縮碼的第一個字節(jié)代表重復(fù)數(shù)據(jù)個數(shù)，RLE8 壓縮算法只用于256色的圖像壓縮，而256色圖像正好是一個字節(jié)存儲一點(diǎn)。從下面的數(shù)據(jù)可以清楚的看到RLE4和RLE8的區(qū)別：

原始數(shù)據(jù) 0x82 0x82 0x82 0x82 0x96 0x46 0x33

RLE4壓縮數(shù)據(jù) 0x08 0x82 0x00 0x06 0x96 0x46 0x33 0x00

RLE8壓縮數(shù)據(jù) 0x04 0x82 0x00 0x03 0x96 0x46 0x33 0x00

1.4 RLE編碼的優(yōu)缺點(diǎn)

當(dāng)圖像中存在很多塊顏色相同的大面積區(qū)域時，RLE編碼產(chǎn)生的壓縮率很高。但如果圖像中很少有兩個相鄰的像素的灰度值相同時，RLE非但不能壓縮，還會造成圖像數(shù)據(jù)量增大的情況。

2 RLE優(yōu)化算法的總體設(shè)計

2.1顏色表

圖像每一個像素都可用RGB值來表示，該文在量化環(huán)節(jié)取B通道顏色，解壓時將B通道的顏色賦到三個通道中，就形成了一張灰度圖像。由于僅取B通道顏色，量化后顏色種類較少，為了用最少的存儲空間來表示顏色，就必須有一個顏色對照表。例如：現(xiàn)在有兩種顏色0和255，用顏色存儲，需要8個bit，用索引存儲，只需要一個bit（0代表0色，1代表255色）。

2.2索引表

索引表和顏色表配合使用，索引表中儲存的是相應(yīng)顏色在顏色表中的位置。索引表的長度為圖片的長乘以寬，所以壓縮圖片即是壓縮索引表，由于索引表中存儲的是顏色位置，所以儲存的數(shù)值較小，經(jīng)量化后，還遠(yuǎn)遠(yuǎn)小于一個字節(jié)能表示的最大長度，存儲時只需要用少量的bit位即可表示相應(yīng)的顏色。

2.3 RLE算法的優(yōu)化

1） RLE算法的思想

將一行中顏色值相同的相鄰像素用一個計數(shù)值和顏色值來代替。一組數(shù)據(jù)需要兩個字節(jié)存儲，其中計數(shù)值用一個字節(jié)，顏色值用一個字節(jié)。

2） RLE優(yōu)化的過程

主要分兩步優(yōu)化RLE圖像壓縮編碼，第一步從圖像的冗余方面，第二步從存儲的方式方面。

圖像冗余方面，整張圖片轉(zhuǎn)換成一個連續(xù)的字符串，相對于以前逐行尋找規(guī)律，連續(xù)的字符串更容易尋找規(guī)律。存儲方式方面，優(yōu)化后的RLE，去掉開始標(biāo)志和結(jié)束標(biāo)志，擴(kuò)展了一個顏色表和一個檢索表。例如：圖片顏色矩陣

243 243 243 252 252 255 255 255 255 255 200

243 243 243 252 252 255 255 255 200 200 200

241 241 243 250 250 255 255 200 200 200 200

顏色表：

如直接存儲圖片矩陣需要33個字節(jié)，轉(zhuǎn)化成檢索表存儲（共6種顏色，每一種用3個bit存儲即可）只需要13個字節(jié)。所以使用顏色表和檢索表可提高壓縮效率，節(jié)約大量的存儲空間。

接下來，針對檢索表進(jìn)行壓縮，檢索表的壓縮，用到了RLE的思想，即相鄰連續(xù)位置（檢索表中存儲的是該顏色在顏色表中的位置），使用顏色數(shù)目和位置表示，上面例子用RLE編碼方式得到結(jié)果：3，0 2，1 5，2 1，3 3，0 2，1 3，2 3，3 2，4 1，0 2，6 2，2 4，3，如果直接用RLE編碼，需要26個字節(jié)存儲，反而擴(kuò)大了存儲空間。該文處理方式是根據(jù)編碼后得到的結(jié)果，分配存儲空間。從上面的結(jié)果，能得出最大數(shù)值為5，用3個bit即可表示，每個位置也只需要用3bit，一組數(shù)據(jù)6bit即可表示，該文的算法壓縮后占用存儲空間為：6bit×13=69bit=9byte。該文算法的總體壓縮率為9byte/33byte=27.27%。

綜上所述，該文算法最核心的地方就是根據(jù)顏色種類和表示連續(xù)顏色的數(shù)值自動選擇合理的存儲位數(shù)，其中如果連續(xù)數(shù)值過大，會對數(shù)值進(jìn)行分割，一組數(shù)據(jù)最大的存儲單位為8bit，超過8bit就分割成多組。算法最大的優(yōu)點(diǎn)和難點(diǎn)即是顏色和數(shù)值的存儲位數(shù)也不是固定的，而是根據(jù)圖片本身的情況，得到最優(yōu)的存儲方式，節(jié)約大量的存儲空間。

2.3 優(yōu)化后RLE算法優(yōu)勢

優(yōu)化后的RLE壓縮編碼相對于傳統(tǒng)的RLE壓縮編碼，對圖片適應(yīng)性更強(qiáng)，適用圖片范圍更大。優(yōu)化后的RLE，繼承了傳統(tǒng)RLE的優(yōu)勢，又在一定程度上避免了RLE編碼的缺陷，不會出現(xiàn)壓縮后比壓縮前文件還要大的情況。

2.4 與優(yōu)化后RLE壓縮率相關(guān)的因素

1） 顏色表的長度（圖片本身和量化情況決定）；2） 相鄰顏色連續(xù)的個數(shù)；3） 顏色個數(shù)儲存使用的bit位數(shù)。

3 RLE優(yōu)化算法與圖像壓縮的設(shè)計

3.1優(yōu)化的RLE編碼

3.1.1獲取顏色表、檢索表

首先對圖片矩陣進(jìn)行掃描，掃描第一個元素時，將第一個顏色寫到顏色表（temclr），并在檢索表（search）中寫入0（顏色表的1號位置即下標(biāo)為0的位置），后面掃描，每掃描一個元素，就到顏色表（temclr）中尋找是否有此元素顏色，如果沒有，則將新顏色寫到顏色表（temclr），并將此時寫到顏色表（temclr）中的位置保存到檢索表（search），如果有，將該顏色所在顏色表（temclr）的位置寫到檢索表（search）。掃描完成則檢索表（search）和顏色表（temclr）生成完成。

3.1.2 檢索表的優(yōu)化RLE編碼

此步驟主要實(shí)現(xiàn)對檢索表進(jìn)行RLE編碼，color_cishu變量即為計算后得到的表示位置數(shù)值的最大bit位數(shù)，代碼中用一個字節(jié)來表示顏色重復(fù)數(shù)目和顏色，其中位數(shù)按照顏色的種類分配。例如：二值圖像，顏色只需要一位來表示（0、1分別表示一種顏色），剩下的7位表示數(shù)目，那么一次能表示的最大個數(shù)為127。

3.2獲取圖片矩陣

加載BMP圖片，獲取圖片的長（iw）、寬（ih）和圖片矩陣灰度值的長串（mData）這些基本信息。這些信息會寫到配置文件中，還原圖片時需要用到這些信息。

3.3 量化

可分為兩步，第一步是計算顏色個數(shù)，第二步是量化。計算顏色個數(shù)，主要目的是根據(jù)顏色個數(shù)和選擇的壓縮級別進(jìn)行量化，例如：統(tǒng)計顏色種類為16，選擇一級壓縮，則此時不進(jìn)行任何量化，直接取該16種顏色；選擇選擇二級壓縮，那么必須根據(jù)這16種顏色量化成為8種。

3.4寫配置文件

分三個步驟，對應(yīng)配置文件主要存儲的三個信息，分別為圖片長寬、顏色個數(shù)和位數(shù)、顏色表。

第一步，將圖片長和寬寫到配置文件中，長和寬分別用兩個字節(jié)表示，所以能壓縮圖片最大的長寬都為65536（16bit能表示的最大值），“長”在配置文件中儲存的位置為第一個和第二個字節(jié)，第一個字節(jié)表示長的高8位，第二個字節(jié)表示長的低8位?！皩挕痹谂渲梦募袃Υ娴奈恢脼榈谌齻€和第四個字節(jié)，第三個字節(jié)表示寬的高8位，第四個字節(jié)表示寬的低8位。

第二步，將顏色個數(shù)和體現(xiàn)這些顏色所需要的最少位數(shù)寫到配置文件中，在配置文件中的位置為第五個和第六個字節(jié)，用for循環(huán)計算顏色表所需要的最少位數(shù)。

第三步，將獲取到的顏色表寫到配置文件中。

3.5解壓檢索表

解壓檢索表相當(dāng)于壓縮過程的反向執(zhí)行，讀出一個字節(jié)，還原其顏色，保存到pix中，讀取完成，則pix的大小為iw×ih，pix中保存的是顏色，不再是顏色表中的位置。

3.6解壓配置文件

讀取配置文件的信息時，讀出顏色表、顏色個數(shù)、存儲顏色的位數(shù)配合檢索表對圖像矩陣進(jìn)行還原，讀出的長和寬配合pix對圖像進(jìn)行還原。

3.7 還原圖像

還原圖像時，將b通道的顏色，賦予到其他通道中，三個通道顏色相同的是灰度圖像，所以本算法只適合灰度圖片的壓縮。

4 壓縮率對比

4.1經(jīng)典壓縮算法壓縮率表

4.2壓縮率對比小結(jié)

圖片顏色越簡單，各種壓縮編碼壓縮率越大。顏色復(fù)雜的圖片，LZW壓縮效果最好，經(jīng)過優(yōu)化的RLE排第二位，RLE編碼壓縮后比壓縮前文件更大；顏色分布較為簡單的圖片，優(yōu)化的RLE壓縮編碼壓縮效果最好，LZW壓縮效果其次，傳統(tǒng)的RLE編碼壓縮效果依然很差；二值圖像，哈夫曼壓縮效果最好，其次是優(yōu)化的RLE，效果最差的依然是傳統(tǒng)的RLE編碼。所以，優(yōu)化后的RLE編碼，適應(yīng)性最好，壓縮比率也較為可觀，較傳統(tǒng)的RLE，具有很大優(yōu)勢。

5 結(jié)束語

優(yōu)化后的RLE編碼較傳統(tǒng)RLE優(yōu)勢明顯，但不足之處也非常明顯，處理圖片有局限性，只適合處理灰度圖片，其他圖片會自動轉(zhuǎn)換成灰度圖片處理。量化算法還需要優(yōu)化，壓縮率大的時候，圖片失真較多，且難以還原。量化的優(yōu)化方向，主要是量化后顏色還可以盡可能多的還原，讓圖片盡可能少的失真。優(yōu)化后的RLE算法，雖說較為靈活，但存儲空間利用率并非達(dá)到了極致。優(yōu)化方向是將霍夫曼編碼整合進(jìn)去，實(shí)現(xiàn)存儲空間的最大利用率。該文算法壓縮的時候，對圖片進(jìn)行了三次掃描，對壓縮速度也有一定的影響。