基于圖卷積神經(jīng)網(wǎng)絡(luò)的道路網(wǎng)匹配

齊 杰,王中輝,李驛言

(1. 蘭州交通大學(xué)測繪與地理信息學(xué)院,甘肅 蘭州 730070; 2. 地理國情監(jiān)測技術(shù)應(yīng)用國家地方聯(lián)合工程研究中心,甘肅 蘭州 730070;3. 甘肅省地理國情監(jiān)測工程實驗室,甘肅 蘭州 730070)

數(shù)字化的道路數(shù)據(jù)是對實體道路的抽象化表達(dá),是基礎(chǔ)地理數(shù)據(jù)庫重要的組成部分[1]。隨著道路的不斷變化,道路網(wǎng)數(shù)據(jù)的快速更新成為一個亟待解決的問題,而道路網(wǎng)匹配是道路網(wǎng)數(shù)據(jù)變化檢測和增量式更新的前提與關(guān)鍵技術(shù),更是實現(xiàn)地圖自動綜合的必然要求。

道路網(wǎng)匹配一般通過計算道路的語義相似性和幾何相似性進(jìn)行匹配。基于語義相似性的匹配方法主要通過計算線要素之間的語義相似性進(jìn)行道路網(wǎng)匹配[2-4],很大程度上依賴于屬性信息的唯一性。而多源道路數(shù)據(jù)往往缺少具有唯一性的屬性信息,因此該方法只能用于輔助匹配。基于幾何相似性的匹配方法通過計算線要素之間的幾何相似性進(jìn)行道路網(wǎng)匹配[5-7]。幾何相似性包括方向、距離、形狀、拓?fù)潢P(guān)系等相似性度量指標(biāo),通常選取一種或多種相似性度量指標(biāo),確定指標(biāo)之間的權(quán)重組合,選擇合適的相似度匹配閾值,完成道路網(wǎng)的匹配。該方法通常采用主觀賦權(quán)法進(jìn)行相似性指標(biāo)權(quán)重組合和匹配閾值確定,對匹配結(jié)果具有較大影響。

圖卷積神經(jīng)網(wǎng)絡(luò)(GCN)是目前最常用的圖數(shù)據(jù)深度學(xué)習(xí)網(wǎng)絡(luò),具有自動提取局部空間特征的能力,從而減少了人工特征工程的構(gòu)建過程,實現(xiàn)了數(shù)據(jù)端到端的預(yù)測。目前,GCN在道路網(wǎng)模式識別領(lǐng)域得到了重要的應(yīng)用[8-9]。鑒于此,本文針對現(xiàn)有道路網(wǎng)匹配方法中相似性度量因子之間的權(quán)值分配和匹配閾值確定方法的不足,結(jié)合圖卷積神經(jīng)網(wǎng)絡(luò),提出一種道路網(wǎng)匹配方法。

1 圖卷積神經(jīng)網(wǎng)絡(luò)的基本原理

文獻(xiàn)[10]基于圖譜理論從卷積定理出發(fā),在譜空間定義圖卷積,首次提出基于頻域的圖卷積神經(jīng)網(wǎng)絡(luò)。文獻(xiàn)[11]用切比雪夫展開多項式參數(shù)化卷積核,實現(xiàn)譜卷積神經(jīng)網(wǎng)絡(luò),從而避免拉普拉斯矩陣的特征分解,加速特征矩陣的求解。文獻(xiàn)[12]通過限制Cheb Net的圖卷積操作在一階鄰域內(nèi)執(zhí)行,大大提高了計算效率。

(1)

圖傅里葉的逆變換為

(2)

圖結(jié)構(gòu)數(shù)據(jù)的節(jié)點排列不均勻,鄰域結(jié)構(gòu)不固定,不能滿足平移不變性,無法定義節(jié)點域的卷積運算。模仿離散時間信號處理中的卷積借助傅里葉變換,將圖的卷積運算轉(zhuǎn)換為譜域中傅里葉變換的點乘運算,公式為

f*g=F-1[F(f)⊙F(g)]=Q[(QTg)⊙(QTf)]

(3)

式中,⊙為哈達(dá)瑪積,指兩個矩陣(或向量)的逐點乘積;f為特征函數(shù);g為卷積核。如果把QTg整體看作可學(xué)習(xí)的卷積核,記為gθ,則圖卷積公式為

σ=QgθQTf

(4)

