基于直接剖分的球面四邊形離散格網生成方法

陳永就，林 川

（1.廣東省國土資源測繪院，廣東 廣州510500）

基于直接剖分的球面四邊形離散格網生成方法

陳永就1，林 川1

（1.廣東省國土資源測繪院，廣東 廣州510500）

提出一種基于直接剖分的球面四邊形離散網格生成方法，將該方法生成的四邊形網格與基于QTM（四元三角網）擴展的四邊形網格的面積形變進行對比分析。根據實驗數據可知，基于QTM擴展的四邊形網格最大與最小面積比值隨著剖分層次的增加而增大，最后會收斂到2.1；基于直接剖分的球面四邊形離散網格最大與最小面積比值隨著剖分層次的增加而增大，且不收斂，但此網格在中間恒定、連續的大片區域，網格最大與最小面積比值隨著剖分層次的增加最終收斂到1.3。

球面離散網格 ；四邊形網格；直接剖分法；面積形變

全球離散網格模型是一種可以無限細分并且不會改變形狀的地球球面擬合網格，當其細分到一定分辨率時，可以對地球的表面進行模擬，它能有效避免傳統的經緯度網格在表達全球數據時產生的面積形變和斷裂等問題[1,2]。剖分單元作為全球離散網格的基本單元，是網格的重要研究對象。目前國內外學者對網格單元的研究主要集中在三角形、四邊形、六邊形等，不同多邊形網格具有各自的優點和缺點。Sadourny在1972年提出了四邊形球面網格，發現基于正六面體的剖分邊界誤差比較大。之后許多學者對該網格進行了改進，其中最具代表性的是Nairetal采用Galerkin方法在四邊形球面網格上使用淺水方程進行數值模擬，得到了非常理想的結果。三角形兩兩合并能很方便地得到四邊形[3]，目前對球面四邊形網格的研究大多是在三角網合并的基礎上進行的，例如趙學勝[4]等在QTM的基礎上，以上下2個三角形合并為一個四邊形，構建出全球離散格網層次模型。直接合并的方法生成的四邊形網格會繼承原三角網的幾何形變特性，本文擬通過直接剖分的方法產生球面四邊形，通過網格面積形變這一種重要的網格質量評價標準[5]對基于直接剖分產生的球面四邊形網格和基于QTM擴展的四邊形網格進行對比分析。

1 球面四邊形網格的構建

球面多邊形網格一般是在多面體剖分的基礎上建立的[6]，本文以正八面體剖分為例對兩種網格進行分析。球內接正八面體和球面相交的6個點是南北兩個極點和赤道上的4個點，它的12條邊線映射到球面上即構成了球面基礎網格，網格將球表面分成了8個相等的區域，以南北相鄰的2個三角面組成的區域為例進行分析，其他球面的情況類似。在確立基礎網格后便是對其采用一定的數學規則進行遞歸細分，不同的細分方法將產生不同的網格。

基于QTM擴展四邊形網格的剖分方法：取3條邊的中點（大圓弧的中點）兩兩相連，即將三角面剖分成4個小三角面。將球面兩點之間的最短距離作為剖分線，這條線等同于兩點間的大圓弧劣弧，用相同的方法進行細分直至所需的分辨率，最后將剖分所得的邊相鄰的南北兩個三角網格兩兩合并成四邊形網格[1]。

基于直接剖分的球面四邊形離散網格的剖分方法：取四邊形4條邊上的4個中點（大圓弧的中點），四邊形相對2條邊上的中點相連，在球面上取兩點間大圓弧的劣弧，即將初始的四邊形剖分成4個子四邊形，可以以相同的方法不斷細分。

2 網格的可視化效果

本文使用OSG(OpenSceneGraph)實現了兩種剖分方案下的球面四邊形網格的可視化（以1/4半球為例，其他球面的情況類似）。圖1顯示的是4次剖分后的QTM擴展四邊形網格，可以明顯看出該網格中間的網格面積較大；圖2顯示的是直接剖分方法生成的球面四邊形，由于四邊形的4個點并不在同一個平面上，因此OSG在顯示時是以三角網的形式。與基于QTM擴展四邊形網格相比，直接剖分法生成的四邊形網格更緊致，但是最大四邊形網格單元與最小四邊形網格單元面積相差非常大。

3 網格的面積形變

網格質量的評判標準之一是網格單元的近似均等性。由球面幾何空間的性質可知，不可能做到把球面分割成完全均勻相等的網格，因此所有的剖分方法目的是使網格單元能夠盡量均等。四邊形網格單元面積是指網格在球面上圍成的表面積，可以看成是由2個三角形組成。球面三角形的面積計算公式如下[7]：

其中，x1、 x2、 x3分別是三角形3個頂點的向量。

圖1 QTM擴展四邊網格

圖2 直接剖分法生成的四邊形網格

圖3 50%較大面積網格的分布情況（6層）

圖4 50%較大面積網格的分布情況（7層）

