多尺度河流和湖泊的矢量目標匹配方法研究

鐘 東，郭慶勝，王 勇，劉紀平

(1.武漢大學 資源與環境科學學院，湖北 武漢 430070;2中國測繪科學研究院，北京 100830)

多尺度河流和湖泊的矢量目標匹配方法研究

鐘 東1，郭慶勝1，王 勇2，劉紀平2

(1.武漢大學 資源與環境科學學院，湖北 武漢 430070;2中國測繪科學研究院，北京 100830)

研究河流和湖泊的矢量目標匹配方法在地理空間變化檢測、地圖更新等方面具有重要意義。文中提出一種計算線線部分匹配的折線集的算法，基于該算法和面面疊置率，研究河流和湖泊的面面、面線、線線1∶1匹配算法和非1∶1匹配策略，實現河流和湖泊整個目標數據集的匹配。實驗表明，文中所研究的算法和策略具有兩個優點：解決了面與線在不相交情況下的匹配問題；對數據誤差有很強的適應性。

多尺度; 河流;湖泊;目標匹配

空間目標匹配可以為進一步探測不同數據集之間的差異或變化奠定基礎[1]，河流和湖泊是兩類重要的地物，研究河流和湖泊的多尺度矢量目標匹配技術在地圖合并、地圖更新、變化檢測等方面有重要意義[1-2]。河流和湖泊空間目標匹配包括1∶1匹配和非1∶1匹配兩大類。已有的面面1∶1匹配算法主要包括基于相似度匹配方法[2]、基于拓撲關系進行匹配的方法[3-4]、基于模糊拓撲關系分類進行匹配的方法[5-6]、基于概率的面目標匹配方法[7]、基于重疊度的面目標匹配方法[8-9]；已有的線線1∶1匹配算法主要有基于幾何相似度的匹配方法[7, 10]、基于拓撲結構的匹配方法[11-12]、基于智能化方法的匹配方法[13-14]；而面線匹配主要通過提取面的骨架線與線目標進行匹配來完成[15-16]。現有算法難以解決面線不相交情況下的匹配，對數據誤差的適應性差。本文提出利用線與線部分匹配的折線集，改進基于幾何相似度的線線1∶1匹配算法，并將面線匹配轉換成線線匹配，將面面、面線、線線1∶1匹配的結果應用于非1∶1匹配。

1 河流和湖泊目標匹配的特點

河流要素在幾何上主要有以下3個特點：①河流多為狹長面目標；②同一地形圖上，不同河流之間的寬度差異可能較大；③同一條河流的不同部分的寬度差異可能較大。相對于河流，湖泊的特點則表現為面積較大，部分湖泊有狹長支流。

一般情況下，目標匹配先基于語義挑選出同一類型的地物，然后再進行匹配。對河流和湖泊而言，大比例尺的河流只與小比例尺上的河流匹配，湖泊亦如此。但是當湖泊與河流相接時，湖泊的某一部分可能變為小比例尺的一小段單線河，此時可以考慮河流和湖泊的跨地物類型匹配。如圖1所示，M0(粗實線)和N0(粗虛線)分別表示大比例尺上的湖泊和單線河，M1(細實線)和N1(細虛線)分別表示小比例尺上的河流和湖泊，C0和C1是N1上的兩個點，陰影部分表示M0的一條細小支流。由于制圖綜合的影響，M0的細小支流在小比例尺上以單線河(折線段C0-C1)的形式呈現。于是，就存在湖泊M0(湖泊的部分)與河流N1(河流的部分)之間的匹配。值得注意的是，此處匹配只是建立目標M0，N0與目標M1，N1之間的關系，而各目標的語義并沒有發生變化。

圖1 河流和湖泊跨類型匹配

在參與匹配的數據源中，通常將現勢性好、位置精度高的數據源稱為參考數據源(通常為較大比例尺)，而將現勢性較差、位置精度相對較低的數據源稱為目標數據源(通常為較小比例尺)[2]。導致不同地圖空間中的同名目標之間的差異的原因有很多，主要包括制圖綜合、實際變化和數據誤差3種[15]。其中制圖綜合是導致同名目標發生變化的主要原因，根據綜合算子不同又分為選取、簡化(包括尺度變化)、多目標的合并、移位、夸大以及典型化。實際變化包括地物的出現、改變和消失。數據誤差則體現在目標位置的改變。

