基于区域快速生长的双目视觉立体匹配算法研究

彭彬彬, 朱大奇



基于区域快速生长的双目视觉立体匹配算法研究

彭彬彬, 朱大奇

1引言

双目视觉[1]是计算机视觉的一个重要分支,在机器人导航、无人车驾驶、医学影像重建等领域有着重要运用。双目视觉即由不同位置的两台摄像机拍摄同一幅场景,通过计算空间点在两幅图像中的视差获得该点的三维坐标值,图1为平行双目视觉示意图。立体匹配[2-5]作为双目视觉的关键问题,匹配的本质是寻求同一空间景物在不同观察点下投影图像的像素间的一一对应关系,并由此得到相应的视差图像[6]。匹配算法根据约束方式的不同大致分为2类[7]:一类为局部匹配算法,包括基于区域相关的立体匹配算法、基于特征检测的立体匹配算法和梯度法[8];另一类为全局最优算法[9-10],包括动态规划法、图割法、置信度传播算法等[11]。

图1　平行双目视觉示意图Fig.1　Schematic diagram of parallel binocular vision

现有的立体匹配算法都是基于Marr提出的立体视觉理论[12]。虽然区域匹配[13]较全局匹配速度有较大的提高,但是仍然无法满足双目立体视觉导航系统所需要的实时性。对此,本文利用区域生长技术进行全局最优化,并尝试改进生长技术,快速实现局部区域的立体匹配,进而获取可靠视差图。

2算法的改进

2.1基于区域的快速生长算法

区域生长的思路源自图像分割[14]中的区域增长算法。图2是区域生长分割示意图。输入图像基于根点和预先设置的生长条件进行生长,在遍历整幅图像后,把输入图像分割成(R1-R6)六个不同区域。

图2　区域生长分割示意图Fig.2　Schematic diagram of region growing segmentation

图3是一个线性生长示意图。如图3(a)所示为原图,图像的第一个像素为根点(红色字体),门限为2,由第一个根点线性生长后在像素为4(红色字体)的点停止了,如图3(b)所示,此时选择此像素点为根点继续生长,如图3(c)所示,直至遍历全图。

图3　线性生长示例图Fig.3　The example of linear growth

由Marr理论的视差连续性假设:场景中相邻像素的视差不会出现突变。由此假设可以利用跳跃式生长法进一步加速生长算法。如图4,跳跃2个像素点后,第4个点仍与根点相关,则把这3个点都归入生长区域;若第7个点与根点不相关,则把生长区域的下一个点作为根点进行生长。

图4　跳跃生长示意图Fig.4　The leaping growth diagram

2.2代价函数

匹配代价是整个立体匹配算法的基础,是对不同的视差进行灰度相似性测量。测量两点差异性的主要有SAD(像素灰度差的绝对值和)函数和SSD(像素灰度差的绝对值平方和)函数。

SAD函数:

(1)

SSD函数:

(2)

上述公式中,IL(x,y)和IR(x-d,y)分别表示左图和右图的像素灰度值。

基于SSD函数思想,对于彩色图像中m*n的块匹配窗口,构造差错能量函数表达式为:

(3)

3基于区域的快速生长立体匹配

3.1快速生长算法匹配步骤

快速生长算法匹配步骤如下:

步骤1:在图像中不属于任何增长区域的行中寻找根点(x,y)。

步骤2:应用式(4)计算与根节点相邻跳跃点的误差能量,如果它低于设定的能量误差阈值D,把这个点以及跳跃的点加入到视差区域,否则,返回1寻找新的根节点。其中l是跳跃步长。

(4)

步骤3:重复步骤1、2对图像的每一行进行计算,当整幅图片都被遍历时,算法停止。生长出的视差区构成视差图d(i,j)。

3.2视差图平滑与可靠度计算

在匹配过程中,由于会受到局部不明确图像区域(遮挡区域、弱纹理区域)的影响,降低了获得视差图的可靠性。为了增加视差图的可靠性,对差错能量通过设置阈值Ve加以过滤,如式(5)所示。

(5)

阈值Ve为差错能量的均值,表达式为:

Ve=αmean(Ed)

(6)

(7)

(8)

由式(7)和式(8)可以得出,当视差图的平均误差能量越小时,Rd的值越大,则视差图越可靠。

4实验分析

针对匹配质量和匹配时间问题,本文选用Middlebury大学立体图像数据集中的Teddy立体图像对进行实验仿真。匹配窗口为(1*5),摄像机焦距f=30,摄像机之间的间距T=20,α=1,dmax=40。

图5为两幅同一物体的立体图像,图6为跳跃步长为2的快速匹配结果,阈值D=70。

图5　Teddy原图Fig.5　Teddy image

图6　步长为2的跳跃生长匹配Fig.6　Stereo matching:step 2

4.1各算法在不同阈值的视差图比较

(1) 阈值D=20匹配效果

