基于边缘和像素类型标记的立体匹配算法

基于边缘和像素类型标记的立体匹配算法

苏志斌，邹芳菊，吕朝辉

(中国传媒大学自动化系，北京100024)

摘要：提出一种基于边缘图像特征和像素类型标记的立体匹配算法，利用边缘信息及视差在边缘和非边缘区域的分布特征，指导有效初始视差在扫描线方向的传递。并且根据标记值对部分不可靠的像素点进行反向赋值和边缘内中值滤波处理，达到视差精化目的。实验证明这种方法对于整体视差范围不太大的远距离图像，能够获得较为精确的稠密视差图。

关键词：边缘；像素类型标记；视差；立体匹配

中图分类号：TP751文献标识码：A

收稿日期：2015-02-15

基金项目：“十二五”国家科技支撑计划重大项目“演出呈现关键技术研发与应用示范(项目编号：2012BAH38F00)”资助

作者简介：苏志斌(1987-)，女(汉族)，新疆乌鲁木齐人，中国传媒大学在读博士. E-mail： seedszb@cuc.edu.cn

Stereo Matching Based on Edge Feature and Pixel Labels

SU Zhi-bin，ZOU Fang-ju，LV Chao-hui

(Department of Automation，Communication University of China，Beijing 100024，China)

Abstract：This paper proposed a new stereo matching algorithm which used the edge feature and pixel labels to obtain the dense disparity map. The edge information and distribution of disparity around the edge area and non-edge area could provide effective guidance for the delivery of reliable original disparity through the label of each pixel designed in our method. After disparity optimization for the whole pixels along the scanline，the areas with special pixel labels were refined in opposite direction or in certain non-edge regions. Experiment results demonstrate the accuracy of our method for the disparity map generated by stereo images captured in a long distance.

Keywords：edge；pixel labels；disparity；stereo matching

1引言

在基于双目立体视觉的图像信息采集和视频处理中，立体匹配是其中的热门研究方向之一。通过立体匹配获得的稠密视差图有助于分析采集处理中的技术问题，当精度达到一定要求后，还能够结合单眼二维图像进行原始场景的还原。然而对于自然图像，受到噪声、低纹理、重复纹理及遮挡等多方面因素的影响，获得高精度的稠密视差图像依然是一个非常困难的问题[1]。现有的立体匹配算法主要有两个分支：基于局部的立体匹配算法和基于全局的立体匹配算法。经典的局部匹配算法有自适应权重(Adaptive Weight)，基于Census或AD-census组合的匹配度量方法等；经典的全局算法有动态规划(Dynamic Programming，DP)，图割(Graph Cut，GC)和置信度传播(Belief Propagation，BP)等[2]。全局匹配算法是从早期的局部匹配算法发展而成，一定程度上依赖局部匹配算法对初始值的准确估计，两种算法在性能上各具优劣。然而基于局部匹配的算

法由于模型结构简单，对每个像素的独立运算可以通过并行优化加速等特点，更适于实时的处理[3]，是立体匹配算法中一个重要的研究内容。

边缘图像是一类重要的底层特征，然而在现有的局部立体匹配算法中，基于边缘图像特征的研究相对较少。本文提出一种基于边缘图像特征和像素类型标记的立体匹配算法，充分利用边缘信息及视差在边缘和非边缘区域的分布特征，指导有效视差在扫描线方向的传递。

2算法流程及实现

本章节主要阐述算法各部分的主要内容。图 1给出的是算法的主要流程。整个算法的核心思想是基于像元的局部匹配方法，具体分为4个部分：1)生成以左眼图像为基准的初始化视差图和可信度图；2)以左眼为基准图像，生成边缘点图；3)在局部像素范围内，根据邻域像素类型标记和边缘点特征，综合基准图像的初始化视差图和标记值进行单个像素的视差优化，并赋予优化后像素点的标记值。4)行内和区域内视差结果精化。

2.1　初始视差图和可信度图获取

