基于区域分割的动态规划立体匹配算法

汤炎甫

(福州大学测试中心，福建 福州 350002)

基于区域分割的动态规划立体匹配算法

汤炎甫

(福州大学测试中心，福建 福州 350002)

提出一种基于区域分割的动态规划立体匹配算法。首先参考图像经自适应多阈值切割之后，得到一个由区域组成的集合，并沿着各个闭合区域的边界进行动态规划跟踪，然后对于非匹配区域和区域内部分别作视差融合和视差插值处理，获得最终的稠密视差图。实验结果表明，该算法能够取得较为理想的效果，视差图横向“条纹”瑕疵和边界区域上的误匹配点明显减少，层次更加分明，整个视差图平滑性较好，匹配效率有了显著提高。

视差图；动态规划；立体匹配；区域分割

立体视觉技术是人们通过研究生物捕获三维空间信息的视觉系统而发展起来的一门重要的 3D显示技术，即通过借助多方位地拍摄目标图像，并合成目标的深度视差信息，以完成空间目标的立体场景信息重建[1]。立体匹配就是从两视点或多视点图像组中获取空间目标深度信息的一个重要步骤，而视差匹配的高精确度和应用实时性这两大难题吸引了诸多学者前来攻关。由匹配约束对象的差异性，通常将立体匹配算法[2]划分为两类，一类是针对像素局部小邻域来制定约束策略的局部匹配算法[3]，这类算法易于操作、运行速度快，但在遮挡区域的匹配效果较差；另一类是采用对整幅图像制定约束策略的全局匹配算法，此类算法在遮挡区域能够实现较低的误匹配率，但计算的复杂度较高，运行速率较慢，难以达到实时性要求。全局匹配算法主要包括动态规划(dynamic programming，DP)[4-5]和图切割(graph cuts，GC)[6]等。其中DP立体匹配算法能够高效地实现稠密视差图的获取，但缺乏行、列双向连续性约束的融合，视差图易出现“条纹”瑕疵，同时在非连续和遮挡区域，该算法的匹配效果有限，甚至会出现较高的误匹配率。针对DP算法的不足，Bobick和Intille[7]制定了地面控制点(ground control point，GCP)策略来约束多种子搜索路径，该算法能够较好地消除行间误匹配对全局匹配的影响，但由于未能制定有效的行间深度关系的约束策略，容易产生类“拖尾”的块状误匹配。而Wei和Quan[8]采用基于区域分割的方法来制定立体匹配约束策略，这种针对每个分割区域来填充视差值的做法能够有效地避免视差图“拖尾”现象的出现。Lin和Tomasi[9]通过多次迭代来拟合区域平面约束，此举虽然可以得到较好的拟合结果，但耗时的数据处理不利于实际应用。

鉴于此，该文提出一种基于区域分割的DP立体匹配算法。首先将参考图像自适应多阈值切割，得到一个由区域组成的集合，并沿着各个闭合区域的边界来进行DP跟踪，然后对于非匹配区域和区域内部分别作视差融合和视差插值处理。经验证，所提算法的运行时间较快，匹配效果良好，并获得了稠密视差图。

1 新型视差图获取算法的研究

近年来，基于小区域集合分解处理数据的匹配算法被广泛运用于立体匹配当中，究其原因在于此类算法能够较好地处理视差图遮挡区域的匹配问题，同时能够保持区域内部视差的连续性。本算法所采用的自适应多阈值图像分割技术[10]主要通过捕捉二维图像的灰度数据信息，并根据设定的精度与参数来求取阈值最优解，确保目标能够在背景图像中被有效提取，而且便于视差图的优化匹配。参考图像由自适应多阈值切割之后，得到了一个由区域组成的集合，并沿着各个闭合区域的边界来进行DP跟踪。相较于分割图像区域内部，在区域边界上的不连续匹配点所占比例较高，故处理好区域边界上的匹配结果会使产生误匹配的概率大大减少，同时这部分的视差匹配结果更加有效、可信。本算法首先从边界上多个种子点出发沿边界跟踪视差，使用GCP来约束DP路径，并通过统计、计算区域内GCP视差值，获得区域的视差区间，同时对于非匹配区域做视差融合处理，最后采用一些匹配度较高的GCP和分割区域边界点作为构建Delaunay三角网格的已知点集，并制定相关区域内部连续、平滑约束策略，对未匹配点进行三角片插值[11]填充，以获取稠密视差表面。此算法流程如图1所示。

图1 算法流程

1.1 自适应多阈值图像分割

图像分割是将一幅参考图像划分为若干区域的过程，在众多的图像分割方法中，阈值法因为其计算量小、易于操作等优点被广泛采用。阈值法就是对比图像背景与目标在灰度特征上的不同，通过设定自适应阈值参数对图像进行区域分割，从而提取出背景中的目标。在实际应用中，处理单一目标灰度的图像比较少，同时繁杂的目标和背景会导致单一阈值难以将图像区域进行清晰划分，这时一般会采用多阈值分割方法。本文采用的是自适应多阈值图像分割算法，详细步骤如下：①借助势基函数[12]聚类来确定阈值划分区间，设定A、tc和 ha分别为势基函数类的个数、分割阈值和聚类中心灰度值；②在 hc和 hc+1之间遍历阈值 tc，并制定形状连通度约束准则，并求解分割阈值最优解由公式：式中，和分别表示目标、区域边界点所占比例，表示连通度准则；③获取阈值组最优解④自适应多阈值图像分割。

