一种利用点基元灰度的快速精确图像匹配算法

王湘伟，莫秋云，粟定华，陈泽章，李军

(1.桂林电子科技大学机电工程学院，广西桂林 541004；2.中橡集团曙光橡胶工业研究设计院，广西桂林 541004；3.桂林科技创业服务中心，广西桂林 541004)

在实现基于双目视觉的机械手对轮胎测温点进行测温的过程中，图像匹配精度和速度是关键。目前常采用基于外极线约束［1-2］的区域相关匹配［3］算法来确定两个对应点间的匹配。但是该算法要求对极线上每一个点都进行区域相关匹配计算，计算量大、耗时并且匹配准确度不高。针对此问题，提出一种将像素点之间灰度值比较与区域匹配相结合的改进算法。由于两图片上对应点之间灰度值相近，该算法先将目标点与对应极线上各像素点依次进行点灰度比较，排除与目标点灰度差别较大的像素点，然后对与目标点灰度值相差较小的像素点进行区域灰度相关匹配计算，以减少区域灰度相关计算量，降低误匹配率，获得较为准确的目标点的左右图像坐标，从而比较准确地获取其三维坐标，提高机械手的定位精度。

1 外极线约束原理

如图1所示，将双目立体视觉所涉及的两个视平面分别称为左视平面和右视平面，分别记为PL和PR。每个摄像机都有一个独立的光心，分别为OL和OR。过光心OL和OR的连线称为光心线，也称基线。基线与视平面的交点称为该视平面的外极点。空间某点P与基线所确定的平面称为外极平面。

对于给定的左图像平面上的一点PL，它所对应的空间点P一定处在该点与左光心点OL的连线上。这条连线与右光心点OR确定了一个外极线平面，该平面与右视平面相交于一条直线PReR，这条直线被称为左图像上PL点的外极线。容易知道，对于左图像上的一点PL，其在右图像上的匹配点PR一定在外极线上，这就是外极线约束。这个约束很大程度上减少了待验证的可能匹配点对的数量，即把一个点在另外一幅图像上可能的匹配点的分布从二维平面降到了一维的线上，极大地减小了搜索匹配点的范围，并且减少了误匹配。这就是立体视觉中最基本的约束。

图1 一般放置的双目视觉中的极线和极平面

2 外极线的选取

图1所示为一般放置的双目视觉模型，如果使用极线约束原则进行匹配，则每求一个目标点都需要计算外极线方程，然后根据极线斜率的不同方向来确定步进方向，这个过程需要大量的计算，极大地影响了程序的运行效率，不能满足机械手测温实时性的要求。

如图2所示，该双目视觉模型在理想状态下平行放置［4］。该模型中两个摄像机C1和C2仅在x轴方向上有一平移b，即左右摄像机光心分别作为左右摄像机坐标系的原点OL和OR，以光心的连线方向作为它们x轴的方向，光心之间的距离为b，两个摄像机的光轴互相平行。

其中OLOR为CL和CR坐标系的x轴，POLOR平面与两个图像平面IL和IR的交线分别为EL和ER，因为两个图像平面位于同一平面，所以EL和ER为该平面上的同一直线。同时，图像平面平行于x轴，故EL、ER与x轴平行。PL与PR分别为OLP与IL、OLP与IR的交点，故PL与PR分别在EL和ER上。

图2 平行结构的双目视觉系统

平行放置的双目视觉模块避免了一般放置的双目视觉模型外极线求解计算量大的缺点，同时简化了后续三维求距的计算量。但是平行放置的双目视觉模块是理想的模型，在实际情况下基本无法让两个摄像机的光轴保持平行。可通过数学校正，对图片进行校正［5］，使两台摄像机的光轴变为平行的，即得到行对准的图像对。

因此，通过比较两种双目视觉模型极线求取的方法，文中选取利用水平极线约束来进行区域匹配。

3 区域匹配算法的改进

3.1 基于水平极线的区域匹配

如图3所示，设Image1和Image2分别为已校正好的左右两幅图像，在左图像中选中一目标点p，以p为中心的某一领域作为模板T，大小为M×M。从立体图像对中大致观察图像对的视差范围［6］，设最大的视差dmax，只需沿目标点p的同一水平扫描线，在 (i+dmax，j)至 (i-dmax，j)范围内进行搜索。匹配时模板图叠放在匹配图像上平移，模板图覆盖下第k个搜索子图为Sk。匹配时通过计算相关函数来找到与模板图尽可能相似的搜索子图以及它的坐标位置。若模板图T和搜索子图Sk完全一致，则T和Sk之差为零。

图3 基于水平极线的区域匹配

