圖形協同編輯一致性關鍵技術研究

李浪峰 鄔春學

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

關鍵詞：圖形編輯；協同設計；順序沖突；意圖沖突

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.

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

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

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

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

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

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

（責任編輯：江艷）