Algorithm 版 (精华区)

发信人: Lerry (第一次有失恋的感觉), 信区: Algorithm
标  题: 对高速二次线性插值算法的讨论
发信站: 哈工大紫丁香 (2002年03月12日10:54:36 星期二), 站内信件

对高速二次线性插值算法的讨论
(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 inter
polation得到：
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, p
11以及我们的运算结果都是整数（对于我们的情况，是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的二
次插值版本

--
　　不在乎天长地久，就怕你从来没有！

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 天外飞仙]