高 真，葉學義，周天琪，宋倩倩

（杭州電子科技大學通信工程學院，杭州310018）

基于反距離加權插值的水聲數據可視化算法

高 真，葉學義，周天琪，宋倩倩

（杭州電子科技大學通信工程學院，杭州310018）

在使用光線投影法對體數據進行三維重建時，采樣點不一定剛好落在數據點的位置，需要通過插值來計算采樣點的數值。插值方法的選擇直接影響最終的可視化繪制效果。反距離加權插值算法是一種計算相對快速、簡單的插值方法。通過分析三維水聲數據特點，引入反距離加權插值算法，確定插值算法的重要參數搜索半徑和權值下降指數，在搜索半徑確定的球體內對采樣點進行插值，進而得到采樣點的灰度值。使用人工干預實現水聲數據的分層，通過調整插值參數改進繪制質量。實驗結果表明，經過反距離加權插值后的圖像具有較好的繪制效果。關鍵詞：體數據可視化；反距離加權插值；光線投射法；搜素半徑；權值下降指數

1 概述

三維空間數據的可視化是科學計算可視化的核心，體繪制技術是近年來迅速發(fā)展的一種三維數據可視化方法，是當前可視化研究的熱點，具有很大的應用前景廣泛。

體數據可視化利用人眼視覺容易感知的二維圖像展示三維數據的內部特征信息，普遍應用于醫(yī)療衛(wèi)生、地質勘探、氣象預測等與人類生活息息相關的領域。在水聲學領域，利用三維可視化技術，可以構造出三維水聲數據的三維圖像，能夠更加有效地表達數據，對水下目標進行可視化分析。還可以在此基礎上進行一系列的三維交互，對水聲數據做更加準確的分析。

本文通過分析水聲數據的特點和反距離加權插值算法的適用條件，將反距離加權插值應用于水聲數據的插值算法中。首先設置插值參數，即搜索半徑和權值下降指數，然后以搜索半徑確定的球體為搜索域對采樣點進行插值，將插值函數定義為各數據點函數值的加權平均，進而確定采樣點的灰度值。在實驗過程中，通過對水聲數據的不同分層進行分析，調整插值參數，改善繪制效果。

2 背景介紹

目前，醫(yī)學圖像的可視化方法，根據繪制過程的不同可分為2大類：間接繪制和直接繪制方法［1］。間接繪制就是指利用等值面等手段，從三維空間數據場中提取出中間幾何圖元等表征物體的邊界，然后使用傳統(tǒng)的計算機圖形學技術進行繪制，通常稱為面繪制技術。直接體繪制法與面繪制的最大不同就是不需要構造中間幾何圖元，而是直接從三維數據場產生二維圖像，并顯示到屏幕上。所以通常稱為體繪制技術。目前常見的體繪制方法中，根據其算法思想被分為基于圖像空間、基于物體空間和基于硬件設計的紋理映射3類體繪制算法?；趫D像空間的體繪制方法主要是光線投射算法［2-4］。

光線投射法是一種以圖像空間為序的體繪制方法，如圖1（a）所示，它從圖像空間的每一像素出發(fā)，按視線方向發(fā)射一條射線，這條射線穿過三維數據場，沿著這條射線選擇K個等距的采樣點，即重采樣過程。采樣點的值根據數據特征通過插值算法得到，繼而求出該采樣點的不透明度值和顏色值。再將每條射線上各采樣點的顏色值和不透明度值進行合成，即可得到發(fā)出該射線的像素點處的值，從而可以在屏幕上繪制出最終的圖像。從光線投射法的實現方法以及圖1（b）所示的繪制流程可以看出，體繪制主要包括4個步驟：數據預處理，數據分類，數據重采樣和圖像合成。

圖1 體數據光線投射法示意圖及繪制流程

由于通常情況下三維重建的體數據都是離散的，采樣點一般不會正好在數據點的位置，因此必須依靠插值計算來獲取采樣點的數值。在光線投射法中，插值算法就是用來計算光線上采樣點的體數據值。數據重采樣的結果取決于所選取的插值算法，也將直接影響到繪制的速度和最終的繪制質量。因此，插值方法在整個體繪制實現過程中具有重要的地位。

