張新長,郭泰圣,唐 鐵
中山大學地理科學與規劃學院,廣東廣州510275
一種自適應的矢量數據增量更新方法研究
張新長,郭泰圣,唐 鐵
中山大學地理科學與規劃學院,廣東廣州510275
針對GIS增量更新中存在的一致性維護與空間沖突問題,提出一種自適應的矢量數據增量更新方法。以同名對象匹配為切入點,探討變化對象的檢測與增量更新的方式。在綜合考慮空間距離,語義相似度及拓撲一致性約束的基礎上,提出接邊匹配度的計算方法并設計自適應的對象接邊算法。同時,介紹矢量數據增量更新中基于約束規則的空間沖突檢測與處理方法。并以矢量地形圖試驗數據驗證文中所提出的模型與算法。
自適應;增量更新;數據一致性;空間沖突
矢量空間數據更新是維護空間數據庫現勢性的主要手段[1],已成為GIS的前沿研究課題。其研究重點主要為變化信息檢測,更新事件建模和空間沖突檢測。在變化信息檢測方面,國內外學者從空間疊加[2]、拓撲關聯等角度[3-4],結合更新事件特征[5]提出檢測方法。文獻[3—4]以拓撲聯動的方式進行實體變化類型的推斷,為增量更新中拓撲一致性的維護提供了新思路。然而,拓撲判斷的準確性容易受到數據不確定性的影響,且聯動規則與專題信息聯系密切,通用性有待進一步提高。在更新事件時空建模方面,研究內容已從基于版本管理的更新模式[6-7]發展到顧及更新傳播與一致性維護的空間數據模型[8]及基于拓撲一致性維護的時空過程建模[9-10]。文獻[8]在概念層面為GIS更新模型設計提出了解決思路,其具體的表達形式及實際的應用仍需要更深入的研究。文獻[10]所提出的數據模型兼顧了拓撲關系維護與時空信息管理,有助于更新信息與歷史數據的管理。但是,該模型對于拓撲關系的維護只局限于相鄰對象,需要深化對復雜空間關系處理的研究??臻g沖突檢測與數據完整性維護是空間數據更新的另一個重要問題[11]。學者提出了空間實體完整性約束表達形式[12]及空間沖突的確認方法[13-14]。文獻[12]所提出的約束模型有利于保證更新后數據的質量。然而,該模型缺少對屬性及規則重要性的明確說明。在對象觸犯多條約束規則時,處理的優先度需要更深入的考慮。
目前的研究側重從變化檢測及時空過程建模的角度,探討更新方法、流程及變化信息的存儲方式,對數據一致性維護及空間沖突處理的論述不夠充分。因此,本文從增量更新與數據完整性維護的角度出發,提出一種自適應的矢量數據增量更新方法,實現矢量數據變化檢測與增量更新、自適應的數據接邊及空間沖突的檢測與處理等功能,以保證更新后數據的完整性與一致性。
2.1 總體設計
本文所指的“更新數據”是地形圖修補測量、竣工測量或市政測量產生的矢量空間數據,可作為增量信息進行更新。本文主要針對同級比例尺的更新研究,更新數據預處理操作是指在更新前依據入庫標準,對更新數據進行坐標系、數據結構及拓撲關系的檢查與修正處理,以產生標準數據。增量更新方法是利用對象的空間相似性、幾何距離與拓撲特征進行變化目標檢測[15-16],然后進行添加、刪除、幾何或屬性修改等更新處理。在更新過程中有可能產生同一地理實體的分割或空間錯位。因此,需要進行對象的接邊處理。更新數據采集或建模的差異有可能產生不合理的空間關系,有必要進行空間沖突的檢測與處理。更新過程還包括歷史數據的存儲、管理與回溯功能。具體的實現步驟如圖1所示。
2.2 空間對象變化檢測與增量更新實現步驟
本文通過進行新舊數據間的實體匹配處理,檢測空間對象的變化信息,再根據變化信息的分類采取不同的更新操作(見圖2)。具體的步驟如下:

圖1 矢量數據自適應增量更新方法Fig.1 An adaptive updating method of vector data

