（通信与信息系统专业论文）基于分形理论的水墨画仿真算法研究及硬件实现.pdf

基于分形理论的水墨画仿真算法研究及硬件实现 摘要 对传统绘画艺术进行计算机仿真是计算机技术领域最具挑战性 的课题之一，特别是对于水墨画的计算机仿真领域的研究，尚处于起 步阶段。本文在前人工作的基础上，对水墨画仿真中的几个关键问题 进行了深入的研究和探索，建立了相应的仿真模型，取得了很好的仿 真效果。 分形理论是近二、三十年才发展起来的一门新的学科，其主要描 述自然界和非线性系统中不光滑和不规则的几何形体。分形理论己广 泛应用于各个领域，如数学、社会科学、计算机、艺术等领域。因此， 分形理论的研究既具有重要的理论意义，又具有广泛的实际应用价 值。本文使用分形算法来生成我们所要处理的图像元素，利用v i s u a l c + + 6 0 良好的用户界面和强大的图形编程技术，设计出分形图生成软 件。本文提出了一个基于物理结构的宣纸模型，同时提出了一个改进 的基于粒子系统的动态水墨扩散算法。完成上述工作之后，把系统进 行整合，实现一个完整的水墨画仿真系统。最后，把编写的代码进行 基于d s p 平台的移植与优化。 本文将分形理论与水墨画的计算机仿真技术进行了有机的结合， 开拓了水墨画计算机仿真的研究领域，取得了令人满意的艺术效果。 关键词：水墨画；计算机仿真；分形；d s p i i t h er e s e a r c ho nt h es i m u i 。a n 0 na l g o r i t h m0 f 验t e r i n kp a i n t i n gb a s e do nf r a c l = a lt h e o r y a n dt h er e a l i z a r l 0 no nt h rh a r d c f 气r e a b s t r a c t o n eo ft h ec h a l l e n g i n gw o r ki nc o m p u t e ra r tr e s e a r c hf i e l di st o s i m u l a t et h et r a d i t i o n a lp a i n t i n g ，e s p e c i a l l yi nw a t e r - i n kp a i n t i n g ，i ti ss t i l l i ni t si n f a n c y r e f e r e n c i n gt h ef o r e g o e r sr e s e a r c ha c h i e v e m e n t ，t h i sp a p e r e x p l o r e ss e v e r a lk e yi s s u e si nt h es i m u l a t i o no fc h i n e s ep a i n t i n gd e e p l y ， s e tu pac o r r e l a t i v es i m u l a t i o nm o d e l ，g e t sas a t i s f a c t o r ys i m u l a t i o nr e s u l t f r a c t a lt h e o r yi sas c i e n c en e w l yd e v e l o p e di nt h ep a s t2 0t o3 0y e a r s ， i tc a nd e s c r i b er o u g h n e s sa n di r r e g u l a rg e o m e t r i cs h a p e si nt h en a t u r eo r i nn o n l i n e a r s y s t e m f r a c t a lt h e o r y i se x t e n s i v e a p p l i e d t o m a n y f i e l d s ，s u c ha sm a t h e m a t i c s 、s o c i a ls c i e n c e 、c o m p u t e r 、a r ta n ds oo n i n c o n s e q u e n c e ，t h er e s e a r c ho nf r a c t a lt h e o r yh a sb o t hi m p o r t a n tt h e o r e t i c a l s i g n i f i c a n c ea n de x t e n s i v ea p p l i e dv a l u e i nt h i sp a p e r , b yu s i n gf r a c t a l a l g o r i t h m ，i tg e t st h ee l e m e n t so fi m a g ew h a th a v et op r o c e s s i t t a k e s a d v a n t a g e o fv i s u a lc + + 6 0t h eb e t t e ru s e ri n t e r f a c ea n dm i g h t y c o m p u t e rp r o g r a m m i n gt e c h n o l o g y ，d e s i g n st h e s o f t w a r ew h i c ht o g e n e r a t ef r a c t a li m a g e s i tp r o p o s e sap a p e rm o d e lb a s e do np h y s i c a l i i i s t r u c t u r e ，a tt h es a m et i m e ，i tp r o p o s e sa ni m p r o v e dw a t e r - i n kd i f f u s e a l g o r i t h mb a s e do np a r t i c l es y s t e m a f t e rt h a t ，i n t e g r a t e ss y s t e m ，m a k e sa c o m p l e t es i m u l a t i o ns y s t e m a tl a s t ，t r a n s p l a n t e sa n do p t i m i z e st h ec o d e i nt h ed s pp l a t f o r m t h i sp a p e rc o m b i n e st h ef r a c t a lt h e o r ya n dt h ec o m p u t e rs i m u l a t i o n t e c h n o l o g y , e x p l o i t st h ef i e l do ft h ec o m p u t e rs i m u l a t i o ni nw a t e r - i n k p a i n t i n g ，a c h i e v e ss a t i s f a c t o r yr e s u l t s k e y w o r d s ：w a t e r - i n k p a i n t i n g ；c o m p u t e rs i m u l a t i o n ；f r a c t a l ；d s p i v 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 本人为获得浙江工商大学或其它教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示谢意。 签名： 魄叩年；月护 关于论文使用授权的说明 本学位论文作者完全了解浙江工商大学有关保留、使用学位论文 的规定：浙江工商大学有权保留并向国家有关部门或机构送交论文的 复印件和磁盘，允许论文被查阅和借阅，可以将学位论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制 手段保存、汇编学位论文，并且本人电子文档的内容和纸质论文的内 容相一致。 保密的学位论文在解密后也遵守此规定。 签名：蚪导师签名：驻臣1 日期：坤年月坯日 1 1 本课题研究的意义 第1 章绪论 对传统绘画艺术进行仿真是计算机艺术领域最具挑战性的课题之一，在吸取 传统绘画艺术的营养、弘扬传统绘画艺术成就的同时，对计算机仿真绘画技术提 出了新的要求。鉴于传统绘画艺术自身的魅力以及计算机艺术的科学与艺术双重 性，艺术效果的计算机模拟生成己经超出了科学仿真的一般意义i 。 随着计算机图形学技术的飞速发展，人们对真实绘画进行了大量的模拟实现 方法的研究，不断引入新的图形学技术，在油画、水彩画等西画系的艺术品类上 取得了卓越的成果。然而，对于东方画系的中国水墨画，尚未有任何的研究尝试， 这对计算机艺术领域不能说不是个缺憾。由于中西两大视觉体系的艺术文化差异 以及中国水墨画自身的特殊性，水墨画艺术效果的计算机仿真实现有着很大的难 度，对水墨画的仿真研究仍处于原始状态。 对中国水墨画进行计算机仿真研究，在艺术以及科学领域，都有着深远的意 义。计算机程序员既不是概念上的艺术家，也不是业余的美术爱好者，没有艺术 方面的训练，只注重程序算法技巧而忽略了审美规律。艺术家艺术家则急于利用 计算机产生的新艺术效果来表达他们所能表达的一切，对计算机技术却是一片茫 然。在这明显矛盾的目标之问的相互撞击中，产生了计算机在艺术领域的仿真技 术。在计算机艺术中引入和继承中国画的审美理论、表现和传播中国画的美学成 就，对中国画的变革和发展是有着积极意义的。 艺术界持续几十年之久的中西之争，在超越绘画材料的限制之后获得新的自 由度，在关于中国画前途的论争中或许能够得到一些有益的启发。f 视计算机对 艺术领域的冲击、客观地分析计算机艺术与中国传统艺术的关系，在计算机艺术 的发展中，积极地溶入中国传统艺术的审美成就，对弘扬民族文化以及使中国几 千年的艺术文化在未来的历史进程中发挥其应有的影响和作用，是有积极意义 的。同时，水墨画计算机仿真生成的研究成果在计算机图形技术应用中的非写实 渲染，自动水墨画效果处理，交互式作图以及虚拟作画等方面有着广泛的应用前 景。对于丰富图形渲染领域的处理手段，推动计算机仿真技术的发展也将起到积 极作用。 中国画( 这里特指中国水墨画) ，作为东方艺术的典范，有着举世无双的悠 久历史，其独特的审美与鲜明的本体特征使它自成体系，独立于世界艺术之林。 鉴于中国画重要的美学地位以及对世界美术的贡献，中国画的发展与变革进程对 整个人类的文明史有着重要的影响。 所以，对中国水墨画的仿真研究，无论在科学还是在艺术方面，都有着深远 的意义。 本文所使用的原始图像素材是基于分形理论生成的，分形理论诞生后，人们 意识到应该把它作为工具，从新的角度来进一步了解自然界和社会。分形涉及的 领域极为广泛，在数学、物理、化学、材料科学、医学与生物、地质与地理学、 地震和天文学、力学、计算机科学乃至经济、社会、艺术等领域都有重要的应用 价值。 分形几何学能为自然界中存在的各种景物提供逼真的描述。这些景物形态复 杂、不规则，而且显得十分的粗糙，使得采用传统的几何工具进行描述遇到了极 大的困难，而分形模型却能很好地描述自然景物，因为自然界中的许多实际景物 本身大体上就是分形，或者反过来说，按照分形几何方法构造的形体非常像许多 自然景物。随着计算机在图像处理方面的技术的成熟，用计算机生成分形图形， 使人们能获得外观新颖奇特、内容丰富多彩的平面图形。 1 2 本课题相关领域研究现状 1 2 1 分形领域研究现状 本文关于分形理论的研究主要集中在分形图形生成方面，因此我们将着重介 绍关于分形图的计算机生成方面的研究现状。 基于l 系统以及i f s 系统的自然景物的模拟是近期研究的热点问题之一，有许 多学者发表了该领域的相关学术论文。冯莉【2 】等提出了一个改进的基于l 系统的 三维植物生成算法，通过该算法，生成的植物逼真、自然，皆可交互控制其生成。 孙轶纠3 】提出了一种在l 系统分形算法基础上的树木模型参数化生成方法该算法 将树木模型先进行参数化处理，然后将分形计算产生的树木模型数据按层次储存 起来，并根据视点与树模型的距离确定所需树木模型数据的层次，从而充分发挥 了应用分形技术生成的树模型真实感强的优点，消除了分形计算耗时长的缺陷， 保证了树木生成的真实性和实时性。华中科技大学马石安等人【4 】给出了一种基于 迭代函数系统i f s 的森林景物的动态模拟方法。首先介绍了以迭代函数系统来探 索和解决森林树木这一类自然景物在计算机生成问题的途径，然后从一个已模拟 景物的i f s 吸引子出发，改变参数自动生成无重复的序列图画，以此达到对森林 景物动态模拟的目的。用此方法生成的前后两帧图形之间即有区别，又具有相对 的连续性，为计算机对复杂自然景物的动态模拟提供了一条新的途径。张文辉等 人1 5 j 首先分析迭代函数系统中i f s 码产生原理，阐述i f s 如何模拟植物形态，然后 依据拼贴定理，研究i f s 码的变换特点，并利用i f s 码的连续性探讨i f s 码变换的规 律及表现效果。并通过增力h i f s 码，对分形图进行变换，逼真模拟森林、草地等自 然景观。美国两位数学家m i c h a e lf r a m e 和t a t i a n ac o g e v i n a l 6 j 给出了由i f s 得到的 一种圆倒置的有限集生成的自相似的分形图形。典型的特例是，这些图是由一些 圆组成的，这些圆是相互在外部的，即每个圆都在其它圆的外部。如果放宽圆是 相互在外部的限制，又可构造出无限延伸的圆倒置的有限集一一它不同于一般的 i f s 分形图像，是一个给人强烈感觉的比例相互独立的分形集。 1 2 2 水墨画仿真的研究现状 在水墨画方面的研究，主要有以下几个问题： 模拟一支逼真而易于使用的毛笔； 模拟墨汁扩散现象： 减轻模拟过程中的计算量，加快仿真速度； 中国古画的修复与画家绘画风格的归纳、识别等； 在中国水墨画扩散的模拟方面，有学者运用纹理匹配( t e x t u r em a p p i n g ) 的 方式来表达墨汁扩散结果【7 】【8 l 【9 】1 1 0 1 ，先在2 d 或3 d 的模型下找出轮廓线 ( s i l h o u e t t e ) ，来代表毛笔作画所要经过的路径，再选择适当的纹路贴到笔触上。 然而墨汁在宣纸上的扩散现象极为复杂，画家在作画时所用的墨汁与宣纸初始状 态不同，扩散后的墨迹便大相径庭，陈永年1 1 1 l 在纹理匹配后引入特定的噪声函数 ( n o i s ef u n c t i o n ) ，尝试模拟手工绘画时所产生抖动的效果，但轮廓线内部区域仍 3 需使用扩散模块才能产生扩散的渲染效果 一部分学者认为墨汁的材料与水彩画相似，希望导入水彩的扩散膜式来仿真 水墨扩散。如：s a m a l l 1 2 l 在水彩画的模拟采取三个步骤。c u r t i s t ：3 】继续加强s a m a i i 研究的模拟架构，将水彩在纸上的扩散行为分成三个阶段，提出了以浅水层 ( s h a l l o w - , w a t e rl a y e r ) 、颜料沉淀层( p i g m e n t d e p o s i t i o nl a ，e r ) 和毛细管层 ( c a p i l l a r yl a y e r ) 三层结构的模型。 另一类研究是以媒材性质来探讨水墨扩散现象，g u o t l 4 l 认为墨汁是一种胶体 溶液( c o l l o i ds o l u t i o n ) ，g u o 将纤维密度分成四个等级，碳粒子在四个等级的纤维 中有不同的扩散速率，粗略的划分出扩散后的墨韵。k u n i i 1 5 】认为g u o 的纤维密 度分成四个等级太粗略，扩散的速度方程式无法详细表现墨汁的扩散现象，因此 提出了一个“多维数扩散模型( m u l t i d i m e n s i o n a ld i f m s i o nm o d e l ) 的方法来说明 来说明墨汁的扩散现象，他将墨汁的扩散分成水和碳两个维数来处理。 l e d l 6 1 将墨汁滴在静止的水中，记录墨汁的扩散纹路，他的实验结果发现， 墨在水中的扩散系数和墨迹的关系，其结果符合k u n i i 的推论。 w a n g t l 7 】1 1 8 】实际运用k u n i i 的模型时，认为k u n i i 的扩散方程式未考虑到纸张 的结构，w a n g 针对纤维的分布不均匀状态导致扩散常数不一致，及纸张的倾斜 角度、重力等因素对扩散的影响，改进k u n i i 原先提出的扩散方程式。在纸张纤 维分布上，w a n g 参考其他学者( 1 4 1 5 1 7 l 【1 9 】提出了几种纤维纹路的宣纸，让墨汁向 外扩散时，各方向的扩散系数不同，呈现不规则的纹路。 h u a n g 2 0 】分析了墨汁在纤维中的运动现象，归纳出影响扩散的几个主要因 素，如相邻水分子的梯度、纸张的吸水性、纸张的纹路及水流动的惯性等。 z h a n g l 2 1 】提出以二维细胞自动机 e l l u l a r 卸t o m a t o n ) 的机制，将纸张视为具有 许多储水功能的纤维筒( c e l l ) ，并提出各纤维筒之间的扩散膜式，计算相邻纤维 筒之间水分的流动关系。纤维筒的参数依纸张的纤维数量而定，当纤维数量越多， 纤维筒的基底越小，可以储存水分越多，纤维的含水量也越高。 k e 【1 9 】【2 2 l 着重于扩散速度的改善，提出了波动构想( w a v es c h e m a ) 的墨汁流 动法则，减轻扩散时的计算量，让墨汁的扩散效果能运用于实时图像显像系统上。 g u o 2 3j 重新定义一个纸张的纤维网格数据( f i b e 卜m e s h d a t a ) ，在纸张上每个点 分别记录与4 o ，定义 h ；( ，) = i n f 砉l 卜 ) 是f 的6 覆盖 ( 2 2 ) 2 - 2 式中i n f ：是f 确界的缩写。考虑所有直径小超过6 的f 的覆盖，并试图便 这些直径的s 次幂的和达到最小。当6 减少时，式( 2 - 2 ) 0 0 能覆盖f 的集类是减少的， 所以下确界h ；( f ) 相应增加，且当6 呻。时趋于一极限。记为 h 3 ( ，) = 溉饿( ，) ( 2 3 ) 对r “中的任何子集f ，这个极限都存在，但极限值可以是( 并且通常是) 0 或，称h 5 ( f ) 为集的s 维h a u s d o 删0 度。 h a u s d o r f - f 澳1 度推广了长度、面积和体积等常见的概念。长度、面积和体积的 比例性质是众所周知的，当比例为原来a 倍时，曲线的长度为原长度的a 倍，平 面区域的面积则是原面积的a 2 倍，三维物体的体积是原体积的a 3 倍。可以推测， s 维h a u s d o r f 澳1 度应当是原来的九5 倍，这个比例性质是分形理论的基础。可用数学 公式描述如下： 设s 是相似比为a 0 的相似变换，如果fcr ”，则 h 5 ( s ( ，) ) = 日5 ( f ) ( 2 - 4 ) 证明 若 配) 为f 的一个6 覆盖，则 s ( 饥) ) 为s ( ，) 的一个柏覆盖。所以 l s ( u 川5 = a5 i u 故取下确界有 日磊( s ( ，) ) s a 5 饿( f ) 令6 一。即得日5 ( s ( ，) ) sa 5 h 5 ( ，) 。用s - 1 替代s 上式的a 成了，则集合f 由 s ( f ) 得到了需要的反向不等式，性质得证。 h a u s d o r f f 在h a u s d o r f 做4 度的的基础上，引入h a u s d o r f f 维数概念，定义如下： 对任何给定的集fc r “且6 s ，且 ) 为f 的个6 覆盖，则有 ms m ”i u t l 5 s 6 h u 厅 ( 2 - 5 ) 取下确界得哦( f ) s6 卜5 日；( f ) 。令6 - , 0 ，可见对于t s ，若h 5 ( f ) 0 0 ，则 h ( ，) = o 。所以日( f ) 关于s 的图( 见图2 1 ) 表明，存在s 的一个临界点使得日5 ( f ) 从0 0 “跳跃 到0 。这个临界值称为f 的h a u s d o r f 雠数，记d i m 日f 。 h 5 ( f ) o s 图2 1 集f 的h ( f ) 的图。h a u s d o r f f 维数是使从“跳跃”到。发生的s 的值 这个定义可以用下式表达： d i m 日f = i n f s a0 ：h 5 ( f ) = 0 ) ；s u p s ：h 5 ( f ) = )( 2 - 6 ) 所以 ，、r ( f ) 2 佰 若0 量s d i m 日f 如果s = d i m 日f ，则h 5 ( f ) 可以是零或者无穷或者满足 ( 2 7 ) o 日5 ( f ) d i m h 互，对于任袁c j ，则必有日p ( ) - o ，同时有 h p ( u e ) z 0 ，于是对于任意j 有 h p ( ) 苫h ，( u e ) ( 5 ) 可数集，如果f 是可数集，则d i m f 一0 。因为若( 是单个点，必 d i m hu f , 一0 有日o ( 曩) = 1 r d i m 日一0 ，由性质4 ，d i m h u e , - 0 。 其他分形维数还有龠维【矧、填充维、信息维【3 l 】等。 2 1 3 分形的主要应用领域 现在分形几何已成为非线性科学中的一个重要分支，它的思想和理论已经渗 透到自然科学中的各个领域。在数学、材料科学、地质勘探、疾病诊断、计算机 及信息科学领域中都得到了广泛的应用，尤其在以下几个方面取得重要成就： 1 图像、数据压缩方面； 分形理论在图像、数据压缩技术中发挥了重要作用。b a r n s l e y ，c o l l a g e 等应 用迭代函数系统编码在分形信息压缩方面做了有益的尝试。2 0 世纪8 0 年代末，美 国数学家b a r n s l e y 提出了一种利用图像本身的复杂性中包含的自相似性进行压缩 编码的新方法。b a m s l e y 和s l o a n 在一片文章中令人惊讶地宣称，利用他们的方法 对静止图像压缩可获得高达1 0 0 0 0 ：1 的压缩比。这当然在从事图像压缩的人群中 引起了极大的震动。 分形图像压缩编码方法适用于二值图和灰度( 彩色) 图像，其理论基础就是前 面所提到的迭代函数系统( i f s ) 理论。从目前的实际情况来看，分形图像压缩的 效果远非像b a m s l e y 等人所宣称的那样令人满意。事实上，在分形图像压缩的理 论研究方面还存在着不少问题，但作为一种新的图像编码框架，其前景仍是十分 光明的。 2 生物医学方面； 采用分形分析方法对某一地区植被景观形状和各类种群分布特征进行分析， 研究群落多样性随空间变化的变异规律；通过对水生态系统空间格局研究，确定 生态因子场的分性特征及水生生物体重与体长关系等参数，为水产养殖业提供有 1 0 力的科学支持。 应用分形测度的概念，在超声波图像检测中，建立超声图像表面分形结构分 析及局部分形指数研究的理论模式，根据分形维值的变化来达到对医学图像边缘 检测和增强的目的，更好的识别图像中的病变结构为医学图像处理和分析领域提 供了新的手段和方法。 3 分形生长模型方面； 很多自然界中的物体明显地以分形的形式生长，分枝重复的分裂产生了更小 的分枝。当用适当的尺度观测一些树、一些根系和一些植物时，它们看起来都像 是分形的。分形方法提供了一种描述自然界各种生长现象的新的模型。著名的d l a 模型、l 系统模型在模拟无机生长现象和植物生长形态描述方面取得了令人鼓舞 的成功，各种新的模型和方法也正在不断发展之中。 4 计算机图形学方面； 作为“t h eg e o m e t r yo fn a t u r e ”，分形几何在描述自然界的真实特征和细节纹 理方面具有特殊的作用。因此，分形技术是计算机真实感几何造型方面十分活跃 并且有效的方法和手段。同时，计算机的应用也大大地推动了分形理论的发展， 并形成了一种新的研究领域：计算机实验数学。目前，国外已经推出多种不同的 以分形技术为特征的计算机绘图软件，而且在许多产品设计中也用到了分形的思 想和方法。混沌分形理论在信息压缩、传送及自然景观的模拟中发挥了重要作用。 5 经济管理方面： 将分形理论的动念维数应用于期货价格行为的研究，能够克服现有技术分析 法在价格预测上具有时滞性的不足，还能够用于预测期货的价格趋势。应用常维 或变维分形模型预测股票指数，预测时先将原始数据进行一系列的变换，从中选 出一种变换，使变换后的数据能与分形模型符合良好，再针对股市所具有的混沌 特征测定出混沌吸引子并计算该吸引子的关联维数，从而可以得到股市波动复杂 程度的定量值。 6 艺术领域； 把分形理论与数字图像处理技术结合起来，使生成的分形图形可人工干预， 以产生协调自然，丰富多彩，并具有较高艺术性的图案。这些分形图形对绘图、 雕塑、建筑设计、印染工业、装潢和广告设计等产生深远的影响。 2 2 生成分形图形的常用方法 2 2 1 文法构图算法 文法构图算法是仿照语言学中的语法生成方法来构造图形的一种算法。1 9 6 8 年，美国生物学家a r i s t i dl i n d c n m a y e r 在研究植物形态的进化与构造是提出了一 种文法描述方法：g r a f l a l ，后来发展为分形语言的一个重要分支，称为 l - s y s t e m s ( l s ) 。l s 文法是一类独特的迭代过程，其核心概念是重写。作为一种 形式语言，l s 文法用字母表和符号串来表达生成对象的初始形式，称为公理 ( a x i o m ) ，然后根据一组产生式重写规则，将初始形式的每个字符依次替换为 新的字符形式，以此过程反复替换重写，最后生成终极图形。 二维l s 文字法的字母表的绘图规则类似于海龟爬行【3 a ，海龟的状态定义为 ( x ，y ，口) ，其中( x ，y ) 表示海龟当前位置，口表示海龟的行进方向。给定步长d 和角度增量6 ，海龟可以反馈下述符号表示的指令： f ：向前移动步长d 并画线，此时海龟状念变成( x ，y ，口) ，其中 x = x + d x s i n a ，y = y + d x c o s a ，在点( x ，y ) 和( x ，y ) 间画一直线段； + ：向左转6 ，龟形的下一状态为( x ，y ，a + 6 ) ，角的正向为逆时针方向； ：向右转6 ，龟形的下一状态为( x ，y ，a 6 ) ； 【：将龟形的当前状态压入堆栈。存入堆栈的信息包括龟形的位置和方向以 及其它一些属性，如所画线段的颜色及宽度等： 】：从堆栈中弹出一个状态作为当前状态，不画线。 在构图时，还要给出循环次数或递归深度，起始符号元即字符串中的每个字 符由生成规则集给出的替代规则进行字符替代，产生一个新字符串，按照规定的 循环次数重复这一替换过程，产生最后的一个字符串，再在计算机屏幕上绘制出 图形。 l 系统的实现算法思想是“字符串替换”，首先要根据起始符号元和替换规 则产生一系列字符串，然后读取字符，按照不同字符表示的意义来执行不同的动 作。因此，其算法实际上是分两个过程完成的。下面简单描述如下： 第一个过程：生成字符串 ( 1 ) 声明并设置公理、产生式规则； ( 2 ) 声明并设置起始点、初始角、迭代步长以及迭代上限等控制参数； ( 3 ) 循环用替换字符串替换种子，直到迭代次数大于迭代的上限。 第二个过程：读取字符并画图 ( 4 ) 逐个读取字符串中的每个字符； 0 ) 根据读取到的字符采取不同的动作： 读取字符为“f ，时，画线段； 读取字符为“+ ”时，逆时针旋转； 读取字符为“”时，顺时针旋转； 读取字符为“【 时，进栈，记录当前状态； 读取字符为】，时，出栈。 2 2 2i f s 迭代函数系统 i f s 迭代函数系统属于一种分形构形系统，是分形几何学的重要分支。1 9 8 1 年，h u t c h i n s o n 首先提出可以用压缩映射方法产生分形【3 3 1 ，1 9 8 5 年，美匪l g e o r g i a 理工学院的数学教授m b a m s l e y 于发明了i f s ，i f s 是分形绘制的典型方法，它主 要是通过若干仿射变换，将整体形态变换到局部，i f s 应用于计算机图形领域， 可以产生许多具有无穷细节、精致纹理的图形【3 4 l 。 下面介绍迭代函数系统的基本理论： 1 仿射变换与压缩映射 在数学上，一个变换s ( 尺“_ 尺4 ) 如果满足条件：s ( x + y ) = s ( x ) + s ( y ) 及 s ( z x ) = a s ( x ) ，其中x ，y e r “，a e r ，则此变换s 被称为线性变换。若当且仅当 x = o 时有s ( x ) = 0 ，则称s 为非奇异的。若变换c o ：r ”_ r “具有形式( x ) = s ( x ) + 口， 其中s 为非奇异线性变换，a 为彤中一点，则c o 被称为仿射变换( 简称仿射) 。本 文用到二维仿射变换，定义如下：定义二维欧氏空间中的仿射变换为 ：r 2 呻尺2 。设x = ( z ，y ) 1 是此二维空问中的一点，经仿射变换后得到点 x = ( z ，y ) 1 ，写成矩阵形式为： ( ；：) 。( ；) 2 ( ：三) ( ；) + ( ；) ( 2 8 ) 其中a ，b ，c ，d ，e ，f 六个参数为实系数，确定一个仿射变换。可以将其分解成平移、旋 转、比例变换等，用下式表示： ( ；：) = ( ；) ；、r ，c s o ；n s 日o - 一q q c s 0 1 n s 驴q ， 1 ( ；) + ( ；) c 2 - 9 ) 其中e , f 为x ，y 方向上的平移分量，0 ，妒为分别围绕x ，y 轴的转角，r , q 是x ，y 方向 上的比例放大系数。 仿射变换具有如下几何特征： ( 1 ) 仿射变换的逆变换仍然是仿射变换； ( 2 ) 仿射变换是线性变换，直线段经仿射变换后仍然是直线段，并且保持线段上 的点的定比不变； ( 3 ) 两平行直线经仿射变换后，仍然保持平行性。因此，平行四边形经仿射变换 后，变为另一个平行四边形； ( 4 ) 任意图形经仿射变换后，其面积将发生变化，为变化前的i 口d - b c i 倍，若 印一6 c i = 1 ，则面积在仿射变换前后不变。 此外，对于一个仿射变换，总可以找到一个非负的数s ：使r “中任意的两个空间 点z 1 ，z ：都满足： i l 珊( z 。) 一( z ：) 0 ss j i z 。一z ：0 ( 2 1 0 ) 其中非负数s 称为映射的l i p s h i t z 常数。上式表明，总可以找到非负数s ，使得 映射像点之间的距离小于原来两点之间距离与s 的乘积。s 可以看作映射1 0 的压 缩比，若s i ，则称仿射变换映射为一压缩映射【3 5 1 。 2 i f s 码及拼贴定理 如果r 2 上的压缩映射集，妒= 11 j sn ) ，哆对应的压缩比( 即q 的 l i p s h i t z 常数) 为s ( o si n m a x s ，) 1 ) ，且对应每一+ t o 一个伴随概率e ： o e 0 0 = 1 ，2 n ) ，套c 一1 。 吸引子定理：设 x ：叱，1 墨咒s ) 是完备度量空间( x ，p ) 上的i f s ，压缩因子 为s ，变换缈：，( x ) 呻f ( x ) 由下式定义：p ) = u 徊) f ( x ) ，则w 是 ( f ( x ) ，) 上压缩因子为s 的压缩映射，即( 形徊) ，矽( c ) ) s s h p ( b ，c ) v b ， c f ( x ) r 存在唯一的不动点( 不变集) 4 f 何) ，满足 r a = w ) 一u t o ( a ) ( 2 1 1 ) - 1 并且对且，( x ) a = l i m 形p ) 月 ( 2 1 2 ) 上式不动点a 称为这个i f s 的吸弓 子，i f s 的吸引子一般都是分形，称为确定 性分形，该定理保证了i f s 的吸引子的唯一存在性以及吸引子的求取方法。 拼贴定理【3 6 j ： 设 ，弓ly = 1 , 2 ，n ) 是一组i f s 码，s 是各个映射哆的l i p s h i t z 常数中最大的一 个，并f ls l ；是任意小的j 下数，t 为r 2 上给定的边界闭合子集。假定甜：己经 选定使得 哪叫 那么 h ( t ，彳) c c n c 4 - 2 ， 积墨性因为墨粒子是不溶于水的细小微粒，纸对墨粒子除了有容墨性之 外，还应有积墨性。当纤维团的容墨数量已经处于饱和( 即 q 或c 口 0 ) 状 时，纤维团仍然对墨粒子具有一定的吸附力( 或称黏附力) ，阻碍墨粒子迁移。墨 粒子只有在克服此力的情况下，才能有迁移的可能。否则，墨粒子将堆积在纤维 团周围，形成积墨现象。 纤维束既不能吸水也不能容墨和积墨，只是水、墨在纤维团之间迁移的虚拟 路径。纤维丝的引入，不仅架起了纤维团之间的桥梁，而且也是纸纤维层与层之 间的纽带，使得纸的内部结构由二维平面转变成三维空间。 纤维束的存在定义了当前纤维团可以和周围哪些纤维团发生粒子迁移。每个 纤维团的下、左、右、前、后纤维团就是当前纤维团的周围纤维团。通过纤维束 的不同分布设置，可以灵活地表征不同宣纸的特性。 4 3 2 纸结构参数对扩散的影响 厚度t ：大量的实验证明，宣纸的有效厚度对水墨沿宣纸的纸纤维移动并 最终形成特殊的纹理效果有着显著的影响。在纤维密度分布不均匀的宣纸上，纸 的有效厚度较小( 纸纤维的分布较稀疏) 处的水墨渗化程度不及有效厚度较大处， 因此，在描述纸的性质时其厚度应予考虑。 致密度d ：致密度通过影响纸的构造过程，以控制纸结构中纤维团和纤维 束的密度，进而影响扩散过程。致密度越大，纤维团越密，连接纤维团的纤维束 也越多，那么水墨粒子越容易扩散，而且粒子运动速度与连接两相连纤维团的纤 维束根数f i b r e i , j 成j 下比：v 。cf i b r e 【i j 】。 吸水力a ：吸水力是指纸张吸收水墨粒子的能力，吸水力越大，水墨粒子 受到的“拉力”就越大，运动速度就越快：v o c a 2 4 3 3 纸模型仿真实现 为实现本文所提出的纸模型，我们先定义一个纸的数据结构。纸的“纤维网 结构包含一个纤维团链表b l o c k l i s t 和一个纤维束列表f i b r e l i s t 。 b l o c k l i s t 中每个纤维团b l o c k 包含内部“细胞 集合c e l l c o l l e c t i o n 以及连 接它的纤维束的集合f i b r e c o l l e c t i o n 。这样一个数据结构可以表示出形状各异、 大小不同的纤维团，很好的模拟了宣纸纤维结构的不规则性。 f i b r e l i s t 中，每个纤维束f i b r e 包含一个串接的纤维团集合b l o c k c o l l c c t i o n 。 除了纤维团和纤维束链表外，纸结构还包含其他参数如：纸的厚度t 、尺寸、分 辨率、致密度d 以及吸水力参数a 。 下面介绍纸模型的构造规则。构造过程必须遵从真实宣纸纤维结构分布的主 要规则，我们将这些规则归纳如下： 纤维分布服从“全局一致，局部随机”。所谓“全局一致”是指从整张宣 纸平面来看，平面上每个象素区域所含的纤维量是“一致”的。本文用正态分布 n 以，口2 ) 随机量来实现“全局一致 ，且其均值服从给定的规则，这里规则可 以是全部相等( 对于没有纹理的宣纸) ，也可以与某种“结构纹理”存在一一对 应关系。而“局部随机”则是指在每个局部区域( 一般是象素平面区域) 内的纤 维分布是完全随机的。这是模拟宣纸纤维结构的不规则分布的关键。 纤维束的数目和长度服从正态分布。因为现实世界的随机事件大多服从正 态分靠。构造算法中，用到最多的就是正态分却随机数的生成算法。根据概率论 知识，服从正态分布n 以，仃2 ) 的随机数x 的概率密度为： 1 一! 兰正 厂( 工) = _ 7 兰e 2 0 2 ( 4 3 ) 饥u 其中为均值，盯为方差。 依据构造规则，我们制定出构造模拟宣纸的步骤如下： 生成纤维 ( f i b r eb l o c k s ) ：把纸平面的每个象素进一步细分为n * 1 1 个细胞 ( c e l l ) ，根据j 下态分布计算每个象素区域的实际纤维含量；依此在各象素区域内 随机分配“纤维点”。最后把相邻的分配了纤维点的细胞组合成纤维团。 生成纤维束：对每个纤维团，根据某一均值a v g _ t h r e a d s 和方差生成个 3 2 艇- - y 黪避霉 i 氅。蓄弧夏。： 麟愁； | ! x 0 照酶熟i 懿；j 鲤；。琵矗菱 3 3 肫一( m 训宰南+ 所 ( 4 4 ) 其中足为灰度图中对应象素的灰度值，m 和m 分别是单位象素纤维含量的上下 界。 同时，为了让水墨画作品能体现出不同的纹理的宣纸上作画效果，就需要将 水墨画的笔迹和背景纹理进行“叠加”。个问题归根结底就变成了在已知两个r g b 值的情况下，求“叠加 后的r g b 值的问题。 考虑到墨是一种“色素物体，宣纸纹理也可以看成“色素物体。本文采用了特 别适合于“色素物体”的颜色混合模型一k u b e l k a m u n k ( k m ) 模型1 3 8 】【3 9 j 。k m 模型广泛应用于印刷、打印等涉及颜料的应用中。c u r t i s 等人成功地将它运用到 水彩画的颜色混合问题中，达到了很好的效果【删，由此可见l 纵模型也十分适用 于水墨画中的颜色叠加问题。 在使用k m 多层叠加公式1 4 1 l 进行叠加之前，先要计算笔迹层和背景层各自的 光学参数。背景层是不透明的，其光学参数为： t 卜惫妒。) 其中r 为反射量，实际就是r 、g 、b 三个通道中某一通道的r g b 值，t 为投射量。 笔迹层( 墨粒子) 的光学参数0 ( 碍，弓) 通过如下公式计算： r =- b + _ b - 2 一- 4 a c ，- 1 2 a z = 卢r ( 4 5 ) 一i c ，卢，1 口- ( p 2 - 1 ) + r ，b = ( 1 + 月：木r ) ，c ；一吃 其中，r m 等于在白纸上的试墨颜色，r b = l 表示白纸颜色，1 b 是墨浓度( 0 1 b o o ，且1 1 3 = r r , ，它是抽象的墨浓度，1 b 越大表示墨越浓) 。 有了光学参数后，笔迹层在上，纹理层在下，使用k m 多层叠加公式进行叠 加，求得各个通道的r ，进而得到叠加后的r 、g 、b 值： r ：r + 垒墨( 4 - 6 ) 1 1 一r b 通过上述过程，我们就仿真出了所要的宣纸模型。调节特征参数可以调节模 拟宣纸的各种属性，仿真效果也会起相应的变化，以反映不同宣纸上的不同水墨 画效果。 4 4 水墨扩散算法 本节介绍几种常用的水墨扩散算法，在此基础上提出自己的水墨扩散算法。 4 4 1 细胞交换法 水墨画中水墨的扩散主要是在纸的内部进行的，影响最后效果的是纸的内部 结构，而不是表面高度细节，这一点与水彩画有很大的不同。水的流动不单单靠 重力作用，更主要的是纸纤维的吸水作用和墨粒子的粘附作用，正是纸纤维的内 部结构差异，才会发生不同的流动效果及渗化效果，进而产生扩散纹理。所以提 出构建一个纸纤维内部结构模型，模拟液体在其内的流动扩散行为n 2 l 。 该模型包含三部分： 水墨：一定量的水墨粒子。 纸模型：具有一定的吸水力和容量的纸纤维细胞组成的三维矩阵。 水流推进引擎：控制水墨粒子与宣纸模型及环境之间的相互作用的行为规则。 这里的“水墨粒子”并不是指纯粹的粒子系统，而只是借鉴粒子系统的基本 概念，用来形容离散的水墨粒子，水墨粒子可以看成是包含一定属性信息的水墨 单位。 像水墨粒子一样，每一个纸纤维细胞也包含一定的属性信息，如自身的容量、 当时的吸水力、所含水墨粒子的数量等。纸纤维细胞的样子可以想象为一个个具 有不同容量的吸水的棉球，它们可以和互相连通的相邻棉球交换水墨粒子。细胞 棉球之间的连通管道是虚拟的，只是粒子流动的通道，并不存储粒子，即只起导 通作用。细胞的状态由它的属性及它所包含的水墨粒子的属性共同决定