分形及其计算机生成

1、分 形 及 其 计 算 机 生 成宣文霞傅德胜文亚平摘 要 本文重点以图象的方式直观地探讨了分形的特征。 并用 c 语言编制程序模拟生成分形图象 j u lia 集和m an2 de lb ro t 集, 通过对其图象的边界进行逐级放大, 可以清楚地了 解到它们的无限嵌套的自相似性以及 j u lia 集和m ande lb ro t 集的密切关系。f 是分形, 是指它具有下面典型的性质2 :(1) f 具有精细的结构, 也就是说在任意小的尺度之下,它总有复杂的细节;( 2) f 是不规整的, 它的整体与局部都不能用传统的几何 语言来描述;( 3) f 通常用自相似形式, 这种自相似可以是近似

2、的或是 统计意义下的;( 4) 一般地, f 的某种定义之下的分形维数大于它的拓扑 维数;( 5) 在大多数令人感兴趣的情形下, f 以非常简单的方法 确定, 可能由迭代过程产生。从以上的定义可以看出, 自相似性和标度下变 ( 或无特征 长度) 性是分形的两大突出特点。 同时这两个特点又是一致的, 即一个具有自相似特性的物体 ( 系统) 必定满足标度不变性。本文以下便主要研究了两个典型的分形图象 j u lia 集和 m ande lb ro t 集的计算机模拟生成及其局部放大算法, 一方面 从实验上验证了分形的以上特点, 另一方面也可以使我们直 接观察到分形精妙无比的无究变化和奥秘。关键词

3、分形j u lia 集 m ande lb ro t 集自相似性近 20 年来。分形的研究受到非常广泛的重视, 其原因在于分形既有深刻的理论意义, 又有巨大的实用价值。分形向人 们展示了一类具有标度不变对称性的新世界, 吸引着人们寻 求其中可能存在着的新规律和新特征。在分形的诸多研究课题中, 分形的计算机生成问题具有 明显的挑战性, 借助计算机的绘图手段以及快速的运算速度, 能够将一些简单的数学公式迭代过程展现在屏幕上, 产生一 幅幅生动美丽的图象。本文用 c 语言编制程序生成了 j u lia 集和m ande lb ro t 集 的图象并逐级放大, 这个功能相当于在计算机的显微镜下观 察复

4、平面上某些特定的区域, 从中探索这些极为壮观而意义 的分维数集, 得到一些极为相似而又混乱的图形。二、jul ia 集与m an de lbro t 集一、分形 (fra c ta l)j u lia 集与m ande lb ro t 集来自非线性映射众所周知, 自然界大部分是处于无序的、不稳定的、非平衡的和随机的状态之中, 它存在着无数的非线性过程。例如我 们平常接触到的天气情况, 实际上, 完全相同的天气是绝对不 会重现的。而利用传统的线性近似方法去研究他们是无能为 力的, 因为对于复杂一些的非线性系统和过程, 连其微分方程 ( 组) 都无法确定。分形理论与传统线性近似处理方法本质上 的区

5、别就在于它直接从非线性复杂系统的本身入手, 从未经 简化和抽象的研究对象本身去认识其内在的规律性1 , 从而 揭示了非线性系统中有序与无序的统一, 确定性与随机性的 统一。引导人们以新的观念、新的手段来处理非线性世界中的 随机性和复杂性, 透过朴朔迷离的无序的混乱现象和不规则 的形态, 揭示隐藏在复杂现象背后的规律、局部和整体之间的 本质联系。一般地, 可把分形看作大小碎片聚集的状态, 是没有特征 长度的图形和构造以及现象的总称。k. f a lco ne r 认为: 称集合x x + 2现在考虑复数的情形, 按习惯, 复数用 表示, 迭代过程写成, n = 0, 1, 2,(1)z n+ 1

6、 = z n +给定复数 z0 作为初始值, 从上式得 z1 , 继而 z2 , z3 ,11jul ia 集我们来看以上迭代过程对于特例 = 0 的情形, 这时简单 的有2 4 8z 0 z 0 z 0 z 0对此可以分三种情况进行讨论:(1) 如果给定的复数 z0 的模小于 1, 那么迭代序列中的数按模将越来越小, 且趋于零, 则说零是 z0 z2 的吸引子。所以0复平面上所有与该原点相距小于 1 的点, 都产生趋向此吸引子的序列。 宣文霞 南京气象学院计算机科学与技术系 助教 南京 210044 傅德胜 南京气象学院计算机科学与技术系 副教授 硕士生导师 南京 210044 文亚平 南京