圖2 矢量數據變化信息檢測與增量更新方法Fig.2 Change detection and incremental updating operations of vector data
(1)同名實體的匹配。點狀實體的匹配通過比較兩者的歐氏距離進行判斷。線狀實體的匹配可通過計算Hausdorff距離[17],Fréchet距離或折線-點距離[18]實現。面狀實體的匹配可以通過位置鄰接度或重疊相似度確定。
(2)更新信息的檢測。如果沒有原對象與目標對象匹配,則認為目標對象是新增對象。沒有目標對象與原對象匹配,認為原對象是消失對象。對于1∶1的對象匹配需要進一步比較幾何形狀與屬性信息,判斷是否發生變化。原對象與目標對象1∶n的匹配表明原對象的分解,m∶1的匹配則表示原對象的合并。m∶n的對象匹配表示出現了對象的聚合。
(3)面向對象的增量更新方法。對象的更新操作可分為創建、刪除、幾何修改與屬性修改。對于新增或消失的對象可直接使用創建或刪除操作;對于發生幾何形狀或屬性變化的對象,則進行幾何修改或屬性修改。處理對象合并、分解及聚合的情況,均可采用刪除原對象,創建與之匹配的目標對象進行處理。
2.3 接邊匹配度計算與自適應的接邊算法
2.3.1 接邊匹配度計算
異構數據的增量更新可能會引入時空的不確定性,造成同一地理目標實體的分割及空間錯位。因此,需要進行接邊操作。接邊對象的確定與空間距離,語義相似度及空間關系等因素有關。本文提出的接邊匹配度計算模型如式(1)所示。

式中,M(A,B)表示對象A、B之間的接邊匹配度;d(A,B)是對象A、B的距離衡量指標;s(A,B)為語義相似度衡量指標;r(A,B)表示對象A、B的空間關系,通過實體的緩沖區重疊面積計算進行衡量。ω1、ω2、ω3為權重值,其取值在[0,1]之間,且
距離鄰接度的指標d(A,B)的值越大,說明對象A、B的距離越近,接邊可能性越大。設對象點集分別為Apts{a1,…,ap}、Bpts{b1,…,bq},式(2)

式中,|Apts-Bpts|是點集Apts和點集Bpts的歐氏距離。min()函數是點集中最近兩點的距離。dtolerance為距離閾值,若最近距離大于閾值,說明對象A、B之間的距離太遠,超出了接邊的考慮范圍。
s(A,B)為對象的語義相似度。語義相似越高,說明兩對象越有可能是同一地理實體的分割,接邊的必要性更大。根據Cobb提出的對象屬性匹配算法[19],語義相似度評價模型如公式(3)所示

式中,N為屬性數目;simAk是第k項屬性值的相似程度;ESWAK為第k項屬性的權重。屬性類型不同,計算語義相似度的方法也有所差異。
對于數值型的屬性,語義相似度可按式(4)計算

式中,x、y分別為接邊對象的數值型;sim(x,y)值反映了數值型屬性的語義相似度。
對于字符型屬性的語義相似性的計算可分為兩種情況。定類或定序屬性按照語義排成偏序關系,通過計算次序的差別計算語義相似度。對于語義關聯性屬性不強的屬性,則通過計算字符串之間的編輯距離(由字符串A編輯為字符串B所需要進行的最小編輯操作次數)判斷兩者的語義相似性,具體如式(5)所示

式中,order(x)、order(y)表示x、y在屬性中的次序編號;N為屬性值個數,對應于分類數或屬性值的最大編號。
r(A,B)反映了A、B的空間關系,通過對象的緩沖區重疊面積計算進行衡量,計算方法如式(6)所示

