李浪峰 鄔春學

摘要：圖形協(xié)同編輯一致性關(guān)鍵技術(shù)能夠解決多個用戶對同一圖形文檔同步進行協(xié)同編輯時產(chǎn)生的并發(fā)問題，包括操作不同步、執(zhí)行順序沖突、意圖沖突等。對實時協(xié)同設(shè)計過程中的一致性問題產(chǎn)生的原因和過程進行深入分析與研究，提出更為完善的解決方案，通過采用圖形協(xié)同編輯一致性算法保證圖形協(xié)同編輯操作一致性。實驗結(jié)果表明，與其它解決方案相比，圖形協(xié)同編輯一致性算法具有更佳的可行性與高效性。

關(guān)鍵詞：圖形編輯；協(xié)同設(shè)計；順序沖突；意圖沖突

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引言

基于圖形協(xié)同編輯的實時協(xié)同編輯設(shè)計系統(tǒng)允許多個用戶通過互聯(lián)網(wǎng)對同一圖形文檔進行編輯，是計算機支持協(xié)同工作（ComputerSupportedCooperativeWork，CSCW）的應用之一[1]，其應用領(lǐng)域涵蓋醫(yī)療、教育、藝術(shù)和IT等。

圖形協(xié)同編輯與其它協(xié)同編輯軟件一樣，必須滿足以下條件：

①高響應。高響應是圖形協(xié)同編輯的必備條件，能夠促進協(xié)同編輯效率提升。在一定范圍內(nèi)，響應越迅速，圖形協(xié)同編輯處理能力越好；

②魯棒性。魯棒性也是圖形編輯系統(tǒng)的必備條件，因為魯棒性越強，圖形編輯系統(tǒng)應對各種突發(fā)情況能力越強；

③分布式。圖形協(xié)同編輯大部分是基于分布式系統(tǒng)開發(fā)的，優(yōu)點是不論何時何地用戶都能進行協(xié)同工作。

圖形協(xié)同編輯一致性關(guān)鍵技術(shù)是基于以上3個原則的研究性課題，因此如何滿足協(xié)同操作一致性的要求，成為圖形協(xié)同編輯一致性關(guān)鍵技術(shù)的核心問題。

近年來關(guān)于CSCW的研究取得了巨大進展，但國內(nèi)圖形協(xié)同編輯研究大都傾向于理論方面，應用研究較少，而圖形協(xié)同編輯一致性關(guān)鍵技術(shù)屬于應用技術(shù)研究范疇，圖形協(xié)同編輯是一個復雜的系統(tǒng)，在該系統(tǒng)中，個體往往通過不同渠道相互作用[2]，因此本文從實際運用出發(fā)，提出一種強健的算法解決一致性缺失問題。

1圖形協(xié)同編輯一致性相關(guān)概念

概念1：最小編輯單元。最小編輯單元圖形繪制能夠一次編輯最簡單圖形。圖形協(xié)同編輯最小編輯單元為點、線，還可以是一個完整的圖形，比如正三角形、正方形和圓。最小編輯單元用“”表示，如果操作是繪制一個點，可以表示為Point；如果是繪制一條最小單元的線，可以表示為Line。

概念2：意圖一致性模型中操作規(guī)范表示。意圖一致性模型中圖形協(xié)同編輯的操作表達方式比其它一致性模型更復雜，每個操作需要添加協(xié)同編輯者意圖。其中圖形編輯操作具體有：增、刪、轉(zhuǎn)、移、復制等，如表1所示。

概念3：簡單圖形。圖形協(xié)同編輯中三角形、四邊形、正多邊形（邊數(shù)多于4）以及圓，都是簡單圖形。簡單圖形之外的圖形都稱為復雜圖形。簡單圖形可以本身是最小編輯單元，也可以由若干最小編輯單元構(gòu)成。

概念4：簡單圖形的中心。將簡單圖形的重心看作簡單圖形的中心，能更方便進行圖形編輯。復雜圖形可以看作由簡單圖形構(gòu)成，因此對復雜圖形進行圖形編輯操作可以被認為是對構(gòu)成復雜圖形的簡單圖形進行相關(guān)編輯。在對簡單圖形進行Move、Rotate、Copy操作時，定位簡單圖形中心非常關(guān)鍵，對復雜圖形進行操作時，可以先將復雜圖形劃分為若干簡單圖形，再找到簡單圖形的中心，最后對簡單圖形進行相關(guān)操作。

