羅國瑋,張新長,齊立新,郭泰圣

1.中山大學(xué)地理科學(xué)與規(guī)劃學(xué)院,廣東廣州 510275;2.廣西師范學(xué)院,廣西南寧 530001;3.廣東省城市化與地理環(huán)境空間模擬重點(diǎn)實(shí)驗(yàn)室,廣東廣州 510275;4.廣東省國土資源測繪院,廣東廣州 510500

矢量數(shù)據(jù)變化對象的快速定位與最優(yōu)組合匹配方法

羅國瑋1,2,張新長1,3,齊立新4,郭泰圣1

1.中山大學(xué)地理科學(xué)與規(guī)劃學(xué)院,廣東廣州 510275;2.廣西師范學(xué)院,廣西南寧 530001;3.廣東省城市化與地理環(huán)境空間模擬重點(diǎn)實(shí)驗(yàn)室,廣東廣州 510275;4.廣東省國土資源測繪院,廣東廣州 510500

要素變化信息對地物生命周期的記錄、時空數(shù)據(jù)庫的構(gòu)建、GlS數(shù)據(jù)庫的更新有重要意義。針對大數(shù)據(jù)量的變化信息發(fā)現(xiàn),本文采用基于格網(wǎng)劃分的方法,通過對空間特征與屬性特征匯總信息的對比,只對發(fā)生變化的格網(wǎng)進(jìn)行檢測,縮小了檢測范圍與空間查詢區(qū)域。為解決要素變化前后的匹配問題,提出一種最優(yōu)組合匹配法,通過對組合對象空間特征及語義特征的綜合比較,從候選要素中選取最佳匹配對象。試驗(yàn)證明,該方法能夠高效準(zhǔn)確地實(shí)現(xiàn)大數(shù)據(jù)量的矢量數(shù)據(jù)變化信息的探測,并能很好地解決非一對一的要素匹配問題。

變化信息;格網(wǎng)劃分;語義樹;最優(yōu)組合匹配

1 引 言

GIS矢量數(shù)據(jù)的要素變化信息對于記錄要素生命周期、時空數(shù)據(jù)庫的建立、GIS客戶數(shù)據(jù)庫更新[1]信息提取等方面有重要的意義。GIS矢量數(shù)據(jù)變化信息檢測與匹配是為了發(fā)現(xiàn)新舊數(shù)據(jù)中的變化信息,并建立變化要素在新舊數(shù)據(jù)中的匹配關(guān)系。國內(nèi)外學(xué)者從空間信息、屬性信息對新舊要素的變化特征進(jìn)行了研究,目前,對矢量要素變化檢測方法的研究多集中在數(shù)據(jù)更新信息識別的方面,文獻(xiàn)[2—3]運(yùn)用基于目標(biāo)匹配的方法提取變化信息。文獻(xiàn)[4]采用了基于事件的變化檢測,變化信息必須由事件驅(qū)動,對數(shù)據(jù)的完整性要求高且不具備通用性。在空間數(shù)據(jù)匹配研究中,研究主要以幾何特征(形狀[5-6]、距離[7]、方向[8]等)、拓?fù)涮卣鱗9-10]、屬性特征作為匹配依據(jù),在一對一的要素匹配中取得了良好的匹配效果。文獻(xiàn)[11—12]運(yùn)用了概率理論的匹配模型,通過融合多種匹配指標(biāo),計算候選目標(biāo)概率大小來確定匹配目標(biāo),但匹配計算量大且沒有完全解決多對多的匹配問題。為解決多對多的要素匹配問題,文獻(xiàn)[13]提出了增量凸包法,文獻(xiàn)[14]采用了組合匹配的方法。另外還有一些基于機(jī)器學(xué)習(xí)、神經(jīng)元網(wǎng)絡(luò)[15]等方面的匹配方法,由于其需要學(xué)習(xí)樣本的參與,使用起來比較復(fù)雜。以上這些匹配方法主要是針對制圖因素而非變化信息的匹配,文獻(xiàn)[2—3]中所進(jìn)行的變化對象匹配沒有給出多對多要素匹配的具體方案。在變化信息的匹配中,由于對象本身發(fā)生了幾何、拓?fù)?、屬性信息的改?采用常規(guī)的特征匹配指標(biāo)很難確定同名實(shí)體。

