基于馬氏距離的多高斯Voronoi圖生成方法

康 順，相 詩 堯

(中國礦業(yè)大學(xué)(北京) 地球科學(xué)與測繪工程學(xué)院，北京 100083)

基于馬氏距離的多高斯Voronoi圖生成方法

康 順，相 詩 堯

(中國礦業(yè)大學(xué)(北京) 地球科學(xué)與測繪工程學(xué)院，北京 100083)

Voronoi圖作為一種重要的幾何結(jié)構(gòu)，不僅是計算幾何研究的重要內(nèi)容，還是地理空間分析的有力工具，在科學(xué)與工程領(lǐng)域應(yīng)用廣泛。針對傳統(tǒng)歐氏距離條件下Voronoi圖生長元權(quán)值大小等同、生長元與Voronoi圖數(shù)據(jù)結(jié)構(gòu)一對一關(guān)系的局限性，該文以高斯分布的統(tǒng)計距離為切入點(diǎn)，利用馬氏距離作為Voronoi圖生成距離測度，提出一種新的Voronoi圖，即多高斯Voronoi圖(MGVD)。MGVD不但囊括了歐氏距離作用下產(chǎn)生的普通Voronoi圖與加權(quán)Voronoi圖，而且將生長元與Voronoi圖數(shù)據(jù)結(jié)構(gòu)的一對一關(guān)系拓展為空間的一對多關(guān)系，表現(xiàn)出單個空間生長元的多個Voronoi圖存在。最后，通過模擬實(shí)驗(yàn)驗(yàn)證了該方法的可行性。

歐氏距離;馬氏距離;多高斯；Voronoi圖；一對多關(guān)系

0 引言

Voronoi數(shù)據(jù)結(jié)構(gòu)是一種存在于自然界的宏觀和微觀實(shí)體間以距離函數(shù)相互作用的普遍結(jié)構(gòu)，在地理信息科學(xué)、計算機(jī)圖形學(xué)、人工智能、生態(tài)學(xué)等領(lǐng)域具有廣泛應(yīng)用[1]。國外相關(guān)研究包括Aurenhammer 對Voronoi圖的基本幾何數(shù)據(jù)結(jié)構(gòu)的研究[2]；DONG、Aurenhammer等對空間點(diǎn)、線和面要素的加權(quán)Voronoi圖算法進(jìn)行的研究[3,4]；Du等對質(zhì)心Voronoi圖的研究[5,6]；Boissonnat等采用一種布雷格曼增益(Bregman divergence)的距離函數(shù)形式生成Voronoi圖[7]；Balzer等構(gòu)建的層次Voronoi樹結(jié)構(gòu)圖[8]等。國內(nèi)主要有陳軍等對Voronoi動態(tài)空間數(shù)據(jù)模型的研究，并提出了基于Voronoi圖的k階空間鄰近關(guān)系、基于Voronoi空間拓?fù)潢P(guān)系的九交模型、球面Voronoi圖的生成算法研究[9-12]；文獻(xiàn)[13]基于Voronoi圖的GIS空間關(guān)系計算研究；文獻(xiàn)[14]利用線性四叉樹結(jié)構(gòu)實(shí)現(xiàn)了柵格數(shù)據(jù)下Voronoi圖的反向膨脹生成方法;文獻(xiàn)[15]通過掃描線算法構(gòu)建出Voronoi圖;以及文獻(xiàn)[16]由水流擴(kuò)展思想生成網(wǎng)絡(luò)Voronoi圖等。

上述方法對Voronoi的發(fā)展起到了積極的推動作用，然而在Voronoi圖勢力范圍的界定上還局限于歐氏距離或歐氏加權(quán)距離。鑒于歐氏距離對空間不確定性表達(dá)的局限性：首先，就數(shù)據(jù)本身的不確定性而言，歐氏距離未顧及空間數(shù)據(jù)的自相關(guān)性；其次，該距離條件下生長元所產(chǎn)生的Voronoi區(qū)域僅存在生長元作用的一定鄰域范圍內(nèi)，數(shù)據(jù)結(jié)構(gòu)表現(xiàn)為生長元與Voronoi圖的一對一關(guān)系，無法滿足由于空間分布結(jié)構(gòu)而產(chǎn)生的跨越鄰近Voronoi圖而產(chǎn)生的空間競爭力模型，如：空間中的購物廣場，鑒于其知名度所產(chǎn)生的“引力”不僅對周圍鄰近對象存在影響力，而且對鄰域外的空間對象也具有一定的吸引力，在Voronoi數(shù)據(jù)結(jié)構(gòu)上表現(xiàn)為生長元Voronoi圖空間分布的離散性，呈現(xiàn)出生長元與其Voronoi圖之間的一對多關(guān)系?；诖耍疚奶岢隽艘环N新的Voronoi圖——多高斯Voronoi 圖(Multi-Gaussian Voronoi Diagram，MGVD)，以馬氏距離為切入點(diǎn)探究Voronoi圖的空間結(jié)構(gòu)。

1 不確定性估計

客觀世界是一個充斥著偶然性的紛亂世界，空間實(shí)體具有復(fù)雜性和可變性。觀測數(shù)據(jù)遠(yuǎn)少于客觀總體數(shù)據(jù)，數(shù)據(jù)的期望值通常由觀測數(shù)據(jù)近似,屬性的感知除實(shí)體本身外，更多是基于空間實(shí)體間的鄰接關(guān)系[17]。如數(shù)據(jù)不確定性中的空間位置不確定是指空間實(shí)體的位置與其實(shí)際位置之間存在不一致性，通常表現(xiàn)為以統(tǒng)計均值作為無偏估計、以分布方差為鄰域來度量其空間的分布形態(tài)；然而，歐氏距離表達(dá)的是一種確定性距離，此項(xiàng)則是歐氏距離所不具備的。在不確定性研究中，高斯分布是統(tǒng)計中最重要的概念，是推論統(tǒng)計的基礎(chǔ)。空間數(shù)據(jù)點(diǎn)的分布很大程度上服從高斯分布。當(dāng)對未知隨機(jī)過程的概率分布建模時，其確定方式多是根據(jù)中心極限定理，在多次采樣的樣本空間中，將樣本頻率作為數(shù)據(jù)整體均值的無偏估計,樣本方差視作整體的無偏方差，表達(dá)式如式(1)，示意圖如圖1。

f(x)=(2π)-p/2|∑|-1/2exp{(x-μ)T∑-1(x-μ)}

(1)

圖1 二元樣本統(tǒng)計量分布Fig.1 Bi-variable statistics distribution

在時空尺度作用下，空間數(shù)據(jù)的不確定性通常是將當(dāng)前尺度下獲得的數(shù)據(jù)作為一種無偏估計值進(jìn)行計算，如圖2所示的單高斯分布。相比之下，歐氏距離局限性主要表現(xiàn)為：首先，它與指標(biāo)的量綱息息相關(guān)，而高斯分布中的馬氏距離可消除量綱；其次，歐氏距離未考慮指標(biāo)間的自相關(guān)性。此外，從統(tǒng)計的角度，歐氏距離的使用要求一個向量的n個分量不相關(guān)且具有相同的方差，換言之，歐氏距離適用的前提條件是各坐標(biāo)對歐氏距離的貢獻(xiàn)相同，也就是權(quán)值相等且變差大小相同，在此條件下歐氏距離才適用空間區(qū)域的界定表達(dá)，否則易得出對真實(shí)地理空間的曲解，甚至錯誤性結(jié)論[18]。

圖2 一元樣本統(tǒng)計量分布Fig.2 Sample statistics distribution of one-variable

2 多高斯Voronoi圖

2.1 普通Voronoi圖

