Stereo Processing by Semi-Global Matching and Mutual Information基础算法解析

本文主要是介绍Stereo Processing by Semi-Global Matching and Mutual Information基础算法解析，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

*原创文章，非作者允许，禁止一切形式的转载。

Stereo Processing by Semi-Global Matching and Mutual Information 是立体匹配中一个非常有名的算法，算法快、重建精度也不错、非常适合并行加速。

A.匹配代价计算

这部分作者在讲匹配代价计算，作者用的是信息熵，然而在实际应用中发现这一匹配代价好像效果也比较一般，使用census transform的很多。如果对信息熵想仔细了解，可以参考 @迷雾forest 这篇文章。

代价计算这一步，首先要确定disparity range（就是你觉得这张图片中场景的深度范围，比如是20）,然后对disparity range划分间隔，可以把间隔划分为256份，这里间隔是多少，就决定了视差图的分辨率。每一个深度值都可以计算出每个像素处的匹配代价，那么就得到了一个cost volume,如图1所示，宽width高height分别对应图像的宽和高，disparity range是深度空间，每一个小格子是一个匹配代价。

B.代价聚合

匹配代价是有噪音的，有时候错误的深度对应的匹配代价反而会比正确深度对应的匹配代价小。因此需要进行优化，也就是代价聚合。论文中构建的能量函数是：

$\small E(D)=\sum_{p}(C(p,D_{p})+\sum_{ q\in N_{p}}P_{1}T[|D_{p}-D_{q}|=1]+\sum_{ q\in N_{p}}P_{2}T[|D_{p}-D_{q}|>1]) \quad (1)$

第一项是匹配代价，第二项表示如果该像素的视差与周围像素相差1，则要加一个值为P1的惩罚，注意这里是累加符号，表明周围有几个视差相差1的像素，则要加几个P1，第三项表示如果该像素的视差与周围像素相差大于1，则要加一个值为P2的惩罚。也是周围有多少个像素满足就要加几个P2.。为什么要有第二项和第三项呢？这两项往往也被称为平滑项，可以这样理解，一个像素点的视差值取决于他自身的cost以及周围像素的视差情况，如果完全相信自身，那就是第一项，但是自身有误差，所以要考虑周围的像素的视差，那么就是后两项，但是要想相信周围的视差必须要加一个惩罚项，表明来自周围的信息的可靠程度没有自身cost的可靠程度高，P1的惩罚主要是为了在弯曲或者倾斜的表面进行调整（深度变化小），P2的惩罚则主要是为了处理深度不连续的情况（深度变化大）。

要最小化这个能量函数，直接求解很困难，论文中说是NPcomplete 问题，但是如果在单独的行上进行1D的求解，求解将会非常的快，所以作者把这个问题分成了在多个方向上进行1D的求解，把一个二维问题分解成多个一维求解问题，注意这里只是一种近似，因此最终的结果并不一定是最优的。下面先说1D方向上的代价聚合：

$\large L_{r}^{'}(p,d)}=C(p,d)+min(L_{r}^{'}(p-r,d),L_{r}^{'}(p-r,d-1)+P1,L_{r}^{'}(p- r,d+1)+P1,min_{i}}L_{r}^{'}(p-r,i)+P2) \qquad \qquad (2)$

第一项是匹配代价，后面的项是传播项。公式的意思是说当前像素某个深度对应的聚合的代价=自己本身的代价（就是census计算的代价）+传播过来的代价，传播过来的代价根据深度不同分为四类：a,等于当前深度 b,比当前深度少1 c,比当前深度大1 d,其他深度值，会在这四类深度中选择一个对应的代价最小的深度，如果是a类深度，就直接是对应代价，如果是b，c类深度，需要在对应代价的基础上加上P1，如果是d类深度，需要在对应代价的基础上加P2。如下图：注意这里有个简化是d类深度加P2，只需找到d类深度的最小代价加P2即可

图2是一个方向上的某个像素代价聚合的过程，假设有10个深度空间，d=1,2...10,分别对应10个匹配代价，该匹配代价就是第一步计算的匹配代价聚合后的结果，当前像素的匹配代价就是第一步直接计算出的匹配代价，然后每个匹配代价都按照公式（2）进行代价更新，更新后的匹配代价作为继续向下一个像素传播，重复该过程。

要求解(1)式,可以把它近似看成在多个1D方向上的聚合，就可以近似求解这个问题了。要注意的是：

代价聚合的方向一般要不少于8个，每个像素最终的代价是所有方向相加的结果。
随着代价聚合的进行，匹配代价会很大造成具体实现时的数据溢出，一般会在代价聚合的时候减去当前像素所有匹配代价中的最小值，对于这个例子来说就是减去11.这个操作对应sgm论文中的公式（13）。
p1,p2的选取可以根据具体的应用进行调整，一般p1是一个定值，p2可以随着图像梯度变化而变化，往往要保证p2>=p1
时间复杂度是o(whd)