徐 晶 晶，趙 東 保*，鄧 悅，曹 連 海，管 相 榮

(1.華北水利水電大學測繪與地理信息學院，河南 鄭州 450046;2.河南省自然資源綜合保障中心，河南 鄭州 450016)

0 引言

隨著空間數(shù)據(jù)獲取技術迅速發(fā)展,海量矢量空間數(shù)據(jù)涌現(xiàn)，由于數(shù)據(jù)尺度、精度、時相以及不同部門對同一地物的理解和服務目的等不同，即使覆蓋相同地理范圍的空間數(shù)據(jù)也存在各種差異，從而導致同名面目標之間存在復雜的匹配對應關系，因此需要進行空間數(shù)據(jù)融合。同名目標匹配是數(shù)據(jù)融合的關鍵環(huán)節(jié)[1]，由于居民地面目標在面要素類數(shù)據(jù)庫中數(shù)量多、占比大、匹配關系復雜，因此以居民地為代表研究同名面目標的匹配對實現(xiàn)空間數(shù)據(jù)的更新與融合具有重要意義。

面目標匹配通?；谕負涮卣鱗2-8]和幾何特征[9-13]，利用拓撲關系、形狀、大小、位置等特征指標進行匹配，而語義特征也經(jīng)常作為輔助信息用于匹配。在拓撲特征匹配方面，有學者利用拓撲關系的疊置特性進行面目標匹配[2-4]，但該類方法的重要前提是待匹配面目標已經(jīng)消除坐標差異且位置極為接近，也有學者對空間目標的鄰近關系進行分析[5-8]，但該類方法僅用拓撲關系進行匹配，未使用幾何條件，未能充分利用現(xiàn)有信息，且對數(shù)據(jù)的質量要求較高；在幾何特征匹配方面，有學者利用面目標的形狀、大小、距離、尺寸、方向、面積、外接矩形等幾何指標構建幾何相似度，雖有效解決了指標單一不可靠的問題，但具體權重不易判斷，匹配結果的魯棒性較差[9-13]，有學者通過引入形狀描述算子(傅里葉描述子[14]、矩描述子[15]等)計算面目標形狀相似程度，進而判定面目標之間的匹配關系，但該類方法僅能處理一對一匹配類型的數(shù)據(jù)，難以處理復雜數(shù)據(jù)。因此，為實現(xiàn)更精確的數(shù)據(jù)融合，應考慮從多特征出發(fā)，綜合使用多種相似性測度進行面目標匹配，在處理復雜匹配關系的同時能有效抵抗位置偏差，也可提高同名面目標匹配的準確率。例如，將幾何相似度與語義相似度結合，以完成同名面目標的準確匹配[16-18]；針對復雜匹配類型的數(shù)據(jù)，根據(jù)多個幾何指標定義面目標的上下文位置關系，再借助神經(jīng)網(wǎng)絡完成面目標匹配[19]；將矩形相似度和空間疊置關系結合，提高位置偏差較大時同名面目標匹配的準確率[20]等，但該類算法計算繁瑣、耗時較長，難以高效處理大規(guī)模數(shù)據(jù)。

綜上，為實現(xiàn)面目標位置的進一步融合，還需對同名面目標的同名特征點進行自動匹配[21]。在數(shù)字圖像處理等領域[22-27]，有RANSAC[28]、SIFT[29]與BRISK[30]等典型的圖像特征點匹配算法，但缺少針對多源、多尺度情況下同名矢量面目標之間特征點匹配問題開展專門研究，尤其是缺乏針對存在復雜匹配關系的同名面目標之間特征點的匹配算法。因此，本文同時考慮多源同名面目標的自動識別以及同名面目標上同名特征點的自動匹配問題，以期為位置融合奠定重要基礎。

1 多源同名居民地面目標的自動識別與匹配

多源同名居民地面目標的自動識別與匹配主要包括3個階段：基于空間相交關系的候選匹配居民地面目標集合確定、參考居民地面目標與調整居民地面目標的候選匹配對獲取和同名居民地面目標匹配關系確定。

