1 何为插值

插值（Interpolation）就是一种通过已知的、离散的数据点，在范围内推求新数据点的过程或方法。这听起来可能有些官方，你可以想象下这样一个场景：当你放大（或缩小）一幅图像时，你会怎么做？脑海里可能会有一个色块“过渡”或者说“渐变”的过程，那具体又是如何"过渡"的呢？💭

2 三种方法

图像放大就是对原图像进行上采样的过程，涉及到从一个图像创建另一个图像。每个图像具有不同的空间几何形状。假设 $\bm I$ 是一个大小为 $R_{in}\times C_{in}$

对于输入图像 $\bm I$ 中的每一个像素 $\bm I(r,c)$

对于输出图像 $\bm J$ 中的每一个像素 $\bm J(r,c)$

很显然，第一种前向映射会导致输出图像 $\bm J$ 中的一些像素位置为空；而第二种后向映射的方法则不会产生这种问题，但是我们需要用插值法来计算“亚像素”位置的像素值。

如同前面所假设一致， $\bm I$ 是一个大小为 $R_{in}\times C_{in}$

$S_R=\frac{R_{out}}{R_{in}},\quad S_C=\frac{C_{out}}{C_{in}}$

如图 2.1 所示，点 $\bm I(r_f,c_f)$

图 2.1：反向映射点 $\bm I(r_f,c_f)$

下面是三种不同的插值方法示意图：最近邻、双线性以及双立方（2D）。

2.1 最近邻插值（NN）

最近邻算法是像素复制和抽取的推广。最近邻插值算法选择距离所求数据点最近点的值，并且根本不考虑其他相邻点的值，从而产生一个分段常数的内插值来作为所求数据点的值。

如图 2.1 所示，最近邻算法就是将点 $\bm I(r_f,c_f)$

2.2 双线性插值（Bilinear）

双线性插值，又称为双线性内插。在数学上，双线性插值是对线性插值在二维直角网格上的扩展，用于对双变量函数（例如 $x$ 和 $y$ ）进行插值。其核心思想是在两个方向分别进行一次线性插值。

如图 2.1 所示， $r_0=\lfloor r_f \rfloor\text{，}c_0=\lfloor c_f \rfloor\text{，}\Delta r=r_f-r_0\text{，}\Delta c=c_f-c_0$

$\begin{aligned} \bm J(r,c)={} & \bm I(r_0,c_0)\cdot(1-\Delta r)\cdot(1-\Delta c)+\bm I(r_0+1,c_0)\cdot\Delta r\cdot(1-\Delta c)\\\\ {} & +\bm I(r_0,c_0+1)\cdot(1-\Delta r)\cdot\Delta c+\bm I(r_0+1,c_0+1)\cdot\Delta r\cdot\Delta c. \end{aligned}$

考虑到如同最近邻插值中描述的， $\bm I(r_0,c_0)$

2.3 双立方插值（Bicubic）

在数值分析这个数学分支中，双三次插值是二维空间中最常用的插值方法。在这种方法中，函数 $f$ 在点 $(x, y)$

三次卷积算法中 $W$ 是一个三次Hermite样条曲线：

$\begin{aligned} W(x)=\begin{cases} (a+2)|x|^3-(a+3)|x|^2+1 & \text{for}\quad |x|\leq 1, \\ a|x|^3-5a|x|^2+8a|x|-4a & \text{for}\quad 1<|x|\leq 2, \\ 0 & \text{otherwise,} \end{cases} \end{aligned}$

其中， $a$ 通常设置 $-0.5$ 或 $-0.75$ 。当 $a=-0.5$

$\begin{aligned} p(d;I_{\mathfrak{R}(r|c)})=\frac{1}{2}\begin{bmatrix} 1 & d & d^2 & d^3 \end{bmatrix}\begin{bmatrix} 0 & 2 & 0 & 0 \\ -1 & 0 & 1 & 0 \\ 2 & -5 & 4 & -1 \\ -1 & 3 & -3 & 1 \\ \end{bmatrix} \begin{bmatrix} I_{-1} \\ I_{0} \\ I_{1} \\ I_{2} \\ \end{bmatrix} \end{aligned}$

在像素 $\bm I(r,c)$

$d=r_f-r,\quad I_{-1}=\bm I(r-1,c),\quad I_0=\bm I(r,c),\quad I_1=\bm I(r+1,c),\quad I_2=\bm I(r+2,c).$

当沿行进行卷积时，

$d=c_f-c,\quad I_{-1}=\bm I(r,c-1),\quad I_0=\bm I(r,c),\quad I_1=\bm I(r,c+1),\quad I_2=\bm I(r,c+2).$

