（计算机软件与理论专业论文）基于局部小波变换的分形图像压缩算法研究.pdf

摘要 y 7 3 8 3 8 6 分形理论( f r a c t mt h e o r y ) 是图像压缩中使用的一种新理论，它以压缩比高 和解码速度快等优点，受到广泛的重视并得到了充分的发展。本文将分形理论和小 波变换结合起来，提出一种新的基于局部小波变换的分形图像压缩算法。实验表明， 该算法在保证图像质量的前提下，可大大缩短编码时间，提高压缩比。 本文首先系统地介绍了图像压缩的基本原理和分形图像编码的数学基础，对具 有开创性的j a c q u i n 分形图像编码方案进行了分析和评价。在对小波理论和分形理论 的研究基础上，提出了二者结合的可能性及互补优势。 在此基础上提出了新的图像压缩算法一l w f c ( f r a c t a lc o d i n gb a s e dl o c a l w a v e l e t ) 算法。该算法不同于一般的在小波域内进行分形编码的方法，雨是根据小 波变换后能量集中于低频的特性，在传统的j a q u i n 分形编码方案的基础上引入局部 小波变换，以低频子图代替原图进行值块、域块阔匹配计算以加快值块和匹配的域 块之间的搜索过程，从而提高编码速度。块匹配搜索时采用了邻域搜索法，仅对定 义域低频信息库中的部分决匹配，从而大大减少了计算量。此外，仅采用4 种仿射变 换，使得重建图像质量基本上能够达到采用8 种仿射变换的效果，同时却减少了匹配 次数，缩短了编码时间。最后，采用新h u f f m a n 无损压缩算法对所得到的分形参数实 现无损压缩，从面进一步提高了压缩比。 最后，本文通过仿真实验，证明了l w f c 算法的高效性。 关键词：分形理论；小波变换；图像压缩；迭代函数系统 a b s t r a c t f r a c t a l t h e o r y i sak i n do fn e wt h e o r yi ni m a g ec o m p r e s s i o n i th a s b e e n a c k n o w l e d g e da n dd e v e l o p e dw e l l b e c a u s eo fi t s h i g hc o m p r e s s i o nr a t i o na n df a s t d e c o d i n g b a s e d o nf r a c t a lt h e o r ya n dw a v e l e tt r a n s f o r m ，t h ep a p e rp r o p o s e san e w f r a c t a l c o d i n ga l g o r i t h mb a s e do nw a v e l e tt r a n s f o r m ，w h i c hd i f f e r sf r o mt h et r a d i t i o n a lm e t h o d o ff r a c t a lc o d i n gi nt h ew a v e l e td o m a i n t h ee x p e r i m e n t ss h o wt h ea l g o r i t h ma s s u r e s i m a g eq u a l i t y ，m a k e st h ec o d i n gs p e e d f a s t e ra n d i m p r o v e sc o m p r e s s i o n r a t i o n t h ep a p e rd i s c u s s e st h ep r i n c i p l eo fi m a g ec o m p r e s s i o na n dm a t h e m a t i c sb a s eo f f r a c t a l i m a g ec o d i n g a n d t h e p a p e ra n a l y s e si m p o r t a n t f r a c t a l i m a g ec o m p r e s s i o n m e t h o d ，w h i c hi sp r o p o s e de a r l i e s tb yj a c q u i n t h ei m p o s s i b i l i t y a n da d v a n t a g eo f m e r g e n c eo ft h et w om e t h o d s i sd i s c u s s e db a s e do nt h ea n a l y s i so fw a v e l e ti m a g e c o m p r e s s i o n a n df r a c t a li m a g e c o m p r e s s i o n t h ep a p e rp u t sf o r w a r dan e wf r a c t a lc o d i n ga l g o r i t h mb a s e do nl o c a lw a v e l e tw h i c h h a sb e e nn a m e da sl w f c a l g o r i t h m i td i f f e r sf r o mt h et r a d i t i o n a lm e t h o do f f r a c t a l c o d i n gi nt h ew a v e l e td o m a i n t h ea l g o r i t h mi n t r o d u c e sp a r tw a v e l e tt r a n s f o r m a t i o no n t h eb a s i so f j a c q u i n sf r a c t a lc o d i n ga l g o r i t h ma n dr e p l a c e st h eo r i g i n a li m a g ew i t hi t s l o w - f r e q u e n c yi m a g e t oc o m p u t et h em a t c h i n gp r o c e s sb e t w e e nd o m a i n b l o c k sa n d r a n g e b l o c k s ，w h i c hs p e e d st h es e a r c h i n gp r o c e s sb e t w e e nt h er a n g eb l o c ka n di t sm a t c h i n g d o m a i nb l o c ka n dq u i c k e n st h ep r o c e s so fe n c o d i n g n e i g h b o r h o o ds e a r c hm e t h o di s a d a p t e dw h i c h l i m i t sm a t c h i n gd o m a i nb l o c k si np a r to fl o w - f r e q u e n c yd o m a i n b a s e sa n d r e d u c e sc o m p u t et i m e sg r e a t l y i na d d i t i o n ，t h ec o d i n gt i m eh a sb e e ns h o r t e db e c a u s ef o u r k i n d so fa f f i n et r a n s f o r mr e p l a c eo r i g i n a le i g h tk i n d s i nt h ee n d ，n e wh u f f m a na l g o r i t h m r e a l i z e sl o s s l e s sc o m p r e s s i o no ff r a c t a lc o d e sw h i c hb r i n g ss a t i s f i e dc o m p r e s s i o n r a t i o n i naw o r d ，t h el w f ci sp r o v e da ne f f e c t i v ei m a g ec o d i n ga l g o r i t h mf r o m t h er e s u l t s o f t h ee x p e r i m e n t s k e y w o r d s ：f r a c t a lt h e o r y ；w a v e l e tt r a n s f o r m ；i m a g ec o m p r e s s i o n ；i t e r a t e df u n c t i o n s y s t e m 第一章前言 第一章前言 随着互联网络的兴旺发达，人类社会迎来了一个崭新的信息时代。以计算机和 通讯技术为代表的数字化技术，不断改变着人类的生活方式。 信息作为这一时代的标志，包含的内容有文字、声音、图像等。其中，图像信 息比其他媒体更加直观、确切和生动。据统计，人类获取信息的8 0 来自眼睛，1 5 来自于声音。这说明图像是人们生活中信息交流最主要的载体。然而，图像信息的 处理需要较大的存储容量和较宽的传输信道，造成系统资源紧张。尤其是在需要实 现大规模图像数据库或者传输高分辨率图像时，这一问题更加突出。即使以现在的 技术，仍然难以满足原始数字图像存储和传输的需要。因此，数据压缩技术就成了 图像处理中的一个迫切需要解决的技术。近3 0 年来，图像压缩技术的研究非常活跃， 在商业上也取得巨大成功。 1 1 图像压缩简介 图像压缩编码技术应用十分广泛，针对不同的应用领域，现已经研究出许多种 压缩编码方法。虽然它们各自基于不同的编码思想，但是基本压缩过程大致可以概 括如图1 1 所示： 图l i1 压缩过程 预处理：原始图像经过数据预处理，改变原始数据的特性，得到有利于压缩编 码的数据。 量化器：对预处理后的“更高精度”的数据量化为“更低精度”的数据，从而 得到更少的数据量。量化有两种方式：标量量化，对数据进行逐个的量化；矢量量 化，对一个数据块进行量化。 熵编码器：为量化器输出端的每个符号分配一个码字或二进制比特流。最理想 的情况是熵编码器输出码流的平均码长等于量化后数据的信息熵。此时，熵编码器 达到了最高的压缩比， 这三个步骤之间是相互联系、相互制约，共同实现数据量的压缩这一目的的。 数据预处理阶段在图像压缩中是极其重要的，这一步即是压缩的建模阶段。对有些 青岛大学硕士学位论文 编码方式，预处理后数据量可能并没有减少，甚至因动态范围的加大而使总数据量 略有增加，但它改变了原始数据的特征，使后两步发挥作用，实现整个过程的高效 压缩。还有一些编码方式，预处理后得到远远小于原始图像的数据量，即第一步已 实现了很大的压缩，后面两步则是做进一步的压缩。总之，在图像压缩的过程中要 把这三者联系起来共同去实现数据的最终压缩。 1 2 图像压缩的依据 图像压缩技术是依据以下两方面开展的： 一、图像的数据冗余。图像本身存在大量的冗余，并且这种冗余在数据编解码 后可以无失真地恢复。信息冗余有许多种，如空间冗余，时间冗余，结构冗余，知 识冗余，视觉冗余等，数据压缩实质上是减少这些冗余量。 从信息论的观点看，图像被视为“信源”。描述信源的数据可分为信息量( 信源 熵) 和信息冗余量两部分。减少信息的冗余量，可以使信源的容量减少，而不影响其 信息量。从数学上讲，图像可看作多维函数，压缩描述这个函数的数据量实质是减 少其相关性。 二、人类的视觉特性较弱。由于人的观察能力有限，因此在图像变化不被觉察 的条件下，适当减少量化信号的灰度级，以一定的客观失真换取数据压缩是可能的。 人眼对图像的细节分辨率、运动分辨率和对比度分辨率的感觉都有一定界限，对图 像处理时引入的失真不易察觉。因此，可在满足图像质量要求的前提下，减少信号 的精度，实现数据压缩。 总之，为适应当前对图像压缩技术的需求，提出商效的图像压缩算法并将其应 用推广，成为目前图像处理研究领域中一个重要的课题。 1 3 图像压缩的发展历程 图像编码理论的研究起源于上个世纪4 0 年代末，直到7 0 年代后，随着大规模 集成电路和计算机科学的迅速发展，各种图像的压缩编码技术和传输技术才得以发 展和成熟。 早在1 9 4 8 年，o l i v e r 就提出了电视信号的p c m ( p u l s ec o d em o d u l a t i o n ，简写为 p c m1 的编码理论。1 9 5 2 年，o l i v e r 、k r e t z m e r 、h a r r i s o n 将线性预测用于预测编码。 1 9 5 8 年，g r a h a m 1 l 首次用计算机模拟试验的方法，研究静止图像差值预测d p c m fd 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 ) 编码法，获得了3 - 4 b p p 的图像质量的良好效 果。1 9 6 6 年，o n e a l 2 1 对三种典型静止图像做了系统研究，为预测编码法奠定了理 论基础。 第一章前言 6 0 年代末到7 0 年代初，出现了图像的变换编码。最初的概念是建立在f o u r i e r 变换、h a d a m a d 变换、k a r h u n e n l o e v e ( k l 变换) 以及余弦变换的基础上。此后其 他图像变换编码方法才发展起来。1 9 6 9 年在美国召开的第一届图像编码会议标志着 图像编码作为一门独立的学科诞生了。 8 0 年代，特别是1 9 8 0 年l b g 算法的提出，使矢量量化( v e c t o rq u a n t i z a t i o n ，简 称v q ) 的研究从理论走向实用，矢量量化在图像编码中的应用从此得到迅速发展。 g e r s h o 、b a k e r 、m u r a l k a m i 等许多学者对v q 进行了研究，出现了一系列矢量量化方 案，使v q 在当时成为新的研究热点。 8 0 年代末到9 0 年代初，自适应离散余弦变换( a d a p t i v e d i s c r e t e c o s i n e t r a n s f o r m ， 简称a d c t ) 编码技术已趋成熟，先后建立了三个国际标准，即电视电话会议电视 的h 2 6 1 建议、静止图像的j p e g 建议标准和活动图像的m p e g 建议的国际标准。其 中a d c t 技术以其综合的优越性成为首选技术标准。此外，自8 0 年代末期以来，开 始了新一代了图像编码方法的研究，如神经网络法、分形几何法、小波变换法等。 其中，小波变换编码和分形编码不仅是现在的研究热点，而且已经取得了一定的 成绩。能否突破目前国际标准，是图像压缩编码领域正在研究和关注的问题。 1 4 图像压缩方法分类 图像压缩的分类，根据不同的划分方法，可以有很多种。目前，多数学者认同 的分类方法，是根据压缩后的图像能恢复成原始图像的程度，分为无损压缩和有损 压缩，这样的分类法似更能说明他们的本质区别。 无损压缩也称可逆压缩，经过压缩的图像能够完全恢复为原来的图像数据，如 h u f f m a n 编码、算术编码等，但其压缩比很低，仅为2 倍左右。从信息论观点来看， 图像作为一个信源，描述信源的数据是信息量( 信源熵) 和信息冗余量之和。无损 压缩实质上是减少信息冗余量保留信源熵，所以也叫熵编码。 其中，由n 个符号组成的符号集 一，h 构成的离散信源的所有符号的平均 自信息量为 n h ( x ) = 一p l 0 9 2 p k 1 一( 1 ) k = l 这个平均自信息量h ( x ) 也称为信源的熵( e n t r o p y ) 。 有损压缩，也称不可逆压缩，信息论中叫熵压缩，它允许重建后的图像与原图 像有一定的误差，只要人眼感觉不到这种差异，或者图像中有用的信息仍能被准确 有效的识别。其中最为重要的一类方法是变换编码，利用变换( 一般是正交变换) 的方法尽可能去掉原始图像象素值之间的统计相关性并实现能量集中( 图像块中的 青岛大学硕士学位论文 能量集中到少量的变换系数) ，然后对变换系数量化并结合熵编码，可获得更大的压 缩比。 此外，还有混合编码，根据一定的规则将多种编码结合在一起，发挥各自的优 势以达到最佳压缩效果。如小波变换和其他压缩方法的结合，已经取得了很好的压 缩效果：静止图像压缩标准j p e g 就是其中成功的一例。 按照上述标准静止图像压缩算法分类如图1 2 所示。 静止图像压缩算法 无损压缩有损压缩 统计编码ll 预测编码| | 量化 | i 变换编码1i 混合编码 瓣 标 量 量 侄 矢 量 量 化 k l 变换 d c t 变换 子带编码 图1 2 静止图像压缩算法分类 1 5 图像压缩方法性能评价 j p e g 标准 小波 分形 在图像压缩领域中，如何评估一个压缩算法的优劣一直是人们关注的焦点，但 还没有统一的评估标准。如今人们已经广泛接受的三个重要评估指标是：压缩比、 图像质量和处理时间。在最短的处理时间里，得到大压缩比的清晰重建图像，这就 是一个好的压缩算法。 1 5 1 压缩比 压缩比指原始图像总数据量与压缩后图像总数据量的比值。另外，也常用比特率 即传输或存储一个像素平均所需要的比特数来表示压缩程度。可见，评价指标压缩 比( 或者比特率) 是评价压缩算法压缩程度的直接体现。 第一章前言 1 5 2 图像质量 现在常用的对压缩后的图像质量给予评价的准则有两种：一是客观准则，一是主 观准则。 1 主观准则 主观准则是由观察者依靠自己的感觉对经过压缩处理之后的重建图像进行质量 评价。通常是选择一组评价者给重建图像打分，然后按照一定规则对这些主观打分 找到一个期望值。虽然这种方法有些主观，不同的观察者会得到不同的结论。但是 主观方法是最可靠的，因为图像最终的接受者通常是人的视觉。 2 客观准则 客观准则是对压缩还原后的图像与原始图像的误差进行定量计算，一般是对整个 图像或图像中一个指定的区域进行某种平均计算，以得到均方误差。目前普遍采用 基于最小均方误差准则的峰值信噪比p s n r 作为衡量解压缩图像质量的指标。客观标 准虽然意义明确，计算简单，但是并没有考虑人类的视觉感知特性。所以，评价一 个压缩算法的优劣，不仅需要客观准则，而且要辅助主观准则两个方面。 设原始图像为f 口( f ，) ，1 f m ，1 j n ) l f ，相应的解压缩后的图像为 盎( f ，_ ，) ，ls f m ，1 ，s n ) ，用p s n r 指标评价： 均方误差m s e = 嘉善扣“( f ，朋2 l _ ( 2 ) 设口= 2 。一1 ，k 是表示一个像素点用的二进制位数，则 峰值信噪比p s n r = l o l g 篆 卜( 3 ) 在许多应用中，常取k = 8 ( 灰度图像) ，所以在一些文献中，直接将口。2 2 5 5 代 入到上式。 很明显，以上评价完全取决于原始图像和重构图像上每个像素灰度值的误差， 虽然有时信噪比不能完全反映人的视觉特性，但毕竟在主观感觉上也有一定的参考 价值。实际上，常用的指标为p s n r 超过3 0 d b ( 分贝) 时，人的主观感觉很难找出差 异。 15 3 处理时间 处理时间包括编码时间和解码时间。显然，一个优秀的图像压缩算法需要在较短 青岛大学硕士学位论文 的时间内完成图像编码过程和解码过程。 除上述指标外，还有实现的难易程度、占有内存大小等。一个好的压缩方法可能 不是以上各个指标都优于其他方法，但他应该根据实际需要取得最优的折中。 1 6 本文的主要工作 本文主要研究小波和分形理论在图像压缩中的应用，具体内容共分为五章。 第一章首先介绍了图像压缩的基本概念和压缩依据，然后对图像压缩技术的发 展历程作了综述，并对目前常用的图像压缩方法进行了分类。另外，重点介绍了评 价图像压缩方法性能的指标，最后简述了各章节的内容安排。 第二章介绍了分形理论和小波变换的数学基础及其应用于图像编码的特点，为 后续章节奠定了理论基础。 第三章对具有开创性的j a c q u i n 分形图像编码方案进行了分析和评价，并在此基 础上充分利用小波变换的特点，引入局部小波变换以加快值域块和定义域块的搜索 过程，提出了本文的基于局部小波变换的分形图像编码模型一l w f c 模型。 第四章基于局部小波变换的分形图像编码l w f c 模型，给出了相应的l w f c 算法。 块匹配搜索时采用了邻域搜索法，仅对定义域低频信息库中的部分块匹配，从而大 大减少了计算量。此外，仅采用4 种仿射变换，减少了匹配次数，缩短了编码时间。 最后，通过实验结果分析了算法的有效性能。 第五章对全文的研究工作进行了总结，并对该研究的未来发展趋势给出自己粗 浅的看法。 第二章小波变换与分形理论 2 1 分形理论 第二章小波变换与分形理论 分形理论( f r a c t a lt h e o r y ) 的数学基础是分形几何。同传统的欧几里德 ( e u c l i d ) 几何学不同，分形几何研究的对象是大自然中不规则、甚至是支离破碎 的几何图形，例如，天空中的云彩、雷雨中的闪电和地面上的海岸线等等。这些图 形有一个共同点就是没有特征尺度，或者说是无标度的，即无法用一种尺度去标量 这种物体的形状。这些不规则的几何形状几乎出现在自然科学的各个领域中，例如 流体力学中的湍流，物理学中的布朗运动，生物学中的细胞生长，非线性动力学中 的奇怪吸引子，甚至经济活动中股市的震荡曲线等等。 分形理论诞生于二十世纪七十年代中期，其标志为美国科学家m a n d e l b r o t 于 1 9 7 5 年发表的专著： f r a c t a l ：f o r m ，c h a n c ea n dd i m e n s i o n 4 1 。分形从诞生到 现在短短不到3 0 年里取得了巨大的成功。首先，分形理论在现代非线性科学研究中 影响巨大，涉及的领域不只是自然科学领域，如地理、地质、工程技术、生物科学、 材料科学等，而且在社会科学与入文科学领域，如经济学、电影制作等领域也受到 广泛青睐。特别是随着计算机技术的迅速发展，分形思想在模式识别、信号处理以 及艺术制作等领域获得了巨大的成功。 2 1 1 分形理论的发展过程 分形理论的发展过程可分为三个阶段。 第一阶段：1 8 7 2 1 9 2 5 年，分形集合存在性的验证阶段。 在此阶段，数学家们已认识到几类典型的分彤集，并力图对这类集合与经典几 何的差别描述、分类和刻画。十九世纪，虽然人们已认识到连续曲线与可微曲线的 差别，但普遍认为连续曲线上的不可微点应是极少的。 1 9 0 4 年，瑞典科学家v a nk o c h 用非常简单的方法构造出处处连续但处处不可 微的曲线( k o c h 曲线) ，k o c h 曲线的面积为零而长度无穷大，具有严格的自相似性 和无限精细结构。如图所示： 青岛大学硕士学位论文 ( b ) ( c ) 图2 1 ( a ) 2 级k o c h 曲线( b ) 3 级k o c h 曲线( c ) 4 级k o c h 曲线 具有严格自相似性和无限精细结构的另一个例子是德国数学家c a n t o r 于1 8 7 2 年构造的c a n t o r 三分集。1 8 9 0 年，意大利数学家p e a n o 构造出了能够通过某个正 方形内所有点的曲线。这与传统的维数观念矛盾，从而人们提出应正确考虑以往的 长度与面积的概念。总之，在第阶段，人们已经认识到分形集合的存在性，并为 讨论这些问题提供了最基本的工具。 第二阶段：1 9 2 6 1 9 7 5 年，分形理论的创立。 人们对第一阶段提出的例子及其分形集合的性质进行了广泛深入的研究，深化 了第一阶段提出的思想，并逐步形成了理论，而且研究范围也扩展到了数学的许多 分支里，取得了丰硕的成果。 在维数理论方面，引入了众多的维数定义，使人们能从不同的侧面刻画和分析 分形集合的复杂性。在分形集合的结构和性质方面，b o s i e o v i t c h 在此期间先后研 究了曲线的维数、分形集合的局部性质、k a k e y a 集、分形集合的积。m a r s t r a n d 于 1 9 5 4 年研究了s 一集的性质和结构、分形集合的投影。在随机布朗运动方面，l e v y 建立分式布朗运动的理论，研究了稳定过程的性质。l e v y 在这方面的杰出工作使他 成为随机分形理论的先驱者。 第二章小波变换与分形理论 随着人们对分形理论研究的深入和其他学科里分形问题的大量涌现，客观上要 求用一种新的思想和工具去处理有关的问题。正是在这样的背景下。m a n d e l b r o t 经 过在众多领域的长期研究后，将自己和已有的研究成果进行了总结和理论的提升。 在1 9 7 5 年，他发表了具有划时代意义的专著f r a c t a l ：f o r m ，c h a n c ea n d d i m e n s i o n 4 1 。从此，分形几何的研究和发展进入了一个新的时期。 第三阶段：1 9 7 5 到现在，分形几何迅猛发展时期。 在这个阶段，分形几何不仅在理论上得到了进一步的完善，而且它的研究内容 也得到了扩展，如随机分形、多重分形、迭代函数系统理论、复动力系统的吸引子 理论、分形的数值方法、随即布朗运动和布朗曲面等。如今，分形理论的应用已经 扩展到了几乎所有的学科领域，如信号处理、分子化学、材料科学乃至经济、艺术 等领域，并且成果显著。 2 1 2 分数维 维数是欧氏几何中重要的参量，它是对该空间物体进行描述所需要的变量数。 传统的几何空间，物体的维数都是整数，例如点是零维、线是一维、面是二维、立 体是三维的( 5 1 。但河流、闪电、云层和神经网络等大量具有相似结构的物体，它们的 维数不再是整数，而是分数一分数维。分数维为描述分形物体的复杂性提供了支持， 它作为分形几何的一个重要的概念得到广泛重视和应用。 2 1 3 分形定义 目前，分形还没有严格的数学定义。现在人们普遍认为无需对分形集合下一个 严格的数学定义，只需对分形集的特征进行描述。我们不妨引用k f a l c o n n e r 对分 形的描述n j ： 1 ) 具有无限的精细结构，即是说在任意小的尺度下，它总有复杂的细节； 2 ) 非常不规则，以至于它的整体和局部都不能用传统的几何语言来描述； 3 ) 具有某种自相似性，这种自相似性可以是近似的，也可能是统计意义上的； 4 ) 在某种分形意义下的分数维通常大于它的拓扑维数； 5 ) 往往可以由递归迭代等简单方法得到。 2 2 分形图像压缩的数学基础 美国数学家m i c h a e lb a r n s l e y 在八十年代末首先将分形理论应用于图像压缩， 提出了分形图像压缩【7 】【8 】f 9 】的概念。分形图像压缩的数学基础是迭代函数系统( i f s ) 、 不动点原理( t h ef i x e dp o i n tt h e o r e m ) 和拼贴定理( t h ec o ll a g et h e o r e m ) 。分 形理论指出，分形是复杂的不规则的集合，也是具有精细结构的集合图像，许多分 青岛大学硕士学位论文 形可以用简捷的构造过程得出。分形图像压缩就是寻找简单的i f s 代码。解码时用 该i f s 代码在任意初始图像上进行迭代，重建吸引子。 2 2 1 压缩映射和迭代函数系统 定义1 压缩映射对度量空间( x ，d ) 上的变换：x - - x ，如果存在一个常数 0 j 0 ，如 果能选到一个i f s 工，h = l ，2 ， ，其压缩因子( 0 5 = m 蹦蛐叫口r ；m ) l f ，( 等卜 2 啷) 其中a 是尺度参数( 尺度因子) ，b 是定位参数( 定位因子) ，连续小波函数y 。( x ) 不 是复变函数时，上述积分中它的共轭函数是其本身。改变a 的值，对函数i f ，( x ) 具有 伸展( a 1 ) 或收缩( a 1 ) 的作用：改变b 的值则会影响函数f ( x 1 围绕b 点的分 析结果。 定义3 连续小波逆变换对于所有厂( x ) ，y ( 工) r ( r ) ；f ( x ) 的连续小波逆变换或重 建公式为： m ) = 砉e a - 2 g ( 口，6 ) y 。( x ) d a d b 2 一( 9 ) w 其中。= 样咖 。 小波变换式可以认为是信号f ( x ) 以y ( x ) 为核函数的一种积分变换。与傅立叶变 换及其他积分变换相比，不同的是核函数v ( x ) 不是固定的，可自行构造。但是也不 是任何函数都可以作小波变换的核函数。因为，任何变换只有其反变换存在才具有 实际意义。所以，为了使得小波变换的反变换存在，基本小波v ( x ) 必须满足下述性 质。 1 允许性：函数缈( x ) 是基本小波，小波变换反变换存在的充要条件是 q = 譬学咖 ，e 4 ) 巧+ t = l + ，z z 5 ) f 铮f ( 2 x ) l 一，z z 2 4 小波变换编码 小波变换用于图像编码的基本思想就是把图像进行多分辨率分解，分解成不同 空间、不同频率的子图像。然后再对子图像进行系数编码。系数编码是小波变换用 于压缩的核心，压缩的实质是对系数的量化压缩。根据s m a l l a t 的塔式分解算法， 图像经过小波变换后被分割成四个频带：水平、垂直、对角线和低频。低频部分还 可以继续分解。图像经过小波变换后生成的小波图像的数据总量与原图像的数据量 相等，即小波变换本身并不具有压缩功能。之所以将它用于图像压缩，是因为生成 的小波图像具有与原图像不同的特性，表现图像的能量主要集中于低频部分，而水 平、垂直和对角线部分的能量则较少；水平、垂直和对角线部分表征了原图像在水 平、垂真和对角线部分的边缘信息，具有明显的方向特性。低频部分可以称作亮度 图像，水平、垂直和对角线部分可以称作细节图像。对所得的四个子图，根据人类 的视觉生理和心理特点分别作不同策略的量化和编码处理。人眼对亮度图像部分的 信息特别敏感，对这一部分的压缩放尽可能减少失真或者无失真，例如采用无失真 d p c m 编码；对细节图像可以采用压缩比较高的编码方案，例如矢量量化编码、d c t 、 小波零树编码方案等。 青岛大学硕士学位论文 l l 3ih l 3 j h l 2 l h 3l h h 3 h l 水平高频分量 l h 2h h 2 l h ih h i 垂直高频分量对角线高频分量 图2 2 图像的三级小波分解 根据实验统计和理论研究得到一致的结论，9 0 的小波系数绝对值都非常小， 并且都集中在零点附近。大的系数主要集中在最低频带，即图像的能量大部分集中 在低频带。并且随黄小波分解级数的增加，由于能量分布在更多的频带内，最低频 带的能量相对于分解级数小的频带相对降低。 本文所提出的算法正是依赖以上所讨论的小波系数分布的特点，将其与分形编 码相结合，加快编码速度的。 小波分解的数据结构，特别适宜于图像的压缩编码。主要由于： 1 ) 小波分解可以看作是信号在一组独立的不同空间频率通道上的分解。这正 适应了人类视觉系统h v s 的空间方向特性，从而可以在相同的主观质量下 得到更高的压缩比。 2 ) 小波变换采用塔形分解的数据结构，分辨率由粗到精，与人眼由粗到精、 由全貌到细节处理视频信号的模式相一致。这是小波变换与h v s 相结合改 善图像质量与压缩性能的又一有利条件。 3 ) 小波变换本质上是全局变换，其量化噪声随机分布在整个图像中，因而不 易觉察，其重建图像中可免除采用分块正交变换所固有的“方块敦应”。 4 ) 小波变换具有时间一频率定位能力，并初步实现了图像中平稳成分和非平 稳成分的分离。低频成分精确定位于频率域，且基本上是平稳的，高频成 分精确定位于空间域，且为非平稳的。处理非平稳信号是统计信号处理的 一个难点，但对于图像，其非平稳成分通常表现为边缘、纹理等。这些非 平稳成分被小波变换精确定位以后有可能实现图像的高效编码。 正是由于这些优点，小波图像编码在较高压缩比的图像编码领域被非常看好。 第二章小波变换与分形理论 然而为了使小波变换图像编码方法的潜在性能发挥出来，还有很多问题需要解决， 如变换系数的有效组织、人眼视觉特性的应用以及最佳小波基的选取等。因此，需 寻找小波变换与其他编码方法的组合编码方法，以综合应用各种方法优点，达到最 佳编码效率。 2 5 小波与分形混合图像编码 将小波与分形结合起来进行混合编码已经有很多人研究过【 ，对其进行结合的 方法有多种【1 2 ，有的在编码方法上进行了改进【1 3 i ，而有的在编解码速度上进行了改 进【1 4 】，并取得了很好的实验结果【”l ，这些实验【1 6 l 充分证明了小波与分形结合起来的 可能性以及研究的必要性。 目前基于小波和分形的混合图像压缩编码主要有两大分支。 2 5 1 小波域内分形图像编码 首先，给出常用的一个重要概念的描述小波树。小波树是由具有不同分辨率 和不同方向但具有相同的相对空间位置的小波系数构成。如下图给出了个经过3 级小波分解产生1 0 个小波子带的示意图。每一级小波变换产生的四个子带分别代表 低频直流分量和水平、垂直及对角方向的高频分量，不同分辨率和不同方向但具有 相同空间位置的小波系数之间都存在较强的相关性【l7 j h 。若同时考虑水平、垂直及 对角三个方向的小波系数，则它们组成分层树状结构小波树。 鲁 、- 目 q 臣 e 水 k 、臼 勃 目 ； 向图 图2 3 小波树 在这个方向最典型的算法是d a v i s l l 7 】在1 9 9 8 年提出的小波子树的自量化s o s 编 码算法。他所设计的采用自上而下的方法循环迭代实现对小波树的每个节点的构 青岛大学硕士学位论文 造，即每一次迭代都要确定小波树的节点是否保留，来相应得修正小波树的分割结 构，以实现小波树的最优分割。但该算法的计算量很大，编码复杂，难以实际应用。 1 9 9 8 年，张颖、于英林【ls 】等在d a v i s 的基础上提出了改进的分形小波自适应混 合编码算法。该算法能在预测过程中根据编码误差自动调整小波树的尺度以实现自 适应。该算法较d a v i s 的算法编码效果略好，复杂度较低。 另外，张宗念等【19 】在1 9 9 9 年通过定义方向性零小波树，提如了一种两级自适应 小波树分割新方案，只采用了两种小波域的分形仿射变换，进一步简化了编码复杂 度。 2 5 2 局部小波变换分形图像编码 这种编码算法对图像分块，然后再对每一块进行局韶小波变换。这种编码算法 充分利用了小波分解的空间、频率局部特性，即通过小波分解的图像的大部分能量 主要集中在低频信息中，而剩下的图像的高频部分，大多数的能量又主要在空间上 集中在边缘附近。本文提出的l w f c 算法就属于这个分支，在此基础上进行改进和 提高的。 第三章基于局部小波变换的分形图像编码模型 第三章基于局部小波变换的分形图像编码模型 创建模型和编码是两件完全不同的事情，但人们常常使用术语“编码”来表示 整个数据压缩处理过程。例如，人们会听到h u f f m a n 编码或算术编码这些描述数据 压缩技术的短语。但事实上，它们仅仅是与模型连接在一起来进行数据压缩的一种 编码方法，事实上，数据压缩= 创建模型十编码。相对于同一种编码过程，可以对应 多种模型。即这些模型都可以使用相同的编码过程来产生它们的输出。本章，将提 出本文图像压缩的模型。 3 1 分形图像编码描述 3 1 1 仿射压缩变换 在分形图像编码中，i f s 的变换通常采用仿射压缩变换，因为它可以很好地描述 平移、旋转、伸缩以及反射的各种组合。 设w ：x _ x 是基本空间( x ，d ) 上的一个映射，如下 w ( x ) ( ： ( ； + ( ； = 彳x + r 3 一( 1 ) 其中，x = ( ； ，一= ( ： ，r = ( ； 。当忙忙。时，称。为平面。二维，仿射压缩变 柑( | + 纠 。也， w ( x ，y ，z ) = ( w ( z ，y ) ，a z + 卢) 3 一( 3 ) 青岛大学硕士学位论文 表3 18 种空间仿射交换 序号变换说明 l恒等变换 2y 轴反射 3 x 轴反射 4对角线x = y 反射。 5对角线x y 反射 6 旋转9 0 7旋转1 8 0 。 8旋转2 7 0 3 1 2 定义域块和值域块的匹配过程 在编码过程中，对于每一个值域块置都要寻找定义域块d l ，空间变换w f ，对比 度s 和亮度0 ，使得变换后的皿与置最相似。一般用e r l 衡量d j 在仿射变换后与 r 的近似程度，其中p q = 1 w f ( 厂) ( y ) 一厂( 墨y ) 1 2a x d y 。这里，d f 的位置信息、 空间变换、对比度j ，和亮度o 。一起构成分形参数。 在定义域块与值域块相匹配的过程中，对选定的定义域块进行伸缩，使得伸缩 后的尺寸与值域块的尺寸相等，然后对变换后的定义域块进行上述的旋转和反射空 间变换后，最后就是计算最优的对比度s 和亮度0 。 对比度和亮度的求取可利用最小二乘法得出。具体计算方法如下：假设 d , j ( i = 1 ，2 ，n ；j = l ，2 ，聊) 是经过伸缩变换和旋转反射后定义域块的象素值。 r j ( i = l 2 棚；= l ，2 ，川) ) 是值域块的象素值，最佳的对比度s 与亮度。应该使得 下式r 最小。 尺= ( s 吒+ o 一_ ) 2 3 - ( 4 ) i = 1 j = l 为了使r 达到最小，对上式的s 和。分别求导，并且令娑和娑等于o ，从而有 2 0 第三章基于局部小波变换的分形图像编码模型 蜥n 饥- z 吒o ，= - 竺= l 上l 苎型掣一 月m， my m 疗d 2 。- i 吒l mnm 一s 吒 d = 兰u = l _ 一旦丝一 m 门 3 一( 5 ) 此时有 r 2 磊1 i 台n 身mr 2 “ 1 5 善n 缶m 口2 一一2 善蔷嘞。+ 2 。善丢。j + 。l ”m 。善；办ji 1“ ， 一 一 nmhm 、f 1l 如果 埘竹蔷否v l 善丢办j 2 0 厂n m 、2 则 。扎d ：上窆妻 n m 百管。 3 2 小波变换模型及系数分布特点 3 2 1 数字图像的小波变换模型 首先，给出利用小波变换分析数字图像的数学模型。对于一个给定的数孚图像， 记为一个数据集合 ，0 i n i ，0 j 2 必然存在一个函数f ( x ，y ) o r ( 尺2 ) 使 f ( x ，y ) = ，识如，y ) ， 通过离散小波变换，获得 f ( x ，y ) = 。o 竹， ，_ y ) = 吒仍，( x ，y ) + ? 。v 0 “( x ，y ) j ，jf ，j ”i ，d f ， 记 d 胛眈，o 7 n i ，o - 2 ) 3 一f 6 ) 0 ，呓4 ，0 f 2 一n i ，0 j 2 2 ，m = l ，2 ，厶d2 l ，2 ，3 ) 为数字图像的小波分解，逆过程是小波合成，均满足m a l l a t 的递推公式和反递推公 青岛大学硕士学位论文 式。对于图像分解，小波变换相当于交替在水平和垂直方向上进行滤波和亚采样。 一个三层分解的离散小波系数矩阵如图所示，它将图像分解成1 0 个子带。 l l 3h l 3 h l 2 l h 3h h 3 h l l 水平高频分量 l h 2h h 2 l h lh h i 垂直高频分量对角线高频分量 图3 1 图像的三级小波分解 3 2 2 小波系数分布特点 一幅图像经过小波分解后，得到一系列不同分辨率的子图像。低频子图像保留 了图像的大部分数据，即图像的能量大部分集中在低频带，高频子图像大部分数据 都接近于零，频率越高这种现象就越明显。 从小波变换理论上，可以分析这种现象。厂具有指数a ( 0 a r ， s t e p 为搜索步长。如果再加上8 种可能的空间仿射变换，则对于每一个r ，可能搜索 的定义域块的数目就是8 ( ( 2 ”一2 “+ 1 ) ( 2 ”一2 4 + 0 ) s t e p 2 。根据统计规律，对于大 多数值域块r 不必搜索所有的可能定义域块d ，就可以或得满足误差要求的匹配定 义域块。因此，对值域块足的匹配定义域块的寻找可以有许多好的办法，来改进原 算法的全搜索方式。 大量的统计试验表明，对于给定位置的值域块r ，搜索到其最优匹配自相似定 义域块的位置的概率分布几乎都集中在值域块咒附近。为此在编程实现中，设定一 搜索范围，以此范围内从定义域小波系数信息库中寻找与给定值域块距离最小的定 义域块，作为其最优匹配自相似定义域块。这就是邻近局部搜索法。采用该搜索法， 减少了待搜索的定义域块数目，从而缩短了编码时间，还节省了编码空间。 青岛大学硕士学位论文 4 1 2 仿射变换 本文通过实验发现，块匹配时仅采用几种仿射变换所得到的图形质量基本不变。 这与空域分形图像压缩编码中8 种仿射变换并非是固不可少的结论是一致的 2 2 】。因 此，本文通过实验验证，只采用了前四种仿射变换( 恒等变换、y 轴反射、x 轴反射、 对角线x = y 反射) 。从而使算法更加简化，计算量大大减少，进一步降低了编码时间。 而且四种仿射变换只需要2 比特记录变换类型，分形参数结构减小，提高了压缩比。 4 1 3 小波变换级数 原算法是对大小为2 2 7 的块进行r 级小波变换，保存低频的四个小波系数，记