基于十字交叉域的Census 立体匹配算法优化研究

宋培玉，王 森

（华东交通大学理学院，江西 南昌 330013）

立体匹配技术在近年来成为机器视觉的热点研究问题。 立体匹配技术是获取图像三维深度信息的重要手段，广泛应用于三维场景重建、无人驾驶、医疗诊断等领域[1]。 但是，快速得到高精度的图像深度信息与立体匹配算法紧密相关[2]。

立体匹配算法根据约束条件的不同大致可以分为全局匹配算法、 半全局匹配算法和局部匹配算法。 全局匹配算法主要是根据全局能量函数最小化来计算深度值。 在全局匹配算法中常用的匹配算法有动态规划法[3]、置信度传播法[4]和图割法[5]。全局立体匹配算法虽然效果比较好， 但是硬件设备要求高，时间复杂度偏高不利于实时计算。 半全局算法[6]将二维图像的优化问题转化为多条路径的一维优化来计算像素点的匹配代价。 局部算法主要是基于非参数变换和灰度相关性进行匹配。基于灰度的图像在噪声的影响下得到的视差图很不平滑[7]，在实际应用中常使用基于非参数的变换即Census 算法。

Census 立体匹配算法的基本原理是建立以参考像素点为中心的窗口，以此窗口为滤波器，一一遍历待匹配的图像，利用窗口内中心像素的灰度值和邻域像素灰度值的大小关系得到二进制字符串，二进制字符串的汉明距离即为匹配代价值[8]。 虽然Census 算法在一定程度上可以缓解光照变化带来的误差[9]，但是Census 算法在代价计算的过程中仅仅利用中心像素值灰度和邻域像素值灰度进行比较，Census 存在以下局限性。

1） 未充分利用邻域像素其它信息造成信息大量丢失。 在Census 变换过程中只考虑邻域像素的灰度信息，忽略了颜色距离等信息，从而产生误匹配。

2） 参考像素点灰度值是代价值的唯一决定性因素。 根据Census 变换原理可知当参考像素点的灰度值由于噪声原因产生突变，会使得到的二进制字符串产生极大的误差， 从而得不到相应的匹配点。

除此之外在匹配代价计算时窗口大小的选择也会在一定程度上影响视差图的精度。 所选择的窗口过小会使匹配代价计算过程所需要的邻域信息过少导致精度不足，若窗口过大会使无用信息过多影响时间复杂度。 局部立体匹配算法容易受噪声的干扰，影响图像匹配的准确率。梁海波等[10]提出了改进的非参数Census 立体匹配算法通过增加局部纹理反差加权项增加匹配精度；张晶等[11]通过联合像素点间RGB 颜色绝对值和Census 变换计算匹配代价值，进一步提高了匹配的精度；黄彬等[12]通过对窗口的像素加入权重和阈值判断来加强Census 算法的抗干扰性。 宋宇等[13]将邻域像素和中心值以及平均值比较得到一个较长的二进制字符串增加匹配数量减少误匹配。

以上算法虽然提高了视差图的精度，但是大大增加了计算的时间复杂度。 本文提出一种基于十字交叉域代价聚合的Census 立体匹配算法的优化方法。 该算法充分利用了邻域像素的颜色信息和距离信息，提高匹配的准确率。

1 十字交叉域的Census 算法的优化

基于Census 算法存在的局限性，提出一种基于十字交叉域代价聚合方法[14]来优化Census 立体匹配算法局限性造成的误差。

1.1 十字交叉域原理

十字交叉域的构造方法是基于相邻像素相近颜色具有相同的视差原理。 十字交叉域的构造是以参考像素点为中心，向左右及上下4 个方向延伸直到遇到和像素颜色相差较大的像素就停止延伸,从而可以确定一个不规则图形，利用这个不规则图形对参考像素进行优化，这样充分利用参考像素的邻域信息，一定程度上改善Census 立体匹配算法过度依赖中心像素点造成的误差。 如图1 所示即为确定的邻域像素。

图1 十字交叉域的构造Fig.1 Cross-based construction

1.2 优化过程

Census 立体匹配算法是基于一个窗口先计算出一个初始代价值。 本文先根据实验确定一个大小合适的窗口计算初始代价值，进而利用十字交叉域确定的邻域像素对参考像素的初始代价值进行优化。 十字交叉域是找参考像素周围和其颜色相近的像素对参考像素进行优化，设定2 个参数L1，t1用来限制邻域像素和匹配像素之间的颜色差异和空间距离长度，如式（1）所示。

式中：Dc代表2 个像素之间的颜色差异；Ds代表2 个像素之间的空间长度；t1为2 个像素的最大颜色差异；L1为2 个像素之间最大距离差。

