基于反距离加权插值的水声数据可视化算法

高 真，叶学义，周天琪，宋倩倩

（杭州电子科技大学通信工程学院，杭州310018）

基于反距离加权插值的水声数据可视化算法

高 真，叶学义，周天琪，宋倩倩

（杭州电子科技大学通信工程学院，杭州310018）

在使用光线投影法对体数据进行三维重建时，采样点不一定刚好落在数据点的位置，需要通过插值来计算采样点的数值。插值方法的选择直接影响最终的可视化绘制效果。反距离加权插值算法是一种计算相对快速、简单的插值方法。通过分析三维水声数据特点，引入反距离加权插值算法，确定插值算法的重要参数搜索半径和权值下降指数，在搜索半径确定的球体内对采样点进行插值，进而得到采样点的灰度值。使用人工干预实现水声数据的分层，通过调整插值参数改进绘制质量。实验结果表明，经过反距离加权插值后的图像具有较好的绘制效果。关键词：体数据可视化；反距离加权插值；光线投射法；搜素半径；权值下降指数

1 概述

三维空间数据的可视化是科学计算可视化的核心，体绘制技术是近年来迅速发展的一种三维数据可视化方法，是当前可视化研究的热点，具有很大的应用前景广泛。

体数据可视化利用人眼视觉容易感知的二维图像展示三维数据的内部特征信息，普遍应用于医疗卫生、地质勘探、气象预测等与人类生活息息相关的领域。在水声学领域，利用三维可视化技术，可以构造出三维水声数据的三维图像，能够更加有效地表达数据，对水下目标进行可视化分析。还可以在此基础上进行一系列的三维交互，对水声数据做更加准确的分析。

本文通过分析水声数据的特点和反距离加权插值算法的适用条件，将反距离加权插值应用于水声数据的插值算法中。首先设置插值参数，即搜索半径和权值下降指数，然后以搜索半径确定的球体为搜索域对采样点进行插值，将插值函数定义为各数据点函数值的加权平均，进而确定采样点的灰度值。在实验过程中，通过对水声数据的不同分层进行分析，调整插值参数，改善绘制效果。

2 背景介绍

目前，医学图像的可视化方法，根据绘制过程的不同可分为2大类：间接绘制和直接绘制方法［1］。间接绘制就是指利用等值面等手段，从三维空间数据场中提取出中间几何图元等表征物体的边界，然后使用传统的计算机图形学技术进行绘制，通常称为面绘制技术。直接体绘制法与面绘制的最大不同就是不需要构造中间几何图元，而是直接从三维数据场产生二维图像，并显示到屏幕上。所以通常称为体绘制技术。目前常见的体绘制方法中，根据其算法思想被分为基于图像空间、基于物体空间和基于硬件设计的纹理映射3类体绘制算法。基于图像空间的体绘制方法主要是光线投射算法［2-4］。

光线投射法是一种以图像空间为序的体绘制方法，如图1（a）所示，它从图像空间的每一像素出发，按视线方向发射一条射线，这条射线穿过三维数据场，沿着这条射线选择K个等距的采样点，即重采样过程。采样点的值根据数据特征通过插值算法得到，继而求出该采样点的不透明度值和颜色值。再将每条射线上各采样点的颜色值和不透明度值进行合成，即可得到发出该射线的像素点处的值，从而可以在屏幕上绘制出最终的图像。从光线投射法的实现方法以及图1（b）所示的绘制流程可以看出，体绘制主要包括4个步骤：数据预处理，数据分类，数据重采样和图像合成。

图1 体数据光线投射法示意图及绘制流程

由于通常情况下三维重建的体数据都是离散的，采样点一般不会正好在数据点的位置，因此必须依靠插值计算来获取采样点的数值。在光线投射法中，插值算法就是用来计算光线上采样点的体数据值。数据重采样的结果取决于所选取的插值算法，也将直接影响到绘制的速度和最终的绘制质量。因此，插值方法在整个体绘制实现过程中具有重要的地位。