目標選取和出現導致在小比例尺地圖上沒有與大比例尺地圖上相對應的目標。目標消失則導致小比例尺地圖上的目標在大比例尺地圖上不顯示。數據誤差和移位導致目標的位置差異。簡化、夸大會造成目標在空間形狀、大小等表達上的差異，簡化也可能導致目標尺度發生變化。合并、典型化則會造成目標在空間形狀、大小和結構等多方面的差異，合并還可能導致目標的數量發生改變。

矢量數據的幾何類型分為點、線、面，河流和湖泊匹配主要考慮面與線2種幾何類型。由于河流和湖泊本身的特點以及尺度的變化，參考數據源和目標數據源中均可能出現面目標和線目標，則河流和湖泊的匹配類型(幾何)就分為面面、面線、線線匹配3種幾何類型組合。

文獻[15]和[16]根據每輪匹配中參考數據源和目標數據源的目標數量之比分為1∶0、0∶1、1∶1、1∶M、N∶1、N∶M 6種匹配模式，本文提出的匹配模式與此相同，只是每輪匹配中參考數據源中的目標數量和目標數據源中的目標數量均有可能是面目標數量與線目標數量的總和。

因此，河流和湖泊的匹配類型可以歸納為未匹配、面面匹配、面線匹配、線線匹配4種，匹配模式可以歸納為未匹配(1∶0、0∶1)、1∶1匹配、非1∶1(1∶M、N∶1、N∶M)匹配3種。對于未匹配的情況，其實沒有單獨涉及到匹配算法，因此，本文只需考慮面面匹配、面線匹配、線線匹配3種匹配類型和1∶1、非1∶1兩種匹配模式。

2 計算線線部分匹配的折線集

兩條折線的匹配可以分為完全匹配和部分匹配。在部分匹配時，匹配成功的部分由一系列折線段組成，本文稱這些折線段構成的集合為線線部分匹配的折線集。為了盡可能準確地計算能部分匹配的折線段，需要對線目標進行頂點加密。匹配的兩條折線段的距離應該為零，方向應該一致，但由于地圖數據誤差的影響，距離和方向都存在一定的偏差。因此，在匹配時，需要指定距離閾值和方向閾值。一般情況下，視力正常的人的肉眼能分辨的圖上最短距離是0.1 mm，距離閾值的設定也是為適應地圖的誤差，再根據3倍中誤差原則，可得距離閾值的算式為

式中：s為地圖比例尺分母；D表示實地距離，單位為m。

如圖2，L1表示細實線，L2表示細虛線，頂點1到頂點8和頂點9到頂點16分別表示L1和L2頂點加密后的部分頂點。假設L1和L2加密后的頂點集分別為P1和P2，兩個臨時的頂點集合T1、T2，則計算L1與L2部分匹配的折線集的算法描述如下(見圖2)：

圖2 計算線線部分匹配的折線集原理

1)遍歷頂點集合P1，得到點1，在P2中找到點1的最近點(圖1的點9)，由于點1和點9之間的距離大于D，繼續遍歷P1集合。清空T1和T2。

2)當遍歷到點3時，在P2中找到點3的最近點(點11)，點3和點11之間的距離小于D，但由于T1和T2均為空，不能判斷方向，直接將點3加入集合T1，點11加入集合T2。

3)當遍歷到點4時，在P2中找到點4的最近點(點12)，點4和點12之間的距離小于D，此時T1和T2不為空，則計算線段(3-5)和線段(11-12)的方向β，由于β小于α，因此將點4加入集合T1，點12加入集合T2。

4)當遍歷到點5時，在P2中找到點5的最近點(點13)，點5和點13之間的距離小于D，此時T1和T2不為空，則計算線段(4-5)和線段(12-13)的方向β，由于β小于α，因此將點5加入集合T1，點13加入集合T2。

5)繼續遍歷P1集合，當遍歷到點8時，在P2中找到點8的最近點(點16)，點8和點16之間的距離大于D，因此，不能再向T1和T2中添加頂點8和16，此時的頂點集合T1和T2就構成兩個折線段。存儲T1、T2，再清空T1和T2繼續遍歷。

6)同理，可以按照步驟1)到步驟5)計算L1與L2部分匹配的其他折線段，所有的折線段構成的集合就是L1與L2部分匹配的折線集。

L1與L2部分匹配的折線集計算結果如圖3所示。圖中粗實線(折線段a，b，c，d)表示部分匹配的折線集，該折線集分為兩部分：L1上的部分匹配的折線集({a，b})和L2上的部分匹配的折線集({c，d})。

