空間相似性和旋轉(zhuǎn)不變性的空間場景匹配研究

房家偉 凌云

摘 要：空間場景與人類生活密切聯(lián)系，無處不在，是人們生活發(fā)生的真實(shí)空間。本文針對矢量空間場景匹配過程中的旋轉(zhuǎn)問題，引入位置圖的概念，分析待匹配場景的內(nèi)部結(jié)構(gòu)之間的關(guān)系，如圖元間的最近點(diǎn)、最遠(yuǎn)點(diǎn)、質(zhì)心點(diǎn)，而這種關(guān)系不隨場景的旋轉(zhuǎn)而變化。突破以往從圖元個體角度描述草圖特征的方法，轉(zhuǎn)換思路為將空間場景作為群組對象，從整體上刻畫草圖特征。本文以鄭州市局部區(qū)域?yàn)閷?shí)驗(yàn)數(shù)據(jù)，利用該區(qū)的矢量化數(shù)據(jù)進(jìn)行驗(yàn)證，并分析評價匹配結(jié)果。實(shí)驗(yàn)結(jié)果表明基于位置圖和空間相似性的方法能很好地實(shí)現(xiàn)空間場景匹配，并能解決場景旋轉(zhuǎn)等問題。

關(guān)鍵詞：空間相似性;旋轉(zhuǎn)不變性;位置圖;波形圖;空間場景匹配

中圖分類號：TP391? 文獻(xiàn)標(biāo)識碼：A? 文章編號：1673-260X（2020）09-0040-05

1 引言

在GIS研究方面，針對空間相似性很多學(xué)者一般都用空間幾何關(guān)系中的圖元形狀特征、圖元的相對大小特征、兩圖元的相對方向特征、空間關(guān)系中的圖元間的拓?fù)潢P(guān)聯(lián)、圖元間的距離遠(yuǎn)近、圖元間的相對方向等來表現(xiàn)[1]?？臻g相似性關(guān)系計(jì)算性不高，且空間關(guān)系相對復(fù)雜，因此在計(jì)算空間圖元相似性時要同時考慮空間幾何關(guān)系中的形狀特性、大小特性、方向特性;空間關(guān)系中的拓?fù)潢P(guān)系、距離關(guān)系、方向關(guān)系等多個因子[2]。通過對空間相似性的度量，可以用來揭示空間場景匹配，也對世界的認(rèn)知提供更多的理論價值和應(yīng)用價值，因此受到國內(nèi)外很多學(xué)者的研究和關(guān)注[1～4]。

探究空間場景匹配問題其實(shí)就是計(jì)算空間圖元目標(biāo)實(shí)體的相像程度[5]。通?？臻g場景相似性是將單個圖元的相似關(guān)系，以及每個圖元之間的空間關(guān)聯(lián)相似性用來建立關(guān)聯(lián)圖，計(jì)算出相似性[6]。但是此類方法難以解決場景的旋轉(zhuǎn)問題，從而導(dǎo)致漏查，錯查等結(jié)果[7]。因此提出位置圖的計(jì)算方法，把輸入數(shù)據(jù)（草圖）看成一個整體，分析其整體關(guān)系，包括各圖元間的類空間關(guān)系。從而解決匹配過程中輸入數(shù)據(jù)與參考數(shù)據(jù)的旋轉(zhuǎn)問題。結(jié)合草圖數(shù)據(jù)融合的優(yōu)勢，探索面向地理場景的匹配方法，將會進(jìn)一步提高空間匹配的可用性;進(jìn)一步揭示地理場景的認(rèn)知、描述和應(yīng)用機(jī)理;促進(jìn)地理信息科學(xué)和技術(shù)的智能化、大眾化、社會化發(fā)展。

2 解決方案

為了提高場景相似性檢索的精度，使用草圖整體特征相似性度量方法，本文首先通過草圖的重心點(diǎn)、最近點(diǎn)、最遠(yuǎn)點(diǎn)繪制出幾何位置圖。然后，利用折線相似性計(jì)算算法計(jì)算出相似性，從而完成粗匹配。最后，結(jié)合空間場景的集合相似性和空間關(guān)系相似性完成精匹配。

本文選取鄭州市部分地區(qū)的矢量數(shù)據(jù)作為匹配場景進(jìn)行實(shí)驗(yàn)。圖1中A為匹配場景，圖B1，B2，B3，B4，B5中為數(shù)據(jù)庫。

3 基于位置圖的草圖場景粗匹配

3.1 空間幾何坐標(biāo)的獲取

每個面狀圖元都可以用一個形狀中心點(diǎn)來表示。通過該點(diǎn)可以從整體的角度來研究旋轉(zhuǎn)不變性、平移不變性等特征[7]。對于矢量數(shù)據(jù)，大多數(shù)都是用幾何坐標(biāo)中心點(diǎn)，但是基于本文場景匹配的條件下，需要考慮可能兩個相似度較高的形狀可能幾何坐標(biāo)點(diǎn)不一致[8]?？紤]到幾何目標(biāo)的面積特征，本文采用重心作為目標(biāo)的形狀中心點(diǎn)。

但是針對多圖元群組來說，很多學(xué)者采用最小外包矩形（MBR）和最小面積外接矩形來描述群組目標(biāo)。因?yàn)橄啾容^于MBR來說，最小面積外接矩形更接近原目標(biāo)的形狀[6，7]。故本文采用最小面積外接矩形來描述群組。根據(jù)公式（1）求得群組的最小面積外包矩形的質(zhì)心。

上式中的n為圖元的每條邊與原點(diǎn)組成三角形的面積，Xi，Yi分別表示第i個點(diǎn)在X和Y軸的坐標(biāo)?；谏鲜龇椒ǖ玫搅丝臻g幾何坐標(biāo)以及群組目標(biāo)的最小面積外接矩形質(zhì)心：

3.2 幾何與力的位置圖繪制與計(jì)算

通過群組目標(biāo)的最小面積外接矩形質(zhì)心與各圖元間的重心點(diǎn)、最近點(diǎn)、最遠(yuǎn)點(diǎn)的關(guān)系特征，且這種關(guān)系特征特別的靈活，在群組整體發(fā)生旋轉(zhuǎn)，偏移的時候，能夠很好地度量群組的相似性[9，11]。本文采用位置圖來反映這種圖元間的關(guān)系。

由力的位置圖分析可得投影比為一個常量[1]，但是由于用戶輸入等問題，匹配圖形可能會存在旋轉(zhuǎn)問題，需要再對每個群組做旋轉(zhuǎn)分析。本文以群組最小MBR的質(zhì)心為旋轉(zhuǎn)中心，為？琢°為旋轉(zhuǎn)角度（0°<？琢<360°）進(jìn)行旋轉(zhuǎn)。用相同算法求出投影比。為了直觀方便的反映圖元間的投影比關(guān)系，采用波形圖的形式進(jìn)行展示。

3.3 波形圖相似性的計(jì)算

波形圖的X軸坐標(biāo)的跨度比較大，為0-360;而Y軸的坐標(biāo)卻是0-20之間[12，13]。針對這個問題，提出了對波形圖進(jìn)行歸一化得做法：

（1）遍歷所有數(shù)據(jù)，找出X，Y的最大值和最小值;

（2）X，Y的所有值分別減去最小值，然后除以最大值和最小值的差。

根據(jù)上述算法[12-17]，得到波形圖的相似度如下，進(jìn)行相似程度排序如表2：

通過繪制波形圖可以看出B1和B2、B3具有較高的相似性。但是并不能確定它們就是用戶所要匹配的場景，還可能存在如下可能，因此要做精匹配。

情況一：MBR相同，重心相同，但是圖元不同。見圖2（a）：群組MBR和重心相同。

情況二：群組相同（包括各圖元相同），但是群組整體變大。見圖2（b）：群組等比放大。

情況三：部分圖元確定，部分只是位置稍微偏離。見圖2（c）：部分圖元偏離。

4 基于空間相似性的精匹配

