图形协同编辑一致性关键技术研究

2018-09-26李浪峰邬春学

软件导刊 2018年7期

李浪峰邬春学

摘要：图形协同编辑一致性关键技术能够解决多个用户对同一图形文档同步进行协同编辑时产生的并发问题，包括操作不同步、执行顺序冲突、意图冲突等。对实时协同设计过程中的一致性问题产生的原因和过程进行深入分析与研究，提出更为完善的解决方案，通过采用图形协同编辑一致性算法保证图形协同编辑操作一致性。实验结果表明，与其它解决方案相比，图形协同编辑一致性算法具有更佳的可行性与高效性。

关键词：图形编辑；协同设计；顺序冲突；意图冲突

DOI：10.11907/rjdk.181279

中图分类号：TP312

文献标识码：A文章编号：1672-7800（2018）007-0097-06

Abstract：Thekeytechnologiesofcollaborativeeditingconsistencybasedongraphicscansolvetheconcurrencyproblemcausedbymultipleuserscollaborativelyeditingthesamegraphicdocumentssynchronously.Concurrencyproblemsingraphicseditingcanleadtoinconsistenciesinoperations，conflictingexecutionorders，conflictingintents，andthelike.Wemakedeepanalysisandresearchonthecausesandprocessesoftheconsistencyproblemsinthereal-timecollaborativedesignprocess，andthenproposeamorecompletesolution.Byadoptingthegraphicsco-editingconsistencyalgorithm，theapporachensurestheconsistencyofgraphicscollaborativeeditingoperationsandverifiesbetterfeasibilityandefficiencyofthekeytechnologiesofgraphicsco-editingconsistencycomparedwithothersolutions.

KeyWords：graphicsediting；collaborativedesign；sequentialconflict；intentionalconflict

0引言

基于图形协同编辑的实时协同编辑设计系统允许多个用户通过互联网对同一图形文档进行编辑，是计算机支持协同工作（ComputerSupportedCooperativeWork，CSCW）的应用之一[1]，其应用领域涵盖医疗、教育、艺术和IT等。

图形协同编辑与其它协同编辑软件一样，必须满足以下条件：

①高响应。高响应是图形协同编辑的必备条件，能够促进协同编辑效率提升。在一定范围内，响应越迅速，图形协同编辑处理能力越好；

②鲁棒性。鲁棒性也是图形编辑系统的必备条件，因为鲁棒性越强，图形编辑系统应对各种突发情况能力越强；

③分布式。图形协同编辑大部分是基于分布式系统开发的，优点是不论何时何地用户都能进行协同工作。

图形协同编辑一致性关键技术是基于以上3个原则的研究性课题，因此如何满足协同操作一致性的要求，成为图形协同编辑一致性关键技术的核心问题。

近年来关于CSCW的研究取得了巨大进展，但国内图形协同编辑研究大都倾向于理论方面，应用研究较少，而图形协同编辑一致性关键技术属于应用技术研究范畴，图形协同编辑是一个复杂的系统，在该系统中，个体往往通过不同渠道相互作用[2]，因此本文从实际运用出发，提出一种强健的算法解决一致性缺失问题。

1图形协同编辑一致性相关概念

概念1：最小编辑单元。最小编辑单元图形绘制能够一次编辑最简单图形。图形协同编辑最小编辑单元为点、线，还可以是一个完整的图形，比如正三角形、正方形和圆。最小编辑单元用“”表示，如果操作是绘制一个点，可以表示为Point；如果是繪制一条最小单元的线，可以表示为Line。

概念2：意图一致性模型中操作规范表示。意图一致性模型中图形协同编辑的操作表达方式比其它一致性模型更复杂，每个操作需要添加协同编辑者意图。其中图形编辑操作具体有：增、删、转、移、复制等，如表1所示。

概念3：简单图形。图形协同编辑中三角形、四边形、正多边形（边数多于4）以及圆，都是简单图形。简单图形之外的图形都称为复杂图形。简单图形可以本身是最小编辑单元，也可以由若干最小编辑单元构成。

概念4：简单图形的中心。将简单图形的重心看作简单图形的中心，能更方便进行图形编辑。复杂图形可以看作由简单图形构成，因此对复杂图形进行图形编辑操作可以被认为是对构成复杂图形的简单图形进行相关编辑。在对简单图形进行Move、Rotate、Copy操作时，定位简单图形中心非常关键，对复杂图形进行操作时，可以先将复杂图形划分为若干简单图形，再找到简单图形的中心，最后对简单图形进行相关操作。

