基于三角剖分與質(zhì)心原理的三維插值方法對比

朱佩婕

摘 要 本文針對空間三維體插值加密與成像問題，進(jìn)行建模、求解和相關(guān)分析并給出兩種解題方法及其優(yōu)劣對比。

關(guān)鍵詞 Delaunay三角剖分 質(zhì)心原理 三維插值 矩陣變換

中圖分類號：TP301.6 文獻(xiàn)標(biāo)識碼：A DOI：10.16400/j.cnki.kjdks.2016.12.015

Abstract In this paper， based on the three-dimensional interpolation and imaging of three-dimensional interpolation problems， modeling， solving and related analysis and give the two methods and their advantages and disadvantages.

Keywords Delaunay； Triangular subdivision； Centroid principle； three dimensional interpolation； Matrix transformation

第一種方法是根據(jù)分段插值的原理，采用基于Delaunay三角剖分的三維插值算法進(jìn)行求解；為了減小距離所求點(diǎn)較遠(yuǎn)的點(diǎn)插值時因增加插值次數(shù)而導(dǎo)致龍格現(xiàn)象，本文所給出的第二種方法是基于質(zhì)心原理的三維插值算法，有效減小節(jié)點(diǎn)間的函數(shù)震蕩，相較于普通的插值方法具有更好的收斂效果。

1 問題重述

1.1 問題背景

在實(shí)際的科研或工程研究中，常常需要在已有數(shù)據(jù)點(diǎn)的情況下獲得這些數(shù)據(jù)點(diǎn)之間的中間點(diǎn)的數(shù)據(jù)，就需要使用不同的插值方法進(jìn)行數(shù)據(jù)插值，而對數(shù)據(jù)的插值加密與成像問題，因?yàn)橐獙Ψ彪s大量的數(shù)據(jù)進(jìn)行插值處理以及涉及部分?jǐn)?shù)字圖像的相關(guān)處理，所以在生活以及軍工業(yè)方面具有十分重要的現(xiàn)實(shí)意義與研究價值。

1.2 待解決的問題

在以上提及的背景，有4851組相關(guān)數(shù)據(jù)有待解決：根據(jù)所給的4851組數(shù)據(jù)的特點(diǎn)，建立兩種適當(dāng)?shù)臄?shù)學(xué)模型，保證用該方法插值計(jì)算后電阻率數(shù)據(jù)的極值及其對應(yīng)的位置不發(fā)生改變，并計(jì)算空間點(diǎn)所對應(yīng)的電阻率數(shù)值。

2 模型假設(shè)

（1）數(shù)據(jù)真實(shí)可靠；

（2）電阻率不隨各類外部因素發(fā)生改變；

（3）三維物體具有各向同性。

3 模型建立與求解

3.1 問題分析

要求我們根據(jù)文本中所給的4851組數(shù)據(jù)，使用兩種適當(dāng)?shù)牟逯涤?jì)算方法計(jì)算出空間中某點(diǎn)處所對應(yīng)的電阻率值并說明該方法插值后所得到的電阻率數(shù)據(jù)極值大小與位置不變。由于題中所給的條件限制，因極值的大小和位置不能發(fā)生改變，若直接采用普通的Lagrange、Newton和Hermite插值時，當(dāng)所選取的節(jié)點(diǎn)個數(shù)較多，插值多項(xiàng)式的次數(shù)會相應(yīng)提高，會出現(xiàn)龍格現(xiàn)象。因此針對這種情況，本文給出了兩種方法求解。

3.2 基于Delaunay三角剖分的三維插值計(jì)算方法

Delaunay三角剖分過程中采用Bowyer-Watson算法，其基本步驟為：（1）構(gòu)造一個大三角形，包含所有散點(diǎn)，放入三角形鏈表；（2）將點(diǎn)集中的散點(diǎn)依次插入，在三角形鏈表中找出外接圓包含插入點(diǎn)的三角形（稱為該點(diǎn)的影響三角形），刪除影響三角形的公共邊，將插入點(diǎn)都影響三角形的全部頂點(diǎn)連接起來，完成一個點(diǎn)在Delaunay三角形鏈表中的插入；（3）根據(jù)優(yōu)化準(zhǔn)則對局部新形成的三角形優(yōu)化，將形成的三角形放入Delaunay三角形鏈表；（4）循環(huán)執(zhí)行上述第2步，直到所有散點(diǎn)插入完畢。

以上計(jì)算過程可通過Matlab中的griddata函數(shù)所實(shí)現(xiàn)，其計(jì)算公式如下所示：

以下為方便敘述，使用“方法一”代指基于Delaunay三角剖分的三維插值算法。