1.1 基于空間相交關系的候選匹配居民地面目標集合確定

多源居民地面目標匹配類型可總結為1∶0、1∶N、M∶N等，產(chǎn)生原因有以下3種情況：1)在進行跨比例尺地圖綜合時，取舍環(huán)節(jié)會產(chǎn)生1∶0或0∶1匹配類型，地圖概括環(huán)節(jié)會產(chǎn)生1∶N或M∶1及M∶N匹配類型；2)數(shù)據(jù)采集人員對同一地物的理解以及需求等不同，導致出現(xiàn)多種匹配結果；3)實地區(qū)域變化伴隨著居民地面目標新增或消失，抑或是局部修改，1∶0或0∶1等匹配類型隨之出現(xiàn)。一般而言，在進行空間數(shù)據(jù)融合時，盡管待匹配的兩組面目標集合可能存在跨尺度現(xiàn)象，但尺度相差不大，且由于面目標通常在圖幅中占據(jù)較大的空間范圍，因此在絕大多數(shù)情況下，可利用空間相交關系確定候選匹配居民地面目標對象。

假設Ri為參考居民地面目標集合R中的一個居民地面目標，Tj為調整居民地面目標集合T中的一個居民地面目標，若Tj與Ri存在空間相交關系，則將該調整居民地面目標Tj加入?yún)⒖季用竦孛婺繕薘i的候選匹配對象序列中，然后在T中依次找出所有符合上述條件的調整居民地面目標，并加入?yún)⒖季用竦孛婺繕薘i的候選匹配對象序列中，最終獲取R、T中每個居民地面目標的候選匹配對象。

1.2 參考居民地面目標與調整居民地面目標的候選匹配對獲取

針對每個居民地面目標的候選匹配對象，進一步得到所有的候選匹配對集合，并使該集合盡可能包含所有正確的匹配對。對于參考居民地面目標集合R和調整居民地面目標集合T，利用算法交迭從兩集合中選擇候選匹配居民地面目標組合，形成候選匹配對。

以圖1為例，參考居民地面目標集合R有R1、R2和R33個居民地面目標，調整居民地面目標集合T有T1和T2兩個居民地面目標，R1的候選匹配居民地面目標對象為T1，R2的候選匹配居民地面目標對象為T1、T2，R3的候選匹配居民地面目標對象為T2，T1的候選匹配居民地面目標對象為R1、R2，T2的候選匹配居民地面目標對象為R2、R3。從R1開始，R1在調整居民地面目標組合中的候選匹配居民地面目標為T1，此時得到第一個候選匹配對(R1∶T1)，依次交迭判斷可獲得T1∶(R1，R2)、(R1，R2)∶(T1，T2)、(T1，T2)∶(R1，R2，R3)等其他匹配對，當滿足以下任一條件時，候選匹配對的搜尋過程結束：1)無法進一步獲取候選匹配對，如圖1中在獲得第四組候選匹配對后，各個居民地面目標均已參與運算，已無法再獲得新的候選匹配對；2)準備生成的候選匹配對此前已經(jīng)生成，如圖1中匹配對(R1，R2，R3)∶(T1，T2)先后出現(xiàn)兩次，在第二次搜尋時即可終止。

圖1 候選匹配對象查找示意Fig.1 Schematic diagram of candidate matching object searching

1.3 同名居民地面目標匹配關系確定

對于所獲取的候選匹配對需進一步確定其匹配關系并給出匹配相似度。由于兩組不同來源的居民地面目標之間往往存在形狀差異和距離偏差，因此需要一種可靠的匹配相似度計算方法。除計算二者最初的重疊相似度以外，本文還對匹配對中的參考居民地面目標進行位置偏移，使參考居民地面目標與調整居民地面目標在位置上進一步配準。具體而言：分別將每個匹配對中的所有參考居民地面目標集合R、調整居民地面目標集合T進行合并，再將合并后R的質心移至合并后T質心的位置，實現(xiàn)質心的配準；之后分別計算配準前的重疊相似度ρbefore(式(1))和配準后的重疊相似度ρafter(式(2))，取二者平均值記為居民地面目標之間的匹配相似度ρfeature(式(3))；最后按照匹配相似度最大原則，篩選最終的多源居民地面目標匹配結果，確定多源居民地面目標匹配對應關系。