概念5：延時截止時間。延時截止時間，即某個操作從一個站點傳送到另外一個站點規(guī)定的最大時延。在圖形編輯時，操作在不同站點間傳輸需要時延，為了防止由于網(wǎng)絡(luò)堵塞或故障導致某個操作遺失，在圖形編輯系統(tǒng)中設(shè)置延時截止時間，如果有操作在延時截止時間內(nèi)還沒有到達目的站點，目的站點發(fā)出重發(fā)請求。根據(jù)不同的計算機網(wǎng)絡(luò)環(huán)境，可以設(shè)置不同的延時截止時間。一個站點在發(fā)送某個操作到其它站點時，還需要發(fā)送操作收到確認信息，如果其它目的站點在延時截止時間內(nèi)收到了該操作，即給源站點發(fā)送一個收到操作確認信息。

概念6：因果關(guān)系“→”。設(shè)來自Si的操作Om和來自Sj的操作On同時存在，Om→On需滿足下列條件：=1＼*GB3i=j，Om發(fā)生在On之前；=2＼*GB3i≠j，Om在站點Sj上的執(zhí)行要先于On；=3＼*GB3存在操作Ox，Om→Ox，Ox→Om。

概念7：并發(fā)關(guān)系“|”。設(shè)操作O1和操作O2，=1＼*GB3當且僅當O1→O2，則O1依賴O2，=2＼*GB3當且僅當O1不依賴O2，且O2不依賴O1，則O1和O2是并發(fā)關(guān)系，即O1|O2。

概念8：沖突關(guān)系“”。設(shè)操作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是沖突關(guān)系，即O1O2。

概念9：兼容關(guān)系“⊙”。如果操作O1和O2相互不沖突，則O1和O2相互兼容，即O1⊙O2。

概念10：兼容組集合（ComptibleGroupSet，CGS）。如果存在一組操作GO，且該操作中任意兩個操作間的集合相互兼容，則GO構(gòu)成的集合稱為兼容組集合，即CGS。其中含有GO操作最多的兼容組集合稱為最大兼容集合，即MCGS，且同一對像操作的最大兼容組集合MCGS是唯一的[3]。

概念11：圖形覆蓋。對不同對象進行圖形編輯時，因為對象不同的操作相互兼容，如果在同一坐標位置出現(xiàn)兩種以上的不同對象，將編輯時間晚的對象覆蓋編輯時間早的對象。

概念12：并組操作（theCommongroupoftheoperations）。在圖形編輯時，如果一個站點在短時間內(nèi)不斷進行操作，那么該站點的操作稱為并組操作。在本文中，并組操作被認為不可分割。

概念13：相對位置差異“”。設(shè)O1是站點Site1的一個操作，由站點向其它站點傳遞，如果Oi是O1在第i個站點Sitei轉(zhuǎn)換后的操作形式，設(shè)O1（x1，y1）、O2（x2，y2），則=x1-x22+y1-y22，相對位置差異值越小，說明一致性算法越好，理想值為0。

2一致性關(guān)鍵技術(shù)研究模型

圖形編輯一致性技術(shù)模型主要包括3類：因果一致性模型（CausalConsistencyModel），結(jié)果一致性模型（ResultConsistencyModel），意圖一致性模型（IntentionConsistencyModel）。

因果一致性指對任意的操作Om和On，如果Om→On，則所有站點的操作Om在On之前執(zhí)行[4]。圖形編輯因果一致性模型如圖1所示。假設(shè)只有站點Site1和Site2進行圖形協(xié)同編輯，協(xié)同用戶在站點Site1的畫布上進行五角星圖形的操作O1，在操作O1中包含了該五角星圖形對象的基本信息：圖形ID、形狀、顏色以及該圖形在畫板的位置坐標。在該站點執(zhí)行O1操作之后，該站點畫布右上方出現(xiàn)一個黑色五角星。與之同時，O1操作由站點Site1傳送到站點Site2，站點Site2檢查緩存區(qū)是否還有其它未執(zhí)行的操作，如果沒有其它操作在緩存中等待，則將操作O1送到站點Site2的待執(zhí)行區(qū)，如果未檢查到待執(zhí)行區(qū)有其它尚未執(zhí)行的操作，則站點Site2直接執(zhí)行O1操作，在站點Site2的畫布上出現(xiàn)與站點Site1一樣的圖形。在某個時間段，站點Site2產(chǎn)生了O2操作，當執(zhí)行O2操作后，站點Site2畫布右下角出現(xiàn)一個正六邊形。然后站點Site2把操作O2傳遞到站點Site1，如果站點Site1中沒有操作等候進入執(zhí)行隊列，在操作O2之前，也沒有等候執(zhí)行的操作，則在站點Site1執(zhí)行O2。

設(shè)站點Site1，Site2，…，Siten（n≥2），根據(jù)實驗得知，當n≥40時，圖形協(xié)同編輯需要處理的信息量復雜度大幅上升，如圖2所示。因果一致性模型適用于比較早期的圖形協(xié)同編輯，如果多用戶之間的操作沒有并發(fā)，因果一致性模型是一種比較簡單且非常適用的模型，同時也可以用在對并發(fā)操作比較兼容的編輯系統(tǒng)中。