針對大數(shù)據(jù)量的變化檢測,為提高變化信息檢測的效率,本文采用基于格網(wǎng)劃分的變化信息快速定位方法。根據(jù)要素變化前后的空間關(guān)系及語義關(guān)系,對常規(guī)的匹配方法進(jìn)行了優(yōu)化,提出了一種最優(yōu)組合匹配方法,目的是提高空間數(shù)據(jù)變化前后對象的匹配精度,匹配結(jié)果能更好地為地物變化過程的跟蹤記錄及客戶GIS數(shù)據(jù)庫增量信息獲取提供數(shù)據(jù)服務(wù)。

2 變化類型與匹配關(guān)系

在GIS矢量數(shù)據(jù)中,要素的變化類型及匹配關(guān)系如表1所示。在現(xiàn)實(shí)中,地理要素會出現(xiàn)多種變化,如對比舊數(shù)據(jù),新數(shù)據(jù)中的同一要素發(fā)生了位移與幾何形變兩種變化,要想檢測出這些復(fù)合的要素變化非常困難,但是可以通過對變化前后要素的特征分析對比,確定它們的匹配關(guān)系。

3 基于格網(wǎng)劃分的變化信息快速定位

傳統(tǒng)的矢量數(shù)據(jù)的要素變化檢測方法是通過對要素進(jìn)行逐一比較來發(fā)現(xiàn)變化信息,需要進(jìn)行大量的空間查詢與屬性對比。本文提出一種基于格網(wǎng)劃分的變化信息快速定位方法,可以對新舊數(shù)據(jù)中的空間信息和屬性信息變化進(jìn)行快速而準(zhǔn)確的定位。具體過程如下:

(1)通過檢測確保新舊數(shù)據(jù)是同一比例尺及采用同一坐標(biāo)系,分別對新舊數(shù)據(jù)增加特征點(diǎn)坐標(biāo)屬性字段(Center_X、Center_Y)及存儲要素屬性匯總信息的屬性字段(TotalStr)。

表1 要素變化類型及匹配關(guān)系Tab.1 Feature change of type and matching relation

(2)分別對新舊數(shù)據(jù)進(jìn)行全局查詢,計算要素特征點(diǎn)坐標(biāo)、要素屬性匯總信息、并確定新舊數(shù)據(jù)對比的范圍(Xmin,Xmax,Ymin,Ymax)。特征點(diǎn)坐標(biāo)代表要素所處的位置,點(diǎn)要素直接取其坐標(biāo),線要素取其中點(diǎn),面要素取其質(zhì)心。要素屬性匯總信息是將要素屬性字段的字段值按字段名的字符串匹配排序進(jìn)行拼接,每個字段值之間用特殊符號分隔,如式(1)所示

(3)將變化檢測范圍按統(tǒng)一的寬度和高度劃分為m×n個規(guī)則的格網(wǎng)[16],m與n按式(2)計算,格網(wǎng)的寬度根據(jù)檢測范圍和要素總數(shù)由系統(tǒng)自動確定。格網(wǎng)的寬度記為Gwidth,高度記為Ghight。根據(jù)格網(wǎng)的總數(shù)定義數(shù)組變量來存儲格網(wǎng)中要素的匯總信息

(4)分別對新舊數(shù)據(jù)按特征點(diǎn)坐標(biāo)(Center_ X、Center_Y)進(jìn)行排序查詢,并按特征點(diǎn)坐標(biāo)將要素匹配到相應(yīng)的格網(wǎng)。格網(wǎng)編號與特征點(diǎn)坐標(biāo)匹配方法按式(3)計算,其中INT()為向下取整。按式(4)對格網(wǎng)內(nèi)要素的特征點(diǎn)坐標(biāo)(Center_X、Center_Y)、幾何值信息、屬性匯總信息按排序結(jié)果依次累加到相應(yīng)的網(wǎng)格變量。線要素和面要素的幾何值信息為要素的弧段長度,點(diǎn)要素不需要累加幾何值信息[17]

gcenx()、gceny()分別表示網(wǎng)格中要素特征點(diǎn)X坐標(biāo)及Y坐標(biāo)的和;glen()表示網(wǎng)格中要素的弧段長度和;gstr()表示網(wǎng)格中要素屬性值字符串拼接;gcount()為行號網(wǎng)格中要素個數(shù)。

(5)對新舊數(shù)據(jù)中編號相同網(wǎng)格中的特征點(diǎn)X坐標(biāo)、特征點(diǎn)Y坐標(biāo)、弧段長度、屬性值拼接字符串進(jìn)行對比

