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

朱佩婕

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

關鍵詞 Delaunay三角剖分 質心原理 三維插值 矩陣變換

中圖分類號：TP301.6 文獻標識碼：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

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

1 問題重述

1.1 問題背景

在實際的科研或工程研究中，常常需要在已有數據點的情況下獲得這些數據點之間的中間點的數據，就需要使用不同的插值方法進行數據插值，而對數據的插值加密與成像問題，因為要對繁雜大量的數據進行插值處理以及涉及部分數字圖像的相關處理，所以在生活以及軍工業方面具有十分重要的現實意義與研究價值。

1.2 待解決的問題

在以上提及的背景，有4851組相關數據有待解決：根據所給的4851組數據的特點，建立兩種適當的數學模型，保證用該方法插值計算后電阻率數據的極值及其對應的位置不發生改變，并計算空間點所對應的電阻率數值。

2 模型假設

（1）數據真實可靠；

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

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

3 模型建立與求解

3.1 問題分析

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

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

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

以上計算過程可通過Matlab中的griddata函數所實現，其計算公式如下所示：

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

3.3 基于質心原理的三維插值計算方法

本方法首先選取所給數據中距離待求點（'，'，'）最近的八個節點及其函數值，如表1所示：

其中八個節點和是方向上與'的前后間距，和是方向上與'的前后間距，和是方向上與'的前后間距。由質心原理，設點（'，'，'）到各節點的權重因子分別為、、、、、、和。

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

4 模型評價與推廣

4.1 模型評價

4.1.1 優點

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

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

4.1.2 不足

（1）方法一運用Matlab實現算法，耗時較長，占用計算機內存較大，對計算機配置有一定要求，并且數據結果的精確度低于方法二；

（2）方法二運用Codeblocks實現算法，時間短、精確度高，但是與原始數據的相似性劣于方法一。

4.2 模型的推廣

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

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

參考文獻

[1] 楊盛林，劉昱，劉玉峰.慣性平臺熱場分析及熱設計的改進[J].中國慣性技術學報，2005.13（1）：5-9.

[2] 王瑾.基于強對流數值模擬的貴州冰雹識別及臨近預報方法研究[D].中國科學院博士論文，2009.

[3] 肖艷嬌.新一代天氣雷達三維組網技術及應用研究[D].南京信息工程大學博士論文，2007.

[4] 徐恭學，李玉忱.一種優化的光線投射體繪制采樣算法[J].廈門大學學報（自然科學版），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.