付仲良，楊元維，高賢君，趙星源，范　亮

1. 武漢大學(xué)遙感信息工程學(xué)院，湖北 武漢 430079； 2. 地球空間信息技術(shù)協(xié)同創(chuàng)新中心，湖北 武漢 430079； 3. 長(zhǎng)江大學(xué)地球科學(xué)學(xué)院，湖北 武漢 430100

?

道路網(wǎng)多特征匹配優(yōu)化算法

付仲良1,2，楊元維1，高賢君3，趙星源1，范亮1

1. 武漢大學(xué)遙感信息工程學(xué)院，湖北 武漢 430079； 2. 地球空間信息技術(shù)協(xié)同創(chuàng)新中心，湖北 武漢 430079； 3. 長(zhǎng)江大學(xué)地球科學(xué)學(xué)院，湖北 武漢 430100

Foundationsupport：TheNationalNaturalScienceFoundationofChina(Nos. 41561084; 41201409; 41201395);TheNaturalScienceFoundationofShandongProvince(No.ZR2014DL001)

同名道路匹配技術(shù)是道路數(shù)據(jù)集成、更新和融合的重要前提。道路網(wǎng)匹配在智能交通(intelligenttransportationsystem，ITS)與位置服務(wù)(location-basedservice，LBS)等方面具有重要的研究?jī)r(jià)值和應(yīng)用意義。本文提出了一種道路網(wǎng)多特征匹配優(yōu)化算法：首先從形狀、距離、語(yǔ)義3方面分別設(shè)計(jì)了基于面積累積的形狀差、綜合中值Hausdorff距離和全局加權(quán)屬性項(xiàng)距離3種相似性度量，以更準(zhǔn)確地描述道路待匹配對(duì)之間的特征差異；然后通過(guò)SVM對(duì)相似性特征樣本集訓(xùn)練，以構(gòu)建道路網(wǎng)回歸匹配模型；最后利用此模型對(duì)未知匹配結(jié)果道路待匹配對(duì)進(jìn)行匹配結(jié)果預(yù)測(cè)。大量試驗(yàn)結(jié)果表明，本文算法對(duì)非線性偏差明顯的道路網(wǎng)數(shù)據(jù)能夠?qū)崿F(xiàn)較高的匹配準(zhǔn)確率和召回率，能有效地用于包含多重匹配關(guān)系的道路網(wǎng)匹配。

道路網(wǎng)匹配；支持向量機(jī)；中值Hausdorff距離；回歸模型

矢量匹配技術(shù)是數(shù)據(jù)融合、變化檢測(cè)、數(shù)據(jù)更新等必不可少的關(guān)鍵技術(shù)，道路網(wǎng)匹配是矢量匹配的研究熱點(diǎn)之一。目前，對(duì)道路網(wǎng)匹配方法的研究多集中在相似性度量和匹配策略兩個(gè)方面。在相似性度量方面，主要以道路實(shí)體的幾何特征(形狀[1]、距離[2-4]、方向[5])、拓?fù)涮卣鱗6-7]、語(yǔ)義特征[8-9]作為相似性特征描述。幾何特征中的形狀描述多用于面實(shí)體整體特征，文獻(xiàn)[1]針對(duì)線實(shí)體進(jìn)行構(gòu)面后再采用多級(jí)弦長(zhǎng)的方式描述，但僅適用于形狀變化劇烈的曲線；距離是較好描述線實(shí)體的特征，L2距離[2]與改進(jìn)Hausdorff距離[3-4]在描述道路待匹配對(duì)之間距離上有很大進(jìn)步，但其處理復(fù)雜線實(shí)體的能力有限；方向描述方法多基于節(jié)點(diǎn)或虛擬節(jié)點(diǎn)之間的局部角度差異，缺乏整體方向相似性的描述方面的研究；拓?fù)涮卣鞅磉_(dá)實(shí)體的拓?fù)潢P(guān)系，文獻(xiàn)[7]提出利用拓?fù)潢P(guān)系進(jìn)網(wǎng)狀要素匹配算法，該算法中微小的拓?fù)洳町惪赡苤率蛊ヅ涫。徽Z(yǔ)義特征的運(yùn)用依賴(lài)于數(shù)據(jù)質(zhì)量和屬性項(xiàng)的完整情況，普適性受到一定的約束。

