文章快速检索  
  高级检索
动态规划立体匹配的状态空间分析和性能改进
杨致中, 西宝
哈尔滨工业大学 管理学院,黑龙江 哈尔滨 150001    
摘要:作为立体视觉的核心技术,立体匹配成为机器视觉领域的热点研究。为提高动态规划立体匹配方法的性能,构建了状态空间模型,分析视差搜索范围、聚合窗口大小、控制点个数这3个主要影响因素。改进方案由2个部分构成:控制点的求取放在高斯塔图像的低分辨率层级上进行,聚合窗口的形状根据两侧控制点的位置进行调整。实验结果表明,经过改进后的动态规划立体匹配方法,可以在确保视差图像质量的情况下,更加快速地完成立体匹配过程。
关键词动态规划     立体匹配     状态空间分析     控制点     聚合窗口    
State space analysis and performance improvement for stereo matching based on dynamic programming
YANG Zhizhong , XI Bao     
School of Management, Harbin Institute of Technology, Harbin 150001, China
Abstract:As a key technology for stereo vision, stereo matching has become a hot research topic in the field of machine vision. In order to improve the performance of the stereo matching method based on dynamic programming, a state space model was built to analyze three main influencing factors, including disparity search range, the size of clustering window, and the number of control points. The improved scheme is composed of two parts: the control points are computed at a low resolution level image of the Gauss tower, and the shape of the window is adjusted according to the position of control points at two sides. The experimental results show that the improved method can quickly finish the stereo matching process while guaranteeing the quality of the disparity image.
Key words: dynamic programming     stereo matching     state space analysis     control point     clustering window    

立体视觉技术是三维场景复原、医学辅助治疗、移动机器人导航领域的关键技术[1, 2],其核心阶段的工作是立体匹配。按照匹配基元的不同,立体匹配可以分为特征匹配、区域匹配、相位匹配[3]。区域匹配可以获得致密的视差场,从而获得了更加广泛的应用。全局优化策略和区域匹配结合以后,区域匹配避免了求取最优视差的局部性。2002年,Scharstein对区域匹配结合全局优化策略的立体匹配方法进行了系统总结,将此类方法的执行过程细化为4个环节——匹配代价求取、匹配代价生成、视差求取和视差优化,并构建了区域匹配方法性能测试的平台[4]。在之后的10余年时间里,基于不同全局优化策略的区域匹配方法,大多在此平台上进行了测试。从获得视差图的质量上看,基于图形切割和置信传递优化策略的区域匹配方法性能最优[5, 6],但二者的执行时间都比较长,不利于实时场合中的应用。如果综合考虑匹配精度和匹配时间两项指标,基于动态规划的立体匹配方法具有一定的优势[7]。影响动态规划立体匹配精度的主要原因在于,动态规划全局优化受到自身理论的局限,会导致错误的后向传递,从而产生条纹瑕疵。如果能在不降低匹配速度的前提下,进一步提高动态规划立体匹配的精度,无疑对其在实时场合下的应用具有重要意义。

本文首先构建状态空间分析模型,判断影响动态规划立体匹配方法匹配精度和匹配速度的重要因素,再针对这些因素进行改进,以期建立性能更佳的立体匹配方法。

1 状态空间模型构建1 状态空间模型构建

影响动态规划立体匹配性能的因素很多,有极线约束、视差搜索范围、匹配代价计算的聚合窗口、动态规划全局优化的光滑因子、修正条纹瑕疵的控制点等等。在以往的研究中,一般都通过数值的调整来观察这些因素对于匹配性能的影响,比如视觉意义上的匹配质量的变化。在本文中,将构建状态空间模型,从统计学意义上分析各种因素对于动态规划立体匹配性能的影响,以确定改进措施执行的切入点。

在现有的数据变量统计分析方法中,回归分析是应用最为普遍的数学模型[8]

式中:yt表示因变量,xt表示m×1阶的解释变量,β表示要求解的m×1阶未知参数,ut表示扰动项。

