基于標準差準則的海底三維地形模型構(gòu)建

韓富江，潘勝玲，王德剛，來向華

（1.國家海洋局第二海洋研究所，浙江 杭州 310012；2.南京大學(xué) 網(wǎng)絡(luò)信息中心，江蘇 南京 210093）

基于標準差準則的海底三維地形模型構(gòu)建

韓富江1，潘勝玲2，王德剛1，來向華1

（1.國家海洋局第二海洋研究所，浙江 杭州 310012；2.南京大學(xué) 網(wǎng)絡(luò)信息中心，江蘇 南京 210093）

針對現(xiàn)有三角剖分需要投影到平面，局部優(yōu)化時屬性丟失的問題，本文采用一種顧及水深屬性的三角剖分準則——標準差準則進行三角剖分，并且討論了標準差的含義、標準差的計算以及標準差準則的描述。根據(jù)標準差準則，實現(xiàn)了一種基于標準差準則的海底三維地形模型構(gòu)建方法。實驗結(jié)果表明該方法提高了三角剖分的合理性，模型重建的細節(jié)與精確程度更高，在處理特殊地形上優(yōu)于基于空外接圓準則的TIN模型構(gòu)建方法。

標準差準則；海底三維地形模型；不規(guī)則三角網(wǎng)；特殊地形

虛擬海洋環(huán)境仿真是數(shù)字海洋建設(shè)的重要組成部分，它以數(shù)字的方式，逼真地模擬再現(xiàn)海洋環(huán)境，使人們可以探索有關(guān)海洋的自然和人文信息，并與之互動。而海底三維地形模型的構(gòu)建是虛擬海洋環(huán)境仿真的關(guān)鍵技術(shù)，對虛擬海洋環(huán)境仿真的效果有著重要影響。

海底三維地形模型的構(gòu)建通常采用數(shù)字地面模型（Digital Terrain Model，DTM）。目前，數(shù)字地面模型包括3種基本數(shù)據(jù)結(jié)構(gòu)：等高線結(jié)構(gòu)（Contour）、規(guī)則格網(wǎng)結(jié)構(gòu)（Grid）以及不規(guī)則三角網(wǎng)結(jié)構(gòu)（Triangulated Irregular Network，TIN）?；诘雀呔€的DTM是由一系列等高線集合和其對應(yīng)的高程值組成，等高線按有序的坐標點存儲，可認為是帶有高程屬性的簡單多邊形或多邊形弧段[1]。通過等高線和流線（等高線的法線方向）可把地形表面劃分成不規(guī)則的多邊形，有利于簡化水文模型的分析計算[2]，因而等高線結(jié)構(gòu)DTM在水文模型等地學(xué)分析領(lǐng)域應(yīng)用較多。規(guī)則格網(wǎng)結(jié)構(gòu)DTM計算處理簡單，但不能準確表示地形的結(jié)構(gòu)和細節(jié)，在地形平坦的地方，存在大量的數(shù)據(jù)冗余；在不改變格網(wǎng)大小的情況下，難以表達復(fù)雜地形的突變現(xiàn)象[3]。而不規(guī)則三角網(wǎng)結(jié)構(gòu)TIN模型由于頂點分布的任意性，能夠較好地反映地形表面特征及變化。TIN模型在表現(xiàn)地形表面起伏特征上具有規(guī)則格網(wǎng)無可比擬的優(yōu)勢。同時，由于TIN模型結(jié)構(gòu)緊湊，在相同表現(xiàn)效果的前提下，TIN模型所需的頂點數(shù)目要少于規(guī)則格網(wǎng)模型，從而TIN模型的數(shù)據(jù)量往往要比規(guī)則格網(wǎng)模型的數(shù)據(jù)量要小得多[4]。因此，基于海量數(shù)據(jù)的海底三維地形模型構(gòu)建通常采用TIN模型。

