|
原理
线性插值并不难理解。以图像处理领域为例，我们的理想图像是均匀的分布在二维平面直角坐标系中的，任意给出一对坐标，就应该能够得到一个对应的颜色值，然而现实是残酷的，我们只能够用离散的点阵信息来近似表现图像。 现在假设给定一对坐标（2.2, 4.0），想要得到这个坐标对应的颜色，那么比较简单的方法是用四舍五入方法来得到距离该点最近的像素，即像素(2, 4)的值来代替，这显然并不十分的精确，如果用这个方法进行图像放大，那么在比例较大的情况下就会出现明显的“马赛克”现象。 对于上面的例子，更好的办法是把像素(2, 4)和像素(3, 4)的值按照一定的比例混合。比例如何选取呢？很简单，离哪个像素近，哪个像素的比例就大些。那么（简单起见，后面均假设是灰度图），若设像素(2, 4)的值是V_24，像素(3, 4)的值是V_34，就可以得到：
好，现在你已经懂得什么叫线性插值了! 二次线性插值也就不难理解了。这次我们给的坐标不再是那么体贴了——求坐标(2.2, 4.6)的颜色值。那么可以想到：可以先分别求出坐标(2.2, 4.0)和坐标(2.2, 5.0)的颜色值，然后用一次纵向的线型插值，就得到了：
到这里，实际上我们已经得到了二次线性插值的计算公式，表述方便起见下面用符号来表示。 设坐标(x, y)的相邻四个像素值分别为p00, p01, p10, p11, 水平方向的比例系数为h0, h1, 垂直方向的比例系数v0, v1（其中h0+h1=1, v0+v1=1），那么用bilinear interpolation得到：
有了这个公式，已经可以编写出算法了，但是这个公式里有六次浮点乘法，如果是真彩图的话，则对每一像素都要有18次浮点乘法！这还不算生成浮点坐标值的时间（比如在旋转算法当中，每得到一对浮点坐标还要有若干次浮点运算）。 优化 学过一些线性代数知识的朋友可能已经注意到，公式(1.1)其实可以写成矩阵连乘的形式： |p00 p01| |h0| v(x, y) = |v0 v1|*| |*| | ................................(1.2) |p10 p11| |h1| 那么我们就可以利用矩阵相乘的运算法则来优化算法。首先，这里的运算瓶颈是v0, v1, h0, h1这四个浮点值带来的，而实际上我们需要这么高的精度吗？p00, p01, p10, p11以及我们的运算结果都是整数（对于我们的情况，是0-255之间的整数）。也就是说，其实把我们的结果最后赋值给v(x, y)时，小数部分已经被截掉了，我们根本用不到那么高的精度！那么我们可以尝试用整数乘法代替浮点乘法。 比如，令V0 = (int)(v0*65536.0+0.5)，V1 = 65536-V0，H0 = (int)(h0*65536.0+0.5), H1 = 65536-H0，那么有： |p00 p01| |H0| v(x, y)*65536*65536 = |V0 V1|*| |*| | ....................(1.3) |p10 p11| |H1| 计算出(1.3)式右边的值，左边就可以用右移来代替除法计算出v(x, y)的值。当然实际实现算法的时候，这个公式是一定会溢出的，因为有符号整数的最大值不过是+(32768*65536-1)，所以可以在运算中间过程中就进行移位运算。 当然，优化不能只局限于这个函数，否则是没有意义的，在设计整个算法的时候（即需要用到bilinear interploation的某个图像处理算法），就应该避免使用浮点，保证V0, V1, H0, H1是整形值。在WannaPlayDIB库中，DIB_RotateFast就是个很好的例子，在循环中央的ox, oy如果不进行右移，就可以通过截取低16位值的方法来得到上面对应的H1和V1，而H0 = 65536-H1, V0 = 65536-V1。因此很容易就能写出DIB_RotateFast的二次插值版本。 |
