劉 闖，錢海忠，王 驍，何海威，陳競男

信息工程大學地理空間信息學院，河南 鄭州 450052

?

顧及上下級空間關系相似性的道路網(wǎng)聯(lián)動匹配方法

劉 闖，錢海忠，王 驍，何海威，陳競男

信息工程大學地理空間信息學院，河南 鄭州 450052

現(xiàn)有道路網(wǎng)匹配方法中，大多利用道路自身結點和弧段特征進行匹配，而較少注意道路鄰域要素在道路網(wǎng)匹配中的重要定位參考作用，從而影響匹配效率和正確率的進一步提高。針對上述問題，本文提出了一種顧及上下級空間關系相似性的道路網(wǎng)聯(lián)動匹配方法，即模仿人在讀圖時通過特征地物和空間關聯(lián)尋找目標地物的思維過程，將匹配看作是一種特征目標尋找、信息關聯(lián)傳遞的推理過程。首先，運用Stroke技術將復雜道路網(wǎng)進行等級劃分。其次，通過道路骨架關聯(lián)關系樹構建道路網(wǎng)聯(lián)動匹配模型。最后，選取高等級骨干道路作為起始特征對象，計算道路間的上下級空間關系相似性，逐級迭代使匹配信息在道路網(wǎng)聯(lián)動匹配模型中傳遞，從而得到匹配結果。試驗表明，本文算法縮小了待匹配數(shù)據(jù)的搜索范圍，能夠有效提高匹配正確率和效率，尤其在數(shù)據(jù)位移較大、存在非系統(tǒng)性幾何位置偏差的情況下優(yōu)勢明顯。

聯(lián)動匹配；空間關系；Stroke技術；信息傳遞

隨著我國城市化進程的加快，城市地物發(fā)生了翻天覆地的變化，特別是道路要素，其變化周期越來越短，變化程度越來越大，使得城市道路數(shù)據(jù)面臨著嚴峻的更新任務。道路網(wǎng)更新的目的是對道路網(wǎng)中的變化信息進行識別與修改，而同名實體匹配是解決這一問題的關鍵技術。其基本原理是通過一系列相似度指標識別出不同來源地圖數(shù)據(jù)庫中表達現(xiàn)實世界同一地物的地圖要素的過程[1]。同名實體匹配是后續(xù)數(shù)據(jù)集成、融合以及更新的基礎，具有重要應用意義。據(jù)此，國內外研究學者圍繞同名道路匹配進行了大量研究。

道路匹配屬于線要素匹配，目前國內外學者對線要素匹配方法研究大致分為以下3類：①利用緩沖區(qū)增長方法進行匹配[2-4]，簡單易行，是線要素匹配的常用方法；②利用曲線自身幾何特征進行匹配[5-11]，主要是通過道路弧段的距離測度直接對道路弧段匹配，或者根據(jù)道路節(jié)點之間距離遠近、拓撲結構相似性等對道路節(jié)點匹配，然后節(jié)點所對應道路弧段匹配；③綜合運用多個評價指標，從整體到局部的策略匹配[12-16]，主要運用道路網(wǎng)自身的空間結構特征進行匹配。

上述匹配方法大多從道路自身節(jié)點和弧段特征出發(fā)進行匹配，而對于道路鄰域要素相似性的研究相對較少。而在實際匹配過程中，匹配雙方數(shù)據(jù)間可能存在較大的幾何位置偏差。如圖1所示，若是從道路自身節(jié)點和弧段特征進行匹配，則A2和B1匹配的可能性比較大，而實際上A1和B1才是一對同名實體。由此可見，若在匹配過程中顧及A1和B1的周邊道路空間分布情況，可容易得出正確匹配結果。本文基于該思路，模仿人在讀圖時通過特征地物和空間關聯(lián)尋找目標地物的思維過程，提出一種道路網(wǎng)聯(lián)動匹配方法。該方法的優(yōu)勢在于有效地克服了非系統(tǒng)性位移誤差所造成匹配錯誤，提高了匹配正確率，避免了道路逐個匹配的策略，提高了匹配效率，在數(shù)據(jù)位移較大、存在位置偏差的情況下具有一定優(yōu)勢。

圖1 誤匹配示例Fig.1 Example of error matching

1 構建道路網(wǎng)聯(lián)動匹配模型

所謂聯(lián)動匹配，即通過一個要素匹配帶動另一個要素匹配，當一個要素匹配結束時，與該要素關聯(lián)的其他要素根據(jù)關聯(lián)關系，也隨即完成匹配。它的核心思想是把匹配看成一種特征目標尋找、信息關聯(lián)傳遞的推理過程。所以聯(lián)動匹配實現(xiàn)的關鍵就是道路與道路之間關聯(lián)關系的構建，其實質就是實現(xiàn)匹配信息在道路網(wǎng)間傳遞。

下面研究如何構建道路網(wǎng)聯(lián)動匹配模型。值得注意的是，由于道路網(wǎng)瑣碎的離散弧段使得道路空間關系量化表達變得復雜。本文借鑒Stroke技術[17-18]平滑連續(xù)的特點，對道路網(wǎng)進行重新組織，使道路的整體連貫性得以保持，更加符合人類的認知習慣。

1.1 道路網(wǎng)Stroke提取及等級劃分

在生成道路Stroke過程中，對數(shù)據(jù)進行拓撲處理，去除數(shù)據(jù)中存在的偽結點。如圖2所示，對拓撲處理后的道路網(wǎng)數(shù)據(jù)構建Stroke，首先選擇一條弧段作為種子弧段，依次遍歷與該種子弧段首、末結點關聯(lián)的其他弧段，依據(jù)道路網(wǎng)Stroke的判斷標準，判斷是否存在與該種子弧段同屬一條Stroke的弧段。若存在，則以該弧段作為種子弧段繼續(xù)尋找其他弧段，依次不斷循環(huán)，直至找不到滿足Stroke構建條件的弧段，由此生成了一條道路。通過對現(xiàn)有Stroke生成算法的分析[19-21]，本文依據(jù)屬性一致性、方向一致性和趨勢一致性這3種判斷指標，作為關聯(lián)弧段是否同屬一條Stroke的判斷標準。

