劉 闖，錢海忠，王 驍，何海威，陳競(jìng)男

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

?

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

劉 闖，錢海忠，王 驍，何海威，陳競(jìng)男

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

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

聯(lián)動(dòng)匹配；空間關(guān)系；Stroke技術(shù)；信息傳遞

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

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

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

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

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

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

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

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

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

圖2 道路Stroke構(gòu)建原理Fig.2 Theory of road Stroke construction

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

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

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

1.2 道路和道路骨架關(guān)聯(lián)樹構(gòu)建

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

(1) 相同等級(jí)道路Stroke之間是網(wǎng)狀關(guān)系，不同等級(jí)道路Stroke之間形成層次結(jié)構(gòu)關(guān)系。

(2) 一條高等級(jí)道路Stroke可能具備多個(gè)子節(jié)點(diǎn)。

(3) 一條低等級(jí)道路Stroke可能具備多個(gè)根節(jié)點(diǎn)。

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

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

1.3 道路和道路聯(lián)動(dòng)匹配模型構(gòu)建

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

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

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

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

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

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

2 道路網(wǎng)上下級(jí)空間關(guān)系相似性計(jì)算

如圖7所示，在構(gòu)建道路網(wǎng)聯(lián)動(dòng)匹配模型時(shí)，一條高等級(jí)Stroke可能與多條低等級(jí)Stroke相交或相鄰，這不利于匹配信息準(zhǔn)確快速的傳遞，甚至?xí)绊懫ヅ湫?。因此引入上下?jí)空間關(guān)系相似性對(duì)匹配過程進(jìn)行約束，以突出的骨干道路作為重要定位參考，通過待匹配道路相對(duì)于骨干道路在空間關(guān)系上的有序性和相似性來引導(dǎo)匹配進(jìn)程，從而實(shí)現(xiàn)道路網(wǎng)聯(lián)動(dòng)匹配。

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

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

2.1 道路和道路上下級(jí)空間關(guān)系相似性計(jì)算

2.1.1 道路和道路上下級(jí)拓?fù)湎嗨菩杂?jì)算

線要素之間的拓?fù)潢P(guān)系可以粗略的歸納為相鄰(部分重合)、重合、相交(相接)和相離4種關(guān)系。參考傳統(tǒng)的拓?fù)潢P(guān)系概念鄰域圖[25-26]，如圖8所示，因?yàn)樵诘缆肪W(wǎng)中相交和相鄰的道路關(guān)聯(lián)相似性比較大，故本文將相交和相鄰視為鄰域內(nèi)關(guān)系，本文所指空間關(guān)系相似性主要就是計(jì)算鄰域內(nèi)道路間的空間關(guān)系相似性。通常將目標(biāo)道路的鄰域道路數(shù)量作為其拓?fù)淇倲?shù)，根據(jù)骨架關(guān)聯(lián)樹的特點(diǎn)，將拓?fù)湎嗨菩苑譃樯霞?jí)拓?fù)湎嗨菩院拖录?jí)拓?fù)湎嗨菩詢刹糠?，即以一?duì)同名道路的上一等級(jí)鄰域道路數(shù)量作為上級(jí)拓?fù)淇倲?shù)，以該條道路的下一等級(jí)鄰域道路數(shù)量作為下級(jí)拓?fù)淇倲?shù)。如圖9所示，道路S8-1的道路等級(jí)為8，與S8-1相交或相鄰的9級(jí)道路數(shù)量為2，則該條道路的上級(jí)拓?fù)淇倲?shù)為2；與S8-1相交或相鄰的7級(jí)道路數(shù)量為4，那么該條道路的下級(jí)拓?fù)淇倲?shù)為6。

圖8 線要素間拓?fù)潢P(guān)系鄰域圖Fig.8 The neighborhood figure of topological relationships between line elements

圖9 線要素拓?fù)淇倲?shù)計(jì)算示例Fig.9 Total number computation of line elements topology

按照這種計(jì)算方法，兩組數(shù)據(jù)源之間的上下級(jí)拓?fù)湎嗨菩钥杀硎緸?/p>

(1)

2.1.2 道路和道路上下級(jí)方向相似性計(jì)算

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

2.1.2.1 目標(biāo)道路自身方向相似性計(jì)算

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

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

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

(2)

將該值作為計(jì)算方向均值的權(quán)值，得到描述整條道路Stroke方向的計(jì)算模型

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

(3)

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

(4)

圖11 方向關(guān)系相似性量化表達(dá)示例Fig.11 Example of quantitative expression of direction relation similarity

2.1.2.2 上下級(jí)方向相似性計(jì)算

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

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

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

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

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

圖13 標(biāo)準(zhǔn)差橢圓Fig.13 Standard deviation ellipse

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

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

(5)

(3) 計(jì)算沿長(zhǎng)軸方向的標(biāo)準(zhǔn)差δx和短軸方向的標(biāo)準(zhǔn)差δy

(6)

有了橢圓中心、轉(zhuǎn)角、長(zhǎng)、短軸，就可以確定一個(gè)標(biāo)準(zhǔn)差橢圓(圖13)。

對(duì)于生成的標(biāo)準(zhǔn)差橢圓，橢圓的長(zhǎng)軸方向代表了對(duì)應(yīng)的點(diǎn)群的主要分布方向，所有點(diǎn)到該方向的標(biāo)準(zhǔn)差距離最小。對(duì)于標(biāo)準(zhǔn)差橢圓夾角分別為θ1、θ2的兩個(gè)道路群組進(jìn)行方向相似性計(jì)算，同時(shí)對(duì)計(jì)算結(jié)果進(jìn)行歸一化處理，可以取θ的余弦來計(jì)算其相似性。具體的相似性計(jì)算公式為

