基于稳定特征点和SLIC超像素分割的快速立体匹配

钱 超，张晓林

（中国科学院 上海微系统与信息技术研究所，上海 200050）

基于稳定特征点和SLIC超像素分割的快速立体匹配

钱 超，张晓林

（中国科学院 上海微系统与信息技术研究所，上海 200050）

针对目前立体匹配中存在的匹配精度和匹配速度很难兼顾的问题，提出了一种基于稳定特征点和SLIC超像素分割算法的快速立体匹配。利用SURF算法高速有效地提取出特征点进行匹配，并且利用三角剖分的方法对稳定特征点作进一步处理，以此匹配作为先验知识来减少其余各点的匹配误差和搜索空间，同时又加入了SLIC超像素分割算法的限制因素进一步提高精度，这样使得立体匹配算法在精度上和速度上都得到了很好的提高。对Middlebury中的标准数据进行测试的结果表明，该算法能较为快速准确地获得视差。

机器视觉；立体匹配；SLIC超像素分割算法；三角剖分；SURF算法

通过校正好的图像对获取图像深度信息是三维重建等计算机视觉问题中很重要的一部分，我们一般称之为立体匹配获取视差。这在三维重建、虚拟视点渲染、自动驾驶、医疗诊断中都有着广阔的应用。

视差是指一个物体在左右两幅图上水平坐标的差距，比如视差为d的物体在左图的坐标是（x，y），在右图的坐标是（x-d，y）。在得到了视差d之后，我们可以用三角测量的原理计算图像深度信息：

f是相机的焦距，B是相机中心之间的距离。

根据Scharstein and Szeliski（2002）的综述，典型的立体匹配算法分为 4个步骤：匹配代价计算、代价聚合、视差计算、视差优化[1]。前两步是关于代价计算的部分，而后两部分是视差计算的部分。

根据匹配方式不同可以将立体匹配算法分为两类：局部匹配和全局匹配。其中局部方法选择那个使得图像中小区域内总体不相似度最小的视差值，而全局方法则是通过最小化一个关于整幅图相似性和平滑性的能量函数来求得视差。局部方法有cencus变换算法[2]，自适应窗口匹配算法[3]，总体而言匹配速度较快，但是在面对光照、弱纹理或者纹理重复、遮挡等等传统立体匹配挑战的时候局部性这个特性往往使得表现不尽如人意；相对而言全局方法克服了这些问题，计算复杂度大大增高，典型的全局方法有 BP（置信度传播）[4]、图割[5]等等，这些算法在实际使用的时候十分依赖计算能力以及性能的优化。

文中提出了一种基于稳定特征点和SLIC超像素分割算法的立体匹配，用SURF算法[6]提取特征点，再利用这些稳定特征点的高鲁棒性匹配作为约束，使用三角剖分[7]的方法形成2D网格作为其余像素视差判断的先决条件，再加入SLIC超像素分割算法[8]的结果来约束增加平滑性，最后得到优化的视差结果。

1 文中算法

首先，用SURF算法提取左右两幅图的特征点，进行匹配，去除非平行匹配点，得到稳定匹配的特征点，再利用这些稳定匹配的特征点使用三角剖分的方法形成2D网格作为剩余像素视差判断的先决条件，在约束中同时加入SLIC超像素分割算法的结果以增加视差图的连续性，最后经过一致性判断后得到优化过的视差图。

图1 算法步骤

1.1 SURF算法特征提取和匹配优化

SURF（Speeded Up Robust Feature）意指加速的具有鲁棒性的特征，由Bay2006年提出。这项技术由SIFT[9-10]算子改进而来，比SIFT快好几倍，采用了harr特征[11]以及积分图像的概念，这大大加快了程序运行时间。

国内干法分级设备的回收率一般在60%～70%，同时因分选设备的磨损快、高压风机的安全经济问题以及细灰的收集和除尘等问题，均制约着电选的进一步发展。由于电选脱炭效率低、工艺不成熟，目前还未获得广泛应用。湖南某研究院于2006年在福建青州某造纸厂的自备电厂内进行了电选法工业试验研究，但系统一直不稳定，精矿热值小于12.54 MJ/kg，尾灰烧失量大于10%，至今未正常使用。

