On Dynamic Programming Stereo Matching Algorithms in Computer Binocular Vision

Yi XU; Xue-jun LIU

doi:10.13718/j.cnki.xsxb.2020.09.018

Computer binocular vision technology is a non-contact measurement method that can be used under natural light conditions. It has important practical application value in reverse engineering, industrial detection, three-dimensional reconstruction, mobile robot navigation and other fields. In this paper, a stereo matching method based on dynamic programming optimization strategy has been proposed, and innovative work been carried out in matching window design and disparity calculation optimization. A rectangular window has been designed to calculate the matching cost, and a dynamic programming process based on occlusion constraints been constructed to obtain control points to suppress fringe defects on dimensionally reduced images. Four groups of images on Middlebury platform have been selected as experimental images. The stereo matching method based on confidence transfer and the stereo matching method based on graph cutting have been selected as comparison methods. The performance of this method is verified. The results of stereo matching experiments of four groups of experimental images show that the dynamic programming stereo matching method based on control point correction can obtain disparity images with dense continuity and low proportion of bad pixels, which is obviously superior to the two comparison methods.

HTML

计算机双目视觉技术，利用两个摄像机拍摄现场景物图像，进而根据左右图像的空间位置关系计算出每一个像素中的视差，从视差中恢复出景物的三维深度信息^[1].

因为计算机双目视觉在自然光下就可以使用，并且不需要和被测物接触，是一种典型的无接触测量方法，因此在三维坐标测量、逆向工程、移动机器人导航、工业在线检测等领域中得到了广泛的应用^[2-3].

从计算机双目视觉技术的实现流程上看，它包括了立体图像的拍摄、立体图像的去噪、立体图像的几何形变校正、立体图像之间的立体匹配、视差图像的优化、视差信息的三维坐标化、三维重建等等.这其中最为关键的核心环节就是立体匹配^[4].立体匹配的实质是根据一定的运算关系，从立体图像间计算出带有深度信息的视差图像，它直接关系到计算机双目视觉技术的测量精度，也是整个技术流程中耗时最长的一个环节.鉴于立体匹配在计算机双目视觉中的重要意义，本文将对其进行深入研究.

1. 立体匹配算法的发展动态

立体匹配作为双目计算机视觉中的关键技术，近年来引起了国内外学者的普遍重视，他们在此方向开展了大量的研究工作.

立体匹配是在立体图像间寻找对应点，根据对应点的像素位置差异计算出视差.为了准确地寻找到对应点，基于像素灰度的相似性判断方法首先建立起来.但是单像素存在被噪声干扰的可能，基于单像素的相似性检测很可能存在误差^[5].为此，基于窗口的像素聚合方法被设计出来，通过窗口内邻域像素的统计结果替代单像素的灰度进行匹配计算.这样的匹配窗口因为形状的不同，有矩形窗口、十字形窗口、米字型窗口等，其中矩形窗口最为常用^[6].矩形窗口虽然最为常用，但需要注重其计算匹配代价的效率.

确定了窗口内每个像素的匹配代价后，立体匹配的进行还需要配合一系列的约束条件.最常见的约束条件有视差约束条件、梯度约束条件、极线约束条件等等.通过这些约束条件，可以限制视差的搜索过程，提高匹配效率^[7-8].但是，约束条件设置过多过复杂，就会导致优化过程出现耦合.

结合窗口代价和视差约束在图像平面可以获得大部分像素的匹配结果，但是在遮挡和噪声区域还是会存在无法正确匹配的现象.为此，一系列的优化算法引入到视差计算过程中，这就是全局优化策略.这些优化方法包括极线扫描优化方法、图形切割优化方法、遗传算法优化方法、动态规划优化方法等等^[9-12].其中，动态规划优化方法执行速度快，并且具有比较理想的优化结果，易于在实际中运用，其缺点是视差图像中存在一定的条纹瑕疵^[13-14].本文以动态规划立体匹配方法为研究对象，并对其进行改进，以提升立体匹配的性能.

2. 本文动态规划立体匹配算法

2.1. 匹配代价的计算

计算立体图像上每个像素的匹配代价，是执行立体匹配的前提工作.本文采用矩形窗口，用窗口内邻域像素的灰度统计结果作为每一个像素的匹配代价测算依据，计算过程为

其中，c_x，c_y代表矩形窗口的中心点; w_x，w_y代表矩形窗口的宽和高; M^L的计算过程为

2.2. 动态规划结合遮挡因素求取视差

动态规划是一种典型的全局优化方法，其核心思想是将复杂问题进行多环节降解.如果用k表示复杂问题的每一个环节，用x_k表示对应环节的状态，用u_k表示各环节状态的迁移，那么状态迁移是否合理，就可以运用V_k，n这样函数进行度量和判断，此函数形式为

其中，v_k(x_k，u_k)表示V_k，n第k个环节下的度量值.运用动态规划优化的最终目标，就是确定一个能让整个复杂问题都得到优化的最佳V_k，n.

运用动态规划实现立体匹配，k为图像中的像素，x_k为像素的横坐标，u_k为最终要求取的视差，v_k(x_k，u_k)为用于判断匹配是否合适的度量函数.

对于v_k(x_k，u_k)的设定，我们一方面考虑公式(1)计算出的匹配代价v_data(x_k，u_k)，另一方面考虑立体图像间遮挡因素的存在，建立遮挡代价函数v_smooth(x_k，u_k)，最终得到v_k(x_k，u_k)，为

2.3. 控制点对视差图像的进一步修正

