一種基于模糊相似度的球面格網幾何變形評價指標

張 斌，苑 爭 一，趙 學 勝，張 新 建

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

?

一種基于模糊相似度的球面格網幾何變形評價指標

張 斌，苑 爭 一，趙 學 勝，張 新 建

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

全球離散格網模型的不確定性，包括格網單元的幾何變形及空間分布問題，是制約其廣泛應用的主要因素之一。該文從三角形相似的角度出發，構造了球面三角格網的模糊相似度評價指標，以此對球面四元三角格網模型的幾何變形特征及其收斂性進行分析評價，并給出了格網單元變形在八面體單元和全球區域的位置分布規律。最后，與傳統評價指標進行對比實驗，結果表明：該指標不但能夠反映剖分模型的幾何變形分布，而且還具有兩大優勢：1)能夠同時反映剖分單元的幾何形狀和面積變形，可作為格網形狀和面積變形的綜合評價指標；2)該指標是相對于不同遞歸層次上理想剖分單元的絕對變形量，相比其他統計量，更便于表達不同層次間的格網幾何變形。

全球離散格網；球面四元三角網；格網幾何變形；模糊相似度

0 引言

近年來，全球離散格網(Discrete Global Grid,DGG)模型的提出，為構建大范圍、多分辨率、全球統一無縫的空間定位基礎框架提供了新思路[1,2]。盡管國內外學者在全球離散格網的剖分類型、索引結構及建模方法等方面取得了豐富成果，但是由于格網單元的不均勻性及其變形分布的不規則性，很難進行變形誤差的傳播和控制，使其在不同領域的應用受到極大的限制。

目前，針對球面格網單元幾何變形評價和分析的研究成果，大致可分為三類：第一類是對格網評價標準的研究。這些標準最早由Goodchild于1992年提出，被稱為“Goodchild標準”[3]，后經不斷補充和修改，Kimerling等[4]把它確定為研究全球格網劃分所遵循的一般標準。該標準共有14條，可以作為對全球離散格網系統的理想描述。第二類是對格網評價指標的研究，基于“Goodchild標準”構造可以量化的格網評價指標，進而通過分析各指標值來尋找格網模型的幾何變形特征。例如，Heikes等[5,6]在應用全球離散格網進行大氣建模的過程中，構造了“Cell Wall Midpoint Ratio”指標；Gregory等[7]基于“參考點到鄰近格網是等距的”及“任何兩個鄰近格網的邊是連接兩個格網中心的大圓弧平分線”這兩條標準，構造了“Coefficient of Variation(CV)”和“Cell Wall Midpoint Ratio”兩個指標，并應用這些指標對比分析了幾種剖分模型的變形特征。第三類是基于格網結點分布的研究，從格網結點的分布特性出發，對比分析不同剖分模型的均勻性特征。例如，明濤等[8]通過計算每個格網結點到鄰近結點的距離、結點與兩鄰近結點間連線的夾角，作為格網結點空間分布均勻性的評價標準；周良辰等[9]通過計算球面格網總的電勢能來評價格網結點分布的均勻性。

本質上看，部分理想格網的標準是相互矛盾的，任何一個全球離散格網系統在數學上不可能同時滿足上述全部指標，一個比較優秀的格網系統應該根據具體的應用條件選擇一個合理的平衡。然而目前的研究僅限于探討不同球面格網幾何特征(長度、面積、角度等)的總體變化及收斂性特征[10-17]，缺乏對不同位置上的變形分布規律的研究[18,19]；另外，對于不同剖分層次上的理想剖分單元，一些傳統的格網變形評價指標(如密實度)的取值是變化的，不適合層次間格網幾何變形的比較分析。為此，本文在相似三角形原理的基礎上，把平面三角形模糊相似度擴展到球面上，構造了一個“球面格網模糊相似度”評價指標，并通過計算實際剖分單元相對于理想剖分單元的模糊相似度，來評定格網的形狀和面積綜合變形特征，進而分析其在球面上的位置分布規律，為構建全球離散格網變形的評價體系及數據質量控制提供參考。

1 球面三角形的模糊相似度

1.1 模糊相似度基本原理及其改進方法

根據三角形相似原理構造平面三角形相似模糊度[20]，用于判定兩個三角形是否相似，基本原理為：如果一個三角形的一個內角為a，則在另一個三角形的對應角x和該角的差異性應遵循以下正態分布：

