劉光孟，劉萬增

(1．廣州市城市規(guī)劃勘測設計研究院，廣東 廣州 510060；2．國家基礎地理信息中心，北京 100830)

線目標特征點相似性匹配

劉光孟1，劉萬增2

(1．廣州市城市規(guī)劃勘測設計研究院，廣東 廣州 510060；2．國家基礎地理信息中心，北京 100830)

針對地圖制圖數據庫更新中多源數據匹配問題，通過提取線目標中的特征點，建立一種基于空間位置和拓撲關系的匹配模型，對特征點進行相似性匹配。實驗證明該模型匹配效果良好，基本滿足數據更新中圖形糾正的需要。

地圖制圖；空間位置；拓撲關系；特征點；相似性匹配

在多種類型的地圖制圖數據中，由于矢量數據具有拓撲屬性、占用空間小、縮放不失真等特點，被廣泛應用于各種地形圖制作和導航應用中。但不同來源的數據的尺度、版本和精度的差異，造成空間目標的位置、度量和拓撲關系等發(fā)生改變[1]，產生數據質量誤差，給空間目標的匹配和更新帶來困難，且多源多尺度數據在轉換過程中存在的誤差，需要對轉換后的數據進行匹配。

各專家學者在地圖數據匹配算法[2]領域對此進行了深入廣泛的研究，采用通過節(jié)點匹配算法搜索道路數來解決道路線交叉口節(jié)點匹配問題[3]，有較好的效果，但該算法只考慮了空間距離和道路條數兩方面，這無法滿足大量復雜的道路網特征點匹配[4]情況，而且提取的特征點還存在一定平移、旋轉和尺度變化[5]。本文在此基礎上對該算法進行改進，提出線目標特征點相似性匹配算法，為解決多源多尺度數據匹配與集成問題，建立基于空間線線拓撲關系的道路網特征點匹配模型，通過計算道路節(jié)點拓撲連接數、節(jié)點最大最小距離、連接方向等空間關系特征，為解決道路網目標特征點匹配問題提供技術方案。

1 線目標特征點的選取與特性描述

1.1 特征點選取

基礎地理信息數據庫為空間數據庫，空間數據庫包含了柵格和矢量圖形等多種數據形式，研究選取矢量圖形中的線目標。對于多源多尺度的矢量數據而言，要實現線目標的精確匹配，必須在眾多的矢量線目標中找到唯一性界定指標，從幾何拓撲學角度分析可知線是由點構成的，因此，將線簡化為點，并選取其特征點信息進行匹配的方法是可行的[3]。作為矢量形式的線段而言，忽略其寬度不計，其特征點主要包含端點、中點、節(jié)點等類型，如圖1所示。本文結合線目標的空間拓撲特性，選取線目標特征點中的端點和節(jié)點作為研究對象實現線目標的最終匹配。

線的端點是相對于有向線段而言的，在給線段指定方向后，即可給定線段開始和結束的兩個端點，簡稱為始端點和末端點。由于兩者的連接具有方向性，因而可以選取線線拓撲關系中的角度因子對線段進行匹配。除了端點之外，線目標中另一個主要的特征點就是節(jié)點也即交叉點，是3個或3個以上的線路會合的點集，其中包含3個或3個以上的點集。以道路線為例，典型的道路線交叉點的特征形式具有T、Y、X等形式[6]，為了判別的方便，對于T、Y型線可以認為是由3條線段交叉形成，而X型線則認為是由4條線段相交而成。這樣，相交成節(jié)點的線段數可視為相似點匹配的一個重要條件。

圖1 線目標相關特征點示意圖

1.2 特征點特性描述

在由點與點相互連接構成線段的過程中，點的位置特性是其最為重要的特性，它決定了線目標的位置屬性，在平面幾何中表現為平面直角坐標(x,y)；點與點的連接所形成的方向角決定了線目標的走向，豐富了線目標的拓撲特性；而線與線之間的連接或交叉，則形成了節(jié)點處不同線段始末端點的相互重疊，在ArcGIS空間分析中，通過拓撲檢查和分析可以很好地獲取節(jié)點處不同線段的端點重復數，也即該節(jié)點所連接的線段數，這對線目標進行拓撲分析具有重要的意義。