图7(a)为区域生长法的视差图,图7(b)为线性生长法的视差图,图7(c)-(e)分别为跳跃生长法步长为2、3、4时的视差图。实验参数分别为n=1,m=5,T=20,dα=1,dmax=40。分别计算5中方法的匹配时间和可靠度数值,见表1。

图7　阈值D=20的实验结果Fig.7　Results:Threshold 20

匹配时间s可靠度Rd区域生长8.790.005729线性生长2.980.004721跳跃步长21.990.004371跳跃步长31.590.003813跳跃步长41.370.003522

由图7和表1可以看出,区域生长算法的可靠度最高,但是耗时也最大,匹配时间为8.79秒,为最小匹配时间6倍以上,无法满足双目立体视觉导航系统所需的实时性要求。而跳跃生长算法匹配时间较小,实时性高,但相对来说可靠度减低;可见跳跃步长越大匹配时间越少,可靠度越 低。

(2) 阈值D=60匹配效果

图8(a)为区域生长法的视差图,图8(b)为线性生长法的视差图,图8(c)-(e)分别为跳跃生长法步长为2、3、4时的视差图。

图8　阈值D=60的实验结果Fig.8　Results:Threshold 60

(3) 阈值D=90匹配结果

图9(a)为区域生长法的视差图,图9(b)为线性生长法的视差图,图9(c)-(e)分别为跳跃生长法步长为2、3、4时的视差图。

表2为三种跳跃生长算法相对于线性生长算法的可靠度与实时性对比,从中可以看出,改进算法较线性生长法的匹配时间节约了20%以上。跳跃步长为2时,在三个不同阈值的实验下可靠度下降最多为7.41%,此时时间节约了33.22%;下降最少时为3.03%,此时时间节约了20.59%。

图9　阈值D=90的实验结果Fig.9　Results:Threshold 90

阈值对比跳跃步长2跳跃步长3跳跃步长4阈值D=20时间节约%33.2246.6454.03可靠度下降%7.4119.2325.40阈值D=60时间节约%28.2636.2339.86可靠度下降%5.5610.9615.30阈值D=90时间节约%20.5924.5029.41可靠度下降%3.035.798.76

但是步长为3和步长为4两种算法可靠度有大幅下降,这是因为跳跃式生长步长越长越省时,但是过长的步长会影响匹配的可靠性,导致有些点无法匹配或者错误匹配。实验表明,跳跃步长为2时的生长算法有较高的可靠度,并大大缩短了匹配时间,我们选择跳跃步长2算法为最佳算法。可以看出本文提出的跳跃步长2生长算法具有很高的实时性和较好的可靠性,适用于实时机器人双目视觉导航系统。

4.2跳跃步长2生长算法在不同阈值下与时间、可靠度的关系

为了进一步了解阈值D与匹配时间消耗、视差可靠性之间的关系,选取阈值范围(0,120),分别计算出跳跃步长2算法的时间消耗和可靠性。图10给出了时间消耗和可靠度的曲线图。由图10可以看出:在阈值D小于60时,时间曲线大幅下降,等于60时匹配时间已小于1 s,之后下降变得平缓。随着阈值的不断增加,时间消耗越来越小。同时可以看出在阈值D大于20时,视差图的可靠性大幅增大,之后增长变得平缓,在60-80之间可靠度最佳,D=70时达到最大值,随后逐步下降。这是由于阈值D较小时,生长出来的区域过小导致匹配精确度不高,而阈值过大时,生长区域的能量误差过大,也会导致匹配可靠度不高。因此,阈值在60-80之间时跳跃步长为2的生长匹配算法性能最佳,不仅匹配时间较小,而且可靠度也比较高,是一种理想的双目视觉立体匹配算法。

图10　跳跃步长2不同阈值的时间比较和可靠度比较Fig.10　 Step 2 algorithm:comparison of time and reliability under different thresholds

5总结

本文提出了一种基于区域的实时立体匹配改进算法。通过线性生长和跳跃式快速生长法在可靠度没有明显下降的境况下大大提高了匹配速度。通过实验对比得出结论:在步长为2时跳跃式生长法的时间消耗和可靠度都达到最佳。在阈值达到60时,它的时间消耗已经小于1 s,而此时却有着较高的可靠度,并快速匹配生成了稠密视差图。基于改进算法,双目立体视觉导航系统的实时性将大大提高。

参考文献:

[1]张元元,张丽艳,杨博文.基于双目立体视觉的无线柔性坐标测量系统[J].仪器仪表学报,2010,31(7):1613-1619.

ZHANG Yuanyuan,ZHANG Liyan,YANG Bowen.Protabla coordinate measurement system based on binocular stereo visio[J].Chinese Journal of Scientific Instrument,2010,31(7):1613-1619.

[2]Bai L,Jing X,Yue J,et al.A Weighted Color Image Stereo Matching Algorithm with Edge-Based Adaptive Window[C].2013 Seventh International Conference on Image and Graphics (ICIG),Qingdao,China,July 26-28,2013:539-544.

[3]原飞,范勇,刘畅,等.基于大窗口的自适应立体匹配[J].计算机工程与设计,2013,34(7):2441-2444.