在道路匹配策略方面，主要采用特征權(quán)值組合與閾值選取[10-11]、概率理論[12]、蟻群算法[13]、概率松弛法[14-15]、最優(yōu)化[3]和迭代邏輯回歸[16]模型等策略獲取匹配結(jié)果。權(quán)值組合與閾值選取法雖能很好的解決匹配問(wèn)題，但權(quán)值、閾值的確定都依賴(lài)于經(jīng)驗(yàn)值，自適應(yīng)能力偏差；概率理論法避免了閾值的選取問(wèn)題，但該方法計(jì)算量較大，增加了匹配結(jié)果對(duì)權(quán)值選取的敏感度；文獻(xiàn)[14—15]均采用概率松弛法求解向量相似性矩陣獲得匹配結(jié)果，其算法結(jié)構(gòu)復(fù)雜且計(jì)算量偏大；最優(yōu)化和迭代邏輯回歸模型具有人工干預(yù)少的優(yōu)點(diǎn)，但實(shí)際應(yīng)用于匹配時(shí)，需考慮數(shù)據(jù)分塊以控制算法耗時(shí)。針對(duì)上述問(wèn)題，本文提出一種道路網(wǎng)多特征優(yōu)化算法，首先設(shè)計(jì)了基于面積累積的形狀差、綜合中值Hausdorff距離和全局加權(quán)屬性項(xiàng)距離3種相似性特征，然后將此3項(xiàng)特征與SVM算法結(jié)合進(jìn)行模型訓(xùn)練，構(gòu)建道路網(wǎng)回歸匹配模型，實(shí)現(xiàn)道路網(wǎng)的有效匹配。

1　道路匹配對(duì)相似性描述

1.1基于面積累積的形狀差

利用累積計(jì)算在差異描述中的作用[5]，本文設(shè)計(jì)了基于面積累積的形狀差，即通過(guò)線對(duì)象之間形成封閉區(qū)域的面積累積大小來(lái)度量?jī)烧咝螤畈町?。結(jié)合圖1所示，其基本思想：首先較短線對(duì)象(lA)向較長(zhǎng)對(duì)象(lB)平移，使lA、lB的首節(jié)點(diǎn)N1和N1′重合(圖1(a)至圖1(b)的過(guò)程)，以lB首節(jié)點(diǎn)N1′為起點(diǎn)，在lB上取等長(zhǎng)于lA的點(diǎn)Ne，將lA的尾節(jié)點(diǎn)7N4與lB中的Ne連接形成封閉區(qū)域(如圖1中陰影區(qū)域D1和D2)；然后對(duì)該區(qū)域進(jìn)行面積累積計(jì)算。

圖1　道路待匹配對(duì)之間的形狀差示意圖　Fig.1　Diagram of shape differences between road corresponding matching pairs

lA與lB基于面積累積的形狀差Orn(lA,lB)即為封閉區(qū)域的多邊形面積積分，如下

(1)

只需要確保每一線對(duì)象及其子對(duì)象具有統(tǒng)一的方向走勢(shì)，且不同線對(duì)象走勢(shì)應(yīng)相反以形成封閉區(qū)域即可，可解除對(duì)線方向的約束，加強(qiáng)對(duì)整體差異的描述。如圖1所示的箭頭方向，設(shè)以逆時(shí)針?lè)较虻姆e分結(jié)果為正，則封閉區(qū)域D1和D2的積分結(jié)果分別為正和負(fù)，兩值求和起到一定的抵消作用，與道路形狀差異描述中關(guān)注整體的描述原則契合。式(1)中直接進(jìn)行面積積分計(jì)算過(guò)于復(fù)雜，本文引入格林公式將函數(shù)的面積分轉(zhuǎn)換為沿封閉區(qū)域邊界線積分從而降低計(jì)算難度。多封閉區(qū)域格林公式為

(2)

式中，n為組成封閉區(qū)域ξ的線段數(shù)量；Li(i=0,1,2,…n)為組成封閉區(qū)域的第i條線段。

將二元積分轉(zhuǎn)化為單元積分，設(shè)式(2)中P=y、Q=0，令第i條組成線段Li的斜率為ki，則有直線方程y=kix+bi。將其帶入式(2)中并結(jié)合式(1)可得道路待匹配對(duì)之間封閉區(qū)域D1、D2面積累積計(jì)算公式為

(3)

式中，xi為L(zhǎng)i線段的x坐標(biāo)。

1.2綜合中值Hausdorff距離