針對粗匹配中出現(xiàn)的問題，本章通過精匹配從粗匹配結(jié)果排序中篩選出最可能的空間場景。首先，群組的幾何相似性通過圖元的形狀，大小，方向等幾何特征來描述[18，19];然后，空間場景的空間關(guān)系相似度用圖元間的拓?fù)潢P(guān)系、距離關(guān)系、方向關(guān)系的相似度來度量[20-25];最后本文用層次分析法，分別對空間場景的幾何相似度及空間關(guān)系相似度附以不同的權(quán)重，來表示空間場景的總相似性。而相似性是定量衡量空間場景的接近程度，因此可以完成空間場景的匹配[18，19，24]。

4.1 空間場景幾何相似性的計(jì)算

空間場景幾何相似性的計(jì)算包含了形狀相似性[25]、大小相似度[21]和方向相似度[15]，計(jì)算方法見參考文獻(xiàn)，由此計(jì)算出本文研究區(qū)的形狀、大小，方向相似度，見表3：

如此，很容易得到A1，B17兩圖元之間的形狀相似程度SimF（A1，B17）、A1，B17之間的大小相似程度SimS（A1，B17）和它們之間的方向相似程度Sim？茲（A，B）。結(jié)合層次分析模型，分別對空間幾何關(guān)系中的形狀、大小和方向相似度賦予不同的權(quán)重因子，即得到兩空間圖元的幾何度SimG（A，B）：

simG（A，B）=kF×simF（A，B）+kS×simS（A，B）

+k？茲×sim？茲（A，B）? （2）

其中，式（2）中的KS、K？茲、KF分別代表空間圖元幾何特征的大小，方向和形狀被賦予的比重因子。它們的和為1，且每個值的大小都在0到1的范圍內(nèi)。

因?yàn)橐粋€群組中有多個圖元，考慮到單圖元的相似性、整體的幾何相似性，本文采用均值的方法，見表4。

4.2 空間場景空間關(guān)系相似性的計(jì)算

空間關(guān)系是研究GIS重要理論之一，目前國內(nèi)外學(xué)者一般從空間圖元間的拓?fù)潢P(guān)系、距離關(guān)系、方向關(guān)系等方面來度量空間關(guān)系的相似性[26，27]。

4.2.1 拓?fù)潢P(guān)系

本文數(shù)據(jù)匹配場景中只涉及面與面的相鄰及面與面的相離這兩種空間拓?fù)潢P(guān)系，研究群組的空間關(guān)系時，以群組為單位分析其內(nèi)部圖元間的空間關(guān)系。

通過粗匹配的匹配結(jié)果排序，排除SimT（A（），B（））=0的情況。因此以下實(shí)驗(yàn)只需考慮匹配場景與數(shù)據(jù)庫中待匹配場景的第二種情況。但是針對匹配場景有4個圖元目標(biāo)，首先要選取其中一個單圖元為參考目標(biāo)，從而以它為參考點(diǎn)來計(jì)算最短距離。本實(shí)驗(yàn)是以A1，B1，B5，B9，B13，B17為參考目標(biāo)得到的是群組整體的數(shù)據(jù)平均距離。計(jì)算拓?fù)湎嗨贫萚26，27]可得表5。

4.2.2 方向關(guān)系

方向Voronoi圖模型和方向關(guān)系矩陣模型能夠通過數(shù)值來反映空間方向相似性。實(shí)驗(yàn)考慮數(shù)據(jù)計(jì)算的復(fù)雜性和考慮圖元的整體性，選用改進(jìn)的方向關(guān)系矩陣模型來描述空間方向相似度。在以A1，B1，B5，B9，B13，B17為參考目標(biāo)時，根據(jù)方向關(guān)系[26，27]公式計(jì)算出匹配場景和數(shù)據(jù)庫待匹配各場景的特征向量。

在上述公式計(jì)算得到的空間圖元特征向量基礎(chǔ)上，根據(jù)相關(guān)系數(shù)法來度量兩個場景的空間關(guān)系相似度[26，27]SimD（AB，EF），見表6。

4.2.3 距離關(guān)系

