python - 如何在 Python 中执行双线性插值

Question

我想使用 python 执行 blinear 插值。
我要插入高度的示例 gps 点是：

B = 54.4786674627
L = 17.0470721369

使用具有已知坐标和高度值的四个相邻点：

n = [(54.5, 17.041667, 31.993), (54.5, 17.083333, 31.911), (54.458333, 17.041667, 31.945), (54.458333, 17.083333, 31.866)]

z01    z11

     z
z00    z10

这是我的原始尝试：

import math
z00 = n[0][2]
z01 = n[1][2]
z10 = n[2][2]
z11 = n[3][2]
c = 0.016667 #grid spacing
x0 = 56 #latitude of origin of grid
y0 = 13 #longitude of origin of grid
i = math.floor((L-y0)/c)
j = math.floor((B-x0)/c)
t = (B - x0)/c - j
z0 = (1-t)*z00 + t*z10
z1 = (1-t)*z01 + t*z11
s = (L-y0)/c - i
z = (1-s)*z0 + s*z1

其中 z0 和 z1

z01  z0  z11

     z
z00  z1   z10

我得到 31.964，但从其他软件我得到 31.961。
我的脚本正确吗？
你能提供另一种方法吗？

2022 年编辑：
我要感谢所有在这个问题发表十多年后给出新答案的人。

Answer 1

这是您可以使用的可重用函数。它包括文档测试和数据验证：

def bilinear_interpolation(x, y, points):
    '''Interpolate (x,y) from values associated with four points.

    The four points are a list of four triplets:  (x, y, value).
    The four points can be in any order.  They should form a rectangle.

        >>> bilinear_interpolation(12, 5.5,
        ...                        [(10, 4, 100),
        ...                         (20, 4, 200),
        ...                         (10, 6, 150),
        ...                         (20, 6, 300)])
        165.0

    '''
    # See formula at:  http://en.wikipedia.org/wiki/Bilinear_interpolation

    points = sorted(points)               # order points by x, then by y
    (x1, y1, q11), (_x1, y2, q12), (x2, _y1, q21), (_x2, _y2, q22) = points

    if x1 != _x1 or x2 != _x2 or y1 != _y1 or y2 != _y2:
        raise ValueError('points do not form a rectangle')
    if not x1 <= x <= x2 or not y1 <= y <= y2:
        raise ValueError('(x, y) not within the rectangle')

    return (q11 * (x2 - x) * (y2 - y) +
            q21 * (x - x1) * (y2 - y) +
            q12 * (x2 - x) * (y - y1) +
            q22 * (x - x1) * (y - y1)
           ) / ((x2 - x1) * (y2 - y1) + 0.0)

您可以通过添加以下内容来运行测试代码：

if __name__ == '__main__':
    import doctest
    doctest.testmod()

在数据集上运行插值会产生：

>>> n = [(54.5, 17.041667, 31.993),
         (54.5, 17.083333, 31.911),
         (54.458333, 17.041667, 31.945),
         (54.458333, 17.083333, 31.866),
    ]
>>> bilinear_interpolation(54.4786674627, 17.0470721369, n)
31.95798688313631

Answer 2

不确定这是否有很大帮助，但是在使用 scipy 进行线性插值时我得到了不同的值：

>>> import numpy as np
>>> from scipy.interpolate import griddata
>>> n = np.array([(54.5, 17.041667, 31.993),
                  (54.5, 17.083333, 31.911),
                  (54.458333, 17.041667, 31.945),
                  (54.458333, 17.083333, 31.866)])
>>> griddata(n[:,0:2], n[:,2], [(54.4786674627, 17.0470721369)], method='linear')
array([ 31.95817681])

Answer 3

从这里受到启发，我想出了以下代码片段。该 API 针对多次重复使用同一张表进行了优化：

from bisect import bisect_left

class BilinearInterpolation(object):
    """ Bilinear interpolation. """
    def __init__(self, x_index, y_index, values):
        self.x_index = x_index
        self.y_index = y_index
        self.values = values

    def __call__(self, x, y):
        # local lookups
        x_index, y_index, values = self.x_index, self.y_index, self.values

        i = bisect_left(x_index, x) - 1
        j = bisect_left(y_index, y) - 1

        x1, x2 = x_index[i:i + 2]
        y1, y2 = y_index[j:j + 2]
        z11, z12 = values[j][i:i + 2]
        z21, z22 = values[j + 1][i:i + 2]

        return (z11 * (x2 - x) * (y2 - y) +
                z21 * (x - x1) * (y2 - y) +
                z12 * (x2 - x) * (y - y1) +
                z22 * (x - x1) * (y - y1)) / ((x2 - x1) * (y2 - y1))

你可以像这样使用它：

table = BilinearInterpolation(
    x_index=(54.458333, 54.5), 
    y_index=(17.041667, 17.083333), 
    values=((31.945, 31.866), (31.993, 31.911))
)

print(table(54.4786674627, 17.0470721369))
# 31.957986883136307

这个版本没有错误检查，如果你试图在索引的边界（或超出）使用它，你会遇到麻烦。有关完整版本的代码，包括错误检查和可选外推，请查看此处。

Answer 4

您也可以参考matplotlib 中的 interp 函数。

Answer 5

基于此公式的 numpy 实现：

def bilinear_interpolation(x,y,x_,y_,val):

    a = 1 /((x_[1] - x_[0]) * (y_[1] - y_[0]))
    xx = np.array([[x_[1]-x],[x-x_[0]]],dtype='float32')
    f = np.array(val).reshape(2,2)
    yy = np.array([[y_[1]-y],[y-y_[0]]],dtype='float32')
    b = np.matmul(f,yy)

    return a * np.matmul(xx.T, b)

