提高線要素匹配率的動態(tài)化簡方法

陳競男，錢海忠，王　驍，何海威，胡慧明

信息工程大學地理空間信息學院，河南 鄭州 450000

?

提高線要素匹配率的動態(tài)化簡方法

陳競男，錢海忠，王驍，何海威，胡慧明

信息工程大學地理空間信息學院，河南 鄭州 450000

摘要：矢量線要素匹配是當前空間數(shù)據(jù)匹配領域的研究焦點之一。本文提出了一種提高已有匹配算法正確率的線要素動態(tài)化簡方法。首先，對待匹配雙方利用開方根規(guī)律分別確定各自的化簡閾值范圍；其次，令化簡參數(shù)在線要素各自的閾值范圍內以一定的步長變化，對每條線要素分別進行化簡，每完成一次化簡，重新計算待匹配雙方的匹配相似度，并與上一次化簡后的匹配相似度進行比較，最終得到最高的匹配相似度值；最后，根據(jù)獲取的最高匹配相似度來判斷其是否成功匹配。該算法是一種以動態(tài)化簡來帶動動態(tài)匹配的過程。通過化簡提取線要素主要形態(tài)，降低了局部細節(jié)對已有匹配算法的影響，從而提高了匹配正確率。試驗驗證及對比分析證明了本方法的科學性和普適性。

關鍵詞：線要素匹配；動態(tài)化簡；開方根規(guī)律

矢量空間數(shù)據(jù)匹配的困難之一來自數(shù)據(jù)的多源性、不一致性。長期以來，由于地圖數(shù)據(jù)采集和維護由不同部門完成，導致多源數(shù)據(jù)在位置精度、數(shù)據(jù)模型等方面千差萬別，給數(shù)據(jù)集成和更新帶來困難?？臻g數(shù)據(jù)匹配是空間數(shù)據(jù)集成與更新的核心技術，是指通過對目標的幾何、拓撲和語義進行相似性度量，識別出同一地區(qū)不同來源空間數(shù)據(jù)集中的同一地物[1]，從而建立同名目標間的聯(lián)接，為數(shù)據(jù)集成共享奠定基礎。

線要素是矢量空間數(shù)據(jù)的常見類型，其匹配也是當前空間數(shù)據(jù)匹配領域研究的焦點之一。針對線要素匹配的研究已有很多，例如文獻[2]采用緩沖區(qū)增長方法進行線要素匹配；文獻[3]基于道路節(jié)點匹配，加入弧段距離、長度、角度、拓撲關系等特征信息進行弧段匹配；部分研究注重與數(shù)學方法結合，文獻[4]提出了一種基于概率的匹配模型，綜合運用多個匹配指標，可有效解決非一對一匹配；也有學者借助形狀匹配領域的方法，采用一些形狀描述函數(shù)，比如傅里葉描述子[5]、轉角函數(shù)[6]等，對線要素進行形態(tài)表達，進而比較其形態(tài)相似度以完成匹配。針對多尺度道路網(wǎng)匹配，文獻[7]根據(jù)道路網(wǎng)折線的匹配特點，提出一種基于格網(wǎng)索引的“折線—節(jié)點”距離匹配算法；文獻[8]將道路網(wǎng)數(shù)據(jù)處理成以“節(jié)點—弧段”表達的網(wǎng)絡數(shù)據(jù)，通過預匹配、節(jié)點匹配、弧段匹配3個步驟，實現(xiàn)最終的匹配運算。

通過以上分析可以發(fā)現(xiàn)，目前大多數(shù)線要素匹配算法集中在對新技術與新算法的研制、改進等，許多方法已經(jīng)很成熟，匹配的正確率也已大幅提升。與此同時，突破也越來越困難。為進一步提升空間數(shù)據(jù)匹配的正確率，本文在已有匹配算法基礎上，從其外部出發(fā)，將制圖綜合中的化簡技術與線要素匹配方法相結合，通過對線要素化簡處理來輔助已有匹配算法從而進一步提高其匹配正確率。

