基于交互式图像分割的立体匹配方法

王雅宁，梁新刚

(1.现代教学技术教育部重点实验室，陕西西安 710062; 2.陕西师范大学计算机科学学院，陕西西安 710119)

基于交互式图像分割的立体匹配方法

王雅宁1，梁新刚2

(1.现代教学技术教育部重点实验室，陕西西安 710062; 2.陕西师范大学计算机科学学院，陕西西安 710119)

立体匹配技术是三维重建系统以及非接触测量的关键步骤，在计算机视觉领域应用广泛。传统基于全局最优的立体匹配方法计算量大，算法框架复杂，通过引入图像分割等手段可以有效降低立体匹配的运算量。为了克服传统基于分割的立体匹配方法没有充分利用分割信息的缺点，提出了一种融合交互式图像分割的立体匹配方法。该方法通过引入用户交互，设置种子点并用快速图割算法完成感兴趣区域的分割提取，由分割模板建立网络图，进行立体匹配。由于仅针对分割区域构建网络图，充分利用网络图信息降低了运算量，因此，和现有的对整幅图像进行立体匹配方法相比，具有匹配准确、运算量小等优点，并通过实验进行了验证。

立体匹配;图割算法;交互;图像分割

0 引言

立体匹配技术是近年来计算机视觉领域广泛关注的难点和热点，它的目的是通过匹配两幅或多幅图像来获得视差图，以便可以计算出场景中的三维信息［1］。由于图割算法具有组合优化的优良性能，并且能够有效处理低纹理区域和遮挡像素［2］，因此广泛应用于立体匹配中。

Roy等［3］最早将图割算法应用于立体匹配，并通过实验表明，图割算法能有效克服其他全局优化算法的缺点(如动态规划算法等生成视差图产生的横向条纹瑕疵)，避免了视差在临近极线处不连续的问题。但该算法生成的视差图轮廓边缘模糊，视差层的区分度低。Boykov等［4］利用特定约束构造能量函数，并通过改进的最大流方法进行能量函数的最小化，将该图割算法应用于立体匹配问题，取得了效果良好的致密视差图。但该方法构建网络图时生成了大量节点，导致空间复杂度较高，同时，该算法运算过程需要多次迭代，时间复杂度高，无法达到实时计算的要求。为了提高匹配速度，Li等［5］提出基于无重叠视差区域分割的立体匹配，并用分割块的能量最小化取代了常用图割算法像素级的能量最小化，降低了算法的时间复杂度，但生成的视差图边缘处有毛刺现象。Bleyer等［6］利用图像在每个分割块中的视差具有光滑性的特点，提出了基于图像分割的立体匹配算法的通用算法。但该方法无法得到像素级的最优分配，且复杂度高，计算量大。Bleyer等［7］提出采用基于低尺度分割，将图像分割成超像素形式从而减少图割算法生成节点的立体匹配方法。假设相同物体具有紧凑、连接并且物体表面视差变化平滑等特性，提出了一种新的基于物体分割的立体匹配方法。该方法虽然在物体分割与视差获取上效果良好，但是运算量大，对于物体和背景的内部区域缺少纹理的深度信息，并且物体间的区域没有准确的视差标注。

上述文献中基于图像分割的立体匹配方法，由于采用自动化非交互的彩色图像分割方法会把相同视差的区域分开或隐去了图像的部分细节信息，导致分割误差，而消除误差需要引入其他方法，如初始视差估计［4-5］等，但这些方法增加了立体匹配算法的整体复杂度，而且没有有效利用分割信息。在实际应用场景中，为了获取感兴趣区域的精细视差图，针对以往基于图像分割的立体匹配算法复杂、计算量大，没有充分利用分割结果的信息等缺点［8］，提出一种基于交互式图像分割的立体匹配方法。该方法在图像分割时采用可交互的图割方法获得感兴趣目标，只针对感兴趣目标进行立体匹配，因此运算量大大减少，同时保留了原有图割算法具有的全局最优特性。

1 基于图割算法的立体匹配

在立体匹配问题中，视差图的标号问题可以等价为全局能量函数的最小化求值问题［9］，通常表示为Greig能量函数形式:

其中，f为视差标注;p为所有像素的集合;Dp为数据项;Vp，q(fp，fq)为平滑项;I1为待匹配图像;M⊂P*P为相邻像素对集合。

数据项一般可写成:

平滑项普遍选用Potts模型:

根据图割算法，利用式(1)构造由节点和连接节点的有向边组成的网络图G=＜V，E＞。网络图如图1所示［10］。

图1中，S点表示源点，T点表示汇点，视差边对应于能量函数式(1)中的第一项，平滑边对应于能量函数第二项。求解式(1)的能量函数的最小值可以等价为求解图的最小割问题，获得全局最优的视差图。

2 交互式快速图像分割

传统基于图割算法的图像分割将图像信息转化为求解对应加权图的最大流/最小割问题［4］，对于低分辨率的简单图像交互分割效果良好但是计算复杂度较高［11-12］，内存开销大。为了提高分割速度并且适用于高分辨率图像，需要减少分割网络中的节点个数，通过添加辅助颜色索引节点［13］，重新定义能量函数为:

其中，θs与θs-表示前景物体跟背景的非归一直方图;σ为图像中所有ΔI的均值。

该方法提高了图割算法图像分割的计算时间，并且能够得到精准的分割结果。

3 基于交互式图像分割的立体匹配

为了减少立体匹配的运算量，文中根据交互式分割的结果得到感兴趣物体与分割模版，由分割模版构建网络图，使用图割算法进行立体匹配，有效利用了分割信息。

综上所述，该算法可以概括为两大步骤:感兴趣目标的提取;利用网络图进行立体匹配。算法流程图如图2所示。

相对于传统方法，根据每个像素构建网络图的算法有所不同。对于图G=＜V，E＞，在两端分别添加源点S、汇点T之后，只在S到I1中每个属于左视图分割模版中标记为目标的像素点之间添加边，在T到集合{(px，py，qn)|(px，py)∈ I1}即立方体网络上与OXY平面相对的另一个面上的节点，添加对应到汇点的边。通过上述方法，可以大大减少计算量。

为了进一步优化匹配结果，文中在对网络图中视差边的处理上，针对彩色图像采用RGB三通道分开处理，用线性最近邻插值算法在图像的横坐标方向添加了亚像素信息，即将式(2)扩展为:

其中，ΔR，ΔB，ΔG为彩色图像各个通道的权值。

按照上述方法构造网络图G=＜V，E＞，并给各个边赋相应的权值，采用基于增广路的最大流算法进行求解［14-15］，得到全局最小值，即为最优视差匹配。

4实验

为了验证文中方法的有效性，在Windows 7 64位系统，CPU为2.5 GHz，内存8 G，编译器为Visual Studio 2010的测试环境下进行实验。实验图像来自Middlebury提供的立体匹配图像库:vision.middlebury. edu/stereo/data/。文中采用错误匹配率衡量算法的匹配性能，其定义如下［16］:

其中，M为整个图像的像素数;dC(x，y)为计算出的视差图;dT(x，y)为真实的视差图，在比对中，标准的真实视差图只取跟分割模板相同的部分，其余全部设置为背景;δ为误差容许值，取1。

利用上述图像库中提供的图像对，文中利用原始图割算法和SAD［16］算法分别对Tsukaba图像进行立体匹配，结果如图3所示。

从图3的视差图可以看出，相对于局部算法SAD［10］和图割算法，文中算法取得了较好的效果，并且最接近于标准视差。由于文中算法分割效果准确，并通过加权分通道处理、添加亚像素信息等手段，不但保证了视差图边缘的准确性，也保留了感兴趣区域内部的视差标注。

图3 立体匹配结果对比图

同时，为了进一步验证文中算法对遮挡，深度不连续，光照变化，低纹理、无纹理区域等的匹配性能，对Middlebury平台提供的部分标准图像进行实验，结果如图4所示。

从图4中可以看出，文中方法对于遮挡，深度不连续，光照变化，低纹理、无纹理区域等情形取得了较好的效果。同时，使用错误匹配率对实验结果进行定量分析，结果如表1所示。

从表1可以看出，与局部SAD算法、原始图割算法相比，文中算法具有相当高的精度。同时，为了比较算法的运算速度，文中统计了各个算法的运行时间，如表2所示。

从表2可以看出，由于相对于传统图割算法，文中算法只对分割出的感兴趣区域生成了立体网格，所以避免了多余的计算，因此，相对于全局优化的图割算法减少了运算时间。虽然文中算法运算时间大于局部算法，但是精度远高于局部算法，因为文中算法为了获取全局最优的视差标注进行了迭代运算，而SAD算法根据邻域窗进行横向匹配，仅能得到局部视差的近似解。