7、气象学院数学系 助教 南京 210044(2) 如果用与原点相距为 1 的点作为初值进行迭代, 那么产生的序列总出现在复平面的单位圆周上。对这种情况, 称单 位圆周为此迭代的吸引区域。(3) 如果给定的复数 z0 的模大于 1, 则迭代序列中的数按模越来越大, 且趋于无穷, 这时说无究也是 z0 z2 的吸引子。0所以复平面上所有与零点的距离超过 1 的点都产生趋向无穷的序列;当 0 时, 吸引子不再是零, 而且吸引区域不再是一个 简单的圆周或圆周的变形, 而是由无究多个变形闭曲线组成 的精美图案。一般说, 对 的不同选择, 可以有不同形状的所 谓边界, 数学上称这类边界为 j u lia 集

8、。对 的某些值, j u lia 集 很明显是连通的, 也就是形成了单独一个区域。但对另一些 值, j u lia 集却不是联通的。21m an de lbro t 集m ande lb ro t 集是基于这样一种考虑而生成的: 在复平面 上, 使迭代过程 x x2 + 产生的序列确定为有界的, 那么复 数 又将怎样分布在复平面上呢? 如此 的集合叫做m ande l2b ro t 集。其精确的定义如下1 :同时, 在完成逐步放大的过程中, 由于后续图象的精细结构将非常敏感地依赖于前面的放大区域的选取。所以在设计 算法时采用了一个双向链表来记录逐步放大的过程, 这样当 在放大的过程中发现已经没

9、有更多的细节或所选取的区域不 满意时可以回到上一幅图, 重新选取放大区域, 并且随时可以 对满意的图象进行存盘, 这样通过运行程序就能方便灵活地 观测分形图象的各种细节, 了解它的无限嵌套的自相似性。程 序采用模块化结构设计, 共有六大功能模块组成, 分别用来完 成鼠标初始化及位置捕获; m ande lb ro t 集的生成; j u lia 集的生 成; 图象数据存储和图象的恢复; 处理过程的链表生成。 程序 布局较灵活, 因而很容易对模块进行修改、扩充。11m an de lbro t 集生成模块此模块是核心部分, 用于生成 m ande lb ro t 集的基本图 象。首先选择复平面上

10、待检查的正方形区域, 这里我们选择左下角的坐标为 (- 2125, - 115) , 边长为 3 的正方形, 与此正 方形相对应的是计算机屏幕上的 480480 点阵。根据迭代公 c : f k (0) 1 有界m =(2)k= c : f k (0) (k ) (3)这是在计算机上生成图象的基础。以上定义可以看出: z 从 0 开始, 是一个初始复数, 进行 反复迭代。迭代运算的对象实际上就是那个初始复数 , 它在 复平面上代表一个点。从这个初始点出发经多次迭代后, 会有 两种趋势:( 1) 迭代的总结果离开平面的中心越来越远, 趋向无究 大, 则初始点 不属于m 集;(2) 迭代的总结果总

11、何持有限, 则初始点 在m 集中。 用不同的 值反复进行迭代, 那些即使进行了无数次的迭代运算之后, x2 + 的值也是有限的复数 的集合, 就构成了形状极其复杂的m ande lb ro t 集。式 zn+ 1 z2 + , 设 z= x + y i, = a + b i, z 的初值取 0, 然后n三、计算机生成对矩形区域内的每个复数 进行迭代, 其基本算法如下:1) co un t0, a= - 2. 25, b = - 1. 5, side= 3. 0从上面的分析可以看出, j u lia 集和m ande lb ro t 集都是考sideside2 ) de lta = m - 1,

12、 de ltb = n - 1 (m 和 n 分别代表屏幕显示查复平面上的点按照迭代公式 zn+ 1 z2 + 进行迭代时所表n区域象素点的宽度和高度值)3) x = 0, y= 0, co un t= 04) 当 co un t 100 且 x2 + y2 4, 重复做下面的操作x 1= x2 - y2 + a y= 2xy+ bx = x 1co un t= co un t+ 14) 根据 co un t 的值标示出当前点的颜色5) 若检测区域已取完, 则程序结束, 否则 a = a + de lta, b =现出来的性质。因此, 运用计算机模拟生成的基本处理过程如图 1 所示。通常情况下