在對單位三角形一分為四時，QTM網格中間三角形的面積明顯比周邊三角形面積大，基于QTM擴展的四邊形網格會繼承QTM網格的形變規律。從直接剖分法生成的四邊形網格的可視化效果來看，網格的面積形變主要集中在邊緣部分，網格中間大片連續的區域較為均勻，這部分區域網格單元的面積較大。將各個剖分層次中的50%較大面積網格用顏色標出，可以看出這部分網格區域是連續的且范圍不會隨著剖分層次的增加而發生明顯改變。圖3、圖4分別顯示的是直接剖分法下6層剖分和7層剖分的網格，紅色標識的是網格總數中50%較大面積網格。

對直接剖分下網格總數中50%較大面積網格、整體網格和QTM擴展的四邊形網格進行對比，求出它們在各個剖分層次的最大與最小網格面積。研究區域中最大單元網格面積和最小單元網格面積的比值越小，說明網格大小越接近，網格越均勻。通過對網格最大與最小面積比值在各個剖分層次變化的統計分析，得到網格均勻性特征隨剖分層次增加的變化趨勢，若變化收斂，則網格均勻性特征穩定。表1顯示的是上述四邊形網格最大與最小面積比值在各個剖分層次的變化。

由上表數據可知，基于QTM擴展的四邊形網格最大與最小面積比值隨著剖分層次的增加而增大，最后會收斂到2.1。基于直接剖分的球面四邊形離散網格最大與最小面積比值隨著剖分層次的增加而增大，且不收斂。通過對單元網格面積的統計結果可得出，是由于剖分層次增加后網格邊緣四邊形面積驟減導致的。直接剖分下網格總數中50%較大面積網格的最大與最小面積比值隨著剖分層次的增加最終收斂到1.3。從全球網格分布來看，基于QTM擴展的四邊形網格面積形變要優于直接剖分法所得網格，從區域網格分布來看，直接剖分法所得網格在中間恒定、連續的大片區域上網格細分更加規整和均勻。

表1 網格最大與最小面積比值在各個剖分層次的變化

4 結 語

基于三角形擴展的四邊形網格會繼承三角形網格的形變特征，本文提出了一種基于直接剖分的球面四邊形離散網格生成方法與基于QTM擴展的四邊形網格相比，它在整體上均勻性較差，但在大范圍的局部區域上表現出更加規整和均勻的特性，滿足一般中小尺度模型的范圍要求。基于直接剖分的球面四邊形離散網格為構建局部高精度網格提出了新的參考，其在球面離散網格建模中的應用值得進一步研究。

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

[2] 李德仁，朱欣焰，龔健雅. 從數字地圖到空間信息格網[J].武漢大學學報：信息科學版， 2003,28(6):642-650

[3] Sahr K, White D, Kimeling A. Geodesic Discrete Global Grid Systems[J].Cartography and Geographic Information Science, 2003,30(2):121-134

[4] 趙學勝，白建軍. 基于菱形塊的全球離散格網層次建模[J].中國礦業大學學報，2007(3):397-401

[5] Goodchild M F. Criteria for Evaluation of Global Grid Models for Environmental Monitoring and Analysis[R].Ncgia Technical Report,1994

[6] 張永生，賁進，童曉沖. 地球空間信息球面離散網格——理論算法及應用[M] . 北京：科學出版社，2007

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

圖3 圖像提取邊界

圖4 邊界點云數

圖5 特征線

圖6 平面點提取結果

6 結 語

本文在掃描線和區域生長方法的基礎上，提出按照特征線的點云數據分割方法。

1）驗證了這種方法在點云分割過程中的正確性和有效性，按照特征線進行數據分割，并擬合出最佳平面，為點云的數據分割提供一種新的方法。

2）本文為點云數據分割提供了一個新的思考方向。在分割過程中，如何更好地提取深度圖像的邊緣信息可以進一步研究。

參考文獻

[1] 蔡潤彬,地面激光掃描數據后處理若干關鍵技術研究[D].上海:同濟大學，2008

[2] Jiang X Y, Bunke H. Edge Detection in Range Images Based on Scan Line Approximation[J]. Computer Vision and Image Understanding, 1999,73(2):183-199

[3] Besl P J, Jain R C. Segmentation Through Variable-order Surface Fitting[J].IEEE Transactionson Pattern Analysis and Machine Intelligence, 1988, 10(2):167-192

[4] 向日華, 王潤生. 一種基于高斯混合模型的距離圖像分割算法[J]. 軟件學報, 2003, 14(7): 1 250-1 257

[5] Yokoya N, Levine M D. Range Image Segmentation Based on Differential Geometry: A Hybrid Approach [J]. IEEE Trans Pami, 1989, 11(6): 643-649

[6] 丁益洪, 平西建, 胡敏. 基于隨機 Hough 變化的深度圖像分割 [J]. 計算機輔助設計與圖形學學報, 2005, 17(5): 902-907

[7] 何麗，李嘉，鄭德華.基于柵格的點云數據的邊界探測方法[J].測繪工程，2013，22(3):69-73

第一作者簡介：張大鵬，碩士，研究方向為三維激光掃描技術。

P208

B

1672-4623（2015）03-0130-03

10.3969/j.issn.1672-4623.2015.03.045

陳永就，工程師，主要從事大地測量、工程測量及地理信息系統的應用和軟件開發工作。

2015-01-13。