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

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

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

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

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

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

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

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

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

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

(1)

(2)

ymin(o3)≤ymin(*)

(3)

ymax(o4)≤ymax(*)

(4)

(5)

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

(6)

算法解題步驟如下：

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

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

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

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

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

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

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

第1步：實(shí)體排序，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步：初始化，當(dāng)前O為null，當(dāng)前解的最優(yōu)值s為0。

第5步：搜索第2層b2子樹,{b2,b5,null,null}和{b2,b6,null,null}不滿足約束函數(shù)，進(jìn)行剪枝；{b2,b4,null,null}滿足約束函數(shù)，進(jìn)入下一層搜索，{b2,b4,b3,null}滿足約束函數(shù)，進(jìn)入下一層{b2,b4,b3,b2}滿足約束函數(shù)，為可行解；{b2,b4,b2,null}滿足約束函數(shù)，進(jìn)入下一層，{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種情況。但在實(shí)際搜索中，如圖2中數(shù)據(jù)演示一樣，回溯法所產(chǎn)生的結(jié)點(diǎn)數(shù)通常只有解空間樹結(jié)點(diǎn)數(shù)的一小部分，所以應(yīng)用回溯法有效提升了搜索效率。

1.2 空間域劃分

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

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

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

1.3 基于ANN的多因子面實(shí)體評價(jià)方法

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

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

(7)

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

(8)

幾何中心點(diǎn)計(jì)算公式為

(9)

(2) 大小相似度

(10)

(3) 方向相似度

(11)

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

(12)

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

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

2 匹配流程

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

3 試驗(yàn)與分析

3.1 試驗(yàn)數(shù)據(jù)

本文選取浙江省舟山市1∶2000島礁海洋基礎(chǔ)空間要素?cái)?shù)據(jù)居民地與設(shè)施面(數(shù)據(jù)A)和1∶10 000臨海區(qū)域陸地基礎(chǔ)空間要素?cái)?shù)據(jù)居民地與設(shè)施面(數(shù)據(jù)B)進(jìn)行匹配算法的驗(yàn)證，數(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)是露天采掘場面。大面實(shí)體相對位置偏差較少，如圖5(d)所示，但是小面實(shí)體相對位置偏差較大，如圖5(b)所示。試驗(yàn)數(shù)據(jù)的統(tǒng)計(jì)信息如表1所示。

表1 試驗(yàn)數(shù)據(jù)詳細(xì)信息

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

3.2 訓(xùn)練決策模型

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

3.3 試驗(yàn)對比與分析

3.3.1 試驗(yàn)對比

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

(13)

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

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

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

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

(14)

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

圖9和圖10展示了兩種方法在位置偏移較大情況下的細(xì)節(jié)表現(xiàn)。圖9顯示該區(qū)域匹配數(shù)據(jù)存在較大位置偏差，同名實(shí)體面積重疊效果較差。表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的預(yù)測的相似度為0.972，因此造成錯誤匹配。而本文MBRCO-ANN方法可同時(shí)檢測到a238：b382和a238,a240：b382，其預(yù)測的相似度分別為0.885和0.917，因此本文方法可以選擇出最佳匹配a238,a240：b382。此外BAO-ANN方法基于面積重疊率S≥0.5漏選了7對正確匹配，即使通過調(diào)整重疊率S,a259：b397a260,a262：b769,b770和a259：b375依然會漏選。同時(shí)還需注意的是，調(diào)整重疊率S還可能造成過度識別，如：a262和b379。因此，直接的面積重疊法是不能解決位置偏移情況下候選匹配的有效識別問題的。

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

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方法錯誤壓蓋了一些面積很小的實(shí)體(a4955和a5236)，或者忽略了一些實(shí)體(如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)計(jì)

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

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

圖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 試驗(yàn)數(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 不同ε下準(zhǔn)確度、召回率、F1和耗時(shí)變化 Fig.11 Precision, recall, F1 and computer time with different value of ε

4 結(jié) 論

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

參考文獻(xiàn)：

[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)絡(luò)決策樹的矢量數(shù)據(jù)變化信息快速識別方法[J]. 測繪學(xué)報(bào), 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]. 測繪學(xué)報(bào), 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]. 武漢大學(xué)學(xué)報(bào)(信息科學(xué)版), 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] 汪匯兵, 唐新明, 邱博, 等. 運(yùn)用多算子加權(quán)的面要素幾何匹配方法[J]. 武漢大學(xué)學(xué)報(bào)(信息科學(xué)版), 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.