第 26卷第 8期 � � � 计算机应用与软件 Vo l�26No. 8
2009年 8月 � � Computer Applications and Softw are Aug. 2009
动力系统生成晶体群圆极限分形图
鲁 � 坚 � 邹玉茹
(深圳大学数学与计算科学学院 � 广东 深圳 518060 )
收稿日期: 2009- 01- 22。国家自然科学基金项目 ( 60873168 ); 广
东省自然科学基金 ( 2008257 )。鲁坚, 讲师,主研领域:计算机图形图像
处理。
摘 � 要 � � 提出从动力系统角度出发构造具有自相似性质的平面晶体群圆极限分形图的有效
方法
快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载
。根据 Carter晶体群迭代
函数
excel方差函数excelsd函数已知函数 2 f x m x mx m 2 1 4 2拉格朗日函数pdf函数公式下载
系
统周期性确定 2�为基本区域, 利用同胚仿射变换, 建立基本区域到上半平面的自相似映射关系, 进而通过保角映射生成圆极限分
形图。同时, 对 C arter混沌函数进一步探讨了边界着色平滑构图条件, 并生成了相应的圆极限分形图。这些图案具有很强的艺术渲
染力。该方法为平面
设计
领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计
对称图像提供了一种新途径。
关键词 � � 混沌 � 晶体群 � 分形 � � E scher 极限图
FRACTAL CIRCLE L IM IT IMAGES OF CRYSTALLOGRAPH IC
GROUPS GENERATED FROM DYNAM ICAL SYSTEM S
Lu Jian� Zou Yuru
(C olleg e of Ma th em atics and C ompu tationa lS cience, Sh enzhen Un iv ersity, Shenzhen 518060, Guangdong, Ch ina )
Abstrac t� � An e ffectiv e a lgor ithm is presented fo r fo rm ing fracta l circle lim it plana r pa tterns w ith se lf�sim ilar properties in te rm o f dynam ica l
system s. The size o f the fundam enta l reg ion is defined as 2� acco rding to the periodicity of iterating func tion system of � Carter c rysta llo�
g raph ic g roups. The self�sim ilarm apping relationsh ip is bu ilt from fundam enta l reg ion to upper ha lf p lane by using homeomo rph ic a ffine trans�
form ation, and then the fracta l circle lim it patte rns are generated by conform al m app ing. M eanwh ile, as fo r � Carter chao tic functions, w e fur�
ther discuss the cond ition o f composing sm ooth im age by colouring the boundary po ints, and correspond ing fractal c irc le lim it pa tterns a re crea�
ted in th is way. These patterns have so strong a rtistic rendering effect, the m ethod proposed here prov ides a nove l approach fo r the g raph ic de�
sign of symm etric im ages.
K eywords� � Chaos� Crystallog raph ic groups� Fracta l� !Escher! lim it im ages
0� 引 � 言
对称性是自然界普遍存在的现象。对称性对历史文物特别
在建筑雕刻装饰等均发挥了重要的作用,历代建筑文明史都有
着对称性的记载。对称图像的优美在装饰、建筑、壁挂、地毯等
上都有着广泛的应用 [ 1, 2]。传统的对称性图像构造与混沌吸引
子密切相关。混沌指发生在确定性系统中类似随机的不
规则
编码规则下载淘宝规则下载天猫规则下载麻将竞赛规则pdf麻将竞赛规则pdf
运
动, 是复杂和不可预测的, 而对称是保持物体等同性的一种刚
体运动, 在动力系统研究中, 人们发现对称和混沌是可以共存
的 [ 1- 4] :混沌吸引子作为混沌系统整体稳定性与局部不稳定性
共同作用下的产物,深刻反映了确定与随机、简单与复杂、有序
与无序、整体与局部等不同的混沌机理的重要转化过程。随着
计算机技术的发展, 混沌吸引子不再是一个抽象的概念, 混沌吸
引子可视化技术逐渐得到重视。文献 [ 1]从 Log istic映射出发,
构造一簇复映射, 生成具有循环群 (Cn )、二面体群 (D n )和部分
晶体群 ( cry sta llographic group)对称性的混沌吸引子,文献 [ 3 ]选
取平面上具有对称性的三角函数族, 通过迭代并记录下由迭代
产生的点, 生成平面上 7种带群 ( fr ieze groups)和 17种晶体群
( wa llpaper g roups)的混沌吸引子。在此基础上, 群对称性图像
的动力系统计算机可视化研究已得到了国内外学者的广泛重
视 [ 6- 9]。文献 [ 6]改进单纯形算法构造平面晶体群动力系统的
广义 M 集;文献 [ 7- 9]提出分别利用轨迹井技术和从构造不变
函数的动力系统角度出发, 计算机自动生成了具有晶体群对称
性和循环群、二面体群对称性的艺术图像。
本文尝试在 Escher的几何图方法 [5]的基础上,从动力系统角
度出发,构造具有自相似性质的晶体群圆极限分形图。同时, 对
Carter晶体群混沌函数,本文进一步探讨了 Escher构图法的边界着
色无缝隙构图条件,并生成了边界着色无缝隙的圆极限分形图。作
者所提供方法生成的图像颜色丰富,具有很强的艺术渲染力,因此
为计算机生成平面对称群艺术分形图像提供了一种新途径。
1� 平面晶体群描述
在二维平面中有四种基本的对称性: 平移、旋转、反射、滑动
反射。晶体对称群具有两个方向平移不变性。在平面对称群的
分类中,存在 17种不同的晶体群, 用传统的记法分别为 p1, p2,
pm, pg, pmm, pmg, pgg, cm, cmm, p3, p3m 1, p31m, p4, p4m, p4g, p6,
p6m。文献 [ 3]讨论了如何用三角迭代函数系统生成这 17种对
称群的混沌吸引子。这里我们仅讨论生成 p4晶体群的混沌函
�
第 8期 � � � 鲁坚等: 动力系统生成晶体群圆极限分形图 19���
数, 其它对称群混沌吸引子的生成方法详见文献 [ 3]。
定义 1� 设 �: R2 ∀ R2是群 G的一个元素, F: R2 ∀ R 2为一
个动力系统。如果 F满足:
�(F ( x, y ) ) = F ( �( x, y ) ) ( 1)
则称 F (x, y )关于 �等价;若 F (x, y )关于群 G的每一个元素均等
价,则称 F (x, y )关于群 G等价,或称 F (x, y )具有群 G对称性。
群 p4包含旋转 90度对称和两个方向平移对称,关于 p4对
称群的等价函数, 本文采用直角坐标平面上如下函数形式 [ 3] :
F
P
x
y
=
x
y
+ T (x )# P# T (y ) � m od 2�
2� ( 2)
其中: T (x ) = ( 1, co s( x ), cos( 2x ), sin ( x ) , sin ( 2x ) ), P = ( p ijk )
是一个 5 ∃ 2 ∃ 5的实参数矩阵。可以通过对参数矩阵 P 的限定
使得函数 (2)关于 p4的两种对称性等价。
定义 2� 设 �: R2 ∀ R 2是群 G的一个元素,如果函数 f: R2 ∀
R满足:
f (�( x, y ) ) = f ( x, y ) ( 3)
则称 f ( x, y )关于 �不变;若 f( x, y )关于群 G的每一个元素均不
变, 则称 f ( x, y )关于群 G不变。
结合等价函数, 文献 [ 7]探讨了从动力系统角度出发利用
不变函数作为绘图策略生成 p4晶体群艺术图像的方法, 例如,
生成图 1采用的不变函数为 f( x, y ) = cos( x2 + y 2 ) + 1+ 15 | cos
( 2x ) |,着色半径为 r = 3�- 1。关于不变函数绘图算法的详细
描述可参考文献 [ 7]。
2� 圆极限分形图构造
设 是上半平面区域 = { ( x, y )T % i2 |y> 0},并设图像的方
极限绘制区域为 ! = { (x, y ) % i2 |0& x& R, 0& y & R } (如图 1( a)所
示 )。考虑晶体群对称混沌函数的平移 2�周期性 (见 (2)式 ),基本
单元为 ∀ = { (x, y ) % i2 |0& x& 2�, 0& y& 2�},令 U为上半平面其
他正方形区域,则 U可通过如下仿射变换 T: ∀∀ U得到:
T
x0
y0
=
2n � 0
0 � 2n
x 0
y 0
+
mg # 2�# g2n
0
=
x 1
y 0
( 4)
T - 1
x1
y
0
=
2- n � 0
0� 2- n
x1
y
0
-
mg# 2�
0
=
x0
y0
( 5)
其中 ( x 0, y0 ) % ∀ , ( x 1, y1 ) % U; n, m = 0, ∋ 1, . . . ; 因为 T是
单的、满的、连续的映射, 且 T - 1也连续,因此 T是一个同胚仿射
变换。根据上述几何变换关系 ,对于绘制区域为 ! 中的每一个
像素点 ( x, y ) ,首先需要变换为基本单元 ∀ 中的对应点相对坐
标 ( x(, y()。对于 ( x, y ) % ! , 注意到必存在整数 n , 有 y )
1
2
n
R ,于是 n = log 1
2
y
R
,其中 ∗a�表示取整数 ) a。记
R(= 1
2
n
R ,则 y(= 2�y
R( , x(=
2�# m od( x, R ()
R( 。
图 1� 上半平面极限图的模版图
� � 由复变函数理论中的保角映射, 将上半平面 保角映射到
单位圆盘 D 上, D = { z % + - , z | < 1} ,其中 +为复平面。
g: ∀ D, g ( z ) = e iz ( 6)
其中 z= x + iy, y > 0。按照此方法可得到由 p4晶体对称性图像
(图 2)生成的彩色圆极限分形图 (图 3);同样, 图 4, 图 5分别是
由 p4m, p3晶体对称性图像生成的彩色圆极限分形图。
� � 图 2� 由不变函数生成的 p4晶体群图像 � � � � � � �
图 3� 图 1的
圆极限分形图 �
�
图 4� p4m 晶体
群圆极限分形图 � � � � � � � �
图 5� p 3晶体群
圆极限分形图
为了使拼砌块间平滑过渡, 应使相应边界点颜色相同 (参
考图 1) ,即应使得基本单元 ∀ 对应衔接边界点颜色相同。设 q1
= ( 0, y ) , q2 = (x, 0) , q3 = ( 2�, y ) , q4 = ( x, 2�) , 注意到
FP 为 2�周期的函数, 则 FP ( q1 ) = FP ( q3 ) ,从而 q1和 q3有相
同的颜色; 同样 q2和 q4有相同的颜色;考虑到拼砌块是 y轴反
方向 1
2
的倍数减小, 于是要求 FP ( q2 ) = FP 1
2
q2 。
代 q2入迭代函数 FP 有 FP ( x, 0) = T (x ) # P # ( 1, 1, 1, 0,
0)m od( 2�, 2� ) , 则:
FP (q 2) =
p 000+ p 001+ p 002+ (p 100+ p 101+ p 102 ) cosx + (p 200 + p 201+
p 202 ) cos2x + (p 300+ p 301+ p 302 ) sinx + (p 400+ p 401+ p 402) sin2x
p 010+ p 011+ p 012+ (p 110+ p 111+ p 112 ) cosx + (p 210 + p 211+
p 212 ) cos2x + (p 310+ p 311+ p 302 ) sinx + (p 410+ p 411+ p 412) sin2x
类似得:
FP
1
2
q2
=
p
000
+ p
001
+ p
002
+ ( p
100
+ p
101
+ p
102
) cos
1
2
x + ( p
200
+ p
201
+ p
202
) cosx
+ ( p300 + p301 + p302) s in
1
2
x + (p 400+ p 401+ p 402) s inx
p 010+ p 011+ p012+ ( p110 + p 111 + p 112) cos
1
2
x + ( p210 +
p 211+ p 212) cosx + ( p310 + p311 + p302) s in
1
2
x + (p 410+ p 411+ p 412) s inx
通过计算, 当 p
i, j, k
= 0, i = 1, 2, 3, 4, j = 1, 2, k = 0, 1, 2
时, FP ( q2 ) = FP 1
2
q2 。
图 6为边界颜色无缝隙的上半平面方极限图, 等价函数的
参数 P为: p 000= - 0. 2508, p001 = - 0. 6383, p 002 = 0. 2748, p003 =
(下转第 55页 )
�
第 8期 � � � 刘向虎等:求矩阵复特征值的双种群改进遗传算法 55���
图 8� 特征根的投影
程序中的结果与 MATLAB7. 0中的结果比较如表 3所示,
与
标准
excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载
遗传算法比较如表 4所示。
表 3� 程序中的结果与 MATLAB7. 0中的结果
特征根 #1 #2 #3
改进的
GA程序
运行结果
- 0. 2709946
2351423+
0. 0000146
6543780 i
2. 0457552
9436173+
0. 0000307
3179044 i
4. 4211953
4762183+
0. 0000226
8527614 i
MATLAB
7. 0中的
结果
- 0. 2709933
3959821
2. 0457697
3046372
4. 4211970
2778307
特征根 #4 #5
改进的
GA程序
运行结果
- 1. 29795341652837+
2. 781635847162219 i
- 1. 29795324516872-
2. 781613283627521 i
MATLAB
7. 0中的
结果
- 1. 29798670932430+
2. 78164819251385 i
- 1. 29798670932430-
2. 78164819251385 i
表 4� 简单遗传算法与改进遗传算法迭代次数
特征根 简单 GA的迭代次数 改进 GA的迭代次数
#1 46 7
#2 31 3#3 57 11#4 82 15
#5 65 13
4� 小 � 结
双种群改进遗传算法由于采用了双种群进化、可变的交叉
概率和变异概率, 并且采用了柯西变异, 提高了个体跳出局部最
小的能力。从而得到矩阵的复特征值, 寻优效率较标准遗传算
法有了大幅提高, 具有很强的鲁棒性和广泛的适应性。本文采
用双种群改进遗传算法来求解矩阵的复特征值 ,取得了比较好
的效果, 为矩阵问题的求解提供了一种方法。
参 考 文 献
[ 1 ] H om R A, Johnson C R. M atrix Analys is, Chap ter 6 [M ]. London: C am�
bridge Un iv Press, 1985.
[ 2 ] GeneH, Co lub CharlesF, V an Loan. M atrix Compu tat ion s[M ] . Am eri�
can: JohnsH opk in sUn iversity Press, 1983.
[ 3 ] 钟绍军.矩阵特征值的估计与定位 [ J] .长沙大学学报, 2005 ( 5) :
21�23.
[ 4 ] 陈惠明.一种改进的遗传算法及其应用 [ J] .福建电脑, 2006 ( 3) :
118�119.
[ 5 ] 陈大新.矩阵理论 [M ] .上海交通大学出版社, 1991.
[ 6 ] 李全龙,徐晓飞.动态联盟伙伴选择的一种自适应遗传算法 [ J] .
高技术通讯, 2001, 10( 1 ): 66�69.
[ 7 ] 赵燕伟,吴斌,蒋丽,等.车辆路径问题的双种群遗传算法求解方法
[ J] .计算机集成制造系统 − C IMS, 2004, 10 ( 3) : 303�306.
(上接第 19页 )
0. 1340, p004 = 0. 2087, p 013 = - 0. 7554, p014 = - 0. 4887, p103 =
- 0. 7972, p104 = 0. 9962, p 113 = 0. 3232, p 114 = - 0. 2118, p203 =
0. 3987, p204 = 0. 9418, p213 = 0. 4695, p 214 = 0. 1236, 其他 p ijk = 0。
图 7为图 6的圆极限分形图。
� �
� � 图 6� 边界颜色无缝隙� 的上半平面方极限图 � � � � � � � �
图 7� 图 6的圆
极限分形图
3� 结 � 语
平面上的晶体群混沌函数通过构造对应的不变函数可以从
动力系统角度生成相应晶体群对称性图像。本文利用 Carte r迭
代函数系统的平移 2�周期性, 确定基本区域, 通过同胚仿射变
换生成了晶体群上半平面极限分形图, 进而利用保角变换生成
圆极限分形图。其它晶体群 (例如 cm, pm, p3m等 )的彩色圆极
限分形图类似可以得出。同时, 对 C arter混沌函数进一步探讨
了边界着色平滑构图条件, 并生成了相应的圆极限分形图。本
文所提供方法生成的图像具有很强的艺术渲染力 ,因此为计算
机生成平面对称群艺术分形图像提供了一种新途径。
参 � 考 � 文 � 献
[ 1 ] F ieldM, Golub itsky M. Symm etry in chaos[M ] . New Y ork: Ox fordUn i�
vers ity Press, 1992.
[ 2 ] A rm strong M A. Groups and symm etry[M ]. New York: Springer�V er�
lag, 1988.
[ 3 ] Carter N C, Eag les R L, H ahn A C, et a.l Chaotic attractors w ith d is�
crete planar symm etries [ J ] . Ch aos, Sol iton s and F ractals, 1998, 9
( 12) : 2031�2054.
[ 4 ] Jon esK C, ReiterC A. Chaotic attractorsw ith cyclic symm etry rev is ited
[ J]. Com puters& Graph ics, 2000, 24 ( 2) : 271�282.
[ 5 ] Chung K W, ChanH SY, W ang BN. Sm aller and sm aller from dynam ics
[ J] . Com puters and graph ics, 1998, 22( 4) : 527�536.
[ 6 ] 陈宁,金华,李晓莉.改进单纯形算法构造平面晶体群动力系统的
广义 M集 [ J].小型微型计算机系统, 2006, 27( 2 ) : 359�364.
[ 7 ] Lu J, Y e Z X, Zou Y R. Au tom at ic gen erat ion of co lorfu l pattern sw ith
w allpaper symm etries from dynam ics[ J ]. The V isual C om pu ter, 2007,
23: 445�449.
[ 8 ] Lu J, Y e Z X, Zou Y R, et a.l Orb it trap rendering m ethod for genera�
t ing art is tic im agesw ith crystallograph ic symm etries[ J] . Com puters and
Graph ics, 2005, 29 ( 5) : 794�801.
[ 9 ] ZouY R, L iW X, Lu J, et a.l Orb it trap rendering m ethod for genera�
t ing art is tic im ages w ith cyclic or d ih edral symm etry [ J] . C ompu ters
and Graph ics, 2006, 30( 6) : 471�474.