13、选取 j u lia 集和m ande lb ro t 集里有意义的局 部边界进行放大以观察其局部细节是困难的, 这是因为迭代 过程对初值的依赖是非常敏感的, 若想凭直觉来选取复平面 上的某一区域来进行放大几乎是不可能。所以本文在设计局 部放大算法时采取了较为新颖的方法, 即考虑直接在生成的 图象上利用鼠标拖动矩形框来定位放大的区域, 由此来确定 新的迭代的开始位置。24b + de ltb 转至步骤 2)21 关键问题的讨论(1) 复数迭代理论的一个简单结果表明, 要使 z 在迭代过 程中趋向无穷大, 其充要条件是在迭代运算的某一步| z| 2。 因此, 在研究m ande lb ro t

14、集和j u lia 集时, 如果某次迭代值| z|2, 则以后的迭代序列中 z 将肯定会趋向无穷大, 再也不返 回。( 2) 由于在程序中不可能让迭代无限制进行下去, 故设置 一个迭代次数的上限 ( 如 100 或 1000) , 若迭代次数达到上限次数还未发散 (即| z| 2) , 则认为此迭代序列必将有界。当然 迭代上限在一定的范围内取值越大, 则得到的图象将越精细,但将花费更多的运算时间。综合考虑两方面的因素, 一般迭代 上限取 500 1000 之间的数较为适宜。(3) 程序中根据迭代次数 co un t 的值来标示屏幕上坐标点 的颜色, 它的大小反映了一个点趋于无穷大的快慢。( 4

15、) 逐级放大时, 移动鼠标在图象边界上选取新的区域,返回新的坐标值 (x 1, y1) , 此时的 (x 1, y1) 指的是屏幕的横、纵 坐标。要实现放大 (这里的放大与普通图象的放大不同, 它实 际上是在复平面上又选取一个矩形区域, 对区域内的每个点 进行迭代) , 必须将 (x 1, y1) 转换为它所对应的复平面上的一 个复数。具体操作如下:a + (s id em ) x 1b + (s id en ) y 1a =b =其中 side 的值为上次放大区域的边长。四、结果与讨论图 2 (a) 中展示了几种j u lia 集的图象。在图 2 (b ) 中展示了m ande lb ro

16、t 集的基本图象及对其边缘放大的一系列图象:图 2 (a)一组 j u lia 集的图象图 2 (b ) m andb ro t 集及其局部放大的图象(1) 虽然m ande lb ro t 集并非象经典分形集那样是数学上严格自相似的, 但是它却具有一种相关特征: 如将m ande lb ro t 集的边界放大, 便会显示出该集无穷数量的微型缩影, 而这些 微型m ande lb ro t 集中没有一个是与母集完全一样的, 它们自 己也各不相同。(2) 从某种意义上讲, m ande lb ro t 集概括了所有可能的j u lia 集, 它是无穷数量的j u lia 集的直观的图解目录表。根

17、据 点在m ande lb ro t 集中的位置, 就能预测与之相关的 j u lia 集的 外形及大小, 如果 点在m ande lb ro t 集内, 相应的 j u lia 集就 是连通的; 如果 点选自m ande lb ro t 集之外, 则其 j u lia 集就 是不连通的。很直观地再现了分形的自相似性及其复杂精细的结构, 这只是对分形理论的一个初步研究。m ande lb ro t 集现在已经是分形理论的内容之一, 也成了 混沌的一种国际标志, 它美丽无比、色彩斑斓的图案给人以艺 术享受。如果能够用于印染工艺, 那么探索m ande lb ro t 集和 j u lia 集的图