3.3 基于質(zhì)心原理的三維插值計(jì)算方法

本方法首先選取所給數(shù)據(jù)中距離待求點(diǎn)（'，'，'）最近的八個節(jié)點(diǎn)及其函數(shù)值，如表1所示：

其中八個節(jié)點(diǎn)和是方向上與'的前后間距，和是方向上與'的前后間距，和是方向上與'的前后間距。由質(zhì)心原理，設(shè)點(diǎn)（'，'，'）到各節(jié)點(diǎn)的權(quán)重因子分別為、、、、、、和。

以下為方便敘述，使用“方法二”代指基于質(zhì)心原理的三維插值計(jì)算方法。

4 模型評價與推廣

4.1 模型評價

4.1.1 優(yōu)點(diǎn)

（1）在方法一中，根據(jù)分段插值的原理，采用基于Delaunay 三角剖分的三維插值算法進(jìn)行求解，先將原始數(shù)據(jù)進(jìn)行插值處理，再將循環(huán)所得的點(diǎn)所對應(yīng)的坐標(biāo)（或要求點(diǎn)的坐標(biāo)）寫入Matlab中，運(yùn)用Matlab內(nèi)置的griddata函數(shù)對各點(diǎn)進(jìn)行插值插值運(yùn)算。根據(jù)問題二的復(fù)雜性評估和定量分析易看出：方法一平均值與標(biāo)準(zhǔn)差的大小更接近原始數(shù)據(jù)且模型簡單易懂，Matlab中有內(nèi)置函數(shù)griddata便捷了此法的運(yùn)算實(shí)現(xiàn)。問題四的相關(guān)數(shù)據(jù)更是能夠清晰地反映方法一與原始數(shù)據(jù)的近似度較高；

（2）在方法二中，基于質(zhì)心原理的三維插值算法，讀入循環(huán)所所得的點(diǎn)所對應(yīng)的坐標(biāo)（或要求點(diǎn)的坐標(biāo)），在待求點(diǎn)附近尋找距離其最近的8個節(jié)點(diǎn)，代入公式進(jìn)行計(jì)算（通過Codeblocks編程實(shí)現(xiàn)）。根據(jù)問題二的復(fù)雜性評估和定量分析易看出：方法二運(yùn)行時間較短，為方法一的近10倍，而且從數(shù)據(jù)結(jié)果可看出，方法二的精確度可達(dá)小數(shù)點(diǎn)后12位，較高。

4.1.2 不足

（1）方法一運(yùn)用Matlab實(shí)現(xiàn)算法，耗時較長，占用計(jì)算機(jī)內(nèi)存較大，對計(jì)算機(jī)配置有一定要求，并且數(shù)據(jù)結(jié)果的精確度低于方法二；

（2）方法二運(yùn)用Codeblocks實(shí)現(xiàn)算法，時間短、精確度高，但是與原始數(shù)據(jù)的相似性劣于方法一。

4.2 模型的推廣

采用圖像插值技術(shù)來提高數(shù)字圖像的分辨率和清晰度，從軟件方面進(jìn)行改進(jìn)具有十分重要的實(shí)用價值，以及用于遙感圖像的幾何校正、醫(yī)學(xué)城鄉(xiāng)以及電影、電視和媒體廣告等影像特技處理中。

應(yīng)用插值加密的方法處理圖像示例圖如圖2：上圖為放大圖片后的結(jié)果，易看出馬賽克色塊且清晰度較低；下圖為插值加密處理后的圖像，圖片清晰度明顯提高。

參考文獻(xiàn)

[1] 楊盛林，劉昱，劉玉峰.慣性平臺熱場分析及熱設(shè)計(jì)的改進(jìn)[J].中國慣性技術(shù)學(xué)報(bào)，2005.13（1）：5-9.

[2] 王瑾.基于強(qiáng)對流數(shù)值模擬的貴州冰雹識別及臨近預(yù)報(bào)方法研究[D].中國科學(xué)院博士論文，2009.

[3] 肖艷嬌.新一代天氣雷達(dá)三維組網(wǎng)技術(shù)及應(yīng)用研究[D].南京信息工程大學(xué)博士論文，2007.

[4] 徐恭學(xué)，李玉忱.一種優(yōu)化的光線投射體繪制采樣算法[J].廈門大學(xué)學(xué)報(bào)（自然科學(xué)版），1997.36（1）：27-32.

[5] Sicot O，Gong X L， Cherouat A， et al. Influence of residual stresses on the mechanical behavior of composite laminatematerials[J].Advanced Composite Materials，2005.14（4）：319-342.