（信号与信息处理专业论文）基于自适应门限的快速分形编码方法研究.pdf

哈尔滨下稗人学硕十学位论文 摘要 随着互联网技术的迅猛发展，以图像为主的多媒体技术大大丰富了我们 的生活。但是如果没有一个高效的压缩方法，图像通信将不可能实现。图像 压缩编码的目的就是要以尽量少的比特数表征图像，同时又要保持复原图像 的质量，使它符合特定应用场合的要求。图像压缩也是多媒体技术的关键和 瓶颈之一。 到目前为止，图像压缩的研究己经产生了一些成熟的技术，如d c t 变换， 霍夫曼编码等，并且以这些编码为基础己形成了一系列的国际标准，如j p e g 、 j p e ( 卜2 0 0 0 、h 2 6 1 、h 2 6 3 、m p e g - 1 、m p e ( 卜2 、m p e g 一4 、m p e g - 7 等。 图像压缩编码技术目前又有了许多新的编码方法，如子带编码、小波变 换编码、利用分形几何的图像编码等等，尤其是分形编码，突破了原有编码 的界限，对于某些图像而言，有着其它传统压缩算法无可比拟的压缩比，引 起了人们的极大关注。 本文考虑了输入图像的特点，在f i s h e r 固定门限的基础上，给出了自适 应门限的计算推导过程，提出了门限与子块的方差成j 下比的自适应门限计算 的分形图像压缩方法，并在此基础上，利用方差减少候选块的数目。实验表 明，对同类图像该方法压缩时间短，还原图像p s n r 高，提高了分形压缩编 码效率，同时，本文方法由于固定了搜索窗，使编码时间具有了相对确定性， 有利于编码器的硬件实现。 分形与小波技术相结合是近几年的一个热点，本文最后提出了与小波编 码相结合的初步设想。 关键词：分形；图像压缩；自适应门限；四又树；方差 哈尔滨i ：稃人学硕十学何论文 a b s t r a c t w i t ht h ed e v e l o p m e n to fn e t w o r kt e c h n o l o g yq u i c k l y , t h em u l t i m e d i a t e c h n o l o g yb a s e do ni m a g ee n r i c h e so u rl i v e s h o w e v e ri ft h e r ei sn oh i g h l y e f f e c t i v ec o m p r e s s i o na p p r o a c h ，i m a g ec o m m u n i c a t i o nc a l ln o tb ea c h i e v e d t h e p u r p o s eo fi m a g ec o m p r e s s i o nc o d i n gi st or e p r e s e n ti m a g e sw i t hf e wb i t s ， m a i n t a i nt h eq u a l i t yo fr e c o v e r i n gi m a g e sa c c o r d i n gw i t ht h er e q u i r e m e n t so f c e r t a i na p p l i c a t i o ns i t u a t i o n s i m a g ec o m p r e s s i o ni st h ek e ya n db o t t l e n e c ko f m u l t i m e d i at e c h n o l o g y u pt on o w , s o m em a t u r et e c h n o l o g i e sh a v eb e e nd e v e l o p e di nt h ea r e ao f i m a g ec o m p r e s s i o n ，s u c ha sd c t ( d i s c r e t ec o s i n et r a n s f o r m ) a n dh u f f m a nc o d e m o r e o v e r , as e r i e so fi n t e r n a t i o n a ls t a n d a r d s ，s u c ha sj p e g , j p e g 2 0 0 0 ，h 2 6 1 ， h 2 6 3 ，m p e g 一1 ，m p e g 一2 ，m p e g 一4a n dm p e g 一7 ，h a v eb e e nf o r m e do nt h eb a s e o ft h e s ec o d i n ga l g o r i t h m s r e c e n t l y , m a n yn e wc o d i n gm e t h o d sh a v eb e e np r o p o s e d ，s u c ha ss u b b a n d c o d i n g ，w a v e l e tt r a n s f o r mc o d i n ga n df r a c t a li m a g ec o d i n g ，e t c f r a c t a li m a g e c o d i n gg e t so u rg r e a ta t t e n t i o nb e c a u s ei tb r e a k st h el i m i to fp r e v i o u sc o d i n ga n d o b t a i n st h em a x i m u mc o m p r e s s i o nr a t i oc o m p a r i n gw i t ho t h e ra l g o r i t h m s t h ep a p e rh a s c o n s i d e r e dc h a r a c t e r i s t i c so ft h ei n p u t i m a g e ，g i v e nt h e c a l c u l a t i n gp r o c e s so ft h ea d a p t i v et h r e s h o l d ，a n dp r o p o s e daf r a c t a li m a g ec o d i n g a l g o r i t h mo ft h r e s h o l db e i n gi nt h ed i r e c tr a t i ot ot h ec h i l db l o c kv a r i a n c eb a s e d o nf i s h e rf i x e dt h r e s h o l d t h en u m b e ro fc a n d i d a t eb l o c kc o u l d b er e d u c e d b e c a u s eo ft h ev a r i a n c e e x p e r i m e n t a lr e s u l t si n d i c a t et h a tt h ec o d i n gt i m ei s s h o r t e n e d ，t h ep e r f o r m a n c eo fp s n ro fr e c o v e r e di m a g ei si m p r o v e d ，a n dt h e e f f i c i e n c yi si n c r e a s e d d u et ot h es e a r c h i n gw i n d o wo ft h i sm e t h o db e i n gf i x e d ， t h e c o d i n g t i m eh a sr e l a t i v e d e t e r m i n i s m ，w h i c hb e n e f i tt h eh a r d w a r e i m p l e m e n t a t i o no ft h ee n c o d e r c o m b i n a t i o no ft h ef r a c t a li m a g ea n dw a v e l e ti sp o p u l a ri nr e c e n ty e a r s ，s o t h ep a p e rp r o p o s e st h et e n t a t i v ei d e a so nt h ec o m b i n a t i o no ff r a c t a li m a g ea n d w a v e l e tc o d i n ga tl a s t k e yw o r d s ：f r a c t a l ；i m a g ec o m p r e s s i o n ；a d a p t i v et h r e s h o l d ；q u a dt r e e ；v a r i a n c e 哈尔滨工程大学 学位论文原创性j 声明 本人郑重声明：本论文的所有工作，是在导师的指导 下，由作者本人独立完成的。有关观点、方法、数据和文 献等的引用已在文中指出，并与参考文献相对应。除文中 己经注明引用的内容外，本论文不包含任何其他个人或集 体已经公开发表的作品成果。对本文的研究做出重要贡献 的个人和集体，均已在文中以明确方式标明。本人完全意 识到本声明的法律结果由本人承担。 作者( 签字) ：亟壹 日期：知四年3 月1 1 日 哈尔滨i - l ：t 人学硕十学何论文 第1 章绪论 1 1 课题研究的背景和意义 数据压缩的思想起源很早，汉语中的文言文是典型代表。在我国古代， 充满智慧的祖先使用言简意赅的文言文表达各种思想。通常，短短数字、寥 寥数语就能表达十分丰富的思想，这充分表明，文言文中字符的信息冗余被 降低到了最小程度。因此，文言文是消除数据冗余以压缩数据思想的生动体 现。 自2 0 世纪8 0 年代以来，计算机在各行各业和社会生活的各个方面得到 普遍应用，并已广泛应用于数据处理与数据通讯。但是，按普通实验室与家 用电脑的配置，资源紧张的问题始终是一个不容忽视的难题。存储容量的限 制、带宽的制约以及网上信息交流的剧增，与有限的传输能力和有限的存储 资源形成了一对很难调和的矛盾，这是当今信息社会的技术瓶颈之一，这迫 切需要各种大量节省传输时间与存储容量的数据压缩技术。在保持一定质量 的前提下提高压缩比，始终是科技工作者寻找新的数据压缩方法的动力。 特别是9 0 年代以来，应用多媒体技术的发展成为计算机系统的时代特 征。简单地说，多媒体技术就是指用计算机综合处理文字、声音、图形、图 像等多种媒体上承载的信息，而图像是其中最主要的信息载体。“百闻不如一 见”这条谚语道出了人类感知语言信息与视觉信息的能力的本质差异，也充 分反映了信息的图像载体存在很多适合于人类视觉系统的优点。因此，许多 离散、有限和结构化的数据常常通过图像得以形象化的表达，从而得到更好 的处理。然而，即使在压缩格式( 如j p e g ) 下，图像也需要巨大的存储空间 和较长的传输时间。例如，存储一幅5 1 2 x 5 1 2 x 8 灰度图像( 按今天的标准， 这不是很高的分辨率) 约需2 5 6 k 的容量；如果是高分辨率彩图，容量需求 更大。尽管多媒体等信息系统涉及数据压缩等方方面面的问题，每个问题都 很重要，但以较少的空问储存海量文件( 如图像) 的压缩是解决数据有效传 输与储存的关键问题。随着多媒体应用的日益增多，如何高效、实时地压缩 图像是多媒体技术中最关键的问题之，图像压缩技术已经成为一个十分重 哈尔滨t 程大学硕十学何论文 要的研究领域。 近二十年来，i e e e i e e 等所属国际著名刊物发表了数以万计的图像压缩 方面的论文，还设有几种有关图像压缩的专刊，这充分说明，图像压缩编码 是当前十分活跃的研究领域。总之，随着多媒体应用的日新月异，发展新的 图像压缩技术已成为十分重要的研究课题。可以预见，图像压缩技术将会是 正在建设的数字信息化社会所依赖的主要技术基础之一。 目前，图像压缩方法已有近百种，但是，压缩效果、压缩比以及编、解 码时间还不能满足信息时代发展的要求。传统的压缩算法如霍夫曼编码等， 压缩比在2 ：1 到5 ：1 ，已经成了定式，发展潜力不大。分形图像编码是近年来 出现的一种新型图像编码方法，它以新颖的分形几何理论为基础，具有潜在 的高压缩比和优良的重建图像质量，因而倍受人们关注。目前分形图像编码 已经成为图像压缩编码研究中的热点。分形编码有许多优点，它以迭代函数 系统理论( i f s ) 为基础，突破以往熵压缩编码的界限，在编码过程中，采用了 类似描述的方法，能达到很高的压缩比。解码是通过迭代完成的，具有与分 辨率无关( r e s o l u t i o ni n d e p e n d e n t ) 的解码特性。 二十世纪后二、三十年，计算机技术和网络技术取得了飞速的发展，人 类社会进入到了前所未有的信息化时代。随着信息时代的来临，人们对通信 业务的要求不断增长，在日常生活中，大量的信息数据需要传输、存储和处 理。科学实验表明，人类从外界获取的知识之中，有8 0 以上都是通过视觉 感知获取的。眼睛获取的是图像信息，和语音、文字等信息相比，图像包含 的信息量更大、更直观、更确切，因而具有更高的使用效率和更广泛的适应 性，一幅图胜过千言万语，图像信息是人类认识世界、自身的重要源泉。所 以在信息数据中，绝大部分数据都是图像数据，而图像数据的传输常常要占 用很大的带宽，需要很大的存储空间，因而怎样对图像数据进行行之有效地 传输是一个极具挑战性的课题。数字图像中包含的数据量十分巨大，如在视 频传输中p a l 制式( 2 5 帧秒) 下，画面分辨率为6 4 0 4 8 0 下，真彩色( 2 4 位) 的图像序列，播放1 秒钟的视频画面数据量为：6 4 0 x 4 8 0 x 3 x 2 5 = 2 3 ，0 4 0 ，0 0 0 字节，相当于存贮一千多万个汉字所占用的空间。如此庞大的数据量，给图 像的传输、存贮、传输线的传输率( 带宽) 以及计算机的处理速度等增加了巨 大的压力。再如在地球资源卫星传输图像数据时，它的一帧( 四幅) 图像将 2 哈尔滨1 ：稃人硕十学位论文 达到2 0 0 多兆比特，这些图像数据都是储存在卫星的磁性记录体中，当卫星 飞过地面接收站的有效接收区域时，要快速将这些数据发送下来，但这个时 间段是有限的，若不能迅速地将这些数据发送完，则必须建立更多的接收站， 或提高传输速度，这样势必增加技术难度和复杂性，增加成本。由此可见， 对降低传输成本，增加数据传输的可靠性，不断满足人们对信息传输的需求， 图像压缩都具有十分重要的作用。为了解决好这个问题，我们就必须对图像 进行编码压缩，在保证一定图像质量的前提下，有效地减少传输时所需的数 据量和占用的频带。 图像压缩就是在没有明显失真的前提下，将图像的位图信息转变成另外 一种能将数据量缩减的表达形式，即去除冗余信息。首先，尽管图像中数据 量很大，但其行、列以及帧间都具有极强的相关性或冗余信息，即一个象素 的灰度值，总是和它周围的象素的灰度值有着某种关系，可以由它们推算表 示出来，应用某种方法提取或减少它们之间的这种相关性，即可实现图像压 缩；其次，大部分图像视频信号的最终接收者都是人眼，而人类的视觉系统 是一种高度复杂的系统，它能从极为杂乱的图像中抽象出有意义的信息，并 以非常精练的形式反映给大脑。人眼对图像中的不同部分的敏感程度是不同 的，如果去除图像中对人眼不敏感或意义不大的部分，对图像的主观质量是 不会有很大影响的，也实现了图像压缩。正由于图像压缩的必要性和可能性， 图像压缩编码研究成为一个越来越活跃的领域，在诸如基于i n t e m e t 的多媒 体通信、可视电话、数字电视和多媒体计算机等领域得到了广泛的应用。 1 2 图像压缩的方法 图像压缩编码的方法很多，其基本技术的发展可分为两个阶段，即第一 代图像编码技术和第二代图像编码技术p 。 第一代图像编码技术是以香农的信息论为基础，并充分考虑了图像信源 的统计特性根据其核心技术的不同又分为预测编码、变换编码和统计编码。 预测编码：指只对新的信息进行编码从而去掉相邻像素之间的相关性和 冗余性。常用的方法有增量调制( d e l t am o d u l a t i o n 简称d m ) 、差分脉冲编 码调帛i j ( d 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 ，简称d p c m ) 。 变换编码：指将给定的图像变换到另一个数据域( 如频域) 上使得大量 哈尔滨t 程大学硕十学位论文 的信息能用较少的数据来表示。常用的方法有：离散傅立叶变换( d f t ) 、离散 余弦变换( d c t ) 、离散哈达玛变换( d h t ) 。 统计编码：指根据信息码字出现概率的分布特征进行压缩编码寻找出现 概率与码字长度间的最优匹配。常见的霍夫曼( h u f f m a n ) 编码以及算术编码 ( a r i t h m e t i c c o d i n g ) 编码、香农费诺( s h a n n o n f a n o ) 都属于统计编码。 第二代图像编码技术不再局限于香农的信息论框架，它充分地利用人眼 的视觉生理特性和图像信源的各种特征以获得更高的压缩比和主观满意度。 第二代图像编码技术主要分为两类： l 、考虑人眼视觉特性的方法：基于方向滤波的图像编码方法、基于图像 轮廓一纹理的编码方法。 2 、考虑图像景物特征的方法：分形编码方法、基于模型的编码方法等。 1 3 图像质量的性能评价 图像质量是评价图像压缩编码方法的最为重要的标准之一，它包括两方 面的含义：一方面是图像的逼真度，即恢复图像与原始图像的偏离程度；另 一方面是图像的可懂度，即图像能向人或机器提供特征信息的能力。对于失 真编码，原图像与重建图像之间存在着差异，差异的大小意味着恢复图像的 质量不相同。但是，由于人的视觉冗余度的原因，对有些差异的灵敏度较低， 这就产生了两种判别标准：一种是客观判别标准，它建立在原始图像与重建 图像之间的误差上；另一种是主观评价标准，通过用人的肉眼对图像打分而 得到。 1 3 1 主观评价 主观评价采用平均判分m o s ( m e a no p t i o ns c o r e ) 或多维计分等方法进行 测试，所评价出的图像质量不仅与图像本身特征有关，也与观察者特性以及 观察者的环境条件有关。组织一群足够多( 至少应有2 0 名) 的观察者( 包括一般 观众及专业人员) ，通过观察来评定图像的质量。观察者将重建图像与原图像 相对比，比较损伤程度，利用表1 1 所示的图象质量主观评价尺度表，给评 定的图像打上一定的质量等级，最后用平均的方法得到图像的分数。这样的 评分虽然很花时间，但比较符合实际。 4 哈尔滨i ：程人学硕十学何沦文 表1 1 图像质量主观评价尺度表 质量尺度妨碍尺度 非常好丝毫看不出图像质量变坏 好能看出图像质量变坏，但并不妨碍观看 一般能清楚地看出图像质量变坏，对观看稍有妨碍 差对观看有妨碍 非常差非常严重地妨碍观看 1 3 2 客观评价 对图像质量进行定量描述是一个比较复杂的问题，进展比较缓慢，一方 面是因为人们还没有充分了解视觉感知的过程和方法；另一方面是由于图像 是多维信号，很难用确定的几个统计参数来表示其特征。彩色图像由于量纲 数增多，而且必须满足人眼对彩色的视觉感知，因此对彩色图像逼真度进行 定量表示是一个更加复杂的问题。目前应用得较多的是对灰度级图像逼真度 的定量表示。一个合理的尺度应该与图像的主观测试结果相吻合或密切相关， 要求便于计算分析而且简单易行。 设原始的二维灰度图像为a = f ( i ，) 其中i = 1 ，2 ；户1 ，2 彤，经压缩 重建后的图像为a 7 = f ( f ，j ) 。可以用以下几种指标来评价图像的质量。 1 、均方误差： 脚2 高f 至1 ，至1 ( 厂w m 2 1 - 1 2 、规范化均方误差： 一= 等，。2 = 嘉兰争“力 m 2 ， 仃，。 ， 朋：一1 ：一1 3 、对数信噪比： 盯f 。 s n r = 1 0 l o g 上= - 1 0 l o g n m s e ( d b )( 1 3 ) 。m s e 、7 哈尔滨t 程人学硕十学何论文 4 、峰值对数信噪l l - 删= 1 。l 。g 面2 5 5 2 ( 招) 5 、压缩l l = 压缩后图像的比特数压缩前图像的比特数 6 、压缩率= 1 压缩比 ( 1 - 4 ) ( 1 5 ) ( 1 - 6 ) 可以看出，以上的评价完全取决于原始图像与重建图像每个像素上灰度 值的误差，这种评价在主观感觉上也有一定的参考意义。常用的客观评价指 标为p s n r ，当p s n r 超过3 0 d b 时，人的主观感觉一般很难找出其差异。 主观评价与客观评价之间有一定的联系，但不能完全等同，客观评价比 较方便，很具有说服力，由于主观评价很直观，比较符合人的视觉效果及实 际，故在制定国际标准时常被采用。 1 4 分形图像压缩编码的发展概况 分形理论是欧氏几何相关理论的扩展，它描述了自然界中物体的自相似 性，这种自相似性可以是确定的，也可以是统计意义上的。分形理论已成为 非线性科学研究中一个十分活跃的分支，并已广泛应用于数学、自然科学和 社会科学等众多领域中。近十几年来，分形在计算机图形学、计算机视觉以 及图像处理与分析等领域中显示出越来越重要的作用。 分形编码是在m a n d e l b r o t 分形几何理谢4 1 的基础上发展起来的一种编码 方法，其理论基础是迭代函数系统p 1 ( i t e r a t e df u n c t i o ns y s t e m s ，简称i f s ) 。分 形图像编码技术建立在自然图像中存在的局部自相似性的基础上，用一个压 缩变换的参数来表征图像。这个压缩变换由一组作用于图像子块的映射组成， 揭示了图像存在的局部自相似性。由于存储仿射变换量化参数的比特数远远 低于储存原始图像的比特数，所以能够实现图像数据的高倍压缩。分形解码 采用新颖的快速迭代过程，重构图像由压缩变换迭代作用于任何初始图像来 生成。然而，如何寻求一个压缩变换，使其不动点图像就是待编码图像的较 好逼近，这是分形图像编码技术最基本的问题。 1 9 8 7 年，巴恩斯利( m e b a m s l e y ) 首次提出分形图像压缩的概念峥1 1 ，其方 法是将迭代函数系统理论应用到图像压缩编码中，对几幅彩色图像及一个女 孩图像获得了1 0 0 0 0 ：1 的高压缩比，并获得u s 专利睁1 ，从而使分形图像压缩 6 哈尔滨t 程大学硕十学位论文 编码方法以其潜在的高压缩比和良好的重建图像质量受到广泛关注。b a r n s l e y 提出了带概率的迭代函数系统( i f s p ) ，采用初始点经压缩变换的参数q ，加 上伴随概率p i 进行迭代，所得到点集的分布类似于灰度值的效果，但在编码 方面却未给出任何具体的算法。其大致步骤为：将原图预分解为若干个分形子 图，使得子图具有一定的分形结构，即子图的整体与局部之间存在某种自仿 射特征：分解可采用其他的图像处理手段，且由大量的这些子图组成了分形 库，每个子图可在这些分形库中找到它们的匹配子图编码。这样，对图像的 分形编码可转化为图像分割，到库中寻找匹配子图的编码，最后扔掉原图， 保存子图编码，进行存贮或传输。然而，b a m s l e y 的方法是有经验的图像处 理专家基于人机交互进行的，对操作者有较高要求，寻找图像整体与局部的 自相似性极其困难。首先，对于图像的子图分割本身，还没有一种计算机自 动分割的办法；其次，分形库的规模大，没有统一的建库办法；最后，高压 缩比编码搜索的过程是以费时费力为代价，难以实现自动压缩，由于以上原 因，使得该方法实用性不强。 现实生活中的大多数图像是非严格自相似的图像，不具有整体和局部的 自相似性，严格分形图像在现实生活中只占极小的部分。1 9 9 0 年，b a r n s l e y 的学生简库恩( a e j a c q u i n ) p 。1 2 1 在其博士论文中首先提出了局部迭代函数系 统( l o c a li t e r a t e df u n c t i o ns y s t e m ，简称l i f s ) 。该方法利用图像局部间的相 似性，实现了全自动分形图像压缩编码3 1 ，使分形图像压缩向实用化迈出了 坚实的一步。该方法以局部的仿射变换代替全局的仿射变换，是基于图像划 块的图像压缩方式。j a c q u i n 的方法解决了人机交互问题，是一种相对实用的 方法，但是这种编码仍然存在许多实际问题，如复杂的匹配库搜索，使编码 计算量极大，编码时间过长；编码质量不是很理想，存在方块效应；对图像 进行压缩编码时，所得到的压缩比与理论上理想的效果差距太大等，从而影 响了其实用性。尽管如此，分形编码还是以其新颖的思想、高压缩比、与分 辨率无关以及快速解码等优点受到技术界的广泛关注。分形编码技术、小波 编码技术与模型编码技术起成为公认的三种最有前途的新一代图像编码技 术。 从这以后的研究工作都是对j a c q u i n 算法的研究和改进。如f i s h e r 4 1 等 人对算法进行了改进，提出一种根据亮度及对比度变化来分类的方法，匹配 7 哈尔滨l ：稃人学硕 ：学位论文 搜索时只在同类中进行，有效地减少了匹配搜索的时间。h u r t g e n 1 把矩形块 分为4 个象限，每一个象限对应一个比特位，如果该象限的亮度均值大于整 个块的亮度均值，就给对应象限的比特位置1 ，否则就置0 。这样，共有1 5 类，然后同样用方差在图像块中出现的顺序来实现分类得到2 4 个子类，于是 一共得到3 6 0 个类，同样减少了编码时间。 纵观国内外大量分形图像编码文献，在加快分形编码速度编码和重建图 像质量等方面，提出了许多新观点和改进算法p 川。在国内，分形编码研究 虽然起步较晚，但近年来研究也相当活跃，几乎涉及分形压缩编码研究的各 个方面。如在快速分形图像编刮2 5 。2 6 1 、图像理解口7 - 2 们、分形与其它方法相结合 1 3 0 - 3 q 、d c t 域分形编码研究3 2 q 3 1 、自适应分块的快速分形图像压缩m 1 、基于预 测模型的分形图像压缩编码p 5 1 、基于小波变换的分形视频编码、使用l i f s 的 静态图像编码等方面的研究。 在诸多图像压缩理论中，分形图像压缩方法以其独特新颖的思想r 益受 到人们的关注，成为当今图像压缩领域中最新的方法之一。1 9 9 2 年，美国微 软公司采用分形图像压缩技术，成功研制出了一张光盘“m i c r o s o t te n c a r t a ， 仅用6 0 0 m b 的容量，就存贮了大量的文字数据、长达7 小时的声像资料、1 0 0 部动画片、8 0 0 张彩色地图和1 0 0 0 幅逼真的风景照片，获得了很高的压缩比 和很好的解码图像视觉效果，这充分显示了分形图像压缩技术广阔的应用前 景和发展潜力。 1 5 本论文的研究内容及章节安排 在参考国内外大量分形理论及其在图像压缩研究方面应用的文献的基础 上，本文首先对分形的基本理论以及分形图像压缩编码的基本原理进行了研 究，并阐述了在分形图像压缩中起着重要作用的迭代函数系统( i f s ) 以及基本 的分形图像压缩编码方法。介绍了f i s h e r 的固定门限四叉树方法，此方法的 门限值一般由实验者的经验来设定，门限值的微小变化会对实验结果产生极 大的影响，同时也决定了分形图像编码的效率。如何自动获得相应子块的门 限值，是目自 分形图像压缩中的技术难点之一。本文给出了自适应门限的计 算推导过程，提出了门限与子块的方差成j 下比的自适应门限计算的分形图像 哈尔滨i ：稃人学硕十学何论文 压缩方法。并在此基础上，利用方差减少候选块的数目，通过计算机仿真， 在同等的环境下，本文算法编码时间减少，还原图像质量提高。 本文内容安排如下： 第1 章简要地介绍课题的研究背景和意义，以及图像压缩的评价标准， 接着介绍了分形图像编码的概念及主要内容。 第2 章介绍分形图像编码的数学基础，主要包括迭代函数系统、b a n a c h 不动点定理和拼贴定理。 第3 章介绍利用迭代函数系统理论来进行图像压缩编码的具体实现方 法。 第4 章主要介绍f i s h e r 自适应门限算法和本文算法。 第5 章介绍小波与分形相结合的快速分形解码算法。 9 哈尔滨i j 程人学硕十学位论文 第2 章分形及分形编码的数学理论 2 1 引言 迭代函数系统、不动点理论以及拼贴定理是分形编码的主要数学基础。 迭代函数系统( i t e r a t e df u n c t i o ns y s t e m ，i f s ) 是b a m s l e y 及其研究小组在 h u t c h i n s o n p q l 9 8 1 年提出的迭代函数理论( i t e r a t e df u n c t i o nt h e o r y ) p 的基础 上发展起来的，它是分形几何的重要组成部分，不动点理论是泛函分析的重 要分支p 8 。3 铂，拼贴定理是b a n a c h 不动点定理的简单推论，并成功地用于集合、 函数( 包括信号、图像) 等的逼近。 基于i f s 的分形图像编码可以获得极好的压缩性能p 6 。删，能够实现很高 的压缩比，其实质是假设现实图像具有自相似性( 分形的典型特征) 来实现图 像数据压缩的。尽管从概念的观点上看，分形编码原理是容易理解的，但是 为了叙述严谨、清晰、坚实可靠而明确的数学描述是绝对必要的1 。此外， 要了解分形编码技术的起源，以及理解该技术的工作原理、分形的概念、度 量空间、不动点理论和拼贴定理是必不可少的。 总之，分形图像编码是分形几何、泛函分析等现代数学分支最成功的应 用之一。这充分说明，一些复杂的数学理论，尽管难于理解，但往往能为图 像处理等技术提供意想不到的合理方法。 2 2 分形概述 1 9 7 5 年以来，法国数学家b b m a n d e l l b r o t 发表了几本专著，标志着“分 形 作为一门科学正式成立h 2 1 。分形理论涉及的领域非常广泛，其应用已经 深入到许多应用领域。“分形”已成为当代科学中最有影响力和感召力的基本 概念之一，分形理论也成为非线性科学的生长点之一。分形理论的基础和主 要内容是分形几何，分形几何的研究对像是理论和现实中不规则的几何图形。 例如，曲折的海岸线、多变的云彩图案、参差不齐的金属表面及涨落无常的 股价曲线等等这些经典几何对之束手无策的现像和状态，均可用分形几何加 以描述、解释和研究，分形几何的核心概念之一就是分数维和局部与整体的 对称性( 自相似性) 。分形集还为研究混沌动力系统的“奇怪吸引子”提供了 1 0 哈尔滨t 程大学硕f ：学何论文 直观的几何语言。近十几年来，分形几何学已成为探讨复杂和无序现像的强 有力的数学工具，被各个学科分支中的学者们广泛应用着，它同孤立子理论、 混沌理论一起被誉为二十世纪后期的非线性科学的三大理论突破。 分形理论大致可分为三个阶段。第一阶段为1 9 2 5 年以前，该阶段发现了 一些典型分形集合，同时为了刻画这些集合的性质，产生了h a u s d o r f f 钡l j 度和 h a u s d o r f f 维数；这些概念说明了度量一个无特征长度( 所谓特征长度是指所 考虑的集合对像所含有的各种长度代表者) 的几何对像时，必须依赖度量方式 和度量的尺度单位。第二阶段是从1 9 2 6 年到1 9 7 5 年，在这半个世纪中，人 们对分形的性质作了较为深入的研究，特别是维数理论的研究已获得了丰硕 的成果，在此期间，产生了覆盖维数和熵维数等概念。第三阶段是从1 9 7 5 年至今，在此期间，分形理论和应用都取得了全面发展，分形几何作为一门 学科正式诞生。在分形理论方面，维数的估计与计算的算法、分形集的生成 与结构、分形的随机理论、动力系统的吸引子理论与分形的局部结构已获得 较深入的研究结果。在应用方面，分形在物理的相变理论、材料的结构与控 制、力学中的断裂和破坏、高分子链的聚合。模式识别、自然景物的模拟、 酶的生长模拟等领域取得了令人瞩目的成果。当计算机科学特别是计算机图 形学应用到分形领域后，它为分形的研究提供了必要的、有效的工具，并且 促使分形理论和应用有更多的新发现。 说到分形，人们会列举一大堆描述它的基本特性，如任意尺度下都显示 细节、有某种自相似结构、“维数 可以是分数等等，但究竟什么是“分形” 恐怕谁也说不清楚，因为目前还没有公认的严格明确的定义，只能对它的特 征进行一些描述。 粗略地说，分形是对没有特征长度但具有一定意义下的自相似图形和结 构的总称，这里特征长度可以理解为刻画一个几何体特征的长度( 如直径就是 一个球的特征长度) 。m a n d e l b r o t 的“f r a c t a l ”是“破碎的，不规则的”之意， 它描述的几何体不同于一般的欧氏几何体。他曾建议将“分形”定义为整体 与局部在某种意义下具有自相似i 生( s e l f - s i m i l a r i t y ) 的集合，也曾把“分形”定 义为h a u s d o r f f 维数严格大于拓扑维数的集合。但是这些定义都不够精确、不 够全面，因为按照这些定义，有些明显应算是“分形”的集合被排除在外。 英国数学家f a l c o n e r 认为“分形”的概念可以按生物学中对“生命”概 哈尔滨工程大学硕十学位论文 念的类似方法处理。在生物学中“生命”并没有严格和明确的定义，但却可 以列出一系列生物体的特征，如繁殖能力、运动能力以及对周围环境的相对 独立的存在能力等等。虽然有一些生物例外，但大部分生物都具有上述特征。 同样，我们也可以不寻求分形的确切简明的定义，而寻求分形的特性。于是， 分形可以看作是具有或部分具有下列典型性质的复杂集合m ： 1 、具有精细的结构，即有任意小尺度比例的细节，或任意尺度下都显示 细节； 2 、非常不规则，它的整体和局部都不能用传统的几何语言来描述； 3 、通常有某种自相似的结构，可能是近似的或是统计的； 4 、一般地，以某种方式定义的“分形维数大于它的拓扑维数。 在大多数令人感兴趣的情形，可用非常简单的方法定义，也可能迭代产 生，其中，自相似性与分形维数是分形的两大显著特征。 2 3 分形编码的数学理论 2 3 1h a u s d o r f f 距离与分形空间 分形理论及其应用问题的研究，总是在一个假定的理想空间中进行的， 一个完备的度量空间常常能够满足我们的要求。 定义2 1一个度量空间陇力是由一个空间或一个非空集合疋以及其 上的一个实值函数d ：x x x - , r 组成，d 即为定义在此空间上的度量，具有如 下性质： l 、讹力却，v x , y e x ( x , d ) 2 、m = o ，当且仅当萨弘v x , y e x 3 、d 0 力气炒为，v x , y e x 4 、d 0 + d ( y z ) 瓠 z ) ，v x , y , z x 定义2 2如果度量空间力中所有的柯西序列都是收敛序列，则称 回为完备度量空间。 定义2 3 设陇力为一完备度量空间，记为h ( x ) = s i s 是x 的紧子集且 s 幻l ，给定b e h ( x ) 及x 兄记m 月) 为点x 到集合b 的距离，其定义如下： d ( x , b ) 2m i n d ( x , y ) v 艿) ( 2 - 1 ) 定义2 4设a 声e h ( x ) ，记d ( a 口) 是从集合么到集合召的距离： 1 2 哈尔滨一【：程人硕十学位论文 d ( a , b ) - - m a x d ( x , b ) x 彳)( 2 2 ) 由上面定义的距离，我们可以得到d ( a 声) 烈曰4 ) ，即不满足交换率，因 此，如上定义的距离不是川上的一个度量，我们定义h a u s d o r f f 距离如下： 定义2 5 设仪回为一完备度量空间，彳声e h ( x ) ，记( 彳，b ) 为彳和b 的h a u s d o r f f 距离，定义如下： ( 彳，曰) = m a ) 【 d 似月) ，以b 4 ) ) ( 2 - 3 ) 根据这个定义，显然有( 彳，b ) = r 2 ( 彳，b ) 。 定理2 1h a u s d o r f f 距离是川上的一个度量，称为h a u s d o r f f 度 量，因此称( h ( j o ，) 为h a u s d o r f f 度量空间。 定理2 2 设仪回为一完备度量空间，则h a u s d o r f f 度量空间，) 也是一个完备度量空间。 ( 脚，) 称为分形空间，对分形的讨论均在这个空间下进行。 综上所述，在实平面上尺2 定义了度量d 的完备度量空间( r 2 ，力上的集合 族组成的，定义了h a u s d o r f f 距离的空间( 瞰r 2 ) ，) 也是一个完备的度量空 间。在本文中，我们研究的图像就是定义在实平面上的点集，即是俄r 2 ) 的 元素，因此，r 2 ) ，) 就是图像存在的空间。 2 3 2 仿射变换 仿射变换是一类重要的变换，n 维欧氏空间r ”中的仿射变换w ：x ”呻， 具有下面的形式： w ( x ) 利+ 6 0 r ”)( 2 - 4 ) 其中a 是r ”上的线性变换，而b 是r ”中的一个矢量，因此，仿射变换 是平移、旋转、伸缩以及反射的组合。相似变换是仿射变换的特例，与相似 变换不同的是，仿射变换在不同的方向上有不同的伸缩比。 定义2 6一个变换w ：r 2 峥r 2 如果具有下列形式： w ( ；) = ( ：三 ( ； + ( 其中a , b ，c ，d , e 和厂是实数，则称w 是仿射变换， 是压缩的，该仿射变换就是压缩的。 ( 2 5 ) 这样，当它的线性部分 哈尔滨一r 秤大学硕十学位论文 平面线性变换有四种特例，具有明显的几何意义，即4 一按比例缩放， 4 一伸长，4 一剪切，4 一旋转，如图2 1 所示。 i j叭 爻9 一 小 铲口 小_ 习 ? ) ： 铲( 篇：髫) 图2 14 种特殊的线性变换 还可以证明，任一平面仿射变换都可分解为这四种变换的乘积。 2 3 3 压缩映射及其不动点 定义2 7设( x , a 9 为一完备度量空间，w 为定义在其上的一个映射( 仿 射变换) ，如果有0 叠 1 使得下式成立 以w i ，w o o ) a d ( x ，力，v x ，y x( 2 6 ) 则称w 为空间x 上的一个压缩映射，s 为压缩因子，且此压缩映射是连续的。 定理2 3 ( 压缩映射定理)设( x 力为一完备度量空间，w ：加x 是x 上 的一个压缩映射。则w 存在唯一的不动点h ，即w ( x d = x 。，且对任意的x z 序列 w n ( x ) ：甩= o ，1 ，2 ，) 收敛到x 。 1 4 哈尔滨_ t ：程人学硕十学位论文 引理2 1设w x - - , x 是度量空间陇田上的一个压缩映射，压缩因子为 s ；，h a ) 是由x 的非空紧集构成的h a u s d o r f 空间，为h a u s d o r f f 度量。 则下面定义的映射w ：坝炉爿是，) 上的压缩映射，压缩因子也为s - w ( 功= w o ) 了曰 ，v b 爿- ( x )( 2 - 7 ) 引理2 2 设 ：，l = 1 ，2 ，朋是( 川，h a ) 上的一组压缩映射，对每个 刀，嵋的压缩因子为s 。，定义w ：娥。驴日， w ( b ) = w ( b ) u w 2 ( 曰) u u w u ( b ) ，v b e n ( x )( 2 - 8 ) 则w ：聊脚是一个压缩映射，压缩因子s - - m a x s 。：，l = 1 ，2 ，朋压缩映射 定理说明，一个完备度量空间上的压缩映射有唯一的吸引子，图像空间 似r 2 ) ，) 是一个完备度量空间，因此，对似r 2 ) ，) 上的压缩映射国，其 唯一的不动点瓦，就是平面上的一幅图像，而且对平面上任意一幅初始图像， 反复使用压缩映射缈，经过一定次数的迭代以后，就形成唯一的一幅图像， 该图像决定于压缩映射缈，而与初始图像无关，这一性质在分形图像压缩的 解码过程中有非常重要的应用，是分形图像压缩解码过程的基础。 2 3 4 迭代函数系统、吸引子、拼贴定理 按照经典的欧氏几何和黎曼积分的观点，分形是复杂的不规则的集合， 然而，分形又是具有精细结构的集合图形。许多分形可以通过简捷的构造过 程得出，这种构造过程或是递归的、或是迭代的。为了更好地了解分形的结 构特怔，需要引进迭代函数系统的概念，可以看到，一个确定的分形是一个 迭代函数系统的不变集。 定义2 8迭代函数系统是完备度量空间( x 力上的一组有限的压缩映 射嵋妇x , n = l ，2 ，每个压缩映射比的压缩因子是s 。，常用i f s 来表示 迭代函数系统( i t e r a t e df u n c t i o ns y s t e m ) ，记为懈比，n = 1 ，2 朋。 定理2 4 ( 吸引子定理)设 置嵋，n = l ，2 ，朋是一个迭代函数系统， 压缩因子为j ，则由下式定义的变换w ：n ( x ) - - 斌x ) 是完备度量空间同( 上的 一个压缩映射，压缩因子是s ： w ( b ) = w l ( 曰) u w 2 ( 曰) u u w u ( b ) ，v b m ( x ) ( 2 - 9 ) 即对所有的b ，c e 脚( ，有 哈尔滨t 程人学硕 ：学何论文 ( w ( b ) w ( c o ) s h , ( 曰，c ) 且w 有不变集，记为a h ( x ) ，使下式 n a = w ( 彳