多源同名居民地面目標(biāo)識別及其同名特征點匹配方法

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

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

0 引言

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

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

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

1 多源同名居民地面目標(biāo)的自動識別與匹配

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

1.1 基于空間相交關(guān)系的候選匹配居民地面目標(biāo)集合確定

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

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

1.2 參考居民地面目標(biāo)與調(diào)整居民地面目標(biāo)的候選匹配對獲取

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

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

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

1.3 同名居民地面目標(biāo)匹配關(guān)系確定

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

ρbefore=S2/(SRST)

(1)

ρafter=S′2/(SRST)

(2)

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

(3)

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

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

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

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

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

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

(4)

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

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

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

(5)

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

(6)

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

(7)

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

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

(8)

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

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

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

(9)

式中：w1、w2、w3為3個相似度指標(biāo)的權(quán)重，通常設(shè)置為1/3。

2.3 同名居民地面目標(biāo)特征點序列對應(yīng)關(guān)系的最短路徑求取

本文算法的基本目標(biāo)是找到特征點對之間的對應(yīng)關(guān)系使代價函數(shù)C值最小，因此可看成求取一條同名居民地面目標(biāo)特征點序列對應(yīng)關(guān)系的最短路徑，可采用動態(tài)規(guī)劃法求取，即當(dāng)沿路徑的累計距離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)為當(dāng)前格點距離。

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

2.4 特征點匹配對應(yīng)關(guān)系進(jìn)一步處理

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

圖3 匹配關(guān)系的進(jìn)一步處理Fig.3 Further processing of matching relationships

3 實驗與分析

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

3.1 同名居民地面目標(biāo)匹配類型識別

參考居民地面目標(biāo)集合(圖4a)共有704個居民地面目標(biāo)，調(diào)整居民地面目標(biāo)集合(圖4b)共有821個居民地面目標(biāo)，兩組居民地數(shù)據(jù)總體大致吻合，但有不少同名居民地面目標(biāo)在形狀、位置上有較大差異。實例中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ù)集中居民地面目標(biāo)發(fā)生誤匹配、漏匹配、匹配類型識別錯誤的數(shù)量分別為7個、9個、13個，目標(biāo)數(shù)據(jù)集中居民地面目標(biāo)發(fā)生誤匹配、漏匹配、匹配類型識別錯誤的數(shù)量分別為7個、18個、15個，總匹配準(zhǔn)確率為95.47%。在算法的實際應(yīng)用中，可通過綜合設(shè)定各個相似度閾值判定多源居民地面目標(biāo)是否發(fā)生變化。

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

圖5 同名居民地面目標(biāo)匹配結(jié)果Fig.5 Matching results of homonymous residential area targets

3.2 多源同名居民地面目標(biāo)上同名特征點匹配

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

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

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

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

4 結(jié)論

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

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