基本的頻域卷積網(wǎng)絡(luò)要計算拉普拉斯矩陣所有的特征值和特征向量,計算量大。切比雪夫多項式(Chebyshev polynomials)可加速特征矩陣的求解。Cheb Net通過對拉普拉斯矩陣進(jìn)行泰勒展開定義圖濾波器,其卷積層定義為

(5)

通過K控制濾波器的復(fù)雜度,可極大地降低過擬合風(fēng)險。但是由于在進(jìn)行矩陣特征分解時具有較高的時間復(fù)雜度,計算效率低,因此在實際應(yīng)用中效率較低。

文獻(xiàn)[12]通過限制式(5)中的K=1,定義第l層的卷積運算,即

(6)

2 基于圖卷積神經(jīng)網(wǎng)絡(luò)的道路網(wǎng)匹配

將待匹配道路網(wǎng)數(shù)據(jù)轉(zhuǎn)化為對偶圖,利用對偶圖將道路構(gòu)建為圖結(jié)構(gòu)數(shù)據(jù),將節(jié)點所代表的兩條道路是否為匹配道路作為標(biāo)簽,輸入GCN模型中進(jìn)行訓(xùn)練,完成道路網(wǎng)的匹配。模型框架如圖1所示,主要包括以下步驟:①數(shù)據(jù)處理,對數(shù)據(jù)進(jìn)行預(yù)處理,確定待匹配道路的候選匹配集;②特征提取,選取長度相似性、距離相似性、方向相似性、拓?fù)湎嗨菩?個特征因子作為對偶圖節(jié)點的特征;③GCN學(xué)習(xí),先構(gòu)建對偶圖,并對道路網(wǎng)標(biāo)注標(biāo)簽,再以圖數(shù)據(jù)轉(zhuǎn)化后的對偶圖作為輸入數(shù)據(jù),利用卷積運算提取特征,通過反復(fù)迭代最終使模型達(dá)到收斂。

圖1 基于圖卷積神經(jīng)網(wǎng)絡(luò)的道路網(wǎng)匹配整體框架

2.1 數(shù)據(jù)處理

將獲取的數(shù)據(jù)利用ArcGIS進(jìn)行拓?fù)錂z測和屬性表檢查,對重復(fù)路段和孤立路段進(jìn)行刪除,統(tǒng)一兩個地圖數(shù)據(jù)的坐標(biāo)系。對可匹配道路進(jìn)行節(jié)點數(shù)量的檢查,為滿足后續(xù)對待匹配路段和參考路段進(jìn)行圖結(jié)構(gòu)構(gòu)建,需要在不影響道路整體結(jié)構(gòu)的前提下對道路進(jìn)行增加或刪除節(jié)點的處理,使節(jié)點的數(shù)量達(dá)到一致。利用緩沖區(qū)增長法確定待匹配道路的候選匹配集。

2.2 特征提取

為了度量待匹配的兩弧段的相似性,定義如下相似特征的度量指標(biāo),作為后續(xù)卷積運算的特征參量。

2.2.1 長度相似性

參考路段的幾何長度和待匹配路段的幾何長度的相似程度,公式為

(7)

式中,LA、LB為道路A、B的長度;min()為獲取最小值函數(shù);max()為獲取最大值函數(shù),余同。

2.2.2 距離相似性

參考路段與待匹配路段的距離相似程度,采用兩線要素之間的有向Hausdorff距離進(jìn)行計算,距離越近相似度越高。計算方法為,若待匹配道路A上的節(jié)點集合為P(p1,p2,…,pn),對于集合P上的任意一點pi(Xi,Yi),作點pi到參考道路B的垂線;若垂線與道路A相交,即垂足在道路B上,則采用垂直距離;若垂足不在道路B上,而在道路B的延長線上,則采用節(jié)點間的歐式距離[13]。距離相似性公式為

(8)

2.2.3 方向相似性

參考路段和待匹配路段在道路走向上的相似程度,采用方向角計算方向的相似程度,公式為

(9)

式中,Sori表示道路A、B方向相似度;OriA、OriB表示道路A、B的方向。

2.2.4 拓?fù)湎嗨菩?/p>

采用節(jié)點連通度對拓?fù)湎嗨菩赃M(jìn)行描述。節(jié)點的連通度即道路節(jié)點關(guān)聯(lián)弧段的數(shù)量[14],見表1。道路A、B的拓?fù)湎嗨贫瓤杀硎緸?/p>

表1 節(jié)點連通度示意

(10)