为了检验自适应阈值分割的效果，将lena实验图进行分步切割，如图2所示。

图2 多阈值图像分割过程示意图

由上所示，将 lena实验图进行多阈值图像分割，其中势基函数类的个数A分别从5~9取值，而多阈值分割实验图是由A=9时得到的。显然，单个阈值分割效果难以满足实际需求，需要采用自适应多阈值图像分割方法。

1.2 多种子动态规划获取边界视差分布

获取边界视差分布的一个简单方法是选定边界上一个种子点，并从它开始搜索DP寻径，直至获取整个边界视差分布。但由于区域遮挡和背景模糊等因素的干扰，仅仅依靠采用单个种子点来实现全局视差跟踪的匹配效果往往不尽人意。基于此，该算法将采用多个种子点DP寻径策略，根据各自分割的子区域来设定匹配相似度阈值，并寻找各个区域边界上相对应的匹配点。一次边界视差跟踪过程就是从一个种子点沿着边界路线出发直到返回该起点所获取边界点视差值的过程，如图3所示。

图3中的矩形框图是以区域边界上的像素点为横轴、视差值为纵轴的视差分布平面示意图，对每一个边界的种子点进行动态跟踪，以获得其对应的所有匹配点，将多种子DP过程作量化处理，那么相应的匹配能量为：

其中，inE 和disE 分别为对应到像素灰度相似性和视差连续性的能量值，1w和2w均为权值。假设当前边界点为n，,nid 为n和第i个候选匹配点的视差值，则通过下述途径确定n的能量值 (,)E n d，搜

图3 多种子动态规划示意图

索n在图3中的所有可能匹配点，则有：

其中，mK 表示匹配成功，是一个预设的常值，则结合式(3)可得：

其中 i= 1,2,··, Mnum，n在图3中候选匹配点的数目，若搜索不到候选匹配点的情况下，该算法设定能量值为一常值：

该算法采用对多个种子点进行多次边界视差跟踪，以提高视差结果的可靠性。由算法运行结果可知，从不同种子点出发所获取的跟踪路径较为接近，而事实上，视差匹配往往出现的是一对多的情况，为了确定边界点所对应视差值的唯一解，该算法制定了一种投票选定策略，即在两个视差值很接近的情况下，对于多个候选视差值都依存于同一边界点时，该算法采取彼此互相支持投票的策略以表示肯定对方，最终赢票数最多的视差值就是唯一被选定的，即为所求视差值最优解，对于每个边界点投票选出票数和多个视差值分别假定为V、d，那么视差分布判定式为：

其中，i、j均为边界点序号，diTH 是视差变化量阈值。由投票法则来选定所有区域边界点的视差值，直至获得所有分割区域边界的视差分布。

1.3 视差点插值填充

由于不连续匹配点集中分布在区域边界上，而区域内部的匹配点具有连续、平滑的特点，则可以在得到区域边界视差后采用插值方法得到区域内部视差。由插值方式的不同，对于区域中的未匹配点视差插值可按两种策略来处理：其一，由其邻域内的GCP和边界匹配点的视差值均值来插值填充；其二，由其邻域内部分遮挡或无遮挡区域中的最小视差值来插值填充。

该算法采用一些匹配度较高的 GCP和分割区域边界点作为构建 Delaunay三角网格的已知点集，并制定相关区域内部连续、平滑约束策略，对未匹配点采用三角片插值[12]填充。该插值策略操作简单、运行较快，能够得到很好的填充效果。

2 实验结果与分析

实验在Intel Core i5 4.2 GHz CPU主频、4 G内存、Windows XP操作系统平台下进行，采用Visual C++ 2010应用软件来验证该算法的实时性和精确度。该算法采用Tsukuba和Teddy(源自Middlebury网站)测试图作为实验对象，像素尺寸为384 ×288，该算法参考左图进行自适应多阈值图像分割，所获得了1、10、28、56、89、105、130、166、185、198、220、240、253、260计14个阈值，由于各区域内存在一些孤立点或是一些孤立的小区域，该算法选择在边界提取前先用中值滤波方法将其并入各相邻区域，然后沿着各个闭合区域的边界来进行DP跟踪并获取视差分布，最后对非匹配区域和区域内部分别作视差融合和视差插值处理，以获得稠密视差图。

为了体现立体匹配效果的优越性，该算法视差结果图与另两种算法(分别为双向 DP算法(DoubleDP)和传统的GC算法)相对照，通过三种评价标准来评判立体匹配的效果：E(%)、D(%)、T(s)，其中E(%)表示误匹配率，D(%)表示匹配率，T(s) 表示算法的执行时间。

其中， dT(i, j)表示标准视差图， dC(i, j)表示计算得到的视差图，N为视差图的像素总数，δd为视差错误阈值。

