一种基于双目测距系统的亚像素精度自适应图像匹配算法

张尧，赵洋，刘博宇，迟名辰，杨进华

（长春理工大学　光电工程学院，长春　130022）



一种基于双目测距系统的亚像素精度自适应图像匹配算法

张尧，赵洋，刘博宇，迟名辰，杨进华

（长春理工大学光电工程学院，长春130022）

摘要：针对目前亚像素精度图像匹配算法中存在的匹配精度不高和匹配速度慢的缺点，对基于灰度的归一化互相关算法进行了改进，提出动态调整匹配区域范围的自适应方法，既保证了亚像素级匹配精度，又提高了运算速度。实验证明，改进后的算法，在保证0.2个像素匹配精度的条件下，匹配速度大大提高，能够满足实际应用中的实时性要求。

关键词：亚像素；自适应；图像匹配；归一化互相关

双目CCD测距技术是一种仿照人类利用双眼得到目标物体的图像来感知距离的光学测距方法。双目CCD测距为被动测距，在测量中不必对被测目标发射任何信号，只需在自然条件下即可实现高精度远距离测距，具有隐蔽性的特点，特别适用于军用设备测距、航空目标测距和工业应用中需要保密和受环境限制的场合。

双目视觉是由不同位置的两台CCD摄像机，通过平移对同一幅场景进行拍摄来估计在两幅图像中对应像素点的视差，从而全面的恢复场景的深度信息，感知三维世界。双目视觉系统主要涵盖了五个基本模块：数字图像对采集、双目立体标定、数字图像对校正、立体匹配和三维结构恢复，而立体匹配模块一直成为该系统研究的核心所在。双目视觉中的立体匹配其实是在两幅图像之间建立匹配点，然后根据摄像机参数和对应的匹配点计算场景中目标的深度值。图像匹配算法的核心就是通过某个特定匹配准则，在两幅图像上寻找同名点间的一一对应关系的过程，其实质就是运用匹配准则在待匹配点中寻找最佳搜索方法。以左图获得的目标点为点源，在右图中寻找最佳准则的匹配点的搜索过程，就是各种立体匹配算法的研究内容。

目前国内外对基于亚像素精度的匹配算法已有一些研究，但是由于要实现的是立体图像对的亚像素精度的稠密匹配，与像素级的匹配算法相比，其在实现精度、复杂度、估计值准确度、运算速度等方面都是一个大的挑战。

在亚像素精度图像匹配领域，研究者们普遍思路是通过插值拟合的处理方式来对整数视差进行进一步细化。Tian Q［1］等人提出对聚集代价进行抛物线拟合来得到亚像素视差，但通过这个方法得到的亚像素视差有明显的像素锁定现象，即视差值取在整数值附近的概率远远大于取在0.5个像素附近值的概率。Shimizu M［2］的研究中，减少了线性相似度策略产生的视差错误。Nehab［3］等在此基础上提出系统偏移的实质性问题，通过在视差空间上进行二维拟合来迭代贴近真实亚像素值，但是针对每一幅图像参数都不同，实现较繁琐。由于在频域进行匹配操作不受亮度变化的影响，所以Takita K等人［4］依据图像对应点频率特性，在频率范围内进行视差估计，提出基于相位相关的图像匹配方法，一定程度上提高了视差精度。随后Hongshi Yan和Jian Guo Liu［5］在联合相位相关方法中加入了一个判定系数来进行亚像素视差估计，使得算法更为鲁棒。但相位方法存在的明显不足是需要场景中的物体为相对规则的刚性目标。2006年Klaus A［6］转换思路，提出了AdaptingBP算法，不同于传统方法对每个像素进行视差求解，而是采用置信度传播在分割面上进行视差求解，采用颜色分割和自适应匹配相似性度量来最大化可靠匹配点的数量。通过平面补丁来对场景结构进行建模，使得算法对奇异点有更好的抗性。在此基础上，Wang Z［7］提出了一种新的基于分割区域间协同优化的方法。该算法以图像区域为匹配基元，进行彩色分割后，利用每个区域不同的彩色特征与其相邻区域间存在的相关特性，来定义每个区域的匹配能量函数，再利用区域之间的合作竞争机制，通过优化子目标之间合作竞争关系来达到优化总体匹配能量的目的，实验证明其匹配性能比较理想。但是区域的分割结果对视差有较大影响。与上述方法都不同的是Yang Q X［8］提出在后处理阶段来提高深度图像的分辨率，通过使用一个或两个高分辨率彩色图像作为参考，对输入的低分辨率图像，迭代地改善空间分辨率和深度精度，获得了非常好的亚像素深度信息。而针对实际场景中的弱纹理问题，翟振刚［9］在2010年提出了基于分割块几何约束的立体匹配算法，利用分割块的上下文几何约束信息来判断可信视差点与可信视差点，通过计算视差值概率分布，由可信分割块的视差信息推理出不可信分割块的视差信息，一定程度上克服了弱纹理区域的误匹配，提高了匹配的准确度。2011年施陈博［10］又提出一种新的高精度全局优化框架，通过可靠点集合与平面平滑模型构建了新的全局能量函数，利用视差图和可信度图交替迭代更新的方式实现了多个亚像素精度上的好效果，并可以在不同的光照条件下都具有较好的鲁棒性，但是其视差图和可信度图容易受实际图像中噪声和边缘模糊影响。Bleyer［11］提出ObjectStereo算法，在传统颜色分割的基础上，充分利用空间的一些相关性的目标组成约束信息，将目标层颜色模型作为软约束的分割方法加入到全局优化模型中进行计算。由于考虑了离散颜色相似区域的相关性特性，所以在彩色图像上获得了很好地效果。

