（电路与系统专业论文）分形图像压缩编码的算法研究及dsp实现.pdf

郑州大学硕士论文 摘要2 0 0 5 年5 月 摘要 本课题来源于河南省科技攻关计划项目“分形图像压缩编码的算法研究及 d s p 实现”。本项目的工作包括以下四个方面： 一、图像的自相似性研究； 二、提出一种快速分形图像编码方法： 三、基于分形图像编码的数字水印技术研究； 四、分形图像编码快速算法的d s p s 实现。 本文首先介绍了分形的基本概念和分形编码研究的发展，概括论述了分形与 分形图像编码的数学理论基础。 在图像的自相似性研究中，本文提出了一种图像自相似系数的定义和计算方 法。仿真结果表明本文定义的图像自相似系数能很好地反映图像的自相似性。 针对分形图像编码时间过长的缺点，本文利用分形理论中的解码与分辨率无 关的特性，提出一种快速分形图像编码方法。此方法与传统的编码方法相比，大 幅提高了编码速度，而编码的性能没有受到影响。在此基础上，将提出的快速算 法以d s p s 硬件实现，并对程序进行了充分优化。 在基于分形图像编码的数字水印技术研究方面，本文首先综述了基于分形图 像编码的数字水印技术原理及发展状况，然后对传统的方法进行改进。改进后的 算法在嵌水印图像质量和水印的鲁棒性方面均有提高。 关键词：分形自相似分辨率无关水印d s p s 郑州大学硕士论文 a b s t r a e l 2 0 0 5 年5 月 a b s t r a c t t h i ss u b j e c ti sf r o mt h ep r o j e c to fs c i e n c ea n dt e c h n o l o g yo fh e n a np r o v i n c e f o rt a c k l i n gk e yp r o b l e m sn a m e das t u d yo ff r a c t a li m a g ec o d i n ga n di m p l e m e n t a t i o n b a s e do nd s et h ep r i m a r yw o r ki sa sf o l l o w s ：f i r s t ，t h es t u d yo fi m a g e s s e l f - s i m i l a r i t y ；s e c o n d ，aq u i c k f r a o a l i m a g ec o d i n gm e t h o d ；t h i r d ，d i g i t a l w a t e r m a r k i n gt e c h n i q u e sb a s e do nf r a c t a li m a g ec o d i n g ；f o u r t h ，a ni m p l e m e n t a t i o no f t h eq u i c kf r a c t a li m a g ec o d i n gm e t h o do nt h ed s p s a tf i r s t ，t h em a t h e m a t i c a lp r i n c i p l ea n dt h ea d v a n c e so ff r a c t a li m a g ec o d i n g a r ei n t r o d u c e d i nt h es t u d yo fi m a g e ss e l f - s i m i l a r i t y , am e t h o dt h a te s t i m a t e si m a g e s s e l f - s i m i l a r i t y i s p r e s e n t e da n dt h ef a c t o rd e n o t i n gt h ec h a r a c t e ro fi m a g e s s e l f - s i m i l a r i t yi sd e f i n e d e x p e r i m e n t a lr e s u l t sh a v es h o w nt h a tt h ea l g o r i t h mc a n e v a l u a t ei m a g e ss e l f - s i m i l a r i t yc h a r a c t e rw e l l a i mt ot h ew e a k n e s s ，l o n ge n c o d i n gt i m e ，o ft r a d i t i o n a lf r a c t a lc o d i n g m e t h o d ，aq u i c kf r a c t a li m a g ec o d i n gm e t h o di sp r e s e n t e d t h em e t h o dm a k e st h eb e s t o ft h et h e o r e mo fr e s o l u t i o ni n d e p e n d e n ti n f r a c t a lt h e o r y c o m p a r e dt ot h e t r a d i t i o n a lc o d i n gm e t h o d ，t h i sa p p r o a c hc a nr e d u c ee n c o d i n gt i m ee f f i c i e n t l yi n s i m i l a rp s n ra n dc o m p r e s s i o nr a t i o a n dt h e nt h i sq u i c kf r a e t a li m a g ec o d i n g m e t h o di si m p l e m e n t e do nt h ed s p sa n dt h ec o d ei so p t i m i z e d i nt h ed i s s e r t a t i o no fm e t h o do fe m b e d d i n gw a t e r m a r k i n gi n t oa ni m a g eb y u s i n gf r a c t a lc o m p r e s s i o ns c h e m e ，t h i st h e s i ss u m m a r i z e st h et h e o r i e sa n dt h ec u r r e n t d e v e l o p m e n ts t a t u s a ni m p r o v e dw a t e r m a r k i n gt e c h n i q u ei sp r o p o s e d e x p e r i m e n t a l r e s u l t sh a v es h o w nt h a tt h ep r o p o s e dw a y sc a ni m p r o v et h eq u a l i f yo fw a t e r m a r k e d i m a g e sa n dt h er o b u s t n e s so f t h ew a t e r m a r k k e yw o r d s ：f r a c t a l ；s e l f - s i m i l a r i t y ；r e s o l u t i o ni n d e p e n d e n t ；w a t e r m a r k ；d s p s 玎 郑重声明 y 7 8 3 0 3 7 本人的学位论文是在导师指导下独立撰写并完成的，学位论文没 有剽窃、抄袭等违反学术道德、学术规范的侵权行为，否则本人愿意 承担由此产生的一切法律责任和法律后果，特此郑重声明。 学位论文作者( 签名) ：才勿借 如，年岁月二6 日 郑州丈学硕士论文第一章概论2 0 n 5 年5 月 1 1 课题背景 第一章概论 图像信息是人类获褥外界信息的主要来源。目前，数字图像已在多媒体通信、 医学i 雪像处理等诸多领域有着广泛的应用。但数字图像数据量大，传输时占用频 带宽，为此，必须针对图像的特点对数据进行编码和压缩。针对不同的需要，国 际电联( u ) 已经出台了许多有关图像压缩编码的标准，如j p e g 、m p e g l 、 m p e g 2 、m p e g 4 等。但如何尽可能地消除图像冗余，在保证图像质量的前提下 提高图像压缩比，一誊是一个非常重要的研究课题。 分形图像编码是近年来出现的”。种新型图像编码方法，它以新颖的分形几何 理论为基础，具有潜在的高压缩比和优良的重建图像质量，因而倍受人们关注。 目前分形图像编码已经成为图像压缩编码研究中的热点。分形编码有许多优点， 它以迭代函数系统理论( i f s ) 为基础，突破以往熵压缩编码的界限，在编码过程 中，采用了类似描述的方法，能达到很高的压缩比。解码是通过迭代完成的，具 有与分辨率无关( r e s o l u t i o ni n d e p e n d e n t ) 的解码特性。 1 2 选题意义 分形理论是欧氏几何相关理论的扩展，是研究不规则图形和混沌运动的一门 新学科。与传统欧氏几何学相比，分形有如下特点：整体上分形几何图形的处处 不规则性和不同尺度上图形的规则性；用欧氏儿何描述的对象具有一定的特征长 度和标度，是规则形状，而分形几何则无特征长度和标度，分彤几何图形具有自 相似性和递归性。简言之，分形理论描述了自然界物体的自相似性。分形图像编 码方法就是利用图像各局部之间的自相似性进行编码的。图像的自相似性越强， 采用分形方法编码的优势越明显。因此研究图像的自相似性、给出自相似性强弱 的度量尤为重要。 分形图像压缩的本质是出于图像中有岛度的仿射冗余，即图像中含有许多白 郑州大学硕士论文第一章概论2 0 0 5 年5 月 我参考物，有很多部分是自相似的。因此，经过适当的变换( 压缩、旋转、平移) ， 各区域可以相互表达。在编码过程中，为了消除图像中的仿射冗余，寻找自相似 的区域，要进行大量的搜索，因此分形编码过程运算量很大，需要较多的运算时 间。编码速度慢直是分形编码实用化的最大障碍。寻找一种快速有效的编解码 方法是目前分形编码研究的一个重要方向。 随着数字媒体的广泛应用以及数字网络通讯的飞速发展，数字产品的版权问 题显得日益突出，作为传统加密方法的有效补充手段，数字水印近年来引起了人 们的高度重视并逐渐成为多媒体信号处理领域的一个研究热点。目前，数字水印 技术已经取得了巨大的发展，出现了许多优秀的算法。从最开始的直接调整图像 像素点的灰度值，发展到利用预测编码或者j p e g 压缩，还有一些算法是利用图 像频域变换来实现的。分形编码和数字水印技术的结合，是一种集图像压缩和版 权保护于一体的技术，虽然它还不如其它水印嵌入方法成熟，但无疑是对分形编 码和数字水印领域的一种新的探索。将分形图像编码与数字水印两种全新的技术 相结合，对二者的发展将有巨大的推动作用。 目前，现有的分形图像压缩、解压缩方案，基本上都是在微机上以纯软件完 成的，这在许多场合是不合适甚至是不可能的。d s p s 数字信号处理器是进行数 字信号处理的专用芯片。将分形图像压缩编码与解码以d s p s 实现，一方砸可以 提高分形编解码的速度，另一方面也可以使分形图像压缩方案适用于需要小型 化、移动等无法配合微机的场合。这将很大程度上促进分形图像编解码从理论研 究走向实用。 基于上述分形图像压缩编码领域的研究意义，本文做了相关的研究工作。 1 3 课题来源及本文研究的主要内容 本文的研究基于河南省科技攻关计划项目“分形图像压缩编码的算法研究及 d s p 实现”。 在论文的研究过程中，本文作者在熟悉分形图像压缩编码原理的基础上，参 阅国内外文献，深入了解了图像的自相似性、快速分形图像编码算法以及基于分 形图像压缩的数字水印算法的研究现状。在硬件实现方面，熟悉和掌握了 t m s 3 2 0 c 6 7 1 1 d s p s 的结构特点、c o d ec o m p o s e rs t u d i o ( c c s ) 集成开发环境的使 郑州大学硕上论文第一章概论2 0 0 5 年5 月 用和d s p s 软件开发中c 程序的优化方法，将提出的快速分形图像编码算法以 t m s 3 2 0 c 6 7 1 1 d s p s 进行硬件实现。 本文主要工作如下： 1 ) 图像的自相似性研究； 2 ) 提出一种快速分形图像编码方法： 3 ) 将分形理论和数字水印技术枢结合，实现基于分形图像压缩韵数字水 印嵌入算法： 4 ) 将提出的快速分形图像编码算法以t m s 3 2 0 c 6 7 1 1 d s p s 进行硬件实现： 3 郑州大学硕士论文 第二章分形图像编码的理论基础2 0 0 5 年5 月 第二章分形图像编码的理论基础 2 1 分形概念的提出 自然界事物的形状和各种图形可分为两类：一类是有特征长度的，有特征长 度的事物如房屋、汽车、足球、人，房子的宽高，汽车的长度，足球的直径， 人的身长都是特征长度，这些事物的形状可以用线段、圆这些基本要素去逼近， 这些线和面几乎都是光滑的，几乎处处可以求微分。另一类是没有特征长度的， 如海岸线、云，它们无论分辩得多细都不能视为直线段或平面片，细节总是 无限丰富的，将局部放大，又发现局部与整体相似，如果没有人工参照物，很难 测量其尺度。传统的欧几里德几何学研究的都是有特征长度的图形，用欧几里德 几何学可以方便地描述这些规则形状的物体，而对于那些没有特征长度的图形， 欧几里德几何学就无能为力了。 为了研究这种大自然的几何学，曼德勃罗特( b b m a n d e l b r o t ) 在2 0 世纪7 0 年代创立了分形几何学。“分形( f r a c t a l1 ”一词来源于拉丁语“f r a c t u s ”，含有“不 规则”和“破碎”的意义“。、3 1 。 曼德勃罗特指出分形具有三个要素：形状、机遇和维数。首先，分形的形状 是支离破碎、参差不齐和凹凸不平的不规则形状；其次，对于一组由给定规则通 过随机迭代而得到的分形，分形对象本身并不依赖于随机性，总是以百分之百的 概率得到同一分形，即随机性或者机遇仅仅是工具，而结果是确定的；第三，分 形的维数可以是分数维，这种分维是通常维数概念的扩展，称为“拓扑维”。 目前，“分形”还没有确切的简明的定义。但是分形的集合具有如下特征： ( 1 ) 该集有精细结构，即在任意小的比例尺度内包含整体： ( 2 ) 无论从局部和整体来看，分形集都是很不规则的，无法用传统的几何语 言来描述； ( 3 ) 通常分形集都有某种自相似性，可能是近似的，也可能是统计意义上的； ( 4 ) 通常分形集的“分形维数”比它的拓扑维数要大； 4 郑州大学硕士论文第二章分形圈像编码的理论基础2 0 0 5 年5 月 ( 5 ) 许多情况下，分形集是非常简单的，或者是递归的。 2 2 分形图像压缩方法 自然界很多事物都具有分形的特征。根据分形理论，不少复杂的图形，从婉 蜒的山脉到多姿的云彩，给以不多的参数，都可以用简单的程序来产生。从数学 意义上说，这种图形含有的信息量很少，用来产生这种图形的程序很短小，而制作 出的图形却是无限的，并且这种图形隐含着有序性和规律性。复杂的图形寓于简 单的算法之中，这是可以采用分形方法进行图像压缩的主要依据。 分形图像压缩是一种新颖、独特的压缩方法。与经典编码方法相比，在编码 思想上它是一个重大的突破。以离散余弦变换( d c t , d i s c r e t ec o s i n e t r a n s f o r m a t i o n ) 为代表的经典图像编码方法，在技术上比较成熟，已进入实用阶 段，但有其局限性。它没有充分考虑人的视觉特性以及自然景物的特点，对图像 是以纯数据的形式看待，而不是结合图像内容自身固有的特点来处理，其压缩比 不高。例如，对于一幅由房子、大树和白云构成的简单的图像，如果用经典编码 方法来处理，是不会考虑其中的内容，而只对这幅图像的数据商接处理。但是如 果从分形的角度来考虑就不同了，分形方法考虑了图像的内容，用相应的数据分 别表示房屋、树木和云彩，而这些正是图像内容的实质。 用分形方法进行图像压缩的先驱是b a m s l e y l 4 5 】。8 0 年代中期，b a m s l e y 从 数学上找到了重要的理论根据，率先提出用迭代函数系统( i t e r a t e df u n c t i o n s y s t e m ，简称i f s ) 这种分形方法进行图像压缩，获得了1 0 0 0 0 ：1 的压缩比，为 图像压缩提供了一条与以往完全不问的新思路。 但是这种方法存在两个缺点：一是图像分割需要人机交互，无法自动实现， 对操作者有较高的专业要求；二是分割的图像只能与整幅图像进行相似性比较， 使比较的范围受到极大的限制，影响恢复图像的质量。因为这两点，虽然此方法 能达到极高的压缩比，但无法实用，在当时并未引起太多的注意。 1 9 9 0 年，j a c q u i n 6 、7 、89 l 在b a r n s l e v 研究的基础上，发展了迭代函数系统理论， 提出了局部迭代函数系统理论( 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 ) 。在此 基础上，又提出了一种基于方块划分的分形图像压缩方案，将b a m s l e y 方案中的 交互式分割变为固定大小的方块分割，这些操作可以由计算机自动完成。j a c q u i n 5 郑州大学硕士论文第二章分形图像编码的理论基础2 0 0 5 年s 月 提出的方案为分形压缩编码的研究注入了生机与活力，为分形图像编码的研究带 来了一次质的飞跃。 刍j a c q u i n 之后，分形图像编码引起了世界各国研究人员的广泛兴趣和关注， 成为目前编码研究的热点。 分形图像编码具有以下几个特点： ( 1 ) 分形编解码思路新颖，利用了数学中的不动点理论( f i x e dp o i n tt h e o r y ) ， 也叫吸引子理论( a t t r a c t o rt h e o r y ) ，因此，又有许多的研究者称其为吸引子图像编 码。在编码中，试图用某一个函数来描述整幅图像，与以往的正交变换编码有着 本质的区别。在解码时，解码图像可通过对任意初始图像的迭代变换而得到，不 管初始图像为何种图像，最后都能收敛到解码图像，显示了数学的威力与神奇： ( 2 ) 解码过程具有分辨率无关性( r e s o l u t i o ni n d e p e n d e n t ) 1 1 0 1 ，在分形编码时存 储的是i f s 参数，它可以对任何分辨率的图像进行迭代变换而获得解码图像，即 解码的分辨率可以与原始图像不同。 ( 3 ) 分形编解码是不对称的过程。在编码时，对每一值域子块，都要在相应 的域池中搜索最匹配的域块，非常耗时，但解码时无须搜索，解码速度较快。雨 传统正交变换编解码是对称的过程。 2 。3 分形图像压缩的数学基础 分形图像压缩编码的理论是基于迭代函数系统( i f s ) 的概念基础上的。迭代 函数系统( i f s ) 是分形集中一类特殊的自相似集，b b m a n d e l b r o t 在1 9 7 7 年用标 准折线的迭代过程来构造这类集。1 9 8 1 年，j e h u t c h i n s o n 推广此迭代过程， 第一次引入了迭代函数系统的理论。术语i f s 是由m eb a m s l e y 于1 9 8 5 年提出 的【1 ”，1 9 8 8 年m eb a m s l e y 把迭代函数系统( 1 f s ) 的思想应用到图像压缩中。 迭代函数系统理论在分形图像编码的发展中起着引导作用，分形图像编码的大多 数工作都是基于迭代函数系统理论的推广。 2 3 1 基本概念 为了定义迭代函数系统，首先介绍“完备度量空间”、“豪斯多夫度量”和“紧 缩变换”等基本概念。 6 郑州大学硕士论文 第二章分形图像编码的理论基础2 0 0 5 年5 月 定义1 ：度量空间 设x 是一个空间或一个集合。d ：x r 是工到r 的函数。若d 满足： ( 1 ) d ( x ，y ) 0 ；d ( x ，y ) ，o ，当且仅当x = y ； ( 2 3 1 ) ( 2 ) d ( x ，y ) = d ( y ，工) ，对所有z ，) ，j ( 对称性) ； ( 2 3 2 ) ( 3 ) d ( x ，y ) + d ( y ，z ) 乏d ( x ，z ) ，对所有x ，y ，z c x ( 三角不等式) 。 ( 2 3 3 ) 则称d 为x 的度量。( x ，d ) 是带度量d 的度量空问。 定义2 ：柯西序列 若度量空间僻，d ) 中一个序列 x 。 ：，收敛于x ，且z x ，贝j j x 。) 是一 个柯西序列。 定义3 ：完备度量空间 若度量空间( 工，d ) 的x 中每一个柯西序列 z 。 ：。都有一个极限x z ，则 称该度量空间( x ，d ) 是完备的。 令h 僻) 表示x 中的非空紧予集的全体。现在定义日( x ) 上的度量豪斯 多夫度量，为此首先给出集合距离的概念。 定义4 ：集合的距离 皑，d ) 是一完备度量空间，a ，b 是x 上的两个子集，定义集合a 到集合曰的 距离d 为： d ，曰) tm a x d ( x ，曰) ；工一 ( 2 3 4 ) 其中：d ( x ，口) - m i n d ( x ，y ) ；y c = b ) ( 2 3 5 ) 这样定义的距离有以下性质： ( 1 ) 一般不满足对称性，a pd o ，b ) - d ( n ，a ) ( 2 3 6 ) ( 2 ) a ( au b ，c ) - d ( a ，c ) vd ( b ，c ) ( 2 3 7 ) 其中，v 表示两数中取较大的一个。 定义5 ：豪斯多夫度量 两集合爿，曰间的豪斯多夫度量h 定义为： 郑州大学硬土论文 第二章分形图像编码的理论基础2 0 0 5 年5 月 h ( a ，b ) = d 研，占) v d ( b ，爿) 或( 2 3 8 ) h ( a ，b ) 一r f l a x s u p d ( x ，b ) ，s u p d ( y ，4 ) ( 2 3 。9 ) 当( x ，d ) 为一完备度量空间，可以证明( 日( 工) ， ( d ) ) 同样是一个度量空间。 下面所有的讨论都离不开这个度量空间，b a r n s l e y 认为这正是分形所在的空间， 而分形集之间的距离也正是由这种豪斯多夫测度度量的。 在迭代函数系统中，涉及到的变换都是紧缩仿射变换，在这里给出“紧缩变 换”和“仿射变换”的概念。 定义6 ：紧缩变换 令t o ：x x 为度量空间( x ，d ) 上的变换，若存在一常数0 sjc 1 ，使得 d ( c o o ) ，( y ) ) ss d ，y ) ，坛，y6 5 x 则称为m 为僻，d ) 上的紧缩变换，s 称为紧缩因子。 定义7 ：仿射变换 一个变换甜：r 2 一r 2 具有如下形式：c o ( x ，y ) 1 ( “+ b y + e ，“+ d y + ，) 。其 中，a , b ，c ，d ，e ，为实数，积一b c - 0 ，则称甜为( 二维) 仿射变换。 上式可写成矩阵形式，即： 甜。，y ，2 【：】 ； + 【；】4 爿石+ r 其中： 彳2 醐叫习 当它的线性部分是压缩的，该仿射变换就是紧缩的，则为二维紧缩仿射变换。 2 3 2 迭代函数系统 定义8 ：迭代函数系统( i t e r a t e df u n c t i o ns y s t e m ，i f s ) 一个迭代函数系统( i f s ) 包括一个完备度量空间( x ，d ) ，以及一系列定义于该 空间的紧缩映射o ) n ：x 一工，紧缩因子分别为s n , n = 1 , 2 ，a ，。通常将i f s 表示 郑州大学硕士论文第二章分形图像编码的理论基础2 0 0 5 年5 月 为仁；，咒一1 ，2 ，a ，收敛因子为s - m a x , i n = i & a ， 。 在分形图像编码中，一般要求迭代函数系统忸；t o n ，抖= 1 , 2 ，a ) 中的为紧 缩仿射变换。 例如考察平面欧式空间中的三个仿射变换： q 阱 1 孑。堋 吡撇蚪喇 州微阶闭 显然，这三个变换都是紧缩变换，紧缩因予均为1 2 。因此怛2 ；t 0 1 ， 就 是一个由这三个变换组成的紧缩因子为1 2 的i f s 。图2 1 表示了把该变换对一个正 方形和个圆的迭代过程。由于三个变换都是仿射压缩的，每次迭带后的新图形 都是缩小的，初始图形的迭代极限将成为一个点，图2 1 中的正方形和圆的迭代 极限是相同的，其极限图形是如图2 2 所示的s i e r p i n s k i _ 三角形。所以已知一个i f s ， 无论采用怎样的初始图形，反复迭代后都将逼近于同样的极限图形。 & 融k k 图2 1 三个变换对止方形和圆的作用 9 郑州人学硕士论文第二章分形图像编码的理论基础2 0 0 5 年5 月 图2 2s i e r p i n s k i 三角形 以下介绍迭代函数系统的两个重要定理，它们是分形图像压缩的主要原理。 定理l ：压缩映射的不动点定理( f i x e dp o i n tt h e o r y ) 令协皑，一一l z a 研为具有紧缩因子s 的迭代函数系统，变换彤：呱砷一同 定义为： 彤) = y 甜。) ，v b e h ( x ) ( 2 3 1 4 ) m l 那么w 是完备度量空间( h 僻) ， 似) ) 上的紧缩映射，且紧缩因子为s ，即 v b ，c e h ( x ) ， p ) ，( c ) ) s ，c ) 且具有唯一一个不动点彳僻) 月矽即) 。；a ) ，并且爿可通过下式得到： v b e h ( x ) ，a l i m w “) ( 2 3 1 6 ) 不动点集a e h ( x ) ，也称为此i f s 的吸引子。所以压缩映射的不动点定理又 称为吸引子定理。 压缩映射的不动点定理保证了迭代函数系统的吸引子的唯一存在性，以及这 种吸引子求取的方法，也就是确定迭代方法对吸引子的生成。 图2 2 中的s i e f p i n s k i 三角形，就是上例中的i f s ：但2 ；q ，：，) 的不动点( 吸 引子1 。 定理2 ：拼贴定理( c o l l a g et h e o r e m ) 令( z ，d ) 为一完备度量空问，令b h ( x ) ，给定f2 0 ，选择一个i f s ： x ；w 。，n ；1 , 2 ，a 1 ，具有紧缩因子s ，0 s 1 。使 n h ( a ，y 。p ) sf ( 2 3 1 7 ) 其中，h ( d ) 为豪斯多夫测度，那么h ( b ，a ) s 0 一s ) 。其中a 是该l f s 的吸 1 0 郑州人学硕士论文第二章分形圈像编码的理论基础 2 0 0 5 年5 月 引子，同时对于所有b e h ( x ) 存在以下关系： n h ( b ，a ) e ( 1 一s ) h ( b ，y 。p ) ) ( 2 3 1 8 ) n - 1 拼贴定理保证了对在完备度量空间中任意给定的有界子集，一定可以找到一 个迭代函数系统，其吸引子相近于该有界子集，近似的度量是豪斯道夫度量。 将以上两定理联系到图像编码。定理1 中，将h ( x ) 看作所有图像的集合， 一个迭代函数系统对应一个，而一个对应一个吸引子即一幅图像，因此， 一个迭代函数系统对应一幅图像。编码时，给定一幅图像曰，其分形编码过程就 是要构造一个迭代函数系统讧；，l = l 2 , a ，使 n b ；w ) = y 0 3 p ) ( 2 3 1 9 ) 月l 迭代函数系统的参数即是这幅图像的编码。解码时，有了迭代函数系统，要 找到它的吸引子，可通过迭代完成。 而给出了一幅图像，如何找到它的迭代函数系统呢? 拼贴定理告诉我们答 案。如果一幅图像，试图找到一个i f s ，使其吸引子与该图像相似或相近，我们 必须在给定的图像空间中找一组收缩变换，使此图像分别对各个收缩变换的结果 即其自身的各个小“拷贝”，拼贴起来和原图像的h a u s d o r f f 距离任意小，那么这 系列紧缩变换组成的迭代函数系统即是这幅图像对应的迭代函数系统。在这 里，拼贴过程可以认为是集合并的过程，而i f s 吸引子与原给定集之间的误差由 拼贴的过程确定。 2 3 3 局部迭代函数系统 对于分形图，如图2 2 中的s i e r p i n s k i 三角形，可以直接用i f s 方法进行处理， 找到3 个压缩仿射变换把自身( 整体) 变换到局部。由于现实中的图像是有灰度级 的，并且一般不具有整体与局部的自相似性，因此不能由自身的压缩仿射变换组 合而成。经验显示，现实中的灰度图像虽然不具有整体与局部的自相似性，但却 存在局部之间的自相似性。图2 3 显示了从l e n n a 像上取出的一些部位，那里具有 不同程度的相似性：她肩上一部分与其重叠的一个小部位几乎是相同的，镜予里 帽子的像的一部分经过旋转和改变亮度以后与她帽子的一部分是相似的。 郑州大学硕士论文第二章分形图像编码的理论基础2 0 0 5 年5 月 图2 - 3l e n n a 图像中某些自相似部分 为此提出局部迭代函数系统概念。实际中使用的分形图像压缩编码，都利 用的是局部迭代函数系统理论。 定义9 ：局部迭代函数系统( 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 ) 设仁，d ) 是完备度量空间，而q x ( i - 1 , 2 ，a ) ，令q ：q - - * x ( i - 1 , 2 , a ，开) 是在僻，d ) 上具有压缩因子黾( f = 1 , 2 ，an ) 的局部压缩映射，则下列压缩映射集 q ：q x ( i t l , 2 ，a ) ( 2 3 2 0 ) 称为局部迭代函数系统。实数s m a x ( s ，s 2 ，as 。) 称为u f s 的压缩因子。 可见局部自相似性与分形图的自相似性不同之处在于现实的图像是由本身 的许多“部分”在适当的交换下复制构成，这些“部分”并不是它们自身的仿射 变换下的恒等复制品，而是有误差的。这样就可构成局部迭代函数系统的方法， 它完全是i f s 方法的推广，只是每个变换的定义域不再是整个图像空间的定义 域x ，仅为x 的一部分。 2 4 小结 本章首先概括介绍了分形理论的提出、分形的概念。在此基础上，阐述了分 形理论应用于图像压缩的发展历程以及分形图像编码的特点。最后重点介绍了应 用分形方法进行图像压缩的数学理论基础。 1 2 郑州大学硕士论文第三章图像的自相似性研究2 0 0 5 年s 胃 第三章图像的自相似性研究 分形理论研究的对象是那些具有自相似特性的物体。分形图像压缩编码就 是利用图像的局部自相似性进行编码的。因而，用分形理论进行图像压缩时，图 像的自相似性对压缩的效果有很大影响。 根据局部迭代函数系统理论，对图像编码的过程就是寻找图像各个相似的区 域，每一对相似的区域对应着一个压缩仿射变换，这一系列压缩仿射变换组成一 个局部迭代函数系统，其对应的参数就是该图像的分形码。在搜寻相似区域时， 如果在允许的误差容限中没有找到匹配的区域，常将该区域分为几个小的部分， 分别寻找更为精细的匹配。由此可见，如果图像自相似性强，则更容易找到相似 区域，毋需细分，那么编码的复杂度小，编码时间短；相似区域对的数目少，则 对应的迭代函数系统中压缩仿射变换的参数少，最终分形码的比特数少，压缩比 高；而且相似区域匹配的效果好，解码图像与原始图像的误差较小，峰值信噪比 高。 可见，在用分形方法进行图像压缩时，自相似性是图像的一个重要参数，直 接决定了图像压缩的效果。基于此，本章在文献【1 2 】的基础上提出了一种图像自 相似系数的定义及计算方法，仿真结果表明该自相似系数能很好地反映图像的白 相似性。 3 1 局部相似系数 一般给定的灰度图像不具有整体与局部的自相似性，但存在局部之间的自相 似性。这就需要首先将图像分为多个小的区域。图像分割的方法有很多，考虑到 便于实现，本文采用将图像分割为方块。下面给出两图像块相似系数的定义。 设给定的两图像块x 和y ，大小为l x l ，y 块经过灰度比例变换和灰度偏 移变换后，与x 块的误差为： 卧一击，薹( p x 。哪圹盯 ，- ， 1 3 郑州大学硕士论文第三章图像的自相似性研究 2 0 0 5 年5 月 这里p x f 和p y 口分别为x 和y 对应在研亍、j 列的像素灰度值，a 为灰度比 例因子，卢为灰度偏移因子。分别对口和卢求偏导，可得误差最小时的口、卢为： 口一r 。yo ； ，芦；p x a p y( 3 1 2 ) 式中， = 壶。羹( 黔。一面) ( p ，。一而 ( s s ) 十击，羹( 盱耐 c 。， p x 和p y 分别为块x 和y 的灰度平均值。将( 3 1 2 ) 式代入( 3 1 1 ) 式可得 误差最小值的表达式为： e n i n = 口“2i 一x 2 y o ，2 口y 2 ) ( 3 1 5 ) 其中o r ：为x 块上的图像灰度值方差， 咖击；n 一一p x ) 2 慨， 定义r x y 口，q 为x 和y 的相似系数，表示为材，容易得出，0 tr , y 盯；盯，t 】。 由( 3 1 5 ) 式可见，r 越大，e r k 。越小，即两图像块的最小误差越小，二者越 接近，则相似性越强。 考虑到仃；o r ，为0 的情况，有两种可能： ( 1 ) 仃。和盯，同时为0 此时，x 块和y 块上的方差均为0 ，说明两个图像块的像素灰度值均为定值， 则二者是完全相似的。故此时卵为1 。 ( 2 ) 口，和盯，中仅有一个为0 此时，两个图像块中仅有一个图像块中像素灰度值为定值，故二者相似性较 差，定义此时r 为0 。 综上所述，相似系数，可表示如下： 郑州大学硕士论文第三章图像的自相似性研究2 0 0 5 年5 月 f 1 仃。，口，同时为。 叩一 0。，盯y 中仅有一个为o ( 3 1 7 ) lr i ，盯，盯，其他 3 2 全局自相似系数 为适应图像的局部自相似性，首先应将图像进行分块。设图像分为i n m 的 方块，步长为d ，dtm ，即各图像块之间可相互重叠。对每一个图像块，要尽 可能找到与它最相似的子块，方能判断二者之间的相似程度，进而综合得出楚幅 图像的自相似性。因为不同图像千差万别，不同图像中同一位置的图像块，与它 们相似的子块可能在不同的位置，很难给出一个绝对统一的标准。但分形压缩编 码多年的研究表明，在局部迭代函数系统中，与给定图像块自相似的区域多在其 邻域。因此，对每一个给定的图像块，取各图像块的中心子块与其作相似性判断 是一个较好的选择。设中心子块的边长为n ，为满足仿射变换的收缩特性，应使 ncm 。考虑到符合分形编码的习惯，可取i n 一2 n 。图像块提取方法和中心予块 取法如图3 - 1 所示： i 二量_ 薹：图liu 兰甜 图3 - 1 图像块提取与中心子块示意图 图像分块完毕后，分别对每一图像块与其对应的中心子块作相似性的判断。 设图像块为l i j ( m x m ) ，其对应的中心子块为e i j ( n n ) ，i 、j 分别为图像块左 上角像素在原图像中的位置，以标示不同的图像块。为根据式( 3 1 7 ) 定量评 价二者的相似性，应使二者对应的像素点数一致。使二者大小相同的方法可采取 郑州大学硕士论文 第三章图像的自榍似性研究2 0 0 5 年5 月 抽样处理或平均压缩处理。一般图像绝大部分灰度连续变化，采用两种方法的效 果差别很小，为算法简便起见，这里选用对l ，块进行抽样处理。当m = 2 n 时， 抽样处理即对l i ，隔行隔列取像素点，得到一个新的n x n 的块，。 利用式( 3 1 7 ) ，分别对每一对t ， q e i , j 求出相似系数巩j ，这样得到一 系列局部相似系数的值。将这些局部相似系数取平均，作为整幅图像的自相似系 数r 。0sr s 1 ，r 值越大，则图像自相似性越强。 综上所述，判断图像的自相似性要经过以下步骤： ( 1 ) 首先将给定的图像按步长d 分为大小为m x m 的方块，各方块之间可相互 重叠。 ( 2 ) 对个图像块，在它的中心取一边长为n 的中心子块，ncn l 。 ( 3 ) 将图像块抽样，使其和中心子块像素点数一致，根据( 6 ) 式得二者的相 似系数。 ( 4 ) 对所有的图像块重复步骤( 2 ) 和( 3 ) ，得到一系列的局部相似系数值叩。 ( 5 ) 将所有的局部相似系数取平均，作为整幅图像的自相似系数叩。 3 3 仿真结果 前面提到，自相似性强的图像，编码过程中很容易找到相似的区域，不必再 作进一步的划分，因而编码所需时间少、压缩比高，同时相似区域匹配的效果好， 解码图像与原始图像的误差较小，峰值信噪比高。 为了验证上面定义的图像自相似系数的正确性，随机选取一系列图像，获取 这些图像采用分形压缩方法编码时的编码时间、压缩比和解码图像的峰值信噪比 三个参数，观察这些参数与图像自相似系数的关系，与理论分析结果进行比较。 这些图像均为2 5 6 x2 5 6 点阵、8 位的b m p 图像，图像内容包括自然景物、医学 图像、卫星云图等各个方面，具有代表性。仿真结果如图3 2 所示： 由图3 2 可看出，随着自相似系数的增大，图像的编码时间逐渐减小，压 缩比增加，峰值信噪比也里增加趋势，尤其是压缩比和自相似系数基本上成线性 关系。由此可见，仿真结果符合理论的分析。 】6 郑州大学硕士论文第三章图像的自相似性研究2 0 0 5 年s 月 3 0 0 2 5 0 童2 0 0 暑1 5 0 霎i 0 0 5 0 0 ( a ) 自相似系数与编码时间关系图 i 、 l 二 0 30 3 50 4 0 4 5 0 50 5 50 60 6 5 白相似系数 3 5 3 0 2 5 丑2 0 姆 出1 5 1 0 5 o 3 7 3 5 妻3 3 耋3 l 逛 詈2 9 2 7 2 5 ( b ) 自相似系数与压缩比关系图 0 30 3 5o 40 4 5 0 5 0 5 5o 6o 6 5 自相似系数 ( c ) 自相似系数与蜂值信噪比关系图 一 l ， 0 30 3 50 ，40 4 50 50 5 50 60 6 5 自相戗系数 图3 - 2自相似系数与编码参数关系图 1 7 郑州大学硕上论文第三章图像的自相似性研究2 0 0 5 年5 月 3 4 小结 图像的自相似性对分形图像编码有非常重要的影响。图像自相似性强，则编 码时间短，压缩比高，解码图像的峰值信噪比高。本章首先由公式推导得出局部 相似系数的定义，在此基础上提出一种图像全局自相似系数的定义及计算方法。 最后随机选取了一系列图像，分析这些图像的全局自相似系数与编码参数的关 系，得出结论如下：随着自相似系数的增大，编码时间逐渐减小，压缩比增加， 峰值信噪比也呈增加趋势。由此可见，本文提出的图像白相似系数能够很好的反 映整幅图像的自相似性。 1 8 郑州大学硕士论文 第四章分形囝像编玛的快速算法2 0 0 5 年s 月 第四章分形图像编码的快速算法 自j a c q u i n 提出可由计算机自动完成的分形图像编码方案以来，分形图像压 缩技术研究引起了世界各国研究人员的广泛兴趣和关注。但是分形图像压缩技术 存在一个致命的缺点，即压缩时间过长，以至于不能实用。所以在9 0 年代后期 之后，对于分形图像压缩的研究主要集中在对编码的加速方面。本章介绍了传统 分形图像编码算法和分形图像编码快速算法的研究现状，提出了一种改进的编解 码方法。 4 1 传统分形图像编码算法 1 9 9 0 年，j a c q u i n 在b a m s l e y 研究的基础上，发展了i f s 理论，提出了局部迭代 函数系统理论，将变换峨的定义域由原来的整个区域放宽为整个区域的某些子 集。在此理论基础上，提出了一种基于方块划分的分形图像压缩方案，这些操作 可以由计算机自动完成，它为分形图像编码的研究带来了一次质的飞跃。 但在j a c q u i n 的算法中，图像分块大小固定，不能很好反映分形特性。若用 较大值块，则图像中复杂度较高区域得不到很好的匹配，从雨解码图像质量将受 到影响。若将分块尺寸减小，则能得到较好的匹配，但图像中很多较为平滑区域 用较大分块就能得到很好匹配，再把区域分块，势必增加编码所需映射数目， 从而降低压缩率。为解决这一矛盾，e w j a c o b s 、y f i s h e r 和r d b 0 s s e r 采用了四 叉树分割方法( q u a d t r e ep a r t i t i o n ) “”，这是目前最流行、最实用的压缩算法，下面 给以简要介绍。 四叉树分割是在给定值块与域块间最大匹配误差的情况下，由匹配误差来改 变值块和域块的尺寸大小，从而改善解码后图像质量的方法。四叉树分割将图像 表示成一棵树结构，树的根结点是原始图像，根节点包含了四个子节点，每个子 结点对应于图像的一个正方形子块，子块的大小为父块的1 4 。每个子节点又包 含了四个子节点。四叉树划分将每个块划分成更小的子块，一直重复这个划分直 到不需再划分或已经划分到了晟小的块。每个子划分都有一个划分条件，用以判 1 9 郑州大学硕士论文第四章分形图像编码的快速算法2 0