StereoVision--立体视觉（5）
转载自：https://zhuanlan.zhihu.com/p/31500311
这次带来的是杨庆雄老师一篇很经典的文章《A Non-Local Cost Aggregation Method for Stereo Matching》这里简称为NL方法。当时我看的文献还主要是基于support window进行代价聚合的，但是看到这篇文章的时候，我发现这篇文章抛弃了support window，而是提出了一种新的方法，也就是这篇文章的核心算法--MST(Minimum Spanning Tree)。文章认为support window在视差估计上普遍具有陷入局部最优的缺陷，这篇算法叫做non-local也是有原因，虽然字面上翻译的为非局部，但是我认为它不等价于就是全局算法。我们都知道全局算法在立体匹配的步骤中，将算法重心放在了最后两步：视差粗计算和迭代求精步骤，舍弃了代价聚合的步骤，并且运算量很大，这也就导致运算时间很长。但是NL算法利用MST可以天然的建立像素之间的关系，利用像素之间关系可以大大的减少代价聚合的时间。（PS：我的上一篇文章介绍的CSCA算法里面也综合了NL的算法，可以在里面找到NL的源码，需要单独的NL算法的源码可以私信我）
Key Word：Minimum spanning tree:MST 最小生成树
在这篇文章中，代价聚合的问题被重新定义，并且提出了通过non-local解决的方法。跟之前的edge-aware filters很像，guidance image（文章原文：a guidance image(typically the reference camera image)，也就是说通常就是左图）用来給自适应聚合计算像素的相似性。但是在本文中，guidance image被看成是一个无向的、连通的图像，它的顶点是所有像素，它的边缘是所有邻近像素的边缘。匹配代价的值以类似于双边滤波的方法，基于像素的相似度进行自适应的聚合，这个类似于双边滤波的方法其实是基于最小生成树（MST）。两个顶点之间的相似性由它们在MST上的最短距离决定。
使用MST的一大优点是它提供了更自然的图像像素相似性度量指标，因为图像中的每个像素都可以在成本聚集过程中正确地为所有其他像素做出贡献。这篇文章的一个亮点就是它抛弃了传统的局部匹配的 support window的概念，而是提出了MST的概念（看文章中说，在理论上比传统方法在低纹理区域有更好的效果。）
在介绍Non-local之前，先来看一看双边滤波（Bilateral Filter），这里直接给出双边滤波的代价聚合公式（这里 都是左图，也就是我们常说的标准图）：
表示像素点
在视差为
的条件下的代价聚合，
表示像素点
在视差为
的条件下的匹配代价，
表示support window内的像素，
是两个常数，用来校正位置相似性和颜色（强度）的相似性（从公式中的
可以看出来）。
好了，简单的介绍了一下双边滤波，但是我们的工作重心当然不在双边滤波这里，下面来讲一下重点。
算法思想:Cost Aggregation on a Tree Structure
不同于之前的代价聚合方法，在这篇文章里，认为左图是一个连接的无向图，我们将其记为 （PS：需要注意的是，这里的图不是image或者picture的图，而是graph的图，是树状图的图；无向图通常就记为
，并且带有权重
，
是非空集合，也称为顶点集，
是
中元素构成的无序二元组合，称为边集），无向图中的顶点
是所有的像素，边集
就是相邻像素之间的连接。在文章中，将无向图
看成一个最简单和标准的4连接图（这里说的4连接指的图像中的4连接，也就是一个像素周围上、下、左、右是其邻近区域）。这里的权重函数
就是图像的梯度，例如，我们假设
与
是一对邻近像素，那么两者之间的权重就是：
通过去除我们“不需要”的边缘，我们就可以得到生成树。很明显的我们可以看到，在颜色/强度变化很大的地方，其权重也就很重，当然我们也不希望在这些深度边缘进行聚合，所以说这些权重较大的边在生成树的过程中也就会被去除。这样我们得到的就是一个最小生成树（MST，并且包含了所有的像素）。
那么用MST就可以很直接的定义两个像素之间的相似度，在MST上两个节点的距离就是对应两个节点连接边的权重和（这个也很好理解，两个点在无向图上的距离越大，不就说明这两个点越不相似嘛，如果两个点相似度很高，不就说明这个点在无向图上的距离很近）。使用 表示
在MST上的距离，使用
表示两个像素之间的像素度。（通过
我们可以看到，当两个像素之间越相似，也就是
越小，也就导致
越小，这样就使得S(p,q)越大，两个像素就越相似）那么代价聚合表达式就可以变成（公式1）：
下面给出一个文章中的例子：
图1
分析一下论文中给出这幅图，首先图一是标准图，我们来分析一下图像上的每一个像素点对 的权重贡献（权重贡献，其实这里的权重贡献看成相似性，由1变到0对应的颜色由红色变为蓝色），（b）和（c）是双边滤波的结果，后面三幅是MST的结果。我们可以看到，当
设置为无穷大时，与后面的MST一样，可以很好的将框状区体现出来，这里从双边滤波的公式可以看出，当
为无穷大时，exp的结果为0，也就可以认为空间信息的作用完全消失，而只用考虑颜色/强度信息。
核心算法
其实看到这里，我对于这篇文章的算法运行时间是打问号的。因为对一个像素进行代价聚合，那就是对所有图片都要进行计算呀，那计算量不是会很大？？？但是，既然作者已经得到了MST，那么MST的性质肯定得到了很好的应用，下面来看一下。
- Leaf To Root
这里先给出claim的原文：
Claim 1. Letdenote a subtree of a node
and
denote the root node of
times the supports node
其实这个定义可以很简单的从公式1得到，举个例子，在这里我们用 来表示子树
（这里
是根节点）的节点，
表示
的根节点，那么我们就可以得到
的聚合
（根据公式1），那么
的聚合中，来至
的部分就可以被分为两个部分：（1）一个部分来自
，即
；（2）另外一个部分来自
的子树部分，即
下面给出一个简单的树（ 为树的根节点），简单的分析一下leaf to root的情况
图2
在这里我们要清楚的是，这一步是leaf to root的代价聚合，不是最后的代价聚合公式！！！
我们首先根据代价聚合的公式算一下
在leaf to root中，文章给出了一个公式，其中 表示aggregated cost values，
表示
的父母节点，下面给出公式2：
当 是一个没有孩子的叶子节点时，
。由于
是根节点，它没有任何的父母，所以说：
所以说，对于根节点而言， 。
- Root To Leaf
仍然先给出claim的原文：
Claim 2: Letdenote all supports received by node
字面上的意思就是说， 表示一颗子树，子树上的一个节点是
,它的根节点是
,
表示节点
在这课树上接受来至其它节点的supports，那么根节点
在树上接受其它节点的support就变成
。
仍然以图2的树为例，不过这次计算的是 :
当我们计算 的supports时，
就是图中画红圈的部分（也就是来自它本身和它的子树），我们同样可以看到蓝色圈的部分也是
的子树，但是在原始树的结构中，
是根节点，所以说蓝色圈的部分也就等价于计算出在原始树中红圈对
的support，所以说根据相互性，我们可以计算出蓝色圈的support：
，所以说可以得到
的聚合：
将其进行扩展，得到公式3：
利用公式3就可以在MST中建立起根节点与叶子节点的关系，如图所示：
图4
注意区分图2与图4，可以看到箭头的方向是不一样的。
总结一下，整个匹配代价的过程可以分为两步：（1）使用公式2，有叶子节点到根节点计算最初的匹配代价 和
；（2）对
进行聚合，利用公式3，从root to leaf。
实验结果
从实验结果的可以看出，使用NL算法和其他以后的方法进行对比可以明显的看出来效果可以有很大的提升。
总结
作为一篇2012年的立体匹配文章，在当时的效果还是很可观，并且在我的上一篇文章中也有介绍过，CSCA论文也将NL算法作为它们算法的一个特例，可以看出NL算法还是有一定的价值的，一些后续的算法就是对其进行了改进，比如说分割树算法《Segment-Tree based Cost Aggregation for Stereo Matching》，将图事先进行区域分割，再在各个区域中计算MST，在生成MST的过程中，考虑到了颜色值与距离作为边缘权值，取得了比NL更好的效果。