1動態(tài)化簡方法及其閾值確定

1.1基本思想

化簡的實質，是要刪除細節(jié)層次，提取其主要形態(tài)?，F(xiàn)實中，多源數(shù)據(jù)相互之間在局部細節(jié)形態(tài)上可能差異較大，給已有匹配算法帶來匹配困難。但其整體形態(tài)往往是高度一致的，可以充分利用這一特性，完成線要素的匹配。如圖1，同名要素經(jīng)化簡后減少了細節(jié)層次和局部位置差異，使得整體形態(tài)相似程度增強。因此，若采用化簡把線要素局部形態(tài)的細節(jié)層次刪除，只保留主要形態(tài)特征，而后利用已有匹配算法對化簡后的數(shù)據(jù)重新進行匹配，其匹配正確率必然會有較大提升。本文基于這一思想展開研究。

圖1　同名要素化簡前后整體形態(tài)相似度對比Fig.1　Comparison of the integral similarity of corresponding features before and after simplification

1.2動態(tài)化簡閾值確定

線要素化簡算法有很多，如Douglas-Peucker法[14](簡稱D-P算法，圖2)、垂距法[15]、斜拉式彎曲劃分曲線化簡方法[16]等。引入化簡的作用在于減少要素的復雜度，這是化簡的最基本特性，因此本文對各類化簡算法是普遍適用的。本文選擇具有代表性的D-P算法來驗證線要素動態(tài)化簡方法對提高匹配正確率的作用。

1.2.1D-P算法原理

圖2　D-P算法化簡示意圖Fig.2　The schematic of D-P simplification algorithm

D-P算法能從整體上有效保持線要素的形態(tài)特征，并較好地保持線要素的幾何特征和位置精度[9]。其基本思想是：首先連接曲線的端點與末端點；再計算曲線上其他各點至連線的垂距，并找出垂距最大的點；然后將最大垂距點與指定的閾值進行比較，若垂距小于閾值，則將中間所有的點舍去，用連線代替該曲線；否則保留該點，并將原曲線分為兩段，分別重復以上步驟，直至無垂距大于閾值的點存在。

1.2.2化簡閾值范圍的自動確定

由于線要素復雜多樣，如何把握化簡強度，是一個重要環(huán)節(jié)[17]?；営衅渥陨淼囊?guī)則與要求，不能盲目進行，必須要界定化簡閾值范圍，只允許在此范圍內化簡。對于多源或多尺度道路數(shù)據(jù)，其節(jié)點個數(shù)、結構特征各不相同，如果采取相同的化簡閾值進行化簡，顯然是不科學的。針對這一問題，本文的解決方案區(qū)別于把數(shù)據(jù)源作為一個整體的做法，而采取對每一條線要素都設置不同的閾值范圍。主要思想是：待匹配數(shù)據(jù)一般分為源數(shù)據(jù)和目標數(shù)據(jù)，為保證化簡的有效性，設定一個比匹配雙方數(shù)據(jù)的比例尺均更小的比例尺，作為化簡的極限比例尺Slimit，以化簡到該比例尺時線要素的節(jié)點數(shù)量作為要保留的最少節(jié)點數(shù)(Nmin)，此時對應的化簡參數(shù)就作為閾值范圍的上限。這里涉及依比例選取的問題，采用制圖綜合中常用的開方根模型來輔助確定Nmin的值。

1982年，特普費爾在對分級問題的研究中，發(fā)現(xiàn)地物要素的選取數(shù)量與地圖比例尺之間有著密切的關系，并建立了如下開方根模型的基本公式[10]

本文在運用開方根模型的過程中，將線要素的一系列節(jié)點作為沿線分布的地物看待，化簡到某一比例尺時保留的節(jié)點數(shù)用開方根規(guī)律確定[11,20]。算法主要步驟如圖3。其中dA表示道路A的化簡閾值，NA為A化簡某一狀態(tài)下的剩余節(jié)點數(shù)，step為閾值變化步長，End_thd1為化簡到Slimit時對應的最大化簡閾值。

