（计算机应用技术专业论文）绣花cad中若干技术的研究.pdf

浙江大学硕士学位论文 摘要 在计算机科学不断发展的今天，学科与学科之间的联系变得非常密切，各个 学科之间的相互交叉和合作在不断的加深。随着网络技术的不断进步以及人工智 能研究的不断深入，传统c a d 系统与这些学科之间的交互合作也就成为了c a d 技 术发展的一个显著的趋势，如何使c a d 技术与上述技术更好的结合已经成为许多 学者研究的课题。c a d 系统向着集成化，网络化以及与人工智能的结合等方向发 展，这种发展带动着电脑绣花c a d 系统向前发展电脑绣花c a d 系统不仅应该根 据其自身的特点不断的发展创新，还要与上述几个领域的交互合作的方向上不断 的向前发展。 本文在电脑绣花c a d 系统的基础上，介绍了c a d 系统与网络以及智能化等的 结合情况，对系统中的一些问题做了研究并完成了一些设计和比较工作文章由 六个部分组成。第一部分对c a d 系统的情况作了简单的介绍，包括基本概念、发 展历程、在我国的发展现状以及今后发展的趋势。第二部分介绍了电脑绣花c a d 系统，包括电脑绣花c a d 系统的背景，系统模型的设计和系统中各个模块的作用 以及它们之间的相互关系第三部分对系统中的绣花制版模块作了介绍，包括针 法的简单介绍和针法、花稿结构的设计。第四部分则讨论了系统中的网络协同模 块，主要包括对网络协同基本的概念和原理的说明，网络模型的设计和协同算法 的设计以及如何与电脑绣花c a d 系统结合等方面的研究。第五部分则主要研究智 能模块，包括对图像的滤波除噪、轮廓识别、轮廓跟踪提取、形状识别以及针法 生成等的应用和研究。最后一部分内容则是对全文的总结和展望 关键词绣花c a d ，网络协同，图像处理，轮廓识别，针法生成 浙江大学硕士学位论文 a b s t r a c t a st h ed e v e l o p m e n to f c o m p u t e rs c i e n c e , r e l a t i o nb e t w e e ns u b j e c t sb e c o m e sv e r y c o n s a n g u i n e o u s a n dt h ec o l l a b o r a t i o nb e t w e e ns u b j e c t s 蛳b e c o m i n gi n t e n s i v e w i t h t h e c o n t i n o u s p r o g r e s s o f t h e n e t w o r k t e c h n o l o g ya n d t h ec o n t i n o u s l u c u b r a t i o n o f t h e a r t i f i c i a li n t e l l i g e n c c ( a i ) t h ec o l l a b o r a t i o nb e t w e e nt r a d i t i o n a lc a d s y s t e ma n dt h e s e s u b j e c t sb e c o m e san o t a b l et r e n do f 也ec a dt e c h n o l o g i c a ld e v e l o p m e n t , t od ob e r e t c o l l a b o r a t i o nb e t w e e nt h e mh a sb e c o m ear e s e a r c hs u b j e c to fm a n ys c h o l a r s n 砖 d e v e l o p m e n to ft h ec a ds y s t e ma l ei nt h ed i r e c t i o no fi n t e g r a t i o n , n e t w o r k i n ga n d t h ec o l l a b o r a t i o nw i t ha r t i f i c i a li n t e l l i g e n c e , t h ed e v e l o p m e n ta r es i m u l a t i n gt h e d e v e l o p m e n to ft h ee m b r o i d e r y - c a ds y s t e m e m b m i d e r y - c a ds y s t e ms h o u l d d e v e l o pn o to n l ya c c o r d i n gt oi t si n t r i n s i cc h a r a c t e r i s t i c , b u ta l s od e v e l o pi nt h e d i r e c t i o no f c o l l a b o r a t i o nw i t ht h e s es u b j e c t sm e n t i o n e da b o v e t i l i sp a p e rp r e s e n t st h ec o l l a b o r a t i o nb e t w e e nc a ds y s t e ma n dn e t w o r k i n g , a i e t c ，d or e s e a r c ht ot h ep r o b l e m si nt h es y s t e ma n dd os o m ec o m p a r i s o na n dd e s i g n w o r kb a s e do nt h ee m b r o i d e r y - c a ds y s t e m t h ep a p e ri s m p o s e do fs i xp a r t s 1 1 他 f i r s tp a r tp r e s e n t sa l le a s yi n t r o d u c t i o nt ot h ec a d s y s t e m , i n c l u d i n gt h eb a s i cc o n c e p t , t h ed e v e l o p m e n th i s t o r y , t h ec u r r e n ts t a t u so ft h ed e v e l o p m e n ti nc h i n aa n dt h e d e v e l o p m e n tt r e n d s t h es e c o n dp a r ti n 删u c e st h ee m b r o i d e r y - c a ds y s t e m , w h i c h c o n t a i n st h eb a c k g r o u n d , d e s i g no f t h es y s t e mm o d e l ，t h ef u n c t i o no f e a c hm o d u l ea n d t h ei n t e r r e l a t i o nb e t w e e nm o d u l e s n 圮t h i r dp a r tb e g i n sw i t ha ni n u o d u c t i o nt o e m b r o i d e r ym o d u l e , m a i n l ya b o u tt h ec o s yi n t r o d u c t i o nt os t i t c ha n dt h ed e s i g no f s t i t c ha n de m b r o i d e r ys t r u c t u r e t h ef o u r t hp a r td i s c u s s e st h en e t w o r k - c o l l a b o r a t i o n m o d u l ei ns y s t e m , i n c l u d i n gb a s i cc o n c e p ta n dp r i n c i p l eo fn e t w o r k - c o l l a b o r a t i o n , t h e d e s i g no fi n t e m e tm o d e la n dc o l l a b o r a t i v ea l g o r i t h m , a n dt h er e s e a r c ho ft h e i n t e g r a t i o n 埘t l lt h ee m b r o i d e r y - c a ds y s t e m t h e 丘f l l ip a r tm a i n l yf o c u so nt h e i n t e l l i g e n c em o d u l e , w ed i s c u s si m a g ef i l t e r i n g , c d g ed e t e c t i o n , e d g ct r a c ea n d e x a c t i o n , s i m p er e c o g n i t i o na n ds t i t c hg e n e r a t i o n n el a s tp a r ti sas u m m a r yo ft h e p a p e ra n dt h ee x p e c t a t i o n e m b r o i d e r y - c a d ,n e t w o r k - c o l l a b o r a t i o n , m a g e - p r o c e s s i n g , e d g e - d e t e c t i o n ，s t i t c h - g e n e r a t i o n 浙江大学硕士学位论文图目录 图目录 图2 1 系统模型图5 图3 1 针法类视图7 图3 2 针法对象数据结构图8 图3 - 3 花稿类视图。 图3 - 4 花稿类数据结构图 图4 - l 协同系统中的冲突 图4 - 2 c s 模型 图4 3 p p 模型 图无效法图示 图4 _ 5 选择保留法图示 图禾6 虚拟主机网络模型 图4 7 对象数据结构图 2 2 图4 8 对象复制图示。3 l 图4 9 冲突的操作引起的不一致。3 2 图5 - 1 腐蚀 图5 - 2 膨胀 4 1 4 2 图5 - 3 图像处理算法流程图。 图5 _ 4 轮廓识别算法实现结果对比图。4 5 图5 5 轮廓线图。 图5 - 6 先搜索到内轮廓图4 6 图5 7 先搜索到外轮廓图 图5 8 一条与原点距离为s ，方向角为a 直线 4 9 图5 - 9 圆与其内接三角形关系图5 0 图5 1 0 圆形图像针法填充效果图 图5 1 l 不规则图像针法填充效果图。 图5 1 2 花稿针法自动生成效果图 i l l 5 2 5 3 浙江大学硕上学位论文 表目录 表目录 表4 1 主机0 上的操作队列片段 表4 2 主机0 的挂起操作队列h q 的片段 表4 _ 3 主机0 上的h o b 片段。 i v 3 0 3 6 浙江大学硕士学位论文 第1 章绪论 第1 章绪论 1 1c a d 基本概念 c a d ，计算机辅助设计( c o m p u t e ra i d e dd e s i g n ) ，是在计算机操作系统的框 架为支撑发展起来的一门技术，它能进行产品的方案设计、解析计算、判断优化、 分析评估和详细设计，通过设计，以数据文件和工程数据库定义产品结构信息， 以数学模型、计算分析和绘图指标建立产品过程信息，其根本目的是为产品的开 发和生产建立模型。c a d 按照应用领域可以分为机械c a d 、建筑c a d 、电子c a d 、 计算机辅助工业设计和地图c a d 【i l 等。 c a d 技术具有工程及产品的分析计算、几何建模、仿真与试验、绘制图形、 工程数据库管理和生成设计文件等功能经过多年的努力，c a d 技术的广泛应用 已经引起了一场工程设计领域的技术革命，特别是近些年以来，由于计算机硬件 性能的不断提高，c a d 技术有了大规模的发展。 1 2c a d 的发展历程 从开始c a d 技术处于被动式的图形处理阶段，到许多c a d 商品化系统，再到 后来完整c a d 系统的出现，c a d 技术正一步步的走向成熟，c a d 技术开始向着开 放式、标准化、集成化和智能化方向2 1 进一步向前发展。 1 3c a d 在我国的发展现状 c a d 技术已经广泛地应用在国家经济建设和高精尖科技的各个领域，包括建 筑业，航空航天等行业应用c a d 技术和软件能够帮助企业提高经济效率，主要 表现在提高制造企业的设计效率，减轻技术人员的劳动强度，优化项目设计方案， 提高设计质量减短开发周期，实现设计的统一标准化等作用。在许多的c a d 领域 除了引进国外的软件外，还出现了不少具有我们自己版权的c a d 系统。 尽管我国在c a d 技术的研究、开发和推广等方面都取得了长足的进步，但我 国的c a d 技术在应用和技术水平的广度和深度上与发达国家相比仍然存在比较大 差距。首先是国内生产高精设备的技术水平还不能满足要求；其次是国内自行研 制开发的c a d 软件的市场占有率较低；最后，c a d 技术的应用主要还是在计算机 辅助制图方面，应用领域还不够广泛 浙江大学硕士学位论文 第1 章绪论 1 4c a d 的发展趋势 随着各种技术的不断发展，c a d 技术的主要发展趋势总结起来有： i 网络功能 c a d 技术作为计算机应用的一个重要方面，同样离不开网络技术【3 l ，网络是 是计算机和通讯互相协作的产物，网络技术的不断发展使得它与计算机科学的各 个领域都能紧密结合，c a d 技术作为计算机应用的一个重要方面，同样离不开网 络技术。随着网络的不断普及，c a d 与网络的结合是大势所趋，比如协同设计， 应用共享等。 2 与人工智能结合 智能化是c a d 发展的必然趋势，其主要的要求是c a d 系统不仅仅能够处理数 据，而且能处理学习知识，它能进行选择、判断，并做出推理、优化，做出决策， 所以与人工智能领域有着广泛的合作前景。c a d 系统可以和人工智能中的专家系 统结合，形成智能c a d 专家系统，而神经网络也能在c a d 的得到巨大应用，它的 自组织和自学习能力，以及比较好的容错性能，使得它能够将c a d 系统的智能化 进一步提高。 3 系统集成 以集成化的工作平台系统为基础的c a d 系统将可能成为应用的主流，集成化 是多角度、多层次的【4 1 这点其实与网络功能有类似之处，但是不同在于它所希 望建立的是一个综合各种功能的分布式的网络工作平台要集成设计管理等各个 环节，系统的目的是实现信息集成和资源共享。而它成为主流的优势主要有费用 低廉，性价比高，可以单机版工作，也可以网络协同工作，具有良好的联网能力， 使用和维护起来均很方便。 4 变量化和参数化 变量化及参数化设计思想和特征造型代表了当今c a d 技术的发展方向c a d 系统增加了变量化和参数化设计模块，使得产品的设计图可以随着某些结构尺寸 的修改和使用环境的变化而自动修改图形，这可以方便用户来减轻设计工作量， 从而减少大量的重复劳动。变量化设计可以用于公差分析、运动机构协调、设计 优化、初步方案设计选型等，尤其在进行概念设计时更显得得心应手【习。 5 产品标准化 由于历史上c a d c a m 软件最初开发过程中标准的不统一，使得它们数据表示 格式的不统一，进而使得不同系统、不同模块间的数据交换比较困难，从而影响 了c a d c a m 系统的集成，然而随着c a d 和c a m ( c o m p u t e ra i d e dm a n u f a c t u r e ) 2 浙江大学硕上学位论文 第l 章绪论 技术的广泛应用，c a d 系统和c a m 系统的品种越来越多，为了便于把c a d 系统产 生的结果传送并提供给c a m 使用，或者将不同的c a d 系统组合起来使用以及共 享一些资源等等原因，国际上提出了通用的数据交换规范，使c a d 软件建立在这 些标准上，以实现系统的开放性、可移植性、可互连性。现在国际上的主要标准 有初始图形信息交换标准( i g e s ，i n i t i a lg r a p h i c se x c h a n g es p e c i f i c a t i o n ) 以及产品模型数据交换标准( s t e p ，s t a n d a r df o rt h ee x c h a n g eo fp r o d u c tm o d e l d a t a ) 【6 】等等。 6 可视化效果 由于可视化的界面比较直观，而且用户易于接受，所以，在c a d 软件中对 于用户友好的图形界面的要求也就越来越高越来越多，不但要求能绘制出生产用 的各种设计工程项目，而且还要求系统的计算处理设计等效果都能可视化。 3 浙江大学硕士学位论文第2 章绣花c a d 系统 第2 章绣花c a d 系统 2 1 背景 刺绣，又称丝绣，是中国优秀的民族传统手工工艺，先后产生号称“四大名 绣”的苏绣、粤绣、湘绣、蜀绣。刺绣产品一直广受国人青睐，同时也是我们对 外贸易的重要产品之一。随着社会的经济的不断发展，国内和国际市场对其需求 量越来越大。传统的人工刺绣已经不能满足需要了在这样的矛盾背景下，刺绣 的机械化和自动化就必然要发展起来 绣花机主要可以分为多头绣花机和单头绣花机，现在占主流的是多头绣花 机，而在市场中占据主导地位的则主要是国外( 主要是同本、德国) 的绣花机， 这样给国内的厂商带来经济上的巨大负担，一方面是购买设备所花费的钱，还有 就是购买与设备匹配的c a d 绣花软件所需承担的费用并且国外的c a d 软件在针 法和功能上却也不一定能够适用我国厂商的需要。 在这样的情况下，我国许多单位都开始研究并开发自己的c a d 绣花系统，其 中浙江大学，上海交通大学，南京大学等单位都开发了各自的系统。现在网上比 较热门的绣花c a d 软件有田岛，山诺，威尔克姆，青鹤，京华，富怡电脑绣花c a d 系统等。 浙江大学的绣花c a d 软件大致经过了前辈们的开发，已经从基于d o s 平台到 现在基于w i n d o w s 平台【7 l ，并且在实际的生产应用中取得了良好的口碑和经济效 益，如浙江大学和青州刺绣花边厂合作开发的多机种刺绣c a d 系统册在导师的 指导下，总结前人的工作成果，我进行了重新建模，设计了新的系统框架和结构， 在类体系上做了改进以适应新系统的需求：根据c a d 系统的发展趋势，尝试着在 系统中增加了网络协同功能，完成了网络协同模块的算法设计以及具体算法的实 现并取得了良好的效果；在系统中增加了对花稿轮廓识别以及针法生成的研究并 进行了测试，对针法生成进行了实验并取得了很好的效果；对系统的实用性和健 壮性以及界面上做了进一步的加强和改进。 4 浙江大学硕士学位论文第2 章绣花c a d 系统 2 2 系统模型 图2 - i 系统模型图 系统的模型图如图2 - i 所示。 我们采用将功能模块化的思想，将该程序分按功能块划分，功能块之间的交 互通过箭头标出 浙江大学硬士学位论文 第2 章绣花c a d 系统 用户通过操作主程序的界面来控制程序 下面一节将大致介绍各个功能模块。 2 3 功能模块简介 2 3 1 绣花制版模块 该功能模块负责处理单机用户的一般操作，包括一般的制作绣花图，参数的 设置，保存花版到库，模拟实际绣花效果，针法的选择等等。 2 3 2 网络协同模块 主要的部分是网络协同设计模块，当然其中的核心包括了网络冲突检测识别 和解决的算法而我们的系统可以添加其它如音视频聊天等功能 2 3 3 轮廓识别和针法生成模块 包括图像轮廓识别，按颜色块分块，针法的自动生成，还有就是用户手动描 针，其中涉及到图像处理的算法等。 2 3 4 功能模块交互 各个模块各自都有自身需要负责的功能，然而有些功能必须通过调用别的模 块的功能才能做到，如下所示： 单机绣花制版模块和轮廓识别和针法生成模块之间相互有调用关系 网络协同模块需要使用单机绣花模块的基本功能 网络协同模块中也会用到针法生成模块中的功能( 通过调用单机模块) 。 网络模块其实是相对独立的，把它拿掉或者说用户并不启用网络功能这个系 统仍然完整，只是变成了单机的电脑绣花c a d 软件了 6 浙江大学硕士学位论文第3 章绣花制版 3 1 针法类和花稿类 3 1 1 针法类 第3 章绣花制版 c s t i t c h b a s e c s t i t c h b a s e + m _ p r e ；指向前一节点，第一个节点该值为n u l l c s t i t c h b a s e t n e x t ：指向后一个节点，最后节点该值为n u l l c s t i t c h b a s e 宰mc o p y ；指向由于意图冲突引起的复制对象链表头 c s t i t c h b a s e m _ c o p y _ p r e ；指向复制对象链表中的前一个节点 b o o lm _ _ i s c h o s e n ； 表示该针段是否被用户选中，初始为f a l s e i n tm _ n e e d l e n u m ；针法针数 i n tm _ s h o u p t n u m ； 针脚数 i n tmb o n e n u m ； 骨架控制点个数 i n tml e f t ，m _ t o p ，mr i g h t 。m _ b o t t o m ；四个方向的坐标 t c o l o rmc o l o r ；本段颜色 p o i n t 奉m _ b o n e p t ：骨架坐标链表头 b 0 0 1i sd e l ： 是否被删除 c s t i t c h b a s e ( ) ： c s t i t c h b a s e ( ) ： v i r t u a lv o i dd r a w ( i n tx o ，i n ty o ，i n tx 1 ，i n ty l ，i n tp n d l n u m ) = o ： 所有子类都将继承并实现的画针法的函数 v o i ds e t n e e d l e n u m ( i n tp n n ) ：设置针的数目( 密度) v o i ds e t c o l o r ( t c o l o rp c o l o r ) ： 设置针段的颜色 v o i dm o v e s e c t ( i n tx ，i n ty ) ： 平移针段，x ，y 代表平移量 v o i dr o t a t e s e c t ( d o u b l ep a n g e l ) ：旋转针段 其他一些辅助函数 图3 - i 针法类视图 7 浙江大学硕士学位论文第3 章绣花制版 针法类的类视图如图3 - 1 所示 这是一个抽象基类，不能生成对象，只能通过继承有派生类来产生对象。所 有的针法，如后面的3 2 节中介绍的单针等都从这里继承。 对于针法类的画法中很重要的一个问题，就是曲线的画法，我们知道已经有 很多成熟的算法，比如贝赛尔曲线或者b _ 样条曲线【l l ，但是我们这里为了平分 曲线方便，我们采用的是类似与参考文献( 1 2 中的圆弧画法。 成员变量里的c s t i t c h b a s e * m _ p r e 和c s t i t c h b a s e * m _ n e x t 是用来将一个 个的对象串成双向链表的，这个链表保存在后面介绍的花稿类对象中，链表的第 一个元素的m _ p r e 和最后一个的m _ n e x t 指向n u l l 。采用双向链表是为了链表更 加稳定牢固，另一个更重要的原因就是为了在后面的协同算法中处理节点的插入 和删除更加的方便，这点我们在后面的章节中将具体的阐述其原因。是否被删除 是用在后面的协同算法中的撤销( u n d o ) 操作中的产生的结果如图3 2 所示 图3 - 2 针法对象数据结构图 而同样的c s t i t c h b a s e * m _ c o p y 和* m _ c o p y _ p r e 是在网络协同时出现冲突后 用来保存因为冲突产生的复制品链表，详细的介绍在网络协同部分。 后面的域是一些针法段的基本信息，如所在矩形框的坐标信息，颜色信息， 骨架点的链表等等。 函数中d r a w 函数是每个派生类都必须去实现的，因为每种针法的画法不同， 浙江大学硕士学位论文第3 章绣花制版 而其他一些函数是基本信息的操作函数。 3 1 2 花稿类 c e m b r o i d e r y i n tms e c t n u m ； 总段数 i n tmn e e d l e n u m ； 总针数 d o u b l em _ z o o m ； 放大或缩小倍数 c s t i t c h b a s e 木m _ h e a d ；链表头指针 c s t i t c h b a s e m _ t a i l ：链表头指针 s t r i n gmg n a m e ；花稿名称 c e m b r o i d e r y ( ) c e m b r o i d c r y 0 ：构造和析构函数 v o i du s e r c h o o s e ( i n tx o 。i n ty o ，i n tx l 。i n ty 1 ) ： 执行用户来选中段这个动作，遍历链表并设置每一个节点的 m _ i s c h o s e n 值并刷新图案，选中的变色或者高亮 b o o ld e l e t e s e c t i o n0 ： 执行用户删除选中的那些段的命令 b 0 0 1 d d s e c t i o n ( c s t i t c h b a s e * p s b ) ： 执行用户增加一个段的命令 b o o lm o d i f y s e c t i o n ( i n tp c m d ) ： 执行用户修改选中的段的命令( 包括密度修改，平移，转向等) b 0 0 1c o p y s e c t i o n ( c s t i t c h b a s e * p s b ) ： 执行用户复制选中的段的命令 b o o ll o a d g b f i l e ( s t r i n gp n a m e ) ： 从花稿文件中载入花稿 b 0 0 1s a v e g b f i l e ( s t r i n gp n a m e ) ： 从花稿文件中载入花稿 其他一些辅助函数 图3 - 3 花稿类视图 9 浙江大学硕士学位论文 第3 章绣花制版 花稿类的设计如图3 3 所示。 成员变量中保存了该花稿的基本信息， 对文件读写的操作 针法段之间用指针相连构成链表结构， 和尾指针的两个指针。 而成员函数主要是对段的处理函数和 而花稿对象中保存了指向链表头指针 - - g j j 束o 绣花稿是由许多的针法对象组成的，每个针法对象又由许多的针步组 成，这样一个结构可以用图3 - 4 的树状结构来表示。 图3 4 花稿类数据结构图 l o 浙江大学硕士学位论文第3 章绣花制版 3 2 针法简介 单针 一般用来刺绣一些比较细的线段，常用于走底线或者包边中，主要用途是用 来包轮廓的。可以加饰花版产生特殊的针迹效果。单针的针步由人来设定。在图 形中有急转弯的时候可以把单针的针步适当放小 挨针 挨针包括了满针，放射针和包针，主要用于来填绣形状细长而弯曲的线条， 挨针的线条感和立体感都很强，针法生动、活泼，覆盖性也很好，但是对于宽度 比较大的图形，挨针的针迹就会拉的比较长，针迹线拉的越长，就越稀松。这正 是挨针不适合绣教宽图形的原因如果输入的轮廓线超过了挨镇的最大步长软件 会自动在挨针中加入一些下针点，这样会在挨针中产生一条明显的线条，影响绣 品的美观。 e 型针 e 型针看上去很象一把梳子，主要用在包边或者填绣较稀松的图形上。最常 用的是在镶绣中的包边上，为了使e 型针迹能更好的跟随图形边界，可以在e 型 针迹中插入几针单针针迹。 塌塌米 塌塌米主要用于填绣大面积的图形或不规则的图形，它是由特殊排列方式的 单针组成，这些针迹跨过整个图形，沿与图形边界相垂的方向排列，分别形成一 组前进和返回针迹，每一列的针迹都按照一定的偏移值来排列，从而避免在图形 中产生明显的分割线。塌塌米的针迹排列紧凑，平行 浙江大学硕士学位论文 第4 章网络协同 第4 章网络协同 4 1 背景 c a d 技术的不断发展带动着电脑绣花c a d 系统的发展，电脑绣花c a d 系统的 发展主要是不同品牌软件的出现，在系统中新的针法的不断加入，更加真是和精 彩的针剂效果，三维立体仿真模拟效果的加入，浮雕效果的针法填充技术的出现， 对文字字库直接调用并生成打版。 在网上种类众多的电脑绣花c a d 系统如田岛，山诺，富怡等主流产品都没有 提供网络协同操作设计的功能，由前述的c a d 发展趋势看，c a d 技术与网络技术 的结合是一种必然的趋势，越来越多的公司出于利益的考虑都希望能够将自己的 c a d 系统与网络结合起来0 3 , 1 s 。随着网络的不断普及，设计人员会希望在自己家 里同别的设计人员一起来完成对花稿的设计。因此我们在这里提出了网络协同绣 花c a d 系统的概念，并且对这个系统进行了系统算法设计和实现，希望能对电脑 绣花c a d 以后的发展做出一些帮助。 4 2 协同系统 4 2 1 协同系统特征 网络协同绣花c a d 系统允许一组分散在各地的人通过网络对绣花稿同时进行 查看设计和修改。在这种网络协同系统中，一个很核心的问题就是对共享的对象 图形的并发操作，即不同用户对相同的某个对象的某个相同的属性做出了不同的 修改，在这种情况下如何处理这种冲突，如何保持各个系统的一致性 其实保持一致性在很多网络协同系统中都是一个基本性的要求，包括数据库 系统【1 4 】，分布式系统【1 5 l ，协同文字编辑系统f ，组件系统【1 7 1 等等。不管是应用在 什么系统，一般来说，协同系统应该满足下面2 个要求： 1 响应速度快 即使用户使用不同的主机，处在不同的网络环境，存在不同程度的网络延时， 但是当某一用户执行一个操作的时候，系统必须而且应该给予很快的响应。因为 首先，对用户来说，他看到的只是系统对他所做操作的即时响应速度的快慢和效 果是否和他的意图一致，他不会想知道你所做的是什么函数。从协同系统本身来 1 2 浙江大学硕士学位论文 第4 章网络协同 讲，很快的响应速度是其自身所必须具备的特征，较差的响应速度会使得系统的 交互设计性大打折扣。 2 并发性好 协同操作的一个目标就是每个人都像在单机工作，并不受别人的影响，而实 际上他是和其他一组人在协同。这就要求任何成员用户在任何时候都能够对共享 花稿的任何部分进行编辑设计修改。这里的主要问题就在于，当两个或者多个用 户对同一对象做了不同的操作的时候，如何解决他们之徊j 的冲突。 如果要满足对用户有较快的响应速度的这个要求，我们必须设计成在每台机 器上都有一份自己的数据，这样用户一旦执行了某种操作，可以现在本地进行执 行响应，然后通过消息等方式传播到远程节点。那么为了这个要求，我们就不能 采用c s 模型结构了。 要满足第二个关于并发性的要求，系统中就不能采用对某个对象加锁的方 式，即一旦某个主机的用户率先选中某针法对象，则通过发消息给服务器宣布对 该对象加锁，并占有该对象直到它解除这个锁。 4 2 2 协同系统中的冲突 霪矮 t i m e - 图4 1 协同系统中的冲突 圆圈团 浙江大学硕士学位论文 第4 章网络协同 由于满足响应速度快的要求形成的每台机器上有自己的一份数据的模型，这 就需要我们处理随之而来的3 个冲突：因果关系冲突，歧义冲突和意图冲裂嘲。 1 因果关系冲突 由于网络通信延时或者其它某种原因，几个操作到达某个站点以及在这个站 点的执行顺序就有可能和它们应该的顺序产生不同，这里说的应该的顺序是指操 作产生的时间先后。如图4 1 所示，图中u 1 、u 2 、u 3 代表三台参加协同的机器， 横轴代表的是时间进度，c 1 、c 2 、c 3 分别是三个用户所做的操作。从时问上来看 c 3 早于c 2 ，c 2 早于c 1 从u 2 中我们看到，c 3 到达u 2 并且执行的时候c 2 还没 有产生，那么c 2 可能就依赖于c 3 ，或者换一个说法，它们应该的执行顺序是( c 3 ， c 2 ，然后我们在看u l ，由于网络延迟或者其它某些原因，c 3 比c 2 更晚到达u 1 ， 这样c 2 就比c 3 在u 1 上更早的被执行，从而和它们应该的顺序产生了冲突。因 果关系冲突是可以用一种序列化的协议来解决的嗍。 2 歧义冲突 由于不淘的操作到达某个站点的顺序以及在这个站点的执行顺序不同，这样 不同的主机就会产生不同的结果，导致了不一致，我们称为歧义冲突。如图4 - 1 所示，在主机u l 上，操作的执行顺序是 c 2 ，c 1 ，c 3 ，而在主机u 2 上的操作 执行顺序则是 c 3 ，c 2 ，c ll ，在u 3 上则变成了 c 3 ，c l ，c 2 ) 。除非这些操作 之间都互不相关，否则它们三组的操作结果一定是不同的。很显然我们必须解决 这个问题，使锝最终的结果一致。 比如我们假设c 1 是将某个针法对象移动到点p 1 ( x l ，y 1 ) ，而c 2 是将某个 针法对象移动到点p 2 ( x 2 ，y 2 ) ，其中p 1 p 2 ，那么当序列执行完毕的时候， u 2 上的该针法对象在点p 1 ，而u 3 上的对象则在p 2 。 3 意图冲突 由于各个用户在执行操作的时候，别的用户也同时在执行操作，他们不会去 考虑别人会不会操作这个对象，这样就导致了用户在某个时刻所做操作的意图和 这个操作在执行的时刻所实际发生的效果可能发生偏差或者不同。 如图4 一l 的模型中，假设c 3 是在末尾插入一个新针法对象，而c 1 也是在末 尾插入另一个对象，那么当c 3 在u l 执行的时候，c l 已经在u 1 执行过了，这时 候的末尾一段针法已经变成了由操作c 1 产生的新的针法对象了，此时的c 3 操作 所完成的效果和其原来的效果已经不是一样的了。 上述的三种冲突问题是彼此独立的，也就是说，某一个或者某两个的发生并 不一定会导致另外一个或一些的发生我们还要指出的是歧义冲突和意图冲突的 1 4 浙江大学硕士学位论文第4 章网络协同 不同歧义冲突和意图冲突的根本不同是歧义冲突总是可以通过一种序列化的协 议来解决，然而如果所有的操作都是按照原来的计划按部就班的执行，那么意图 冲突是不能被任何序列化的协议所解决的2 0 1 。 4 3 模型分类 我认为网络协同模型按照通信方式不同可以分为以下三种： 4 3 1c s 模型 如图4 - 2 所示，这就是我们通常所说的客户端服务端模型，在该模型中， 有一台机器在建立的时候成为实际意义上的主机，其它机器要加入协同操作、设 计都必须与主机建立联系。在成功建立联系以后，该客户端只与主机保持通信关 系客户端要进行任何相关操作，包括新建一个针法对象，移动一个对象，改变 其属性值等等，都必须通过命令的形式发往主机，由主机进行判断协调仲裁后在 以命令的方式广播发回所有客户端。 图4 - 2 c s 模型 浙江大学硕士学位论文 第4 章网络协同 这种模型解决网络同步的方法是所有的数据都只在服务器上，客户端对数据 是“透明”的，客户端要执行一个操作，则必须通过消息的方式传到服务端，由 服务端根据各个客户端提供的消息的时间戳或者其他的方式来判断是否可以执 行，通过则服务端对唯一的一份位于服务端的数据进行更新，并且通知各客户端 进行位图的更新。优点是几乎不会产生数据同步的问题，因为“可见”的数据只 在服务器上存在，而缺点就是当网络出现问题滞后的时候，客户端并不能对数据 迸行实际的操作，从而甚至无法保证本地拥有的数据和程序中显示的画面相吻 合，并且不能很好的满足响应速度快的要求，还有就是服务器的负担会比较重。 4 3 2 p - p 模型 该模型如图4 - 3 所示，每台机器还是先与某台主机建立连接，然后有该主机 将所有与其连接的机器的地址发给要求连接的机器，然后此机器在根据地址一一 去建立两两连接 这个模型的特点是所有的机器都是平等的，它们之阀相互建立连接，任何通 信都不再经过服务器转发，而是自己其实就是一台为自己转发信息的服务器。在 这个模型中，对每台机器的端口是比较浪费的，同时将原来属于服务器的负担丢 给了各主机。与服务器模型形成对比的是其复杂的网络结构，这样使得每台机器 的网络负担也会加重。 图4 _ 3 p o p 模型 1 6 浙江大学硕上学位论文 第4 章闷络协同 4 3 3 广播模型 广播模型与前两种模型结构相比，不需要开始的时候去寻找主机建立连接。 该模型的特点是通过广播来发送命令和消息，任何机器有操作或者命令都直 接向某些段广播。这样的优点是网络结构简单，但是缺点也很明显，就是广播将 占用大量的网络资源，使得网络上的其他用户的网络瘫痪等，还有就是向什么地 址广播这部分需要通过一些其他手段来获得。 4 4 协同算法分类 下面将要介绍的是几种网络协同算法，包括仲裁法( 如用加锁法【1 9 b ，时间 戳法【2 1 , 2 8 1 ，无效法和选择保留法。 4 4 1 仲裁法 这种方法采用前面章节介绍的c s 结构模型，由服务器束仲裁，所有用户的 操作命令都通过服务器来决定是否有效，具体策略可以采用对对象加锁等方法， 但是这种方法是不符合协同系统的两个特征的，即违背了响应速度快和并发性好 这两条要求。 4 4 2 时间戳法 时间戳法的基本思想就是在系统中事先定义某种协议，在这种协议里规定了 各个协同主机之间有一种全局的逻辑时间标准，每个操作都会将主机自己的逻辑 时间按照一定的步伐增加，每次都通过比较本地的逻辑时间和到达的逻辑时间来 判断是否可能产生冲突 时间戳是一种很好的解决因果冲突的一种方法，目前主要的实现手段主要有 三种： 1 单一变量法 基本的想法是每台机器用一个无符号整型变量标志自己机器的逻辑时间 值【捌，每到执行一个操作时，将自己的逻辑时间值加上一个事先设定的常量d ， 如果收到一个新的消息则将消息中带的逻辑时间值和自己的比较，选择较大的一 个值来更新自己的逻辑时间值，并将这个值用来更新消息的逻辑时间值。 2 时间向量法 假设协同系统中的协同用户的数量是n ，分别编号为0 ，l ，2 n l ，那么 1 7 浙江大学硕士学位论文 第4 章网络协同 每台协同主机上都保存一份有n 个无符号整型变量所组成的数组，假设编号i 的 机器上的数组为v i 1 n 。那么这个数组中的v i j 的值代表的就是在编号为i 的机器上在这个时刻所知道的关于j 台机器在这个时刻的逻辑时问值的信息田l 。 如果用户i 将要执行一个操作，那么它会先将自己的逻辑时间值加上一个固定的 步伐值d ，当有新的命令消息来的时候，则系统将根据比较的结果来判断是否可 能产生冲突并更新自己这里的值。 3 矩阵法 用矩阵来表示时问向量【2 4 】。假设协同系统中的协同用户的数量是n ，分别编 号为1 ，2 n ，那么每台协同主机上都保存一份有n * n 个无符号整型变量所组成 的矩阵，假设第i 台机器上的矩阵为m i o n - 1 0 n - 1 ，那么m i i i 代 表的是i 这台机器自己所拥有的逻辑时自j 信息，而m i i 儿j 代表i 这台主机所知 道的最新的j 主机的逻辑时间值的信息，m j k ( j i ) 代表的是i 主机所知道 的最新的j 机器所拥有的k 机器的逻辑时间值的信息。 4 4 3 无效法 当两个或多个操作有冲突的时候，我们可以采用这种无效法，即将所有的互 相产生冲突的操作都设置为无效的，也就是所有的操作都不发挥作用，如果发现 已经执行的某个或某些操作与某个当前操作冲突了，可以采用取消操作( u n d o ) 的方法 1 8 浙江大学硕上学位论文 第4 章网络协同 匿一j r 习 莨。+ 一l 赫爵驾i 埘。搠瀛 。 函蔫，7 i 。以魏 ? 司 f 。万习 艮一、一l 一。一、一i 。涵 图4 - 4 无效法图示 如图4 - 4 所示，这就是一个无效法执行的例子。 初始状态下u 1 ，u 2 都含有一个针法对象0 ，某个时刻u 2 执行了将针法对象0 移动到点p 2 的操作，并且在本地执行后发往协同方u 1 ，然而在受到u 2 关于对针 法对象0 移动的操作前，u l 执行了将针法对象o 移动到另外一个点p l 的操作， 并在执行后将其通知协同方u 2 这样两个操作如果不经过处理而顺序执行的话， 最后在u l 的针法对象0 是在点p 2 ，而