采用离散小波变换和游程长度编码的图像压缩与恢复*
2012-12-17蒋正金张长江端木春江
蒋正金, 张长江, 端木春江
(浙江师范大学数理与信息工程学院,浙江金华 321004)
0 引言
信息时代的到来,数据量呈现爆炸式增长,无论传输或存储这些海量数据都需要对数据进行有效的压缩.在遥感技术中,各种航天探测器采用压缩编码技术,将获取的巨大信息送回地面.图像压缩就是数据压缩技术在数字图像上的应用,它的目的是减少图像数据中的冗余信息,从而能采用更加高效的格式存储和传输图像[1].
常用的图像压缩编码方法有熵编码、预测编码、变换编码和混合编码等[2].随着图像编码技术的发展,许多新的压缩方法被提出,如利用人工神经网络的压缩编码、分形编码、基于对象压缩编码和基于模型的压缩编码及小波图像编码方法等[3].
离散小波变换(discrete wavelet transform,DWT)具有频率分解的特点,能把图像信号的能量聚集于某些频带中.由于离散小波变换具有聚能特性和位平面码流中有大量的连“0”,所以游程长度编码(run length encoding,RLN)是适应该情况的有效编码[4].
本文在研究离散小波变换和游程长度编码的基础上,提出了一种采用离散小波变换先对图像进行3层分解,并对分解后的图像进行游程长度编码实现图像压缩,然后进行游程长度解码和离散小波逆变换实现图像恢复的方法.
1 离散小波变换
1.1 定义
一维离散小波的定义可由下式表示:
式(1)中,一般m,n取整数.为了便于计算机处理,对平移时间也进行离散化处理,且保证小波函数生成的小波为标准正交基,选择a0=2,b0=1,则得到二进离散小波变换如下式所示:
习惯上简称式(2)为离散小波变换.进一步推广可以得到二维离散小波变换.而且小波变换要可逆,即要存在逆变换.
1.2 特点
离散小波变换具有多分辨率(也叫多尺度)的特点,可由粗及细地逐步观察信号.通过其定义式可以看出,其变换过程可以看成用基本频率特性为ψ(ω)的带通滤波器在不同尺度a下对信号进行滤波处理.这样,通过适当地选择基小波,使ψ(t)在时域上为有限支撑,ψ(ω)在频域上也比较集中,这样就可以使小波变换在时域、频域上都具有表征信号局部特征的能力,有利于检测信号的瞬态或奇异点[5].
借助于离散小波变换的这种分析工具,可将信号分解成许多具有不同的分辨率、频率特性和方向特性的子带信号,实现同时处理低频长时特征和高频短时特征.而小波基,在关于伸缩平移的特性上与分形几何的全局与局部的自相似性以及小尺度下的精细结构间存在许多内在的联系[6],这是本文中将离散小波变换与游程长度编码结合起来用于图像压缩与恢复的理论基础.
因为若对图像作j层离散小波分解,则小波分解的尺度a=2j.所以,当离散小波变换用于图像分解时,图像的尺寸M×N必须满足M=2p,N=2q(p,q∈1,2,…),即图像尺寸必须是2的整数次方.
2 游程长度编码与解码
2.1 基本原理
游程长度编码是一种能够有效消除或减小像素间冗余的编码算法,仅存储一个像素的灰度或颜色值以及具有相同灰度或颜色值的像素数目,尤其是对某些相同灰度值成片连续出现的图像非常有效.游程长度编码尤其适用于计算机生成的图形图像,对减少存储容量效果明显.
一幅图像中往往有许多灰度或颜色相同的图块.在这些图块中,许多连续的扫描行都具有同一种灰度或颜色值,或者同一扫描行上有许多连续的像素都具有相同的灰度或颜色值.在这种情况下就可以不需要存储每一个像素的颜色值,而仅仅存储一个像素的灰度或颜色值以及具有相同灰度或颜色值的像素数目.其压缩率的大小取决于图像本身.若图像中具有相同灰度或颜色值的横向色块越大,则这样的图像块数目越多,压缩率就越大,反之就越小.
例如,一个数组为[10,10,10,24,24,33,33,33,33],这个数组的长度为 9 个数字,如果采用游程长度编码为[3,10,2,24,4,33],则将长度压缩成了6个数字.因此,图像中相邻像素的灰度或颜色值越接近,压缩的效果就越好,故游程长度编解码比较适合于此类图像.但对于实际的场景图片,例如另一个数组为[1,2,3,3,5,7,7,8,9],这个数组的长度也为 9 个数字,若采用游程编码为[1,1,1,2,2,3,1,5,2,7,1,8,1,9],则可以看到编码后成了14个数字,比编码前更长,不但没有压缩效果,而且增加了冗余数据.解码的过程相对容易,直接根据像素灰度或颜色值和对应的个数一次性地填充到原来的图像中去即可.
2.2 具体实现
经典的游程长度编码是横向扫描.本文以4张标准测试图像 lena.bmp,dollar.bmp,bridge.bmp和aerial.bmp为例进行实验仿真.编码过程首先读入图像,图像采用二维矩阵保存,每个像素的灰度作为矩阵对应的取值.确定图片尺寸就可以确定行、列循环的终点.读取第一个像素的灰度值后开始横向扫描,扫描时若灰度值相同,则计数器加1,累计下去直到不相同灰度值的像素出现为止,此时计数器清0,保存新的灰度数值继续进行上述操作,直到整个图像被扫描完毕.
解码过程首先读取编码后的灰度值,根据相同灰度值的像素个数依次还原或者填充到解码矩阵中.还愿一个像素计数器减1,直到计数器减为0,重新读取一次新的灰度值分量和对应的像素个数,一直进行类似的操作,直到整个解码矩阵填充完毕结束.从上述过程可以看出,关键的2个信息就是灰度值分量和扫描过程中相邻相同灰度值的像素个数.这两部分信息在编码和解码中起了至关重要的作用.
若要实现无损压缩与恢复,则解码矩阵必须和原始图像完全一致.本文是对3层分解后的离散小波的图像进行编码和解码,因此,它属于有损压缩.
3 实验仿真与结果分析
3.1 实验仿真
为了检验经过离散小波变换和游程长度编码对图像进行压缩和恢复的性能,本文选取了4张尺寸为512 ×512 的标准测试图像 lena.bmp,dollar.bmp,bridge.bmp 和 aerial.bmp 的灰度图像进行 MATLAB实验仿真.实验仿真环境为:IntelⓇDual-CoreTM2.00 GHz,CPU,1.50 GB RAM,MATLAB 7.8.0(R2009a).
实验仿真结果见图 1 ~ 图8,图1、图3、图5、图 7 分别是测试图像 lena.bmp,dollar.bmp,bridge.bmp和aerial.bmp的仿真结果,其中:(a)为原始图像;(b)为经过离散小波作3层分解后的图像;(c)为经过游程长度编解码且由离散小波逆变换后恢复的图像;(d)为原始图像与恢复图像的误差图.图2、图4、图 6、图8 分别是 lena.bmp,dollar.bmp,bridge.bmp 和 aerial.bmp 图像仿真结果图对应的直方图,其中:(a)为原始图像的直方图;(b)为经过离散小波作3层分解后的图像的直方图;(c)为经过游程长度编解码且由离散小波逆变换后恢复的图像的直方图;(d)为原始图像与恢复图像的误差图的直方图.
3.2 结果分析
从图1及图2可以看出,lena.bmp图像由于灰度值相同且相邻的像素点多,或者说图像的相邻像素灰度值的相关性高,所以采用游程长度编码的情况下,编码解码情况良好,恢复图像与原始图像误差较小,压缩率也较高.
从图3及图4可以看出,dollar.bmp图像由于灰度值相同且相邻的像素点相对较少,或者说图像的相邻像素灰度值的相关性低,所以采用游程长度编码的情况下,编码解码情况稍差,恢复的图像与原始图像的误差偏大,压缩率也较低.
图1 测试图像lena.bmp的仿真结果图
图2 测试图像lena.bmp仿真结果图的直方图
图3 测试图像dollar.bmp的仿真结果图
图4 测试图像dollar.bmp仿真结果图的直方图
从图5及图6可以看出,bridge.bmp图像由于灰度值相同且相邻的像素点相对更少,或者说图像的相邻像素灰度值的相关性更低,所以采用游程长度编码的情况下编码解码情况更差,恢复的图像与原始图像的误差更大,压缩率也更低.
从图7及图8可以看出,aerial.bmp图像与dollar.bmp图像类似,由于灰度值相同且相邻的像素点相对较少,或者说图像的相邻像素灰度值的相关性低,所以采用游程长度编码的情况下编码解码情况稍差,恢复的图像与原始图像的误差偏大,压缩率也较低.
对标准测试图像lena.bmp和dollar.bmp进行压缩与恢复的性能对比见表1;对标准测试图像bridge.bmp和aerial.bmp进行压缩与恢复的性能对比见表2.
表1 标准测试图像lena.bmp和dollar.bmp压缩与恢复的性能对比
表2 标准测试图像bridge.bmp和aerial.bmp压缩与恢复的性能对比
从表1及表2可以看出:对标准测试图像lena.bmp压缩与恢复的性能明显好于对标准测试图像dollar.bmp,bridge.bmp和aerial.bmp的压缩与恢复性能,前者压缩率高,而且误差小、耗时短,后面三者压缩率低,误差大、耗时长.由此可以看出,该方法处理图像像素灰度值相对集中和相关性高的图像能取得较好的效果,但对于图像像素灰度值相对分散和相关性差的图像效果不是很理想.
4 结束语
本文提出将离散小波变换与游程长度编解码相结合实现图像的压缩与恢复的方法,通过对标准测试图像 lena.bmp,dollar.bmp,bridge.bmp 和 aerial.bmp 进行 MATLAB 实验仿真,证明了该方法的可行性,尤其是对于像lena.bmp这种像素灰度值相同且相关性高的图像,不但能够实现较好的压缩与恢复,而且具有压缩率高、误差小、耗时短等优点.
与目前广泛使用的JPEG算法相比较,本文提出的算法实现起来相对简单,因为JPEG算法中必须经过颜色模式转换及采样、离散余弦变换(discrete cosine transform,DCT)、量化和编码.当然,本文的方法在处理像dollar.bmp,bridge.bmp和aerial.bmp这种像素灰度值相同且相邻和相关性不高的图像时,虽然能够实现压缩与恢复,但性能有所下降,要提高对任意图像的压缩与恢复性能,需要进一步研究改进编解码算法.
[1]赵婷婷.基于游程编码的图像处理系统设计[J].经营管理者,2010(11):280.
[2]Haritaoglu I,Harwood D,Davis L S.W4:Real-time surveillance of people and their activities[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2000,22(8):809-830.
[3]Tao Zhao,Nevatia R.Tracking multiple humans in complex situations[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2004,26(9):1208-1221.
[4]祝本明,刘桂华.基于小波游程编码的改进算法[J].火力与指挥控制,2009,34(6):4-6.
[5]娄莉,刘天时.基于小波与分形相结合的图像压缩优化算法[J].微电子学与计算机,2010,27(6):145-148.
[6]Star k H G.Fractal graphs and wavelet series[J].Physics Letters A,1990,143(9):443-447.