一種基于最大基因組比對法的地理要素匹配相似度算法

高昭良

(福州市勘測院，福建 福州 350003)

一種基于最大基因組比對法的地理要素匹配相似度算法

高昭良*

(福州市勘測院，福建 福州 350003)

地理要素同名匹配是地理空間信息數(shù)據(jù)庫實現(xiàn)要素級更新維護的基礎，它對于提高地理空間信息現(xiàn)勢性與應用水平具有重要的理論和實踐意義。本文針對目前空間數(shù)據(jù)庫變化特征進行了深入分析，并在此基礎上，針對空間數(shù)據(jù)庫快速更新需求，從幾何視角提出了一種基于最大基因組比對法的地理要素匹配相似度算法，在空間信息數(shù)據(jù)庫更新過程中驗證了該匹配算法的可行性。

最大基因組比對法；要素匹配；空間數(shù)據(jù)庫更新

1 引 言

隨著基礎數(shù)據(jù)庫建設的不斷完成，空間數(shù)據(jù)庫的維護和更新逐步成為國際GIS學術界和應用部門的前沿研究與應用課題。由于目前常用的批量更新方式采用簡單區(qū)域替代方法，嚴重損害了空間數(shù)據(jù)庫變化的真實性，應用上造成所有的非空間信息全部失去空間關聯(lián)。因此更新過程中如何快速識別同名空間要素(即：地理要素匹配技術)，進行要素級的增量更新變化檢測方法已成為GIS空間數(shù)據(jù)更新研究領域的熱點問題。地理要素匹配其本質(zhì)是通過分析兩個數(shù)據(jù)集(新舊版本)中空間目標的差異與相似性，檢測出不同數(shù)據(jù)集中表達現(xiàn)實世界同一地理要素的空間目標，目的是確定不同時期、不同尺度的同名地物是否發(fā)生變化，然后在不同數(shù)據(jù)之間傳播變化以達到數(shù)據(jù)更新的目標[1]。就明確定義的點、線、面要素而言，國內(nèi)外學者進行了深入的探討與研究，提出了許多方法[2～10]，這些方法在使用對象、技術細節(jié)等方面?zhèn)戎攸c各不相同。現(xiàn)有匹配算法假設這些不同數(shù)據(jù)源中的同名地物具有強空間相似度，即空間相似度越好越能夠得到肯定的匹配結(jié)果[11～14]。但總體從選取的匹配指標來說可以歸納為三類[15～17]：第一類是幾何匹配的檢測方法，通過分析不同類別數(shù)據(jù)中地物目標的幾何空間特性，如形狀、位置、方向、長度、大小等，計算其幾何相似度，從而建立同名地物的對應關系。第二類是語義匹配的檢測方法，即通過分析不同地物的屬性信息，利用語義關聯(lián)來實現(xiàn)匹配。第三類是拓撲匹配的檢測方法，通過分析數(shù)據(jù)中地物目標的拓撲以及其他地物的空間關系。在實際操作中單純運用某一類檢測方法往往得不到正確的匹配結(jié)果，而往往需要綜合運用語義、幾何、拓撲等信息對目標進行綜合匹配。

由上述分析可知，空間數(shù)據(jù)庫更新中同名要素匹配是一個非常復雜過程，需要對此進行長期的深入研究。本文內(nèi)容作為同名要素匹配中的分支算法，認為在相鄰兩個新舊版本的數(shù)據(jù)集中，同名地物之間可能會有所差別，但仍具有較高的空間相似度，從而基于遺傳算法，提出了一種最大基因組比對法計算新舊地物相似度，實現(xiàn)了對幾何上存在較小差異的同名要素之間的匹配。該方法能在相鄰兩個新舊版本的數(shù)據(jù)集中檢測出一組粗略的地理要素匹配集合，縮小了拓撲和語義匹配的對象范圍，極大地減少了后續(xù)匹配階段的計算量。

2 最大基因組比對算法

2.1 遺傳算法

遺傳算法(Genetic Algorithm)是一類借鑒生物界的進化規(guī)律(適者生存，優(yōu)勝劣汰遺傳機制)演化而來的隨機化搜索方法。它是由美國的J.Holland教授1975年首先提出。其主要特點是直接對結(jié)構(gòu)對象進行操作，不存在求導和函數(shù)連續(xù)性的限定；具有內(nèi)在的隱并行性和更好的全局尋優(yōu)能力；采用概率化的尋優(yōu)方法，能自動獲取和指導優(yōu)化的搜索空間，自適應地調(diào)整搜索方向，不需要確定的規(guī)則[10]。對于一個求函數(shù)最大值的優(yōu)化問題(求函數(shù)最小值也類同)，一般可以描述為下列數(shù)學規(guī)劃模型：

