石鑫华视觉论坛微信公众号:石鑫华视觉

 找回密码
 注册会员
查看: 3198|回复: 0

[图像处理] 对高速二次线性插值算法的讨论

[复制链接]
  • TA的每日心情
    慵懒
    6 小时前
  • 签到天数: 3156 天

    连续签到: 26 天

    [LV.Master]2000FPS

    发表于 2013-5-19 16:08:18 | 显示全部楼层 |阅读模式 来自:广东省东莞市 联通

    注册登陆后可查看附件和大图,以及购买相关内容

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

    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)其实可以写成矩阵连乘的形式:

    |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的二次插值版本。


    回复

    使用道具 举报

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

    本版积分规则

    LabVIEW HALCON图像处理入门教程(第二版)
    石鑫华机器视觉与LabVIEW Vision图像处理PDF+视频教程11种全套
    《LabVIEW Vision函数实例详解》教程-NI Vision所有函数使用方法介绍,基于NI VISION2020,兼容VDM21/22/23
    LabVIEW图像处理教程
    机器视觉商城淘宝店铺
    视觉论坛充值赞助方法

    QQ|石鑫华视觉论坛 |网站地图

    GMT+8, 2024-3-29 13:27

    Powered by Discuz! X3.4

    © 2001-2024 Discuz! Team.

    快速回复 返回顶部 返回列表