圖3　確定最大化簡閾值　Fig.3　Determination of the maximal simplification threshold

對于同尺度數(shù)據(jù)匹配和跨尺度數(shù)據(jù)匹配，確定其化簡閾值范圍的模式也有所差異：

表1、2列舉出部分道路通過上述方法得到的閾值范圍?？煽闯鲭m然化簡比例相同，但不同線要素的閾值范圍差異較大，一方面是由于道路結構本身較復雜，同時也受到制圖綜合存在較多主觀因素的影響。這也說明了對每條道路單獨化簡的科學性和必要性。

表11∶10萬道路化簡閾值范圍(部分)

Tab.1Numeric range of the simplification threshold for road data 1∶100 000(part)

道路ID原節(jié)點數(shù)應保留節(jié)點數(shù)(化簡至1∶25萬)對應化簡參數(shù)化簡閾值范圍13171017.4(0,17.4)141066.1(0,6.1)17231426.3(0,26.3)1810623.3(0,23.3)2826165.2(0,5.2)3229184.6(0,4.6)133372310.3(0,10.3)174291813.7(0,13.7)175412515.9(0,15.9)

1.3最佳匹配相似度獲取

1.3.1動態(tài)化簡流程

對不同數(shù)據(jù)源的兩條待匹配的同名道路A和B，確定各自的化簡閾值dA、dB范圍分別為(0，End_thd1)和(Start_thd2，End_thd2)，圖4為動態(tài)化簡算法流程。其中，step為化簡閾值變化步長；Sim為最高匹配相似度，TempSim記錄化簡過程中A和B的相似度值。具體操作步驟如下：

(1) 首先初始化各變量的值，dA=0.0，dB=start_thd2，Sim=0.0，TempSim=0.0，并設置步長step=1.0。

(2) 固定道路A的化簡閾值dA，化簡后得到道路A′。

表2　1∶2.5萬道路化簡閾值范圍(部分)

圖4　動態(tài)化簡算法流程Fig.4　Flow chart of the dynamic simplification algorithm

(3) 道路B的化簡閾值dB在(Start_thd2，End_thd2)內以步長step變化，循環(huán)對B進行化簡，每次化簡都將得到的道路B′與A′用已有匹配方法計算其匹配相似度TempSim，并通過比較替換找到該組化簡過程中的TempSim的最大值賦值給Sim。

(4)dA=dA+step。如果dA≤End_Thd1，重復步驟(2)和(3)，否則結束循環(huán)。

(5) 循環(huán)結束后，輸出此時的最佳匹配相似度Sim值以及最優(yōu)化簡閾值。

1.3.2動態(tài)化簡對匹配相似度的影響

不同的匹配方法采用的匹配指標各異，得到的匹配相似度值也各不相同[19]，但動態(tài)化簡對提升每種匹配算法的匹配正確率都具有積極作用。這里以緩沖區(qū)法為例，匹配原理為：對源數(shù)據(jù)建立緩沖區(qū)，計算目標數(shù)據(jù)落入緩沖區(qū)內的長度與自身長度之比，得到的數(shù)值作為兩要素的匹配相似度[12]。如表3，道路A、B為隨機選取的已知同名道路數(shù)據(jù)，根據(jù)1.3.1方法得到最優(yōu)化簡閾值，比較化簡前后的緩沖區(qū)匹配相似度。

表3最優(yōu)化簡閾值化簡前后匹配相似度對比

Tab.3Comparison of the matching similarities before and after simplification with the optimal thresholds

