倪曉東，鄒德華，鄧德標(biāo)

(1. 廣東南方數(shù)碼科技有限公司，廣東 廣州 510665； 2. 廣東省航道測繪中心，廣東 廣州 511483)

Research on the Algorithm of Tracing Contour with Thin Plate

Spline Fitting Surface

NI Xiaodong,ZOU Dehua,DENG Debiao

?

薄板樣條函數(shù)支持下的等深線追蹤算法研究

倪曉東1，鄒德華2，鄧德標(biāo)1

(1. 廣東南方數(shù)碼科技有限公司，廣東 廣州 510665； 2. 廣東省航道測繪中心，廣東 廣州 511483)

Research on the Algorithm of Tracing Contour with Thin Plate

Spline Fitting Surface

NI Xiaodong,ZOU Dehua,DENG Debiao

摘要：基于薄板樣條函數(shù)的擬合曲面能很好地根據(jù)水深點(diǎn)數(shù)據(jù)模擬水下地形，通過建立一定密度的規(guī)則格網(wǎng)可以十分精細(xì)地追蹤等深線。因薄板樣條曲面是光滑的，故生成的等深線具有一定的平滑性。本文首先論述了薄板樣條曲面的解算步驟，然后研究了在該曲面上構(gòu)建規(guī)則格網(wǎng)模型和追蹤等深線的算法，最后以南方CASS作為實(shí)現(xiàn)平臺，根據(jù)實(shí)際數(shù)據(jù)生成的等深線效果證明了本文提出的算法是可行有效的，能有效地避免曲線擬合過程中產(chǎn)生的凸起或陡變現(xiàn)象。

關(guān)鍵詞：薄板樣條；曲面擬合；等深線；DEM；CASS

早期的等深線是通過手扶數(shù)字化繪制的，勞動強(qiáng)度大、周期長，現(xiàn)在發(fā)展到了自動數(shù)字化成圖，等深線可通過建立三角網(wǎng)或規(guī)則格網(wǎng)來生成。在該過程中，三角網(wǎng)對離散點(diǎn)的分布比較敏感，分布不均勻會導(dǎo)致稀疏處出現(xiàn)比較嚴(yán)重的失真，格網(wǎng)模型構(gòu)建的精度和光滑程度不高，這些都直接影響等深線的效果。而對于等深線，要求在表達(dá)信息準(zhǔn)確的前提下，盡量要使線型流暢順滑，這就對數(shù)據(jù)擬合有較高的要求。

薄板樣條是一種關(guān)于幾何設(shè)計(jì)的插值方法，可用于復(fù)雜曲面的數(shù)學(xué)表示[1]，該方法通過模擬金屬薄板的彎曲得到一個經(jīng)過所有控制點(diǎn)且彎曲程度最小的光滑曲面。因?yàn)樵撉鎳?yán)格經(jīng)過控制點(diǎn)，曲面有嚴(yán)密的公式表達(dá)，可根據(jù)曲面范圍內(nèi)的二維坐標(biāo)精確計(jì)算曲面上每一點(diǎn)的第三維坐標(biāo)值，因此該方法廣泛應(yīng)用于區(qū)域似大地水準(zhǔn)面擬合[2]、高程異常的插值計(jì)算[3]等領(lǐng)域。文獻(xiàn)[4]將其應(yīng)用于中國氣候空間模擬，取得很好的效果。早在ANUDEM軟件里就使用薄板樣條函數(shù)建立高精度的DEM，現(xiàn)已集成到ArcGIS系統(tǒng)中[5]。岳天祥等[6-8]提出一種基于微分幾何曲面論的曲面建模方法中也使用了薄板樣條模型，可見薄板樣條在建立DEM上起著非常重要的作用。

本文提出了基于薄板樣條函數(shù)的等深線追蹤算法，先通過薄板樣條函數(shù)建立光滑的曲面格網(wǎng)模型，然后在該模型的格網(wǎng)上追蹤等深線，文獻(xiàn)[9]介紹了格網(wǎng)式數(shù)字地形模型追蹤等高點(diǎn)的一種簡易算法。通過與傳統(tǒng)的基于三角網(wǎng)生成等深線的算法比較，新算法得到的等深線效果明顯優(yōu)于傳統(tǒng)算法。

