基于圖卷積神經網絡的道路網匹配

齊 杰,王中輝,李驛言

(1. 蘭州交通大學測繪與地理信息學院,甘肅 蘭州 730070; 2. 地理國情監測技術應用國家地方聯合工程研究中心,甘肅 蘭州 730070;3. 甘肅省地理國情監測工程實驗室,甘肅 蘭州 730070)

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

道路網匹配一般通過計算道路的語義相似性和幾何相似性進行匹配?；谡Z義相似性的匹配方法主要通過計算線要素之間的語義相似性進行道路網匹配[2-4],很大程度上依賴于屬性信息的唯一性。而多源道路數據往往缺少具有唯一性的屬性信息,因此該方法只能用于輔助匹配?；趲缀蜗嗨菩缘钠ヅ浞椒ㄍㄟ^計算線要素之間的幾何相似性進行道路網匹配[5-7]。幾何相似性包括方向、距離、形狀、拓撲關系等相似性度量指標,通常選取一種或多種相似性度量指標,確定指標之間的權重組合,選擇合適的相似度匹配閾值,完成道路網的匹配。該方法通常采用主觀賦權法進行相似性指標權重組合和匹配閾值確定,對匹配結果具有較大影響。

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

1 圖卷積神經網絡的基本原理

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

(1)

圖傅里葉的逆變換為

(2)

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

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

(3)

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

σ=QgθQTf

(4)

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

(5)

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

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

(6)

2 基于圖卷積神經網絡的道路網匹配

將待匹配道路網數據轉化為對偶圖,利用對偶圖將道路構建為圖結構數據,將節點所代表的兩條道路是否為匹配道路作為標簽,輸入GCN模型中進行訓練,完成道路網的匹配。模型框架如圖1所示,主要包括以下步驟:①數據處理,對數據進行預處理,確定待匹配道路的候選匹配集;②特征提取,選取長度相似性、距離相似性、方向相似性、拓撲相似性4個特征因子作為對偶圖節點的特征;③GCN學習,先構建對偶圖,并對道路網標注標簽,再以圖數據轉化后的對偶圖作為輸入數據,利用卷積運算提取特征,通過反復迭代最終使模型達到收斂。

圖1 基于圖卷積神經網絡的道路網匹配整體框架

2.1 數據處理

將獲取的數據利用ArcGIS進行拓撲檢測和屬性表檢查,對重復路段和孤立路段進行刪除,統一兩個地圖數據的坐標系。對可匹配道路進行節點數量的檢查,為滿足后續對待匹配路段和參考路段進行圖結構構建,需要在不影響道路整體結構的前提下對道路進行增加或刪除節點的處理,使節點的數量達到一致。利用緩沖區增長法確定待匹配道路的候選匹配集。

2.2 特征提取

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

2.2.1 長度相似性

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

(7)

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

2.2.2 距離相似性

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

(8)

2.2.3 方向相似性

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

(9)

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

2.2.4 拓撲相似性

采用節點連通度對拓撲相似性進行描述。節點的連通度即道路節點關聯弧段的數量[14],見表1。道路A、B的拓撲相似度可表示為

表1 節點連通度示意

(10)

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

2.3 GCN學習

2.3.1 道路網對偶圖構建

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

2.3.2 圖卷積網絡模型構建

道路網匹配任務的標注、輸入和輸出如下。

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

(2)輸入:將數據集轉化為對偶圖,把道路的路段作為圖的節點,連接關系作為圖的邊,最終得到的道路網圖模型G=(V,E,A)。每個圖模型都包含N個節點,每個節點都有4個計算特征值{f1,f2,f3,f4},分別對應長度相似性、距離相似性、方向相似性、拓撲相似性。所有節點構成N×4的特征向量和一個N×N的鄰接矩陣。

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

3 試驗與分析

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

圖4 不同尺度下的兩種類型道路網

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

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

(11)

(12)

式中,S為道路總數;M為存在匹配關系的道路數量;C為正確匹配的道路數量。

為了同時考慮道路網的匹配率和召回率,避免因匹配率和召回率相反變化引起的描述與評價不便,采用匹配準確率和召回率的調和平均值F進行結果的評價[16],公式為

(13)

式中,P為準確率;R為召回率。

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

表2 不同試驗數據下道路網匹配結果

圖6 匹配試驗的損失與準確度變化

對試驗結果進行分析可知:

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

(2)同尺度下方格網式道路的匹配結果優于環狀放射式道路的匹配結果。這是由于方格網式道路網中多為平行或垂直的直線型道路,結構較為簡單,而環形道路網中曲線型道路數量較多,兩條可匹配道路之間部分路段的差異性較大,導致匹配結果產生誤差。而在多尺度下環狀結果卻優于方格網式,對數據進行統計分析發現,方格網式道路中復雜道路尤其是環島類型路段的數量多于環狀道路,這使得最終的匹配結果出現了不同的變化。

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

4 結 語

本文提出了一種基于圖卷積神經網絡的道路網匹配方法,在進行監督分類學習后,利用反向傳播機制,自動調整權重和閾值,完成道路網的匹配。試驗結果表明,該方法具有以下優勢:①可以自動對相似性度量因子進行權重賦值,有效降低了由主觀賦值導致的匹配錯誤,提高了匹配精度;②可以自動確定匹配閾值,無須人為設定初始匹配閾值和經過反復試驗調整閾值,提高了匹配效率。

但圖卷積神經網絡疊加多層會出現過擬合現象,使模型產生退化,從而導致過于簡化的復雜路段的局部特征相似度較低,產生錯誤匹配的情況。下一步工作考慮采取殘差網絡等復雜網絡結構,增加網絡深度,提高匹配精度。