基于Stroke的道路網(wǎng)匹配

王 鵬，鄭貴省，王 元，車亞輝，李月明

(1.軍事交通學(xué)院研究生管理大隊，天津300161;2.軍事交通學(xué)院基礎(chǔ)部，天津300161)

隨著空間技術(shù)和計算機(jī)技術(shù)的不斷發(fā)展，地理信息系統(tǒng)(geographic information system，GIS)已經(jīng)廣泛地用于各行各業(yè)，特別是在交通領(lǐng)域，位置服務(wù)、車輛導(dǎo)航、交通規(guī)劃等已經(jīng)大量采用GIS技術(shù)。但GIS數(shù)據(jù)的獲取一直是制約GIS發(fā)展的重要瓶頸之一，空間數(shù)據(jù)變化快、采集獲取代價大，如何維護(hù)數(shù)據(jù)的現(xiàn)勢性，是確保依托GIS提供準(zhǔn)確服務(wù)的關(guān)鍵。目前，道路網(wǎng)發(fā)展速度驚人，線路變更周期短，只有路網(wǎng)空間數(shù)據(jù)變化的及時發(fā)現(xiàn)與更新，才能確保路網(wǎng)地理信息滿足服務(wù)需求。

針對路網(wǎng)數(shù)據(jù)更新的問題，大多采用不同來源的路網(wǎng)數(shù)據(jù)融合作為解決問題的途徑。其中路網(wǎng)數(shù)據(jù)匹配是完成路網(wǎng)數(shù)據(jù)融合的關(guān)鍵。文獻(xiàn)［1］針對道路實體匹配提出采用緩沖區(qū)增長的方法，通過設(shè)置待匹配弧段的緩沖區(qū)確定另一數(shù)據(jù)集中的候選匹配集，從而完成各種類型的線要素匹配。文獻(xiàn)［2］采用迭代最近點法進(jìn)行道路網(wǎng)匹配，將道路網(wǎng)經(jīng)拓?fù)涮幚砗?，建立“邊—?jié)點”的數(shù)據(jù)模型，建立道路網(wǎng)絡(luò)的鄰接矩陣，將路網(wǎng)匹配轉(zhuǎn)化為節(jié)點匹配。文獻(xiàn)［3］提出了一種基于概率理論的匹配模型，模型中包含多個匹配指標(biāo)，通過計算實體匹配概率大小來確定匹配實體。文獻(xiàn)［4］提出基于格網(wǎng)索引的“折線—節(jié)點”距離匹配算法，將路網(wǎng)折線間的幾何相似度轉(zhuǎn)換為節(jié)點到折線的距離，對大比例尺的目標(biāo)數(shù)據(jù)建立格網(wǎng)索引，通過格網(wǎng)索引來提高計算效率。文獻(xiàn)［5］將道路網(wǎng)目標(biāo)匹配分解為分解、基本和抽象3個匹配層次，利用緩沖區(qū)分析和拓?fù)潢P(guān)系等手段開發(fā)了系列算法，進(jìn)而完成了各目標(biāo)間的匹配。但目前的道路空間數(shù)據(jù)來源各異，數(shù)據(jù)質(zhì)量很難得到保證，單條道路的整體性較難保持。單條道路往往有多條弧段構(gòu)成，現(xiàn)有的匹配算法大都針對單一的弧段進(jìn)行單獨匹配，未將道路看成一個整體，這就導(dǎo)致匹配后道路存在局部的誤匹配和未匹配，匹配結(jié)果的正確性很難得到保證。

1 路網(wǎng)結(jié)構(gòu)Stroke表達(dá)

目前，道路網(wǎng)表達(dá)都采用“節(jié)點—弧段”模型，可用圖論的知識進(jìn)行描述。也就是道路網(wǎng)可以表示成G=(V，E)，其中G為帶權(quán)的圖，一條道路可以被分割成若干條邊E，每條邊之間的連接點用V表示，道路的拓?fù)潢P(guān)系可以通過邊與節(jié)點之間的連接關(guān)系表示。而道路網(wǎng)的stroke(路化)表達(dá)實際上是按照特定的規(guī)則將路段連接成一條平滑的stroke［6］，利用 Gestalt視覺感知中的“良好連續(xù)性(good continuation)”原則連接在同一節(jié)點的弧段，若在該點處方向的偏差角小于一定的閾值，在視覺感受上方向一致，可以將這些弧段元素看著一個整體，即一個 stroke。如圖1所示，可將用“節(jié)點—弧段”表達(dá)的道路弧段a、c、e用一個stroke表達(dá)。從存儲上來說，可以有效減少邊和節(jié)點的數(shù)量，減少存儲空間，提高數(shù)據(jù)的整體性。

圖1 道路Stroke表達(dá)示例