圖2 道路Stroke構建原理Fig.2 Theory of road Stroke construction

為了構建具有明顯層次結構特征的聯(lián)動匹配模型，需要對道路Stroke進行等級劃分。在道路網(wǎng)的建設和規(guī)劃時，往往按照道路的通行能力或者是用途差異將道路分為不同的等級。在矢量地圖中，當?shù)缆返膶傩孕畔⒈容^完整時，一般按照道路等級將道路分為高速公路、省道、縣道、鄉(xiāng)道等，在城市中分為主要道路和次要道路。但當?shù)缆返膶傩孕畔⒉煌暾麜r，只能依靠道路的幾何特征和拓撲特征來區(qū)分道路等級。

借鑒已有對道路數(shù)據(jù)等級評價的方法[22-24]，本文采取長度和通達性兩個指標對道路進行量化等級劃分。道路長度在獲取上相對比較容易，顯然道路越長，表明道路服務的區(qū)域就越大，重要性越高。道路通達性是指通過道路網(wǎng)中道路之間的相互連通關系實現(xiàn)道路網(wǎng)所在區(qū)域兩點之間的通達。該指標通常用道路網(wǎng)絡中心度來描述，道路的網(wǎng)絡中心度越大，即所處的中心地位越高，說明該道路的通達性越好，從而發(fā)揮的作用越大。圖3為某城市道路網(wǎng)數(shù)據(jù)，對其提取Stroke，并按照長度和通達性兩種指標，進行等級評價，共分為10級道路，即選取重要性前10%的道路作為10級道路(最高級)，選取重要性前10%～20%的道路作為9級道路，依次類推，如圖3(c)所示，加粗實線為各等級道路示意。

圖3 城市道路網(wǎng)Stroke提取和等級劃分結果Fig.3 Results of urban road network Stroke extraction and grade classification

1.2 道路和道路骨架關聯(lián)樹構建

利用Stroke技術對整個城市道路網(wǎng)進行分類分級后，高等級的道路Stroke，如同一棵樹的主干和粗枝，可反映出整個城市的大致形態(tài)結構，因此，高等級道路Stroke，也即主要道路，是整個城市的骨架，而那些較低等級的道路Stroke，就像樹的細枝和樹葉。如此，對整個城市道路網(wǎng)有了層次化的認知，將這種層次化認知模型映射到一個樹狀結構中，稱之為骨架關聯(lián)樹，如圖4所示。在這種層次化認知模型中，每條高等級的道路Stroke可能與多條較低等級的道路Stroke具有關聯(lián)關系，每條較低等級的道路Stroke可能與更多的更低等級的道路Stroke具有關聯(lián)關系，因此這種骨架關聯(lián)樹具備以下特性：

(1) 相同等級道路Stroke之間是網(wǎng)狀關系，不同等級道路Stroke之間形成層次結構關系。

(2) 一條高等級道路Stroke可能具備多個子節(jié)點。

(3) 一條低等級道路Stroke可能具備多個根節(jié)點。

圖4 道路網(wǎng)骨架關聯(lián)樹Fig.4 Road network skeleton relation tree

骨架關聯(lián)樹構建的關鍵問題是如何找到根節(jié)點。本文提出一種基于樹狀結構索引的骨架關聯(lián)樹構建方法。對于整個城市道路網(wǎng)而言，選取最高等級的一條道路Stroke作為該骨架關聯(lián)樹的根節(jié)點，將與該道路相交或相鄰的較低等級的道路Stroke作為子節(jié)點，之后，對每個子節(jié)點按照同樣的方法找到各自的子節(jié)點，經(jīng)過這樣的索引過程，便構成了一條完整的骨架關聯(lián)樹。為了便于對道路進行存儲和讀取，本文將數(shù)據(jù)源1中道路Stroke命名為Sn-i，其中n代表道路等級，i代表該條道路在該等級道路層中的編號。同理，數(shù)據(jù)源2中的道路Stroke命名為Pm-j。

1.3 道路和道路聯(lián)動匹配模型構建

在圖1所示的示例中，人眼之所以能夠判斷出道路A1和B1是一對同名實體，是因為人腦對兩個目標信息的獲取并非是獨立的，而是通過對兩者的關聯(lián)信息比較進行的。本文正是基于此，將人腦的這種感知能力通過結構化的方式表示出來，并進行相互關聯(lián)分析，在模擬人腦這種綜合信息的能力的基礎上，構建道路網(wǎng)聯(lián)動匹配模型，為道路網(wǎng)匹配提供新的思路。

聯(lián)動匹配模型的構建原理如下，通過道路網(wǎng)骨架關聯(lián)樹，可以尋找多源空間數(shù)據(jù)在層次結構上的整體性和差異性。如圖5所示，歸納、分析數(shù)據(jù)源A與數(shù)據(jù)源B中每一條高等級道路Stroke和與其具有關聯(lián)關系的低等級Stroke在空間數(shù)據(jù)中的分布狀態(tài)，通過尋找兩數(shù)據(jù)源結構相似的骨架關聯(lián)樹來構建道路網(wǎng)聯(lián)動匹配模型，實現(xiàn)道路聯(lián)動匹配的目的。

這種關聯(lián)關系的構建可以通過圖6的示意性說明較好地闡釋其原理。如圖6(a)和圖6(b)所示，選取突出的骨干道路如S10-0和P10-0作為起始匹配對象，對同一區(qū)域的數(shù)據(jù)源A和數(shù)據(jù)源B分