同名要素ID(A-B)最優(yōu)化簡閾值(dA,dB)化簡前相似度化簡后相似度26-341(19.6,31.8)0.7910.92738-73(12.6,48.1)0.6920.808147-280(0.0,52.4)0.8100.870159-933(8.4,19.8)0.7970.87655-129(6.3,31.3)0.8360.894109-791(4.2,20.8)0.7820.833203-936(16.8,26.1)0.8630.99228-175(23.1,65.3)0.7040.95370-113(10.5,20.1)0.7910.890

取表中一對同名道路(28-175)作具體分析，如圖5，可直觀地看出化簡后的數(shù)據(jù)提取出了道路主要形態(tài)，并使得匹配雙方整體相似程度明顯提升。圖5(a)為原始匹配，目標道路長度L=1 392.043，落入緩沖區(qū)內長度L_InBuffer=980.165，匹配相似度Sim=0.704；圖5(b)為化簡后的匹配狀態(tài)，此時目標道路長度L′=1 360.507，落入緩沖區(qū)內長度L_InBuffer′=1 296.577，匹配相似度Sim=0.953。因此，化簡可以顯著提高匹配雙方的整體相似度，對進一步提升匹配正確率具有積極意義。

圖5　最優(yōu)化簡閾值化簡前后緩沖區(qū)匹配Fig.5　Comparison of buffer matching before and after simplification with the optimal thresholds

2匹配方法與流程

2.1匹配流程

在先化簡后匹配的過程中，匹配雙方的相似度Sim是動態(tài)變化的，當Sim滿足設定的匹配閾值時，就可被判定為相互匹配。匹配整體流程如圖6所示。在算法實現(xiàn)的流程中對化簡過程作以下優(yōu)化：①已有匹配方法能夠完成匹配的數(shù)據(jù)，不再作化簡處理；②動態(tài)化簡過程中，當發(fā)現(xiàn)Sim值大于匹配閾值時，立即中斷化簡過程，完成匹配。(注：即此時化簡參數(shù)不再要求必須是最優(yōu)化簡閾值)。

圖6　本文方法匹配流程Fig.6　Matching flow chart based on dynamic simplification

2.2誤匹配避免

整體來說，動態(tài)化簡與匹配在理論上是正確的。當然，也可能存在少量不確定因素而造成誤匹配。誤匹配的發(fā)生一方面主要是由于化簡算法的閾值設置不當造成的，另一方面是由于匹配算法自身采用的指標約束不全面造成的。因此可從上述兩個方面最大程度地避免誤匹配：①設置極限比例尺的目的是限制化簡的比例，在試驗過程中，采取動態(tài)設置極限比例尺的方式，即初始設置一個較大值，若此時出現(xiàn)誤匹配，將比例尺再增大，若未出現(xiàn)誤匹配，將初始值減小，依此類推，統(tǒng)計最優(yōu)匹配結果，將此時的比例尺作為極限比例尺的合適值；②設置較高的匹配閾值，由于匹配算法約束不夠全面造成的誤匹配，在不改進算法的前提下，采取通過提高匹配標準來盡可能地降低匹配的不確定性，從而進一步減少誤匹配發(fā)生的概率。

3試驗及對比分析

動態(tài)化簡實質上是一種輔助匹配方法，具有普遍適用性，限于篇幅，僅以常用的緩沖區(qū)法和轉角函數(shù)法為例，驗證其整體匹配性能。此外，本文主要針對提高變化要素匹配正確率的問題展開研究，新增要素和消失要素的匹配較為簡單(無匹配對象)，文中對其進行了過濾處理，只顯示變化要素的匹配結果。

3.1緩沖區(qū)匹配試驗