目前在體繪制算法中使用最多的是三線性插值法和加權插值法［5］等。線性插值方法主要以三線性插值為主，并且已經有不錯的繪制效果。本文通過對水聲數據特點的分析，尋找一種新的對規(guī)則體數據的插值方法。反距離加權（Inverse Distance W eight，IDW）插值算法［6］是散點數據中常用的插值算法，并對散點數據的插值起到良好的繪制效果［7］。在研究IDW插值算法之前，首先應該了解它的適用條件：研究對象中的體數據點分布相對較均勻，即沒有局部聚集或者局部稀疏現象。本文研究的水聲數據是規(guī)則的三維數據，數據在三維網格上是均勻分布的，不存在數據局部過于密集和局部過于稀疏的現象。

3 IDW插值

3.1 IDW插值原理

在對體數據進行插值之前，首先定義空間離散數據集的采樣集合S為：

其中，（Pi，fi）與采樣點si一一對應，i=1，2，…，N；Pi∈Rm是m維空間離散數據集中的任一采樣點，當m=2時，數據集為二維空間；當m=3時，數據集為三維空間，即體數據，本文所研究的三維水聲數據就是體數據；fi為所在Pi點的標量值（灰度值）。

IDW插值算法基于相近相似的原理，每個數據點都對插值點有一定的影響，即權重。在進行插值的過程中，權重隨著數據點和插值點之間距離的增加而減小，距離插值點越近的數據點的權重越大，對采樣點的貢獻越大。當數據點在距離插值點一定范圍以外時，權重可以忽略不計。在圖像空間，該性質反映了圖像像素鄰域之間的相關性，通過設置參數，反距離加權插值算法可以控制插值的平滑效應［8］。

IDW的插值結果為選定范圍內各個點的權重之和，其算法原理［9-10］表示如下：

其中，w（χ，Pi）為權值；μ為冪值（也稱權值下降指數），是可調參數；d（χ，Pi）為采樣點χ到搜索域內其他點Pi的歐式距離。

3.2 IDW插值計算

IDW插值方法假定每個輸入點都對采樣點有不同程度的影響，這種影響隨著距離d的增加而減弱。具體實現步驟［11-12］如圖2所示。

圖2 IDW插值算法流程

算法具體執(zhí)行步驟如下：

步驟1 選取插值參數。

對所研究的水聲數據進行數據分析，選取適合于水聲數據插值的參數，主要是對IDW插值算法中的搜索半徑R和權值下降指數μ的選取。

搜索半徑R的選擇：搜索半徑是指搜索參與插值的數值點所需要的鄰域半徑。以待插值點為中心，R為半徑決定的區(qū)域為搜索域。搜索半徑決定了搜索域，搜索域的大小決定了選取數據點的個數，它影響了待插值點的精度和最終圖像的質量。

為了方便說明，以二維數據為例進行說明，如圖3所示。若搜索半徑過大，如圖3中R2，選取的數據點個數多，會降低插值的效率；反之搜索半徑過小，如圖3中R1，選取的數據點個數較少，不足以表現待插值點的真實值，會影響最終繪制結果的質量。因此，搜索半徑既不易選得過大，又不能選得過小。類推到體數據也是同樣的道理。

圖3 搜索半徑R的選擇

由于所研究的水聲數據是三維規(guī)則的體數據，數據不存在局部過于稀疏或者局部過于密集現象。因此整個插值過程可選擇相同的搜索半徑R。

搜索半徑R的選擇不是盲目的。如圖4所示，為保證數據體中每一個采樣點都能夠得到正確的插值結果，應當滿足當采樣點位于體數據相鄰八鄰域的中心（即圖4中的點χ）時也能夠得到正確的插值。χ點的八鄰域即立方體的8個頂點（P1～P8）。那么搜索半徑R應該滿足以下條件：為相鄰像素間的最短距離，例如圖4中一般地，當半徑R＞4r時，搜索域內的點已經達到要求的飽和狀態(tài)?？紤]到插值算法的速度，選擇搜索半徑

