我有一个稀疏的数组,如下所示。是否有一种算法可以用线性有意义的值填充所有空白? IE。从周围的原始值推导出来。
我研究过双线性插值和双三次插值,但还有其他插值吗?
| 1 | 2 | 3 | 4 | 5 | 6 | 7
---------------------------------------------------------------------------------
1 |
2 |
3 | 55
4 | 50 12 6
5 | 45 19
6 | xxx
7 | 35 45 50 yyy
8 |
9 |
10 |
11 |
12 | zzz
13 |
14 |
15 |
例如,我预计 xxx 会在 40 附近,yyy 会在 50 附近。但是 zzz 可能有一个更随机的值。但请注意:我想填充每个空格,而不仅仅是 xxx、yyy 和 zzz。并且能够对任何稀疏的数组执行此操作。
这样的算法存在吗?
存在一百万个这样的算法。所以首先你有一些已知值的字典,如下所示:
known_values = {
(2, 3): 55.0,
(2, 4): 50.0,
(2, 5): 45.0,
(2, 7): 35.0,
(3, 7): 45.0,
(4, 7): 50.0,
(6, 4): 12.0,
(7, 4): 6.0,
(7, 5): 19.0,
}
最简单的方法是任意点的值是所有填充点的加权平均值。其权重为 1/距离的平方。所以在上面的例子中,你会有这样的代码:
def interpolate(known_values, p):
total_weight = 0.0
total_sum = 0.0
for q, value in known_values:
if p == q:
return value
d_square = (p[0] - q[0])**2 + (p[1] - q[1])**2
total_weight = total_weight + 1.0 / d_square
total_sum = total_sum + value / d_square
return total_sum/total_weight
只要矩阵填充了任何数据,该解决方案就可以工作。
但是从您提出问题的方式来看,您可能需要一个在任何小区域中近似线性的平滑插值。一种方法是寻找
(a, b, c)
,使得函数 a*x + b*y + c
最小化误差平方的加权和,权重是从所需点到已知点的距离的 4 次方。 (前 2 次幂消除了面积的平方,另外两次幂附近的点权重更大。)
这里使用最小二乘法来计算误差的原因是数学计算起来很简单。当
a
、b
或 c
的微小变化不会使值发生太大变化时,您将精确最小化,这意味着偏导数为 0。因此,这三个偏导数为您提供了 3 组线性方程。求解 3 个变量的 3 个方程相当容易。
然而,推导过程又长又乱。如果你想尝试一下,你应该看看通常的最小二乘推导,并尝试解决细节。然后尝试去实现它。但只有当您真的想尝试对远离数据的点进行线性投影时才可以尝试。
这个问题可以被视为“二元插值”问题,并且该领域有大量的研究。您可以在 Wiki 中搜索“多元插值”并在“二维”部分下查找算法。
在各种方法中,双线性/双三次插值需要数据形成网格,而您的数据则不是这样的。 Delaunay 三角测量方法不适合根据您的情况进行外推。反加权距离方法易于实现,适合外推,但结果往往不令人满意。我个人建议使用径向基函数,只要您没有太多数据点(例如数千个)。
GitHub上有一个解决方案,使用的是薄板样条方法: