高昭良

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

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

高昭良*

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

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

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

1 引 言

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

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

2 最大基因組比對(duì)算法

2.1 遺傳算法

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

maxf(x)

(1)

x∈R

(2)

R?U

(3)

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

遺傳算法的基本運(yùn)算過(guò)程如下：

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

(2)個(gè)體評(píng)價(jià)：計(jì)算群體P(t)中各個(gè)個(gè)體的適應(yīng)度。

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

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

(5)變異運(yùn)算：將變異算子作用于群體。即是對(duì)群體中的個(gè)體串的某些基因座上的基因值作變動(dòng)。

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

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

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

2.2 最大基因組比對(duì)算法模型

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

圖1 基因比對(duì)算法流程

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

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

2.3 輪廓線標(biāo)準(zhǔn)化與編碼

標(biāo)準(zhǔn)化后的地物表示為新版本地物a={a1，a2，a3，…am}，其中ai為等距點(diǎn)；舊版本地物b={b1，b2，b3，…bm}，其中bj為等距點(diǎn)。

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

0000，0000，0000，0001，

0000，0000，0000，0001。

2.4 適應(yīng)度計(jì)算

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

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

圖2 最大基因組評(píng)價(jià)模型

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

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

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

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

2.5 選擇與交叉算子

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

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

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

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ī)算法，收斂速度太慢。經(jīng)過(guò)本文提出的算法進(jìn)行反復(fù)實(shí)驗(yàn)，取變異概率為0.01，效果較好。對(duì)種群中適應(yīng)度最差的幾個(gè)個(gè)體進(jìn)行淘汰，但最新交叉繁殖和變異得到新種群不包括在此例。

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

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

3 實(shí)驗(yàn)與分析

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

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

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

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

4 結(jié)論與展望

本文空間數(shù)據(jù)庫(kù)快速更新中地理要素匹配問(wèn)題進(jìn)行深入研究，采用空間信息科學(xué)與模糊數(shù)學(xué)相結(jié)合的分析方法，提出基于最大基因組比對(duì)模型的地物相似度計(jì)算方法，有效解決圖形相似度匹配算法中存在的不足，并通過(guò)與Fourier算法在多組地物要素實(shí)例進(jìn)行了實(shí)驗(yàn)和比較，證實(shí)該算法在同名地物檢測(cè)過(guò)程中對(duì)小范圍局部變化有較高的容忍度，適用于空間數(shù)據(jù)庫(kù)更新過(guò)程中的要素匹配。地物要素匹配是空間數(shù)據(jù)庫(kù)維護(hù)和更新的關(guān)鍵技術(shù)和研究基礎(chǔ)，基于幾何的地物相似度計(jì)算是其最重要的匹配方面之一，然而匹配精度的提高也需要語(yǔ)義、拓?fù)潢P(guān)系等指標(biāo)的參與，因此綜合多指標(biāo)，采取不同匹配策略的地物要素匹配算法成為今后發(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]. 測(cè)繪學(xué)報(bào)，2007，36(1)：84～90.

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

[6] 胡云崗，趙仁亮，李志林等. 地圖數(shù)據(jù)縮編更新中道路數(shù)據(jù)匹配方法[J]. 武漢大學(xué)學(xué)報(bào)·信息科學(xué)版，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]. 武漢大學(xué)學(xué)報(bào)·信息科學(xué)版，2014，39(8)：963～967.

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

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

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

[12] 趙宇，陳雁秋. 曲線描述的一種方法：夾角鏈碼[J]. 軟件學(xué)報(bào)，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] 丁虹. 空間相似性理論與計(jì)算模型的研究[D]. 武漢：武漢大學(xué)，2004，13～34.

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

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

[17] 趙彬彬. 多尺度矢量地圖空間目標(biāo)匹配方法及其應(yīng)用研究[D]. 長(zhǎng)沙：中南大學(xué)，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—)，男，博士，高級(jí)工程師，主要從事測(cè)繪、地理信息生產(chǎn)研究工作。

國(guó)家863計(jì)劃資助項(xiàng)目(2013AA01A608)