按式(5)計算網(wǎng)格中幾何特征的變化率, cx()為格網(wǎng)中要素特征點(diǎn)X坐標(biāo)和的變化率; cy()為格網(wǎng)中要素特征點(diǎn)y坐標(biāo)和的變化率; cl()為格網(wǎng)中弧段長度的變化率;N()與O()分別代表新舊數(shù)據(jù)。當(dāng)新舊數(shù)據(jù)中的對應(yīng)網(wǎng)格滿足以下條件之一,該網(wǎng)格中的要素存在變化情況,需要對網(wǎng)格內(nèi)的要素逐一作變化檢測(如圖1所示):

(1)要素特征點(diǎn)X坐標(biāo)和的變化率cx()或要素特征點(diǎn)Y坐標(biāo)和的變化率cy()大于給定閾值,閾值由測量點(diǎn)坐標(biāo)誤差許可范圍確定。

(2)要素弧段長度和變化率cl()大于給定閾值,閾值由邊長測量誤差許可范圍確定。

(3)要素數(shù)量不同。

(4)要素屬性值拼接字符串gstr不同。

變化要素的發(fā)現(xiàn)方法是在目標(biāo)數(shù)據(jù)中搜索與源數(shù)據(jù)的面積,弧段長度、方向、重心等空間特征與語義特征相同(差異小于閾值)的對象,當(dāng)搜索結(jié)果為空時說明要素發(fā)生了變化。在作新舊要素逐一變化對比時,需要通過大量的空間查詢,當(dāng)數(shù)據(jù)范圍較大時,花費(fèi)時間較多。由于本文已對查詢空間進(jìn)行了格網(wǎng)劃分,且要素屬性中記錄了該要素的重心坐標(biāo),進(jìn)行要素空間查詢時通過屬性過濾(Center_X＞＝Grid X左AND Center_X＜＝Grid X右AND Center_Y＞＝Grid Y下AND Center_Y＜＝Grid Y上),只對要素所在格網(wǎng)內(nèi)的要素進(jìn)行,大大縮小了查詢的范圍,提高了查詢的效率。

圖1 格網(wǎng)劃分Fig.1 Grid partition

4 變化要素最優(yōu)匹配

具有匹配關(guān)系說明新要素對舊要素有繼承性,繼承性可以通過相似度來量化。變化要素的匹配關(guān)系需要綜合考慮空間相似度及語義相似度。

4.1 空間相似度檢測

空間相似度檢測的目的是確定候選匹配要素,并與語義相似度結(jié)合來確定要素的匹配關(guān)系。下面分別介紹點(diǎn)、線、面的空間相似度檢測方法。

4.1.1 點(diǎn)要素

點(diǎn)要素的候選匹配要素通過緩沖區(qū)來搜索。以源數(shù)據(jù)中的點(diǎn)要素進(jìn)行半徑為r的緩沖區(qū)搜索, r的值根據(jù)不同的地物取最大可能位移距離。目標(biāo)數(shù)據(jù)中落入緩沖區(qū)的點(diǎn)作為候選匹配要素,候選要素與源要素的空間相似度按式(6)計算,d(A, B)為源數(shù)據(jù)中點(diǎn)要素A與目標(biāo)要素中點(diǎn)要素B的空間相似度,dis(A,B)為A與B的歐氏距離

4.1.2 線要素與面要素

目前,面要素及線要素的空間特征匹配方法有很多,面要素可通過對象的面積、位置、形狀、方向來匹配,線要素可通過長度、位置、方向、彎曲度等特征來匹配。由于是對變化了的對象進(jìn)行匹配,對象的單個空間特征都可能發(fā)生了改變,且變化前后的對象數(shù)目存在非一對一的關(guān)系,采用單個空間特征匹配難以保證準(zhǔn)確性[3]。重疊面積能夠綜合反映對象變化前后的位置與幾何相似性且計算方法簡單而快速,并有利于進(jìn)行對象間多對多的匹配;拓?fù)洳町惸軌蚍从硨ο笞兓昂蟮耐負(fù)潢P(guān)系相似性,因此本文采用了重疊面積比與拓?fù)洳町悂碛嬎憧臻g相似度:

