霍夫曼編碼和游程編碼在圖像編碼中的應(yīng)用*

李 薇 胡偉文 沈 靜

(海軍工程大學(xué)理學(xué)院 武漢 430033)

1 傳真圖像數(shù)據(jù)的特點(diǎn)[1]

三類傳真機(jī)的主要特點(diǎn)之一是對(duì)圖像數(shù)據(jù)進(jìn)行編碼。雖然一幅圖像數(shù)據(jù)量很大,但其中有很大的信息多余度,這部分?jǐn)?shù)據(jù)可以不用傳輸。圖像信息的多余度可以用圖像的像素統(tǒng)計(jì)特性來(lái)說(shuō)明,包括像素本身出現(xiàn)的百分比和不同像素間的相關(guān)特性。統(tǒng)計(jì)表明黑像素出現(xiàn)的百分比與白像素出現(xiàn)的百分比有很大差別,相鄰像素之間的相關(guān)性也很強(qiáng)。例如用計(jì)算機(jī)對(duì)七種典型的傳真樣張作統(tǒng)計(jì),結(jié)果是:白像素平均出現(xiàn)的百分比是93.7%。即使在文字密度很大的樣張中,白像素出現(xiàn)的百分比也達(dá)到88.8,而黑像素只占11.2%。在這些像素中,約有2/3的黑像素是相鄰的,有97%以上的白像素是相連的。還有持續(xù)長(zhǎng)度的統(tǒng)計(jì)特性。總之,圖像中有許多特性可以通過(guò)統(tǒng)計(jì)而預(yù)測(cè)到,這些圖像特征信息是多余的,只需傳輸無(wú)法預(yù)測(cè)的圖像信息。

2 改進(jìn)的霍夫曼編碼(MHC)方法[2～4]

改進(jìn)的霍夫曼編碼以八張具有代表性的樣張為統(tǒng)計(jì)依據(jù),得出游程長(zhǎng)度的出現(xiàn)概率,然后,再編制霍夫曼(Huffman)碼表,這樣就擺脫了游程長(zhǎng)度的隨機(jī)性,難以獲得游程長(zhǎng)度出現(xiàn)概率的問(wèn)題。根據(jù)八張樣張統(tǒng)計(jì)出來(lái)的游程長(zhǎng)度出現(xiàn)概率發(fā)現(xiàn),游程長(zhǎng)度在0～63bit的居多,因此,就把每行 1728像素的游程長(zhǎng)度分為兩張統(tǒng)計(jì)表,一張是游程長(zhǎng)度在0～63bit間白、黑像素的游程長(zhǎng)度給出一個(gè)碼表,這就是終止碼表,另一張是像素游程長(zhǎng)度≥64的碼表,該像素的碼表就是形成碼表。這樣MH編碼實(shí)際上就是一個(gè)查表過(guò)程,即游程的碼字=形成碼+終止碼。

表1 改進(jìn)的Huffman碼表

每張的數(shù)據(jù)傳輸格式如圖1所示。

圖1 M H碼的數(shù)據(jù)傳輸格式

編碼舉例:白游程65(64+1)的編碼為“64”的形成碼 11011和“1”的終止碼 000111,也就是11011000111。

改進(jìn)的Huffman碼當(dāng)游程長(zhǎng)度較長(zhǎng)時(shí)碼字很長(zhǎng)。

3 一種改進(jìn)的游程編碼方法[5～9]

3.1 問(wèn)題的提出

從二進(jìn)制的表達(dá)方式可以得到啟發(fā):二進(jìn)制計(jì)數(shù)方法的實(shí)質(zhì)是對(duì)不同位置的比特分配不同的權(quán)重,而這些權(quán)重的分配能夠描述任何一個(gè)整數(shù)。因此,最為理想的游程編碼的游程長(zhǎng)度的字長(zhǎng)應(yīng)當(dāng)?shù)扔谟纬痰膶?shí)際長(zhǎng)度對(duì)應(yīng)的二進(jìn)制數(shù)的比特總數(shù)。但是,游程的實(shí)際長(zhǎng)度是隨機(jī)的,因此解碼器無(wú)法確切知道當(dāng)前游程長(zhǎng)度的字長(zhǎng)是多少。為此,文獻(xiàn)[5]提出了一種改進(jìn)的游程編碼算法。

3.2 改進(jìn)自適應(yīng)游程編碼算法

