陳永就，林 川

（1.廣東省國(guó)土資源測(cè)繪院，廣東 廣州510500）

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

陳永就1，林 川1

（1.廣東省國(guó)土資源測(cè)繪院，廣東 廣州510500）

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

球面離散網(wǎng)格 ；四邊形網(wǎng)格；直接剖分法；面積形變

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

1 球面四邊形網(wǎng)格的構(gòu)建

球面多邊形網(wǎng)格一般是在多面體剖分的基礎(chǔ)上建立的[6]，本文以正八面體剖分為例對(duì)兩種網(wǎng)格進(jìn)行分析。球內(nèi)接正八面體和球面相交的6個(gè)點(diǎn)是南北兩個(gè)極點(diǎn)和赤道上的4個(gè)點(diǎn)，它的12條邊線映射到球面上即構(gòu)成了球面基礎(chǔ)網(wǎng)格，網(wǎng)格將球表面分成了8個(gè)相等的區(qū)域，以南北相鄰的2個(gè)三角面組成的區(qū)域?yàn)槔M(jìn)行分析，其他球面的情況類似。在確立基礎(chǔ)網(wǎng)格后便是對(duì)其采用一定的數(shù)學(xué)規(guī)則進(jìn)行遞歸細(xì)分，不同的細(xì)分方法將產(chǎn)生不同的網(wǎng)格。

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

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

2 網(wǎng)格的可視化效果

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

3 網(wǎng)格的面積形變

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

其中，x1、 x2、 x3分別是三角形3個(gè)頂點(diǎn)的向量。

圖1 QTM擴(kuò)展四邊網(wǎng)格

圖2 直接剖分法生成的四邊形網(wǎng)格

圖3 50%較大面積網(wǎng)格的分布情況（6層）

圖4 50%較大面積網(wǎng)格的分布情況（7層）

在對(duì)單位三角形一分為四時(shí)，QTM網(wǎng)格中間三角形的面積明顯比周邊三角形面積大，基于QTM擴(kuò)展的四邊形網(wǎng)格會(huì)繼承QTM網(wǎng)格的形變規(guī)律。從直接剖分法生成的四邊形網(wǎng)格的可視化效果來(lái)看，網(wǎng)格的面積形變主要集中在邊緣部分，網(wǎng)格中間大片連續(xù)的區(qū)域較為均勻，這部分區(qū)域網(wǎng)格單元的面積較大。將各個(gè)剖分層次中的50%較大面積網(wǎng)格用顏色標(biāo)出，可以看出這部分網(wǎng)格區(qū)域是連續(xù)的且范圍不會(huì)隨著剖分層次的增加而發(fā)生明顯改變。圖3、圖4分別顯示的是直接剖分法下6層剖分和7層剖分的網(wǎng)格，紅色標(biāo)識(shí)的是網(wǎng)格總數(shù)中50%較大面積網(wǎng)格。

對(duì)直接剖分下網(wǎng)格總數(shù)中50%較大面積網(wǎng)格、整體網(wǎng)格和QTM擴(kuò)展的四邊形網(wǎng)格進(jìn)行對(duì)比，求出它們?cè)诟鱾€(gè)剖分層次的最大與最小網(wǎng)格面積。研究區(qū)域中最大單元網(wǎng)格面積和最小單元網(wǎng)格面積的比值越小，說(shuō)明網(wǎng)格大小越接近，網(wǎng)格越均勻。通過(guò)對(duì)網(wǎng)格最大與最小面積比值在各個(gè)剖分層次變化的統(tǒng)計(jì)分析，得到網(wǎng)格均勻性特征隨剖分層次增加的變化趨勢(shì)，若變化收斂，則網(wǎng)格均勻性特征穩(wěn)定。表1顯示的是上述四邊形網(wǎng)格最大與最小面積比值在各個(gè)剖分層次的變化。

