双目立体视觉区域局部匹配算法的改进及其实现

何人杰

摘 要:匹配算法是双目立体视觉中关键技术之一。这里讨论双目立体视觉区域局部匹配的相似性测度函数、局部相关匹配算法,并分析其复杂度,进而提出模板滑动的匹配算法。在VC++平台上,通过双相机实验系统的标准测试图及实际场景图对所提方法进行验证。分析和实验结果都表明了该改进算法的有效性和快速性。

关键词:双目立体视觉;区域相关;立体匹配;标准测试图

中图分类号:TP391文献标识码:A

文章编号:1004-373X(2009)12-068-03

Improvement of Regional Related Match Algorithm for

Binocular Stereo Vision and Its Implementation

HE Renjie

(Electronics and Information School,Northwestern Polytechnical University,Xi′an,710129,China)

Abstract:Match algorithm is one of key techniques in the binocular stereo vision system.The similarity functions,the regional related match algorithms for Binocular stereo vision are discussed and the algorithmic complexity is analyzed.Moreover,a new improved regional related match algorithm by sliding pattern plate is proposed to decrease the matching time and a test software is designed by using VC++ and OPEN-CV.A number of experiments are carried out through the two-camera system and the standard test images as well as practical sense images.The analytical and experimental results show that the improved method is effective and its matching time is decreased greatly.

Keywords:binocular stereo vision;regional related;stereo match;standard test image

0 引 言

立体视觉是计算机视觉的一个重要分支,主要研究如何借助成像技术从图像中获取场景中物体的三维信息[1-3] 。立体视觉的基本方法是从两个或者多个视点去观察同一场景,获得在不同视角下的一组图像;然后通过三角测量原理获得不同图像中对应像素间的视差,并从中获得深度信息,进而与平面信息整合形成立体图像。立体匹配是立体视觉算法中最重要也是最困难的部分。

根据匹配基元的不同,现有的立体匹配方法可大致分为三类:基于特征的匹配[4,5],基于区域的匹配[6]和基于相位的匹配[7]。

本文重点研究双目视觉立体匹配中基于区域的局部匹配算法,对基于SAD(Sum of Absolute Difference)的区域匹配算法通过模板滑动进行了改进。经分析和多次实验结果表明,该改进算法具有有效性和快速性。

1 双目立体视觉区域局部匹配的理论基础

1.1 相似性测度函数

匹配算法的实质就是估计待匹配点和候选匹配点之间的相似性程度,评价这种相似性程度度量方法有多种。由于单个像素点所包含的信息太少,因而只依据单个像素点是的信息建立度量方法可靠性较差。为了提高相似性度量方法的可靠性,一般需要在匹配点上的一个小邻域内的像素点集合中进行。

表1列出了目前几种主要的相似性测度函数[6]。其中,IL(x,y),IR(x,y)分别代表左右图像中像素坐标(x,y)处的灰度值;IL(x,y),IR(x,y)分别表示左右图中以坐标(x,y)为中心,在窗口范围U内像素灰度的平均值。由于SAD相似性测度函数在时间以及匹配质量方面较其他测度函数更具有优势,且实现较简单[8]。这里研究选择SAD作为局部相关匹配算法的相似性测度函数。

1.2 局部相关匹配算法原理

局部相关匹配算法是以基准图像中待匹配点为中心像素来创建一个大小为n×n的矩形窗,由该窗口内的像素灰度分布来表征该像素。在第二幅图像中,沿极线在视差范围内取出与基准点邻域同样大小为n×n的像素邻域,依次与匹配点的窗口进行比较,最大相似性对应的点就是最佳匹配。整个匹配过程如图1所示。

表1 几种相似性测度函数

名称公式

SAD∑(i,j)∈U|IL(x+i,y+j)-IR(x+dx+i,y+j)|

ZSAD∑(i,j)∈U|[IL(x+i,y+j)-IR(x,y)]-

[IR(x+dx+i,y+j)-IR(x+dx,y)]|

SSD∑(i,j)∈U[IL(x+i,y+j)-IR(x+dx+i,y+j)]2

ZSSD∑(i,j)∈U[IL(x+i,y+j)-IL(x,y)]-

[IR(x+dx+i,y+j)-IR(x+dx,y)]2

SSD-N∑(i,j)∈U[IL(x+i,y+j)-IR(x+dx+i,y+j)]2∑(i,j)∈UIL(x+i,y+j)2∑(i,j)∈UIR(x+dx+i,y+j)2

SCP∑(i,j)∈UIL(x+i,y+j)IR(x+dx+i,y+j)

图1 局部相关算法原理示意图

1.3 局部相关匹配算法的时间复杂度

