反距离加权

反距离加权(英语:inverse distance weightingIDW)是一种在有已知的离散数据点的情形下进行多元插值英语Multivariate interpolation确定性算法。赋给未知点的值是用已知点的值的加权平均数计算得出的。该算法也可在空间自相关分析(例如莫兰指数)中用于构建空间权重矩阵。[1]

该方法的名称来自其加权的方式:未知点到每个已知点的距离的倒数。

问题的定义

对于给定的离散数据点,我们希望以一个函数 对研究区域进行插值:

 

其中 是研究区域。

 个已知数据点可以视为元组列表:

 

该函数应当是“平滑的”(连续且一次可微),确定的( ),并满足用户对研究的现象的直观预期。此外,该功能应能够以合理成本在电脑应用上实现(如今,基本实现方法中可能会用到并行计算)。

谢泼德法(Shepard's method)

历史参考

自1965年起,在哈佛计算机图形和空间分析实验室,各专业的科学家汇聚一堂,重新思考现在称作“地理信息系统”的各种问题。[2]

实验室工作的推动者霍华德·费舍尔(Howard Fisher)构思了一种改良的计算机绘图程序:SYMAP,其设计伊始,费舍尔就希望对插值进行改进。他向哈佛大学新生展示了SYMAP的进展,而后许多新生参与了实验室活动。一位大一新生唐纳德·谢泼德(Donald Shepard)决定对SYMAP中的插值法进行大改,随后发表了他1968年的著名论文。[3]

谢泼德的算法也受到William Warntz和实验室其他从事空间分析工作的人的理论方法的影响。他用距离的指数进行了许多实验,决定更接近重力模型(-2的指数)。谢泼德不仅实现了基本的反距离加权,还允许障碍(包括可渗透的和绝对的)插值。

其他研究机构此时也在研究插值,特别是堪萨斯大学及其SURFACE II计划。但SYMAP的功能仍是最先进的,尽管是由本科生编写的。

基本形式

 
来自表面上的散点在不同幂参数p下的谢泼德插值 

给定一组样本点 ,反距离加权插值函数 定义为:

 

其中

 

这是一个简单的反距离加权函数,其定义由谢泼德提出,[3]x表示一个被插值点(未知点),xi表示一个节点(已知点), 是从已知点xi到未知点x的给定距离(度规算符),N是插值中使用的已知点的总数,并且 是一个正实数,称为幂参数。

其中,权重随着与已知点的距离的增加而减小。 值越大,则最邻近已知点的对插值的影响越大,当 足够大时,插值结果形似马赛克多边形(沃罗诺伊图),每一个多边形内的数值几乎为恒定值。对于二维面,幂参数 时,插值由距离较远的点主导,因为密度为 、邻近节点距离为  之间的数据点集,权重的加和约为

 

其在  时发散。对于M维,同样的结论适用于 。对于 值的选择,可以考虑插值中所需的平滑程度、被插值的样本密度和分布,以及允许单个样本影响周围样本的最大距离。

谢泼德法是最小化与插值点{x, u}的元组和插值点{xi, ui}的i元组之间的偏差度量相关的函数的结果,定义为:

 

从最小化条件导出:

 

该方法容易扩展到其他数的空间,它实际上是将拉格朗日插值法推广到多维空间。为三元插值设计的修改版算法由Robert J. Renka提出,Netlib的toms库中的算法661提供该算法。

一维下的示例

 
Shepard法在一个维度下的插值,基于4个样本数据点,p = 2

调整谢泼德法

谢泼德法的另一个修改版是仅使用半径R范围内的最近邻(而不是完整样本)来计算插值。在这种情况下,权重略有修改:

 

当与快速空间搜索结构(如k-d树)结合使用时,它即为适用于大尺度问题的高效N log N插值方法。

参见

参考文献

  1. ^ Spatial Autocorrelation (Global Moran's I) (Spatial Statistics). ArcGIS Pro Documentation. ESRI. [13 September 2022]. (原始内容存档于2022-10-31). 
  2. ^ Chrisman, Nicholas. History of the Harvard Laboratory for Computer Graphics: a Poster Exhibit (PDF). 
  3. ^ 3.0 3.1 Shepard, Donald. A two-dimensional interpolation function for irregularly-spaced data. Proceedings of the 1968 ACM National Conference: 517–524. 1968. doi:10.1145/800186.810616.