d(x)=e-k(x-a)2

(1)

大于0的系數k可由下式計算：

(2)

式中:a*Pa為正態分布的3σ點，這里令Pa為50%。這樣對角度的相似度可由下式得到：

Ia=cosn(ks(1-d(x)))

(3)

基于余弦曲線的特征，可定義n=3，ks=π/2。對于一對三角形，可先利用式(3)分別計算3個內角的相似度，而后利用式(4)計算整個三角形的相似度。

It=k1Ia+k2Ib+k3Ic

(4)

通常取k1=k2=k3=1/3，即取3個內角相似度的算術平均值作為整個三角形的模糊相似度，但這容易受極大值的影響，使得所求三角形的模糊相似度偏大。而幾何平均值受極大值的影響小于算術平均值，且幾何平均值更適用于求比率(大于0小于1)的均值,因此，采用幾何平均值代替上述算術平均值，作為整個三角形的模糊相似度，計算公式如下：

(5)

1.2 模糊相似度在球面三角形的擴展

把上述平面三角形的模糊相似度擴展到球面上。 從球面幾何可知，沒有一種剖分方法能使球面格網在每個層次上獲得像平面柵格那樣完全相同的幾何特征(如：面積、長度、角度)，只能達到近似相等[13]。對于球面三角剖分，理想的剖分單元應當滿足面積相等、幾何形狀相同(即球面正三角形)。由球面三角形面積計算式(8)可知，球面三角形的內角和不是定值，因此需要計算每一層的理想剖分單元的內角，進而計算每一個剖分單元的內角，并帶入模糊相似度計算公式求解每個球面三角形單元的模糊相似度。具體過程如下：

(1)用球面面積除以每一層剖分的格網單元的個數，得到該層理想剖分單元的面積，進而根據球面三角形面積和式(8)反算出理想剖分單元的內角，經計算可得理想剖分單元的面積和內角的計算如式(6)、式(7)所示，其中n為剖分層次，R為球半徑。

Sideal=4×PI×R2/(8×4n)

(6)

(7)

S=R2×(A+B+C-π)

(8)

(2)設A、B、C為球面上任意3點，X1、X2、X3分別為A、B、C 3點的向量(笛卡爾坐標系)，則球面三角形ABC的內角ai為：

(9)

(3)將球面三角形單元的內角ai及理想剖分單元的內角Aideal帶入式(1)—式(3)，分別求得三角形單元3個內角的模糊相似度Ia、Ib、Ic，由式(5)求出該球面三角形的模糊相似度。式(8)為球面三角形的面積公式，其中E=A+B+C-π為球面三角形角超，A、B、C為球面三角形的3個內角。角超反映了球面幾何與平面歐式幾何的差異，在平面幾何中三角形內角和等于π，角超等于0，三角形面積與角超沒有關系；在球面幾何中，三角形的內角和大于π，角超大于0，三角形的面積隨角超的變化而變化。

在球面幾何中，有“對應角相等的兩個球面三角形全等”的判定定理，即模糊相似度為1的兩個球面三角形，其對應角和面積均相等，兩個三角形全等。因此將平面三角形的模糊相似度擴展到球面上后，該指標既能反映出剖分單元幾何形狀的變形，又能反映出面積的變形。面積形狀均無變形的剖分單元，模糊相似為1，其他情況下都小于1。

2 實驗設計及結果分析

2.1 實驗設計

本實驗以基于正八面體的QTM剖分為例，采用面積近似的“經緯度平分法”剖分，直接采用經緯度平均值作為新的結點。以正八面體的一個原始球面三角形ABC為例，A與極點重合，其他兩個頂點位于赤道上，具體剖分過程如下：1)將正八面體每個原始球面三角形的兩個大圓弧(AB和AC)剖分成2n個相等的部分，分別得到2n-1個新點{p1,p2,…,p2n-1}和{q1,q2,…,q2n-1};2)沿緯線分別連接pi和qi，然后對緯線進行i等分，得到2i-1個新點，其中i∈[1,2n](當i=2n+1時，弧piqi對應于BC)；3)用大圓弧線連接鄰近3個球面點，得到第n層的球面剖分。剖分效果如圖1所示[11]。選取球面格網模糊相似度(similarity)及其傳統的密實度(compactness)和格網單元面積，作為剖分單元形狀和面積的變形指標，對比分析各指標隨剖分層次的變化及其分布特征。

