基于MBR組合優(yōu)化算法的多尺度面實體匹配方法

劉凌佳，朱道也，朱欣焰,2,3，丁小輝，咼 維,2

1. 武漢大學測繪遙感信息工程國家重點實驗室，湖北 武漢 430079； 2. 武漢大學地球空間信息技術(shù)協(xié)同創(chuàng)新中心，湖北 武漢 430079； 3. 武漢大學空天信息安全與可信計算教育部重點實驗室，湖北 武漢 430072； 4. 中國科學院東北地理與農(nóng)業(yè)生態(tài)研究所，吉林 長春 130102

實體匹配是空間數(shù)據(jù)處理和應用領(lǐng)域的基礎(chǔ)性研究問題[1]，其定義為通過相似性指標識別出不同來源地圖數(shù)據(jù)之間的同名實體，并建立對應關(guān)系的過程[2]，它被廣泛應用于空間數(shù)據(jù)的更新、維護和融合[3]。近年來，隨著“自發(fā)地理信息(VGI)”的興起，實體匹配又成為VGI數(shù)據(jù)質(zhì)量改善和評價的關(guān)鍵技術(shù)[4-5]。然而不同來源的地理空間數(shù)據(jù)往往在現(xiàn)勢性、表達尺度、幾何和語義等方面不一致[6-9]，導致獲得精確的匹配結(jié)果成為一個的挑戰(zhàn)，尤其是多尺度數(shù)據(jù)的匹配，因為多尺度匹配中復雜匹配(1∶N和M∶N匹配)廣泛存在，且匹配數(shù)據(jù)之間的特征更為模糊[10]。因此，提出一種適用于多尺度數(shù)據(jù)的匹配方法具有重要意義。

近年來，在實體匹配領(lǐng)域已有許多的探索。文獻[11]從匹配的特征出發(fā)提出了語義匹配、拓撲匹配和幾何匹配；文獻[7]提出了緩沖區(qū)增長法來獲取候選匹配，然后基于通信理論的調(diào)查統(tǒng)計方法來匹配道路網(wǎng)；文獻[12]通過測量目標實體與地標的位移來衡量建筑物的環(huán)境相似性，并和幾何特征一并用來匹配建筑物面；文獻[13]擴展了文獻[12]關(guān)于環(huán)境相似度的計算方法，通過目標建筑物周圍三角形的面積和周長來計算環(huán)境相似度。匹配特征可以是單一的或多元的。然而，為了獲得可靠的匹配結(jié)果，多元特征組合進行匹配被普遍接受[14]。因此，一些學者嘗試將實體匹配問題轉(zhuǎn)化為模型分類問題以解決多元特征的權(quán)重分配和匹配閾值設(shè)置問題。文獻[15]對比了決策樹、樸素貝葉斯和SVM在建筑物面實體匹配中的精度；文獻[16]通過神經(jīng)網(wǎng)絡決策樹來匹配點、線和面實體；文獻[17]引入SVM構(gòu)建道路網(wǎng)多特征匹配模式，并用于預測未知道路網(wǎng)待匹配對；文獻[18]利用文獻[19]中面積重疊法獲取候選匹配，然后引入了人工神經(jīng)網(wǎng)絡從中發(fā)現(xiàn)正確匹配。

盡管以上研究取得了較好的匹配精度，但需進一步改進以匹配多尺度數(shù)據(jù)。在這些研究中，通常采用緩沖區(qū)增長法和面積重疊法來獲取候選匹配，文獻[20]還開發(fā)了依據(jù)面積重疊獲取鄰接矩陣，然后利用鄰接矩陣運算確定多對多匹配候選的方法。然而，緩沖區(qū)增長法只能獲取1∶1匹配候選，其不能確定緩沖區(qū)內(nèi)哪些要素需聚合起來進行匹配；面積重疊法在空間數(shù)據(jù)存在較大位移偏差時是完全無用的[14]，如圖1所示，a2、a3與b1錯誤重疊。由于存在人為主觀認識差異和地理實體空間不確定性[21]，即使通過投影轉(zhuǎn)換、格式轉(zhuǎn)換和地圖糾正等預處理，匹配實體也只是粗糙對齊，坐標偏差依然存在，這將導致大量的正確匹配被漏選，面積較小的實體被忽略。

為了解決以上問題，本文提出依據(jù)形狀特征來確定候選匹配的方法。形狀特征是衡量同名實體的重要指標[22-23]，對于1∶N和M∶N匹配，其整體上也存在輪廓和結(jié)構(gòu)上的相似性[24]。然而，直接通過要素的隨機組合獲取聚合要素集的形狀特征來確定候選匹配，其計算量過大。為此本文將實體簡化為最小外包矩形來代替，并結(jié)合回溯算法來提高搜索效率，定義所提出的獲取候選匹配的算法為MBR組合優(yōu)化算法。本文還將距離、大小、方向和形狀特征與人工神經(jīng)網(wǎng)絡結(jié)合，各特征的權(quán)重由智能學習確定，以預測被調(diào)查候選匹配的匹配概率并評估其是否匹配。

1 基于MBR組合優(yōu)化算法的面實體匹配方法