虽然基于扩展相位相关的算法在亚像素精度下的配准都达到了相当高的精度，但是他们无一例外都是算法复杂度非常高，运行速度很慢，因此，发展较慢，现在大多应用于遥感图像配准等刚性变换的自动配准领域；二次曲线拟合可以在每一个像素上进行视差的亚像素化，实现过程很简单，但是也存在着不足，即如果图像的初始视差就是不正确的，那么拟合后的结果必定也是存在偏差的；通过基于曲面拟合的方法来对视差进行视差精度的提升有很多的方式，但是由于曲面拟合存在着拟合过程需要在相对单一的表面模型才能进行，依据拟合的表面模型的不同拟合系数个数以及拟合公式也有很大的不同。

综合以上亚像素精度图像匹配策略研究的发展现状可知，不管是哪一种算法，它们都各有优势，但也都存在不足之处，在匹配精度、运行时间上存在较大的差异，也都还需要进一步的研究与实验论证。在本课题的研究当中，考虑通过自适应匹配窗口来实现提高亚像素匹配精度和速度。其中，如何确定匹配窗口的大小是比较关键的问题：窗口越小，在视差不连续区域匹配精度越高，但是低纹理区域没有覆盖足够的灰度变化，会因灰度信息太少使得视差估计不准确；窗口越大，可以包括足够的灰度变化，对于低纹理区域匹配精度越高，但窗口太大且包含视差的较大变化，会因为左右图像上不同的投影畸变，使得匹配位置不正确，且计算量大。因此，分别在像素级精度和亚像素级精度匹配阶段，引入自适应窗口进行匹配是非常有必要的。

1　像素级精度粗匹配

1.1互相关匹配算法

针对双目测距，采用的左右CCD摄像机型号、参数可以保持一致，基本保持光轴平行、双目摄像机坐标系共面且各坐标轴平行放置，由此同步采集的左右CCD图像大小、比例一致，图像的灰度信息受噪声干扰较小。因此，采用最适合双目测距系统的基于模板匹配的灰度互相关的图像匹配算法，其原理如图1所示。

图1　互相关匹配原理图

这里用归一化互相关匹配算法来比较Si，j和T相似度。互相关函数的表达式为

1.2自适应图像粗匹配原理

对于截取的特征模板t（h×h，h初始值为50pixel），如果其中包含的图像特征不明显的话，则会大大降低粗匹配精度，甚至造成误匹配，所以在图像粗匹配环节引入自适应窗口可以有效解决这一问题，其原理如下：