(1)通過面積重疊度確定候選要素。線要素與面要素的匹配,設(shè)源數(shù)據(jù)中的要素(線要素的緩沖區(qū))為A,搜索目標(biāo)數(shù)據(jù)中與A相交的要素Bi,按式(7),當(dāng)A與Bi(線要素的緩沖區(qū))的相交面積與A與Bi中面積比較小的要素面積的比值S(A,B)大于給定閾值ф,Bi作為與A匹配的候選要素。為顧及非一對一的要素匹配,需要對候選要素進(jìn)行反向搜索,搜索源數(shù)據(jù)中與目標(biāo)數(shù)據(jù)中候選要素Bi相交的要素Ai。當(dāng)Bi與Ai(線要素的緩沖區(qū))的相交面積與Ai與Bi中面積比較小的要素面積的比值S(A,B)大于閾值, Ai作為與Bi匹配的候選要素。只要搜索到新的候選匹配要素,就以此候選要素作為源要素,反向進(jìn)行搜索,經(jīng)反復(fù)迭代,直到?jīng)]有搜索到新的候選匹配要素為止。閾值ф的設(shè)定是為避免將過多的將匹配可能性低的要素納入候選匹配對象,所取值根據(jù)地物類型來確定。

經(jīng)過反復(fù)雙向搜索,會得到集合A(a1,a2,…,am)與集合B(b1,b2,…,bn)的候選匹配要素。

(2)拓?fù)湎嗨贫扔嬎?。在多要素的匹配?變化前后要素組合之間的拓?fù)潢P(guān)系是空間相似性的重要因子,在其他因素相等的情況下,變化前后組合拓?fù)湫畔⒉町愋∑ヅ涞目赡苄源?例如相接的兩個對象比相離的兩個對象合并為一個對象的可能性大。本文定義候選要素之間的拓?fù)渚嚯x,相接或相交為1,相離為2,單要素距離為0。源候選要素之間與目標(biāo)候選要素之間的拓?fù)洳町悶閮山M要素拓?fù)渚嚯x的和。拓?fù)湎嗨贫炔捎檬?8)計算,其中td(A,B)為源要素與目標(biāo)要素的拓?fù)洳町?λ為可調(diào)節(jié)參數(shù),本文經(jīng)多次試驗(yàn),λ取1時相拓?fù)渌贫扔嬎憬Y(jié)果較理想

4.2 語義相似度檢測

源要素與目標(biāo)要素間的語義相似度反映了要素變化前后的語義繼承關(guān)系。語義相似度通過要素屬性值的相似度來確定,按文獻(xiàn)[18]提出的語義相似度評價模型計算。因?qū)ο蟮膶傩灾涤锌赡馨l(fā)生變化,屬性項(xiàng)中的特征碼及類別等變化可能性小的字段應(yīng)加大權(quán)重。

空間矢量數(shù)據(jù)的屬性字段類型大多為文本或數(shù)字,這兩類字段能較好地反映對象的語義特征。對一般字符型的屬性字段,本文采用字符串的編輯距離[19]來計算相似度。字符串編輯距離的相似度計算方法有時無法反映概念間的語義距離[20],字符串編輯距離很遠(yuǎn)但是表達(dá)的語義信息很相似的情況會經(jīng)常出現(xiàn),如“溝渠”與“河流”。針對要素類別的字段,本文采用了基于語義樹的計算方法,通過事先利用專家知識構(gòu)建好的領(lǐng)域本體[21]語義樹,來計算兩個概念間的語義距離。如圖2所示,要計算概念A(yù)與概念B之間的語義相似度參考按文獻(xiàn)[22]提出的語義相似度計算模型,按式(9)、式(10)進(jìn)行計算。

圖2 層次語義樹Fig.2 Hierarchical semantic tree

式(9)中maxdepth為語義樹的最大深度;式(10)中com(A,B)為節(jié)點(diǎn)A與節(jié)點(diǎn)B在語義樹中的最近共同祖先;式(10)中dis(A,com(A, B))與dis(B,com(A,B))分別計算A、B到最近共同祖先的有向邊距離。

對于數(shù)值型字段,本文認(rèn)為數(shù)值在一定變化

閾值內(nèi)存在相似性,變化范圍超出閾值時相似度為0。數(shù)值型字段相似度計算如式(11)所示。v為變化前的數(shù)值,v′為變化后的數(shù)值,ε為變化閾值,且ε＜v

4.3 匹配策略

