基于双权重聚合的立体匹配算法

引用本文

何凯, 朱程涛, 姚静娴. 基于双权重聚合的立体匹配算法. 2015, 45(4): 1318-1323
HE Kai, ZHU Cheng-tao, YAO Jing-xian. Stereo matching algorithm based on double weighting aggregation. Journal of Jilin University Engineering and Technology Edition, 2015, 45(4): 1318-1323 复制到剪切板

Permissions

基于双权重聚合的立体匹配算法

何凯, 朱程涛, 姚静娴

天津大学电子信息工程学院,天津 300072

作者简介:何凯(1972-),男,副教授,博士.研究方向:数字图像及视频修复,电子稳像,图像拼接,纹理识别.E-mail:hekai626@163.com

基金:国家自然科学基金项目(61271326)

摘要

针对传统的局部立体匹配算法通常采用基于窗口聚合匹配的方法获得视差图,采用分割与平面拟合的方法进行视差精炼,算法性能过度依赖于窗口尺寸、分割与数据拟合的精度的问题,提出了基于双边滤波的双权重聚合方法,利用快速匹配代价的方法进行聚合,在视差精炼阶段采用双曲线平滑聚合匹配代价的策略;这种不依赖于窗口大小的算法有利于提高匹配精度。仿真实验结果表明,本文算法在低纹理区域和深度不连续区域均得到了较高的立体匹配精度;针对实际场景进行的立体匹配,可以得到较高精度的视差图及三维重建效果。

关键词: 通信技术; 立体匹配; 权重聚合; 快速代价聚合; 视差精炼; 三维重建

中图分类号:TN91 文献标志码:A 文章编号:1671-5497(2015)04-1318-06

Stereo matching algorithm based on double weighting aggregation

HE Kai, ZHU Cheng-tao, YAO Jing-xian

School of Electronic Information Engineering, Tianjin University, Tianjin 300072, China

Abstract

In traditional local matching algorithms, the window-based aggregation methods are usually used to obtain disparity map; also, the segmentation and plane fitting methods are used in disparity refinement. The performance of the algorithms is greatly dependent on the window size, and precision of segmentation and data fitting methods. In this paper, a stereo matching algorithm based bilateral filter is proposed, which is called double weighting aggregation. The fast cost aggregation method and hyperbola are employed to smooth the matching cost. The proposed algorithm is beneficial to improve the stereo matching accuracy since it is independent on the window size. The simulation results show that the proposed algorithm can obtain higher accuracy disparity map in low-texture and depth discontinuity regions. Besides, superior disparity map and 3D reconstruction results are also achieved in real stereo images.

Keyword: communication; stereo matching; weighted aggregation; fast cost aggregation; disparity refinement; 3D reconstruction

Show Figures

0 引言

立体匹配算法主要是通过建立一个能量代价函数, 通过此能量代价函数最小化来估计像素点视差值^[1]。由视差图得到深度信息, 再将深度信息用于三维场景的重建。立体匹配算法的实质就是一个最优化求解问题, 通过建立合理的能量函数, 增加一些约束, 采用最优化理论的方法进行求解, 这也是目前病态问题常用的求解方法。

目前国内外学者已经提出了许多立体匹配方法, 如基于局部约束的立体匹配算法^{[2, 3, 4, 5]}以及全局约束的立体匹配算法^{[6, 7]}。局部立体匹配算法是利用兴趣点周围的局部信息进行计算, 涉及信息量较少, 相应的计算复杂度较低; 其优点是算法速度快、效率高; 缺点是其对噪声较敏感, 对低纹理区域、深度不连续区域效果不理想。

传统的采用固定窗口的局部立体匹配算法存在窗口选择的问题, 通常低纹理区域应该采用大尺寸窗口进行聚合, 而在高纹理区域则通常采用较小尺寸窗口, 缺乏自适应性。为解决这一问题, Yoon等^[2]提出了一种自适应权重匹配算法, 取得了较好的匹配精度, 但由于该算法需要计算参考窗口及目标窗口内的每一点像素权重, 导致计算复杂度大大增加。为此, Min等^[3]引入联合直方图以减少视差搜索范围, Humenberger等^[4]提出了Census快速算法。除此之外, Einecke等^[5]引入SNCC, 提高了匹配精度, 但是在深度不连续区域误匹配率较高。为了获得高精度视差, 文献[6-7]采用分割与平面拟合的方法, 但算法的性能受限于分割与平面拟合的精度。

