Semi-GlobalMatching（SGM）算法原⽂理解
半全局⽴体匹配算法基于⼀种逐像素匹配的⽅法，该⽅法使⽤互信息来评价匹配代价，并通过组合很多⼀维的约束来近似⼀个全局的⼆维平滑约束。本⽅法分成下⾯⼏个步骤，其中有⼀些并不是必须的。 丙酮回收
输⼊的左右图像必须已经知道对极⼏何模型，但是不⼀定是校正过的，因为有些图像是难以校正的，⽐如推扫式图像。要计算参考图（base image）某点P的匹配代价，需要⽤到其灰度为I bp，及在待匹配图（match image）的疑似匹配点q，其灰 度为I mq，p和q之间有极线⽅程q=ebm(p,d)，d是极线的参数。如果图像已经被校正了，那么待匹配图在参考图的右边，且d 代表视差。 ⼀个重要的问题是⽤于匹配的区域的⼤⼩和形状，区域越⼤，鲁棒性越好，但是⼤了以后会导致物体的边界模糊。这⾥不使⽤P邻域内的视差是连续的这⼀假设，也就是说，只有I bp和I mq这两个灰度值被⽤来计算点p匹配代价，其他的点不考虑。
缺陷者捧出的花束
⽂章介绍⼀种逐像素匹配代价计算的⽅法是Brichfield and Tomasi提出的基于采样的⽅法《Depth Discontinuities by Pixel-to-Pixel Stereo》，该⽅法在OpenCV SGBM算法中使⽤。但是这⾥，⽂章使⽤了新的⽅法，即基于互信息的匹配代价，该⽅法对光照不敏感。下⾯介绍互信息。
互信息M的定义式，互信息是基于熵来计算的，下⾯的三项分别是图1的熵，图2的熵，以及图12的联合熵，紧接着给出熵和联合熵的定义：
崔月犁
什么是熵？参考@迷雾forest：先说说熵，熵是⽤来表征随机变量的不确定性（可以理解为变量的信息量），不确定性越强那么熵的值越⼤（最⼤为1），那么图像的熵其实就代表图像的信息量。互信息度量的是两个随机变量之间的相关性，相关性越⼤，那么互信息就越⼤。可以想想看，两幅图像如果
匹配程度⾮常⾼，说明这两幅图像相关性⼤还是⼩？显然是⼤，知道⼀幅图像，另外⼀幅图像马上就知道了，相关性已经不能再⼤了反之，如果两幅图像配准程度很低，那么两幅图像的互信息就会⾮常⼩。所以，⽴体匹配的⽬的当然就是互信息最⼤化。这就是为什么使⽤互信息的原因。
此时，为了计算互信息，就要先计算熵，⽽根据上的定义式，为了计算H I和H I1I2，⾸先需要知道P I和P I1I2是啥，其中P I代表某个点i的概率分布，也就是灰度直⽅图中灰度为i的点出现的概率。P I1I2是⼆维概率分布，⼆维概率分布是什么意思呢，⽐如现在左图是100*100，则⼀共有10000个像素点，对于左图中的每⼀个点p，它在左图的灰度值为i，它在右图的对应点的灰度值为j，它们构成⼀个点对（i,j），此时点对（i，j）对应的计数加1；然后遍历其他所有点，如果某个点对出现过，就把该点对对应的计数值加1，最后把所有点对的计数值除以10000，就得到某个点对（i,j）的概率。不难理解，因为i和j的范围都是0-255，所以这个⼆维概率分布图P I1I2的尺⼨为256*256。
清溪玉芽
现在知道了P I和P I1I2，就要返回去计算H I和H I1I2。对于H I1I2，作者根据Kim等⼈的成果，直接⽤泰勒展开式，把原来的联合熵公式转换为下⾯这个：
也就是各像素点对应的h值之和的形式，那么h I1I2⼜是什么呢？h I1I2是根据P I1I2来计算的，其公式是：
也就是说，得到⼆维概率分布图（其尺⼨永远是256*256），然后与⾼斯核进⾏卷积，然后求log，然后再卷积，就得到这个h I1I2，其实它也是个256*256的图，这样就可以建⼀个256*256的表，然后H I1I2的解释就是，对于逐个点p，其左图像中灰度值为I1P，右图像灰度值为I2p，则其对应的h I1I2可以直接查表得出，然后整个图的H I1I2就是把所有点p的h I1I2加起来。
这⾥列出由两个图得到h I1I2的过程，这⾥有⼀个warp，它的意思是，在求⼆维概率分布之前，要根据⼀个初始的视差图，对待匹配图像进⾏修正，修正后，左图中某⼀点⼤概率能有⼀个正确的对应点，则此时两个点的灰度值基本相同，这样就使得（5,5）（10,10）这样的点对占⼤多数，所以P的图像基本是⼀个45度的直线。但是这个作为参考的视差图是粗糙的，它是怎么得到的作者没有提到，只知道遮挡点的视差都被设为0，只有⾮遮挡点才有视差，⽤这样粗糙的视差图作为参考去对待匹配图像做修正，就可能使对应点的视差不⼀致，因此就会出现不在45°线上的情况，这就需要⾼斯模糊来去躁了。⾄此，就讨论完了H I1I2的计算。还有HI1和HI2。
对于H I，其计算⽅法本来跟H I1I2是不同的。但是这⾥有个问题，如果考虑遮挡的问题，那么有些点根本没有可以匹配的点，那么这些点不应该被考虑，为此，我们⼜⼀次想到联合熵，联合熵是基于联合概率分布的，其基于的点都可以保证是匹配点，因此，这⾥考虑对于H I的计算，也使⽤H I1I2即联合熵的求法。公式如下：
这⾥h I的计算就跟上⾯很相似了，需要注意的是计算P的时候不要把遮挡点统计进来。
最后，互信息MI的最终定义就是：
相应的，基于互信息的某点p的匹配代价CMI就是：
这就是说，计算某⼀点的匹配代价，就是先根据极线⽅程求出在右图像中的灰度，根据这两个点的灰度构成的灰度值对直接在互信息图M 中查，然后取负。
这⾥还有⼀个问题，求互信息之前要对待匹配图像进⾏校正，根据Kim等，采⽤⼀个迭代的过程，⼀开始采⽤⼀个随机的视差图来进⾏第⼀次的互信息计算，然后根据这个互信息就可以得到新的视差图，再根据这个视差图再求互信息，如此迭代，⼀般也不要太多次数，⽐如3次可以。为什么可以这么“随意”，因为像素点很多，所以即使随机⽣成的视差图有错误，体现在概率分布上也没有特别⼤的影响。
最后就是分层互信息。既然⼀个粗糙的初始视差图也可以得到较精准的概率分布，那么在前⾯的迭代中可以使⽤⼀个基于相关的快速⽅法，并且只在最后⼀次迭代时使⽤更精准和耗时的⽅法。下⾯就介绍这种⽅法，也就是分层互信息法（HMI）。
⽤HMI来计算匹配代价，该⽅法递归的使⽤降采样过的参考图和待匹配图，采样率是1/2，然后得到的视差图的长宽也是上⼀幅视差图的⼀半（注意，因为我们只对图像降采样，⽽图像上的点仍然是可能占满0-255空间的，因此概率分布图仍然是256*256）。那么如果迭代四次，第⼀次使⽤的是1/16的图，
下⼀次是1/8，再1/4和1/2，最后⼀次是1，这就得到较⾼精度的匹配代价。单次迭代的时间复杂度是O(WHD)，所以总的运算时间是 ，可见复杂度并不是很⾼，之⽐BT算法多了14%。注意低⼀层的图只作为下⼀层的输⼊，⽽不作为最后结果的输⼊。上⾯的公式中为啥要乘3，根据@迷雾forest，乘以3的原因是随机⽣成的视差图⼗分不靠谱，需要反复迭代3次才能得到同样分辨率下的靠谱视差图，然后再参与后续⾼分辨率的计算。
2.2 代价聚合aeviou输入法
由2.1已经得到基于互信息的匹配代价，但是这个逐像素的匹配代价容易受到误匹配和噪声点的影响，因此这⾥还要考虑使⽤某点的邻域视差数据来构造惩罚函数以增加平滑性约束。也就是说，把代价聚合⾥⾯加⼊平滑性约束的考虑，也就是设计⼀个全局的能量函数E(D)，⽤它来综合匹配代价和平滑性约束。能量函数的定义式如下：
（注意这⾥惩罚值的意义，惩罚就代表着不想选这种情况，如果有⼀个视差图它的惩罚值⽐另⼀幅⼤，那么就不选这个，也就是通过惩罚筛掉了我们不想要的情况，这个弯要转过来）
式中第⼀项是基于互信息的代价计算项；后两项是当前像素p和其邻域N p内所有像素q之间的约束，如果p和q的视差只差1，那么惩罚
P1，否则惩罚系数P2，P2要⼤于P1。如果当前点和邻域点的差值⽐较⼩，就选择⼀个⼩的惩罚值，这么做保证可以对斜⾯和曲⾯有⼀定的适应性（也就是说不是完全要筛掉它们，⽽是还有容忍）。
现在问题就变成到⼀个视差图，它能使这个全局的能量函数最⼩。关于求这个视差图的⽅法，@迷雾forest⽂章说的讲⽐较清楚：这个时候问题来了，这个E对p是不可导的，这意味着我们常看到的梯度下降，⽜顿⾼斯等等算法在这⾥都不适⽤，作者于是采⽤了动态规划来解决这⼀问题。简单地说，p的代价想要最⼩，那么前提必须是邻域内的点q的代价最⼩，q想要代价最⼩，那么必须保证q的领域点m的代价最⼩，如此传递下去。怎么利⽤动态规划来求解E，其实这个求解问题是NP完全问题，想在2D图像上直接利⽤动态规划求解是不可能的，只有沿着每⼀⾏或者每⼀列求解才能够满⾜多项式时间，但是这⾥问题来了，如果我们只沿着每⼀⾏求解，那么⾏间的约束完全考虑不
到，q是p的领域的点其实这个时候被弱化到了q是p的左侧点或者右侧点，这样的求优效果肯定很差。于是，⼤招来了！！我们索性不要只沿着横或者纵来进⾏优化，⽽是沿着⼀圈8个或者16个⽅向进⾏
优化。
什么叫“沿着⼀圈8个或者16个⽅向进⾏优化”呢，结合下⾯的执⾏步骤详细解释。现在可以采⽤⼀种新的匹配代价聚合⽅法，它使⽤某点p上邻域内所有⽅向上的代价构成⼀维的DP问题。S(p,d)代表某⼀点（像素点名p，视差值d）的代价聚合值，它的求法是
，所以Lr是什么？以p为中⼼，可以到16个（或8个，下同）邻域⽅向，然后在每个邻域⽅向上有⼀个指向p的⽮量，⽽r表⽰16个⽮量中的某⼀个。因此Lr就是代表当前⽮量路径r上的代价聚合值。所以，S（p,d）就是把16个代价聚合值相加，⽽这16个⼜都是各⾃路径上的最⼩代价。所以求出来的S(p,d)就是p点的最⼩代价。注意r是⼀条路，它只能是这个⽅向，但是长度可以延长。也就是说，16个⽅向分别算到底。那么下⾯就是考虑，Lr(p,d)到底如何计算呢。且看下式：
P点上某个邻域⽅向的代价聚合值分为三项，第⼀是当前点的匹配代价，就是前⾯的C MI；第⼆项是
min（当前邻域⽅向上p-r这个像素点的当前视差代价聚合值，p-r点的视差差值为1的代价聚合值 + P1，p-r点的视差插值⼤于1的最⼩代价聚合值 + P2）；最后⼀项是p-r点的视差插值⼤于1的最⼩代价聚合值，最后⼀项是为了防⽌计算结果太⼤，做的统⼀的调整。
关于这个p-r，它的意义不是很好理解，我的理解的是，因为每次要沿着⼀个⽮量⽅向算到底，那么p-r就是某个⽮量上距离p为⼀个单位、两个单位等等点，直到算完（addsthe lowest cost of the previous pixel p-r ofthe path）。
把各个⽅向上的Lr都求和得到S(p,d)，作者建议⽅向数最好⽤16，⾄少为8，这些⽅向最好是⽔平、垂直或位于某对⾓线上，如果不是，那就多做⼀步，调整为这三种。
农村妇女肥大
最后考虑⼀下计算量和实现⽅法。作者推荐的是先计算所有点的C(p,d)，然后把值规范化到0-211的取值范围内。所有的匹配代价都存在C[]数组⾥⾯，该数组⼤⼩W*H*D，然后⽤⼀个与C同样⼤⼩的数组S[]来保存代价聚合值。然后对每个点b，计算所有邻域⽮量⽅向上的代价聚合值，计算过程中体现动态规划中记忆化搜索的思想。
2.5 视差求精
2.6 ⼤尺⼨图⽚的处理
SGM算法需要保存临时变量包括每个点的匹配代价、聚合代价、融合前的视差图等等，因此中间步骤需要的存储空间⾮常⼤，很可能导致空间占满的情况。为此，提出⼀种⽅法，把基准图分成⽚，以⽚的形式参与到2.1-2.3步的运算，然后再组合起来进⾏2.4的运算。划分⽚的时候，它们需要是重叠的，也就是每个⽚取⼤⼀点。这种⽅法对于⼤尺⼨的照⽚⾮常适⽤。
2.7 视差图融合
注意这⾥不是左右视差图的融合，⽽是针对不同视⾓获取到的视差图进⾏融合。我的应⽤只⽤了⼀个视⾓，所以这⾥没怎么看。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议