考虑到处理时间和准确率的平衡，初始视差图的获取采用固定窗口的经典局部匹配算法。为了获得尽可能多的初始准确点，采用文献[4]的方法构造结合SAD度量和census度量的鲁棒性较强的相似性测度代价函数CSAD-Census，如公式(1)、(2)所示。

图1　基于边缘和像素类型标记的立体匹配算法流程图

CSAD-Census=ρ(CSAD(p，d)，λSAD)

+ρ(Ccensus(p，d)λcensus)

(1)

(2)

通过函数ρ的加入，能够将代价函数取值的范围控制在0和1之间，同时避免了过大的偏差，有助于寻找最佳初始匹配点。

可信度在本文的算法中仅作为像素类型在标记过程中的参考因素，并不是唯一指导可靠像素传递的因子，因此选用实现简单，适用性和准确度较高的PKR准则，并根据文献[3]的方法计算像素的可信度conf(x，y)，当像素可信度超过阈值时，认为是可信点。

2.2　边缘图像获取及边缘方向检测

左眼基准图像采用基于canny的算子检测图像边缘。canny算法是目前公认的性能优良的算法，能够有效地提取较弱的边缘，有助于理解图像构成和分割预判发生视差跳变的区域。为获得足够数量的边缘点，本文对左眼图像的RGB通道分别提取边缘并合成边缘图像。

原始边缘图像中的单个边缘检测值无法直接体现其方向，但是可以通过边缘像素点邻域内其他值的分布总和来区分，因此本文提出一种在邻域给定区域内判断边缘逻辑值分布情况的算法来获得边缘点的方向特征。边缘方向的判断分两步进行：

(1)判断左右类/上下类边缘：在以x，y为中心的3×3十字范围内，若左右两侧像素边缘逻辑值均为0，而上下两侧像素逻辑值均为1时，当前边缘点为左右类边缘点；反之则为上下类边缘点。当遇到上下左右的边缘点逻辑值都为1的特殊情况时，认为当前点属于左右类边缘点。

(2)在(1)的基础上，继续预判该边缘属于左侧/右侧边缘点或上方/下方边缘点。以左/右边缘点的判定为例，比较当前点同左侧像素点的色彩差值，若小于或等于给定色彩阈值，则判定该点属于左侧边缘，用Ⅰ类边缘点表示；若大于色彩阈值，则判断改点属于右侧边缘，用Ⅱ类边缘点表示。对上下类边缘点的判定类似，区别是比较当前点同上方像素点的色差值。

在视差传递的过程中，边缘点同视差传递的关系规定如下：

2.3　像素类型标记方法

根据边缘点图对像素类型的划分，将整个视差图像的特征区分为边缘视差点和非边缘视差点。下表 1给出了具体像素类型的标记方法。

表1　像素类型标记方法

在标记像素的实现过程中，为了简化对像素类型的判断，我们将类型特征值赋予经过优化运算后的可信值中，每个点的可信度值在经过视差优化后便不具备其他作用，查询邻域像素类型时直接读取该点的可信图值即可。标记值的大小主要用于区分各类像素点，实际可以取0-255之间的任意值。

2.4　基于边缘和像素类型标记的初始视差优化

根据边缘图获得像素类型及具体标记方法之后，优化算法的主要任务就是沿着从上到下，从左到右的扫描线方向对每个像素点进行逐点的初始视差优化。对于每个待优化像素点，提取其边缘信息，视差信息和可信度信息，并且检查其邻域内左方的(x-1，y)点和上方的(x，y-1)点的可信图值(此时为像素类型标记值)和视差值。下文中用disp(x，y)表示x，y点的视差值，常数DISM表示跳变阈值，这里为一个视差像素所代表的等级数。整个像素优化的过程中应遵循如下原则：

(1)当前点标记值非104或非102时，当前点视差同左侧及上侧相比不应发生大的跳变，若超过跳变阈值DISM，则直接将左侧或上侧的视差值赋予当前点。

(2)若(1)的情况下发生当前点同左侧或上侧像素视差在DISM范围内的变化，接受当前点视差的条件是：在3*3邻域内满足变化方向和视差跳变范围小于等于DISM的点数超过一定阈值。该阈值视当前点的可信度而定，可信点的跳变点数阈值小于非可信点的阈值。

