算法的一种快速实现方法.doc

图像匹配中 NCC 算法的一种快速实现方法
黄真宝,陈 阳
(东南大学信息科学与工程学院,江苏南京,210096)
摘 要:在计算机视觉领域,图像匹配是常见的任务,基于灰度的点的匹配是常见的方法。其中
又以抗噪能力强、匹配精度高的归一化互相关(NCC)算法最为常用。然而 NCC 算法计算量较大,常常难以满足实时处理的要求。通过引入合适的全 1 矩阵,让其和原图像的数据做卷积,大幅度地降低的计算量,提高了效率,仿真实验结果也证明了本文方法的有效性。
关键词:图像匹配;归一化互相关;快速算法;卷积
中图分类号:TP751
引
言
0
耗不少的时间。
本文通过引入合适尺寸的全 1 矩阵来直接和图像的某些数据做卷积,可一次性地获得当前视差值下的所有感兴趣位置的互相关值,对所有可能的视差情况均做一遍同样的卷积过程即可得所有可能的视差值下的互相关值。各个位置处互相关值取最大时所对应的视差值即为该位置处对应的所求视差,这样视差图就很方便地获得了。可见,从理论上讲本文方法可极大地提高 NCC 匹配的速度,实验结果也确实证实了这一点。
人之所以有立体视觉的一个主要原因是人有两
只眼睛,通过两只眼睛观察到的景物影像略有差别, 在大脑中就可以据此合成出具有纵深感的立体影像。近年来,电视技术正迅速地由高清向立体发展, 三维立体建模在计算机视觉中的重要性也日益突出, 这其中双目立体视觉的图像匹配[1] 是一个常见的任务。所谓双目立体视觉的图像匹配,就是从两台如人眼一样摆放的摄像机获取的两幅图像中分别找出相同景物的各像素点的位置并建立对应关系。由图像匹配的结果可得视差图[2],它是深度信息获取和三维重建的前期步骤[3]。本文以右图(右摄像机拍摄的图片)为基准进行匹配,则视差[4]为 d 的互相匹配的点在左图(左摄像机拍摄的图片)和右图的坐标可分别表示为 IL( x, y + d ) 和 IR ( x, y) 。
图像匹配中常采用 NCC(Normalized cross correla⁃
tion,归一化互相关)算法[5],其思想是计算对应右图上
的指定点,左图上搜索范围内各个点和该点的相关程
度。如果对整幅图进行匹配的话,以尺寸为 450 像素×
375 像素的测试图片[6]为例,视差范围为[0,59],即使选
取 7×7 的较小矩形支撑区域,相关运算的计算量依然
巨大。因此,必须设法降低计算复杂度。孙卜郊等人
[7] 采用了卷积的思想来加速运算过程,但是其需要先对其中一幅图像做逆序运算,这本身也需消耗一定的时间。Ke Zhang 等人[8]为加快运算提出了构造整数图像的思想,并采用了优化的策略来构造所需的整数图像,尽管如此,构造两幅图像各自的整数图像仍需消
匹配算法介绍
图像匹配的方法很多[9],其中基于灰度的点的匹配最直接而又常用[9]。常见的匹配相似性度量函数有 SAD(Sum of Absolute Differences,差绝对值和)、SSD
1
(Sum of squared differences,差平方和)和 NCC 三种[5]。
其中 SAD 和 SSD 算法都是搜索使相似性度量函数取
最小值时对应的 d ,而 NCC 算法则是搜索使相似性度
量函数取最大值时对应的 d 。
在图像匹配中,有搜索窗和模