本文将所有邻近像素的匹配代价与权值相结合, 得到参考像素的聚合匹配代价; 并采用文献[8]中提出的SWS方法进行快速匹配代价聚合减少计算复杂度。同时, 在视差精炼阶段, 提出了基于聚合匹配代价平滑的精炼策略。

1 传统局部立体匹配算法

传统算法通常采用AD、AG、NCC^[9]等匹配代价:

$\begin{matrix} \begin{matrix} e_{AD} (x, y, d) = | I_{L} (x, y) - I_{R} (x + d, y) | (1) \\ e_{AG} (x, y, d) = | \nabla I_{L} (x, y) - \nabla I_{R} (x + d, y) | (2) \end{matrix} \end{matrix}$

式中:x、y分别为像素点P所在的列数、行数; d为视差; I_L、I_R分别代表左、右图; Ñ I_L、Ñ I_R分别代表左、右两图的梯度图。

代价聚合则通常采用窗口聚合, 即

$\begin{matrix} \begin{matrix} C (x, y, d) = \sum_{k} w_{k} (i, j) e_{k} (i, j, d) (3) \\ (i, j) \in N (x, y) \end{matrix} \end{matrix}$

式中:N(x, y)为参考像素(x, y)的邻近区域; e_k(i, j, d)代表某种类型的匹配代价; w_k(i, j)为相应的权重。

2 本文算法

提出了一种新的权重匹配代价聚合方法, 以及基于该匹配代价的视差精炼方法。

2.1 匹配代价计算方法

$\begin{matrix} \begin{matrix} e_{D} (x, y, d) = \\ \min [\overset{3}{\sum_{n = 1}} | I_{Ln} (x, y) - I_{Rn} (x + d, y) |, T_{D}] (4) \\ e_{G} (x, y, d) = \\ \min [\overset{3}{\sum_{n = 1}} | \nabla_{x} I_{Ln} (x, y) - \nabla_{x} I_{Rn} (x + d, y) | + \\ \overset{3}{\sum_{n = 1}} | \nabla_{y} I_{Ln} (x, y) - \nabla_{y} I_{Rn} (x + d, y) |, T_{G}] (5) \end{matrix} \end{matrix}$

式中:n代表图像R、G、B三个通道; $\begin{matrix} \nabla_{x} \end{matrix}$ I_L_n、 $\begin{matrix} \nabla_{y} \end{matrix}$ I_L_n分别代表左图R、G、B通道的水平、竖直方向梯度图; $\begin{matrix} \nabla_{x} \end{matrix}$ I_R_n、 $\begin{matrix} \nabla_{y} \end{matrix}$ I_R_n分别代表右图R、G、B通道的水平、竖直方向梯度图; T_D、T_G是截断阈值。与传统方法采用灰度信息做匹配代价相比, 本文采用3个通道的亮度信息, 以提高匹配效率。

2.2 匹配代价聚合

为了提高匹配精度, 必须采用一定的权重匹配代价方法进行聚合^{[10, 11, 12]}。本文将参考像素周围所有像素的匹配代价加以适当权值, 以得到参考像素的聚合匹配代价。