为了判断图像上是否存在特征，需要对图像上的每点都建立Hessian矩阵（公式4），然后依据该矩阵判别式（公式5），对其是否为极值点进行判断，如果判别式为正，则特征值是同号，该点是极值点，说明截取图像中含有明显特征，可以进行粗匹配；如果判别式为负，则特征值是负号，该点不是极值点，说明截取图像内没有没有明显特征，则返回重新截取大小为h= h+1的特征模板。

1.3粗匹配过程描述

（1）对待匹配图像的目标区域进行提取。利用双目测距系统对待测目标进行拍摄，左幅图像称为模板图像T，右幅图像称为搜索图像S。

中心是图像上非常特殊的一个点，以中心为参考点来研究双目测距系统的问题也很方便，因此中心坐标在计算机图像的研究中早已得到了广泛的应用，如利用中心定位、跟踪、识别图像等［12］。本课题所研究的双目测距系统基线为2m，测距范围3～5公里，根据平面几何比例性质计算，可以得出左、右相机的图像都会包含中心区域。图像的中心区域可以极大的克服由于相机旋转、伸缩以及添加噪声而带来的大幅度位置变化，相应结合中心的匹配算法更具有一定的鲁棒性。因此，采取截取中心区域正方形匹配的思想来提高归一化互相关算法的效率，降低其运行时间。

分别以两幅原图像T（M×N）、S（M×N）中心点（M/2，N/2）为中心，截取特征模板t（m×m）、搜索子图s（n×n）。实际实验中，所拍摄的图像S、T实际大小均为1280pixel×960pixel，如图2所示。

图2　实验图像和截取图像

（2）对截取后的T图和S图进行互相关匹配运算。以T为模板在S上进行模板搜索，进行每一像素点的互相关运算，当运算结果达到最大值时，我们认为此时T与S达到像素级匹配，进而可以得到S中与T的中心点A相对应的粗匹配点A’的坐标。

为了方便观察，将每次互相关运算结果储存在与t相等大小的矩阵C中，矩阵C中每个点坐标与t左上角像素点的坐标相对应，每个数值都反映了s 与t的匹配程度，越接近于1则匹配的程度越高，C的函数分布如图3所示。

图3　粗匹配互相关函数分布情况

2　亚像素级精度匹配

在亚像素级精度匹配阶段，再次引入图像自适应截取窗口，以确保节省运算时间。

（1）以粗匹配点A和A’为中心，分别在S和T中截取大小为5k +1和10k +1个像素的正方形区域T1和S1（k为1，2，3，…，20的整数）。这里k的取值是变动的，如果后续的亚像素精度匹配结果不理想，是特征区域选取过小的缘故，k则取下一个较大的值，进行再次运算，直到大于能反映匹配程度的阈值g为止。经过大量实验，我们可以得到k的值与图像匹配程度所拟合成的曲线关系如图4所示。

图4　k值与匹配程度的关系

可以看出，当k＞2时，曲线斜率变化趋于平缓。所以，根据节省运算时间的原则，当匹配程度大于0.9970时，我们即视为两幅图像匹配，也就是说阈值g设置为0.9970。至此完成了亚像素匹配的自适应过程。

（2）三次曲面拟合

分别对T1和S1进行三次曲面拟合，将其函数用二元三次多项式表示为：

通过最小二乘法获得最佳系数akj，然后再分别对T1和S1进行二维均匀插值，无论k为何值，都要确保插值的间距为0.2像素，即对每个像素进行25细分，亚像素精度为0.2，如图5所示。

图5　曲面插值结果

（3）对细分后的T1、S1再次进行互相关匹配运算，如果匹配程度没有达到阈值g，则扩大T1、S1的截图范围，再次进行运算，匹配结果的函数分布如图6所示。

图6　亚像素级精度匹配互相关函数分布情况

（4）算法的大致流程如图7所示。

图7　程序流程图

（5）实验结果

实验是在Windows XP的系统上（CPU双核1.8GHz，内存2GB），用Matlab 7.0实现的算法，CCD相机采用的是AVT GC1290C，结果如表1所示。

表1　实验结果

