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

AD

  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(*)表示像素点*处的灰度值， ⊕为比特位的逐位连接运算。 ∈（）运算则由下面公式定义：

  通过上文的公式可以得到了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]的自然指数函数：

  其中c是代价值，λ是控制参数，当c和λ都为正值时，这个函数的值区间在[0,1]的。并且c即代价值越大，函数值越大。因此可以通过该函数将任意代价值归一化到[0,1]的范围。
  最终，AD-Census的代价计算公式为：

  两个结果进行归一化后，最终的结果范围为[0,2]。
    
 

下一篇：双目立体匹配之代价聚合