概念5：延时截止时间。延时截止时间，即某个操作从一个站点传送到另外一个站点规定的最大时延。在图形编辑时，操作在不同站点间传输需要时延，为了防止由于网络堵塞或故障导致某个操作遗失，在图形编辑系统中设置延时截止时间，如果有操作在延时截止时间内还没有到达目的站点，目的站点发出重发请求。根据不同的计算机网络环境，可以设置不同的延时截止时间。一个站点在发送某个操作到其它站点时，还需要发送操作收到确认信息，如果其它目的站点在延时截止时间内收到了该操作，即给源站点发送一个收到操作确认信息。

概念6：因果关系“→”。设来自Si的操作Om和来自Sj的操作On同时存在，Om→On需满足下列条件：=1＼*GB3i=j，Om发生在On之前；=2＼*GB3i≠j，Om在站点Sj上的执行要先于On；=3＼*GB3存在操作Ox，Om→Ox，Ox→Om。

概念7：并发关系“|”。设操作O1和操作O2，=1＼*GB3当且仅当O1→O2，则O1依赖O2，=2＼*GB3当且仅当O1不依赖O2，且O2不依赖O1，则O1和O2是并发关系，即O1|O2。

概念8：冲突关系“”。设操作O1和O2，当且仅当=1＼*GB3O1|O2；=2＼*GB3Target（O1）=Target（O2）；=3＼*GB3Attitude.key（O1）=Attitude.key（O2）；=4＼*GB3＼*MERGEFORMATAttitude.value（O1）≠Attitude.Value（O2），则O1和O2是冲突关系，即O1O2。

概念9：兼容关系“⊙”。如果操作O1和O2相互不冲突，则O1和O2相互兼容，即O1⊙O2。

概念10：兼容组集合（ComptibleGroupSet，CGS）。如果存在一组操作GO，且该操作中任意两个操作间的集合相互兼容，则GO构成的集合称为兼容组集合，即CGS。其中含有GO操作最多的兼容组集合称为最大兼容集合，即MCGS，且同一对像操作的最大兼容组集合MCGS是唯一的[3]。

概念11：图形覆盖。对不同对象进行图形编辑时，因为对象不同的操作相互兼容，如果在同一坐标位置出现两种以上的不同对象，将编辑时间晚的对象覆盖编辑时间早的对象。

概念12：并组操作（theCommongroupoftheoperations）。在图形编辑时，如果一个站点在短时间内不断进行操作，那么该站点的操作称为并组操作。在本文中，并组操作被认为不可分割。

概念13：相对位置差异“”。设O1是站点Site1的一个操作，由站点向其它站点传递，如果Oi是O1在第i个站点Sitei转换后的操作形式，设O1（x1，y1）、O2（x2，y2），则=x1-x22+y1-y22，相对位置差异值越小，说明一致性算法越好，理想值为0。

2一致性关键技术研究模型

图形编辑一致性技术模型主要包括3类：因果一致性模型（CausalConsistencyModel），结果一致性模型（ResultConsistencyModel），意图一致性模型（IntentionConsistencyModel）。

因果一致性指对任意的操作Om和On，如果Om→On，则所有站点的操作Om在On之前执行[4]。图形编辑因果一致性模型如图1所示。假设只有站点Site1和Site2进行图形协同编辑，协同用户在站点Site1的画布上进行五角星图形的操作O1，在操作O1中包含了该五角星图形对象的基本信息：图形ID、形状、颜色以及该图形在画板的位置坐标。在该站点执行O1操作之后，该站点画布右上方出现一个黑色五角星。与之同时，O1操作由站点Site1传送到站点Site2，站点Site2检查缓存区是否还有其它未执行的操作，如果没有其它操作在缓存中等待，则将操作O1送到站点Site2的待执行区，如果未检查到待执行区有其它尚未执行的操作，则站点Site2直接执行O1操作，在站点Site2的画布上出现与站点Site1一样的图形。在某个时间段，站点Site2产生了O2操作，当执行O2操作后，站点Site2画布右下角出现一个正六边形。然后站点Site2把操作O2传递到站点Site1，如果站点Site1中没有操作等候进入执行队列，在操作O2之前，也没有等候执行的操作，则在站点Site1执行O2。

设站点Site1，Site2，…，Siten（n≥2），根据实验得知，当n≥40时，图形协同编辑需要处理的信息量复杂度大幅上升，如图2所示。因果一致性模型适用于比较早期的图形协同编辑，如果多用户之间的操作没有并发，因果一致性模型是一种比较简单且非常适用的模型，同时也可以用在对并发操作比较兼容的编辑系统中。

