WannaPlay
原创文章
对高速二次线性插值算法的讨论
(by Rocks Lee - http://wannaplay.51.net)
原理
线性插值并不难理解。以图像处理领域为例，我们的理想图像是均匀的分布在二维平面直角坐标系中的，任意给出一对坐标，就应该能够得到一个对应的颜色值，然而现实是残酷的，我们只能够用离散的点阵信息来近似表现图像。
现在假设给定一对坐标（2.2, 4.0），想要得到这个坐标对应的颜色，那么比较简单的方法是用四舍五入方法来得到距离该点最近的像素，即像素(2,
4)的值来代替，这显然并不十分的精确，如果用这个方法进行图像放大，那么在比例较大的情况下就会出现明显的“马赛克”现象。
对于上面的例子，更好的办法是把像素(2, 4)和像素(3, 4)的值按照一定的比例混合。比例如何选取呢？很简单，离哪个像素近，哪个像素的比例就大些。那么（简单起见，后面均假设是灰度图），若设像素(2,
4)的值是V_24，像素(3, 4)的值是V_34，就可以得到：
坐标(2.2, 4.0)的颜色值 V(2.2, 4.0) = V_24*(1-0.2)+V_34*0.2
好，现在你已经懂得什么叫线性插值了!
二次线性插值也就不难理解了。这次我们给的坐标不再是那么体贴了——求坐标(2.2, 4.6)的颜色值。那么可以想到：可以先分别求出坐标(2.2,
4.0)和坐标(2.2, 5.0)的颜色值，然后用一次纵向的线型插值，就得到了：
坐标(2.2, 4.0)的颜色值 V(2.2, 4.0) = V_24*(1-0.2)+V_34*0.2
坐标(2.2, 5.0)的颜色值 V(2.2, 5.0) = V_25*(1-0.2)+V_35*0.2
坐标(2.2, 4.6)的颜色值 = V(2.2, 4.0)*(1-0.6)+V(2.2,
5.0)*0.6
到这里，实际上我们已经得到了二次线性插值的计算公式，表述方便起见下面用符号来表示。
设坐标(x, y)的相邻四个像素值分别为p00, p01, p10, p11, 水平方向的比例系数为h0, h1,
垂直方向的比例系数v0, v1（其中h0+h1=1, v0+v1=1），那么用bilinear interpolation得到：
v(x, y) = (p00*h0+p01*h1)*v0 + (p10*h0+p11*h1)*v1 ................(1.1)
有了这个公式，已经可以编写出算法了，但是这个公式里有六次浮点乘法，如果是真彩图的话，则对每一像素都要有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的二次插值版本。
在“实战图形编程”讲座里我将会详细的说明具体的算法。
