空間點群目標相似度計算模型及應用

梁哲恒，謝輝榮，謝剛生

(1. 廣東南方數碼科技股份有限公司，廣東 廣州 510665； 2. 華南農業大學，廣東 廣州 510640)

?

空間點群目標相似度計算模型及應用

梁哲恒1，謝輝榮2，謝剛生1

(1. 廣東南方數碼科技股份有限公司，廣東 廣州 510665； 2. 華南農業大學，廣東 廣州 510640)

Study on the Calculation Model of Spatial Grouped Point Object Similarity and Its Application

LIANG Zheheng，XIE Huirong，XIE Gangsheng

摘要：為了研究點群目標的相似性問題，整合了與點群目標有關的拓撲關系、方向關系、距離關系、分布范圍和分布密度5種要素，這5種要素是影響點群目標相似度的主要因子。根據這5種因子的特點，提出了各個因子相似度的計算模型，最后得到了點群目標之間相似度的總體計算模型。經過驗證，該方法能準確地計算點群目標之間的相似程度，符合人們的日常認知。

關鍵詞：空間關系；相似性；點群目標

空間目標的相似性在人類認知過程中具有重要的作用，是進行歸納、分類和類比的基礎。空間目標的相似性在空間認知中起著同樣的作用[1]。同一尺度空間下的不同目標之間，相似性的研究可以提供空間數據的查詢和檢索[2]、數據集成和互操作[3]、數據挖掘等方面的應用；并在不同尺度空間下的同一目標進行匹配和綜合質量評價[4]。

在心理學和認知科學中，相似關系研究得較多，但在地理空間中的應用，相似關系一直以來研究得較少。一方面由于空間相似關系比較復雜、可計算性差[5]，地理空間的相似關系的計算要考慮的因素很多，如空間關系、空間分布、幾何特征、語義特征等[1]。空間相似關系研究與模式識別、圖像檢索密切相關。模式識別中主要針對單一目標的相似性研究[6]，圖像檢索主要是以柵格圖像為主[7]。國內外學者作了諸多探討和研究，如Bruns等引入心理學中的變換模型[8]；Li等在此基礎上引入拓撲關系、方向關系和距離關系，并提出計算模型[1]。

點群目標是空間目標的重要組成部分，有一定的研究價值[9]。本文考慮到視覺識別的Gestalt原則，以及影響空間點群目標的拓撲關系、距離關系、方向關系、分布范圍和分布密度，對空間點群目標相似度進行整體度量，并以試驗驗證結果的可靠性。

一、點群信息與點群相似度

1. 相似度的定義

Holt在考慮了空間尺度和空間上下文關系之后，對空間目標相似度的定義如下:在某一特定的粒度(比例尺)和內容(專題屬性)上被認為是相似的兩個區域。但該定義過于籠統和模糊，文獻[4]用集合學的方法對空間相似性進行了定義，具有清晰的數學描述。

2. 點群信息

空間目標可以從目標屬性、空間變量和幾何特征[9]等幾個角度認識。點群目標的信息普遍由統計信息、專題信息、拓撲信息、度量信息[10]決定，但根據Bruns提出的觀點，空間目標的幾何特征中拓撲關系、方向關系和距離關系是最關鍵的幾個因素[11]，應該突出某些參數的重要性。因此，本文分別從空間拓撲關系、空間方向關系、空間距離關系、點群分布范圍、點群分布密度[8]幾個方面進行研究，最后得到計算點群相似度的公式。

二、點群目標相似度的計算方法

點群目標具有聚合的性質，其分布輪廓與凸殼有密切聯系，因此用凸殼來逼近點群的全局結構[11]。凸殼是覆蓋點群目標的最小凸圖形，在實際的應用中，凸殼起著重要作用，如公路規劃中，各個鄉、鎮、村建立點集凸殼，可科學規劃環形公路；且凸殼直徑具有一定的方向性，符合人們的日常認知。本文對點群目標建立凸殼，計算凸殼的直徑，并通過凸殼直徑確定定長值K；以凸殼直徑與水平方向的夾角來表示方向；在此基礎上，用凸殼的面積與點群的點的個數計算點群的分布范圍和分布密度。如圖1、圖2所示。

圖1　點群目標的凸殼

圖2　凸殼直徑

1. 拓撲相似度

點群之間的拓撲關系可以用點的鄰居來表示，如圖3所示。點的鄰居可以是定長距離鄰居、k個最近鄰居、Voronoi鄰居等。選擇定長距離鄰居作為點群拓撲信息的描述參數，主要是由于可以根據實際情況設定鄰居的長度。通過嘗試不同的定長距離d，記錄每個點的拓撲鄰居個數，拓撲相似度的計算公式為

(1)

式中，D為點群目標鄰居的數量；n為點群目標點的個數。

圖3　點群的拓撲鄰居

2. 方向關系相似度

點群的方向可以表示點群目標分布的大體趨勢，點群凸多邊形的直徑可以看成點群分布的主要方向，用凸殼多邊形的直徑與水平線之間的夾角θ表示點群目標分布的方向，θ取值范圍為[0，π]。當兩凸殼直徑夾角相差180°時，兩目標的相似度為1，這符合人們的認知。其相似性的公式為

(2)

式中，θ1、θ2分別為點群目標凸殼直徑與水平線的夾角。

3. 分布范圍相似度

在點群周圍構建凸殼，凸殼的面積大致能夠反映點群的分布范圍。點群目標的分布范圍大致上可以用凸殼的面積S計算，其公式如下