道路stroke的選取，通常采用道路的屬性、弧段間偏向角度和弧段整體趨勢發(fā)展等來判斷。一般通過道路的屬性信息來判斷弧段是否屬于一條stroke比較準(zhǔn)確，但在實際運用中，屬性信息有的不完整甚至缺失，這就導(dǎo)致無法生成準(zhǔn)確的stroke。所以，通過設(shè)定偏向角度的閾值(30°～75°)，來判斷弧段與關(guān)聯(lián)弧段的角度，選取stroke的候選弧段。在選取過程中，可能存在一條弧段與關(guān)聯(lián)弧段的偏向角度均小于閾值。如圖2所示，與a關(guān)聯(lián)的弧段b、c之間的偏向角均小于閾值，其都可作為stroke的弧段。這里引入全局最優(yōu)原則，即在節(jié)點N處兩兩比較弧段間的偏向角，選取偏向角最小的一組作為stroke的弧段，可以看到弧段b和弧段e構(gòu)成的偏向角遠(yuǎn)小于弧段a和弧段b的偏向角，因此弧段b和弧段e可以構(gòu)成單獨一條stroke，弧段a將選擇弧段c作為連接弧段。

圖2 Stroke提取示例

在一些特殊區(qū)域，存在同一道路的弧段間偏向角大小超過設(shè)定的閾值。如圖3所示，若采用偏向角度來生成stroke，那弧段a和弧段c屬于一條stroke，但實際上弧段a和弧段b屬于同一條道路。這樣就導(dǎo)致生成的stroke與實際差距較大。

圖3 采用不同方式的Stroke選取示例

因此，為了確保數(shù)據(jù)的準(zhǔn)確性，本文對路網(wǎng)數(shù)據(jù)先通過道路名稱一致性生成stroke，而后對不具備屬性信息的弧段采用偏向角生成stroke。

2 Stroke等級劃分與分組匹配

在完成道路stroke生成的基礎(chǔ)上，進(jìn)行道路網(wǎng)絡(luò)的整體匹配。目前，在路網(wǎng)stroke匹配前，一般會事先對道路stroke采取量化等級劃分。等級越高的道路stroke，說明其在路網(wǎng)中的重要程度以及對路網(wǎng)通達(dá)性的影響較大，在匹配中應(yīng)當(dāng)優(yōu)先考慮等級較高的道路匹配的成功率，確保路網(wǎng)匹配的整體準(zhǔn)確性和實用性。在道路等級劃分中，一般采用道路類型屬性信息進(jìn)行劃分，如國道、省道等。在屬性信息不完善時，可采用道路長度作為道路等級劃分的參考，道路長度越長，其服務(wù)的區(qū)域越廣闊，影響范圍越大，重要性就越高。道路的長度可以看作是構(gòu)成路網(wǎng)的各子線段長度的總和。如圖4所示，設(shè)各子線段的端點為Pi的坐標(biāo)為(xi，yi)，i=0，1，2，…，n，則線段長度 L 為

圖4 線長度表示

匹配是在目標(biāo)數(shù)據(jù)集和參考數(shù)據(jù)集之間建立映射的過程。在stroke分組的基礎(chǔ)上，采用由整體至局部的匹配策略。根據(jù)上面stroke等級劃分的結(jié)果，利用stroke之間的關(guān)聯(lián)關(guān)系對stroke進(jìn)行分組匹配，其基本流程如下:

(1)選取等級最高的 stroke，即長度最長的stroke，記作k，查詢與k首尾節(jié)點相連的 stroke，與k組成新的鏈Li;

(2)再查詢以L的首尾節(jié)點相連的stroke，重復(fù)上面過程，直至鏈L的首尾節(jié)點無相連的stroke，對鏈Li建立分組序號n;

(3)n=n+1，在剩下的stroke中重復(fù)上述步驟，至分組完畢;

(4)對目標(biāo)數(shù)據(jù)集和參考數(shù)據(jù)集按步驟(1)—(3)處理，建立分組后，以序號作為索引，縮小搜索候選匹配stroke的范圍，對分組內(nèi)的stroke按匹配判定方法進(jìn)行匹配。

3 道路網(wǎng)Stroke匹配判定方法

對于線實體的匹配主要采用線的總長度、線的方向、線的最大弦等作為相似度匹配指標(biāo)。由上面分組的結(jié)果可知，每組中stroke的長度以分組序號作為索引，具有相同分組序號的兩條stroke長度的比值越接近1說明其在幾何特征上可能越相似。但僅僅依靠長度是不夠的，選取匹配候選stroke實體后，通過stroke的首尾節(jié)點匹配，來確定stroke是否匹配，若首尾節(jié)點匹配可以認(rèn)為stroke匹配。點匹配可由歐幾里德距離來確定，其計算式為

式中(xs，xt)和(ys，yt)分別為目標(biāo)數(shù)據(jù)集和參考數(shù)據(jù)集的節(jié)點坐標(biāo)。

若Δd小于閾值Δβ可認(rèn)為兩個節(jié)點是匹配的，閾值的大小由數(shù)據(jù)的精度、以及比例尺等因素來確定，一般比例尺越小，其精度越低。

若首尾節(jié)點不能匹配，計算兩條stroke的空間鄰近度，采用中間面積法計算線實體之間的距離，以此來確定線之間的相似度［7］。其計算式為

