（信号与信息处理专业论文）小波变换在图像压缩中的应用.pdf

上海大学硕士学位论文 摘要 随着多媒体技术的应用及i n t e m e t 的迅猛发展，图像的应用范围不断 扩大，如医学图像，数字图书馆，图像的远程浏览和检索，数码设备等领 域的应用。人们对图像编码的要求也日益提高。传统的基于离散余弦变换 ( d c t ) 的图像编码由于其自身存在的致命弱点方块效应，到目前为 止已经无法满足人们的要求，小波变换编码技术是一个新兴的图像编码方 法。一方面，小波编码拥有传统编码的优点。另一方面，小波变换多分辨 率的变换特性提供了利用人眼视觉特性的良好机制。 j p e g2 0 0 0 标准对静态图像压缩具有良好的性能，但由于其算法复杂 度高，不利于硬件实现。本文在s p i h t 算法的基础上提出了一种基于像素 域的改进方法。首先将图像的偶数列像素减去相邻两奇数列的均值，形成 分裂图像。然后将分裂图像的奇数列提取出来作为主图像，将偶数列提取 出来作为副图像。最后将主副图像以合适的权值分别进行压缩。解码时， 将主副图像分别解码，再恢复分裂图像，最后再恢复原图像。用该方法对标 准图像进行测试，结果表明，在相同的比特率条件下，重构图像的峰值信 噪比高于原算法0 3d b 以上。 最后在本论文提出的改进算法基础上，对图像压缩中小波基的选取进 行了研究。实验证明，d a u b e c h i e s 小波具有良好的图像压缩性能。 关键字：小波变换编码；零树；嵌入式零树编码；分层树的集分割；小波 基 v 上海大学硕士学位论文 a b s t r a c t w i t ht h ea p p l i c a t i o no fm u l t i m e d i at e c h n o l o g ya n dt h er a p i d d e v e l o p m e n to fi n t e r n e t ，t h ei m a g ei sc o n s t a n t l ye x p a n d i n gt h es c o p eo f a p p l i c a t i o n ，s u c ha sm e d i c a li m a g e s ，d i g i t a ll i b r a r y ，b r o w s i n ga n d r e m o t ei m a g er e t r i e v a l ，d i g i t a le q u i p m e n tf i e l d s p e o p l e sn e e do nt h e i m a g ec o d i n gi sa l s oi n c r e a s i n g i m a g ec o d i n gm e t h o d s ，w h i c ha r eb a s e d o nt h et r a d i t i o n a ld i s c r e t ec o s i n et r a n s f o r m ( d c t ) h a v eaf a t a lw e a k n e s s b l o c ke f f e c t ，u n a b l et om e e tt h ep e o p l e sd e m a n d s w a v e l e tt r a n s f o r m c o d i n gt e c h n o l o g yi sa ne m e r g i n gi m a g ec o d i n gm e t h o d o nt h eo n eh a n d ， w a v e l e te n c o d i n gh a st h ea d v a n t a g e so ft r a d iti o n a lc o d in gm e t h o d s o n t h eo t h e rh a n d ，t h ep r o p e r t yo fm u l t i r e s o l u t i o nw a v e l e tt r a n s f o r m p r o v i d e sag o o dm e c h a n i s mo fu s i n gh u m a nv i s u a lc h a r a c t e r i s t i c s j p e g2 0 0 0h a san i c ep r o p e r t yi ni m a g ec o m p r e s s i o n b u tt h e a l g o r i t h mi st o oc o m p li c a t e dt o ob ea c h i e v e db yh a r d w a r e o n ei m p r o v e d s p i h ta l g o r i t h mb a s e do np i x e ld o m a i ni sp r e s e n t e d f i r s to fa l l ，t h e p i x e lv a l u eo fe v e nc o l u m n ss u b t r a c t st h em e a no fn e i g h b o r i n gt w oo d d c o l u m n st of o r mt h es p lit i m a g e t h e n ，t a k eo u tt h eo d dc o l u m n so ft h e s p l i ti m a g et of o r mm a i ni m a g e ，t h ee v e nc o l u m n st of o r ma s s i s ti m a g e a tl a s t ，c o m p r e s st h em a i ni m a g ea n da s s i s ti m a g er e s p e c t i v e l yw i t ha p r o p e rw e i g h t w h e nn e e d i n gt os h o wt h eo r i g i n a li m a g e ，d e c o m p r e s st h e m a i ni m a g ea n da s s is ti m a g er e s p e c ti v e l yt of o r mt h es p lit i m a g e ，a n d r e v e a lt h eo r i g i n a li m a g ea tl a s t t h i sc o d i n gm e t h o di st e s t e db y s t a n d a r di m a g e s t h er e s u l t ss h o wt h a tt h ep s n rv a l u ei sm o r et h a n0 3 d bt h a to fo r i g i n a ls p i h ta tt h es a m eb itr a t e t h ep r o p e r ti e so fw a v e l e tb a s e sa r er e s e a r c h e db a s eo nt h ei m p r o v e d s p i h ta l g o r i t h ma tl a s t t h ee x p e r i m e n t a lr e s u l t ss h o w sd a u b e c h i e sw a v e l e t b a s e sh a v ean i c ep r o p e r t yi ni m a g ec o m p r e s s i o n 上海大学硕士学位论文 k e y w o r d s ：c o d i n gb a s e do nw a v e l e tt r a n s f o r m ；z e r ot r e e ； e z w ( e m b e d d e dz e r ow a v e l e 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 ) ； 腑v e l e tb a s e v i i 上海大学硕士学位论文 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已发 表或撰写过的研究成果。参与同一工作的其他同志对本研究所做的 任何贡献均已在论文中作了明确的说明并表示了谢意。 签各斗日期硷叫 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即： 学校有权保留论文及送交论文复印件，允许论文被查阅和借阅；学 校可以公布论文的全部或部分内容。 ( 保密的论文在解密后应遵守此规定) 签名： 导师签名：辫期：划 上海大学硕士学位论文 第一章绪论 1 1 论文研究的背景及意义 在人类所接收到的全部信息中，有7 0 以上是通过视觉得到的【l 】。和语音 或文字信息相比，图像包含的信息量更大，更直观、更确切，因而具有更高的 使用效率和更广泛的适应性，图像信息的处理、存储和传输在社会生活中的作 用越来越突出。 然而图像经过采样和量化转换成数字信号后，其数据量的巨大已经成为多 媒体技术发展中的一个非常棘手问题。尽管随着科学技术的发展，海量存储技 术、处理器的速度以及数字通信系统的性能迅猛发展，但高清晰度数字图像数 据量对数据存储的能力和数据传输带宽的需求仍然超出了现有技术的能力【2 1 。 同时，在某些图像通信场合下的传输受客观物理条件的限制，难以扩展。例如 在深海勘探中利用水声通信技术的水下视频传输，其水声信息所具有的通信带 宽是极其有限的。因此，只有对图像进行编码压缩处理，去除图像中大量的冗 余信息，大大地压缩图像的数据量，使其适应数字通信信道和存储介质，才是 目前解决这一矛盾的一个切实可行的途径【3 1 。静态图像编码技术的研究发展， 对于动态图像编码技术有很大的借鉴作用，本文的研究集中于静态图像的编码 技术。 小波变换编码技术是在二十世纪九十年代以后兴起的编码方法。一方面， 小波编码拥有传统编码的一些优点，能够很好消除图像数据中的统计冗余。另 一方面，小波变换多分辨率的变换特性提供了利用人眼视觉特性的良好机制， 而且小波变换后的图像数据能够保持原图像在各种分辨率下的精细结构，为进 一步去除图像中其他形式的冗余信息提供了便利。因此，小波图像编码在图像 编码领域被非常看好【4 1 。但目前，基于小波变换的图像编码国际标准尚不十分 成熟，相应的由纯硬件实现的小波编码的算法相对于传统的基于d c t 变换的编 码方法来说，算法复杂度和灵活性都要大很多。就算法本身而言，还存在着如 何有效组织变换系数，应用人眼视觉特性、选取合适小波基等问题。 上海大学硕士学位论文 由a s a i d 和w a p e a r l m a n 提出的基于嵌入零树编码思想的s p i h t ( s e t p 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 ) 算法被认为是目前国际上图像变换领域最先进 的方法之一。该算法无需任何训练，支持多码率，而且具有较高的信噪比和较 好的图像复原质量。但该算法还存在一些不足： ( 1 ) 在快速小波变换过程中，需要与庞大的图像数据作卷积运算，计算复杂， 严重降低了编码速度。 ( 2 ) 对图像的尺寸有要求，并不能对所有尺寸图像进行变换。 ( 3 ) 未考虑人眼视觉特性( h u m a n v i s u a ls y s t e m ) ，影响了图像复原质量。 许多学者致力于该算法的改进。 柯丽，黄廉卿针对原算法的不足引入了“最小阈值 和“最小输出位 ，同 时改变了原算法的扫描顺序，降低了算法的复杂程度，并使其更有利于并行优 化处型5 1 。 陈红新，刘正光等提出了基于提升小波的s p i h t 改进算法【6 1 ，采用整数实 现的提升格式代替了原来的小波变换，简化了计算过程。对小波系数采用基于 块的结构划分，在频域重新建立空间方向树。根据块中相邻系数相关性建立上 下文模型，提高了编码效率。 王向阳，杨红颖提出一种基于人眼视觉特性的快速图像编码算法【7 1 ，通过 全面引入快速小波变换，重新定义扩充零树结构，综合考虑人眼视觉特性的方 法，取得了良好的改进效果。 大多数的改进都是基于频域，对方向树进行改进或是用小波提升算法、小 波包、多小波等进行改进，本文提出一种基于像素域的改进方法。从恢复图像 的p s n r 角度来看，柯丽，黄廉卿提出的算法改进效果比较明显。在不同的压 缩率下，本文提出的改进算法与其比较，结果表明，本文提出的算法改进效果 更加有效。 1 2 论文的主要研究工作 论文在基于小波变换的图像编码方法研究的基础上，提出一种在像素域改 进的s p i h t 算法。并在改进算法的基础上，对几种常用小波基的压缩性能进行 2 上海大学硕士学位论文 了比较。具体研究工作包括： ( 1 ) 在s p i h t 算法的基础上，提出了一种基于像素域的类似于视频图像 中帧内压缩的改进算法。通过将原图像分裂为包含原图像主要信息的 主图像与包含原图像细节信息的副图像，然后分别进行压缩的方法， 取得了良好的改进效果 ( 2 ) 在本文提出的改进算法基础上，对图像压缩中小波基的选取进行了研 究。对几种常用小波基的压缩性能进行了比较。实验结果表明， d a u b e c h i e s 小波最有良好的图像压缩性能。 1 3 论文的结构 本文共分六章，各章的内容安排如下： 第一章，绪论。简要阐述了本论文的研究背景、意义、主要工作以及结构 安排。 第二章，介绍图像编码技术。包括数据压缩系统组成、图像编码压缩的必 要性、图像编码压缩的可行性、图像编码压缩的技术指标、图像 数据压缩的方法，包括统计编码，预测编码，变换编码，子带编 码，分形编码，模型基图像编码，块截断编码，神经网络图像编 码等、并对静态图像压缩编码标准做了介绍。 第三章，对小波变换理论进行了介绍。包括相关的数学背景、小波编码的 流程、小波变换的性质等。 第四章，基于小波变换的图像压缩。对e z w 与s p i h t 算法分别进行了研究， 分析了s p i h t 算法优于e z w 的原因；在s p i h t 算法的基础上，提 出了一种基于像素域的改进算法，通过实验验证，取得了良好的 改进效果。 第五章，在本文提出的改进算法基础上，对图像压缩中小波基的选取进行 了研究。 第六章，总结与展望。对本文的工作进行了总结，并探讨了可以继续深入 研究的方向。 上海大学硕士学位论文 2 1 数字图像 第二章图像压缩编码 图像是自然界景物的客观反映。自然界的图像无论在亮度、色彩，还是空 间分布上都是以模拟函数的形式出现的，无法采用数字计算机进行处理、传输 和存储。 在数字图像领域，将图像看成是由许多大小相同、形状一致的像素( p i c t u r e e l e m e n t 简称p i x e l 组成) 用二维矩阵表示。图像的数字化包括取样和量化两个 主要步骤。在空间将连续坐标离散化的过程为取样，而进一步将图像的幅度值 整数化的过程称为量化。 2 2 图像编码技术 数据压缩就是以较少的数据量表示信源以原始形式所代表的信息，其目的 在于节省存储空间、传输时间、信号频带或发送能量等。其组成系统如图2 1 所示。 ( 图2 1 数据压缩系统组成图) 信息论认为：以熵代表信源所含的平均信息量，若信源编码的熵大于信息 源的实际熵，则信源中的数据一定存在冗余度。冗余数据的去除不会减少信息 量。信息量与数据量的关系可由式( 2 1 ) 给出： ，= d d u ( 2 1 ) 式中，d ，幽分别表示信息量，数据量，冗余量。在实际应用场合下，压缩 4 上海大学硕士学位论文 过程应尽量保证去除冗余量而不会减少或较少减少信息量，即压缩后的数据要 能够完全或在一定的容差内近似恢复。完全恢复被压缩信源信息的方法称为无 损压缩或无失真压缩，近似恢复的方法称为有损压缩或有失真压缩。 2 2 1 图像压缩编码的必要性与可能性 1 图像压缩编码的必要性 采用数字技术会使信号处理技术性能大为提高，但其数据量的增加也是十 分惊人的。图像数据更是多媒体、网络通信等技术重点研究的压缩对象。不加 压缩的图像数据是计算机的处理速度、通信信道的容量等所无法承受的。 如果将上述的图像信号压缩几倍、十几倍、甚至上百倍，将十分有利于图 像的存储和传输。可见，在现有硬件设施条件下，对图像信号本身进行压缩是 解决上述矛盾的主要出路。 2 图像压缩编码的可能性 图像数据量大，同时冗余数据也是客观存在的。在有些图像中可压缩的可 能性很大。一般图像中存在着以下数据冗余因裂8 】【9 】【10 1 。 ( 1 ) 编码冗余 编码冗余也称信息熵冗余。去除信源编码中的冗余量可以在对信息无损的 前提下减少代表信息的数据量。对图像进行编码时，要建立表达图像信息的一 系列符号码本。如果码本不能使每个像素所需的平均比特数最小，则说明存在 编码冗余，就存在压缩的可能性。 ( 2 ) 空间冗余 这是静态图像存在的最主要的一种数据冗余。同一景物表面上各采样点的 颜色之间存在着空间连贯性，但是基于离散像素采样来表示物体颜色的方式通 常没有利用景物表面颜色的这种空间连贯性，从而产生了空间冗余。 ( 3 ) 时间冗余 时间冗余反映在视频图像中就是相邻帧图像之间有较大的相关性，一帧图 像中的某物体或场景可以由其他帧图像中的物体或场景重构出来。 ( 4 ) 结构冗余 上海大学硕士学位论文 冗余。 有些图像的纹理区中图像的像素值存在着明显的分布模式，即存在着结构 ( 5 ) 知识冗余 有些图像的理解与某些知识有相当大的相关性，这类规律性的结构可由先 验知识和背景知识得到，该类冗余称为知识冗余。 ( 6 ) 视觉冗余 事实表明，人类的视觉系统对图像场的敏感性是非均匀和非线性的。然而， 在记录原始的图像数据时，通常假定视觉系统是均匀和线性的，对视觉敏感和 不敏感的部分同样对待，从而产生了比理想编码更多的数据，这就是视觉冗余 【1 1 1 。通过对人类视觉进行大量实验，发现了以下的视觉均匀特性： 视觉系统对图像的亮度和色度的敏感性相差很大，视觉系统对亮度的 敏感度远远高于对色彩度的敏感度。 随着亮度的增加，视觉系统对量化误差的敏感性降低。这是由于人眼 的辨别能力与物体周围的背景亮度成反比。因此，在高亮度区，灰度值的量化 可以更粗糙一些。 2 2 2 图像压缩编码的技术指标 一般地，图像压缩应能做到压缩比大、算法简单、易于硬件和软件实现、 压缩和解压实时性好、解压缩恢复的图像失真小等。但这些指标对同一压缩方 法很难统一，在实际系统中往往需要抓住主要矛盾，全面权衡。下面介绍常用 的图像压缩技术指标。 1 图像熵与平均码长 熵是指信源的平均信息量。如果一幅图像像素的灰度级为玉( f = 1 ，2 ，朋) ， 若毛出现的概率为尸( 五) ，则图像的熵定义为： m h ( z ) = 一p ( x ，) l 0 9 2p ( 薯) 图像熵表示像素灰度级集合的平均比特数。熵的单位为比特字符。熵具有以下 6 上海大学硕士学位论文 的性质： ( 1 ) 当m 级灰度出现的概率相等时，即p ( ) = 1 m 时，有最大熵值 h ( x ) = l 0 9 2 m ； ( 2 ) 在极端情况下，当p ( 而) = 0 或p ( ) = 1 时，日( z ) = 0 ，这表明确定性信号 的熵值为0 ； ( 3 ) 随机性图像信号的熵非负，满足o 0 ，即当s 2 墨 s 时，乃是墨的 严格单调递增函数。而当墨 s 2 时，五 o ，即当o 墨 s 2 时，乃是墨的 严格单调递减函数。因此如的构造函数( 式( 2 1 4 ) ) 满足近似条件。 由式( 2 1 5 ) 可得： l i m 允= l i m 1 + 2 k s _ 0 s _ o 一 当墨= s 时，由五= 1 可得a = 1 ，所以式( 2 1 6 ) 满足a 的边界条件。 以墨为变量，对式( 2 1 5 ) i 两边求导，即： 水筹一毒”缸 将式( 2 1 6 ) 代入到式( 2 1 8 ) 得 水一型嚼豆 很明显 1 ) ，或收缩( 口 o ) 或左移( 6 l ，6 0 r ；m ，疗z ，则由式( 3 4 ) 得离散小波 一旦 少。o ) = a o2 ( 口i “t n b o ) ( 3 1 3 ) 离散小波变换为： 既，。= s ( f ) y ：一( t ) d t ( 3 1 4 ) 如果s ( f ) 也是离散的，记为s ( k ) ，则有 既。= s ( 七) 戒。( 七) ( 3 1 5 ) 小波逆变换的离散形式为： s ( 七) = ，。y m ，。 ( 3 1 6 ) 若a o = 2 ，则离散小波变换为二进小波变换。 6 二维小波变换 在图像处理中应用的小波变换是二维小波变换，二维小波函数j ( 工，y ) 的连 续小波变换的定义如下： 形( 口，吃，毛) = j ( 石，y ) 也以( 工，y ) d x d y ( 3 1 7 ) 式中，吃和瓦分别表示在x ，y 轴的平移。二维连续小波变换逆变换为： 舡川= 吉j c o 形( 口，吃，岛耽鹕( 五y ) 识也7 d a ( 3 1 8 ) 式中，勺为系数，a 6 ，( 工，j ，) 为： 小川= 南y c 等，孚， 上海大学硕士学位论文 而( 石，y ) 是一个二维基本小波。 7 小波变换的性质 ( 1 ) 线性性质 若胛b ( f ) 】呢( 口，6 ) ，则对任何常数集 q ，i = 1 ，2 ，) 有 唧口，毛( f ) 】_ 口；岷( 口，6 ) ( 2 ) 平移不变性 若g t i s ( f ) 】一形( 口，6 ) ，则 w t s f o f ) 】= 形( 口，b f ) ( 3 ) 伸缩共变性 若唧s ( f ) 】_ 形( 口，6 ) ，则 嘲s ( c f ) 】- 睨( c a , c b ) ， 、，c ( 4 ) 自相似性 对不同尺度因子a 和平移因子b ，小波变换是自相似的。 ( 5 ) 冗余性 连续小波变换中存在信息表达的冗余，如一维信号的小波变换是二维的，存在 信息的重复表达。 ( 6 ) 能量守恒 与短时傅里叶变换不同，小波变换不增加信号的能量。 3 3 多分辨率分析 小波分析之前的许多技术发展都来自一个称为多分辨率分析的领域。多分辨 率分析的发展是为了克服f o u r i e r 分析存在的局限性。通常我们希望在较大的尺 度上，可以看到物体的总体特征，而在较小的尺度上，则看到物体某一部分的 细节特征。如果把一个对象分解到不同的尺度上，就可以达到我们的期望。这 上海大学硕士学位论文 便是多分辨率分析的基本思想。沿着多分辨率分析的发展，开成了现代的小波 分析。 3 3 1 多分辨率分析的定义 多分辨率分析又称多尺度分析，它是在r ( 尺) 函数空间内，将函数厂描述为 一系列近似函数的极限。每一个近似都是函数厂的平常版本，而且具有越来越 精细的近似函数。这些近似都是在不同尺度得到的，多分辨率分析由此得名。 在对多分辨率分析进行严格的数学定义之前，引入雷斯基( r i e s z ) 的概念： 希尔伯特( h i l b e r t ) 空间h 中的一个元素序列 ) 脚称为h 的一个雷斯基， 如果它满足以下两个条件： ( 1 ) h = s p a n a 。z ，即h 是由 口。) 舵z 的元素线性组合生成的空间的闭包； ( 2 ) 存在正数彳b ，使对任意数列 巳) 艟z ，2 ( z ) ，有 嘲n e z 刊i l i 荟巳卜驯2 一e z n e z 函数空间口( r ) 中的多分辨率分析是指r ( r ) 满足如下条件的一个子空间序列 f 矿l l 历j m e z ( 1 ) 单调性 。ckcv oc 圪lc ： ( 2 ) 逼近性 n = o ) ，u = r ( 尺) ； m e z朋e z ( 3 ) 伸缩性 f ( t ) 圪 f ( 2 t ) 圪一l ； ( 4 ) 平移不变性 矽( f ) 巧= 矿( 一2 一七) 巧，v 尼z ； ( 5 ) 雷斯基存在性 上海大学硕士学位论文 存在函数矽( f ) z o ，使得 矽( 2 7 t - k ) ，kez ) 构成巧的r i e s z 基。 3 3 2m a i l a t 快速算法 m a l l a t 提出了信号的塔式多分辨率分解与重构算法。即：m a l l a t 算法。m a l l a t 算法是小波变换的一个快速算法，它在小波分析中的地位颇有些类似于f f t 在 经典f o u r i e r 分析中的地位。 m a l l a t 算法的基本思想如下：假定已经计算出一个函数或信号f ( t ) 亭似) 在分辨率2 7 下的离散逼近4 厂，则厂( f ) 在分辨率2 叫“的离散逼近4 + 。fn - f f $ 以j l t l 过用离散低通滤波器对彳，厂滤波获得。 令吐。( f ) 和甲一肚( f ) 分别是函数( f ) 在2 7 分辨率逼近下的尺度函数和小波 函数，则其离散逼近彳，f ( t ) 和细节部分d j f ( t ) 可分别表示为： a j f ( t ) = q ，t 丸肚( f ) ( 3 2 3 ) k = - - d j f ( t ) = 甲吐i ( f ) ，j 0 ( 3 2 4 ) k = - - o 其中，q 。和q ，。分别为2 - j 分辨率下的近似分量分解系数和细节分量分解系数。 根据m a l l a t 算法的分解思想，a j f ( t ) 可以分解为为近似分量4 + 。厂( f ) 与细节 分量q + 。厂( f ) 之和： a j f ( t ) = 4 + l 厂( f ) + q + l 厂( f ) ( 3 2 5 ) 由式( 3 2 2 ) 、( 3 2 3 ) 和式( 3 2 4 ) 可以得到q ，女和q 。i 的分解迭代公式如下： q “。= h ( k - 2 m ) c j ，i ( 3 2 6 ) k = - - o q “啊= g ( k - 2 m ) c j 2 8 其中： ( 七一2 m ) = ( 3 2 8 ) g ( 七一2 ，1 ) = ( 3 2 9 ) 同时，由( 3 2 2 ) 、( 3 2 3 ) 和式( 3 2 4 ) 还可以得到q ，。和q ，。的合成迭代公式： 一 = h ( k - 2 m ) c j + l ，啊+ g ( k 一2 m ) d j + l 。 ( 3 3 0 ) m = m t 式( 3 2 6 ) 、( 3 2 7 ) 便是一维m a l l a t 塔式分解算法，而式( 3 3 0 ) 是m a l l a t 重构算法。它们分别如图3 1 所示 c o ，t 一c a ，女 - c 2 ，c 3 ；七- c 4 d 1 吣b ，钆 弋弋孓弋 把一维m a l l a t 算法推广到二维的情况，二维m a l l a t 分解算法为： q + 。( 所，1 ) = j l l ( 尼一2 m ) h ( z 一2 n ) c j ( k ，) t = i = - - ” 谚+ 。( 聊，刀) = j i ( 七一2 m ) g ( ，一2 n ) c j ( k ，) k = - - ，= o 瑶。( 朋，1 ) = g ( k - 2 m ) h ( ，一2 n ) c j ( k ，) k = - - a o ，2 1 巧+ 。( 聊，刀) = g ( k - 2 m ) g ( ，一2 n ) c j ( k ，) 这里，q + 是q 的低频近似分量部分，珥+ 是水平方向上的高频部分，d j 2 + 。是 垂直方向上的高频部分，而壤。则是对角线方向上的高频部分。 相应的，二维m a l l a t 重构算法可以表述如下： 2 9 上海大学硕士学位论文 1 0 c j ( k ，驴h ( k 一2 m ) h ( 1 - 2 n ) c j + l ( m ，玎) + h ( k - 2 m ) g ( 1 - 2 n ) d _ ：+ 。( m ，刀) ，一=一=，开=目=。 + g ( k - 2 m ) h ( 1 - 2 n ) d + ，( m ，z ) + g ( k - 2 m ) g ( 1 - 2 n ) d ；+ 。( 所，疗) ( 3 3 2 ) ，”=月2-肘暑。nz- 本论文在后面的改进算法中均采用m a l l a t 算法。 3 4 本章小结 本章对小波变换理论进行了介绍。包括相关的数学背景、小波编码的流程、 小波变换的性质等。 上海大学硕士学位论文 第四章基于小波变换的图像压缩 j p e g2 0 0 0 标准对静态图像压缩具有良好的性能，但由于其算法复杂度高， 不利于硬件实现。本章从嵌入式小波零树压缩编码的经典算法e z w 与s p i h t 算法入手，提出了一种基于像素域的改进的s p i h t 算法。 4 1 小波图像压缩概述 4 1 1 小波图像压缩的特点 长期以来，图像压缩编码利用离散余弦变换( d c t ) 作为主要的变换技术， 并成功地应用于各种标准，如j p e g ，m p e g 1 ，m p e g 2 。但是，在基于d c t 的图像变换编码中，人们将图像分为8 x8 像素或1 6 1 6 像素的块来处理，从 而容易出现方块效应。 小波变换是全局变换，时域和频域都具有良好的局部化性能，而且在应用 中易于考虑人类的视觉特性，从而成为图像压缩编码的主要技术之一。基于小 波变换的图像编码与经典的基于d c t 的图像编码方法相比，具有如下优点： ( 1 ) 小波变换本质上是全局变换，重建图像中可以免除采用分块正交变换编码 所固有的“方块效应。 ( 2 ) 小波变换采用塔式分解的数据结构，与人眼由粗到精、由全貌到细节的视 觉生理特性相一致，这是将w t 与h v s 的空间分解特性结合起来以改善图像压 缩性能的有利条件。小波变换比经典的变换( d c t ) 更符合人的视觉特性，通 过合理的量化编码产生的人为噪声比同样比特率的j p e g 方法产生的影响要小 得多。 ( 3 ) 小波变换具有保持性、能够有效地改变图像的能量分布，同时不损伤原始 图像所包含的信息。 ( 4 ) 多级分解后形成的不同分辨率和频率特征的子带信号，在失真编码中综合 考虑视学特性，同时有利于图像的渐近传输。 小波变换能比d c t 变换得到更高性能、用途更广的图像编码。目前，基于 3 1 l 海大学碗学托论文 小波的多分辨率编码方法已经引起了普遍关注。在静态图像压缩方面，d w t 相 比d c t 有明显优势，而在视频图像压缩方面啪1 ，优势并不明显。 4 1 2 编码流程 一般情况下，对于静止扶度图像，小波编码可以分成四个部分小波变换 量化、编码、熵编码。解码过程与编码过程完全相反。如图4l 所示。 图4 l ( a ) 小波图像编码流程 。吾匝丑1 亘卜恒习1 巫亚 4 1 3 零树的概念 圈4 1 巾) 小波图像解码流程 图4 1 小波图像编解码流程 如图42 ，图43 所示，一幅图像经过三级小波分解后形成了1 3 个子带。相 应的父子关系也在图中标出。如果该结构中有一个元素，它本身不重要，而且 它的子孙后代都不重要，我们称这是一棵树。这样的结构在编码中_ e i j 一个符号 即可以表示。这种零树是e z w 5 2 1 ( e m b e d d e d z e r o w a y e l e t ) 、s p i h t l 5 3 1 ( s e t p a r t i t i o n i n g i n h i e r a r c h i c a l t r e e s ) 编码算法的基础。 隧 i 隧蓊 图4 2l e n a 图像三级小渡分解图 上海大学硕士学位论文 4 2e z w 算法原理 4 2 1 内嵌编码 内嵌编码也就是嵌入式编码，就是编码器将待编码的比特按重要性的不同 进行排序，根据目标码率或失真度大小要求随时结束编码；同样，对于给定码 流解码器也能够随时结束解码，并可以得到相应码流截断处的目标码率的恢复 图像。 i 上父 h l 2h l l 弋 衄2 、 坩h 2 t l h l ； 心h 1 l 图4 3 小波系数间的父子关系 内嵌编码中首先传输的是最重要的信息，也就是幅值最大的变换系数的位 信息。图4 4 示出了一个幅值由大到小排序后的变换系数的二进制列表。每一 行代表一层位平面，最上层为符号位，越高层的位平面的信息权重越大，对于 编码也重要。内嵌编码的次序是从最重要的位( 最高位) 到最不重要位( 最低 位) 逐个发送，直到达到所需要的码率时停止。 如图4 4 可知内嵌编码的输出信息主要包括：排序信息和重要像素的位信 息。其中，位信息是编码必不可少的有效信息，对应于表中箭头所划过比特位； 而排序信息则是辅助信息，按其重要性从左到右排，反映了重要像素在原图上 的空间位置，用于恢复原始的数据结构。因此内嵌算法中排序算法的优劣和排 序信息的处理决定了整个编码算法的效率。 经过离散小波变换后，把一个图像分解成若干级子带图，对于同一级子图， 上海大学硕士学位论文 低频图像屿最重要，其次是屿和l i t , ，高频图像吗相对不重要；对于不 同的级来说，级高的重要，级低的相对不重要。所以，子图按其重要性排序是： l l j ，h l j ，l hj ，h h j ，h l j 、，l hj ，h hj ，h k ，l hl ，i - h i 符号 1 2 3 4 5 6 7 sss sssss ll ooo0 o 0 llo0 o0 ll1o l 图4 4 按幅度排序的二进制信息 小波分解在不同分辨率下各子带中系数的父一子关系可以表示成树结构， 粗尺度上的那个小波系数称为父系数，为树根，在较细尺度上相应空间位置上 的小波系数称为子系数，父系数与子系数的关系如图4 3 所示。 对于一个给定的门限t ，- d , 波系数x , 如果有i x l l i ，其中i i 是小波变换系数矩阵中的最大绝对值。s a q 实际上就是 一种按比特平面的编码方式。 在利用s a q 量化的编码过程中，依次形成两个表，一个主表，一个副表。 对于一个给定的门限互，首先进行一遍主扫描，生成主表。主表包含的是以z 为 门限的有效值映射，由符号p o s ，n e g ，z t r ，i z 构成，形成方式如上所述。 对于门限正在进行完一遍扫描后，紧接着进行副扫描，副扫描是对已发现 的有效值进行更细化的表示。假设当前门限是写，进行完主扫描后，已发现的 有效值的幅度处于2 瓦一瓦之间，如果没有进一步细化表示，解码器仅知道这些 值处于2 r o - r 0 2 _ r 日q ，一般可能会用( 2 t o + t o ) 2 作为它的重构值，副扫描的目的 是进一步细化这些值。用l b i t 的0 或1 进一步描述一个值是处于该区间的上半 部还是下半部，用1 表示一个值处于上半部，即( 2 t o ，r o + 瓦2 】之间，；用0 表 示一个值处于下半部，即( 瓦+ 瓦2 ，r o 2 _ r 日- j 。上半部的重构值用r o + 3 4 t o ，下 半部的重构值用r o + l 4 t o ，这样就将一个有效值重构时的不确定区间从r o 2 降 低到瓦4 ，相当于提高了一倍表示精度。 4 3s p i h t 算法 自1 9 9 3 年s h a p i r o 提出嵌入零树小波算法( e z w ) 以来，由于其算法复杂 3 7 上海大学硕士学位论文 度不高，且产生的码流是嵌入式的，易于进行压缩比的控制和实现可伸缩编码， 因此有许多人致力于零树小波编码的研究，陈红卫等提出了一种基于e z w 小波 树结构组织的改进的图像编码方法【州。其中a s a i d 和w p e a r l m a n 提出的基 于e z w 的分层树的集分割( s p m t ) 算法影响最大。 由a s a i d 和w a p e a r l m a n 提出的基于嵌入零树编码思想的s p i h t ( s e t p 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 ) 算法被认为是目前国际上图像变换编码领域最 先进的方法之一。它以零树编码( e z w ) 算法的零树结构为基础，将某一树节 点及其所有后继节点划为同一集合，并采用适当的集合分割排序策略，通过初 始化、排序( s o r t i n gp a s s ) 、细化过程( r e f i n e m e n tp a s s ) 和量化步长更新 ( u p d a t e ) 这四个子过程完成嵌入编码。s p i h t 编码算法不仅结构简单，无需 任何训练，支持多码率，而且具有较高的信噪比和较好的复原质量，它是对e z w 算法的改进，总体性能要更优于e z w 算法。 4 3 1 算法描述 s p i h t 编码算法使用了如下定义： ht 空间方向树所有根节点的坐标集合： g ，：点( f ，_ ，) ； z ( i ，j ) ：点( f ，_ ，) 及其所有的后代的坐标集合，即指空间方向树； o ( i ，j ) ：表示节点( f ，歹) 的直接后继节点( 即4 个子节点) 的坐标集合； d ( i ，j ) ：表示节点( f ，) 的所有后继节点的坐标集合，并记以类型a ； 三( f ，j ) ：表示节点( f ，) 的除了直接后继节点以外所有后继节点的坐标集合，即 l ( i ，_ ，) = d ( i ，) 一o ( i ，j ) ，记以曰类型； 基于以上概念，在s p i h t 算法中，集合的分割策略如下所示： z ( i ，_ ，) = c j ，+ d ( f ，j ) ( 4 1 ) d ( i ，_ ，) = o ( i ，j ) + l c i ，_ ，) ( 4 2 ) 上海大学硕士学位论文 l ( i ，) = 3 ( k ，) ( 七，驰o ( i ，歹) l i s ( 1 i s to f i n s i g n i f i c a n ts e t s ) 表示不重要集合表( 待编码集合) ； l p ( 1 i s to f i n s i g n i f i c a n tp i x e l s ) 表示不重要系数表： l s p ( 1 i s t o f s i g n i f i c a n tp i x e l s ) 表示重要系数表； 设c f ，为点( f ，) 的系数，定义重要性数量( ) ： s 。( r ) ：l , m a x 1 c t 。，i ) 2 4 l 0 ，e l s e 算法流程为： ( 1 ) 初始化 输出t i = 【! 。g ： i i l a u ，x i c , 。娜! j ，将铲置空，将所有最高层节点( f ，j ) 彭t f l , l i p 中，并将其中有后继节点的节点放入l i s 表中，同时标以彳类型。 ( 2 ) 排序过程 对于卿表中每个节点( f ，_ ，) ： 1 ) 输出鼠( z ，j ) ； 2 ) 如果最( f ，) = 1 ，则将节点( f ，) 移到