输入：这里，x_是列表，[x0,x1]是y_列表[y0,y1]

bilinear_interpolation(x=54.4786674627,
                       y=17.0470721369,
                       x_=[54.458333,54.5],
                       y_=[17.041667,17.083333],
                       val=[31.993,31.911,31.945,31.866])

输出：

array([[31.95912739]])

Answer 6

我认为做一个floor函数的重点是，通常你希望插入一个坐标位于两个离散坐标之间的值。但是，您似乎已经有了最近点的实际坐标值，这使得数学变得简单。

z00 = n[0][2]
z01 = n[1][2]
z10 = n[2][2]
z11 = n[3][2]

# Let's assume L is your x-coordinate and B is the Y-coordinate

dx = n[2][0] - n[0][0] # The x-gap between your sample points
dy = n[1][1] - n[0][1] # The Y-gap between your sample points

dx1 = (L - n[0][0]) / dx # How close is your point to the left?
dx2 = 1 - dx1              # How close is your point to the right?
dy1 = (B - n[0][1]) / dy # How close is your point to the bottom?
dy2 = 1 - dy1              # How close is your point to the top?

left = (z00 * dy1) + (z01 * dy2)   # First interpolate along the y-axis
right = (z10 * dy1) + (z11 * dy2)

z = (left * dx1) + (right * dx2)   # Then along the x-axis

从您的示例进行翻译时可能存在一些错误的逻辑，但其要点是您可以根据每个点与插值目标点​​的距离比其其他邻居更近来对每个点进行加权。

Answer 7

这与此处定义的解决方案相同，但适用于某些功能并与interp2dScipy 中的可用解决方案进行比较。我们使用 numba 库使插值函数比 Scipy 实现更快。

import numpy as np
from scipy.interpolate import interp2d
import matplotlib.pyplot as plt

from numba import jit, prange
@jit(nopython=True, fastmath=True, nogil=True, cache=True, parallel=True)
def bilinear_interpolation(x_in, y_in, f_in, x_out, y_out):
    f_out = np.zeros((y_out.size, x_out.size))
    
    for i in prange(f_out.shape[1]):
        idx = np.searchsorted(x_in, x_out[i])
        
        x1 = x_in[idx-1]
        x2 = x_in[idx]
        x = x_out[i]
        
        for j in prange(f_out.shape[0]):
            idy = np.searchsorted(y_in, y_out[j])
            y1 = y_in[idy-1]
            y2 = y_in[idy]
            y = y_out[j]

            
            f11 = f_in[idy-1, idx-1]
            f21 = f_in[idy-1, idx]
            f12 = f_in[idy, idx-1]
            f22 = f_in[idy, idx]
            

            
            f_out[j, i] = ((f11 * (x2 - x) * (y2 - y) +
                            f21 * (x - x1) * (y2 - y) +
                            f12 * (x2 - x) * (y - y1) +
                            f22 * (x - x1) * (y - y1)) /
                           ((x2 - x1) * (y2 - y1)))
    
    return f_out

我们把它做成一个相当大的插值数组来评估每种方法的性能。

样本函数是，

x = np.linspace(0, 4, 13)
y = np.array([0, 2, 3, 3.5, 3.75, 3.875, 3.9375, 4])
X, Y = np.meshgrid(x, y)
Z = np.sin(np.pi*X/2) * np.exp(Y/2)

x2 = np.linspace(0, 4, 1000)
y2 = np.linspace(0, 4, 1000)
Z2 = bilinear_interpolation(x, y, Z, x2, y2)

fun = interp2d(x, y, Z, kind='linear')
Z3 = fun(x2, y2)


fig, ax = plt.subplots(nrows=1, ncols=3, figsize=(10, 6))
ax[0].pcolormesh(X, Y, Z, shading='auto')
ax[0].set_title("Original function")
X2, Y2 = np.meshgrid(x2, y2)
ax[1].pcolormesh(X2, Y2, Z2, shading='auto')
ax[1].set_title("bilinear interpolation")

ax[2].pcolormesh(X2, Y2, Z3, shading='auto')
ax[2].set_title("Scipy bilinear function")

plt.show()

性能测试

没有 numba 库的 Python

bilinear_interpolation在这种情况下，函数与numba版本相同，只是我们在 for 循环中prange使用 python normal进行更改，并删除函数装饰器rangejit

%timeit bilinear_interpolation(x, y, Z, x2, y2)

每个循环给出 7.15 秒 ± 107 毫秒（平均值 ± 标准偏差。7 次运行，每个循环 1 个）

Python 与 numba numba

%timeit bilinear_interpolation(x, y, Z, x2, y2) 

每个循环给出 2.65 ms ± 70.5 µs（平均值 ± 标准偏差。7 次运行，每次 100 个循环）

Scipy 实现

%%timeit
f = interp2d(x, y, Z, kind='linear')
Z2 = f(x2, y2)

每个循环给出 6.63 ms ± 145 µs（平均值 ± 标准偏差。7 次运行，每次 100 个循环）

性能测试在“Intel(R) Core(TM) i7-8700K CPU @ 3.70GHz”上进行

Answer 8

我建议以下解决方案：

def bilinear_interpolation(x, y, z01, z11, z00, z10):

    def linear_interpolation(x, z0, z1):
        return z0 * x + z1 * (1 - x)

    return linear_interpolation(y, linear_interpolation(x, z01, z11),
                                   linear_interpolation(x, z00, z10))