目前在体绘制算法中使用最多的是三线性插值法和加权插值法［5］等。线性插值方法主要以三线性插值为主，并且已经有不错的绘制效果。本文通过对水声数据特点的分析，寻找一种新的对规则体数据的插值方法。反距离加权（Inverse Distance W eight，IDW）插值算法［6］是散点数据中常用的插值算法，并对散点数据的插值起到良好的绘制效果［7］。在研究IDW插值算法之前，首先应该了解它的适用条件：研究对象中的体数据点分布相对较均匀，即没有局部聚集或者局部稀疏现象。本文研究的水声数据是规则的三维数据，数据在三维网格上是均匀分布的，不存在数据局部过于密集和局部过于稀疏的现象。

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插值算法流程

算法具体执行步骤如下：

步骤1 选取插值参数。

对所研究的水声数据进行数据分析，选取适合于水声数据插值的参数，主要是对IDW插值算法中的搜索半径R和权值下降指数μ的选取。

搜索半径R的选择：搜索半径是指搜索参与插值的数值点所需要的邻域半径。以待插值点为中心，R为半径决定的区域为搜索域。搜索半径决定了搜索域，搜索域的大小决定了选取数据点的个数，它影响了待插值点的精度和最终图像的质量。

为了方便说明，以二维数据为例进行说明，如图3所示。若搜索半径过大，如图3中R2，选取的数据点个数多，会降低插值的效率；反之搜索半径过小，如图3中R1，选取的数据点个数较少，不足以表现待插值点的真实值，会影响最终绘制结果的质量。因此，搜索半径既不易选得过大，又不能选得过小。类推到体数据也是同样的道理。

图3 搜索半径R的选择

由于所研究的水声数据是三维规则的体数据，数据不存在局部过于稀疏或者局部过于密集现象。因此整个插值过程可选择相同的搜索半径R。

搜索半径R的选择不是盲目的。如图4所示，为保证数据体中每一个采样点都能够得到正确的插值结果，应当满足当采样点位于体数据相邻八邻域的中心（即图4中的点χ）时也能够得到正确的插值。χ点的八邻域即立方体的8个顶点（P1～P8）。那么搜索半径R应该满足以下条件：为相邻像素间的最短距离，例如图4中一般地，当半径R＞4r时，搜索域内的点已经达到要求的饱和状态。考虑到插值算法的速度，选择搜索半径

图4 相邻八邻域数据体

权值下降指数μ的选择：反距离加权插值算法影响的权重用点之间距离乘方的倒数表示。乘方为1意味着点之间数值变化率恒定，该方法称为线性插值法。乘方为2或更高则意味着越靠近已知点，数值的变化率越大；越远离已知点，数值的变化率趋于平稳。因此，当取样点足够密时，相比较其他的空间插值算法模型，IDW插值方法采用指数权值对局部变化具有更好的效果。

权值下降指数决定了搜索域内的各个点对待插值点的贡献值大小。权值下降指数增大，强调距离待插值点近的点对插值点的影响较大，距离较远影响较小。结合经验以及通过对实验结果的分析，可以选择最佳的权值下降指数。通常情况下μ取［1，3］时，结果较为合理。

步骤2 根据所选取的搜索半径R确定搜索域，计算采样点χ到搜索域内所有其他点Pi的欧氏距离d（χ，Pi）。

步骤3 由所选取的权值下降指数μ以及步骤2求得的距离d（χ，Pi），根据式（2）计算每个待插值点的权重w（χ，Pi）。

步骤4 由IDW插值公式（式（1））计算出采样点最终的插值结果。

采用循环方式，按照上述计算方法依次求得每一个采样点的数值。至此，整个插值过程完成。

4 实验仿真与结果分析

4.1 仿真数据与实验步骤