5 结束语

针对基于图像分割的立体匹配方法没有有效利用分割信息的问题，文中利用图割算法实现了基于交互式图像分割的立体匹配。该方法对于遮挡，深度不连续，光照变化，低纹理、无纹理区域均取得了良好的匹配结果。相对于以往算法，该方法得到了精确的匹配结果，并且在运算时间和计算精度上都有提高。

［1］ 肖艳青，刘党辉，孙 朋.图像立体匹配研究进展［J］.测控技术，2009，28(8):1-5.

［2］ 伍春洪，付国亮.一种基于图像分割及邻域限制与放松的立体匹配方法［J］.计算机学报，2011，34(4):755-760.

［3］ Roy S，Cox I J.A maximum-flow formulation of the ncamera stereo correspondence problem［C］//Proc of IEEE international conference on computer vision.Bombay，India: ［s.n.］，1998:492-499.

［4］ Boykov Y，Kolmogorov V.An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2004，26(9):1124-1137.

［5］ Hong L，Chen G.Segment-based stereo matching using graph cuts［C］//Proc of IEEE conference on computer vision and pattern recognition.Washington DC，USA:IEEE，2004:74-81.

［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］ Bleyer M，Rother C，Kohli P，et al.Object stereo-joint stereo matching and object segmentation［C］//Proc of IEEE conference on computer vision and pattern recognition.Colorado，USA:IEEE，2011:3081-3088.

［8］ 尹传历，刘冬梅，宋建中.改进的基于图像分割的立体匹配算法［J］.计算机辅助设计与图形学学报，2008，20(6):808 -812.

［9］ 王 年，范益政，鲍文霞，等.基于图割的图像匹配算法［J］.电子学报，2006，34(2):232-236.

［10］张令涛，曲道奎，徐 方.一种基于图割的改进立体匹配算法［J］.机器人，2010，32(1):104-108.

［11］尹传历，向长波，宋建中，等.一种基于自适应窗口和图切割的快速立体匹配算法［J］.光学精密工程，2008，16(6): 1117-1121.

［12］祝世平，杨 柳.基于自适应分水岭的图割的立体匹配算法［J］.光学学报，2013(3):221-229.

［13］Tang M，Gorelick L，Veksler O，et al.GrabCut in one cut ［C］//Proc of IEEE international conference on computer vision.Sydney，Australia:IEEE，2013:1769-1776.

［14］Kolmogorov V.Graph based algorithms for scene reconstruction from two or more views［D］.New York:Cornell University，2004.

［15］Kolmogorov V，Zabih R.Multi-camera scene reconstruction via graph cuts［C］//Proc of European conference on computer vision.Copenhagen:［s.n.］，2002:82-96.

［16］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.

A Stereo Matching Method Based on Interactive Image Segmentation

WANG Ya-ning1，LIANG Xin-gang2
(1.Key Laboratory of Modern Teaching Technology of Ministry of Education，Xi’an 710062，China; 2.School of Computer Science，Shaanxi Normal University，Xi’an 710119，China)

Stereo matching technology is the key step in 3D-reconstruction system and non-contact measurement，which has a wide range of applications in computer vision.The traditional stereo matching method based on global optimization is of large computation quantity，and the framework of its algorithm is very complex.By using the method of image segmentation，it can effectively reduce the amount of computation.In order to overcome the disadvantage that traditional method cannot make use of the information of segmentation，a stereo matching method integrated human-computer interaction image segmentation is presented.Introducing the user interaction and setting the seeds，the Region Of Interest(ROI)segmentation area is obtained by a fast graph cuts algorithm.Then the stereo matching is realized based on the network map which is constructed from the segmentation template.Compared with existing stereo matching methods，the method proposed has more accurate and less computational cost，which is verified by experiment.

stereo matching;graph cuts;interaction;image segmentation

TP391.4

A

1673-629X(2016)09-0163-04

10.3969/j.issn.1673-629X.2016.09.036

2015-09-19

2016-02-24< class="emphasis_bold">网络出版时间:

时间:2016-08-23

陕西省自然科学基础研究计划项目(2011JM8014);陕西师范大学实验技术研究项目(SYJS201314)

王雅宁(1990-)，男，硕士，研究方向为计算机视觉。

http://www.cnki.net/kcms/detail/61.1450.TP.20160823.1343.034.html