(7)

2.1.3 道路和道路上下級(jí)距離相似性計(jì)算

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

(8)

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

2.2 道路和道路上下級(jí)空間關(guān)系總相似性計(jì)算

以上分別定義了鄰域道路空間關(guān)系的拓?fù)?、方向和距離相似性，根據(jù)Egenhofer和Mark提出的“拓?fù)潢P(guān)系起主導(dǎo)作用，其他可度量關(guān)系起提煉作用”的原則[26]，突出拓?fù)潢P(guān)系在空間關(guān)系中的關(guān)鍵作用，在對(duì)鄰域道路之間空間關(guān)系相似性進(jìn)行整體度量時(shí)，對(duì)上述3種空間關(guān)系相似性分別賦予不同的權(quán)值。采用文獻(xiàn)[28]中對(duì)拓?fù)洹⒎较蛞约熬嚯x關(guān)系的權(quán)值設(shè)置方法，對(duì)以上3種空間關(guān)系相似性度量分別賦予不同的權(quán)值，即對(duì)上下級(jí)拓?fù)湎嗨贫?、方向相似度和距離相似度，分別賦予0.4、0.3、0.3的權(quán)值。所以，鄰域道路空間關(guān)系總相似度的計(jì)算公式為

sim_sr=0.4sim_topo+0.3(0.5sim_dir1+

0.5sim_dir2)+0.3sim_dis

(9)

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

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

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

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

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

步驟6 上下級(jí)空間關(guān)系相似性計(jì)算。若(H，G)中道路c和道路d的上級(jí)拓?fù)淇倲?shù)和下級(jí)拓?fù)淇倲?shù)都相等，且上下級(jí)空間關(guān)系總相似性大于設(shè)置的閾值。若上述假設(shè)成立，轉(zhuǎn)到步驟7。若上述假設(shè)不成立，轉(zhuǎn)到步驟8。

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

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

匹配流程如圖14所示。

3.2 特殊情況處理

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

3.2.1 道路等級(jí)評(píng)價(jià)時(shí)同名道路被劃分為不同的道路等級(jí)

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

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

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

3.2.2 無法滿足聯(lián)動(dòng)匹配模型中道路間關(guān)聯(lián)關(guān)系構(gòu)建條件

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

4 試驗(yàn)與分析

4.1 試驗(yàn)數(shù)據(jù)及對(duì)比試驗(yàn)方法

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

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

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

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

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

4.2 匹配結(jié)果

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

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

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

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

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

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

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

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

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

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

表3 匹配時(shí)間對(duì)比

4.3 試驗(yàn)分析

對(duì)兩種算法的匹配結(jié)果作如下分析：

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

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

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

通過以上試驗(yàn)對(duì)比分析，聯(lián)動(dòng)匹配方法在匹配正確率和匹配效率兩個(gè)方面具有以下特點(diǎn)：

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

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

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

5 結(jié) 論

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

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

[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]. 測(cè)繪學(xué)報(bào), 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] 童小華, 鄧愫愫, 史文中. 基于概率的地圖實(shí)體匹配方法[J]. 測(cè)繪學(xué)報(bào), 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)自動(dòng)匹配方法研究[J]. 測(cè)繪學(xué)報(bào), 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] 張?jiān)品? 楊必勝, 欒學(xué)晨. 利用概率松弛法的城市路網(wǎng)自動(dòng)匹配[J]. 測(cè)繪學(xué)報(bào), 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]. 武漢大學(xué)學(xué)報(bào)(信息科學(xué)版), 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層次結(jié)構(gòu)模型的道路網(wǎng)匹配方法[J]. 測(cè)繪科學(xué)技術(shù)學(xué)報(bào), 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] 翟仁健. 基于全局一致性評(píng)價(jià)的多尺度矢量空間數(shù)據(jù)匹配方法研究[D]. 鄭州: 信息工程大學(xué), 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] 錢海忠, 張釗, 翟銀鳳, 等. 特征識(shí)別、Stroke與極化變換結(jié)合的道路網(wǎng)選取[J]. 測(cè)繪科學(xué)技術(shù)學(xué)報(bào), 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] 錢海忠, 武芳, 朱鯤鵬, 等. 一種基于降維技術(shù)的街區(qū)綜合方法[J]. 測(cè)繪學(xué)報(bào), 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]. 測(cè)繪學(xué)報(bào), 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] 楊敏, 艾廷華, 周啟. 顧及道路目標(biāo)Stroke特征保持的路網(wǎng)自動(dòng)綜合方法[J]. 測(cè)繪學(xué)報(bào), 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] 劉濤, 楊樹文, 李軼鯤, 等. 空間線群目標(biāo)方向相似度計(jì)算模型[J]. 測(cè)繪科學(xué), 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] 劉濤. 空間群(組)目標(biāo)相似關(guān)系及計(jì)算模型研究[D]. 武漢: 武漢大學(xué), 2011: 45-57.

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

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

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

劉闖，錢海忠，王驍，等.顧及上下級(jí)空間關(guān)系相似性的道路網(wǎng)聯(lián)動(dòng)匹配方法[J].測(cè)繪學(xué)報(bào)，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

國(guó)家自然科學(xué)基金(41171305；41571442)

2016-02-18

修回日期： 2016-06-27

劉闖(1992—)，男，碩士生，研究方向?yàn)榭臻g數(shù)據(jù)匹配與更新、自動(dòng)制圖綜合。

E-mail： liuchuang310@163.com

錢海忠

E-mail： qianhaizhong2005@163.com