研究過程中對線目標節(jié)點的界定和選取為多條線段在某處的相交點，該節(jié)點的特性表現為在同一數據集中，其空間位置坐標、連接線目標數、包含的點集是唯一的，在此基礎上進行不同數據集匹配時結合另外一個節(jié)點所形成的方向角，通過對數據集的預處理，便能夠在空間線目標匹配的過程中實現相應范圍內線目標節(jié)點的一對一匹配。而對于線目標的節(jié)點，因其表達形式的多樣性，因此,所包含的結構特性也比較復雜，按照其連接線目標的結構問題分析，除了節(jié)點空間位置坐標唯一外，其連接的線目標數、包含點集和形成方向角的個數均≥3，這對于線目標特征點的相似性匹配加大了難度，但同時也提高了相似性匹配的精確度。

2 相似性匹配模型和過程

2.1 相似性匹配模型

考慮到原始數據在尺度及空間變換上存在的平移、旋轉、縮放和數據綜合方面存在的任意性，根據線目標的幾何特征和圖論拓撲連通關系，確定要選取的參考基準目標[2]，以兩點間距離、方位角的幾何特征結合節(jié)點的拓撲構成關系作為匹配因子，其中節(jié)點處包含的點集為主要匹配因子。

兩點間的距離和方位角可以由選取的參考基準點計算得到，節(jié)點處的點集則由在打散線段時未簡化的相同端點個數決定。對于單一線段，其節(jié)點(即始/末端點)的點集為1；而點集為2的節(jié)點在拓撲連通上認為是點構成線的主要因素，排除在外；因此，節(jié)點的點集n集合范圍為{n∈N+,n≠2}。

由于多源多尺度數據轉換造成的空間數據誤差在整個數據集中是均勻分布的，因此，通過數理統(tǒng)計的方法在整個數據集的不同空間位置均勻選取若干個相似性匹配參考點，進行誤差統(tǒng)計，取其誤差平均值作為匹配條件的閾值。相似性匹配參考點的選取數量不應小于10個，分別在以小范圍數據集中心的東、西、南、北、東南、東北、西南、西北和中心各取一個，誤差較大的位置附近多取一個，以保證誤差統(tǒng)計的準確性。

為了更精確地匹配到相似點，根據相同長度下兩線夾角所圍外切圓面積最小的原則，采用“相似圓”對距離和角度進行匹配，即落在“相似圓”內的所有被匹配點被認為跟匹配點是相似的。圖2為參考點A與B進行相似性匹配示意圖。

圖2 相似點匹配模型

任意i和j兩點進行相似匹配，需滿足的關系式為

f(pi≈pj)=(f(dis)ij,f(angle)ij,f(topo)ij),

(pi∈點集1,pj∈點集2).

其中：f(dis)為距離因子，f(angle)為角度因子，f(topo)為拓撲關系因子。

2.2 相似性匹配過程

根據已建立的線目標相似性匹配模型，對于存儲在空間數據庫中的矢量線目標進行分析操作，其具體實施技術方案如下：

1)從空間數據庫加載兩幅相關的矢量線目標，提取特征點及其坐標，進行線目標特征點拓撲結構分析處理。線目標特征點的提取包含線端點的提取和節(jié)點的提取，其中線的端點，即線拓撲結構中的起始點(From Point)和終止點(To Point)可以直接獲取，而節(jié)點則需要經過專門處理。在基于ArcEngine組件庫的開發(fā)環(huán)境中，通過相關的類庫函數和接口，采用Simplify方法對節(jié)點進行簡化處理，獲取其包含的端點個數及相對應的坐標，將數值存入計算函數數組，用于后續(xù)相似性匹配計算。

2)選取一對相似點基準，計算距離、方位角因子，并進行圖形分塊和鄰近搜索等優(yōu)化處理。在整個線目標相似性匹配的過程中，選擇線目標中的相似點參考基準是必不可少的。在此基礎上，獲取距離、方位角和端點個數等搜索因子，輸入相似性匹配模型，并進行圖形分塊和鄰近搜索等優(yōu)化處理，提高模型匹配的速度。

3)執(zhí)行相似性匹配，對已匹配完成的數據顯示相互匹配的特征點和輸出其坐標信息表，用于檢驗匹配結果是否準確，圖3給出了線目標特征點提取和匹配的詳細過程。

