（检测技术与自动化装置专业论文）基于小波变换的分形图像压缩技术研究.pdf

1 1 1 基于小波变换的分形图像压缩技术研究 摘要 帅i i i i l l liiii1 11tlllllllllllllllllllllllltlliiiiii i i i i i y 17 4 0 5 19 近3 0 年来，作为一个新兴的数学分支，分形几何成为了人们描述与研究自然 界纷繁复杂现象的强有力的工具之一，同时，它在图像压缩编码中也得到了广泛 应用。 基于分形理论的图像编码方法是一种全新的方法，它通过图像整体或局部的 自相似性和自成比例特性，消除图像的内部几何冗余来实现图像信息的压缩。分 形压缩具有压缩比大的优点，这也是它得到广泛研究的重要原因。但是压缩时间 长是一个主要缺点，妨碍了它走向实用化。缩短压缩时间是一个主要研究方向。 基于小波变换理论的图像压缩技术也是一个热点。小波变换本身存在着压缩 比小，受图像的分辨率影响大等缺点。本文通过使两者结合进行图像编码，以期 达到良好的压缩目的。事实上，人们已经开始了关于小波与分形理论相结合的混 合编码方法的研究。 本文在研究快速分形压缩编码和与小波变换相结合的编码方法方面作了以 下工作： ( 1 ) 本文提出了一个新方案，主要是改善原来的搜索方法。先对图像进行 小波分解，在小波分解时，我们通过研究证明，小波基的选取对于重构图像的质 量有重要影响。同时，本文通过研究s p i h t 算法的不足，提出了一种改进的算法。 ( 2 ) 通过研究发现，在选择块搜索和创建块池时，图像值域块与定义域块 之间，定义域块和定义域块，值域块与值域块之间都存在着大量的相似块。如果 在块池建造过程中，考虑并消除这种相似块，那么值域块与定义域块的搜索过程 将会大大缩减。 ( 3 ) 小波包变换是小波变换的改进和完善，本文通过研究小波变换与分形 的结合，进一步推广到了小波包与分形变换相结合的图像压缩编码研究。通过仿 真证明，本文算法取得了很好的效果。对于小波包的引入和应用，拓宽了分形编 码与小波变换结合的范围。 关键词：图像压缩分形编码小波变换小波包 i i r e s e a r c ho nf r a c l l a li m a g ec o d i n g b a s e do n 乙瓠厂e l e t a bs t r a c t d u r i n gt h ep a s t3 0y e a r s ，a san e wb r a n c ho fm a t h e m a t i c s ，f r a c t a lg e o m e t r yh a s b e c o m eo n eo ft h ep o w e r f u lt o o l si nn a t u r ed e s c r i b i n ga n dc o m p l e xp h e n o m e n o n r e s e a r c h i n g a tt h es a m et i m e ，i ti sw i d e l yu s e di nt h ei m a g ec o d i n gd o m a i n t h e i m a g ec o d i n gm e t h o db a s e do nf r a c t a li san e wo n e ，b a s i n go nt h es e l f - i m a g e a n ds e l f - s i m i l a rc h a r a c t e r i s t i e so ft h ew h o l eo rp a r ti nt h ei m a g e ，w h i c he l i m i n a t e st h e i n t e r n a lg e o m e t r i ci m a g ei n f o r m a t i o nr e d u n d a n c yt oc o m p r e s s f r a c t a lc o m p r e s s i o n h a sa na d v a n t a g eo fh i g hc o m p r e s s i o nr a t i o ，w h i c hr e s u l t st oi t si n - d e p t hs t u d y b u t t h ec o m p r e s s i n gt i m ei sam a j o rd r a w b a c kh a m p e r i n gi t sf u r t h e rt o w a r dp r a c t i c a l a p p l i c a t i o n r e d u c i n gt h ec o m p r e s s i o nt i m ei sam a j o rr e s e a r c hd i r e c t i o n i m a g ec o m p r e s s i o nt e c h n o l o g yb a s e do nw a v e l e tt r a n s f o r mi sa l s oah o ts p o t w a v e l e tt r a n s f o r mh a ss e v e r a ld r a w b a c k s ，s u c ha sal o wc o m p r e s s i o nr a t i oa n di t s c o m p r e s s i o ni m p a c t e db yt h ei m a g er e s o l u t i o n i nt h i sp a p e r ，w ep r o p o s eam e t h o dt o c o m b i n et h e s et w om e t h o d s ，i n c l u d i n gw a v e l e ta n df r a c t a l ，i no r d e rt o g e tab e t t e r r e s u l t , ah i g hc o m p r e s s i o nr a t i oa n das h o r tc o m p r e s s i o nt i m e i nf a c t ，p e o p l eh a v e s t a r t e do nt h em i x e dm e t h o ds t u d yo fw a v e l e ta n df r a c t a lc o d i n gt h e o r yf o rac e r t a i n t i m e t h es t u d i e dt h i s p a p e rh a s d o n eo nf a s tf r a c t a l c o d i n ga n dw a v e l e ta r ea s f o l l o w i n g ： ( 1 ) t h i sp a p e rp r o p o s e san e wp r o g r a m ，m a i n l yt oi m p r o v et h eo r i g i n a ls e a r c h m e t h o d f i r s t ，d e c o m p o s et h ei m a g ew i t hw a v e l e t w h e ny o u a r es e a r c h i n g , w ep r o v e t h a tt h es e l e c t i o no f w a v e l e tb a s e sf o rt h er e c o n s t r u c t i o no f t h ei m a g e q u a l i t y h a sab i g i m p a c t a tt h es a m et i m e ，b ys t u d y i n gt h ed e f i c i e n c yo fs p i h t ，t h i sp a p e rp r o p o s e s a ni m p r o v e ds p i h tm e t h o d ( 2 ) a sw ek n o w ，t h e r ei sr e d u n d a n c yb e t w e e nr a n g eb l o c k sa n dd o m a i nb l o c k s ，i n r a n g eb l o c k s ，e v e ni nd o m a i nb l o c k s w h e nc o n s t r u c t i n gt h eb l o c k sp o o l ，t h e s e a r c h i n gp r o c e s sw i l lb el a r g e l yr e d u c e d ，i fw et a k et h e s eb l o c k s s i m i l a r i t y c h a r a c t e r i s t i c si n t oc o n s i d e ra n dr e d u c et h er e d u n d a n c yb e t w e e nt h e m ( 3 ) w a v e l e tp a c k e tt r a n s f o r m a t i o ni sa ne x t e n d i n gd e v e l o p m e n to fw a v e l e t a f t e r t h es t u d yo fw a v e l e ta n df r a c t a l ，w eg o tag o o de f f e c t t h e nt h i sa r t i c l ei n t r o d u c e d i i i ， w a v e l e tp a c k e tm e t h o dt oi m p r o v ef r a c t a li m a g ec o d i n g t h es i m u l a t i o ns h o w st h i s a l g o r i t h ma c h i e v e dg o o dr e s u l t s w es u c c e e d e dw i d e nt h ea p p l i c a t i o no ff r a c t a l c o d i n ga n dw a v e l e tt r a n s f o r mb yt h ei n t r o d u c t i o na n da p p l i c a t i o no fw a v e l e tp a c k e t k e y w o r d s ：i m a g ec o d i n gf r a c t a lc o d i n gw a v e l e tt r a n s f o r m a t i o nw a v e l e t p a c k e t i v 目录 第一章绪论1 1 1 引言。i 1 2 图像压缩基础2 1 2 1 图像压缩的必要性和可能性2 1 2 2 图像品质的度量3 1 2 3 图像压缩名词术语6 1 3 图像压缩方法的研究与现状8 1 3 1 图像压缩方法的分类标准8 1 3 2 无失真图像压缩编码9 1 3 3 有限失真图像压缩编码9 1 3 4 分形与小波变换相结合的压缩1 2 1 4 分形压缩的发展背景及前瞻1 3 1 5 本文结构1 4 第二章分形理论基础1 5 2 1 分形简介1 5 2 1 1 分形几何的基本概念1 5 2 1 2 分形几何的维数1 7 2 2 度量空间、不动点、压缩映射2 0 2 3 拼贴定理2 3 2 4 迭代函数系统2 4 2 4 1 分形方法用于图像数据压缩的技术思路2 4 2 4 2 迭代函数系统2 5 2 5 本章小结2 9 第三章分形图像压缩方法简介3 0 3 1 带映射的局部迭代函数系统( l i f s m ) 3 0 3 2 自动分形图像压缩方法3 1 3 3 分形编码实例3 6 3 4 实验结果分析3 7 3 5 本章小结3 8 第四章基于小波变换的图像压缩研究3 9 4 1 小波变换简介3 9 4 2 多分辨率分析4 1 4 3 小波变换应用于图像处理4 3 4 4 小波变换的特点4 5 4 5s p i h t 小波图像压缩算法研究与改进5 1 v 4 5 1s p i h t 算法简介5 1 4 5 2 改进的s p i h t 方法图像压缩5 3 4 6 本章小结5 7 第五章基于小波分析的分形编码5 9 5 1 分形编码和小波分析结合的可能性j 5 9 5 2 简单改进的分形与小波变换的混合编码5 9 5 3 改进的分形与小波变换的混合编码6 0 5 3 1 本方法的改进与实验步骤6 0 5 3 2 实验步骤6 3 5 3 3 实验结果与分析6 4 5 4 小波包分析方法及其应用6 6 5 5 基于小波包的分形编码方法6 8 5 5 1 编码过程步骤6 8 5 5 2 试验结果与分析6 8 5 6 本章小结7 0 结论7 1 参考文献7 3 致谢7 6 攻读学位期间发表的学术论文和参加科研情况说明7 7 独创性声明一7 8 关于论文使用授权的说明7 8 v i 青岛科技大学研究生学位论文 1 1 引言 第一章绪论 日常生活中，人们主要是通过语音和图像来传递信息。据统计，在人类所接 受的信息中，视觉信息占6 0 ，听觉信息占2 0 ，其他如味觉、触觉、嗅觉总的 加起来不过占2 0 。可见，图像信息作为传递信息的一种重要的媒体和手段【l 】。 数字图像处理的定义，就是通过使用计算机和其他大规模集成、高速的数字硬件， 对从图像信息数据中转换来的数字电信号，进行特定的数字运算或处理，以保证 提高图像的质量或能够达到人们所预期的效果，因此通常也把数字图像处理称为 计算机图像处理，如对图像信息中的噪声污染进行滤出、对信息信息少或者微弱 的图像进行增强处理、从犯罪现场提取指纹特征、对失真的图像进行几何校正、 对数据量过大的图像进行编码压缩等。使用计算机对图像进行处理精度高，处理 方法可通过改变软件实现，灵活方便，现如今已经实现了实用化和普及应用【2 】。 数字图像处理起源于2 0 世纪2 0 年代，美国纽约与英国伦敦间首次通过海底 电缆传输了一幅采用了数字压缩技术的数字化新闻图片。就当时的技术水平来 看，如果不通过压缩，传一幅图像需要一星期左右的时间，而压缩后仅需3 小时。 这是一种图像处理技术的简单雏形。数字图像处理开始于2 0 世纪5 0 年代中期， 当时美国在“太空搜索计划的推动下，开始了对该技术的研究探索。在1 9 6 4 年美国的喷气推进实验室( j p l ) 通过数字计算机，对“徘徊者7 号”太空船所 发回的4 0 0 0 多张月球照片进行了处理，是此项新技术诞生的重要标志。此后几 年，该技术继续在在空间研究计划中得到应用。如“水手号”太空船的靠近火星 飞行“观察者 太空船的登月飞行以及“阿波罗载人登月”飞行中，并对飞行中 所传回的许多图像进行了增强和恢复等。在2 0 世纪6 0 年代至7 0 年代这l o 多年 中，伴随着数字计算机、成像技术以及信号技术在速度、规模和经济效果上的改 进，与此同时由于离散数学理论的创立和不断完善，数字图像处理技术得到了迅 猛发展，它的理论和方法进一步得到完善。 图像信号经过数字化后，它的数据量是相当大的。若根据c c i r 6 0 1 号建议( 电 视演播中心的数字电视编码标准) ，数字电视的数据率高达2 1 6 m b s 。而对于计算 机图像，在分辨率为6 4 0 4 8 0 ，2 5 6 色的v g a 显示模式下时，一帧图像数据信 息约为3 0 7 2 0 0 字节。如果要达到每秒3 0 帧的动态显示，其数据率则为9 2 m b s 。 基于小波变换的分形图像压缩技术研究 可见，数据量是非常大的，非常难以直接对其进行保存。显然，为了提高信道利 用率和在资源有限的信道容量下传输更多的图像信息，很有必要对图像数据进行 压缩。数据信息压缩技术也因此在数字图像传输中起着关键性的作用【3 5 】。 1 2 图像压缩基础 1 2 1 图像压缩的必要性和可能性 一幅能够实用的数字图像的信息数据量是非常巨大的。例如，一幅2 4 位真彩 色6 4 0 4 8 0 分辨率的图像的数据量约占9 0 0 k b 的存储空间，如此大的数据量不 仅对计算机本身的存储和处理能力提出了很高的要求，同时也使得图像通信的信 道传输速率受到较大的限制。因此，为存储、处理和传输这些数据信息，必须要 对图像数据信息进行压缩编码。 在满足一定图像质量条件下，采用某种编码方式，以期尽量减少图像的比特 数，这就是图像压缩的研究课题 6 1 。另外，还要研究是否能减少图像的比特数， 最少能减少到多少，用何种方法去减少等。 事实上，减少图像数据信息量是可能的，因为一般的图像数据中，通常存在 很大的各类冗余度 2 】【j 7 1 。例如空间性冗余，结构性冗余，心理视觉冗余，系统的 匹配性冗余等。一般的，相邻的两个像素之间具有相似的灰度值，这种灰度上存 在的相关性，表明图像内部存在空间性冗余；根据先验知识，人们可以依据图像 中的一部分信息来推知另一部分信息。如，某些物体是关于轴线、中心或点对称 的，某物体的_ 个物面灰度是相同的，这是图像本身存在的结构性冗余。 还有根据人的视觉特性，当图像中的某些信息去掉后，人通过视觉对图像内 容的理解与原意不大。比如，人的视觉具有掩盖效应和对空缺直线填充的能力， 所谓心理视觉冗余，就是指那些因视觉的有限性和联想性，可以丢弃的不重要的 信息。 另外，人们通常只对原始图像的一部分信息感兴趣，对不感兴趣的另一部分 我们可以降低其分辨率，进而减少关注冗余度；当图像系统各部分的分辨率不一 致时，单独保持某一部分的高分辨率是没有什么意义的。系统存在匹配性冗余， 如当通信信道的分辨率不高于所输入图像的分辨率时，降低所输入图像的分辨率 后再进行输出，图像质量变化不大；对于序列图像，相邻帧中相同对应点处的灰 度值也是相近的，也存在相关性，这就表明图像序列的灰度值间存在时间性冗余。 研究表明，图像中通常还存在着量化性冗余，这种冗余表现为，通过改变量 化判决灰度值和重建灰度值，用更少的量化等级数便可达到相同的或相似的视觉 2 青岛科技大学研究生学位论文 效果；图像间还可能存在所谓的编码性冗余，如对图像的灰度压缩编码过程中， 所用的符号数多于用来表示各个灰度级的实际所需的最少符号数，那么用这种压 缩编码方式所得到的图像便具有编码冗余。 1 2 2 图像品质的度量 图像质量也就是图像的保真度，它描述了被评价的图像区别于初始图像的程 度【6 】【8 1 。图像质量的可靠程度和保真程度在图像处理中有着极其重要的作用。有 了这种度量，人们就能评价各种图像处理技术或系统的性能，进而为设计工作提 供各种有力的证据。 图像质量度量的方法主要有主观评价、图形测试以及数值度量法等【7 】【引。 ( 1 ) 主观评价法 图像质量的主观评价是指以人来作为图像的观察者，对图像的好坏优劣作出 评价。因为经过处理后的图像大部分最终是供人们观察的，故用主观判断作为图 像质量的度量不仅是合理的，通常也是最为可靠的。主观评价法有两种度量尺度， 即绝对性尺度和比较性尺度，它们都附有文字说明。如下表( 表1 1 ) 是给出的 绝对性尺度的两个例子，表1 2 是比较性尺度的例子。在此需指出，所谓群优尺 度就是把需要评价的一群图像中每幅图像，与该群中所有其它图像经过对比后得 出的。 表1 - 1 绝对性尺度 t a b 1 - 1a b s o l u t es c a l e 全优度尺度损害尺度 5 优1未感觉损害 4 好 2 刚好感觉损害 3 中3 感觉到，但只对图像有轻微损害 2 劣 4 对图像优损害，但尚悦目 l 差 5 稍感不悦目 6不悦目 7 非常不悦目 基于小波变换的分形图像压缩技术研究 表1 2 比较性尺度 t a b 1 - 2c o m p a r a t i v es c a l e 群优度尺度群优度尺度 7 一群中最好的 3 稍差于该群平均水平 6 好于该群平均水平 2 差于该群平均水平 5 稍好于该群平均水平 1 一群中最差的 4 该群的平均水平 主观评价的一般步骤是这样的，先用某些原始标准图像建立起像表1 1 或表 1 2 所列的质量等级标准，尔后由观察者观看被评价的图像( 一般是对原始标准 图像做图像处理后得到的) 并与原始标准图像各等级作对比，以定出被评价图像 的等级。但有时也可完全根据观察者先前观察的经验来评判。 主观评价的结果通常情况下使用被评价图像的平均得分，来表示： 一x x 厂：y ，l ， y ( 1 1 ) _ 一 _ 一 ，= lj = l 上式中，k 是质量等级总数。例如，损害尺度，k = 7 ；全优度尺度，k = 5 。刀，是 评判该图像为第i 等级的人数。，是质量为第i 等级时所规定的得分，实际上， 就是表上该等级前面所标的数字值。例如，在损害尺度中选择了“稍感不悦目 ， 则这一等级的得分为5 分。 为保证统计上的可靠性，主观评价法一般要求观察者的人数大于等于2 0 名： 并且这些人中既要有“外行，即未经过判图训练的人，以代表观众的真实平均 水平，也要有训练有素的“行家 或“专家”，以便能够对图像的质量作出专业、 中肯的判断。此处还应着重指出，图像的类型对于测试的结果也有很大影响。因 为观察者对于图像早已熟悉，由于本身的先入之见，对图像的质量往往很挑剔， 很严格；而那些不为大家所熟悉的图像，有些质量问题很有可能就被疏忽掉。当 然，试验的条件本身也是影响结果的一个重要因素，应尽可能的把实验的环境安 排的与人们平常生活中实际观看的情况相符。 ( 2 ) 图形测试法 对于图像扫描器和显示器，常用的方法是把该类设备对测试信号或图像的响 应记录下来，以对其质量进行评价。例如，若在电视摄像机前放一张灰阶测试卡， 4 青岛科技大学研究生学位论文 则摄像机输出信号电压偏离完整阶跃波形的程度，可用来作为摄像机质量的一种 度量。电视传输系统中常用升余弦脉冲作为测试信号，经过信道传输后，所得信 号用来和刻有标度的信号末班进行拟合，以度量系统所做成的各种失真。 ( 3 ) 数值度量法 图像质量的数值度量一般分为两类：单变量( u n i v a r i a t e ) 和双变量( b i v a r i a t e ) 。 单变量度量仅仅计算被评价的图像，质量尺度则是根据被评价的图像偏离标准图 像的程度来确定的；双变量度量则要用被评价图像和标准图像两幅进行计算以确 定它的质量尺度。 单变量数值度量通常用来计算图像的空间频谱，因为图像质量的变坏常表现 为空间高频分量或低频分量的丢失。被评价的图像函数设为f ( x , y ) ，在连续情况 下，二维傅里叶变换为 分( “，1 ，) = “$ _ l f ，“f l y ，厂“y ) 唧卜f 易似+ v y ) l d x d y ( 1 - 2 ) 式中，t 、，分别代表图像的x 、y 轴方向的有限尺寸。在离散情况下，其表达 式为 f ( u ，1 ，) = zz 1 6 ( 像素) 时，其性能已经 改善不大。同时，子图像块过大，其中所包含的像素就越多，变换时所需的计算 量也越大，因此一般子图像块的大小选为8 x 8 或1 6 x 1 6 。 对图像进行子块划分的另一个好处是：它可以将传输误差所造成的图像损伤 限制在子图像的范围之内，从而避免误码的扩散。本文所要介绍的分形编码，以 及小波变换编码同属此类： 1 3 4 分形与小波变换相结合的压缩 当前，常用的无失真与有失真的图像编码方法都存在压缩比低的缺点，因而 1 2 青岛科技大学研究生学位论文 人们一直在努力寻找新的压缩编码方法。自9 0 年代以来，由于分形压缩和小波 压缩都突破了在局域内相关法去冗余的传统压缩编码方法的局限性，有很多优良 的特性，从而引起了人们的广泛关注。 分形压缩编码有着精细的结构，可以有任意小比例且有自相似的细节【1 2 - l5 1 。 通常它能以非常简单的方法定义，并通过迭代方法产生，表现的是事物的总体和 局部相互转化，认识从宏观向微观深化的过程。然分形编码也有很多不足之处， 由于它的编码时间较长，限制了分形的硬件实用化，同时限制了它的发展。 小波变换方法是一种频率域与空间域相结合的图像分析手段，并且它基于事 物认识过程中的多分辨原则，即人们由远到近观察事物是一个逐步认识的过程， 首先是总体轮廓，然后是结构线条，最好是纹理细节。将分形与小波变换相结合， 是对分形技术应用于图像压缩编码领域的一个新的探索【1 6 2 0 】。 1 4 分形压缩的发展背景及前瞻 1 9 7 0 年代初，经过长期研究，m a n d e l b r o t 提出了用分形几何学描述自然界不规 则的，具有自相似特性的物体，并从而准确地为分形作了定义【l 引。受他的启迪， 人们开始对大自然中复杂的自相似图像的研究。伴随着计算机技术的迅猛发展， 到1 9 8 0 年代中期，研究者们开始用计算机建立的分形模型来模拟描述自然景物， 其中b 锄s l e v 将基于迭代函数系统的分形图像压缩编码成功地应用在计算机图像 学上，其压缩比甚至达到了1 0 0 0 0 ：1 。但其算法有很大的局限性：首先压缩编码 过程需要人工干预；其次原图像与解码图像的差别很大；再次解码图像从主观上 判断缺乏真实感。 在1 9 8 9 年，j a c q u i n 对b a n l s l e y 的算法【2 l 】【2 2 】进行了改进，并第一次提出了基于 块仿射变换的自动分形编码方法。尽管其压缩比大大低于b a m s l e y 的方法，但是 其算法的编码和解码过程可自动进行。正是由于j a c q u i n 的贡献，为分形压缩编码 被人们所应用带来了转机，于是人们开始沿着j a c q u i n 提出的新思路，对分形编码 过程和解码过程进行深入的研究探讨，进一步完善了思路，并不断提出了新的算 法。 1 9 9 2 年，f i s h e r 针对压缩过程中图像剖分成p 区域过程中采用四叉树剖分方法， 水平和垂直剖分方法和三角剖分方法【2 3 1 。m o n r o 针对压缩编码过程中d 区域搜索 方式速度较慢加以了改进，提出b a t h 分形编码算法f 2 4 】【2 5 1 ，采用非线性的高阶映射， 代替原有的搜索匹配方式，但解码后的重建图像效果要差于j a c q u i n 算法。 近几年来，研究者开始尝试把分形方法与其他方法结合在一起，如将向量量 基于小波变换的分形图像压缩技术研究 化和分形编码方法结合起来，来提高编码效率。1 9 9 8 年，d a v i s 从小波变换域角度 分析了分形编码算、法【2 6 1 。目前，小波与分形结合方法多数是针对小波域进行分形 编码变换的。 1 5 本文结构 本论文共分7 章。 第l 章简要介绍了研究课题的现实意义、图像压缩的理论基础和编码方法的 分类以及评价图像压缩编码方法优劣的指标体系。 第2 章介绍了分形几何的基本理论，分析了分形理论的产生背景和研究现状。 分形作为一个崭新的理论，与常见的欧几里德几何有相当的不同。 第3 章系统归纳总结了分形图像压缩编码的理论基础，以及分形压缩编码的 具体实现方法和分形图像压缩编码的现状。 第4 章介绍了应用较广泛的小波变换理论以及小波变换编码，指出小波理论 在图像处理中的应用相当广泛，并介绍了小波变换理论中的一种图像编码方法及 其改进方案。 第5 章针对分形图像压缩编码中，加快编码速度以降低重建图像质量为代价 的缺点，提出了一个新方案，达到了既加快编码速度又提高重建图像质量的目的。 最后还引入了小波包分析的方法，并与分行压缩结合，拓宽了分形编码的思路。 本文最后对全文内容以及所做的工作进行了总结，同时对分形图像压缩编码 方法的实用化方向作了展望。 1 4 青岛科技大学研究生学位论文 2 1 分形简介 第二章分形理论基础 2 1 1 分形几何的基本概念 m a n d e l b r o t 于2 0 世纪7 0 年代创建的分形几何学( f r a e t a lg e o m e t r y ) 【2 7 】【2 8 】不 仅描述了存在于自然界中那些似乎很复杂的形态和模式，而且还提供了研究这些 形态和模式的数学模型。计算机图形学与图像处理技术为分形学提供了研究分形 物体的工具和手段，童话死分形学再用计算机显示、建模或模拟自然景物及各种 奇异形状中起着重要的作用。 下表指出了分形几何学与我们熟悉的欧几里德几何学相差甚远。 表2 - 1 分形几何与欧几里德几何的区别 t a b 2 - 1d i f f e r e n c e sb e t w e e nf r a c t a la n de u c l i dg e o m e t r y 分形儿何欧几里德儿何 发展历史2 0 多年2 0 0 0 多年 描述基础无特征尺寸对象的特征尺寸 适合对象自然形状人造 描述方式过程公式 以下是两个典型的分形的例子，画出了一个漂亮的蝴蝶( 图2 - 1 ) 2 9 】和分形树 ( 图2 2 ) 。自相似性是分形中的中心概念之一，它与维数的概念是密切相关的。 分形几何描述的对象是自相似的( 或统计意义上的相似) 。自相似性用分形维数 来描述。 若一自相似物由n 部分组成，每一部分的尺度均是整体的r ( r - i u ，r ) 。 2 - 5 ) p r u 当d 减小时，式( 2 5 ) 是增加的。当s 增加时，s 存在一临界值s ，使得日5 ( f ) 由 8 下跳至0 ，这个临界值s + 称为f 的h a u s d o r f f 维d h 。d h 维是应用最广泛的分维 之一。 ( 3 ) 盒维 定义2 1 2 设集合f c r “，记m ( f ) 是可以覆盖f 的、边长为e 的n 维立方 体( 记作s “立方体) 的最少个数，则f 的盒维d b 定义为( 当极限不存在时) d b l 删i m 等 协6 ) 所以，盒维与h a u s d o r f f 维一样，也是考虑f 的覆盖，只是可采用同样大小的 占一立方体。所以总有 磷岛 而盒维与h a u s d o r f f 维的关系是 d 8 巩 直线段的分维是1 ，对于分维大于1 小于2 的分形可想象为无限长的曲线挤 进有限的面积中。光滑曲面维数是2 ，对于分维大于2 小于3 的分形可想象为将 有限的面积挤进有限的三维空间中。 我们希望_ 个维数d 具有如下性质： 1 ) 单调性：若e c f ，则d ( e ) d ( f ) 。 2 ) 稳定性：d ( e u f ) = m a x d ( e ) ，d ( f ) 】。 1 9 基于小波变换的分形图像压缩技术研究 3 ) 仿射不变性：若f 是欧几里德空间的仿射变换，则d ( 九f 】) = d ( f ) 。 4 ) 李卜希兹不变性：若f 是双一李卜希兹函数，贝j j d ( f f ) = d ( f ) 。 设变换f ：x y 。若存在某个常数c ，使得 i f ( x ) 一( j ，) 阵c i x - y ix ，y x 则称f 为李卜希兹函数。若对0 c l c 2 o o ，有 c lix - y i 蚓f ( x ) - f ( y ) 喀c 2ix - yix , y x 则称f 为双。李卜希兹函数。 5 ) 可数集：若f 是有限的或可数的，则 d ( f ) = 0 6 ) 开集：若f 是r ”的开子集，则d ( f ) - - m 7 ) 光滑流行：若f 是m 维的光滑流行，则 d ( f ) 铀 不同的维数定义不一定具有上面的全部或某些性质，但所有的维数都是单调 的，大部分都是稳定的，所有平常的维数都是李卜希兹不变的、仿射不变的，而 d h 具有上面的所有性质。 2 2 度量空间、不动点、压缩映射 定义2 2 1 ( 度量空间) 设x 是一个空间或集合，d 是一个x x x 到r 的映 射，d ：x x x r ，若d 满足 ( 1 ) 非负性：d ( 毛j ，) o ，v x ，y x ；d ( x ，y ) = 0 当且仅当x = y 。 ( 2 ) 对称性：d ( x ，y ) = d ( y ，x ) 。 ( 3 ) 三点不等式：d ( x ，”+ d ( y ，z ) 2d ( x ，z ) ，v x ，y , z x ，则称d 为x 的度量。定 义了度量的空间x 称为度量空间，记为( x ，d ) 。 定义2 2 2 ( 度量等效) 空间x 上两个度量d 1 和d 2 是等效的，若存在常数 0 c l 0 ，使得 d ( 矗，力 n( 2 1 0 ) x 称为该序列的极限，记为 1 i m x = x ( 2 - 1 1 ) 1 - - t 0 0 定义2 2 6 ( 完备空间) 若x 中每个柯西序列都有一个极限x x ，则称该度 量空间d ) 为完备空间。r ，欧几里德度量，r * r ，欧几里德度量等都是完备度 量空间。 定义2 2 7 ( 子集极限点) 令scx 是度量空间( ) ( ，d ) 的一个子集，若存在点 s 的序列瓴 ：，使得l i m x - - - - - x ，则称点x x 为子集s 的极限点。 定义2 2 8 ( 紧集) 一个集合s 是紧集，若覆盖s 的任何一族开集都有一个 覆盖s 的有限子覆盖。 定义2 2 9 ( 紧急充分性) 令 d ) 为一个完备的度量空间，s cx ，则当且 仅当s 是闭的和完全有界的时候，s 是紧的。 定义2 2 1 0 ( b o r e l 集) 凡可以从开集出发，通过有限次运算，用取余集， 取有限个或可数个集合的并集或交集等方法得到的集合称为b o r e l 集，记作b 。 在度量空间( x ，d ) 的b o r e l 集上定义的测度u 为b o r e l 测度。 定义2 2 1 1 ( 不动点) 令厂：x 专x ，为空间的一个变换，l 吏f ( x y ) = x ，的点 x ，x 称为改变换的一个不动点。 定义2 2 1 2 ( 压缩映射) 设完备度量空间( x ，d ) 中的映射：x x ，若存在 一个正常数s 0 ) ，即 求一个压缩变换f f ，使d ( x i ，a t t ( f ) ) 占。 定理2 3 1 ( 完备度量空间的拼贴定理) 设( x ，d ) 为一个完备度量空间，x i 属 于x ，厂f + 是一个压缩因子为s 0 ，若 d ( x i ，f ( x i ) ) 占，nd ( x i ，口纡( 门) _ = 一 。 i j 定理2 3 1 表明，编码只需寻找这样一个压缩变换f f ，使得对艺x ， o ， 都有d ( 而，( 毛) ) 0 的非漫游点，这些点 服从一个近似的不变性方程 基于小波变换的分形图像压缩技术研究 一万一占 d ( x ，z ( x ) ) 万 ( 2 1 9