（电路与系统专业论文）基于三维小波变换的视频压缩算法研究[电路与系统专业优秀论文].pdf

摘要 随着数字多媒体技术和网络技术的发展，视频图像编码算法显得越来越重 要。在追求图像编码质量的同时，编码算法在硬件上的运行效率也是一个很重要 的问题。本文就是以提高运行效率为出发点，提出了一种基于整数三维小波变换 的视频压缩算法。 小波技术由于其优秀的时频特性，在图像压缩中已经得到了广泛的应用。而 视频图像数据除了可以使用小波变换来处理单帧图像外，也可以使用小波变换来 进行帧问数据压缩。视频图像数据可以被看成三维数据体来进行三维小波变换， 对变换后的数据进行编码就可以达到压缩视频数据的目的。本文主要讨论了这种 三维小波变换的整数实现方法，以及对小波系数使用s p i h t 算法进行编码压缩， 并针对整数小波系数的特点，对s p i h t 算法进行了改进。仿真实验证明，本文 提到的方法压缩效果良好，运行效率高，输出码流具有嵌入式特性，是一种很有 应用前景的算法。 关键词：三维整数小波变换视频压缩小波系数编码 第2 页 a b s t r a c t w i t ht h ed e v e l o p m e n to fd i g i t a lm u l t i m e d i aa n dn e t w o r k ，t h ec o d i n ga r i t h m e t i c f o rv i d e oc o m p r e s s i o ni sm o r ea n dm o r ei m p o r t a n t b e s i d e st h ep i c t u r eq u a l i t y , t h e e f f i c i e n c yf o rt h ec o d i n ga r i t h m e t i cr u n n i n go nh a r d w a r ei sa l s ov e r yi m p o r t a n t t o i m p r o v et h ee f f i c i e n c y , t h i sp a p e ri n t r o d u c e sac o d i n ga r i t h m e t i cf o rv i d e o c o m p r e s s i o nb a s e do nt h r e ed i m e n s i o n a lw a v e l e tt r a n s f o r m a t i o n w a v e l e tt r a n s f o r m a t i o nh a sb e e nw i l d l ya p p l i e di ni m a g ec o m p r e s s i o nf o ri t s t r a n s c e n d e n c et i m e - f r e q u e n c ec h a r a c t e r i s t i c t h er e d u n d a n ti n f o r m a t i o nb e t w e e n f r a m e sc a nb ec o m p r e s s e dw i t ht h ew a v e l e tt r a n s f o r m a t i o n d i g i t a lv i d e od a t ac a nb e c o n s i d e r e da s3 - dd a t aa r r a y ss ot h a tw ec a np e r f o r m3 - dw a v e l e tt r a n s f o r m a t i o no n i t a f t e rt h et r a n s f o r m a t i o n ，t h ew a v e l e tt o e f f i c i e n t sc a nb ec o d e dt oa c h i e v et h e p u r p o s eo fv i d e oc o m p r e s s i o n t h i sp a p e ri n t r o d u c e sa ni n t e g r a li m p l e m e n t a t i o no f 3 - dw a v e l e tt r a n s f o r m a t i o n ，a n du s e sa ni m p r o v e ds p i h ta r i t h m e t i ct oc o m p r e s st h e w a v e l e tc o e f f i c i e n t s t h er e s u l t so ft h es i m u l a t e de x p e r i m e n ti n d i c a t et h a tt h e a r i t h m e t i cm e n t i o n e di n t h i sp a p e rc a r lp r o v i d eg o o dc o m p r e s s i o np e r f o r m a n c ea n d i m p r o v e de f f i c i e n c yw i t ht h eo u t p u tc o d eb e i n ge m b e d d e d t h i sa r i t h m e t i ch a sg o o d a p p l i c a t i o np o t e n t i a l k e yw o r d s ：3 - di n t e g r a lw a v e l e tt r a n s f o r m a t i o n ，v i d e oc o m p r e s s i o n ，w a v e l e t c o e f f i c i e n t sc o d i n g 第3 页 1 1 数据压缩技术 第一章绪论 计算机和网络技术的高速发展已经使人类社会进入了信息化时代，越来越多 的数据被交给计算机处理并通过互联网传输。数据量的不断膨胀给信息技术的发 展带来很大的压力。解决这个问题需要从两个方面入手。一方面要不断扩大计算 机的存储量和网络带宽，近年来计算机内存和硬盘容量都在飞速提高，诸如 d v d r o m 这种大容量的存储介质得到了广泛应用，同时各种宽带网也逐渐普 及。另一方面则要通过数据压缩来减少数据量。 数据压缩技术几乎与通信系统的设计同时发展。1 8 4 3 年出现的穆尔斯 ( m o r s e ) 电报码是最原始的变长数据压缩实例。1 9 3 8 年里夫斯( r e e v e s ) 、1 9 4 6 年德劳雷恩( e m d e l o r a i n ) 以及1 9 5 2 年贝尔公司德卡特勒( c c c u t l e r ) 分 别取得了脉冲编码调制( p u l s ec o d em o d u l a t i o n ，简写p c m ) 、增量调制( d e l t a m o d u l a t i o n ，简写为a m ) 和差分脉冲编码调制( d i f f e r e n t i a l p c m ，简写为d p c m ) 德专利。1 9 5 2 年，霍夫曼( d a h u f f m a n ) 给出了最优变长码的构造方法。直 到现在，已经出现了很多编码压缩算法。而关于数字压缩的理论研究，还是在仙 侬( c e s h a n n o n ) 信息论基础上开始的。1 9 4 8 年仙侬的经典论文“通信的数学原 理”中首次提到信息率一失真函数概念，1 9 5 9 年他又进一步确立了率失真理论， 从而奠定了信源编码的理论基础。随后又由伯杰f tb e r g e r ，1 9 7 1 ) 等人进行了深 入研究。 数字数据压缩按照压缩原理可以分为无损压缩和有损压缩。无损压缩可以保 证压缩前后数据的一致性，主要应用于文本、程序、数据库等不允许出现数据失 真的场合。有损压缩会在压缩过程中损失掉一部分信息( 即损失一部分信息熵) ， 它是以丢失部分信息为代价而获得很高的压缩比，主要应用在图像、多媒体视频 音频等数据的压缩上。 第6 页 1 2 视频压缩技术的发展概况 随着近年来多媒体技术的不断发展，视频数据被越来越多地应用到人们的工 作和娱乐中。同时互连网的普及使人们更多地使用网络进行视频通信。原始数字 视频数据的存储量是相当惊人的，一段6 4 0 x 4 8 0 x8 b i t 、3 0 帧秒的彩色数字元 视频，其数据量达到了2 1 0 9 m b i t s 。要存储和传输这么大的数据量，不经过压 缩是非常困难的。数字视频数据存在大量空间和空间上的相关性。根据人眼视觉 对细节不敏感的特点，我们可以通过变换编码来去除这种相关性，并丢掉一部分 不重要的信息，达到对视频数据的高比例压缩。 2 0 世纪8 0 年代后期以来，一种基于d c t 变换和运动补偿的混合编码方案在 视频压缩中得到了广泛应用，这种方法将图像看成是二维波形，利用d c t 变换 消除图像空间域上的冗余，以运动估计与运动补偿消除运动图像时间域上的冗 余，从而达到压缩数据的目的。此时基于这种变换方法，逐步形成了一系列国际 标准，如： 由国际电信联盟i t u ( 前称国际电报电话咨询委员会c c i t t ) 制定的，于1 9 9 0 年1 2 月公布的h 2 6 1 标准、于1 9 9 5 年推出并于1 9 9 6 年完善的在公用电话网上 传输甚低码率视频的编解碣标准h 2 6 3 和于2 0 0 3 年5 月公布的h 2 6 4 标准。 由国际标准化组织i s o 运动图像专家组( m o v i n gp i c t u r e se x p e l sg r o u p ) 制定 的，于1 9 9 3 年8 月公布( i s o i e c1 1 1 7 2 ) 的m p e g 1 标准、于1 9 9 4 年1 1 月公布 的( i s o i e c l 3 8 1 ) m p e g 2 标准和于1 9 9 9 年5 月公布的m p e g 一4 标准。 1 3 基于小波变换的视频压缩技术 小波的概念最先是8 0 年代初由法国地球物理学家m o d e t 在分析地震信号时 提出的1 8 1 。之后由于ym e y e r ，s + m a l l a t 和i d a u b e h i e s 等人的工作，小波分析 迅速发展起来，并被广泛应用到各种信号处理中。9 0 年代初，小波变换被应用 到图像压缩中【1 1 。1 9 9 3 年，由s h a p i r o 等人提出了嵌入式零树小波编码( e z w ) 算法 3 】，这种算法根据不同尺度下小波系数之间的联系，对小波变换后的系数进 行了量化和编码压缩。1 9 9 6 年，a s a i d 等人提出了一种更紧凑的多级树集合分 第7 磺 裂( s p i h t ) 编码算法【4 】。到9 0 年代末，i s o 组织将小波变换作为j p e g 2 0 0 0 标 准的基本变换方法。 小波变换由于其局部时频特性和多分辨率分析等优点，近年来已经成为静态 图像压缩算法研究的焦点。由于小波变换在图像压缩领域取得的巨大成功，人4 1 开始把小波变换应用到视频压缩领域，提出了很多种基于小波变换的视频变换和 编码算法。在这方面，国内外主要的研究方向分为两类： ( 1 ) 基于空域或变换域运动补偿的小波视频编科” 【3 4 。这种编码方案是先使用小 波变换消除空间冗余，再通过小波域的运动估计和运动补偿技术消除时间冗 余，最后对变换域的补偿残差进行小波压缩编码；或者先用运动估计和运动 补偿消除时间冗余，再用小波变换对每帧的差值信号编码。 ( 2 ) 基于三维小波变换的视频编码 6 j 1 1 】 1 2 】【2 l 】【2 2 埘j 。这种方法通过三维的子带小波 分解和编码，能够同时消除时间和空间上的冗余。 其中第一种方法和传统的基于运动补偿的视频编码算法在消除时间冗余的方 法上并没有本质区别。而第二种方法则采用的方法却在原理上不同，这种三维子 带小波变换方法是直接从二维图像子带小波编码算法扩展得到的，加入时间轴 后，图像序列被看作是三维信号。通过在水平、垂直和时间方向分别进行小波分 解，图像序列被分解到三维空间中的不同子带。这样序列的能量得到重新分布， 时间上的帧间冗余就可以和空间上的冗余信息一起通过编码来消除。相比第一种 方法，三维子带小波编码的优势在于编码器结构简单、容易实现嵌入式编码、消 除方块效应等，目前已经成为研究的热点。 总之，三维小波变换在视频编码算法的应用中体现出很多优秀的特性，本文 在这方面的研究显得很有意义。 1 4 本文内容安排 本文首先从图像压缩技术的发展谈起，总结了目前流行的图像和视频压缩技 术，并简略介绍了现在广泛应用的几种图像和视频压缩标准( 第一章和第二章) 。 接下来介绍了关于小波的基本思想和快速算法( 第三章) ，在此基础上详细介绍 了应用小波变换对静态图像和视频序列进行压缩编码的算法( 第四章和第五章) 。 第8 页 然后基于提高硬件执行效率的考虑，提出了一种基于整数三维小波变换的视频压 缩算法，最后对这种算法做了进一步的改进( 第六章) 。实验证明，本文提出的 算法在保证压缩质量的同时，算法在硬件上的运行效率有很大的优势。 第二章关于数字图像和视频压缩的基本理论 我们知道，数字图像数据中包含了大量冗余的信息。数字图像压缩既是消除 这些冗余信息。本章将对数字图像及视频压缩的基本原理和方法进行简要总结， 并介绍几种常用的数字图像及视频压缩的标准。 2 1 数字图像及视频压缩的基本原理 在我们日常生活中接触的图像经过量化表示成二进制数据存储在计算机中。 这些数据之间存在很强相关性。例如成片的色块、连续的线条、渐变的颜色、周 期重复的纹理等，都是这种资料间相关性的表现。图像压缩的基本原理就是消除 这种相关性，然后根据信息论原理将这些数据编码，以达到压缩数据的目的。 数字图像和视频压缩分为有损压缩和无损压缩。有损压缩通过丢失一部分人 眼不敏感的信息，可以达到很高的压缩比而不明显影响视觉质量。无损压缩可以 保持数据压缩前后的一致性。这两种压缩方法可以应用在不同场合。通常一个图 像编码和译码系统可以用下图表示： 第9 页 竺屯翌h 耍巫埒像 图像编码统统i 图2 1 图像编码和译码系统结构框图 原始图像数据首先通过变换或预测器( 如著名的d c t 变换) 编码为一种能 表示出空间和频域相关性的形式，然后通过编码和量化来消除这些相关性。如果 是有损压缩，一部分人眼不敏感的信息在这个过程中丢失了。编码后的图像最后 再通过熵编码器，用最短的码字表示出来，就得到了最终的压缩图像数据。图像 的译码基本上可以看作是编码的逆过程。 预测和变换技术是构成当前图像编码器最常用的技术，预测和变换的主要目 的是降低图像原始空间域表示中存在的非常强的相关性，使得预测或变换后的资 料矩阵变成低相关( 理想情况是无相关) 矩阵，这样可以用标量量化和一阶熵编 码技术进行有效的压缩。因此，预测和编码的首要目的是降低编码器的复杂性， 从而用简单的结构设计出高效的压缩编码算法。 图像的变换编码的应用非常广泛，理想的变换不仅去除相关，还可以将信号 的主要能量集中在很少的几个系数上，这实际是信号的一种更紧凑表示。通过量 化将细节信号除去，使量化矩阵变成一个非零值非常稀疏的矩阵，用很少的量化 系数逼近原始信号，然后通过有效的方法表示量化系数中的非零值位置和幅度， 以获得高压缩率。 第1 0 页 2 2 数字图像及视频压缩的常用方法1 5 】【3 5 l 2 2 1 预测编码 预测编码主要是根据相邻象素间存在很强的相关性，由前面的象素值预测当 前的象素值，由实际值减去预测值得到预测误差。由于这种强相关性，预测值会 比较接近实际值，因此预测误差序列的均值接近为0 ，且方差很小。一般预测误 差的阶熵远小于原象素值。对单象素的预测误差量化后进行熵编码，比直接对 单象素编码有更高的效率。 最常用的预测编码方法是差分脉冲编码器( d i f f e r e n t i a lp u l s ec o d em o d u l a t i o n ， d p c m ) 。其原理实际上就是上面描述的预测编码方法。它的编译码器的基本结 构如图2 2 所示。 ( a ) 预测编码器 ( b ) 译码器 图2 2 d p c m 的基本结构 对于视频信号而言，除了可以通过预测编码器消除单帧图像空间上的相关性 外，也可以利用前后帧间在时间上的相关性来进行预测编码，称为帧间预测。 第1 i 页 2 2 2 变换编码 变换编码方法主要是通过数学变换把数字图像数据表示到另一个域。一般来 说，在变换后的域，原信号的熵没有发生改变，信号的能量分布被重新组合，且 大部分能量集中到了少数几个变换系数上。采用量化和熵编码就可以有效地压缩 数据。同时，在变换域我们还可以利用人的视觉特性，如人眼的分辨率、空间概 率特性和视觉心理等，去除对图像主观质量影响较小的数据。 一个理想的变换方法能够使得变换系数之间完全是统计独立的，那么，变换 系数的一阶熵h ( y ) 就表示了该信源的无失真编码码率的下限。k l 变换被认为是 目前这种最理想的变换方法，然而就其实现的成本和实时性来说，这种变换又被 认为是最困难的”1 。目前最一种常用的变换编码是离散余弦变换( d c t ) ，d c t 变换的性能接近于理想变换，且有快速变换算法。现在d c t 变换已经成为了 h 2 6 1 、h 2 6 3 、j p e g 、m p e g 等国际标准的主要变换算法。 d c t 变换和反变换的主要公式如下： 砌) - a 丽1n 扩- i ) c o s 鼍】0 0 _ o 是尺度因子，b 是位移，b r ，其中 眦，= 忑1 收等) z ， 式( 3 1 ) 中的小波变换定义具有很深刻的含义，首先对它的时域性质做一下说 明：基本小波v ( t ) 可能是复信号或实信号在复信号时，般是取解析信号或近 似解析信号，例如图像的边缘，称为m o r l e t 小波，它是以高斯函数为包络的复 指数函数。复信号小波主要用于对信号频率的跟踪和估计，实小波信号则常用于 检测信号的瞬变特性和信号的变换域处理，例如图像的边缘检测、信号去噪和图 像编码等。 尺度因子a 的作用是对基本小波进行伸缩。a 越大，f 三1 愈宽，a 越小， a ， y 仁 越窄 a 1 a 与角频率o l 等价。改变a 则改变小波变换的分析区间。或者等 价地说，从时域观点i a 与角频率等价。改变a ，则改变小波变换的分析区间。 w t ( a ，b ) 反映两重特性，一方面，它仅反映了t = b 附近x ( t ) 的性质；另一方面它 也具有抽取x ( t ) 在r = b 附近的某一频率成分( 正比于l a ) 的能力，因此，小波变 换是一个时频联合分析的工具。a 称为尺度因子，它与分辨率是成反比的，a 越 大，( 吉) 越宽，小变换能够分辨两个突变发生所要求的时差就要增加，时域分 辨率降低；反之，a 越小 缈f 三1 越窄 l a 时域分辨率越高。由于a 是变量，在变 换过程中，为使v a b ( t ) 的能量保持相等，式3 2 前3 n n 子。 、a 第2 4 页 小波变换的等效频域表示为： ” 厂 暇( 咖) = 尝p ( w ( a c o ) e 脚d 珊( 3 3 ) 对于这个频域表达式，可以做进一步的说明：如果、l ，( t ) 是幅频特性比较集中 的带通函数，则小波变换便具有表征待分析信号i ( ) 频域上局部性质的能力， 改变a 的值，可以分析i t ( c o ) 不同领域区间的性质。 根据以上分析，小波变换的时频特性可以总结为： a 增加，降低 f 三 展宽 l 0 时域窗变宽，能够观测更长时间区间，同时 少驴( n ) 变窄，在频域能够观测更窄的频域窗，且频率中心向低频移动。这 相当于对于低频情况，小波变换对时间看得粗些，对时域看得细一些。 a 减小，增大，y f 丢 变窄，时域窗变窄，观测更短时间区间，同时痧( d ) 变宽，观测更宽的频域窗，且中心频率向高频方向移动。小波变换对于高频 情况，对时间域看得细一些，对频域看得粗些。 3 3 离散小波变换 如果在每个可能的平移尺度上进行小波系数计算，将导致复杂的计算并产生 过多的数据。如果首先对尺度因子和平移因子进行一定形式的取样，再用得到的 小波函数族进行小波变换，就得到了离散小波变换，它并没有降低精度，但却提 高了小波变换的效率。离散小波变换对实际应用具有更大的意义。 若口= 口? ，b = n b o 簖，其中 1 ；b o r ；m ， z 。则可得到离散小波： 。( f ) = 啄2 y ( 日i “f 一b o ) ( 3 4 ) 则离散小波变换为： d 。= = 厂( 缈。( t ) d t ( 3 5 ) 若f i t ) 也是离散的，记为f ( k ) ，则有 第2 5 页 d ，= ，( t ) l f ，。( k ) ( 3 6 ) 其逆变换的离散形式为 m ) = d 肌。= 。磊和甄分别为 魄和甑的镜像滤波器，即6 ( ) = ( 一女) ，季( k ) = g ( 一t ) 。又有 掣“= 丸。彰= 丘。群 ( 3 1 3 ) 酬“= 岛。群= 蜃：。群( 3 1 4 ) e zn e z 式( 3 1 3 ) 表明，信号f ( t ) 在分辨率j 下的离散逼近a j + 1 可以通过a j 与的卷 积并保留输出样本的偶系数上的值而得到。同理，式( 3 1 4 ) 表n ，分辨率j 下的 细节信号d i 可以通过a j 和氧的卷积并保留输出样本的偶系数上的值而得到。 a i 初始值即为信号f ( t ) ，信号最终可以被分解为一个低频逼近a j 和j 个细节信号 d 来表示。如图3 1 所示： 第2 7 页 图3 1 一维金字塔( p y r a m i d ) 分解过程 低频逼近 高频细节 滤波器和g k 2 _ f 日j 的关系为：g ( k ) = ( - 1 ) 。h ( 2 n - 1 一k ) ，n 为滤波器长度。魄和 甄为分解滤波器，和吼为综合滤波器，它们分别构成正交镜像滤波器对， 和魄是低通滤波器，鼠和是高通滤波器。 综上所述，一维多分辨率m a l l a t 分解算法将信号通过分解低通和高通滤波 器，将输出结果分为两部分，得到低频逼近信号和高频细节信号，其后低频逼近 信号经过相同的分解低通和高通滤波器，得到新的更高尺度下的低频和高频分 量，这样依次分解直到达到所需的分辨率为止。对一个长度为n 的信号，其分 解的最大层数为j = l 0 9 2 n 。 已i j d , 波分解后的各层信号 及d i ，则可通过m a l l a t 重构算法将原信号恢 复出来。它进行与分解算法相反的过程，在同一分辨率j 下的低频信号和高频信 号首先每二点补零，然后通过综合低通和高通滤波器，得到低分辨率的逼近信号， 再重复该过程即可获得重建的原始信号。 对于处理平面图像数据的二维小波分解算法，可以由水平和垂直方向上的两 次一维小波分解组合而成。如图3 2 所示。低频子带( l l ) 对应的是水平方向和垂 直方向上的低频分量，水平子带对应的是垂直方向的高频分量( l h ) 即水平边缘， 垂直子带对应的是水平方向的高频分量( h l ) 即垂直边缘，而对角子带对应的是水 平和垂直方向的高频分量( h i ) 。分解后图像集的数据量之和等于原图像的数据 量。 第2 8 页 l lh l l hh h 图3 2 二维小波分解示意图 图3 _ 3 显示了3 次二维小波分解后的数据分布。 l l 3 h l 3 h l 2 l h 3h h 3 h l ， l h 2 h h ， l h lh h l 图3 33 次二维小波分解后的数据分布图 图3 4 显示了对一个图像数据进行二维小波分解的过程。 第2 9 页 ( b ) 1 级小波分解( c ) 2 级小波分解 图3 4 图像数据的小波分解 3 5 提升和整数小波变换 3 5 1 提升小波变换1 2 小波基的一个重要性质就是由一个母函数的伸缩平移构成一个正交基。但在 第3 0 页 一些应用环境下，伸缩平移是不可能实现的，例如定义在球面上的函数就很难做 到伸缩平移，难以用传统的小波变换分析这类函数。 放弃用伸缩平移一个母函数构成小波基，也就可以不采用傅立叶变换作为主 要分析工具，在这样的前提下，出现了应用范围更广、计算速度更快的新一类小 波变换，s w e l d e n s 等提出的提升( 1 i f t i n g ) d , 波变换方法就是这样一类新的小波变 换工具。 传统研究的小波变换都是实数域的变换，即使待分析的信号本身是整数序 列，相应小波变换系数也是实数。由于数字图像一般都是用位数比较低的整数表 示，最常用的是8 位，我们也非常希望图像矩阵的小波变换是整数矩阵，也就是 希望有一种“整数集到整数小集的波变换”，将整数序列映像为整数小波系数， 并且这种映像是可逆的，具有这种性质的小波变换称为整数小波变换。用提升的 方法，很容易构造一般的整数小波变换。 提升方法具有如下几个优点： 1 可以实现更快速的小波变换算法，一般通过提升方法可以达到比m a l l a t 算法快2 倍的离散小波分解。 2 提升方法可以实现完全的同址运算，这一点与f f t 类似。 3 利用提升方法，正向小波变换和反变换结构是非常一致的，仅有正负号 的区别。 4 提升小波变换的描述非常简单，可以避免使用f o u r i e r 变换。 3 5 2 提升小波变换的基本方法 下面介绍提升小波变换的基本步骤，提升过程分为三步：分裂、预测和更新。 在离散情况下，给定数据集s ，通过一个提升过程将它分解成数据集s j ，也，使 得s j ，d j 是s 的更紧支的表示，通过一级完整的提升过程( 三步) ，得到尺度系 数s j ( 1 ) 和小波系数d j ( o ) 。 ( 1 ) 分裂 s w e l d e n s 使用了一种称作懒小波变换( 1 a z yw a v e l e t t r a n s f o r m ) 的方法将原始 信号sj 简单分作两部分：偶数序列s j ( o ) = s 2 j 和奇数序列d j ( o ) 2 s n + i 。不同的分 裂方式就相当于采用不同的小波基。在实现中，最常用的是用懒小波作为第一级 第3 i 页 分解。 ( 2 ) 预测 可以使用资料间的相关性来通过偶数序列s j ( o ) 预测奇数序列d j ( o ) ，预测值 为p ( s j ( o ) ) 。然后将奇数序列的值替换为原值d j ( o ) 跟预测值之差： d j2 d j ( o ) 一p ( s j ( o ) ) ( 3 1 5 ) 当预测值与原值接近时，d j 接近于0 ，数据间的相关性得到消除。 ( 3 ) 更新 为了使变换后的数据保持原信号的一些性质，需要采用更新过程对偶数序列 s j ( o ) 作修正。更新的过程与预测类似，利用更新操作数u 对d j 得到更新值u ( d j ) ， 然后将其与s j ( o ) 相加得到更新后的s j ： s j = s j ( o ) + u ( d j )( 3 1 6 ) 可以看到，此分解方式与离散小波变换的思想是一致的，将序列分解成更紧 致的表示方式，分裂方式、预测器的不同选择，等价于选取了不同的滤波器组。 变换的全过程如图3 5 所示： 图3 5 提升方法的分解过程 s j 实际上，s j 包含了信号的低频部分，d j 则包含了信号的高频部分。 其反变换可以当作上述变换的逆过程。如图3 6 ： s j d j 图3 6 提升方法的重构过程( 反变换) 第3 2 页 预测和更新所用到的操作数可以通过因子分解得到。并且s w e l d e n s 已经提到 可以通过提升的方法构造整数集到整数集的小波变换。其中一种最简单的变换是 以h a a r l j , 波构造的操作数： d j = d j 一s j o ( 3 1 7 ) s j = s j o + d j 2 f 3 1 8 ) 3 5 2 两种常用的提升小波变换 在图像压缩中，我们主要应用的是( 5 ，3 ) 整数小波变换和( 9 ，7 ) 实数小波变换。 d a u b e e h i e s ( 9 ，7 ) 小波变换定义的滤波器组如下： k低通滤波器 高通滤波器 o0 6 0 2 9 4 9 0 1 8 1 1 1 5 0 8 7 0 5 1 - i0 2 6 6 8 6 4 1 1 80 5 9 1 2 7 1 7 6 3 2 , - 2 0 0 7 8 2 2 3 2 6 7 0 0 5 7 5 4 3 5 2 6 3 , - 3 o 0 1 6 8 6 4 1 1 8o 0 9 1 2 7 1 7 6 3 4 ，一40 0 2 6 7 4 8 7 5 7 表3 1d a u b e c h i e s ( 9 ，7 ) 分解滤波器组系数 k低通滤波器高通滤波器 01 1 1 5 0 8 7 0 50 6 0 2 9 4 9 0 18 1 ，一1 o 5 9 1 2 7 1 7 6 3 0 2 6 6 8 6 4 1 1 8 2 , - 2 0 0 5 7 5 4 3 5 2 60 0 7 8 2 2 3 2 6 7 3 , - 3 0 0 9 1 2 7 1 7 6 3o 0 1 6 8 6 4 1 1 8 4 , - 4 0 0 2 6 7 4 8 7 5 7 表3 2 d a u b e c h i e s ( 9 ，7 ) 重构滤波器组系数 其正变换的算法可以描述为 第3 3 页 y ( 2 n + i ) 卜x 。( 2 n + 1 ) + 口( 土么( 2 n ) + 乙( 2 n + 2 ) 】； y ( 2 n ) 卜。( 2 n ) 4 - 卢 y ( 2 n 一1 ) 4 - y ( 2 n 4 - 1 ) ； y ( 2 ”+ 1 ) 卜y ( 2 ”+ 1 ) + y 。【y ( 2 ”) + y ( 2 ”+ 1 ) ； f 3 1 9 1 y ( 2 n ) 卜y ( 2 n ) 十占 y ( 2 n 一1 ) + y ( 2 n + 1 ) 】； 、 y ( 2 n 4 - 1 ) t o - - 一k y ( 2 n 4 - 1 ) ； y ( 2 n ) 4 - - ( 1 k ) y ( 2 n ) 其中的参数为 = 1 5 8 6 1 3 4 3 4 2 b = 0 0 5 2 9 8 0 1 18 v = 0 8 8 2 9 1 1 0 7 5 6 = 0 4 4 3 5 0 6 8 5 2 k = 1 2 3 0 1 7 4 1 0 5 ( 5 ，3 ) 小波变换是一个可逆变换，它的分解和重构滤波器组如下表所示 k 低通滤波器高通滤波器 06 81 1 ，一1 2 81 2 2 ，一2 1 8 表3 3 ( 5 ，3 ) 小波分解滤波器组系数 k低通滤波器高通滤波器 0l6 8 1 ，一1 1 ，22 8 2 , - 2 一l 8 表3 , 4 ( 5 ，3 ) 小波重构滤波器组系数 y、，(，2n。、+1)，=x，ex,，n(2nl乏；鐾。，：。， y ( 2 栉) = x 。( 2 n ) + ! 羔型! 二旦! j 掣 。 在实际应用中，d a u b e c h i e s ( 9 ，7 ) 小波变换和( 5 ，3 ) 小波变换各有长处。总体上 说，同样进行有损压缩时，d a u b e c h i e s ( 9 ，7 ) 小波能l t ( s ，3 ) 小波产生更高的p s n r ， 即压缩质量更好：而在算法复杂度上，( 5 ，3 ) 小波又比d a u b e c h i e s ( 9 ，7 ) 小波简单大 约一般，即处理时间是d a u b e c h i e s ( 9 ，7 ) j , 波的一半。从这种意义上来说不可逆( 9 ， 7 ) 小波变换并不是绝对优于可逆( 5 ，3 ) 小波变换。并1 1 ( 5 ，3 ) 小波变换复杂度低，可 以实现全过程整数运算，又能进行无损压缩，于是在选择变换基的时候，可逆( 5 ， 3 ) 小波变换有其可选性。 3 6 本章小结 本章主要讨论了小波变换的性质，基本原理和公式，介绍了离散小波变换和 提升小波变换的基本方法。提升法构造小波变换是目前的热点方法，它可以构造 整数集到整数集的小波变换。然后引入了两种广泛应用于图像压缩领域的提升小 波：d ( 9 ，7 ) 提升小波和( 5 ，3 ) 提升小波，这两种小波变换各自具有不同的特点。 第四章应用小波变换的图像编码方法 图像数据经n 级小波分解后形成一个四叉树形的结构。图4 1 显示了这种结 构，以h h 3 子带中的一个系数( i ，j ) 作为为根节点的一颗树为例，那么，h h 2 子 带内 2 i + m ，2 j + n o m ，n 1 共4 个系数是根节点的儿子节点，h h l 子带内 4 i + m ， 4 j + n 0 m ，n 3 共1 6 个系数是根节点的孙子节点，这个三层的树共包含了2 1 个系数值，根节点有2 0 个子孙。 这种树形结构主要反映了来自于不同尺度上描述同一位置小波系数的内在 联系。这种不同尺度上的描述具有相似性，称为尺度之间的自相似性。利用这种 树形结构中的相似性，就能构造一个编码器，经过编码后的小波系数能够以一种 跟紧凑的结构来描述这种树形结构，从而达到压缩数据的目的。 第3 5 页 拣p 封- 一、 划 p 过 划型 ： 、 j 、 捌封 图4 1二维小波系数的树形结构 s h a p i r o 在1 9 9 3 年提出了一个高效的编码算法，称为嵌入式零树编码算法 ( e z w ) 【3 ，这个算法的提出对基于小波变换的图像压缩算法研究产生了巨大影 响。而后p e a r l m a n 等人又提出了其改进的多级树集合分裂算法( s p i h t ) 【4 】、集合 分裂嵌入块编码( s p e c k ) 算法等。 4 1 嵌入式零树编码( e z w ) 3 】 4 1 1 零树 嵌入式零树编码算法中包含两个重要概念：嵌入式编码和零树。所谓嵌入式 编码是指编码器输出的码流具有这样的特点：一个低比特编码嵌入在码流的开始 部分，即从嵌入式码流的起始至某一位置这段码流被取出后，它相当于是一个更 低码率的完整的码流，由它可以译码重构这个图像。与原码流相比。这部分码流 译码出的图像具有更低的质量或分辨率，但译码的图像是完整的。因此，嵌入式 编码器可以在编码过程的任一点停止编码，译码器也可以在获得的码流的任一点 停止译码，其译码效果只是相当于一个更低码串的压缩码流的译码效果。嵌入式 码流中比特的重要性是按次序排列的，排在前边的比特更重要，显然，嵌入式码 第3 6 页 流非常适用于图像的渐进传输、图像浏览和因特网上的图像传播。在后面的算法 中，嵌入式码流的实现是由零树结构结合逐次逼近传输实现的。 零树就是指：对于给定的门限t ，如果一个四叉树的根节点及其所有子孙节 点的系数值均是无效值，根节点称为零树根。一个零树或零树根指的是由该根节 点起始的一棵树是零树，同时，该零树不是一棵更大零树的子集，也就是说被称 为零树根的节点，它的父节点不是零树根。 4 1 2 零树编码 通常小波系数中较小的值表示的是图像上细微的变化，也就是在人眼视觉特 性上容易忽视的变化。根据这个特点，在图像编码中就可以认为绝对值小于门限 t 的值是无效值。丢掉这部分数据后，可以实现更高比例的图像压缩。 对图像数据小波系数的编码过程是通过逐级量化的方法来确定系数的精度： 首先给定一个不大于最大小波系数幅度的门限t _ - t o ，将小于t 的系数都看成0 ， 完成对小波系数的第一次编码，然后用t = t 佗重复这个过程，直到t i 为止。 同时每次编码时还要对每个大系数用一个b i t 的数据量来细化大系数值的区间。 这样的编码过程可以根据需要的精度随时截断，具有嵌入式编码的特性。 为了构成一个完整的有效值映像，除了定义零树根( z t r ) 外，还需定义其它 三个符号：孤立零0 z ) ，表示当前系数值是无效值，但它的子孙系数中至少有一 个是有效值；正有效值( p o s ) ，表示当前系数是一个正的有效值；负有效值( n e g ) ， 表示当前系数是一个负的有效值。 有了这四个符号，可以按一定顺序扫描小波变换系数矩阵，从而形成一个符 号表，它就是要得到的有效值映射。扫描过程中，各子带可以按图4 2 所示的顺 序，在每个子带中，按从上到下、从左到右的次序，当遇到一个系数是正有效值， 将p o s 放入表中：当遇到一个系数是负有效值，将n e g 放入表中；当遇到一个 系数是孤零，将i z 放入表中；当遇到一个系数是零树根，将z t r 放入表中，同 时，对z t r 的所有子孙系数进行标注，因为已经知道它们是无效值，在今后扫 描到它们时跳过。具体扫描过程的流程图，如图4 3 所示。 第3 7 页 沙 董2 l 一夕 l 形 图4 2 嵌入式零树小波编码的扫描次序 输入一个系数 图4 3 有效值的判定过程 第3 8 页 跳过不 编码 z t r 放 入符号 表标注 所有子 4 1 3 逐次逼近量化 在编码过程中，除了需要一个主表记录重要系数的空间位置外，还需要一个 额外的辅表来记录各重要系数的值。这里用到了逐次逼近量化技术( s a q ) 来产生 一个嵌入式的码流。编码分为主、辅两个过程：在主过程中，设定当前阈值为 t o ，按上述判定方法对主表进行扫描编码，若是重要系数，则将其幅值加入到辅 表中，然后将该系数在数组中置零，这样当阈值减小时，该系数不会影响新零树 的出现；在辅过程中，对辅表中的重要系数进行细化，通过主扫描，已发现的有 效值的幅度处于t o 到2 t o 之间，这样如果不经过进一步细化，译码器能够用t o + t o 2 作为它的重构值。如果经过进一步的细化，通过1 b i t 的表示就能确定其 重构值在t o 到t o + t 啦之间还是在t 0 + t o 2 到2 t o 之间，即提高了t o 4 的精度。 零树表示和s a q 结合构成的编码器的工作方式概括如下：首先给出t 0 ，进 行第一遍主扫描，构成有效值映射，形成主表，然后进行第一起副扫描，细化有 效值的表示。更新门限，t l = t o 2 ，进行新一遍主扫描，新的主扫描时，对已经 发现的有效值的位置，不需扫描，将它们设为0 ，以便用于发现零树，因为门限 已减半，会发现一些新的有效值；主扫描结束，进入新一遍副扫描，对原已发现 的有效值和本次新发现的有效值进行细化处理。继续取t 2 = t l 2 作为新门限， 这个过程继续进行下去，直到预设条件达到而结束。 可以看出，在编码过程中，为了使各门限t i 均为整数，t o 的选取应当为不 大于最大小波系数绝对值的2 的整数次幂。 4 2s p i h t 编码算法【4 】 4 2 1s p i h t 算法的基本思想 s p i h t 算法是多级树集合分裂( s e tp a r t i t i o n i n gi nh i e r a r c h i c a lt r e e s ) 算法的缩 写，它是对e z w 算法的一种更一般化的表示，它吸取了零树的许多思