圖1 O-QTM剖分模型(第5層)

Fig.1O-QTMsubdivisionmodel(infifthlevel)

傳統密實度是通過表面積和周長的比值來測定。為了便于比較不同剖分模型、不同剖分層次該指標的變化，Kimerling等[12]對上述指標進行了標準化處理，即選取與格網等面積、以極點為中心的球形區域的密實度作為比較對象，用格網單元的密實度去除球形區域的密實度，得到區域標準化密實度(ZSC)，計算公式如下：

(10)

式中:cell area為格網單元的面積，cell perimeter為格網單元的周長，zoon area為與格網等面積、以極點為中心的球面區域的面積，zoon perimeter為球形區域的周長，r為球半徑。

2.2 結果分析

剖分單元面積、單元密實度、模糊相似度的最大、最小值比(Max/Min)及標準差(SD)隨剖分層次的變化見表1所示。

表1 各指標在不同剖分層次的取值

Table 1 Index values in different levels

QTM層次三角形個數面積Max/Min面積SD密實度Max/Min密實度SD相似度Max/Min相似度SD141．622206370．500000001．05216428090．0203077379 8．7393900．4407155162161．796340770．285318471．05806972460．014535173988．4636730．3715202973641．821284830．228418601．05847688950．0141140508185．1146200．36623010742561．826690240．208605351．06715075400．0148671098225．1008160．357470994510241．827995800．201911231．07695392070．0152985092367．7972530．353482848640961．828319470．199775941．08382387130．0154694815595．2621610．3520762147163841．828400210．199125401．08850589920．0155284241836．7910220．3516343468655361．828420650．198933551．09159951160．01554727011053．9904630．35150293392621441．828430660．198877681．09361314820．01555301631227．2979510．3514650041010485761．828516450．198850741．09492835000．01555471871354．6346070．351454267

2.2.1 剖分模型收斂性分析 根據表1數據繪制隨剖分層次增加的格網變形趨勢圖(圖2-圖4)。從圖2和圖3可以看出，隨著剖分層次的增加，格網面積及密實度的最大、最小值之比逐漸增大并趨于穩定；指標的標準差逐漸減小并趨于穩定。從圖4可以看出，盡管模糊相似度的最大、最小值比的收斂性較差，但該指標的標準差收斂性較好。這表明該指標對極值較為敏感，但隨著剖分層次的增加，格網間的差別逐漸減小，模型的穩定性良好，格網變形是收斂的。

圖2 格網面積最大最小值比、標準差隨剖分層次的變化

Fig.2 Variations of Area_Max/Min and Area_SD in different levels

圖3 格網密實度最大最小值比、標準差隨剖分層次的變化

Fig.3 Variations of Compactness_Max/Min and Compactness_SD in different levels

圖4 格網相似度最大最小值比、標準差隨剖分層次的變化

Fig.4 Variations of Similarity_Max/Min and Similarity_SD in different levels

2.2.2 格網變形在八面體上的位置分布 以八面體的一個單元面為例，將球面剖分5層，計算各剖分單元的以上3種指標值，并借助可視化方法直觀地展現在球面上，進而分析球面上不同位置的變形分布規律。圖5a顯示了剖分單元面積變形率(相對于理想剖分單元)在球面上的分布規律，深色區域的變形率較小，主要分布在八面體的中間區域，呈帶狀分布；往極點和赤道方向逐漸變大。圖5b顯示了格網單元密實度在球面上的分布規律，其中深色區域的密實度較小。從圖中可以看出八面體中心區域的密實度較大，即格網形狀較規則，接近于理想剖分；從中心向八面體的3個頂點逐漸減小，變形逐漸增大。圖5c顯示了格網單元模糊相似度在球面上的變化規律，其中深色區域的模糊相似度較小。圖中八面體中心區域模糊相似度最大，即最接近理想剖分；從中心向八面體3個頂點方向逐漸減小，變形增大。

圖5 三種變形指標在八面體上的位置分布

Fig.5 Location distributions of three deformation indices on the octahedral