圖7為某地1∶10萬和1∶2.5萬的不同尺度道路網(wǎng)數(shù)據(jù)。通過對源數(shù)據(jù)構建緩沖區(qū)，依據(jù)目標數(shù)據(jù)落入緩沖區(qū)內的長度比率來判斷是否匹配。其中，緩沖區(qū)半徑的設置對匹配結果影響很大，主要根據(jù)數(shù)據(jù)精度等因素來選擇合適的緩沖區(qū)半徑：1∶10萬和1∶2.5萬的道路網(wǎng)數(shù)據(jù)，其誤差要求分別為±50 m和±12.5 m。以1∶10萬道路為參考數(shù)據(jù)，取其大者即50 m并在該值左右動態(tài)設置緩沖區(qū)半徑值，同時調整匹配閾值，發(fā)現(xiàn)當緩沖區(qū)半徑設置為50 m、匹配閾值設為0.8時，既可避免過度匹配，又最大程度地減少了漏匹配，匹配效果達到最佳。因此，在加入動態(tài)化簡方法進行匹配時，也選用上述同樣的參數(shù)，以便于比較。

圖7　不同尺度道路網(wǎng)試驗數(shù)據(jù)Fig.7　Experimental road data of different scales

圖8為本文方法輔助Buffer法的匹配結果(包括局部匹配)，其中圓圈標記的要素①②③④為一部分新成功匹配的道路，它是指直接采用Buffer法無法匹配、而采用動態(tài)化簡輔助后匹配成功的變化要素，將其在圖9中放大顯示，并對化簡前后的緩沖區(qū)匹配情況進行了對比，其中連接短線為匹配標識。

圖8　本文方法輔助Buffer法的匹配結果Fig.8　Buffer matching result after dynamic simplification

圖9　Buffer法新成功匹配道路化簡前后匹配情況對比(部分)Fig.9　Buffer matching state comparison of the new successful matches before and after simplification(part)

由于匹配雙方為不同尺度數(shù)據(jù)，匹配結果比較復雜，存在大量一對多(1∶N)情況[18]，為方便對匹配結果進行統(tǒng)計，本文以1∶10萬源數(shù)據(jù)為參考，其中參與匹配道路為198條，匹配道路中，將正確并完整找到匹配對象的情況歸為正確匹配，而1∶N匹配中只完成道路部分匹配的稱為局部匹配。

表4數(shù)據(jù)統(tǒng)計表明，僅使用緩沖區(qū)法時正確匹配143條道路，正確率為72.2%(143/198)；加入本文方法后，正確匹配道路增加到172條，匹配正確率為86.8%(172/198)，匹配正確率提高了14.6%。

對數(shù)據(jù)作進一步分析：①未匹配道路由17條減少到4條，即新增13條1∶1匹配的道路，說明本文方法能夠提高匹配雙方的整體相似度；②局部匹配減少了16條，說明本文方法減弱了局部細節(jié)層次對緩沖區(qū)匹配的影響，彌補了漏匹配，使得一些只完成部分匹配的道路最終實現(xiàn)完全匹配。

4緩沖區(qū)匹配結果對比統(tǒng)計(step=1.0Slimit=1∶250 000)

Tab.4Statistics and comparison of the buffer matching results (step=1.0Slimit=1∶250 000)

匹配方法參與匹配匹配道路正確匹配局部匹配未匹配道路匹配正確率/(%)緩沖區(qū)法198143381772.2本文方法19817222486.8

3.2轉角函數(shù)法匹配試驗

轉角函數(shù)法是將組成面或線的眾多弧段通過其節(jié)點處的方位角，表達在直角坐標系中來，由于顯示在坐標系的圖形類似于正切函數(shù)圖像，故該方法也稱正切空間形狀描述法[13]。本文借鑒該方法用于線要素匹配，并加入動態(tài)化簡方法進行對比。由于轉角函數(shù)法是顧及線要素整體形態(tài)的匹配方法，并不適用于1∶N匹配較多的跨尺度匹配，因此，選取某地不同時期的1∶25萬同尺度道路網(wǎng)進行試驗驗證。如圖10為同尺度匹配試驗數(shù)據(jù)。

圖10　同尺度不同來源數(shù)據(jù)疊加Fig.10　Road data of the same scale from different sources

