2011年1月第1期
电子测试
ELECTRONIC TEST
Jan.2011No.1
双目视觉中立体匹配算法的研究与比较★
高一宁, 韩燮
（中北大学 电子与计算机科学技术学院 山西 太原 030051）
摘 要: 在基于双目立体视觉三维重建的研究中，立体匹配是其中最重要的部分，它的准确性影响着最后的重建结果。本文主要讲述了常用的立体匹配算法，并详细介绍了两种算法分类中的代表性算法的实现步骤，即局域算法中的基于特征点匹配的算法和全局算法中的基于图割法的匹配算法，并对算法从运算速度和误配率两方面进行了比较，总结了两种算法的优缺点，比较了两种匹配算法最终获取的视差图，以及已有的立体匹配算法所存在的问题和今后需要改进的方向。关键词: 立体匹配；特征匹配；图割法 中图分类号: TP301 文献标识码：A
Research and comparison of stereo matching
alaorithm based on binocular vision
Gao Yining, Han Xie
（College of Electronics and Computer Science and Technology, North University of China,Taiyuan
030051,China）
Abstract: In the research of three-dimensional reconstruction based on binocular vision,the stereo matching is one of the most important part,its accuracy affects the reconstruction of the final results.This article describes the commonly used stereo matching algorithm,two algorithms are described in detail which are the representation of category steps of the algorithm,that algorithm based on local feature points matching algorithm and the global algorithm in the matching based on graph cuts.Compared the two on computational speed and error rate,summed up the advantages and disadvantages,compared the final disparity map obtain by the two matching algorithm,and the promblems the algorithms have had and future directions for improvement.
Keywords: stereo matching; feature matching;graph cut method
★基金项目：
山西省自然科学基金（2010011023-1）资助
0 引言
立体匹配是立体视觉中最重要的部分。常用的立体匹配算法，根据其用的约束信息的不同，总体上分为局域算法和全局算法两种。局域算法是利用对应点本身以及其邻近的局部区域的约束信息的匹配算法，根据其匹配基元的不同，主要分为基于特征的匹配算法，区域匹配算法和梯度法。局域算法的优点是效率高，但是它对一些由于遮挡和纹理单一等造成的模糊比较敏感，易造成误匹配。全局算法利用了图像的全局约束信息，是一种对扫描线甚至整幅图像进行约束的匹配算法。主要算法有：基于动态规划算法、图割法、置信度传播算法、非线性融合算法、基于神经网络的匹配算法和基于遗传算法的匹配等。其优点是对局部图像的模糊不敏感，但算法的时间复杂度高，计算效率较低。
局域算法中常用算法为基于特征的匹配算法，基于全局算法中，图割法可以有效地融合水平和垂直方向上的连续行约束，是目前处理效果最好的立体匹配算法。因此，本文主要介绍这两种常用算法的具体实现步骤并对其进行分析比较。
w(x,y)为窗口函数，I(x,y)为图像灰度，I(x+u,y+v)为平移后的图像灰度。
Harris 算法步骤为：
第一步：计算图像的方向导数即图像像素在水平和垂直方向上的梯度，以及两者的乘积，得到M 中4个元素的值：
⎡I x 2
M =⎢M
⎢⎣I x I y
；
第二步：对图像进行高斯滤波，得
I x I y ⎤2⎥I y ⎥⎦
到新的M M。离散二维零均值高斯函数为(x 2+y 2)
Gauss =exp(−) ；
2σ第三步：计算原图像上对应的每个像素点的兴趣值，即R 值。
22
R ={I x 2×I y −(I x I y ) 2}−k {I x 2+I y }
2
；
第四步：选取局部极值点。Harris方法认为，
特征点是局部范围内的极大兴趣值对应的像素点。
第五步：设定阈值，选取一定量的角点。
1.2 特征点的匹配
特征点的匹配即是根据所选特征的计算，建立特征之间的对应关系，将同一个空间物理点在不同图像中的映射点对应起来。
特征点的匹配由3个基本的步骤组成：第一步：从图像对中的一幅图像如左图上选择与实际物理结构相应的图像特征；
第二步：在另一幅图像如右图中确定出同一物理结构的对应图像特征；
第三步：确定这两个特征之间的相对位置，得到视差。通过立体匹配得到视差图像之后，最终获得深度图像，并恢复场景的三维信息。
1 基于特征的匹配算法
1.1特征点的选取
特征匹配是基于图像的几何特征，如边缘、轮廓、拐点、线段等对图像进行匹配。本文采用Harris 算法提取图像的特征点。
Harris 检测的算法思想是：在图像中设计一个局部检测窗口，当该窗口沿各个方向作微小移动时，考察窗口的平均能量变化，当该能量变化值超过设定的阈值时，就将窗口的中心像素点提取为角点。
E (u , v ) =其数学表达式为：∑w (x , y )[I (x +u , y +v ) −I (x , y )]
x , y
2
2 图割法
2.1 图割法介绍
基于图割法的立体匹配算法等价于一个能量函
将图像窗口平移[u,v]产生灰度变化E(u,v)。其中
注f’)的一次移动。每次α-扩展移动将增加标号为α的像素个数。
算法步骤：
第一步：任取一标注f 作为初始标注。第二步：对每一个标号α∈L，计算f1=argminE(f’),其中f’为f 在一次α-扩展移动后得到的新标注。
循环迭代直至得到使能量函数最小的f，从而计算得出最小化的能量函数。
数最小化的过程。设输入为像素集合P，视差标注集合L，目标是寻找一个标注f(从P 到L 的一个映射)，使能量函数最小，通常选择的能量函数具有以下形式：
E (f ) =
∑D
p ∈P
(p )
(f p ) +∑V p ⋅q (f p , f q )
p ⋅q
其中：f 为视差标注；P 为所有像素的集合；Dp 为数据项，用来度量像素p 所分配的标号fp 与观测数据不一致程度；N
⊂P×P为邻域像素对的
集合；Vp.q(fp,fq)度量将fp,fq 分配给相邻的像素p,q 的代价，为平滑项。Vp.q为以fp-fq 为自变量的凸函数，也可以是一些不连续性保留函数，如截断二次函数、截断线性函数以及Potts 模型等。
3 算法对比
立体匹配算法的结果是要得到一个稠密且精度
2.2 图割法实现步骤
用图割法来实现立体匹配，主要包括两个步骤：第一步：根据匹配问题中的约束条件写出相应的能量函数；
第二步：根据能量函数构造图网格，再依据图网格最小化该能量函数。
Boykov 等给出了两种基于图割技术的算法，即扩展移动算法（基于其定义的α-扩展移动）和交换移动算法（基于其定义的α-β-交换移动）来计算其近似解。算法从一个初始标注开始，迭代应用图割技术计算一次α-扩展（或α-β-交换）移动内的最低能量标注，并以此更新当前标注，算法最终收敛到能量函数的局部最小值。
高的深度图像。基于特征的匹配算法只考虑局部的约束信息，精度比较差，另外由于相机采样的离散化以及光线等各种因素的影响，特征匹配算法本身的限制，无法得到稠密的深度图。而图割法考虑了图像的整体像素的约束，能得到更为准确的深度值。
3.1优缺点对比
特征点匹配算法的优缺点
优点：特征匹配以几何特征为基元，不易受光线的影响，因此鲁棒性较好，而且计算量小，速度快。
缺点：由于几何特征的稀疏性和不连续性，因此特征匹配只能得到稀疏的深度图。需要通过内插的方法才能得到稠密的深度图。
图割法的优缺点：
2.3 α-扩展移动算法
本文采用的是α-扩展移动算法。设Pl={p∈P|fp=l},那么对于任一标注f，它唯一确定了图像像素集合的一个划分H={Pl|l∈L}，即标注f 和划分H 之间存在一一对应。给定一个标号α，α-扩展移动是指从划分H （标注f）到新的划分H’(标优点：可以有效融合水平和垂直方向上的连续性约束，匹配效果好。
缺点：算法复杂度较高，计算量较大。
3.2 运算时间和误配率
表1给出了基于特征的匹配算法和基于图割的
匹配算法在运算时间和误配率上的比较。
表1 两种匹配算法的比较
基于特征的匹配算法
运算时间(s)误配率(%)
1.3721.58
基于图割法的匹配算法
1.9310.94
参考文献
[1] 尹传历, 刘冬梅, 宋建中.改进的基于图像分割的立体匹
配算法[J].计算机辅助设计与图形学学报,2008,20(6):808-812.
[2] 杨恒, 王庆.一种高效的图像局部特征匹配算法[J].西北
工业大学学报,2010,28(2):291-297.
[3] 熊英.利用图像分割的基于图割理论的立体匹配算法的
研究[D].秦皇岛:燕山大学,2009.
[4] 鲍文霞, 梁栋, 王年, 等.基于图割理论和极几何约束的
图像匹配算法[J].计算机工程,2007,33(1):193-194,197.
实验表明，图切割的立体匹配算法能得到效果较好的立体匹配视差图。实验对比结果如图1-图4所示。
图1 原始图像 图2 视差真值图
[5] Rui Li,Stan Sclaroff.Multi-scale 3D scene flow from
binocular stereo sequences[J].Computer Vision and Image Understanding,2008(110):75-90.[6]
Bleyer M, Gelautz M. Graph-cut-based stereo matching using image segmentation with symmetrical treatment of occlusions [J]. Signal Processing: Image Communication,2007, 22(2): 127-143.[7] 刘维, 罗桂娥, 杨欣荣.一种快速鲁棒区域匹配算法[J].
微计算机信息,2009,11(25):184-191.
图3 图割法的视差图 图4 基于特征匹配的视差图
[8] 韩云生, 刘国栋, 刘光宇.基于Canny 算子边缘特征匹配
的双目深度测量[J].计算机系统应用,2009,11:52-55.
4 总结
通过两种算法的对比可以得到全局算法因从图像的整体约束信息考虑进行匹配，因此比局域算法有更好的匹配效果和较低的误配率。
立体匹配算法经过几十年的发展，一些匹配算法已经发展成熟，但仍然面临着一些问题需要继续研究。比如由于构成立体视觉系统的摄像机与观测目标在位置上的局限性，造成场景中的某些点的遮挡问题；形状和光照变化问题；算法效率问题；多种匹配算法的有效融合问题等，还需要我们进一步的研究解决。
[9] 胡明昊, 任明武, 杨静宇.一种快速实用的特征点匹配算
法[J].计算机工程,2004,9(30):31-33.
作者简介：
高一宁，中北大学在读研究生，主要研究方向为虚拟现实仿真。E-mail ：[email protected]
2011年1月第1期
电子测试
ELECTRONIC TEST
Jan.2011No.1
双目视觉中立体匹配算法的研究与比较★
高一宁, 韩燮
（中北大学 电子与计算机科学技术学院 山西 太原 030051）
摘 要: 在基于双目立体视觉三维重建的研究中，立体匹配是其中最重要的部分，它的准确性影响着最后的重建结果。本文主要讲述了常用的立体匹配算法，并详细介绍了两种算法分类中的代表性算法的实现步骤，即局域算法中的基于特征点匹配的算法和全局算法中的基于图割法的匹配算法，并对算法从运算速度和误配率两方面进行了比较，总结了两种算法的优缺点，比较了两种匹配算法最终获取的视差图，以及已有的立体匹配算法所存在的问题和今后需要改进的方向。关键词: 立体匹配；特征匹配；图割法 中图分类号: TP301 文献标识码：A
Research and comparison of stereo matching
alaorithm based on binocular vision
Gao Yining, Han Xie
（College of Electronics and Computer Science and Technology, North University of China,Taiyuan
030051,China）
Abstract: In the research of three-dimensional reconstruction based on binocular vision,the stereo matching is one of the most important part,its accuracy affects the reconstruction of the final results.This article describes the commonly used stereo matching algorithm,two algorithms are described in detail which are the representation of category steps of the algorithm,that algorithm based on local feature points matching algorithm and the global algorithm in the matching based on graph cuts.Compared the two on computational speed and error rate,summed up the advantages and disadvantages,compared the final disparity map obtain by the two matching algorithm,and the promblems the algorithms have had and future directions for improvement.
Keywords: stereo matching; feature matching;graph cut method
★基金项目：
山西省自然科学基金（2010011023-1）资助
0 引言
立体匹配是立体视觉中最重要的部分。常用的立体匹配算法，根据其用的约束信息的不同，总体上分为局域算法和全局算法两种。局域算法是利用对应点本身以及其邻近的局部区域的约束信息的匹配算法，根据其匹配基元的不同，主要分为基于特征的匹配算法，区域匹配算法和梯度法。局域算法的优点是效率高，但是它对一些由于遮挡和纹理单一等造成的模糊比较敏感，易造成误匹配。全局算法利用了图像的全局约束信息，是一种对扫描线甚至整幅图像进行约束的匹配算法。主要算法有：基于动态规划算法、图割法、置信度传播算法、非线性融合算法、基于神经网络的匹配算法和基于遗传算法的匹配等。其优点是对局部图像的模糊不敏感，但算法的时间复杂度高，计算效率较低。
局域算法中常用算法为基于特征的匹配算法，基于全局算法中，图割法可以有效地融合水平和垂直方向上的连续行约束，是目前处理效果最好的立体匹配算法。因此，本文主要介绍这两种常用算法的具体实现步骤并对其进行分析比较。
w(x,y)为窗口函数，I(x,y)为图像灰度，I(x+u,y+v)为平移后的图像灰度。
Harris 算法步骤为：
第一步：计算图像的方向导数即图像像素在水平和垂直方向上的梯度，以及两者的乘积，得到M 中4个元素的值：
⎡I x 2
M =⎢M
⎢⎣I x I y
；
第二步：对图像进行高斯滤波，得
I x I y ⎤2⎥I y ⎥⎦
到新的M M。离散二维零均值高斯函数为(x 2+y 2)
Gauss =exp(−) ；
2σ第三步：计算原图像上对应的每个像素点的兴趣值，即R 值。
22
R ={I x 2×I y −(I x I y ) 2}−k {I x 2+I y }
2
；
第四步：选取局部极值点。Harris方法认为，
特征点是局部范围内的极大兴趣值对应的像素点。
第五步：设定阈值，选取一定量的角点。
1.2 特征点的匹配
特征点的匹配即是根据所选特征的计算，建立特征之间的对应关系，将同一个空间物理点在不同图像中的映射点对应起来。
特征点的匹配由3个基本的步骤组成：第一步：从图像对中的一幅图像如左图上选择与实际物理结构相应的图像特征；
第二步：在另一幅图像如右图中确定出同一物理结构的对应图像特征；
第三步：确定这两个特征之间的相对位置，得到视差。通过立体匹配得到视差图像之后，最终获得深度图像，并恢复场景的三维信息。
1 基于特征的匹配算法
1.1特征点的选取
特征匹配是基于图像的几何特征，如边缘、轮廓、拐点、线段等对图像进行匹配。本文采用Harris 算法提取图像的特征点。
Harris 检测的算法思想是：在图像中设计一个局部检测窗口，当该窗口沿各个方向作微小移动时，考察窗口的平均能量变化，当该能量变化值超过设定的阈值时，就将窗口的中心像素点提取为角点。
E (u , v ) =其数学表达式为：∑w (x , y )[I (x +u , y +v ) −I (x , y )]
x , y
2
2 图割法
2.1 图割法介绍
基于图割法的立体匹配算法等价于一个能量函
将图像窗口平移[u,v]产生灰度变化E(u,v)。其中
注f’)的一次移动。每次α-扩展移动将增加标号为α的像素个数。
算法步骤：
第一步：任取一标注f 作为初始标注。第二步：对每一个标号α∈L，计算f1=argminE(f’),其中f’为f 在一次α-扩展移动后得到的新标注。
循环迭代直至得到使能量函数最小的f，从而计算得出最小化的能量函数。
数最小化的过程。设输入为像素集合P，视差标注集合L，目标是寻找一个标注f(从P 到L 的一个映射)，使能量函数最小，通常选择的能量函数具有以下形式：
E (f ) =
∑D
p ∈P
(p )
(f p ) +∑V p ⋅q (f p , f q )
p ⋅q
其中：f 为视差标注；P 为所有像素的集合；Dp 为数据项，用来度量像素p 所分配的标号fp 与观测数据不一致程度；N
⊂P×P为邻域像素对的
集合；Vp.q(fp,fq)度量将fp,fq 分配给相邻的像素p,q 的代价，为平滑项。Vp.q为以fp-fq 为自变量的凸函数，也可以是一些不连续性保留函数，如截断二次函数、截断线性函数以及Potts 模型等。
3 算法对比
立体匹配算法的结果是要得到一个稠密且精度
2.2 图割法实现步骤
用图割法来实现立体匹配，主要包括两个步骤：第一步：根据匹配问题中的约束条件写出相应的能量函数；
第二步：根据能量函数构造图网格，再依据图网格最小化该能量函数。
Boykov 等给出了两种基于图割技术的算法，即扩展移动算法（基于其定义的α-扩展移动）和交换移动算法（基于其定义的α-β-交换移动）来计算其近似解。算法从一个初始标注开始，迭代应用图割技术计算一次α-扩展（或α-β-交换）移动内的最低能量标注，并以此更新当前标注，算法最终收敛到能量函数的局部最小值。
高的深度图像。基于特征的匹配算法只考虑局部的约束信息，精度比较差，另外由于相机采样的离散化以及光线等各种因素的影响，特征匹配算法本身的限制，无法得到稠密的深度图。而图割法考虑了图像的整体像素的约束，能得到更为准确的深度值。
3.1优缺点对比
特征点匹配算法的优缺点
优点：特征匹配以几何特征为基元，不易受光线的影响，因此鲁棒性较好，而且计算量小，速度快。
缺点：由于几何特征的稀疏性和不连续性，因此特征匹配只能得到稀疏的深度图。需要通过内插的方法才能得到稠密的深度图。
图割法的优缺点：
2.3 α-扩展移动算法
本文采用的是α-扩展移动算法。设Pl={p∈P|fp=l},那么对于任一标注f，它唯一确定了图像像素集合的一个划分H={Pl|l∈L}，即标注f 和划分H 之间存在一一对应。给定一个标号α，α-扩展移动是指从划分H （标注f）到新的划分H’(标优点：可以有效融合水平和垂直方向上的连续性约束，匹配效果好。
缺点：算法复杂度较高，计算量较大。
3.2 运算时间和误配率
表1给出了基于特征的匹配算法和基于图割的
匹配算法在运算时间和误配率上的比较。
表1 两种匹配算法的比较
基于特征的匹配算法
运算时间(s)误配率(%)
1.3721.58
基于图割法的匹配算法
1.9310.94
参考文献
[1] 尹传历, 刘冬梅, 宋建中.改进的基于图像分割的立体匹
配算法[J].计算机辅助设计与图形学学报,2008,20(6):808-812.
[2] 杨恒, 王庆.一种高效的图像局部特征匹配算法[J].西北
工业大学学报,2010,28(2):291-297.
[3] 熊英.利用图像分割的基于图割理论的立体匹配算法的
研究[D].秦皇岛:燕山大学,2009.
[4] 鲍文霞, 梁栋, 王年, 等.基于图割理论和极几何约束的
图像匹配算法[J].计算机工程,2007,33(1):193-194,197.
实验表明，图切割的立体匹配算法能得到效果较好的立体匹配视差图。实验对比结果如图1-图4所示。
图1 原始图像 图2 视差真值图
[5] Rui Li,Stan Sclaroff.Multi-scale 3D scene flow from
binocular stereo sequences[J].Computer Vision and Image Understanding,2008(110):75-90.[6]
Bleyer M, Gelautz M. Graph-cut-based stereo matching using image segmentation with symmetrical treatment of occlusions [J]. Signal Processing: Image Communication,2007, 22(2): 127-143.[7] 刘维, 罗桂娥, 杨欣荣.一种快速鲁棒区域匹配算法[J].
微计算机信息,2009,11(25):184-191.
图3 图割法的视差图 图4 基于特征匹配的视差图
[8] 韩云生, 刘国栋, 刘光宇.基于Canny 算子边缘特征匹配
的双目深度测量[J].计算机系统应用,2009,11:52-55.
4 总结
通过两种算法的对比可以得到全局算法因从图像的整体约束信息考虑进行匹配，因此比局域算法有更好的匹配效果和较低的误配率。
立体匹配算法经过几十年的发展，一些匹配算法已经发展成熟，但仍然面临着一些问题需要继续研究。比如由于构成立体视觉系统的摄像机与观测目标在位置上的局限性，造成场景中的某些点的遮挡问题；形状和光照变化问题；算法效率问题；多种匹配算法的有效融合问题等，还需要我们进一步的研究解决。
[9] 胡明昊, 任明武, 杨静宇.一种快速实用的特征点匹配算
法[J].计算机工程,2004,9(30):31-33.
作者简介：
高一宁，中北大学在读研究生，主要研究方向为虚拟现实仿真。E-mail ：[email protected]