圖4 相鄰八鄰域數據體

權值下降指數μ的選擇：反距離加權插值算法影響的權重用點之間距離乘方的倒數表示。乘方為1意味著點之間數值變化率恒定，該方法稱為線性插值法。乘方為2或更高則意味著越靠近已知點，數值的變化率越大；越遠離已知點，數值的變化率趨于平穩(wěn)。因此，當取樣點足夠密時，相比較其他的空間插值算法模型，IDW插值方法采用指數權值對局部變化具有更好的效果。

權值下降指數決定了搜索域內的各個點對待插值點的貢獻值大小。權值下降指數增大，強調距離待插值點近的點對插值點的影響較大，距離較遠影響較小。結合經驗以及通過對實驗結果的分析，可以選擇最佳的權值下降指數。通常情況下μ?。?，3］時，結果較為合理。

步驟2 根據所選取的搜索半徑R確定搜索域，計算采樣點χ到搜索域內所有其他點Pi的歐氏距離d（χ，Pi）。

步驟3 由所選取的權值下降指數μ以及步驟2求得的距離d（χ，Pi），根據式（2）計算每個待插值點的權重w（χ，Pi）。

步驟4 由IDW插值公式（式（1））計算出采樣點最終的插值結果。

采用循環(huán)方式，按照上述計算方法依次求得每一個采樣點的數值。至此，整個插值過程完成。

4 實驗仿真與結果分析

4.1 仿真數據與實驗步驟

實驗采用的數據分別為2組大小是768×300× 41的實測三維水聲數據raw_data和process_data。這2組數據具有不同分層的水體分布，在每個分層中都有疑似目標物存在，是水聲數據處理中比較有代表的水聲數據。其中，raw_data數據是未經過任何處理的原始水聲數據，含有較多的噪聲；process_ data經過了降噪處理，含有的噪聲信號較少。本文所有實驗在一臺W indow s XP系統(tǒng)的PC上進行實驗，電腦的顯示分辨率為1 024×768像素。通過Matlab軟件（Matlab R2008a版本）編程實現IDW插值算法，三維繪制顯示使用VTK技術實現，繪制方法是光線投影法。VTK（Visualization Tool K it）技術是使用Visual Studio 2008編程實現的。VTK是一個開放資源的免費軟件系統(tǒng)，主要用于三維計算機圖形學、圖像處理和可視化，在面向對象原理的基礎上設計和實現，它的內核用C++構建。

分別將2組數據在Matlab中實現IDW插值算法，經過插值后的數據導入VTK中，使用光線投射體繪制算法實現水聲數據的三維重建。在實際編程實現時，通過篩選，搜索半徑選擇R=5 r/2，權值下降指數選擇μ=2進行實驗。

首先對raw_data數據進行實驗，插值過程用時6.59e+3 s。得到的插值前后的結果對比如圖5所示。

圖5 raw_data插值前后重建效果

為了進一步觀察效果，將圖5的2幅圖像相同地方（水體不同分層中的疑似目標物）進行局部放大后觀察插值效果。為了比較插值前后各個部位的繪制效果，可以通過調整VTK的視角進行觀察對比。本文給出的是視角為0°（圖6）和～-30°（圖7）時的繪制結果。

圖6 raw_data插值前后局部放大對照（0°）

圖7 raw_data插值前后局部放大對照（-30°）

由圖6和圖7的局部放大結果可以看出，經過IDW插值后的效果圖紋理較清晰，水聲數據中不同分層的交界處的噪聲明顯減少，并且疑似目標物較清晰，具有良好的效果。但是，對于水聲數據上層中的目標似乎有削弱的現象，其噪聲有所增加。

對process_data數據進行插值實驗，插值過程用時6.49e+3 s。插值前后的實驗結果對比如圖8所示。同樣為了觀察效果，調整VTK的觀察視角為45°。

圖8 Process_data插值前后重建效果

