李智鹏;宋勇;余烨;何小旭;聂振兴
【摘 要】In the traditional local stereo matching algorithms ,cost aggregation needs to accomplish the weighted point aggregation in the correlated neighborhood model ,which causes large computation and extraordinary time consumption .In this paper ,a new stereo matching algorithm based on the minimal spanning tree theory is proposed which is applied to the cost aggregation and disparity refinement .In this method ,interesting points can get the aggregation support from all points in the image ,w hich o‐vercomes the deficiency of high false matching rate in weak texture region in local stereo matching al‐gorithm ,and improves the matching accuracy .At the same time ,all points in the image can be divid‐ed into different levels through the minimal spanning tree ,thus reducing the computation time abun‐dantly .T he experimental results show that ,through the algorithm proposed ,smooth disparity maps with high accuracy can be achieved rapidly .%在传统的局部立体匹配算法中，代价聚合要对相关邻域内的点进行加权聚合，这种方式计算量大，非常耗时。文章提出 一种基于最小生成树的立体匹配算法，该方法将图论中的最小生成树引入代价聚合和视差细化中，使得图像中所有点都对兴趣点进行聚合支持，弥补了局部算法在弱纹理区误匹配率高的局限性，提高了匹配的准确性，并且最小生成树能够对图像所有点进行层次性的划分，极大地简化了计算量。实验证明，该算法能够快速得到平滑且精度高的视差图。
【期刊名称】《合肥工业大学学报（自然科学版）》
【年(卷),期】2015(000)005
【总页数】5页(P622-626)
【关键词】立体匹配;双边滤波;最小生成树;自适应
【作 者】李智鹏;宋勇;余烨;何小旭;聂振兴
【作者单位】四川航天系统工程研究所，四川 成都 610000;四川航天系统工程研究所，四川 成都 610000;合肥工业大学 计算机与信息学院，安徽 合肥 230009;四川航天系统工程研究所，四川 成都 610000;合肥工业大学 计算机与信息学院，安徽 合肥 230009
【正文语种】中 文
【中图分类】TP391.41
0 引 言
自20世纪80年代第1个计算机视觉系统框架被提出以来，立体匹配一直是计算视觉研究领域的热点。文献［1］将立体匹配算法归为全局算法和局部算法2大类，并将立体匹配算法分为以下4个步骤：① 匹配代价计算；② 代价聚合；③视差最优化；④ 视差细化。
全局算法主要是采用全局最优化的思想估计视差值，它需要一个全局的能量函数，通过最小化全局能量函数得到最优的视差值，它没有代价聚合的过程。这种方式能够得到准确度非常高的视差图，但是计算开销大、费时，不能运用于实时系统。文献［2］提出了图割算法进行立体匹配，采用最大流、最小割理论计算最佳视差值；文献［3］提出了基于置信传播的立体匹配算法，采用马尔科夫网络计算最大后验概率从而得到最优视差；文献［4］提出了基于神经网络的匹配算法，通过边缘特征在3个约束下的对应关系构建目标函数，采用分级提取边缘的思想实现实时匹配；文献［5］引入了水平和垂直方向不连续的最小约束到动态规划算法中，有效地提高了匹配的速度。
局部算法依赖于兴趣点相关邻域内的像素对其加权聚合，计算简单、效果适中，适用于实时系统，但是对噪声敏感，在遮挡区域匹配效果不好。文献［6］提出一种单向匹配算法，利用极限约束只从左到右匹配1次，并且从数学的角度提出了优化的计算策略，极大地提高了匹配速度；文献［7］提出了一种基于窗口的自适应权重立体匹配算法，通过相似性自适应地调整窗口中权值的大小，在局部算法中取得了良好的效果；文献［8］利用视差图的分段连续性，将像素点分为特征点和非特征点，提出了一种快速双目立体匹配算法，但是线条特征明显，在视差渐变处精度一般；文献［9］利用双边滤波的思想，提出了一种non－local的快速代价聚合方法，能够得到平滑高精度的视差图；文献［10］利用图像分割的思想，提出了分割树的匹配算法，能够得到高精度的视差图，但是计算复杂度非常高；文献［11］没有关注匹配代价计算和代价聚合，而专注于视差细化的过程，实验效果相当显著，证明了视差细化的重要性；文献［12］添加了多因素的影响，改进了自适应权重匹配算法，增加了匹配的准确性。
鉴于对立体匹配算法的快速性和准确性需求，在前人研究的基础上，本文提出了一种基于最小生成树的立体匹配算法。它采用双边滤波的思想，在代价聚合中将整幅图像向兴趣点聚合，并在视差细化方面采用了相似的方式进行滤波，使得聚合和细化能够有效结合，提
高了匹配的精度，加快了算法整体的速度。
1 算法介绍
立体匹配最终要得到平滑、准确、稠密的视差图，研究的关键问题是求取视差。代价聚合是利用邻域中像素点的匹配代价加权和来计算中心像素点的最终代价，聚合将当前点的匹配代价向周围传递，以达到纠正错误匹配即滤波的目的，所以代价聚合实质上也是一个滤波的过程。而视差图有许多深度不连续区域，某些滤波器在滤除噪声的同时也会将一些边缘区域模糊掉，所以采用保边去噪的双边滤波器是一个很好的选择。一般的双边滤波器是在一个子区域内进行加权滤波的。局部立体匹配算法也是在一个子区域内进行聚合的，相关窗口的选取影响着匹配的快速性和准确性。局部算法寻最佳匹配点是一个局部最优化过程，受到局部特征的影响，它的局限性在于针对弱纹理和遮挡等区域无法有效地到正确匹配点。为了弥补这种缺陷，本文提出了一种新的算法，是在双边滤波的基础上增加了最小生成树的结构改进，算法流程如图1所示。
图1 算法流程图
每个步骤的说明如下：
（1）匹配代价计算。本文采用经典的AD方法，计算出每一个视差下的匹配代价。
（2）代价聚合。本文将图像上的所有点都向兴趣点聚合，计算出新的匹配代价。在这里本文引入了双边滤波和最小生成树。双边滤波具有保边去噪的特性，并且能够产生自适应的权值。最小生成树能够使得整体的匹配代价最小，还能够对图像中所有像素点进行层次性的划分，使得所有点的的聚合有了统一的标准。其他点对兴趣点的权重支持依赖于最小生成树上它们之间的最短路径。
（3）计算视差值。本文采用WTA优胜者全选的方式，每一个视差值都有一个最终的匹配代价，WTA就是选取最小匹配代价对应的视差值为兴趣点最终的视差。
（4）视差细化。优化视差图，验证舍去错误匹配点，本文采用与代价聚合相似的方式，通过图像所有点来验证。
与其他的局部算法相比，该方法计算简单，没有复杂的数学公式，没有涉及到相关窗口，计算复杂度为ο（HWdmax）。
本文特在于将最小生成树引入代价聚合和视差细化。
1.1 自适应权值的代价聚合
本文将图像看成一个无向图G（V，E），则图像上的像素点为无向图的顶点v，相邻像素点的差值为相邻顶点的权值w。此无向图G（V，E）中有若干回路，不便于聚合，本文采用Kruskal算法将其转化为最小生成树，这样去除回路后既简化了聚合过程，又能使整体的聚合代价最小。本文将左上角第1个像素点约定为树的根节点，父子节点关系使树结构化，从而进一步简化聚合过程。
代价聚合针对的是匹配代价，匹配代价在聚合之后要进行最优值比较，所以双边滤波能够进行改造，即
改造的结果既能省略平均过程、简化计算，又不影响比较的结果。其中，G（p）为滤波器输出；f（q）为滤波器输入；权值S（p，q）为：
其中，Dis（p，q）表示最小生成树上p、q 2点的最短路径；σ为一个常数。（2）式是一个权重传递的过程，体现了双边滤波思想中位置与像素值2方面的变化。本算法对于兴趣点的代价聚合值计算公式如下：
其中，Ea（p）为来自图像上所有点的代价聚合支持值；V为所有像素点的集合。
1.2 简化聚合步骤及证明
本文发现每一个点的代价聚合值只与它的父节点和子树有关，这又进一步简化了代价聚合的复杂度。
证明
其中，Tr为s点下的一颗子树；r为子树Tr的根节点；点v为子树Tr 里的任意一点；S（s，v）为点s和点v之间的权重系数；Et（s）为点s的子树对它的聚合。
（4）式可转换为：
（5）式表示点s的子树对它的聚合Et（s）可以转化为子树上所有点对子树根节点的聚合值与根节点r对点s的权重支持S（s，r）的乘积。
其中，（v）为点v下子树中所有节点对它的聚合支撑，v∈Tr；P（vc）为点vc 的父节点。如果点v为叶子节点，则（v）＝f（v）；如果点v为根节点，则（v）＝Ea（v）。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议