為了準(zhǔn)確地計(jì)算距離關(guān)系的相似程度的大小，需選用圖元的重心點(diǎn)表示質(zhì)心距離中的質(zhì)心點(diǎn)。在粗匹配中第一步已經(jīng)獲取各圖元的重心坐標(biāo)。且粗匹配已經(jīng)考慮了圖元的形狀、大小和方向的相似度，所以在計(jì)算空間場景A的距離關(guān)系[26，27]時，可以用每個圖元與參考圖元的距離總和作為匹配場景和數(shù)據(jù)庫待匹配各場景的距離（見表7）;

4.3 空間場景相似性的計(jì)算

為了提高匹配的準(zhǔn)確性和充分利用匹配的約束特征，采用層次分析法同時度量空間幾何關(guān)系和空間關(guān)系，并賦予不同的權(quán)重因子。

本文參考文獻(xiàn)[22]的權(quán)重賦值如下：

SIM=0.8×[0.6×[0.4×simT+（simd+simD）×0.3]

+0.4×（simF+simS+sim？茲）]+0.2×simCU? （3）

匹配結(jié)果排序，見表8。

5 總結(jié)

早就有“一圖勝千言”的說法，人們可以簡單便捷地通過感知將大量的數(shù)據(jù)融合用草圖表示出來，通過對草圖的分析，可以高效地整合信息，節(jié)約信息化成本和精確地獲取地理空間位置。由此可見草圖在描述空間場景方面的優(yōu)勢。

本文是以空間場景匹配為突破口，旨在解決在場景匹配中存在的場景旋轉(zhuǎn)問題。充分利用矢量數(shù)據(jù)的可視化及空間圖元間的空間幾何和空間關(guān)系特征。從人們對空間的定性思考的思維方式來說，空間場景匹配可以通過空間相似性進(jìn)行度量。通過對空間相似性的研究，也為多源數(shù)據(jù)的融合和空間場景查詢提供了強(qiáng)有力的理論基礎(chǔ)，對將來智能化GIS的發(fā)展也有深遠(yuǎn)的影響。

論文通過在前人相關(guān)知識研究的基礎(chǔ)上，進(jìn)行了圖像場景匹配的分析列舉與匯總。從空間場景的中圖元的幾何特征（形狀、大小等）來計(jì)算圖元的幾何特征相似度，并對拓?fù)潢P(guān)系、方向關(guān)系、距離關(guān)系進(jìn)行了深度的描述，并最終找出最合適的方法來度量空間關(guān)系的相似性;對提出的位置圖方法也進(jìn)行了深度的解讀，清晰地表述粗匹配的各步驟及計(jì)算波形圖的相似度算法的介紹。最后取鄭州市某局部地區(qū)的矢量數(shù)據(jù)為實(shí)驗(yàn)數(shù)據(jù)，對上述的方法進(jìn)行了驗(yàn)證，并對實(shí)驗(yàn)的結(jié)果進(jìn)行了多角度的分析評價。最終從實(shí)驗(yàn)結(jié)果發(fā)現(xiàn)，基于空間相似性和旋轉(zhuǎn)不變性的方法能夠匹配到更為相似的空間場景，匹配的結(jié)果也更符合用戶的空間認(rèn)知觀念。

——————————

參考文獻(xiàn)：

〔1〕潘柔.矢量面狀地物的空間場景相似性計(jì)算方法研究[D].長安大學(xué)，2015.

〔2〕Xu Y ， Xie Z ， Chen Z ， 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（1-2）：253-279.

〔3〕郝燕玲，唐文靜，趙玉新，等.基于空間相似性的面實(shí)體匹配算法研究[J].測繪學(xué)報(bào)，2008，37（04）：501-506.

〔4〕鄭宇志，張青年.基于拓?fù)浼翱臻g相似性的面實(shí)體匹配方法研究[J].測繪科學(xué)技術(shù)學(xué)報(bào)，2013，30（05）：106-111.

〔5〕翟仁健.基于全局一致性評價的多尺度矢量空間數(shù)據(jù)匹配方法研究[D].解放軍信息工程大學(xué)，2011.

