本文是自己的一篇学习笔记，记录自己学习代价匹配过程中的问题，在此分享，转载请附原文链接
在之前双目立体匹配步骤中已经简单介绍过代价聚合了，直白的说，其主要目的就是让匹配代价计算的效果更好。
之前也介绍过立体匹配的第一步——匹配代价计算匹配代价计算，我在文中介绍了相关的匹配代价计算方法，如AD、AD-cencus等等。通过这些方法我们可以得到一个代价矩阵C(DSI),矩阵C中存储了每个像素在视差范围内每个视差下的匹配代价值。
这时候得到的代价矩阵C能不能直接拿来用呢？能，当然能，但是效果嘛就比较差了，这时候我们要对之前的矩阵C进行改进，这样的对其进行改进的方法就是代价聚合了。首先我们先直观的来看一下代价聚合前后得到的视差图的差距：
图1 代价聚合前后视差示意图
可以看出，代价聚合前后的效果差距还是很大的。肯定很多人问为什么效果差别这么大呢？这是因为我们第一步代价计算只考虑了局部的相关性，对噪声非常敏感，往往会导致正确的同名点对应的视差代价不是最小的，也就无法找出正确的同名点。可能又有人问了，那代价聚合就可以弥补上述的缺陷嘛？别急，下面就来具体讲述一下代价聚合的过程。
首先需要明确的是，只有局部匹配算法和半全局匹配算法（SGM）需要进行代价聚合，全局匹配算法是不需要的。下面以半全局匹配算法（SGM）为例进行介绍。为了获得较好的匹配效果，SGM算法依旧采用全局立体匹配算法的思路，即全局能量最优化策略，简单来说就是寻找每个像素的最优视差使得整张影像的全局能量函数最小。全局能量函数的定义如公式1所示：
其中 Edata(d)为数据项，是反应视差图对应的总体匹配代价的测度；Esmooth(d) 是平滑项，为了让视差图满足某些条件假设的约束，如场景表面的连续性假设，平滑项会对相邻像素视差变化超过一定像素的情况进行惩罚（惩罚一般就是加大能量值）。
上文红字标注的连续性在文章双目立体匹配步骤第二节已经提到，不再过多赘述。
对于公式1，我们的目标是要最小化该能量函数，但能量函数最小化是一个二维最优问题，是一个NP完全问题（何为NP完全问题大家可以查阅资料，反正我没看懂，有兴趣可以看看，我认为就是这个问题解决比较麻烦，所以就换一种思路来解决吧！！！）。enmm,姑且这么说，NP完全问题太难了，所以SGM算法采用基于类似于扫描线或者叫单方向动态规划的方法，使用一维路径聚合的方式来近似二维最优，相比其他解决方法效率更高，效果相当。
接下来SGM提出更具体话的能量函数表达式，如公式二所示：
其中，C为匹配代价，公式的第一项是数据项，表示当视差图为D时，所有像素的匹配代价的累加，第二项和第三项是平滑项，表示对像素p的Np邻域内的所有像素q进行惩罚。其中第二项惩罚力度较小（ P1较小），表示对相邻像素视差变化很小的情况（1个像素）进行惩罚；第三项惩罚力度较大（ P2>P1），表示对相邻像素视差变化很大（大于1个像素）的情况进行惩罚。较小的惩罚项可以让算法能够适应视差变化小的情形，如倾斜的平面或者连续的曲面，较大的惩罚项可以让算法正确处理视差非连续情况，但是由于影像的亮度边缘位置（也就是梯度较大的位置）是前景背景交界的可能性较大，这些位置的像素邻域内往往不是视差连续的，相差较大，为了保护真实场景中的视差非连续情况，P2往往是根据相邻像素的灰度差来动态调整，如公式3所示：
P2' 为 P2的初始值，一般设置为远大于 的数。这个公式的含义是：如果像素和它的邻域像素亮度差很大，那么该像素很可能是位于视差非连续区域，则一定程度上允许其和邻域像素的视差差值超过1个像素，那么对于超过1个像素的惩罚力度就适当减小一点。其中I表示灰度值。
但是实际上，公式2也是一个NP完全问题，enmm,比较难…于是呢，SGM算法提出了代价聚合的想法，就是把像素所有视差下的匹配代价进行像素周围所有路径的一维聚合，得到各个路径下的路径代价，然后将所有路径代价相加得到该像素聚合后的匹配代价值。像素p沿着某条路径r的路径代价计算方法如公式4所示：
首先要说明的是，公式4和公式2表达的含义其实基本一致。第一项为匹配代价值C，属于数据项；第二项是平滑项，表示累加到路径代价上的值取不做惩罚、做 P1惩罚和做 P2惩罚三种情况中代价最小的值；第三项是为了保证新的路径代价值Lr不超过一定数值上限，即
现对公式4做相关解释。首先来整体分析一下这个公式，即一个像素在视差为d时的聚合代价等于其初始的代价值C加上四个运算值的最小值再减去另一个最小值（这个最小值不需额外计算，在前面的四个计算中，这个最小值也没有什么特殊的含义，只是为了让L的值不超过一定上限，如公式5所示）。
其次，公式中的p代表像素，r代表路径，左右路径的情形下， p − r就是p左侧（从左到右聚合）或者右侧（从右到左聚合）的相邻像素，他们行号相等，列号相差1。L是聚合代价值，C是初始代价值。
是不是对于公式中的第二项还是有点懵，下面来对第二项进行相关解释如下：
其实讲到这里代价聚合的核心已经讲完了，剩下的就是根据图片利用上述公式来计算就可以了。这就好了！！！？其实理论上是这样的，但是你是不是和我当初一样充满了疑问，不知道具体是怎么实现这个过程的，对于公式中的表述也不能很好的理解，下面讲讲我学习过程中遇到的问题以及我的思考（PS:可能不是很正确，仅代表我个人的理解，如有错误，希望大佬们指出）。
其一：关于公式中的p-r，我的理解是：这个算法其实需要不断的迭代进行求解，每次都需要沿着一个路径计算到底，那么p-r就是某条路径上距离p为一个单位的点，p-2r就是某条路径上距离p为两个单位的点，依此内推。
其三：关于公式中第二项中 minLr(p-r,i)的i值，我的理解是它应该满足|i-d|>1,即相关像素的视差不是第二项中前三种情况，也即像素的视差>1。其实我想理论上也是这样的，即i要满足|i-d|>1，但是对于第二项的式子，有没有这个限制其实是不影响结果的，因为若i不满足|i-d|>1，即|i-d|<=1，那么第二项式子中的四部分最小值一定不会在 中取得，肯定在前三部分取（ P2>P1），这一项将无意义，故在此式中可不对i的范围做讨论。
其三：我之前一直不明白这个聚合的具体怎么进行的，看了很多文章后有了自己的理解（有误恳请指出），现通过一些图示进行解释。比如，我们现在需要计算p点的聚合代价值，那么我们在计算之前肯定是知道p的各个视差下的初始匹配代价（就存储在立体匹配之匹配代价计算求出来的矩阵C里面嘛），所有对于p来说，要求p的路径聚合代价，那么根据公式4，其第一部分C(p,d)肯定是已知的。这里理解了的话，那么其实对于图像中的任意一个像素，都可以在初始代价矩阵C中找到各个视差下的初始匹配代价，也就是对于公式4来说，第一部分的C(p,d)都是已知的。再来看公式4的第二项，不难看出，这一项主要是要寻找前一个像素的路径聚合代价。前一个像素的路径代价？？？我们根本不知道啊，其实这里就是一个不断递归的过程，不断寻找前一个像素的路径代价直到一个特定的像素为止。这里特定的像素可以理解为我设置一个递归次数，递归次数到了，此时递归到了某个像素p,那么这个p像素就是所谓的特定的像素。有人要问了，p像素我也不知道它的路径聚合代价啊，对了，这时我们就要对其进行初始化，让p像素的聚合代价值L等于它的初始代价值C。这时我们有了第一个像素路径聚合代价，那么我们就可以一步步的算出其它像素的路径聚合代价，当然目标像素的路径聚合代价也可以算出。下面用一张图表示一个方向上某个像素的代价聚合过程。
图2 一个方向上某个像素的代价聚合过程
上图图2表示的是某个方向上的一个像素的代价聚合过程，假设视差的范围只有10个，那么这个像素在各个视差下的初始匹配代价是已知的，在矩阵C中，图中的当前像素匹配代价即为初始匹配代价，上一像素匹配代价表示聚合后的代价值，当前像素更新后匹配代价是根据公式4计算而来（注：没有减去第三项，因为这里p1,p2的值没定，不能确定哪个最小，故省去了相减的操作）。
呼…终于快写完了…前文公式4介绍的是某条路径上聚合代价的值，那么总路径的聚合代价公式如下：
上式中的r表示聚合的路径，一般情况下，有4路径（红色箭头方向）、8路径（红色+黑色箭头方向）和16路径（白色箭头方向）三种聚合方式，路径数越多效果越好，但是耗时也会越长，往往需要平衡利弊，根据应用的实际要求来选择合适的路径数。（注：在实际中往往4路径的效果和性价比是不错的）下图为路径聚合的示意图：
图3 路径聚合示意图
我们常用的路径就是4，8，16，这样我们从常用情况出发，就可以说路径数不超过16，那么根据公式5和公式6我们就能很容易的推出S<=16(Cmax+P2) ,根据这个等式，我们就可以通过选择适当的 的值来控制聚合代价的范围，控制聚合代价的范围有什么用呢？这样可以减少聚合代价数组对内存的占用。例如若采用5x5窗口cencus变换方法得到的匹配代价值C最高不超过25（因为cencus变换匹配代价是两个比特位异或后二进制位为1的个数，所有Census变换后的比特串最大有效长度为25），则匹配代价只需用一个字节来存储，而当P2≤65535/16 −25时（216=65536 ），S可以只用两个字节来存储，因为存储代价的C和S空间大小是W × H × D，当影像尺寸较大时，对内存的占用是巨大的，所以减少元素存储所需要的字节数是必要的。
吼吼吼…终于写完了，本文算是一篇自己的学习笔记，其中有不严谨不正确的地方希望大家指出，共同进步！！！
咻咻咻咻~~duang\~~点个赞呗
下一篇：双目立体匹配之视差优化