式中,CA、CB表示道路A、B收尾節(jié)點的連通度的和。

2.3 GCN學(xué)習(xí)

2.3.1 道路網(wǎng)對偶圖構(gòu)建

對道路網(wǎng)數(shù)據(jù)進(jìn)行預(yù)處理后,需要將道路網(wǎng)數(shù)據(jù)構(gòu)建為圖結(jié)構(gòu),使之符合圖卷積神經(jīng)網(wǎng)絡(luò)對輸入數(shù)據(jù)的結(jié)構(gòu)形式要求。現(xiàn)有的圖卷積方法都是針對節(jié)點的分類或圖分類,因此選擇道路作為節(jié)點,道路之間的連接關(guān)系作為邊,將道路網(wǎng)抽象為對偶圖。試驗在進(jìn)行道路網(wǎng)匹配時是在兩個數(shù)據(jù)集上進(jìn)行的計算,因此在進(jìn)行對偶圖構(gòu)建的過程中,將兩個數(shù)據(jù)集中待判斷是否匹配的道路抽象表示在一張對偶圖上,每個節(jié)點所提取的特征因子即為兩條道路之間的相似性度量。如圖2所示,將待匹配道路A和參考道路B抽象為一個對偶圖C。其中,C1為道路L1和道路M1所抽象的對偶圖節(jié)點,C1提取的特征因子即為道路L1和道路M1之間各相似性度量因子的計算值,C2和C3同理。因此,將道路網(wǎng)匹配問題轉(zhuǎn)化為節(jié)點的分類問題,輸出為0或1,0表示不能匹配道路,1表示可匹配道路。

2.3.2 圖卷積網(wǎng)絡(luò)模型構(gòu)建

道路網(wǎng)匹配任務(wù)的標(biāo)注、輸入和輸出如下。

(1)標(biāo)注:y∈{0,1}。標(biāo)簽值為1,則說明該對偶圖所對應(yīng)的兩條道路為匹配道路;反之,標(biāo)簽值為0,則說明該對偶圖所對應(yīng)的兩條道路為不匹配道路。

(2)輸入:將數(shù)據(jù)集轉(zhuǎn)化為對偶圖,把道路的路段作為圖的節(jié)點,連接關(guān)系作為圖的邊,最終得到的道路網(wǎng)圖模型G=(V,E,A)。每個圖模型都包含N個節(jié)點,每個節(jié)點都有4個計算特征值{f1,f2,f3,f4},分別對應(yīng)長度相似性、距離相似性、方向相似性、拓?fù)湎嗨菩浴Ｋ泄?jié)點構(gòu)成N×4的特征向量和一個N×N的鄰接矩陣。

模型分為輸入層、卷積層、輸出層3部分,如圖3所示。

3 試驗與分析

考慮不同地區(qū)自然地理環(huán)境和經(jīng)濟發(fā)展水平不同,其道路網(wǎng)類型也各有不同。當(dāng)前道路網(wǎng)的類型可以被歸納為方格網(wǎng)式、環(huán)狀放射式、自由式、混合式4種。為驗證本文方法的合理性和普適性,選取較為常見的方格網(wǎng)式道路和環(huán)狀放射道路,在同尺度和多尺度下進(jìn)行道路網(wǎng)匹配試驗。如圖4所示,方格網(wǎng)式道路共有1410條待匹配道路,環(huán)形放射式道路共有920條待匹配道路。將待匹配道路和參考道路構(gòu)建為對偶圖,完成標(biāo)注后作為試驗樣本。將試驗樣本按8∶2的比例劃分為訓(xùn)練樣本和測試樣本。

圖4 不同尺度下的兩種類型道路網(wǎng)

如圖5所示,選取不同卷積層數(shù)和不同的卷積核,所得到的匹配精度和曲線擬合速度不同。綜合分析,試驗最終使用的圖卷積模型由4個卷積層和1個輸出層組成,每個卷積層包含64個卷積核。將ReLU作為激活函數(shù)、Adam作為優(yōu)化器進(jìn)行參數(shù)更新,設(shè)置學(xué)習(xí)率為0.005,L2正則化參數(shù)為0.000 5。模型經(jīng)過400次迭代達(dá)到收斂,損失值基本不再發(fā)生變化。

為驗證模型的合理性和普適性,通過計算匹配的準(zhǔn)確率P和召回率R,評價道路網(wǎng)的匹配質(zhì)量[15],公式為

(11)

(12)