ρbefore=S2/(SRST)

(1)

ρafter=S′2/(SRST)

(2)

ρfeature=(ρbefore+ρafter)/2

(3)

式中：SR為參考居民地面目標集合R的面積；ST為調整居民地面目標集合T的面積；S和S′分別為R平移前后二者的重疊部分面積。

2 同名居民地面目標上同名特征點的自動識別與匹配

在自動識別出同名居民地面目標后，對同名面目標進行幾何糾正，進而實現(xiàn)同名面目標在空間位置上的融合，在同名居民地面目標匹配結果基礎上實現(xiàn)同名居民地面目標特征點的自動匹配。

2.1 基于編輯距離的同名居民地面目標上同名特征點自動匹配

本文使用編輯距離算法尋找同名居民地面目標之間特征點的匹配對應關系，該特征點是指依據(jù)待匹配面要素數(shù)據(jù)集的比例尺選擇相應的閾值進行多邊形化簡所提取的點。編輯距離算法用于處理兩個字符串str1與str2之間的匹配問題[31]，算法規(guī)定在匹配過程中只能進行插入、刪除、替換3種操作，每種操作需要耗費相應代價，匹配完成后，操作所需的最小總代價可表示str1與str2的匹配程度。若將組成居民地面目標的每個特征點看作一個字符，則兩個待匹配的居民地面目標可看作兩個字符串，從而將編輯距離算法運用于居民地面目標的特征點匹配中，確保同名居民地面目標特征點的匹配結果保持拓撲關系一致性，避免交叉匹配現(xiàn)象。

假設R、T互為同名居民地面目標，分別對應特征點集合R(p1,p2,p3,…,pm-1,pm)和T(q1,q2,q3,…,qn-1,qn)，且R、T的每個特征點均有特征量U(pm)、V(qn)，共包括k組對應點{(px1,qy1),(px2,qy2),(px3,qy3),…,(pxk,qyk)},其中x1=y1=1，xk=m，yk=n，使對應頂點間特征量之差的總和最小，則此時所耗費的代價可表示為函數(shù)C(式(4))，當C取最小值時，對應的特征點配對序列為最優(yōu)的特征點匹配序列。

(4)

2.2 同名居民地面目標特征點對匹配相似度計算

編輯距離算法的關鍵在于構建可靠特征點匹配對的匹配相似度，本文分別定義向量方向相似度、面積比相似度和距離鄰近度3種特征指標。假設已經(jīng)確定同名居民地面目標，且二者質心之間的平均距離為r，則針對參考居民地面目標R的每個特征點，在調整居民地面目標T中與其距離不超過r的特征點則為其候選匹配點。

圖2 方向相似度和面積比相似度的計算Fig.2 Calculation of vector direction similarity and area ratio similarity

(5)

(2)面積比相似度。以圖2為例，可以看出調整居民地面目標T1中的q3點內(nèi)部區(qū)域的夾角為270°，與參考居民地面目標中p3、p6、p93個點的角度值(90°)明顯不同，但如果構建面積比相似度，則發(fā)現(xiàn)其局部特征很相似。對于參考居民地面目標R2的p6點，以p6點為圓心，以r為半徑做圓C1，對于調整居民地面目標T1的q3點，以q3點為圓心，同樣以r為半徑做圓C2，則面積比相似度可由式(6)計算；對式(6)進一步簡化，使其值域在[0,1]之間(式(7))，可以發(fā)現(xiàn)，盡管p6和q3點的角度值明顯不同，但其面積比卻極為接近，符合人眼的視覺觀察。

(6)

式中：S1為各參考居民地面目標與圓C1相交部分的面積之和(圖2a中陰影部分)；S2為各調整居民地面目標與圓C2相交部分的面積之和(圖2b中陰影部分)；S為圓C1和C2的面積。

(7)

(3)距離鄰近度。在匹配過程中，距離遠近也是匹配對應關系的重要判別指標，為此定義特征點的距離鄰近度指標，計算公式為：