Hausdorff距離常用于描述線對(duì)象之間的距離相似性，由于其取極值原理，致使無(wú)法有效表達(dá)線對(duì)象之間的平均距離。中值Hausdorff距離能較好表達(dá)線對(duì)象之間的距離分布主趨勢(shì)[4]，但不適用于線對(duì)象之間長(zhǎng)度差異較大的情況，而文獻(xiàn)[16]提出的較短中值Hausdorff距離(shorted median Hausdorff distance，SM_HD)通過(guò)從較短線對(duì)象到較長(zhǎng)線對(duì)象的有向距離解決了這一問(wèn)題，但其未考慮垂足不在對(duì)應(yīng)的線段上時(shí)造成的距離不準(zhǔn)確問(wèn)題。因此，本文提出一種以歐氏距離和垂直距離為基礎(chǔ)的綜合中值Hausdorff距離(mixed median Hausdorff distance，MM_HD)，是通過(guò)對(duì)較短線對(duì)象到較長(zhǎng)線對(duì)象的有向綜合距離取舍、計(jì)算、排序，并從中選取中值距離。其基本思想是：做較短線對(duì)象中節(jié)點(diǎn)到較長(zhǎng)線對(duì)象的垂線，若垂足點(diǎn)位于長(zhǎng)線對(duì)象的線段上，則采用垂直距離；若位于其延長(zhǎng)線上，則采用歐氏距離。這樣可有效避免單純垂線計(jì)算時(shí)造成距離錯(cuò)誤情況的發(fā)生。其計(jì)算公式為

MM_HD(lA,lB)=

(4)

式中，length(lA)和length(lB)分別表示道路線對(duì)象lA和lB的長(zhǎng)度；m(lB,lA)、m(lA,lB)分別為lB到lA、lA到lB的綜合中值Hausdorff距離，計(jì)算公式分別為

m(lB,lA)=

(5)

m(lA,lB)=

(6)

1.3全局加權(quán)屬性項(xiàng)距離

目前，大多數(shù)語(yǔ)義相似性度量方法是基于單一屬性項(xiàng)進(jìn)行屬性信息相關(guān)性匹配[17-18]，易導(dǎo)致匹配結(jié)果會(huì)過(guò)于依賴(lài)此屬性項(xiàng)。因此，本文提出一種全局加權(quán)屬性項(xiàng)距離，步驟是：選取道路待匹配數(shù)據(jù)集中所有具有對(duì)應(yīng)關(guān)系的屬性項(xiàng)，并按顯著性等級(jí)比例系數(shù)對(duì)各屬性項(xiàng)權(quán)值進(jìn)行分配，再根據(jù)屬性項(xiàng)內(nèi)容差異及對(duì)應(yīng)權(quán)值計(jì)算獲得全局加權(quán)屬性項(xiàng)距離公式為

(7)

式中，M為lA與lB中具有可比性屬性項(xiàng)的數(shù)量；Ak(lA,lB)表示均存在于lA與lB中的第k個(gè)屬性項(xiàng)；sim{Ak(lA,lB)}表示第k個(gè)屬性項(xiàng)的語(yǔ)義相似性，wk表示第k個(gè)屬性項(xiàng)的權(quán)值，Smn(lA,lB)表示lA與lB之間的全局加權(quán)屬性項(xiàng)距離。

矢量數(shù)據(jù)屬性項(xiàng)類(lèi)型可歸為兩類(lèi)：數(shù)字和文本。對(duì)于道路矢量數(shù)據(jù)，數(shù)字類(lèi)型一般包括道路的寬度、長(zhǎng)度等；文本類(lèi)型包括道路的名稱(chēng)、級(jí)別、編碼等。本文具體采用編輯距離來(lái)表達(dá)文本類(lèi)型屬性項(xiàng)語(yǔ)義差異，該距離是指從原字符串轉(zhuǎn)換到目標(biāo)字符串所需要的最少的字符插入、刪除和替換的編輯次數(shù)[19]；并通過(guò)數(shù)值大小比較表達(dá)數(shù)字類(lèi)型屬性項(xiàng)的語(yǔ)義差異。屬性項(xiàng)語(yǔ)義相似性計(jì)算公式為

(8)

式中，Ak(lA)與Ak(lB)分別表示第k個(gè)屬性項(xiàng)的值，當(dāng)Ak(lA)與Ak(lB)不為空且為字符串時(shí)，Ed{Ak(lA),Ak(lB)}表示兩者編輯距離，MaxLen(Ak(lA),Ak(lB))表示獲取字符串較長(zhǎng)者；當(dāng)Ak(lA)與Ak(lB)不為空且為數(shù)字，|Ak(lA)-Ak(lB)|表示兩者差值的絕對(duì)值，MaxCount(Ak(lA),Ak(lB))表示獲取數(shù)值較大者。

2　SVM回歸匹配模型

判定道路網(wǎng)待匹配對(duì)之間是否匹配可被視為一種分類(lèi)問(wèn)題，SVM是一種基于統(tǒng)計(jì)學(xué)習(xí)理論的二分類(lèi)模型，分類(lèi)是一種特殊的回歸。本文求解待匹配對(duì)之間的最優(yōu)分類(lèi)函數(shù)為

(9)

