采用拟仿射变换进行分形树模拟

２０１２年２月　第３３卷第２期　

计算机工程与设计　

ＣＯＭＰＵＴＥＲ　ＥＮＧＩＮＥＥＲＩＮＧ　ＡＮＤ　ＤＥＳＩＧＮ　Ｆｅｂ．２０１２　

Ｖ０１．３３　ＮＯ．２　

采用拟仿射变换进行分形树模拟　韩江萍，周　敏，郑红婵，潘璐璐　（西北工业大学理学院应用数学系，陕西西安７１０１２９）　摘要：针对分形图形生成中带凝聚的ＩＦＳ（／ｋ代函数系统）的延伸变换难以有效地选取，其参数修改达不到所需水平的　问题，提出一种新的分形树模拟方法，利用拟仿射变换来实现树木成行、树木成林，该方法不涉及延伸变换，而以分形图　拟仿射变换取而代之，并通过调整参数可取得理想的效果；另外，对所生成的树木进行渲染（着色），增强了视觉上的真　实感。实验结果表明，该方法与传统的实现树木成行、树木成林方法～一带凝聚的ＩＦＳ相比，算法简单，操作灵活，模拟　效果较好。　关键词：拟仿射变换；带凝聚的ＩＦＳ；分形；着色；树木模拟　中图法分类号：ＴＰ３９１。４１　文献标识号：Ａ　文章编号：１０００—７０２４（２０１２）０２—０７００—０５　