一般来说通过相关函数来确定最佳匹配点，应用中可以用相似性测度函数［7-8］来衡量T和Sk的相似程度:

展开得:

当D(i，j)最小时，T和Sk达到最佳匹配。

该算法中，基准图沿平行线每移动一个像素，模板都需要做一次区域灰度相关计算，其中除了匹配点计算以外都是在非匹配点上做无用功，而且受光照等条件影响极有可能存在区域相似程度更高的非匹配点而造成误匹配。该算法不能满足机械手快速准确定位的要求，因此，文中提出对基于水平极线的区域匹配算法的改进，如第3.2节。

3.2 改进算法

针对上述区域匹配算法存在的问题，提出一种将像素点灰度值比较与区域相关匹配相结合的改进算法。由于点基元灰度值计算量远远小于区域灰度相关计算量，因此先将目标点与极线上各像素点进行点灰度值比较后再判定是否进行区域匹配，即相当于对像素点进行一次刷选后再区域相关匹配，这样可减少区域匹配计算次数以及减小误匹配的概率，具体方法如下:

(1)利用点基元灰度值比较排除极线上一部分非匹配点，以减少不必要的区域灰度匹配相关计算量。由于受光照等条件影响，左右两张图片上对应点之间的灰度值一般不会相等，但其值不会相差很大，会保持在一定范围内。若极线上一像素点与目标点之间灰度值相差很大，则该点必定不会是匹配点，故没有进行区域匹配的必要。因此，设定阀值α(一般很小，可以根据需要做调整)，取目标点p依次沿 (i+dmax，j)至 (i-dmax，j)上的像素点进行点灰度值比较。

(2)若两像素点灰度值之差大于阀值α，则该点必定不是匹配点，因此不进行区域灰度相关匹配，直接进入对下一像素点的灰度值比较。

(3)若两像素点灰度值之差小于阀值α，则进行区域相关匹配计算，保存D(i，j)的值，再进入下一像素点的灰度值比较。

(4)比较所有记录下来的D(i，j)的值，取D(i，j)值最小的子图Si，j的中心点为最佳匹配点。

4 算法实现与验证

依据上述原理，采用C++6.0编程对上述方法进行验证，设定初始阀值α=10，最大视差dmax=100。用鼠标在图4中框选轮胎上记号点，然后沿水平极线去寻找对应匹配点，两种算法的匹配结果分别如图5和图6所示。为了进一步证明该方法的有效性，把记录下的8个目标点与两种算法所求出的对应匹配点的灰度值作对比，如表1所示;并且将两种算法的区域灰度相关计算次数做比较，如表2所示。

图4 左视图

图5 原算法匹配结果

图6 改进算法匹配结果

表1 对应点灰度值对比结果

表2 区域灰度相关计算次数对比结果

从以上结果可知:

(1)对于仅利用区域匹配的算法，如图5所示，匹配结果不是很准确，点3、5、7都出现了误匹配;从表1可以看出，图5中的点3、5、7与其对应目标点灰度值相差很大;并且该算法计算量非常大，目标点与沿极线上每一点都进行了一次区域灰度相关计算，如表2所示。

(2)改进算法能将极线上与目标点灰度值相差较大的点进行排除，提高匹配准确度，如图6所示;从表2可知，该算法大大减少了区域灰度相关计算次数，从而节省了大量的计算时间。

5 结论

通过大量的实验验证，可以得到以下结论:采用先将目标点与极线各像素点进行点灰度比较后再进行区域匹配的算法，可以有效减少仅采用沿极线进行区域匹配的匹配误差，提高匹配精度，同时减少计算量。

［1］韩伟，郑江滨，李秀秀.基于外极线的快速精确立体匹配算法［J］.计算机工程与应用，2008，44(1):51-53.

［2］邓志燕，陈炽坤.利用外极线约束的图像匹配新算法［J］.工程图学学报，2009(5):104-107.

［3］ZHOU J，XU Y，YU W R.Phase Matching with Multiresolution Wavelet Transform［C］//Proc SPIE，2002:82-91.

［4］富巍，刘美俊.排爆机器人的研究与开发［M］.北京:电子工业出版社，2010:68-88.

［5］刘金鑫.双目视觉的摄像机标定与立体匹配技术研究［D］.广州:广东工业大学，2011.

［6］曾吉勇，苏显渝.浓密视差图的快速提取［J］.光学技术，2004，30(1):40-43.

［7］段湘斌.基于灰度图像的匹配算法改进［D］.长沙:中南大学，2012.

［8］冯宇平，赵文仓.基于局部灰度值编码的图像匹配［J］.青岛科技大学学报:自然科学版，2011，32(4):435-440.