本文將核函數(shù)設(shè)置為RBF類(lèi)型，特征維數(shù)為3，分別為基于面積累積的形狀差、綜合中值Hausdorff距離、全局加權(quán)屬性項(xiàng)距離。通過(guò)選取訓(xùn)練樣本，統(tǒng)計(jì)N條待匹配對(duì)的3種相似性特征值，可構(gòu)建包含N個(gè)樣本的輸入向量(x1,x2,x3,…,xN)，通過(guò)訓(xùn)練可求取最優(yōu)解和分類(lèi)閾值等帶入式(9)中確定分類(lèi)函數(shù)，即可構(gòu)建相應(yīng)的SVM回歸匹配模型。在此模型基礎(chǔ)上進(jìn)行道路匹配判別時(shí)，按照SVM最優(yōu)分類(lèi)規(guī)則進(jìn)行分類(lèi)，僅需輸入任一道路待匹配對(duì)的三維特征數(shù)據(jù)到分類(lèi)函數(shù)中求解I(x)，所得結(jié)果只有兩種，即為{1,-1}，分別表示此測(cè)試數(shù)據(jù)對(duì)應(yīng)的道路匹配對(duì)的匹配結(jié)果為{匹配，不匹配}。

3　試驗(yàn)與分析

本文從相似性特征的描述能力和基于SVM回歸模型的道路網(wǎng)匹配兩方面進(jìn)行對(duì)比試驗(yàn)驗(yàn)證與分析。

3.1相似性特征描述能力測(cè)試對(duì)比分析

3.1.1基于面積累積的形狀差對(duì)比試驗(yàn)

選取兩份形狀相對(duì)較難分辨的相鄰比例尺的鄉(xiāng)村道路網(wǎng)數(shù)據(jù)，如圖2所示兩份數(shù)據(jù)之間存在明顯的非線性差異，將面積累積形狀差與文獻(xiàn)[5]中的角度累積形狀差進(jìn)行對(duì)比試驗(yàn)，結(jié)果如表1所示。

Orn(a,b)和ADir(a,b)分別表示面積累積和角度累積[5]的計(jì)算值。從表1中可以看出，待匹配對(duì)a16∶b6在4個(gè)不匹配對(duì)的Orn(a16,b6)和ADir(a16,b6)最大，這符合a16∶b6相對(duì)于其他不匹配對(duì)a14∶b3、a8∶b9、a3∶b10的形狀差異最大的事實(shí)；在待匹配對(duì)中，兩對(duì)的形狀結(jié)構(gòu)相似，但局部特征差異相對(duì)較大的a1∶b1、a8∶b8其面積累積的計(jì)算值均小于角度累積的值，說(shuō)明面積累積在處理鋸齒線形狀的描述能力要優(yōu)于文獻(xiàn)[5]中的方法。且本文面積累積法形狀描述也能夠處理1對(duì)多的匹配類(lèi)型(表1中a12∶b5、a13∶b5)。表中兩組樣本的方差分別是0.12和0.09，方差越大說(shuō)明其描述能力越強(qiáng)，說(shuō)明其形狀描述能力比文獻(xiàn)[5]中的角度累積法強(qiáng)。

圖2　形狀差異測(cè)試數(shù)據(jù)圖Fig.2　Diagram of shape differences between two data sets

表1　面積累積和角度累積形狀差結(jié)果表

注：數(shù)據(jù)均已歸一化處理，粗體顯示為不匹配對(duì)及其對(duì)應(yīng)值。

3.1.2綜合中值Hausdorff距離對(duì)比試驗(yàn)

對(duì)如圖3所示的測(cè)試數(shù)據(jù)采用文獻(xiàn)[16]中提出的SM_HD與本文提出的MM_HD分別進(jìn)行距離對(duì)比，部分待匹配對(duì)結(jié)果如圖4所示?？梢钥闯?，在圖中大部分待匹配對(duì)的距離描述上，兩者的描述能力相當(dāng)。但在部分待匹配對(duì)上存在明顯的差異：從兩組不匹配對(duì)a1∶b9和a7∶b4的距離結(jié)果MM_HD(a1,b9)=23.42，SM_HD(a1,b9)=5.75；MM_HD(a7,b4)=11.87，SM_HD(a7,b4)=4.64可以得出；其SM_HD和MM_HD的距離表達(dá)差異相差較大，相對(duì)較小的SM_HD距離的a1∶b9和a7∶b4可能在匹配預(yù)測(cè)時(shí)被錯(cuò)分為真匹配；而MM_HD可有效避免這種情況的發(fā)生，原因是MM_HD顧及了待匹配對(duì)中對(duì)象A的節(jié)點(diǎn)到對(duì)象B的線段做垂線在其延長(zhǎng)線時(shí)可能出現(xiàn)的錯(cuò)分情況，從而使MM_HD在區(qū)分錯(cuò)誤匹配的能力上要強(qiáng)于SM_HD。