別以S10-0和P10-0為起點建立各自的道路網(wǎng)骨架關聯(lián)樹，使其具有樹狀結構關系；對兩個骨架關聯(lián)樹進行結構相似性比對，找出兩數(shù)據(jù)源道路中結構相似的部分，并將這些結構相似的道路按照等級由高到低的順序排列，如圖6(c)所示；這些結構相似道路即可構成道路網(wǎng)聯(lián)動匹配模型，如圖6(d)。其余的不具有結構相似性的部分則是新增或消失的部分，可以在數(shù)據(jù)更新過程中直接對數(shù)據(jù)集進行增加或刪除等操作。

圖5 道路網(wǎng)聯(lián)動匹配示例Fig.5 Example of road network linkage matching

圖6 道路網(wǎng)聯(lián)動匹配模型構建原理Fig.6 Construction principle of road network linkage matching model

2 道路網(wǎng)上下級空間關系相似性計算

如圖7所示，在構建道路網(wǎng)聯(lián)動匹配模型時，一條高等級Stroke可能與多條低等級Stroke相交或相鄰，這不利于匹配信息準確快速的傳遞，甚至會影響匹配效率。因此引入上下級空間關系相似性對匹配過程進行約束，以突出的骨干道路作為重要定位參考，通過待匹配道路相對于骨干道路在空間關系上的有序性和相似性來引導匹配進程，從而實現(xiàn)道路網(wǎng)聯(lián)動匹配。

圖7 骨架關聯(lián)樹多節(jié)點示例Fig.7 Example of skeleton relation tree with multiple nodes

當然，本文所說的空間關系是一條道路相對于骨干道路的空間關系(上下級拓撲關系、上下級方向關系、上下級距離關系等)，這些關系雖然表達上不嚴格一致，但也絕不會違背制圖規(guī)則。由于在構建道路網(wǎng)Stroke時，將同一等級的道路連接為一條Stroke，而這些道路有可能名稱不同，因此很難用語義特征來判斷相似性情況，故本文中暫不考慮語義相似性。

2.1 道路和道路上下級空間關系相似性計算

2.1.1 道路和道路上下級拓撲相似性計算

線要素之間的拓撲關系可以粗略的歸納為相鄰(部分重合)、重合、相交(相接)和相離4種關系。參考傳統(tǒng)的拓撲關系概念鄰域圖[25-26]，如圖8所示，因為在道路網(wǎng)中相交和相鄰的道路關聯(lián)相似性比較大，故本文將相交和相鄰視為鄰域內關系，本文所指空間關系相似性主要就是計算鄰域內道路間的空間關系相似性。通常將目標道路的鄰域道路數(shù)量作為其拓撲總數(shù)，根據(jù)骨架關聯(lián)樹的特點，將拓撲相似性分為上級拓撲相似性和下級拓撲相似性兩部分，即以一對同名道路的上一等級鄰域道路數(shù)量作為上級拓撲總數(shù)，以該條道路的下一等級鄰域道路數(shù)量作為下級拓撲總數(shù)。如圖9所示，道路S8-1的道路等級為8，與S8-1相交或相鄰的9級道路數(shù)量為2，則該條道路的上級拓撲總數(shù)為2；與S8-1相交或相鄰的7級道路數(shù)量為4，那么該條道路的下級拓撲總數(shù)為6。

圖8 線要素間拓撲關系鄰域圖Fig.8 The neighborhood figure of topological relationships between line elements

圖9 線要素拓撲總數(shù)計算示例Fig.9 Total number computation of line elements topology

按照這種計算方法，兩組數(shù)據(jù)源之間的上下級拓撲相似性可表示為

(1)

2.1.2 道路和道路上下級方向相似性計算

方向特征是線要素匹配中的重要判斷指標。為了更準確地確定道路間關聯(lián)關系，本文采用目標道路自身方向和目標道路鄰域道路群組方向相結合的方法進行道路方向相似性計算。

2.1.2.1 目標道路自身方向相似性計算

Stroke的方向分為整體方向和局部方向，整體方向是指用Stroke首末結點的連線相對于水平軸旋轉的角度來近似描述，局部方向可用組成該條Stroke的小弧段的方位角表示?，F(xiàn)實中，多源數(shù)據(jù)由于來源不同，采集方法不同，相互之間在局部細節(jié)形態(tài)上可能差異較大，當把道路弧段連接成Stroke時，原來的同名道路之間都會存在或多或少的位置偏差，這給Stroke方向計算帶來了困難。如圖10所示，兩幅不同的數(shù)據(jù)集中同名Stroke分別為S7-1和P7-1，兩者的整體方向分別為θ1和θ2，經(jīng)過計算，得到θ1=122.78°和θ2=136.67°，兩者的差異度為13.89°。這是因為組成S7-1和P7-1的道路弧段個數(shù)不同，造成了位置偏差。

圖10 道路網(wǎng)局部差異情況Fig.10 Local difference of road network

針對上述情況，本文借鑒文獻[15]中Stroke方向相似性計算方法，連接道路Stroke的特征點形成新的弧段，將各弧段的相關長度系數(shù)作為權值，對各弧段的方位角加權求值，以此作為度量Stroke自身方向的指標。如圖11所示，設組成Stroke的道路弧段總長度為L，第i個道路弧段的長度為Li，則相關長度系數(shù)為

(2)

將該值作為計算方向均值的權值，得到描述整條道路Stroke方向的計算模型

θ均值=λ1θ1+λ2θ2+…+λiθi

(3)

式中，θi為為第i條連線與x軸正方向的夾角。依據(jù)此度量方法，得出目標道路自身方向相似性的計算公式為

