基于动态规划的快速立体匹配算法

罗嗣卿，贾子书

（东北林业大学信息与计算机工程学院，哈尔滨150040）

·图形图像处理·

基于动态规划的快速立体匹配算法

罗嗣卿，贾子书

（东北林业大学信息与计算机工程学院，哈尔滨150040）

为提高立体匹配算法的匹配速度使其满足实时性要求，同时减少视差图中的条纹现象提高匹配准确率，基于动态规划原理提出一种快速立体匹配算法。利用快速自适应权重累积策略累积匹配成本，通过二维有序表结构加快动态规划的计算速度，采用基于方向滤波的视差后处理方法减少视差图中的条纹现象。实验结果表明，该算法在保证视差图准确的基础上能有效提高立体匹配效率，可应用于实时匹配系统。

立体匹配；动态规划；自适应权重；快速累积；积分图像

1 概述

立体匹配是计算机视觉领域中的一个经典问题，目前国内外学者已提出大量的匹配算法来解决这个问题，但由于问题本身的病态性而导致较少有算法能完美解决匹配中的所有困难。文献［1］对目前已有的各种算法进行了全面的分析和综述。根据该文献提出的分类标准，立体匹配方法可分为局部立体匹配方法和全局立体匹配方法。局部立体匹配方法的关键问题是确定支撑窗口。支撑窗口一方面要尽可能大以便包含足够多的灰度信息变化从而增强匹配的可靠性，另一方面要尽可能小，以避免投影畸变和窗口内视差不一致而导致的不正确匹配。支撑窗口的选择主要集中在2个方面：一方面集中在支撑窗口的尺寸与形状，例如文献［2-3］方法；另一方面集中在窗口内像素的支撑权重，例如文献［4-5］方法。虽然局部立体匹配方法在匹配准确率上已取得了较大的进展，但是由于在匹配过程中没有综合考虑全局信息，导致在非纹理区域和物体边界容易产生误匹配。全局立体匹配方法综合考虑了立体像对中的全局信息，通过优化算法最小化全局能量函数来求解最优视差，这类方法主要包括动态规划［6-9］、置信传播［10-11］和图割［12-13］方法。基于图割和置信传播的立体匹配方法是一种基于整体图像的全局匹配算法，其特点是匹配精度高、准确性好，但算法复杂度高。基于动态规划的立体匹配算法是一种基于扫描行的全局匹配算法，其特点是实现简单、效率高，但在匹配过程中由于缺少行间一致性约束而导致在视差图中出现较为明显的条纹现象。目前，大部分学者主要针对动态规划立体匹配方法中的两大问题进行研究：一是解决匹配中的条纹现象；二是加快动态规划立体匹配的速度使之成为一种实时立体匹配方法。Birchfie等人提出一种点对点（Pixelto-Pixel）的动态规划立体匹配方法［9］。该方法分为2个阶段：匹配阶段和后处理阶段。匹配阶段包括2个版本的动态规划立体匹配算法：Backw ard-Looking算法和Forward-Looking算法。这2种算法在计算最优路径的过程中执行了大量的冗余计算，为此，Birchfie又提出一种快速Forward-Looking算法，有效地缩短了Forw ard-Looking算法的计算时间。但该快速算法在理论上损失了最终解路径的最优性，造成了视差精度损失，而且由于缺少成本累积阶段也造成了一部分视差精度的损失。

本文针对快速Forward-Looking算法存在的缺点，提出一种基于动态规划的立体匹配算法。首先根据快速自适应权重累积策略在视差空间图中累积匹配成本，然后利用快速Backw ard-Looking算法计算视差，最后通过视差后处理方法去除视差图中的条纹现象，提高视差精度。

2 视差空间建立

视差空间图（Disparity-space Image，DSI）［6］是一个三维数据结构，该结构中的每一点（x，y，d）都代表参考图像中的像素点（x，y）被赋予视差d时的匹配代价。本文提出的快速立体匹配算法利用这个数据结构来表达匹配中的遮挡和匹配，并通过动态规划获得一个最小成本路径，其中路径中的每一节点都代表一对匹配。

2.1 匹配成本