1.1 MBR組合優(yōu)化算法

確定候選匹配是實體匹配的重要環(huán)節(jié)，其目的是通過粗略分析以限制潛在相似特征的數(shù)量，以此來減少匹配耗時[7,25]。對于待匹配面要素a，通過緩沖分析獲取a的n個候選要素Ba={b1,b2,…,bn}。若a為一對一或一對多的匹配關(guān)系，需搜索b中哪一個要素或哪一些要素與a存在潛在的對應關(guān)系。最直接的方法是使用窮舉法獲取所有的組合，然后比較要素組合與a的形狀特征是否相似來篩選潛在匹配。然而，窮舉法計算量過大(2n個組合)，雖精度較高但形狀描述子(如轉(zhuǎn)角函數(shù)、幾何矩、傅里葉等)計算很復雜，所以當n過大時，窮舉法并不可行。為了快速有效地篩選潛在匹配，本文采用實體的最小外包矩形(MBR)來代替實體進行運算。MBR是包含實體最小x-y的平行矩形，具有簡單、高效的特點，它是地理實體使用最廣泛的近似表達[26]。這樣就可以將要素聚合搜索轉(zhuǎn)化為MBR組合的搜索，搜索組合數(shù)從2n減少為n4。此外，本文還引入回溯法來提高MBR組合搜索的效率?；厮莘ㄊ且环N常用的組合搜索算法，其優(yōu)勢在于能適時“回頭”，若再往前搜索不到解，就退回一步重新選擇，可以大大提高搜索效率?；厮莘ㄗ畹湫偷膽檬墙鉀QN皇后問題[27]。算法設(shè)計如下：

設(shè)目標組合MBR的寬和高分別w和h，ε為算法搜索閾值，問題的解向量O={o1,o2,o3,o4}，共n4個狀態(tài)，當前解狀態(tài)為*。若o1=o2=o3=o4，則目標候選實體只有一個要素，否則為多個要素聚合。由于MBR組合優(yōu)化搜索時，解向量中已存在的元素會影響解向量中其他元素的搜索，所以搜索解空間不同層次結(jié)點時約束函數(shù)不同。為了快速回溯，本文還在定義解空間樹時，對結(jié)點進行了排序。算法涉及的約束函數(shù)包括

(1)

(2)

ymin(o3)≤ymin(*)

(3)

ymax(o4)≤ymax(*)

(4)

(5)

最優(yōu)解s計算公式為

(6)

算法解題步驟如下：

(1) 實體排序。沿x正逆方向和y正逆方向按照MBR的xmin、xmax、ymin和ymax對b中要素排序，結(jié)果分別為Oxmin、Oxmax、Oymin和Oymax。

(2) 建立深度為5的完全n叉解空間樹。根結(jié)點為o，o派生出n個子結(jié)點，o的子結(jié)點再派生出n個子結(jié)點，以此類推，整個解空間樹為一棵n叉的滿樹，包含n4+1個結(jié)點。為了進一步提高搜索效率，子結(jié)點按照一定順序排列，第2層按照Oxmin排列，第3層按照Oxmax排列，第4層按照Oymin列，第5層按照Oymax建立的解空間樹。

(3) 約束函數(shù)。第3層約束函數(shù)為式(1)和式(2)，第4層為式(1)、式(2)和式(3)，第5層為式(1)、式(4)和式(5)。

(4) 初始化。當前O為null，當前解的最優(yōu)值s為0。

(5) 搜索。按照深度優(yōu)先策略，從根結(jié)點出發(fā)搜索樹，搜索到第2層時，記錄解為{o1，null，null，null}，搜索到第3層結(jié)點時，判斷該結(jié)點是否滿足約束函數(shù)，若不滿足約束函數(shù)，則跳過對該結(jié)點為根的子樹的搜索，且與該結(jié)點同一層，排序小于該結(jié)點其他結(jié)點也不用搜索，回溯至上一層，此時解為{}；否則，記錄解為{o1，o2,null，null}對以該結(jié)點為根的n棵子樹，繼續(xù)按照深度優(yōu)先策略進行搜索，操作步驟與上述一致。

(6) 最終獲得所有解向量，根據(jù)式(6)計算最優(yōu)值s，按照s對解集排序。

完成相似MBR查詢后，對齊MBR的幾何中心點，然后通過面積重疊排除無關(guān)要素。本文以圖2中數(shù)據(jù)演示算法查詢過程,搜索閾值ε=0.2，MBR在xmin上排序已顯示，如圖2(a)所示。

第1步：實體排序，Oxmin={b1,b2,b4,b3,b5,b6}、Oxmax={b5,b6,b4,b3,b2,b1}、Oymin={b3,b6,b2,b4,b5,b1}、Oymax={b5,b1,b2,b4,b3,b6}。

第2步：建立深度為5的完全六叉解空間樹，如圖2(b)所示。由于篇幅有限，本文僅列出每一層中一個子樹的排列情況。

第3步：初始化，當前O為null，當前解的最優(yōu)值s為0。