圖3　距離測(cè)試數(shù)據(jù)圖Fig.3　Diagram of distances between two data sets

圖4　SM_HD與MM_HD的距離特征對(duì)比圖Fig.4　Roads of the distance values between the matching pairs using the SM_HD and MM_HD

3.1.3全局加權(quán)屬性項(xiàng)距離對(duì)比試驗(yàn)

本試驗(yàn)數(shù)據(jù)選自同一地區(qū)不同來(lái)源的道路網(wǎng)屬性數(shù)據(jù)，表2、表3分別是兩個(gè)對(duì)應(yīng)數(shù)據(jù)集中部分實(shí)體屬性數(shù)據(jù)，本文選取在語(yǔ)義差異描述方面具有代表性的復(fù)合編輯距離[20]和語(yǔ)義樹(shù)距離[10]等兩種距離與本文提出的語(yǔ)義距離進(jìn)行對(duì)比試驗(yàn)。前兩種距離均選取道路名稱(chēng)“Name”屬性進(jìn)行比較，給定的表4中屬性項(xiàng)權(quán)值依次是0.27、0.17、0.27、0.13、0.16，判定是否為同一對(duì)象的閾值為0.15。3種距離的對(duì)比結(jié)果如表4所示。

表2　試驗(yàn)數(shù)據(jù)1屬性信息

表3　試驗(yàn)數(shù)據(jù)2屬性信息

表4　3種算法語(yǔ)義差異結(jié)果表

注：粗體顯示為不匹配對(duì)及其對(duì)應(yīng)值。

從表4中可看出，待匹配對(duì)a9∶b9中屬性項(xiàng)“Name”的值分別為“三緯路”和“二緯路”，屬性項(xiàng)“Way”的值分別為“T”和“F”，3種距離均能成功區(qū)分兩者為不匹配。而不匹配對(duì)a3∶b4、a3∶b5、a4∶b4的復(fù)合編輯距離和語(yǔ)義樹(shù)距離與其他匹配對(duì)(如a2∶b1)的計(jì)算值相同，導(dǎo)致被誤判為匹配，原因是兩種距離對(duì)道路網(wǎng)數(shù)據(jù)中道路名稱(chēng)相同時(shí)情況處理能力不足，未顧及屬性項(xiàng)“Way”中信息比較導(dǎo)致匹配錯(cuò)誤的發(fā)生。而它們的全局加權(quán)屬性項(xiàng)距離分別為0.16、0.173 7、0.174 3，均大于匹配閾值，能夠有效區(qū)分為不匹配。原因是本文提出的全局加權(quán)屬性項(xiàng)距離克服了文獻(xiàn)[20]和[10]中兩種距離過(guò)于依賴(lài)單一屬性項(xiàng)的問(wèn)題，且能夠綜合處理數(shù)字、文本類(lèi)型的屬性項(xiàng)信息。試驗(yàn)可得本文提出的全局加權(quán)屬性項(xiàng)距離的語(yǔ)義差異描述能力從整體上優(yōu)于其他兩種距離。

3.2SVM回歸匹配模型試驗(yàn)

3.2.1測(cè)試數(shù)據(jù)介紹

本文試驗(yàn)選取某省同一地區(qū)2014年基礎(chǔ)地理數(shù)據(jù)A和2008年導(dǎo)航數(shù)據(jù)B進(jìn)行算法試驗(yàn)(藍(lán)色為數(shù)據(jù)A)，兩份數(shù)據(jù)由于時(shí)間跨度較大，大量道路的幾何形狀和屬性信息發(fā)生變化，具有較好的匹配意義。數(shù)據(jù)A中包含2317個(gè)要素對(duì)象，數(shù)據(jù)B包含3606個(gè)要素對(duì)象。緩沖距離設(shè)為200 m。通過(guò)Microsoft Visual Studio 2010(C#)和ArcGIS Engine 10.1實(shí)現(xiàn)道路待匹配對(duì)之間的相似性計(jì)算；并通過(guò)Matlab R2010b實(shí)現(xiàn)樣本訓(xùn)練、構(gòu)建SVM回歸匹配模型以及預(yù)測(cè)匹配結(jié)果。

首先對(duì)相似性特征數(shù)據(jù)進(jìn)行格式調(diào)整和歸一化等預(yù)處理；其次將數(shù)據(jù)劃分為訓(xùn)練集和測(cè)試集兩個(gè)子集，通過(guò)對(duì)訓(xùn)練集數(shù)據(jù)進(jìn)行訓(xùn)練以構(gòu)建SVM回歸匹配模型；然后依據(jù)此模型對(duì)測(cè)試集數(shù)據(jù)的匹配結(jié)果進(jìn)行預(yù)測(cè)。其中，從相似性特征數(shù)據(jù)中選取訓(xùn)練集數(shù)據(jù)時(shí)，需考慮被選取樣本數(shù)據(jù)的普遍性、全面性、數(shù)量均衡性等方面。從而為構(gòu)建SVM匹配模型提供最佳訓(xùn)練樣本數(shù)據(jù)，保證分類(lèi)精度。同樣的，測(cè)試集也應(yīng)當(dāng)包含了各種類(lèi)型的道路網(wǎng)待匹配對(duì)的特征數(shù)據(jù)，以更為準(zhǔn)確的評(píng)判匹配模型的區(qū)分能力。

如表5所示，列出了部分?jǐn)?shù)據(jù)的3個(gè)相似性特征值、實(shí)際匹配結(jié)果和預(yù)測(cè)匹配結(jié)果。

