CV笔记2：图像插值算法—最近邻插值双线性插值

一、简介

在图像处理中，平移变换、旋转变换以及放缩变换是一些基础且常用的操作。这些几何变换并不改变图象的象素值，只是在图象平面上进行象素的重新排列。在一幅输入图象[u，v]中，灰度值仅在整数位置上有定义。然而，输出图象[x，y]的灰度值一般由处在非整数坐标上的（u，v）值来决定。这就需要插值算法来进行处理，常见的插值算法有最近邻插值、双线性插值和三次样条插值。

二、最近邻插值

最近邻插值，是指将目标图像中的点，对应到源图像中后，找到最相邻的整数点，作为插值后的输出。

如上图所示，目标图像中的某点投影到原图像中的位置为点P,此时易知，f(P) = f(Q11).

举个栗子：

举个简单的图像：3*3 的256级灰度图。假如图像的象素矩阵如下图所示（这个原始图把它叫做源图，Source）：

这个矩阵中，元素坐标(x,y)是这样确定的，x从左到右，从0开始，y从上到下，也是从零开始，这是图象处理中最常用的坐标系。

如果想把这副图放大为 4*4大小的图像，那么该怎么做呢？那么第一步肯定想到的是先把4*4的矩阵先画出来再说，好了矩阵画出来了，如下所示，当然，矩阵的每个像素都是未知数，等待着我们去填充（这个将要被填充的图的叫做目标图,Destination）：

? ? ? ?

然后要往这个空的矩阵里面填值了，要填的值从哪里来呢？是从源图中来，好，先填写目标图最左上角的象素，坐标为（0，0），那么该坐标对应源图中的坐标可以由如下公式得出

srcX=dstX* (srcWidth/dstWidth) ,

srcY = dstY * (srcHeight/dstHeight)，

其中dst表示目标图，src表示源图（该公式相当于分别在x，y方向位置进行线性插值，找到目标图像中的每一个像素点来源于源图的哪个点）

好了，套用公式，就可以找到对应的原图的坐标了(0*(3/4),0*(3/4))=>(0*0.75,0*0.75)=>(0,0)，找到了源图的对应坐标,就可以把源图中坐标为(0,0)处的56象素值填进去目标图的(0,0)这个位置了。

接下来,如法炮制,寻找目标图中坐标为(1,0)的象素对应源图中的坐标,套用公式:

(1*0.75,0*0.75)=>(0.75,0) 结果发现,得到的坐标里面竟然有小数,这可怎么办?计算机里的图像可是数字图像,象素就是最小单位了,象素的坐标都是整数,从来没有小数坐标。这时候采用的一种策略就是采用四舍五入的方法（也可以采用直接舍掉小数位的方法），把非整数坐标转换成整数，好，那么按照四舍五入的方法就得到坐标（1，0），完整的运算过程就是这样的：(1*0.75,0*0.75)=>(0.75,0)=>(1,0) 那么就可以再填一个象素到目标矩阵中了，同样是把源图中坐标为(1,0)处的像素值38填入目标图中的坐标。

依次填完每个象素，一幅放大后的图像就诞生了，像素矩阵如下所示：

对上述的过程进行简单总结，就是针对目标图像中的每一个像素点f(x, y),寻找源图像中的对应的最近邻的像素点：

三、双线性插值

双线性插值是是一种比较好的图像缩放算法，它充分的利用了源图中虚拟点四周的四个真实存在的像素值来共同决定目标图中的一个像素值，因此缩放效果比简单的最邻近插值要好很多。双线性插值就是线性插值在二维时的推广，所以从线性插值开始讲起。

3.1 线性插值

线性插值多项式为：

即我们通过一些已知点，如下图中的（x0, y0）和（x1, y1）,找到该线性插值多项式，之后每给定一个x，我们就可以通过该多项式计算出来一个对应的y值。

线性插值推导公式为：

3.2 双线性插值

通过已知的单位正方形顶点确定的双线性插值多项式为：

其推导通过结合图像处理进行说明。

在图像处理中，双线性插值可以描述为：

对于一个目标像素（位于目标图像），设此像素坐标通过反向变换得到的浮点坐标为(i+u,j+v) (其中i、j均为浮点坐标的整数部分，u、v为浮点坐标的小数部分，是取值[0,1)区间的浮点数，位于源图像)，则这个像素的值 f(i+u,j+v) 可由原图像中坐标为 (i,j)、(i+1,j)、(i,j+1)、(i+1,j+1)所对应的周围四个像素的值决定，即：f(i+u,j+v) = (1-u)(1-v)f(i,j) + (1-u)vf(i,j+1) + u(1-v)f(i+1,j) + uvf(i+1,j+1)，其中f(i,j)表示源图像(i,j)处的的像素值，以此类推。

通过上图进行简单的推导，对于坐标 (i, j+v)，f(i, j) 到 f(i, j+1) 的灰度变化为线性关系，对(i, j) 和(i, j+1)进行线性插值，则有：

f(i, j+v) = [f(i, j+1) - f(i, j)] * v + f(i, j)

同理对于 (i+1, j+v) 则有：

f(i+1, j+v) = [f(i+1, j+1) - f(i+1, j)] * v + f(i+1, j)

