PostScript 3中预测过滤器的算法研究和性能分析-上海联兵环保免费电话：400-600-5030

摘 要:Flate-Filter是Postscript 3中用于压缩文字、图像等数据流的过滤器,预测过滤器则是Postscript 3中的辅助Flate-Filter压缩图像数据流的过滤器.本文在分析比较各预测过滤器函数的基础上,采用两种新的替代性启发规则,从而得到比原有的PNG标准更为优化的结果.本文还提出一个基于矢量的模型来定量地描述和评估各预测过滤器.
关键词:PostScript 3;预测;过滤器;压缩
分类号:TP311
文献标识码:A
1 引 言
桌面出版领域的页面描述语言最新版本PostScript 3(简称PS 3)由于应用的需要,增设过滤器Flate-Filter,以支持PostScript文件中的文本和图像的通用压缩,从而减少PostScript文件的传输流量,特别是PS解释器和输出设备之间的通讯流量.
Flate-Filter过滤器的核心是DEFLATE通用压缩算法,该算法对于自然语言和PostScript语言中的正文部分压缩效率较高,但是对于PostScript语言中经常要运用到的图像数据而言,基于DEFLATE算法的Flate Filter显然效果不尽人意.
鉴于此,Adobe公司在推出PS3标准的时候,为新过滤器Flate Filter加入了一个可选的开关参数:预测函数(Predictor).它利用了像素之间的信息相关性,在PS3的过滤器前级预处理图像数据.
2 预测的定义和几种预测函数
2.1 通用压缩算法和预测算法
在网络和多媒体技术日益成为计算机发展潮流的今天,大数据量的存储、处理和传输促进了数据压缩技术的研究和开发.数据压缩技术主要研究的是数据的表示和传输,目标是减少数据占用的存储空间和通讯时间.
数据压缩技术的核心是压缩算法,该算法的任务是处理原始数据,找出其中的相关信息,从而用冗余度更低的编码来表示原有的信息.按照压缩过程的可逆性,压缩算法可以分为有损压缩和无损压缩两类.在以文字和图像为主要压缩对象的应用场合,需要面向通用数据的无损压缩算法.PS3语言中采用的压缩过滤器Flate-Filter就是基于这样的一种算法——DEFLATE.
DEFLATE是基于LZ77算法(Lempel-Ziv 1977)和霍夫曼编码的一种混合算法.它的核心思想是用滑动窗口和动态的词典来搜索和记录连续数据中重复出现的特定排列模式.它的工作流程如下:用滑动窗口遍历输入数据,每三个字节作为一个单元与词典上已有的词组进行对照.如果该三元组不在词典中,则原封不动地拷贝一份到输出,同时将其作为词组加入词典;对于不是第一次出现的符号,词典中某词组的三元组则进一步进行后续搜索,看输入数据是否和词典中的词组或以前的数据存在更佳(长)的匹配,后用一个由(位移、长度)构成的指引元组来代替.该指引元组指向的就是先前曾经出现过的这一模式的位置和长度,同时该匹配的排列也被作为词组加入词典;最后再利用霍夫曼编码二次处理编码后数据,从而进一步降低数据冗余度.
DEFLATE压缩算法主要是针对顺序数据(一维相关)的压缩,通过找出前后相同的排列模式来降低数据冗余性.但是基于像素矩阵的图像数据具有二维相关性:行关联和列关联.因而如果只对其简单地使用Flate Filter进行压缩,会因为没有充分利用数据之间的内在相关性而效果不佳.
因此在图像编码过程中,我们可以利用图像像素间的相关性,根据某像素点的值来预测下一个像素点的取值,然后将像素点的实际值与预测值相减得到一个误差值,并对该误差值进行编码(压缩算法任意),这就是预测编码.进行预测编码需要先建立预测模型,根据这个模型和已输入的数据得到下一时刻的预测值,然后根据实际值与预测值计算出预测误差,最后再对这些误差序列进行压缩编码.由此可见,预测模型的优劣对于编码效率的影响很大.
PS3中预测函数的作用主要是用来提高Flate编码过滤器的压缩比.这样,当输入图像数据具有较高可预测性的时候,压缩比将明显提高.对于连续色调的取样图像来说,预测函数的工作就是将每个像素的取样值置换为预测值和该像素值之间的差.这里的预测值是由预测模型根据“较早”的像素和该像素取样值计算得出的.所谓“较早”像素是指按图像数据排列(输入)顺序和当前像素位置,由预测函数定义的某一个或几个像素.如果预测函数定义的适当的话,原有的离散图像数据流将变成丛集在零值附近(均值接近0)的平稳随机过程.再经过Flate Filter压缩处理,即可得到具有较高压缩比的编码数据.
2.2 预测函数
PS3中定义了两类预测函数:基于TIFF图像标准的预测函数(以下简称TIFF预测函数)和基于PNG图像标准的预测函数(以下简称PNG预测函数).在PS3的标准中,TIFF预测函数对应于Predictor 2,而PNG预测函数对应于Predictor 10、11、12、13、14、15.
为了方便起见,PS3中对于预测函数的输入数据作了如下假定:图像数据为未经任何处理的像素矩阵,像素按色彩分量采样,排列次序为从左到右,每排为一扫描线,扫描线自上而下排列.
2.2.1 TIFF预测函数
PS3中的TIFF预测函数仅由TIFF 7.0标准中的第二类预测函数(predictor 2)构成,即用每个像素左侧最紧邻的像素作为预测值(每条扫描线最左端的像素则用零作为预测值).求得原像素值与该预测值之间的差代替原有的像素采样值;
2.2.2 PNG预测函数
PS3中的PNG预测函数包括了World Wide WebConsortium (W3C) Portable Network Graphics (PNG)推荐标准中的所有过滤器.共五种基本的PNG预测算法,此外还有第六种算法,它实际上是前五种算法的混合.
上述预测函数在PS3 Flate Filter的数据词典中分别如下定义:
(1) Predictor 10
Predictor 10不作任何预测.像素数据的每条扫描线原样不动地拷贝到输出流中,仅在每条扫描线的头部加入一个代表过滤器类型的值为10的字节,作为算法标志;
(2) Predictor 11
Predictor 11采用SUB预测函数.每个像素以其左侧的紧邻像素作为预测值,将原有的采样值代之以它与预测值的差值.算法标志字节设为11.
SUB预测函数应用如下的公式来计算扫描线中的每一个字节:
Sub(x) = Raw(x) -Raw(x-bpp)
这里,Ra w(x)是指在扫描线上X位置处的原始数据字节.bpp为每个像素所占的字节数.
SUB预测函数也是所有预测函数中比较关键的函数.在进行差值运算时,必须使用无符号、模256的算术运算,这样可以保证输入数据和输出数据都在八位字节的表示范围内,从而使得差值序列可以作为过滤后的扫描数据输出.
在Sub过滤器还原经过Flate-Filter解压缩后的数据时,应用如下公式:
Sub(x) + Raw(x-bpp) (模256运算)
这里,Raw(x)指向解压后的预测值序列中某字节.要注意的是Predictor 11中进行的计算是针对字节而忽略字长的.
(3) Predictor 12
Predictor12采用Up预测函数.每个像素用正上方(前一条扫描线中相同位置)的像素作为预测值,第一条扫描线的像素则一律用零作为预测值.算法标志字节值为12.
除了预测像素的位置定义不同之外,Up预测函数的计算公式与Sub预测函数完全一样:
Up(x) = Raw(x) -Prior(x) (模256运算)
这里,Prior(x)为上一条扫描线中相同位置上未经预测处理字节的值.
在Up过滤器还原经过Flate-Filter解压缩后的数据时,应用如下公式:
Up(x) + Prior(x) (模256运算)
(4) Predictor 13
Predictor 13采用Average预测函数.每个像素用正上方像素和左侧最紧邻像素的均值作为预测值(边界条件下的像素预测的值选取,参照Up和Sub预测函数),算法标志字节值为13.
该预测函数的预测公式如下:
Average(x) = Raw(x) -floor((Raw(x-bpp)+Prior(x))/2) (模256运算)
这里,floor()表示除法的结果应向下取整.换句话说,这是一个整数除法或者右移操作.
在Average过滤器还原经过Flate-Filter解压缩后的数据时,应用如下公式:
Average(x) + floor((Raw(x-bpp)+Prior(x))/2)(模256运算)
实现过程中,用九位进行运算,以避免上面两个公式中的Raw(x-bpp)+Prior(x)运算溢出.
(5) Predictor 14
Predictor14采用Paeth预测函数.每个像素预测值的选取是通过一个关于正上方像素、左侧像素以及左上方像素(皆为紧邻)的非线性函数来实现.
Paeth过滤器首先计算一个关于上述三个相邻像素(左,上,左上)的线性函数值作为预测值,然后将这三个相邻像素中最接近该预测值的作为预测值.这一方法的名称来自于其发明者Alan W. Paeth〔PAETH〕.该算法标志字节为14.
该预测函数的预测公式如下:
Paeth(x) = Raw(x) -PaethPredictor(Raw(x-bpp),
Prior(x),Prior(x-bpp)) (模256运算)
在Paeth过滤器还原经过Flate-Filter解压缩后的数据时,应用如下公式:
Paeth(x) + PaethPredictor(Raw(x-bpp), Prior(x),
Prior(x-bpp)) (模256运算)
上述两个公式中PaethPredictor函数的定义上文已经给出.该函数计算必须精确,不能有溢出,而且函数中三个相邻像素的位置非常关键,且不能错乱.模256运算只在最后一步减法中使用.
(6) Predictor 15
Predictor15采用最优(Optimum)预测函数.它是同时混合上述五种算法的预测函数:该预测函数将顺序尝试前面五种PNG预测函数,找出其中使得预测后扫描线上所有像素的值(差值)之和为最小的预测函数,将其作为最优预测函数,作用于输入数据,详见图1.