(3)当前点为非边缘点，同时左侧和上方像素点的标记值都为42时，当前点的变化视差可以是增大的方向，也可以是减小的方向。而当左侧和上侧的标记值为22时，变化视差只允许向减小的方向进行。

(4)当前点为非边缘点，左侧同上方的标记值为103或101时，若当前点可信，disp(x，y)可直接用于邻域视差值比较；若当前点不可信，取当前点右侧邻域内的视差均值作为当前点的视差值，再分别同上方和左侧像素点比较视差值。若当前点的视差值大于左侧及上侧，认为是非遮挡点，在传递过程中以42作为标记值。若当前视差值小于等于左侧及上侧，则认为是可能发生遮挡的点，传递过程中以22作为标记值。

(5)当前点为非边缘点，而左侧或上侧为边缘点，需要进行同边缘点方向相关的梯度检测，判断是否存在小范围内边缘缺失的情况，并进行补边。

(6)对于图像左边界处的点，由于受到边界对象截取后图像不完整匹配的影响，即使使用邻域信息也未必能获取正确的视差值，对于这些点先按照(3)中左侧和上方像素点的标记值都为42的方式在令视差不发生大波动的条件下传递，再将像素类型标记为11。在遇到边缘或上方有可信度等于42的点后，标记值为11的像素点停止视差传递。为保证准确性，被标记为11的点需要通过反向填充的方式处理。

2.5　视差结果精化

2.5.1　反向检测赋值

根据标记原则，像素类型值为11和22的点是不可靠的非边缘点，考虑到每一个像素点的视差优化同时受到来自左侧和上方两部分像素点的影响，选择在每行的精化运算结束后，对本行中类型值为11和22的点进行反向填值，即将右侧经过优化后更加可靠的视差传递给左侧视差波动较大的点。

2.5.2　边缘内中值滤波

上述的反向赋值完成了水平扫描线方向的视差精化，而垂直方向的视差可以通过边缘内中值滤波来进行处理。边缘内中值滤波的基本思想是以标记值为22的边缘内点为中心，形成左右上下宽度不大于BLOCK的滤波窗口，并且从中心起遇到标记值大于100或标记值为11或42的点停止，如图 2所示。

图2　边缘内中值滤波窗口示意图

进行边缘内中值滤波的过程中，需要注意以下3点：

1)中值滤波包括不规则窗口区域内的所有点。为区分经过滤波处理的点，将整个窗口内的标记值由22更改为23。在下一轮中值滤波时，将标记值为22和23的点均列入新窗口内的中值滤波序列中，然而结果仅对标记值为22的点进行重赋值。

2)在边缘数量较多的区域，边缘内中值滤波代价较准确度而言意义不大。因此在确定滤波窗口时加入额外的约束条件，即对于以(x，y)为中心的点，当且仅当水平方两侧宽度不大于BLOCK的滤波窗口内均为非边缘点时，进行边缘内中值滤波，否则将跳过当前点向右侧和下方继续寻找。

3)当视差范围超过一定程度，同时图像中含有大量连续变化的视差时(例如存在斜面，曲面等)，边缘内中值滤波的平滑作用可能会使准确率降低。此时，应考虑使用尺寸较小的滤波窗口。

3实验结果及分析

本文算法实验硬件环境为Inter(R)core处理器，CPU主频为2.4GHz，操作系统windows 7，编程工具Visual Studio 2008。算法的有效性通过Middleburry网站提供的立体图像库中的经典图像进行验证。图3为其中代表性的图像对之一Tsukuba的匹配算法验证结果。其中涉及的主要参数为：λSAD=10，λcensus=1，DISM=1，BLOCK=10。计算初始视差值的过程中，SAD窗口大小为3×3，census窗口大小为5×5。

从Tsukuba的验证结果可以看出，在携带边缘特征的像素类型标记指导下，算法在保证视差准确率的同时，还能够形成平滑效果，同时在一定程度上还原边缘的位置。然而受到初始边缘检测的影响，在一些边缘缺失区域，若左右两侧的视差值相差正好同设置的跳变阈值DISM相等，则很难通过优化算法中的补边处理还原这部分的边缘。若要改变这一情况，需要优化边缘提取算法，或结合其他基于像素色彩特征的方法将边缘更准确地提取出来。

