霍夫曼编码和游程编码在图像编码中的应用*

李 薇 胡伟文 沈 静

(海军工程大学理学院 武汉 430033)

1 传真图像数据的特点[1]

三类传真机的主要特点之一是对图像数据进行编码。虽然一幅图像数据量很大,但其中有很大的信息多余度,这部分数据可以不用传输。图像信息的多余度可以用图像的像素统计特性来说明,包括像素本身出现的百分比和不同像素间的相关特性。统计表明黑像素出现的百分比与白像素出现的百分比有很大差别,相邻像素之间的相关性也很强。例如用计算机对七种典型的传真样张作统计,结果是:白像素平均出现的百分比是93.7%。即使在文字密度很大的样张中,白像素出现的百分比也达到88.8,而黑像素只占11.2%。在这些像素中,约有2/3的黑像素是相邻的,有97%以上的白像素是相连的。还有持续长度的统计特性。总之,图像中有许多特性可以通过统计而预测到,这些图像特征信息是多余的,只需传输无法预测的图像信息。

2 改进的霍夫曼编码(MHC)方法[2～4]

改进的霍夫曼编码以八张具有代表性的样张为统计依据,得出游程长度的出现概率,然后,再编制霍夫曼(Huffman)码表,这样就摆脱了游程长度的随机性,难以获得游程长度出现概率的问题。根据八张样张统计出来的游程长度出现概率发现,游程长度在0～63bit的居多,因此,就把每行 1728像素的游程长度分为两张统计表,一张是游程长度在0～63bit间白、黑像素的游程长度给出一个码表,这就是终止码表,另一张是像素游程长度≥64的码表,该像素的码表就是形成码表。这样MH编码实际上就是一个查表过程,即游程的码字=形成码+终止码。

表1 改进的Huffman码表

每张的数据传输格式如图1所示。

图1 M H码的数据传输格式

编码举例:白游程65(64+1)的编码为“64”的形成码 11011和“1”的终止码 000111,也就是11011000111。

改进的Huffman码当游程长度较长时码字很长。

3 一种改进的游程编码方法[5～9]

3.1 问题的提出

从二进制的表达方式可以得到启发:二进制计数方法的实质是对不同位置的比特分配不同的权重,而这些权重的分配能够描述任何一个整数。因此,最为理想的游程编码的游程长度的字长应当等于游程的实际长度对应的二进制数的比特总数。但是,游程的实际长度是随机的,因此解码器无法确切知道当前游程长度的字长是多少。为此,文献[5]提出了一种改进的游程编码算法。

3.2 改进自适应游程编码算法

采用两个元素的序对(a0,a1)组成码字,最为理想的游程编码的游程长度的字长应当等于游程的实际长度对应的二进制数的比特总数。而二进制数的第一位都是比特“1”,由信息论中缩减循环码(把循环码开始相同的第一位码字删除就得到缩减循环码)我们得到启发,把上述游程长度所有码字开始的比特“1”删除,得到的码字为a1。a0是a1的标志位,表示a1对应的二进制数的比特总数。

我们设定一个游程指针(简称游针)和两个码表(0码表和1码表)。0码表适合对连0编码,1码表适合对连1编码,a0取四位。

首先根据游针探测输入码元极性,判断是采用0码表还是1码表。选中码表后,游针通过计数器方式探测连续码流,得到连续码流长度n;然后将n转化为二进制码,得到Ik,然后删除Ik的第一位,就得到a1,同时计算a1的长度,并转化为二进制码得到a0。设原始游程长度为 x1,则x1转化为二进制可以采用如下算法:

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

最后合并{a0,a1},得到最终编码。

4 传真图像的改进压缩编码

4.1 编码方法

考虑到自适应游程编码在连续比特较长时应用效果好,我们把每行1728像素的游程长度分为两部分,一部分是游程长度在0～63bit间的黑、白像素,采用霍夫曼编码;另一部分是游程长度≥64的黑、白像素,采用自适应游程编码。

规定每行都是从白游程开始,因此我们只需要对游程长度进行编码,不需要区分黑、白像素的游程长度。