采用兩個(gè)元素的序?qū)?a0,a1)組成碼字,最為理想的游程編碼的游程長(zhǎng)度的字長(zhǎng)應(yīng)當(dāng)?shù)扔谟纬痰膶?shí)際長(zhǎng)度對(duì)應(yīng)的二進(jìn)制數(shù)的比特總數(shù)。而二進(jìn)制數(shù)的第一位都是比特“1”,由信息論中縮減循環(huán)碼(把循環(huán)碼開(kāi)始相同的第一位碼字刪除就得到縮減循環(huán)碼)我們得到啟發(fā),把上述游程長(zhǎng)度所有碼字開(kāi)始的比特“1”刪除,得到的碼字為a1。a0是a1的標(biāo)志位,表示a1對(duì)應(yīng)的二進(jìn)制數(shù)的比特總數(shù)。

我們?cè)O(shè)定一個(gè)游程指針(簡(jiǎn)稱游針)和兩個(gè)碼表(0碼表和1碼表)。0碼表適合對(duì)連0編碼,1碼表適合對(duì)連1編碼,a0取四位。

首先根據(jù)游針探測(cè)輸入碼元極性,判斷是采用0碼表還是1碼表。選中碼表后,游針通過(guò)計(jì)數(shù)器方式探測(cè)連續(xù)碼流,得到連續(xù)碼流長(zhǎng)度n;然后將n轉(zhuǎn)化為二進(jìn)制碼,得到Ik,然后刪除Ik的第一位,就得到a1,同時(shí)計(jì)算a1的長(zhǎng)度,并轉(zhuǎn)化為二進(jìn)制碼得到a0。設(shè)原始游程長(zhǎng)度為 x1,則x1轉(zhuǎn)化為二進(jìn)制可以采用如下算法:

把 yn-1…y2y1合并就得到a1(注意 yn被刪除了),同理可得到a0。

最后合并{a0,a1},得到最終編碼。

4 傳真圖像的改進(jìn)壓縮編碼

4.1 編碼方法

考慮到自適應(yīng)游程編碼在連續(xù)比特較長(zhǎng)時(shí)應(yīng)用效果好,我們把每行1728像素的游程長(zhǎng)度分為兩部分,一部分是游程長(zhǎng)度在0～63bit間的黑、白像素,采用霍夫曼編碼;另一部分是游程長(zhǎng)度≥64的黑、白像素,采用自適應(yīng)游程編碼。

規(guī)定每行都是從白游程開(kāi)始,因此我們只需要對(duì)游程長(zhǎng)度進(jìn)行編碼,不需要區(qū)分黑、白像素的游程長(zhǎng)度。

為了防止霍夫曼編碼的碼字與游程編碼的碼字之間構(gòu)成前綴,霍夫曼編碼的碼字以0開(kāi)頭,游程編碼的碼字以1開(kāi)頭,為此,我們把改進(jìn)的霍夫曼編碼終止碼表中白游程長(zhǎng)度為3～9,14～17的碼字替換成形成碼表中白游程長(zhǎng)度為 192,256,320,384,448,512,576,640,704,768,832的碼字,將自適應(yīng)游程編碼的碼字修改為以1開(kāi)頭。

4.2 編碼規(guī)則

編碼規(guī)則如下:

1)若游程長(zhǎng)度=0～63,則用改進(jìn)的Huffman碼終止碼表中一個(gè)相應(yīng)的碼字表示。

例如:若游程長(zhǎng)度=25,通過(guò)查表可知:其編碼為 0101011,共 7bit。

2)若游程長(zhǎng)度≥64,則編碼由1和兩個(gè)元素的序?qū)?a0,a1)組成。

例如:若游程長(zhǎng)度=80,其編碼由(1+a0+a1)組成,a1=010000,a0=0110,故編碼為1+a0+a1=10110010000,共 11bit。

3)規(guī)定每行都是從白游程開(kāi)始。若實(shí)際圖像由黑游程開(kāi)始,則需在行首加上零長(zhǎng)度的白游程(國(guó)際上規(guī)定其碼字為 00110101)。每一行結(jié)束時(shí),要加一個(gè)同步碼EOL(根據(jù)國(guó)際標(biāo)準(zhǔn),同步碼EOL的碼字為000000000001),每頁(yè)文件第一個(gè)數(shù)據(jù)前要加EOL。

4)每行數(shù)據(jù)恢復(fù)像素應(yīng)為1728,否則視為出錯(cuò)。

5)連續(xù)發(fā)六個(gè)EOL表示文件傳輸結(jié)束,轉(zhuǎn)向控制流程(RTC)。

5 改進(jìn)壓縮編碼在傳真圖像上的應(yīng)用

例如:1)若黑游程長(zhǎng)度=50,

通過(guò)改進(jìn)的Huffman碼終止碼表我們知道,其碼字為01010011,共8bit。若在行首則需要加上長(zhǎng)度為0的碼字,合起來(lái)碼字為0011010101010011,共16bit。

