《自动化与仪器仪表》2011 年第 6 期（总第 158 期） 一种基于SSD和图割的快速立体匹配算法 程 浩，李 寒 (武汉工程大学电气信息学院 湖北武汉，430205) 摘 要：针对图割法的立体匹配算法耗时多的问题，提出了一种基于 S S D 和图割的快速立体匹配算法。为了 缩小视差搜索范围, 缩短匹配时间，先采用区域匹配 S S D 算法得到初始视差，然后再采用左右一致性校验法去除误 匹配点，可以提高初始视差图的质量；在构造能量函数时, 把初始视差图中的像素视差作为图割的能量函数的限制 项，根据这些限制可以减少不必要的节点，从而减少了计算量, 缩短匹配时间。通过实验证明了本文算法在保证匹 配图像质量的情况下，能提高匹配效率，减少匹配时间。 关键词：图割法；S S D 算法；立体匹配 Abstract: For the problem that stereo matching methods based on graph cuts are time consuming, this paper presents a fast stereo matching algorithm based on SSD algorithm and graph cuts algorithm. In order to reduce the parallax hunting zone and matching time, t he SSD matching method is used as a similarity decision criterion to determine the initial disparity map. Then, the left-right conformity verification is adopted to remove mistake matching points. This may enhance the quality of the initial parallax map. When the energy function is constructed, the initial parallax map is used as a limit of function to get the optimization of disparity distribution by graph cuts. Therefore, reducing the node of graphs, the graph capacity and execution time are decreased. At last, it is proved by experiments that this algorithm not only achieve a relatively ideal but also save much time in stereo matching. Key words: graph cuts ; SSD algorithm ; stereo matching 中图分类号：TP13 文献标识码：B 文章编号：1001-9227(2011)06-0131-03 0 引 言 立体匹配问题是机器人视觉技术中比较困难的问题 之一，其目的是寻找两幅或两幅以上图像中像素点的对应 关系。近几十年，立体匹配问题已经成为了重要的研究内 容，并且取得了很大的进展，而且出现了许多经典的算 法。根据匹配生成视差图的疏密，立体匹配算法分为稀疏 视差匹配算法和稠密的视差匹配算法[ 1 ] 。然而在许多重要 的应用领域，要求的匹配出来的深度图必须是稠密深度 图，所以如何获取稠密深度图才是研究的重点。获取稠密 深度图有基于区域的算法(local- based algorithms) 和 基于全局的算法(global-based algorithms) 两种方法。 区域立体匹配算法主要是采用局部优化方法进行视 差值估计，区域立体匹配算法主要有SAD[2]，SSD[2]，NCC[3]等 算法。区域立体匹配算法求取视差的优点是效率高，速度 比较快，能满足实时性要求，占内存少。但是其获取的视 差准确度不高, 噪声较敏感，对无纹理区域或弱纹理区域、 视差不连续区域和遮挡区域匹配效果不理想。 全局算法主要是采用了全局的优化理论方法估计视 差，建立全局能量函数，通过最小化全局能量函数得到最 优视差值。主要的算法有图割(Graph Cut:GC) [4]、动态规 划(Dynamic Programming:DP) [5]、信念传播(Belief Propagation:BP)[6-7]等算法。全局匹配算法比起局部匹配 算法匹配精度就高很多，但是它有两大缺点。第一它的算 法复杂而巨大，实时性不好；第二，目前先进的全局匹配 收稿日期:2011-09-01 作者简介: 程浩( 1 9 8 5 - ) , 男, 湖北武汉人, 主要研究方向为三 维立体视频处理, 图像处理，模式识别与智能系统。 算法没有考虑到光照不连续问题。为了快速获得高质量的 稠密深度图像，本文提出一种基于图割的快速立体匹配算 法，先采用局域立体匹配算法和左右一致验证法得到可靠 的初始视差，再利用图割算法做最后的立体匹配处理。 1 图割算法 图割算法是将图像中空间相邻、像素值相近的点聚 类的过程。通过对图像分割，可去除图像中不必要的细节 信息而保留主要信息。图割法一般包含 3 个步骤：建立匹 配能量函数，构造网格图，利用最大流求解能量函数的最 小值。其基本思路是将图像中的每个象素视为构造图中的 节点，像素之间的邻接关系采用构造图的边表示将能量函 数最小值转化为构造图的最小割，采用最大流最小割算法 求解最小割，并根据最小割为图像中的每个象素分配亮度 值。为了获得像素的恰当标号需要构造一个关于标号的能 量函数。对能量函数的构造通常有两大约束：数据约束和 平滑约束。匹配的能量函数可构造如下： ( 1 ) 式中 素的相似程度： (1) 是数据项，它是用来衡量图像之间像 (2) ( 1 ) 式中 是平滑项，在弱纹理或具有规则纹 理区域匹配的时，视差值会不唯一, 所以单靠颜色信息很 难获得理想的视差。平滑项是根据相邻像素信息来确定某 像素视差, 所以在这些区域内应该减少数据项的惩罚量, 而更多地依靠平滑项。 131 

