SGM

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计算是基于熵和互信息来完成的。熵HI、联合熵HI1,I2和互信息MII1,I2如下公式定义。

HI=01PI(i)logPI(i)di

HI1,I2=0101PI1,I2(i1,i2)logPI1,I2(i1,i2)di1di2

MII1,I2=HI1+HI2HI1,I2

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

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

PI1,I2(i,k)=1nΣpT[(i,k)==(I1p,I2p)]

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

代价聚合

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

E(D)=Σp(C(p,Dp)+ΣqNpP1T[|DpDq|=1]+ΣqNpP2T[|DpDq|>1])

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

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

点上某个邻域方向的代价聚合包含:当前点的匹配代价;min(当前邻域方向上这个像素点的当前视差代价聚合,点的视差差值为1的代价聚合点的视差值大于1的最小代价聚合);点的视差插值大于1的最小代价聚合,last term是防止结果过大做的处理。

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

关于部分实现

在实现SGM的时候,文章中说是随机初始化几次来做初值,但是一般的做法是在Disp范围内都去计算互信息得到最初的Cost Volume,然后在对不同方向上做代价聚合。

后记

SGM是一个很强大的方法,在Deep Learning没开战以前榜单前列都是基于SGM的改进,OpenCV也实现了SGBM的双目立体匹配算法,同时也有很多基于CUDA的并行实现,让SGM算法有了更快的运行时间,是双目立体匹配中经典的算法。

Reference

Stereo Processing by Semi-Global Matching and Mutual Information

CSDN-王嗣钧 blog

CSDN-Witnesses blog


SGM
https://alschain.com/2022/06/28/SGM/
作者
Alschain
发布于
2022年6月28日
许可协议