（信号与信息处理专业论文）基于小波变换的视频压缩加密的研究.pdf

中国科学技术大学硕士毕业论文 摘要 近十几年来，随着网络的发展，数字视频在这个领域有了越来越多的应用， 相应的数字视频技术研究也日趋深入，视频安全性问题的解决需求也同益紧迫。 同时由于小波理论研究的不断深入，小波图像压缩的应用研究已经相当成熟。在 此背景下，基于小波的视频压缩和加密的研究已成为现今研究的热点。小波变换 具有的时频分辨率、多尺度表示、去相关和能量压缩等良好的特性，使其能有效 地对非平稳的图像和视频信号进行分析和压缩，而且小波变换良好的可操作性也 为视频加密提供了很好的平台。因此研究基于小波变换的视频压缩加密对视频的 推广应用有重要意义。 本文主要内容及创新工作： 1 对基于小波的视频压缩加密算法进行了研究，提出了一种基于小波变换 的压缩加密框架，采用二维离散小波变换和基于块的运动估计和运动补偿技术来 实现视频编解码器，并在编码的同时进行了小波系数加密和运动矢量加密。 2 压缩框架中选择提升算法实现快速小波变换，通过非均匀量化、小波零 树编码和自适应算术编码实现视频压缩。实验结果表明本文中的压缩框架对视频 序列的编码达到了与h 2 6 3 可比的压缩性能，且主观质量优于h 2 6 3 。 3 对比参考国内外小波系数置乱算法，提出了一种新的小波系数置乱算法 c w b ，对小波系数和运动矢量置乱，实现视频加密。实验结果表明本文中提出的 新算法具有加密效果好，密钥开销较小，安全性好等优点，且对压缩比和压缩效 率有较好的保持。 关键词：小波变换：提升法：零树；小波系数置乱；运动矢量置乱 中国科学技术人学硕士毕业论文 a b s t r a c t w i mt h ed e v e l o p m e n to ft h en e t w o r k t h ed i g i t a lv i d e oh a sb e e nm o r ew i d e l y u s e di nt h i sf i e l di nt h el a s td e c a d e s ，a n dt h er e l e v a n t t e c h n o l o g y ( c o m p r e s s i o n ， e n c r y p t i o n ) h a sa l s ob e e nm o r em a t u r e t h ea p p l i c a t i o nr e s e a r c ho fw a v e l e t b a s e d i m a g ec o m p r e s s i o ni sb e c o m i n gm a t u r e a st h ew a v e l e tt h e o r yr e s e a r c hp r o c e e d s u n d e rt h i sb a c k g r o u n d ，t h ew a v e l e t b a s e dv i d e oc o m p r e s s i o na n de n c r y p t i o nr e s e a r c h h a sd r a w nm u c ha t t e n t i o n t h ed e s i r a b l ep r o p e r t i e so fw a v e l e tt r a n s f o r ms u c ha s t i m e - f r e q u e n c y r e s o l u t i o n ，m u l t i s c a l er e p r e s e m a t i o n ，d e c o r r e l a f i o n a n d e n e r g y c o m p a c t i o n ，h a sm a d e i ta ne f f i c i e n tt o o lf o ra n a l y z i n ga n dc o m p r e s s i n gi m a g ea n d v i d e o s i g n a l s w h i c ha r en o t s t a t i o n a r y a n d i t s g o o dm a n e u v e r a b i l i t y h a sa l s o p r e p a r e daf l a tr o o ff o rv i d e oe n c r y p t i o n t h er e s e a r c ho fv i d e oc o m p r e s s i o na n d e n c r y p t i o n i sp r o p i t i o u st ot h ee x t e n s i o na n d a p p l i c a t i o no fd i g i t a lv i d e o t h em a i nw o r ka n dt h ei n n o v a t i o ni nt h i sd i s s e r t a t i o n ： 1 im a k es o m es t u d i e si nw a v e l e t - b a s e dv i d e oc o m p r e s s i o na n de n c r y p t i o n 1h a v e b r o u g h tf o r w a r d aw a v e l e t b a s e df r a m eo fv i d e oc o m p r e s s i o na n de n c r y p t i o n t h i sf r a m eu s e d2 dd i s c r e t ew a v e l e tt r a n s f o r i l la n db l o c k b a s e dm o t i o ne s t i m a t i o n a n dc o m p e n s a t i o nt oa c h i e v ev i d e oc o d e r ，a n de n c r y p t e dw a v e l e tc o e f f i c i e n ta n d m o t i o nv e c t o rd u r i n gt h ec o m p r e s s i o n 2 t h ef r a m ec h o s ef a s tw a v e l e tt r a n s f o r m u s i n gl i f t i n g ，s c h e m e ，n o n u n i f o r m q u a n t i z a t i o n ，t h er e a l i z a t i o no f z e r o t r e ec o d i n ga n da d a p t i v ea r i t h m e t i cc o d i n gt o a c h i e v ev i d e oc o m p r e s s i o n t h ee x p e r i m e n t a lr e s u l ts h o w st h a tt h ec o d e rm a t c h e s t h ep e r f o m a a n c eo fh 2 6 3 t h es u b j e c t i v eq u a l i t yo ft h i sw a v e l e tv i d e oc o d e ri s s u p e r i o rt oh 2 6 3 3 a f t e rc o n t r a s t e dw i t ho t h e rw a v e l e tc o e f f i c i e n tc o n f u s i o nm e t h o d s ，ii n n o v a t e da n e ww a v e l e tc o e 腼c i e n tc o n f u s i o nm e t h o dc w bw h i c hi sw o r kw i t hm o t i o n e n c r y p t i o nt oa c c o m p l i s hv i d e oe n c r y p t i o n t h ee x p e r i m e n t a lr e s u l ts h o w st h a t t h i sm e t h o dc a r l g e t b e t t e re n c r y p t i o ne f f e c t ，l o w e rc o s to nk e yc o s t ，h i g h e r s e c u r i t ya n ds m a l li m p a c t o n c o m p r e s s i o ne f f i c i e n c ya n dc o m p r e s s i o n r a t i o k e y w o r d s ：w a v e l e tt r a n s f o r m ；l i f t i n gs c h e m e ；z e r o t r e e ；w a v e l e tc o e f f i c i e n ts h u f f l e m o t i o nv e c t o rs h u f f i e 4 中国科学技术大学硕士毕业论文 第一章引言 1 1 课题背景及研究意义 随着数字化的迅速发展，视频在我们工作、学习和生活中的应用已经十分广 泛，大量的视频需要进行传输和存储等处理。然而视频信号巨大的数据量，对现 有的数据存储能力和数据传输能力提出了极大的挑战。为此，我们需要对视频信 号进行压缩。所谓“压缩”，就是指寻求原始信号的另一种表达方式，它通过减 少原始表达方式中韵冗余信息，而实现以更少的数据量来表达的目的。视频信号 中存在的冗余现象，如时间冗余、空间冗余、视觉冗余等，为视频压缩提供了可 能。同时这些视频所包含的信息，有的涉及到个人的隐私和生命的安全、有的 涉及公司的巨大商业利益、有的甚至涉及到国计民生和国家安全，其价值无法衡 量，因此不同程度地需要保密。以前，一方面由于数字图像和视频的应用还升i 广 泛，少量的应用直接使用密码技术加密就可以满足需要，另一方面，通过使用专 线、禁入控制等方法，通信信道本身也可以方便地提供一定程度的保密功能，加 之技术上的局限性，数字视频加密技术还没有受到高度重视。随着多媒体技术、 特别是网络通信技术的飞速发展和普及，以及无线通信技术的广泛使用，使得愈 来愈多的人更容易接触和获取传输存储处理中的数字图像和视频，威胁到其中所 含信息的安全。因而视频信号的保密工作及其加密披术的研究就显得十分紧迫和 重要。 视频压缩可以理解为通过编码、量化等过程将原本较大的视频流压缩为占用 空问较小的码流以便存储和传输。它所实现的功能就是将视频占用的空间缩小。 那么视频加密将要对视频进行什么操作昵? 它又是如何解决随着网络和数字视 频发展所带来的安全问题呢? 视频加密就是通过密钥与图像中的某些特定参数 进行某种设定的操作后从而改变图像数据的排列，使人们无法在未经解密的情况 下获得正确解码的视频。它所实现的功能就是对视频码流的排列进行改变。没有 解密就无法获得正确解码的视频，换言之就是无法看到未经授权的视频，从而保 证了所需要的数字视频保密，从而确保了安全性。 适用于视频数据的加密技术，应建立在视频流信源特征基础上。视频流信源 中国科学技术大学硕士毕业论文 特征主要有：( 1 ) 数据量大。例如，一秒钟的n t s c 彩色视频就有2 3 m b 的数 据量：( 2 ) 要求实时性处理。为了保证流畅的视觉效果，视频实时播放帧速率 通常为每秒2 5 3 0 帧( f p s ) 之间。( 3 ) 一般按国际标准编码，视频流采取分 层式数据结构，各层都有明确标志，用于解码和检索等；( 4 ) 各部分数据的重 要性不均等，部分数据更重要 2 0 , 2 1 。 视频流的这些信源特征决定了其适用加密方案应考虑以下几点： 1 )数字视频( 图像) 加密的计算量通常缀大，又必须实时以保证流畅，因此 要求计算简捷，处理速度高； 2 )对全部数据加密，使视频流中的标志码不能识别，无法实现视频在线检索 等功能( 2 2 0 3 j ； 1 2 国内外研究现状 数字视频在许多方面与静止图像有相同的特性，例如数据量大、结构性强、 各部分数据的重要性不相同，视频的帧内编码与静止图像编码类似。另外，为了 保证流畅的视觉效果，视频加密必须在一定时限内实时处理大量数据，因此要求 有很高的实时处理速度。 下面是视频加密的几种方法： 1 )传统加密 这是最早的高密级视频加密方法，如图1 1 所示，是对全部视频数据流直接 用密码技术加密和解密1 2 4 1 ，由于密码技术已有许多安全可靠的成熟算法，以二 维或多维数据表示的图像和视频传输和存储时都要映射( 例如通过编码) 变成一 维数据，若不考虑具体数据特征，很适合直接应用已有的成熟密码技术加密，也 易于实现。但是由于图像和视频信号数据量很大，所以这种加密方法计算量非常 大，不仅浪费资源，而且难以保证实时性。 2 ) 置乱技术 图1 1 传统加密方法( 单纯密码学方法) 6 中国科学技术大学硕士毕业论文 设每帧图像像素的灰度( 色彩) 值为：f ( x ，y ) ，其中( x ，y ) 为像素的坐标，置 乱技术一般是按某种算法( 如基于d e s 2 外、a r n o l d 变换、幻方、h i l b e r t 曲线、 c o n w a y 游戏、正交拉丁方2 7 l 等) 随机改变( x ，y ) 的值( 或f ( x ，y ) 的值) ，使原图 像无法辨认，解密时恢复原( x ，y ) 值。置乱过程虽然可以在图像的空间域( 色彩空 间、位罱空间) 上进行，但置乱后的图像不具备空间相关性，难以压缩。因此不 适合视频的压缩传输要求。一般情况下，置乱在变换域中进行。如果先将图像经 d c t 或小波变换，再对变换域系数按同样算法置乱，效果更好，而且可以只对少 量重要系数置乱，减少计算量。本文中采用的加密主要算法就是基于d w t 的频域 置乱方法。 3 ) 选择性加密 它主要思想就是只对选择的重要数据进行加密，这里主要包括( 1 ) 加密i 帧算 法，仅对i 帧d c t 系数块加密，具有扩散作用，使p b 帧利用运动补偿进行差值 编码的相应块不加密也难以正确解码，达到了选择部分数据加密减少计算量的目 的：( 2 ) 运动矢量加密算法：随机改变运动矢量的符号位或同时改变符号位和数 值来影响p 帧正确解码【2 8 】。对i 帧编解码完全没有影响，故不能单独使用，主 要作为增强安全性的补充算法【2 9 1 。加密数据量小，计算量小因而速度快：不降 低编码压缩率，只适用于视频( 运动图像) 编码数据：( 3 ) 头信息加密算法：将 头信息加密，再与其它数据随机混合【3 0 1 ，使接收方难以按原数据结构区分结构 信息和视频信息并解码。该算法不降低压缩率，计算量小。但是安全性较低，因 为头信息所含信息量小，加密效率低，这种加密方式比较容易破译。这类算法均 为辅助加密算法，必须与其他加密算法配合使用否则其太低的安全性就使加密 失去了意义。 4 ) 熵编码加密 比如采用h u f f m a n 编码的时候，将通用h u f f m a n 码表修改( 加密) 后使用【3 2 1 ， 并作为密钥。非法接收方无此特殊码表，不能正确解码。该算法完全不增加计算 量。但是一般改变h u f f m a n 码表，会降低压缩率。 1 3 本文主要研究工作 小波分析是一种较新的信号分析工具，其具有的时频分辨率使得小波变换能 够更加有效地对非平稳信号进行分析，因此在图像、视频处理领域得到了只益广 中国科学技术大学硕士毕业论文 泛的应用。基于小波变换的图像压缩，不需要对图像进行分块，从而有效地消除 了基于块变换所导致的方块效应，如图1 2 所示。此外，小波变换所具有的多分 ( a ) 采用d c t 变换( t 5 ：1 )( b ) 采用离散小波变换( d w t ) ( 15 ：1 ) 图1 2i 帧编码c a r p h o n e 第1 帧 辨率分析特性，使得基于小波变换的图像和视频编码能够更加容易地实现可伸缩 性编码。如图1 3 所示，对一幅图像编码后形成段码流，解码端可以通过对该 码流进行不同的截断，重建出具有不同分辨率和质量的图像。 图1 2分辨率和质量的可伸缩性编码 由于小波变换的良好性能和可操作性，本文中提出了一种基于小波变换的视 频压缩加密方案。我们搭建了一个视频压缩平台，将自己设计的加密算法在此平 台上实现。并通过实验对整个压缩加密方案进行性能分析。 各章内容安排如下： ( 1 ) 第2 章为基于小波变换的视频压缩平台介绍： 中国科学技术大学硕士毕业论文 a ) 论述小波理论以及实现小波变换的提升算法； b ) 小波零树编码算法； c ) 量化方法； d ) 熵编码方法，即g o l o m b r i c e 编码和自适应算术编码； ( 2 ) 第3 章为基于小波变换的视频加密： a ) 小波系数加密模块，主要分析了3 种经典的小波系数置乱算法和性能， 提出了一种新的的小波系数置乱算法，并比较分析其性能： b ) 运动矢量加密模块，介绍了流行的运动矢量加密算法； ( 3 ) 第4 章为实验结果，将我们的编码器的压缩性能与其它的编码器进行了比 较：同时对自己提出的加密算法和其他算法进行了性能比较分析； ( 4 ) 第5 章是结束语，对本文的工作进行了总结，为下一步的改进工作提出了 建议。 9 中国科学技术大学硕士毕业论文 第二章基于小波变换的视频压缩平台 本文提出的视频加密方案是在基于小波变换的视频压缩平台中实现的。该压 缩平台采用了基于空域运动补偿的小波视频编码( m c d w t ) 方案。它利用空域运 动估计和运动补偿技术消除时间冗余，然后对残差图像进行二维小波变换以消除 空间冗余。采用这种方案能直接利用现有的已比较成熟的空域运动估计和运动补 偿技术，同时达到利用小波压缩技术的优点，取得较好压缩效率的目的。 图2 i 为基于小波变换的视频编码加密器的系统框图。 图2 1基于小波变换的视频编码器的系统框图 通常，视频帧分为i 帧和p 帧进行编码。i 帧直接采用小波零树编码算法进 行编码。p 帧则首先利用前一个视频帧进行基于块的运动估计和运动补偿，形成 当前帧的预测帧，再将当前帧与预测帧相减得到的残差用小波零树编码算法进行 编码。 该平台采用与传统的基于d c t 的混合编码类似的方式来消除相邻视频帧问 的时间冗余，即采用基于块的运动估计和运动补偿技术。为了提高运动估计的准 确性，还采用了半象素精度的运动估计。同时，所采用的块的大小是可变的。如 图2 2 所示，为可变块的示意图。当所有的块完成运动估计后，即可得到由前一 帧的不同图像块经过一定平移后所拼接成的预测帧。为了减小分块运动补偿在块 边缘处的不连续性对信号能量压缩的不利影响，在预测帧的块边缘处进行了环路 i o 中国科学技术大学硕十毕业论文 滤波。随后，将当前帧与预测帧相减即可得到一个残差帧，为接下来小波零树编 码做好准备。 ：目t s 田：田 1 6 可变块示意图 该平台采用d a u b e c h i e s ( 9 , 7 ) 滤波器的提升算法进行二维离散小波变换。提升 算法是一种不同于传统的卷积运算的快速小波变换方法，具有简单、快速、节省 内存开销和易于硬件实现等优点。然后对小波变换后的系数，进行零树编码。零 树是由不重要的小波系数组成的一种树形数据结构。它利用了位于不同尺度的子 带中的小波系数间的自相似特性，以实现对小波系数的有效压缩。这里采用的零 树编码算法主要基于零树熵编码( z e r o t r e ee n t r o p yc o d i n g ，z t e ) 算法的思想1 4 “。该算法与经典的嵌入式零树小波( e m b e d d e dz e r o t r e ew a v e l e t ，e z w ) 算法f 6 1 的不 同之处主要在于以均匀量化取代了e z w 算法的连续逼近量化；以一次扫描代替 了e z w 算法的多次扫描：并且对零树符号进行了重新定义。我们采用了z t e 算 法的思想，但在具体的实现细节上并不同于1 5 1 中的算法。 经过零树编码后将产生一系列零树符号以及量化系数，我们采用具有自适应 模型的算术编码对它们进行编码。对于运动估计中产生的运动矢量，则用 g o l o m b r i c e 码编码。 2 1 小波变换 小波变换是在傅立叶分析的基础上发展起来的，作为一种新的数学工具，近 十几年来，在图像处理、语音分析、模式识别、机器人视觉、量子力学等众多领 域得到广泛的应用。本节将从图像、视频处理的角度简单介绍小波理论，重点介 绍一种新的双正交小波构造方法提升算法( l i r i n gs c h e m e ) 。与传统算法相 一田m 2 2 一日。 2 2 托口4 4 中围科学技术人学硕士毕业论文 比，提升算法更加简便，运算速度更快，易于硬件实现。 2 1 1 小波变换基本概念 连续小波 函数，( x ) 以小波y ( x ) 为基的连续小波变换定义为函数( x ) 和。( x ) 的内 积， ( 咖) 2 ( 加咖) 2e m ) 旁( 等) 出 ( 2 _ t ) 其中，e ( x ) 称为母小波( m o t h e rw a v e l e t ) ，是一个定义在有限区间的函数。小波 基函数组( 心。( 砷) 由母小波y ( x ) 通过缩放和平移来生成， ( 加l 矿矿( 等) 陋：) a 为缩放因子，反映特定基函数的宽度( 或者叫尺度) ：b 为平移参数，指定沿x 轴平移的位置。缩放因子小，表示小波函数比较窄，度量信号的细节，即高频信 息：反之，缩放因子大，表示小波函数比较宽，度量信号的低频信息。 离散小波 连续小波变换中，缩放因子口和平移参数b 都是连续的， 人的。为了解决计算量的问题，我们将a 、b 离散化即令 a = a d ，b = i z o a 通常取a o = 2 ，f 0 = 1 ，则一维小波基函数序列定义为， 显然其计算量是惊 ( 2 3 ) 。( x ) = 2 一“2 妒( 2 一。x f )( 2 - 4 ) 采用这样的缩放因子和平移参数的小波变换又叫做双尺度小波变换( d y a d i c w a v e l e tt r a n s f o r m ) ，它是离散小波变换的一种形式。 1 9 8 9 年，m a l l a t 提出了多分辨率分析理论和一种离散小波变换和重构的快速 算法m a l l a t 算法，它使用滤波器实现离散小波变换。对一维信号采用m a l l a t 算法执行2 级小波分解的过程如图2 _ 3 所示。 中国科学技术大学硕士毕业论文 ，c n ) = w f ( ，川 阻( * ) w p p 。一2 ， ) 图2 3 2 级_ 维离散小波分解过程及其频率划分特性 其中，九( ，z ) 被称为小波滤波器，伽) 为尺度滤波器。从频率划分特性图上可 以看出，钆( 甩) 和( 刀) 分别相当于高通滤波器和低通滤波器，分别提取信号的 高频和低频信息。 、 厂匝丑 丑一 亟越 t 器k ， j 侧c o 吣l u l n m l l s l 匝丑 互卜i1 ，j - 1 _ j 1 趣妻 u 亘 伍h 队“ 。“亚 囤一 r o w s 图2 4二维离散小波分解过程及分解结果 w 2 ( 肌n ) 哪：c 。一) r 敛，n ) 对于图像这类二维信号，二维m a l l a t 算法采用了可分离的滤波器设计，实质 上相当于对二维信号分别在行和列上做一维小波变换，如图2 4 所示。可以看到， 经过l 级二维离散小波变换后原图像被分解为四个子图像睨( ，m ，, ) 又被 中国科学技术大学硕士毕业论文 称为l b 子带( l o w - l o wb a n d ) ，是水平和垂直方向低通滤波的结果，同时也是原 图像在低一级分辨率下的近似； 掣( ，z ，聍) 又被称为h l j 子带( h i g h l o w b a n d ) ， 是水平方向高通、垂直方向低通滤波的结果，反映原图像在水平方向的细节信息； f 形( ，肌，胛) 又被称为l h j 子带( l o w h i g hb a n d ) ，是水平方向低通、垂直方向高 通滤波的结果，反映原图像在垂直方向的细节信息： 咿( ，肌，门) 又被称为h h j 子带( h i g h h i g hb a n d ) ，是在水平和垂直方向均进行高通滤波的结果，反映原图 像在对角方向的细节信息。 由于小波变换的减抽样性质，经过一级小波分解后，低频系数和高频系数个 数之和等于原图像灰度系数的个数，即总数据量没有发生变化，但能量分布发生 了改变，在一定程度上去除了原图像数据的空间冗余性，因此可以用较少的比特 数来表示它( 低频信息尽量保毅，细节信息大大减少) ，从而实现图像数据压缩 的目的。 2 1 2 小波变换提升算法 m a u a t 算法虽然是一种较为快速的小波变换方法，但为了实现滤波操作，一 般需要进行卷积操作，运算量仍然很大。1 9 9 5 年，w i ms w e l d e n s 提出了一种新 的双正交小波构造方法提升算 法( l i f l i n gs c h e m e ) t 7 1 。该方法保留了小波分析 的特性( 如时间频率局部化和快速计算) ，放弃了用傅立叶分析来构造小波( 传 统方法通过尺度缩放和平移母小波来构造小波基函数，而经过傅立叶变换后，平 移和缩放成为代数操作) ，完全在空域完成对双正交小波滤波器的构造，因而又 被称为第二代小波。d a u b e c h i e s 已经证明，任何离散小波变换或具有有限长滤波 器的双通道滤波变换都可以被分解成为一系列简单的提升步骤，所有能够用 m a l l a t 算法实现的小波变换，都可以用提升算法来实现【8 j 。 提升算法的主要优势在于： ( 1 ) 运算速度更快： ( 2 ) 能够实现小波变换的原位( i n p l a c e ) 计算； ( 3 ) 反变换方法易于确定： ( 4 ) 适用于傅立叶变换不适用的情况。 提升算法的基本思想： 提升算法主要由分割( s p l i t ) 、预测( p r e d i e t ) 、更新( u p d a t e ) - 三- 个基本步骤组成， 中圈科学技术大学硕士毕业论文 如图2 5 所示。 图2 5 提升算法的基本步骤 1 设原始数据序列为凡，由于数据之间有某种相关性，我们希望找到一种更为紧 凑的表达方式。分割步骤将凡分割成两个相关的予序列丑，和以；预测步骤则 利用丑。和y 一，之间的相关性，用量，来预测y _ 1 弗用，一、与其预测值之间的差值代 替丘；更新步骤用经过预测得到的丘。来更新矗，使丑，能够在某一度量标准( 如 均值) 下，保持与无相同的性质。 重复进行上述三个步骤的分解，经过门步，就可以用小波表示 量。，正，一。) 取代原数据序列凡， l ，丘，z - ) 是比五更紧凑的表达形式。 用公式表示为 乃，j = 一1 d o w n t o 一” 戌”= 一门r 。一： t j ：；：三翥主。， c ：s ， 2 1 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 p e g 2 0 0 0 标准即采用了d a u b e c h i e s ( 9 ，7 ) 滤波器对图像进行有损压缩。此p b ( 5 ，3 ) 9b 札 跏鹏 | | | j i | 一 十 咐乃乃 l 中国科学技术大学硕士毕业论文 滤波器也比较常用。在这里，我们选用d a u b e c h i e s ( 9 ，7 ) 滤波器进行小波变换。 表2 1d a u b e c h i e s ( 9 ，7 ) 滤波器系数 穗 ” g 。 o+ o 6 0 2 9 4 9 0 1 8 2 3 60 + 1 1 1 5 0 8 7 0 5 2 4 5 6 1+ o 2 6 6 8 6 4 l1 8 4 4 2l一0 5 9 1 2 7 1 7 6 31 1 4 2一o ，0 7 8 2 2 3 2 6 6 5 2 820 0 5 7 5 4 3 s 2 6 2 2 8 30 0 1 6 8 6 4 1 1 8 4 4 23+ o 0 9 1 2 7 1 7 6 3 1 1 4 4+ o 0 2 6 7 4 8 7 5 7 4 1 0 将( 9 ，7 ) 滤波器的z 变换写成如下所示的多项式表示形式 向( 三) = h o + 吃( z 2q _ z - 2 ) + 允( ：4 + z - 4 ) ) + z _ h i ( z 2 + 1 ) + 鬼( z 4 + ：) ) 。、。_ 。 也(r)ho(z2) 季( z ) = g o + 9 2 ( z 2 + z - 2 ) ) + z _ 1 g l ( z 2 + 1 ) 十( z 4 - - z - 2 ) ) ( 2 7 ) 。、。c 。 丘( ：。)蠡( ：2 ) 则有 将多项式矩阵 觅( z ) = h 。+ h 2 ( z + z - i ) + h 4 ( z 2 + z - 2 ) g o ( z ) = h i ( z + 1 ) + h 3 ( z 2 + z - i ) 季。( z ) = g o + 9 2 ( z + z - i ) ，(2-8) 季。( z ) = g l ( z + 1 ) + 9 3 ( z 2 + z - i ) 彪，= 矧 用欧几里得算法进行分解( 设= 疋( z ) ，b o = 觅( z ) ) ，可以得到 p ( z ，= ( 吾。足) ( 硼l + ：，： ( p ( 船l + ：，巩州1 ：2 式中 t 6 ( 2 9 ) f 2 一l o ) 心 中国科学技术大学硕上毕业论文 口一1 5 8 6 1 3 4 3 4 2 - 0 0 5 2 9 8 0 1 18 ，o 8 8 2 9 1 1 0 7 5 占z0 4 4 3 5 0 6 8 5 2k * 1 2 3 0 1 7 4 1 0 5 图2 6 为( 9 ，7 ) 滤波器提升法实现结构： 图2 ：6d a u b e c h i e s ( 9 ，7 ) 滤波器提升法实现结构图 x ( n ) 为原始一维数据序列，y ( n ) 为小波变换结果，贝1 1 ( 9 ，7 ) d 、波变换提升 法实现的数学表达式为式f 2 3 2 ) 。 f y ( 2 n + 1 ) 一k ( 2 n + 1 ) + ( 口 。j o ( 2 疗) 4 - k ( 2 订+ 2 ) ) s t e p l 】 ly ( 2 n ) _ 爿0 ( 2 以) + ( f l x y ( 2 n 一1 ) + y ( 2 n + 1 ) 】) 【s t e p 2 】 l】z ( 2 n + 1 ) 卜y ( 2 n + 1 ) + ( y x r ( 2 n ) + y ( 2 n + 2 ) 1 ) s t e p 3 】 1y ( 2 门) 卜y ( 2 肝) + ( j y ( 2 7 - - 1 ) + y ( 2 胛+ 1 ) 】) s t e p 4 ( 2 - 1 1 ) ly ( 2 n + 1 ) 卜一( 1 k ) y ( 2 n + 1 )【s t e p 5 1 【y ( 2 n ) 卜k y ( 2 n ) s t e p 6 】 其中，也，( 以) 为x ( 玎) 经过边界延拓后的数据序列。该数学表达式可以形象地用 示图2 7 表示 1 9 1 。 弋7yf 孓7 。，7 7 ，77 。y， 飞穸弋77 。7 7 ，、“： y - 1 n p u ts e q l i c r l c c lr i t c r m e di a t c 8 “g 。8 r 一l i g h 一| 1 s 1 矿 ：j ；：o 、一。“8 pj = 口，“l = ，p 2 = y ，“2 = 万，k o = k ，k 1 = 一( 1 k ) 图2 7 d a u b e c h i e s ( 9 ，7 ) 滤波器提升法实现示意图 1 7 中国科学技术大学硕士毕业论文 2 2 小波零树编码 小波变换对非平稳信号的有效分析特性，使得小波变换在图像编码领域得到 了广泛的应用。自2 0 世纪9 0 年代初以来，出现了各种新颖的小波图像编码方法。 1 9 9 2 年，l e w i s ，a s 和k n o w l e s ，g 首先介绍了一种树形数据结构来表示 小波变换的系数。1 9 9 3 年，s h a p i r o ，j m 提出了嵌入式编码( e m b e d d e dc o d i n g ) 的概念，并开发出嵌入式零树小波( e m b e d d e dz e r o t r e ew a v e l e t ，e z w ) 算法n e z w 算法的开拓，给后来者带来很大的启发。a m i rs a i d 和w i l l i a mp e a r l m a n 在 19 9 6 年发表了层树分集算法( 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 ，s p i h t ) 【l 。 19 9 9 年，d a v i dt a u b m a n 发表了最佳截断嵌入码块编码( e m b e d d e db l o c kc o d i n g w i t h o p t i m i z e dt r u n c a t i o n ，e b c o t ) 1 1 j ，j p e g 2 0 0 0 的基本编码方法就是在 e b c o t 算法的基础上开发的。此外，d a v i ds a m o f f 研究中心的研究人员在1 9 9 6 年提出了零树熵编码( z e r o t r e ee n t r o p y , z t e ) 算法 4 , 5 1 ，在此基础上开发的多级零树 熵编 i 目j ( m u l t i s c a l ez e r o t r e ew a v e l e te n t r o p y , m z t e ) 算法，被m p e g 4 静态纹理编 码采用【t 2 , 1 3 。 2 2 1 零树 通过静面的分析我们知道，离散小波变换是一种多分辨率的分解方法，它将 图像分解为包含不同频率信息的子带。各级子带中的系数是相关的具有一定的 分布特性： ( 1 ) 小波系数的能量随着尺度的递减而递减( 这里，低尺度具有高分辨率) 。 即平均院来，位于高频子带中的小波系数比低频子带中的小波系数小。 ( 2 ) 大的小波系数比小的小波系数更为重要，高频子带中的小系数可以被 抛弃。 利用以上特性，我们可以在小波系数间建立一种树形依赖关系，如图2 8 所 示。除了频率最高的一级子带( h l i 、l h i 以及h h l 子带) ，每一个小波系数都 可以和相似方向上低一级尺度上的一组小波系数建立关联。其中，高一级尺度上 的小波系数被称为双亲( p a r e n t ) ，低一级尺度上相同空间位置、相似方向上的小 波系数被称为孩予( c h i l d r e n ) 。根据小波分解尺度变化的规律，一般认为，一个双 中国科学技术大学硕士毕业论文 亲和四个孩子对应。最低频子带( l l 3 ) 稍有不同，位于最低频予带中的系数与三 个孩子对应，它们分别来自同一尺度上，相同空间位置、不同方向的三个子带 ( h l 3 、l h 3 以及h h 3 子带) 。 澍肌：一 h 1 一l 1 j n m 2 卜擘2 li 甬 h l 。 一 l南 图2 , 83 级小波树构造方法 在给出零树概念之前，我们先定义不重要系数：如果一个小波系数的绝对值 小于某一给定的阈值t ，我们就认为，当前，该小波系数是不重要的。所谓零树， 就是指对当前闽值t ，所有子孙系数都是不重要系数的树。小波系数的分靠特性 体现了这样一条规律，即如果一个小波系数相对于当前闽值t 是不重要的，那 么相似方向上、相同空间位置、更低尺度上的小波系数也很可能是不重要的。娃 然，零树结构与d c t 变换后，采用z 字形扫描( z i g z a gs c a n ) 和块结束符的思想 是类似的。 图2 9 零树编码示意图 定义零树的重要意义在于，如果一棵树是零树，那么这棵树就可以用一个预 中国科学技术大学砸上毕业论文 先定义的符号来代替，从而提高压缩比。如图2 9 所示。图2 9 ( a ) 中，s 表示重 要( s i g n i f i c a n t ) 系数，i 表示不重要( i n s i g n i f i c a n t ) 系数，采用如图2 9 ( b ) 所示的迂回 扫描( m o r t o ns c a n ) 方式，直接编码的码流为s s i ss i i si i i is i s i 。定义零树后，编 码码流为s s z ss i i ss i s i ，其中“z ”表示零树根，表示其子孙系数都是不重要 系数，不用再进行编码。显然，与直接编码相比，采用零树后，缩短了码流，实 现了压缩。 2 2 2z t e 算法描述 1 d c 子带编码 小波变换后的最低频予带( 如3 级小波变换中的l l 3 子带) ，又称为d c 子 带。它是原图像在此分辨率下的近似，包含了图像的低频信息，是最为重要的予 带。同时，d c 子带的小波系数具有与其它高频子带不同的分布特性。类似于采 用d c t 变换的图像编码中对d c 直流系数的编码，我们采用差分脉冲编码方式， 对d c 子带进行单独编码，而不将该子带纳入零树结构中。 对d c 予带采用如图2 1 0 所示的光栅( r a s t e r ) 顺序进行扫描。 ， ， b c ax 图2 1 0 光栅扫描图2 1 1d c 子带的d p c m 编码 如图2 1 l 所示，对每一个量化后的系数x ，利用相邻的三个系数a 、b 、c 进行预测，具体方式为 矿( 1a - b i ) ( ib c 1 ) 谛= c e l s e 谛= 彳 x = x 一如 如果a 、b 或c 不在图像范围内，则设为零。 2 0 中国科学技术大学硕七毕业论文 2 a c 子带编码 除d c 子带外的高频予带，统称为a c 子带。对量化后的a c 子带系数，我 们利用零树结构进行编码。我们定义了四种零树符号： a ) z t r ( z e r o t r e er o o t ) ；如果当前系数及所有的子孙系数都是零，则当前系 数被标记为零树根，从而其所有的子孙系数都不再需要进行编码。 b ) v z t r ( v a l u e dz t 鼬：如果当前系数不为零，但是它的四个直接子孙都是 零树根，则当前系数被标记为v z t r 。除了需要对当前系数进行编码外， 其所有的子孙系数都不再需要进行编码。 c ) v a l ( v a l u e ) ：如果当前系数不为零，且其子孙中存在非零系数，则被标 记为、a l 。当前系数需要进行编码，其子孙系数也需要继续进行扫描和 编码。 d ) i z ( i s o l a t e dz e r o ) ：如果当前系数为零，但其子孙中存在非零系数，则被 标记为i z 。当前系数不需要进行编码，但其子孙系数需要继续进行扫描 和编码。 频率最高的一级子带( h l l 、l h l 以及h h i 子带) 的系数又被称为叶子系 数。对于叶子系数，不需要输出零树符号，只需要对还没有被编码的叶子系数( 即 其双亲或祖先不为z t r 和v z t r ) 进行编码。 这罩需要说明的是，零树符号的定义方式并不唯一。比如，也可以仅定义两 种零树符号【l 。对当前系数，不需要判断它的值是否为零，直接对其值进行编 码，然后输出其零树符号。如果当前系数所有的子孙都为零，则输出一个0 比特表示其子孙不再需要进行编码。如果其子孙中存在非零系数，则输出一个“1 ” 比特，表示其子孙需要继续进行扫描和编码。表面看来，这种定义方式似乎更加 简单明了，由于只有两种零树符号，用一个比特表示即可，而按照之前定义四种 零树符号的方式，则需要两个比特。但实际的情况是，选用哪种定义方式更好， 与对系数值进行熵编码的方法有关。这个问题将在对熵编码的讨论中进一步进行 说明。由于我们采用了自适应的算术编码以比特面的方式对系数值进行编码，采 用四种零树符号优于两种零树符号。 在实现中，先以深度优先访问的顺序遍历所有的小波树( 对于如图2 1 9 所示 的3 级小波分解，树根位于h l 3 、l h 3 以及h h 3 子带) ，确定每个量化系数的零 树符号。当前系数需根据其四个子孙的零树符号确定自身的零树符号，即子孙的 2 l 中国科学技术大学硕士毕业论文 零树符号先于当前系数确定。这实际上是一个递归过程。 471 6 l72 8冀 mbt s悖蛳3 1 1 ，：。： 69 04 1j ： i ：1 54 24 35 45 5 2 01 i雒2 42 5 孙 ? 22 33 4邵2 62 7站坤 “4 5竭5 74 84 90 06 i s l位6 ,