Algorithm 版 (精华区)

发信人: Lerry (戒网·学习), 信区: Algorithm
标  题: 16色BMP格式图像的压缩算法的改进
发信站: 哈工大紫丁香 (2001年11月20日20:46:11 星期二), 站内信件

16色BMP格式图像的压缩算法的改进
　　颜士刚　孙浩军
　　摘要：
　　数据压缩技术一直是多媒体发展的瓶颈，提高图像压缩比无疑具有现实意义。本文
对16色BMP图像的BI_RLE8压缩算法进行了改进，把压缩比提高到原来的 4/3倍。并针对
源图像文件和已压缩的图像文件给出了两种新的压缩算法描述。
　　　
　　关键词：图像 压缩 游程编码 算法改进 压缩比
　　随着WINDOWS95的推出，WINDOWS逐渐成为个人电脑使用最为广泛的操作系统，它已
经成为PC机窗口系统的事实上的工业标准，由于BMP格式是WINDOWS环境中交换与图有关
的数据的一种标准，因此BMP图像文件格式也越来越受到重视。WINDOWS支持的BMP图像的
压缩格式有两种，BI_RLE8和BI_RLE4。本文对BI_RLE8的压缩算法进行了改进，改进后的
压缩算法把压缩比提高了 4/3。为了说明这个问题，我们有必要先来了解一下BMP图像文
件的组成。
　　一、16色BMP格式图像文件的组成
　　16色BMP格式图像文件共有四部分组成：
　　１、文件头
　　这部分共14个字节。从这里我们可以得到文件的大小以及图像数据部分开始处的字
节偏移。
　　２、图像头
　　这部分共40个字节。这儿都是有关图像性质的参数，如：图像的宽、高度像素值、
压缩类型等等。
　　３、色彩对应表
　　这部分共64个字节。每种颜色分配四个字节，前三个字节分别表示该颜色的B、G、
R值，第四个字节保留未用。图像存储时仅仅存的是这儿的颜色编号，从 0--15。因此，
仅用 4位二进制数就能够表示这16种颜色，一个字节能够存储两种颜色，高四位、低四
位各一种。
　　４、数据
　　如果文件没有压缩，数据部分存储的是这16种颜色的编号。按照WINDOWS中图像的扫
描顺序（从下到上从左到右）对像素的颜色进行存储，一个字节存储两个像素。如果文
件是压缩文件，数据部分的内容会根据压缩格式的不同而不同。
　　二、BI_RLE8压缩算法
　　１、游程编码游程编码是一种非常简单的编码方法，它将数据流中连续出现的数据
（称为游程）用该数据以及它连续出现的个数来表示。例如，假设有一段数据流是这样
的：
　　… 0A0A0A0A0D0D0D0F0F0F0F0F0F0F …
　　经过游程编码后，该数据流可以表示为：
　　… 040A030D070F …
　　很显然，这种编码方法实现了数据的压缩。由于这种方法编码和解码的算法都非常
简单，因此得到了广泛的应用。
　　２、BI_RLE8压缩过程
　　BI_RLE8 这种压缩方法属于无损压缩类型。它根据图像的局部性原理，对图像文件
的数据部分进行游程编码。具体压缩过程如下：
　　打开待压缩的源图像文件以及目标文件，并把源文件的指针定位到文件的数据部分

