最近在做双目视差估计算法，在OpenCV里有一些算法，其中半全局块匹配（Semi-Global Block Matching，SGBM）算法具有视差效果好速度快的特点，因此常常被广泛应用。本文主要讨论的就是SGBM算法。OpenCV的SGBM算法主要参考了《Stereo Processing by Semiglobal Matching and Mutual Information》这篇论文。

1. 计算每个像素点的代价

原论文使用的方法是利用互信息熵，而OpenCV使用的是Birchfield和Tomasi的方法（参照《Depth Discontinuities by Pixel-to-Pixel Stereo》）。这里我们分别介绍一下。

1.1 利用互信息熵

所谓的熵，是用来表示随机变量的不确定性，熵的值越大，信息的不确定性也越大。熵H和互信息MI的定义分别如下：

熵H的定义 互信息MI（Mutual Information）的定义

其中，P_I代表某个点i的概率分布，也就是灰度直方图为i的点出现的概率；对应地，P_I1,I2就是两个图对应点i₁和i₂的联合概率分布，也就是：

Kim等人将上式做了一个改进：利用泰勒展开把H_I1,I2的计算转化为求和问题（参见论文《Visual Correspondence Using Energy Minimization and Mutual Information》）。

其中圈中带叉表示卷积运算，g(i,k)为高斯卷积核。

相应地，边缘熵以及边缘概率的计算如下：

这样的话，互信息的定义为：

MI匹配代价C_MI为：

其中q是点p在视差为d的情况下的对应校正点。

原作者使用分层互信息（HMI）进行计算，每一层尺寸减少一半。单次计算的时间复杂度是O(WHD)，即width×height×disparity range，所以上次迭代将会是当前迭代速度的1/8。

这里1/16³要乘3的原因是小尺寸的随机视差图不靠谱，需要迭代3次。我们可以看到，相比于后文的BT方法仅仅慢了14%

1.2 Birchfield和Tomasi的方法（简称BT方法）

对于一个匹配序列M，其代价函数γ(M)表示匹配结果不准确的程度，其值越小越好。

其中，κ_occ表示未匹配的惩罚项(constant occlusion penalty)，κ_r表示匹配的奖励项，N_occ和N_r分别表示未匹配和匹配的点数。

2. 损失聚合

我们为视差设置一个能量函数E(D)

其中P₁和P₂分别表示视差差值为1和视差差值大于1的惩罚系数，一般P₁<P₂。添加两个正则化项一是为了保持视差图平滑，二是为了保持边缘。我们要做的是找到D使得能量函数E(D)最小，但是不幸的是，在二维图像的这个问题是一个NP-完全问题。为了解决这个问题，原文选择沿着一圈8个或者16个方向进行优化。

代价聚合公式（初始为C(p,d)） 图片的代价聚合是各个像素点代价聚合之和

选取使代价聚合最小的视差值min_dS[e_mb(q,d),d]即可。

3. OpenCV相关函数的使用

我们看一下stereoSGBM类的参数。

static Ptr<StereoSGBM> cv::StereoSGBM::create   (int    minDisparity = 0,
int     numDisparities = 16,
int     blockSize = 3,
int     P1 = 0,
int     P2 = 0,
int     disp12MaxDiff = 0,
int     preFilterCap = 0,
int     uniquenessRatio = 0,
int     speckleWindowSize = 0,
int     speckleRange = 0,
int     mode = StereoSGBM::MODE_SGBM 
)       

• minDisparity：最小的视差值。
• numDisparity：视差范围，即最大视差值和最小视差值之差，必须是16的倍数。
• blockSize：匹配块大小（SADWindowSize），必须是大于等于1的奇数，一般为3~11 。
• P1，P2：惩罚系数，一般：P1=8*通道数*SADWindowSize*SADWindowSize，P2=4*P1
• disp12MaxDiff ：左右视差图的最大容许差异（超过将被清零），默认为 -1，即不执行左右视差检查。
• preFilterCap：预滤波图像像素的截断值。该算法首先计算每个像素的x导数，并通过[-preFilterCap，preFilterCap]间隔剪切其值。结果值被传递给Birchfield-Tomasi像素成本函数。
• uniquenessRatio：视差唯一性百分比， 视差窗口范围内最低代价是次低代价的(1 + uniquenessRatio/100)倍时，最低代价对应的视差值才是该像素点的视差，否则该像素点的视差为 0，通常为5~15.
• speckleRange：视差变化阈值。
• mode：模式

简单地试了一下：

#include "stdafx.h"

#include <opencv2\core\core.hpp>
#include <opencv2\highgui\highgui.hpp>
#include <opencv2\imgproc\imgproc.hpp>
#include <opencv2\calib3d\calib3d.hpp>
#include <iostream>

using namespace cv;
int main(int argc, char** argv) {

    //读入图像。
    Mat left = cv::imread("left.png");
    Mat right = cv::imread("right.png");
    if (left.empty() || right.empty()) {
        std::cout << "could not load image...\n";
        return -1;
    }

    //图像转灰度
    cv::cvtColor(left, left, CV_BGR2GRAY);
    cv::cvtColor(right, right, CV_BGR2GRAY);

    //设置参数
    int numberOfDisparities = 48, SADWindowSize = 11;
    int uniquenessRatio = 15, speckleWindowSize = 50, speckleRange = 32;
    cv::Ptr<cv::StereoSGBM> sgbm = cv::StereoSGBM::create(0, numberOfDisparities, SADWindowSize);
    int cn = left.channels();
    sgbm->setP1(8 * cn * SADWindowSize * SADWindowSize);
    sgbm->setP2(32 * cn * SADWindowSize * SADWindowSize);
    sgbm->setPreFilterCap(63);
    sgbm->setUniquenessRatio(uniquenessRatio);
    sgbm->setSpeckleWindowSize(speckleWindowSize);
    sgbm->setSpeckleRange(speckleRange);
    sgbm->setDisp12MaxDiff(1);

    //计算并显示视差
    Mat disp;
    sgbm->compute(left, right, disp);
    disp.convertTo(disp, CV_8U, 255 / (numberOfDisparities*16.));   //将16位符号整形的视差矩阵转换为8位无符号整形矩阵
    cv::imshow("disparity", disp);
    cv::waitKey();

    return 0;
}

左视图 视差结果

参考资料

• Heiko Hirschmuller “Stereo Processing by Semiglobal
  Matching and Mutual Information ”[M]．IEEE，2005
• S. Birchfield and C. Tomasi, “Depth Discontinuities by Pixel-toPixel Stereo,” Proc. Sixth IEEE Int’l Conf. Computer Vision, pp. 1073-
  1080, Jan. 1998.
• cv::StereoSGBM Class Reference
• OpenCV学习笔记（18）双目测距与三维重建的OpenCV（三）立体匹配与视差计算
• Stereo Matching文献笔记之（九）：经典算法Semi-Global Matching（SGM）之神奇的HMI代价计算~
• Stereo Matching文献笔记之（十）：经典算法Semi-Global Matching（SGM）之碉堡的动态规划~
• Semi-Global Matching（SGM）算法原文理解