18、象将是一项非常有价值的工作。参考文献张济忠编著, 分形, 清华大学出版社, 1995, 99 102齐东旭著, 分形及计算机生成, 科学出版社, 1996, 24 26,30d ew dney a k , 科学 (中文版, 谭建亮译) , 1985d ew dney a k , 科学 (中文版, 朱丹译) , 1988(收稿日期: 99 年 9 月 21 日)12五、结语34本文实现了m ande lb ro t 集和 j u lia 集图象的生成与放大,issn 10072757xm ic ro c om p u te r a p p lic a t io nsm o n th ly(s i

19、n ce 1985)w u q id ie d ito r2in 2c h iefv o l. 16, n o. 3 (gen e ra l n o. 83) m a rch 2000spec ia l top ic: ne twork an d its a pp l ica t ionp5s c ience & t ech nology w u h an 430074) l an q u n ru i (s ch ool ofre search on ne twork storage techn o logyh an d ez h i ( i ns t itu te of c om p u

20、te r, c en t ra l2c h ina u n iv e rs ity ofa d u l t e d u ca t ion , x iny ang n orm a l c ol leg e x iny ang 464000)a bstrac t t h is p ap e r de sc r ibe s th e p re sen t sta tu s o f ne tw o rk sto rage a s w e ll a s th e d isadvan tage o f t rad it io na l sto rage dep end ingo n se rve r. t

21、 h e tech no lo gy o f ne tw o rk a t tach ed sto rage and sto rage lo ca l ne tw o rk a re p re sen ted. a com p a r iso n be tw een bo th is g iven. f ina lly, it g ive s an in t ro duc t io n to app lica t io n s o f sto rage lo ca l ne tw o rk and ne tw o rk a t tach ed sto rage.keywords ne tw o

22、 rk sto rage ne tw o rk a t tach ed sto rage sto rage lo ca l ne tw o rk f ib re ch anne lp9d e s ign an d a pp l ica t ion of a rem o te m on itor in g & d iagn o st ic sy stem ba sed on in tern e tj i l im ing w ang t a iy ong ( i ns t itu te of m ech an ica l e ng inee r ing , t ianj in u n iv e

23、rs ity t ianj in 300072)a bstrac t t h is p ap e r de sc r ibe s in te rne t2ba sed rem o te m o n ito r ing & d iagno sing m ach ine fau lt s. it a lso p re sen t s it s k ey tech2n ique s and p rac t ica l im p lem en ta t io n.keywords rem o te m o n ito r ing & d iagno sing in te rne t d iagno s

24、t ic cen te rrea l iza t ion m e thods of vo ice comm un ica t ion over a tm broadban d ne tworkl in c h u an (w enz h ou n orm a l c ol leg e) z h ang q i (x ian a ir f orce t e lecom m u n ica t ion e ng inee r ing i ns t itu te)p12a bstrac t t h is p ap e r in t ro duce s seve ra l m e tho d s fo

25、 r vo ice comm un ica t io n o ve r a tm b ro adband ne tw o rk and th a t in th e h yb r idf ib re co ax ia l (h fc ) ne tw o rk u sing cab le m o dem.keywords a tm b ro adband ne tw o rk vo ice o ve r ip h yb r id f ib re co ax ia l ne tw o rk cab le m o demp14ip techn o logy a pp l ied in comm un

26、 ica t ion a rea st u j ie m a q iany i c h en y i (s h ang h a i c om p u t ing t ech nology r esea rch i ns t itu te s h ang h a i 200040)a bstrac t w ith th e deve lopm en t o f in te rne t, ip becom e s a pop u la r te rm. t h is p ap e r d iscu sse s ip tech no lo gy and it s app lica t io nin

27、comm un ica t io n a rea s w ith em p h a sis o n th e ho t top ic o f ip te lep ho ny.keywords ip tech no lo gy ip te lep ho ny ip faxre sea rch & d e s ignp18d ig ita l m ap in the veh ic le l oca t ion an d nav iga t ion sy stemw e i x ing tao z h u c a il ian ( i ns t itu te of m easu rem en t &

28、 g eop hy s ics, a cad em ia s in ica w u h an 470077)a bstrac t t h e d ig ita l m ap is v ita l in a veh ic le lo ca t io n and nav iga t io n sy stem (v l n s). t h e succe ss o f a v l n s dep end s o n th ede sign o f th e d ig ita l m ap. t h is p ap e r f ir st de sc r ibe s th e requ irem en

29、 t ana ly sis o f th e d ig ita l m ap , th en d iscu sse s it s co n ten t and st ruc tu re, and f ina lly g ive s it s o b jec t2o r ien ted im p lem en ta t io n.keywords d ig ita l m ap v eh ic le l o ca t io n and n av iga t io n sy stem (v l n s)par t ia l im provem en t of a 3 a lgor ithm in

30、a i an d its im p lem en ta t ionm ap m a tch ing o b jec t2o r ien tedp21w u y u anx in (a u tom a t ic c on t rol d ep a r tm en t, u n iv e rs ity of d ef ense s c ience & t ech nology c h ang sh a 410073)a bstrac t a 3 a lgo r ithm is a c la ssica l o ne w ith h eu r ist ic sea rch in a r t if ic ia l in te lligence. t h is p ap e r g ive s it s p a r t