一种提取分形图IFS参数新方法及实现.docVIP

PAGE 8 ??? PAGE 7 一种提取分形图IFS参数的新方法及实现 一种提取分形图IFS参数的新方法及实现 陈传臻1, 王化雨1 1(山东师范大学 信息科学与工程学院, 山东省济南市 邮政编码 250014) Abstract: Rough set theory is a new mathematical means to deal with vagueness and uncertainty. This paper explains the characteristics of rough set theory, mainly reviews several extensions of rough set theory, then discusses the recent ways of combining rough set with other methods, furthermore discusses the possible prospect for further research of rough set theory. Key words: Rough set; Data analysis; Knowledge discovery 摘 要: 粗糙集理论是一种新型的处理模糊和不确定知识的数学工具。本文给出了粗糙集理论的特点，主要阐述了几种粗糙集理论的扩展模型，然后讨论了近来粗糙集理论与其他方法的结合，并进一步讨论了粗糙集理论研究的前景。 关键词: 粗糙集，数据分析，知识发现 中图法分类号: TP18　　　文献标识码: A 自从Benoit B.Mandelbrot于20 世纪70 年代创立分形几何学以来,分形理论已从最初的对自然物体形态的描述过渡到对现象的解释。目前,在计算机上生成分形图形的方法主要有L系统和迭代函数系统(IFS),但由一个数学系统去解析地构造、研究一大类人为的或自然的具有自相似结构的对象,最为成功的还是的IFS。 IFS的吸引子一般呈现出精细复杂、具有自相似性的结构,能够很好地模拟传统几何难以描述的各种自然景物。但采用IFS进行景物模拟时,需要获得构成该IFS的各个压缩映射的参数,通常的做法是对经典已知的某景物的IFS参数,改变它的某些参数值或加入随机因素来得到此类景物新的IFS参数,然而对那些无已知参数的景物就无能为力了。如何得到所需的IFS参数目前还是一个难点。 提取IFS码的理论基础 迭代函数系统(Iteration Function System 缩写为IFS )的基本思想:分形具有局部与整体的自相似性，也就是说局部是整体的一个小复制品，只是在大小、位置和方向上有所不同而已;而数学中的仿射变换是一种线性变换，它正好具有把图形放大、缩小、旋转和平移的性质。因此，产生一个复制品就相当于对图形作一次压缩仿射变换。于是，从原则上说，任何图形都可以用一组压缩仿射变换来描述或生成。在这里，一个仿射“变换”就是一个线性“函数”，“不断重复”应用仿射变换就是一个“迭代”过程。一般说来，生成一个分形图需要一组仿射压缩变换，这就是“迭代函数系统”名称的由来。 迭代函数系统（IFS）是由一组压缩仿射变换。及对应的压缩比（即的Lipschitz常数）,满足,及其一组对应的伴随概率且，那么称为一迭代函数系统，记为。 IFS码是指迭代函数系统中的集合,一个概率集,其中,且。 吸引子定理：设是一个完备的度量空间，是压缩映射，,,且在上存在唯一的不动点A，即满足,并且A可由下式给出 ，对，有, A即为该IFS的吸引子，且表示变换w的n次复合，即： (B)=w(w(w(……(wB)))) 以上定理说明：迭代函数系统生成的图形总是存在的，而且是唯一的。 拼贴定理:设是一个完备量度空间,给定与。如果可以找到一个具有压缩因子的,使得下式成立:，则,其中A为该IFS的吸引子。等价地对任一有: 。其中H为中非空紧集的全体构成的集合族,为Hausdorff距离。 拼贴定理说明对任意给定的有界集, 一定可以找到一个IFS,其吸引子在一定的Hausdorff距离下与给定集相近。 要获得某图形的IFS参数，由拼贴定理知，就是要在图形空间中找到一组压缩映射，使给定图形在该组压缩映射作用下形成的子图的拼贴与给定图形相近。原始图形可由压缩映射作用下形成的个子图拼贴而成。 则这个压缩映射就组成了吸引子相近于原图的一个IFS。此IFS 所有的参数就是要获得的该图形的参数。又由拼贴定理知:每个压缩映射将原图整体上所有的点映射到一个子图上，且从(1)式可看出：每个压缩映射由 这六个参数确定。因此,通过在原图整体及每个拼贴子图上分别取点和(其中 为小拷贝的总个数),解方程即可得到IFS 的参数。 ω: （1）其中,