如果存在空間點(diǎn)集P= {x1，x2，...，xn}?R2，(2

V(xi)={p|d(p，xi)≤d(p，xj)，j≠i，i，j∈N*}

(2)

多個生長元生成的普通Voronoi圖形式化表達(dá)如式(3)所示，其示例圖如圖3a所示；當(dāng)距離函數(shù)變?yōu)榧訖?quán)距離d(p，xi)-wi時，則產(chǎn)生加權(quán)Voronoi圖(WeightedVoronoiDiagram，WVD)(圖3b)[8,19]。

V= {V(x1),…,V(xn)}

(3)

圖3 歐氏距離界定下的Voronoi圖Fig.3 Voronoi diagram produced by Euclidean distances

2.2 馬氏距離

歐氏距離對統(tǒng)計不適用性的具體表現(xiàn)為:當(dāng)坐標(biāo)表示隨機(jī)波動的測量值時，需對可變性大的坐標(biāo)賦予較大權(quán)值、對微小變化的坐標(biāo)賦予較小權(quán)值，此時需要一個能夠?qū)嚯x進(jìn)行不同測度表達(dá)的量值。因此，從變差及相關(guān)性角度，要求使用一種能夠消除量綱、涵蓋并拓展歐氏距離作用的馬氏距離，描述如下：

(4)

從圖4可以看出歐氏距離是協(xié)方差為單位矩陣的馬氏距離，即當(dāng)馬氏距離的協(xié)方差陣為單位陣時，馬氏距離與歐氏距離是等價的。

圖4 馬氏距離Fig.4 Mahalanobis distance

(5)

定義 多高斯Voronoi圖:

若存在空間點(diǎn)集P= {x1，x2,…，xn}?R2，(2

MGV(xi)={p|dm(p，xi)≤dm(p，xj)，j≠i，i，j∈N*}

(6)

則多高斯Voronoi圖(MGVD)的形式化表達(dá)如式(7)，圖形可視化表達(dá)如圖5所示。

MGV= {MGV(x1),…,MGV(xn)}

(7)

圖5 馬氏距離界定下的多高斯Voronoi圖Fig.5 MGVD generated by Mahalanobis distance

3 算例與分析

該實(shí)驗(yàn)采用MATLAB 6.5模擬的空間分布數(shù)據(jù)為實(shí)驗(yàn)算例，研究了空間中存在多種高斯分布的生長元Voronoi圖表現(xiàn)形式，如馬氏距離中協(xié)方差正相關(guān)性相同、大小相等條件下的多高斯Voronoi圖存在形式，即表現(xiàn)為普通Voronoi圖；協(xié)方差正相關(guān)性相同、大小不等條件下多高斯Voronoi圖存在形式，即表現(xiàn)為加權(quán)Voronoi圖；協(xié)方差正相關(guān)、負(fù)相關(guān)性并存、大小不相等條件下多高斯Voronoi圖的存在形式，即表現(xiàn)為一種跨域性、生長元與Voronoi圖表現(xiàn)為一對多關(guān)系的空間結(jié)構(gòu)。

圖6a對應(yīng)為式(8)、式(9)實(shí)驗(yàn)?zāi)M生成的距離協(xié)方差正相關(guān)、數(shù)值大小相等條件下的多高斯Voronoi圖表達(dá)，即普通Voronoi圖。

(8)

(9)

圖6b對應(yīng)為式(10)、式(11)實(shí)驗(yàn)?zāi)M生成的距離協(xié)方差正相關(guān)、數(shù)值大小不等條件下多高斯Voronoi圖存在形式，即表現(xiàn)為一種加權(quán)Voronoi圖。

(10)

(11)

圖6c對應(yīng)為式(12)、式(13)實(shí)驗(yàn)?zāi)M生成的距離協(xié)方差正相關(guān)、負(fù)相關(guān)并存，且協(xié)方差數(shù)值大小不等條件下多高斯Voronoi圖的存在形式，即表型出Voronoi圖在空間分布中的一種離散型態(tài)，體現(xiàn)出Voronoi圖的跨域性。

(12)

(13)

圖6 協(xié)方差矩陣不同的多高斯Voronoi圖Fig.6 MGVD on different covariance matrices