TIN模型構(gòu)建的核心技術(shù)就是散點的三角剖分，三角剖分過程也就是TIN的構(gòu)建過程。而三角剖分準則決定著三角形的幾何形狀和生成TIN模型的質(zhì)量[5]，影響著模型所表達地形的逼真度和精度。目前常用的三角剖分準則有：最短距離和準則、對角線準則；Lee、Lawson提出的空外接圓準則、最大最小角準則、張角最大準則[6,7]；徐利治提出的面積比準則[8]等。理論上空外接圓準則、最大最小角準則、張角最大準則是等價的，可以保持三角網(wǎng)的唯一性，其余的則不然。對角線準則含有主觀因素，現(xiàn)今已使用不多[5]。這些成果為TIN模型的構(gòu)建研究提供了重要的借鑒和技術(shù)參考。然而這些傳統(tǒng)的準則在進行散點集的三角剖分時，首先依據(jù)散點的平面分布確定一個三角網(wǎng)，然后將第三維數(shù)據(jù)如水深附加于平面三角網(wǎng)上，從而形成了包含連續(xù)的三角形面元的地形模型，因此它是一種面向曲面（三角形面元）的地形模型構(gòu)建技術(shù)。面向曲面的模型構(gòu)建方法，僅考慮了曲面元素的平面幾何形狀，而沒有考慮其在空間的分布情況，當(dāng)空間三角形與平面的夾角超過一定角度時，往往平面上形狀較好的三角形在空間上其形狀并不一定好，平面上形狀不好的三角形在空間上其形狀并不一定不好；另外一個問題是二維平面上的三角剖分忽略了點的屬性值，導(dǎo)致局部優(yōu)化過程（Local Optimization Procedure，LOP）中數(shù)據(jù)點的屬性丟失，造成在特殊地形如陡崖、虎口等處構(gòu)建的TIN模型與實際地表不相符。

為了解決上述問題，本文采用標準差準則[9]，將散點三維數(shù)據(jù)（x,y,h）計算得到的標準差，作為判斷三角形形狀在空間上好壞的依據(jù)，該準則將水深值引入三角剖分過程，提高了剖分的合理性。同時，在分析總結(jié)現(xiàn)有TIN剖分準則和算法的基礎(chǔ)上，實現(xiàn)了一種基于標準差準則的海底三維地形模型構(gòu)建方法，并實驗證明該方法構(gòu)建的海底三維地形模型更能反映海底的真實地表。

1 標準差準則

1.1 標準差的含義

標準差是一種量度數(shù)據(jù)分散程度的標準，用于衡量一組數(shù)據(jù)對算術(shù)平均值的離散程度。標準差較大，表示大部分數(shù)據(jù)與算術(shù)平均值之間的差異較大；標準差較小，表示這些數(shù)據(jù)較接近算術(shù)平均值。在TIN模型的構(gòu)建過程中，標準差則是衡量一個三角形接近正三角形程度的標準。對于一個三角形而言，三角形的三個頂角角度作為樣本數(shù)據(jù)，其算術(shù)平均值為60°，計算出的標準差越小表示三角形的三個頂角越接近60°，也意味著該三角形越接近正三角形，符合了TIN模型中三角形的幾何形狀盡量接近正三角形的剖分原則。

1.2 標準差的計算

在概率論與數(shù)理統(tǒng)計中，離散型隨機變量的標準差計算公式[10]為：

其中n表示隨機變量的個數(shù)；為n個隨機變量的算術(shù)平均值。對于TIN模型中的一個三角形ABC而言（圖1），假設(shè)三個頂點坐標為A（x1，y1，h1），B（x2，y2，h2），C（x3，y3，h3）,三個頂角為A、B、C，其算術(shù)平均值為60°,則標準差的計算公式（1）可以改寫為：

圖 1 三角形示意圖Fig.1 Triangle sketch

式(2)中的A、B、C表示三角形的三個頂角，可由三角形的余弦定理求得：

式(3)中的a、b、c表示三角形的三條邊長，可由空間兩點的距離公式求得：

1.3 標準差準則描述

標準差準則就是TIN模型構(gòu)建中一種三角形的剖分法則，指在兩相鄰三角形形成的凸四邊形中，這兩三角形的標準差之和一定小于交換凸四邊形對角線后所形成的兩三角形的標準差之和。利用標準差準則進行三角形剖分時，原始空間數(shù)據(jù)的三維坐標（x,y,h）參與三角形形狀好壞的判斷，不需要投影到平面上，直接從空間上進行三角剖分，剖分結(jié)果更符合空間實際的地形表面。