(4)

圖11 方向關系相似性量化表達示例Fig.11 Example of quantitative expression of direction relation similarity

2.1.2.2 上下級方向相似性計算

若只是從目標道路自身弧段特征出發(fā)進行方向相似性計算，那么容易出現(xiàn)圖1所示的誤匹配情況。所以本文在單個道路方向度量的基礎上引入上下級道路方向相似性計算，以目標道路周邊的鄰域道路作為重要參考，進行道路群組的方向相似性計算。以圖9中的8級道路S8-1為例，在S8-1鄰域內的9級道路有2條，在S8-1鄰域內的7級道路有4條，那么S8-1的上下級道路總數(shù)為6條，這6條上下級道路就相當于一個道路群組。

道路群組方向相似性的計算方法如下：

首先利用上一節(jié)中道路自身方向的計算方法

計算單個道路的方向，然后以坐標原點為原點，以一定長度為半徑，將線要素的方向關系用離散點表示，并擬合該離散點群的標準差橢圓，即將線群轉化為點群計算，如圖12所示。標準差橢圓是用來描述群組目標分布方向偏離的，由經(jīng)典統(tǒng)計分析學中的樣本標準差擴展而來(圖13)?？臻g統(tǒng)計中的歐氏距離，就相當于經(jīng)典統(tǒng)計中的標準差。標準差表示觀測值對均值的偏離情況，標準距離則表示各點的空間位置對平均中心位置或空間均值的偏離情況[27]。

圖12 擬合橢圓Fig.12 Schematic of fitting ellipse

圖13 標準差橢圓Fig.13 Standard deviation ellipse

在離散點集的原始坐標系(XOY)下，假設存在某一方向，所有離散點到該方向的標準差距離最小，那么該方向與原坐標軸的X方向的夾角就是點集的定向方向。將坐標軸進行旋轉形成新的坐標系(X′O′Y′)，新坐標系的坐標原點為點集中所有點的平均值中點(xmc,ymc)。標準差橢圓的計算方法簡述如下：

(2) 計算轉角θ。根據(jù)以下公式計算點群的整體分布方向

(5)

(3) 計算沿長軸方向的標準差δx和短軸方向的標準差δy

(6)

有了橢圓中心、轉角、長、短軸，就可以確定一個標準差橢圓(圖13)。

對于生成的標準差橢圓，橢圓的長軸方向代表了對應的點群的主要分布方向，所有點到該方向的標準差距離最小。對于標準差橢圓夾角分別為θ1、θ2的兩個道路群組進行方向相似性計算，同時對計算結果進行歸一化處理，可以取θ的余弦來計算其相似性。具體的相似性計算公式為

(7)

2.1.3 道路和道路上下級距離相似性計算

常見的線要素距離度量方法有3種：歐氏距離、Hausdorff距離和Fréchet距離。根據(jù)人對道路距離的認知習慣，本文采用歐氏距離作為距離度量指標，提出一種顧及上下級關系的距離度量方法。即提取目標道路中心點，計算目標道路中心點與其鄰域內上級和下級所有道路的中心點距離，然后對這些距離求和，進行加權求平均值，以此平均值作為目標道路的距離度量值，本文稱這樣的距離值為平均中心距離值。所以對于數(shù)據(jù)源A和數(shù)據(jù)源B中的兩條道路，其上下級距離相似度計算公式為

(8)

式中，dis1、dis2為兩個同名道路平均中心距離值。

2.2 道路和道路上下級空間關系總相似性計算

以上分別定義了鄰域道路空間關系的拓撲、方向和距離相似性，根據(jù)Egenhofer和Mark提出的“拓撲關系起主導作用，其他可度量關系起提煉作用”的原則[26]，突出拓撲關系在空間關系中的關鍵作用，在對鄰域道路之間空間關系相似性進行整體度量時，對上述3種空間關系相似性分別賦予不同的權值。采用文獻[28]中對拓撲、方向以及距離關系的權值設置方法，對以上3種空間關系相似性度量分別賦予不同的權值，即對上下級拓撲相似度、方向相似度和距離相似度，分別賦予0.4、0.3、0.3的權值。所以，鄰域道路空間關系總相似度的計算公式為

sim_sr=0.4sim_topo+0.3(0.5sim_dir1+

0.5sim_dir2)+0.3sim_dis

(9)

3 道路和道路聯(lián)動匹配流程

3.1 聯(lián)動匹配過程

道路網(wǎng)聯(lián)動匹配的特點就是通過一條高等級道路的匹配帶動與其具有關聯(lián)關系的多條低等級道路進行匹配，而要實現(xiàn)準確聯(lián)動匹配的前提是道路本身的特征相似和其上下級道路空間關系相似保持高度一致性?；谶@一原則，假設兩數(shù)據(jù)源中目標道路和參考道路的上級拓撲總數(shù)和下級拓撲總數(shù)均相等，且上下級空間關系總相似性數(shù)值大致相同，如果兩者在一定條件下同時成立，證明目標道路組成的道路群組和參考道路組成的道路群組兩兩互為同名道路。其具體匹配過程如下：

步驟1 添加匹配標記變量。將兩數(shù)據(jù)源中所有未匹配的道路添加匹配標記變量NUL=0，若在匹配過程中有道路匹配成功，則NUL=1。對于NUL=1的道路，就不會再作為待匹配道路參與匹配。

步驟3 匹配標記變量判斷。將數(shù)據(jù)源A中NUL=0的道路添加到集合S，同理，將數(shù)據(jù)源B中NUL=0的道路添加到集合V。

步驟6 上下級空間關系相似性計算。若(H，G)中道路c和道路d的上級拓撲總數(shù)和下級拓撲總數(shù)都相等，且上下級空間關系總相似性大于設置的閾值。若上述假設成立，轉到步驟7。若上述假設不成立，轉到步驟8。

