栅格与线性插值
栅格对于搞机器人的朋友们而言应该很熟悉了，它是我们数字化描述周围世界的主要手段之一。 图像、占用栅格地图都是典型的栅格应用。 栅格毕竟是一种离散化的表述方法，它在描述周围连续的物理世界时多少有些局限。对于一幅图像而言，它可以直接告诉我们第\(i\)行，第\(j\)列的像素值是多少。 但假如我们需要对一个像素进一步细分成\(10 \times 10\)的小栅格，那么这些小栅格对应的值应该是多少呢？确定这些小栅格取值的过程可以说是一种插值的过程。
稍微形式化一点来说，插值就是在一个规则分布的栅格空间中，估计栅格中任意一点的取值。通常我们用点来抽象地表示空间中的某个具体位置， 认为栅格空间中相邻两个单元\(p_0, p_1\)之间某点的取值可以由参数方程\(f(p_0, p_1, u), u \in [0, 1]\)给出。根据参数方程的形式，可以有很多中不同的插值方法，比如多项式插值、 三角函数插值等等。
本文所讨论的线性插值是阶次为1的多项式插值方法。根据栅格空间的维度不同，本文将分别讨论线性插值、双线性插值、三线性插值。
1. 线性插值(linear interpolation)
如右图所示，给定空间中两个点\(\boldsymbol{p_0}, \boldsymbol{p_1}\)，它们的连线可以看作是一个动点\(\boldsymbol{p}\)，从起点\(\boldsymbol{p_0}\)运动到终点\(\boldsymbol{p_1}\)扫过的轨迹。 矢量\(\boldsymbol{p} - \boldsymbol{p_0}\)与矢量\(\boldsymbol{p_1} - \boldsymbol{p}\)之间存在如下的比例关系，我们可以用一个关于参数\(u \in [0, 1]\)的函数来表示这个轨迹\(\boldsymbol{p}(u)\)。 当 \(u\) 从 0 连续变化到 1 时，所扫出来的轨迹就是连接\(\boldsymbol{p_0}\)和\(\boldsymbol{p_1}\)的直线段。
$$ \begin{align} \frac{\boldsymbol{p} - \boldsymbol{p_0}}{\boldsymbol{p_1} - \boldsymbol{p}} & = \frac{u}{1 - u} , & u \in [0, 1] \\ \boldsymbol{p} - \boldsymbol{p_0} & = u (\boldsymbol{p_1} - \boldsymbol{p_0}) , & u \in [0, 1] \\ \boldsymbol{p}(u) & = \boldsymbol{p_0} + u (\boldsymbol{p_1} - \boldsymbol{p_0}) , & u \in [0, 1] \\ \boldsymbol{p}(u) & = (1 - u)\boldsymbol{p_0} + u \boldsymbol{p_1} , & u \in [0, 1] \\ \end{align} $$上式中多项式 \(u\) 只有一次，所以我们称之为线性插值。
在参数多项式中，可以定义高次的直线。如果有参数 \(t \in [0, 1]\) 满足关系 \(u = t^2\)，那么上式就可以写出一个关于 \(t\) 的二次多项式 \(\boldsymbol{p}(t) = (1 - t^2)\boldsymbol{p_0} + t^2 \boldsymbol{p_1}\)。