maxf(x)

(1)

x∈R

(2)

R?U

(3)

式中x為決策變量，式(1)為目標函數(shù)式，式(2)、式(3)為約束條件，U是基本空間，R是U的子集。滿足約束條件的解X稱為可行解，集合R表示所有滿足約束條件的解所組成的集合，稱為可行解集合。

遺傳算法的基本運算過程如下：

(1)初始化：設置進化代數(shù)計數(shù)器t=0，設置最大進化代數(shù)T，隨機生成M個個體作為初始群體P(0)。

(2)個體評價：計算群體P(t)中各個個體的適應度。

(3)選擇運算：將選擇算子作用于群體。選擇的目的是把優(yōu)化的個體直接遺傳到下一代或通過配對交叉產(chǎn)生新的個體再遺傳到下一代。選擇操作是建立在群體中個體的適應度評估基礎上的。

(4)交叉運算：將交叉算子作用于群體。遺傳算法中起核心作用的就是交叉算子。

(5)變異運算：將變異算子作用于群體。即是對群體中的個體串的某些基因座上的基因值作變動。

群體P(t)經(jīng)過選擇、交叉、變異運算之后得到下一代群體P(t+1)。

(6)終止條件判斷：若t=T，則以進化過程中所得到的具有最大適應度個體作為最優(yōu)解輸出，終止計算。

本文主要思路是基于遺傳算法，借鑒生物學理論，將地理要素輪廓線看作生物基因鏈，其變化看做是基因遺傳和變異的結(jié)果。新舊版本對象相似與否，可通過新舊地物基因比對來決定，如果新舊地物基因組重疊度長度大于某一個閥值，可判定其相似，否則不相似。算法涉及復雜的多變量最優(yōu)化求解問題，本文采用改進的實數(shù)編碼遺傳算法進行求解。

2.2 最大基因組比對算法模型

最大基因組比對算法模型在遺傳算法的基礎上構(gòu)建，包含了遺傳算法的基本步驟，即是一個“產(chǎn)生+檢測”(generate-and-test)的迭代過程，基本過程為：創(chuàng)建初始種群；種群中個體適應度計算；評估適應度；根據(jù)適應度選擇個體；被選擇個體進行交叉繁殖；在繁殖的過程中引入變異機制；淘汰掉最差的個體；回到第二步，直至滿足要求為止。

圖1 基因比對算法流程

使用遺傳算法求解新舊地物的基因匹配問題，主要解決好編碼、適應度、交叉、變異算法等問題，其中編碼問題是遺傳算法中至關重要的一步，直接影響后面適應度計算的復雜度，算法流程如圖1所示。

在本文中，新地物集(即參考數(shù)據(jù))表示為A={A1，A2，A3，…Am}，舊地物集(即匹配數(shù)據(jù))表示為B={B1，B2，B3，…Bn}，其中Ai和Bj分別為參考數(shù)據(jù)集和匹配數(shù)據(jù)集中地物。

2.3 輪廓線標準化與編碼

標準化后的地物表示為新版本地物a={a1，a2，a3，…am}，其中ai為等距點；舊版本地物b={b1，b2，b3，…bm}，其中bj為等距點。

編碼是遺傳算法中至關重要的一步，本文以地物要素的空間特征為表現(xiàn)型，并將表現(xiàn)型轉(zhuǎn)化為基因型，即把求解空間中的參數(shù)轉(zhuǎn)化成遺傳空間中的染色體或者個體。針對新舊地物比對問題，本文采用長度為32位的二進制字符串表示新舊地物匹配的基點序號，即前面16位表示新地物的坐標序號，后16位表示舊地物的坐標序號。例如，假設兩個地物都以1號點為基點開始匹配，其基因型就是：

0000，0000，0000，0001，

0000，0000，0000，0001。

2.4 適應度計算

考核一個基因型對當前環(huán)境的適應度，在本文中即考核地物相似程度，相似度越高的地物更有可能存活遺傳下去，用適應函數(shù)f(x)表述，構(gòu)建最大基因組評價模型。如圖2所示，①為標準化后舊地物a={a1，a2，a3，…am}，②為標準化后新地物b={b1，b2，b3，…bm}，計算方法如下：