Ｓｉｍｕｌａｔｉｏｎ　ｏｆ　ｆｒａｃｔａｌ　ｔｒｅｅｓ　ｕｓｉｎｇ　ｐｓｅｕｄｏ—ａｆｆｉｎｅ　ｔｒａｎｓｆｏｒｍａｔｉｏｎ　ＨＡＮ　Ｊｉａｎｇ—ｐｉｎｇ，ＺＨＯＵ　Ｍｉｎ。ＺＨＥＮＧ　Ｈｏｎｇ—ｃｈａｎ，ＰＡＮ　Ｌｕ一１ｕ　（Ｄｅｐａｒｔｍｅｎｔ　ｏｆ　Ａｐｐｌｉｅｄ　Ｍａｔｈｅｍａｔｉｃｓ，Ｓｃｈｏｏｌ　ｏｆ　Ｓｃｉｅｎｃｅ，Ｎｏｒｔｈｗｅｓｔｅｒｎ　Ｐｏｌｙｔｅｃｈｎｉｃａｌ　Ｕｎｉｖｅｒｓｉｔｙ，Ｘｉ’ａｎ　７１０１２９，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：Ｔｏ　ｔａｃｋｌｅ　ｔｈｅ　ｄｉｆｉｃｕｌｔｙ　ｏｆ　ｃｈｏｏｓｉｎｇ　ｅｘｔｅｎｓｉｏｎ　ｔｒａｎｓｆｏｒｍａｔｉｏｎ　ａｖａｉｌａｂｌｙ　ａｎｄ　ｔｈｅ　ｐｒｏｂｌｅｍ　ｏｆ　ａｄｊｕｓｔｉｎｇ　ｐａｒａｍｅｔｅｒｓ　ｔｈａｔ　ｃａｎ’ｔ　ｒｅａｃｈ　ｗｈａｔ　ｉｔ　ｉｓ　ｎｅｅｄｅｄ　ｉｎ　ｉｔｅｒａｔｅｄ　ｆｕｎｃｔｉｏｎ　ｓｙｓｔｅｍ　ｗｉｔｈ　ａｇｇｌｏｍｅｒａｔｉｏｎ，ａ　ｎｏｖｅｌ　ａｐｐｒｏａｃｈ　ｔｏ　ｒｅａｌｉｚｉｎｇ　ｓｅｖｅｒａｌ　ｒｏｗｓ　ｏｆ　ｆｒａｃｔａｌ　ｔｒｅｅｓ　ｉｓ　ｐｒｏｐｏｓｅｄ　ｕｓｉｎｇ　ｐｓｅｕｄｏ－ａｆｆｉｎｅ　ｔｒａｎｓｆｏｒｍａｔｉｏｎ．Ｔｈｅ　ｆｒａｃｔａｌ　ｐｓｅｕｄｏ－ａｆｆｉｎｅ　ｔｒａｎｓｆｏｒｍａｔｉｏｎ　ｉｎｓｔｅａｄ　ｏｆ　ｔｈｅ　ｅｘｔｅｎｓｉｏｎ　ｔｒａｎｓｆｏｒ—　ｍａｔｉｏｎ　ｉｓ　ｔａｋｅｎ　ａｄｖａｎｔａｇｅｄ．Ｄｅｓｉｒａｂｌｅ　ｒｅｓｕｌｔｓ　ｂｙ　ａｄｊｕｓｔｉｎｇ　ｐａｒａｍｅｔｅｒｓ　ａｒｅ　ｏｂｔａｉｎｅｄ．Ｗｈａｔ’Ｓ　ｍｏｒｅ，ｔｈｅ　ｆｒａｃｔａｌ　ｔｒｅｅｓ　ｇｅｎｅｒａｔｅｄ　ｉｎ　ｔｈｉｓ　ｗａｙ　ａｒｅ　ｒｅｎｄｅｒｅｄ　ｔｏ　ｒａｉｓｅ　ｔｈｅ　ｓｅｎｓｅ　ｏｆ　ｒｅａｌｉｔｙ．Ｔｈｅ　ｅｘｐｅｒｉｍｅｎｔ　ｉｎｄｉｃａｔｅｓ　ｔｈａｔ　ａｌｇｏｒｉｔｈｍ　ｏｆ　ｐｒｅｓｅｎｔｅｄ　ｍｅｔｈｏｄ　ｉｓ　ｓｉｍｐｌｅｒ，ｏｐｅｒａｔｉｏｎ　ｉｓ　ｍｏｒｅ　ｆｌｅｘｉｂｌｅ，ａｎｄ　ｓｉｍｕｌａｔｉｏｎ　ｒｅｓｕｌｔ　ｉＳ　ｂｅｔｔｅｒ　ｔｈａｎ　ｔｒａｄｉｔｉｏｎａｌ　ｍｅｔｈｏｄ　ｗｈｉｃｈ　ｉｓ　ｉｔｅｒａｔｅｄ　ｆｕｎｃｔｉｏｎ　ｓｙｓｔｅｍ　ｗｉｔｈ　ａｇｇｌｏｍｅｒａｔｉｏｒ￣　Ｋｅｙ　ＷＯｌｄＳ：ｐｓｅｕｄｏ－ａｆｆｉｎｅ　ｔｒａｎｓｆｏｒｍａｔｉｏｎ；ＩＦＳ（ｉｔｅｒａｔｅｄ　ｆｔｍｃｔｉｏｎ　ｓｙｓｔｅｍ）　ｔｈ　ａｇｇｌｏｍｅｒａｔｉｏｎ；ｆｒａｃｔａｌ；ｒｅｎｄｅｒｉｎｇ；ｔｒｅｅ　ｓｉｍｕｌａｔｉｏｎ　

０引　言　Ｈｕｔｃｈｉｓｏｎ在１９８１年提出的迭代函数系统（ＩＦＳ）是定　义和描绘分形的典型重要方法，许多分形图都可以用ＩＦＳ　码来绘制。利用ＩＦＳ模拟的图像无比精细、美妙绝伦，有　的堪称艺术，这在图形图像史上是一个新的突破。近年来，　不少学者对分形的图像模拟应用进行了诸多研究＿１　］，在这　些学者的研究中，大多数都集中在对分形植物的模拟上，　但是所研究的对象都仅限于单株植物，而实现树木成行、　树木成林却只有带凝聚的ＩＦＳ这一基本方法。带凝聚的ＩＦＳ　将两类不同的变换（凝聚变换和延伸变换）放在同一个ＩＦＳ　中同时生成图像，使最终图像复杂多变，其中凝聚变换与　一般的ＩＦＳ无异，但是延伸变换的选取就比较棘手，倘若　选取不当，生成的分形将一片混乱或达不到预期的视觉效　果，并且不易修正。本文受带凝聚的ＩＦＳ的启发，提出了　利用拟仿射变换实现树木成行、树木成林的新方法，以分　形图平移、缩放变换产生树木成行、树木成林，并以分形　图旋转、错切变换产生树的阴影等，本文方法可克服带凝　聚的ＩＦＳ在分形树生成中的缺陷。为了使生成的图形更具　真实感，文中对所生成的树木进行渲染，将文献Ｅｉｏ一１３２　中的单株植物着色算法扩展应用到一行树木、一片树林。　