2)假設(shè)某一行有連續(xù)22個(gè)比特“1”,連續(xù)167個(gè)比特“0”,…。首先通過(guò)編碼器進(jìn)行編碼:由于22在0～63bit之間,故應(yīng)采用查表的方法進(jìn)行編碼,其碼字為0000011,又因?yàn)樗霈F(xiàn)在行首,按照編碼規(guī)則,當(dāng)實(shí)際圖像由黑像素開(kāi)始時(shí),則需在行首加上零長(zhǎng)度的白游程,所以比特“1”的碼字為00110101+0000011,共 15bit;接著對(duì)“0”游程進(jìn)行編碼,由于167＞64bit,故應(yīng)采用改進(jìn)的自適應(yīng)游程編碼算法,其碼字由(1+a0+a1)組成。比特“0”的長(zhǎng)度為167=(10100111)B,因此比特“0”的二進(jìn)制編碼為a1=0100111,其長(zhǎng)度為7,所以標(biāo)志位為a0=0111,所以比特“0”編碼為 1+0111+0100111。依次循環(huán)編碼就可以實(shí)現(xiàn)所有輸入碼流的編碼,所以總的編碼結(jié)果為:001101010000011101110100111…。從中我們可以看出,改進(jìn)編碼對(duì)長(zhǎng)連續(xù)比特流編碼效果是非常突出的。

解碼時(shí),當(dāng)解碼器讀到00110101時(shí),說(shuō)明此時(shí)是以黑游程開(kāi)始,然后繼續(xù)往下讀,接下來(lái)的碼字0000011與碼表中游程長(zhǎng)度為22的碼字相同,此時(shí)便譯碼為連續(xù)22個(gè)比特1;緊接著對(duì)“0”游程解碼,“1”開(kāi)頭說(shuō)明是自適應(yīng)游程編碼,開(kāi)始四位(0111)B=7表示比特“0”的二進(jìn)制編碼是7位,也即是0100111,此時(shí)比特“0”的長(zhǎng)度為(10100111)B=167,譯碼為連續(xù)167個(gè)比特0,依次交替就可以實(shí)現(xiàn)所有解碼。

6 結(jié)語(yǔ)

本文針對(duì)傳真圖像壓縮這一實(shí)際問(wèn)題提出了一種實(shí)用編碼。實(shí)用編碼將霍夫曼編碼與自適應(yīng)游程編碼有機(jī)結(jié)合,對(duì)于出現(xiàn)頻率較大的游程長(zhǎng)度,采用霍夫曼編碼,這樣可以充分利用霍夫曼編碼對(duì)于高頻率信息分配短碼字的特點(diǎn);對(duì)于出現(xiàn)頻率較小且長(zhǎng)度較長(zhǎng)的游程,采用自適應(yīng)游程編碼,這也充分利用了自適應(yīng)游程編碼在連續(xù)比特較長(zhǎng)時(shí)壓縮效果好的優(yōu)勢(shì),有效地縮短了碼字,提高了編碼效率。

[1]陳雙輝,季曉勇.M H及MR碼的新型快速解碼方法的設(shè)計(jì)與實(shí)現(xiàn)[J].微型電腦應(yīng)用,2002,18(3):13～15

[2]劉立柱.傳真圖像和傳真信號(hào)處理原理與技術(shù)[M].北京:國(guó)防工業(yè)出版社,2006:90～102

[3]劉立柱.數(shù)字傳真通訊[M].成都:電子科技大學(xué)出版社,2000:69～90

[4]林承基.圖文傳真機(jī)實(shí)用維修技術(shù)[M].成都:四川科學(xué)技術(shù)出版社,1999:17～26

[5]祝本明,劉桂華.一種改進(jìn)的游程編碼算法[J].西南科技大學(xué)學(xué)報(bào),2007,22(3):75～78

[6]Servetto,S.D.,K.Ramchandran,M.T.Orchard.Image Coding Based on Morphological Representation of Wavelet Data[J].IEEE Trans.Image Processing,1999,9(8):1161～1174

[7]Costa,M.H.M.,H.S.M alvar.Efficient Run-length Encoding of Binary Sources with Unknown Statistics[R].Microsoft Research Tech.ReportTR-2003-95,2003,12

[8]馬寧,朱福萌,尹志軍,等.改進(jìn)游程編碼在天氣雷達(dá)數(shù)據(jù)壓縮中的應(yīng)用[J].解放軍理工大學(xué)學(xué)報(bào)(自然科學(xué)版),2004,5(6):88～90

[9]吳錚,何明一.小波圖像的膨脹—游程編碼算法[J].電子與信息學(xué)報(bào),2005,27(7):1030～1034