双目立体匹配之匹配代价计算

作者：秃头小苏

2022 年 7 月 10 日
本文字数：1898 字
阅读完需：约 6 分钟

之前谈到过双目立体匹配的步骤，主要分为四步（半全局方法）：匹配代价计算、代价聚合、视差计算、视差优化。匹配代价计算是双目立体匹配的第一步，其有很多实现的方法，现举其中的几种方法，旨在理解匹配代价的计算过程。

AD 算法可以说是匹配代价计算中最简单的算法之一，其主要思想是不断比较左右相机中两点的灰度值大小，首先固定左相机中的一点，然后遍历右相机中的点，不断比较它们之前的灰度之差，灰度之差即为匹配代价。其数学公式为：

其中，p,q 分别为左右图像中的两点， IL()表示左图像中的灰度值，同理 IR()表示右图像中的灰度值。上式为灰度图像的匹配代价；若为彩色图像，则 AD 算法计算代价的公式为：

即左右视图像素点的三个颜色分量之差的绝对值取平均。 AD 算法是基于单个像素点计算的匹配代价，受光照不均、图像噪声影响较大，但对纹理丰富区域有较好的匹配效果。

SAD

SAD（Sum of absolute differences）也是匹配代价计算中基础的算法，其基本思想是：差的绝对值之和。相对于 AD 算法计算的代价是通过两点之间的灰度值进行的，而 SAD 的匹配代价则是通过某点及其一定范围内的像素点决定的，其基本流程如下：首先输入两幅图像，一幅 Left-Image，一幅 Right-Image。其次对左图，依次扫描，选定一个锚点：（1）构造一个小窗口,类似于卷积核；（2）用窗口覆盖左边的图像,选择出窗口覆盖区域内的所有像素点；（3）同样用窗口覆盖右边的图像并选择出覆盖区域的像素点；（4）左边覆盖区域减去右边覆盖区域，并求出所有像素点灰度差的绝对值之和；（5）移动右边图像的窗口，重复（3）-（4）的处理（这里有个搜索范围,超过这个范围跳出）；（6）找到这个范围内 SAD 值最小的窗口,即找到了左图锚点的最佳匹配的像素块。其中，SAD 的匹配代价计算公式如下：

其中， Np、Nq 分别表示 p、q 周围的像素点。

Cencus

Census 变换法也被广泛用于匹配代价计算。它能够较好地检测出图像中的局部结构特征，如边缘、角点特征等。其基本的思想如下：在图像区域定义一个矩形窗口，用这个矩形窗口遍历整幅图像。选取中心像素作为参考像素，将矩形窗口中每个像素的灰度值与参考像素的灰度值进行比较，灰度值小于或等于参考值的像素标记为 0，大于参考值的像素标记为 1，最后再将它们按位连接，得到变换后的结果，变换后的结果是由 0 和 1 组成的二进制码流。 Cencus 变换过程可通过如下公式表达：

其中 p 是窗口中心像素，q 是窗口中心像素以外的其他像素，Np 表示中心像素 p 的邻域。I(*)表示像素点*处的灰度值， $\otimes$ 为比特位的逐位连接运算。 $ξ ()$ 运算则由下面公式定义：

通过上文的公式可以得到了 Cencus 变换的一串二进制，基于 Census 变换的匹配代价计算方法是计算左右影像对应的两个像素的 Census 变换值的汉明（Hamming）距离，即匹配代价为：

其中，T( p)为左图产生的二进制串，T(q)为右图产生的二进制串。Hamming 距离即两个比特串的对应位不相同的数量，计算方法为将两个比特串进行亦或运算，再统计异或运算结果中的比特位中为 1 的个数。我们可以通过下图辅助理解 Cencus 匹配代价的计算方法，先分别计算出左图和右图中一定范围的 Cencus 变换的二进制串结果（上文已经介绍），然后对得到的两串二进制进行异或操作，得到结果中 1 的个数即为所求匹配代价（下图结果为 2）。

我们前面说到，AD 和 SAD 算法都对光照较为敏感，这里的 Cencus 变换则对图片的明暗变化并不敏感，因为 Cencus 算法是比较的相对灰度关系，所以即使左右影像亮度不一致，也能得到较好的匹配效果。但是 Cencus 变换对重复区域的匹配效果不好，例如下图的两个领域窗口中灰度完全不同，但 Cencus 变换得到的代价完全相同。

AD-Cencus

前文已经介绍了 AD 算法和 Cencus 变换，显而易见，AD-Cencus 是将 AD 和 Census 结合,这样就能对两种方式起到一个互补作用。Cencus 算法对重复纹理的效果不好，而 AD 算法是基于单像素的，可以在一定程度上缓解 Cencus 算法对重复纹理处理棘手的问题。但是将两种算法结合存在算法结果尺度不一致的问题，需要进行归一化处理。，AD 的结果是亮度差，范围是[0,255]，而 Census 是比特串对应位值不相同的个数，范围为[0,N]（N 等于比特串的位数）。因此，需要通过归一化，将两者的结果归一化到相同的范围区间，AD-Census 所采用的方法是一个值区间在[0,1]的自然指数函数：