第5步：搜索第2層b2子樹,{b2,b5,null,null}和{b2,b6,null,null}不滿足約束函數(shù)，進行剪枝；{b2,b4,null,null}滿足約束函數(shù)，進入下一層搜索，{b2,b4,b3,null}滿足約束函數(shù)，進入下一層{b2,b4,b3,b2}滿足約束函數(shù)，為可行解；{b2,b4,b2,null}滿足約束函數(shù)，進入下一層，{b2,b4,b2,b2}滿足約束函數(shù)，為可行解。以此類推，最終獲得所有可行解為O1={b2,b4,b2,b2}、O2={b4,b6,b6,b4}、O3={b2,b4,b3,b2}和O4={b4,b5,b4,b5}。

第6步：將a的MBR對齊可行解MBR，通過面積重疊篩選無關(guān)要素。獲取a的候選匹配分別為{b2,b4}和{b4,b5}。

基于回溯的MBR組合優(yōu)化算法最壞的情形可搜索到n4種情況。但在實際搜索中，如圖2中數(shù)據(jù)演示一樣，回溯法所產(chǎn)生的結(jié)點數(shù)通常只有解空間樹結(jié)點數(shù)的一小部分，所以應用回溯法有效提升了搜索效率。

1.2 空間域劃分

MBR組合優(yōu)化算法實現(xiàn)了單向的要素聚合搜索，即輸入數(shù)據(jù)A中實體a，能在數(shù)據(jù)B中查詢到a的候選匹配。然而，對于多對多匹配候選，需要一并獲得A和B中對應的聚合要素集，即實現(xiàn)雙向搜索。本文的策略是首先在數(shù)據(jù)A(或B)中搜索聚合要素集，然后輸入初次搜索到的聚合要素集，在B(或A)中搜索其候選匹配。但直接在A(或B)中搜索聚合要素集，將導致搜索到的聚合要素集數(shù)爆炸，且獲取的大多數(shù)聚合要素集是無效的。為此本文提出空間域的概念，目的是將實體劃分到一個個閉合的空間區(qū)域內(nèi)。這些閉合的空間區(qū)域沒有分隔應聚合的要素集，本文定義其為空間域。它包含兩個重要特征：一是邊界性，劃定了MBR組合優(yōu)化算法的搜索范圍，避免了搜索結(jié)果爆炸的困境；二是連續(xù)性，保證了聚合要素集的整體性沒有被破壞。

在地理空間分布模式中，Gestalt原則得到廣泛認同，并用于指導地圖綜合[28]。Gestalt原則認為一群地理要素根據(jù)視覺感受進行分組時，將結(jié)構(gòu)模式一致性且鄰接的要素集放在一起。例如，在地圖綜合時，會將存在鄰接關(guān)系且具有一定特征相似性的要素進行綜合。對于多對多匹配中聚合要素集，其要素之間應存在鄰接關(guān)系，類似于“飛地”現(xiàn)象是極少存在的。本文依據(jù)Gestalt原則來劃分多對多匹配的空間域。首先，將匹配實體分為兩類，設(shè)A0={a1,a2,…,am}和B0={b1,b2,…,bm}分別為A和B的第1類實體，A1={am+1,am+2,…,am+p}和B1={bn+1,bn+2,…,bn+q}分別為A和B中的第2類實體；然后，使用Delaunay三角網(wǎng)構(gòu)建鄰接第1類實體中A0或B0的鄰接關(guān)系[29]，具體操作為獲取A0中要素的幾何中心點VA0={v(a1),v(a2),…,v(am)}，通過VA0創(chuàng)建Delaunay三角網(wǎng)。最后將壓蓋了A1中實體的三角空間進行合并，這些單個的三角空間區(qū)域或多個三角空間合并的區(qū)域即為A1的空間域。在劃分操作中，A0和B0不包含M∶N匹配類型，通過A0建立Delaunay三角網(wǎng)后，M∶N匹配就分布在一個或多個三角空間內(nèi)，然后合并壓蓋A1中實體的三角空間，避免了M∶N匹配中A1來源的聚合要素集被破壞，因此保證了空間域的邊界性和連續(xù)性。如圖3所示，第1類實體的Delaunay鄰接關(guān)系已構(gòu)建，D1、D2、D3和D4為形成的三角區(qū)域，D1、D2和D3與A1中要素相交，則將他們記錄為合并；D3和D4也與A1中要素相交，則將D3和D4記錄為合并；最后將D1、D2、D3和D4進行合并，形成一個空間域，即為圖中陰影區(qū)域。

空間域獲取后，通過MBR組合優(yōu)化算法在空間域內(nèi)查找A1中聚合要素集，此時聚合條件為目標MBR至少包含兩個面要素，然后輸入初次查詢到的聚合要素集，再次利用MBR組合優(yōu)化算法在B1中搜索其候選匹配。

1.3 基于ANN的多因子面實體評價方法