圖3 部分匹配的折線集計算結果

3 1∶1匹配算法和非1∶1匹配策略

目標A(面或線)與目標B(面或線)的1∶1匹配結果有5種(假設每種結果用一個整數表示)： ①A與B未匹配(用0表示)； ②A與B(完全)匹配(用1表示)； ③A部分匹配B，也就是A匹配B的一部分，(用2表示)； ④B部分匹配A，也就是B匹配A的一部分，(用3表示)； ⑤A部分匹配B，同時，B也部分匹配A，(用4表示)。

3.1 線線、面線1∶1匹配算法

假設L1與L2的部分匹配的折線集為R，其中L1上的部分匹配的折線集為R1，L2上的部分匹配的折線集為R2，則L1與L2部分匹配的長度ML1為R1所有折線段的長度和，L1與L2部分匹配的長度ML2為R1所有折線段的長度和，再假設L1的長度為Len1，L2的長度為Len2，則有L1與L2的相似度S1和L2與L1的相似度S2為

將計算改進的線線相似度的思想與文獻[15]和[16]中的面線匹配算法進行融合，可以彌補現有面線1∶1匹配算法的缺陷。假設面目標P和線目標L進行1∶1匹配，P的骨架線集合為Ske，i表示Ske中第i個元素(i= 0, 1, …,n-1)，n為Ske集合的元素個數。先計算每條骨架線與L的部分匹配的折線集，從而得到Ske中第i條骨架線與L匹配的長度為SL1i，L與Ske中第i條骨架線匹配的長度為SL2i。再假設面P的所有骨架線的長度和為PL，線目標L的長度為LL，則得到P與L的相似度S1和L與P的相似度S2為

3.2 面面1∶1匹配算法

同一地區不同來源的地圖(即使是不同比例尺)在消除整體和局部坐標偏差后，同名面實體總是會有較大的重疊面積；面實體之間的重疊面積大小反映兩個面之間的距離差異以及形狀差異等，而且它反映兩個面實體之間的整體相似性，符合人眼的視覺效果[5]。因此,本文使用面面疊置率來計算面面1∶1匹配結果。在重疊面積的基礎上，面積疊置率定義為兩個面域重疊部分面積與各自總面積的比率[6]。假設面A1的面積為a1，面A2的面積為a2，A1與A2的重疊面積為a0，則A1與A2的疊置率O1和A2與A1的疊置率O2分別為

改革開放的總設計師鄧小平同志曾說過：“科學技術是第一生產力”，目前通明公司雖然仍存在很多不盡如人意的地方，但是我相信，在單位領導的正確領導下，只要我們不斷提高自身業務水平，培養并儲備充足的技術人才，我們一定有足夠的能力和社會上的路燈企業競爭，在日后的工程投標中勝出，成為市場經濟大環境下的弄潮兒。

在進行面面、面線、線線1∶1匹配時，由于地圖誤差的存在，面、線目標的位置有誤差，使得完全匹配的兩個目標，其相似度S1，S2(疊置率O1，O2)不一定為1，因此，當S1，S2(疊置率O1，O2)均大于一定閾值Smax(Omax)，就可以認為這兩個目標是完全匹配的。同理，由于地圖誤差的存在，如果兩個目標的相似度S1，S2(疊置率O1，O2)均小于一定閾值Smin(Omin),則認為這兩個目標不匹配。假設目標A(面或線)和目標B(面或線)的1∶1匹配結果用r表示，則A與B的1∶1匹配結果的判斷規則如圖4所示(以面線、線線為例，面面1∶1匹配結果的判斷規則類似)。

圖4 1∶1匹配結果判斷規則

3.3 非1∶1匹配策略

針對河流和湖泊的目標匹配，本文的策略是：使用面面、面線、線線1∶1匹配算法，計算兩個目標的1∶1匹配結果，然后根據1∶1匹配結果進行非1∶1匹配。在進行河流和湖泊的目標匹配時，參與匹配的數據集有4個：參考數據源的面目標集DS1、線目標集DS2，目標數據源的面目標集DS3、線目標集DS4。大比例尺地圖上的面目標在小比例尺地圖上變成線目標是由尺度變化引起的，因此不考慮大比例尺地圖上的線目標與小比例尺地圖上的面目標進行匹配的情況，并且，參考數據集中的目標只能和目標數據集中的目標匹配。因此，數據集之間可能進行匹配的對應關系是：DS1與DS3、DS4，DS2與DS4，DS3與DS1，DS4與DS1、DS2。匹配時，遍歷對應數據集中的目標，針對當前遍歷得到的兩個目標(假設為OB1和OB2)，根據其幾何類型組合，選擇使用面面、面線或線線1∶1匹配算法，計算其1∶1匹配結果r，根據r的值做如下處理：