式中,buffer(A)、buffer(B)表示對象A、B的緩沖區面積;intersect()函數計算重疊的面積,max()函數用于選擇較大的緩沖區面積。
2.3.2 自適應接邊的算法
目前的接邊方法通過搜索鄰近要素及比較屬性來確定接邊對象[20-21],容錯能力不強,難以處理屬性不完整的數據。而且判斷的因素單一,容易造成匹配錯誤。傳統的接邊處理直接采用union方法進行對象合并[21],對數據特征的考慮不充分,缺乏靈活性。
自適應處理是根據數據特征自動調整處理方法、參數或約束條件,以取得最優效果的方法。在全球地形可視化[22]、全球離散格網建模[23]、制圖表達等GIS領域得到了廣泛應用。本文的接邊方法綜合多項評價指標,能更客觀地反映對象特征,有助于提高準確度與容錯能力。該方法的自適應性體現在:系統根據數據的精度特征,自動調整對象位移;選擇合適的接邊方法,使其與高精度的數據相適應。具體實現步驟如下:
(1)進行更新對象周邊區域的緩沖區搜索,確定候選接邊對象。線對象在首尾節點處創建緩沖區,進行候選對象的搜索。面對象則按一定距離創建緩沖區并搜索相交對象,作為候選接邊對象。
(2)進行候選對象的接邊匹配度計算,選取匹配度最高的對象進行接邊操作。
(3)接邊操作需根據對象的幾何類型進行相應處理。線對象的優先接邊策略是通過比較更新數據與原數據的精度,接邊到精度較高的數據。如果數據間的精度相差不大,則可選用平均接邊法(見圖3)。

圖3 線對象優先接邊策略Fig.3 Edge matching preferential method of line features
面對象接邊策略首先根據數據的精度選擇平移的方式,精度低的數據平移至精度高的數據,精度接近的數據則讓新舊對象分別平移坐標偏移量的一半。以房屋面對象接邊為例進行說明:假設房屋面是具有4個節點的規則矩形,更新后房屋被分為兩個獨立對象。比較鄰近的節點P1、P3或P2、P4的坐標,計算出坐標偏移量。由于對象精度相近,因此把節點分別平移坐標偏移量的一半。最后利用P′1、P′2、P′3、P′44個節點來重畫一個多邊形(見圖4)。

圖4 面對象優先接邊策略Fig.4 Edge matching preferential method of polygon features
(4)屬性融合。接邊后對象的屬性融合有3種方式,一是以原始數據的屬性作為接邊后對象的屬性;二是以更新對象的屬性作為接邊后對象的屬性;三是通過數值計算的方法獲取接邊后對象的屬性,如數值平均,求和等。
2.4 基于約束規則的空間沖突檢測與處理
數據更新可能會帶來不符合完整性約束的空間關系,不能正確表達現實地理實體的結構特征[24]。因此,更新后需要進行空間沖突的檢測與處理[25]。空間沖突的檢測可以通過定義約束規則來實現。本文以Hakima Kadri-Dahmani提出的空間實體完整性約束表達式[12]為基礎,修改了約束對象類的表達方法,并添加了屬性約束規則與重要性指標。以六元組的方式表達約束規則

式中,ID是空間沖突約束的編號;C1、C2為受約束的空間對象類;TR表示指拓撲約束規則;AR表示屬性約束規則;Bd表示規則的執行的范圍;I是指該規則的重要性,取值在0~1之間。
空間沖突的檢測方法是按照空間沖突約束規則,使用顧及語義的拓撲檢驗方法構建約束條件進行目標搜索??臻g沖突的處理則利用空間編輯功能對沖突對象進行處理。反復檢驗直至消除所有沖突后,才進行歷史庫備份與現狀庫更新處理,完成更新的全過程。
為驗證本文所提出的更新模型與方法,本文在Windows環境下,以Visual Studio 2008為開發工具,集成ArcEngine開發包研制了更新原型系統。實現了增量更新,自適應接邊及空間沖突檢測等功能,以1∶1000矢量地形圖數據進行試驗(見圖5)。

圖5 自適應的矢量數據增量更新試驗Fig.5 An experiment of the adaptive incremental updating method
式(1)中接邊匹配度的計算與對象之間的空間距離、語義相似度及空間關系等因素密切相關。其中,語義相似度的計算取決于對象屬性值的整體匹配程度。作為關鍵字的編碼在語義相似度的計算中應占較大的比重(見圖6),以保證接邊對象的屬性一致性。