結(jié)果一致性，即當一個協(xié)同會話在靜默狀態(tài)時，所有站點共享文檔副本是一致的。結(jié)果一致性模型跟因果一致性模型有根本區(qū)別，結(jié)果一致性模型的操作之間并不一定需要存在某種特定關(guān)系，結(jié)果一致性模型只需要在協(xié)同站點間所有操作完成后，各站點間結(jié)果一致，結(jié)果一致性模型如圖3所示。

當站點Site1創(chuàng)建并執(zhí)行操作O1后，站點Site1畫布右上角出現(xiàn)一個五角星，與此同時，站點Site1把O1操作傳到站點Site2，但是O1傳輸需要一定時延，在O1操作還沒到達站點Site2時，站點Site2創(chuàng)建了一個操作O2，即在畫布左下角畫出一個正六邊形，在站點Site2執(zhí)行完O2操作后，立即將O2操作傳到站點Site1，當操作O1和O2分別到達站點Site1和Site2后，如果站點Site1和Site2沒有緩沖區(qū)且等待執(zhí)行區(qū)沒有其它操作，則站點執(zhí)行O1和O2，站點Site1畫布左下方將畫上一個正六邊形，在站點Site2畫布右上角將會出現(xiàn)一個正六邊形。站點Site1和Site2最終結(jié)果一致，雖然操作O1、O2創(chuàng)建時間有先后，但在各站點間的執(zhí)行順序沒有嚴格規(guī)定。圖3中操作O1和O2的關(guān)系是O1⊙O2，因?qū)ν粚ο竦囊唤M操作中最大兼容組集合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中的操作不管按照何種執(zhí)行順序，最后各站點都能保持一致性[3]。

設(shè)站點Site1，Site2，……，Siten（n≥2），根據(jù)實驗結(jié)果統(tǒng)計得知當n≥36時，圖形協(xié)同編輯需處理的信息量復雜度大幅上升，如圖4所示。

由圖2和圖4比較可以看出如果信息量較大，結(jié)果一致性模型在在單位時間內(nèi)圖形協(xié)同編輯處理優(yōu)于因果一致性模型。因果一致性模型在圖形協(xié)同編輯時需遵循操作間因果關(guān)系，由于實際圖形協(xié)同編輯時，不同站點操作發(fā)送、接收、執(zhí)行都有時延，尤其是互聯(lián)網(wǎng)擁堵甚至癱瘓時，各站點如果采用因果一致性模型，會導致整個圖形協(xié)同編輯系統(tǒng)效率嚴重下降、甚至癱瘓，但在結(jié)果一致性模型中各個MCGS的操作沒有執(zhí)行先后順序之分，各個站點間操作獨立性更強。所以在圖形協(xié)同編輯系統(tǒng)中，結(jié)果一致性模型優(yōu)于因果一致性模型。

意圖一致性是指各站點產(chǎn)生操作時，操作對象之間建立某種操作效果序，通過執(zhí)行調(diào)度算法和轉(zhuǎn)換函數(shù)，確保每一步操作都不違背已建立的操作效果序，即保證當所有操作在各站點被執(zhí)行后，各站點操作對象之間有相同的操作效果序，維護了操作意圖的一致性[4]。

意圖一致性模型如圖5所示，其中有3個站點Site1、Site2和Site3，初始化GO={}和MCGS={}，表示GO和MCGS操作初始值為空，具體圖形編輯過程如下：

（1）當操作O1和O2到達站點Site1時，變量更新為GO={O1，O2}，因為O1|O2，MCGS1={O1}，MCGS2={O2}；當站點Site1創(chuàng)建并執(zhí)行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創(chuàng)建O1后，變量更新GO={O1}，MCGS={O1}，當站點Site2創(chuàng)建并執(zhí)行O2后，變量更新GO={O1，O4}，因為O1→O4，MCGS={O1，O4}。由于網(wǎng)絡(luò)出現(xiàn)擁塞，超過延時截止時間后站點Site2還沒有收到來站點site1發(fā)來的操作O3，所以站點Site2向站點Site1請求重新發(fā)送，站點Site1收到來自站點Site2的請求后，重新向站點Site2發(fā)送了操作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創(chuàng)建操作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的操作無需考慮執(zhí)行順序，因此圖形協(xié)同編輯效率較高。然而結(jié)果一致性的不足之處在于圖形協(xié)同編輯的結(jié)果并不一定是協(xié)同用戶想獲取的結(jié)果，如圖5所示的實例中，最后雖然3個站點具有結(jié)果一致性，但是最后協(xié)同編輯可能出現(xiàn)的情況最多為23，而正常情況下協(xié)同用戶只期待編輯后的結(jié)果是唯一的。由此可見，要進一步提高圖形協(xié)同編輯的一致性，還需要一個更加完備的一致性模型，而意圖一致性模型則能滿足協(xié)同用戶需求。