如果多项式 $p$ 先按照列进行然后再进行行计算（与图 2.4 类似），那么输出图像像素 $\bm J(r,c)$

$\begin{aligned} K_{-1}=& p\left(d_r;\begin{bmatrix} \bm I(r-1,c-1) & \bm I(r,c-1) &\bm I(r+1,c-1) &\bm I(r+2,c-1) \end{bmatrix}^{T}\right),\\\\ K_{0}=& p\left(d_r;\begin{bmatrix} \bm I(r-1,c) & \bm I(r,c) &\bm I(r+1,c) &\bm I(r+2,c) \end{bmatrix}^{T}\right),\\\\ K_{1}=& p\left(d_r;\begin{bmatrix} \bm I(r-1,c+1) & \bm I(r,c+1) &\bm I(r+1,c+1) &\bm I(r+2,c+1) \end{bmatrix}^{T}\right),\\\\ K_{2}=& p\left(d_r;\begin{bmatrix} \bm I(r-1,c+2) & \bm I(r,c+2) &\bm I(r+1,c+2) &\bm I(r+2,c+2) \end{bmatrix}^{T}\right),\\\\ \bm J(r,c)=&p\left(dc;\begin{bmatrix} K_{-1} & K_0 &K_1& K_2 \end{bmatrix}^{T}\right). \end{aligned}$

其中 $dr=r_f-r\text{，}dc=c_f-c$

3 MATLAB实现

三种插值方法的实现都是基于MATLAB语言实现，这里给出三种方法的核心代码。

3.1 最近邻

最近邻的实现不需要对输入图像进行填充，核心代码如下所示。

% 双重for循环
for cou1 = 1:x_new
    for cou2 = 1:y_new
        % 取最近的点，实际上用ceil更合适，而非round,同时解决了边界范围问题
        % 映射点落在哪个像素就用哪个像素，也符合最近邻的思想
        M(cou1,cou2) = I(ceil(cou1./x_scale),ceil(cou2./y_scale));
3.2 双线性
  双线性的实现也可以不用对输入图像进行填充，实现的效果类似当输出图像反向映射到输入图像最外周时，就让这点作为输出图像的像素值。核心代码如下所示。
for cou1 = 0:x_new-1
    for cou2 = 0:y_new-1
        % 输出图像映射到输入图像的亚像素位置
        o1=cou1./x_scale;
        o2=cou2./y_scale;
        % 计算因子
        W = 1-o1+floor(o1);
        H = 1-o2+floor(o2);
        % 周围4个点
        I11 = I(1+floor(o1),1+floor(o2));
        I12 = I(1+ceil(o1),1+floor(o2));
        I21 = I(1+floor(o1),1+ceil(o2));
        I22 = I(1+ceil(o1),1+ceil(o2));
        % 计算公式
        M(cou1+1,cou2+1) = (1-W).*(1-H).*I22 + (W).*(1-H).*I21 + (1-W).*(H).*I12 + (W).*(H).*I11;
3.3 双立方
  双立方插值的实现对输入图像进行填充，然后如节2.3所述方法计算即可，核心代码如下。
for row=1:x_new
    for column=1:y_new
        % 先沿列计算
        for m=0:3
            K(m+1)=p(dr(row),I_pad((r0(row):r0(row)+3),c0(column)+m)); 
        % 再按照行计算输出像素值
        M(row,column)=p(dc(column),K);
4 结果示例与比较
为了比较算法实现的效果如何，本文对一系列经典图片进行测试并与MATLAB的函数imresize做了比较，主要通过计算本文实现结果和imreszie的结果的相似度来衡量实现的效果。
4.1 结果示例
  本文只给出了部分示例结果（原始图像放大3倍），如下所示。对于此类自然图像，整体看起来三种方法效果差不多，但是看细节还是有所区别的（当然在这里是看不出来的🙃）。
5 算法评价
就最近邻插值的实现而言，效果还不错，至少在 SSIM 值的表现上与 imresize 的结果保持着高度相似。最近邻的插值图像实则复制像素，它的的边缘更清晰，但大部分图像为块状，锯齿感较强。
关于双线性插值，它的实现效果与最近邻比较差点，而且在它的效果还与图片的内容有所关联。双线性插值的边缘易模糊，但大多数图像更平滑，整体看起来好。
双立方被认为是放大图像的最佳插值方法，MATLAB中函数imresize的默认方法也是bicubic。但本文实现的方法在放大倍数较大时程序运行耗时较长，这是一个缺点。
6 参考文献
[1] Giassa M. Upsampling Interpolation.

[2] EECE_4353_15_Resampling.pdf
这里非整数的像素位置称为“亚像素"。 ↩︎