圖6 接邊匹配中的語義相似程度評價Fig.6 The evaluation of semantic similarity in edge matching
接邊匹配度參數的設置是通過分析更新對象與原數據,找出必須要進行接邊的樣例對象m對{{A1,B1},{A2,B2},…,{Am,Bm}},把它們的接邊匹配度M(Ai,Bi)設置為1,找出明顯不需要接邊的樣例對象n對{{A1,B1},{A2,B2},…,{An,Bn}},把它們的接邊匹配度設置為0。分別計算對象Ai,Bi的距離鄰近度d(Ai,Bi),語義相似度s(Ai,Bi)與空間關系衡量指標r(Ai,Bi)。然后,計算各分指標與接邊匹配度的相關系數ri,并對相關系數進行歸一化處理,作為接邊匹配度的權重參數。
接邊匹配度的閾值選擇影響著接邊的準確度與查全率,本文將接邊匹配度設為不同數值進行試驗。試驗結果如圖7所示。觀測結果表明隨著匹配閾值的提高,匹配要求越嚴格,查準率也相應提高,并在匹配閾值為0.96處達到高峰。然而,匹配要求的過分嚴格會造成查全率降低,查全率在匹配閾值為0.95處達到高峰后就逐漸下降。

圖7 接邊匹配度閾值對接邊結果的影響Fig.7 The impact of threshold to the edge-matching results
根據上述參數確定的方法,對接邊匹配度的計算參數設定如下:距離指標的權重設為0.6,語義相似度指標的權重設為0.2,空間關系指標的指標值設為0.2,匹配度的閾值設為0.95。將不同的更新樣本導入程序進行計算,自適應接邊運算的結果如表1所示。

表1 自適應接邊方法的試驗結果Tab.1 Experimental results of the adaptive edge matching method
試驗表明,自適應接邊匹配度與接邊算法在運算過程中可以保持健壯性,運算速度保持穩定。綜合考慮幾何與語義條件的接邊匹配算法準確程度與查全率高,能夠實現自適應的接邊操作。
在算法試驗中,本文定義了空間沖突拓撲的樣例規則,以地形圖數據進行模擬運算,空間沖突的檢測結果如表2所示。