ρ3=1-distance(p6,q3)/r

(8)

式中：distance(p6,q3)為p6、q3兩點間的距離。

進一步綜合考慮向量方向相似度、面積比相似度與距離鄰近度，構成特征點之間的匹配相似度ρpoint，計算公式為：

ρpoint=w1×ρ1+w2×ρ2+w3×ρ3

(9)

式中：w1、w2、w3為3個相似度指標的權重，通常設置為1/3。

2.3 同名居民地面目標特征點序列對應關系的最短路徑求取

本文算法的基本目標是找到特征點對之間的對應關系使代價函數(shù)C值最小，因此可看成求取一條同名居民地面目標特征點序列對應關系的最短路徑，可采用動態(tài)規(guī)劃法求取，即當沿路徑的累計距離D(i,j)(式(10))最小時，該路徑即為最短路徑。

D(i,j)=M(i,j)+min{D(i-1,j),D(i,j-1),

D(i-1,j-1)}

(10)

式中：i∈(1,m),j∈(1,n),M(i,j)為當前格點距離。

在參考居民地面目標與調整居民地面目標匹配過程中，本文首先指定參考居民地面目標的起始特征點，然后依次變換調整居民地面目標的起始點，每變換一次，計算一次總的代價函數(shù)C，則最小代價函數(shù)所對應的路徑為最短路徑，將最短路徑進行回溯得到特征點對之間的最佳對應關系。由于多源居民地面目標之間可能存在M∶N匹配關系，故采用編輯距離方法在參考居民地面目標與調整居民地面目標之間進行同名特征點序列匹配，即執(zhí)行M×N次編輯距離算法，以獲取多源居民地面目標特征點的匹配對應關系。

2.4 特征點匹配對應關系進一步處理

多源居民地面目標之間的M∶N匹配關系結果中特征點之間可能存在多重匹配對應關系，針對此種匹配結果需進行特殊處理。例如，在圖3a中，多源居民地面目標之間存在M∶N匹配關系，特征點匹配結果如圖3a中紅色短線所示，其中，r5點與t7、t8點，t8點與r5、r6點，r4點與t4、t6點，t3點與r9、r10、r11點，其間存在非一對一的匹配對應關系。針對此種情況采用如下策略進行處理，以確保特征點之間的一一匹配對應關系。假設參考居民地面目標中特征點集合為P，調整居民地面目標中特征點集合為Q，將其特征點之間的匹配相似度構成M行N列矩陣，則有：1)當匹配相似度矩陣中i行j列的向量相似度大于i行其他列以及j列其他行的匹配相似度時，則特征點pi與特征點qj之間存在一一匹配對應關系；2)將已經(jīng)獲得匹配關系的特征點排除，若此時還有特征點未獲得匹配，則重復上一步，直至無法再找到特征點之間的一一匹配對應關系為止，最終可得到特征點的一一匹配對應關系(圖3b)。

圖3 匹配關系的進一步處理Fig.3 Further processing of matching relationships

3 實驗與分析

在普通計算機環(huán)境下(Intel Core i5處理器，1.60 GHz主頻)利用C#語言編寫本文算法，實驗數(shù)據(jù)為鄭州市局部區(qū)域居民地面目標，來自高德地圖和四維圖新地圖。

3.1 同名居民地面目標匹配類型識別

參考居民地面目標集合(圖4a)共有704個居民地面目標，調整居民地面目標集合(圖4b)共有821個居民地面目標，兩組居民地數(shù)據(jù)總體大致吻合，但有不少同名居民地面目標在形狀、位置上有較大差異。實例中1∶1(圖5a)、M∶1(圖5b)、1∶N(圖5c)、M∶N(圖5d)、1∶0、0∶1匹配類型的匹配次數(shù)分別為463、70、16、19、89、119，平均匹配相似度分別為0.77、0.74、0.67、0.74、0、0。其中，參考數(shù)據(jù)集中居民地面目標發(fā)生誤匹配、漏匹配、匹配類型識別錯誤的數(shù)量分別為7個、9個、13個，目標數(shù)據(jù)集中居民地面目標發(fā)生誤匹配、漏匹配、匹配類型識別錯誤的數(shù)量分別為7個、18個、15個，總匹配準確率為95.47%。在算法的實際應用中，可通過綜合設定各個相似度閾值判定多源居民地面目標是否發(fā)生變化。