標準差準則的基本思想是將空間4點組成的四邊形進行三角剖分劃分為了兩種情形a和b（圖2），分別計算兩種情形下的三角形標準差之和，如果情形a的三角形標準差之和小于情形b的兩個三角形標準差之和，根據(jù)TIN模型中三角形的幾何形狀盡量接近正三角形的原則，選擇情形a作為構(gòu)建TIN的三角形，否則，選擇情形b。

圖 2 標準差準則Fig.2 Standard deviation criterion

對情形a和情形b中的三角形A、B、C、D以其內(nèi)角的角度作為樣本數(shù)據(jù)，根據(jù)公式(2)分別計算其標準差，用σA、σB、σC、σD表示。則情形a中A、B兩個三角形的標準差之和為σA+σB；情形b中C、D兩個三角形的標準差之和為σC+σD。根據(jù)標準差準則，可以通過判斷σA+σB與σC+σD的大小，選擇情形a還是情形b作為構(gòu)建TIN模型的優(yōu)化三角形。如果（σA+σB）－（σC+σD）小于零，則情形a好；（σA+σB）－（σC+σD）大于零，則情形b好；（σA+σB）－（σC+σD）等于零，則兩種情形一樣好，選擇情形a或是情形b都可以。

2 基于標準差準則的海底三維地形模型構(gòu)建

一個良好的數(shù)據(jù)結(jié)構(gòu)和三角形剖分準則，必須有高效的算法和程序?qū)崿F(xiàn)。目前離散型數(shù)據(jù)集的TIN模型構(gòu)建使用最為廣泛的是Delaunay直接三角剖分算法，包括分割合并算法、三角網(wǎng)增長算法和逐點插入算法[5]。由于分割合并算法是遞歸執(zhí)行，內(nèi)存開銷較大；三角網(wǎng)增長算法最大的問題是計算的時間復(fù)雜性，數(shù)據(jù)點越多問題越突出[11]；而逐點插入算法在很大程度上克服了上述問題，并且概念簡單，容易實現(xiàn)，還能夠進行約束三角剖分，所以本文構(gòu)建海底三維地形模型的方法沿用了逐點插入法的基本思想，只是把LOP時采用的空外接圓準則替換為標準差準則，在空間上直接對散點進行剖分，提高模型重建的細節(jié)與精確度。

算法的基本思想是：先在包含所有數(shù)據(jù)點的多邊形中建立初始三角網(wǎng)，然后在已存在的三角網(wǎng)中插入數(shù)據(jù)點，找到包含該數(shù)據(jù)點的三角形，連接該點與其所在三角形的三個頂點形成新的三個三角形，用標準差準則優(yōu)化新形成的三角形，直至所有數(shù)據(jù)點都插入到三角網(wǎng)中。具體的算法步驟如下：

步驟1 建立包含所有數(shù)據(jù)點的初始包容盒，該包容盒可以為凸殼、矩形包容盒或超級三角形，并對該包容盒進行初始三角剖分。本文選用的包容盒為超級三角形，超級三角形的三個頂點坐標可以通過以下方法得到。假設(shè)離散數(shù)據(jù)集中含有n個離散點，坐標為（xi，yi，hi），i=1,2,…,n。對離散點的坐標進行比較得到最大值xmax，ymax，最小值xmin，ymin，hi為水深值。通過以下公式計算得到坐標范圍dx，dy，坐標范圍最大值dmax以及坐標中間值xmid，ymid。

步驟2 往初始三角網(wǎng)中插入數(shù)據(jù)點，設(shè)當(dāng)前處理數(shù)據(jù)點為P，首先找出包含點P的三角形T，設(shè)T的三頂點為V1、V2、V3，然后P與T三頂點相連，形成三個新的三角形T1、T2、T3，如圖3所示。

步驟3 對所有新形成的三角形，利用標準差準則進行優(yōu)化處理。為了對所形成的新三角形進行優(yōu)化，需要將包含當(dāng)前點的三角形的相鄰三角形放入一個堆棧中。然后從堆棧中每次彈出一個三角形，與包含插入點的三角形進行LOP優(yōu)化，如果進行了對角線交換，相鄰三角形也要放入堆棧，這是一個循環(huán)過程，直到堆棧為空，方可進行下一點的處理。具體優(yōu)化過程如下：

