（计算机应用技术专业论文）基于小波变换的图像可分级编码研究.pdf

基于小波变换的图像可分级编码研究 摘要 图像渐进传输、多质晕服务以及图像数据库浏览等多分辨率环境下的多媒体应用 导致了图像可分级编码思想的产生，并成为目前图像编码的一个热点问题。为了提高 图像的解码质量，而且还能够适应网络异构特性的需求，本文提出了基于小波变换的 图像可分级编码研究来解决上述问题。 文章首先对图像编码技术进行了概述；其次，对可分级编码技术的研究进展做了 较详细的总结，从d c t 变换、小波变换和c o n t o u r l e t 变换三个方面来分析和对比各个 方法的优缺点；接着给出了小波变换的理论基础，包括多尺度分析的概念，m a l l a t 算 法、离散小波变换的原理和具体实现过程，以及小波分解的空间一频率局部化特征； 这也是本文提出的一系列解决方案所必需的理论依据；最后，在多分辨率分析的基础 上，本文提出了三种嵌入式图像可分级编码算法：( 1 ) 在零树结构的基础上，提出了一 种基于最小二乘拟合的小波图像可分级编码算法，该算法经过小波变换之后，利用最 小二乘拟合法，线性的对隔层子带内的小波系数进行预测，取得了较好的解码效果； ( 2 ) 在对图像小波分解后各个子带中的重要系数的“聚类”特性进行分析的基础上，提 出利用“簇间向量”来确定相邻两个重要系数簇种子之间的相对坐标信息，在此基础 上提出一种基于重要系数簇和簇间向量的低码率图像数率可分级编码算法，该算法结 合数学形态学的膨胀操作，利用重要系数簇和簇间向量来实现重要系数位置信息的同 步，实验结果表明，在低码率下取得了较好的编码效果，其编码性能优于目前流行的 e z w 、s p i h t 、m r w d 、e b c o t 和g w 等嵌入式图像编码方法；( 3 ) 提出了一种基于 k 阶零树问向量表示的图像数率可分级编码算法，该算法利用一种新的数据结构- k 阶零树，对小波变换后相同方向不同尺度的重要系数进行有效的表示，在低码率下取 得了较好的重构效果。 关键词：可分级编码；小波变换；向量；形态学膨胀：k 阶零树 基于小波变换的图像可分级编码研究 a b s t r a c t t h em u l t i m e d i aa p p l i c a t i o n si nam u l t i r e s o l u t i o ne n v i r o n m e n t ，s u c ha sp r o g r e s s i v e t r a n s m i s s i o no fi m a g e ，m u l t i q u a l i t ys e r v i c ea n di m a g ed a t a b a s eb r o w s i n g ，e t c ，r e q u i r er a t e s c a l a b l ei m a g ec o d i n ga l g o r i t h m s ，a n dn o wi tb e c o m e sah o t s p o ti ni m a g ec o d i n gd o m a i n i no r d e rt oi m p r o v et h ed e c o d i n gq u a l i t yo fi m a g e sa n df i tt h eh e t e r o g e n e o u sh i e r a r c h yo f n e t w o r k ，a na l g o r i t h mo fm u l t i - s c a l et r a n s f o r m b a s e ds c a l a b l ei m a g ec o d i n gi sp r o p o s e dt o s o l v et h e s ep r o b l e m sa b o v e f i r s t ，t h i sp a p e rs u m m a r i z e st h et e c h n i q u e so ft h ei m a g ec o d i n g ，t h e ng i v e sas u m m a r y o nt h er e s e a r c hp r o g r e s s0 1 1s c a l a b l ei m a g ec o d i n gd e t a i l e d l y , a n a l y z e sa n dc o m p a r e st h e a d v a n t a g e sa n dd i s a d v a n t a g e so fd c t , w a v e l e ta n dc o n t o u r l e tt r a n s f o r mr e s p e c t i v e l y s e c o n d ，t h eb a s i so ft h e o r yf o rw a v e l e tt r a n s f o r i l li si n t r o d u c e d w h i c hi n c l u d e st h ec o n c e p t o fm u l t i s c a l ea n a l y s i s ，t h ep r o c e d u r eo fm a l l a ta l g o r i t h ma n dt h ed w t , t h el o c a lf e a t u r eo f s p a c e f r e q u e n c y , a n dt h e ya r ea l s ot h en e c e s s a r yb a s eo ft h e o r yf o rs o l u t i o n si nt h i sp a p e r f i n a l l y , b a s e do nt h em u l t i s c a l ea n a l y s i s ，t h r e ee m b e d d e dq u a l i t ys c a l a b l ei m a g ec o d i n g a l g o r i t h m sa r ep r o p o s e d ( 1 ) b a s e do nt h ez e r o t r e es t r u c t u r e an e wp r e d i c t i v ec o d i n g a l g o r i t h mf o ri m a g ew a v e l e tc o d i n gb a s e do nt h el e a s ts q u a r ef i r i n gm e t h o di sp r o p o s e d w h i c h ，u s e st h el e a s ts q u a r ef i t t i n gm e t h o dt op r e d i c tt h ew a v e l e tc o e f f i c i e n t sf r o mt h eo d d s u b b a n d st oe v e ns u b b a n d sa n da c h i e v e sb e t t e rr e c o n s t r u c t e dq u a l i t y ( 2 ) o nt h eb a s i so f a n a l y z i n gt h ec l u s t e r i n gc h a r a c t e r i s t i co fs i g n i f i c a n tw a v e l e tc o e f f i c i e n t s ，w eu s eav e c t o rt o d e t e r m i n et h er e l a t i v ec o o r d i n a t eb e t w e e nt w os e e d so fa d j a c e n ts i g n i f i c a n tc o e f f i c i e n t c l u s t e r s b a s e do nt h es i g n i f i c a n tc o e f f i c i e n tc l u s t e r sa n dt h ev e c t o r sb e t w e e nt h e m ，al o w b i t r a t es c a l a b l ei m a g ec o d i n ga l g o r i t h mi sp r o p o s e d i tu s e ss i g n i f i c a n tc o e f f i c i e n tc l u s t e r s a n dv e c t o r sb e t w e e nt h e mt oe f f e c t i v e l yr e d u c et h eb i t r a t eo fe n c o d i n gt h ep o s i t i o n so f s i g n i f i c a n tc o e f f i c i e n t sc o m b i n e dw i t ht h em o r p h o l o g i c a ld i l a t i o no p e r a t o r e x p e r i m e n t a l r e s u l t ss h o wt h a tt h ep r o p o s e da l g o r i t h ma c h i e v eg o o ds u b j e c t i v eq u a l i t yi nl o wb i t r a t e ， a n di ss u p e r i o rt os t a t e o f - t h e - - a r te m b e d d e di m a g ec o d i n ga l g o r i t h m si nt e r m so fp s n ra n d c o m p u t a t i o n a lc o m p l e x i t y , s u c ha se z w , s p i h t , m r w d ，e b c o t ，a n dg w ( 3 ) a n a l g o r i t h mo fr a t es c a l a b l ei m a g ec o d i n gb a s e do nv e c t o r sb e t w e e nd e g r e e - kz e r o t r e e si s p r o p o s e d i tu s e san e wd a t as t r u c t u r e ，d e g r e e - kz e r o t r e e s ，t or e c o r dt h ei n f o r m a t i o no f r e l a t i v el o c a t i o n se f f e c t i v e l yb e t w e e nt h ei m p o r t a n tw a v e l e tc o e f f i c i e n t so ft h es a m e d i r e c t i o na n dt h ed i f f e r e n ts c a l e s i nl o wb i t r a t e ，t h ea l g o r i t h mc a na c h i e v eb e t t e rs u b j e c t i v e q u a l i t y k e yw o r d s ：s c a l a b l ec o d i n g ；w a v e l e tt r a n s f o r m ；v e c t o r ；m o r p h o l o g i c a ld i l a t i o n ；d e g r e e k z e r o t r e e 基于小波变换的图像可分级编码研究 学位论文独创性声明 本人承诺：所呈交的学位论文是本人在导师指导下所取得的研究成果。论文中 除特别加以标注和致谢的地方外，不包含他人和其他机构已经撰写或发表过的研究 成果，其他同志的研究成果对本人的启示和所提供的帮助，均已在论文中做了明确 的声明并表示谢意。 学位论文作者签名：型丕。 学位论文版权的使用授权书 本学位论文作者完全了解辽宁师范大学有关保留、使用学位论文的规定，及学 校有权保留并向国家有关部门或机构送交复印件或磁盘，允许论文被查阅和借阅。 本文授权辽宁师范大学，可以将学位论文的全部或部分内容编入有关数据库并进行 检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文，并且本人电子 文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后使用本授权书。 学位论文作者签名：型墨指导教师签 签名日期：9 罗年厂月矽日 4 2 基于小波变换的图像可分级编码研究 第l 章绪论 1 1 论文的选题背景及意义 随着多媒体技术的不断发展，越来越多的图像需要在互联网上传输，理想的情况是 占用尽可能小的带宽，并得到较好的重构质量，以满足人眼的视觉要求，这就需要图像 编码技术来解决这些问题。图像编码作为多媒体处理的核心技术之一，其基本思想是尽 可能的去除存在于原始图像当中的冗余信息，保留较少的、对人眼有意义的数据来表征 图像的绝大部分重要信息，这就是图像编码技术的目的。从信息论的角度讲，图像可以 当作是一个信息源，它的数据量由信息量和信息冗余量共同组成。图像可分为静态图像 和动态图像，围绕它们的信息冗余量有多种不同的形式，例如时间冗余、空间冗余、结 构冗余、知识冗余和视觉冗余等，编码( 也称做压缩) 的目的就是要减少甚至去除这些 冗余信息，特别是应用在网络传输方面。既然编码的目的是去除多余的信息量，那就不 免会存在一定程度上的失真，不过只要能够充分利用人眼视觉特性，舍弃那些对人眼不 敏感或者说不重要的图像信息，就可以实现高压缩比，同时解码后的图像主观质量仍然 很高。 还是要提到网络应用上，图像的渐进传输是一个很好的例子。由于用户要求不同、 终端能力不同、异构网络的不同支路所能提供的q o s 不同或网络传输条件的变化( 比如 噪声、拥塞等) 等原因，需要提供不同质量的图像信号，方法是用单个编码器产生分层 次的压缩码流，对不同层次的码流解码可以获得不同的图像质量，这种编码机制通常被 称为可分级编码【l 】。可分级编码分为静态图像可分级编码和视频可分级编码，本文重点 研究静态图像的可分级编码，该编码方法能够获得较高的编码效率，尤其是在低码率情 况下。 图像编码的目的简单的说就是在一定条件下，利用尽量少的比特流来表示图像信 息，以便更好的存储和传输。图像编码技术已经走过了几十年的研究历程，形成了许多 国际标准。例如运用于二值图像压缩的g 3 、g 4 和j b i g 标准，用于视频存储和传输的 m p e g 1 、m p e g 一2 、m p e g 4 和m p e g 7 标准等。随着人们对图像质量和读取速度的要 求越来越高，又出现了g i f 、j - p e g 、p n p 、j p e g 2 0 0 0 等各种图像压缩标准。 在2 0 世纪9 0 年代的j p e g 图像编码标准中，静态图像可分级编码的思想便有所体 现并得到迅速的发展。例如在m p e g 4 视频标准校验模型中，对静态图像纹理的编码便 提出了空间分辨率可分级、数率可分级以及二者的混合可分级的编码模式；此外在 j p e g 2 0 0 0 中，还提出了基于r o i ( r e g i o n so f i n t e r e s t ) 的可分级编码思想【2 ，3 】。 本文在应用可分级编码思想的基础上，运用小波变换 4 】的方法，即将静态图像看做 是一个二维信号，对其进行低通滤波和高通滤波，将某一分辨率下的信号分解成下一层 次上的若干低通近似信号和高通细节信号，然后在频率域下对小波系数进行几种有效的 编码方法，均取得了较好的压缩效果。 基于小波变换的图像可分级编码研究 1 2 图像编码技术概述 图像编码最开始起源于上世纪4 0 年代末的s h a n n o n 信息论。信息论的重要意义在 于他把信息进行量化，并且证明在不产生失真的前提下，通过合理有效的编码算法，对 于每一个信源符号分配不等长的码字，平均码长可以任意接近于信源的熵。图像压缩可 分为无损压缩，如：h u f f m a n 编码、算术编码、字典编码等和有损压缩，如：预测编码、 子带编码、变换编码等。在大多数情况下，人们允许图像有一定的失真，即可对图像进 行有损压缩编码。这种方法因为应用广泛，如数字电视( d v d 、h d t v 、v o d 等) 、计 算机、电子图书、指纹库等图像信息系统，多媒体教育、工业监控、多媒体演示和咨询 等用的都是有损压缩方法。 1 2 1 第一代编码技术 在图像压缩编码的发展历史中，主要包括统计编码、预测编码和变换编码三大经典 方法。对于无记忆的信源，可以利用像素值出现概率的不均等性，采用统计编码方法来 压缩码流，统计编码就是根据出现概率的分布特性而进行的压缩编码。常用的统计编码 有游程编码、h u f f m a n 编码和算术编码等。预测编码是一种简单、有效的编码方法，其 基本原理是利用线性预测技术去除像素间的相关性，对预测值与实际值之间的差值( 即 预测误差) 进行量化与编码，而不直接对原始数据进行量化与编码，从而提高编码效率。 变换编码是先对图像进行变换，使得变换域中数据间的相关性减小或者互不相关，从而 减小冗余度，再进行量化与编码，实现数据压缩。典型的变换编码主要有k l 变换编码、 离散余弦变换编码、傅立叶变换编码和w a l s h 变换编码。这些编码技术是以信息论和数 字信号处理技术为理论基础，旨在去除图像数据中的线性相关性的一类编码技术，其压 缩比不高，通常称为“第一代编码技术 。 1 2 2 第二代编码技术 “第二代编码技术”充分利用了人的视觉生理、心理和图像信源的各种特征来获 得更高压缩l t , 矛d 重构图像的质量，主要分为：分形编码【5 6 j 、基于模型或知识的编码方法 和神经网络编码方法。分形编码是将迭代函数系统应用到图像编码中，由于一幅图像中 局部与整体之间或者局部与局部之间存在相似性，利用一组表示仿射变换的迭代函数系 统( i f s ) 【7 】描述这些相似性，解码时是通过对这个迭代函数系统反复迭代而得到。基于 模型或知识的编码方法是编码时提取所建立模型的特征和状态参数，解码时根据这些参 数，通过模型及相关知识生成所建模型的信源。神经网络编码方法是模仿人的大脑来处 理问题的方法，通过各种人工神经元网络模型对数据进行非线性压缩。 第二代编码技术克服了第一代编码技术存在的压缩比小、图像解码质量不理想等缺 点，将主观解码质量大致相同的情况下，压缩比提高了几倍至几十倍或者是在相同的码 率下显著的增强了重构图像的主观质量。由于第二代编码技术计算复杂，方法实现起来 比较困难，所以它仍然处于深入研究的阶段，但由于其具有巨大的压缩潜能，使得人们 2 基于小波变换的图像可分级编码研究 还在致力于这些新方法的研究之中。 对于近期出现的如子带编码、金字塔编码和基于小波变换的编码等方法，虽然仍属 于变换编码，可归入经典编码方法，但它们又充分利用了人眼视觉特性，因此可以被看 作是“第一代”编码技术向“第二代”编码技术的过渡。 1 2 3 图像压缩性能的评价 在数字图像处理中，评价一种图像编码技术的性能主要有三个重要指标：压缩比、 图像的重构质量、编码和解码的速率。 压缩比是指压缩后图像信息的数据与压缩前图像信息的数据大小( 比特数) 之比。 压缩比= 器怨 ( 2 ) 图像的重构质量 图像的重构质量的评价方法分为两种：主观保真度和客观保真度。图像质量的主观 保真度，就是国际上通行的5 级评分的质量尺度和妨碍尺度，如表1 1 所示。它是由观 察者通过视觉和自己的经验，对被评价图像做出主观上的质量判断。一种常用的主观评 价方法是，把图像显示给一组观察者，把他们对该图像的评价结果加以平均来评价图像 的主观质量。 在静止图像和视频图像领域中常用的图像质量的客观保真度度量是均方误差和峰 值信噪比，其定义分别为： 以5 赤善荟 厂( “) 一厂( “) 】2 ( i - 1 ) 删= l o l g 啤= 1 0 l g t 丁浮竺o ( 1 - 2 ) 上m n 善善l 厂o ) _ 八l 力】2智等 其中s p p 为原始图像的峰一峰值，在一般的处理中图像被均匀量化为2 5 6 个电平，其峰 一峰值为2 5 5 。 ( 3 ) 压缩速度 表l l 两种尺度的图像5 级评分 3 基于十洼壹捷目像t 分级* 码研究 压缩和解压缩的速度也是衡量图像压缩性能的一个重要指标。在图像通信中。如果 压缩和解压的速度太慢，通信需要等待的时间太睦而达不到实时处理，就会影响整个通 信的效率尤其足对于视频传输。因此，好的压缩方法还要兼顾压缩处理的速度。 13 图像可分级编码技术研究 1 3 1 基本概念 在许多实际应用中，由于用户要求不同、终端能力不同、异构网络的不同支路所能 提供的q o s 不同或网络传输条件的变化( 比如噪声、拥塞等) 等原因，需要提供不同质 量的图像信号，解决此类问题的最好方法是用单个编码器产生分层次的压缩码流，对不 同层次的码流解码可以获得不同的图像质量，这种编码机制通常被称为可分级编码。一 个图像编码的比特流具有可分级性( s c a l a b i l i t y ) 是指利用该比特流的一部分( 或子集) 可以产生对该图像一个有用表示的能力，即解码器能够根据分辨率的情况对码流的一部 分进行解码。 图像的可分级编码通常包括以下情况：空间分辨率可分级编码、数率可分级( 或称 s n r 可分级) 编码、空间和数率混合可分级编码以及r o i 可分级编码等。 图像的数率可分级指对一个压缩的码流，用户可根据带宽或系统能力的具体情况从 码流的开始端来截取相应的一段码流进行解码。在对码流的截取过程中，如果可在一定 范尉内任意选择数率，则此时的数率可分级被称为连续数率可分级( 参见图1 1 ) 。空间 分辨率可分级则指以不同空间分辨率对图像进行解码( 参见图l 一2 ) 。 舀，- 西z ；譬 鬯兰茎兰三三三三三三兰刍竺 图1 1 图像和视频的数率可分级币意图图1 - 2 图像和视频的空问可分级示意图 除r 单独的数牢町分级和空间可分级编码方案外，二者还可以联合起来构成一种图 像和视频的数率可分级与空间可分级的混合编码方案，即码流在总体上实现基于分层的 空间可分级编码情况下，对每一层次的空间可分级图像码流，又可实现其数率可分级解 码( 参见图l - 3 ) 这在一定程度上提高了可分级的灵活性。 一叫哆“? 魄z i ；i i ! ：三= _ _ ：二二= 兰二二1 堕 r o i 可分级编码技术是指在图像编码码流中，允许图像的某一部分( 即感兴趣区域) 以更好的质晕被解码( 参见图l - 4 ) 。 一 基 十波变挺目像t 9 衄嫱码研究 嗣汪一弘嗣 图l - 4 以左上角矩形区域为“感兴趣区域”的r o i 罔像可分级解码图像 1 3 2 图像可分级编码研究进展 d c t 变换编码是酉变换的一种，其变换前后的信号熵和能量不变，在时域( 或空域) 中的r i 维信号x 其变换核可分离的正、逆d c t 变换分别定义如下： 砸) = 厝) 薹州“1 ( 2 n + r 1 ) k t r 卢虬一1 ( 1 - 3 )砸) 2 j 寺) 善州”s 1 万一卢o r 。1 砌) = 摇篓c ( 帕c “1 ( 2 n + 万1 ) 一k l r 加- 1 ( 1 4 ) 其中，c ：j1 7 2 ，o = ， 1 1 ，k = 1 , 2 ，一1 d c t 具有熵保持性质，即不丢失信息，从而通过传输变换系数来传送信息。d c t 变换域中的能量多集中于少数变换系数上，大多数系数的数值都很小。对于能量较小的 系数可以较粗糙量化，分配较小的比特，或者完全忽略。对于能量较大的系数，可分配 较多的比特，很适合采用熵编码来压缩数据。同时，d c t 能够去除像素间的冗余变换 系数间的相关性为零或较小。因此，在信息传输或存储系统中，可通过对空间域或时问 域中的相关数据施加d c t 变换，在变换域内对变换系数进行量化与编码，便可实现数 据压缩，从而提高信息传输或存储系统的有效性。综合d c t 编码特性及相关性等方面 因素，它仅狄于理想的k l 变换，所以d c t 在众多变换( d f t 、斜变换、h a a r 变换、 k l t 和沃尔什变换等) 中脱颖而出。 由于小波变换在非平稳图像信号分析方面的灵活性和适应人眼视觉特性的能力，已 经成为图像视频编码的有力工具。小波分析以时一频局部化提供了对信号的个多分辨 率表示，这对于编码是十分有用的性质。而小波变换所提供的多分辨率分解结构使它本 身更适合于可分级的编码。 小波变换是全局变换，在时域和频域同时具有良好的局部化性能，并且易于考虑人 类视觉特性，从而成为图像压缩编码的主要技术之一，并成功的应用与j p e g - 2 0 0 0 。与 经典的图像编码方法相比，小波变换编码至少具有这些优点：( 1 ) b 波变换本质上是全局 变换，重构图像中可以免除采用分块正交变换编码所固有的“方块效应”。( 2 ) b 波变换 采用塔式分解的数据结构，与人眼由粗到精，由全貌到细节的观察习惯相一致，这是 d w t 与人类视觉系统的空间分解特性结合起来以改善图像压缩性能的有利条件。小渡 变换比经典的变换更适合于人的视觉特性，通过合理的量化编码产生的人为噪声比同样 5 基于小波变换的图像可分级编码研究 比特率j p e g 方法产生的影响要小得多。( 3 ) 小波变换是图像的时一频表示，具有时间一 频域定位能力，并初步实现图像中评为成分与非平稳成分的分离，可以对其进行高效编 码。因此，小波变换用于图像压缩，除了具有时一频局部化分析方法处理非平稳信号的 固有长处外，还体现在它具有适于与人类视觉系统相结合的潜力上。 2 0 0 2 年，m i n hn d o 等人提出了c o n t o u r l e t 8 , 9 】变换，作为一种新的逼近工具，它能 够对直线奇异的多变量函数具有很好的逼近性能，具有最优非线性逼近误差衰减阶，真 正的对二维图像进行表示。可以这样讲，c o n t o u r l e t 变换是图像最稀疏的表示方法，用 它来进行图像的压缩应该能够达到很好的效果。 1 4 本文的工作 目前已经有很多基于小波变换的图像编码方法，本文将在后续的章节当中对基于小 波变换的图像编码方法结合可分级的思想来深入研究具体的实现方法，例如：基于重要 系数簇的低码率图像数率可分级编码算法。这些方法基本上都是通过小波变换下的低频 和高频系数之间的逻辑关系，运用一些特殊的数据结构来有规律的表示它们之间的相对 位置，这样会节省大量的比特流而达到压缩的目的，同时能够得到较高的解码质量。 本论文的章节安排如下： 第l 章首先给出了论文的选题背景和意义，明确了本文应该从哪些方面对图像编码 技术进行研究和改进；接着介绍了第一代和第二代图像编码技术的概况以及图像压缩性 能的评价标准；然后对图像可分级编码技术进行了简要的论述和比较分析： 第2 章介绍了小波变换的理论基础，包括多尺度分析的概念和经典的m a l l a t 算法以 及二维离散小波变换的原理和具体实现过程，最后介绍了小波分解的空间一频率局部化 特征； 第3 章提出了一种基于最小二乘拟合的零树小波图像可分级编码算法，简单的将多 尺度变换和可分级编码结合在一起； 第4 章提出了一种基于重要系数簇的低码率图像数率可分级编码算法，该方法利用 小波变换后频率域下重要小波系数之间的聚簇特性，其中需要运用数学形态学的膨胀操 作使这些重要的系数形成多个聚簇，然后通过向量将这些重要系数簇连接在一起，按照 某一特定的顺序记录这些重要系数的位置信息，从而节省了比特流的开销，将更多的码 流分配给量化系数上，实现高效的压缩编码； 第5 章提出了一种基于k 阶零树间向量表示的图像数率可分级编码算法，它的核心 思想是引入k 阶零树这一特殊的数据结构来存储同一方向不同尺度之间的重要小波系 数，同时每个k 阶零树之间仍需要向量来连接，形成零树链，有利于编码重要系数的位 置信息，在一定程度上提高了压缩比； 第6 章是总结与展望。 本文的主要研究工作集中在文章的第2 、3 和4 章，提出了多种基于小波变换的图 6 基于小波变换的图像可分级编码研究 像编码算法，如最小二乘拟合模型、重要系数簇模型以及k 阶零树模型，均结合了可分 级的思想。实验结果表明，本文提出的一系列图像编码算法与经典的算法相比，可以得 到更好的主观图像质量。 7 基于小波变换的图像可分级编码研究 第2 章小波变换理论基础 小波变换是8 0 年代后期发展起来的应用数学分支，它被认为是半个世纪以来泛函分 析、调和分析、数值分析等发展的最完美的结晶，在诸多工程应用领域中都有广泛的应 用，被认为是近年来在工具及方法上的重大突破。本文将小波变换应用到图像编码技术 当中，借助于小波变换，可以把图像信号分解成许多具有不同空间分辨率、频率特性和 方向特征的子带信号，实现低频长时特征和高频短时特征的同时处理，有效地克服了 f o u r i e r 分析在处理复杂图像时所存在的局限性，使得图像信号的分解更适合于人的视觉 特性和特征数据压缩的要求。其中，所涉及到的小波相关概念将做较详细的介绍。 2 1 多尺度分析 多分辨率分析，也称做多尺度分析，这一概念最初是由m a l l a t 提出的，它是从空间 域的角度来论述小波的多分辨率特性，并且将先前的所有正交小波基统一到了一起，总 结出了正交小波的构造方法以及快速的塔形算法，即m a l l a t 算法【i 们。 首先在r ( 尺) 内定义一系列的闭合嵌套子空间，且cl 2 ( r ) ，j z ，引入一个 尺度函数妒( 石) ，它与小波基函数v ( x ) 一一对应，其中： 丘2ce lc v ockc 且n 乃= o ，u 巧= l 2 ( r ) ，各个子空间之间的这种包含关系如图2 1 所示。对于每个 j e zj , e z z ，均有函数f ( x ) 一f ( 2 x ) _ + 1 对于尺度函数伊( x ) v o ，可以由妒( x ) 经过伸 缩和平移得到以下公式： 妒m ( x ) = 2 - j 2 1 p ( 2 吖x k ) ( 2 一1 ) 这里，纺，。( x ) 是巧的正交基。定义是v j 在巧一。中的正交补空间，即_ 一。= 巧+ 形， 形上，此时q j , k ( x ) = 2 - j 2 y ( 2 7 x - k ) 是的正交基。这样，可以将任何一个信号 f ( x ) v o 分解成两个子空间k 和彬上的正交投影，以次类推，将f ( x ) k 分解成和 的正交投影等等。反复的分解会得到一个树型结构的小波变换算法。其中，厂( x ) 在上 的正交投影对应的是近似信号，巧称为尺度空间或近似空间，f ( x ) 在形上的正交投影 对应的是细节信号，形i 称为小波空间或细节空间。 图2 1 尺度空间相互包含关系 8 基于小波变换的图像可分级编码研究 2 2m a l l a t 算法 对于上一节讨论的缈( x ) 和y ( x ) ，可以建立双尺度方程： 缈( x ) = 2 1 2 h ( n ) 缈( 2 x - n ) 吣) = 2 1 2 佗圭g 昨) q 乏 则由此能够推导出： a j , k ( 厂) = h ( 2 k - n ) a j _ l , ( 厂) “舻ng ( 2 k - - n ) a j _ l , n ( 厂) ( 2 - 3 ) 其中，h ( n ) 称为低通滤波器，g ( n ) 称为高通滤波器，且有： j i l ( 刀) = iq g ( x 切( 2 x 一，z ) d x 。( 2 - 4 ) 、一 。， g ( n ) = ly ( x ) 妒( 2 x n ) d x 存在的频域关系为： c p ( 2 c o ) = h ( 缈) 缈( 缈) ( 2 - 5 ) y ( 2 c o ) = g ( c o ) f a ( c o ) 这样看来，可以将信号通过滤波器进行滤波后，把某一分辨率对应的信号分解为下 一层次分辨率对应的一个低通信号和一个高通信号( 即近似信号和细节信号) ，同时还 可以将低通信号继续分解，这就是m a l l a t 算法，具体过程如图2 2 所示。 a j 一1 ，后 q j k c ，七 图2 2 一维信号小波分解 相应的重构公式为： a j - l , n ( 厂) = h ( 2 n - k ) a j , k ( ) + g ( 2 n - k ) c j , k ( 厂) ( 2 6 ) 2 3 二维离散小波变换 上一节中我们以一维信号小波变换为例讲解了多分辨率分析的原理和m a l l a t 算法 的实现过程，但是图像是二维信号，因此需要把小波变换由一维推广到二维。首先，我 们用f ( x 。，x 2 ) 表示一个二维的信号，五和屯分别表示横纵坐标，y ( 五，叠) 表示二维的基 本小波，妒( 五，x 2 ) 表示对应的尺度函数，如果尺度函数是可分离的，即 c p ( x i ，而) = 缈( 五) 伊( 恐) ( 2 7 ) 设( ) 是和缈( ) 对应的一维小波函数，则二维小波可以表示为以下三个可分离的 9 基f 十波换的图像t 分级蝙码研完 正交小波基雨数： ( 葺，t ) = 妒0 1 ) y ( 2 ) 矿( ，j 2 ) = 矿( ) 妒( t ) ( 2 8 ) p ( ，乇) = 伊( 玉) 妒( 也) 这样对二维信号的分解可以分成两个步骤进行，即先沿方向分别用妒( ) 和 y ( 五) 作分析，将，“，x 2 ) 分解成平滑和细节两部分，然后对这两个部分再做沿屯方向 用妒( 也) 和y ( 乇) 作同样的分析。 对于图像而言，首先对整个图像做一次水平方向和一次垂赢方向的小波分解，得到 一个低频子带工和三个高频子带删、栊，和h h 。其中，l h 表示水平高通垂直低通 予带，i l l 表示水平低通垂直高通予带，h h 表示水平高通垂直高通子带。此时，图像 的分辨率缩减为原始的1 2 ，频率的范围也是各补相同。第二次小波变换只对上子带进 行操作，将其分解为血、珥、崩；和删且分辨率为原始的1 ，4 ，频率范围也进一 步减半，以此类推，具体如图2 - 3 所示：图2 - 4 是l e n a ( 8 b p p , 5 1 2 5 1 2 ) 原图及进行小波 分解3 层后的分解图。本文提出的很多算法所使用的小波变换，就是基丁二维离散小波 变换所做的一些工作，具体内容将在后续章节中进行介绍。 a 原始图像 日一h l 广_ l hh h 1j一 b 一级小波分解 围2 0 图像的小波分解 臣l i - i l 2 崩：_ 【。h 1l “h lc i i j _ 一 c 二级小渡分解 曩蒸荔i 磊器 _ 1 囊攀爹 麟 ( a ) 原g a l _ e n a ( 5 1 2 5 1 2 ) ( b ) 对a 分解3 层后的图像 图2 - 4l e n a 原始阿像及其3 级小波变换后的图像 24 小波分解的空间一频率局部化特征 小波变换具有许多良好的空间一频率局部化特性，比如，对图像进行二进小波变换 1 0 ，u，、 基于小波变换的图像可分级编码研究 时，以对数形式划分频带，这与人类视觉系统的多通道模型一致；小波分解后，除了有 反映近似信息的低频子带，还有反映沿着水平、竖直和对角线方向信息的高频子带，这 一性质与人类视觉系统的空间方向分解特性一致，等等。同时，图像的小波分解系数还 具有较好的统计特性，这些特性主要表现在以下三个方面： ( 1 ) 频率压缩特性：从频率分解上看，原始图像的能量大部分聚集在低频子带； ( 2 ) 空间压缩特性：从系数在空间的分布看，原始图像的能量大部分集中在图像的边 缘、轮廓等对应的位置； ( 3 ) 系数分布相似性：同一方向上各级高频子带系数幅值分布大体一致。 以上这些特性奠定了各种基于小波图像编码算法的理论基础，同时为开发出高效的 图像编码算法提供了可能。早期的基于小波的图像编码算法主要是利用了小波分解的频 率压缩特性。近年来，人们除了利用频率压缩特性外，还利用了另两个特性，提出了高 效的图像编码算法。 2 5 小结 由于在非平稳图像信号分析方面的灵活性和适应人眼视觉特性的能力，小波变换已 经成为图像视频编码的有力工具。小波分析以时一频局部化提供了对信号的一个多分辨 率表示，这对于编码是十分有用的性质。真实世界的图像视频实际上是非平稳的信号， 小波变换把非平稳信号分解成一系列的具有不同分辨率的子带，每个子带中的分量变得 相对比较平稳，编码多个平稳的分量比编码整个非平稳信号的效率更高，因此易于编码。 同时，小波变换所提供的多分辨率分解结构使它本身更适合于可分级的编码，本文的后 续章节就是以小波变换为基本工具，提出了一系列图像编码算法。 基于小波变换的图像可分级编码研究 第3 章基于最小二乘拟合的零树小波图像可分级编码算法 3 1 引言 图像在互联网上传输，理想情况是占用尽可能小的带宽，并得到较好的重构质量， 这就需要一种压缩效果良好的编码方法。本章提出了一种基于零树结构并结合最小二乘 拟合的思想，对静态图像进行基于尺度间的子带预测编码，实验结果表明，解码后的图 像效果基本上达到人眼的视觉要求。 3 2 提升方案小波变换 对图像做小波变换处理是利用提升方案小波变换【1 1 1 的方法，与传统的小波变换相 比，提升方案小波变换应用范围更广，计算速度更快且易于实现。其变换过程共分为三 个步骤：分裂、预测和更新。假设原始信号为c j ，小波分解后的结果分为近似信号c j + i 和 细节信号d j + 1 ，则分解具体过程如下： 第一步：分裂。按照下标的奇偶性将信号分成两个集合，每个集合长度为原始信号 长度的一半，这一步被称为“懒惰小波变换 ( 1 a z yw a v e l e tt r a n s f o r m ) 。 第二步：预测。根据信号的相关性，用偶数样本点来预测奇数样本点，d j + l 表示奇 数点与预测点的偏差，这一步被称为“对偶提升( d u a ll i f t i n g ) 。 第三步：更新。用偏差d j + 1 修正偶数样本点，这一步被称为“主要提升( p r i m a l l i f t i n g ) 。 分解过程的表达式为： f ( e v e n j + 19o d d j + t ) = s p l i t ( c j ) 西+ t = d d 巩+ ，一p ( e v e m + t )( 3 - 1 ) lc j + l - - e v e n j + l + u ( 扔+ 1 ) 重构的过程就是分解过程的逆过程，即反更新，反预测和合并，其实现步骤在这里 就不具体给出了。 3 3 基于零树的子带预测 零树的概念最初是f l 了s h a p i r o 于1 9 9 3 年提出的。所谓零树是指如果一个小波系数在一 个粗的尺度上关于给定的阂值丁是不重要的，之后在较细尺度上在同样的空间位置中的 所有小波系数也关于阈值丁是不重要的，则称这些小波系数形成了一棵零树，具体可参 见文献 1 2 】。 1 2 基于小波变换的图像可分级编码研究 i a r n l 3l e v e l ：h 1 1 l l堪 l u m mh l ： 正l l 垃h 岐 习碎 u l 删 翔薛 l l 3硫3 ， i l 2 l 茁1 - 1 1 1 3 + h l i l h 2m 1 2 u m r h h l 图3 - 1 三级小波分解图图3 - 2 子带的重要性 一幅图像进行了三级小波变换后如图3 1 所示，小波系数的特点是越往低频子带系 数值越大，所包含的信息量越多，对人眼视觉越重要；而越往高频子带系数值越小，所 包含的信息量越少，对人眼视觉越不重要【l3 1 。它们的重要性排序如图3 2 所示，是从低 频到高频的“z ”字型扫描顺序。零树反映的就是h h 3 中的1 个结点对应h h 2 中的4 个结 点，再对应h h i 中的1 6 个结点这种数据结构。本章提出的算法就是基于图像中每棵零树 父子之间的这种逻辑对应关系所给出的预测编码方法。 3 4 基于最小二乘拟合的零树小波图像子带预测编码方案 3 4 1 总体过程 本文提出的算法整体实现过程如下： 输入原始图像h 三糍、波h 黼9h 三裂啵h 输入原始图像 图3 - 3 算法的整体实现过程 其中，对第二高频子带进行预测就是利用最小二乘拟合，对小波变换后的h l 2 ，l h 2 和h h z 三个子带的小波系数所采用的编码方法。 3 4 2 最小二乘拟合法 最小二乘拟合【1 4 】是根据所给数据点的分布情况，预测它们之间呈线性关系的一种有 效方法。假设有一组数据点( 船，y i ) ( 扛1 ，2 ，聊) ，使用最小二乘拟合法使它们满足类似 y = a l x + a z 这样的线性方程。而通过零树这种特殊的数据结构可以看出，第一、第二和 第三高频子带之间满足零树结构的结点应该存在某种线性关系。本章提出的算法就是利 用这种线性关系，通过第一和第三高频子带的小波系数来预测第二高频子带的小波系 数，满足方程的数据点集即为各个子带的小波系数。因此，只要方程的系数a i 确定下来， 就可以通过