一、薄板樣條擬合曲面

設(shè)薄板樣條曲面的方程為

z=a1+a2x+a3y+Δ

(1)

(2)

(3)

式中，z為點(diǎn)(x,y)處的高程值；a1、a2、a3和wi為方程系數(shù)；Δ為修正值；s為當(dāng)前控制點(diǎn)與其余控制點(diǎn)的平面距離；n為控制點(diǎn)總數(shù)。

將曲面方程用矩陣的形式表達(dá)如下：

由

(4)

得

(5)

由式(5)即可求得方程系數(shù)，式中w和a為待求向量，形式如下

K為n×n矩陣，每個元素由下式計(jì)算

(6)

其余矩陣和向量如下

解算過程如下：先根據(jù)每個控制點(diǎn)的平面坐標(biāo)計(jì)算矩陣K，再組成矩陣P和向量z，最后通過矩陣求逆和相關(guān)運(yùn)算即可求得薄板樣條擬合曲面方程的系數(shù)。

從矩陣K可知，控制點(diǎn)數(shù)越多，矩陣的階數(shù)越高，矩陣的運(yùn)算量就越大，最后需要求解一個巨大的線性方程組，試驗(yàn)表明，當(dāng)擬合點(diǎn)個數(shù)超過500時效率就不理想。因此算法的實(shí)現(xiàn)采用文獻(xiàn)[10]的建議，當(dāng)?shù)匦伪容^復(fù)雜、數(shù)據(jù)量較多時，將擬合區(qū)域適當(dāng)分塊，薄板樣條函數(shù)可以自動實(shí)現(xiàn)不同區(qū)域之間的拼接。

二、等深線追蹤

目前常用生成等深線的算法是線性三角網(wǎng)法，先構(gòu)建覆蓋整個測區(qū)的三角網(wǎng)，然后在三角網(wǎng)上計(jì)算等深線經(jīng)過的點(diǎn)，接著將這些點(diǎn)連線形成折線形的等深線，最后用張力樣條或三次樣條函數(shù)對每條折線進(jìn)行擬合即得到最終光滑的等深線。整個過程只進(jìn)行了一次擬合，加上三角網(wǎng)上控制節(jié)點(diǎn)的數(shù)量是隨機(jī)的，故最終生成的等深線的線型會常出現(xiàn)突然變化，拐彎的幅度大，凹凸變化明顯且無法控制的情況。

由于三角網(wǎng)的密度依賴于測量點(diǎn)的數(shù)量和分布，而等深線與三角形的交點(diǎn)一般只能采用少量的測量數(shù)據(jù)來計(jì)算，因此在測量點(diǎn)比較稀疏的地方，等深線的可靠性非常低。而由薄板樣條擬合曲面的解釋過程可知，該方法是一種過點(diǎn)的擬合方式，最終得到的曲面均經(jīng)過每個控制點(diǎn)，當(dāng)計(jì)算曲面上任意一點(diǎn)的高程時，需要計(jì)算該點(diǎn)與構(gòu)成曲面的所有控制點(diǎn)的距離，該過程可認(rèn)為是充分考慮每個已知點(diǎn)的距離相關(guān)性，結(jié)果的可靠性大大提升。基于薄板樣條函數(shù)的等深線追蹤算法的步驟如下：

1) 導(dǎo)入具有測量點(diǎn)的三維坐標(biāo)作為曲面擬合的控制點(diǎn)數(shù)據(jù)。

2) 解算式(1)的參數(shù)，得到一個通過每個控制點(diǎn)的光滑曲面。若控制點(diǎn)數(shù)量較多，可根據(jù)測區(qū)面積將數(shù)據(jù)分塊后再進(jìn)行擬合，相鄰兩塊區(qū)域需保留一定的重疊度，有利于后續(xù)的拼接保持光滑。

3) 根據(jù)控制點(diǎn)的密度和實(shí)際需求構(gòu)建覆蓋整個測區(qū)的平面格網(wǎng)。