步驟7 道路c和道路d互為同名道路，集合H和G中的道路兩兩之間可能也互為同名道路。對集合H與G中的道路進行緩沖區(qū)增長法判斷，確定兩兩同名道路之間的對應關系，轉到步驟9。

步驟8 計算(H，G)中道路的上下級空間關系總相似性，若相似性數(shù)值大于閾值，則道路c和道路d是一對同名道路，將道路c和道路d的NUL值賦值為1，并轉到步驟10；若相似性數(shù)值小于閾值，刪除集合G中的道路，選取在空間位置上與道路bj相交或相鄰的另一條低等級道路d′，并保持道路c不變，轉到步驟5。

匹配流程如圖14所示。

3.2 特殊情況處理

道路網(wǎng)十分復雜，具有較強的不確定性，在利用本文方法進行匹配時需要考慮下面兩種特殊情況：

3.2.1 道路等級評價時同名道路被劃分為不同的道路等級

在對道路網(wǎng)進行等級評價時，兩幅圖中的同名道路可能被劃分為不同的等級，由于本文方法只在相同等級的道路集合中搜索關聯(lián)匹配對象，這就造成了原本存在匹配對象的要素被錯誤地判斷為無匹配對象的情況。

針對這種情況，采用“緩沖區(qū)增長匹配”的思路解決。當數(shù)據(jù)源A中的道路在對應的數(shù)據(jù)源B中搜索判斷后，若無匹配對象，尚不能斷定其不存在匹配關系，而要將其加入道路“候選匹配集”中。當聯(lián)動匹配整體結束后，對緩沖匹配集中的每條道路，重新在道路數(shù)據(jù)源B中進行整體遍歷判斷其是否確實不存在匹配對象。若存在道路與之匹配，則將其納入匹配結果中；若仍無匹配對象，此時確定該道路不存在匹配關系，判斷為新增道路。

“緩沖區(qū)增長匹配”確保了匹配結果的正確，雖然一定程度上增加了匹配判斷總次數(shù)，但是這種情況相對很少，因此不會對匹配效率產(chǎn)生較大影響。

3.2.2 無法滿足聯(lián)動匹配模型中道路間關聯(lián)關系構建條件

聯(lián)動匹配流程圖中判斷匹配信息傳遞結束的條件是雙方數(shù)據(jù)中道路的數(shù)據(jù)的匹配標記變量值同時為1，這是理想的理論情況。實際情況中，如果某區(qū)域經(jīng)歷了大面積重建，就會出現(xiàn)部分區(qū)域道路不滿足構建關聯(lián)模型的閾值的情況，無法完成匹配信息的傳遞，其道路匹配標記變量值依然為0。若仍按原流程進行則會出現(xiàn)誤匹配或者無匹配情況。針對這類對象，只能將標記值為0的未匹配道路加入新的候選匹配圖層，將雙方看成是新的數(shù)據(jù)源，采用“緩沖區(qū)增長匹配”方法進行匹配。若此過程后仍存在匹配標識值為0的道路，則將其判定為新增道路。

4 試驗與分析

4.1 試驗數(shù)據(jù)及對比試驗方法

為驗證本文方法的有效性和適用性，選擇環(huán)形放射式、方格網(wǎng)式和混合式3種不同形式的城市道路網(wǎng)數(shù)據(jù)進行試驗。分別選擇成都、西安和北京3組不同來源相同比例尺的數(shù)據(jù)作為上述路網(wǎng)代表進行試驗，目的是測試路網(wǎng)形式不同是否會影響聯(lián)動匹配信息傳遞，從而檢驗本文方法的適用性。3種路網(wǎng)形式數(shù)據(jù)疊加顯示效果如圖15(a)、圖16(a)與圖17(a)所示，由圖中可以看出，盡管經(jīng)過了數(shù)據(jù)預處理和系統(tǒng)誤差糾正，兩幅圖之間仍存在一定的位置偏差。同時，由于文獻[16]將每條道路作為一個整體，基于Stroke層次結構模型進行城市道路網(wǎng)匹配，具有一定的時效性和科學性，所以本文選取文獻[16]中方法(以下簡稱為層次結構方法)作對比試驗。

圖14 聯(lián)動匹配流程Fig.14 Flow chart of linkage matching

圖15 環(huán)形放射式道路數(shù)據(jù)預處理Fig.15 Ring radial road data preprocessing

圖16 方格網(wǎng)式道路數(shù)據(jù)預處理Fig.16 Grid type road data preprocessing

圖17 混合式道路數(shù)據(jù)預處理Fig.17 Mixed road data preprocessing

4.2 匹配結果

對不同路網(wǎng)形式的數(shù)據(jù)構建Stroke并進行等級劃分，完成構建Stroke的疊加效果如圖15(b)、圖16(b)、圖17(b)所示。由圖中可以看出，環(huán)形放射式和混合式道路網(wǎng)構完Stroke后同名道路大多被劃分為相同等級，而方格網(wǎng)式道路網(wǎng)構完Stroke后存在較多的同名道路被劃分為不同等級的情況，這在匹配過程中就要用到3.2節(jié)中特殊情況處理的方法。表1的統(tǒng)計結果顯示經(jīng)過Stroke提取后道路網(wǎng)數(shù)據(jù)得以大幅度簡化，這有利于提高聯(lián)動匹配效率。

表1 道路網(wǎng)數(shù)據(jù)提取Stroke前后對比

Tab.1 Comparison of road network data before and after Stroke extraction

道路類型道路網(wǎng)弧段數(shù)量Stroke數(shù)量環(huán)形放射式577/585136/140方格網(wǎng)式522/513113/114混合式1092/1101220/230