1)若r=0，OB1與OB2不匹配，此時只需要繼續遍歷數據集中的下一個目標；

2)若r=1，OB1與OB2完全匹配，OB1與OB2均不需要再跟別的目標匹配；

3)若r=2，OB1部分匹配OB2，OB1不需要再跟別的目標匹配，而OB2需要再跟別的目標匹配；

5)若r=4，OB1部分匹配OB2，同時，OB2也部分匹配OB1，OB1與OB2均需要再跟別的目標匹配。

由于待匹配的河流和湖泊數據集龐大，在匹配的過程中使用了格網索引、MBR[15-16]等技術。格網索引可以有效縮小遍歷范圍，而在判斷兩個目標是否匹配時，要先判斷這兩個目標的MBR是否相交，如果相交則再使用相應的1∶1匹配算法，對于MBR不相交的目標則不需要計算其1∶1匹配結果，可有效減少計算時間。

4 實驗與分析

為了驗證本文所研究的算法和策略的正確性，用武漢市局部地區的水系數據進行實驗。該實驗的參考數據源為1∶50萬，有115個面狀目標(圖5(a)實線)和24個線狀目標(圖5(a)虛線)；目標數據源為1∶400萬，有43個面狀目標(圖5(b)實線)和46個線狀目標(圖5(b)虛線)。實驗中，設置插點距離為100 m，距離閾值為150 m，方向閾值為0.5度，Smax和Omax都為0.9，Smin和Omin都為0.1。

圖5 實驗數據

實驗結果如表1所示，有49對目標匹配成功，15對目標未匹配。匹配成功目標的幾何類型組合有面、線—面、線，面—面，面—線，線—線4種；未匹配的目標包括參考數據源中的12個面目標和目標數據源的3個線目標。圖6(a)和圖6(b)分別對應圖5中①號方框和②號方框所在位置的數據的放大，圖6(c)對應圖6(b)中③號方框所在位置的數據的放大，這幾個位置的數據比較典型。通過實驗，本文所研究的算法和策略的優點得以證明：

表1 實驗結果

1)面線不相交情況下依然能匹配成功。如圖6(a)所示，X(粗實線表示的面目標)為參考數據源的面目標，Y3為(粗虛線表示的線目標)參考數據源的線目標，Y1和Y2(細虛線表示的線目標)為目標數據源的線目標，Z1，Z2為折線Y2上的兩個點。使用本文的算法和策略對這幾個目標進行匹配的過程是：①遍歷參考數據源和目標數據源得到兩個目標，不失一般性，假設當前遍歷得到的兩個目標為X和Y2；②使用面線1∶1匹配算法計算X和Y2的1∶1匹配結果r，X目標上的陰影部分的骨架線應該和Y2目標上的Z1-Z2折線段匹配，因此，對于X與Y2而言，應該是X部分匹配Y2，同時Y2也部分匹配X(r=4)；③r= 4，則X和Y2都有可能跟別的目標匹配，針對X和Y2繼續遍歷對應的數據集，可以得到X與Y1的面線匹配和Y3與Y2的線線匹配。最終，參考數據源的X，Y3目標與目標數據源的Y1，Y2目標匹配成功，匹配模式為2∶2。彌補了文獻[15]和[16]中的面線匹配缺陷，解決面X與線Y2不相交情況下的匹配。

圖6 實驗數據局部放大

2)對數據誤差的適應性強。如圖6(b)所示，Q1，Q2(粗實線表示的面目標)為參考數據源的面目標，Q3，Q4(細虛線表示的面目標)為目標數據源的面目標。實際情況是Q1與Q3匹配，Q2與Q4匹配，但是，由于數據誤差的影響，Q1與Q4的疊置率卻不為零(圖6(c)中陰影部分)。本文設置了疊置率閾值Omin，而計算得到的Q1與Q4的疊置率和Q4與Q1的疊置率均小于Omin，故Q1與Q4匹配不成功，不影響Q1與Q3的匹配和Q2與Q4的匹配。

5 結束語