结果一致性，即当一个协同会话在静默状态时，所有站点共享文档副本是一致的。结果一致性模型跟因果一致性模型有根本区别，结果一致性模型的操作之间并不一定需要存在某种特定关系，结果一致性模型只需要在協同站点间所有操作完成后，各站点间结果一致，结果一致性模型如图3所示。

当站点Site1创建并执行操作O1后，站点Site1画布右上角出现一个五角星，与此同时，站点Site1把O1操作传到站点Site2，但是O1传输需要一定时延，在O1操作还没到达站点Site2时，站点Site2创建了一个操作O2，即在画布左下角画出一个正六边形，在站点Site2执行完O2操作后，立即将O2操作传到站点Site1，当操作O1和O2分别到达站点Site1和Site2后，如果站点Site1和Site2没有缓冲区且等待执行区没有其它操作，则站点执行O1和O2，站点Site1画布左下方将画上一个正六边形，在站点Site2画布右上角将会出现一个正六边形。站点Site1和Site2最终结果一致，虽然操作O1、O2创建时间有先后，但在各站点间的执行顺序没有严格规定。图3中操作O1和O2的关系是O1⊙O2，因对同一对像的一组操作中最大兼容组集合MCGS是唯一的，因此如果对n个对象进行操作则有n个MCGS，即MCGS1、MCGS2…MCGSn，GO={MCGS1、MCGS2…MCGSn}，而MCGS1={Op1，Op2…Opn}，MCGS2={Ok1，Ok2…Okn}，…，MCGSn={Or1，Or2…Orn}，在MCGS中的操作相互兼容，即在MCGS中的操作不管按照何种执行顺序，最后各站点都能保持一致性[3]。

设站点Site1，Site2，……，Siten（n≥2），根据实验结果统计得知当n≥36时，图形协同编辑需处理的信息量复杂度大幅上升，如图4所示。

由图2和图4比较可以看出如果信息量较大，结果一致性模型在在单位时间内图形协同编辑处理优于因果一致性模型。因果一致性模型在图形协同编辑时需遵循操作间因果关系，由于实际图形协同编辑时，不同站点操作发送、接收、执行都有时延，尤其是互联网拥堵甚至瘫痪时，各站点如果采用因果一致性模型，会导致整个图形协同编辑系统效率严重下降、甚至瘫痪，但在结果一致性模型中各个MCGS的操作没有执行先后顺序之分，各个站点间操作独立性更强。所以在图形协同编辑系统中，结果一致性模型优于因果一致性模型。

意图一致性是指各站点产生操作时，操作对象之间建立某种操作效果序，通过执行调度算法和转换函数，确保每一步操作都不违背已建立的操作效果序，即保证当所有操作在各站点被执行后，各站点操作对象之间有相同的操作效果序，维护了操作意图的一致性[4]。

意图一致性模型如图5所示，其中有3个站点Site1、Site2和Site3，初始化GO={}和MCGS={}，表示GO和MCGS操作初始值为空，具体图形编辑过程如下：

（1）当操作O1和O2到达站点Site1时，变量更新为GO={O1，O2}，因为O1|O2，MCGS1={O1}，MCGS2={O2}；当站点Site1创建并执行O3操作时，变量进行更新，GO={O1，O2，O3}，因为（O1|O2）→O3，MCGS1={O1，O3}，MCGS2={O2，O3}；当操作O4到达站点Site1，变量进行更新，GO={O1，O2，O3，O4}，因为O1→O4，O2|O4，O3|O4，所以MCGS1={O1，O3}，MCGS2={O2，O3}，MCGS3={O1，O4}，最后GO={{O1，O3}，{O2，O3}，{O1，O4}}。

（2）在站点Site2创建O1后，变量更新GO={O1}，MCGS={O1}，当站点Site2创建并执行O2后，变量更新GO={O1，O4}，因为O1→O4，MCGS={O1，O4}。由于网络出现拥塞，超过延时截止时间后站点Site2还没有收到来站点site1发来的操作O3，所以站点Site2向站点Site1请求重新发送，站点Site1收到来自站点Site2的请求后，重新向站点Site2发送了操作O3，当站点site2收到O3操作后，对变量进行更新，GO={O1，O3，O4}，因为O1⊙O3且O1|O4，O3|O4，所以MCGS1={O1，O3}，MCGS2={O4}；当操作O2到达站点Site2的时候，变量更新为GO={O1，O2，O3，O4}，因为O2⊙O3，O2|O1，O2|O4，所以MCGS1={O1，O3}，MCGS2={O2，O3}，MCGS3={O1，O4}，最后GO={{O1，O3}，{O2，O3}，{O1，O4}}。

