基于区域增长自适应窗口的Census变换立体匹配方法

王小明

（江西省地质矿产勘查开发局九一二大队 江西鹰潭 335000）

1 引言

随着社会对智慧城市建设需求的不断增强，基于双目视觉的城市三维重建越来越引发专家和学者的关注。立体匹配作为三维重建的关键性步骤，其匹配精度很大程度上决定了三维重建的精度。立体匹配过程可分为四个阶段：代价计算、代价聚合、视差计算和视差优化[1]。目前，立体匹配算法大致可分为两类：基于局部的立体匹配算法和基于全局的立体匹配算法[2]。Census变换[3]作为局部匹配算法的一种，以其对光照强度不敏感且算法复杂度较低等优势，在一种代价计算方法中脱颖而出。近年来，许多专家和学者致力于对常规Census变换算法的改进，大致可分为两类[4]：利用自身窗口不同特性改变计算方式或赋予一定权值[5-7]；结合其他具有互补特性的代价计算方式[8-9]。这些改进均从不同程度提升了匹配精度，但存在一个共同弊端；即在采用规则矩形窗口计算匹配代价，使得在图像不同区域适应性不强，从而导致易产生误匹配。且虽然匹配精度有所提高，但算法复杂度亦有不同程度的提升，一定程度上阻碍了算法的推广使用。

为解决以上问题，提出一种基于区域增长自适应窗口的Census变换立体匹配算法。该算法能在保持传统Census变换匹配速率的基础上，提升匹配精度。该算法针对传统Census变换算法采用矩形窗口计算匹配代价，使得在图像不同的纹理区域难以获取合适的窗口，且窗口易包含视差不连续区域，使得误匹配率增高的弊端，提出以待匹配点为种子点，利用一定规则的区域增长算法自适应地获取不同形状和大小的匹配窗口。且传统Census变换在代价聚合阶段采用垂直交叉自适应窗口，存在漏检区域，因此，在代价聚合阶段采用与代价计算阶段相同策略的区域增长算法获取聚合窗口。实验表明，基于区域增长自适应窗口的Census变换立体匹配算法匹配速率与传统Census变换算法相当，但匹配精度更优。

2 算法原理

2.1基于区域增长的自适应窗口策略

立体匹配实质上是寻找同名点的过程，其精度很大程度上取决于代价计算和代价聚合策略的优劣。本文欲结合基于区域增长的自适应窗口策略和传统Census变换的代价计算方法，提出一种既能保持传统Census变换算法对光照和各种幅度失真鲁棒性强的优势，又能一定程度弥补其误匹配率较高的劣势的算法。该算法从优化代价计算和代价聚合的窗口入手，结合文献[3]及文献[10]的方法，本文采用的基于区域增长的自适应窗口策略如式1所示。

以待匹配点p为种子点，分别沿其x轴正方向和负方向增长窗口。当满足以下条件时将新增点p1纳入窗口，否则停止该方向的增长：

①待匹配点p与新增点p1的灰度值之差小于阈值，且新增点p1与该方向下一点的灰度值之差也小于。

②新增点p1与待匹配点p之间的距离称为臂长Ds(p1,p)，臂长Ds(p1,p)小于于阈值L1。

③当臂长小于阈值L1，但大于另一特定值L2，且待匹配点与新增点p1的灰度差小于另一更小的阈值τ2。

其中，条件①不仅限制了待匹配点p与新增点p1之间的差异，也限制了新增点p1与该方向下一点的的差异。如此，不仅能将相近的像素纳入窗口，也能避免出口跨越图像内的边界。条件②和③使得窗口能获取合适大小和形状的窗口。条件②使得窗口能够纳入足够多的像素，但当臂长大于另一个更小的阈值L2时，此时对新增像素的要求更严格，需满足其与待匹配点p的灰度差异小于一个更小的阈值，确保了纳入窗口的像素都是与待匹配点相近的像素。

然后，以同样的策略对水平臂上的像素沿y轴正方向和负方向增长窗口。窗口增长流程图见图1。

图1 基于区域增长的窗口增长示意图

相较于传统Census变换算法采用的9 x7的矩形窗口，该窗口增长策略，不仅能在图像不同区域自适应地获取不同大小和形状的窗口，而且窗口内不易包含深度不连续区域，有利于提升匹配精度。

2.2 代价函数

确定匹配窗口后，进一步则需确定代价函数的选择。本文选择采用与传统Census变换一致的代价计算方法，该方法以对光照不敏感且对图像的各种幅度失真有较强的稳健性著称。该方法将匹配窗口内的其它像素点与待匹配像素点进行比较，若某像素灰度值大于待匹配像素点灰度值，则将该像素对应位置设为1，否则设为0。待整个窗口内像素都比较完成之后，得到一个只含0和1的比特串，然后用该比特串代替待匹配点的灰度值，计算公式如式2所示。