为了防止霍夫曼编码的码字与游程编码的码字之间构成前缀,霍夫曼编码的码字以0开头,游程编码的码字以1开头,为此,我们把改进的霍夫曼编码终止码表中白游程长度为3～9,14～17的码字替换成形成码表中白游程长度为 192,256,320,384,448,512,576,640,704,768,832的码字,将自适应游程编码的码字修改为以1开头。

4.2 编码规则

编码规则如下:

1)若游程长度=0～63,则用改进的Huffman码终止码表中一个相应的码字表示。

例如:若游程长度=25,通过查表可知:其编码为 0101011,共 7bit。

2)若游程长度≥64,则编码由1和两个元素的序对(a0,a1)组成。

例如:若游程长度=80,其编码由(1+a0+a1)组成,a1=010000,a0=0110,故编码为1+a0+a1=10110010000,共 11bit。

3)规定每行都是从白游程开始。若实际图像由黑游程开始,则需在行首加上零长度的白游程(国际上规定其码字为 00110101)。每一行结束时,要加一个同步码EOL(根据国际标准,同步码EOL的码字为000000000001),每页文件第一个数据前要加EOL。

4)每行数据恢复像素应为1728,否则视为出错。

5)连续发六个EOL表示文件传输结束,转向控制流程(RTC)。

5 改进压缩编码在传真图像上的应用

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

通过改进的Huffman码终止码表我们知道,其码字为01010011,共8bit。若在行首则需要加上长度为0的码字,合起来码字为0011010101010011,共16bit。

2)假设某一行有连续22个比特“1”,连续167个比特“0”,…。首先通过编码器进行编码:由于22在0～63bit之间,故应采用查表的方法进行编码,其码字为0000011,又因为它出现在行首,按照编码规则,当实际图像由黑像素开始时,则需在行首加上零长度的白游程,所以比特“1”的码字为00110101+0000011,共 15bit;接着对“0”游程进行编码,由于167＞64bit,故应采用改进的自适应游程编码算法,其码字由(1+a0+a1)组成。比特“0”的长度为167=(10100111)B,因此比特“0”的二进制编码为a1=0100111,其长度为7,所以标志位为a0=0111,所以比特“0”编码为 1+0111+0100111。依次循环编码就可以实现所有输入码流的编码,所以总的编码结果为:001101010000011101110100111…。从中我们可以看出,改进编码对长连续比特流编码效果是非常突出的。

解码时,当解码器读到00110101时,说明此时是以黑游程开始,然后继续往下读,接下来的码字0000011与码表中游程长度为22的码字相同,此时便译码为连续22个比特1;紧接着对“0”游程解码,“1”开头说明是自适应游程编码,开始四位(0111)B=7表示比特“0”的二进制编码是7位,也即是0100111,此时比特“0”的长度为(10100111)B=167,译码为连续167个比特0,依次交替就可以实现所有解码。

6 结语

本文针对传真图像压缩这一实际问题提出了一种实用编码。实用编码将霍夫曼编码与自适应游程编码有机结合,对于出现频率较大的游程长度,采用霍夫曼编码,这样可以充分利用霍夫曼编码对于高频率信息分配短码字的特点;对于出现频率较小且长度较长的游程,采用自适应游程编码,这也充分利用了自适应游程编码在连续比特较长时压缩效果好的优势,有效地缩短了码字,提高了编码效率。

[1]陈双辉,季晓勇.M H及MR码的新型快速解码方法的设计与实现[J].微型电脑应用,2002,18(3):13～15

[2]刘立柱.传真图像和传真信号处理原理与技术[M].北京:国防工业出版社,2006:90～102

[3]刘立柱.数字传真通讯[M].成都:电子科技大学出版社,2000:69～90

[4]林承基.图文传真机实用维修技术[M].成都:四川科学技术出版社,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]马宁,朱福萌,尹志军,等.改进游程编码在天气雷达数据压缩中的应用[J].解放军理工大学学报(自然科学版),2004,5(6):88～90

[9]吴铮,何明一.小波图像的膨胀—游程编码算法[J].电子与信息学报,2005,27(7):1030～1034