本文采用空間相似度與語義相似度結(jié)合來計算對象的相似度,計算模型如式(12)所示

點(diǎn)要素直接按公式進(jìn)行源要素與目標(biāo)要素一對一相似度計算,線要素與面要素變化匹配涉及非一對一的匹配,A、B分別代表新舊數(shù)據(jù)候選匹配對象的集合。r(A,B)對點(diǎn)要素為距離相似度,對線與面要素為面積重疊度;st(A,B)代表候選匹配要素的拓?fù)湎嗨贫?sem(A,B)為語義相似度;ω1、ω2、ω3為可調(diào)節(jié)權(quán)重值,ω1＋ω2＋ω3＝1,點(diǎn)要素取ω2＝0。針對變化信息可能存在一對多、多對一或多對多匹配,本文提出了最優(yōu)組合匹配法。從候選匹配要素中選取相似度最大的候選匹配組合,如選取的候選匹配組合的相似度大于閾值,表明這對組合為最終的匹配結(jié)果。具體算法:設(shè)A(a1,a2,…,am)、B(b1,b2,…,bn)為候選匹配要素的集合,根據(jù)排列組合公式集合A與集合B分別有2m－1、2n－1項(xiàng)候選組合。集合中組合的生成方法是依次將十進(jìn)制數(shù)1至2m－1轉(zhuǎn)換成二進(jìn)制數(shù),判斷該二進(jìn)制數(shù)的值,從右往左判斷不為0的項(xiàng)為集合中選取的要素的下標(biāo),如110表示要生成的組合為(a3,a2)。源要素組合與目標(biāo)要素組合的面積重疊度按式(13)計算

式中,PA、PB對于面要素分別代表源要素組合與目標(biāo)要素組合,對于線要素代表源要素緩沖區(qū)組合與目標(biāo)要素緩沖區(qū)組合。PA、PB為組合中各元素的并集。

源要素組合與目標(biāo)要素組合的拓?fù)湎嗨贫劝词?8)計算,如組合中的要素個數(shù)大于2,該組合的拓?fù)渚嚯x取組合內(nèi)兩兩要素之間拓?fù)渚嚯x的最大值。

源要素組合與目標(biāo)要素組合的語義相似度計算方法如下:如兩個組合的元素數(shù)量均為1,按本文4.2節(jié)的方法求取集合的語義相似度。如組合中元素不為1,按以下方法計算:對可累加數(shù)值型字段分別對兩個組合中該字段的值的求和,對非累加數(shù)值型字段取兩個組合中該字段的平均值,再用式(11)計算相似度;對字符型字段,根據(jù)字段性質(zhì)采用字符編輯距離法或?qū)哟握Z義樹法求出兩兩相應(yīng)字段值的相似度,再計算字段相似度的平均值;求出兩組合各屬性字段的相似性之后,再按語義相似度評價模型[18]計算源要素組合與目標(biāo)要素組合的語義相似度。

當(dāng)候選要素較多時,生成的組合較多,計算量也相應(yīng)增大。為減少計算時間,本文對不存在相交或包含關(guān)系的組合對不再進(jìn)行計算,直接將相似度賦為0。在匹配過程中,需要進(jìn)行大量的空間查詢操作,對點(diǎn)要素及面要素的匹配,將空間搜索范圍限制在與源要素所在格網(wǎng)及相鄰的格網(wǎng)內(nèi),以提高匹配的速度。

完成源候選要素與目標(biāo)候選要素生成的所有組合的相似度計算之后,進(jìn)行匹配要素的最終確定。方法如下:①將相似度大于閾值的組合對存入隊列;②從隊列中選取相似度最大的組合對作為相匹配要素記錄存入匹配列表,同時將這對組合從隊列中刪除,并將隊列中含有最大相似度組合對中的要素的其他組合對從隊列中刪除;③重復(fù)步驟2,直到隊列中的所有組合對被刪除。匹配列表為匹配的最終結(jié)果,根據(jù)列表中每一條匹配記錄的要素數(shù)目,可識別匹配關(guān)系1∶0、0∶1、1∶1、1∶n、m∶1、m∶n。

5 試驗(yàn)案例

5.1 變化信息快速定位試驗(yàn)