1）构建Hessian矩阵：

其中I（x，y）代表图像像素，G（t）代表二阶标准高斯函数

2）对Hessian矩阵的行列式进行简化：

3）构建尺度空间精确定位极值点。

4）确定方向得到特征描述子。

1.2 三角剖分建立2D网格

Delauney三角剖分的准则：

1）空圆特性：Delaunay三角网是唯一的 （任意四点不能共圆），在Delaunay三角形网中任一三角形的外接圆范围内不会有其它点存在。

2）最大化最小角特性：在散点集可能形成的三角剖分中，Delaunay三角剖分所形成的三角形的最小角尽可能的大。

1.3 SLIC超像素分割算法

SLIC（Simple linear iterative clustering）简单线性迭代聚类事实上是k-means[12]在超像素生成上的一个应用，不过有两个重要的区别：

1）优化过程中距离计算的数目会随着搜索空间接近超像素大小而显著减少。

2）所使用的加权的距离度量标准结合了颜色和空间的近似结果，与此同时还控制着超像素块的大小和紧凑性。

1.4 视差获得及优化

我们已经得到了部分稳定特征点的匹配，现在用贝叶斯方法进行分析。用S={s1，s2，…，sM}代表匹配好的稳定特征点对，对于每一个稳定特征点 sM=（uM，vM，dM）T，其中（uM，vM）代表坐标，dM代表视差。令O={o1，o2，…，oN}作为参考图像中的待匹配点，假设左右图像对应的观察点和S在给定视差的条件下满足独立分布，则联合概率分布函数为：

定义先验分布函数为均匀分布与高斯采样的线性和:

其中i表示点（un，vn）所属三角剖分的索引数，通过方程组可以解出每一个参数（ai，bi，ci）。

相似度定义为以观察点为中心的9*9窗口的像素的NCC函数[14]，以含有约束条件的Laplace分布作为似然概率分布：

其中β是一个常量，概率不为0的条件保证了在同一条极线上寻找右图的匹配点。

我们使用最大后验概率来计算视差，后验概率可以表示为：

找出使得这个后验概率最大的dn作为每个像素的视差值。表示与在同一极线上的右图中的观察点。通过建模可得观察点有如下的性质：

对于每一个视差dn，在右图中的观察点都是唯一的，所以我们用取了概率密度函数的负对数的能量函数求解使得p最大的视差：