〔6〕趙彬彬.多尺度矢量地圖空間目標(biāo)匹配方法及其應(yīng)用研究[D].中南大學(xué)，2011.

〔7〕郭黎，鄭海鷹，王豪.面狀矢量空間數(shù)據(jù)匹配技術(shù)研究[J].海洋測繪，2009，29（03）：12-15.

〔8〕黃智深，錢海忠，王驍，金永崗，張強(qiáng).基于降維技術(shù)的面狀居民地匹配方法[J].測繪科學(xué)技術(shù)學(xué)報(bào)，2012，29（01）：103-109.

〔9〕Zhang J R， Zhang J， Lok T M， et al. A hybrid particle swarm optimization-back-propagation algorithm for feedforward neural network training[J]. Applied Mathematics & Computation， 2007， 185（02）：1026-1037.

〔10〕Papadias D， Egenhofer M J， Sharma J. Hierarchical reasoning about direction relations? in： Proc. 4th ACM Workshop on GIS [C]. 1996：105-112.

〔11〕Papadias D， Delis V. Relation-based similarity[C]. Fifth ACM International Workshop on Advances in Geographic Information Systems. ACM， 1997：1-4.

〔12〕Ai T， van Oosterom P. A displacement method based on field analysis[C].In：SymPosium on Integrated Systems for Spatial Data Production，Custodian and Decision Support. Xi'an，2002：1-8.

〔13〕WANG Zeshen， DanLee. Buliding Simplification Based on Pattern Recognition and Shape Analysis[C].SDH 2000-Conference? Proceedings.2000，58-72.

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

〔15〕郭黎，崔鐵軍，鄭海鷹.基于空間方向相似性的面狀矢量空間數(shù)據(jù)匹配算法[J].測繪科學(xué)技術(shù)學(xué)報(bào)，2008，25（05）：115-121.

〔16〕Nedas K A， Egenhofer M J. Spatial-Scene Similarity Queries[J]. Transactions in Gis， 2008， 12（6）：661-681.

〔17〕Jun Chen， Chengming Li， Zhilin Li， et al. A Voronoi-based 9-intersection model for spatial relations[J]. International Journal of Geographical Information Science， 2001， 15（3）：201-220.

〔18〕童小華，鄧愫愫，史文中.基于概率的地圖實(shí)體匹配方法[J].測繪學(xué)報(bào)，2007，36（02）：210-217.

〔19〕邵世維.基于幾何特征的多尺度矢量面狀實(shí)體匹配方法研究與應(yīng)用[D].武漢大學(xué)，2011.

〔20〕Rylov M A， Reimer A W. Improving label placement quality by considering basemap detail with a raster-based approach[J]. GeoInformatica， 2015， 19（3）：463-486.

〔21〕章莉萍，郭慶勝，等.相鄰比例尺地形圖之間居民地要素匹配方法研究[J].武漢大學(xué)學(xué)報(bào)信息科學(xué)版，2008，33（06）：255-260.

〔22〕劉濤，閆浩文.空間面群目標(biāo)幾何相似度計(jì)算模型[J].地理信息科學(xué)學(xué)報(bào)，2013，15（05）：356-361.

〔23〕吳靜，尹濤.多尺度空間關(guān)系相似性研究[J].測繪科學(xué)，2011，36（04）：59-63.

〔24〕Deng M， Li Z L，Chen X Y. Extended? Hausdorff distance for spatial objects in GIS[J].International Journal of Geographical Information Science，2007，21（04）：459-475.

〔25〕艾廷華，帥赟，李精忠.基于形狀相似性識別的空間匹配[J].測繪學(xué)報(bào)，2009，38（04）：306-310.

〔26〕Frontiera， P.， R. Larson and J. Radke， A comparison of geometric approaches to assessing spatial similarity for GIR[J]. International Journal of Geographical Information Science， 2008. 22（03）： p. 337-360.

〔27〕Yan H，Chu Y，Li Z，et al.A quantitative description model for directional relations based on direction groups[J].Geoinformatica，2006，10（02）：177-195.