实验采用的数据分别为2组大小是768×300× 41的实测三维水声数据raw_data和process_data。这2组数据具有不同分层的水体分布，在每个分层中都有疑似目标物存在，是水声数据处理中比较有代表的水声数据。其中，raw_data数据是未经过任何处理的原始水声数据，含有较多的噪声；process_ data经过了降噪处理，含有的噪声信号较少。本文所有实验在一台W indow s XP系统的PC上进行实验，电脑的显示分辨率为1 024×768像素。通过Matlab软件（Matlab R2008a版本）编程实现IDW插值算法，三维绘制显示使用VTK技术实现，绘制方法是光线投影法。VTK（Visualization Tool K it）技术是使用Visual Studio 2008编程实现的。VTK是一个开放资源的免费软件系统，主要用于三维计算机图形学、图像处理和可视化，在面向对象原理的基础上设计和实现，它的内核用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 实验结果分析与改进

经过上述实验和分析，发现采用相同的实验参数进行绘制时，对水声数据下层的绘制质量较好，疑似目标物也较清晰。但是，对于水声数据上层的绘制效果欠佳，尤其是当数据本身噪声较多时，会影响绘制的质量。考虑实际，水体数据上层相对清澈，因此数据灰度相近，此时采用过大的搜索半径或过小的权值下降指数均会导致水体数据的噪声增加，这是由水体中本身存在的噪声决定的。raw_data数据本身的噪声比process_data中的噪声大，因此重建后的噪声更明显。考虑采用对水声数据的不同分层分别采用不同的参数进行实验。

由于本文在实验过程中还不具备对水声数据的不同分层进行自动分层的能力，因此仅是在提高视觉效果上，采用人工参与的方式对水声数据进行分层。由以上绘制结果可知，对数据进行上下水体分层。

对分层后的数据选择不同的实验参数重新进行实验，水声数据的下层数据选择参数不变，水声数据的上层数据选择参数经过实验最终选择如表1所示。

表1 最佳参数选取结果

插值过程用时6.71e+3 s。实验结果如图10所示。其中，图10（a）是插值前的效果，图10（b）是采用不同参数进行插值后的效果。

由图10结果可以看出，采用实验获得的最佳参数选择结果分别对水声数据的不同分层采用不同的参数设置，得出的结果较使用相同参数时的效果好。水声数据上层的噪声没有明显增加，下层数据也得到了良好的绘制效果。并且水声数据中不同分层中的目标相对较清晰，具有很好的绘制效果，明显提高了绘制质量。绘制效果有如此大的区别主要是由于本文的水声数据的特点造成的。

图10 改变参数后的插值前后局部放大效果

由于上层水体相比较下层水体较清澈，水中含有较少的泥沙以及其他各种杂质的存在。如果选择与下层含有较多杂质的水体一致的参数，就会造成水声数据噪声的增加。因此，当选择不同参数进行实验时就会收到更好的绘制效果。

5 结束语

插值计算在水声数据可视化过程中具有十分重要的作用。本文根据水声数据的特征分析，引入具有计算快速、简单的反距离加权插值算法，提出了一种基于IDW插值的水声数据可视化方法，即采用IDW插值方法对体数据进行插值，并将该方法应用于水声数据的三维重建当中。首先对数据进行分析，选择合适的插值参数，主要是搜索半径和权值下降指数2个参数的选择。然后，根据所选参数对水声数据进行插值计算，求得采样点的数值。最后，应用VTK实现水声数据的三维重建。在对实验结果进行分析的基础上，发现采用相同的参数处理数据时，对不同分层的水声数据绘制效果不同。考虑水声数据某一部分分层数据的灰度值相近的因素，对算法进行改进。通过人工参与的方式对水声数据进行分层，对水声数据的不同分层采用不同的参数，改善绘制效果。实验结果表明，经过IDW插值后的图像较插值前具有较好的绘制质量。通过设置不同的插值参数，绘制结果又得到了进一步的改善。因此，本文方法对三维水声数据的重建具有较好的绘制效果，减少了噪声，使绘制结果的疑似目标更加突出清晰。

［1］ 田 玲.基于体绘制的三维数据场可视化技术研究［D］.成都：西南交通大学，2007.

［2］ 周志光，陶煜波，林 海.基于视觉感知增强的最大密度投影算法［J］.软件学报，2013，24（3）：639-650.

［3］ 郑 迟.体绘制采样方法研究［D］.杭州：浙江工业大学，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在医学断层图像可视化中的应用［J］.计算机系统应用，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