式(1)所示的回归模型中,一般假设是要求解的未知参数在估计的时间范围内是固定的,因此可以采用最小二乘法等手段加以求解,即形成最小二乘回归(ordinary least squares,OLS)。就本文的研究而言,更希望观测各个因素对动态规划立体匹配的动态影响,而状态空间模型就是一种典型的可以用于动态分析的模型[9, 10],尤其是它的可变参数形式对经济问题研究具有较好的适用性,其具体描述为

与式(1)所示的固定参数的回归模型相比,状态空间模型用可以随时间变化的βt替代了β,从而可以更加真实地反映解释变量xt和因变量yt之间的关系改变,有效地解释某些规律动态的变化。

如果βt可以用AR(1)模型加以描述的话,则有:

式中βt是不可观测变量,需要借助可观测变量ytxt来进行估计。因此,式(2)被称为量测方程,式(3)被称为状态方程。

ut和εt分别是量测方程和状态方程的扰动项,在βt服从AR(1)的情况下,它们满足:

式(4)表明,utεt相互独立,并且同样服从均值为0、方差为σ2、协方差为Q′的正态分布。

2 动态规划立体匹配性能分析

在动态规划立体匹配方法的各种影响因素中,视差搜索范围、匹配代价计算的聚合窗口、修正条纹瑕疵的控制点,是可以在匹配执行过程中加以控制和调整的,也成为本文重点考察的3项因素。

对于匹配质量的表征,选取匹配精度和匹配时间2项指标。针对立体匹配经典的测试图像(Map、Tsukuba、Sawtooth、Venus),采用式(1)~(4)所描述的状态空间模型,测试视差搜索范围、聚合窗口大小、控制点个数对于匹配质量的影响。其中,匹配精度和匹配时间取4种图像的平均值,状态空间分析的曲线如图 1所示。

图 1 3种因素的状态空间分析

图 1(a)中,从精度弹性曲线来看,在20~38 pix的区间上,视差搜索对于匹配精度起到了正向影响,影响峰值达到0.035;当视差搜索低于18 pix和大于38 pix时,匹配精度会受到负面的影响。从时间弹性曲线来看,随着视差搜索范围逐步扩大,匹配时间受到的弹性影响不断增加,峰值出现在0.09。

图 1(b)采用的是一般的方形窗口,横坐标刻度代表窗口的边长。从精度弹性曲线来看,聚合窗口大小对于匹配精度一直处于正向影响,在匹配窗口边长为5个像素以后稳定在0.05的弹性范围内。从时间弹性曲线来看,聚合窗口越大对于匹配时间的弹性影响越大,峰值出现在0.14。

图 1(c)中,从精度弹性曲线来看,随着控制点个数的增多,其对匹配精度的影响不断增加,并在35个控制点之后区稳定在0.13左右。从匹配时间曲线来看,控制点个数的弹性影响陡峭上升,并在45个时达到0.225左右。

综合3幅图的弹性分析结果,控制点个数对于匹配精度和匹配时间的影响最大,聚合窗口大小的影响次之,最后是视差搜索范围。

3 动态规划立体匹配改进方案

根据本文第2节的分析可知,对动态规划立体匹配性能影响最大的是控制点。结合动态规划立体匹配的实际情况可知,如果不使用控制点,匹配结果会沿着极线方向出现明显的条纹瑕疵;如果使用过多的控制点,匹配时间又会明显的增加。

在动态规划立体匹配的传统方法中,对于控制点的求取是比较费时的,要通过执行左右一致性校验来确定最终的控制点,这相当于执行两次立体匹配。

通过图 1的弹性曲线可知,控制点的数量增加到一定程度时,对于匹配精度的影响已经不大。因此,在动态规划立体匹配的过程中,求取足以控制匹配精度的控制点即可。

3.1 控制点求取方案

本文对于控制点的求取,构建了如下的方案:首先,利用高斯金子塔获得图像的各级分辨率结果;其次,在低分辨率图像上求取控制点。因为低分辨率图像的像素数目大为减少,控制点的求取速度将显著提高。另一方面,虽然低分辨率上求取的控制点会少于原始图像上的控制点,但其数目仍然满足匹配精度的控制要求。