圖11為本文方法輔助轉角法的匹配結果，匹配閾值設為0.9，采用與Buffer法類似的表示方法，將其中圈出的新成功匹配要素①、②、③、④在圖12中放大顯示，對比了化簡前后的匹配情況。

圖11　本文方法輔助轉角法的匹配結果Fig.11　Turning function matching result after dynamic simplification

圖12　轉角法新成功匹配道路化簡前后匹配情況對比(部分)Fig.12　Turning function matching state comparison of the new successful matches before and after simplification(part)

分析表5，轉角函數(shù)法原始匹配正確率為74.7%(165/226)，采用本文方法后正確率為87.2%(197/226)，提高了12.5%，說明本文化簡方法降低了局部形態(tài)差異產(chǎn)生的噪聲，從而減少了轉角函數(shù)描述線要素的不確定性，改善了道路網(wǎng)匹配結果。

5轉角函數(shù)匹配結果對比統(tǒng)計(step=1.0Slimit=1∶500 000)

Tab.5Statistics and comparison of the buffer matching results (step=1.0Slimit=1∶500 000)

匹配方法參與匹配正確匹配未匹配匹配正確率/(%)轉角函數(shù)法2261656174.7本文方法2261972987.2

3.3匹配效率對比

由于本文方法是在原有匹配的基礎上，加入動態(tài)化簡對已有匹配算法未成功匹配的數(shù)據(jù)重新進行匹配，因此匹配效率降低是必然的。表6統(tǒng)計了上述兩試驗化簡前后匹配時間的變化。

表6　匹配時間統(tǒng)計

表6說明，經(jīng)動態(tài)化簡動態(tài)匹配后，匹配算法耗時均有所增加，其中緩沖區(qū)法的耗時增幅較大，這是因為構建緩沖區(qū)本身較為耗時，而動態(tài)匹配需要多次構建緩沖區(qū)，導致匹配速度降低。轉角函數(shù)法的匹配時間僅增加了2.9 s，在可接受范圍之內，能夠滿足實用。由于本文方法著重在于提高匹配正確率，未能較好地兼顧匹配的效率，匹配效率的研究將作為下一步的重點研究內容。

4結論

本文方法為基于已有匹配算法來提高多源線要素匹配正確率提供了一個有效途徑。在已有線要素匹配方法的基礎上，提出了采用動態(tài)化簡來輔助已有匹配方法，從而提高了匹配正確率。該方法也可以為面要素匹配提供參考借鑒。其優(yōu)勢在于可有效降低匹配數(shù)據(jù)的復雜性和可能產(chǎn)生的不確定性，增強已有匹配算法對整體形態(tài)相似度的識別與區(qū)分能力。

參考文獻：

[1]李德仁,龔健雅, 張橋平. 論地圖數(shù)據(jù)庫合并技術[J]. 測繪科學, 2004, 29(1): 1-4.

LI Deren, GONG Jianya, ZHANG Qiaoping. On the Conflation of Geographic Databases[J]. Science of Surveying and Mapping, 2004, 29(1): 1-4.

[2]WALTER V, FRITSCH D. Matching Spatial Data Sets: A Statistical Approach[J]. International Journal of Geographical Information Science, 1999, 13(5): 445-473.

[3]VOLZ S. An Iterative Approach for Matching Multiple Representations of Street Data[C]∥The 3rd Symposium on Location Based Services and Telecartography, Vienna, Austria, 2005.

[4]童小華, 鄧愫愫, 史文中. 基于概率的地圖實體匹配方法[J]. 測繪學報, 2007, 36(2): 210-217.

TONG Xiaohua, DENG Susu, SHI Wenzhong. A Probabilistic Theory-based Matching Method[J]. Acta Geodaetica et Cartographica Sinica, 2007, 36(2): 210-217. DOI: 10.3321/j.issn:1001-1595.2007.02.017.