匹配成本是立体匹配方法的基础，它测量的是2个位置的相似性或者不相似性。计算匹配成本最直接方法是采用像素点的灰度差绝对值，但该方法对噪声和辐射差异的鲁棒性很差，易造成能量函数中的数据项不能准确反应匹配约束。因此，在实际计算过程中经常采用截断的匹配代价计算方法，其计算公式如下：

其中，IL（x，y）表示参考图像；IR（x，y）表示匹配图像；IS表示截断阈值。

2.2 快速积累方法

在匹配过程中，经常需要对匹配成本进行累积以增加匹配的可靠性，其成本累积形式可表示为：

将式（3）代入式（2）整理得：

为了能使用积分图像加速该权重函数的计算，本文将函数f（k）取为恒定的常数函数ω，为此，式（4）可简化为：

针对式（5）中的c（p，d），c（p，d）IL（p），c（p，d）和IL（p）分别建立积分图像，然后使用这些积分图像累积匹配成本，从而提高累积过程的计算效率，使累积过程的计算复杂度与窗口大小无关。

3 动态规划原理及快速实现

3.1 动态规划原理

本文提出的立体匹配方法是一种基于扫描行优化的全局立体匹配方法，它把立体匹配中的对应搜索问题阐述为在每一扫描行y0所对应的二维代价矩阵φy0［d，x］=c（x，y0，d）中（如图1（a）所示）查找最优成本路径问题，其最优路径上的每一节点代表着相应的匹配点。针对每一扫描行y0，其相应的能量函数可表达为：

其中，κOCC表示遮挡惩罚；kr表示匹配奖励；c（xi，y0，d）表示匹配成本；NOCC和Nm分别表示遮挡数和匹配数。如图1（b）和图1（c）所示，根据次序性约束和遮挡约束，当前匹配点（di，xi）的直接前驱和直接后继可分别表示为：

其中，Δ表示最大视差。利用动态规划技术在代价矩阵φy0［x，d］上求解最优成本路径，相当于计算如式（9）所示的递归公式：

反向追踪找到最优成本路径。在文献［9］中根据图1（b）更新代价矩阵的算法称为Backward-Looking算法，而根据图1（c）更新代价矩阵的算法称为Forward-Looking算法。

图1 动态规划的搜索空间

3.2 快速Forward-Looking算法的最优性分析

Backward-Looking算法和Forward-Looking算法在计算最优路径时执行了大量的冗余计算，为减少这部分冗余计算，文献［9］提出了一种快速的Forw ard-Looking算法。该算法是在Forward-Looking算法的基础上通过修剪策略减少这些不必要的计算，该修剪策略为：如果某一匹配的匹配成本大于其所在行中的最低匹配成本，则拒绝向右扩展该匹配；类似地，如果某一匹配的匹配成本大于其所在列中的最低匹配成本，则拒绝向下扩展该匹配。虽然该算法减少了大量的冗余计算，提高了算法的匹配速度，将优化部分的时间复杂度从O（nΔ2）降到了O（nΔlgΔ），但是该算法导致解路径损失了最优性，造成了视差精度的损失。

如图2所示，存在一匹配点p和及其后继匹配点c，它们之间存在着左遮挡。现假设存在一点r，它与匹配点p位于同一扫描行并且假设r点的匹配成本小于p点的匹配成本即r0（r）＜r0（p）。那么当快速算法遇见匹配点p时，则拒绝向右扩展匹配点p，因为在它所在的行中存在更低的匹配成本。然而，如果p点左边那些匹配点的匹配成本都大于p点的匹配成本时，则到c点的最优路径很可能会经过p点，所以会使解路径损失其最优性，从而导致视差精度的损失。

图2 最优性损失

3.3 快速Backw ard-Looking算法

为了提高动态规划立体匹配方法的匹配效率同时保证不损害解路径的最优性，本文提出了一种快速Backward-Looking算法。该算法以Backward-Looking算法为基础，通过二维有序表结构加快了动态规划部分的计算，而且该算法在理论上没有损失解路径的最优性。快速实现动态规划立体匹配算法的关键是快速实现递归公式（式（9））中的最小化操作。Birchfie提出的Forward-Looking算法和Backward-Looking算法实现最小化操作的时间复杂度为O（Δ），而其提出的快速Forward-Looking算法通过修剪策略减少了不必要的节点扩展，将最小操作的时间复杂度降低为O（lgΔ）。为了加快最小化操作的计算速度，本文首先分析式（9）中最小化操作的结构。由于式（9）中的遮挡惩罚κOCC是一个恒定的常数项，因此