$\begin{matrix} \begin{matrix} W_{ix} = \\ \{\begin{matrix} \overset{x}{\prod_{k = i + 1}} \exp (\frac{\sqrt[]{\overset{3}{\sum_{n = 1}} {[I_{Ln} (k, y) - I_{Ln} (k - 1, y)]}^{2}}}{- 2 α}), i < x \\ 1, i = x \\ \overset{i}{\prod_{k = x + 1}} \exp (\frac{\sqrt[]{\overset{3}{\sum_{n = 1}} {[I_{Ln} (k, y) - I_{Ln} (k - 1, y)]}^{2}}}{- 2 α}), i > x \end{matrix} (6) \\ T_{ix} = \\ \{\begin{matrix} \overset{x}{\prod_{k = i + 1}} \begin{matrix} \exp (\frac{\sqrt[]{\overset{3}{\sum_{n = 1}} {[\nabla_{x} I_{Ln} (k, y) - \nabla_{x} I_{Ln} (k - 1, y)]}^{2}}}{- 2 β}), \\ i < x \end{matrix} \\ 1, i = x \\ \overset{i}{\prod_{k = x + 1}} \begin{matrix} \exp (\frac{\sqrt[]{\overset{3}{\sum_{n = 1}} {[\nabla_{x} I_{Ln} (k, y) - \nabla_{x} I_{Ln} (k - 1, y)]}^{2}}}{- 2 β}), \\ i > x \end{matrix} \end{matrix} (7) \\ \bar{C} (x, y, d) = \\ λ {\hat{C}}_{TAD} (x, y, d) + (1 - λ) {\hat{C}}_{TAG} (x, y, d) (8) \end{matrix} \end{matrix}$

$\begin{matrix} {\hat{C}}_{TAD} \end{matrix}$ (x, y, d)= $\begin{matrix} \overset{s}{\sum_{i = 1}} \end{matrix} \begin{matrix} \overset{t}{\sum_{j = 1}} \end{matrix}$ W_ixW_jye_D(i, j, d) (9)

$\begin{matrix} {\hat{C}}_{TAG} \end{matrix}$ (x, y, d)= $\begin{matrix} \overset{s}{\sum_{i = 1}} \end{matrix} \begin{matrix} \overset{t}{\sum_{j = 1}} \end{matrix}$ T_ixT_jye_G(i, j, d) (10)

式中: $\begin{matrix} \bar{C} \end{matrix}$ (x, y, d)为点P的总聚合匹配代价; $\begin{matrix} {\hat{C}}_{TAD} \end{matrix}$ (x, y, d)为点P的TAD聚合匹配代价; $\begin{matrix} {\hat{C}}_{TAG} \end{matrix}$ (x, y, d)为点P的TAG聚合匹配代价; λ 为权重; s、t分别为参考图像的宽度、高度; α 、β 为权重平滑因子; W_ix、W_jy分别代表点P的TAD聚合的横向、纵向权重; T_ix、T_jy分别为点P的TAG聚合的横向、纵向权重。

权重的设置根据双边滤波的原则, 即与参考像素亮度越相近的像素, TAD聚合代价权重W_ix、W_jy设置得越大; 与参考像素梯度值越相近的像素, TAG聚合代价权重T_ix、T_jy设置得越大。此外, 双边滤波中权重还考虑到空间信息, 即离参考像素越近权重越大; 任意一点像素到参考像素的聚合代价权重可以分解为横向和纵向的权重乘积, 即总权重是随着空间距离的增大而减小。

本文将两种不同聚合匹配代价的权值分开来考虑, 即TAD匹配代价的聚合权重依赖于亮度信息的差异, TAG匹配代价的聚合权重依赖于梯度信息的差异, 这样的聚合权重设置更能反映不同权值对不同匹配代价的影响, 且权重的设置使用R、G、B三个通道的信息, 较使用单一通道信息更为可靠。

类似地, W_jy、T_jy可分别参考W_ix、T_ix。匹配代价聚合的计算相当于二维卷积, 为了减少计算复杂度, 可根据文献[8]提出的降维算法, 利用SWS(Successive weighted summation)将每个二维卷积运算分解为4个一维卷积, 分别为匹配代价由左至右卷积、由右至左卷积、由上至下卷积、由下至上卷积。

2.3 视差精炼

视差值的计算一般采用WTA(Winner takes all)策略, 即为

$\begin{matrix} D (x, y) = \arg \min_{d \in S (d)} \bar{C} (x, y, d) (11) \end{matrix}$

式中:S(d)是搜索视差集合, 即S(d)={0, 1, …, d_max}。

得到初始视差图后, 利用左右一致性检测方法检测视差异常值点, 不满足式(12)的点即为视差异常值点。

$\begin{matrix} | D_{rl} (x, y) - D_{lr} (x - D_{rl} (x, y), y) | < 1 (12) \end{matrix}$

式中:D_rl(x, y)是以左图为参考图得到的视差图; D_lr(x, y)是以右图为参考图得到的视差图。通常绝大多数异常点均为背景遮挡点, 因此采用简单的遮挡点视差填充方法^[3]即可。

每个像素点对应的视差值均为离散的整数, 将这些离散值直接用于三维重建会导致重建场景表面出现断层, 因此, 必须对每个像素点聚合匹配代价函数进行平滑, 以得到连续变化的视差值。

本文提出了一种新的平滑函数, 采用式(13)所示的双曲线函数对视差值进行平滑。

$\begin{matrix} \begin{matrix} f (d) = k_{1} d + \frac{k_{2}}{d} + k_{3} (13) \\ k_{1}, k_{2}, k_{3} \in R 且 k_{1} > 0, k_{2} > 0 \end{matrix} \end{matrix}$

将 $\begin{matrix} \bar{C} \end{matrix}$ (x, y, d)记为C_d, 将点(d-1, C_d-₁)、(d, C_d)、(d+1, C_d+₁)带入式(13)中, 可得下式:

$\begin{matrix} [\begin{matrix} d - 1 & \frac{1}{d - 1} & 1 \\ d & \frac{1}{d} & 1 \\ d + 1 & \frac{1}{d + 1} & 1 \end{matrix}] [\begin{matrix} k_{1} \\ k_{2} \\ k_{3} \end{matrix}] = [\begin{matrix} C_{d - 1} \\ C_{d} \\ C_{d + 1} \end{matrix}] (14) \end{matrix}$

根据双曲线函数的性质可知:f(d)在 $\begin{matrix} {d_{1}}^{*} \end{matrix}$ = $\begin{matrix} \sqrt[]{k_{2} / k_{1}} \end{matrix}$ 处取得极小值。由上式可解得:

$\begin{matrix} {d_{1}}^{*} = \sqrt[]{\frac{(d^{3} - d) (C_{d + 1} + C_{d - 1} - 2 C_{d})}{d (C_{d + 1} + C_{d - 1} - 2 C_{d}) + C_{d + 1} - C_{d - 1}}} (15) \end{matrix}$

3 实验结果及分析

3.1 测试图实验结果

为了测试本文算法的匹配精度, 选用Middlebury网站提供的测试图进行测试。各参数设置分别为{λ , T_D, T_G, α , β }={0.4, 25, 50, 35, 25}, 利用不同算法获得视差图如图1所示。

利用不同算法获得视差图的误匹配率如表1所示。其中, SNCC、RTCensus、AdaptWeight代表传统局部立体匹配算法, FeatureGC、AdaptingBP为全局立体匹配算法。误差阈值取为0.5。

从图1中可以看出, 本文算法在低纹理区域能够获得更好的效果, 如‘ Venus’ 黑色板区域、‘ Teddy’ 屋顶区域等; 由于在视差精炼阶段采用了视差平滑策略, 由4张测试图的视差图均可看出, 视差过渡平滑, 有效减少了视差图中“ 波纹” 现象, 整体视差图的匹配效果较好。

从表1中可以看出, SNCC算法在图‘ Tsukuba’ 视差边缘处(如灯的边界和支架处)误匹配率较高; 虽然在图‘ Cones’ 非遮挡区域误匹配率低于本文算法, 但平均误匹配率明显高于本文算法。RTCensus算法虽然在图‘ Cones’ 非遮挡区域误匹配率比本文算法略低, 但在其视差边缘处误匹配率高于本文算法, RTCensus算法平均误匹配率为14.4%。

从表1中可以看出, 与采用固定窗口聚合匹配代价的AdaptWeight算法相比, 本文算法采用的权重聚合匹配代价, 在视差边缘处及非遮挡区域的匹配性能均优于传统算法, 平均误匹配率最低。

	Figure Option View Download New Window
	图1 视差图效果比较Fig.1 Comparison of disparity maps results

表1 几种算法的误匹配率比较 Table 1 Comparison of error rate of different algorithms %

相比较于计算复杂度较高的全局立体匹配算法, 如:FeatureGC、AdaptingBP, 本文算法也有较大的优势。两种算法分别基于图割理论和置信度传播理论进行分割, 采用平面拟合的方法进行视差精炼。FeatureGC算法对图‘ Tsukuba’ 前景与背景分割的效果好, 匹配性能稍好于本文算法, 但图‘ Cones’ 平均误匹配率高达11.5%, 本文算法只有6.04%。而AdaptingBP算法误匹配率明显过高; 究其原因是由于分割与平面拟合的精度不够, 影响了整体视差精度。

3.2 实际场景的立体匹配与三维重建

实际场景立体匹配效果如图2所示。从图2可以看出, 本文算法在画作边框附近处误匹配点明显少于SNCC, 在树枝及花的位置处, 本文算法的误匹配点也少于SNCC算法; 从三维重建结果可以看出, 利用SNCC算法进行重建, 画作边框有较多的突刺现象, 在画作树枝及花的位置处突刺也比较多, 而本文算法则较好地避免了这一现象, 较为真实的重建了画作的立体信息。

	Figure Option View Download New Window
	图2 画作的匹配与重建Fig.2 Stereo matching and reconstruction for picture

4 结束语

提出了一种基于双权重聚合的立体匹配算法, 利用双边滤波器的特性设置匹配代价聚合的权重获得每一点的聚合匹配代价, 并将匹配代价聚合过程分离开来, 利用不同聚合权重进行匹配代价聚合。在视差精炼阶段, 采用双曲线函数对聚合匹配代价平滑, 得到稠密视差图。通过对比一些优秀的局部立体匹配算法和全局立体匹配算法, 证明了本文算法优越性。

The authors have declared that no competing interests exist.

参考文献

View Option

[1]	Sharstein D, Szeliski R. A taxonomy and evaluation of dense two-frame stereo correspondence algorithms[J]. International Journal on Computer Vision, 2002, 47(1-3): 7-42. [本文引用:1]
[2]	Yoon K J, Kweon S. Adaptive support-weight approach for correspondence search[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2006, 28(4): 650-656. [本文引用:2]
[3]	Min D, Lu J, Do M. Joint histogram based cost aggregation for stereo matching[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2013, 35(10): 2539-2545. [本文引用:3]
[4]	Humenberger M, Zinner C, Weber M, et al. A fast stereo matching algorithm suitable for embedded real-time systems[J]. Computer Vision and Image Understand ing, 2010, 114(11): 1180-1202. [本文引用:2]
[5]	Einecke N, Eggert J. A two-stage correlation method for stereoscopic depth estimation[C]∥International Conference on Digital Image Computing: Techniques and Applications, Sydney, New South Wales, 2010: 227-234. [本文引用:2]
[6]	Saygili Gorkem, van der Maaten Laurens, Hendriks Emile A. Feature-based stereo matching using graph-cuts[C]∥Conference on Asian Society of Cardiovascular Imaging, Hong Kong, 2011: 14-15. [本文引用:1]
[7]	Klaus A, Sormann M, Karner K. Segment-based stereo matching using belief propagation and a self-adapting dissimilarity measure[C]∥The 18th International Conference on Pattern Recognition, Hong Kong, 2006: 15-18. [本文引用:1]
[8]	Cigla Cevahir, Alatan A Aydin. Information permeability for stereo matching[J]. Signal Processing on Image Communication, 2013, 28(9): 1072-1088. [本文引用:1]
[9]	Mattoccia S, Tombari F, Di Stefano L. Fast full-search equivalent template matching by enhanced bounded correlation[J]. IEEE Transactions on Image Processing, 2008, 17(4): 528-538. [本文引用:1]
[10]	Hosni A, Rhemann C, Bleyer M, et al. Fast cost-volume filtering for visual correspondence and beyond[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2013, 35(2): 504-511. [本文引用:1]
[11]	赵岩, 刘静, 陈贺新, 等. 用于单视加深度视频编码的快速立体匹配算法[J]. 吉林大学学报: 工学版, 2012, 42(4): 1032-1036. Zhao Yan, Liu Jing, Chen He-xin, et al. Fast stereo matching algorithm used in stereo video coding based on video plus depth[J]. Journal of Jilin University(Engineering and Technology Edition), 2012, 42(4): 1032-1036. [本文引用:1]
[12]	门朝光, 边继龙, 李香. 基于限制搜索空间的快速立体匹配方法[J]. 吉林大学学报: 工学版, 2012, 42(2): 423-428. Men Chao-guang, Bian Ji-long, Li Xiang. Fast stereo matching algorithm based on limited search space[J]. Journal of Jilin University (Engineering and Technology Edition), 2012, 42(2): 423-428. [本文引用:1]

2002

0.0

... 0 引言立体匹配算法主要是通过建立一个能量代价函数,通过此能量代价函数最小化来估计像素点视差值^[1] ...

2006

0.0