图4 三种算法分别得到的视差图

图4和表1所示的三种算法得到的视差图结果可知，本文算法相较于DoubleDP算法和GC算法，其立体匹配效率有了显著提高，同时视差图横向“条纹”瑕疵和边界区域上的误匹配点明显减少，层次更加分明，整个视差图平滑性较好。在图像各分割区域间隙中的一些孤立点或小区域采用中值滤波归并到相邻区域所导致匹配结果的不确定性，以及区域内插值填充的不完整性等诸多原因，致使视差图仍存在一些误匹配点。

表1 三种匹配算法的性能比较

3 结 束 语

提出一种基于区域分割的DP立体匹配算法，首先参考图像经自适应多阈值切割之后，得到了一个由区域组成的集合，并沿着各个闭合区域的边界来进行DP跟踪，然后对于非匹配区域和区域内部分别作视差融合和视差插值处理，以获得最终的稠密视差图。实验结果表明，该算法能够取得较为理想的效果，与DP算法和GC算法相比，视差图横向“条纹”瑕疵和边界区域上的误匹配点明显减少，层次更加分明，整个视差图平滑性较好，匹配效率有了显著提高。

由于 GCP的选定策略和区域自适应阈值分割对该算法视差匹配有着较大的影响，而聚合操作能够促使区域分割更加明晰、精确，同时 GCP的选定策略有待进一步地优化，故将沿着更加全面准确的 GCP验证策略和更为高效可靠的图像分割算法方向作后续的研究工作。

[1]刘晓丽, 徐光柱, 雷帮军, 等. 立体匹配技术研究[C]// 2010系统仿真技术及应用学术会议论文集, 2010: 597-602.

[2]Shi C B, Wang G J, Pei X K, et al. An interleaving updating framework of disparity and confidence map for stereo matching [J]. IEICEeice TRANSACTIONS on Information and Systems, 2012, E95-D(5): 1552-1555.

[3]Zhou Yihao, Chen Yanqiu. Feature matching for automated and reliable initialization in three-dimensional digital image correlation [J]. Optics and Lasers in Engineering, 2013, 51(3): 213-223.

[4]Hu Tingbo, Qi Baojun, Wu Tao, et al. Stereo matching using weighted dynamic programming on a single-direction four-connected tree [J]. Computer Vision and Image Understanding, 2012, 116(8): 908-921.

[5]Yu Shuchun, Yu Xiaoyang, Hu Lijuan, et al. Stereo matching for dynamic programming on TRIZ [J]. Information Technology Journal, 2012, 11(7): 891-897.

[6]Wang Daolei, Kah B L. Obtaining depth map from segment-based stereo matching using graph cuts [J]. Journal of Visual Communication and Image Representation, 2011, 22(4): 325-331.

[7]Bobick A F, Intille S S. Large occlusion stereo [J]. International Journal of Computer Vision, 1999, 33(3): 181-200.

[8]Wei Yichen, Quan Long. Region-based progressive stereo matching [C]//Conference on Computer Vision and Pattern Recognition, Washington, DC, 2004: 106-113.

[9]Lin M H, Tomasi C. Surfaces with occlusions from layered stereo [J]. Pattern Analysis and Machine Intelligence, 2004, 26(8): 1073-1078.

[10]张 伟, 蒋 宏, 任 章. 自适应多阈值图像分割算法[J]. 自动化技术与应用, 2007, 26(8): 71-73．

[11]Ji Fengxin, Ou Zongying, Qin Xujia, et al. An algorithm of reconstructing 3D surface from discrete data of layered images based on delaunay triangulation [J]. Journal of Engineering Graphics, 2001, 22(2): 53-58.

[12]裴继红, 谢维信. 势函数聚类自适应多阈值图像分割[J]. 计算机学报, 1999, 22(7): 758-762.

Dynamic Programming Stereo Matching Algorithm Based on Region Segmentation

Tang Yanfu
(Measuring Center of Fuzhou University, Fuzhou Fujian 350002, China)

A dynamic programming stereo matching algorithm was proposed based on region segmentation. Firstly, the reference image was divided into several different regions by use of adaptive multi-threshold image segmentation. Then, the multi-seed dynamic programming approach was presented for acquiring disparity distribution along the border of closed areas. Finally, parallax in the mismatching area was fused together and interpolated within its area in order to obtain a dense disparity map. The experiment results reveal that the algorithm is better effective both in decreasing the overall matching error rates on the boundary of the domain and reducing apparent defective stripes. Moreover, its efficiency of matching is improved significantly.

disparity map; dynamic programming; stereo matching; region segmentation

TP 751

A

2095-302X(2015)01-0090-05

2014-03-25；定稿日期：2014-08-25

国家“863”重大专项基金资助项目(2012AA03A301，2013AA030601)；国家自然科学基金资助项目(61101169，61106053)；福建省自然科学基金资助项目(2011J01347)

汤炎甫(1964–)，男，福建建瓯人，工程师，工学学士。主要研究方向为驱动程序开发与仿真、应用软件开发等。E-mail：tyf406@163.com