表5　圖5中的部分道路相似性特征值及匹配結(jié)果

注：待匹配對(duì)(matching pairs, MP)、實(shí)際匹配結(jié)果(real matched result，RMR)、預(yù)測(cè)匹配結(jié)果(predict matched result, PMR)，表中特征數(shù)據(jù)均已歸一化處理。

對(duì)表5統(tǒng)計(jì)，本文算法的整體匹配準(zhǔn)確率是93.0%。從表5可以看出，除a18∶b2以外，其他待匹配對(duì)的實(shí)際匹配結(jié)果與預(yù)測(cè)匹配結(jié)果相同，匹配效果良好。a18∶b2匹配錯(cuò)誤的原因是形狀差和距離值不足以對(duì)其進(jìn)行不匹配的劃分。a2∶b2的Orn(a2,b2)=0.096 7，相對(duì)于形狀差異較小的匹配對(duì)(如Orn(a1,b1)=0.005 5和Orn(a3,b3)=0.033 2)要大許多，但相對(duì)于形狀差異巨大的不匹配對(duì)(如Orn(a10,b5)=0.478 2和Orn(a9,b11)=0.540 1)要小很多，說(shuō)明基于面積累積形狀差具有良好的區(qū)分性。類(lèi)似的情況還有a20∶b21存在一部分的形狀很相似的情況(圖5(b)所示)，但Orn(a20,b21)=0.790 2很容易區(qū)分其形狀差異。a11∶b11和a18∶b1的距離值分別為0.136 4與0.058，可以看出兩個(gè)待匹配對(duì)之間地圖偏移距離不同(圖5(a))，說(shuō)明本文提出的綜合中值Hausdorff距離能夠很好描述非線性偏差情況下線對(duì)象之間的距離。另外，形狀差異不大的待匹配對(duì)a14∶b7，其MM_HD(a14,b7)=0.767 9，Smn(a14,b7)=0.467 4均是較大值，使得綜合中值Hausdorff距離和全局加權(quán)屬性項(xiàng)距離可進(jìn)一步用于區(qū)分僅依據(jù)面積累積的形狀差無(wú)法區(qū)分的待匹配對(duì)，三者相互補(bǔ)充，以更全面地衡量對(duì)象差異。

3.2.2算法對(duì)比試驗(yàn)分析

本文的道路網(wǎng)匹配算法設(shè)計(jì)中，在相似性特征和匹配算法兩個(gè)部分均做了改進(jìn)，為驗(yàn)證各部分在匹配精度提升上的貢獻(xiàn)差異，選取logistic回歸模型和文獻(xiàn)[16]中的SM_HD特征進(jìn)行兩兩組合試驗(yàn)(如表6中第2、3列所示)，測(cè)試數(shù)據(jù)仍然為數(shù)據(jù)A和數(shù)據(jù)B，表6中f(C)、f(W)和f(U)分別表示正確匹配、錯(cuò)誤匹配和漏匹配的數(shù)量，P、R和耗時(shí)分別為準(zhǔn)確率、召回率和算法耗時(shí)方面的比較結(jié)果。

圖5　匹配實(shí)例Fig.5　Matching examples

表6　算法比較

