劉光孟，劉萬增

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

線目標特征點相似性匹配

劉光孟1，劉萬增2

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

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

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

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

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

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

1.1 特征點選取

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

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

圖1 線目標相關(guān)特征點示意圖

1.2 特征點特性描述

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

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

2 相似性匹配模型和過程

2.1 相似性匹配模型

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

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

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

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

圖2 相似點匹配模型

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

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

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

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

2.2 相似性匹配過程

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

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

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

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

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

3 線目標相似性匹配實驗

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

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

圖4 兩層不同的道路線

3.2 實驗結(jié)果

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

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

圖5 實驗匹配結(jié)果

圖6 局部放大的匹配效果

4 結(jié)束語

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

[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矢量數(shù)據(jù)匹配方法[J]．測繪工程，2011，20(5):9-12.

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

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

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

[9]呂金建，文貢堅，李德仁，等．一種新的基于空間關(guān)系的特征匹配方法[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