3一致性關(guān)鍵技術(shù)CGCE算法

圖形協(xié)同編輯一致性關(guān)鍵技術(shù)的研究重點是意圖一致性模型及其復雜算法，意圖一致性是圖形協(xié)同編輯最重要屬性。圖形協(xié)同編輯一致性關(guān)鍵技術(shù)CGCE算法如表2-表9所示。

4圖形協(xié)同處理實現(xiàn)

（1）圖形處理協(xié)同軟件在谷歌瀏覽器打開時界面如圖7所示，界面主要包含的按鈕和功能是：①畫任意曲線；②畫任意大小的圓；③繪制立體圖形，且能夠?qū)D形進行協(xié)同編輯。

（2）圖形協(xié)同處理軟件不僅能繪制各種圖形，而且能實現(xiàn)在內(nèi)網(wǎng)或外網(wǎng)連接時對圖形進行協(xié)同處理，如圖8所示。

5結(jié)語

本文主要從因果一致性、結(jié)果一致性、意圖一致性3個方面分析圖形協(xié)同編輯一致性的關(guān)鍵技術(shù)，并在此基礎(chǔ)上提出了CGCE算法。該算法通過增加圖形繪制的基本符號，能夠?qū)碗s圖形進行數(shù)學描述，使復雜抽象的圖形轉(zhuǎn)變成簡單具體的數(shù)學模型，在圖形協(xié)同編輯中發(fā)揮了十分重要的作用。該算法還通過增加3個緩存空間、并發(fā)轉(zhuǎn)換機制和撤銷機制，有效解決了圖形協(xié)同編輯中并發(fā)、網(wǎng)絡(luò)擁堵或中斷造成的一致性沖突問題。經(jīng)過測試證明，本文設(shè)計的算法在原型系統(tǒng)上有效地解決了圖形協(xié)同編輯一致性問題，實現(xiàn)了預期目標。

參考文獻：

[1]施尉霽，尹建偉，陳剛，等.基于圖形編輯的實時協(xié)同設(shè)計系統(tǒng)中的同步性問題研究[J].計算機工程與應用，2004，40（20）：95-98.

[2]李明，汪秉宏.多重網(wǎng)絡(luò)的結(jié)構(gòu)與魯棒性[J].復雜系統(tǒng)與復雜性科學，2015，12（2）：32-37.

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

[4]何發(fā)智，呂曉，蔡維緯，等.支持操作意圖一致性的實時協(xié)同編輯算法綜述[J].計算機學報，2018（4）：840-867.

[5]GULMIRAT，鄔春學.基于深度學習方法的句子及語素邊界劃分研究[J].電子科技，2017，30（9）：20-23.

[6]王樹文，閆成新，張?zhí)煨?，?數(shù)學形態(tài)學在圖像處理中的應用[J].計算機工程與應用，2004，40（32）：89-92.

[7]魏武，張起森，王明俊，等.基于計算機視覺和圖像處理的交通參數(shù)檢測[J].信息與控制，2001，30（3）：257-261.

[8]余飛.HTML5圖形圖像處理技術(shù)研究[J].計算機光盤軟件與應用，2013（12）：261-263.

[9]吳恩華，柳有權(quán).基于圖形處理器（GPU）的通用計算[J].計算機輔助設(shè)計與圖形學學報，2004，216（5）：601-612.

[10]王曉宏，孫壯志.計算機協(xié)同設(shè)計中工作流可靠性的研究[J].計算機工程與應用，2003，39（3）：47-49.

[11]王培珍，許睿.任意多邊形填充新算法[J].安徽工業(yè)大學學報：自科版，2009，26（4）：405-408.

[12]沈穎，宋文強.計算機圖形學的基本算法實現(xiàn)研究[J].電腦知識與技術(shù)，2009，5（4X）：4518-4519.

[13]胡光華.計算機圖形學的數(shù)學工具與C#實現(xiàn)[J].國外科技新書評介，2010（2）：21-22.

[14]徐保民，時炳艷.應用協(xié)同技術(shù)研究[J].計算機工程與應用，2002，38（14）：106-108.

[15]吳文傳，張伯明.基于圖形數(shù)據(jù)庫的網(wǎng)絡(luò)拓撲及其應用[J].電網(wǎng)技術(shù)，2002，26（2）：14-18.

[16]吳恩華.圖形處理器用于通用計算的技術(shù)、現(xiàn)狀及其挑戰(zhàn)[J].軟件學報，2004，15（10）：1493-1504.

[17]柳海蘭.淺談計算機圖形學的發(fā)展及應用[J].電腦知識與技術(shù)，2010，6（33）：9551-9552.

（責任編輯：江艷）