分析表6可得，本文算法(第3組合)由于對(duì)道路網(wǎng)匹配采用了3種較好的相似性描述方法和SVM回歸匹配算法，在匹配準(zhǔn)確率P和回歸率R均優(yōu)于其他3種組合。其中，第3組合相比于第1組合的優(yōu)勢(shì)較小，說(shuō)明本文提出的相似性特征比匹配模型的貢獻(xiàn)大。本文算法相比于文獻(xiàn)[16]算法(第2組合)在匹配準(zhǔn)確率P和回歸率R上有了一定的提升，說(shuō)明本文算法比文獻(xiàn)[16]算法中單純采用SM_HD特征與logistic回歸模型對(duì)道路網(wǎng)匹配更加有效。從組合2和組合4可以看出，基于SVM回歸匹配模型的匹配結(jié)果要優(yōu)于基于logistic回歸匹配模型。原因是SVM尋求最優(yōu)超平面的原理，雖然使得其復(fù)雜度稍高于logistic回歸，導(dǎo)致更耗時(shí)，但在分類(lèi)精度要更高，與優(yōu)化的3種相似性特征結(jié)合，在道路網(wǎng)匹配中能實(shí)現(xiàn)高精度的匹配。

4　結(jié)　論

本文通過(guò)設(shè)計(jì)3種有效的道路相似性特征，并結(jié)合SVM回歸模型構(gòu)建具有高精度的道路網(wǎng)匹配模型。通過(guò)試驗(yàn)論證，得出以下結(jié)論：①多特征的優(yōu)化不僅使得每個(gè)相似性特征具有較強(qiáng)的特征差異描述能力，三者結(jié)合可實(shí)現(xiàn)差異互補(bǔ)，整體具有更強(qiáng)的識(shí)別能力。再結(jié)合區(qū)分能力強(qiáng)的SVM分類(lèi)算法，使得構(gòu)建的道路網(wǎng)匹配模型的匹配精度和召回率更高。②無(wú)須設(shè)定相似性特征之間權(quán)值和匹配閾值，使得匹配算法自動(dòng)化水平得到一定提升。

本文算法仍存在定的不足之處：基于面積累積的形狀差方法對(duì)局部差異描述的能力相對(duì)較弱；SVM回歸匹配模型算法復(fù)雜度較高，使得耗時(shí)較長(zhǎng)，降低了匹配效率。這些問(wèn)題將是下一步研究的重點(diǎn)。

[1]安曉亞,孫群,肖強(qiáng),等.一種形狀多級(jí)描述方法及在多尺度空間數(shù)據(jù)幾何相似性度量中的應(yīng)用[J]. 測(cè)繪學(xué)報(bào), 2011, 40(4): 495-501, 508.

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-501, 508.

[2]SAALFELD A. Conflation Automated Map Compilation[J]. International Journal of Geographical Information Systems, 1988, 2(3): 217-228.

[3]LI Linna, GOODCHILD M F. An Optimisation Model for Linear Feature Matching in Geographical Data Conflation[J]. International Journal of Image and Data Fusion, 2011, 2(4): 309-328.

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

[5]YANG Bisheng, ZHANG Yunfei, LUAN Xuechen. A Probabilistic Relaxation Approach for Matching Road Networks[J]. International Journal of Geographical Information Science, 2013, 27(2): 319-338.

[6]SAFRA E, KANZA Y, SAGIV Y, et al.AdHocMatching of Vectorial Road Networks[J]. International Journal of Geographical Information Science, 2013, 27(1): 114-153.

[7]安曉亞, 孫群, 尉伯虎. 利用相似性度量的不同比例尺地圖數(shù)據(jù)網(wǎng)狀要素匹配算法[J]. 武漢大學(xué)學(xué)報(bào)(信息科學(xué)版), 2012, 37(2): 224-228, 241.

AN Xiaoya, SUN Qun, YU Bohu. Feature Matching from Network Data at Different Scales Based on Similarity Measure[J]. Geomatics and Information Science of Wuhan University, 2012, 37(2): 224-228, 241.

[10]羅國(guó)瑋, 張新長(zhǎng), 齊立新, 等. 矢量數(shù)據(jù)變化對(duì)象的快速定位與最優(yōu)組合匹配方法[J]. 測(cè)繪學(xué)報(bào), 2014, 43(12): 1285-1292. DOI: 10.13485/j.cnki.11-2089.2014.0191.

LUO Guowei, ZHANG Xingchang, QI Lixin, et al. The Fast Positioning and Optimal Combination Matching Method of Change Vector Object[J]. Acta Geodaetica et Cartographica Sinica, 2014, 43(12): 1285-1292. DOI: 10.13485/j.cnki.11-2089.2014.0191.

[11]欒學(xué)晨, 楊必勝, 李秋萍. 基于結(jié)構(gòu)模式的道路網(wǎng)節(jié)點(diǎn)匹配方法[J]. 測(cè)繪學(xué)報(bào), 2013, 42(4): 608-614. LUAN Xuechen, YANG Bisheng, LI Qiuping. Pattern-based Node Matching Approach for Road Networks[J]. Acta Geodaetica et Cartographica Sinica, 2013, 42(4): 608-614.

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