１带凝聚的ＩＦＳ　１．１　ＩＦＳ基本理论　ＩＦＳ理论＿５］是研究整个问题的基础和关键。一个ＩＦＳ由　一个完备度量空间（Ｘ，ｐ）上一个有限的压缩映射集ｗ　：　

收稿日期：２０１１—０３一１０；修订日期：２０１１－０５—１６　基金项目：国家自然科学基金项目（６１０７０２３３）；西北工业大学基础研究基金项目（ＪＣ２００９４６）　作者简介：韩江萍（１９８５一），女，陕西渭南人，硕士研究生，研究方向为分形及其计算机生成、图形图像处理；周敏（１９６６一），女，浙江　宁波人，博士，副教授，研究方向为几何造型、细分与分形、图形图像处理；郑红婵（１９７１一），女，陕西铜川人，博士，副教授，研究方　向为几何造型、细分与分形、图形图像处理；潘璐璐（１９８１一），女，河南郑州人，博士研究生，讲师，研究方向为分形、图形图像处理。　Ｅ－ｍａｉｌ：１１ｊｐｍａｔｈ＠１６３．ｃｏｍ　第３３卷第２期　韩江萍，周敏，郑红婵，等：采用拟仿射变换进行分形树模拟　・７０１・　Ｘ—Ｘ及相应的压缩因子　，　一１，２，…Ｎ（满足：Ｏ＜　一　｛Ｓ　，”一１，２，…Ｎ）＜１）所组成，每个Ｗ。有一个　伴随概率Ｐ　，０＜ｐ　＜１且∑Ｐ　一１。迭代函数系统ＩＦＳ记　为：｛Ｘ；Ｗ　，　一１，２，…，Ｎ｝，随机迭代函数系统ＩＦＳＰ　记为：｛ｘ；Ｗｎ，Ｐ　，　一１，２，…，Ｎ），压缩因子都为Ｓ。　分形仿射变换的ＩＦＳ码通常采用随机迭代函数系统，ＩＦＳ生　成分形也常采用随机迭代算法。　定理１［。　（拼贴定理）　设（ｘ，ｐ）为度量空问，给　定ＬＥＨ（Ｘ）和ｅ＞０，，｛Ｘ；Ｗ　，＂一１，２，…，Ｎ｝是一　个压缩仿射变换的ＩＦＳ码，其压缩因子０＜　＜１，满足：　Ｎ　ｈ（Ｌ，Ｕ　ｗ　（Ｌ））≤　，则有ｈ（Ｌ，Ａ）≤　。　

ｌ　

拼贴定理的意义在于告诉人们如何去寻找一个ＩＦＳ，使　

