鄭靜 王騰

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

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

中圖分類號(hào)：TP1 8 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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ù)量的圖像信息會(huì)給儲(chǔ)存器的儲(chǔ)存容量，通信信道的帶寬以及計(jì)算機(jī)的處理速度增加極大的壓力，單純靠增加儲(chǔ)存容量，提高信道帶寬以及計(jì)算機(jī)的處理速度等方法來(lái)解決這個(gè)問(wèn)題是不現(xiàn)實(shí)的，只能從軟件方面著手，即壓縮。研究結(jié)果表明，選用合適的數(shù)據(jù)壓縮技術(shù)，有可能將原始數(shù)據(jù)量壓縮為原來(lái)的二分之一左右。

1 RLE編碼壓縮算法概述

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

1.1 一般的RLE壓縮算法

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

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

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

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

經(jīng)過(guò)壓縮處理后，圖像數(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三個(gè)值互不相同，只能保持原狀，接著連續(xù)重復(fù)70個(gè)0x27，這已經(jīng)超出最大值63，所以，必須用兩組壓縮碼來(lái)代表。最后三個(gè)數(shù)并不相同，卻用三組壓縮碼代替，是為了避免解壓縮數(shù)據(jù)時(shí)發(fā)生錯(cuò)誤，誤將0xD7和0xD5譯為55個(gè)0xD5，因此，遇到圖像數(shù)據(jù)大于或等于0xC0 （192）時(shí)，即使不是連續(xù)重復(fù)出現(xiàn)的數(shù)據(jù)，也必須用一組壓縮碼來(lái)代表一個(gè)Byte值。

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

1.2 RLE4壓縮算法

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

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

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

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

4） 0x00 N…表示有N點(diǎn)不同數(shù)值的圖像數(shù)據(jù)。如果不同數(shù)值的圖像數(shù)據(jù)為奇數(shù)個(gè)字節(jié)，必須在數(shù)據(jù)末端加入0x00，以維持壓縮數(shù)據(jù)的長(zhǎng)度為偶數(shù)個(gè)字節(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)過(guò)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非常類似，只是計(jì)數(shù)方式不同。在RLE8中，壓縮碼的第一個(gè)字節(jié)代表重復(fù)數(shù)據(jù)個(gè)數(shù)，RLE8 壓縮算法只用于256色的圖像壓縮，而256色圖像正好是一個(gè)字節(jié)存儲(chǔ)一點(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ū)域時(shí)，RLE編碼產(chǎn)生的壓縮率很高。但如果圖像中很少有兩個(gè)相鄰的像素的灰度值相同時(shí)，RLE非但不能壓縮，還會(huì)造成圖像數(shù)據(jù)量增大的情況。

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

2.1顏色表

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

2.2索引表

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

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

1） RLE算法的思想

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

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

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

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

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

顏色表：

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

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

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

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

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

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

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

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

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

3.1.1獲取顏色表、檢索表

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

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

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

3.2獲取圖片矩陣

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

3.3 量化

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

3.4寫配置文件

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

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

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

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

3.5解壓檢索表

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

3.6解壓配置文件

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

3.7 還原圖像

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

4 壓縮率對(duì)比

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

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

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

5 結(jié)束語(yǔ)

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