基于区域的稠密立体匹配方法
2011-04-04金玲
金 玲
(辽宁大学信息学院,辽宁 葫芦岛 110036)
稠密立体匹配指计算图像中所有像素的视差值得到致密的视差图,它对三维重建的质量具有十分重要的意义,作为立体匹配的重要研究方向,稠密立体匹配更是计算机视觉领域极富挑战性的研究课题。
近年来各国学者对稠密立体匹配方法进行了不断深入的研究。自适应窗口算法通过调节不同像素点的窗口尺寸[1]提高匹配准确性,不过计算非常复杂,无法实现实时运算。Vladimir Kolmogorov等将图论中的最小割算法应用到立体匹配算法中,求得的最短路径给出了整个图像的视差曲面。此算法复杂度也较高,计算效率低。基于区域增长的半稠密匹配算法具有较好的鲁棒性和可实现性,但是此算法存在一些缺陷:在匹配平滑的区域,匹配关系的传播就会停止。区域匹配的缺陷可归纳成3点:①区域匹配直接利用图像的灰度值进行匹配导致图像的旋转以及光强和对比度的变化对区域匹配影响较大;②相似测度函数的时空复杂性比较大;③匹配窗口大小难以选择,窗口过大导致视差跳跃处出现误匹配,窗口选择过小导致区域的灰度分布不能得到充分体现。
1 基本思想
为了克服上述基于区域存在的问题,本文算法先提取特征点进行匹配,然后将匹配之后得到的种子点消除误匹配;再次,根据种子点匹配度排序策略进行区域增长,按照种子点的匹配可靠系数,动态改变搜索窗口得大小,进而生成稠密视差图。实验表明,本文基于区域增长获得的视差图在保证致密的情况下,运行效率比较高。
2 种子点的鲁棒性匹配算法
2.1 SIFT算法求取特征点
Lhuillier和Quan指出即使种子匹配存在较多外点,增长效果依然能够良好地进行,但算法的运行时间与复杂度明显增加。在实验中我们发现,通过特征匹配和极线几何的鲁棒估计,已经可以正确恢复出图像对的极几何关系。此外,种子点如果能够在图像中均匀分布,增长后的对应点就能覆盖图像的大部分区域,从而在纹理丰富和稀疏区域存在足够多的匹配,以提高重建效果。
Lowe提出的 SIFT(Scale Invariant Feature Transform)特征点检测和匹配算法,相对于传统的Harris等角点检测方法在实际应用中对图像变形呈现出更好的鲁棒性。因此,本文采用基于SIFT特征匹配的方法来确定初始的候选种子点,并且经实验表明能去除大部分的误匹配,但是为了获得更为可靠和精确的对应点作为种子点,我们在实验中,对SIFT得到的匹配通过鲁棒估计进行了进一步的剔除。见图 2(c)(d)。
2.2 种子点(对应点初匹配)
在提取图像的特征点后,对两幅图像提取的特征点进行初始匹配,即确定哪两个点是空间同一场景的投影点,建立候选匹配集合。对于这个初始候选匹配点对集合,它允许包含错误的匹配,但这些错误的匹配将在后续的鲁棒匹配阶段剔除掉。建立初始匹配集,采用相似性,度量函数对两幅图像中的对应点匹配之后成为种子点。文章采用的是去均值的归一化相关算法:
上式中,U,V为模板大小;u,v为匹配点;f(x,y)为图像中匹配区域的像素灰度值t(x-u,y-ν)为模板中的像素灰度值,t为模板的灰度均值,f(u,ν)为图像中匹配区域的均值。由于受环境影响、图像亮度或图像内可能存在的相似特征,必然存在许多误匹配,通过鲁棒的估计基础矩阵可以剔除更多的误匹配,得到一个精度较高的匹配点集。种子点的可靠匹配是十分重要的,它是以后区域增长的基础。见图 3(e)(f)。
2.3 去除外点,种子点求精
关于鲁棒估计,即使用某种方法对外点加以识别,或者说从测量数据中确定出内点(inlier)或称有效点,然后再重新进行模型估计,这就是鲁棒估计的原理。常用的鲁棒估计法有RANSAC方法,最大后验的RANSAC方法,M-估计和最小中值估计等。本文使用 RANSAC(Random Sampling Consensus)方法,它是由Fischler和Bolles于1981年所引入的鲁棒方法。最初它被用于3点确定摄像机姿态的估计,现在无论在计算机视觉领域还是在其他学科的估计问题中都有广泛的应用。对于处理大比例的外点,RANSAC是一种十分有效的方法。经过RANSAC算法消除误匹配点见图 4(g)(h)。
3 基于区域的稠密匹配
考虑到窗口的选择对匹配精度有很大影响,所以在匹配传播过程中,为了避免前一个点的匹配误差对后一个点匹配精度的影响,本文提出了以下动态改变搜索窗的方法:若前一对匹配点的R(u,v)值比较大,则下一个匹配点就可以在它的较小邻域内搜索求得;若前一对匹配点的R(u,v)值较小,则下一个匹配点就需要在它的较大邻域内搜索求得。这就是说,搜索窗的大小N与 R(u,v)值成反比,如公式(2)。
在公式(2)中的常数因子λ需要根据待匹配的图像对的情况由实验确定,通常它的取值在1~2之间。采用自适应的搜索窗既可以有效地减少计算时间,又可以提高匹配算法的准确性,同时避免了区域增长过程中匹配误差的累积。见图5、图6(i)(j)。
文章基于区域增长的稠密匹配的步骤如下:
(1)将种子匹配按R(u,v)值从高到低排成一个队列,称之为全局种子队列;建立两个与图像同大小的标志矩阵,矩阵中每个元素不是1就是0,分别标志对应像素是否找到匹配(0表示没有被匹配,1表示已被匹配,初始为0)。
(2)从种子队列中取出R(u,v)分数最高的匹配值记为R0(u,v),并将它从种子队列中删除;对于R0(u,v),按照公式(2)求出搜索窗口的大小N0以便于下一步R0(u,v)增长。
(3)在N0范围内按R(u,v)值从高到低排成另一个临时局部队列;从局部队列中逐个去除候选匹配,如果候选匹配的R值超过既定的阈值,并且没有被匹配过(即相应的标志位为0),就将它判为正确匹配存入种子队列中并将匹配标志置为1。随后更新相应的数据结构。
(4)重复步骤(1)-(3)直到种子队列为空。
在实验中发现,种子点增长过程的速度很快,往往只需要几个种子点就可以匹配图像大部分的纹理区域,前提条件是建立在种子匹配可靠性很高的基础上的。通常情况下,种子越多,分布越均匀,结果就越好。说明了种子匹配点获取环节的重要性。
4 实验分析
图1 原始图像
图2 提取特征点之后的图像
图3 提取种子点图像
图4 种子点消除误匹配图像
图5 区域增长后的种子点
图6 以左图像为参考图像的视差图
文章使用一组杯子,其大小为 640×480,见图 1(a)(b);图 2(c)(d)是采用第二节的算法获取的特征点,共705对,它们比较均匀地分布于两幅图像中;图3(e)(f)是种子点提取效果图;图4(g)(h)是采用第二节去除误匹配后得到的精匹配种子点,共生成127对种子点;图5是采用第三小节的算法对种子点进行区域增长之后得到的结果,共50 183个种子点;图6是以左图象为参考图像生成的视差图。
6 结论
为了获得致密视差图,文章提出了改进的基于区域的稠密立体匹配方法。采用分步思想的策略先提取出图像对中匹配的种子点,在此基础之上采用变窗口方法进行区域增长,从而得到致密视差图。通过对测试图像的实验,证实本算法的可行性和准确性,具有实用价值。