4) 計(jì)算每個格網(wǎng)節(jié)點(diǎn)所在擬合曲面上的高程值，將平面格網(wǎng)轉(zhuǎn)換成曲面格網(wǎng)，如圖1所示。

5) 根據(jù)給定的高程值在曲面格網(wǎng)上追蹤等深線。

6) 檢查每條等深線，刪除距離過短的相鄰節(jié)點(diǎn)和節(jié)點(diǎn)數(shù)過少的線，并依據(jù)實(shí)際需求再對等深線進(jìn)行擬合。

因?yàn)槭窃诠饣嫔献粉櫝鰜淼牡壬罹€，因此即使不對等深線進(jìn)行擬合也具有一定的平滑性。

圖1　曲面規(guī)則格網(wǎng)

三、實(shí)例應(yīng)用

在航道測量中，需要繪制河流等深線以便為船舶行駛提供安全保障。常規(guī)做法是按照一定的密度測量水下地形的水深值，據(jù)此繪制等深線。由于水下地形不可見，很難采集到特征線或特征點(diǎn)，而且大部分地形都比較平緩，從而大大增加了生成等深線的難度。

在測繪行業(yè)中，南方CASS成圖軟件廣泛應(yīng)用于大比例尺地形圖的生產(chǎn)，經(jīng)過多年的積累和發(fā)展，已實(shí)現(xiàn)生成等高線、等深線的自動化功能，而且具備二次開發(fā)的接口。因此采用南方CASS作為試驗(yàn)平臺，利用ObjectARX進(jìn)行二次開發(fā)，實(shí)現(xiàn)了薄板樣條函數(shù)的解算、擬合曲面格網(wǎng)的生成和等深線的追蹤等算法。下面比較原有等深線追蹤算法和本文所述算法的效果。

圖2是廣東省航道局提供的某一段河流的水深點(diǎn)測量數(shù)據(jù)。按照相關(guān)規(guī)范要求，測量航線應(yīng)盡量垂直于河流方向，相鄰航線間距約40m，同一條航線上的相鄰水深點(diǎn)間距約13m。圖3和圖4分別是兩種算法生成的模型。

圖2　水深測量點(diǎn)

圖3　Delaunay三角網(wǎng)模型

圖4　規(guī)則格網(wǎng)模型

圖5和圖6展示了兩種模型追蹤生成的等深線效果，等高距為0.5m。從整體來看兩種算法得到的結(jié)果基本一致，基于三角網(wǎng)的等深線沒有擬合的情況下突變較多，而基于曲面格網(wǎng)的等深線卻顯得比較圓滑，可見該算法避免了曲線擬合造成的凹凸變化明顯和突變等情況，從對同一個地方的放大圖證明了這一點(diǎn)。

圖5　基于三角網(wǎng)的等深線

圖6　基于曲面格網(wǎng)的等深線

為了安全起見，航道等深線還應(yīng)遵循就淺不就深的原則，即若有一塊平坦區(qū)域，等深線應(yīng)該從靠近較淺的那邊通過，而不應(yīng)穿越區(qū)域或往深的那邊靠。圖2的數(shù)據(jù)中，中間部分有一塊平坦區(qū)域，深度為6m，如圖7空白區(qū)所示。圖5的等深線只是把該區(qū)域圈出來，而基于曲面格網(wǎng)的等深線卻從較淺的一側(cè)通過，即圖7中的平坦區(qū)域上邊線。因?yàn)槠教箙^(qū)域在網(wǎng)中以平三角形(三個頂點(diǎn)的高程相同)的形式存在，很容易被檢查出來，進(jìn)而根據(jù)鄰接三角形的高低作為判斷條件。因此在追蹤等深線時，加入三角網(wǎng)模型作為參照約束條件，自動識別出平坦區(qū)域，調(diào)整等深線的走向。

圖7　平坦區(qū)域效果

若河道中有孤島，可在圖面上繪制指定編碼的輪廓線，在生成曲面格網(wǎng)時加入該輪廓線作為約束區(qū)域，區(qū)域內(nèi)格網(wǎng)節(jié)點(diǎn)的高程置為無效值，那么在追蹤等深線時就會自動繞過該孤島。