在图1(a)中坐标为(x,y)的像素点,算法要计算图1(b)中所有相关像素的相似性。根据极线约束以及视差约束,在图1(b)中只需计算同一极线上,视差范围内的像素相似性即可,需要的计算量为:

T(x,y)=dmaxn2(1)

式中:n为正方形窗口边长;dmax为最大视差。设W为图像的宽度;H为图像的高度,对于整幅图片,全部相似性的计算量为:

T=∑0≤i

易知,局部相关匹配算法的时间复杂度为O(WHdmaxn2)。

1.4 局部相关匹配算法的改进

若假设匹配窗口的边长为2n+1,对于每行像素,其相似性测度函数为P(x,y,d)=∑ni=-n|IL(x+i,y)-IR(x+i+d,y)|;在模板向右滑动时,P(x+1,y,d)可由之前的计算结果得到,有迭代公式:

P(x+1,y,d)=P(x,y,d)+[|IL(x+n+1,y)-

IR(x+n+1+d,y)|-|IL(x-n,y)-

IR(x-n+d,y)|](3)

即在模板滑动时,不需要重新计算整个窗口的SAD,而只需计算新的一列SAD。分析可知,改进后算法的时间复杂度由O(WHdmaxn2)降为O(WHdmaxn),算法实时性有了较大提升。

2 双目立体视觉区域局部匹配算法的实现

2.1 实验环境

该研究的实验主要是通过计算机编程实现区域局部匹配算法,并在双相机系统上利用标准和实际场景图像进行验证性实验的。以VC++ 6.0及OPENCV为编程环境,完成验证软件设计。

该研究的验证实验使用了西安交通大学系统工程所的实验设备(如图2所示)。两只摄像机平行放置,其位置姿态参数已由标定结果给出,如表2所示。

图2 试验系统

表2 相机标定参数表(以像素为单位)

参数指标左相机右相机

焦距699.85696.15

相机中心[392.34 283.94][389.26 308.18]

畸变[-0.270 20 0.454 48][-0.239 75 0.256 22]

旋转角/radα=0.013 77,β=0.001 07,γ=0.000 38

相对位移/mmt1=87.921,t2=1.205,t3=4.980

摄像机与处理计算机之间通过双1394总线连接,计算机中配备2块64位PCI-1394卡,以适应摄像机高速图像流的要求。摄像机的主要参数如表3所示。

表3 摄像机参数

摄像机特性参数

CCD传感器Sony Progressive Scan CCDs

CCD最大像素1 624×1 224

像素大小4.4 μm×4.4 μm

支持图像大小320×240(30),640×480(30),800×600(30),1 600×1 200(15)

快门0.01~66.63 ms

图像输出方式双1394总线输出

2.2 软件设计流程图

系统算法流程图如图3所示。

图3 系统算法流程图

2.3 实验结果

部分实验结果如图4所示。

图4 实验结果

由图4可知[10],实验得到的图片较好地完成了对现实场景中的匹配,可以较直接地从所得视差图中获得物体的深度信息。

同时,图像边缘处的匹配精度受到图像边界的影响,误差较大,真实场景图片中噪声较大,导致误匹配较多。如何减少误差,提高精度是现在和今后重点考虑的问题之一。

3 结 语

这里对双目立体视觉中的区域局部匹配算法进行讨论,对现有SAD算法进行了改进,较显著地提高了匹配速度。在实验平台上较好地完成了对标准图像及现实场景图像的视差图获取,验证了算法的有效性和快速性。

参考文献

[1]章毓晋.图像工程(下册)图像理解[M].2版.北京:清华大学出版社,2007.

[2]何明一,卫保国.数字图像处理[M].北京:科学出版社,2008.

[3]游素亚.立体视觉研究的现状与进展[J].中国图像图形学报,1997,2(1):1-2.

[4]Hajar Sadeghi,Payman Moallem,Monadjemi S A.Feature Based Dense Stereo Matching using Dynamic Programming and Color[J].International Journal of Computational Intelligence,2004,4(3):179-186.

[5]高峰,文贡坚,吕金建.一种准自动高精度图像配准算法[J].现代电子技术,2007,30(6):56-59.

[6]Kuk Jin Yoon,In So Kweon.Adaptive Support-Weight Approach for Correspondence Search[A].APRIL[C].2006,28(4):650-655.

[7]徐奕,周军,周源华.立体视觉匹配技术[J].计算机工程与应用,2003,39(15):388-392.

[8]Cyganek B,Borgosz J.A Comparative Study of Performance and Implementation of Some Area-based Stereo Algorithms[A].CAIP[C].2001,21(24):709-716.

[9]夏永泉.计算机视觉中双目匹配相关技术的研究[D].南京:南京理工大学,2007.

[10]Middlebury College Stereo Vision Research[EB/OL].http://cat.middlebury.edu,2008.