由上表數(shù)據(jù)可知，基于QTM擴(kuò)展的四邊形網(wǎng)格最大與最小面積比值隨著剖分層次的增加而增大，最后會(huì)收斂到2.1?；谥苯悠史值那蛎嫠倪呅坞x散網(wǎng)格最大與最小面積比值隨著剖分層次的增加而增大，且不收斂。通過(guò)對(duì)單元網(wǎng)格面積的統(tǒng)計(jì)結(jié)果可得出，是由于剖分層次增加后網(wǎng)格邊緣四邊形面積驟減導(dǎo)致的。直接剖分下網(wǎng)格總數(shù)中50%較大面積網(wǎng)格的最大與最小面積比值隨著剖分層次的增加最終收斂到1.3。從全球網(wǎng)格分布來(lái)看，基于QTM擴(kuò)展的四邊形網(wǎng)格面積形變要優(yōu)于直接剖分法所得網(wǎng)格，從區(qū)域網(wǎng)格分布來(lái)看，直接剖分法所得網(wǎng)格在中間恒定、連續(xù)的大片區(qū)域上網(wǎng)格細(xì)分更加規(guī)整和均勻。

表1 網(wǎng)格最大與最小面積比值在各個(gè)剖分層次的變化

4 結(jié) 語(yǔ)

基于三角形擴(kuò)展的四邊形網(wǎng)格會(huì)繼承三角形網(wǎng)格的形變特征，本文提出了一種基于直接剖分的球面四邊形離散網(wǎng)格生成方法與基于QTM擴(kuò)展的四邊形網(wǎng)格相比，它在整體上均勻性較差，但在大范圍的局部區(qū)域上表現(xiàn)出更加規(guī)整和均勻的特性，滿足一般中小尺度模型的范圍要求?；谥苯悠史值那蛎嫠倪呅坞x散網(wǎng)格為構(gòu)建局部高精度網(wǎng)格提出了新的參考，其在球面離散網(wǎng)格建模中的應(yīng)用值得進(jìn)一步研究。

[1] 趙學(xué)勝，侯妙樂(lè)，白建軍. 全球離散格網(wǎng)的空間數(shù)字建模[M].北京:測(cè)繪出版社，2007

[2] 李德仁，朱欣焰，龔健雅. 從數(shù)字地圖到空間信息格網(wǎng)[J].武漢大學(xué)學(xué)報(bào)：信息科學(xué)版， 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] 趙學(xué)勝，白建軍. 基于菱形塊的全球離散格網(wǎng)層次建模[J].中國(guó)礦業(yè)大學(xué)學(xué)報(bào)，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] 張永生，賁進(jìn)，童曉沖. 地球空間信息球面離散網(wǎng)格——理論算法及應(yīng)用[M] . 北京：科學(xué)出版社，2007

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

圖3 圖像提取邊界

圖4 邊界點(diǎn)云數(shù)

圖5 特征線

圖6 平面點(diǎn)提取結(jié)果

6 結(jié) 語(yǔ)

本文在掃描線和區(qū)域生長(zhǎng)方法的基礎(chǔ)上，提出按照特征線的點(diǎn)云數(shù)據(jù)分割方法。

1）驗(yàn)證了這種方法在點(diǎn)云分割過(guò)程中的正確性和有效性，按照特征線進(jìn)行數(shù)據(jù)分割，并擬合出最佳平面，為點(diǎn)云的數(shù)據(jù)分割提供一種新的方法。

2）本文為點(diǎn)云數(shù)據(jù)分割提供了一個(gè)新的思考方向。在分割過(guò)程中，如何更好地提取深度圖像的邊緣信息可以進(jìn)一步研究。

參考文獻(xiàn)

[1] 蔡潤(rùn)彬,地面激光掃描數(shù)據(jù)后處理若干關(guān)鍵技術(shù)研究[D].上海:同濟(jì)大學(xué)，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] 向日華, 王潤(rùn)生. 一種基于高斯混合模型的距離圖像分割算法[J]. 軟件學(xué)報(bào), 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] 丁益洪, 平西建, 胡敏. 基于隨機(jī) Hough 變化的深度圖像分割 [J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2005, 17(5): 902-907

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

第一作者簡(jiǎn)介：張大鵬，碩士，研究方向?yàn)槿S激光掃描技術(shù)。

P208

B

1672-4623（2015）03-0130-03

10.3969/j.issn.1672-4623.2015.03.045

陳永就，工程師，主要從事大地測(cè)量、工程測(cè)量及地理信息系統(tǒng)的應(yīng)用和軟件開發(fā)工作。

2015-01-13。