分別對3組道路類型數(shù)據(jù)構建骨架關聯(lián)樹，然后按照3.1節(jié)所述試驗步驟進行空間關系相似性計算，從而使匹配結果得以從高等級道路傳遞到低等級道路，實現(xiàn)聯(lián)動匹配。圖18為環(huán)形放射式道路數(shù)據(jù)中一條高等級骨干道路的匹配結果示意。由圖中可以看出一條高等級道路帶動了數(shù)條低等級道路進行匹配，取得很好的匹配結果，有效提高匹配效率。圖19(a)、圖20(a)與圖21(a)分別為本文方法進行匹配得到的結果，圖中黑色短線為匹配標識線。同時，對同樣數(shù)據(jù)采用層次結構方法進行試驗，圖18(b)、圖19(b)與圖20(b)分別為層次結構方法進行匹配得到的結果。由表2可知，層次結構方法對于3種不同路網(wǎng)形式道路數(shù)據(jù)匹配正確率分別為68.33%、69.81%和76.92%，而本文方法匹配正確率均超過75%。

圖18 一條高等級骨干道路聯(lián)動匹配結果示例Fig.18 Example of the results of a high level backbone road linkage matching

圖19 環(huán)形放射式路網(wǎng)匹配結果Fig.19 Result of ring radial road network

圖20 方格網(wǎng)式路網(wǎng)匹配結果Fig.20 Result of grid road network matching

根據(jù)試驗結果進行統(tǒng)計，從匹配率與匹配正確率兩方面進行試驗對比分析。匹配率、匹配正確率是衡量匹配結果質量的重要指標，其中匹配率又稱查全率，是指匹配結果中實現(xiàn)匹配的要素個數(shù)與同名要素個數(shù)的比值；匹配正確率是指匹配結果中正確匹配的要素個數(shù)與匹配要素個數(shù)的比值。試驗結果見表2。

圖21 混合式路網(wǎng)匹配結果Fig.21 Result of mixed road network matching

表3所示為聯(lián)動匹配方法、層次結構方法傳統(tǒng)緩沖區(qū)增長方法匹配時間的統(tǒng)計結果。從中看出，在匹配消耗時間方面，聯(lián)動匹配方法與層次結構法時間耗時相當，但是與傳統(tǒng)緩沖區(qū)增長法相比，聯(lián)動匹配方法大幅減少了匹配時間，緩沖區(qū)匹配方法的耗時大約是本文方法的2倍。因此聯(lián)動匹配方法有效提高了匹配效率。

表3 匹配時間對比

4.3 試驗分析

對兩種算法的匹配結果作如下分析：

(1) 本文方法在避免了全局遍歷搜索候選匹配對象的基礎上，采取了一條高等級道路匹配結果帶動多條與其相關的低等級道路進行匹配的聯(lián)動匹配策略，從而減少了匹配判斷時間，提高了匹配效率。

(2) 本文在道路網(wǎng)進行Stroke提取和等級劃分后，利用道路網(wǎng)上下級空間關系相似性構建道路網(wǎng)聯(lián)動匹配模型，充分發(fā)揮骨干道路在匹配過程中定位參考的優(yōu)勢，對于位置偏差較大的道路數(shù)據(jù)具有較強的適應性，故本文方法得到較好的匹配結果。而文獻[16]所述的層次結構方法沒有顧及道路鄰域要素對匹配結果的影響，所以對于幾何位置偏差較大的數(shù)據(jù)適應性相對較差。

(3) 對于本文方法匹配結果中出現(xiàn)的錯誤情況，原因在于不同來源的道路數(shù)據(jù)存在較強的不確定性，同名道路空間特征和幾何特征相似度也可能較低，而非同名道路間也可能具有較高的相似度，這也可能造成錯誤匹配。但是，這種情況出現(xiàn)概率較小，所以本文方法基本能夠保證大部分的道路匹配結果的正確性。

通過以上試驗對比分析，聯(lián)動匹配方法在匹配正確率和匹配效率兩個方面具有以下特點：

(1) 匹配正確率：①對于存在位置偏差的數(shù)據(jù)，道路網(wǎng)聯(lián)動匹配方法充分利用骨干道路在匹配中定位參考的優(yōu)勢，使匹配信息在關聯(lián)道路之間進行傳遞，在一定程度上避免了幾何位置偏差對匹配結果的影響，有效提高了匹配正確率；②對于不存在明顯位置偏差的匹配數(shù)據(jù)，由于聯(lián)動匹配縮小了候選匹配集的數(shù)據(jù)搜索范圍，能夠減少周邊道路的干擾，從而提高匹配正確率。

(2) 匹配效率。聯(lián)動匹配的特點就是通過一條高等級道路匹配帶動與其具有關聯(lián)關系的多條低等級道路進行匹配，大幅減少了匹配判斷次數(shù)，使得在匹配判斷總次數(shù)方面此方法遠遠少于整體遍歷式匹配方法。因此本文方法能夠減少匹配時間、提高匹配效率。

(3) 適用范圍。聯(lián)動匹配在3種不同形式的路網(wǎng)中均有較好的匹配效果，不會受到道路形式的影響，因此，聯(lián)動匹配適用于多種形態(tài)的路網(wǎng)。

5 結 論

本文模仿人在讀圖時通過特征地物和空間關聯(lián)尋找目標地物的思維過程，將匹配看作是一種特征目標尋找、信息關聯(lián)傳遞的推理過程。運用Stroke技術將復雜道路網(wǎng)進行重新組織和等級劃分，在匹配過程中以上下級空間關系相似性為約束條件，以相鄰道路作為定位參考，構造具有明顯層次特性的道路網(wǎng)聯(lián)動匹配模型，最后，以突出的骨干道路作為起始匹配對象，實現(xiàn)了匹配信息在道路之間的傳遞，達到了聯(lián)動匹配的目的。與Stroke層次結構方法和傳統(tǒng)的緩沖區(qū)匹配方法的試驗對比驗證了本文方法在效率和準確率方面的優(yōu)勢。尤其對于存在明顯幾何位置偏差的數(shù)據(jù)，本文方法具有較強的適應性。