表2 基于約束規則的空間沖突檢查試驗Tab.2 The experiment of rule-based spatial conflict detection
試驗結果顯示:在矢量數據增量更新中產生了空間沖突現象,導致數據的相互關系與地理現實不符,沖突的檢查與處理具有必要性?;诩s束規則的空間沖突檢查方法能有效地檢測出錯誤,結合人工的空間沖突確認與處理,有助于更新后數據庫的拓撲一致性維護。
本文以一致性維護與空間沖突處理為切入點,提出了一種自適應的矢量數據增量更新方法。試驗表明該方法可應用到基礎地理數據庫及規劃管理數據庫的更新與維護中。增城市規劃管理數據庫系統使用本文所提出的方法,在2008—2011年之間把增城市區域內742宗建設用地竣工測量數據作為增量信息進行入庫更新,減少了大量人工操作。因此,可以得出以下結論:
(1)本文所提出的自適應的對象接邊算法綜合考慮了對象間的空間距離、語義相似度及拓撲一致性,對幾何及語義聯系最緊密的對象進行自適應的接邊處理??捎糜诮鉀Q矢量數據更新中的數據完整性維護的問題。
(2)基于約束規則的空間沖突檢測與處理方法,有助于修正與現實地理實體不符的空間關系,維護更新后空間數據庫的拓撲一致性。該約束模型設計合理、計算效率高,有利于更新過程中數據質量的控制。
本文提出的增量更新方法是針對同級比例尺的數據進行處理。如果更新數據與基礎地理數據的比例尺不同,需要依據相應的數據規范,對更新數據進行制圖綜合處理。此外,還需要結合多尺度對象匹配的技術進行變化檢測,確定更新的對象與范圍,以執行跨尺度的聯動更新處理。這將是本文后續的研究重點。為更好地提高更新效率與自動化程度,自適應的矢量數據更新方法還應該朝著智能化與網絡化的方向發展。因此,進一步的研究工作包括:① 以更新信息的跨尺度傳遞為切入點,結合制圖綜合模型與算法,探討多尺度空間數據聯動更新算法;② 應用人工智能與數據挖掘技術,確定接邊匹配度模型中的權重參數,并實現空間沖突約束規則的自動提取,提高算法的智能化水平;③ 搭建空間數據動態更新的網絡服務框架,實現自適應的矢量數據在線動態更新。
[1] BRIAT M O,MONNOT J L,KRESSMANN T.Incremental Update of Cartographic Data in a Versioned Environment[C]∥Proceedings of 22nd ICA Conference.A Coru?a:[s.n.],2005:1-9.
[2] CHEN Jun,LIN Yan,LIU Wanzeng et al.Formal Classification of Spatial Incremental Changes for Updating[J].Acta Geodaetica et Cartographica Sinica,2012,41(1):108-114.(陳軍,林艷,劉萬增,等.面向更新的空間目標快照差分類與形式化描述[J].測繪學報,2012,41(1):108-114.)
[3] FAN Y T,YANG J Y,ZHU D H.An Event-based Change Detection Method of Cadastral Database Incremental Updating[J].Mathematical and Computer Modeling,2010,51(11-12):1343-1350.
[4] CHEN Jun,ZHOU Xiaoguang.Incremental Updating of Spatial Database Based on Topological Linkage,Taking Cadastral Database’s Updating as an Example[J].Acta Geodaetica et Cartographica Sinica,2008,37(3):322-337.(陳軍,周曉光.基于拓撲聯動的增量更新方法研究-以地籍數據庫為例[J].測繪學報,2008,37(3):322-337.)
[5] LIN Yan,LIU Wanzeng,WANG Yuhong.Spatial Changed Information Description Based on Updating Process[J].Geography and Geo-information Science,2011,27(4):24-27.(林艷,劉萬增,王育紅.一種基于更新過程的空間變化信息描述方法[J].地理與地理信息科學,2011,24(4):24-27.)
[6] COOPER A K,PELED A.Incremental Updating and Versioning[C]∥Proceedings of 20th International Cartographic Conference.Beijing:Sinomap Press,2001:2806-2809.
[7] HARDY P,WOODSFORD P.Incremental Updating Using the Gothic Versioned Object Database with the Hydrographic S57ENC and SOTF Spatial Object Transfer Formats[C]∥Proceedings of ICA/ISPRS Workshop on Incremental Updating and Versioning of Spatial Databases.Amsterdam:[s.n.],2000:1-13.
[8] HAKIMA K D.Updating Data in GIS:Towards a More Generic Approach[C]∥Proceedings of 20th International Cartographic Conference.Beijing:Sinomap Press,2001:1463-1471.
[9] ZHANG Feng,LIU Nan,LIU Renyi,et al.Research of Cadastral Data Modeling and Database Updating Based on Spatio-temperal Process[J].Acta Geodaetica et Cartographica Sinica,2010,39(3):303-309.(張豐,劉男,劉仁義,等.面向對象的地籍時空過程表達與數據更新模型研究[J].測繪學報,2010,39(3):303-309.)
[10] VAN OOSTEROM P.Maintaining Consistent Topology Including Historical Data in a Large Spatial Database[C]∥Proceedings of ACSM/ASPRS of Autocarto.Seattle:[s.n.],1997:327-336.
[11] ADBELMOTY A I,JOINES C B.Towards Maintaining Consistency of Spatial Databases[C]∥Proceedings of 6th International Conference on Information and Knowledge Management.Las Vegas:[s.n.],1997:293-300.
[12] HKIMA K D.Consistent Updating of Geographical Database as Emergent Property over Influence System[J].International Journal of Modeling Identification and Control,2008,3(1):58-68.
[13] LIU Wanzeng,Chen Jun.A Method to Confirm the Spatial Conflict in GIS Database for Circular Economy[J].Geoinformation Science,2007,9(1):78-83.(劉萬增,陳軍.循環經濟GIS數據庫空間沖突的確認方法研究[J].地球信息科學,2007,9(1):78-83.)
[14] CHEN J,LIU W,LI Z,et al.Detection of Spatial Conflict between Rivers and Contours in Digital Map Updating[J].International Journal of Geographical Information Science,2007,21(10):1093-1114.
[15] AN Xiaoya,SUN Qun,XIAO Qiang,et al.A Shape Multilevel Description Method and Application in Measuring Geometry Similarity of Multi-scale Spatial Data[J].Acta Geodaetica et Cartographica Sinica,2011,40(4):495-508.(安曉亞,孫群,肖強,等.一種形狀多級描述方法及在多尺度空間數據幾何相似性度量中的應用[J].測繪學報,2011,40(4):495-508.)
[16] MASUYAMA A.Methods for Detecting Apparent Differences between Spatial Tessellations at Different Time Points[J].International Journal of Geographical Informa-tion Science,2006,20(6):633-648.
[17] DENG M,LI Z L,CHEN X Y.Extended Hausdorff Distance for Spatial Objects in GIS[J].International Journal of Geographical Information Science,2007,21(4):459-475.
[18] CHEN Yumin,GONG Jianya,SHI Wenzhong.A Distance-based Matching Algorithm for Multi-scale Road Network[J].Acta Geodaetica et Cartographic Sinica,2007,36(1):84-90.(陳玉敏,龔健雅,史文中.多尺度道路網的距離匹配算法研究[J].測繪學報,2007,36[1]:84-90.)
[19] COBB M A,CHUNG M J.FOLEY III H,et al B.A Rule-based Approach for the Conflation of Attributed Vector Data[J].GeoInformatica,1998,2(1):7-35.
[20] DAI Xiangxi,ZHOU Wei,GAO Lei.The Algorithm and Realization of DLG Edge Match of Arbitrary Scope[J].Bulletin of Surveying and Mapping,2008,7:32-35.(戴相喜,周衛,高磊.DLG數據任意范圍接邊算法及實現[J].測繪通報,2008,7:32-35.)
[21] CAO Jian,LI Guozhong,XU Xiaobo,et al.Study on Edge Matching of Digital Topographic Maps on the Basis of ArcGIS Engine[J].Geomatic &Spatial Information Technology,2010,33(2):76-78.(曹鍵,李國忠,徐效波,等.基于ArcGIS Engine的多圖幅數字地形圖接邊算法研究[J].測繪與空間地理信息,2010,33(2):76-78.)
[22] ZHAO Xuesheng,Bai Jianjun,WANG Zhipeng.An Adaptive Visualized Model of the Global Terrain Based on QTM[J].Acta Geodaetica et Cartographica Sinica,2007,36(3):316-320.(趙學勝,白建軍,王志鵬.基于QTM的全球地形自適應可視化模型[J].測繪學報,2007,36(3):316-320.)
[23] ZHAO Xuesheng,WANG Lei,WANG Hongbin,et al.Modeling Methods and Basic Problems of Discrete Global Grids[J].Geography and Geo-information Science,2012,28(1):29-34.(趙學勝,王磊,王洪彬,等.全球離散格網的建模方法及基本問題[J].地理與地理信息科學,2012,28(1):29-34.)
[24] SERVIGNE S,UBEDA T,PURICELLI A,et al.A Methodology for Spatial Consistency Improvement of Geographic Databases[J].GeoInformatica,2000,4(1):7-34.
[25] VAN DER POORTEN P M,ZHOU S,JONES C B,et al.Topologically-consistent Map Generalization Procedures and Multi-scale Spatial Databases[C]∥Proceedings of the Second International Conference on Geographic Information Science.London:Springer-Verlag,2002:209-227.
An Adaptive Method for Incremental Updating of Vector Data
ZHANG Xinchang,GUO Taisheng TANG Tie
School of Geography and Planning,Sun Yat-Sen University,Guangzhou 510275,China
To maintain data consistency and eliminate the spatial conflicts brought by spatial database updating,an adaptive method for incremental vector data updating is proposed.Based on the matching of correspondent objects,a change-object detection and incremental updating method is discussed.Considering the constraint of spatial distance,semantic similarity and topology consistency,it is proposed a calculated method for edge matching evaluation.An adaptive edge matching strategy is also designed to maintain the consistency of spatial data.The rule-based detection and manipulation of spatial conflicts is also discussed.Topographical data are used to verify the practicality and efficiency of the method.
adaptive;incremental updating;data consistency;spatial conflict
ZHANG Xinchang(1957—),male,PhD,professor,PhD supervisor,majors in urban GIS.
ZHANG Xinchang,GUO Taisheng,TANG Tie.An Adaptive Method for Incremental Updating of Vector Data[J].Acta Geodaetica et Cartographica Sinica,2012,41(4):613-619.(張新長,郭泰圣,唐鐵.一種自適應的矢量數據增量更新方法研究[J].測繪學報,2012,41(4):613-619.)
P208
A
1001-1595(2012)04-0613-07
國家自然科學基金(40971216;41071246)
叢樹平)
2012-03-01
2012-05-17
張新長(1957—),男,博士,教授,博士生導師,研究方向為城市地理信息系統。
E-mail:eeszxc@mail.sysu.edu