將圖8的2幅圖像相同地方（水體不同分層的交界面）進行局部放大后觀察插值效果，如圖9所示。其中，圖9（a）是經過IDW插值前的效果，圖9（b）是插值后的效果。由對比結果可以看出，經過IDW插值后的效果圖紋理較清晰，水聲數據中的疑似目標物相對較明顯，具有良好的繪制效果。

圖9 Process_data插值前后局部放大對照

4.2 實驗結果分析與改進

經過上述實驗和分析，發(fā)現采用相同的實驗參數進行繪制時，對水聲數據下層的繪制質量較好，疑似目標物也較清晰。但是，對于水聲數據上層的繪制效果欠佳，尤其是當數據本身噪聲較多時，會影響繪制的質量?？紤]實際，水體數據上層相對清澈，因此數據灰度相近，此時采用過大的搜索半徑或過小的權值下降指數均會導致水體數據的噪聲增加，這是由水體中本身存在的噪聲決定的。raw_data數據本身的噪聲比process_data中的噪聲大，因此重建后的噪聲更明顯?？紤]采用對水聲數據的不同分層分別采用不同的參數進行實驗。

由于本文在實驗過程中還不具備對水聲數據的不同分層進行自動分層的能力，因此僅是在提高視覺效果上，采用人工參與的方式對水聲數據進行分層。由以上繪制結果可知，對數據進行上下水體分層。

對分層后的數據選擇不同的實驗參數重新進行實驗，水聲數據的下層數據選擇參數不變，水聲數據的上層數據選擇參數經過實驗最終選擇如表1所示。

表1 最佳參數選取結果

插值過程用時6.71e+3 s。實驗結果如圖10所示。其中，圖10（a）是插值前的效果，圖10（b）是采用不同參數進行插值后的效果。

由圖10結果可以看出，采用實驗獲得的最佳參數選擇結果分別對水聲數據的不同分層采用不同的參數設置，得出的結果較使用相同參數時的效果好。水聲數據上層的噪聲沒有明顯增加，下層數據也得到了良好的繪制效果。并且水聲數據中不同分層中的目標相對較清晰，具有很好的繪制效果，明顯提高了繪制質量。繪制效果有如此大的區(qū)別主要是由于本文的水聲數據的特點造成的。

圖10 改變參數后的插值前后局部放大效果

由于上層水體相比較下層水體較清澈，水中含有較少的泥沙以及其他各種雜質的存在。如果選擇與下層含有較多雜質的水體一致的參數，就會造成水聲數據噪聲的增加。因此，當選擇不同參數進行實驗時就會收到更好的繪制效果。

5 結束語

插值計算在水聲數據可視化過程中具有十分重要的作用。本文根據水聲數據的特征分析，引入具有計算快速、簡單的反距離加權插值算法，提出了一種基于IDW插值的水聲數據可視化方法，即采用IDW插值方法對體數據進行插值，并將該方法應用于水聲數據的三維重建當中。首先對數據進行分析，選擇合適的插值參數，主要是搜索半徑和權值下降指數2個參數的選擇。然后，根據所選參數對水聲數據進行插值計算，求得采樣點的數值。最后，應用VTK實現水聲數據的三維重建。在對實驗結果進行分析的基礎上，發(fā)現采用相同的參數處理數據時，對不同分層的水聲數據繪制效果不同。考慮水聲數據某一部分分層數據的灰度值相近的因素，對算法進行改進。通過人工參與的方式對水聲數據進行分層，對水聲數據的不同分層采用不同的參數，改善繪制效果。實驗結果表明，經過IDW插值后的圖像較插值前具有較好的繪制質量。通過設置不同的插值參數，繪制結果又得到了進一步的改善。因此，本文方法對三維水聲數據的重建具有較好的繪制效果，減少了噪聲，使繪制結果的疑似目標更加突出清晰。

［1］ 田 玲.基于體繪制的三維數據場可視化技術研究［D］.成都：西南交通大學，2007.

［2］ 周志光，陶煜波，林 海.基于視覺感知增強的最大密度投影算法［J］.軟件學報，2013，24（3）：639-650.