進一步研究的難點是：本文目前只針對相同或相近比例尺道路網(wǎng)進行了試驗和對比分析。下一步研究的方向是探尋將該算法應用于一對多和多對多匹配情況。

[1] QUDDUS M A, OCHIENG W Y, NOLAND R B. Map Matching Algorithms for Intelligent Transport Systems Applications[C]∥Proceedings of the 13th World Congress on Intelligent Transport Systems and Services. London: ITRD, 2006.

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

[3] MANTEL D, LIPECK U. Matching Cartographic Objects in Spatial Databases[C]∥Proceedings of the ISPRS Congress, Commission 4. Istanbul, Turkey: ISPRS, 2004.

[4] ZHANG Meng, MENG Liqiu. An Iterative Road-matching Approach for the Integration of Postal Data[J]. Computers, Environment and Urban Systems, 2007, 31(5): 597-615.

[5] GABAY Y, DOYTSHER Y. Adjustment of Line Maps[C]∥Proceedings of the GIS/LIS’94. Phoenix, Arizona: [s.n.], 1994: 191-199.

[8] DENG Min, LI Zhilin, CHEN Xiaoyong. Extended Hausdorff Distance for Spatial Objects in GIS[J]. International Journal of Geographical Information Science, 2007, 21(4): 459-475.

[9] ZHANG Meng, SHI Wei, MENG Liqiu. A Generic Matching Algorithm for Line Networks of Different Resolutions[C]∥Proceedings of the 8th ICA Workshop on Generalisation and Multiple Representation. Corua, Spain: [s.n.], 2005.

[10] 陳玉敏, 龔健雅, 史文中. 多尺度道路網(wǎng)的距離匹配算法研究[J]. 測繪學報, 2007, 36(1): 84-90. DOI: 10.3321/j.issn:1001-1595.2007.01.015.

CHEN Yumin, GONG Jianya, SHI Wenzhong. A Distance-based Matching Algorithm for Multi-scale Road Networks[J]. Acta Geodaetica et Cartographica Sinica, 2007, 36(1): 84-90. DOI: 10.3321/j.issn:1001-1595.2007.01.015.

[11] ZHANG M. Methods and Implementations of Road-network Matching[D]. Munich, Germany: Technical University of Munich, 2009: 47-94.

[12] 童小華, 鄧愫愫, 史文中. 基于概率的地圖實體匹配方法[J]. 測繪學報, 2007, 36(2): 210-217. DOI: 10.3321/j.issn:1001-1595.2007.02.017.TONG Xiaohua, DENG Susu, SHI Wenzhong. A Probabilistic Theory-based Matching Method[J]. Acta Geodaetica et Cartographica Sinica, 2007, 36(2): 210-217. DOI: 10.3321/j.issn:1001-1595.2007.02.017.

[13] 趙東保, 盛業(yè)華. 全局尋優(yōu)的矢量道路網(wǎng)自動匹配方法研究[J]. 測繪學報, 2010, 39(4): 416-421.

ZHAO Dongbao, SHENG Yehua. Research on Automatic Matching of Vector Road Networks Based on Global Optimization[J]. Acta Geodaetica et Cartographica Sinica, 2010, 39(4): 416-421.

[14] 張云菲, 楊必勝, 欒學晨. 利用概率松弛法的城市路網(wǎng)自動匹配[J]. 測繪學報, 2012, 41(6): 933-939. ZHANG Yunfei, YANG Bisheng, LUAN Xuechen. Automated Matching Urban Road Networks Using Probabilistic Relaxation[J]. Acta Geodaetica et Cartographica Sinica, 2012, 41(6): 933-939.

[15] 劉海龍, 錢海忠, 王驍, 等. 采用層次分析法的道路網(wǎng)整體匹配方法[J]. 武漢大學學報(信息科學版), 2015, 40(5): 644-651.

LIU Hailong, QIAN Haizhong, WANG Xiao, et al. Road Networks Global Matching Method Using Analytical Hierarchy Process[J]. Geomatics and Information Science of Wuhan University, 2015, 40(5): 644-651.

[16] 劉海龍, 錢海忠, 黃智深, 等. 采用Stroke層次結構模型的道路網(wǎng)匹配方法[J]. 測繪科學技術學報, 2013, 30(6): 647-651, 657.

LIU Hailong, QIAN Haizhong, HUANG Zhishen, et al. Road Network Matching Method with Stroke-hierarchical Model[J]. Journal of Geomatics Science and Technology, 2013, 30(6): 647-651, 657.

[17] THOMSON R C, RICHARDSON D E. The “Good Continuation” Principle of Perceptual Organization Applied to the Generalization of Road Networks[C]∥Proceedings of the 19th International Cartographic Conference. Ottawa, Canada: [s.n.], 1999: 1215-1223.

[18] THOMSON R C. The Stroke Concept in Geographic Network Generalization and Analysis[C]∥Proceedings of the 12th International Symposium on Spatial Data Handling. Vienna, Austria: [s.n.], 2006: 681-697.

[19] ANG Y H, LI Z, ONG S H. Image Retrieval Based on Multidimensional Feature Properties[C]∥Proceedings of the SPIE 2420, Storage and Retrieval for Image and Video Databases III. San Jose, CA: SPIE, 1995: 47-57.

[20] 翟仁健. 基于全局一致性評價的多尺度矢量空間數(shù)據(jù)匹配方法研究[D]. 鄭州: 信息工程大學, 2011: 31-36.