圖 3 包含點P的三角形及初始三角剖分Fig.3 Triangle including point P and initial triangulation

（1）把包含P的三角形的三個鄰接三角形P1、P2、P3放入堆棧中；

（2）從堆棧中彈出三角形P3；

（3）計算三角形P3與鄰接三角形T3的標準差之和σ1，以及交換對角線之后兩個三角形的標準差之和σ2。如果σ1大于σ2，則需要交換對角線，否則，彈出下一個三角形；

（4）如果交換對角線，原來與P3相鄰的兩個三角形也要壓入堆棧；

（5）重復(fù)（2）－（4），直到堆棧為空，則P點的插入過程結(jié)束。

步驟4 重復(fù)步驟（2）－（3），直至所有數(shù)據(jù)點都被插入到TIN模型中。

步驟5 處理外圍三角形，完成海底三維地形模型的構(gòu)建。由于超級三角形的頂點并不是水深離散點集中的點，所以要將包含超級三角形頂點的三角形和超級三角形的三個頂點移除，得到最終的海底三維地形TIN模型。

基于標準差準則的海底三維地形模型構(gòu)建方法較好地解決了LOP時水深屬性丟失的問題，同時，對數(shù)據(jù)點的三角剖分直接在空間進行，提高了海底地形TIN模型的細節(jié)性和準確性。

3 實驗與分析

為了驗證基于標準差準則海底三維地形模型構(gòu)建方法的優(yōu)越性，本文在C#.NET開發(fā)環(huán)境中編程實現(xiàn)了該方法，構(gòu)建了海底三維地形TIN模型，并且與利用空外接圓準則構(gòu)建的海底三維地形模型進行了對比分析。實驗選取的數(shù)據(jù)為由SeaBeam 2112多波束測深系統(tǒng)測得的水深數(shù)據(jù)，共有5 844個數(shù)據(jù)點，數(shù)據(jù)分布比較均勻，數(shù)據(jù)點的三維顯示如圖4所示。由圖4可以看出本文所選實驗區(qū)的海底地形起伏變化較大，并且還有一個特殊地形陡崖。

圖4 水深數(shù)據(jù)點的三維顯示Fig.4 Three-dimensional display of bathymetric data points

基于標準差準則算法構(gòu)建的海底三維地形TIN模型如圖5（a）所示；空外接圓準則算法構(gòu)建的海底三維地形TIN模型如圖5（b）所示。

由圖5（a）可以看出，基于標準差準則算法構(gòu)建的海底三維地形TIN模型有效地避免了狹長三角形的出現(xiàn)，保證了三角形形狀在空間上的良好性，解決了水深屬性丟失的問題，使得在特殊地形陡崖處構(gòu)建的TIN更接近海底的真實地表。而空外接圓準則算法構(gòu)建的海底三維地形模型，由于其三角剖分過程是在投影平面上進行，造成陡崖處的TIN很凌亂，狹長三角形較多，不符合三角剖分的原則，也不能反映特殊地形的真實表面，結(jié)果如圖5（b）所示。兩種方法構(gòu)建的海底三維地形模型不一致的主要原因是在利用空外接圓準則對TIN模型進行優(yōu)化的過程中，只用到了數(shù)據(jù)點的（x,y）坐標，沒有顧及水深屬性，并且需要投影到平面xoy上進行，這樣就造成在空間上形狀較好的三角形，投影到平面上反而變成了狹長三角形；空間上狹長的三角形，投影到平面上反而接近正三角形。特別是在陡崖等特殊地形，上部的數(shù)據(jù)點投影到平面上還有可能與下部數(shù)據(jù)點重合或相鄰較近，在三角剖分過程中，容易引起狹長三角形的形成。基于標準差準則的算法則直接在空間對水深數(shù)據(jù)點進行三角剖分，利用數(shù)據(jù)點三維坐標（x,y,h）計算得到的標準差作為判斷三角形形狀好壞的依據(jù)，剖分準則顧及了海底地形的屬性水深值，提高了海底地形三維TIN模型的細節(jié)性和準確性。

