转载请注明出处：http://blog.csdn.net/wangyaninglm/article/details/51533549，
来自：
shiter编写程序的艺术

图割，置信传播等全局优化立体匹配算法，由于运算过程中需要迭代求精，运算时间长，无法达到实时计算立体匹配的需求，然而实时性需求却广泛存在立体匹配的应用场景中。很多基于局部匹配的算法虽然运算时间短，但由于仅考虑匹配窗内的代价聚合，效果很差，视差图只有很多稀疏的视差点，还要经过插值计算，显然无法用于汽车导航，目标拾取等需要精确结果且对运算速度有一定要求的场景。

1局部代价聚合

基于窗结构局部立体匹配算法，按照匹配约束来搜索最佳的匹配点，在搜索求取左右两幅图像在视差d下一点的匹配代价时，实际是求得以该点为中心的匹配窗内所有点的代价的平均值（或者其他的度量方式）。如图（4-1）：

图 4-1 局部匹配算法的代价传递
Figure 4-1 Cost delivery of local aggregation
我们把这一过程叫做代价聚类（Cost aggregation），这种基于区域的匹配方法利用局部窗口之间的相似性度量来匹配对应基元的空间坐标，对于连续性细节明显的区域效果较好。显然，此类方法对于匹配窗以外的点却无法影响该点的代价值，使得代价聚类的值不具有全局特性，也就丧失了匹配基元的全局结构特性，因此在纹理特征较低的区域非常容易产生误匹配。
如何在代价聚类中获取匹配基元的全局特征，进而使得局部代价聚合方法克服上述缺点，本章相对于基于区域的局部窗立体匹配方法，采用图论中的最小生成树方法，利用树结构进行全局代价聚合。

2 双边滤波与代价聚合

双边滤波（Bilateral filter）是一种可以保边去噪的滤波器。简单的说就是一种同时考虑了像素空间差异与强度差异的滤波器，因此具有保持图像边缘的特性。该滤波器可以由两个滤波参数进行控制。一个控制几何空间距离。另一个控制像素差。

图 4-2 双边滤波对空间和颜色权重的同时作用
Figure 4-2 bilateral filter weights of the central pixel
在传统高斯滤波器中，权重只和像素之间的空间距离有关系，无论图像的内容是什么，都有相同的滤波效果。双边滤波器，在高斯滤波器的基础上增加了像素差值的权重信息，公式（4-1）如下所示：

公式（4-1）是一个归一加权平均，和分别衡量图像I的滤除量，前者控制距离信息的权重，后者控制颜色信息的权重。因此总体而言，在像素强度变换不大的区域，双边滤波有类似于高斯滤波的效果，而在图像边缘等强度梯度较大的地方，可以保持梯度。该特性在立体匹配问题中可以取代图像分割方法，或者作为图像分割方法的预处理手段，降低核心匹配算法的计算量。
设为像素p在视差层级d的匹配代价，为聚集代价。则双边滤波可以按照公式（4-1）与求取聚集代价进行融合中。

其中q作为支撑窗中的一个像素。和与公式（4-1）的参数类似分别为调整空间相似性，和颜色（灰度）相似性的两个参数。通常双边滤波函数计算中可以省去标准化的步骤，则公式（4-3）可以简化为：

3 最小生成树

最小生成树也叫最小权重生成树。在给定的无向图中，(u,v)代表连接顶点u与顶点v的边，w(u,v)代表此边的权重，若存在T为E的子集且不存在环，使得w(T)最小，则T为G的最小生成树。

根据最小生成树结构，当把图像看做是一个四联通区域的图时，图像两点所形成边的权值定义为这两点灰度值的差值（或者颜色信息等其他度量准则），这种定义下生成的最小生成树结构正好符合为匹配窗添加全局特性的期望。

4 基于最小生成树的代价聚合