上述實(shí)驗(yàn)表明，馬氏距離生成的多高斯Voronoi圖不僅可以利用距離協(xié)方差矩陣綜合普通Voronoi圖、加權(quán)Voronoi圖的歐氏距離生成方式，而且實(shí)驗(yàn)生成的多高斯Voronoi圖能夠產(chǎn)生具有跨域延展性的離散Voronoi圖。顧及數(shù)據(jù)本身的相關(guān)性，由圖6可知，由馬氏距離產(chǎn)生的Voronoi圖空間結(jié)構(gòu)可表現(xiàn)為普通Voronoi圖、加權(quán)Voronoi圖及跨域性Voronoi圖?？缬蛐訴oronoi圖延展了傳統(tǒng)Voronoi圖的概念，如圖6c中由左上方生長元所產(chǎn)生的兩個Voronoi圖Ⅰ跨越Voronoi圖Ⅱ，形成空間離散分布形態(tài)存在的Voronoi圖Ⅰ，表明其影響范圍不僅僅局限于生長元自身的一定空間鄰域內(nèi)，而且可拓展至其Voronoi圖以外的其他生長元的Voronoi鄰域內(nèi)，表現(xiàn)出Voronoi圖切入到其他生長元Voronoi圖之間形成競爭關(guān)系，擴(kuò)展了傳統(tǒng)Voronoi數(shù)據(jù)結(jié)構(gòu)與生長元的一對一關(guān)系，實(shí)現(xiàn)了空間生長元與Voronoi圖之間數(shù)據(jù)結(jié)構(gòu)一對多關(guān)系的表達(dá)。

4 結(jié)論

本文分析了普通Voronoi圖與加權(quán)Voronoi圖的生成距離及空間結(jié)構(gòu)中數(shù)據(jù)結(jié)構(gòu)關(guān)系的局限性，提出一種基于馬氏距離的多高斯Voronoi圖生成方法。從統(tǒng)計角度，馬氏距離不僅包含了普通Voronoi圖與加權(quán)Voronoi圖生成的歐氏距離，而且拓展了Voronoi圖的空間結(jié)構(gòu)，形成了跨域性的Voronoi圖，彌補(bǔ)了普通Voronoi圖及加權(quán)Voronoi圖的空間不可分離性，實(shí)現(xiàn)了生長元Voronoi圖的跨域性，由傳統(tǒng)的生長元與Voronoi圖一對一的數(shù)據(jù)結(jié)構(gòu)關(guān)系拓展為一對多的數(shù)據(jù)結(jié)構(gòu)關(guān)系。針對空間中存在的多種分布結(jié)構(gòu)，發(fā)現(xiàn)Voronoi圖在空間分布中存在的其他形態(tài)以及對Voronoi數(shù)據(jù)結(jié)構(gòu)多對多關(guān)系的研究是今后研究中需要進(jìn)一步探討和解決的問題。

[1] OKABE A,BOOTS B,SUGIHARA K,et al.Spatial Tessellation:Concepts and Applications of Voronoi Diagrams[M].Chichester:John Wiley,2000.6-11.

[2] AURENHAMMER F.Voronoi diagrams——A survey of a fundamental geometric data structure[J].ACM Computing Surveys,1991,23(3):345-405.

[3] DONG P.Generating and updating multiplicatively weighted Voronoi diagrams for point,line and polygon features in GIS[J].Computers & Geosciences,2008,34(4):411-421.

[4] AURENHAMMER F,EDELSBRUNNER H.An optimal algorithm for constructing the weighted Voronoi diagram in the plane[J].Pattern Recognition,1984,17(2):251-257.

[5] DU Q,FABER V,GUNZBURGER M.Centroidal Voronoi tessellations:Applications and algorithms[J].SIAM Review,1999,41(4):637-676.

[6] JU L L,DU Q,GUNZBURGER M.Probabilistic methods for centroidal Voronoi tessellations and their parallel implementations[J].Parallel Computing,2002,28(10):1477-1500.

[7] BOISSONNAT J D,NIELSEN F,NOCK R.Bregman Voronoi diagrams[J].Discrete & Computational Geometry,2010,44(2):281-307.