表 2给出的是本文算法同其他算法在Middleburry网站上的测试结果和排名。其中nonocc表示非遮挡区域视差错误点率，all表示整体误点率，disc表示视差不连续区域的误点率。对比Tsukuba的结果显示，在整体视差精度上，本文算法优于传统的DP算法和GC算法；在非遮挡区域，本文算法优于全局DP算法和局部的RTCensus算法，略低于GC算法。然而对于Venus而言，本文算法虽然优于DP算法，却在准确率上低于GC等其他全局和局部算法。这是因为Venus图像含有大量的斜面，表现为连续变化的视差，而本文算法处理的是一个像素精度的初始匹配结果，乘以尺度系数后精度有所下降。

(a)　　　　　　　　　　　　(b)　　　　　　　　　　　　(c)

(d)　　　　　　　　　　　　(e)　　　　　　　　　　　　(f) 图3　tsukuba图像立体匹配结果 (a.经过基于边缘和像素类型标记的初始视差优化的匹配结果；b.经过视差初始化后得到的像素类型标记图；c.经过视差精化后得到的最终结果图，最终结果进行了5*5的中值滤波处理；d.视差真值图；e.和真值相比的误差图；f.和真值相比的符号误差图)

表2　同其他算法的主要结果比较

注：Error Threshold = 1。

4结论

本文算法整体上属于基于像元的局部立体匹配方法，但不同于传统的基于颜色、可信度传递及一致性检测的匹配算法，本文提出了一种基于边缘和类型标记的立体匹配算法，算法复杂度较低，且对于大面积的非边缘区域，在没有进行平面或曲面拟合的情况下，依靠标记值的传递原则，能保留一定的视差渐变过程，同时满足精度的需求。从仿真结果分析，该算法适用于视差整体范围较小的远距离场景。此外，通过像素类型标记，能够在原始边缘图像的基础上，结合对应的视差信息进一步获得封闭的图像边缘，有助于对图像区域的提取、分析和其他处理。但是，由于算法对视差优化和精化的过程受到边缘图像的制约，视差对象的边缘提取的越准确，越有利于视差的匹配优化；反之当边缘不足时，会较大程度地影响匹配结果。为满足算法的适用性和准确性，还需要进一步研究像素类型标记值在视差传递中的判定和约束方法。本文算法所还原的视差在尺度放大前为一个像素精度，对于连续变化的平面或曲面，还需要研究亚像素精度的视差优化方法。

参考文献

[1]李治江，冯谨强，曹文冬，曹丽琴，杨萍. 基于边缘特征和可信度的立体匹配算法[J]. 包装工程，2014，35(23)：47-51.

[2]Sun X，Mei X，Zhou M，et al. Stereo matching with reliable disparity propagation[C].3D Imaging，Modeling，Processing，Visualization and Transmission (3DIMPVT)，2011 International Conference on，2011：132-139.

[3]施陈博. 快速图像配准和高精度立体匹配算法研究[D].北京：清华大学，2011.

[4]Mei X，Sun X，Zhou M，et al. On building an accurate stereo matching system on graphics hardware[C].Computer Vision Workshops (ICCV Workshops)，2011 IEEE International Conference on，2011：467-474.

[5]Hu X，Mordohai P. Evaluation of stereo confidence indoors and outdoors[C].Computer Vision and Pattern Recognition (CVPR)，2010 IEEE Conference on，2010：1466-1473.

[6]Humenberger，Martin，et al. A fast stereo matching algorithm suitable for embedded real-time systems[J]. Computer Vision and Image Understanding，2010，114(11)：1180-1202.

[7]Boykov Y，Veksler O，Zabih R. Fast approximate energy minimization via graph cuts[J]. Pattern Analysis and Machine Intelligence，IEEE Transactions on，2001，23(11)：1222-1239.

[8]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.

(责任编辑：王谦)