得其吸引子贴近或看起来像给定的集合，即ＩＦＳ的反问题。　根据拼贴定理，对于任意图形，都可将其分解成若干子图，　绘出图形的吸引子，并且保证只要变换选取的恰当，图形　与吸引子之间就可任意接近。所以ＩＦＳ方法在模拟分形图　像方面具有极其重要的作用。　１．２带凝聚的ＩＦＳ实现树木成行、树木成林　定义１＿６］（凝聚变换）　设（Ｘ，ｄ）为度量空间和　ＣＥＨ（Ｘ）（Ｈ（ｘ）是由ｘ的全体非空紧子集组成的空　间），定义变换为Ｗｏ：Ｈ（Ｘ）一Ｈ（ｘ），ｗ。（Ｂ）一Ｃ，　ＢＥＨ（Ｘ），则ｗｏ为凝聚变换，集合Ｃ为相关凝聚集。　实际上，由于ｈ（Ｗｏ（Ｂ１），Ｗ　（Ｂ２））一ｈ（Ｃ，０—　０，因此凝聚变换实际上是压缩因子ｓ＝０的变换，当然也是　压缩变换，其唯一不动点就是这个凝聚集。　定义２［　］（带凝聚的ＩＦＳ）　设｛ｘ；Ｗ　，　：０，１，　２，…，Ｎ）为具有压缩因子ｓ的ＩＦＳ，变换ｗｏ：Ｈ（　）一　Ｈ（Ｘ）是凝聚变换，则｛Ｘ；Ｗｏ，　一０，１，２，…，Ｎ｝　是带凝聚的ＩＦＳ，其压缩因子为ｓ。　定理２［６］（压缩映射不动点定理）　设｛Ｘ；Ｗｎ，　一　０，１，２，…，Ｎ｝为带凝聚且压缩因子为５的ＩＦＳ，变换　Ｎ　Ｗｏ：Ｈ（Ｘ）一Ｈ（Ｘ）由下式定义：Ｗ（Ｂ）一Ｕ　（Ｂ），　ｎ＝ｏ　ＶＢ∈Ｈ（Ｘ），则Ｗ是（Ｈ（Ｘ），ｈｏ）上，压缩比为５的　压缩映射。　即：ｈ。（Ｗ（Ｂ），Ｗ（Ｃ））≤ｓ　ｈ。（Ｂ，Ｃ），Ｂ，ＣＥ　Ｈ　（Ｘ）且存在唯一的不动点（吸引子）ＡＥＨ（Ｘ），满足Ａ—　Ｎ　Ｗ（Ａ）一Ｕ　（Ａ），并且对ＶＢ　Ｅ　Ｈ（Ｘ），Ａ—ｌｉｍＷ＂（Ｂ）。　具体地，每次迭代时，ｗ。的作用只是生成单个景物，　即凝聚变换，而其它多个景物由ｗ　，ｗｚ，…ｗ　来生成，　这些变换使图像不断向空间不同方向上延伸，即延伸变换。　树木成行只需要ｗｏ，Ｗｚ（如图１所示），树木成林则需要　Ｗｏ，ｗ　，ｗｚ（如图２所示），若要产生其它更复杂的效　果，所需延伸变换就更多。带凝聚的ＩＦＳ重在延伸变换的　选取，例如为了模拟现实中的树木成行，我们通常必须注　意几个细节：①越往远处延伸，树会越来越小，树与树之　间的间距也越来越小，最后甚至挤在一起；②在保证图像　效果的前提下，树的数目应尽量多，这样有一眼望不到尽　头的意境。如图１所示，ｗ。生成了图中第一棵树，而其它　的树则由ｗ　来完成，从图中我们可以看到ｗ　绘制了１Ｏ　棵树，但是最后的视觉效果却不尽如人意，达不到细节②　要求的水平，对ｗ　的参数做一下调整，效果仍不理想。　本文提出的拟仿射变换实现树木成行、树木成林可以灵活　的、简捷的解决这两个问题并且能够产生令人满意的模　拟效果。　。…　０ｇ　毒　誊　黧ｉ　：　—　｜　ｉ　∞ｊｉ鼍鬻　图１用带凝聚的ＩＦ＇Ｓ生成树木成行　图２用带凝聚的ＩＦＳ生成树木成林　２拟仿射变换实现树木成行、树木成林　２．１拟仿射变换口　由于分形图的特殊性，实现分形图的仿射变换Ｃｇ实　是拟仿射变换）要比几何学上的仿射变换¨８］复杂得多。依　据拼贴定理，ＩＦＳ将待生成的图像看成是许多与整体相似　或经过一定的变换与整体相似的子图拼贴而成，而每个子　图都是整体图形的一个仿射变换。但是，迭代形成的整体　分形图却不能简单的用一般几何图形仿射变换的规则实现　图形的平移、缩放、旋转等，对分形图实施通常的仿射变　换后，分形图产生了严重的畸变，甚至面目全非了，究其　原因：在具体算法中，对迭代生成的点进行平移、旋转、　缩放、错切变换操作之后，必须将变换之前的点作为下一　次迭代的初值而不是直接进行下一次迭代。对分形图整体　实施仿射变换实质上是对构成分形图的每个点实施仿射变　换，只要把握住这个核心，就可以成功实现分形图整体的　仿射变换，达到预期的效果。