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

7袆莃芃螆螂莂蒅蕿膁莂薇袅肇莁蚀蚇羃莀荿袃衿荿蒂蚆膈蒈薄袁肃蒇蚆蚄罿蒆莆衿袅肃薈蚂袁肂蚁羈膀肁莀螁肆肀蒂羆羂肀薅蝿袈聿蚇薂膇膈莇螇肃膇葿薀罿膆蚁螅羅膅莁蚈袁膄蒃袄腿膄薆蚇肅膃蚈袂羁膂莈蚅袇芁蒀袀螃芀薂蚃肂艿节衿肈芈蒄螁羄芈薆羇袀芇虿螀膈芆莈薃肄莅蒁螈羀莄薃薁袆莃芃螆螂莂蒅蕿膁莂薇袅肇莁蚀蚇羃莀荿袃衿荿蒂蚆膈蒈薄袁肃蒇蚆蚄罿蒆莆衿袅肃薈蚂袁肂蚁羈膀肁莀螁肆肀蒂羆羂肀薅蝿袈聿蚇薂膇膈莇螇肃膇葿薀罿膆蚁螅羅膅莁蚈袁膄蒃袄腿膄薆蚇肅膃蚈袂羁膂莈蚅袇芁蒀袀螃芀薂蚃肂艿节衿肈芈蒄螁羄芈薆羇袀芇虿螀膈芆莈薃肄莅蒁螈羀莄薃薁袆莃芃螆螂莂蒅蕿膁莂薇袅肇莁蚀蚇羃莀荿袃衿荿蒂蚆膈蒈薄袁肃蒇蚆蚄罿蒆莆衿袅肃薈蚂袁肂蚁羈膀肁莀螁肆肀蒂羆羂肀薅蝿袈聿蚇薂膇膈莇螇肃膇葿薀罿膆蚁螅羅膅莁蚈袁膄蒃袄腿膄薆蚇肅膃蚈袂羁膂莈蚅袇芁蒀袀螃芀薂蚃肂艿节衿肈芈蒄螁羄芈薆羇袀芇虿螀膈芆莈薃肄莅蒁螈羀莄薃薁袆莃芃螆螂莂蒅蕿膁莂薇袅肇莁蚀蚇羃莀荿袃衿荿蒂蚆膈蒈薄袁肃蒇蚆蚄罿蒆莆 蕿蚀聿膆蚂袆羅膆莁虿袁膅蒄袄螇芄薆蚇肅芃芆袂羁节蒈蚅羇芁薀羁袃芀蚂螃膂芀莂薆肈艿蒄螂羄莈薇薄袀莇芆螀螆莆荿薃肅莅薁螈肁莄蚃蚁羇莄莃袇袃莃蒅虿膁莂薈袅肇蒁蚀蚈羃蒀莀袃衿肇蒂蚆螅肆蚄袁膄肅莄螄肀肄蒆羀羆肃薈螃袂肂蚁薅膀肁莀螁肆膁蒃薄羂膀薅蝿袈腿芅薂袄膈蒇袇膃膇蕿蚀聿膆蚂袆羅膆莁虿袁膅蒄袄螇芄薆蚇肅芃芆袂羁节蒈蚅羇芁薀羁袃芀蚂螃膂芀莂薆肈艿蒄螂羄莈薇薄袀莇芆螀螆莆荿薃肅莅薁螈肁莄蚃蚁羇莄莃袇袃莃蒅虿膁莂薈袅肇蒁蚀蚈羃蒀莀袃衿肇蒂蚆螅肆蚄袁膄肅莄螄肀肄蒆羀羆肃薈螃袂肂蚁薅膀肁莀螁肆膁蒃薄羂膀薅蝿袈腿芅薂袄膈蒇袇膃膇蕿蚀聿膆蚂袆羅膆莁虿袁膅蒄袄螇芄薆蚇肅芃芆袂羁节蒈蚅羇芁薀羁袃芀蚂螃膂芀莂薆肈艿蒄螂羄莈薇薄袀莇芆螀螆莆荿薃肅莅薁螈肁莄蚃蚁羇莄莃袇袃莃蒅虿膁莂薈袅肇蒁蚀蚈羃蒀莀袃衿肇蒂蚆螅肆蚄袁膄肅莄螄肀肄蒆羀羆肃薈螃袂肂蚁薅膀肁莀螁肆膁蒃薄羂膀薅蝿袈腿芅薂袄膈蒇袇膃膇蕿蚀聿膆蚂袆羅膆莁虿袁膅蒄袄螇芄薆蚇肅芃芆袂羁节蒈蚅羇芁薀羁袃芀蚂螃膂 一种提取分形图IFS参数的新方法及实现陈传臻1, 王化雨11(山东师范大学 信息科学与工程学院, 山东省济南市 邮政编码 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参数目前还是一个难点。1 提取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）其中, : 放缩变换系数； ：平移变换系数；: 旋转变换系数。2 已有的提取IFS码的方法对于规则的图形如我们熟知的Sierpinski垫片，因为我们已经知道压缩仿射变换中的六个参数所起的作用，再根据图形本身的几何关系，其IFS码可以比较容易的得出。对于不规则但具有分形特性的图形提取IFS码的方法主要有以下几种：2.1 最初的方法对那些经典的已知的某景物的IFS参数，改变它的某些参数值或加入随机因素来得到此景物新的IFS参数，然而对那些无已知参数的景物就无能为力了。2.2 三点法我们知道，一般具有分形特征的自然景物图形，它必然存在一些有特征性的点。由于整体和局部的相似性， 整体存在一些有特征性的点， 局部也必然相应地存在一些有特征性的点。由于局部是由整体仿射变换而来，则局部上的一些有特征性的点必然也是由整体上的一些有特征性的点经过同样的仿射函数变换而来。同时我们还知道， 通过三对点(整体上的三个点和局部上对应的三个点)， 我们就可求出一个仿射变换。基于这个道理， 我们只要在整体轮廓上选取三个有特征性的点，然后再在各个局部轮廓上按相同的顺序选取对应的三个有特征性的点。这样根据这些点，就可以获得整体到各个局部的仿射变换。具体步骤如下:1.在原图上取三点：，然后在每一个拼贴子图上相应的取三点: 。选取点时注意：选取的三点最好不使之形成钝角三角形,并尽量能体现图形的整体信息,如选最上、最左、最右或最下的三点小拷贝上点的位置要尽量与整体上点的位置相对应,即小拷贝上取的三点尽量为整体上的三点在压缩映射作用下在小拷贝上的象。2.将这六个点分别代入公式 其中，为原图坐标，为拼贴子图坐标。3.采用三点对应解线性方程组的方法来求取仿射变换系数。4.各个仿射变换的概率可以通过计算得到，最后应对概率集归一化，使其和。至此可得到所求的IFS码。2.3 三角形法三角形法和三点法有着相同的理论基础，三角形法实际上是对三点法在取点方面的一个改进。具体做法如下：在原图上选取三个有特征性的点，然后再在各个拼贴子图上按相同的顺序选取对应的三个有特征性的点。这样根据这些点，就可以获得整体到各个局部的仿射变换，这和三点法是相同的。它们的不同之处在于：根据几何中三角形的稳定性我们知道，三角形以锐角三角形最稳定， 因此我们所选取的三点所构成的三角形最好是三个角均为锐角的三角形，也因此我们称此法为三角形法。我们从取三点过渡到画三角形，这实际上是为了让三点取得更准确，也就是说三角形法实际上是对三点法在取点方面做了改进。具体步骤如下:1.整体上按一定的顺序选取三个最有特征性的点，构成三角形。2. 各个局部上按相同的顺序选取局部上与整体对应的三个特征性的点， 构成三角形。3.根据整体上的三角形和各个局部上的三角形，再根据下面的公式:.同样采用选主元素法直接三角分解法进行求解，我们就可以很容易地获得整体到各个局部的仿射变换。4.得到仿射变换集后，各个仿射变换的概率可以通过计算得到，最后应对概率集归一化，使其和。3 提取IFS码的矩形框方法及实现三角形法是在三点法的基础上提出来的，它实际上是对取点的准确性方面进行了改进。这两种方法在拼贴方式的选择上都画出了拼贴示意图，但画出的拼贴示意图都是独立于原图的。我们知道想要通过拼贴得到与原图尽可能接近的图形，取点的准确性很重要，然而拼贴方式也是很重要的，因为它直接影响到最终的吸引子与原图的近似程度。这一步是通过人为判断来完成的。如何尽可能的避免主观因素的影响，使得生成的图形更接近原图。首先人为判断时应注意以下几点：每一个拼贴子图要小于原图，且与原图整体相似。每个拼贴子图之间最好为紧相邻的。所有的拼贴子图能够拼贴成原图。在此，我们引入一种新的方法，即在原图上画出其拼贴方式的示意图，这可使得拼贴方式的选取更为准确；同时，在拼贴方式示意图上对原图及其拼贴子图用矩形进行了约束，这又提高了取点的准确性。综上所述，此方法在取点和选取拼贴方式两个方面都做了一定的改进。具体步骤如下:1. 打开一个图形文件。在本程序中我们打开的是一个位图格式的图形文件。如下图1所示。 图1 羊齿叶原图2. 选择拼贴方式，画出拼贴方式示意图。在此我们用一个矩形来表示拼贴方式示意图中所表示的每一个图（包括原图和子图）。矩形的画法如下：在图上取纵向相隔最远的两个点A,B这两点决定了一条直线AB。再取横向相隔最远的两个点C,D。分别过C,D两点作直线AB的平行线L1,L2。分别过A,B两点作直线AB的垂线L3,L4。L1,L2,L3,L4两两相交，四个交点为M,N,P,Q，根据几何知识我们很容易证得四边形MNPQ是矩形，该矩形就是我们要画的矩形。在本例中，画出的拼贴示意图如下图2所示。3. 在拼贴示意图所示的每个矩形内（包括原图的矩形和各个拼贴子图的矩形），取三个特征点画三角形。如图3所示。 图2 拼贴示意图 图3 在拼贴示意图中画三角形根据整体上的三角形和各个局部上的三角形，再根据下面的公式:： 其中，代表仿射变换，是变换前图形的坐标值，是变换后图形的坐标值；是仿射变换系数。 通过解上述线性方程组，我们就可以得到很容易地获得的值，也就得到了整体到各个局部的仿射变换，到此为止我们就求出了该分形图的IFS码。在本例中得到的IFS码如下表1所示。表1 羊齿叶的IFS码abcdefp0.85-0.040.040.8538-90.770.20.26-0.230.22-333460.11-0.16-0.29-0.250.252883980.110000.16124428 4. 得到仿射变换集后，各个仿射变换的概率可以通过计算得到，最后应对概率集归一化，使其和。5. 根据以上步骤得到的IFS参数,采用随机迭代算法重构原图。如果重构图与原图差别不大,根据吸引子的稳定性,可以对参数做很小的改动来调整吸引子的形状; 若重构图与原图差别很大,则需要重新考虑拼贴方式或压缩映射的个数,进入步骤2.再重新提取参数。下图4是用表1中的数据得到的重构图。 图4 羊齿叶的重构图图 图5 树的拼贴示意图另外本文采用以上步骤，对树和枫叶画出了拼贴示意图如图5、 图6，并分别提取了参数如表2、表3所示。表2 树的IFS码abcdefp0.060.010.120.5849580.040.430.29-0.420.34-15770.270.480.13-0.160.428190.230.34-0.250.310.4474-110.230.3-0.320.430.387330.23图6 枫叶的拼贴示意图表3 枫叶的IFS码abcdefp0.6000.60.180.360.250.6000.60.180.120.250.40.3-0.30.40.270.360.250.4-0.30.30.40.270.090.25实验表明，该方法简单易行，而且也不受原图背景及图中其他景物的影响。采用画矩形的方式（即在原图中画出其拼贴示意图，并在图中矩形的约束下取点）在很大程度上减少了“试凑”次数，从而提高了参数提取的效率。4 小结本文在三点法和三角形法的基础上，提出了一种新的方法：在原图上画出其拼贴原理的示意图，并引入矩形来规范原图及其每一个拼贴子图，这使得在原图及其拼贴子图上取的点更为准确，从而使得拼贴出来的图形更容易与原图接近。此方法在Vc6.0上编程实现，试验结果表明该方法可大大提高拼贴效率，有效的减少“试凑”次数，可用来获取具有分形结构的图形的IFS码用于植物的模拟等。但仍有一些不足之处：模拟出来的图形真实感不强，需要采取措施进一步改善其逼真度。另外很重要的一点是，重构图形与原图的相似度是通过人的主观观察来评价的，带有很强的主观性，怎样找出一种客观的评价标准，这也是后续工作的努力方向。参考文献： 1期刊： PawlakZ . Rough sets. International Journal of Information and Computer Science. 1982,11(5):341-356.2期刊：Ziarko W. Variable Precision Rough Set Model. Journal of Computer and System Science,1993,46:4060.3论文集：Katzberg J D, Ziarko W. Variable Precision Rough Sets with Asymmetric bounds. In: Ziarko W P, ed. Proc. of PSKD93. Springer-Verlag,1994,167177. 4期刊：Dubois D, Prade H. Rough fuzzy sets and fuzzy rough sets. International Journal of General Systems,1990,17:191209.5期刊：Quafafou M. -RST: a generalization of rough set theory. Information Sciences,2000(4):301316.6期刊：Jelonek J, et al. Rough Set Reduction of Attributes and Their domains for Neural Networks. Computational Intelligence,1995,11(2).7论文集：Lingras P, Davies C. Rough Genetic algorithms. In: Zhong N, Skowron A eds. Proc.7th Intl.Wksp on RSFD,Springer,1999,3846.8期刊：Chakrabarty K., Biswas R., Nanda S. Fuzziness in rough sets. Fuzzy Sets and Systems,2000,110(2):247251.9期刊：fernanadez Salido J M, Murakami S. Rough set analysis of a general type of fuzzy data using transitive aggregations of fuzzy similarity relations. Fuzzy Sets and Systems,2003,139(3):635660.10论文集：Liu YunXiang, Sun Jigui. The Concept of Approximation Based on Fuzzy Dominance Relation in Decision-Making. In:Wang G., Liu Q., Yao Y., Skowron A eds Proc. of RSFD-GrC2003.Heidelberg, Springer,2003.382385.11论文集：Li Yuancheng, Fang Tingjian. Rough Set Methods for Constructing Support Vector Machines. In:Wang G., Liu Q.,Yao Y., Skowron A eds Proc. of RSFD-GrC2003.Heidelberg, Springer,2003.33433812论文集：王杨, 任永功, 闫德勤.基于遗传算法的粗糙集属性约简算法. 第三届不确定系统年会论文集, 南京2005. 376382.13编著：张文修, 吴伟志, 梁吉业. 李德玉.粗糙集理论与方法. 北京：科学出版社, 2001.14编著：刘清. Rough集及Rough推理. 北京：科学出版