为了防止十字臂构成过程中臂穿过像素边缘区域，要使匹配像素的后一个像素和前一个像素的颜色差异也小于t1[15]，如式（2）所示。

为了确保构建的十字域的准确性，当十字臂长于某一个数值时， 就要求长于的部分颜色更加相近。 如式（3）所示。

当L2＜Ds（p，pl）＜L1时，Dc（p，pl）＜t2，其中t2＜t1（3）式中：L2为两像素之间的最小距离差；t2为两像素之间最小颜色差异。

进而将左右臂上的代价值都加到与参考像素垂直的竖直臂上，将竖直臂上的代价值之和再加到参考像素上，总体再除以十字臂上的像素个数就是聚合后的匹配代价值, 从而达到优化的效果。 如式（4）所示。

式中：Cl为十字域上邻域像素代价值；N 为十字域上邻域像素的个数；Ca为聚合后的代价值。

1.3 视差选择

在完成代价聚合后，视差的选取只需要在特定的范围内匹配代价最优的点即可。 在代价空间中寻找匹配代价最小点的视差值即为参考像素点的视差。

一般情况下，最常用的视差求取法是赢家通吃法WTA（winner takes all）。 其思想为在代价空间中把每一个深度值下的匹配代价列出，最小的那个视差值就为参考像素点的视差值。

1.4 Census 优化算法对比

对于Census 算法存在的不足，杨淑云等[16]为了得到更加准确的匹配视图，在初始匹配代价的基础上加入四路径代价累积。 代价累积之后的代价值即为初始代价值加上路径上相邻点当前视差下的最小代价值，以及当前路径上上一视差下和下一视差下的最小代价值。 四路径代价累积即将上下左右路径上符合条件的像素点代价进行加和，从而达到对Census 视差图的优化。

利用Census 立体匹配算法分别加入十字交叉域和四路径代价聚合对相同窗口以及相同的图像对求取视差图。 对比分析得到的视差图的精度以及时间复杂度。

2 实验结果分析

算法的实现是在Visual Studio 2019 软件平台上使用C++操作， 采用立体匹配数据集Middlebury上 的Cones，Piano，Tsukuba 立 体 图 像 对[17]对 算 法 进行测评。 实验环境为Windows10_x64 系统，Intel Core i5-7200U，主频为2.50 GHz。

由于窗口大小的选取也会对实验造成误匹配，以下采用3×3 窗口、5×5 窗口、15×15 以及9×7 窗口进行比较。经过实验验证3×3 窗口、5×5 窗口和15×15 除了匹配代价所用时间不同之外，匹配精度均没有明显的提高，但是在9×7 的窗口下视差图有所改善。 如图2 所示。 因为在视差不连续的区域长方形窗口可以减少窗口内无用点对视差代价值的影响，从而降低了误匹配。

图2 Census 算法实验结果对比Fig.2 Comparison of experimental results of Census algorithm

实验采用9×7 的窗口作为匹配代价计算窗口。 表1 为实验优化过程中各个参数的设置。

表1 实验参数设定Tab.1 Experimental parameter setting

图3 为加入代价聚合后的实验结果。 图3（c）～图3（f）分别为加入不同的代价聚合。 图3（c）,图3（e）是本文的算法，加入了十字交叉域的代价聚合。图3（d），图3（f）为加入四路径代价聚合。

由实验结果可知加入两种代价聚合后所达到的视差图精度相似，但是，在代价聚合的过程中十字交叉域代价聚合的时间复杂度很大程度上低于四路径代价聚合。 代价聚合时间如表2 所示。

除此之外，还对图像Tsukuba 运用本算法进行测试，实验结果发现：对于Tsukuba 大分辨率的图像，视差图效果不是很理想，并且代价聚合的时间复杂度很高。

3 结论

1） 根据Census 算法存在的不足， 通过加入十字交叉域代价聚合来优化Cenusu 代价值的计算，十字交叉域充分利用了邻域像素点距离信息以及颜色信息，很大程度上提高了视差图的精度。

2） 对窗口大小的选取进行了比较，实验结果表明在9×7 的窗口下Census 的匹配比5×5 规则窗口下Census 的匹配精度高。

3） 在保持匹配准确性的条件下，十字交叉域的代价聚合方法时间复杂度低于四路径代价聚合的时间复杂度，十字交叉域代价聚合的Census 算法更有利于实时性的场景。

4） 从代价聚合的实验结果发现两幅聚合后的视差图在边缘不连续精度都有待提高，对于大分辨率的图像视差图精度还有待提高。