河流和湖泊的匹配是面面、面線和線線相結合的匹配，也是1∶1匹配與非1∶1匹配相結合的匹配。使用本文所研究的面面、面線、線線1∶1匹配算法和非1∶1匹配策略對河流和湖泊數據集進行匹配，取得了良好的匹配效果。在這些算法的基礎上，為了提高計算效率，還用到格網索引、MBR等技術，很好的解決了河流和湖泊的匹配問題。

由于目標匹配是為地圖更新、變化檢測等研究服務的，對地圖更新、變化檢測等方向的深入研究也是亟需解決的問題，還需要做進一步的努力。

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

[2] 翟仁健. 基于全局一致性評價的多尺度矢量空間數據匹配方法研究[D]. 鄭州：信息工程大學, 2011.

[3] MASUYAMA A. Methods for Detecting Apparent Differences Between Spatial Tessellationsat Different TimePoints[J]. InternationalJournal of Geographical Information Science, 2006, 20(6):633-648.

[4] YUAN S, TAO C.Development of Conflation Components[A].ProceedingsofGeoinformatics1999 Conference[C]. Ann Arbor, 1999:1-13.

[5] 張橋平, 李德仁, 龔健雅. 城市地圖數據庫面實體匹配技術[J]. 遙感學報, 2004, 8(2):107-112.

[6] 郭黎, 崔鐵軍, 王豪,等. 基于面狀要素拓撲關系的數據匹配技術研究[J]. 測繪科學, 2010, 35(1):130-132.

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

[8] VON G,SESTER G.Change Detection and Integration of Topographic Updates from ATKIS to Geoscientific DataSets[A]. International Conferenceon Next Generation Geospatial Information[C]. Boston, October 2003:19-21.

[9] VAN W,VANPUTTEN F,VANOOSTEROM J,et al.Map Integration-Update Propagation In A Multi-Source Environment[A]. Proceedings of the 5th ACM International Workshop on Advances In Geographic Information Systems[C]. Las Vegas, Nevada, United States,1997:71-76.

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

[11] FILIN S, DOYTSHER Y. The Detection of Corresponding Objects In A Linear-Based Map Conflation[J]. Surveying and Land Information Systems,2000,60(2):117-128.

[12] MANTEL D, LIPECK U. Matching Cartographic Objects in Spatial Databases[A]. ISPRS Vol. XXXV, ISPRS Congress, Commission 4[C]. Istanbul, Turkey, July 12-23th, 2004.

[13] 張云菲, 楊必勝, 欒學晨. 利用概率松弛法的城市路網自動匹配[J]. 測繪學報, 2012,41(6):933-939.

[14] TONG Xiaohua, LIANG Dan, JIN Yanmin. A linear road object matching method for conflation based on optimization and logistic regression[J]. International Journal of Geographical Information Science, 2014, 28(4):824-846.

[15] 趙彬彬. 多尺度矢量地圖空間目標匹配方法及其應用研究[D]. 長沙：中南大學, 2011.

[16] 趙彬彬, 鄧敏, 劉慧敏,等. 多尺度地圖的水系面目標與線目標匹配方法與實驗[J]. 地球信息科學學報, 2011, 13(3):361-366.

[責任編輯：張德福]

Research on the method of multi-scale vector objects matching for rivers and lakes

ZHONG Dong1, GUO Qingsheng1, WANG Yong2, LIU Jiping2

(1. School of Resource and Environmental Science, Wuhan University, Wuhan 430070, China;2. Chinese Academy of Surveying and Mapping, Beijing 100830，China)

It is important to study the vector object matching method of rivers and lakes in geospatial changing detection and map updating. In this paper, an algorithm on calculating the polyline set in partly matching of line to line is put forward, and based on this and area to area overlay rate, the one to one matching algorithm for area to area, area to line and line to line, and tactics of not one to one matching for rivers and lakes are presented. The matching of the whole dataset of rivers and lakes can be realized. The experiments show that the algorithm and tactics in this paper has two advantages: a.the matching can be resolved when an area does not intersect with a line; b.it has a great adaptation to data error.

multi-cale; rivers; lake; object matching

著錄：鐘東，郭慶勝，王勇，等.多尺度河流和湖泊的矢量目標匹配方法研究[J].測繪工程，2017，26(10)：70-75.

10.19349/j.cnki.issn1006-7949.2017.10.013

2016-10-14

國家自然科學基金資助項目(41471384);測繪地理信息公益行業科研專項項目(201512032)

鐘 東(1992-)，男，碩士研究生.

P208

A

1006-7949(2017)10-0070-06