ZHAI Renjian. Research on Automated Matching Methods for Multi-scale Vector Spatial Data Based on Global Consistency Evaluation[D]. Zhengzhou: Information Engineering University, 2011: 31-36.

[21] 錢海忠, 張釗, 翟銀鳳, 等. 特征識別、Stroke與極化變換結合的道路網(wǎng)選取[J]. 測繪科學技術學報, 2010, 27(5): 371-374, 378.

QIAN Haizhong, ZHANG Zhao, ZHAI Yinfeng, et al. Road Selection Method Based on Character Recognition, Stroke and Polarization Transformation[J]. Journal of Geomatics Science and Technology, 2010, 27(5): 371-374, 378.

[22] 錢海忠, 武芳, 朱鯤鵬, 等. 一種基于降維技術的街區(qū)綜合方法[J]. 測繪學報, 2007, 36(1): 102-107, 118.

QIAN Haizhong, WU Fang, ZHU Kunpeng, et al. A Generalization Method of Street Block Based on Dimension-reducing Technique[J]. Acta Geodaetica et Cartographica Sinica, 2007, 36(1): 102-107, 118.

[23] 何海威, 錢海忠, 劉海龍, 等. 道路網(wǎng)層次骨架控制的道路選取方法[J]. 測繪學報, 2015, 44(4): 453-461. DOI: 10.11947/j.AGCS.2015.20130787.

HE Haiwei, QIAN Haizhong, LIU Hailong, et al. Road Network Selection Based on Road Hierarchical Structure Control[J]. Acta Geodaetica et Cartographica Sinica, 2015, 44(4): 453-461. DOI: 10.11947/j.AGCS.2015.20130787.

[24] 楊敏, 艾廷華, 周啟. 顧及道路目標Stroke特征保持的路網(wǎng)自動綜合方法[J]. 測繪學報, 2013, 42(4): 581-587, 594.

YANG Min, AI Tinghua, ZHOU Qi. A Method of Road Network Generalization Considering Stroke Properties of Road Object[J]. Acta Geodaetica et Cartographica Sinica, 2013, 42(4): 581-587, 594.

[25] EGENHOFER M J, FRANZOSA R D. Point-set Topological Spatial Relations[J]. International Journal of Geographical Information Systems, 1991, 5(2): 161-174.

[26] EGENHOFER M J, MARK D M. Naive Geography[M]∥FRANK A U, KUHN W. Spatial Information Theory：A Theoretical Basis for GIS. Berlin: Springer, 1995: 1-15.

[27] 劉濤, 楊樹文, 李軼鯤, 等. 空間線群目標方向相似度計算模型[J]. 測繪科學, 2013, 38(1): 156-159.

LIU Tao, YANG Shuwen, LI Yikun, et al. Direction Similarity Calculation Model of Spatial Line Groups[J]. Science of Surveying and Mapping, 2013, 38(1): 156-159.

[28] 劉濤. 空間群(組)目標相似關系及計算模型研究[D]. 武漢: 武漢大學, 2011: 45-57.

LIU Tao. Similarity of Spatial Group Objects[D]. Wuhan: Wuhan University, 2011: 45-57.

(責任編輯：叢樹平)

A Linkage Matching Method for Road Networks Considering the Similarity of Upper and Lower Spatial Relation

LIU Chuang，QIAN Haizhong，WANG Xiao，HE Haiwei，CHEN Jingnan

Institute of Geospatial Information, Information Engineering University, Zhengzhou 450052, China

Existing road network matching methods mostly use the characteristics of the road’s own nodes and arcs to carry on the matching process, while less attention is focused on the importance of the road neighborhood elements in the road network matching, thus affecting further improvement of the matching efficiency and accuracy. In response to these problems, a linkage matching method for road network considering the similarity of upper and lower spatial relation is proposed. The linkage matching imitates the human thinking process of searching for target objects by the signal features and spatial correlation when reading maps, regarding matching as a reasoning process of goal feature searching and information association transmitting. Firstly, classify the complex road network by using Stroke technology. Secondly, establish the road network linkage matching model based on road skeleton relation tree. Finally, select the high-level road in the classifying results of the source data as the reference road to start matching, calculate the road between the upper and lower levels of the spatial relationship similarity, and through a step-by-step iteration, make the matching information transmit in the road network linkage matching model thus to obtain the final matching results. Experiment shows that the mentioned algorithm can narrow the search range of the data to be matched, effectively improving the match efficiency and accuracy, especially applicable to the data with large non systematic geometric location deviation.

linkage matching; spatial relations; Stroke technology; information transfer

The National Natural Science Foundation of China (Nos.41171305; 41571442)

LIU Chuang(1992—)，male，postgraduate，majors in spatial data matching, spatial data updating and map automatic generalization.

QIAN Haizhong

劉闖，錢海忠，王驍，等.顧及上下級空間關系相似性的道路網(wǎng)聯(lián)動匹配方法[J].測繪學報，2016,45(11)：1371-1383.

10.11947/j.AGCS.2016.20160062.

LIU Chuang，QIAN Haizhong，WANG Xiao，et al.A Linkage Matching Method for Road Networks Considering the Similarity of Upper and Lower Spatial Relation[J]. Acta Geodaetica et Cartographica Sinica,2016,45(11):1371-1383. DOI:10.11947/j.AGCS.2016.20160062.

P208

A

1001-1595(2016)11-1371-13

國家自然科學基金(41171305；41571442)

2016-02-18

修回日期： 2016-06-27

劉闖(1992—)，男，碩士生，研究方向為空間數(shù)據(jù)匹配與更新、自動制圖綜合。

E-mail： liuchuang310@163.com

錢海忠

E-mail： qianhaizhong2005@163.com