如果用G0表达原始图像,那么在高斯金字塔中表示第1层图像。要获得高斯塔中的第L层图像,可以将第L-1层图像执行低通卷积,进而将低通结果进行间隔采样,其数学描述为

式中:n代表高斯金字塔的层数;w(m,n)称之为窗口函数,其5阶形式为

经过高斯金字塔处理,可以获得原始图像的各级分辨率效果,如图 2所示。

图 2 金字塔结构示意图

控制点的求取放在第3层图像上进行,以256 pix×256 pix大小的图像为例,第3层的图像像素减少到64 pix×64 pix。

控制点的求取方法,采用局部最优匹配SAD算子结合左右一致性检验技术。SAD算子是绝对值型相似性测度,比平方和型测度算子的计算量小:

式中:SAD(x,y,d)代表相似性,xy为像素的横纵座标,I1I2为像素灰度,mn为聚合窗口的尺寸。

执行左右一致性交验的过程,先以右侧图像为基准图,执行SAD算子寻找最佳匹配:

再以左图像为基准图,执行SAD算子寻找最佳匹配:

对于一个像素而言,SADr(d,i)和SADl(d,i)的计算结果一致,则该像素对应的视差值为视差图像上的控制点。

3.2 聚合窗口修正方案

聚合窗口的尺寸对于匹配过程也有很大影响,尺寸过小会降低聚合过程的可信度,尺寸过大会导致匹配时间的增加。

根据图 1(b)的分析曲线,本文选择5 pix×5 pix尺寸的聚合窗口。如果使用一般的矩形窗口,聚合计算的像素点位25个。为了减少计算量,依托控制点进行进一步的修正。

控制点是视差图像上已经确定为正确的匹配点,也是动态规划全局优化时优化路径必须要经过的点。据此,将控制点看作在聚合过程中具有调整聚合窗口形状作用的点,对5 pix×5 pix像素窗口进行修正,具体处理过程如图 3所示。

图 3 聚合窗口修正过程

图 3中,黑色方块代表控制点像素,灰色(斜剖面线)方块代表待匹配像素,白色(空白)方块代表聚合窗口其他像素。

聚合过程是沿着极线搜索最佳匹配的过程,图 3就是由右向左的搜索过程。当控制点恰好为待匹配点时,聚合窗口的尺寸选择了其周围邻域的21个像素。但实际上,这一点不需计算(控制点就是匹配正确的点),只是为了便于说明后续处理才画出,故此用虚线表示。

随着搜索过程离开当前控制点、从右向左地沿极线向下一个控制点运动,当前控制点对聚合窗口的作用逐渐弱化,而目标控制点的作用逐渐增强,使得,聚合窗口的形状沿极线方向不断变化。

图 3中最上方的情况,描述了搜索过程正好到达了2个控制点之间,之后的过程类似。

在这种修正措施下,从当前控制点到目标控制点移动的过程中,聚合窗口的像素分别是21、19、17、13、13、13、17、19、21,并且2个21 pix的聚合窗口是不需要计算的。

可以看出经过这一修正,相比于25 pix的矩形聚合窗口,计算量会大大降低。

4 实验结果与分析 4 实验结果与分析

为了验证本文方法的有效性,采用tuskuba、venus标准立体图像作为实验对象,分别执行传统动态规划立体匹配和本文改进的动态规划立体匹配,结果分别如图 4、5所示。

图 4 实验结果一
图 5 实验结果二

图 4中可以看出,与Tsukuba立体图像的真实视差图像相比,传统动态规划方法和本文方法都获得了较为理想的视差图像,但传统动态规划方法获得的视差图像中,条纹效应要明显的多。经过本文的改进措施,条纹效应在图 4(d)中得到了抑制。这有两点原因,一方面高斯塔第3层图像的使用,使得局部最优匹配求取控制点的结果更为准确;另一方面,聚合窗口形状的调整,更注重了控制点的作用,减少了优化过程出现错误和错误传播的几率。

