苏小红哈尔滨工业大学计算机科学与技术学院.ppt

《苏小红哈尔滨工业大学计算机科学与技术学院.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、苏小红哈尔滨工业大学计算机科学与技术学院迭代函数系统与植物叶片模拟哈尔滨工业大学计算机学院苏小红2迭代函数系统（1/24）IteratedFunctionSystem（简称IFS）美国佐治亚理工学院Demko,Barnsley教授首创在SIGGRAPH’85国际会议上，IFS专题报告IFS方法的魅力是分形迭代生成的“反问题”哈尔滨工业大学计算机学院苏小红3迭代函数系统（2/24）确定性算法与随机性算法相结合的方法生成植物杆茎或叶片用以迭代的规则是确定性的，它们由一组仿射变换(如R_1，R_2，R_3等)构成迭代过程是不确定的，每一次迭代哪一个规则，即R_i中具体哪一个，非预先定好，而要

2、靠掷骰子的办法来决定。设最终要生成的植物形态图为M，它要满足下述集合方程：M=R_1∪R_2∪…∪R_N含义：随机地从R_i(i=1,…，N)中挑选一个迭代规则迭代一次然后再随机地在R_i(i=1,…，N)中选一个规则迭代一次不断重复此过程最后生成的极限图形M就是欲求的植物形态图。每个迭代规则R_i都是一个仿射变换。哈尔滨工业大学计算机学院苏小红4迭代函数系统（3/24）一个变换S：Rn→Rn称为线性的假若S(x+y)=S(x)+S(y)，且S(λx)=λS(x)S称为非奇异线性变换当且仅当x=0时，有S(x)=0ω称为仿射变换如果变换ω：Rn→Rn具有形式ω(x)=S(x)+a，这里

3、S为非奇异线性变换，a为Rn中一点哈尔滨工业大学计算机学院苏小红5迭代函数系统（4/24）正交变换保持几何图形的度量性质不变向量的夹角，点与点之间的距离，图形的面积等仿射变换一般会改变几何图形的度量性质但不改变共线、平行、相交、共线点的顺序、中心对称、二次曲线的次数等仿射变换在不同方向可以有不同的压缩和扩张例如可将球变换为椭球，正方形变换为平行四边形哈尔滨工业大学计算机学院苏小红6迭代函数系统（5/24）每个迭代规则R_i都是一个仿射变换。哈尔滨工业大学计算机学院苏小红7迭代函数系统（6/24）图形经仿射变换后面积变小，则此变换是收缩的面积变大，则是扩张的保持不变，则是恒等的。因为极限

4、图形M应是所有迭代R_i的吸引子每个仿射变换是收缩性的才能保证迭代收敛到M上所以只用到收缩性仿射变换（ContractiveAffineTransformation）哈尔滨工业大学计算机学院苏小红8迭代函数系统（7/24）设给定一个仿射变换f，对任意向量x和y，如果总存在一个非负实数，满足则s称为压缩因子使得上式成立的最小实数称为Lipschitz常数（李普希茨常数）因s<1，因此仿射变换f是收缩仿射变换哈尔滨工业大学计算机学院苏小红9迭代函数系统（8/24）上的收缩仿射变换（压缩映射）记为迭代函数系统若干个收缩仿射变换的组合哈尔滨工业大学计算机学院苏小红10迭代函数系统（9/24）I

5、FS方法生成分形图像的步骤：一个二维的IFS的组成收缩仿射变换的集合概率的集合确定仿射变换确定概率向量按照相应的概率，随机从仿射变换集中选择一个作为迭代规则迭代一次，不断重复此迭代过程（通过迭代过程产生点集序列来绘制分形图形）哈尔滨工业大学计算机学院苏小红11迭代函数系统（10/24）怎样确定仿射变换？确定a,b,c,d,e,f哈尔滨工业大学计算机学院苏小红12迭代函数系统（11/24）怎样实现掷骰子操作？设N=4，每次生成一个随机数E∈(0，100)设0＜β_1＜β_2＜β_3＜100，作如下规定：若0＜E＜β_1，则选择规则R_1若β_1≤E＜β_2，则选择规则R_2若β_2≤E＜

6、β_3，则选择规则R_3若β_3≤E＜100，则选择规则R_4指定β_i的过程相当于为每种迭代规则R_i指派一个概率p_i怎样确定概率向量？控制概率就是控制图形各部分的落点密度，使图形在有限迭代步数内显现出浓淡虚实不同的绘制效果。哈尔滨工业大学计算机学院苏小红13迭代函数系统（12/24）概率向量对分形图形的影响假设硬币呈现正面、反面和侧立的概率分别为0.5，0.47，0.03可以发现计算机的迭代次数（n）与图形清晰度的关系。1.在平面上任意确定三个点A、B、C，使得甲、乙、丙三人分别占据其中一个点；并轮流在平面上添画并占据新的点。2.一个新点出现后，由谁接着画要由掷硬币来决定：硬币出

7、现正面时由甲画，出现反面时由乙画，出现侧立时由丙画。3.当平面上出现一个新点时，不论轮到谁画，他都必须在新点与自己所占据的点之间的连线的中点处画出一个新点n=106n=107迭代函数系统（13/24）哈尔滨工业大学计算机学院苏小红15迭代函数系统（14/24）D=log3/log2=1.585Sierpinski三角形fabcdefp10.5000.52510.3320.5000.51500.3330.5000.550500.33哈尔滨工业大学