　　(2) 把源文件的数据部分读出来进行游程编码，然后，再把编码后形成的数据流写
入目标文件。假如源图像文件的一段数据流如下：… EEEEEEEEEEEEEBBBBBBBBBBBBBBBB
BBB …
　　(I)这段数据表示有13个连续像素的颜色编号均为 E，紧接着有19个连续像素的颜色
编号均为 B。经编码后，写入目标文件的数据流应为：
　　… 0D0E130B …
　　(II)其中0D和13表示连续像素的个数，0E和0B则表示两个颜色编号。就这样，原来
用16个字节表示的数据流，经过编码后，用 4个字节就可以表示。这就是BI_RLE8的压缩
思想。
　　(3) 关闭源文件和目标文件。
　　三、BI_RLE8压缩算法的不足及改进
　　１、不足
　　采用BI_RLE8压缩算法压缩16色BMP格式的图像的不足之处主要表现在压缩以后的数
据还存在一定程度的浪费。让我们再来分析一下(II)式表示的数据流，第一、三两个字
节表示连续像素的个数，从1--255都有可能，它们是不可预见的；第二、四两个字节表
示像素的颜色编号，虽然它们的值也是不可预见的，但是颜色编号范围是从 0--15，也
就是说，颜色编号只占用了这两个字节的低四位，高四位全是 0，没有利用起来，造成
了压缩数据的浪费。这就是它的不足之处。
　　２、算法改进算法改进的关键是如何把表示颜色编号的那个字节的高四位利用起来
。我们采用了如下处理方法：把两个相邻的颜色段看成一组，用三个字节就可以表示，
第一个字节表示第一种颜色的连续像素个数，第二个字节表示第二种颜色的连续像素的
个数，第三个字节的高四位存储的是第一种颜色的编号，低四位存储的是第二种颜色的
编号，它是原来那两个表示颜色编号字节的合成（合成的方法见算法描述）。这样我们
用三个字节就可以表示这个颜色段；而原算法却用了四个字节。从而，每一组都能节省
一个字节，这样，改进后的压缩比就比原算法提高了4/3。例如，我们把（I）式表示的
数据看成一组，就可以把它重新编码为：
　　... 0D13EB ...
　　(III)其中0D和第三个字节的高四位 E对应，13和第三个字节的低四位 B对应。这样
，对(I)式所表示的数据流，经过新的编码方法编码后，用(III)式所示的三个字节就能
够表示出来，而使用BI_RLE8游程编码方法，只能压缩成(II)式所示的四个字节。显然，
采用新的编码方法能够把压缩比提高 4/3。
　　３、新算法的压缩过程
　　这种新算法可以对未压缩的源图像文件进行压缩，也可以压缩已经使用BI_RLE8 压
缩算法压缩过的16色BMP图像文件。下面我们就分别说明一下。
　　(1) 压缩源图像文件
　　压缩源图像文件是指把文件的数据流直接采用新的编码方法进行编码，编码形成的
数据流组成压缩文件。它的压缩对象是未压缩过的源图像文件。压缩过程和BI_RLE8 压
缩算法的压缩过程基本类似。其中第一、三两步完全相同，第二步编码处理要复杂一些
，把(I)式表示的数据流直接编码为(III)式。压缩算法如下：PackYuan(FILE *sf,FILE
 *df)/*sf和df分别表示指向源文件和目标文件的指针*/{sf=fopen(sfname,"rb"); df=
fopen(dfname,"wb");
　　fseek(sf,number,0);/*定位到数据部分,number表示偏移量*/
　　temp=第一个像素的颜色值;
　　do {ch=fread(sf);
　　/*处理高字部分*/
　　ch1=高字部分的颜色值;
　　if(ch1==temp) count++;
　　else /*改进部分即是下面这个if语句*/
　　if(tag==FALSE) {c1=temp;ic1=count; tag=TRUE;}
　　else {c2=temp;ic2=count;
　　c1=c1<<4;c1=c1|c2;/*两色存到一个字节中*/
　　fputc(ic1,df);fputc(ic2,df);fputc(c1,df);
　　temp=ch1;count=1;tag=FALSE;
　　}
　　/*处理低字部分，这部分处理和高字部分基本相同，故略去*/
　　ch1=低字部分的颜色值;
　　……
　　}while(!feof(sf))
　　fclose(sf); fclose(df);
　　}
　　(2) 压缩已压缩过的图像文件
　　这里所说的已压缩的图像文件是专指采用BI_RLE8压缩算法压缩的16色BMP格式的图
像文件，由于游程编码后的压缩数据还存在一定程度的浪费，所以我们要进行再压缩。
压缩过程如下：
　　①打开待压缩的压缩文件和目标文件，把压缩文件的指针定位到数据部分。
　　②把压缩文件的数据流每四个字节划为一组，分成若干组，然后，对每组进行再编
码。编码后形成的数据流再顺序写入目标文件。再编码就是把(II)式那样的数据流全部
用(III) 式的样子表达。这就实现了压缩文件的再压缩。
　　③关闭待压缩文件和目标文件。
　　压缩算法简述如下：PackYa(FILE sf, FILE df)/*sf和df分别表示指向源文件和目
标文件的指针*/{
　　sf=fopen(sfname,"rb"); df=fopen(dfname,"wb");
　　fseek(sf,number,0);/*定位到数据部分,number表示偏移量*/
　　do /*从待压缩的文件中读出一组数据*/
　　{ count1=fread(sf); color1=fread(sf);
　　count2=fread(sf); color2=fread(sf);
　　/*利用color1的高四位,把color1和color2合成一个字节*/
　　color1=color1<<4; color1=color1|color2;
　　/*写入目标文件*/
　　fputc(count1,df); fputc(count2,df);
　　fputc(color1,df);
　　}while(!feof(sf)) /*若文件未结束,转到do语句*/
　　fclose(sf); fclose(df);
　　}
　　

--
　　不在乎天长地久，就怕你从来没有！

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 天外飞仙]