(1)對新地物進行旋轉(zhuǎn)平移操作(二項式變換)，使新舊地物基點前后3點～5點相互對齊，如圖2(a)中a8、a9、a10點與圖2(b)中b9、b10、b11號點對齊，舊地物基點為a9，新地物的基點為b10，平移旋轉(zhuǎn)參數(shù)用最小二乘法求得。對其后效果如圖2(c)；

圖2 最大基因組評價模型

(2)為保障算法魯棒性，用雙倍點位誤差為緩沖距離，對舊地物輪廓線a作緩沖計算，如圖2(c)窄條型多邊形；從基點a9開始先向前逐點計算新地物點是否落入緩沖區(qū)內(nèi)，直至不滿足為止；然后向后逐點比對，直至不滿足為止；落入總點數(shù)，即為單向適應度；

(3)設M，N為舊地物a={a1，a2，a3，…am}中標準化后的特征點數(shù)，n為新地物b={b1，b2，b3，…bm}中與a重合的特征點數(shù)，則單向適應度函數(shù)可表示為：

(4)對新地物輪廓線b作緩沖計算，用舊地物a進行疊加分析，可求得反向適應度。

(5)取兩個單向適應度和反向適應度平均值作為總的適應度。

2.5 選擇與交叉算子

選擇算子采用賭輪的方式進行淘汰選擇。先按照每個地物的適應度大小創(chuàng)建一個賭輪，設擁有不同基因的地物的適應度為f(xi)，則選擇概率可表示為：

當賭輪轉(zhuǎn)動起來，總以較大概率選擇適應度高的地物，即地物相似度高的地物。本文對賭輪選取4次，每次產(chǎn)生一個0～1的隨機小數(shù)，然后判斷該隨機數(shù)落在哪個選擇概率區(qū)間內(nèi)就選取相對應的地物。這個過程中，選取概率P高的個體將可能被多次選擇，而概率低的就則被淘汰。

兩個父代地物在交叉后繁殖出了下一代的同樣數(shù)量的地物。本算法采用黃金分割法進行交叉運算，即在黃金分割點0.618處進行交叉。設個體1新舊地物的比對基點分別是p11，p12；設個體2新舊地物的比對基點分別是p21，p22；交叉產(chǎn)生兩個新的個體的比對基點p31，p32；p41，p42；交叉計算公式如下：

p31=p11*0.618+p21*0.382；

p32=p12*0.618+p22*0.382；

p41=p11*0.382+p21*0.618；

p42=p12*0.382+p22*0.618；

2.6 變異、淘汰與終止條件

變異概率太小，則可能陷入局部最優(yōu)。變異概率太大，可能變成純粹的隨機算法，收斂速度太慢。經(jīng)過本文提出的算法進行反復實驗，取變異概率為0.01，效果較好。對種群中適應度最差的幾個個體進行淘汰，但最新交叉繁殖和變異得到新種群不包括在此例。

本算法設置兩類終止條件：一類是種群中最大適應度大于地物基因長度的90%，max(f(x))≥90%；

二類條件是迭代代數(shù)超過100代，最大適應度沒有發(fā)生變化。以上兩種類型視為已得到算法的穩(wěn)定解。

3 實驗與分析

為證實本文提出的匹配算法的有效性和適應性，選取福州市鼓樓區(qū)范圍內(nèi)約 2 km2的地形圖及城市管理部件數(shù)據(jù)進行更新實驗，分別采用Fourier描述子和本文提出的最大基因比對法進行相似度計算，實驗結(jié)果選取了9組典型的匹配實例，計算結(jié)果如表1所示：

典型圖形計算結(jié)果一覽表 表1

結(jié)果分析：2、5、8組圖形Fourier法和Gene法結(jié)果相差不大，可以看出這幾組圖形的形狀確實變化不大；1、3、6、7、9組計算結(jié)果差別很大，從圖形上看，這幾組地物出現(xiàn)了小部分變化，但仍具有較高的相似性，而在這幾組結(jié)果數(shù)據(jù)中，Gene比對法均能計算出比Fourier更高的相似度。

結(jié)果表明：本文算法比傳統(tǒng)相似度算法對局部較小變化有更強的容忍度，更適合空間數(shù)據(jù)庫更新過程中的要素匹配，不僅可一次性計算出新舊地物的匹配度，而且具有較好的平移旋轉(zhuǎn)不變性、和起點無關性。通俗地說，相似度結(jié)果計算過程有如我們打靶，我們首先尋找視野范圍較大的靶標，然后調(diào)整準心尋找靶心。

4 結(jié)論與展望

