提高图像匹配速度的一种方法
2008-12-24
作者：曾 峦 李迎春
摘 要： 根据工程实践的需要、在进行图像匹配" title="图像匹配">图像匹配时、利用在外极线上动态确定搜索范围的方法减小匹配的搜索空间、从而降低匹配错误率、提高匹配速度。
关键词： 图像匹配 约束 外极线定界
立体视觉是计算机视觉" title="计算机视觉">计算机视觉中的一个重要分支，一直是计算机视觉研究的重点和热点。它是计算机被动测距方法中最重要的距离感知技术，可以在多种条件下灵活地测量景物的立体信息。在非接触测量方面越来越占有重要的地位。
立体视觉中最重要也是最困难的问题是图像匹配。匹配方法" title="匹配方法">匹配方法按照所选基元可分为两类：其一是基于图像灰度分布的匹配；以图像的灰度信息为基础，对二维图像平面进行统计分析，用灰度相关性和相似性做相关匹配判决。直接对图像象素进行匹配可以得到较高的定位精度和密集的视差表面，由于过分依赖图像灰度统计特性，使得匹配对景物表面结构、光照反射和成像几何十分敏感。其二是基于图像特征的匹配；有选择地采用能表示景物自身特性的特征，通过更多的强调空间景物的结构信息解决匹配的歧义性，匹配特征主要为点状特征、线状特征、角特征、区域特征，也可取图像统计特征。
空间三维景物成像为二维图像时，不同视点的图像有很大差异。有很多因素会使特征点" title="特征点">特征点不稳定，如光照条件、景物几何形状、物理特性、噪声干扰、畸变等都被综合成单一的图像中的灰度值。这使得像点灰度信息不能作为局部匹配的判决依据。物体对光照的非漫反射，在场景中产生阴影，在光照条件变化时，阴影的位置，形状也发生变化，影响了特征区域的选择和特征信息的提取。可见，要准确地对包含了如此之多不利因素的图像进行无歧义的匹配有相当的难度。特别是在匹配过程中，一般都是在图像对的宽度范围内进行匹配搜索，不仅费时，而且还增加了匹配的错误概率。因此，在实际应用中，如何尽可能地缩短匹配搜索范围，对匹配定位的准确性和匹配运算的实时性都有着无可置疑的重要性。
1 基本约束条件
不同视点投影图像的差异和物体表面局部结构的相似性使对应性求解呈多义性。为提高匹配的可靠性、置信度，消除歧义性，根据物体某些固有特性和先验知识拟定了匹配约束。
1.1 外极线约束
空间序列图像中，摄像机焦点f1，f2与物点P决定一个外极面，与像面的交线为外极线，也叫核线。同名像点位于同名外极线上，在标定得到内外方位参数后，图像序列信息中，同名外极线是确定的。图像匹配中只需要沿外极线方向搜索就可以找到相应像点，搜索是沿着外极线方向进行的，也就形成了一维搜索，习惯上把这种图像匹配叫做外极线数字相关或核线相关。由于沿外极线的一维图像匹配，搜索位置比二维少得多，它具有计算量小，图像匹配速度大大提高的优点，是目前许多图像匹配方案中都广泛采用方法。[2]
1.2 视差连续性约束
仅在被遮挡区域或边界上，视差才出现不连续，用此可剔除部分伪匹配点。
1.3 物体形态约束
物体表面有一定的坡度和高度，在一定范围内变化，由此可找出对应点范围限制，减少搜索区和剔除部分伪匹配点。
1.4 偏差梯度约束
对于绝大多数自然场景，即使很复杂，两对共轭点的偏差梯度总是小于1的；而对于不正确的匹配，则很少能满足这种限制。这种约束需要第三个相机。[1]
另外，还有相容性约束、唯一性约束等等。我们在这些约束的基础上，根据测量系统的具体情况，提出了一种新的约束条件，即根据被测物体深度空间所具有的坐标范围约束。
1.5 坐标范围约束
被测物体的深度空间已知和投影几何固定时，可以利用被测物的高度信息来限制同名像点在外极线上的范围。由物点坐标用一元线性回归可求出同名像点在对应的外极线上的可能区域，减小了直线搜索范围。
2 动态外极线定界方法
在图像匹配中加入上述各种匹配约束后，特征点的搜索范围已经减小。但在工程实践中，我们发现特征点数目越多，求得空间物体上的对应点越密集，对物体的三维描述就越容易，得到的形态参数就越精确，同时匹配所需的时间就越长。这在图像匹配中始终是一个突出的矛盾，因此正确地增加匹配约束，减小搜索范围，提高匹配速度是我们一直研究的问题。
煤场中的煤堆类似于四棱柱体，空间几何关系示意图如图1所示。
在工程中，摄像机被固定在立于煤场一边的铁塔顶上，两台摄像机均俯视煤堆，交向摄影。这样得到的两幅图像像面上每一个像素间隔代表的空间距离是不同的。在图像的下边，每个像素间隔代表的空间距离大，空间分辨率小；随着像面坐标J值的增大，越往上，每个像素间隔代表的空间距离减小，空间分辨率增大。根据前面叙述的外极线定界得到的匹配搜索范围如图2所示。
图2中左图有四个特征点，右图中有相应的四条外极线与之对应，并且图像经过几何变换后，外极线接近于水平。右图中的两条虚线表示对应点在外极线上的搜索范围，随着像面坐标J值的增大，越往上，外极线的定界范围越宽，匹配点搜索所需时间就越长，匹配出错概率就越大。而像面坐标J值越大，对应的空间物点的三维坐标Z的值就越大。因此，在两幅图像上部的特征点能否正确匹配，对所求的空间物体的高度影响非常大。
在实践中，我们发现前面所述的定界方法只利用了空间物体整体的坐标连续性、整体的形态限制和坐标范围限制。而没有充分利用相邻两个特征点之间的空间坐标和像面坐标连续性。为了克服原有的定界方法的不足，我们采用了动态定界来缩小匹配点的搜索范围，如图3所示。
在左、右两幅800×600×256级灰度图像中，首先确定出已知的基准点在图像中的对应位置(在两幅图像的最下方中央)，及基准点的空间三维坐标，根据基准点像面坐标，在与I垂直的方向上，划分n个15×15大小的区域，按照寻找特征点的方法，在每个小区域中以灰度重心作为它的特征点(图中只以四个特征点为例)，图3(a)中，第一个" title="第一个">第一个特征点与基准点垂直相邻。根据像面坐标的连续性可知，在图3(b)中与之对应的匹配点在第一条外极线上，并且像面坐标I的值在基准点坐标I值左右的一定范围。根据空间物点坐标连续性可知，与相邻的两个特征点相对应的空间点三维坐标中，Z、Y和X值的差别在一定范围内，即煤堆在X、Z方向不可能剧烈突起、下凹或断裂；在Y方向随着像面坐标J的增大，Y值只能增大，不可能减小。由此可以在第一条外极线上划定一定范围，与图3(b)基准点垂直相邻，在这个范围内依据特征点的对应准则进行匹配。在图3(b)中得到第一个匹配点后，第二个匹配点的搜索范围根据第一个匹配点的像面坐标而定，依次类推。在图像J方向上确定了一系列的特征点和匹配点后，与其相邻的左边或右边的特征点也可以类推。这种定界方法中，每一个特征点在外极线上的搜索范围都是靠前一个已知对应点来确定，我们称之为动态定界。
从示意图中可以看出，采用动态定界后，在像面上方匹配点的搜索范围大大缩小。因此，匹配速度进一步加快，匹配错误概率也同时降低。
另外，作者认为，在交向摄像中，图像中心部位是整幅图像分辨率和清晰度最好的地方，匹配时，从图像中心线方向上首先进行，采用上述动态定界的方法搜索对应点；然后再向左、右两个方向扩展，以中心线上的匹配点作为外极线定界的参考点，逐步进行匹配，直到整幅图像匹配完毕。
3 实验结果
作者用图像对分别用传统方法和动态外极线定界方法进行对比实验，并用人机交互方法检验其匹配结果正确性，结果如表1所示。
从表中看出，同一图像对用定界匹配方法比常规匹配方法节省匹配时间79.4%，而匹配准确率则提高了41.7%。在大部分匹配点正确的前提下，利用图像的整体结构信息，可以剔除一些误匹配点，更进一步提高匹配的准确度。
参考文献
1 吴立德.计算机视觉.上海：复旦大学出版社，1993
2 Kenneth R.Castleman.Digital Image Processing.北京：清华大学出版社，1997