只有当{d-μ|＜3σ的时候才计算能量函数，通过对每个像素操作，可以得到稠密的视差图。由于像素点可以处于多个三角形内，那么这些最小化能量函数的计算可以并行进行。

在此之后，将左图求右图和右图求左图的结果利用一致性判断去除不一致点集。

2 实验验证

为了验证算法的实际效果，将算法的每一步依次实现，并采用国际通用的Middlebury立体匹配算法测试平台上的4组图像数据集进行测试。这4组图像数据分别是：Tsukuba、Venus、Teddy[15]、Cones，都有真实的视差Ground Truth可供对比。实验结果均在CPU为Intel core i5 2.40GHz，操作系统为Windows7的PC上用VS2010开发编译平台实现的，多幅图像平均每幅运行时间为1.572 3 s。实验结果如下：

其中Tsukuba的分辨率是 384*288，Venus的分辨率是434*383，Teddy和Cones的分辨率是450*375。

表1显示了所提出的算法与现有几个算法效果对比，其中精确的值是根据Middlebury网站上的真实视差图计算得来，在表中，我们计算了非遮挡区域 （Nonocc）、所有区域（All）、视差不连续区域（Disc）所产生的匹配错误像素点所占的百分比，相应的调整误差计算的范围即可。

图2 所提算法在Middlebury图像对上的结果

表1 匹配结果误差百分比

可以看出，由于稳定特征点的较为准确的先验知识，所提算法在视差不连续区域有一定的优势，总体效果优于所对比的其余算法。

3 结束语

文中将匹配好的稳定特征点和SLIC超像素分割的结果作为先验知识，利用贝叶斯的方法对后续匹配作出了限制，提高了匹配精度，减少了大区域的匹配误差，与此同时，由于其余像素搜索空间的减小在运行时间方面也有了较大提升。在匹配精度方面，稳定特征点的选择和得到视差后的优化还可以有所提升。

[1]Scharstein D，Szeliski R.A Taxonomy and evaluation of dense Two-frame stereo correspondence algorithms[J].International Journal of Computer Vision，2002，47（1-3）:7-42.

[2]Weber M，Humenberger M，Kubinger W.A very fast censusbased stereo matching implementation on a graphics processing unit[C]//2009 IEEE 12th International Conference on. Computer Vision Workshops（ICCV Workshops），2009:786-793.

[3]Kuk-Jin Y，In So K.Adaptive support-weight approach for correspondence search[J].IEEE Transactions on Pattern Analysis&Machine Intelligence，2006，28（4）:650-656.

[4]Felzenszwalb P F，Huttenlocher D P.Efficient belief propagation for early vision[J].International Journal of Computer Vision，2006，70（1）:41-54.

[5]Kolmogorov V，Zabih R.Computing visual correspondence with occlusions using graph cuts[C]//Computing visual correspondence with occlusions using graph cuts.IEEE，2001（2）:508-515.

[6]Bay H，Tuytelaars T，Gool L V.SURF:Speeded up robust features[J].Computer Vision&Image Understanding，2006，110（3）:404-417.

[7]Lee D T，Schachter B J.Two algorithms for constructing a delaunay triangulation[J].International Journal of Parallel Programming，1980，9（3）:219-242.

[8]Radhakrishna A，Appu S，Kevin S，et al.SLIC superpixels compared to state-of-the-art superpixel methods[J].IEEE Transactions on Pattern Analysis&Machine Intelligence，2012，34（11）:2274-2282.

[9]Lowe D G.Object recognition from local scale-invariant features[C]//1999.The Proceedings of the Seventh IEEE International Conference on.Computer Vision，1999（2）:1150-1157.

[10]Lowe D G.Lowe D G.Distinctive image features from Scaleinvariant keypoints[J].International Journal of ComputerVision，2004，60（2）：91-110.

[11]Mita T，Kaneko T，Hori O.Joint Haar-like Features for Face Detection [C]//Tenth IEEE International Conference on. Computer Vision，Iccv，2005（2）:1619-1626.

[12]Kanungo T，Mount D M，Netanyahu N S，et al.An Efficient k-Means Clustering Algorithm:Analysis and Implementation[J].IEEE Transactions on Pattern Analysis&Machine Intelligence，2002，24（7）:881-892.

[13]Geiger A，Roser M，Urtasun R.Efficient Large-Scale Stereo Matching[C]//Proceedings of the 10th Asian conference on Computer vision-Volume Part I.Springer-Verlag，2010:25-38.

[14]Yoo J C，Han T H.Fast Normalized Cross-Correlation[J].Circuits Systems&Signal Processing，2009，28（6）:819-843.

[15]Scharstein D，Szeliski R.High-accuracy stereo depth maps using structured light[C]//In IEEE Computer Society Conference on Computer Vision and Pattern Recognition（CVPR 2003），2003（1）：195-202.

Fast stereo matching algorithm based on steady features and SLIC superpixels

QIAN Chao，ZHANG Xiao-lin
（Shanghai Institute of MicroSystem and Information Technology，Chinese Academy of Sciences，Shanghai 200050，China）

Focus on the problem existing in stereo matching that the accuracy and speed can not advance together，we propose a fast matching algorithm which is based on steady feature points and SLIC Superpixels.We use SURF algorithm to extract the feature points efficiently，then these points is triangulated for building a prior on disparities to reduce the search space and matching errors，SLIC Superpixels is treated as another restrictive condition at the mean time for further advancing matching accuracy and speed.Results for Middlebury standard test data shows that the algorithm can obtain disparities more quickly and accurately.

machine vision；stereo matching；SLIC Superpixels algorithm；triangulation；SURF algorithm

TN911.73

A

1674－6236（2016）23-0146-03

2016-03-21稿件编号：201603287

中国科学院战略性先导科技专项（B类）（XDB02080005）

钱 超（1991—），男，江苏扬州人，硕士研究生。研究方向：计算机视觉。