2.2.3 特定格網單元評價指標的取值及其變化分析 為了體現模糊相似度在評價格網變形方面的綜合性特征，抽取特定的格網單元，定量分析三種指標(面積、密實度、模糊相似度)的差別。如圖6所示，以八面體的一個面為例，剖分4層，得到256個球面三角形，取中央經線上三角形單元，分別計算上述各格網單元的三種指標值。為了便于對比分析，將各指標分別進行歸一化處理，計算結果見表2。根據表2中的數據繪制指標變化曲線(圖7)。由圖7可知：1)從赤道到兩極，沿中央經線，隨著緯度的增加，密實度和模糊相似度指標都逐漸減小，極點附近區域震蕩現象明顯；2)格網的面積變形先隨緯度增加減小，后又增加，極點附近區域震蕩現象明顯；3)模糊相似度指標同密實度指標的變化趨勢一致，其變化曲線介于密實度和面積變形指標之間。

3 結語

本文從三角形相似的角度出發，構造了球面三角形模糊相似度評價指標，用于評價不同剖分層次上的實際剖分單元與理想剖分單元間的差異，并與傳統的密實度和面積變形指標在O-QTM剖分的變形收斂特性及空間分布特性進行了對比。實驗及分析表明：1)球面模糊相似度指標同其他指標一樣，能夠反映剖分模型的收斂規律，其分布特征同密實度指標相似，能夠很好地反映格網幾何形狀變形的分布規律；2)由于球面三角形的面積受其內角和的影響，該指標還能夠間接地反映出格網的面積變形，可作為衡量格網形狀和面積變形的綜合評價指標；3)該指標是相對于理想剖分單元的絕對變形量，相比于其他統計量，更便于表達不同剖分層次間格網的幾何變形。因此，無論是在評價指標的綜合性，還是層次間的可比較性方面，球面模糊相似度指標都要優于傳統的密實度等變形評價指標。

圖6 特定測試單元

Fig.6 Specific test grids

圖7 特定格網上的各個指標變化曲線

Fig.7 The changing curve of each index on specific grids

表2 中央經線(45°)上的格網指標值

Table 2 Index values of grids on the central meridian

行號三角形編號中心緯度模糊相似度密實度面積變形原始值歸一化原始值歸一化原始值歸一化0087．1875N0．00444240600．73486773 00．21333999 0．4862710151181．5625N0．9985309480．9985352 0．7778649810．99708482 0．43612411812775．9375N0．1188280350．1148972870．7564241190．4998819310．0881202410．19752057531170．3125N0．7927684780．7918523340．77284250．8806159950．3214678230．73560835442164．6875N0．2936109270．2904620010．7632417170．657978620．12053291 0．27226255852959．0625N0．7108976650．7096153040．7714570280．8484875990．2443629720．5578084564353．4375N0．5248413560．5227267470．7682381320．7738429880．1029090980．23162293575547．8125N0．7763504740．775360890．7724861020．8723513170．1747422010．39726645687342．1875N0．7864623770．7855180250．7725876710．8747066490．0594411420．13138801698936．5625N0．8963249470．8958720220．7745633670．9205220350．1006596370．2264357911011130．9375N0．9636373340．9634855030．7760663470．9553753980．00246330801113125．3125N0．9833417140．9832780230．7767487520．9712000260．0193761540．0390001711215719．6875N0．9999122090．999922640．7779246350．9984681740．0788217730．1760787771318114．0625N0．99998922510．77799069210．0692301470．153960969142118．4375N0．9917315280．9917053660．7769970910．9769589050．1665607810．378400513152392．8125N0．9997198880．9906289560．7769326480．9754644990．1642811810．373143871

[1] DUTTON G.A hierarchical coordinate system for geoprocessing and cartography[A].Lecture Notes in Earth Sciences[C].Berlin Springer-Verlag,1999.

[2] LUKATELA H.Ellipsoidal area computations of large terrestrial objects[A].The First International Conference on Discrete Grids′2000[C].2000.

[3] GOODCHILD M F.Criteria for evaluation of global grid models for environmental monitoring and analysis[R].NCGIA Technical Report,1994.9-47.

[4] KIMERLING J A,SAHR K,WHITE D,et al.Comparing geometrical properties of global grids[J].Cartography and Geographic Information Science,1999,26(4):271-288.

[5] HEIKES R,RANDALL D A.Numerical integration of the shallow-water equations on a twisted icosahedral grid.Part II.A detailed description of the grid and an analysis of numerical accuracy[J].Monthly Weather Review,1995,123(6):1881-1887.