2.3 两类预测函数的比较
TIFF预测函数和PNG预测函数有一些相同之处,都假设图像数据是按顺序输入的,扫描线从上到下,同一扫描线内的像素自左而右,每一条扫描线的数据占整数个字节,像素和它们的色彩分量的二进制值按从高到低的顺序装入字节(Big-Endian),以及假设所有图像边界以外的像素的色彩采样值均为0,以便计算图像边界像素的预测值.
这两组预测函数也有几处明显的区别:经过PNG预测函数预测处理过的图像数据,每条扫描线都以一个算法标志字节作为首字节(详细定义见上述PNG预测函数),因此各扫描线可以用不同的算法进行预测来提高压缩比率.TIFF 2预测函数没有算法标志,它对所有扫描线采用同样的算法.
TIFF预测函数用“前”一个像素的相应色彩分量来预测每一个色彩分量,而不考虑色彩分量的位长和像素的色彩数,也就是说可以跨越字节边界和不受字节边界限制.PNG预测函数用“前”(依赖定义)一个像素的相应字节来预测每一个字节,而不管一个字节里面是否有多个色彩分量,也不管一个色彩分量是否会横跨多个字节,这种改进使得压缩速度得以较大的提高,但却会引起压缩效率的少许降低.
2.4 替代性启发规则
我们在开发PS3解释器过程中,实现了上述的各类预测函数.但在实现最优预测函数(Predictor15)时发现:PNG标准定义的预测函数使用的启发性规则并非是完全意义上的最优.事实上由于图像数据和Flate Filter互动的不确定性,找到最优预测函数在实现上也是不太可能的(除非穷举),因此我们尝试着利用其他的规则来代替PNG的原有规则,目标是使得到的结果更接近最优.
第一种替代的规则是误差平均方差最小,即:

其中Xj为图像数据中某一像素的值,而Pij则为对它应用第i种预测函数得到的预测值.
另一种替代的规则是基于Flate Filter的Multi Call特性的逐步试探法:
PS3中的Flate Filter有一个重要的特性Multi Call:即对于同一待压缩的数据可以分多次输入直至完成.这主要是为了使主机与输出设备之间通讯流相适应而设计的.我们在实现这一特性时发现:Multi Call同样可以用作OptimumPredictor的启发规则.可以将经过某预测函数预测的图像数据逐条扫描线作为Multi Call的输入(在此之前当然要先保存Flate Filter的中间状态),得出压缩后的数据大小,然后再恢复Flate Filter到未输入该扫描线数据之前的状态,尝试下一个预测函数,最终找出一个使得压缩后数据为最小的预测函数.
该方法的优点是比原有的启发规则更接近最优解,我们测试的十几个例子都证明了这一点,代价则是压缩所耗费的时间线性增加.因此,在面对存储为主而不是通讯为主的应用场合,我们不妨利用该启发规则;而对实时性要求十分严格的情况,可以仍然使用原有的启发规则.误差平均方差规则则介于两者之间,可以作为原启发规则的一个更优替代.
3 预测模型性能比较和分析
3.1 实例测试与比较
为了更进一步了解上述几种预测函数的性能与效率及其在不同条件下的表现,下面用几个简单例子来测试一下几类预测函数的压缩率.
测试的例子分为两组:文本文件和图像文件.文本文件:
Casabl.txt :921字节的文本文件;
RFC2083.txt :248,540字节的文本文件;图像文件:
1.bmp :582字节的一幅简单图像;
Landscape.bmp: 1,440,054字节的较大图像(色调较连续,适合预测);
Ff7.bmp: 1,500,054字节的较大图像(色调不连续,不适合预测);
第一步先用Flate Filter的默认压缩比进行压缩,得到的压缩后的各文件大小和压缩比(压缩比定义为压缩后文件大小和原文件大小的比值)为:文本文件:
Casabl.txt : 478字节,压缩比率51.9%;
RFC2083.txt : 71,158字节,压缩比率28.63%;图像文件:
1.bmp : 143字节,压缩比率24.57%;
Landscape.bmp: 536,713字节,压缩比率37.27%;
Ff7.bmp: 1,155,254字节,压缩比率77.01%;
不难看出Flate Filter对于文本文件尤其是较大的文本文件,压缩比是相当高的;而对于比较复杂的图像文件则压缩比有所降低.对于色调不连续、内容较“杂乱”的图像效率下降更快.
第二步用预测函数和Flate Filter同时作用于这些本来压缩效果不太理想的图像文件,得到压缩后的各文件大小和压缩比分别见下面两个表格.