式中,S為道路總數(shù);M為存在匹配關(guān)系的道路數(shù)量;C為正確匹配的道路數(shù)量。

為了同時考慮道路網(wǎng)的匹配率和召回率,避免因匹配率和召回率相反變化引起的描述與評價不便,采用匹配準(zhǔn)確率和召回率的調(diào)和平均值F進(jìn)行結(jié)果的評價[16],公式為

(13)

式中,P為準(zhǔn)確率;R為召回率。

匹配試驗的迭代過程如圖6所示,同尺度方格網(wǎng)式道路、同尺度環(huán)狀放射道路,以及不同尺度方格網(wǎng)式道路、不同尺度環(huán)狀放射道路的匹配結(jié)果,具體見表2。

表2 不同試驗數(shù)據(jù)下道路網(wǎng)匹配結(jié)果

圖6 匹配試驗的損失與準(zhǔn)確度變化

對試驗結(jié)果進(jìn)行分析可知:

(1)兩種方法在同尺度下的匹配結(jié)果均優(yōu)于多尺度下的匹配結(jié)果。比例尺相同的兩幅地圖采集數(shù)據(jù)與制作地圖時的精度相同,特別是在環(huán)島、立交等較為復(fù)雜的道路上表現(xiàn)尤為明顯。在大比例尺數(shù)據(jù)中這部分道路被完整刻畫,而在小比例尺道路數(shù)據(jù)上會被簡化甚至刪除,這就造成在相同比例尺道路上能夠成功匹配的復(fù)雜道路在不同比例尺上極易產(chǎn)生輔路與主路無匹配的情況,從而導(dǎo)致在不同比例尺道路匹配的結(jié)果低于在相同比例尺道路上匹配的結(jié)果。

(2)同尺度下方格網(wǎng)式道路的匹配結(jié)果優(yōu)于環(huán)狀放射式道路的匹配結(jié)果。這是由于方格網(wǎng)式道路網(wǎng)中多為平行或垂直的直線型道路,結(jié)構(gòu)較為簡單,而環(huán)形道路網(wǎng)中曲線型道路數(shù)量較多,兩條可匹配道路之間部分路段的差異性較大,導(dǎo)致匹配結(jié)果產(chǎn)生誤差。而在多尺度下環(huán)狀結(jié)果卻優(yōu)于方格網(wǎng)式,對數(shù)據(jù)進(jìn)行統(tǒng)計分析發(fā)現(xiàn),方格網(wǎng)式道路中復(fù)雜道路尤其是環(huán)島類型路段的數(shù)量多于環(huán)狀道路,這使得最終的匹配結(jié)果出現(xiàn)了不同的變化。

(3)G1法的匹配率和召回率在同尺度方格網(wǎng)式道路數(shù)據(jù)中最高,分別達(dá)到88.79%和93.61%;在不同尺度環(huán)狀放射道路最低,只有86.19%、90.86%。這主要是由于G1法是一種主觀賦權(quán)法,主要依據(jù)專家的經(jīng)驗賦予各個相似性度量因子之間的權(quán)值,具有一定的主觀性。而GCN的方法中匹配率和召回率最低的也達(dá)到96.63%、98.68%,F值最低為97.69%,相較于G1法具有更好的匹配精度。

4 結(jié) 語

本文提出了一種基于圖卷積神經(jīng)網(wǎng)絡(luò)的道路網(wǎng)匹配方法,在進(jìn)行監(jiān)督分類學(xué)習(xí)后,利用反向傳播機制,自動調(diào)整權(quán)重和閾值,完成道路網(wǎng)的匹配。試驗結(jié)果表明,該方法具有以下優(yōu)勢:①可以自動對相似性度量因子進(jìn)行權(quán)重賦值,有效降低了由主觀賦值導(dǎo)致的匹配錯誤,提高了匹配精度;②可以自動確定匹配閾值,無須人為設(shè)定初始匹配閾值和經(jīng)過反復(fù)試驗調(diào)整閾值,提高了匹配效率。

但圖卷積神經(jīng)網(wǎng)絡(luò)疊加多層會出現(xiàn)過擬合現(xiàn)象,使模型產(chǎn)生退化,從而導(dǎo)致過于簡化的復(fù)雜路段的局部特征相似度較低,產(chǎn)生錯誤匹配的情況。下一步工作考慮采取殘差網(wǎng)絡(luò)等復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu),增加網(wǎng)絡(luò)深度,提高匹配精度。