基于Stroke的道路網匹配

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

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

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

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

1 路網結構Stroke表達

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

圖1 道路Stroke表達示例

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

圖2 Stroke提取示例

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

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

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

2 Stroke等級劃分與分組匹配

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

圖4 線長度表示

匹配是在目標數據集和參考數據集之間建立映射的過程。在stroke分組的基礎上，采用由整體至局部的匹配策略。根據上面stroke等級劃分的結果，利用stroke之間的關聯關系對stroke進行分組匹配，其基本流程如下:

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

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

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

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

3 道路網Stroke匹配判定方法

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

式中(xs，xt)和(ys，yt)分別為目標數據集和參考數據集的節點坐標。

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

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

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

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

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

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

圖6 圍成的區域存在尾巴的情況

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

圖7 修正后的區域面積表示

4 實例驗證

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

圖8 參與匹配的道路數據

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

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

圖9 數據中不能匹配的部分

圖10 道路匹配結果的部分區域

5 結語

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

［1］ Walter V，Fritsch 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］.測繪學報，2007，36(2):210-217.

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

［5］ 胡云崗，趙仁亮，李志林，等.地圖數據縮編更新中道路數據匹配方法［J］.武漢大學學報(信息科學版)，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］ 張橋平.地圖數據庫實體匹配與合并技術［D］.武漢:武漢大學，2002:55-76.