本文采用Visual Studio 2010結(jié)合ArcGIS Engine 10開發(fā)了GIS矢量數(shù)據(jù)變化檢測與匹配原型系統(tǒng),分別選取不同時期的大比例尺地形圖中的多組點(diǎn)、線、面要素運(yùn)用全局逐個檢測法和格網(wǎng)法進(jìn)行了試驗(yàn),要素的變化形式包括新增、消失、位移、幾何形變、合并、分裂、聚合、屬性變化等,如圖3所示。表2列出了格網(wǎng)劃分法與全局逐個檢測的效率對比信息。試驗(yàn)證明,雖然在網(wǎng)格信息初始化、要素特征點(diǎn)計算等方面花費(fèi)一些時間,但格網(wǎng)劃分法只對變化了的區(qū)域進(jìn)行檢測,可以大大減少檢測的時間,檢測要素越多加速效果越明顯,且該方法的效率不會受到變化要素分布區(qū)域的影響,只與要素的變化率有關(guān),要素變化率越低,加速比越高。本文還采用了不同的格網(wǎng)寬度做了試驗(yàn),結(jié)果顯示格網(wǎng)寬度在一定范圍內(nèi)變化對加速效果影響不大。

圖3 GIS數(shù)據(jù)變化檢測與匹配原型系統(tǒng)Fig.3 GIS data change detection and matching prototype system

表2 格網(wǎng)劃分法與全局逐個檢測的檢測效率對比Tab.2 Comparison of efficiency grid partition method and traversal method

在實(shí)際運(yùn)用中,可能出現(xiàn)要素特征點(diǎn)正好落在格網(wǎng)邊界上,解決的方法是統(tǒng)一將格網(wǎng)左右邊界上的特征點(diǎn)統(tǒng)一歸左邊網(wǎng)格,上下格網(wǎng)邊界上的特征點(diǎn)統(tǒng)一歸上邊網(wǎng)格。

5.2 最優(yōu)組合匹配試驗(yàn)

本文利用變化對象快速定位試驗(yàn)中檢測出的要素進(jìn)行匹配試驗(yàn)。運(yùn)用式(13)計算匹配相似度時,權(quán)重ω1、ω2、ω3根據(jù)數(shù)據(jù)源的不同,采用對已匹配好的樣本進(jìn)行特征分析結(jié)合專家經(jīng)驗(yàn)來設(shè)定,試驗(yàn)中點(diǎn)要素分別取(0.7,0,0.3),線要素與面要素分別取(0.6,0.1,0.3)。試驗(yàn)結(jié)果顯示(表3),對比常規(guī)的組合方法[13-14],最優(yōu)組合匹配法的匹配精度有所提高。應(yīng)用實(shí)例如表4所示,最優(yōu)組合匹配法在一對多、多對一及多對多的匹配中具有明顯的優(yōu)勢。但在要素發(fā)生了較大位移時,系統(tǒng)沒有將其納入候選要素,會導(dǎo)致誤匹配。

表3 匹配試驗(yàn)結(jié)果對比Tab.3 Comparison of the matching experiment

表4 應(yīng)用實(shí)例Tab.4 Examples of application

6 結(jié) 論

GIS矢量數(shù)據(jù)的變化信息的發(fā)現(xiàn)與匹配能為地物生命周期的記錄、時空數(shù)據(jù)獲取及客戶空間數(shù)據(jù)更新信息的發(fā)布提供服務(wù)。本文對空間矢量數(shù)據(jù)的變化對象的快速定位與匹配進(jìn)行了研究,經(jīng)過試驗(yàn),得出了以下結(jié)論:①基于格網(wǎng)劃分的變化信息快速定位法大大縮小了檢測范圍,極大地提高了變化信息的檢測速度,且不受變化對象分布范圍的影響,能夠準(zhǔn)確高效地檢測出矢量數(shù)據(jù)空間信息及屬性信息的變化;②最優(yōu)組合匹配法通過對變化對象空間信息與語義信息的綜合對比,從候選要素中找出最優(yōu)組合,提高了匹配的準(zhǔn)確度,能更好地解決多對多的變化要素匹配問題。本文方法的不足之處在于匹配的準(zhǔn)確度對相似度因子權(quán)重及匹配閾值的設(shè)置有較大的依賴性。這是下一步研究需要解決的問題。

[1] JIAN C L,H U ANG M L.Research on Geographic Information Database Incremental Updating Method [C]∥Proceedings of International Conference on Audio Language and Image Processing.Shanghai:[s.n.],2010: 985-989.

