Semi-Global Matching

Semi-Global Matching，即半全局匹配，是双目立体匹配中一项非常出色的工作。SGM由Heiko Hirschmuller于2007年在T-PAMI上发表的文章Stereo Processing by Semi-Global Matching and Mutual Information提出。Semi-Global顾名思义，是介于全局和局部之间的一种算法，既没有考虑整张图像所有的像素点，也没有只考虑像素的局部区域。

熵与互信息

SGM文章中采用的cost计算是基于熵和互信息来完成的。熵$H_I$、联合熵$H_{I_1,I_2}$和互信息$MI_{I_1,I_2}$如下公式定义。

$$
H_I = - \int_0^1P_I(i)\log P_I(i)di
$$

$$
H_{I_1,I_2} = - \int_0^1\int_0^1P_{I_1,I_2}(i_1,i_2) \log P_{I_1,I_2}(i_1,i_2)di_1di_2
$$

$$
MI_{I_1,I_2}=H_{I_1} + H_{I_2} - H_{I_1,I_2}
$$

其中$P$为值出现的概率。文章指出利用互信息的方式来表示pixel对应的cost值，对于光强等有良好的鲁棒性。

那么在图片中如何计算呢？SGM的输入是左右两张极线矫正后的灰度图，因此首先计算每一张图片的灰度直方图，以此来表示每一个灰度值出现的概率，所以单张图片中的概率函数自变量的取值是0~~255。而图片的联合概率$P_{I_1,I_2}(i,k)$则定义域(0,0)~~(255,255)，定义为：

$$
P_{I_1,I_2}(i,k) = \frac{1}{n} \Sigma_pT[(i,k)==(I_{1p},I_{2p})]
$$

其中$T$为指示函数，条件为真值为1否则为0。那么实际上在预处理的时候我们只需要将256*256的联合概率图计算好就行。另外还对这个概率图做了Gaussian平滑处理，目的是为了减少噪声对结果的影响。

代价聚合

我们已经可以算出基于MI的匹配代价，但是这只是per-pixel level的处理，很容易受到误差和噪声的影响。因此SGM还需要考虑使用邻域信息来构造loss function对其进行约束。文章使用能量公式$E(D)$来表示。

$$
E(D)=\Sigma_p(C(p,D_p)+\Sigma_{q\in N_p}P_1T[|D_p-D_q|=1]+\Sigma_{q\in N_p}P_2T[|D_p-D_q|>1])
$$

其中$P_1,P_2$都是人为设置的惩罚项常数，后两项是当前像素$p$和其邻域$N_p$内所有像素$q$之间的约束。现在问题就转化为找出一个最终的Disparity Map使得这个全局能量函数最小。

文章提出每一个点都有周围的N个（8个、16个等）方向，我们只需要将没一个方向上进行传播计算就能够让对点$p$不可导的$E(D)$利用这种方式来进行优化。

$$
L_r(p,d)=C(p,d) + \min(L_r(p-r,d), L_r(p-r,d-1)+P_1, L_r(p-r,d+1)+P_1, \min_iL_r(p-r,i)+P_2) - \min_kL_r(p-r,k)
$$

$p$点上某个邻域方向的代价聚合包含：当前点的匹配代价；min（当前邻域方向上$p-r$这个像素点的当前视差代价聚合，$p-r$点的视差差值为1的代价聚合$+P_1$，$p-r$点的视差值大于1的最小代价聚合$+P_2$）；$p-r$点的视差插值大于1的最小代价聚合，last term是防止结果过大做的处理。

而$p-r$实际上就是沿着某一个方向从前往后计算直到结束。