[8] BALZER M,DEUSSEN O.Voronoi treemaps[A].IEEE Symposium on Information Visualization 2005:INFOVIS[C].New York:IEEE,2005.49-56.

[9] CHEN J,LI C M,LI Z L,et al.A Voronoi-based 9-intersection model for spatial relations[J].International Journal of Geographical Information Science,2001,15(3):201-220.

[10] 陳軍.Voronoi動態(tài)空間數(shù)據(jù)模型[M].北京:測繪出版社,2002.20-32.

[11] CHEN J,ZHAO X S,LI Z L.An algorithm for the generation of Voronoi diagrams on the sphere based on QTM[J].Photogrammetric Engineering and Remote Sensing,2003,69(1):79-89.

[12] CHEN J,ZHAO R L,LI Z L.Voronoi-based k-order neighbour relations for spatial analysis[J].ISPRS Journal of Photogrammetry and Remote Sensing,2004,59(1-2):60-72.

[13] 趙仁亮.基于Voronoi圖的空間關(guān)系計算研究[D].湖南:中南大學(xué),2002.30-38.

[14] 李佳田,陳軍,趙仁亮,等.基于線性四叉樹結(jié)構(gòu)的Voronoi圖反向膨脹生成方法[J].測繪學(xué)報,2008,37(2):236-242.

[15] HU S M,JIN L,DONGUK K,et al.A sweepline algorithm for Euclidean Voronoi diagram of circles[J].Computer Aided Design,2002,38(3):260-272.

[16] 艾廷華,禹文豪.水流擴(kuò)展思想的網(wǎng)絡(luò)空間Voronoi圖生成[J].測繪學(xué)報,2013,42(5):760-776.

[17] SHI W Z.Principles of Modeling Uncertainties in Spatial Data and Spatial Analyses[M].CRC Press,2009.8-12.

[18] MAHALANOBIS P C.On the generalized distance in statistics[J].Proceedings of the National Institute of Sciences (Calcutta),1936,2:49-55.

[19] 吳立新.地理信息系統(tǒng)原理與算法[M].北京:科學(xué)出版社,2003.283-295.

A Generating Method of Multi-Gaussian Voronoi Diagram Based on Mahalanobis Distance

KANG Shun,XIANG Shi-yao

(CollegeofGeoscienceandSurveyingEngineering,ChinaUniversityofMiningandTechnology(Beijing),Beijing100083,China)

Voronoi diagram not only is regarded as one of the most popular data structure in computational geometry,but also an advantageous tool in geospatial analysis,and provided with extensive applications in all fields of science and engineer.In terms of the equal weight values being possessed by each generating cell of Voronoi diagram,and the one-to-one relationship data structure limitation between generating cell and its corresponding Voronoi diagram produced by traditional Euclidean distance,from viewpoint of the statistical distance of Gaussian distribution,a new Voronoi diagram,namely Multi-Gaussian Voronoi Diagram,abbr.MGVD,is proposed in this paper based on Mahalanobis distance,which is utilized as the distance measure.The MGVD includes the generalization method of ordinary Voronoi and weighted Voronoi diagram based on Euclidean distance.Moreover,the MGVD extends the data structure between generating cell and its corresponding Voronoi diagram from one-to-one relationship in space to that one-to-many,which makes the spatial existence of multi-Voronoi diagram which belongs to a single generating cell.Last but not least,the method was proved to be feasible by simulation experiments.

Euclidean distance;Mahalanobis distance;multi-Gaussian;Voronoi diagram;one-to-many relationship

2015-12-10；

2016-01-24

中央高校基本科研業(yè)務(wù)費(fèi)專項(xiàng)資金項(xiàng)目(2010YD06)

康順(1987- )，男，博士研究生，主要研究方向?yàn)閂oronoi建模與計算。E-mail：421347922@qq.com

10.3969/j.issn.1672-0504.2016.03.010

P208

A

1672-0504(2016)03-0049-04