运用动态规划方法完成立体匹配，优化过程清晰、优化速度相比于其他优化方法也具有一定优势.但是，动态规划因为状态的可分性和先前状态对后续失效，会导致视差图像上出现条纹瑕疵.

为了解决条纹瑕疵对最终获取的视差图像质量的影响，文献[8]提出控制点修正技术.在视差图像上，控制点应该是确定的匹配正确的点，亦是通过左右一致性校验的点，其计算公式为

在控制点的修正之下，如果动态规划在优化过程中出现了某个错误匹配，且这一点错误视差试图对后续进行影响形成条纹瑕疵时，控制点会及时终止这种行为.

需要指出的是，控制点的计算是通过左右一致性校验方法来获得的，其耗时时间很长.所谓左右一致性校验，就是分别以立体图像中的左右图像为参考图像，各自执行一次立体匹配，这就是2次立体匹配的时间.

为了有效降低控制点的计算时间，本文在原始立体图像的降维图像上执行左右一致性校验.例如，如果原始图像的大小为256×256，那么我们就在这个图像的降2维图像64×64面积上进行左右一致性校验，从而有效地缩短整个算法的执行时间.此处控制点修正方法主要分为3个步骤：

1) 对立体图像进行小波分解，形成对应于原始图像的低1维图像，低2维图像.

2) 在低2维图像上进行左右一致性校验，提取控制点.

3) 将低2维图像上的控制点映射回原始图像，用它们作为指导动态规划匹配过程的可心点.

4. 结语

本文针对计算机双目视觉中立体匹配问题开展研究工作，提出了一种基于控制点修正的动态规划立体匹配方法(DP).首先，设置了计算匹配代价的矩形窗口; 其次，将动态规划的优化过程对应到立体匹配之上，构建了含有匹配代价和遮挡约束代价的优化函数; 再次，在降维图像上求取控制点，对动态规划的条纹效应进行抑制.选用4个组的立体图像和3种方法进行实验，实验结果充分表明本文提出的方法可以获得连续稠密的视差图像，且坏像素分布低于其他2种方法.

Figure (2) Table (1) Reference (14)

Name
	Name cannot be empty!
E-mail
	Mailbox cannot be empty! Mailbox cannot be empty!
Telephone
	Mobile number cannot be empty! Please enter a valid mobile number!
Title

Content
Verification Code

[1]	黄椰, 黄靖, 肖长诗, 等.基于双目立体视觉的船舶轨迹跟踪算法研究[J].计算机科学, 2017, 44(1): 308-313. Google Scholar
[2]	BALTER M L, CHEN A I, MAGUIRE T J, et al. Adaptive Kinematic Control of a Robotic Venipuncture Device Based on Stereo Vision, Ultrasound, and Force Guidance [J]. IEEE Transactions on Industrial Electronics (1982), 2017, 64(2): 1626-1635. doi: 10.1109/TIE.2016.2557306 CrossRef Google Scholar
[3]	顾桂鹏, 邵勇, 张钰婷, 等.基于机器视觉的零件产品检测系统设计[J].工业控制计算机, 2017, 30(1): 21-22, 25. Google Scholar
[4]	周琼.基于计算机的视觉立体匹配算法探究[J].数字通信世界, 2018(8): 108-109. Google Scholar
[5]	SINISTERRA A J, DHANAK M R, VON ELLENRIEDER K D. Stereovision-based Target Tracking System for USV Operations [J]. Ocean Engineering, 2017, 133: 197-214. doi: 10.1016/j.oceaneng.2017.01.024 CrossRef Google Scholar
[6]	门宇博, 张国印, 门朝光, 等.像素扩展自适应窗口立体匹配算法[J].哈尔滨工程大学学报, 2018, 39(3): 547-553. Google Scholar
[7]	TIJMONS S, DE CROON G C H E, REMES B D W, et al. Obstacle Avoidance Strategy Using Onboard Stereo Vision on a Flapping Wing MAV [J]. IEEE Transactions on Robotics, 2017, 33(4): 858-874. Google Scholar
[8]	高波, 马利庄.加入结构约束的半全局立体匹配方法[J].计算机应用与软件, 2009, 26(2): 244-247, 259. Google Scholar
[9]	MCGUIRE K, DE CROON G, DE WAGTER C, et al. Efficient Optical Flow and Stereo Vision for Velocity Estimation and Obstacle Avoidance on an Autonomous Pocket Drone [J]. IEEE Robotics and Automation Letters, 2017, 2(2): 1070-1076. doi: 10.1109/LRA.2017.2658940 CrossRef Google Scholar
[10]	陈华, 张志娟, 刘刚, 等.基于局部纹理特性和图像分割的分步立体匹配[J].计量学报, 2017, 38(1): 73-77. Google Scholar
[11]	周春燕, 贾渊.基于遗传算法的图像配准研究及改进[J].计算机技术与发展, 2011, 21(8): 46-49. Google Scholar
[12]	耿冬冬, 罗娜.一种基于多邻域非线性扩散的动态规划全局立体匹配算法[J].华东理工大学学报(自然科学版), 2017, 43(5): 677-683. Google Scholar
[13]	张浩峰, 赵春霞, 陈得宝.一种基于分割的两步立体匹配算法[J].中国图象图形学报, 2007, 12(11): 2098-2103. Google Scholar
[14]	王鹏, 李少达, 赵雪, 等.加权约束代价聚合的立体匹配算法[J].地理空间信息, 2018, 16(1): 58-60, 67, 8. Google Scholar

Message Board

On Dynamic Programming Stereo Matching Algorithms in Computer Binocular Vision

Abstract

References

Access History

通讯作者: 陈斌, bchen63@163.com

Article Metrics

Access History

Other Articles By Authors