(3)

式中，S為點群的凸殼面積。

4. 點群分布密度相似度

點群目標的分布密度可以表示點群分布的疏密程度。點群密度的計算公式為點群數目與凸殼面積的比值。其點數與凸殼面積的比值大致上表示點群的分布密度，因此，可以用以下公式表示點群的分布密度相似度

(4)

5. 距離關系相似度

計算點群目標的距離相似度，本文借助的是最小外接矩形(minimum bounding rectangle, MBR)。點群目標的最小外接矩形能夠大致反映點群目標分布的形狀及集中程度，如圖4所示。做出點群目標的最小外接矩形，求出外接矩形的長和寬，由此可求得

(5)

式中，A、B為MBR的長和寬。其中MBR長和寬的比值反映了點群目標的分布的密集程度。

圖4　最小外接矩形

6. 點群目標相似度的計算

考慮到點群目標的幾何特征，對點群目標進行總體計算，其計算公式如下

(6)

上式為點群目標相似性的整體計算模型。根據數值分析和概率論的研究,幾何平均值要比算術平均值在處理差異性方面更加具有穩定性，因此，對點群目標的總體相似性應用幾何平均值。

三、試驗和結論

為了驗證點群相似程度算法的正確性，選擇某公交站點的分布情況。圖5為幾年前的公交車站的分布情況，圖6為現在公交車站的分布情況，圖7為不相關的某些點集。分別對這3個點群求各個因子的相似度及總體相似度，結果見表1、表2。

圖5　點群1

圖6　點群2

圖7　點群3

由表1可知，點群1和點群2之間的各因子的度量結果都比較接近，點群1與點群3之間、點群2與點群3之間的各個度量值差距比較大。

表1　各因子的統計結果

表2　點群各影響因素的相似度及總體相似度

由表2的計算結果可以得到以下結論：

1) 點群1和點群2之間各個因素的相似度都很高，說明同一點群目標在一定的時間段內的變化不大。

2) 點群1與點群3之間，點群2與點群3之間的各要素相似程度都很小，說明互不相關的點群目標之間相關程度很小。

3) 點群1和點群2之間的分布密度相似度很小，由于在同一區域，點群數目的變化比較大，而點群目標的影響范圍變化不大，導致計算點群目標之間的分布密度相似度時，出現不一致性。

4) 此結果符合人們的日常認知，可以作為比較兩個點群目標之間相似度的一般方法。

四、結束語

本文提出點群目標之間相似度的計算模型，并通過試驗證明了此算法可以較為準確地計算點群目標之間的相似程度，為同一尺度下的不同目標之間的數據查詢、互操作、數據挖掘方面提供支持，希望對實際的計算分析能提供一定的參考。

參考文獻：

[1]LI B,FONSECA F. TDD-A Comprehensive Model for Qualitative Spatial Similarity Assessment[J]. Spatial Cognition & Computation an Interdisciplinary Journal，2006,6(1):31-62.

[2]GOODCHILD M F, EGENHOFER M J, KEMP K K, et al. Introduction to the Varenius project.[J]. International Journal of Geographical Information Science, 1999, 13(8):731-745.

[3]FRONTIERA P, LARSON R, RADKE J. A Comparison of Geometric Approaches to Assessing Spatial Similarity for GIR[J]. International Journal of Geographical Information Science, 2008, 22(3):337-360.

[4]閆浩文，褚衍東.多尺度地圖空間相似關系基本問題研究[J].地理與地理信息科學，2009，25(4)：42-44.

[5]陳春希，凌子燕，廖超明.基于遙感與GIS技術的景觀格局自相似性的尺度效應研究——以防城港市為例[J].測繪通報，2012(5)：50-52.

[6]陳飛，張榮，何華貴.城市多尺度空間數據庫的實現方法[J].測繪通報，2014(S2)：252-255.

[7]郭仁忠.空間分析[M].北京：高等教育出版社，2001：240-244.

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

[9]WANG J Z, LI J, WIEDERHOLD G. Simplicity: Semantics-Sensitive Integrated Matching for Picture Libraries[J].IEEE Transactions on Pattern Analysis and Machine Intelligence, 2001, 9(23):947-963.

[10]BRUNS H T, EGENHOFER M J. Similarity of Spatial Scenes[C]∥Seventh Symposium on Spatial Data Handling.London:[s.n.], 1998:31-42.

[11]劉濤，杜清運，閆浩文.空間點群目標相似度計算[J].武漢大學學報(信息科學版)，2011，36(10)：1149-1153.

[12]LI Z L, HUANG P Z. Quantitative Measures for Spatial Information of Maps[J]. International Journal of Geographical Information Science, 2002, 16(7):699-709.

[13]毋河海.凸殼原理在點群目標綜合中的應用[J] .測繪工程，1997，6(1)：1-6.

[14]郝燕玲，唐文靜，趙玉新，等.基于空間相似性的面實體匹配算法研究[J].測繪學報，2008，37(4)：501-506.

中圖分類號：P208

文獻標識碼：B

文章編號：0494-0911(2016)03-0111-04

作者簡介：梁哲恒(1977—)，男，碩士，工程師，主要研究方向為GIS軟件開發管理。E-mail：zheheng.liang@southgis.com

收稿日期：2015-11-16； 修回日期： 2016-01-07

引文格式： 梁哲恒，謝輝榮，謝剛生. 空間點群目標相似度計算模型及應用[J].測繪通報，2016(3)：111-114.DOI:10.13474/j.cnki.11-2246.2016.0100.