(3) 其中： 为固定平滑惩罚量，当 p 与 q 为相邻像素 时，认为视差是平滑的, 增加惩罚量; 当 p 与 q 不为相邻像 素时，惩罚量为 0 。 ( 4 ) 式中Eocclusion 是遮挡项。当匹配点的三个颜色通道 的差异大于一定阈值时，该像素定义为遮挡像素。其中 是惩罚量。 (4) 2 本文算法 为了缩小视差搜索范围, 缩短匹配时间，先采用区域 匹配算法得到初始视差，然后再采用左右一致性校验法去 除误匹配点，这样可以进一步提高初始视差图的质量。在 构造能量函数时，把初始视差图中的像素视差作为图割的 能量函数的限制项，根据这些限制可以减少节点，从而减 少了计算量。 2.1 初始匹配 初始视差图的精度对后续工作的影响很大，因此，本 文采用了文献[ 8 ] 提出的一种改进的 S S D 算法快速获得初 始视差图。如图 1 所示。 一种基于SSD 和图割的快速立体匹配算法 程 浩，等 误匹配点。左右一致验证法的思想是先假设右图为参考 图，在右图中搜索匹配点，得到视差 D L(p),然后反过来，得 到以左图为参考图的视差 D R ( p ) ，最后看左右视差图是不 是一致， (7) 如果一致则说明它是视差点，如果不是这是遮挡点， 这个可以做为图割的限制项进行优化能量函数，使能量函 数最小。 2.2 构建能量函数 远远偏离实际的视差无助于降低优化函数的能量, 只 会使生成的网络规模扩大, 加大算法的计算量，影响运算 速度。为了使构建的网络的规模较小，减小计算量，本文 根据初始可靠像素视差的计算结果, 控制网络的规模。 能量函数如下： 其中 : (8) (9) f 初始是经过改进的 S S D 算法和左右一致验证法处理 后得到的初始视差，f r a n g e 是视差变化的允许范围。 3 实验结果与分析 为了验证本文提出的算法的性能，本文将采用美国 M i d d l e r b u y 大学计算机视觉研究中心提供 4 3 4 x 3 8 3 的 venus、434x380 的sawtooth、384x288 的Tsukuba 测试图像 进行仿真实验。计算机硬件条件为：单核 C P U 主频为 2 . 93GHz，内存为 1G，软件编译环境为 VC6.0。 表 1 图1 设 I 1 代表图像 1 ，I 2 代表图像 2 ，邻域大小为( 2 n + 1 ) (2m+1)，d 代表视差。四个圆点区域是I 1(x,y)的匹配区域， 三角是I 1(x,y+1)的匹配区域，四边形是I 1(x+1,y)的匹配 区域，五边形是I1(x,y+2)，扇形点是I1(x+1,y+1)的匹配区 域。 其思路是：利用计算图像每个像素的 S S D 值时，前后 上下像素模板的相互关系，根据已计算的 S S D 值，来计算 新的像素点的SSD 值。假设SSD(x,y,d)表示I1(x,y)与I1(x, y+d)区域的SSD 值时，则I1(x,y+1)与I1(x,y+1+d)区域的 SSD(x,y+1,d)值可以用SSD(x,y,d)值表示： 因为采用了初始像素视差的计算结果来控制网络的 规模，它只会在图切割网络中可能的视差范围内添加新的 节点，而在允许视差范围内增加的节点要比搜索全部视差 范围的节点要小得多, 所以这样就减少了网络中的节点 数，降低了计算复杂度。表 1 是两种算法对 v e n u s 、s a w t - ooth、Tsukuba 的匹配耗时情况，不难看出本算法明显减少 匹配时间；图 2 中依次是 Tsukuba 的左右图像对、经过改进 S S D 算法处理获得的左右初始视差图、G C 算法视差图和本 文算法视差图。对 G C 算法和本文算法进行P S N R 评估发现， 两种算法 PSNR 值相差不到0.1db，从主观和客观可以说明 本算在保证匹配质量的前提下，能很好的缩短匹配时间。 其中dif(x,y+1,d)为： (5) (6) 为了进一步获得高精度的视差值，本文采用左右一 致验证法[ 9 ] ，对通过该改进的 S S D 算法获得视差进行去除 Tsukuba左图 Tsukuba 右图 （下转第136页） 132 