从f(i, j+v) 到 f(i+1, j+v) 的灰度变化也为线性关系，对(i, j+v) 和(i+1, j+v)进行线性插值，由此可推导出待求象素灰度的计算式如下：

f(i+u, j+v) = (1-u) * (1-v) * f(i, j) + (1-u) * v * f(i, j+1) + u * (1-v) * f(i+1, j) + u * v * f(i+1, j+1)

再通过二维坐标进行理解一下双线性插值：

假设我们已知函数 f 在Q11= (x1,y1)、Q12= (x1,y2),Q21= (x2,y1) 以及Q22= (x2,y2) 四个点的值，求 f 在在点P = (x,y) 处的值。

首先在x方向进行线性插值，得到

然后在y 方向进行线性插值，得到

这样就得到所要的结果f (x,y)，

回到图像处理上面，我们仍然使用上节中的例子，现在假如目标图的象素坐标为（1，1），那么反推得到的对应于源图的坐标是（0.75 , 0.75）, 这其实只是一个概念上的虚拟像素坐标,实际在源图中并不存在这样一个坐标,那么目标图的坐标（1，1）的像素取值不能够由这个虚拟像素坐标来决定，而只能由源图的以下四个坐标中的像素共同决定：（0，0）（0，1）（1，0）（1，1），而由于（0.75,0.75）离（1，1）要更近一些，那么（1,1）所起的决定作用更大一些，这从公式1中的系数uv=0.75×0.75就可以体现出来，而（0.75,0.75）离（0，0）最远，所以（0，0）所起的决定作用就要小一些，公式中系数为(1-u)(1-v)=0.25×0.25也体现出了这一特点。

在图像处理的时候，我们先根据

srcX=dstX* (srcWidth/dstWidth) ,

srcY = dstY * (srcHeight/dstHeight)

来计算目标像素在源图像中的位置，这里计算的srcX和srcY一般都是浮点数，比如f（1.2, 3.4）这个像素点是虚拟存在的，先找到与它临近的四个实际存在的像素点

（1，3）（2，3）

（1，4）（2，4）

写成f(i+u,j+v)的形式，则u=0.2,v=0.4, i=1, j=3

在沿着X方向差插值时，f(R1)=u(f(Q21)-f(Q11))+f(Q11)

沿着Y方向同理计算。

或者，直接整理一步计算，f(i+u,j+v) = (1-u)(1-v)f(i,j) + (1-u)vf(i,j+1) + u(1-v)f(i+1,j) + uvf(i+1,j+1)

3.3 双线性插值的加速及优化策略

单纯按照上文实现的插值算法只能勉强完成插值的功能，速度和效果都不会理想，在具体代码实现的时候有些小技巧。参考OpenCV源码以及网上博客整理如下两点：

源图像和目标图像几何中心的对齐。将浮点运算转换成整数运算

源图像和目标图像几何中心的对齐

方法：在计算源图像的虚拟浮点坐标的时候，一般情况：

srcX=dstX* (srcWidth/dstWidth) ,

srcY = dstY * (srcHeight/dstHeight)

中心对齐(OpenCV也是如此)：

SrcX=(dstX+0.5)* (srcWidth/dstWidth) -0.5

SrcY=(dstY+0.5) * (srcHeight/dstHeight)-0.5

原理：

双线性插值算法及需要注意事项这篇博客解释说“如果选择右上角为原点（0，0），那么最右边和最下边的像素实际上并没有参与计算，而且目标图像的每个像素点计算出的灰度值也相对于源图像偏左偏上。”有点保持疑问。

将公式变形，srcX=dstX* (srcWidth/dstWidth)+0.5*(srcWidth/dstWidth-1)

相当于我们在原始的浮点坐标上加上了0.5*(srcWidth/dstWidth-1)这样一个控制因子，这项的符号可正可负，与srcWidth/dstWidth的比值也就是当前插值是扩大还是缩小图像有关，有什么作用呢？看一个例子：假设源图像是3*3，中心点坐标（1，1）目标图像是9*9，中心点坐标（4，4），我们在进行插值映射的时候，尽可能希望均匀的用到源图像的像素信息，最直观的就是（4,4）映射到（1,1）现在直接计算srcX=4*3/9=1.3333！=1，也就是我们在插值的时候所利用的像素集中在图像的右下方，而不是均匀分布整个图像。现在考虑中心点对齐，srcX=(4+0.5)*3/9-0.5=1，刚好满足我们的要求。

将浮点运算转换成整数运算

参考图像处理界双线性插值算法的优化

直接进行计算的话，由于计算的srcX和srcY 都是浮点数，后续会进行大量的乘法，而图像数据量又大，速度不会理想，解决思路是：浮点运算→→整数运算→→”<<左右移按位运算”。

放大的主要对象是u，v这些浮点数，OpenCV选择的放大倍数是2048“如何取这个合适的放大倍数呢，要从三个方面考虑，第一：精度问题，如果这个数取得过小，那么经过计算后可能会导致结果出现较大的误差。第二，这个数不能太大，太大会导致计算过程超过长整形所能表达的范围。第三：速度考虑。假如放大倍数取为12，那么算式在最后的结果中应该需要除以12*12=144，但是如果取为16，则最后的除数为16*16=256，这个数字好，我们可以用右移来实现，而右移要比普通的整除快多了。”我们利用左移11位操作就可以达到放大目的。