式中:s為兩條線首尾節(jié)點連接后圍成的區(qū)域;l為兩條線之間的平均長度。

若d越小說明兩條線圍成的區(qū)域面積就越小，其在空間的距離就越近(如圖5所示)。

圖5 線實體之間圍成的面積

但是在實際運用中，存在兩條線實體，其中一條的長度遠(yuǎn)小于另一條的長度。即在圍成的區(qū)域中，在視覺效果上存在著尾巴(如圖6所示)。

圖6 圍成的區(qū)域存在尾巴的情況

如果仍然采用原來的計算方法，將會產(chǎn)生較大的誤差。選擇長度較短的線實體的首尾端點投影到長度較長的一條線上(如圖7所示)。通過計算線L1在線 L2上的投影點 N1、N2，以及線端點M1、M2和線L1、L2圍成的面積，這樣就能有效避免出現(xiàn)長尾巴的情況，使距離測度能更客觀地反映出線的匹配度，更加符合人的視覺效果。

圖7 修正后的區(qū)域面積表示

4 實例驗證

本文從地理數(shù)據(jù)庫中提取青島市區(qū)1∶10萬和1∶20萬的城市道路數(shù)據(jù)進(jìn)行匹配，按照上述方法分別對數(shù)據(jù)源提取stroke后，以1∶10萬作為參考數(shù)據(jù)集進(jìn)行匹配(如圖8所示)。

圖8 參與匹配的道路數(shù)據(jù)

由于提取的城市道路數(shù)據(jù)中道路等級劃分層次多，等級較高的主干道一般具備道路名稱的屬性，而且長度較長，而等級較低的支路道路名稱一般不全，而且容易被其他道路分割，因此，該提取的數(shù)據(jù)有利于驗證本文算法的有效性。

在道路數(shù)據(jù)匹配后，進(jìn)行了人工目視檢查與更正，圖9為參與匹配的路網(wǎng)數(shù)據(jù)不能匹配的部分。圖10為局部區(qū)域匹配放大圖，可以看出，參與匹配的數(shù)據(jù)對應(yīng)的路段R1與T1、R2與T2基本匹配，而1∶10萬道路數(shù)據(jù)中的R3則不存在匹配對象，其原因可能是道路更新或在地圖繪制中舍棄了部分細(xì)節(jié)。采用匹配方法能較清晰地發(fā)現(xiàn)不同數(shù)據(jù)源中道路的變化，能夠與人工目視判別得到較一致的結(jié)果。

圖9 數(shù)據(jù)中不能匹配的部分

圖10 道路匹配結(jié)果的部分區(qū)域

5 結(jié)語

道路空間數(shù)據(jù)匹配一直是路網(wǎng)數(shù)據(jù)發(fā)現(xiàn)和更新的關(guān)鍵技術(shù)，本文通過對道路網(wǎng)絡(luò)數(shù)據(jù)選取stroke，并根據(jù)其長度劃分了stroke等級，在等級劃分基礎(chǔ)上建立了節(jié)點關(guān)聯(lián)的stroke分組，并以分組序號作為索引對路網(wǎng)進(jìn)行匹配，可以縮小選取匹配對象的范圍。該方法有效降低了道路網(wǎng)數(shù)據(jù)邊和節(jié)點的數(shù)量，降低了路網(wǎng)表達(dá)的復(fù)雜度，并且維護(hù)了道路的整體性。在stroke分組匹配中，采用了由整體至局部的匹配方法，通過計算相對簡單的節(jié)點間匹配，來進(jìn)行初始匹配判斷，有效地減少了計算的復(fù)雜程度。但本文采用的方法只能針對結(jié)構(gòu)相對比較簡單的道路數(shù)據(jù)，即不具備交叉口和單雙行道等復(fù)雜的結(jié)構(gòu)。對具備這些特征的復(fù)雜路網(wǎng)匹配，改進(jìn)匹配方法，將是下一步研究的方向。

［1］ Walter V，F(xiàn)ritsch D.Matching spatial data sets:a statistical approach［J］.International Journal of Geographical Information Systems，1999，13(5):445-473.

［2］ Zhang M.Methods and implementations of road-network matching［D］.Munich:Technical University of Munich，2009:23-67.

［3］ 童小華，鄧愫愫，史文中.基于概率的地圖實體匹配方法［J］.測繪學(xué)報，2007，36(2):210-217.

［4］ 陳玉敏，龔健雅，史文中.多尺度道路網(wǎng)的距離匹配算法［J］.測繪學(xué)報，2007，36(1):84-90.

［5］ 胡云崗，趙仁亮，李志林，等.地圖數(shù)據(jù)縮編更新中道路數(shù)據(jù)匹配方法［J］.武漢大學(xué)學(xué)報(信息科學(xué)版)，2010，35(4):451-456.

［6］ Thomson R C.The stroke concept in geographic network generalization and analysis［C］//Proceedings of the 2th International Symposium on Spatial Data Handling，Vienna，2006:681-697.

［7］ 張橋平.地圖數(shù)據(jù)庫實體匹配與合并技術(shù)［D］.武漢:武漢大學(xué)，2002:55-76.