[5]PERSOON E, FU K S. Shape Discrimination Using Fourier Descriptors[J]. IEEE Transaction on Systems, Man and Cybernetics, 1977, 7(3): 170-179.

[7]陳玉敏, 龔健雅, 史文中. 多尺度道路網(wǎng)的距離匹配算法研究[J]. 測繪學報, 2007, 36(1): 84-90.

CHEN Yumin, GONG Jianya, SHI Wenzhong. A Distance-based Matching Algorithm for Multi-scale Road Networks[J]. Acta Geodaetica et Cartographica Sinica, 2007, 36(1): 84-90.

[8]黃蔚, 蔣捷. 多尺度矢量簡單幾何實體數(shù)據(jù)幾何匹配方法研究[J]. 遙感信息, 2011(1): 27-31.

HUANG Wei, JIANG Jie. Simple Geometry Matching of Multi-scales Spatial Data[J]. Remote Sensing Information, 2011(1): 27-31.

[9]武芳, 朱鯤鵬. 線要素化簡算法幾何精度評估[J]. 武漢大學學報(信息科學版), 2008, 33(6): 600-603.

WU Fang, ZHU Kunpeng. Geometric Accuracy Assessment of Linear Features’ Simplification Algorithms[J]. Geomatics and Information Science of Wuhan University, 2008, 33(6): 600-603.

[10]王殷行,李白英, 徐泮林. 基于特普費爾公式的制圖綜合取舍比例探討[J]. 山東科技大學學報(自然科學版), 2006, 25(1): 40-46.

WANG Yinxing, LI Baiying, XU Panlin. Study on the Proportion with Synthetic Acceptance or Rejection on Cartography Based on F.f?pfer Formula[J]. Journal of Shandong University of Science and Technology (Natural Science), 2006, 25(1): 40-46.

[11]牛繼強, 徐豐. 線狀要素多尺度表達不確定性的綜合分析與評價研究[J]. 測繪科學, 2007, 32(6): 69-71.

NIU Jiqiang, XU Feng. General Analysis and Estimate Research on Uncertainty of Multi-scale Representation of Linear Feature[J]. Science of Surveying and Mapping, 2007, 32(6): 69-71.

[12]黃智深, 錢海忠, 王驍, 等. 基于降維技術的面狀居民地匹配方法[J]. 測繪科學技術學報, 2012, 29(1): 75-78.

HUANG Zhishen, QIAN Haizhong, WANG Xiao, et al. Dimension Decrease-oriented Habitation Matching Method[J]. Journal of Geomatics Science and Technology, 2012, 29(1): 75-78.

[13]付仲良, 邵世維, 童春芽. 基于正切空間的多尺度面實體形狀匹配[J]. 計算機工程, 2010, 36(17): 216-217, 220.

FU Zhongliang,SHAO Shiwei,TONG Chunya.Multi-scale Area Entity Shape Matching Based on Tangent Space[J]. Computer Engineering, 2010, 36(17): 216-217, 220.

[14]DOUGLAS D H, PEUCKER T K. Algorithms for the Reduction of the Number of Points Required to Represent a Digitized Line or Its Caricature[J]. The Canadian Cartographer, 1973, 10(2): 112-122.

[15]MCMASTER R B. Automated Line Generalization[J]. Cartographica: The International Journal for Geographic Information and Geovisualization, 1987, 24(2): 74-111.

[16]錢海忠, 武芳, 陳波, 等. 采用斜拉式彎曲劃分的曲線化簡方法[J]. 測繪學報, 2007, 36(4): 443-449.

QIAN Haizhong, WU Fang, CHEN Bo, et al. Simplifying Line with Oblique Dividing Curve Method[J]. Acta Geodaetica et Cartographica Sinica, 2007, 36(4): 443-449.

[17]鄧敏, 樊子德, 劉慧敏. 層次信息量的線要素化簡算法評價研究[J]. 測繪學報, 2013, 42(5): 767-773, 781.