图 5中,有关Venus立体图像的实验结果,也反映出和图 4结果一样的结论。

下面,进一步给出改进前后两种方法匹配时间上的比较结果。实验过程中使用的计算机配置情况为:AMD四核CPU、威刚DDR3 1600 4G内存。2组立体图像执行立体匹配的时间如表 1所示。

表 1 匹配时间
ms
数据传统动态规划本文改进方法
Tsukuba立体图像430221
Venus立体图像357174

表 1的结果可以看出,经过本文方法的改进,动态规划立体匹配的时间大幅度下降。这有两点原因,一方面控制点的求取放在低分辨率图像上,执行SAD和左右一致性校验的时间大为缩短;另一方面,聚合窗口的像素数目,比一般矩形窗口少,也使得匹配时间降低。

5 结论

动态规划立体匹配是立体匹配方法中的典型方法之一,影响其匹配性能的因素也比较多。本文构建了状态空间模型,分析视差搜索范围、聚合窗口大小、控制点个数3个关键因素对于动态规划立体匹配的影响,证实了控制点个数的影响最大、聚合窗口大小的影响次之。

基于状态空间模型的分析结果,本文对传统动态规划立体匹配方法进行了以下改进:

1)构建原始图像的高斯塔多级分辨率图像,将控制点的求取放在第3层低分辨率上进行。

2)根据控制点的位置,调整极线上搜索最佳匹配的聚合窗口形状。

实验结果表明,经过上述改进措施,动态规划立体匹配方法的匹配精度得以保证并有所提高,匹配时间显著降低,增强了在高实时性场合中应用的可能性。

参考文献
[1] ARSHAD J, SUBRATA R. Augmenting graph cut with TV-L approach for robust stereo matching[C]// International Conference on Image Information Processing. Shimla, India, 2011: 2201-2207.
[2] WANG Y C, WU C Y, CHUNG P C. Constraint-based correspondence matching for stereo-based interactive robotic massage machine[J]. Journal of Intelligent and Robotic Systems: Theory and Applications, 2013, 72(2): 179-196.
[3] 姜宏志, 赵慧洁, 梁宵月, 等. 基于极线校正的快速相位立体匹配[J]. 光学精密工程, 2011, 19(10): 2520-2525.
[4] SCHARSTEIN D, SZELISKI R. A taxonomy and evaluation of dense two-frame stereo correspondence algorithms[J]. International Journal on Computer Vision, 2002, 47(1): 7-42.
[5] 祝世平, 杨柳. 基于自适应分水岭的图割的立体匹配算法[J]. 光学学报, 2013, 33(3): 1-9.
[6] 周自维, 樊继壮, 赵杰, 刘晓丽. 基于置信传播的立体匹配并行算法[J]. 光学精密工程, 2011, 19(11): 2774-2781.
[7] 林俊钦, 胡晓明, 闫达远. 场景轮廓的动态规划立体匹配算法[J]. 光学技术, 2013, 39(1): 87-91.
[8] 杨群. 我国房地产市场货币政策中介指标的选择——基于VEC模型的脉冲响应和方差分解[J]. 江西社会科学, 2011, 12: 49-53.
[9] 黄瑜. 货币政策对房地产市场供求影响的动态测度——基于状态空间模型的实证[J]. 经济管理, 2010, 479(11): 16-20.
[10] 于羽. 货币政策的通胀与通缩效应: 基于状态空间模型的计量分析[D]. 长春: 吉林大学, 2011: 26-32.

文章信息

杨致中,西宝
YANG Zhizhong,XI Bao
动态规划立体匹配的状态空间分析和性能改进
State space analysis and performance improvement for stereo matching based on dynamic programming
应用科技, 2015, 42(05): 19-23
Applied Science and Technology, 2015, 42(05): 19-23.
DOI:10.11991/yykj.201506035

文章历史

收稿日期:2015-06-24
网络出版日期:2015-09-21

相关文章

工作空间