求两幅待匹配图像在视差d下一点的代价值时，基于区域的匹配窗代价聚合方法对与匹配窗以外的点无法影响该点的代价值，着眼于代价聚类，为了使代价值具有全局属性，使图像内所有点都对该点传递一个支撑量，距离该点较远的颜色差别很大的像素点传递较小的支撑量，距离相近颜色差别不大的传递较大的支撑量。
根据最小生成树结构我们知道，当把图像看做是一个四联通区域的图时，图像两点所形成边的权值我们可以定义为这两点灰度值的差值，这种定义下生成的MST结构正好符合我们的期望，相当于在局部算法上加了全局性质，并且没有增加过多的运算量。
基于最小生成树的代价聚类过程十分简单，针对待匹配图像生成一颗最小生成树后，其代价聚合方式主要有两种：
1.自底向上聚合，即从叶子节点到顶点的遍历。
2.自顶向下聚合，即从顶点到叶子节点的遍历。
对于每一个节点的聚合代价，只需要对生成树遍历两次就可以得到结果（如图4- ）。

图 4-3 两种代价聚合方案
Firgure 4-3 Two cost aggregation schemes
设S（p，q）定义为两点的相似度，D（p，q）定义为两点的距离（MST两点间的最小路径），为聚类值。则有：

其中作为控制两点之间相似度的参数。融合公式（4-4）双边滤波的结果后：

注意到公式（4-4）中存在两个滤波控制参数，由于最小生成树结构本身带有距离度量，并且在树中距离相近的像素也越相似，所以公式（4-7）只使用一个参数控制相似度。
下面根据两种聚合方式分别介绍如何计算聚合代价。

4.1 自底向上聚合（Leaf to Root）

图4-4 自底向上聚合
Figure 4-4 Leaf to Root aggregation
自底向上聚合即为Leaf to Root，是从叶子节点到根节点的代价聚合，以图4-4为例，假设图4-4是一个最小生成树，边上的数值代表权重，此时计算节点V4的代价聚合，那么可以直接计算子节点（V3， V4）的代价聚合值与各自边缘的乘积集合，因为V4是根节点，不需要考虑父节点的影响。箭头向上代表从叶子到当前节点的代价聚合值。则V4的聚合代价可以表示为公式（4-8）：

根据公式（4-8）可以推导出计算自底向上聚合代价的方法，按照根节点的聚合代价为子节点聚合代价乘积的和来进行计算：

如果节点v是叶子节点，则
由于在计算过程中利用了最小生成树的特性，自底向上的代价聚合过程中每一层的计算只需要计算其子节点的乘积，而子节点的代价聚合值已经包含了孙子节点及其子孙节点的影响。所以运算过程中极大的降低了运算量。

4.2 自顶向下聚合（Root to leaf）

对于图4-4中的情况，V4没有父亲节点，属于特殊情况，如果我们要计算V3的代价聚合值呢？显然只考虑V1和V2是不够的，还得考虑V4的影响。也就是从上到下的影响。如图4-5所示：

图 4-5 自顶向下聚合
Figure 4-5 Root to leaf aggregation
此时我们完全可以假设V3为根节点，它的父节点向下转换变为他的子节点，则可以利用同样的办法，将V4的代价聚合值乘以它的权重一起再加进来。但是因为V4的代价聚合值已经考虑到了V3的影响，所以必须事先将V4的代价聚合值减去V3的代价聚合值才可以。则V3的聚合代价值可以表示为：

其中，自顶向下的代价聚合值就是最终的代价聚合值，要从上到下一层一层的计算代价，这样同样可以减少计算量。对于更为一般的情况，即当从根节点向叶子节点代价聚集时候，根据公式（4-10）可以推导出其一般形式：

化简得：

5 立体匹配的通用并行化处理

并行程序开发的编程模型主要分为两类：1.消息传递模型，2.共享存储模型。本文主要采用共享存储模型在彩色图像的各个通道上采取粗粒度的并行划分，在彩色图像上进行并行化处理，各个通道内部针对滤波算法，最小生成树的建立等算法，进行基于处理器指令向量化的SIMD扩展。
其主要流程如下流程图所示：