獲得候選匹配后，一個匹配評價方法被用于評估被調(diào)查候選匹配是否為幾何上的正確匹配。匹配評價是一個復雜的決策過程，包含了特征因子的選定和根據(jù)這些因子做出決策兩部分。本文選取的面實體特征因子包括距離、大小、方向和形狀。同時，為了避免人為設(shè)置決策模型的權(quán)重和閾值，本文通過機器學習算法——人工神經(jīng)網(wǎng)絡的學習確定決策模型的權(quán)重和閾值。人工神經(jīng)網(wǎng)絡(ANN)廣泛應用于科學和工程問題，它試圖模擬生物神經(jīng)系統(tǒng)的識別模式[30]。在實體匹配中，如果不同地圖中兩個實體的多個特征存在相似性，則它們可能是同名實體，本文將該判斷過程擬合為一個人工神經(jīng)網(wǎng)絡的模式識別過程。本文采用ANN中3層BPNN來解決該問題。BPNN是一種誤差反向傳播的前饋學習算法，其對希望的映射能達到全局最優(yōu)逼近，且具有較強的泛化能力[31]。BPNN包含輸入層(input layer)、隱含層(hidden layer)和輸出層(output layer)。本文選擇輸入層為特征因子中的距離(Sdis)、大小(Ssize)、方向(Sdir)和形狀(Sshape)相似度，隱含層設(shè)置為9個節(jié)點，輸出層為1(匹配)和0(不匹配)。BPNN輸出匹配結(jié)果時，同時能得到該實體對匹配(歸為1)的概率P，不匹配概率為1-P。當P≥0.5時，則實體對匹配，且P越接近1，實體對越相似；反之P<0.5，1-P越接近1，實體越不相似。各特征因子計算公式如下：

(1) 距離相似度，采用文獻[32]提出的距離相似度計算公式

(7)

式中，ra、rb分別為面實體a和b最小外接矩形對角線長的一半，d(a,b)表示a、b之間的幾何中心點之間的距離，其計算公式為

(8)

幾何中心點計算公式為

(9)

(2) 大小相似度

(10)

(3) 方向相似度

(11)

(4) 形狀相似度。本文采用轉(zhuǎn)角函數(shù)法[22]來描述面實體的形狀。轉(zhuǎn)角函數(shù)法是基于輪廓的形狀描述方法，被廣泛應用的閉合折線形狀描述[33]。如圖4所示，a和b面實體從P0點沿順時針方向展開，記錄每一段弧的長度，以歸一化長度作為X軸，沿弧每點的轉(zhuǎn)向角累加值作為Y值。轉(zhuǎn)角函數(shù)形狀相似性計算公式為

(12)

式中，θa(x)和θb(x)分別是面實體a、b轉(zhuǎn)向角累加值。

為了適應于一對多和多對多匹配特征因子的相似性計算，本文采用凸包將聚合要素集聯(lián)合為單一面實體進行評價。

2 匹配流程

整個匹配流程主要有5個組成部分：①數(shù)據(jù)預處理，主要包括格式轉(zhuǎn)換、拓撲檢查、幾何坐標轉(zhuǎn)換，目的是解決不同來源數(shù)據(jù)的系統(tǒng)性錯誤[34]；②訓練決策模型，隨機選擇樣本，計算每個樣本數(shù)據(jù)的距離、大小、方向和形狀特征的相似度，并人工匹配樣本數(shù)據(jù)，輸入特征數(shù)據(jù)和匹配結(jié)果數(shù)據(jù)訓練神經(jīng)網(wǎng)絡，并采用測試樣本測試所訓練模式；③初匹配，利用MBR組合優(yōu)化算法獲取1∶1和1∶N的候選匹配，然后通過已訓練的決策模型評估這些候選匹配；④基于初匹配結(jié)果將已匹配的實體標記A0和B0，未匹配的實體標記為A1和B1，主要包含M∶N匹配和1∶0匹配。通過A0創(chuàng)建Delaunay三角網(wǎng)，劃分多對多匹配空間域；⑤在空間域內(nèi)查詢A1的聚合要素集，然后通過該聚合要素集在B1查找其候選匹配，最后通過已訓練的決策模型評估這些候選匹配，獲取所有匹配結(jié)果。

3 試驗與分析

3.1 試驗數(shù)據(jù)

本文選取浙江省舟山市1∶2000島礁海洋基礎(chǔ)空間要素數(shù)據(jù)居民地與設(shè)施面(數(shù)據(jù)A)和1∶10 000臨海區(qū)域陸地基礎(chǔ)空間要素數(shù)據(jù)居民地與設(shè)施面(數(shù)據(jù)B)進行匹配算法的驗證，數(shù)據(jù)A和數(shù)據(jù)B疊加在一起的情況如圖5所示。

圖5(a)為全部數(shù)據(jù)疊加在一起顯示，圖5(b)、5(c)和5(d)為圖5(a)中部分區(qū)域的放大顯示，其中圖5(b)是居民建筑物面，圖5(c)是工業(yè)設(shè)施面，圖5(d)是露天采掘場面。大面實體相對位置偏差較少，如圖5(d)所示，但是小面實體相對位置偏差較大，如圖5(b)所示。試驗數(shù)據(jù)的統(tǒng)計信息如表1所示。

表1 試驗數(shù)據(jù)詳細信息

