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

齊 杰,王中輝,李驛言

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

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

道路網(wǎng)匹配一般通過計(jì)算道路的語義相似性和幾何相似性進(jìn)行匹配。基于語義相似性的匹配方法主要通過計(jì)算線要素之間的語義相似性進(jìn)行道路網(wǎng)匹配[2-4],很大程度上依賴于屬性信息的唯一性。而多源道路數(shù)據(jù)往往缺少具有唯一性的屬性信息,因此該方法只能用于輔助匹配。基于幾何相似性的匹配方法通過計(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)重組合和匹配閾值確定,對(duì)匹配結(jié)果具有較大影響。

圖卷積神經(jīng)網(wǎng)絡(luò)(GCN)是目前最常用的圖數(shù)據(jù)深度學(xué)習(xí)網(wǎng)絡(luò),具有自動(dòng)提取局部空間特征的能力,從而減少了人工特征工程的構(gòu)建過程,實(shí)現(xiàn)了數(shù)據(jù)端到端的預(yù)測(cè)。目前,GCN在道路網(wǎng)模式識(shí)別領(lǐng)域得到了重要的應(yīng)用[8-9]。鑒于此,本文針對(duì)現(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]用切比雪夫展開多項(xiàng)式參數(shù)化卷積核,實(shí)現(xiàn)譜卷積神經(jīng)網(wǎng)絡(luò),從而避免拉普拉斯矩陣的特征分解,加速特征矩陣的求解。文獻(xiàn)[12]通過限制Cheb Net的圖卷積操作在一階鄰域內(nèi)執(zhí)行,大大提高了計(jì)算效率。

(1)

圖傅里葉的逆變換為

(2)

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

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

(3)

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

σ=QgθQTf

(4)

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

(5)

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

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

(6)

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

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

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

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

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

2.2 特征提取

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

2.2.1 長(zhǎng)度相似性

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

(7)

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

2.2.2 距離相似性

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

(8)

2.2.3 方向相似性

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

(9)

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

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

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

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

(10)

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

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

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

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

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

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

3 試驗(yàn)與分析

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

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

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

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

(11)

(12)

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

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

(13)

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

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

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

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

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

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

(2)同尺度下方格網(wǎng)式道路的匹配結(jié)果優(yōu)于環(huán)狀放射式道路的匹配結(jié)果。這是由于方格網(wǎng)式道路網(wǎng)中多為平行或垂直的直線型道路,結(jié)構(gòu)較為簡(jiǎn)單,而環(huán)形道路網(wǎng)中曲線型道路數(shù)量較多,兩條可匹配道路之間部分路段的差異性較大,導(dǎo)致匹配結(jié)果產(chǎn)生誤差。而在多尺度下環(huán)狀結(jié)果卻優(yōu)于方格網(wǎng)式,對(duì)數(shù)據(jù)進(jìn)行統(tǒng)計(jì)分析發(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)驗(yàn)賦予各個(gè)相似性度量因子之間的權(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í)后,利用反向傳播機(jī)制,自動(dòng)調(diào)整權(quán)重和閾值,完成道路網(wǎng)的匹配。試驗(yàn)結(jié)果表明,該方法具有以下優(yōu)勢(shì):①可以自動(dòng)對(duì)相似性度量因子進(jìn)行權(quán)重賦值,有效降低了由主觀賦值導(dǎo)致的匹配錯(cuò)誤,提高了匹配精度;②可以自動(dòng)確定匹配閾值,無須人為設(shè)定初始匹配閾值和經(jīng)過反復(fù)試驗(yàn)調(diào)整閾值,提高了匹配效率。

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