（计算机软件与理论专业论文）基于分形的信息防伪技术的研究.pdfVIP

独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得 一 ( 注：如 没有其他需要特别声明的，本栏可空) 或其他教育机构的学位或证书使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明 并表示谢意。 学位论文作者签名：导师签字： 学位论文版权使用授权书 0i ，1 劂勿 本学位论文作者完全了解堂撞有关保留、使用学位论文的规定，有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。 本人授权堂撞可以将学位论文的全部或部分内容编入有关数据库进行检索，可 以采用影印、缩印或扫描等复制手段保存、汇编学位论文。( 保密的学位论文在 解密后适用本授权书) 学位论文作者签名： i 二军 j 十 i导师签字浏磊 签字日期：2 0 0 7 年牛月1 日签字日期：2 0 0 年牛月) 7 日 z上i 、， 土 山东师范火学硕：l 学位论文 摘要 分形理论是上世纪7 0 年代兴起的一门学科，是继微积分之后数学史上的又 一次革命。随着计算机图形学的发展，分形理论的应用范围变得越来越广泛，逐 渐成为非线性科学中一个重要的研究领域，成为探索世界复杂性的重要工具。作 为一种新的世界观和方法论，分形以其新颖的指导思想和独特的分析方法被各个 学科竞相引入，成为推动学科发展的新的驱动力。分形理论深化了人类对大自然 的认识，诱发了一些新的科学生长点，打破了各个学科问的壁垒，把思考者从相 距甚远的各个学术领域吸引到一块共同的领地，它的应用几乎涉及自然科学的各 个领域，甚至社会科学，前景十分诱人，引起了人们普遍的关注。 在当今的社会中假冒伪劣产品泛滥成灾，防伪技术虽然层出不穷，但是造假 集团也在不遗余力的破解不断更新的防伪技术，使得一些防伪技术形同虚设 严 重损害了广大企业和消费者的切身利益。近年来一类新型的基于计算机网络的防 伪技术正在兴起，通过计算机网络将商品包装上复杂的防伪设计及验证过程简化 为防伪信息的查询，网络化的平台使生产厂家与消费者之间的距离大为缩短。消 费者买到商品后直接就能从网上对商品进行真假鉴别，从而建立了全方位的，即 时的社会化打假网络，这种防伪技术被称为信息防伪技术。 本文致力于研究分形信息防伪系统的建立与应用的问题，将分形理论和新型 的信息防伪技术结合起来，结合它们各自的优势，推动防伪技术的发展。本文的 主要工作为； 1 对分形理论与信息防伪技术结合的可行性进行分析研究 本文通过分析比较现在市场上使用的信息防伪技术，再结合分形理论本身的 特点，创新性的将分形理论和信息防伪技术结合起来，通过借助分形理论来进行 防伪，为信息防伪技术的研究提供了一个新的思路。 2 建立了一种基于“分形信息防伪技术”的防伪流程 参考一般信息防伪的流程，本文提出了一种适合于分形信息防伪的防伪流 程：先开发分形图案设计软件，再将设计出来的分形图案和生成该图案的数学参 数保存在数据库中，形成一种一一对应的关系，然后把分形图案做成防伪标志并 山东师范人学硕七学位论文 同时将数学参数经过转换机制转换成防伪码一块印刷在商品的包装上，当用户要 进行真假鉴别的时候就可以利用防伪码和分形防伪标志的对应关系，到专门的防 伪网站上面输入防伪码来鉴别商品的真伪。 3 设计了一个分形信息防伪系统，并开发了一个分形图案设计软件，最后对数 据库和防伪网站的框架进行了设计 本文设计的分形信息防伪系统由“分形图案设计软件”，“存放分形图片和防 伪码的数据库”和“鉴别商品真伪的防伪网站”三部分组成。通过研究所需要的 分形理论，利用逃逸时间算法设计出一个集成m a n d e l b r o t 集，j u l i a 集和l 系统 的分形图案设计软件，它可以根据分形中的数学公式设计出很多精美的各不相同 的图案。此软件系统即是提供一个平台，让设计人员通过自己的摸索、试验，得 到满意的“设计图案”，并可把这些“图案”取到如p h o t o s h o p 软件中做进一步 加工，或与其他图案合并使用。通过对设计出来的实例进行分析，设计结果令人 满意。最后对数据库和防伪网站的框架进行了设计。 关键词：分形，信息防伪，i f s ，逃逸时间算法，m - j 集 中图分类号：t p 3 9 1 4 1 4 山东师范大学硕士学位论文 f r a c t a l b a s e dr e s e a r c ho fi n f o r m a t i o nc o u n t e r f a k i n g t e c h n o l o g y a b s t r a c t f r a c t a lt h e o r yi sad i s c i p l i n et h a to r i g i n a t e di nt h e1 9 7 0 s ，l e a d i n g an e wr e v o l u t i o ni nm a t h e m a t i c sa f t e rc a l c u l u s 。a s c o m p u t e rg r a p h i c s d e v e l o p s ，i t sa p p l i c a t i o nh a sb e e ng e t t i n gw i d e r ，b e c o m i n ga ni m p o r t a n t r e s e a r c hf i e l di nn o n 一1i n e a rs c i e n c ea n da ni m p o r t a n tt o o li nt h e e x p l o r a t i o no ft h ec o m p l e x i t yo ft h ew o r l d 。a san e ww o r l dv i e wa n d m e t h o d o l o g y ，f r a c t a li si n t r o d u c e dt oag r e a tv a r i e t yo fd i s c i p l i n e sd u e t oi t sb r a n dn e wi d e aa n du n i q u em e t h o d o l o g y ，b e c o m i n gan e wd r i v i n gf o r t h ed e v e l o p m e n to ft h e s ed i s c i p l i n e s i tb r o a d e n st h eh u m a ni n s i g h t si n t o t h en a t u r e ，r e s u l t i n gi ne m e r g e n c eo fn e ws c i e n c ea n db r e a k i n gb a r r i e r s b e t w e e nd i f f e r e n td i s c i p l i n e s ，s ot h a tt h i n k e r si nd i s t a n ta c a d e m i c f i e l d sa r ed r a w nt o g e t h e rt oas h a r e df i e l d i tc a nb ea p p i i e dt oa l m o s t e v e r yf i e l do fn a t u r a ls c i e n c ea n de v e nt os o c i a ls c i e n c e s i th a sa r o u s e d g r e a tc o n c e r nw i t hi t sa t t r a c t i v ep r o s p e c t s f a k e d p r o d u c t s a r e p l a g u i n g t h e p r e s e n ts o c i e t y a l t h o u g h c o u n t e r f a k i n gt e c h n o l o g ya p p e a r s ，p e o p l ew h oa r em a k i n gf a k e dp r o d u c t s a r es p a r i n gn oe f f o r tt os t r u g g l ea g a i n s tc o u n t e r f a k i n gt e c h n o l o g y ， m a k i n gi tap u p p e t ，v i o l a t i n gt h ei n t e r e s t so fe n t e r p r i s e sa n dc o n s u m e r s i nr e c e n ty e a r ，c o u n t e r f a k i n gt e c h n o l o g yo nt h eb a s i so fc o m p u t e rn e t w o r k i s e m e r g i n g ，t h ec o m p l i c a t e dc o u n t e r f a k i n gd e s i g na n d t h ef a k i n g v a l i d a t i n gp r o c e s ss i m p l i f i e dt oi n q u i r yi n t oc o u n t e r f a k i n gi n f o r m a t i o n n e t w o r kp l a t f o r mh a ss h o r t e n e dt h ed i s t a n c eb e t w e e n p r o d u c e r sa n d c o n s u m e r s w h e np r o d u c t sa r e s o l d 。p r o d u c e r s c a n d i s t i n g u i s hb y t h e m s e l v e si nt h en e t w o r k t h i se s t a b l i s h e sa f t a l 卜r o u n d ，t i m e l y c o u n t e r f a k i n gn e t w o r ki nt h ew h o l es o c i e t y 山东师范大学硕士学位论文 t h i s t h e s i sa i m st oe x p l o r et h ee s t a b li s h m e n ta n da p p l i c a t i o no f f r a c t a li n f o r m a t i o nc o u n t e r f a k i n gs y s t e m ，c o m b i n gf r a c t a lt h e o r ya n d i n f o r m a t i o nc o u n t e r f a k i n gt e c h n o l d g y ，d r a w i n go nt h e i rr e s p e c t i v e a d v a n t a g e ss oa st op r o m o t et h ed e v e l o p m e n to fc o u n t e r f a k i n gt e c h n o l o g y t h em a i nc o n t e n t sa r e1 i s t e da sf o l l o w s ： 1 a n a l y z et h ef e a s i b i li t yo ft h ec o m b i n a t i o no ff r a c t a lt h e o r ya n d i n f o r m a t i o nc o u n t e r f a k i n gt e c h n o l o g y t h i ss t u d yc o m b i n ef r a c t a lt h e o r ya n di n f o r m a t i o nc o u n t e r f a k i n g t e c h n o l o g y ，d r a w i n go nt h ei n f o r m a t i o nc o u n t e r f a k i n gt e c h n o l o g ya n dt h e c h a r a c t e r i s t i c so ff r a c t a lt h e o r y 。c o u n t e r f a k i n gb yf r a c t a lt h e o r y p r o v i d i n gan e wa p p r o a c ht oi n f o r m a t i o nc o u n t e r f a k i n gt e c h n o l o g y 2 ac o u n t e r f a k i n gp r o c e s so nt h eb a s i so ff r a c t a li n f o r m a t i o n c o u n t e r f a k i n gi se s t a b l i s h e d d r a w i n go nt h eg e n e r a lp r o c e s so fi n f o r m a t i o nc o u n t e r f a k i n g ，t h i s p a p e rd e s i g n sac o u n t e r f a k i n gp r o c e s sb a s e do nf r a c t a li n f o r m a t i o n c o u n t e r f a k i n g af r a c t a lp i c t u r ed e s i g n i n gs o f t w a r ei sd e v e l o p e da n dt h e p i c t u r ea n dt h ev a r i a b l e sf o r m u l a t i n gi ta r es t o r e di nad a t a b a s e ，f o r m i n g ao n e o n o n ec o r r e s p o n d e n c e t h ef r a c t a lp i c t u r ei st h e nm a d e i n t oa c o u n t e r f a k i n gm a r ka n dv a r i a b l e st r a n s f o r m e di n t oa n t i f a k i n gc o d e ， w h i c hi sp l a c e do nt h ep a c k a g e so fp r o d u c t s w h e nc u s t o m e r sn e e dt oi n q u i r e w h e t h e rt h e i rp r o d u c t sa r ef a k e d ，t h e yc a nc h e c kt h ei n f o r m a t i o ni nt h e d a t a b a s e ，w h i c hi sp r o v i d e db ya u t h o r i z e dw e b s i t e s 3 d e s i g nas y s t e mo ff r a c t a li n f o r m a t i o nc o u n t e r f a k i n g s o f t w a r ef o r d e s i g n i n go ff r a c t a lp i c t u r ei sd e v e l o p e da n dt h ed e s i g no ff r a m e w o r kf o r d a t a b a s ea n dc o u n t e r f a k i n gw e b s i t ei sp u tf o r w a r d t h es y s t e mo ff r a c t a li n f o r m a t i o nc o u n t e r f a k i n gi sm a d eu po fs o f t w a r e o fd e s i g n i n gf r a c t a lp i c t u r e ，d a t a b a s ea n dc o u n t e r f a k i n gw e b s i t e r e s e a r c hn e e d st of r a c t a lt h e o r y ，t h ee s c a p e t i m ea l g o r it h mt od e s i g na n i n t e g r a t e dg a n d e l b r o ts e t ，j u l i as e t a n dl - s h a p e d d e s i g nf o r t h e 6 山东师范大学硕士学位论文 s u b s y s t e ms o f t w a r e i tc a nb eam a t h e m a t i c a lf o r m u l ab a s e do nf r a c t a l d e s i g nal o to fn i c en o t t h es a m ep a t t e r n t h iss o f t w a r es y s t e mi st o p r o v i d eap l a t f o r mt o a l l o wt h ed e s i g n e r st oe x p l o r e ，e x p e r i m e n t ， s a t i s f a c t o r yp i c t u r e sa l s ot h e s ep i c t u r e st og a i nf u r t h e rp r o c e s s i n g s o f t w a r es u c ha sp h o t o s h o po rc o m b i n e dw i t ho t h e rd e s i g n s p i c t u r e sa r e t h eb a s i so ff r a c t a la n a l y s i so nt h ec a s e sd e s i g n e dh a ss h o w ns a t i s f y i n g r e s u l t s a tl a s tn e wa p p r o a c ht ot h ed e s i g no f d a t a b a s ea n dc o u n t e r f a k i n g w e b s i t ei sp u tf o r w a r d k e y w o r d s ：f r a c t a l ，c o u n t e r f a k i n go fi n f o r m a t i o n ，i f s ，e s c a p e t i m e a l g o r i t h m ，m js e t c 1 a s s i f i c a t i o n ：t p 3 9 1 4 1 7 山东师范丈学硕士学位论文 第一章绪论 本章介绍了课题的研究背景和分形信息防伪的研究意义，最后介绍了本文的 主要工作和组织结构。 1 1 本课题的研究背景 仿造、伪造、盗版正在全世界范围内蔓延。在中国，几乎所有世界名牌都遭 受假冒品牌的困扰。仅在0 4 年，先有意大利服装品牌华伦天奴宣布从整个中国 市场撤出，后有梦特娇推出新的多重防伪标记，其中包括用钞票纸来印刷商标牌， 再有派克笔状告超市，佳能巨资网络式打假。这正是中国市场上无法遏制的假冒 商品冲击的结果。据不完全统计，中国本土企业申请的加各种前后缀的“华伦天 奴”品牌多达1 6 0 多个，目前国内市场有大大小小1 0 0 多家“假鳄鱼”服装厂 家。再如国酒茅台，每年要拿出1 5 0 0 万元用于引进，购买防伪技术。根据统计， 每年茅台酒的销量是真实产量的十倍左右，就是一个例证。 资料显示，查获的假冒伪劣产( 商) 品主要有：食品、各种饮料酒、饮料、食 盐、卷烟、药品、保健品、化妆品、洗涤用品、服装、鞋类、胶卷、医疗器械、 钢材、水泥、化工原料、化肥、农药、种子、汽车零部件、电视机等等。从社会 公共安全领域看，还有大量伪造的钞票、邮票、各种有价证券、居民身份证、户 口簿、毕业证书、公章等。 据不完全统计，目前全国有近千家企事业单位从事防伪技术及防伪材料和相 关产品的研发、生产和销售。防伪印刷产品( 不含人民币和证件等特殊防伪产品) 年销售额已由8 0 年代初的几千万元，发展到目前的近百亿元。我国防伪技术产 品市场需求之大、发展速度之快是惊人的。针对我国防伪行业的现状，以及我国 加入w t o 的严峻挑战，中国防伪行业协会召集有关专家及企业技术人员进行多次 研讨，制定了我国防伪产业技术政策，即：以技术创新为动力，结合防伪技术应 具有的综合性、层次性、独占性和系统化、智能化、标准化、数字化等特点，建 立防伪系统安全保证体系和质量保证体系以及认证体系，突出高新技术领域的自 主创新，逐步形成一大批拥有自主知识产权，具有竞争优势的高新技术产品和新 的系统防伪手段，并注重开发、研制高新技术防伪产品与普及大众防伪识别产品 9 山东师范大学硕士学位论文 相结合的产品，为打击假冒，保护名优提供有效手段，使我国防伪技术及其产业 走上健康发展的道路。 1 2 研究意义 我国防伪技术的发展和防伪行业的形成，是发展社会主义市场经济的需要， 是扩大开放，发展对外贸易，保证国家经济秩序有序发展的需要，是当前打假治 劣，净化市场，保护名优，维护国家、企业和消费者利益的需要。在中国的防伪 是任重道远的，长久以来，人们没能找到一种生命周期长，防伪效果好的防伪手 段，这是目前假冒商品泛滥成灾的重要原因。防伪界有一个定论：“世界上没有 不可仿冒的防伪技术。”所以为了打击假冒伪劣产品的泛滥，净化我们的商品市 场，防伪技术的研究是很有必要的。 防伪技术的研究涉及到很多学科，如光学，材料学，生物学，化学等等。一 项成功的防伪技术就像一个大熔炉，包含着多个学科的研究成果，在防伪技术领 域里面，学科之间的界限逐渐变的模糊起来。分形理论也是一门新兴的跨专业的 学科，伴随着计算机技术的发展，分形已经与很多学科联系起来，推动了其它学 科的发展。本文创新性的把分形理论引入到防伪技术中来，为防伪技术的研究提 供了一个新的思路。 1 3 本文的主要工作及组织结构 本文致力于研究分形信息防伪系统的建立与应用的问题，将分形理论和新型 的信息防伪技术结合起来，结合它们各自的优势，推动防伪技术的发展。本文的 主要工作为： 1 对分形理论与信息防伪技术结合的可行性进行分析研究 本文通过分析比较现在市场上使用的信息防伪技术，再结合分形理论本身的 特点，创新性的将分形理论和信息防伪技术结合起来，通过借助分形理论来进行 防伪，为信息防伪技术的研究提供了一个新的思路。 2 建立了一种基于分形信息防伪技术的防伪流程 参考一般信息防伪的流程，本文提出了一种适合于分形信息防伪的防伪流 程：先开发分形图案设计软件，再将设计出来的分形图案和生成该图案的数学参 0 山东师范大学硕士学位论文 数保存在数据库中，形成一种一一对应的关系，然后把分形图案做成防伪标志并 同时将数学参数经过转换机制转换成防伪码一块印刷在商品的包装上，当用户要 进行真假鉴别的时候就可以利用防伪码和分形防伪标志的对应关系，到专门的防 伪网站上面输入防伪码来鉴别商品的真伪。 3 设计了一个分形信息防伪系统，并开发了一个分形图案设计软件，最后对数 据库和防伪网站的框架进行了设计 本文设计的分形信息防伪系统由“分形图案设计软件”，“存放分形图片和防 伪码的数据库”和“鉴别商品真伪的防伪网站”三部分组成。通过研究所需要的 分形理论，利用逃逸时间算法设计出一个集成m a n d e l b r o t 集，j u l i a 集和l 系统 的分形图案设计软件，它可以根据分形中的数学公式设计出很多精美的各不相同 的图案。此软件系统即是提供一个平台，让设计人员通过自己的摸索、试验，得 到满意的“设计图案”，并可把这些“图案”取到如p h o t o s h o p 软件中做进一步 加工，或与其他图案合并使用。通过对设计出来的实例进行分析，设计结果令人 满意。最后对数据库和防伪网站的框架进行了设计。 本文的组织如下： 第一章绪论。 第二章对分形理论进行了分析。首先介绍了分形理论的诞生及内涵，然后介 绍了一下分形的定义和维数，分析了分形理论生成图形的常用算法，它们分别是 递归算法，文法构图算法，迭代函数系统( i f s ) 方法，逃逸时间算法。最后对分 形理论的发展过程和应用进行了一下阐述。 第三章首先研究一下当今市场上防伪技术的现状，并简单介绍了一下纸张防 伪技术和油墨防伪技术。然后重点分析了一下信息防伪技术的原理及特点。 第四章对分形理论与信息防伪结合性进行了分析，创新性地提出了“分形信 息防伪”的概念，并总结了一套针对分形信息防伪的流程。 第五章根据分形防伪的流程，开发了一套分形图案的设计软件，通过它来设 计分形防伪标志，并对设计出来的实例进行分析，设计结果令人满意。最后对数 据库和防伪网站的框架进行了设计。 第六章总结了本文的主要工作和进一步的研究方向。 山东师范大学硕士学位论文 第二章分形理论分析 本章主要给出分形理论的诞生及内涵，分形的定义和维数的定义，研究了分 形的基本算法，回顾了分形理论的发展过程，并介绍了一下分形理论在各个领域 韵应用情况。 2 1分形理论的诞生及内涵 在以往的生产实际和科学研究中，人们用以描述客观世界的几何学是欧几里 德几何学，以及解析几何，射影几何，微分几何等，它们能有效地对人为设计的 三维物体进行描述，是人们千百年来生产实践的有力工具。但是随着人类的发展， 人们逐渐感觉用传统几何并不能包罗万象地描述大自然中和人类社会中所有的 对象，分形现象已成为自然界和人类社会生活中一种普遍现象。如果我们仔细地 观察周围的世界，可随时随地的看到许许多多有趣的形象，有一些是大自然赋予 的，例如生长得枝枝杈权的树木、高低不平的山脉、弯弯曲曲的河流与海岸线、 棉絮团似的云烟和冬天里美丽的雪花以及地震波能量的传播、太阳黑子的爆 炸；有一些是在人类日常生活中不断出现的，例如股市上天天发布的股票价 格曲线、水文测量中的水位变化曲线等等。这些不规则的对象是不能用传统的欧 几里德几何学来描述的，这就迫切的需要一种新的理论来解释这些现象。 直到1 9 6 7 年曼德布罗在科学杂志上发表了一篇“英国的海岸线有多长? 统计自相似性与分形维数”的论文“。在这篇论文中他对海岸线的本质作了独特 的分析震惊了学术界，也成为他自己思想的转折点，分形概念就从这里萌芽生长， “分形( f r a c t a l ) ”这个名词就首次在科学界出现。1 随后他在1 9 7 7 年发表的分 形：形，机遇与维数( f r a c t a l s ：f o r m ，c h a n c ea n dd i m e n s i o n ) ) ) 及1 9 8 2 年发 表的自然界的分形几何学( 1 1 1 ef r a c t a lg e o m e t r yo f n a t u r e ) ) ) 专著中，他进 一步阐述了他的观点，从而开创了二门新的学科“分形学”。1 “分形”一词原是从拉丁文“f r a c t u s ”转化而来的，它的原意是“不规则 的、分数的、支离破碎的”物体；而英文“f r a c t a l ”一词的含意是指“小块的、 断片的、分数的”物体。顾名思义，我们可以想到“分形学”是一门描述不规 1 2 山东师范大学硕士学位论文 则事物规律性的科学。至此，国际上对分形的研究迅速地进入了一个新纪元，分 形学的产生和完善，启发了人们对自然规律全新的认识。 分形理论正是为了研究自然界中常见的，变幻莫测的，不稳定的，非常规的 但又具有自相似性的图形而产生出来的。分形理论的产生，有着其哲学上的内涵： “第一，分形几何学通对整体与局部关系得认识的深化，进一步丰富和深化了唯 物辩证法关于物质世界普遍联系的原理。分形理论从整体与局部的自相似性关系 上来揭示世界的普遍联系，揭示了整体与部分之间的内在联系，找到了从部分过 渡至u 整体的媒介与桥梁，揭示了部分与整体的“同构性”，从一个新的层面丰富 和深化了整体与部分关系这一哲学范畴，从而也丰富和深化了唯物辩证法关于普 遍联系的原理。第二，分形理论的产生，迸一步证明了认识是一个有浅入深，由 片面到全面，由低级到高级，由相对真理到绝对真理的过程这一辩证唯物主义认 识原理。我们都知道欧几里德几何学中维数的取值是在整数范畴的，但是分形里 面有一种曲线叫k o c h 曲线。它的维数是；雩。根据曼德布罗特的计算，英国海 l o g j 岸线的维数为1 2 6 ，这就把维数的概念从整数维扩展到分数维，更代表了一般性。 “分数维”的维数是定量地表示自相似的随机形状和现象的最基本的量。在自然 界中许许多多物体都可以用分形来描述，如海岸线、云彩的边界等等，分数维对 整数维的发展，充分说明了科学认识由片面到全面的辩证运动过程，它表明任何 具体的科学理论都不可能穷尽到世界的真理。真理是一个有相对到绝对，再由绝 对到相对的无限发展过程。 分形理论进一步丰富和深化了科学哲学的一系列原理，体现出了其深刻的哲 学内涵，它的发展和完善，必将为哲学注入新鲜活力，从而推动哲学走向新的更 高的发展阶段。“1 2 2 分形的定义 曼德布罗特曾指出，h a u s d o r f f 维数严格大于拓扑维数的集合称为分形。 但这仅是试验性的定义，很不严格，也无可操作性。而后曼德布罗特又对定义进 行了修改，提出。其组成部分以某种方式与整体相似的形体叫分形”目前分形 还没有一个确切的定义，但现在流行的定义是称集合f 是分形，是指它具有下面 山东师范大学硕士学位论文 典型的性质：”“1 ( 1 ) f 具有精细的结构，即在任意小的尺度下，它总有复杂精细的细节； ( 2 ) f 是不规整的，它的整体与局部都不能用传统的几何语言描述； ( 3 ) f 通常有自相似形式，这种自相似可以是近似的或统计意义下的； ( 4 ) 一般的，f 的某种定以下的分形维数大于它的拓扑维数； ( 5 ) 在大多数下情况下，f 以非常简单的方法确定，可由迭代过程产生。 2 3 分形的维数 分形理论是非线性科学的三个组成部分之一，其它的两个部分分别是：混沌 和孤立子。世界的本质是非线性的，线性的只不过是非线性的一个特例。欧几里 德几何研究的就是光滑的图形，它只不过是人工构建的抽象几何学，而分形研究 的是不光滑的图形，更代表着一般性。分形的基本特征是自相似，即部分与整体 有着惊人的相似，自然界有许多事物都呈现分形的几何特征，所以分形被称为大 自然的几何学。”1 分维是分形的数量表示，由于欧几里德几何的尺度：长宽高无 法描述不规则形体，曼德布罗特用分数维来表示分形。在欧几里德几何中，0 维 表示点，一维表示线，二维表示面，三维表示空间。分数维是1 9 1 9 年由德国数 学家豪斯道夫在研究奇异集合时提出来的，但豪斯道夫分数维数在很多情况下难 以计算，1 9 8 6 年，曼德布罗特将分形定义为局部以某种方式与整体相似的集， 并重新讨论分维，就得出比较容易计算的分数维数。 两种最常用的分形维数是豪斯道夫( h a u s d o r f f ) 维数和盒维数。“1 ( 1 ) 豪斯道夫( h a u s d o r f f ) 维 设a 为欧氏空间肜中的子集，s 为一非负数，对任何万 0 ，定义： ， h ；( a ) = i n f iu ，l 5 f ；l 其中u 为r ”中的集合， a c u ，j i 表示u 的直径， 即 l u l - s u p i x - - y l ；x ，y u ，且0 q u 降占， q 称为a 的一个占一覆盖i 。令 4 山东师范大学硕士学位论文 h ( 4 ) = 。l i m 。h i ( a ) ，可以证明，对于集合4 存在唯一的非负实数，记为d ( 爿) ， 它满足下列性质； 若0 j 见( 爿) ，则h 4 ( 爿) = 0 0 ： 若p ( 爿) s 0 ，令n ( a ，s ) 表示覆盖a 的最小闭球的数目，闭球的半径为占。若存在 d = l i i i l 坚掣，则称d 是的盒数维。 一o m 形) 盒数维不仅便于实际应用，而且具有重要的理论意义，可以很方便的用盒 数维数表明分形的不规则性。可以证明，一些集合的盒数维和h a u s d o r f f 维数相 等。 2 4 分形的基本算法 目前比较常用的生成分形图案的算法分别是递归算法、文法构图算法、迭代 函数系统算法、逃逸时间算法。 2 4 1 递归算法 在计算机程序设计中，递归是指一个过程直接或间接地调用其自身的一种算 法，这种算法是种最简单的生成分形图的算法。 c a n t o r 三分集的递归算法是以( a x 。c r y ) ( b x ，b y ) 为初始线段，( a x 。 a y ) 一( “，c y ) 和( a x ，方) 一( b x ，砂) 为初始线段三等分后，去掉中间线段 1 5 山东师范大学硕士学位论文 所剩下的两个线段。按照递归的想法，以后每一次操作都将遵循这一规则。 甜a t b x ，b y 似缈 “，秒 出，咖h ，砂 削2 - 1c a n t o r 三分集构造示意图 如图2 1 所示，给定初始直线两个端点的坐标( a x ，a t ) 和( b x ，b y ) ，按 c a n t o r 三分集生成规则计算出各关键点的坐标如下：“= 蕊+ ( b x f 7 x ) 3 ， 甜= c o , 一d ，d x = 如一( b x 一甜) 3 ，砂= b y d ，a t = 缈一d ，b y = b y d ，其中，d 为一个常量，代表上下两层线段之间的距离。然后利用递归算法，将计算出来的 新点分别对应于( a x ，a t ) 和( b x ，b y ) ，即饿一盯，a t a y ，k 一“，缈一 c y ，觑一出，缈一咖，如一如，砂一砂再按照c a n t o r 集的生成规则中的计 算关系计算出下一级的新点。给定一个小量c ，当( 缸，b y ) c 时，绘制直线段( 肼， 缈) ( h ，砂) ，然后程序结束。程序的终止有递归深度c 来决定，可加入一些 控制条件来加速其分形图的生成。 1 6 | 笙i2 _ 2 样序生成的c a n t o r 集 图2 - 3 中a 图给出了由迭代算法生成的k o c h 雪花衄线，其中它的生成元是 山东师范大学硕士学位论文 图2 - 3 中b 图。 a 。b 图2 - 3k o c h 雪花曲线与生成元 2 4 2 文法构图算法 文法构图算法又称l s 文法，是仿照语言学中的语法生成方法来构造图形的 一种算法。l s 文法是一类独特的迭代过程，其核心概念是重写。作为一种形式 语言，l s 文法用字母表和符号串来表达生成的对象的初始形式，称之为公理， 然后根据一组产生式重写规则，将初始形式的每个字符依次替换为新的字符形 式，以次过程反复替换重写，最后生成终极图形。 在二维平面上，l s 文法的图形生成过程，类似于海龟在沙滩上面行走。他的 基本思想是将龟形形态定义成一个三元素集合( 石，y ，口) ，其中笛卡儿坐标( x ，y ) 表 示龟形的位置，方向角口表示龟形的方向，给出步长d 和角增量占，龟形对应于 下列命令： f ( d ) ：向前移一步，步长为d ，龟形形态变为( r ，y ，o t ) 。其中x = x + d e o s a ， j r = y + d s i n t t l ，在点( z ，y ) 和 ，y ) 之间划一条线段。 + ( 占) ：向左转万，龟形的下一状态为( x ，y ，口+ j ) ，角的正向为逆时针方 向。 一( 艿) ：向右转艿，龟形的下一状态为( x ，y ，a 一艿) 。 1 7 山东师范人学硕t 学位论文 给定一个字符串v ，龟形的初始状态( x o ，y o ，口) 以及固定参数和艿，v 的龟形 说明就是由与v 相应得龟形画出的图形。 上面利用迭代法生成的k o c h 雪花也可以用文法构图算法生成，用龟形画分 形图的过程是： 占= 6 0 0 v ：f ( 1 ) 一( 占) 一( 占) f ( 1 ) 一( 占) 一( 艿) f ( 1 )( 初始图) p ：f ( d ) 一f ( d 3 ) + ( 占) f ( d 3 ) 一( 6 ) 一( 艿) f ( d 3 ) + ( 万) f ( d 3 ) ( 生成 元) k o c h 曲线的初始图是一个边长为1 的等边三角形( 如图2 - 4 ) ，生成元是一 条由4 个边长为1 3 的线段组成的有向折线( 如图2 - 5 ) ，将初始图的每一条线段 都有生成元替代，得到图2 6 ，再将生成元缩小到原来的1 3 ，依次替换图2 6 的每一条线段得到图2 - 7 ，依次类推，便得到k o c h 分形曲线。 1 8 圈2 4k o c h 曲线的初始图图2 5 生成元 图2 - 6 第一次替换结果 图2 7 第二次替换结果 山东师范大学硕士学位论文 上面的k o c h 雪花的生成过程是利用单一规则的l s 文法生成的，我们也可 以利用多规则的l s 文法生成更复杂一点的图形，可以通过将单规则中的字母表 增加为两个甚至更多字母。我们也可以在l s 方法中引入随机量，使表现不同形 态的规则按照不同的概率分布随机出现，从而产生更加自然更加生动的图形来， 这便是随机l s 文法，下图就是利用随机l s 文法生成的分形图形。 图2 - 8 随机分形树 2 4 3 迭代函数系统( i f s ) 迭代函数系统( i f s ) 方法是美国佐治亚理工学院的巴恩斯利教授首创的。1 。 i f s 方法的魅力在于它是分形迭代生成的“反问题”，根据拼接定理，对于一个 给定的图形( 比如一幅照片) ，求得几个生成规则，就可以大幅度压缩信息。i f s 的 基本思想并不复杂，它认定几何对象的全貌与局部，在仿射变换的意义下具有自 相似结构，在几何对象的整体被定义之后，将整体形态变换到局部，并且这一过 程可以迭代地进行下去，直到得到满意的造型。具体地说，它将待生成的图像看 成是由许多与整体相似的( 自相似) 或经过一定的变换与整体相似的( 自仿射) 小 块拼贴而成。其中相似变换是指在各个方向上变换的比率必须相同的一种比例变 换，仿射变换是指在不同的方向上变化的比率可以不同的一种比例变换，可以将 相似变换看成是仿射变换。 仿射变换是一种线性变换，在二维平面上进行讨论，二维仿射变换的形式为： 国：p 一+ ? + ： i y = c x + 砂+ ， 其中国代表仿射变换，x ，y 是变换前图形的坐标值，r 和y 是变换后图形的 1 9 山东师范大学硕士学位论文 坐标值；a ，6 ，f ，d ，e ，f 是仿射变换系数。 仿射变换有以下的几何特征： 仿射变换的逆变换仍然是仿射变换。 仿射变换是线性变换，直线段仿射变换后仍为直线段，并且保持线段上点的定 比关系不变。 两平行直线经仿射变换后，仍然保持平行性。 任意平面图形经过仿射变换后，其面积将发生变化，为变化前的( 耐一6 c ) 倍。 只有当( a d b c ) = 1 时，面积在仿射变换前后才不变。 设平面上一有面积区域为d ，经仿射变换r 变换后变成d 。，则d 与d 的面 积关系为： s ( d ) = id e t ( a ) i s ( d ) 这里i d e t ( d ) l 表示矩阵a 的行列式的绝对值，它是小于1 的j 下数，其中彳为系数 矩阵。 对于不同的c o , ( 持1 ，2 ，疗) ，有相应的系数a ，6 ，q ，t ，相应的常数e ，和，。 通常聆取2 ，3 ，4 ，有时高达1 6 。 对于一个比较复杂的图形，可能需要多个不同的仿射变换来实现，一个迭代 函数系统是由一组仿射变换族 国i ，2 国。) 组成，记为 国。， 珂= l ，2 ，胛) ，胛为整体所分局部的个数，仿射变换族 。) 控制着图形的结构 和形状，由于仿射变换的形式是相同的，所以不同的形状取决于仿射变换的系数。 另外，对应每一个缈。有一个伴随概率o 只 1 。 在仿射变换族 国) 中，每一个仿射变换被调用的概率不一定是等同的，就 是落入图形各部分中点的数目不一定相同，这就要引进一个仿射变换调用的概率 只，一般来讲概率只取决于仿射变换子图的面积，即子图面积越大，落入该子 2 0 山东师范大学硕士学位论文 图的点数就越多，此子图所对应的仿射变换系数被选中的概率就越大，对应的概 率值越大。确定概率只就相当于实现一个掷筛子的操作，在计算机上可以很容 易地用伪随机数发生器不断生成随机数，用来代替人工抛掷有n 个面的骰子。不 失一般性，设n = 4 ，每次用计算机生成一个随机数e ( 0 ，i 0 0 ) ，设o 屈 尾 屈 1 0 0 ，作如下规定： 若o e 屈，则选择规则i ， 若届e 屈，则选择规则