DENG Min,FAN Zide,LIU Huimin.Performance Evaluation of Line Simplification Algorithms Based on Hierarchical Information Content[J]. Acta Geodaetica et Cartographica Sinica, 2013, 42(5): 767-773, 781.

[18]趙東保, 盛業(yè)華. 全局尋優(yōu)的矢量道路網(wǎng)自動匹配方法研究[J]. 測繪學報, 2010, 39(4): 416-421.

ZHAO Dongbao, SHENG Yehua. Research on Automatic Matching of Vector Road Networks Based on Global Optimization[J]. Acta Geodaetica et Cartographica Sinica, 2010, 39(4): 416-421.

[19]郝燕玲, 唐文靜, 趙玉新, 等. 基于空間相似性的面實體匹配算法研究[J]. 測繪學報, 2008, 37(4): 501-506.

HAO Yanling,TANG Wenjing,ZHAO Yuxin,et al. Areal Feature Matching Algorithm Based on Spatial Similarity[J]. Acta Geodaetica et Cartographica Sinica, 2008, 37(4): 501-506.

[20]顏玉龍, 江南. 線性目標多尺度表達的改進內插方法研究[C]∥第七屆全國地圖學與地理信息系統(tǒng)大會. 廣州: [s.n.], 2012.

YAN Yulong, JIANG Nan. The Study on Improvement Interpolation Method of the Linear Objective Multi-Scale Representation[C]∥Proceedings of the 7th National Conference on Cartography and Geography Information System. Guangzhou: [s.n.], 2012.

(責任編輯：宋啟凡)

修回日期： 2015-07-15

First author： CHEN Jingnan(1992—),female, postgraduate, majors in spatial data matching and auto map generalization.

E-mail： cjnchxy_ieu@163.com

E-mail： haizhongqian@163.com

Improving the Matching Rate of Line Feature by Using Dynamic Simplification

CHEN Jingnan,QIAN Haizhong,WANG Xiao,HE Haiwei,HU Huiming

Institute of Geographic Spatial Information, Information Engineering University, Zhengzhou 450000, China

Abstract：Vector line feature matching is one of the hot research in the field of spatial data matching. This paper proposes a method of improving the accuracy of line feature matching based on dynamic simplification. Firstly, use the square root law to respectively determine the numeric ranges of the simplification thresholds for the two matching line features; then, let the threshold change by a certain step within this range, and simplify the line features separately. After every simplification is completed, the matching similarity is recalculated and replaced by a higher value so as to attain the maximum similarity. Finally, compare the maximum similarity with the matching threshold to judge if the two line features match. This algorithm is essentially a process which adopts the dynamic simplification to drive the dynamic matching. The dynamic simplification can retain line’s main morphological feature, in this way the impact of local details on matching algorithm decreases, accordingly the matching accuracy is improved. The validity and universality of the presented method is proved through experiments and comparative analysis.

Key words：line feature matching; dynamic simplification; square root law

Corresponding author：QIAN Haizhong

通信作者：錢海忠

第一作者簡介：陳競男(1992—)，女，碩士生，研究方向為空間數(shù)據(jù)匹配、自動制圖綜合。

收稿日期：2015-02-02

基金項目：國家自然科學基金(41171305；41571442)

中圖分類號：P208

文獻標識碼：A

文章編號：1001-1595(2016)04-0486-08

Foundation support： The National Natural Science Foundation of China (Nos.41171305;41571442)

引文格式：陳競男，錢海忠，王驍，等.提高線要素匹配率的動態(tài)化簡方法[J].測繪學報，2016,45(4)：486-493. DOI:10.11947/j.AGCS.2016.20150074.

CHEN Jingnan,QIAN Haizhong,WANG Xiao,et al.Improving the Matching Rate of Line Feature by Using Dynamic Simplification[J]. Acta Geodaetica et Cartographica Sinica,2016,45(4):486-493. DOI:10.11947/j.AGCS.2016.20150074.