（3）在站点Site3创建操作O2，变量更新GO={O2}，MCGS={O2}，当操作O1到达站点Site3时，变量进行更新，GO={O1，O2}，O1|O2，所以MCGS1={O1}，MCGS2={O2}；当操作O3到达站点Site3，变量进行更新GO={O1，O2，O3}，O3⊙O1，O3⊙O2，所以MCGS1={O1，O3}，MCGS2={O2，O3}；当O4到达站点Site3时，变量进行更新GO={O1，O2，O3，O4}，因为O4⊙O1，O2|O4，O4|O3，MCGS1={O1，O3}，MCGS2={O2，O3}，MCGS3={O1，O4}，最后GO={{O1，O3}，{O2，O3}，{O1，O4}}。

综上可知，在一组操作GO中，MCGS的操作无需考虑执行顺序，因此图形协同编辑效率较高。然而结果一致性的不足之处在于图形协同编辑的结果并不一定是协同用户想获取的结果，如图5所示的实例中，最后虽然3个站点具有结果一致性，但是最后协同编辑可能出现的情况最多为23，而正常情况下协同用户只期待编辑后的结果是唯一的。由此可见，要进一步提高图形协同编辑的一致性，还需要一个更加完备的一致性模型，而意图一致性模型则能满足协同用户需求。

3一致性关键技术CGCE算法

图形协同编辑一致性关键技术的研究重点是意图一致性模型及其复杂算法，意图一致性是图形协同编辑最重要属性。图形协同编辑一致性关键技术CGCE算法如表2-表9所示。

4图形协同处理实现

（1）图形处理协同软件在谷歌浏览器打开时界面如图7所示，界面主要包含的按钮和功能是：①画任意曲线；②画任意大小的圆；③绘制立体图形，且能够对图形进行协同编辑。

（2）图形协同处理软件不仅能绘制各种图形，而且能实现在内网或外网连接时对图形进行协同处理，如图8所示。

5结语

本文主要从因果一致性、结果一致性、意图一致性3个方面分析图形协同编辑一致性的关键技术，并在此基础上提出了CGCE算法。该算法通过增加图形绘制的基本符号，能够对复杂图形进行数学描述，使复杂抽象的图形转变成简单具体的数学模型，在图形协同编辑中发挥了十分重要的作用。该算法还通过增加3个缓存空间、并发转换机制和撤销机制，有效解决了图形协同编辑中并发、网络拥堵或中断造成的一致性冲突问题。经过测试证明，本文设计的算法在原型系统上有效地解决了图形协同编辑一致性问题，实现了预期目标。

参考文献：

[1]施尉霁，尹建伟，陈刚，等.基于图形编辑的实时协同设计系统中的同步性问题研究[J].计算机工程与应用，2004，40（20）：95-98.

[2]李明，汪秉宏.多重网络的结构与鲁棒性[J].复杂系统与复杂性科学，2015，12（2）：32-37.

[3]SUNC，CHEND.Consistencymaintenanceinreal-timecollaborativegraphicseditingsystems[J].ACMTransactionsonComputer-HumanInteraction，2002，9（1）：1-41.

[4]何發智，吕晓，蔡维纬，等.支持操作意图一致性的实时协同编辑算法综述[J].计算机学报，2018（4）：840-867.

[5]GULMIRAT，邬春学.基于深度学习方法的句子及语素边界划分研究[J].电子科技，2017，30（9）：20-23.

[6]王树文，闫成新，张天序，等.数学形态学在图像处理中的应用[J].计算机工程与应用，2004，40（32）：89-92.

[7]魏武，张起森，王明俊，等.基于计算机视觉和图像处理的交通参数检测[J].信息与控制，2001，30（3）：257-261.

[8]余飞.HTML5图形图像处理技术研究[J].计算机光盘软件与应用，2013（12）：261-263.

[9]吴恩华，柳有权.基于图形处理器（GPU）的通用计算[J].计算机辅助设计与图形学学报，2004，216（5）：601-612.

[10]王晓宏，孙壮志.计算机协同设计中工作流可靠性的研究[J].计算机工程与应用，2003，39（3）：47-49.

[11]王培珍，许睿.任意多边形填充新算法[J].安徽工业大学学报：自科版，2009，26（4）：405-408.