其中，p为待匹配点，q为匹配窗口内除待匹配点以外的点，I(p)为待匹配点的灰度值，I(q)为窗口内其他像素的灰度值，T(p)为经过比较之后获得的比特串。如此，获取左图和右图每个像素的比特串。

最后利用Hamming距离计算匹配代价，计算方法如图2所示。

图2 代价计算示意图

如图，获取左图和右图各像素点的比特串后，将左图上的待匹配点比特串与右图视差范围内的像素点的比特串进行比较，统计对应位不同的数量作为匹配代价。如图2中，左图和右图有两个对应位的比特数不同，则此时的匹配代价为2。

采用如上代价计算方法，考虑的仅仅是待匹配点与窗口内其它像素点间灰度值的相对大小关系，因此，当左图和右图亮度不一致时，也能获得较好的视差图。这也是Census变换算法对光照不敏感的原因。

2.3代价聚合

传统Census变换在代价聚合阶段采用的是垂直交叉自适应窗口，具有较好的适应性，但该窗口存在漏检区域，不利于获得最优的聚合代价。因此，本文采用与代价计算阶段相同，适应性较垂直交叉自适应窗口更强的的区域增长策略获取代价聚合窗口。将待匹配点x轴和y轴方向的像素视为水平臂和垂直臂。先将聚合窗口内的像素沿待匹配点p的垂直臂上聚合，然后再将p的垂直臂沿待匹配点p上聚合，获得该点的聚合代价值。其原理如图3所示。

图3 代价聚合示意图

与代价计算阶段不同的是，在代价聚合阶段采用2次迭代的方式，第一次迭代先沿水平方向增长再沿垂直方向增长窗口，第二次迭代先沿垂直方向增长，再沿水平方向增长，取二者中较小的作为代价聚合值。如此，能有效降低视差不连续区域的误匹配率。

视差计算采用“胜者为王（Winner Takes All,WTA）”策略，取聚合代价值最小的窗口对应的像素点为最佳匹配点，其对应的视差为最终视差。

3 实验分析

为验证算法的性能，利用Middleburry网站提供的标准测试图像对：bull、cones、teddy和venus进行实验。实验共分为两部分：第一部分将传统Census变换与本文基于区域增长自适应窗口的Census变换立体匹配方法获取的视差图进行对比；实验第二部分，为定量分析本文算法的性能，将传统Census变换与本文算法对以上四个标准测试图像对的匹配精度及算法运行时间进行对比分析。

经实验对比分析，算法中涉及的参数L1、L2、、分别取34、17、20和6。为测试本文基于区域增长自适应窗口的Census变换立体匹配方法的优势，实验第一部分分别获取了本文算法及传统Census变换的视差图，以直观分析两种算法获取的视差图的质量，对比图如图4所示。

图4 实验图集

由图可知，本文基于区域增长自适应窗口的Census变换立体匹配方法获取的视差图较传统Census变换更优，特别是在边界区域（如图中圈内区域）。这是由于传统Census变换在计算匹配代价时采用规则的矩形窗口，在图像不同区域无法获取最适合的匹配窗口，且易包含图像边界，导致在图像边界区域误匹配率较高。而本文基于区域增长自适应窗口的Census变换立体匹配方法在图像不同区域能自适应地获取合适大小和形状的匹配窗口，且在图像边界区域能自动退回至边界内，使得图像边界能得到较好的保持。

实验第二部分，为定量衡量本文基于区域增长自适应窗口的Census变换立体匹配方法的优势，将其匹配精度与算法运行时间与传统Census变换进行对比，结果见表1。

表1 算法性能对比

由实验结果可知，基于区域增长自适应窗口的Census变换立体匹配方法相较于传统Census变换，算法运行时间略长。这是由于算法较传统Census变换，增加了自适应获取匹配窗口的过程。但算法匹配精度更高，这是由于基于区域增长自适应窗口的策略能针对图像的不同区域自适应地获取合适的窗口用于匹配，有利于提高匹配精度。

4 结束语

针对传统Census变换在计算匹配代价时采用相同大小的规则矩形窗口完成整张图的匹配工作，缺乏良好的适应性，且在代价聚合阶段采用垂直交叉自适应窗口，存在漏检区域等缺陷，提出一种基于区域增长自适应窗口的Census变换立体匹配方法，在代价计算及代价聚合阶段，采用区域增长策略自适应获取合适大小和形状的窗口。实验结果表明，基于区域增长自适应窗口的Census变换立体匹配方法相较于传统Census变换算法运行时间略长，但匹配精度更高，综合比较，还是该算法更优。