本文空間數(shù)據(jù)庫快速更新中地理要素匹配問題進行深入研究，采用空間信息科學與模糊數(shù)學相結(jié)合的分析方法，提出基于最大基因組比對模型的地物相似度計算方法，有效解決圖形相似度匹配算法中存在的不足，并通過與Fourier算法在多組地物要素實例進行了實驗和比較，證實該算法在同名地物檢測過程中對小范圍局部變化有較高的容忍度，適用于空間數(shù)據(jù)庫更新過程中的要素匹配。地物要素匹配是空間數(shù)據(jù)庫維護和更新的關鍵技術和研究基礎，基于幾何的地物相似度計算是其最重要的匹配方面之一，然而匹配精度的提高也需要語義、拓撲關系等指標的參與，因此綜合多指標，采取不同匹配策略的地物要素匹配算法成為今后發(fā)展方向。

[1] Saalfeld，A. Conflation Automated map compilation[J]. International Journal of Geographical Information System，1988，2(3)：217～228.

[2] Eliyah Safra，Yaron Kanza，etc. Efficient integration of road maps[C]. Proceedings of the 14th annual ACM international symposium on Advances in geographic information systems，New York，USA，2006.

[3] Sébastien Mustière. Thomas Devogele. Matching Networks with Different Levels of Detail[J]. Geoinformatica，2008，2(12)：435～453.

[4] 陳玉敏，龔健雅，史文中. 多尺度道路網(wǎng)的距離匹配算法研究[J]. 測繪學報，2007，36(1)：84～90.

[5] 趙東保，盛業(yè)華. 全局尋優(yōu)的矢量道路網(wǎng)自動匹配方法研究[J]. 測繪學報，2010，39(4)：416～421.

[6] 胡云崗，趙仁亮，李志林等. 地圖數(shù)據(jù)縮編更新中道路數(shù)據(jù)匹配方法[J]. 武漢大學學報·信息科學版，2010，35(4)：451～456.

[7] Maythm Al-Bakri，David Fairbairn. Assessing Similarity Matching for Possible Integration of Feature Classifications of Geospatial Data from Official and Informal Sources[J]. International Journal of Geographical Information Science，2012，26(8)：1～20.

[8] 田文文，朱欣焰，咼維. 一種VGI矢量數(shù)據(jù)增量變化發(fā)現(xiàn)的多層次蔓延匹配算法[J]. 武漢大學學報·信息科學版，2014，39(8)：963～967.

[9] 徐楓，鄧敏，趙彬彬等. 空間目標匹配方法的應用分析[J]. 地球信息科學學報，2009，11(5)：657～663.

[10] 王濤，劉文印，孫家廣等. 傅立葉描述子識別物體的形狀[J]. 計算機研究與發(fā)展，2002，13(12)：1715～1718.

[11] 唐爐亮，李清泉，楊必勝. 空間數(shù)據(jù)網(wǎng)絡多分辨率傳輸?shù)膸缀螆D形相似性度量[J]. 測繪學報，2009，38(4)：336～340.

[12] 趙宇，陳雁秋. 曲線描述的一種方法：夾角鏈碼[J]. 軟件學報，2004，15(2)：300～307.

[13] Kieler B，Sester M，Wang H，etal. Semantic Data Integration：Data of Similar and Different Scales[J]. Photogrammetrie Femerkundung Geoinformation，2007，3(6)：447～457.

[14] 丁虹. 空間相似性理論與計算模型的研究[D]. 武漢：武漢大學，2004，13～34.

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

[16] 張橋平，李德仁，龔健雅. 城市地圖數(shù)據(jù)庫面實體匹配技術[J]. 遙感學報，2004，8(2)：107～112.

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

A Method of Geographical Feature Matching Based on the Largest Genome Comparison

Gao Zhaoliang1，2

(Fuzhou Investigation and Mapping Institute，F(xiàn)uzhou 350003，China)

Geographical feature matching technology is the technical basement of update maintenance of geographic spatial database. It has important theoretical and practical significance to improve the level of geospatial information application and timeliness. This paper makes a detailed analysis for changes of the spatial database，points out the shortage of the existing matching technology，based on this，a matching algorithm based on the largest genome comparison method is introduced from the perspective of geometry for oriented spatial database rapid updating. And the feasibility of the method is validated.

the largest genome comparison method；feature matching；spatial database updating

1672-8262(2016)06-10-04

P208，O235

A

2016—05—31

高昭良(1972—)，男，博士，高級工程師，主要從事測繪、地理信息生產(chǎn)研究工作。

國家863計劃資助項目(2013AA01A608)