本文算法通過Microsoft Visual Studio 2010(C#)+ ArcGIS Engine10.1實現(xiàn)，并通過Spyder+Python3.5構(gòu)建BP神經(jīng)網(wǎng)絡評價模型及預測匹配結(jié)果。本試驗在core i5 CPU 2.6Hz Win8操作系統(tǒng)上運行。

3.2 訓練決策模型

試驗選取了數(shù)據(jù)B中大約20%的實體所產(chǎn)生的964個候選匹配作為樣本來訓練BP神經(jīng)網(wǎng)絡模型，樣本匹配結(jié)果是人工確認的。樣本中包含86個1∶1匹配樣本，正確匹配52個，錯誤匹配34個；849個1∶N匹配樣本，正確匹配375個，錯誤匹配474個；29個M∶N匹配樣本，正確匹配11個，錯誤匹配18個。樣本數(shù)據(jù)中一半作為訓練數(shù)據(jù)，另一半作為測試數(shù)據(jù)。按照2.3節(jié)模型設(shè)定，本文所選取的BP神經(jīng)網(wǎng)絡模型隱含層節(jié)點數(shù)為9個，激活函數(shù)為logistic函數(shù)，學習效率設(shè)為0.01，動量因子設(shè)為0.9，最大迭代次數(shù)為1000次。最終，所訓練的模型匹配測試數(shù)據(jù)，精度為89%。

3.3 試驗對比與分析

3.3.1 試驗對比

為定量評價所提出匹配方法的性能，本文通過與人工檢查的結(jié)果進行比較來評估匹配結(jié)果，評價公式采用最流行F1-Measure，其計算公式為

(13)

式中，P為準確率；R為召回率；TP為正確匹配數(shù)；FP為錯誤匹配數(shù)；AM為人工無法判斷的匹配數(shù)；FN為漏匹配數(shù)。試驗中設(shè)置本文方法緩沖分析距離σ=30 m，MBR組合優(yōu)化算法搜索閾值ε=0.2。為了驗證本文算法對坐標偏移情況的解決能力，選取文獻[18]方法進行對比。文獻[18]方法首先利用面積重疊法(重疊率S≥0.5)正向獲取候選匹配，然后通過距離、大小、方向和長度構(gòu)建BPNN評價模型篩選正確匹配；再通過面積重疊法反向獲取未匹配實體的候選匹配，然后再利用已構(gòu)建的BPNN評價模型篩選正確匹配。為方便表示，本文方法簡記為MBRCO-ANN(minimum bounding rectangle combinatorial optimization algorithm & artificial neural network)，對比方法為BAO-ANN(bidirectional area overlap & artificial neural network)。BAO-ANN方法仍然采用上文介紹的樣本數(shù)據(jù)進行訓練，兩種方法匹配結(jié)果統(tǒng)計如表2所示。

表2 兩種方法的匹配結(jié)果統(tǒng)計

從表2中可看出，本文MBRCO-ANN方法的準確率、召回率均高于對比的BAO-ANN方法，因此整體表現(xiàn)(F1)也優(yōu)于BAO-ANN方法，但BAO-ANN方法耗時遠小于本文方法。此外，兩種方法都取得了相對較高的準確度，說明基于人工神經(jīng)網(wǎng)絡的決策模型在實體匹配領(lǐng)域也有良好表現(xiàn)。本文方法精度略高于BAO-ANN方法，這主要是因為：①本文中選取的正切空間函數(shù)法來描述形狀特征相較于BO-ANN的實體長度信息更精確；②本文中MBR組合優(yōu)化算法可獲得相對較多的候選匹配，這有利于從多個候選中選擇出最佳匹配。

兩種方法獲得候選匹配對比如圖6、圖7和圖8所示。圖中N為獲得候選匹配的總數(shù)，Ncontain為所獲得的候選匹配中包含的正確匹配數(shù)，Pcontain為包含率，其計算公式為

(14)

從圖6可知，MBRCO-ANN方法獲得了7584個候選匹配，遠多于BAO-ANN方法獲得的793個候選匹配。由于大量的候選匹配需要計算位置、大小、方向和形狀的相似度，因此本文方法較BAO-ANN方法耗時多。但是獲取的大量候選匹配也減少了正確匹配的漏選，如圖7和圖8所示，MBRCO-ANN方法獲得了740個有效候選匹配，包含率達到了95.1%，而對比的BAO-ANN方法僅獲得了449個有效候選匹配，包含率為57.7%。這也直接限制了BAO-ANN方法召回率的提升。因此本文MBRCO算法獲得候選匹配的能力顯著高于BAO-ANN方法中的面積重疊方法。

圖9和圖10展示了兩種方法在位置偏移較大情況下的細節(jié)表現(xiàn)。圖9顯示該區(qū)域匹配數(shù)據(jù)存在較大位置偏差，同名實體面積重疊效果較差。表3顯示MBRCO-ANN方法獲得了7對正確匹配，0對錯誤匹配和3對漏匹配，而BAO-ANN方法獲得了3對正確匹配，1對錯誤匹配和7對漏匹配。MBRCO-ANN方法未檢測到的3對匹配：b376∶a263、b375∶a273和b271∶a377，其中存在明顯的形狀差異，如圖9(a)所示，所以MBR組合優(yōu)化算法未檢測到。BAO-ANN方法中的錯誤匹配對：a238∶b382，這是由于b382通過面積重疊法只找到了a238，且a238與b382的預測的相似度為0.972，因此造成錯誤匹配。而本文MBRCO-ANN方法可同時檢測到a238：b382和a238,a240：b382，其預測的相似度分別為0.885和0.917，因此本文方法可以選擇出最佳匹配a238,a240：b382。此外BAO-ANN方法基于面積重疊率S≥0.5漏選了7對正確匹配，即使通過調(diào)整重疊率S,a259：b397a260,a262：b769,b770和a259：b375依然會漏選。同時還需注意的是，調(diào)整重疊率S還可能造成過度識別，如：a262和b379。因此，直接的面積重疊法是不能解決位置偏移情況下候選匹配的有效識別問題的。

表3兩種方法在圖9中數(shù)據(jù)匹配情況統(tǒng)計

Tab.3MatchingresultsofMBRCO-ANNandBAO-ANNmethodinexample1

方法正確匹配對錯誤匹配對漏匹配對MBRCO-ANNa233,a240∶b331a253∶b499a254∶b381a259∶b397a260,a262∶b769,b770a261∶b378a265∶b615a274∶b766b376b377b375BAO-ANNa253∶b499a261∶b378a265∶b615a238∶b382b381b397b769,b770b376b377b375b765

從表4可知，MBRCO-ANN方法識別了全部的匹配，包括2對1∶N匹配和3對M∶N匹配，而BAO-ANN方法只獲得了5對正確匹配，但存在2對錯誤匹配，1對漏匹配。從圖10(b)可看出，BAO-ANN方法錯誤壓蓋了一些面積很小的實體(a4955和a5236)，或者忽略了一些實體(如a5327和a6170)，造成錯誤匹配(a4955,a5167,a5760,a5806,a5842,a6175∶b767,b768和a5236,a5975,a6173,a6174a6180,a6195∶b354)。這種錯誤(或過度)壓蓋在1∶N和M∶N匹配類型中經(jīng)常出現(xiàn)，即使通過精確決策模式也不能解決這些微小的差異。因此本文提出的不依賴于位置精確的MBRCO-ANN方法在解決1∶N和M∶N匹配中具有明顯的優(yōu)勢。

表4兩種方法在圖9中數(shù)據(jù)匹配情況統(tǒng)計

Tab.4MatchingresultsofMBRCO-ANNandBAO-ANNmethodinexample2

方法正確匹配錯誤匹配漏匹配MBRCO-ANNa5167,a5760,a5806a5842,a6175∶b767,b768a5293∶b738a5001∶b740a4895,a5128,a6200∶b365,b366a4542,a6177∶b353a4212∶b356a4495,a6051∶b771,b772,b773a4690,a5327,a5975,a6170a6173,a6174,a6195∶b354BAO-ANNa5293∶b738a5001∶b740a4542,a6177∶b353a4212∶b356a4495,a6051∶b771,b772,b773a4955,a5167,a5760,a5806a5842,a6175∶b767,b768a5236,a5975,a6173,a6174a6130,a6195∶b354b365,b366

3.3.2 參數(shù)分析

由于神經(jīng)網(wǎng)絡減少了參數(shù)的人為設(shè)定，但是本文方法也使用了緩沖區(qū)距離σ和MBR組合優(yōu)化算法閾值ε。σ的值由匹配數(shù)據(jù)中同名實體最大偏移距離決定，σ過小，部分偏移較大的同名實體不能被選中；σ設(shè)置為太大值時，會獲得更多的候選匹配，但也增加程序運算時間。本文試驗中，σ根據(jù)多次試驗選擇為30 m。不同參數(shù)ε(0.05，0.1，0.2，0.3，0.4)對本文所提出的MBR組合優(yōu)化算法表現(xiàn)的影響，如圖11所示。

從圖11中可知，當ε過小時，一些正確的匹配候選沒有被MBR組合優(yōu)化算法查詢到，因此召回率很低，相應也影響了整體表現(xiàn)(F1)。當ε逐漸增大至0.2時，召回率急劇上升，準確率和F1值也相應上升，這是由于更多的候選匹配讓正確匹配被發(fā)現(xiàn)。當ε繼續(xù)增大時，準確率和召回率相對平穩(wěn)，這是由于ε在0.2左右時，絕大多數(shù)正確匹配已經(jīng)被搜索到。匹配耗時是隨著ε增大，先相對平穩(wěn)后急劇上升，這是由于ε過小時初次匹配中很多候選匹配沒有獲取到，但未查詢到的匹配對增加了二次匹配的檢索負擔。當ε逐漸增大至0.2時，初次匹配中越來越多正確匹配搜索到，二次匹配檢索工作減少，匹配耗時相對穩(wěn)定；當ε繼續(xù)增大時，大量無效候選匹配被搜索到，匹配耗時急劇增加。所以ε的取值從1.8到2.5之間，本文方法在精確度和耗時方面達到較好均衡。

圖1 位置偏移的匹配數(shù)據(jù)Fig.1 Matching data in positional discrepancy

圖2 MBR組合優(yōu)化算法示意圖Fig.2 MBR combinatorial optimization algorithm

圖3 三角空間合并示意圖Fig.3 Merging triangular spaces

圖4 面a和b轉(zhuǎn)角函數(shù)形狀描述圖Fig.4 Shape description of polygon a and b by the turning function

圖5 試驗數(shù)據(jù)Fig.5 Test data

圖6 候選匹配總數(shù)Fig.6 Number of identifying the potential matching pairs

圖7 有效候選匹配數(shù)Fig.7 Number of identifying the effective potential matching pairs

圖8 包含率Fig.8 Percentage of containing

圖9 示例1：使用MBRCO-ANN方法和BAO-ANN方法獲得的匹配結(jié)果Fig.9 Matching results of example 1 according to MBRCO-ANN and BAO-ANN methods

圖10 示例2：使用MBRCO-ANN方法和BAO-ANN方法獲得的匹配結(jié)果Fig.10 Matching results of example 2 according to MBRCO-ANN and BAO-ANN methods

圖11 不同ε下準確度、召回率、F1和耗時變化 Fig.11 Precision, recall, F1 and computer time with different value of ε

4 結(jié) 論

本文提出了基于MBR組合優(yōu)化算法的多尺度面實體匹配方法，該方法包含3個部分：①MBR組合優(yōu)化算法，其解決了單向(1∶1和1∶N)候選匹配搜索問題；②基于空間域改進MBR組合優(yōu)化算法，通過劃分空間域限定了查詢算法的搜索范圍，以解決雙向(M∶N)候選匹配的搜索問題；③構(gòu)建基于距離、大小、方向和形狀的人工神經(jīng)網(wǎng)絡匹配評價模型來識別幾何上相似的匹配對。本文所提出的方法試驗于存在位置偏差的不同尺度面數(shù)據(jù)，結(jié)果表明，本文方法能夠有效克服位置偏差對匹配的影響。下一步工作將側(cè)重于改進獲得候選匹配的效率，并且將該方法擴展到道路網(wǎng)的匹配。

參考文獻：

[1] LI Linna, GOODCHILD M F. Automatically and Accurately Matching Objects in Geospatial Datasets[M]∥GOODCHILD M F, LEUNG Y, SHI Wenzhong, et al. Advances in Geo-Spatial Information Science. London, UK: CRC Press, 2012: 71-79.

[2] SAALFELD A. Automated Map Conflation[D]. Washington DC: University of Maryland, 1993: 1-10.

[3] RUIZ J J, ARIZA F J, UREA M A, et al. Digital Map Conflation: A Review of the Process and a Proposal for Classification[J]. International Journal of Geographical Information Science, 2011, 25(9): 1439-1466.

[4] GIRRES J F, TOUYA G. Quality Assessment of the French OpenStreetMap Dataset[J]. Transactions in GIS, 2010, 14(4): 435-459.

[5] YANG Bisheng, ZHANG Yunfei, LUAN Xuechen. A Probabilistic Relaxation Approach for Matching Road Networks[J]. International Journal of Geographical Information Science, 2013, 27(2): 319-338.

[6] DEVOGELE T, PARENT C, SPACCAPIETRA S. On Spatial Database Integration[J]. International Journal of Geographical Information Science, 1998, 12(4): 335-352.

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

[8] GOODCHILD M F. Chapter Four-attribute Accuracy[M]∥GUPTILL S C, MORRISON J L. Elements of Spatial Data Quality: A Volume in International Cartographic Association. Amsterdam: Elsevier, 1995: 59-79.

[9] GUPTILL S C, MORRISON J L. Elements of Spatial Data Quality[M]. Oxford, UK: Elsevier Science, 1995.

[10] ZHANG Xiang, AI Tinghua, STOTER J, et al. Data Matching of Building Polygons at Multiple Map Scales Improved by Contextual Information and Relaxation[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2014, 92(2): 147-163.

[11] DEVOGELE T, TREVISAN J, RAYNAL L. Building a Multi-scale Database with Scale-transition Relationships[C]∥Proceedings of the 7th International Symposium on Spatial Data Handling. Delft, The Netherlands: SDH, 337-351.

[12] SAMAL A, SETH S, CUETO K, et al. A Feature-based Approach to Conflation of Geospatial Sources[J]. International Journal of Geographical Information Science, 2004, 18(5): 459-489.

[13] KIM J O, YU K, HEO J, et al. A New Method for Matching Objects in Two Different Geospatial Datasets Based on the Geographic Context[J]. Computers & Geosciences, 2010, 36(9): 1115-1122.

[14] XAVIER E M A, ARIZA-LPEZ F J, UREA-CMARA M A. A Survey of Measures and Methods for Matching Geospatial Vector Datasets[J]. ACM Computing Surveys, 2016, 49(2): 39.

[15] ZHANG X, ZHAO X, MOLENAAR M, et al. Pattern Classification Approaches to Matching Building Polygons at Multiple Scales[C]∥ISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences. Melbourne: ISPRS, 2012: 19-24.

[16] 郭泰圣, 張新長, 梁志宇. 神經(jīng)網(wǎng)絡決策樹的矢量數(shù)據(jù)變化信息快速識別方法[J]. 測繪學報, 2013, 42(6): 937-944.

GUO Taisheng, ZHANG Xinchang, LIANG Zhiyu. Research on Change Information Recognition Method of Vector Data Based on Neural Network Decision Tree[J]. Acta Geodaetica et Cartographica Sinica, 2013, 42(6): 937-944.

[17] 付仲良, 楊元維, 高賢君, 等. 道路網(wǎng)多特征匹配優(yōu)化算法[J]. 測繪學報, 2016, 45(5): 608-615. DOI: 10.11947/j.agcs.2016.20150388.

FU Zhongliang, YANG Yuanwei, GAO Xianjun, et al. An Optimization Algorithm for Multi-characteristics Road Network Matching[J]. Acta Geodaetica et Cartographica Sinica, 2016, 45(5): 608-615. DOI: 10.11947/j.agcs.2016.20150388.

[18] WANG Yanxia, CHEN Deng, ZHAO Zhiyuan, et al. A Back-propagation Neural Network-based Approach for Multi-represented Feature Matching in Update Propagation[J]. Transactions in GIS, 2015, 19(6): 964-993.

[19] FU Zhongliang, WU Jianhua. Entity Matching in Vector Spatial Data[C]∥International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences. Beijing: ISPRS, 2008, 37(5): 1467-1472.

[20] VON GOESSELN G, SESTER M. Change Detection and Integration of Topographic Updates from ATKIS to Geoscientific Data Sets[C]∥Proceedings of International Conference on Next Generation Geospatial Information. Boston: International Conference on Next Generation Geospatial Information, 2003.

[21] HUH Y, KIM J, LEE J, et al. Identification of Multi-scale Corresponding Object-set Pairs between Two Polygon Datasets with Hierarchical Co-clustering[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2014, 88(1): 60-68.

[22] ARKIN E M, CHEW L P, HUTTENLOCHER D P, et al. An efficiently Computable Metric for Comparing Polygonal Shapes[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1991, 13(3): 209-216.

[23] XU Yongyang, XIE Zhong, CHEN Zhanlong, et al. Shape Similarity Measurement Model for Holed Polygons Based on Position Graphs and Fourier Descriptors[J]. International Journal of Geographical Information Science, 2017, 31(2): 253-279.

[24] 許俊奎, 武芳, 朱健東, 等. 相鄰比例尺居民地匹配[J]. 武漢大學學報(信息科學版), 2014, 39(3): 340-345.

XU Junkui, WU Fang, ZHU Jiandong, et al. A Multi-to-Multi Matching Algorithm between Neighborhood Scale Settlement Data[J]. Geomatics and Information Science of Wuhan University, 2014, 39(3): 340-345.

[25] ZHANG Meng, MENG Liqiu. An Iterative Road-matching Approach for the Integration of Postal Data[J]. Computers, Environment and Urban Systems, 2007, 31(5): 597-615.

[26] COBB M A, PETRY F E, SHAW K B. Fuzzy Spatial Relationship Refinements based on Minimum Bounding Rectangle Variations[J]. Fuzzy Sets and Systems, 2000, 113(1): 111-120.

[27] KNUTH D E. The Art of Computer Programming[M]. Upper Saddle River, NJ: Addison-Wesley, 1968.

[28] LI Z, YAN H, AI T, et al. Automated Building Generalization Based on Urban Morphology and Gestalt Theory[J]. International Journal of Geographical Information Science, 2004, 18(5): 513-534.

[29] TSAI V J D. Delaunay Triangulations in TIN Creation: An Overview and a Linear-time Algorithm[J]. International Journal of Geographical Information Systems, 1993, 7(6): 501-524.

[30] CRACKNELL M J, READING A M. Geological Mapping Using Remote Sensing Data: A Comparison of Five Machine Learning Algorithms, Their Response to Variations in the Spatial Distribution of Training Data and the Use of Explicit Spatial Information[J]. Computers & Geosciences, 2014, 63(1): 22-33.

[31] FUNAHASHI K I. On the Approximate Realization of Continuous Mappings by Neural Networks[J]. Neural Networks, 1989, 2(3): 183-192.

[32] 汪匯兵, 唐新明, 邱博, 等. 運用多算子加權(quán)的面要素幾何匹配方法[J]. 武漢大學學報(信息科學版), 2013, 38(10): 1243-1247.

WANG Huibing, TANG Xinming, QIU Bo, et al. Geometric Matching Method of Area Feature Based on Multi-weighted Operators[J]. Geomatics and Information Science of Wuhan University, 2013, 38(10): 1243-1247.

[33] FAN Hongchao, ZIPF A, FU Qing, et al. Quality Assessment for Building Footprints Data on OpenStreetMap[J]. International Journal of Geographical Information Science, 2014, 28(4): 700-719.

[34] DOYTSHER Y. A Rubber Sheeting Algorithm for Non-Rectangular Maps[J]. Computers & Geosciences, 2000, 26(9-10): 1001-1010.