［3］ 鄭 遲.體繪制采樣方法研究［D］.杭州：浙江工業(yè)大學，2012.

［4］ 唐澤圣，袁 駿.用圖像空間為序的體繪制技術顯示三維數據場［J］.計算機學報，1994，17（11）：801-808.

［5］ Walia E，Singh C.An Analysis of Linear and Non-linear Interpolation Techniques for Three Dimensional Rendering［C］//Proceedings of New Trends Conference on Geometric Modeling and Imaging.Washington D.C.，USA：IEEE Press，2006：69-76.

［6］ Tomczak M.Spatial Interpolation and Its Uncertainty Using Autom ated Anisotropic Inverse Distance Weighting-cross Validation/Jackknife Approach［J］. Journal of Geographic Inform ation and Decision Analysis，1998，2（2）：18-30.

［7］ Falch T L，Elster A C，Floystad J B，et al.GPU-accelerated Visualization of Scattered Point Data［J］. IEEE Access，2013，1：566-568.

［8］ 鄧 彩.圖像插值算法研究［D］.重慶：重慶大學，2011.

［9］ 周 敏，黃 芳.IDW在醫(yī)學斷層圖像可視化中的應用［J］.計算機系統(tǒng)應用，2009，18（10）：160-163.

［10］ 趙曉捷，穆 冬，薛斌黨.反距離加權插值自適應圖像直方圖均衡化算法［J］.中國體視學與圖像分析，2012，15（1）：8-11.

［11］ Yucel M，Orm eci C.Land Surface Tem perature Based Spatial Interpolation Using a Modified Inverse Distance Weighting Method［EB/OL］.（2013-08-04）.http：//en. wikipedia.org/w iki/Inverse_distance_w eighting.

［12］ Lu G Y，W ong D W.An Adaptive Inverse-distance Weighting Spatial Interpolation Technique［J］. Computers&Geosciences，2008，34（9）：1044-1055.

編輯 顧逸斐

Visualization Algorithm of Underwater Acoustic Data Based on Inverse Distance W eight InterPolation

GAO Zhen，YE Xueyi，ZHOU Tianqi，SONG Qianqian
（College of Comm unication Engineering，Hangzhou Dianzi University，Hangzhou 310018，China）

In the use of ray casting algorithm for 3-d reconstruction of volume data，the samp ling point w ill not necessarily fall in the location of the data point.So interpolation is needed for the values of sampling points.The choice of interpolation method directly affects the rendering quality.Inverse Distance Weight（IDW）interpolation algorithm is a relatively fast and simple interpolation method.In this paper，through the analysis of the characteristics of underwater acoustic data，a method using the inverse distance weight interpolation for volume data is proposed.The important parameters of the interpolation algorithm，the search radius and power exponent are selected.Interpolate in the sphere is determined by the search radius.The grey value of the sampling point is calculated.It also layers the acoustic data by manual operation.And the different layer parameters of underwater acoustic data are parameters with different parameters to get better results.Experimental results show that the image with inverse distance weight interpolation has better rending quality than before.

volume data visualization；Inverse Distance Weight（IDW）interpolation；ray casting method；search radius；weight drop exponent

高 真，葉學義，周天琪，等.基于反距離加權插值的水聲數據可視化算法［J］.計算機工程，2015，41（9）：266-270，275.

英文引用格式：Gao Zhen，Ye Xueyi，Zhou Tianqi，et al.Visualization Algorithm of Underwater Acoustic Data Based on Inverse Distance W eight Interpolation［J］.Computer Engineering，2015，41（9）：266-270，275.

1000-3428（2015）09-0266-05

A

TP301.6

10.3969/j.issn.1000-3428.2015.09.049

國家自然科學基金青年基金資助項目（60802047）。

高 真（1989-），女，碩士研究生，主研方向：水聲數據可視化；葉學義，副教授；周天琪、宋倩倩，碩士研究生。

2014-07-31

2014-10-08 E-m ail：youlan0510@163.com