圖5 兩種剖分準則構(gòu)建的海底三維地形模型透視圖對比Fig.5 Contrast of three-dimensional seabed terrain model constructed by different algorithms

4 結(jié) 語

本文在分析現(xiàn)有三角剖分準則的基礎(chǔ)上，采用一種顧及水深屬性的三角剖分準則—標準差準則進行三角剖分，該準則克服了原有剖分準則需要投影到平面上進行三角剖分的不足，解決了LOP時屬性丟失的問題。根據(jù)標準差準則，實現(xiàn)了一種基于標準差準則的海底三維地形模型構(gòu)建方法。實驗結(jié)果表明該方法提高了三角剖分的合理性，模型重建的細節(jié)與精確程度更高，在處理特殊地形上優(yōu)于基于空外接圓準則的TIN模型構(gòu)建方法。由于水深測量數(shù)據(jù)的海量性，基于標準差準則的海底三維地形模型的構(gòu)建效率以及模型的紋理映射處理都需要進一步的深入研究。

[1]Moore I D, Grayson R B.Terrain-based Catchment Partitioning and Runoff Prediction Using Vector Elevation Data [J].Water Resources Research.1991b, 27(6):1177-1191.

[2]Wilson J P, Gallant J C.Terrain Analysis: Principles and Applications [M].New York: John Wiley and Sons, 2000.

[3]鄔倫, 劉瑜, 張晶, 等.地理信息系統(tǒng)-原理、方法和應(yīng)用 [M].北京: 科學(xué)出版社, 2001.

[4]石松.虛擬地理環(huán)境中地形建模及其空間分析研究 [D].福州:福州大學(xué), 2005.

[5]湯國安, 劉學(xué)軍, 閭國年.數(shù)字高程模型及地學(xué)分析的原理與方法 [M].北京: 科學(xué)出版社, 2005.

[6]Lee D T, Schachter B J.Two Algorithms for Constructing a Delaunay Triangulation [J].Int.Journal of Computer and Information science.1980, 9(3): 219-242.

[7]Lawson C L.Software for c' Surface Interpolation [C]//Mathematical Software III, New York: Academic Press, 1977: 161-194.

[8]徐利治.逼近論 [M].北京: 國防工業(yè)版社, 1985.

[9]潘勝玲, 劉學(xué)軍.基于標準差的地形三維表面模型建立方法 [J].計算機應(yīng)用研究, 2007, 24(11): 295-297.

[10]余錦華, 石北源, 楊維權(quán).概率論與數(shù)理統(tǒng)計[M].廣州: 中山大學(xué)出版社, 2000.

[11]李志林, 朱慶.數(shù)字高程模型 [M].武漢: 武漢大學(xué)出版社, 2003.

Construction of 3D Seabed Terrain Model based on the Standard Deviation Criterion

HAN Fu-jiang1, PAN Sheng-ling2, WANG De-gang1, LAI Xiang-hua1

(1.Second Institute of Oceanography, SOA, Hangzhou 310012, China; 2.Network Information Center, Nanjing University, Nanjing 210093, China)

At present, existing triangulation must be done in the projection plane, so it causes the loss of attribution information in LOP (Local Optimization Procedure).In this paper, a new triangulation criterion based on standard deviation is used.The definition of standard deviation, calculation of standard deviation, and description of standard deviation criterion is investigated.Then the construction algorithm of 3D seabed terrain model based on standard deviation is presented according to the standard deviation criterion.The result of experiment shows that this method improves the rationality of triangulation, the details and precision of seabed terrain model are better than others, and it is better in dealing with special terrain than the algorithm based on empty circum-circle criterion.

standard deviation criterion; three-dimensional seabed terrain model; Triangulated Irregular Network; special terrain

TP311

A

1001-6932(2011)06-0674-05

2011-01-05；

2011-05-23

國家海洋局第二海洋研究所基本科研業(yè)務(wù)費專項資金資助項目（JG0913, JT0803, JG0911）。

韓富江（1977－），男，碩士，工程師，主要從事三維建模及可視化、海洋測繪、DEM及地形分析方面的研究。電子郵箱: hfj111@126.com。