圖3 線目標特征點匹配過程

3 線目標相似性匹配實驗

3.1 統(tǒng)一坐標系和確定閾值

實驗選取某市導航數據和1∶5萬道路網數據為例(見圖4)，首先獲取地圖數據所采用的坐標系和投影參數，對兩種不同實驗數據的空間參考進行統(tǒng)一的設置，然后量取部分線目標特征點與相鄰特征點之間的距離進行統(tǒng)計，取所有計算距離之差的平均值作為“相似圓”半徑的閾值，這有利于線目標特征點距離的計算和提高匹配的精度。

圖4 兩層不同的道路線

3.2 實驗結果

經對落在“相似圓”內的點進行匹配實驗計算驗證，發(fā)現閾值Δd對匹配的結果有很大的影響，實驗證明，匹配的準確率隨著Δd的增大而減小，Δd越大所圈定的搜索范圍就越大，Δd太小則找不到匹配點，而Δd0采用算術平均值進行匹配時，取得了較好的匹配效果。

利用該模型對圖4的道路數據進行匹配，獲得的結果如圖5所示，圖6為局部放大后的匹配效果。匹配計算結束后得到圖7匹配點對應數據表，不僅可以清楚地查閱對應點的坐標和拓撲構成情況，通過雙擊屬性表還可以定位到圖形控件中的對應點上。

圖5 實驗匹配結果

圖6 局部放大的匹配效果

4 結束語

空間數據特征點匹配是空間數據糾正和數據庫更新的重要部分。本文針對多源復雜線目標數據的匹配問題，通過提取線目標特征點進行相似性匹配，利用線目標節(jié)點間的空間關系建立相似性匹配模型，直觀描述局部匹配點間的拓撲、方向與度量的相似關系，選用實際中常用的道路線目標數據進行相似性匹配實驗，顯示并輸出對應匹配點數據，取得較好的效果。

[1]劉萬增，陳 軍，鄧喀中，等．線目標空間沖突自動檢測方法研究[J]．中國礦業(yè)大學學報，2006，35(6):768-771.

[2]曾波，江資斌．GPS車載導航系統(tǒng)的地圖匹配算法[J]．測繪工程，2004，13(3):65-67.

[3]孫棣華，畢俊杰，廖孝勇．一種矢量道路圖層節(jié)點匹配新算法[J]．計算機系統(tǒng)應用，2010,19(10)：225-227.

[4]胡明昊，任明武，楊靜宇．一種快速實用的特征點匹配算法[J]．計算機工程，2004，30(9):31-33.

[5]張江水，李傳廣，郭海濤．基于動態(tài)規(guī)劃和Hough變換的遙感影像與GIS矢量數據匹配方法[J]．測繪工程，2011，20(5):9-12.

[6]陳曉飛，薛 峰，王潤生．航空照片中道路交叉口的自動檢測[J]．模式識別與人工智能，2000，13(1):83-86.

[7]胡云崗，陳 軍，李志林，等．基于網眼密度的道路選取方法[J]．測繪學報，2007，36(3):351-357.

[8]郭克華．基于微分幾何的局部相似目標匹配算法研究[D]．南京：南京理工大學，2008:3-16.

[9]呂金建，文貢堅，李德仁，等．一種新的基于空間關系的特征匹配方法[J]．測繪學報，2008，37(3):367-373.

[10]俞慈君，李江雄，余鋒杰，等．帶工程約束的點匹配算法[J]．機械工程學報，2010，46(5):183-190.

[責任編輯：劉文霞]

Similaritymatchingoffeaturesextractionandlineobjects

LIU Guang-meng1, LIU Wan-zeng2

(1．Guangzhou Urban Planning & Design Institute，Guangzhou 510060,China; 2．National Geomatic Center of China, Beijing 100830,China)

For the matching cases of multi-source data on mapping data updating, by extracting the feature points from the line objects, a model of similarity matching is established based on space-based position and topology. Experimental results show that the model matches basely well with the needs of the graphic correction in the data updating.

mapping; spatial location; topology; feature points; similarity matching

2013-04-16

劉光孟(1986-)，男，碩士研究生.

P28

：A

：1006-7949(2014)01-0035-04