圖4 實驗數(shù)據(jù)情況Fig.4 Experimental data situation

圖5 同名居民地面目標匹配結果Fig.5 Matching results of homonymous residential area targets

3.2 多源同名居民地面目標上同名特征點匹配

進一步依據(jù)多源同名居民地面目標的自動匹配結果，實現(xiàn)對同名居民地面目標上同名特征點的自動匹配。其中，居民地面目標化簡的閾值設置為1 m，該值通過反復實驗得出，普遍適用于大比例尺導航數(shù)據(jù)。由兩組居民地面目標特征點的匹配結果統(tǒng)計可知，特征點匹配結果中共有3 236個匹配點對，其中參考數(shù)據(jù)集中發(fā)生誤匹配和漏匹配的特征點分別為43個和32個，調整數(shù)據(jù)集中發(fā)生誤匹配和漏匹配的特征點分別為41個和36個，總匹配準確率為95.30%。本實驗中，特征點錯誤匹配的原因皆為居民地面目標匹配類型出現(xiàn)錯誤，因此對居民地面目標匹配結果進行核查糾正后，還可進一步提高匹配率。圖6展示了不同匹配關系類型的實例。

圖6 不同匹配類型特征點匹配結果Fig.6 Matching results for different matching types of feature points

根據(jù)同名居民地面目標同名特征點的匹配結果，可建立居民地面目標匹配對的局部坐標變換關系，并可根據(jù)同名特征點之間的匹配相似度確定相應權重，采用最小二乘抗差估計方法穩(wěn)健估計仿射變換參數(shù)，再根據(jù)參考居民地面目標對調整居民地面目標進行幾何糾正。圖7展示了圖4中圓框區(qū)域的幾何糾正結果，可以看出，相比圖7a，圖7b中兩組居民地面目標在位置上明顯更近，同名參考居民地面目標與調整居民地面目標同名特征點間的平均距離從10.5 m減至2.5 m，明顯減小了位置偏差，有效實現(xiàn)了幾何糾正。

圖7 特征點幾何糾正結果的細節(jié)展示Fig.7 Geometric correction results of feature points

4 結論

針對大比例尺導航地圖居民地面目標數(shù)據(jù)融合問題，本文提出多源同名居民地面目標自動識別及其特征點匹配方法。首先基于空間拓撲關系確定候選匹配對象集，并根據(jù)質心重疊后的居民地面目標之間的重疊程度確定匹配相似度，完成同名居民地面目標之間1∶1、1∶N、M∶N等匹配關系的自動識別；繼而構建向量方向相似度、面積比相似度與距離鄰近度等特征指標，并利用編輯距離算法實現(xiàn)同名居民地面目標上同名特征點的自動匹配。以鄭州市局部區(qū)域居民地面目標電子地圖數(shù)據(jù)對方法的驗證結果表明，本文算法既能自動識別多源同名居民地面目標的1∶1、1∶N和M∶N等匹配關系，又能對同名面目標上的同名特征點進行自動匹配，且二者的匹配準確率均在95%以上?；谕婺繕松贤卣鼽c的匹配結果，采用抗差穩(wěn)健估計模型進一步實現(xiàn)多源居民地面目標的幾何糾正，結果表明同名特征點間的平均距離從10.5 m減至2.5 m，明顯減小了位置偏差，有效實現(xiàn)了幾何糾正，可為多源面目標的位置融合奠定重要基礎。

需要說明的是，當多源居民地面目標存在較大的非一致性位置偏差時，可能產(chǎn)生錯誤匹配現(xiàn)象。針對該現(xiàn)象，可在預處理階段通過精確配準或采用人工智能算法設定最優(yōu)匹配函數(shù)，以解決更為復雜的匹配問題。