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

李 薇 胡偉文 沈 靜

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

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

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

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

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

表1 改進的Huffman碼表

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

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

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

改進的Huffman碼當游程長度較長時碼字很長。

3 一種改進的游程編碼方法[5～9]

3.1 問題的提出

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

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

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

我們設(shè)定一個游程指針(簡稱游針)和兩個碼表(0碼表和1碼表)。0碼表適合對連0編碼,1碼表適合對連1編碼,a0取四位。

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

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

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

4 傳真圖像的改進壓縮編碼

4.1 編碼方法

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

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

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

4.2 編碼規(guī)則

編碼規(guī)則如下:

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

例如:若游程長度=25,通過查表可知:其編碼為 0101011,共 7bit。

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

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

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

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

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

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

例如:1)若黑游程長度=50,

通過改進的Huffman碼終止碼表我們知道,其碼字為01010011,共8bit。若在行首則需要加上長度為0的碼字,合起來碼字為0011010101010011,共16bit。

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

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

6 結(jié)語

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

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

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

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

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

[5]祝本明,劉桂華.一種改進的游程編碼算法[J].西南科技大學學報,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]馬寧,朱福萌,尹志軍,等.改進游程編碼在天氣雷達數(shù)據(jù)壓縮中的應(yīng)用[J].解放軍理工大學學報(自然科學版),2004,5(6):88～90

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