从上面的两个表格可以看出:
1.在应用了预测函数之后,Flate Filter对于较大图像文件的压缩能力大大提高.
2.基于同一个预测模型的TIFF预测函数和PNG Sub预测函数效果大致相同,而PNG Sub的压缩能力略有降低.
3. PNG预测函数中,11(Sub)、12(Up)、13(Average)的压缩能力大致相近;14(Paeth)在图像数据量较大、画面比较复杂的时候优于前面三种预测函数.而15(Optimum)在所有情况下都表现出了接近最优化的压缩效果.
3.2 预测模型的形式化定义和评测
从分析中可以看出,预测模型的构造对于预测函数辅助压缩的效果有着较大的影响,因此一个很自然的想法就是用一个量化的指标来表征预测模型的性能优劣.
所有的预测模型都是利用图像矩阵数据中相邻像素的相关性来降低数据冗余,对于二维图像数据而言,可以将两个相邻像素A、B之间的相关性定义为R〔A,B〕:


从上述公式可见,在给定图像数据的情况下,S值越小则说明预测模型充分利用了图像数据的自相关性,压缩比也就越高;反之亦然.因而可将S作为选择预测模型的重要依据.
4 小结
文中对PS3语言的两组共七类预测过滤器进行了分析和比较,尤其对基于PNG标准的Optimum预测函数的启发规则,给出了两个可行的替代规则,在我们实现PS 3解释器的过程中已经证明是可以接受的,而且性能更优.
本文还提出了一种矢量化的模型来衡量各预测函数性能,并估测图像数据各像素的相关性,从而为量化地评估各预测模型提供了可能.

上海联兵环保科技有限公司
地址：上海市松江区工业区茸北分区茸阳路69号
总机：021-51691929
传真：021-57784244
免费电话：400-600-5030
技术支持：13641659499
E-mail：zhanglianbing@126.com
http://www.shlbhb.com