图像压缩算法性能的测试与分析工具

1、图像压缩算法性能的测试与分析工具 1蔡正兴,张虹中国矿业大学计算机科学与技术学院,江苏徐州 (221008摘 要:本文研究了图像压缩算法性能的评价方法,提出了图像压缩算法性能的测试算法, 包括横向比较测试和纵向分解测试, 并在此基础上设计并实现了压缩算法性能的测试与分析 工具。 该工具能够测试和分析压缩算法的性能, 并自动生成各种分析图表, 为用户提供了方 便,具有较大的实用价值。为了提高评价的效率、准确性和全面性,文中提出了测试图像的 选择方法和测试结果的分析方法,具有一定的理论意义。关键词:压缩性能,测试方法,分析方法,图像选择方法1. 引言近年来,图像压缩得到快速发展 1,各种算法层出不

2、穷,比如有损的压缩算法可以在低 失真的条件下达到高压缩比 2, 3,而无损的压缩算法则可以保证重建图像的无失真 4。因此 在实际应用中得知各种压缩算法的性能及特点是必要的。 在评价图像压缩算法性能时主要考 虑压缩比、重建质量、时间复杂度、空间复杂度和实现代价这几个方面 5,其中较为重要的 是压缩比、重建质量和时间复杂度。为了计算这些压缩性能指标,常常使用一些工具软件, 比如在图像处理领域广泛使用的 MATLAB 系列软件, 它提供了大量的内置函数 6, 操作方便, 功能强大, 但它不是评价图像压缩算法性能的专业工具, 需要进行二次开发, 不能有效的分 析和评价压缩性能。其次,利用性能指标来评价

3、压缩方法,尽管方便快捷,但还不能反映图 像压缩算法的全部特点。例如,在考虑变换编码系统的失真性质时,一般采用 MSE(均方误 差 ,有时利用 MSE 计算得到的重建质量很好,但视觉效果却不好,这是因为 MSE 对图像中 的失真显著性不敏感 7,可见,性能指标仅仅是对压缩算法进行宏观上的评价,无法评价每 个过程对压缩性能的影响。再次,在评价压缩性能时,不可避免地要使用测试图像,用户在 选择测试图像时带有随机性, 不利于全面地评价压缩方法。 针对这些不足, 本文设计了图像 压缩算法性能的测试与分析工具 AutoTA 。 AutoTA 的目标是自动地对图像压缩算法进行 测试与分析,并生成各种分析图表

4、,全面的评价图像压缩算法的性能。 AutoTA 具有广泛的 应用前景,科研人员利用 AutoTA 可横向比较各种压缩算法的性能,也可纵向分析压缩算法 的特点;工程技术人员也可以根据 AutoTA 的测试结果,在实际应用中选择合适的图像压缩 算法。2. 压缩算法性能指标压缩性能指标是评价压缩算法的重要方面,也是 AutoTA 分析图像压缩算法性能的重要 依据,下面将描述相关的性能指标。2.1压缩比压缩比是指压缩过程中输入数据量和输出数据量之比, 反映了图像压缩算法的压缩性能, 当压缩比小于 1时为正压缩,当压缩比大于 1时为负压缩。压缩比的计算公式为:1本课题得到国家自然科学基金项目 (编号:6

5、0372102 、教育部博士点基金项目 (编号:20030290011 、软件 新技术国家重点实验室课题 (编号:A200309 资助。=输入文件大小 压缩比 输出文件大小.1 这里输入文件指的是原始文件, 输出文件指的是压缩后的文件。 值得注意的是, 这种度量方 法必须指明输入输出的显示形式,否则将是不可靠的 8。2.2峰值信噪比在有损图像压缩中, 峰值信噪比用来衡量与原始图像相比较的重建图像的质量, 与人类 视觉系统所察觉到的误差有有限的近似关系 7,易于计算,定义为:2(21 PSNR=10lgB MSE 2 其中 B 表示该图像的色深, MSE 为原图像和恢复图像的失真均方差,定义为:

6、1212112121200121(, , N N n n MSE n n n n N N =. 3其中 12, n n 表示原图像在 处数值, 表示重建图像在 处数值。 12, n n 21, n n 12, n n 2.3时间复杂度时间复杂度是指图像压缩算法编解码的速度,希望编解码的速度很快。在许多应用中, 编解码将在不同的时间,不同的地点和不同的系统中运行 8,因此编解码速度对评价压缩算 法的效率和通用性具有重要的意义。 AutoTA 中采用读取 CPU 中的存储器值的方法来计算编 解码时间,描述如下:在压缩或解压缩算法运行前,先读取 CPU 内部 64位计数器的值并存储;在压缩或解压缩算

7、法运行结束后,再次读取 CPU 内部 64位计数器的值并存储;将两次的存储值相减,得到运行的时钟周期数,用该值除 CPU 的频率就得到算法运行 的时间。计算公式为:2T T T H=1 .4 其中 表示算法运行结束时 CPU 计数器的值, 表示算法运行前 CPU 计算器的值, H 代 表 CPU 的频率。2T 1T 还有一些压缩性能指标如空间复杂度,实现代价等无法精确衡量,本文暂不讨论。3. AutoTA系统设计3.1系统结构AutoTA 以目前常见的几种压缩算法为测试和分析对象,主要包括离散余弦变换 (DCT算法、离散小波变换 (DWT算法、哈夫曼编码算法、算法编码算法、 JPEG 压缩算法

8、 和 JPEG2000压缩算法 。在实现这些压缩算法的同时,重点在于实现对图像压缩算法的测试 和分析, 测试的目的在于获得性能指标等数据, 而分析则是利用这些数据对压缩性能进行评 价,因此 AutoTA 应该具备 97图像压缩算法的测试功能、分析功能、测试图像选择功能、图像压缩质量控制功能、性能指标的计算功能、压缩算法的分解功能等。由此,图像压缩算法的 性能测试与分析工具可划分为五个部分:初始化设定、测试图像选择、压缩算法实现、参数 计算和性能分析。 初始化部分选择待测试的压缩算法和测试策略, 进行压缩图像的质量控制 和性能指标的选择; 测试图像选择主要是系统根据设定的测试算法自动的选择测试图

9、像; 压 缩算法实现部分根据要求实现相应的压缩算法; 参数计算部分进行性能指标的计算或者跟踪 压缩算法每一步的数据变化; 性能分析部分根据测试策略和计算得到的各种数据, 自动生成 各种性能分析图表。系统结构如图 1所示。 图 1 AutoTA 系统框架3.2工作原理由 AutoTA 的框架图可知,用户需要选择测试策略,并指定待测试的压缩算法,可以是 一种或多种,由测试策略确定;确定压缩算法后,用户需要进行系统参数的设置,这和具体 的测试策略有关,比如恢复图象质量,跟踪数据块大小等;然后, AutoTA 将自动地选择测 试图像, 并调用指定的图像压缩算法, 计算需要的参数, 如性能指标等, 并存

10、储于数据库中; 最后系统将分析这些数据,并绘制图表。3.3 AutoTA的实现技术AutoTA 的关键在于压缩算法的测试方法,测试图像的选择方法和测试结果的分析方法。 以下将详细介绍它们的实现算法。3.3.1 AutoTA测试方法为了全面的评价图像压缩算法,避免利用性能指标评价压缩算法的误差,本文提出了 两种测试方法 : 横向比较测试和纵向分解测试。 横向比较测试是将待评价的图像压缩算法与 其他压缩算法进行比较, 比较的内容是压缩性能指标; 纵向分解测试是将待评价图像压缩算 法分步骤实现,并记录每一步的数据,纵向观察数据的变化。测试方法是 AutoTA 的基础, 它决定整个系统的流程。下面给出

11、测试策略的实现算法:1 系统初始化。 令 n=0, testmethod=0, imagemethod=3, imagecount=1, imagequality=100, blocksize=4, x=0, y=0。其中 n 表示测试次数,为正整数; testmethod 表示测试策略, 0代表横向比较测试, 1代表分解测试,为布尔型数; imagemethod 表示测试图像的选择方法, 1代表同类图像, 2代表不同类图像, 3代表随机选取, 为正整数; imagecount 表示测试图像的数目, 为正整数; imagequality 表示压缩图像质量,其值在 0到 100之间变化,值越大表

12、示图像质量越好; blocksize 表示跟踪的块大小,为正整数且是 2的方幂; x , y 表示跟踪块的起始位置,为整 数且大于等于 0。2选择测试策略,即设定 testmethod 。3设定测试图像选择方法,即设定 imagemethod 。4对测试策略进行判断。if testmethod=0,则设定测试次数 n ;设定 imagecount 为 n ;设定 imagequality ;选择需要计算的性能指标,包括 PSNR 、压缩比、压缩时间等。调用测试图像选择算法;循环调用相应的图像压缩方法,循环次数为 n ;计算选择的性能指标,并存入数据库;调用压缩结果分析算法。else设定 n=1

13、;设定 imagecount 为 n ;设定 blocksize 和 x , y ;设定 imagequality ;调用测试图像选择算法;调用相应的图像压缩方法;记录每一步变换后,跟踪块的数据,并存入数据库中;调用压缩结果分析算法。end5算法结束。3.3.2测试图像选择方法测试图像对全面而准确地评价压缩算法具有重要意义, 因为任何一种压缩算法都不可能 对所有的图像都适用, 因此在测试压缩算法时, 需要有针对性地选择测试图像, 本文认为测 试图像的选择应遵循以下几个原则:1 测试图像要包括多种类型;2 每幅测试图像需要有多种特性,比如说在一幅以连续色调为主的图像中有一些离散 色调,或者在大多

14、数图像像素相似的情况下,有一些跳跃的像素等等;3 测试图像应有不同的大小。这里的大小是指图像的高度与宽度的乘积。为了符合这些原则, 本文提出了基于图像特征的测试图像选择方法。 该方法首先对图像 进行颜色空间的转换,由 RGB 空间转换为 HSV 空间,然后对 HSV 空间进行区域分类,并 使用区域生长算法对图像进行分割和合并, 将得到一系列的块, 计算各个块的尺寸, 色度平 均值和均方差, 并作为该图像的特征, 最后利用特征值选择符合要求的图像。 下面先给出颜 色空间转换方法和区域生长方法的描述。3.3.2.1颜色空间转换及色度空间划分规则一般认为 R,G,B 颜色空间与人眼的感知差异很大,这

15、里采用较好符合人眼感知特性的 HSV 颜色模型。首先将图像中每一像素的 r,g,b 值转换为 h,s,v 值 (h 0,2,s 0,1,v 0,1, 然后将转换后将色彩空间划分为三部分 10:黑色区域 :所有 v <20%的颜色均归入黑色 , 令 h =0,s =0,v =0;白色区域 :所有 s <20%且 v >70%的颜色归入白色 , 令 h =0,s =0,v =1;彩色区域 :位于黑色区域和白色区域以外的颜色 , 其 h, s, v值保持不变。3.3.2.2 区域生长算法区域生长算法 11主要用于图像分割与合并,描述如下:将图像分成等面积的单元 .从左上角的第 1个

16、单元开始与其相邻的单元进行颜色比较 , 若两者相似且符合归并准 则 , 那么就将两者归并形成一个小片 , 并且计算该小片的平均颜色 . 若相邻的某单元与其颜色 不相似 , 则将该单元标以 “ 未完成 ”.继续将小片与其相邻单元逐个进行颜色比较 , 凡是与小片相似者并入小片使小片逐渐 生长扩大 , 直到没有再可归并的单元为止 . 然后将此生长完毕的小片标以 “ 已完成 ”.对于下一个 “ 未完成 ” 的单元重复上面生长小片的步骤 , 直到所有的单元都已被标记为 “ 已完成 ”.区域生长方法的关键是要使用合适的相邻单元合并的门限,本文设定颜色 (c 1 ,c2,c 3的距离门限为 0.512,进一

17、步提高区域生长方法的精度需要利用区域间的特征进行单元合并等后 处理工作 13,这里不作讨论。在图 1的模块 2中实现了测试图像的选择,实现算法为:1 设定 imagetype ,这里 imagetype 表示测试的图像类型,为正整数, 1表示连续色调图 像, 2表示离散色调图像, 3表示随机图像;将测试图像集中所有图像的 imageflag 置 0,这 里 imageflag 为测试图像集中图像的选中标志, 1表示选中, 0表示未选中,为布尔数;2 按照要求从测试图像集中随机选择一幅图像 A ;3 对选择图像数量 imagecount 进行判断。if imagecount=1算法结束;else

18、取 imagecount , imagemethod 值;for j=1:1: imagecount-1调用图像筛选算法;输出图像编号。endend这里 imagecount , imagemethod 的值由模块 1确定, j 为正整数;4 算法结束。图像筛选算法基于图像的特征,实现算法为:1 判断测试图像集每幅图像 imageflag 值。if imageflag=1选择下一幅图像;Else选择当前图像 B ; imageflag=1; 将图像由颜色空间转换为色度空间； 使用色度空间的划分规则对图像进行处理。 End 2用区域生长方法对图像进行区域分割与合并，并记录合并后每个区域的数据，包

19、括区 域的长度、宽度、色度平均值和色度均方差。 3依次比较 A 和 B 两幅图像中从大到小的 m 个区域的长度、宽度、色度平均值和均方 差，并计算两者的误差，如果所有参数的误差都在 20%以内，则认为是相似的，如果有一 个参数的误差超过 20%则认为是不相似的，不相似程度由误差的大小表示。这里 m 指图像 的区域数，如果有一幅图像区域数不足 m，则按较小的 m 取值。然后设定 similar 的值，0 表示相似，1 表示不相似，这里 similar 为布尔数。色度平均值定义式为： S= 1 m 1 Si m i =0 .5 色度均方差定义为： S'= 1 m 1 ( Si S 2 m

20、i =0 .6 其中Si表示某点的色度，m为正整数，i为整数且大于等于 0。 误差定义为： D= | X 2 X1 | ×100% X1 .7 式中 D 表示误差， X 1 表示原始图像的尺寸或其他参数值， X 2 表示待选取图像的尺寸 或其他参数值。 4）根据 imagemethod 和 similar 的值判断当前图像是否保留。 if imagemethod =3 /表示随机选取图像 保留当前图像； else /表示选取同类型或者不同类型的图像 imagemethod = imagemethod-1； if imagemethod=similar 保留当前图像； else 不保留

21、。 end end 5）算法结束，复位，imagetype=3，其它变量置 0。 3.3.3 AutoTA 分析方法 AutoTA 采用的分析策略与测试策略相对应， 如果是横向比较测试则分析压缩算法的性 能指标； 如果是纵向分解测试则分析压缩算法每一步的数据变化。 1 中的模块 5 实现这一 图 功能，具体算法描述如下。 /算法开始 判断 testmethod 的值。/testmethod 的值由模块 1 确定 -6- if testmethod=0 /横向比较测试 读取 n； 从数据库中取出 n 份性能指标； 绘制图表； else /分解测试 取得 blocksize*blocksize 的

22、原始图像数据；/blocksize 的值由模块 1 确定 从数据库中取出每步的跟踪数据；/大小为 blocksize*blocksize 绘制图表； End 4. 测试结果分析 AutoTA 可以自动地对压缩算法的性能进行测试，测试方法包括横向比较测试和纵向分 解测试，最后自动生成各种分析图表。这里给出对 DCT 和 DWT 算法进行测试与分析的结 果。 本文的测试环境均为 Intel Celeron CPU 1.70GHz,256MB 内存， DWT 进行的是三层变换， 选择的基小波为 w5/3。首先选择横向比较测试，AutoTA 根据测试图像选择算法自动选定了 四幅测试图像(bmp 格式：

23、lena、girl、copule 和 boat，设定的性能指标包括变换时间、反变 换时间和峰值信噪比，测试结果如图 2、图 3 所示。由图 2 可以看出 DCT 算法在编解码速 度上都要比 DWT 优越，而且较为明显，这主要是由于 DWT 要进行卷积运算的缘故；由图 3 可知两者在图像重建质量上较为接近，从曲线的变化趋势还可知，对不同的测试图像，两 者在重建时质量有相同的变化规律， 当然图像重建质量和 DWT 的变换层次和选择的基小波 也有关系。其次选择纵向分解测试，采用的测试图像为 lena(格式为 bmp，选择跟踪的块大 小为 4*4。得到 DCT 与 DWT 的变换数据如表 1 所示，A

24、utoTA 绘制的数据变化趋势图如图 4 所示。由表 1，可以看出 DCT 变换和 DWT 变换后多数能量都集中在左上角，DCT 越往右 下角方向，能量越小，而 DWT 的变换数据除了左上角的数据，其他数据相差不大，从而可 以说明 DCT 的能量集中特性和 DWT 的多分辨率特性；由图 4，可以看出经 DCT 与 DWT 变换后的数据变化趋势基本一致，但 DCT 数据存在跳变，这也是 DCT 存在块效应的原因。 图 2 DCT 与 DWT 时间性能对比图 图 3 DCT 与 DWT 重建质量对比图 -7- 表 1 图像原始数据与 DCT、DWT 变换数据 原始数据 变换数据 DCT 变 224

25、 29 -1 -2 换 13 5 -5 1 64 64 60 54 0 -9 2 1 66 63 53 46 2 2 -1 0 62 48 41 DWT 变 68 224 11 -1 8 61 54 45 46 换 27 -5 8 -1 2 7 -2 -1 7 3 -1 4 5. 结论 本文针对传统的压缩性能评价方法效率低，不全面等不足，设计了 AutoTA 系统。该系 统实现了压缩算法自动测试，性能指标计算，数据跟踪，测试结果分析和分析图表生成等功 能。 为了实现这些功能文中提出了压缩算法的性能测试方法， 基于特征的测试图像选择方法 和测试结果分析方法。与一般的工具平台相比，如 MATLAB

26、 等，AutoTA 具有明显的优势。 首先它不需要用户进行二次开发即实现了上述功能；其次，AutoTA 具有良好的时间性能， 图 5 显示了在 AutoTA 与 MATALAB6.5 上运行 DCT 算法得到的时间性能曲线， 从图中可以 看出 AutoTA 的运行效率远优于 MATLAB6.5；第三，AutoTA 操作方便，评价准确、全面。 文中提出的几种算法， 提高了系统评价压缩方法性能的准确性和全面性， 具有一定的理论意 义； 同时 AutoTA 能够协助科研人员和工程技术人员在实际应用中选择合适的图像压缩算法， 为用户提供了更大的方便,具有较大的应用价值。 图 4 DCT 与 DWT 变

27、换数据趋势图 图 5 AutoTA 与 MATALAB 时间性能对比图 参考文献： 1 Mathias Johanson. A SCALABLE VIDEO COMPRESSION ALGORITHM FOR REAL-TIME INTERNET APPLICATIONS. EC-VIP-MC 2003.4th EURASIP Conference focused on Video I Image Processing and Multimedia Communications, 2-5 July 2003, Zagreb. Croatia:329 2 M. Antonini, M. Barl

28、aud, P. Mathieu, I. Daubechies, “Image Coding Using Wavelet Transform,” IEEE Transactions on Image Processing, l(2. pp 205-220 (1991. 3 S. Mitra, and Shu-Yu Yang, “High Fidelity Adaptive Vector Quantization at Very Low Bit Rates for Progressive Transmission of Radiographic Images,” Journal ofElectro

29、nic Imaging, Vo1.8, No. I, pp 13-35, 1999. 4 K. Denecker, J. van Overloop, L. Lemahien, “ An Experimental Comparison of Several Lossless Image Coder for Medical Images,” Proceedings of the 1997 Data Compression Conference. -8- 5 Wang, Xiang-yang. The Principle of Multimedia Information Procession Te

30、lenology. Beijing : Science Press,2005(in Chinese 6MathWorks, Inc. MathWorks MatLab R14. 7 David S.Taubman, Michael W.Marcellin. JPEG2000 Image Compression Fundamentals, Standards and Practice. Boston :Kluwer Academic Publishers, 2001. 8 Zhang, Wei-ming. Multimedia Information System. Beijing: Publi

31、shing House of Electronics industry,2002(in Chinese. 9 David Salomon. Data Compression: The Complete Reference, Second Edition. New York: Springer-Verlag, 1998:204-220 10 WANG Tao, HU Shi-min, SUN Jia-guang. Image Retrieval Based on Color-Spatial Feature. Journal of Software, 2002,13(10:2032 11 Bian

32、, Zhao-qi. Patern Recognition. Beijing: Tsinghua University Press, 1986:262263 (in Chinese. 12 WANG Tao, HU Shi-min, SUN Jia-guang. Image Retrieval Based on Color-Spatial Feature. Journal of Software, 2002,13(10:2032-2033 13 Pavlidis, T., Liow, Y.T. Integrating region growing and edge detection. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1990,12(3:225133. 中文参考文献： 5王向阳.多媒体信息处理技术原理.北京：科学出版社，2005 8张伟明.多媒体信息系统.北京：电子工业出版社，2002 11 边肇祺.模式识别.北京：清华大学出版社,1986: 262263 AutoTA：A Te