（应用数学专业论文）快速分形图像编码算法的研究.pdf

论文题目：快速分形图像编码算法的研究 专业：应用数学 硕士生：黄晓莉 指导教师：李勇 摘要 ( 签名) ( 签名 分形图像编码技术以新颖的思想冲破了传统编码方法的理论框架，以潜在的高压缩 比( 对特定图像可以达到1 0 0 0 0 ：1 ) 、解码时问短、与分辨率无关的解码特性，以及良好 的重建图像质量，为图像编码开辟了一条新的途径，成为当今图像压缩领域中最新的方 法之一。尽管分形图像编码有诸多的优点，但它的编码过程是相当耗时的，在某种程度 上限制了它的广泛应用。因此，本文主要针对它的这个缺点，深入研究了在保证解码图 像质量的同时如何减少编码时间的问题。本文主要工作有以下两个方面： 1 重点研究了分形图像编码的基本算法( 即j a c q u i n 算法) ，对其改进策略进行了 总结；并针对每一类改进策略介绍了几种具体的改进算法，给出了每种算法与其它算法 的比较。其中，重点介绍了四叉树算法和形态算法，并通过实验验证了它们的有效性。 2 针对分形编码时间过长的不足，本文通过分析图像块的分布特点，定义了图像 块的一种新特征特征角。在不考虑等距变换的i j 提下，该特征很好的体现了图像块 的分布特点，是图像块间相似的必要条件。本文将特征角特征与特征向量策略相结合， 实现了一种基于图像块特征角的快速分形编码算法。该算法在保证解码质量的前提下， 大大提高了编码的时间，它将有力的推动分形编码技术的实用化进程。 最后，本文对分形图像编码的研究前景进行了展望。 关键词：分形理论；迭代函数系统；压缩映射；特征角 研究类型：应用研究 s u b j e c t ：r e s e a r c ho nf a s tf r a c t a l l m a g e c o d i n g s p e c i a l t y ：a p p j i e dm a t h e m a t i c s n a m e ：h u a n gx i a o h i n s t r u c t o r ：l iy 0 n g ( s i g n a t ur e ) ( s i g n a t u r e ) a bs t r a c t 。i h en o v e l t h o u g h to f 行a c t a ji m a g ec o d i n gt e c l u l 0 1 0 9 ) ，b r o k e nt i d u 曲t h et h e o r e t i c m 妇n e w o r ko ft r a d i t i o m lc o d i n gm e t h o d s st e c h i l o l o g ) ri 删g u r a t e san e w a p p r o a c hf o r l l l l a g ec o d i n ga 1 1 db e c o m e so n eo ft 1 1 eu p t o - d a t em e t h o d si ni m a g ec o m p r e s s i o nf i e l d ，d u et 0 l t s1 1 i 曲p o t e n t i a lc o m p r e s s i o nr a t i ow h i c hc a i lg e ta sh i g ha sl0 0 0 0 ：1f o rs o m es p e c i a li m a g e ， s h o nc o d i n gt i m e ，t 1 1 ed e c o d i n gf e a t u o f i n d e p e n d e n c eo fr e s o l u t i o n ，f a v o r a b i er e c o n s 仃i l c t e d l m a g eq u a l i t ya n ds oo n n l em a i nd r a 、v b a c ko f 胍t a li m a g ee n c o d i n gi st h e e x p e n s i v e c o m p u t a t l o n a lc o s ti nt h ee n c o d i n gp r o c e s s ，a l t h o u g hi th a sm a i l ya d v a n t a g e s t h e r e f o r e ，t m s a u t h o rs t u d i e sm a i n l yh o wt or e d u c er u n t i m ei nt h ee n c o d i n gp r o c e s sw h i l em a i n t a j i l i n gt h e r e c o n s 饥i c t e di i i l a g eq u a l i 吼t h em a i nr e s e a r c h 、o r kc a l lb eo 唱a n i z e di nt h ef o l l o w i n g “v o a s p e c t s ： 1 t h i sm e s i sm a j l l l yr e s e a r c h e so nb a s i c a l g o r i m m ) ，a n ds u n u n a r i z e si m p r o v e dp o l i t i c s a l g o r i n u no f 丘a c t a li m a g ec o d i n g ( j a c q u i n o fj a c q u i na l g o r i t l l i i l ；m o r e o v e r ，f o re a c h l m p r o v e dp o l i t i c ，s o m es p e c i f i ca l g o r i t h m sa r ep r e s e n t e da i l dc o m p a r i s o ni sg i v e nb e 铆e e n e a c ha l g o r i t l l 】 1 1 趾da n o t h e ra l g o r i t h i l l s t 1 l i st l ：i e s i sm a i l d yp r e s e n t sq u a d t r e ea l g o r i t h ma i l d s h 印ef e a t u r ea l g o r i t l l l l l ，a i l dv e r i f i e st h ev a l i d i t yo ft h e s ea l g o r i t h m st l l r o u 曲e x p e r i m e n t s 2 f o rt l l el a c ko f 丘a c t a li i l l a g e a l g o r i t h m sl o n ge n c o d i n gt i m e s ，b ya 1 1 a l y z i n gt h e d i s t r i b u t i o np r o p e r t i e so fi m a g eb l o c k ，an e wf e a t u r e ，n 锄e de i g e n a n g l e ，i sd e f i n e di nt l l i s p 印e r w i t h o u tc o n s i d e r i n gi s o m e t r i ct r a i l l s f o n i l a t i o n ，t h j sf e a n 鹏c a ni n d i c a t et h ed i s t r i b u t i o n p r o p e r t i e so fi m a g eb l o c l 【a i l di st i l en e c e s s a r yc o n d i t i o no fi m a g eb l o c ks i i i l i l a r i 戗i nt h i s p 印e r ，b yi n t e g r a t i n ge i g e n a n 9 1 ea n df e 狐鹏v e c t o rs n a t e g y ，af ；l s tf 梳t a li m a g ee n c o d i l l g a l g o d t l l i i lb a s e do ne i g e n a n g l ei sp r o p o s e d 7 1 1 1 i sa l g o r i t h m ，o nm ep r e m i s eo fg u a r a n t e e i n g t 1 1 e d e c o d i n gi m a g eq u a l i 劬c a i lg r e a t l ye i l l l a j l c et i l e e n c o d i n gt i m e s ，a 1 1 dw i l lp 0 、v e r ：m l l y i m p e t u st h ep r a c t i c a l i t yo ft h en a c t a l i m a g ee n c o d i n g l a s t l y ，t h er e s e a r c hp r o 罂e s so f 行a c t 翻i m a g ec o d i n gi sv i e 、v e di nt h ee n do f t h e s i s k e yw o r d s ： f r a c t a l c o d i n g i t e 腓d 劬c t i o ns y s t e m c o m p r e s s i o nm a p p i n g e i g e n a n g l e t h e s i s ：a p p l i e dr e s e a r c h 西要甜，技夫学 学位论文独创性说明 本人郑重声明：所呈交的学位论文是我个人在导师指导下进行的研究工作及 其取得研究成果。尽我所知，除了文中加以标注和致谢的地方外，论文中不包含 其他人或集体已经公开发表或撰写过的研究成果，也不包含为获得西安科技大学 或其他教育机构的学位或证书所使用过的材料。与我一同工作的同志对本研究所 做的任何贡献均已在论文中做了明确的说明并表示了谢意。 学位论文作者签名：甍j 日；涕1 日期： 砷9 参莎厦 学位论文知识产权声明书 本人完全了解学校有关保护知识产权的规定，即：研究生在校攻读学位期间 论文工作的知识产权单位属于西安科技大学。学校有权保留并向国家有关部门或 机构送交论文的复印件和电子版。本人允许论文被查阅和借阅。学校可以将本学 位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存和汇编本学位论文。同时本人保证，毕业后结合学位论文研究课 题再撰写的文章一律注明作者单位为西安科技大学。 保密论文待解密后适用本声明。 学位论文作者签名： 蠢睨确 指导教师签 勿9 年月莎日 1 绪论 1 1 研究背景 1 绪论 进人2 1 世纪，人类已步入信息社会，新信息技术革命使人类被日益增多的多媒体数 字信息所包围，一个“信息爆炸”的时代已经来临。多媒体信息主要有三种表现形式，即 文本、声音和图像。其中，图像作为最常见的信息存储方式，其表现形式生动而直观， 能提供比其它形式数据更多的信息。然而图像是三种信息形式中数据量最大的，若不经 过压缩，数字图像传输所需的高传输速率和数字图像存储所需要的巨大容量将会是十分 惊人的，因此对图像数据进行压缩十分必要。 图像压缩已研究了几十年，提出了诸如d p c m 、d c t 、v q 等压缩算法，并已出台了 基于d c t 等技术的国际压缩标准，如j p e g 、m p e g 、h 2 6 1 等，图像压缩己得到较为广 泛的实际应用。然而，随着人们对这些传统编码方法的深入应用，也逐渐发现了这些方 法的许多缺点，比如：高压缩比时图像出现严重的方块效应、人眼视觉系统( h 啪a 1 1 s l l a l s y s t e m ，简称h v s ) 的特性不易被引入到压缩算法中等等。为克服传统压缩方法中的上述 缺点，人们又在不断探索新的图像编码方法。经过十多年的发展，m k 删等人认为，目 前有三种方法属于第二代图像编码方法：基于分割( s e g m e n t - b a s e d ) 的压缩方案、基于模 型( m o d e l - b a s e d ) 的压缩方案及基于分形( f r a c t a l - b a s e d ) 的压缩方案【1 1 。 基于分形的压缩方法( 简称为分形编码) 是二十世纪九十年代新兴的一种编码方法。 由于其不同于传统的图像编码技术，具有较高的压缩比，被认为很有发展潜力。但是目 前分形编码还存在着编码时间过长、编码效果有待提高等不尽人意的地方。因此，仍有 进一步进行研究的必要。 1 2 国内外发展现状 分形编码是m f b 锄s l e y 于1 9 8 8 年提出的美国专利技术，源于他对迭代函数系统 的研究，该技术对几幅图像的分形编码获得了难以置信的超高压缩比( 1 0 0 0 0 ：1 ) 团，但这 种方法的缺点是在图像分割时需要人机交互，对操作者有较高的要求，无法实用，此方 案在当时并未引起太多的注意。 1 9 9 0 年，m f b 锄s l e y 的博士生a e j a c q u i n 发表了一种基于方块划分的分形图像压 缩方案瞄j ，在其方案中，首先将原始图像划分为固定大小的方块，然后对每一方块，通 过仿射变换在原始图像的紧缩图像中寻找最相似的部分。这些操作都可以由计算机自动 完成，是一种相对实用的方案，但这种方案仍然存在许多实际问题，如复杂的匹配库搜 索，编码时间过长；解码质量也不是很理想，存在方块效应：实际压缩比与理论上理想 西安科技大学硕士学位论文 效果差距太大等，影响了其实用性。尽管如此，分形编码还是以其新颖的思想、潜在高 压缩比、解码分辨率无关以及快速解码等优点受到技术界的广泛关注。 事实上，正是j a c q u i n 算法出现之后，分形图像编码才真正成为一个多领域学者参与 的活跃研究领域，而且后来绝大多数分形编码方案都是以该算法为基础，都是对j a c q u i n 算法的研究和改进。 通过阅读大量分形图像编码文献，在加快分形编码速度编码和提高解码图像质量等 方面，已提出许多新的观点和改进算法。在国外，f i s h e r 等人对j a c q u i n 算法进行了改进， 提出一种根据亮度及对比度变化来分类的方法【4 j ，匹配搜索时只在同类中进行，有效的 减少了匹配搜索的时间。h u n g e n 【5 】把矩阵块分为4 个象限，每一个象限对于一个比特位， 如果该象限的亮度均值大于整个块的亮度均值，就给对应象限的比特位置为1 ，否则置 为0 ，这样，共有1 5 个类，同样用方差在图像块中出现的顺序来实现分类得到2 4 个子类， 于是一共得到3 6 0 个类，同样减少了编码时间。 在国内，分形编码研究虽然起步较晚，但近几年来研究也相当活跃，几乎涉及分形 编码研究的各个方面。如快速分形图像编码、图像理解、分形与其它方法相结合1 6 ，7 j 、 d t c 域分形编码研究【8 1 、自适应分类的快速分形图像压缩【9 】、基于预测模型的分形图像 压缩编码【l o 】、基于小波变换的分形视频编码i l l 】等方面的研究。 1 9 9 2 年，美国微软公司采用分形图像编码技术，成功研制出了一张光盘“m i c m s o r e n e a i t a ，。仅用6 0 0 m b 的容量，就存储了大量的文件数据、长达7 小时的声像资料、1 0 0 部动画片、8 0 0 张彩色地图和1 0 0 0 幅逼真的风景照片，获得了很高的压缩比和很好的解 码图像视觉效果。这充分显示了分形图像压缩技术广阔的应用前景和发展潜力。 1 3 论文工作 作者参考了国内外大量分形及其在图像压缩研究方面的文献，在此基础上展开了论 文的研究工作。本文主要工作有以下两个方面： 1 深入研究了采用分块的方法对图像进行压缩编解的j a c q u i n 算法，给出了该算法 的具体实现。同时，通过仿真试验，研究了值域块与定义域块的尺寸与编码时间、图像 压缩比以及重建图像质量之间的关系。并针对j a c q u i n 算法的不足，重点对四叉树改进算 法和形态改进算法进行了深入研究，并通过试验验证了这两种算法改进效果。 2 针对分形编码时间过长的不足，本文通过分析图像块的分布特点，定义了图像 块的一种新特征精征角。在不考虑等距变换的前提下，该特征很好的体现了图像块 的分布特点，是图像块间相似的必要条件。本文将特征角特征与特征向量策略相结合， 实现了一种基于图像块特征角的快速分形编码算法。该算法能够在相对小的搜索邻域内 找到输入值域块的最佳匹配块，从而减少匹配块的搜索数目，实现提升分形编码速度的 目的。 2 1 绪论 1 4 论文结构 本文共分为五章，各章的内容安排如下： 第一章绪论。简述了课题的研究背景、国内外发展现状及内容安排。 第二章分形图像编码相关原理。主要介绍了分形的理论基础；并阐述了在分形图 像编码中有着重要作用的迭代函数系统，包括：仿射变换、压缩映射定理、迭代函数系 统的定义以及拼帖定理。 第三章分形图像编码算法。首先对j a c q u i n 算法的编解码过程进行了详细的阐述， 并对该算法进行了算法分析；然后，针对它的不足给出了几种改进策略，并针对每种策 略介绍了几种具体的算法，其中，重点介绍了四叉分割算法和形态算法。 第四章基于图像块特征角的快速算法。针对分形编码时间过长的问题，定义了图 像块新的特征特征角，基于此特征提出了一种快速编码算法。并通过试验验证了该 快速算法的可行性。 第五章结论与展望。对全文的工作和理论、实际意义作了一个总结，并探讨可以 进一步深入研究的方向。 3 西安科技大学硕士学位论文 2 分形图像编码相关原理 2 1 分形几何学 分形几何学是由曼德勃罗特( m a n d e l b r o t ) 在2 0 世纪7 0 年代创立的，是现代非线 性科学中十分活跃的一个数学分支。其研究对象是自然界和非线性系统中出现的不光滑 和不规则的几何形体。它既有深刻的理论意义，又有巨大的实用价值，在自然科学的各 个领域都有着广泛的应用。近年来，分形理论在信号处理、模式识别、图像编码、自然 图像的模拟等领域取得了很大的发展。 2 1 1 分形的创立及发展 1 9 7 5 年，m a l l d e l b r o t 出版了f r a c t a l ：f o 咖、c h a n c ea 1 1 dd i m e n s i o n ，可以翻译为 分形、机遇和维数，标志着分形作为一门科学正式成立。分形及其理论涉及的领域 非常广泛，其应用已经深入到许多应用领域。分形已成为当代科学中最有影响力和感召 力的基本概念之一，分形理论也成为非线性科学的生长点之一。分形理论的基础和主要 内容是分形几何，分形几何的研究对象是理论和现实中不规则的几何图形，例如：曲折 的海岸线、多变的云彩图案、参差不齐的金属表面以及涨落无常的股价曲线等等，这些 令经典几何束手无策的现象和状态，均可用分形几何加以描述、解释和研究。分形几何 的核心概念之一就是分数维和局部与整体的自相似性。分形几何还为研究混沌动力系统 的奇怪吸引子现象提供了直观的几何语言。 近几十年来，分形几何学已成为探讨复杂和无序现象的强有力的数学工具，被各个 学科分支中的学者们广泛的应用着。它同孤立子理论、混沌理论一起被誉为二十世纪后 期的非线性科学的三大理论突破。 分形理论的发展大致可分为三个阶段： 第一阶段为1 9 2 5 年以前：该阶段发现了一些典型的分形集合。同时，为了刻画这 些集合的性质，产生了h a u s d o r f r 测度和h a u s d o m 维数，这些概念说明了度量一个无特 征长度的几何对象时，必须依赖度量方式和度量的尺度单位。 第二阶段是从1 9 2 6 1 9 7 5 年：在这半个世纪中，人们对分形的性质做了较为深入的 研究，特别是维数理论的研究已获得了丰硕的成果。在此期间，产生了覆盖维数和熵维 数等概念。 第三阶段是从1 9 7 5 年至今：在此期间，分形理论和应用都取得了全面发展，分形 几何作为一门学科正式诞生。在分形理论方面，维数的估计与计算的算法、分形集的生 成与结构、分形的随机理论、动力系统的吸引子理论、分形的局部结构已获得较深入的 4 2 分形图像编码相关原理 研究结果。在应用方面，分形在物理的相变理论、材料的结构与控制、力学中的断裂和 破坏、高分子链的聚合、模式识别、自然景物的模拟、霉的生长模拟等领域取得了令人 瞩目的成果。当计算机科学特别是计算机图形学应用到分形领域后，它为分形的研究提 供了方便的、有效的工具，并且促使分形理论和应用有更多的新发现。 2 1 2 分形的定义及性质 分形的概念，最初是由美国i b m 公司的数学家m a l l d e l b r o t 引入的【1 2 】，意为破碎的、 不规则的。粗略地说，分形是对没有特征长度，但具有一定意义下的自相似性的结构的 总称。其中，自相似性是某种结构或过程的特征从不同的空间尺度或时间尺度来看都是 相似的，或者某系统或结构的局部性质或局部结构与整体相似。 事实上，到目前为止分形还没有严格的数学定义，虽然曾经有入尝试给出分形的严 格的数学定义，但是所提出的定义都不够全面和精确，只能给出描述性的定义。一般认 为分形f 具有以下五种性质： ( 1 ) f 具有精细的结构，即有任意小比例的细节， ( 2 ) f 是不规则的，以至于不能用传统的几何语言来描述， ( 3 ) f 通常有某种自相似性，可能是近似的或统计的相似， ( 4 ) f 在某种方式下定义的分形维数，通常大于它的拓扑维数， ( 5 ) 在大多数情况下，f 可以以非常简单的方式定义，可以由迭代产生。 为了对分形的自相似性及构造过程有个直观的了解，下面给出三个经典分形的例 子。 1 ) k 0 c h 曲线 k o c h 曲线是瑞典数学家h v o nk o c h 于1 9 0 4 年构造的，其几何表示如图2 1 所示。 其构造步骤如下： 首先，将一单位线段三等分，并截去中间的l 3 部分，代之以边长为l 3 的6 0 度角； 然后，再对每一条l 3 长的线段重复上述过程，直至无穷，便得到了具有自相似结构的 折线，即为k o c h 曲线。 图2 1k o c h 曲线 5 西安科技大学硕士学位论文 k o c h 曲线是包含于有界区域内的无限长曲线，它是数学领域中处处连续、处处不 可微曲线的典型代表。 2 ) c 枷o r 三分集 集合论创始人德国数学家康托( g c 锄t o r ，1 8 4 5 1 9 1 8 年) 在1 8 8 3 年曾构造了一种三 分集，其几何表示如图2 2 所示。 图2 2c 卸t o r 三分集 其构造过程为：取一条欧氏长度为c o = 【0 ，1 的直线段，c o 叫做初始操作长度。将这条 直线段三等分之后，保留两端的线段，将中间的一段丢掉，如图2 2 所示c l = 0 ，1 3 】u 【1 3 ，l 】 的操作；再将剩下的两条直线分别三等分，然后将其中间的部分丢掉，如图2 2 所示 c 2 = 0 ，l 9 】u 【2 9 ，l 3 】u 2 3 ，7 9 】u 8 9 ，l 】的操作，以此类推，直至无穷，便形成了无数个 尘埃似的点，这便是c a i l t o r 三分集。它们的数目无穷多，但长度为零。从几何关系来看， 最终生成点的分布是局部和整体相似的，甚至，这个过程中每一步的图形之间也是局部 相似的，这便是自相似。 3 ) s i e r p i n s k i 挚片 上面两个自相似图形都是基于一条欧氏直线段生成的，k o c h 曲线是将线段增加一 部分，最终得到的是一个处处不光滑的折线集，而c 觚t o r 三分集是将线段删去一部分， 最终得到的是一个离散的点集。波兰数学家谢尔宾斯基( w s i e 印i n s k i ，1 8 8 2 年1 9 6 9 年) 于1 9 1 5 年给出了一个从平面上的二维图形出发作曲线的有趣例子。所构造的s i e 印i n s k i 垫片相当于将上述构造方法推广到平面上，其初始图形是一个等边三角形面，其几何表 示如图2 3 所示。 a 图2 - 3 s i e r p i n s k i 垫片 6 n u l 2 3 4 西凸岛巴d 2 分形图像编码相关原理 s i e r p i n s b 垫片具体构造过程如下： 首先，将这个等边三角形面四等分，得到4 个小等边三角形面，去掉中间一个。将 剩下的3 个小等边三角形分别进行四等分，再分别去掉中间的一个。重复以上操作直至 无穷，可以得到如图2 3 所示的图形，可以看出它的每一小部分在结构上都与整体相同， 这也是一个典型的自相似的图形。 通过分析上述三个经典分形图形可知，分形与普通的欧氏几何图形有以下明显的区 别： ( 1 ) 欧氏图形是规则的，而分形是不规则的，也就是说，欧氏图形一般是逐段光 滑的，而分形往往在任何区间内都不具有光滑性， ( 2 ) 欧氏图形层次是有限的，而分形从数学角度上讲，层次是无限的， ( 3 ) 欧氏图形一般不会从局部得到整体的信息，因为它们不强调局部与整体的关 系，而分形强调这种关系，所以，分形往往可以从局部“看出”整体， ( 4 ) 欧氏图形越复杂，其背后的规则也必定越复杂，而对于分形图形，虽然看上 去十分复杂，但其背后的规则却是相当简单的。 2 2 迭代函数系统 对于一些特殊的分形，它们可以由计算机图形学和数学构造两方面提出。其中最简 单的一类，称为自相似集。起初，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 t e r a t e df u n c t i o ns y s t e m s ，简称i f s ) 的理论，把度量空间中的压缩变换集作为动力 系统的模型。b 锄s l e y 又把i f s 的思想应用到图像压缩编码中。i f s 在分形图像编码的 发展中起着引导的作用，分形图像编码的大多数工作都是基于i f s 或它的推广。 为了定义迭代函数系统，首先介绍分形空间和压缩映射等基本概念。 为了简单起见，只讨论r 2 中的分形，并把研究分形几何的基本空间记作( z d ) ，其 中xc 足2 ，x 是非空的闭集；d 是x 中的度量，如可取d 为欧氏距离，即d ( x ，力= k 一川， x ，y x ，所以( x ，d ) 是度量空间，一般还要求基本空间是完备的。由于我们讨论的图 形都是空间x 的子集，还要定义新的空间日。 设( x ，d ) 是完备度量空间。把x 中非空紧子集( 即有界闭集) 的全体记作h ( x ) ， 则任意一幅图像都可由胃( x ) 的一个子集来表示。现在要定义日( x ) 上的度量，即任意 两幅图形( 子集) 之间的距离，称为h a u s d o r f r 距离，记作办。它依赖于基本空间x 的 度量d 。 定义2 1 分形空间 设彳，b ( x ) ，两个子集彳和b 的h a u s d o r f r 距离办为 7 西安科技大学硕士学位论丈 办( 4 ，b ) 一m a x s u p d ( x ，b ) ，s u p d ( y ，彳) lj e y e 占 j 其中，从点x 到子集b 之间的距离为 d ( x ，b ) = i n f d ( x ，y ) ：y b )诋彳，b h ( x ) 由于日( x ) 的子集之间定义了度量厅，( 日( x ) ，办) 也是一个度量空间，被称为分形空间。 我们先构造完备距离空间上的压缩映射，由此引出分形空间上的压缩映射。因为压 缩映射是特殊的仿射变换，所以在介绍压缩映射之前先给出仿射变换的定义。 定义2 2 仿射变换 变换缈：尺2 专r 2 的形式如下 国( ； = ( ：三 ( ； + ( ； ( 2 1 ) 其中，口，6 ，c ，d ，p ，厂r ，则称国为一个仿射变换。 当x r 2 时，式( 2 1 ) 常写成： 国x = 彳z + 6 x r 2 其中，4 = ( ：三) 是r 2 上的线性变换，6 = ( ； 是尺2 的一个矢量。 因此在平面上，线性变换彳有四种特例，具有明显的几何意义，记为 4 = ，4 = ，4 = ，4 = 瞄嚣) 则称4 为缩放变换，4 为伸长变换，4 为剪切变换，4 为旋转变换。边长为1 的正方 形经过以上四种变换后的结果如图2 4 所示 x x x 原图( a ) 缩放变换( b ) 伸长变换( c ) 剪切变换( d ) 旋转变换 图2 4 四个特殊的仿射变换 因此，任何仿射变换都能表示成伸缩、旋转、剪切和平移的组合。 定义2 3 压缩映射 设彩：x 专x 是度量空间( x ，d ) 上的一个仿射变换，石cr 2 。如果存在一个常数 s ( o s 研， 办( 肜”( 4 ) ，形”( 彳) ) s 办( ”1 ( 彳) ，形”1 ( 4 ) ) s ”办( 彳，”( 么” 重复运用三角不等式得 办( 彳，( 爿) ) 办( 彳，形。_ 1 ( 彳) ) + 乃( 形卜1 ( 爿) ，形( 彳) ) 矗( 彳，形( 彳) ) + 办( ( 彳) ，形( 形( 么) ) ) + + 办( 形扣1 ( 彳) ，形。( 么) ) 一所 则我们可把上式写作办( 形”( 么) ，形”( 彳) ) # 一厅( 彳，形( 4 ) ) ，因为s o 。如果能选取到一个 1 0 2 分形图像编码相关原理 i f s x ：哆，f = 1 ，2 ，玎 ，其压缩因子为s ( o s 有关。图像之间的度量有很多种，都可以表示图像之间差异程 度，本文中用图像之间的均方根度量来衡量图像之间的距离。 2 3 2 带映射的局部迭代函数系统 实际中，不是所有的扶度图像都具备严格的整体与局部自相似性，如图2 删中的 a ) m 崩26l 锄a 图像 b ) 月m 柙似性 2 分形图像编码相关原理 标准测试图像l e n a 就不能由自身压缩仿射变换组合而成。因此，用2 2 节方法研究这一 类图像的分形压缩编码时，会遇到困难，并且压缩过程中需要专业技术人员的人机交互 操作，但l e l l a 图像存在图像中局部与局部的相似性。对于自然图像，我们不难找出其 不同区域间确实存在这种不同尺度下的相似性，如仔细观察l e n a 图像( 图2 6 ( b ) ) 不难发 现这个事实：三个白色方框部分就具有不同比例的相似性。 通过以上研究，灰度图像中确实存在局部与整体或局部与局部的相似性，主要是局 部之间的相似性。因此若我们将原始图像进行块划分，并能通过局部自相似性找出划分 块的局部迭代函数系统，就能实现图像分形压缩的目的。实际上这是i f s 的一个推广， 这时，局部迭代函数系统的每一个变换以的定义域不再是整个图像空间的定义域x ，而 是x 的一部分口。 为了寻求图像的局部自相似性，下面介绍一些新的概念和定理： 定义2 7 局部迭代函数系统 设( x ，d ) 是完备度量空间，而口c x ，则下列压缩映射集： m ：口一x ) ，汪1 ，2 ，刀 称为局部迭代函数系统，简称l i f s 。图2 7 给出了l i f s 的映射示意图。 i w l 一r ， _ 7 _ d l i w | 2 1 ， 一_ 一 d 2 一 l w j m d 3 一 图2 7l f i s 方法 对于一幅平面灰度图像，把厂( i ，_ ) 称为每个象素点( f ，歹) 的灰度，为了简单起见，假 设图像所在的平面区域就是单位正方形，2 ，设g 力，= ( “，1 ，) ：0 “，v 1 ，以及灰度值 厂( f ，) ，= o ，l 】，图像的灰度空间f = 厂：，2 一r ) 容许的值域为尺。若采用上确界度 量，则得到如下定理。 定理2 3 是上界度量，则空间( f ，) 是完备度量空间。 定理证明可见文献1 3 】。 在研究灰度图像时必须考虑灰度，因此对2 维的局部平面仿射变换要再加上灰级的 映射作为第3 维，这就构成了带映射的局部迭代函数系统。 在寻找带映射的局部迭代函数系统时，首先将图像二维平面空间，2 划分成n 个互不 1 3 西安科技大学硕士学位论文 相交的子块墨，心，兄，称为值域块，满足：i = j 足= ，j 。其次，在，2 上寻找n 个块 ，= l q ，d 2 ，见，称为定义域块，不要求口之间互不相交也不要求它们的并集等于，2 。 定义2 8 带映射的局部迭代函数系统 设v i ，v 2 ，：，3 一，3 是一组映射，如果对每个e 的定义域加以限制，即有 哆= vid f 。，：d ，专置， 其中，江1 ，2 ，甩，q 被限制定义在定义域块d ，上，称 q ，哆， 为带映射的局部 迭代函数系统( l o c a li t e r a t e df u n c t i o ns y s t e mw i t hg r e yl e v e lm a p s ) ，简称为l i f s m 。 将哆作用在厂上定义为：哆( 厂) = q ( f ，j f ，厂( f ，) ) ，可以把它看作，2 上的一个函数的 图，而要做到这点，需要引入“铺覆”的概念。图2 8 显示了l i f s m 中以在三维空间中的 映射示意图。 图2 8 口到r 上的映射 定义2 9 铺覆 设定义2 8 中的映射q ，吐，如果对于一切厂f ，使u 哆( 厂) f ，则称q ， 哆，覆盖，2 。 定义2 9 告诉我们，如果将带映射的变换q 作用于对应定义域块口上的图像 厂n ( 口，) 上时，必定得到铺覆值域块r 上的函数的图像，而且，2 = u r 。因此，铺覆 i = i 条件就意味着u 咀( 厂) 产生覆盖上的函数的图像，而且各个r 互不重叠。 ，= j 与i f s 方法一样，现在要建立空间( f ，) 上的压缩映射；利用不动点定理，求出 不动点。 定义2 1 0 三维压缩映射 设三维变换缈：r 3 专尺3 ，记( x ，j ，彳) = 国( x ，y ，毛) 和( x 7 ，y 7 ，z ：) 。国( x ，y ，z 2 ) ，如果存在 1 4 2 分形图像编码相关原理 一个正实数j 灭，以满足压缩映射定理，一般来说d = 2 r 。图3 1 显示了原始图像划分的效果图。 1 7 西安科技大学硕士学位论文 第1 个值 ( a ) 值域蛱( b ) 定义域块 圈3 1 分形编码分块示意幽 自相似性的匹配就在讽 与 q 之间进行。由于母和q 比原图像要小的多，只 要值域块足够小，局部的自相似性在图像中总是存在的。整个匹配过程如图3 2 所示： 图3 2 分形编码的匹配过程示意图 为了以后说明的方便，我们定义一些操作符如下： ( 1 ) 诹块”操作符号。 。作用于图像j t 表示在上取出一个三维子块，子块大小为2 。：置，表 8 3 分形图像编码算法 示子块在二维图像中左上角的坐标。 ( 2 ) “放块”操作符号( ) 将( 。) 作用于，即( ，l ) ，表示把2 ，2 j 的三维子块插入全。的图中，用( k ，三) 表示子块左上角的坐标，用( 七，) 表示子块内的像素坐标。 ( 3 ) “平均抽取”操作符号l 一，表示把2 j 2 j 大小子块的灰度图像中的邻近四像素点灰度求“平均抽取”，变成 2 卜1 2 卜1 尺寸的子块。l 操作可写为： ( l ，。耿七，) = 缸，( 2 后，2 ，) + ，( 2 七+ l ，2 们 + ，肥啦川) + ，。肥j | + 1 ，2 川) 通过，操作，2 ，图像块变为2 卜1 2 卜1 的图像块，其灰度分辨减少，即图像变的粗糙。 ( 4 ) “旋转反射”操作符号厶 三。操作表示将子块进行旋转变换，犹如i f s 变换中的系数口，6 ，c ，d 一样。为了简化 匹配，把一个正方子块的旋转化为最简单的8 种操作，即旋转o 。，9 0 。，1 8 0 。，2 7 0 。和垂直 中线反射、水平中线反射和分别沿两条对角线反射这8 种固定方式。设d ，是一个大小 为2 d 2 d 的图像子块，子块的灰度函数为 邑( ，) ：，0 = o ，1 ，2 d 的对应的8 种变 换： 厶：g ，( t ，) = g ，( t ，) ， 旋转o 。： 厶：毋( ，) = 毋( ，2 d 一1 0 ) ， 垂直中线反射； 厶：g ，( ，0 ) = g ，( 2 d l 一，) ， 水平中线反射； 厶：毋( t ，) = 邑( 0 ，t ) ，对角线= 反射； 厶：毋( ，0 ) = 毋( 2 。一1 0 ，2 d l t ) ，对角线t + 0 = 2 d 反射； 厶：毋( ，0 ) = 毋( ，2 。一l t ) ， 旋转9 0 。； 厶：g ( ，0 ) = 毋( 2 。一1 一，2 d 一1 一) ， 睫转1 8 0 。； 1 9 西安科技大学硕士学位论文 厶：毋( ，) = g ，( 2 d l 一0 ，) ， 旋转2 7 0 ； 因此，在将值域块q 与定义域块9 进行相似性比较时，通过“厶”操作将定义域块 q 作8 种旋转变换后，再分别与值域块吩进行比较，选出其中相似性最好的结果，并 记录下这时的n 值。 利用上面的8 种操作寻找值域块与定义域块之间的相似性搜索，使 ( 磷，l ，) 以，l 厶( m ) l 磁“) ，+ k ，磁，l l ( 3 1 ) 其中，以为定义域块的变换伸缩因子；k 。为定义域块的偏移量；万( k ，三) 表示从 位于( k ，三) 上的定义域块映射到相应的值域块位置；胛( k ，三) 表示对定义域块的8 种变 换；l 是2 2 的全1 矩阵。 j a c q u i n 全自动的分形图像编码算法的编码的过程如下： s t e pl ：对于从待编码图像l 分割出的互不相交的值域块 r ) ，用取块操作磷上l 从 待编码图像中取出每个值域块足。 s t e p2 ：搜索与值域块相似的定义域块哆，并通过取块操作碟肌) l 、压缩l 和 厶( 鼬) 操作后，即厶( m ) 厶端鼬) 厶，使定义域块与值域块有相同的尺寸。 s t e p3 ：若值域块磷，。l 和定义域块厶( 砒) l 瑞鼬) l 各像素点上灰度值分别为q 和包 ( f - l ，2 ，肌) ，则式( 3 1 ) 两边近似误差司用 2 去善( 以，l 6 f + k 厂q ) 2 ( 3 2 ) 搜索是通过改变万( k ，三) 和厶( k m ，使“，达到最小，即得到与值域块最优匹配的定义域 块。因此，对式( 3 2 ) 求偏导数得系数饥和，且口：令锯= 0 ，老- o ，得 聊q 包一q 6 f 以。= 堕芦j 乇止 聊6 f 2 一( 6 j ) 2i j 、_ 一i 卅刖 其中，当聊6 j 2 一( 匆) 2 = o 时，久，l = o ， j ；l，= l 2 0 3 分形图像编码算法 。去l 善q 工善叫 将它们代入到式( 3 2 ) ，则有 = 准小( 善即私地纠吨如卅善q ) 3 ， s t e p4 ：在对每一个值域块r ，通过改变万( k ，三) 和k 鼬) 寻找一个最优匹配的定义 域块d ，使达到最小，则记下疋k 工万( k ，) ，聆( k ，三) ，就完成了一个值域块r 的 编码。 s t e p5 ：对所有的值域块r ，重复第3 、4 步，均找到相应最优匹配的定义域块，使 图像厶上的每个值域块r 都用其定义域块来覆盖。存储所有值域块的编码参数，这样就 完成了整幅图像的编码。 s t e p6 ：结束。 由上述编码过程可知，每个值域块r ，的编码是其最优匹配定义域块d ，的位置 万( k ，三) 及所对应的五k 刀( k ，三) 等参数的集合。考虑到以。和k 。工参数不一定为整 数，为达到更高的压缩目的，我们经常采取的措施是对这些参数首先经过量化，然后存 储，作为r 对应的分形代码。对每一个值域块冠都找到一组分形代码，就得到整个图像 的分形代码。 3 1 2j a c q u i n 算法的解码过程 解码过程相对于编码简单多了。由l f l s m 的理论可知，在编码过程中所得到的i f s 是压缩的，它的不动点可以通过对任意初始图像的不断迭代变换而得到。具体迭代式可 以写为如下形式： 形( ，) = 以，l ( ，l ) 厶( ) l 端m ) ，+ k ，( 磷，l ) 磷，。 k l = kx ，1 = r f 其中，为初始迭代图像；足为，中所有值域块。迭代过程可以表示为如下形式： l = 以，l ( 硭，l ) 磷，l 7 = 形( 形( 形( 聊) r ，上= 心 其中7 为形的不动点，严格的数学角度来说，需要迭代无数次才能得到不动点。然 而在实际应用过程中，只需要迭代有限次后即可认为收敛，其中满足在进行+ 1 迭 代后，图像的质量只是轻微的变化。一般情况下，s 1 0 。 根据上述算法描述，作者用程序实现了j a c q u m 算法的编码和解码过程，并对一幅 2 5 6 x 2 5 6 的l e n a 图像进行了演示试验，其中l e n a 图像被分为4 0 9 6 个4 4 的正方形值 域块，定义域块取8 8 的正方形块，划分定义域块的步长为4 个像素点。对于每个值域 块