[2] WU Jianhua,FU Zhongliang.Methodology of Feature Change Detection and Matching in Data Updating[J].Computer Applications,2008,28(6):1612-1615.(吳建華,付仲良.數(shù)據(jù)更新中要素變化檢測與匹配方法[J].計算機(jī)應(yīng)用, 2008,28(6):1612-1615.)

[3] YING Shen,LI Lin,LIU Wanzeng,et al.Change-only Updating Based on Object Matching in Version Databases [J].Geomatics and Information Science of Wuhan University,2009,34(6):752-755.(應(yīng)申,李霖,劉萬增,等.版本數(shù)據(jù)庫中基于目標(biāo)匹配的變化信息提取與數(shù)據(jù)更新[J].武漢大學(xué)學(xué)報:信息科學(xué)版,2009,34(6):752-755.)

[4] ZHANG Feng,LIU Nan,LIU Renyi,et al.Research of Cadastral Data Modeling and Database Updating Based on Spatio-temporal Process[J].Acta Geodaetica et Cartographica Sinica,2010,39(3):303-309.(張豐,劉南,劉仁義,等.面向?qū)ο蟮牡丶畷r空過程表達(dá)與數(shù)據(jù)更新模型研究[J].測繪學(xué)報,2010,39(3):303-309.

[5] AI T H,CHENG X,LIU P,et al.A Shape Analysis and Template Matching of Building Features by the Fourier Transform Method[J].Computers,Environment and Urban Systems,2013,41:219-233.

[6] KIELER B,HUANG W,HAUNERT J H,et al.Matching River Datasets of Different Scales[M].Advances in GIScience.Berlin:Springer,2009:135-154.

[7] 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.

[8] DENG M,LI Z L.A Statistical Model for Directional Relations between Spatial Objects[J].Geoinformatica,2008,12: 193-217.

[9] PAN LI,WANG Hua.Automatic Recognition of Change Types of Residential Areas Using Topology Relations Model[J].Geomatics and Information Science of Wuhan University,2009,34(3):301-303.(潘勵,王華.利用拓?fù)潢P(guān)系模型自動檢測居民地的變化類型[J].武漢大學(xué)學(xué)報:信息科學(xué)版,2009,34(3):301-303.)

[10] DENG M,CHENG T,CHEN X Y,et al.Multi-level Topological Relations between Spatial Regions Based upon Topological Invariants[J].Geoinformatica,2007,11:239-267.[11] TONG Xiaohua,DENG Susu,SHI Wenzhong.A Probabilistic Theory-based Matching Method[J].Acta Geodaetica et Cartographica Sinica,2007,36(2):210-217.(童小華,鄧愫愫,史文中.基于概率的地圖實(shí)體匹配方法[J].測繪學(xué)報,2007,36(2):210-217.)

[12] WALTER V,FRITSCH D.Matching Spatial Data Sets: A Statistical Approach[J].International Journal of Geographical Information Systems,1999,13(5):445-473.

[13] ZHANG Liping,GUO Qingsheng,SUN Yan.The Method of Matching Residential Features in Topographic Maps at Neighboring Scales[J].Geomatics and Information Science of Wuhan University,2008,33(6):604-607.(章莉萍,郭慶勝,孫艷.相鄰比例尺地形圖之間居民地要素匹配方法研究[J].武漢大學(xué)學(xué)報:信息科學(xué)版,2008,33(6):604-607.)

[14] WU Jianhua.Entity Matching Methods Based on Combining Multi-similarity-characteristics Considering Environment Similarity[J].Geography and Geo-Information Science, 2010,26(4):1-6.(吳建華.顧及環(huán)境相似的多特征組合實(shí)體匹配方法[J].地理與地理信息科學(xué),2010,26(4):1-6.)

[15] XU Junkui,WU Fang,WEI Huifeng.Areal SettlementsMatching Algorithm Based on Artificial Neural Network Technique[J].Journal of Geomatics Science and Technology, 2013,30(3):293-298.(許俊奎,武芳,魏慧峰.人工神經(jīng)網(wǎng)絡(luò)在居民地面狀匹配中的應(yīng)用[J].測繪科學(xué)技術(shù)學(xué)報, 2013,30(3):293-298.)

[16] CHEN Yumin,GONG Jianya,SHI Wenzhong.A Distancebased Matching Algorithm for Multi-scale Road Networks [J].Acta Geodaetica et Cartographica Sinica,2007,36 (1):84-90.(陳玉敏,龔健雅,史文中.多尺度道路網(wǎng)的距離匹配算法研究[J].測繪學(xué)報,2007,36(1):84-90.)