其中的最小化操作可以简化为：

如果已知：

则式（10）可以简化为：

通过式（13）计算动态规划中的最小化操作只需3次比较，与视差范围Δ无关。由于二维数组a，b存在如式（14）与式（15）所示的递归关系：

因此，本文设计2个二维有序表a和b，其中的每一点都分别代表垂直方向和对角方向上的最小值，而且维护每个二维有序表仅需要一次比较，其二维有序表的结构如图3所示。其中，成本矩阵φ中每个元素对应着视差空间图中相应的元素；有序表a中每个元素都是一个三元组（v，d，x），v代表φ［0，x］～φ［d，x］之间的最小值，d和x代表其相应的坐标；有序表b中每个元素也都是一个三元组（v，d，x），v代表φ［d+x，0］～φ［d，x］之间的最小值，d和x代表其相应的坐标。

图3 最小化操作的快速实现过程

本文以计算φ［4，4］为例来说明这一快速计算过程，如图3中代价矩阵所示，φ［4，4］为图3中的黑色单元格。如果根据式（9）计算该单元格的值，则有：

式（16）表明计算每个单元格需要Δ次比较。如果根据有序表a和b计算该值，则有：

式（17）表明根据有序表计算该值仅需要3次比较，而且维护有序表a和b仅需要2次比较，通过该快速计算方法可以节省大量的计算时间，而且没有损失解路径的最优性。

本文提出的加速方法仅适用于Backward-Looking算法，因为当计算当前节点最优匹配代价时，它的所有前驱节点都已计算完成，而且可以在计算最优代价的同时来维护这2个有序表，具体算法如下所示：

3.4 基于方向滤波的视差后处理

由于动态规划立体匹配算法在优化过程中缺少行间一致性限制导致在视差图中产生了条纹现象。因此本文提出一种基于方向滤波的视差后处理方法，该方法的优点是实现简单、速度快，可以有效地减少条纹现象。

在该视差后处理方法中，首先提出一种线状滤波器族，该滤波器族中的每个滤波器之间间隔相等的角度，且每个滤波器与水平方向分别成θi角度，然后分别使用这些滤波器对视差图中的每个像素进行处理。

图4显示了一个线状滤波器族，图中的每个滤波器之间相隔15°。

图4 线状滤波器族

一般来讲，每个线状滤波器含有2 l+1个像素，且与水平方向成θi角度，其数学表达式为：

基于方向滤波的视差后处理方法的具体过程如下：

（1）在滤波器族中选择一滤波器fθi（x，y）。

（2）在视差图中选择一像素点（x，y），然后对在该点滤波器内的像素进行统计生成视差直方图，视差直方图内视差出现频率最高的视差即为mode，其频率为max（x）；（x，y）点的视差d及其左右相邻视差d-1，d+1的出现频率分别为hist［d］，hist［d-1］，hist［d+1］，它们的频率和为inertia=hist［d］+ hist［d-1］+hist［d+1］。

（3）如果max（x）＞inertia，则当前点（x，y）的视差为mode，否则如果hist［d-1］＞max（x），则当前点（x，y）的视差为d-1，否则如果hist［d+1］＞max（x），则当前点（x，y）的视差为d+1。

经过上述滤波处理之后，已基本去除视差图中的条纹现象，而且可以有效提高视差的准确度。在实际应用当中，一般选择较少的滤波器即可获得较好的效果，本文选择了4个滤波器，即θi∈［0°，45°，90°，135°］。

4 实验与结果分析

4.1 实验环境

为验证本文算法的性能，本文使用了C++语言实现了该算法，并在CPU Pentium IV 2.2 GHz，内存2 GB，操作系统W indow s XP的环境下对M iddlebury网站上提供的立体数据集Tsukuba，Venus，Saw tooth和Map进行了测试。

4.2 经验参数分析

在本文提出的立体匹配方法当中涉及到了一些经验参数的选择，这些参数会直接影响立体匹配方法的匹配精度，要选择合适的经验参数保证达到最好的匹配效果。为此，本文以M ap立体像对为测试对象，分析了成本截断阈值、遮挡成本及匹配奖励对立体匹配精度的影响以确定合适的经验参数。

