人气 206

[行业观察] 对高速二次线性插值算法的讨论 [复制链接]

九艺网 2017-3-10 17:00:54

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?注册

x
原理线性插值并不难理解。以图像处理领域为例,我们的理想图像是均匀的分布在二维平面直角坐标系中的,任意给出一对坐标,就应该能够得到一个对应的颜色值,然而现实是残酷的,我们只能够用离散的点阵信息来近似表现图像。
现在假设给定一对坐标(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)其实可以写成矩阵连乘的形式:

  1.                         |p00 p01| |h0|
  2. v(x, y) = |v0 v1|*|       |*|  | ................................(1.2)
  3. |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,那么有:

  1.                         |p00 p01| |H0|
  2. v(x, y)*65536*65536 = |V0 V1|*|       |*|  | ....................(1.3)
  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的二次插值版本。
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

QQ|手机版|小黑屋|九艺游戏动画论坛 ( 津ICP备2022000452号-1 )

GMT+8, 2024-3-29 19:25 , Processed in 0.102347 second(s), 23 queries .

Powered by Discuz! X3.4  © 2001-2017 Discuz Team.