表1表明：归一化互相关和曲面插值拟合结合的匹配算法可达到0.2像素的匹配精度，较好地解决了以往图像匹配精度不高的问题，自适应匹配窗口的使用，相对于传统的全区域搜索，大大节省了图像匹配的时间。

3　结论

采用提出的自适应图像匹配算法提高了双目CCD被动测距系统的图像匹配精度，同时节省了运算时间。在图像匹配过程中，对目标图像应用改进的互相关算法与三次曲面拟合相结合的算法，使其达到了图像的亚像素级匹配，精度可以达到0.2个像素，具有较高的实用价值。

参考文献

［1］Tian Q，Huhns M. Algorithms for subpixel registration［J］.Computer Vision，Graphics，and Image Processing，1986，35（2）：220-233.

［2］Shimizu M，Okutomi M. An analysis of subpixel estimation error on area-based image matching［C］.Japan In proceeding of Digital Signal Processing，2002，14（2）：1239-1242.

［3］Nehab D，Rusinkiewicz S，Davis J.Improved sub-pixel stereo correspondences through symmetric refinement ［C］.Proceedings of International Conference on Computer Vision（ICCV），2005：557-562.

［4］Takita K，Aoki T，Sasaki Y，et al. Kobayashi. High-accuracy subpixel image registration based on phase only correlation［J］.IEICE Trans. Fundamentals，2003，E86-A（8）：1925-1934.

［5］Hongshi Yan，Jian Guo Liu.Robust phase correlation based sub-pixel disparity estimation and its refinement around depth discontinuity and featureless areas ［J］. Geoscience and Remote Sensing Symposium （IGARSS），IEEE International，2010：4576-4579.

［6］Klaus A，Sormann M，Karner K. Segment-based stereomatchingusingbelief propagationanda self-adapting dissimilarity measure［C］. Proceedings of 18th International Conference on Pattern Recognition，2006，18（3）：15-18.

［7］Wang Z，Zheng Z. A region based stereo matching algorithm using cooperative optimization［C］.Proceedings of IEEE Conference on Computer Vision and Pattern Recognition，2008：1-8.

［8］Yang Q X，Yang R G，Davis J，et al. Spatial-depth super resolution for range images［C］.Proceedings of IEEE Conference on Computer ^sion and Pattern Recognition，2007：1-8.

［9］翟振刚.立体匹配算法研究［D］.北京：北京理工大学，2010.

［10］施陈博.快速图像配准和高精度立体匹配算法研究［D］.北京：清华大学，2011.

［11］Bleyer M，Rother C，Kohli P，et al. Object stereo：Joint stereo matching and object segmentation ［C］. Proceedings of IEEE Conference on Computer Vision and Pattern Recognition，2011：3081-3088.

［12］吕娜，冯祖仁.质心迭代图像跟踪算法［J］.西安交通大学学报，2007，41（12）：1396-1399.

A Kind of Sub-pixel Accuracy Adaptive Image Matching Algorithm for Binocular Ranging System

ZHANG Yao，ZHAO Yang，LIU Boyu，CHI Mingchen，YANG Jinhua
（School of Optoelectronic Engineering，Changchun University of Science and Technology，Changchun 130022）

Abstract：In view of the disadvantages of the low matching accuracy and the slow speed of the matching accuracy in the sub-pixel accuracy image matching algorithm，the normalized cross correlation algorithm based on gray scale is improved，an adaptive method for dynamically adjusting the range of matching regions is proposed，it can not only ensure the accuracy of sub-pixel level matching，but also improve the operation speed. Experimental results：Improved algorithm，both ensuring the accuracy of 0.2 pixels matching，and improving the operation speed，Be able to meet the real-time requirements of the practical application

Key words：sub-pixel；self-adaption；image matching；normalized cross-correlation

中图分类号：TP391.41

文献标识码：A

文章编号：1672-9870（2016）02-0014-05

收稿日期：2015-10-10

作者简介：张尧（1986-），男，硕士研究生，E-mail：254874002@qq.com

通讯作者：杨进华（1969-），男，博士，教授，E-mail：yangjh@cust.edu.cn