分别进行3组实验测试经验参数对匹配精度的影响。

实验1 分析了成本截断阈值TS对匹配精度的影响。首先假定遮挡成本κOCC=15，匹配奖励kr= 30，然后测试成本截断阈值对匹配精度的影响，具体测试结果如表1所示。实验1结果表明成本截断阈值为30时，坏点比例最低，立体匹配效果最好。

表1 成本截断阈值对匹配精度的影响

实验2 分析匹配奖励kr对匹配精度的影响。首先假定遮挡成本κOCC=15，成本截断阈值TS=30，测试匹配奖励kr对匹配精度的影响，具体测试结果如表2所示。实验2结果表明匹配奖励为40，45，50时，坏点比例最低，具有较好的匹配效果。

表2 匹配奖励对匹配精度的影响

实验3 分析遮挡惩罚κOCC对匹配精度的影响。首先假定匹配奖励kr=40，成本截断阈值TS=30，测试遮挡惩罚对匹配精度的影响，具体测试结果如表3所示。实验3结果表明遮挡惩罚为15时，坏点比例最低。

表3 遮挡惩罚对匹配精度的影响

通过以上3组实验可以看出，当匹配奖励kr= 40，成本截断阈值TS=30及κOCC=15时，可以达到最佳的匹配效果。因此，在后续的测试当中，选择该组参数进行测试。

4.3 时间复杂度分析

为提高匹配精度，本文在匹配之前加入了成本累积，该累积策略只包含了值域支撑支持，忽略了空间支撑；然后选择了二次函数作为窗口函数；最后通过积分图像加速该过程的计算速度使其与窗口大小无关。本文提出的快速自适应成本累积的计算时间与没有使用积分图像累积过程的计算时间对比如图5所示。可以看出，当没有使用积分图像时，累积速度随着窗口大小的增加而迅速增加；而当使用积分图像时，该过程的计算时间与窗口大小无关，其计算时间表现为平行于x轴的一条直线。

图5 累积过程的时间对比

Backw ard-Looking算法和Forw ard-Looking算法的时间复杂度为O（nΔ2），其中，n为图像宽度，Δ为最大视差搜索范围；快速Forw ard-Looking算法的时间复杂度为O（nΔlgΔ）；而本文提出的快速Backw ard-Looking算法的时间复杂为O（nΔ）。上述4种算法的运行时间对比如图6所示，可以看出本文的快速算法具有更快的匹配速度，而且该算法没有导致解路径损失最优性造成视差精度损失。

图6 运行时间对比

4.4 匹配精度分析

为验证本文算法的立体匹配效果，利用本文算法对Tsukuba，Venus，Saw tooth和M ap进行实验，结果分别如图7～图10所示。可以看出，经过视差后处理之后视差图中的条纹现象明显减少，本文算法的最终视差图非常接近于真实视差图，具有较好的匹配效果。

图7 Tsukuba图像实验结果

图8 Venus图像实验结果

图9 Saw tooth图像实验结果

图10 M ap图像实验结果

将本文算法与同类算法（传统DP，SO，GCP+ DP算法、Two-Pass算法、TreeDP算法和Pixel-to-Pixel算法）的坏点比例进行对比，结果如表4所示。可以看出，本文提出的后处理算法复杂度非常低，处理实验中的立体像对的时间一般在0.2 s左右。为了给出匹配精度的定量分析，本文同时计算了非遮

挡区域all、非纹理区域untex和视差不连续区域disc的误匹配率，并与其他同类算法进行了对比。

表4 本文算法与其他算法的处理结果对比%

由表4可见，本文算法的优于其他动态规划算法，而且该匹配算法具有较快的匹配速度。实验结果表明，本文算法是一种高效可靠的立体匹配算法，它不仅可以获得准确性较高的视差图，而且具有较快的匹配速度，有效地提高了算法的匹配效率，可以应用于实时匹配系统。

5 结束语