[17] GUO Taisheng,ZHANG Xinchang,LIANG Zhiyu.Research on Change Information Recongition Method of Vector Data Based on Neural Network Decision Tree[J].Acta Geodaetica et Cartographica Sinica,2013,42(6):937-944.(郭泰圣,張新長,梁志宇.神經(jīng)網(wǎng)絡(luò)決策樹的矢量數(shù)據(jù)變化信息快速識別方法[J].測繪學(xué)報,2013,42(6): 937-944.)

[18] COBB M A,CHUNG M J,FOLEY I H,et al.A Rule-based Approach for the Conation of Attributed Vector Data[J].GeoInformatica,1998,2(1):7-35.

[19] DIAO Xingchun,TAN Mingchao,CAO Jianjun.New Method of Character String Similarity Computing Based on Fusing Multiple Edit Distances[J].Application Research of Computers,2010,27(12):4523-4525.(刁興春,譚明超,曹建軍.一種融合多種編輯距離的字符串相似度計算方法[J].計算機(jī)應(yīng)用研究,2010,27(12):4523-4525.)

[20] HASTINGS J T.Automated Conflation of Digital Gazetteer Data[J].International Journal of Geographical Information Science,2008,22(10):1109-1127.

[21] LOPEZ-PELLICER F J,LACASTA J,FLORCZYK A,et al.An Ontology for the Representation of Spatiotemporal Jurisdictional Domains in Information Retrieval Systems [J].International Journal of Geographical Information Science,2012,26(4):579-597.

[22] LEACOCK C C.Milling in a Sparse Training Space for Word Sense Identification[EB/OL].[2009-02-25].http:∥arxiv.org/PS_cache/cmp-lg/pdf/9511/9511007v1.pdf.

(責(zé)任編輯:叢樹平)

The Fast Positioning and Optimal Combination Matching Method of Change Vector Object

LUO Guowei1,2,ZHANG Xingchang1,3,Ql Lixin4,GUO Taisheng1
1.School of Geography and Planning,Sun Yat-sen University,Guangzhou 510275,China;2.Guangxi Teachers Education University,Nanning 530001,China;3.Guangdong Key Laboratory for Urbanization and Geo-simulation, Guangzhou 510275,China;4.lnstitute of Surverying and Mapping of Land and Resources Department of Guangdong Province,Guangzhou 510500,China

The change-only information is important to the recording of object life cycle,the establishment of spatial-temporal database and the updating of GlS database.To solve the problem of low efficiency of traditional method in change detection when the data volume is large,we proposed a highly efficient method of change detection based on the grid-partitioning of data and the comparison of synthesis of spatial and attribute information.This method only detects the changed grid to reduce the detection region.ln order to solve the matching problem of old features and new features,we propose a method named optimal combination-matching method.The method selects the optimally matched features through the comparison of the characteristic of spatial information and semantic information.The method’s high efficiency and accuracy in change detection of large volume of spatial data and matching of changed features is validated by experiment.

change-only information;grid-partitioning;semantic tree;optimal combination-matching

LUO Guowei(1979—),male,PhD candidate,senior engineer,majors in spatial data updating and fusion.

ZHANG Xinchang

P208

A

1001-1595(2014)12-1285-08

國家自然科學(xué)基金重點(diǎn)項(xiàng)目(41431178);國家863計劃(2013AA122302);高等學(xué)校博士點(diǎn)專項(xiàng)基金(20120171110030)

2014-01-17

羅國瑋(1979—),男,博士生,高級工程師,研究方向?yàn)榭臻g數(shù)據(jù)更新與融合。

E-mail:bestlgw＠163.com

張新長

E-mail:eeszxc＠m(xù)ail.sysu.edu.cn

LUO Guowei,ZHANG Xingchang,QI Lixin,et al.The Fast Positioning and Optimal Combination Method of Change Vector Object[J].Acta Geodaetica et Cartographica Sinica,2014,43(12):1285-1292.(羅國瑋,張新長,齊立新,等.矢量數(shù)據(jù)變化對象的快速定位與最優(yōu)組合匹配方法[J].測繪學(xué)報,2014,43(12):1285-1292.)

10.13485/j.cnki.11-2089.2014.0191

修回日期:2014-06-22