YUAN Fei,FAN Yong,LIU Chang,et al.Adaptive stereo matching based on large window[J],Computer Engineering and Design,2013,34(7):2441-2444.

[4]霍智勇,朱秀昌.基于区域的立体匹配算法研究[J].南京邮电大学学报:自然科学版,2011,31(3):44-49.

HUO Zhiyong,ZHU Xiuchang.Research of Region Based Stereo Matching Algorithms[J].Journal of Nanjing University of Posts and Telecommunications (Natural Science),2011,31(3):44-49.

[5]郭龙源,孙长银,杨万扣,等.SIFT特征点引导的区域立体匹配算法[J].计算机工程与应用,2013,49(4):23-25,38.

GUO Longyuan,SUN Changyin,YANG Wankou,et al.Area-based stereo matching based on SIFT feature guidance[J].Computer Engineering and Applications,2013,49(4):23-25,38.

[6]Alvarez L,Deriche R,Sanchez J,et al.Dense disparity map estimation respecting image discontinuities:A PDE and scale-space based approach[J].Journal of Visual Communication and Image Representation,2002,13(1):3-21.

[7]Brown M Z,Burschka D,Hager G D.Advances in computational stereo[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2003,25(8):993-1008.

[8]王进花,曹洁,李宇,等.一种基于特征融合的点特征目标跟踪算法[J].电子测量与仪器学报,2010,24(6):536-541.

WANG Jinhua,CAO Jie,LI Yu,et al.Object tracking algorithm based on the feature fusion points[J].Journal of Electronic Measurement and Instrument,2010,24(6):536-541.

[9]石红艳.基于双目视觉的立体匹配算法的研究[D].燕山大学,2013.

SHI Hongyan.The research on stereo matching algorithm based on binocular vision[D].Yanshan University.2013.

[10]王洋,范剑英,林立军,等.物流配送路径优化理论在立体匹配技术中的应用研究[J].哈尔滨理工大学学报,2011,16(2):24-28.

WANG Yang,FAN Jianying,LIN Li-jun,et al.Optimization of Logistics Dispatching Route Theory Application and Research in Solid Matching Technic[J].Journal of Harbin University of Science and Technology,2011,16(2):24-28.

[11]Zhou Z,Li G,Fan J,et al.A new stereo matching algorithm based on image segmentation[C].2012 International Conference on Information and Automation (ICIA),Shenyang,China,6-8 June 2012:861-866.

[12]Marr D,Poggio T.A computational theory of human stereo vision[J].Proceedings of the Royal Society of London.Series B.Biological Sciences,1979,204(1156):301-328.

[13]张彦峰,黄向生,李杭,等.基于渐进可靠点生长的散斑图快速立体匹配[J].计算机科学,2014,41(z1):143-146.

ZHANG Yanfeng,HUANG Xiangsheng,LI Hang,et al.Fast Stereo Matching Based on Progressive Reliable Point Growing Matching for Speckle Pattern Images[J].Computer Science,2014,41(z1):143-146.

[14]Zhang L,Ji Q.A Bayesian Network Model for Automatic and Interactive Image Segmentation[J].IEEE Transactions on Image Processing,2011,20(9):2582-2593.

彭彬彬男(1989-),重庆人,硕士研究生,主要研究方向为图像分析与视频处理。

朱大奇男(1964-),安徽安庆人,教授,博士生导师,主要研究方向为智能故障诊断、水下机器人路径规划与控制。

(上海海事大学 水下机器人与智能系统实验室,上海201306)

摘要：立体匹配是立体视觉的重要研究内容之一,视差图的可靠性和计算复杂度直接影响了立体视觉的性能。针对目前双目视觉立体匹配算法计算量过大,本文提出了一种基于快速生长的区域立体匹配算法,应用差错能量作为匹配代价分别进行线性生长和跳跃式生长,遍历整幅图像后得到视差图,并采用均值滤波器滤除不可靠视差。实验表明该算法在保证较好可靠性的同时具有很好的实时性。

关键词：立体匹配; 快速生长; 视差图; 差错能量

Binocular Vision’s Stereo Matching Algorithm Research Based on Regional Rapid GrowthPENGBinbin,ZHUDaqi

(Laboratory of Underwater Vehicles and Intelligent System,Shanghai Maritime University,Shanghai 201306,China)

Abstract：Image stereo matching is one of the key research topics in stereo vision.Reliability of disparity maps and computational cost of algorithm directly affect the performance of stereo vision.Because the binocular vision stereo matching algorithm is complex,in this paper,a region matching algorithm based on the rapid growing is proposed.In the algorithm,the error energy is used as the matching cost for the linear growing and leaping growth.After traversing the entire image the disparity map is obtained,and the mean filter is used to filter out unreliable disparity.Experiments show that the algorithm ensures reliability and has good real-time performance.

Key words：stereo matching; rapid growing; disparity map; error energy

基金项目：上海市科委创新行动计划 (14JC1402800);国家自然科学基金青年项目(61503239)

中图分类号：TP 391

文献标识码：A