四、結(jié)束語

對于復(fù)雜的水下地形，由于離散的水深點(diǎn)帶有隨機(jī)性，密度和分布不均勻，導(dǎo)致所建的模型失真，基于三角網(wǎng)的內(nèi)插精度不高，使得追蹤出來的等深線跟實(shí)際地形相差較大。而基于薄板樣條的擬合曲面能很好地模擬水下地形，通過建立一定密度的規(guī)則曲面格網(wǎng)可以十分精細(xì)地追蹤等深線。由于是過點(diǎn)擬合，曲面上每一處的高程都能根據(jù)所有參與擬合計(jì)算的控制點(diǎn)進(jìn)行計(jì)算得到，因此充分利用了測量點(diǎn)的精度。

利用南方CASS成圖軟件作為實(shí)現(xiàn)平臺，通過試驗(yàn)表明，本文提出的算法較傳統(tǒng)方法更貼近真實(shí)地形，從而能生成精度更高的等高線，同時也證明了該算法的可行性和有效性。用三角網(wǎng)作為參照約束條件，可以很好地解決“就淺不就深”的原則，為航道安全提供保障。

為進(jìn)一步發(fā)揮薄板樣條函數(shù)擬合的作用，今后可推廣到等高線追蹤算法中，通過加入地性線的約束，有望實(shí)現(xiàn)比基于Deluanay三角網(wǎng)生成的等高線更好的效果。

參考文獻(xiàn)：

[1]孫海燕, 丁咚. 薄板樣條函數(shù)及復(fù)雜曲面的數(shù)學(xué)表示[J]. 測繪工程, 2006, 15(2): 7-8.

[2]郭春喜, 聶建亮, 王斌,等. 區(qū)域似大地水準(zhǔn)面擬合方法及適用性分析[J]. 大地測量與地球動力學(xué), 2013, 33(1): 103-107.

[3]程義軍, 孫海燕. 薄板樣條與大區(qū)域高程異常插值[J]. 測繪科學(xué), 2008, 33(4): 42-45.

[4]閻洪. 薄板光順樣條插值與中國氣候空間模擬[J]. 地理科學(xué), 2004, 24(2): 163-169.

[5]宋敦江, 岳天祥, 杜正平. 一種由等高線構(gòu)建DEM的新方法[J]. 武漢大學(xué)學(xué)報(信息科學(xué)版), 2012, 37(4): 472-476.

[6]YUETianxiang,SONGDunjiang,DUZhengping,etal.ANewMethodofSurfaceModelingandItsApplicationtoDEMConstruction[J].Geomorphology, 2007, 91(12): 164-172.

[7]宋印軍, 岳天祥. 基于多重格網(wǎng)法求解的高精度曲面建模模型[J]. 武漢大學(xué)學(xué)報(信息科學(xué)版), 2009, 34(6): 711-714.

[8]YUETianxiang,SONGDunjiang,DUZhengping,etal.HighAccuracySurfaceModelingandItsApplicationtoDEMGeneration[J].InternationalJournalofRemoteSensing, 2010, 31(8): 2205-2226.

[9]潘松慶, 張學(xué)利. 格網(wǎng)式數(shù)字地形模型追蹤等高點(diǎn)的一種簡易算法[J]. 測繪通報, 2000(1): 29-30.

[10]陳聯(lián). 用薄板樣條函數(shù)建立沙漠地區(qū)的DEM[J]. 地理空間信息, 2005, 3(5): 49-50.

引文格式： 倪曉東，鄒德華，鄧德標(biāo). 薄板樣條函數(shù)支持下的等深線追蹤算法研究[J].測繪通報，2016(1)：132-135.DOI:10.13474/j.cnki.11-2246.2016.0033.

作者簡介：倪曉東(1972—)，男，工程師，主要從事測繪地形與地籍成圖軟件開發(fā)工作。E-mail：xiaodong.ni@southgis.com

收稿日期：2015-04-29

中圖分類號：P208

文獻(xiàn)標(biāo)識碼：B

文章編號：0494-0911(2016)01-0132-04