图4- 并行化立体匹配流程
Figure 4-
首先针对基于最小生成树的全局立体匹配算法，的整个算法流程进行计算量分析建模，分析并提取其中的密集计算任务，参照[32]进行双边滤波的优化

5.1 OpenMP 线程并行化

OpenMP实际上是对共享内存并行系统，提供了一套指导性的编译注释方案。现在的常用的品牌基于x86架构的Intel AMD桌面处理器，基于ARM架构的处理器对OpenMP都有很好的支持。作为主流的共享内存模型，得到了几乎所有商业编译器的支持，具有很好的可移植性。
主要是，加上openmp代码编译选项后，代码可移植了。

5.2 通用处理器指令优化（SIMD向量化计算）

几乎所有的处理器厂商都为自己的处理器产品制作了多媒体扩展部件。图形处理器的并行计算需要额外的硬件投入，而且与内存交换数据需要耗费时间。多媒体扩展部件一般在处理器中以向量部件的形式出现，相应的指令集以（Single Instruction Multi Data）单指令多数据流作为出现.
SIMD在性能上的优势：编辑以加法指令为例，单指令单数据（SISD）的CPU对加法指令译码后，执行部件先访问内存，取得第一个操作数；之后再一次访问内存，取得第二个操作数；随后才能进行求和运算。而在SIMD型的CPU中，指令译码后几个执行部件同时访问内存，一次性获得所有操作数进行运算。这个特点使SIMD特别适合于多媒体应用等数据密集型运算。
SIMD适量指令能够加速如C和Java语言的处理。矢量指令对过个数据元素进行并行操作，从而使主机能够快速处理大量数据。这对于社交媒体和大数据工作负载来说是个福音，但对面临普通负载的系统程序员来说似乎没有太大的帮助。
SIMD指令通过多种方式增加吞吐量。大多数机器指令会的结果会覆盖输入操作数其中之一不同，大部分SIMD指令集会使用两个输入寄存器，并将结果存储在第三个寄存器。这意味着程序员可以节省与寄存器纠结的时间。
矢量寄存器为128字节长度。前16个寄存器实际上与64位浮点寄存器(FPRs)共存。改变一个FPR同样会破坏对应矢量寄存器的所有字节。存在一些关于通过程序调用保护矢量寄存器的特殊规则，IBM的Assembler Services Guide有详细说明。
SIMD向量指令包括所有数学函数和浮点模式。同样也有字符串操作以及用于获取和存储数据的方法。

参考文献

[11]Yang Q. A non-local cost aggregation method for stereo matching[C]// Proceedings / CVPR, IEEE Computer Society Conference on Computer Vision and Pattern Recognition. IEEE Computer Society Conference on Computer Vision and Pattern Recognition. 2012:1402-1409.
[12]Yang Q, Ji P, Li D, et al. Fast stereo matching using adaptive guided filtering[J]. Image and Vision Computing, 2014, 32(3): 202-211.
[13]Yang Q. Hardware-efficient bilateral filtering for stereo matching[J]. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 2014, 36(5): 1026-1032.
[14]Yang Q. Stereo Matching Using Tree Filtering[J]. Pattern Analysis & Machine Intelligence IEEE Transactions on, 2015, 37(4):834-846.

论文资源合集

立体匹配综合论文集 : http://download.csdn.net/detail/wangyaninglm/9591251

基于图像分割的立体匹配论文合集 : http://download.csdn.net/detail/wangyaninglm/9591253

并行立体匹配论文合集 : http://download.csdn.net/detail/wangyaninglm/9591255

基于置信传播的立体匹配论文合集 : http://download.csdn.net/detail/wangyaninglm/9591256

基于稠密匹配的论文合集： http://download.csdn.net/detail/wangyaninglm/9591259

转载请注明出处：http://blog.csdn.net/wangyaninglm/article/details/51533549，
来自：
shiter编写程序的艺术