[13]鞏現(xiàn)勇, 武芳, 姬存?zhèn)? 等. 道路網(wǎng)匹配的蟻群算法求解模型[J]. 武漢大學(xué)學(xué)報(bào)(信息科學(xué)版), 2014, 39(2): 191-195.

GONG Xianyong,WU Fang,JI Cunwei,et al.Ant Colony Optimization Approach to Road Network Matching[J]. Geomatics and Information Science of Wuhan University, 2014, 39(2): 191-195.

[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]趙東保, 盛業(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.

[16]TONG Xiaohua, LIANG Dan, JIN Yanmin. A Linear Road Object Matching Method for Conflation Based on Optimization and Logistic Regression[J]. International Journal of Geographical Information Science, 2014, 28(4): 824-846.

[17]YUAN Shuxin, TAO Chuang. Development of Conflation Components[C]∥Proceedings of Geoinformatics’99 Conference. Ann Arbor: [s.n.], 1999: 1-13.

[18]VOLZ S. An Iterative Approach for Matching Multiple Representations of Street Data[C]∥Proceedings of the ISPRS Workshop on Multiple Representation and Interoperability of Spatial Data. Hanover: ISPRS, 2006: 101-110.

[19]NAVARRO G. A Guided Tour to Approximate String Matching[J]. ACM Computing Surveys, 2001, 33(1): 31-88.

[20]刁興春, 譚明超, 曹建軍. 一種融合多種編輯距離的字符串相似度計(jì)算方法[J]. 計(jì)算機(jī)應(yīng)用研究, 2010, 27(12): 4523-4525.

DIAO Xingchun, TAN Mingchao, CAO Jianjun. New Method of Character String Similarity Compute Based on Fusing Multiple Edit Distances[J]. Application Research of Computers, 2010, 27(12): 4523-4525.

(責(zé)任編輯：宋啟凡)

FU Zhongliang(1965—), male, PhD, professor, PhD supervisor, majors in GIS, vector data matching.

AnOptimizationAlgorithmforMulti-characteristicsRoadNetworkMatching

FUZhongliang1,2,YANGYuanwei1,GAOXianjun3,ZHAOXingyuan1,FANLiang1

1.SchoolofRemoteSensingandInformationEngineering,WuhanUniversity,Wuhan430079,China; 2.CollaborativeInnovationCenterofGeospatialTechnology,Wuhan430079,China; 3.SchoolofGeosciences,YangtzeUniversity,Wuhan430100,China

Identifyinghomonymousroadobjectsisacrucialprerequisitetotheintegration,updatingandfusionofroaddata.Roadnetworksmatchingisofgreattheoreticalresearchvalueandpracticalsignificanceinaspectofintelligenttransportationsystemandlocation-basedService.Thispaperproposedanoptimizationalgorithmformulti-characteristicsroadnetworkmatching.Designedfromshape,distanceandsemanticsaspects,threesimilaritycharacteristics—shapedifferencesbasedonareaaccumulated,mixedmedianHausdorffdistanceanddistancewithglobalweightedattributes,describedcandidatecorrespondingpairsmoreaccurately.Then,thematchingregressionmodelcouldbethenconstructedbytrainingthesimilaritysamplessetthroughSVMalgorithm.Finally,theconstructedmodelcanbeusedtopredictwhethertheroadmatchingpairswerematched.Agreatnumberofexperimentsshowthatthealgorithmachievesarobustmatchingprecisionandrecallevenforroadnetworksdatawithapparentnon-rigiddeviation.Andtheproposedmethodcanbeeffectivelyappliedforroadnetworksmatchingwithmultiplematchingrelationship.

roadnetworksmatching;SVM;medianHausdorffdistance;regressionmodel

2015-07-21

2016-03-10

付仲良(1965—)，男，博士，教授，博士生導(dǎo)師，主要研究方向?yàn)镚IS、矢量數(shù)據(jù)匹配。

E-mail： fuzhl@263.net

楊元維

YANG Yuanwei

E-mail： yyw_08@whu.edu.com

FUZhongliang,YANGYuanwei,GAOXianjun,etal.AnOptimizationAlgorithmforMulti-characteristicsRoadNetworkMatching[J].ActaGeodaeticaetCartographicaSinica,2016,45(5):608-615.DOI:10.11947/j.AGCS.2016.20150388.

P208

A

1001-1595(2016)05-0608-08

國(guó)家自然科學(xué)基金(41561084; 41201409; 41201395)；山東省自然科學(xué)基金(ZR2014DL001)

引文格式：付仲良，楊元維，高賢君，等.道路網(wǎng)多特征匹配優(yōu)化算法[J].測(cè)繪學(xué)報(bào)，2016,45(5)：608-615.DOI:10.11947/j.AGCS.2016.20150388.