通过分析成本函数结构发现，利用恒定的遮挡惩罚能大幅简化成本函数的结构，使用2个二维有序表可有效提高算法的计算速度。为此，本文在此基础上提出了一种基于动态规划的快速立体匹配算法。首先利用积分图像加快自适应权重累积策略的计算速度，使计算量与窗口大小无关，然后通过一种二维有序表结构在保证不损失解最优性的情况下提高动态规划部分的运算速度，最后采用视差后处理方法减少视差图中的条纹现象。实验结果表明，该算法是一种高效可靠的立体匹配算法，可以应用于实时匹配系统。下一步将研究保存边缘的滤波方法以改善成本累积过程，并尝试将本文算法移植到GPU平台，以加快匹配速度。

［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）：7-42.

［2］ Yang Qingxiong.Stereo Matching Using Tree Filtering［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence，2014，37（4）：834-846.

［3］ 祝世平，李 政.基于改进梯度和自适应窗口的立体匹配算法［J］.光学学报，2015，35（1）：123-131.

［4］ Heo Y S，Lee K M，Lee S U.Robust Stereo Matching Using Adaptive Normalized Cross-correlation［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2011，33（4）：807-822.

［5］ 翟振刚，陆 耀，赵 红.利用块几何约束及视差概率的立体匹配算法［J］.软件学报，2010，21（11）：2985-2998.

［6］ Bobick A F，Intille S S.Large Occlusions Stereo［J］. International Journal of Computing Vision，1999，33（3）：181-200.

［7］ Kim JC，Lee K M，Choi B T，et al.A Dense Stereo Matching Using Two-pass Dynamic Programming with Generalized Ground Control Points［C］//Proceedings of IEEE Computing Society Conference on Computing V ision and Pattern Recognition.San Diego，USA：IEEE Press，2005：1075-1082.

［8］ Veksler O.Stereo Correspondence by Dynamic Programming on a Tree［C］//Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition.San Diego，USA：IEEE Press，2005：384-390.

［9］ Birchfield S，Tomasi C.Depth Discontinuities by Pixelto-Pixel Stereo［J］.International Journal of Computing Vision，1999，35（3）：269-293.

［10］ Da Feipeng，He Fu，Chen Zhangwen.Stereo Matching Based on Dissimilar Intensity Support and Belief Propagation［J］.Journal of Mathematical Imaging and Vision，2013，47（1/2）：27-34.

［11］ 张惊雷，王艳姣.基于图像区域分割和置信传播的立体匹配算法［J］.计算机工程，2013，39（7）：257-260，278.

［12］ Wang Daolei，Lim K B.Obtaining Depth Map from Segment-based Stereo Matching Using Graph Cuts［J］. Journal of Visual Communication and Image Representation，2011，22（4）：325-331.

［13］ 祝世平，杨 柳.基于自适应分水岭的图割的立体匹配算法［J］.光学学报，2013，33（3）：228-236.

编辑金胡考

Fast Stereo Matching Algorithm Based on Dynamic Programming

LUO Siqing，JIA Zishu
（College of Information and Computing Engineering，Northeast Forestry University，Harbin 150040，China）

A fast stereo matching algorithm based on dynamic programming is proposed to improve the efficiency of stereo matching to meet the real-time requirement and reduce the streaking phenomenon in a disparity map to increase matching accuracy.In this algorithm，the fast adaptive weight aggregation is firstly used to aggregate raw matching costs. Secondly，the stage of dynamic programming for computation of disparities is accelerated by two dimensional order tables.Finally，a disparity post processing method based on oriented filters is em ployed to reduce the streaking phenomenon in a disparity map.Experimental results show that the proposed algorithm can improve the efficiency of stereo matching and the matching accuracy.It can be applied in real time matching system.

stereo matching；dynamic programming；adaptive weight；fast aggregation；integral image

罗嗣卿，贾子书.基于动态规划的快速立体匹配算法［J］.计算机工程，2015，41（11）：224-231.

英文引用格式：Luo Siqing，Jia Zishu.Fast Stereo Matching Algorithm Based on Dynamic Programming［J］.Computer Engineering，2015，41（11）：224-231.

1000-3428（2015）11-0224-08

A

TP391.41

10.3969/j.issn.1000-3428.2015.11.039

国家自然科学基金资助项目（71473034）。

罗嗣卿（1964-），男，副教授、硕士，主研方向：图像处理，数据挖掘；贾子书，硕士。

2015-06-01

2015-07-21 E-m ail：luosq@nefu.edu.cn