波电流检测的实际需要。 粒子群优化 R B F 神经网络的自适应谐波检测 刘永科，等 [6] Keerthi S S, Lin C J. Asymptotic behaviors of support vector machines with gaussian kernel[J]. Neural 参考文献 computation, 2003, 15:1667-1689. [1] 林雪海,孙树勤.电力网中的谐波[M].北京:中国电力出版社, [7] 王安娜,陶子玉,姜茂发.基于PSO 和BP 网络LF 炉钢水温度智能 1998. 预测[J].控制与决策,2008,21(7)814-820. [2] 张金龙,王海春,赵芙生.基于模糊RBF 神经网络的超精密定位 [8] 柴旭峥,文习山,关根志等.一种高精度的电力系统谐波分析算 系统[J].光电子.激光,2007,18(3):345-348. 法[J].中国电机工程学报,2003,23(9):67-70. [3] Qi Wua, Rob Law. The forecasting model based on modified [9] 李 红,马新瑜.多层前馈神经网络在电力系统谐波测量中的应 SVRM and PSO penalizing gaussian noise[J]. Expert Sys- 用[J].电测与仪表,2003,40(446):15-17. tems with Applications, 2011,38(1):138-142. [10] Liu wei,Wang Ke iun,Tang Mo．Study on power system load [4] 汤红诚,伍建林,李著信等.一种基于人工神经元的实时谐波及 forecasting based on MPSO artificial neural networks 无功电流数字检测方法[J].电网技术,2002,26(12):13-17. [C].Dalian. [5] 王小艺,侯朝桢,原菊梅.基于进化策略改进的D-S 证据识别算 [11] The 6th World Congress on Intelligent Control and 法[J].光电子.激光,2006,17(8)L:999-1003. Automation．2006:2728-2732. （上接第132页） press. [2] H. Hirschm uller, D. Scharstein, “Evaluation of cost functions for stereo matching,”[J].In IEEE Computer So- ciety Conference on Computer Vision and Pattern Recognition, 2007. [3] Yong Seok Heo, Kyoung Mu Lee, Sang Uk Lee.Robust Stereo Matching Using Adaptive Normalized Cross-Correlation [J].In IEEE Computer Society,pp.807-821,2010. SSD算法的视差图DL(p) SSD 算法的视差图DR(p) [4] Pedro F. Felzenszwalb , Ramin Zabih, Dynamic Programming and Graph Cut Algorithms in Computer Vision[J]. In IEEE Transactions on Pattern Analysis and Machine in Telligence. 721-740,4,2011. [5] Y. Deng , X. Lin, “A fast line segment based dense stereo algorithm using tree dynamic programming,”[J]. In ECCV, 2006, pp. III: 201-212. [6] Q. Yang, L. Wang, R. Yang, H. Stewenius, and D. Nister, GC算法视差图 本文算法视差图 “Stereo matching with color-weighted correlation, hier- 图2 图形比较 archical belief propagation, and occlusion handling, ” 4 结 语 本文在图割法的立体匹配算法的基础上提出了一种 改进的快速立体匹配算法。采用改进的 S S D 匹配算法快速 获得初始视差图，并将其作为 G C 算法的参考项，减少网络 的规模，优化了能量函数，在保证匹配图像质量的情况 下，进一步提高了匹配效率。 [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 31,pp.492-504,2008. [7] A. Banno , K. Ikeuchi, “Disparity map refinement and 3d surface smoothing via directed anisotropic diffusion, ” [J]. In 3-D Digital Imaging and Modeling, 2009, pp.1870- 1877. [8] 宋 毅.基于分步思想的立体图像匹配算法研究[C].北京工业 大学,2006. [1] Zeng-Fu,Wang,Zhi-Gang Zheng.A Region Based Stereo Matching with Adaptive Support-Weight correlation and Graph Cuts 参考文献 [9] Limin Shi,Fusheng Guo,Wei Gao,Zhanyi Hu.Stereo Matching Algorithm Using Cooperative Optimization.In Computer [J].In IEEE,pp,3575-3579,2010. Vision and Pattern Recognition, [C](2008),accepted.In 136