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计算是基于熵和互信息来完成的。熵
其中
那么在图片中如何计算呢?SGM的输入是左右两张极线矫正后的灰度图,因此首先计算每一张图片的灰度直方图,以此来表示每一个灰度值出现的概率,所以单张图片中的概率函数自变量的取值是0255。而图片的联合概率(255,255),定义为:
其中
代价聚合
我们已经可以算出基于MI的匹配代价,但是这只是per-pixel level的处理,很容易受到误差和噪声的影响。因此SGM还需要考虑使用邻域信息来构造loss function对其进行约束。文章使用能量公式
其中
文章提出每一个点都有周围的N个(8个、16个等)方向,我们只需要将没一个方向上进行传播计算就能够让对点
而
关于部分实现
在实现SGM的时候,文章中说是随机初始化几次来做初值,但是一般的做法是在Disp范围内都去计算互信息得到最初的Cost Volume,然后在对不同方向上做代价聚合。
后记
SGM是一个很强大的方法,在Deep Learning没开战以前榜单前列都是基于SGM的改进,OpenCV也实现了SGBM的双目立体匹配算法,同时也有很多基于CUDA的并行实现,让SGM算法有了更快的运行时间,是双目立体匹配中经典的算法。
Reference
Stereo Processing by Semi-Global Matching and Mutual Information