[6] HEIKES R,RANDALL D A.Numerical integration of the shallow-water equations on a twisted icosahedral grid.Part I:Basic design and results of tests[J].Monthly Weather Review,1995,123(6):1862-1880.

[7] GREGORY M J,KIMERLING A J,WHITE D,et al.A comparison of intercell metrics on discrete global grid systems[J].Computers,Environment and Urban Systems,2008,32(3):188-203.

[8] 明濤,莊大方,袁文,等.幾種離散格網模型的幾何穩定性分析[J].地球信息科學,2007,9(4):40-43.

[9] ZHOU L,LV G.Distortion distribution and convergence analysis of spherical diamond discrete grids[J].ISPRS-International Archives of the Photogrammetry,Remote Sensing and Spatial Information Sciences,2013,1(2):89-93.

[10] MING T,ZHANG D,YUAN W.The study on geometrical distortion of triangular partitions in discrete global grid[A].Education Technology and Training,2008 and 2008 International Workshop on Geoscience and Remote Sensing[C].2008,2:175-178.

[11] 趙學勝,孫文彬,陳軍.基于QTM的全球離散格網變形分布及收斂分析[J].中國礦業大學學報,2005,34(4):438-442.

[12] KIMERLING J A,SAHR K,WHITE D,et al.Comparing geometrical properties of global grids[J].Cartography and Geographic Information Science,1999,26(4):271-288.

[13] 賁進,童曉沖,張永生,等.球面離散網格在橢球面上的擴展及變形分析[J].測繪科學,2006,31(4):25-27,59.

[14] 孫文彬,趙學勝,高彥麗,等.球面似均勻格網的剖分方法及特征分析[J].地理與地理信息科學,2009,25(1):53-56.

[15] 白建軍,孫文彬,趙學勝.基于QTM的WGS84橢球面層次剖分及其特點分析[J].測繪學報,2011,40(2):243-248.

[16] 崔馬軍,趙學勝.球面退化四叉樹格網的剖分及變形分析[J].地理與地理信息科學,2008,23(6):23-25.

[17] WHITE D,KIMERLING A J,SAHR K,et al.Comparing area and shape distortion on polyhedral-based recursive partitions of the sphere[J].International Journal of Geographical Information Science,1998,12(8):805-827.

[18] 趙學勝,王磊,王洪斌,等.全球離散格網的建模方法及基本問題[J].地理與地理信息科學,2012,28(1):29-34.

[19] 趙學勝,侯妙樂,白建軍.全球離散格網的空間數字建模[M].北京：測繪出版社,2007.

[20] 李贛華,周東祥,董黎,等.基于Delaunay三角化的有效角點匹配算法[J].信號處理,2007,23(5):695-698.

An Geometry Deformation Evaluation Index of the Spherical Discrete Grid Based on the Fuzzy Similarity

ZHANG Bin,YUAN Zheng-yi,ZHAO Xue-sheng,ZHANG Xin-jian

(CollegeofGeoscienceandSurveyingEngineering,ChinaUniversityofMining&Technology(Beijing),Beijing100083,China)

The uncertainty problem of discrete global grid models,including geometry deformation and spatial distribution,has been one of the restricting factors in its broad applications.In this paper,a fuzzy similarity evaluation index which based on the principle of similar triangles is constructed,and the geometry deformation characteristics and the convergence property of QTM (Quaternary Triangular Mesh) grid are analyzed using the above index.Meanwhile,the location distribution rules of the grid deformation on the octahedral unit and sphere are also presented.Finally,the contrast experiment with the traditional evaluation index (such as the compactness index) is given.The results show that the index not only can reflect the geometry deformation distribution of subdivision models,but also has two advantages just as follows.Firstly,it can reflect both the shape and area deformation of subdivision units,so it can be used as a synthesized evaluable index for the grid′s shape and size.Secondly,the index is an absolute deformation relative to the ideal subdivision units in different recursion levels,and compared with other statistics,it is easier to express the grid geometry deformation in different levels.

discrete global grid system;QTM;geometry deformation of grid;fuzzy similarity

2015-04-20

國家自然科學基金項目(41171306、41171304)

張斌(1990-)，男，碩士研究生，主要研究方向為全球離散格網及三維可視化。E-mail：1289711551@qq.com

10.3969/j.issn.1672-0504.2015.05.005

P208

A

1672-0504(2015)05-0020-05