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

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

基于標(biāo)準(zhǔn)差準(zhǔn)則的海底三維地形模型構(gòu)建

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

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

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

標(biāo)準(zhǔn)差準(zhǔn)則；海底三維地形模型；不規(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)的高程值組成，等高線按有序的坐標(biāo)點(diǎn)存儲，可認(rèn)為是帶有高程屬性的簡單多邊形或多邊形弧段[1]。通過等高線和流線（等高線的法線方向）可把地形表面劃分成不規(guī)則的多邊形，有利于簡化水文模型的分析計(jì)算[2]，因而等高線結(jié)構(gòu)DTM在水文模型等地學(xué)分析領(lǐng)域應(yīng)用較多。規(guī)則格網(wǎng)結(jié)構(gòu)DTM計(jì)算處理簡單，但不能準(zhǔn)確表示地形的結(jié)構(gòu)和細(xì)節(jié)，在地形平坦的地方，存在大量的數(shù)據(jù)冗余；在不改變格網(wǎng)大小的情況下，難以表達(dá)復(fù)雜地形的突變現(xiàn)象[3]。而不規(guī)則三角網(wǎng)結(jié)構(gòu)TIN模型由于頂點(diǎn)分布的任意性，能夠較好地反映地形表面特征及變化。TIN模型在表現(xiàn)地形表面起伏特征上具有規(guī)則格網(wǎng)無可比擬的優(yōu)勢。同時(shí)，由于TIN模型結(jié)構(gòu)緊湊，在相同表現(xiàn)效果的前提下，TIN模型所需的頂點(diǎn)數(shù)目要少于規(guī)則格網(wǎng)模型，從而TIN模型的數(shù)據(jù)量往往要比規(guī)則格網(wǎng)模型的數(shù)據(jù)量要小得多[4]。因此，基于海量數(shù)據(jù)的海底三維地形模型構(gòu)建通常采用TIN模型。

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

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

1 標(biāo)準(zhǔn)差準(zhǔn)則

1.1 標(biāo)準(zhǔn)差的含義

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

1.2 標(biāo)準(zhǔn)差的計(jì)算

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

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

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

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

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

1.3 標(biāo)準(zhǔn)差準(zhǔn)則描述

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

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

圖 2 標(biāo)準(zhǔn)差準(zhǔn)則Fig.2 Standard deviation criterion

對情形a和情形b中的三角形A、B、C、D以其內(nèi)角的角度作為樣本數(shù)據(jù)，根據(jù)公式(2)分別計(jì)算其標(biāo)準(zhǔn)差，用σA、σB、σC、σD表示。則情形a中A、B兩個三角形的標(biāo)準(zhǔn)差之和為σA+σB；情形b中C、D兩個三角形的標(biāo)準(zhǔn)差之和為σC+σD。根據(jù)標(biāo)準(zhǔn)差準(zhǔn)則，可以通過判斷σ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 基于標(biāo)準(zhǔn)差準(zhǔn)則的海底三維地形模型構(gòu)建

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)與分析

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

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

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

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

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

4 結(jié) 語

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

[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é)軍.基于標(biāo)準(zhǔn)差的地形三維表面模型建立方法 [J].計(jì)算機(jī)應(yīng)用研究, 2007, 24(11): 295-297.

[10]余錦華, 石北源, 楊維權(quán).概率論與數(shù)理統(tǒng)計(jì)[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ù)費(fèi)專項(xiàng)資金資助項(xiàng)目（JG0913, JT0803, JG0911）。

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