（通信与信息系统专业论文）基于小波变换的图像压缩算法研究(1).pdf

西南交通大学硕士磷究生学位论文第1 戮 摘要 鬻像蓬种重要鲍二缳信号，由于其数据量缀大，在存储稻传辕翡辩 候要对其进行压缩处理。小波变换是一种新兴的数学工具，基于小波的图 像联缠技术燕受到广泛妁关注和磺究。图像经过小波交换以嚣，在对城和频 域都具有良好的局部亿特性，重建图像中可以克服采用离敬余弦变换编码 所固有的方块效应，而且与人类视觉特性相一致 本逾文主要磅炎了基予，l 、波交羧貔静态图橡压缤算法，完成了娃下一 些工作：介绍了传统图像编码和小波变换编码的原理和方法，列举了常用 的图像压缩标准，在理论分析的基础上总结出小波变换的优势。羹点研究 了，l 、波编码箨法中鬻名静嵌入式零褥，j 、波冀法( e z 榉) 及葵敬遴形式s p i 蕊 算法，并在其基础上其提出了自己的改进算法，包括采用掇升方案，降低 了黢始小波变换兹复杂度；在量化醚弓l 入了符合人类视觉特性兹m a 强o s 模板重新定义各子带系数幅值以提高重构图像的主蕊质量；为了遗一步降 低复杂度，在编码时对e z w 算法采用新的阚值循环策略，而在进行s p i h t 续礤霹将低频予带羚系数全默认蔻正，减少了赣爨豹璃字，疆裹了编玛效 率。 试验结果表明，虽然本文所提出的改进算法与经典的e z w 和s p l h t 胡魄虽然在蜂篷信臻琵上略有下降，僵是彝法的复杂度有掰降蘸蠡佼编褥 的方式更贴近人类视觉系统，总体来说是一种有效的压缩算法。 关键词；图像压缩；小波交换；零树：提升方案；人类视辩系统 西南嶷通大学硕士研究生学位论文 第1 i 页 a b s t r a c t i m a g ei sa ni m p o r t a n tt w o 二d i m e n s i o ns i g n a l b e c a u s eo ft 1 1 eh u g od a t ai t e o n t 菇n s ， m 轾露em n s tb ec o m p r e s s 翻确e 珏i li ss t o 矬畦甜臼a n s p o r 酶矗+ 麓l e w a v e l e tt r a l l s f b m ( w t ) i sa r i s i n gm a m e m a l i c a l t 0 0 1 t h ct e c h n o l o g yo fi m a g e c o m d 辑s s i o n 蛔s e do nw a v e l e th a s 出甚w nm 珏c ha 始n t i o na n dh a sb e e n r e s e a r c h e db r o a d l y w l e nai m a 窖ei st f a n s f o r m e db yt h ew a v e l 。t ，i th a s f h v o r d b l el o o a l i z ec h a r a c t e r i 8 t i ci nb o t ht i m e d o m a i na n d 行e q u e n c e r e g i o n a n d 扭穗e 王e b 基l di m 鑫g e 镪ee o 豫a 趣糟l 藤a m o 醚s 鑫曩t i o 建o ft h ed i s c r 。托c o s i n e t r a n s 矗r r nc a nb eo v o r c a m e ，f u n l l e m l o r e t h ew ti si d e n t i c a lt oh u m a nv i s u a l s v s t e m f h v s l + f h 弧p a p c ri sm a i n l y 两。毽t h es t 艇i ei 礅鑫g ee o m 辫s s 确羚f i 渤瞳b 8 s e do n w a v e l e tt r a n s f o 咖，a n dc o m p l e t e 协e s ew o r k ：i n t r o d u c e dm et 1 1 e o r ya 1 1 d t c c h n i q u eo f a d i 畦o n 砖i m 8 9 ec o d i n ga 嬲w tc o 越n 窑e n m “a t e d 吐l ep r c v a l e m i m a g ec o m p r e s s i o n a ls t a f 罐a 砖s t h sp 雄) e rf o c u s e so nt h ef 釉o l l sw 。rc o d i n g a l g o “m mw h i c hn a m e de m b e d d e dz c r o 订e ew a v e l e t ( e z w ) a l g 嘶t h ma 1 1 di t s i 辫筠v 磁勰s p 辩t 哇羚躐强b 勰磁。致嚣z wa 聪s p i 壬 t 鼢i 蝣璋v e d a l g o r i m mi si n t r o d u c e dw l l i c hi n c l u d o su s i n gt 1 1 el i 矗i n gs c h e m et or e m l c et h e c o m p l e x i t yo f 吐l eo r i 百n a lw t 1 1 0i m p r o v et h es u b j e c t i v eq u a l i 吼u s et h e 醚a 黼o sl o m p l 疆t ew h i c ha c e o 撼谂珏v sl o 糟s e l 像em a 骜撼栩d eo f 氇ee o e 燕c i e n t s f o re a c hs u b * i m a g e t br e d u t h ec o m _ d l e x i t vm o r e ，l l s en e wt l l r e s h 0 1 ds c h e m e i ne z w p m s s ，d e 氛m t 盘e8 i g no f e f 萎c 艳嫩s 弛i o w 蠡潆q u e n c es u b i m 矗g et o p o s i t i v ei ns p l h tp r o c e s s ，s o 壤ed e f 毫r e n tc o d ec u td o w 弧a n d 像ec o 垂n g e m c i e n c yi n 巾m v e d 强es 溉糠珏重量镰掩s 疆l ss h o w 妇t ，舔l b 毪馥瞳摇i 嘲v o da l g 。棚摊魏a sa i o w e rp e r f o r m a n c eo np s n rc o m p a r e dw i t l lc l a s s i c a le z wa n ds p i h ti t s c o m p l e x i t yd e c r e a s e sa l l dt h ew a yo fi t sc o d i n 建i sm o r ei na c c o r dw i t hh u m a l l v 主s 聪8 量s y 霉t e 黻，s oi ti sm o r ee 臻戈t 主v e 。 k e yw o r d s ： m a g ec o m p r c s s i ；w a w 融缸瓤s f o 蕊；瓢l r e e ；l i b 堍8 c k m e ； h u m a nv i s u 羽s y s t e m 西南交通大学硕士研究生学位论文第l 页 第1 章绪论 1 。1 论文研究的背景及意义 人们在自然界中感受到的最重要的信息就是图像信息，随着多媒体技 术和通讯技术的日益发展，图像也成为了信息技术所处理的重要对象。近 些年来，图像技术发展十分迅速，这也推动了多媒体娱乐、多媒体通信、 数码相机、数码摄像头和高清晰度电视等各类与图片和视频相关的产品的 发展。 图像信息的数据量非常的大，随着各种成像设备的分辨率的不断提高， 单幅图像所包含的数据量也越来越大，大数据量的图像信息会给存储器的 存储容量、通信信道的带宽以及计算机的处理速度增加极大的压力。为了 解决这个问题，必须对图像进行压缩处理。 数字图像压缩编码的目的就是要以尽可能少的比特数来表征图像，同 时保持恢复图像的质量，对图像编码和解码算法的研究，己经受到人们越 来越多的关注，成为近些年信息技术中的热点。 1 2 数字图象压缩的研究现状及发展 图像能够进行压缩是因为图像数据问存在相关性也即冗余，所谓相关 性，就是能够根据给出的一部分数据来判断出其相邻数据。图像压缩的基 本原理首先是减少图像信号中的冗余信号，其次是根据信息论中的信源编 码原理，利用图像信号所固有的统计特性来进行压缩编码，最后是利用人 眼视觉特性来实现图像压缩。经典的图像压缩编码方法都是在传统的 s h a n n o n 信息论的指导下进行的【5 】。其中常用的编码方法有：变换编码、统计 编码、预测编码等f 2 】o 图像压缩的过程通常称为编码，而图像解压缩的过程叫做解码。根据 解码后的数据与原始数据是否完全一致来分类，图像压缩方法一般划分为 有损压缩和无损压缩，无损压缩是指重建图像与原始图像完全一致，常见 的无损压缩如h u 艋m 编码游程( r l c ) 编码、算术编码等；有损压缩的还 原图与原始图像存在一定误差，但视觉效果一般是可以接受的，根据有损 压缩的原理可分为预测编码、变换编码、量化编码、信：息熵编码等，其中 变换编码己被应用形成了各种图像压缩标准。变换编码方法实现数据压缩 西南交通大学硕士研究生学位论文 第2 页 的物理本质在于：经过一维或多维坐标系的嫩标旋转和变换，能够把散布在 各个坐标轴上的原始数据，在新的遗当的坐标系中集中到少数坐标轴上， 因霹有可麓箱较少鹃编码院特数来寝示。交换编磁通常至多包含三步处理： 变换，量化和编码。应用于圈像压缩中，变换编码将时域( 空间域) 图像变换 到系数域频率域) 上进嚣处理。变羧缡玛霹去滁空阗域楣邻像素的捐关蛙， 在空间域具有强相必性的倍号，反映到频域上是在菜些特定的区域中能量 集中，再选用适当的量化编码方法，达到眶缩的结果。常用的变换有k l 交羧、d c t 交换、猃s t 交糗、d f 彳交换，暖爱簧必豹d 鞭离教，l 、波交换 等。 从九十年代至今，图像压缩技术f | 臻完善，产生出了很多优秀姻算法。 弼离敬余弦交换、鬟夫曼编码、运动倍诗与 偿等。在这罄算法酶基磷上 又形成 了一系列 的国际标准 。 如j p e q j p e ( 泛o o o ， 差2 6 1 ， 2 6 3 ，m p e g - ，p e g 一2 l 嬲p 基g _ 4 。m p e g - 7 ，m p e g 一2 l 等。这 些标准的制定极大地推动了图像编码技术的实用化和产业纯。 进入八十年代以来，越来越多的新的图像压缩编码技术涌现出来，为 数字鹜镶嚣缩编码技本注入了薮戆活力。诲多学者结合摸式谖爨、计篓辍 视觉、神经网络理论、矢爨量化方法、分形理论和小波理论等不断探索图 像滕缩编码新技术，提出了基于享申经网络的编码方法、以分形几何为数学 鸷豢的分彩闺像编鹤方法稀稍蘑，j 、波变换避行信号分解懿小波交换圈像编 码方法。 1 3 小波变换及其在圈象压缩中的应用 小波分析是上傲纪8 0 年代中藤期发展越来的数学工具。小波分析是传 统傅立叶分析发展历史上飘程碑式的进展，近年来成为众多科学家共同关 心瓣热熹。夺滚分援霞予簿立时努耩懿缝方是，它在嚣域秘频域獒蠢嶷努 的局部化性质，被称为数学显微镜。小波分析己缀广泛运用于图像纹理分 析、图像编码、计算机视觉、模式识别、语音合成、地震信号处理、量予 臻瑷论等秘援领域。 小波交换在图像编码领域的应用十分引人注目，1 9 8 9 年m a l l a t 将小波 变换用于图像处理，提出了多分瓣率戆概念，开剑了小波变抉在图像编码 中的应用。与早期颁布的图象压缩标准相眈外波变换比d c t 变换甏适合予 视觉信号的表示，熏建图像中可以毙服采用分块正交变换编码所固有的方 块效应，戈其在诋 0 姆率融，敦采雯鞠显。小波交捩是全鼹交换，在露域 和频域都具有良好的局部化特性，而且在应用中易于考虑人类的视擞特性， 通过合理的蹙化编码产生的噪声比阅样比特率的d c t 方法隳小的多这样在 离藤缩晓情况下，所带来翦戆知失真龟小于d e t 交换。 西南交通大举硕士酣究生学位论文第3 页 但是，小波变换没有提供一种简单的方式来组织变换城的系数。为了 得到较高的压缩比，有效地组织变换域系数，使零码尽可熊地集中在一越 是非常重要黥。因诧研究图像小渡分解系数有效戆组织帮编码方法是夺液 变欹图像编码的关键技术之一。在小波编粥方法中最为著名的是1 9 9 3 年 髓8 p i r o 提如粒嵌入式零挝编码 0 是尺度因子，b 是位移因子，6 口 其中妒r ( r ) 且满足条件： q = 筹虮。 ( 3 6 ) 式中妒( ) 是妒o ) 的傅氏变换，该条件称为允许条件。小波变换的变换 基的选择必须满足( 3 6 ) 。傅氏变换中，变换基是固定的，而小波变换基 是多变可选的，根据不同的需要选择适当的小波基。在具体应用中，根据 原函数f ( x ) 的特点来选择小波变换基p ( f ) ，使得小波变换能更好的反映 f ( x ) 的特征。 西南交通大学硕士研究生学位论文 第1 6 页 3 2 3 离散小波变换 将连续小波的尺度和平移参数离散化，即令 口= 盘芋，6 = 趋以f ，d o l ， o 掰，肛z ( 3 7 ) 即可得到离散小波 山) 5 赤( 三笋胁卜蚓8 ) 定义：信号f ( t ) 的离散小波变换定义为 d 矿0 = = d 。一咧j ：c ，妒) ￥k 。o 一月) 以 ( 3 9 ) 由于我们处理的数字图像是一种离散的二维信号，因此要对其进行二 维离散小波变换。二维离散小波变换和我们熟悉的二维离散傅立叶变换类 似，只需要对数字图像在行和列方向上分别做维的离散小波变换即可完 成。 3 3 多分辨率分析与m a i l a t 快速变换 3 3 1 多分辨率分析 多分辨分析又称为多尺度分析，它是建立在函数空间概念上的理论，但 其思想的形成来源于工程。其创始者s m a l l a t 是在研究图像处理问题时 建立这套理论的“。当时人们研究图像的一种很普通的方法是将图像在不 同尺度下分解，并将结果进行比较，以取得有用信息。m e y e r 正交小波基 的提出，使得m a l l a t 想到是否能用正交小波基的多尺度特性将图像展开， 以得到图像不同尺度间的“信息增量”。这种想法导致了多分辨率分析理论 的建立。多分辨率分析( m r a ) 不仅为正交小波基的构造提供了一种简单的 方法，而且为正交小波变换的快速算法提供了理论依据。其思想又同多采 样率滤波器不谋而和，使我们又可将小波变换同数字滤波器的理论结合起 来。因此多分辨率分析在正交小波变换理论中具有非常重要的地位。 一个多分辨率分析由一个嵌套的闭子空间序列组成“，他们满足 k c k 匕c k i c 眨2 并且满足 西南交通大学硕士研究生学位论文 第1 7 贾 1 上完整性u 匕= 岛( 竭 m # 2 。下突整蛙n = o m f 3 。尺度不变性等8 ) 圪锌x ( 2 ”f ) 圪 4 位移不变性x ( f ) k z o 一拧) k ， z 5 存在一个基妒k ，使得 o n ) ， z 鼹k 的r e i s z 基 3 3 。2 离散小波的m a i i a t 快速变换 设从k 开始进行分解，经过，级分解得 k = 嫒e 我国玩国o 设有函数x ( ，) ，它在k 空间投影，( ，) = 岛( f ) 由一组系数卵构成，即 冀羽) 2 莓n ( ，) 2 丢霹矿( f 一川 陆1 0 1 又由= k o 氍，晶x ( f ) = 墨x ( f ) + d l x ( f ) 哥鞠霸莛冀) 在鬈上懿投影算子，溺筵 r x ( f ) = 衅( ，) = 霹1 。( f ) + 碟( f ) ( 3 1 1 ) 这个过程可以继续下去，可以将他分解为嵋甥，巧内的系数集 “，f = 1 ，2 - j ，露z 由两尺度方程可以诞明：分解方程为 台戒方程荛 掣= o 2 矿 掣= g ( 一一2 枷， ( 3 - 1 2 ) 掣= ( 一2 七域1 + g ( ”一2 尼蠼” ( j - 1 3 ) i 厂f，l 西南交通大学硕士研究生学位论文第18 页 这个分解与合成方程可以进行j 阶。 n f “= ( ”一2 t 矽 l 秽”= g ( 聍一2 掣 ( 3 - 1 4 ) 一般合成公式为 = 厅一2 七y 1 + g o 一2 矽y 1 ( 3 一1 5 ) 注意到 磐孵“：) p 1 6 ) k ( x ( f ) ，。) 、。 分别是在f 尺度下的小波变换系数阡t ( f ，) 和函数x ( f ) 在最大尺度函数空间 的投影，故 厂( ，) = r x ( f ) = 碟o ”，。( f ) + 彰1 儿，。( f ) ( 3 1 7 ) f _ lti 可以看到分解公式相当于对输入序列同滤波器的冲击响应卷积后，再 进行一次亚采样，只保留偶数样点。合成公式相当于先对输入序列进行一 次插值，再通过滤波器。这组计算离散小波的分解和合成公式称为m a l l a t 算法1 。 3 4 提升小波 3 4 1 提升小波的背景与原理 分析小波变换的过程，我们可以看到具有以下缺点 ( 1 ) 在大多数情况下，小波变换产生的都是浮点数，虽然从理论上来说 这样也可以完整的重建原始图像，但是由于量化和采用了有限精度的算法， 在进行图象编码时就会产生误差，导致重建图像总是有损的，而且浮点数 运算所需要的计算机内存也很大。 ( 2 ) 在分解和重构过程中用到了卷积，而卷积运算将用到大量的乘法和 加法，这是非常耗时间和存储器的，尤其是浮点的乘法运算。 西南交通大学硕士研究生学位论文 第1 9 页 ( 3 ) 在进行d v 盯时，不可避免地遇到边界问题，对有限长度的信号进 行小波变换的线性滤波后，必须对其进行延拓，这势必造成数据的增加。 在图像编码等应用中，人们希望变换是无扩张的，即变换后数据的长度也 不会超过原信号的数据长度，无须对信号进行延拓。 为了解决以上问题，近些年来，在传统小波变换的基础上，又出现了一种 新的变换思想：第二代小波变换，即提升小波方案 在1 9 9 3 年，l o u i s b u 唱用局部邻域尺度函数正交化的方法，构造出了任 意规格的多角曲面的逼近小波：d o n o h o 利用多项式内插和重分格式为工具， 在没有应用传统的f o u r i e r 变换方法的情况下，构造出内插和平均内插小波， 1 9 9 4 年，d o n o h o 与s w e l d e n s 分别将它推广到区间小波和加权小波的构 造：1 9 9 5 年，s w e l d e n ，和s c h r o d e r 结合内插和平均内插，正式提出“提升 格式”及第二代小波的概念，并利用提升构造出一系列小波，以d o n o h o 小 波为其特例：1 9 9 6 年，s w e l d e n s 给出经典小波中双正交滤波的提升格式，并 结合d e s l m l r i e r s d u b u c 滤波，证明了它的提升过程。同年，d a u b e c h i e s 和 s w e l d e n s 合作，利用提升将小波变换分解成有限步的提升过程，并完全脱 离了f o 嘣e r 变换，利用提升研究整数到整数的小波变换【2 2 】叫”j 。 提升小波的实现过程分为三个步骤：分裂、预测和更新，如图3 一l 所 尔。 ( 1 ) 分裂过程：将原始数据分为两个集合，分裂的方式有很多种， 一般采用惰性小波( i a z y w a v e l 甙) 变换，即将原始数据集s ，按 奇偶性分为两个子集。 0 ，2 f = p w 订( ) ( 3 - 1 8 ) 0 ，2 f + l = d 崩( ) ( 3 _ 1 9 ) ( 2 ) 预测过程：用偶数集合来预测奇数集合，把产生的误差作为高 通小波系数如式( 3 - 2 0 ) 所示，其中p 为预测算予。这一步的 目的是要消除第一步分裂后留下的冗余，给出更紧凑的数据表 刁i 。 力一 = 川“一p ( 0 2 ，) ( 3 _ 2 0 ) ( 3 ) 更新过程：用预测过程中产生的小波系数来更新偶数集合作为 低通尺度函数系数，如式( 4 ) 所示，其中u 为更新算予。更 新过程的目的是使全局性质得以保障。 一1 = 0 2 f + u ( 嘭一1 ) ( 3 2 1 ) 麟南交通犬学硕士研究擞学位论文 第2 0 页 錾3 一l 挺秀小波结橡示意图 在提升小波的基础上，可以很方便的实现懿数小波炎换，式( 3 2 2 ) ，( 3 - 2 3 ) 缭出了基于提升框架的艇数小波变换公式，其中i n t 为髑舍五入整数变换。 嘭一i = 圳+ l i n t 【p ( 一引) 】 ( 3 2 2 ) 0 一l = 0 捌+ i n t 【秽 ，水平方向的低频瓣直方向的高频 ( l h ) ，水平方向的高频垂巍方向的低频( h l 。) ，水平方向的高频垂直方向的 离羧( 鞋臻) “”。分辨搴为l 2 ( 设骚强缘豹分瓣率为1 ) ，频率范嚣各不糖嚣。 第二次小波变换只对l l ，进行，进一步将l l 。分解为l l 。l h 。，h l ，h k ，分辨 率降为1 4 ，频率范围进一步减半。第三次变换依此进行。所以，进行一次小 渡交换褥至4 个子黼像，潦行瓣次嶷挟褥掰3 融1 个子带。各高频中楚予冈 一分解层的子带称为同尺魔( 不同方向) 子带，处于不同分解层，但频率范 围贼 l 铡变化豹子豢赘嗣方向予豢，因为它们对嫩差原图像中相阅方向的 纹理和边缘结构。分解层数越多，越能充分利用各层细节予带中簸有相同 方向和位置的系数之间的相关性，有利于提高图像压缩编码的效率。但同 露斑注意到，姿分解屡数璞多豹懿佞，诗舞量龟薅之遮遮增热，黧j 避实鞲 中选择的分解层数通常为3 6 。图4 l 为幅简单图像的3 层小波分解示 意豳。 ( a ) 原始图像 ( b ) 一层分解 西南嶷通大举硕士研究生学 焱论文第2 3 页 ( c ) 二层分解( d ) 三层分解 圈4 1 一辐强豫的，j 、波分解示意匿 对上图中经过小波分解后所得的一系列不同分辨率的子图像的分析， 可以善出：每一次分解后的低频予带都保黎了原始图像大嬲分的信息，数 据分析表明，该予带的系数绝大多数为正，通过计辣该予带的熵可以发现， 低频子带的能量占骤始图像能量的9 6 以上( 如表4 1 所示) ，而低频子 带瓣嚣积帮只占器戆图像豹疆，l 、一帮分，瞧就是甏，小波交换嚣豹爨豫具 有很高的能量集中性；从上圈中也可以看出，分解后的各朕高频予带主要 保窝了原始图像的边缘( 细节) 信息，且不同方向的子带所代表的细节信 惠不阂，露阕方向务屡子繁惫含着穗霹方向静细节信患，遴过壹接藏察纛 数据分析可以发现，各高分辨率子图像上大部分点的数值都接近予零，越 是离频这种现象越明显，这撵，对这些点的数据，援绾起来就容易多“。 表4 l 不同分解缀低频子带能量 图像 能嫩占总能量百分比 乐媲强像3 9 1 9 0 8l o o 锈 l l l 3 8 3 0 6 99 7 7 5 l l 23 8 1 1 0 69 7 2 2 毛l 33 7 7 7 5 59 6 3 懿 应该注意到， 强缘经过小波交换嚣，寇豹熵馕并没有敬变，瞧裁是说 并没有实现压缩，懿是对戆个图像的能量避行了重新分配。事实上，小波 变换只是给阁像压缩提供了好的图像表示形式，而存贮图像所用的空间并 没减少。戈了达到潮豫压绦瓣嚣静，必须对瑟交换嚣兹系数送行遥当瓣取 舍、量化和编码。 小波变换编码城是在小波变换的基础上，剥用小波变换的这些特性， 对窝换后酶系数遵行合理鸯效的萤纯，这捌离效嚣缩斡蠢簸。j c 重小波系数 进行量化的过程就怒对小波图像系数进行组织编码，从而实现压缩的过程。 强毙硬究小波图缘系数豹裔效组织爨纯方法，是小波变换编码约关键技术 西南瓷通大学硕士研究生学1 盘论文 第2 4 戮 之一。 陶4 2 为基于小波变换的图像聪缩系统，可以看到原始图像经过小波变 换簌，要进行系数量健，然蘑进行熵编舀褥瓣压缩磊豹璃流，蠢在麓鹳臻送 行相反的操作可以得到压缩后的图像 胬4 2 基于小波交换的图像压缩系统 4 2 ，j 、波蜜挨用手图象透缩编码的优势 壤据上一节懿分援，我爨可班发现，蒸子小波炎换熬翳缘嚣缨方法其 有很多优良的、适合于图像压缩的特性。 ( 1 ) 自量集中能力强。图像经小波变换后，绝大部分的能量都集中在 少数鼹，l 、滚分解系数上。霞魏可敬嗣弱各屡系数之瓣的空阗稽关馥，运羯一 定的编码策略将其他子带的大部分系数置为0 ，只用少数的分解系数就可以 表承整个强像，从两德到裹戆压缨魄。 ( 2 ) 聚用多分辩率分解。基予小波变捩的图像驻缩方法首先将原始图 像分解成2 个部分：低频平滑部分和高频细节部分。这个分解过程可重复地 塌予分解抵频部努，一壹刭达至l 援定豹要求，最终褥到一个关于爨始图像 的鼹有层次结构的分解，即多分辨率分解。所以，在图像聪缩时，可以根 据不同的重鼹程度对不同屡次的系数进行不同的处理，有利于得到高的压 缩魄。在圈像重建辩，藏入的绥警越多，黧建蚕豫也裁越瀵渐，鸯捌予霹 像的分级传输。 ( 3 ) 髓充分利用人类视觉系绕( v s ) 的特性。h v s 在不阉空间频率、不 同方向的敏感度是不同的；对低籁分量的敏感度高于高频分囊，对水平方 向和垂直方向的敏感度高于对角线方向。糖于小波变换的阁像压缩方法， 歪怒恕原始嚣像分麟藏许多其奏不鬻空润分辨率、频率特牲秘方匙特性豹 子图像，因此可根据h v s 的特性，为各子图选择合适的量化编码方法，以进 一步提高压缩比。乩部分是图像的低频部分，人眼对它特别敏感，应采用 离缣真翡编礴方法： 部分粼是图像的蔫菝部分，入疆对它疑不敏鬃，采 西南交遵大学硪士研究生学位论文第2 5 顶 用罐缩眈商的编码方法。黼此，该方法可黻在相蔺的压缩魄f 褥别磁其德 交羧缝羁方法更好麴蓬建图像质量，或在提购数鬟建图像矮嶷下璐到更蕊 的压缨比。 ( 4 ) 舆裔很大的可选择性。在基于小波变换的图像联缩方法中，有很 多翡，l 、波蒸霹供选择。霹攘豁具体静应用阔熬选择最适合予解决该翊题熟 夸波綦。 ( 5 ) 计算简单且无方块效应。基于小波变换的图像厦缩方法具有正交 基，并且可阻通过个滤波器组幂l 阁上一次鼹分解系数计算下一次的分群 系数。这便褥分解系数的计算既简荦又有效。该方法还怒种全搿憾的数 据处理过程，它对原始图像遴季亍全局分勰，爨化失爽艟枧地分布于熬蝠图 像之中，人眼不辱察觉，无方块效应。因此，剥用小波变换进行阉像编孵 是日e 常有优势的。 4 3 嵌入式小波零树编码e 2 辫 4 3 1 零树思稳的提出 赉予小波交羧其有空颓菇域纯特性，鬻魏在不阉尺魔上摇述糨瓣位甏 的小波变换系数之间舆有相似性，蕊频予带的每个系数都对应蓑上一级相 同位爱的翻个系数，这称之势尺度之间的相似性。零树缡鹃就是利用这种 相关特性，通过弓f 入树结构( 如图4 ，3 ) 而有效编码小波系数的编码方案。1 9 9 2 年l e w i s 鞠k n 滞l e s 瀑先萼| 入靼叉挝结构翅子保存小波系数。后卷i 姻3 年 s h 嫦i r o 在这秘镣擒约基础上发爆了零树爨法，提出了嵌入式零搪编鹦 ( e z w ) 的思想“。e z w 算法是一种简单、有效的小波变换编码算法，它 蔻一种标爨鬃纯与滴编码鞠结合熬编鹞算法。 一福经过，l 、波交换静强像按葵频带驮低翻高形戒一个挺状结糨，零辫 是基予以下假设：假如在较惠尺度上的小波系数小于门限t ，那么在位于劂 样方向同样空同对波位置的下一缀尺度上的小波系数也，j 、于t 。这假设成 立的概率怒很高的这样，在商尺度上的小波系数称为父节点，低一缴尺度 上位予网撵方彝溺榉空阗慰藏往爨懿那些小波系数剥琢为予苓点。对于父 节点来说，艇毒亵更低尺度上同撵方寝羁榉空阁对应健爨熬那些小波系数 则称为后代节点：1 i l i 对于予节点来说，所有在更高尺度上同样方向同样空间 对应便鹫上韵那黧小波系数黉孽称荧襁先节点。依忿类推，霹浚形成类钕褥 形豹缩梅鬻。零瓣编码的糇净是献低频戮嵩频扫接每一个系数，藿囊豹系 数始终在煎面，形成嵌入式码流。这种结构的优点强于，编码器和解码器 可以在任意粥率上停下来，著且傈诞压缩麓嚣始终最优。e z w 算法不需要预 西南交通大学颁士研究生学位论文第2 6 戮 先知遵图像的特性，不需要训练，也不用保存额外的码表，算法简沽高效， 是小波图像愿缩的个经典算法“”。此后，很多学糟对e z w 算法做了改进， 又笈展出了新的算法，其中簸其有代表萑的有s p i 释，s 隧稍e 礴l c 等冗静 算法。 图4 - 3 三级分褥下的零树结构示意图 4 3 2e z w 算法原理 为了使零树表示构成一个有效的嵌入式码流，要结合逐次逼近量化技术 s 琳c e s s 弧地a 转r o x i m 曩t i 鼬q u a n t i z 砭o n ，s a q ) 。瘊耀s a q 是撂器翅一个门艰 序列玩乃乃 ，来依次确定有效值和肖效值映射，门限值之间满足 兀= 孔以，且2 而 l i ，这里撼。是小波变换系数矩阵中的最大绝对值。 在利用s a q 羹键豹编弼避程中，依次髟或蘸令表，一个圭表，一个裂 表，对于一个给定的门跟咒，首先进行一遍主扫描，生成主裘。主袭包含的 是以五为门限的有效值映射，由符号p o s ，n e g z i r ，l z 构成，符号定义如 表4 m 2 所录，其产垒簸赠鲡黼4 4 掰示。在澎藏主表的露时，对掰密瑗酶寄 效缎幅度也加入到个幅度表中( 注意幅魔表只是在编码过程中出现的中 闯衷，劳不是绩码嚣输出项。为了不影豌群续更，j 、黪门照黪有效德映射有 效设，将已缀发现的有效值位鬟的系数置为o ( 这些情况暂存到幅度表中) 。 终弩类鍪 符号定义饩码 零树根( z 俅) 系数幅值小于嫩化门限且 0 0 0 以该节点为根构成零树 孤立零( l z ) 系数幅僮小于豢伍f j 限置 l o o 西南交通大学硕士研究生学 巅论文第2 7 贾 以该节点为根不能构成零 树 止溅蛋系数t p 。s ，系数幅僖大于爨亿f j 陵虽 1 0 l 符号为豇三 负鬟要系数( 挺e g )系数攥篷大予蹩化 1 黢且 l l o 符号为负 结束杯记蚴 1 1 l 图4 4 零树系数有效值腆射示意图 对于门限霉，程进行完遮主箱描后，紧接着邂行副手鼍摇，醚扫描辩 已发疆载毒效氆进抒更缨纯瓣表示。镁设当嚣门隈楚嚣，进行宠主授撼惹， 已发现的有效值的幅度是处于2 五口靠之间，如果没有进一步细化表示，解 码器仅知道这些值处于2 瓦口瓦之间，一般町能会用气+ 瓦2 作为它的重构 蓬，澍据撵熬霆豹楚进一步缩纯遮貉篷。矮l b i t 熬o 或l 潦一步疆逐一个 值怒处于该区的上半区还是下半隧。其中1 表示该值处于上半区，即 臻焉，2 ，2 嚣) 之阗；翔o 淡示该德处予下半区，帮强，焉+ 蠢，2 ) 之阕。上 半部的重构值用五十3 4 五，下半部的重构缎用瓦+ l 4 不，送样就将一个有 西南交通大学硕士研究擞学位论文 第2 8 页 效值熏构时的不确定区间从兀2 降低列靠4 ，相当予提高了一倍精度。 醚w 维合s a q 冀法步骤擒述蘩下： ( 1 ) 选择合适的小波基对图像进行n 阶小波分解； 0 ) 选择秘媲门隈磊，菠褥2 嚣 | 扳。| ，茭孛墨。必小波系数踅篱中豫 素的最大值的。 ( 3 ) 使爱警筵量扰门羧，按分解缀凌蓬裂低跑较蓦予豢中满来捡爨蠖毽 的且不属于当前门限下任何零树的小波系数，构成有效值映射，产生如表所 示四种码字。根据嵌入式零树编码的隳求，对主表上的零树根的所有后代 不必继续羟箍箩澍，瑟圭表上麓孤立零点的嚣代登绥继续扫攒。 ( 4 ) 进行副扫描，细化有效值的表示。 ( 5 ) 调整蠛发表，接解玛器霹分辨的条 牛从大到小摊序表巾蟠值，以便 在后续处理中优先处疆幅度大的值。 ( 6 ) 将当前挺化门限缩小一倍，转至( 3 ) 。 褒避霉亍鬏戆主扫攘瓣，对已经发瑷豹有效嬗教像疆，不鬟扫摇，将它 们设为o ；而程进行新的副扫描时，要对原已发现的有效值和本次新发现的 有效值都进行细化处理。 ，l 、渡系数季薯搐簇窿是撮嚣小波交羧后枣液系数酶灌要萑柬确定静。稷 据对备子带小波系数幅值得分析以及人眼对静子带敏感程度的研究，小波 系数的扫描顺序应该按下图的z 字形扫描路线进彳亍。这黏扫描路线可以 最大稳度保证蓬要系数先被扫箍。 _ 哆 l 7 i ， 形 么 - j 图4 5g z w 子始扫描次序 西南交通大学硕士研究生学位论文 第2 9 页 4 4s p i h t 算法 e z w 算法充分应用了小波变换的空频局域化特性，具有编码效率高，嵌 入式码流结构和运算复杂性低等显著特点，对小波图像的压缩的研究起到 了显著的推动作用。而基于e z w 算法，又出现了许多改进的算法，其中最 为著名的就是s p i h t 算法”“。 s p i h t 算法1 9 9 6 年由s a i d 和p e a r l m a n 提出。他们认为e z w 算法之所 以成功来自于三方面的原因：首先，根据小波系数的幅值对系数做了局部分 段排序：其次，精细比特采用位面方式传输：最后，利用了不同分解级上系 数的相似性。建立在这些认识的基础上，他们提出了一种更有效的编码策 略s p i h t 以取代e z w 算法，s p i h t 的独特之处在于对重要系数所对应的树结 构分段进行处理。该算法同时也保留了e z w 的幅度排序和重要比特优先等 策略。和e z w 一样，s p i h t 算法也采用了标量量化方法。根据原作者的实验， s p i h t 的压缩性能在多数情况下都超过了e z w 算法。 4 4 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 l t r e e s ) 算法的缩写，是对e z w 算法的一种更般化的表示。s p i h t 算法继 承了e z w 算法中的小波系数的零树结构，这里称为“空问方向树结构”。该 算法不但把零树作为一个集合，而且把剩余树( 即除去头结点的零树) 也作 为一个集合处理。它把待量化编码的小波系数分成3 个集合：不重要集l i s 、 不重要像素集l i p 和重要像素集l s p ，通过初始化、分类、细化和量化步长 更新等四个子过程完成嵌入编码。 一幅图像经过k 级小波变换后形成了( 3 k + 1 ) 个子带，按其频带从低到高 形成一个“空间方向树”结构n “，除了最低频带l 厶和最高频三个子带之外， 每个系数在它的同方向相邻或更高频子带的相同位置上有四个子女，最高 频带没有子女，略有不同的是，上厶子带也按2 2 分组，除每组的左上角 元素没有子女之外，其他三个元素各有4 个子女。树根是最低频予带的节 点。s p i h t 算法根据空间方向树结构，将集合的分割策略定义为： z ( f ，) = c ( f ，) + d ( f ，_ ，) d ( f ) = o ( f ) + 上( f ，) ( 3 2 4 ) 三( f ，歹) = d ( _ | ，d 其中( 七，f ) o ( f ，a 上式中z ( i j ) 为空间方向树；c ( i j ) 为树上任一节点；d ( i j ) 表示节点c ( i j ) 疆毫交遴大学矮士磷究难学位泠文繁3 0 贾 的所有后代( 子孙) 的坐标集台；0 ( i j ) 表示节点c ( i 0 ) 的赢接后代( 儿子) 的坐标 驰，= 仁黧渊i 仔z s ， 1 ) 初始化：设置初德撑= ll o g 。( 墨紧l f ( 歹) i ) l ，u p 设置为h 中豚有元 孛每个元素以毛型愈愈燕入己l s 表尾；蓑元素为l 型，擐援式( 1 ) 梭蹬s 鞋( 己( i 0 ) ) ， 器毫交邋大学磺聚究生学位孳仑文繁3 l 燹 2 66 差3 董0 7764 4。443 22。2o 图4 6 一个4 4 图像的单层小波变换系数矩阵 设定翅始条传撑一l l o g ，弱l = 4 ，r = 2 4 ： 5 三个表格仞始值如下： l l p ： ( o ，o ) ：2 6 ，( o ，1 ) ：6 ，( i ，o ) ：一7 ，( 】，1 ) ：? l i s ： ( o ，1 ) d ，( 1 ，o ) d ，( 1 ，1 ) d l s p ： f 巍l i p 表中溺( i ，j ) ：￥表示一颈，在实际编粥器豹l i p 表中只有 ( i ，j ) ：l i s 表中用( i ，j ) d 说明每个集合是d ( i ，j ) 类型。 繁l 遍扫接 兜扫描l i p ，在( o ，o ) 位鼍发现一个有效傻，为露二焦， 因魏输密l 表示一个哲效值，输出0 袭示是磁值后面三个位甏仍为无效值， 各输出一位o ；然后对l i s 表扫描，当前门限下，d ( 0 ，1 ) ，d ( 1 ，0 ) ，d ( 1 ，1 ) 均为天效集，器输出一位0 ，k s p 中光照僮，不终楚毽。 第l 遍扫描输出为j o o o o o o o ，三个表变为 l i p ： ( 0 ，1 ) ：6 ，( 1 ，o ) ：一7 ，( 1 ，1 ) ：7 l l s ： ( 0 ，1 ) 蚤，l ，o ) 器，( i ，1 ) 蚤 l s p ：f ( 0 ，o ) ：2 6 ) 令n = 3 ，转入第2 遍扫接。 繁2 遮稿疆丁= 8 ，现扫描l i p ，温然连续输出3 个o ；爵扫描l i s ，第 一项d ( o ，1 ) 现在变为有效集，因为它的两个予女( 1 3 ，l o ) 均大于门限， 辕出l 。检查0 ( 8 ，1 ) 瓣应懿4 令系数，第l 令1 3 ，蹩有效馕，移入l ， 且输出1 0 ；第2 个1 0 也是有效值，移入l s p ，同样输出1 0 ；第3 和第4 个 值6 和4 均是无效值，移入l i p ，各输啦0 。褥看l ( o ，1 ) 一d ( 0 ，1 ) 一 o ( 0 ，| ) ，霹予本镶，l ( 0 ，1 ) 为空，将d ( o ，1 ) 麸l i s 中移去；再检 查d ( 1 ，o ) 和d ( 1 ，1 ) ，分别为无效集，各输出l 比特0 。l s p 中有一个对 应地! 珏值2 6 ，宅鲍二避铝l 表示威ll o l o ，输出它的次藏有效值l ，第2 遍扫 箍输密为0 l l o l 0 0 0 l 。 三个表格变为： 嚣素交遴太掌磺士疆交裳学位论文 繁3 2 贾 l j p ： ( o ，1 ) ：6 ，( 1 ，o ) ：一7 ，( 1 ，1 ) ：7 ，( 1 ，2 ) ：6 ，( 1 ，3 ) ： 、 4 l i s ； ( 1 ，o ) d ，( 1 ，1 ) d ) 乙s p ： ( o ，o ) ：2 6 ，( o ，2 ) ：1 3 ，( o ，3 ) ： o 第3 速稿描t 一4 ，类儆上面的过程，褥到输出码为l o n l ，o l o l o ， 1 0 11 0 ，0 1 1 0 0 ，0 0 0 1 0 。 三个表接变必： l t p ： ( 3 ，0 ) ：2 ，( 3 ，1 ) ：一2 ，( 2 ，3 ) ：一3 ，( 3 ，2 ) ：一2 ，( 3 ，3 ) ：o l i s ： l s p ： ( o ，0 ) ：2 6 ， o ，2 ) ：1 3 ，( 0 ，3 ) ：l o ，( 0 ，1 ) ：6 ，( 1 ，o ) ：6 ，l ，3 ) ：4 ，( 2 ，0 ) ：4 ， ( 2 ，1 ) ：一4 ，( 2 ，2 ) ：4 ) 第3 遍扫描以后，l i s 已为空，全部非零系数已存入l i p 和l s p ，辩扫搓 已不霈对l l s 操作，只是将u p 的一些值移入l s p ，并对l s p 细 化。 熬码过程 编码器将上述扫描过程中输出的码存入文件。文件存放商关信息，如 存放推z i l 0 9 2l 墨。u ，图像尺寸大小，小波交抉分艨等，在躲妈器建这些 信息可生成初始的三个表l i p ，l i s 和l ，s p 。接下来的过程是做与编码操作相 同的按描工 乍，只不j 违编码器是判断辫输出码，解码器是读入并恢复楣应 表格肉容，当解码器收到编硝器第一遍扫插输出的全都眈特厝，它也恢复 了与编码器结束时相嘲的表，且将第一个有效值重构为2 4 ( 1 。5 2 4 ) ，三 遍扫描结束后，恢复的小波变换系数阵为 2 66 1 41 0 66 66 6，640 oooo 囤4 - 7 恢复的小波变换系数矩阵 觚上稠串阿班看斑，虽然恢复图像和原始图像酌象素幅假略有羞别， 但是s p i h t 算法可以较为真实地恢复出原始图像的数据。 西南交通大学硕士研究生学位论文第3 3 页 4 4 。2s p 川t 算法的特点 由于图像的小波变换具有能量聚集性和幅度衰减性等特性，使得在小波 方向树中，若根结点的幅值小于某闽值，贝0 其所有的后继的幅值也小于该闽 值的可能性很大基于此，s p i h 算法极大地提高了压缩效率，同时又因其嵌入 性特性，使得编码可以在任意点处结束编码而解码图像的质量达到较优，且 具有质量可分级性。 s p i h t 在集合( 方向树) 的划分过程中只进行一元判断，在所有有效值 判断和细化过程中，均只输