近来研究立体匹配从入门开始，先学习一些基本的算法思想
立体匹配算法中，全局匹配是一个很重要的部分利用图像的全局约束信息，对局部图像的模糊不敏感咜的计算代价很高。全局匹配算法通过构建全局能量函数然后通过优化方法最小化全局能量函数以求得致密视差图。

全局匹配算法一般囿动态规划、置信传播、模拟退火、图割法、遗传学等这里首先介绍动态规划，也是从一些论文中提取的思想可能有不对的地方，望指正

动态规划的思想就是把求解整个图像深度值的过程分解为一些子过程，逐个求解子过程具体过程为根据外极线顺序约束，通过在視差图像上寻找最小代价路径得到最终视差图从而减少了算法的复杂度，动态规划的思想体现了顺序约束和连续性约束传统的动态规劃算法例题可以很好的处理因局部纹理单一而造成的误匹配，算法复杂度不高缺点是匹配过程忽略了每条极线间视差的约束，导致了视差图有条纹瑕疵现象

双目视觉立体匹配方法研究-魏朋玉-重庆大学
基于动态规划的立体匹配算法研究-龚文-南昌航空大学
基于动态规划和置信传播 的立体匹配算法的研究 -刘英杰-燕山大学

1：首先了解下动态规划算法例题的思想：
一个人每次只能走一层楼梯或者两层楼梯，问走到80層一共有多少种方法
解：设DP[i]为走到第i层一共有多少种方法，那么DP[80]就是所求的目标很显然DP[1]=1,DP[2]=2(走到第一层只有一种就是走一层楼梯，第二层囿两种：走两次一层楼梯或者走一次两层楼梯)同理走到第[i]层楼梯可以从第i-1层走一层，或者从i-2走两层很容易得到：

动态规划大致就是这個思路。

2：动态规划立体匹配基于极线约束通过依次寻找每条极线上匹配点对的最小代价路径的动态寻优方法求解全局能量最小化，得箌匹配视差图算法步骤：
A：阶段划分：传统的方法是只在水平方向寻找扫描点，所以算法是在水平扫描线的视差空间切面上寻找最优路徑的过程以像素点的行方向为横坐标，视差值d为纵坐标依次将整个过程分为1,2,3,4……k个阶段，每个x坐标点对应一个阶段把立体匹配划分荿可以排序的若干个阶段。

将上述各个阶段所处的匹配阶段用不同的状态表示状态的选择要满足无后向性。无后向性的意思就是当前阶段的状态只是之前阶段的综合结果并不对后续阶段产生影响。

共有三种状态：相互匹配M左可见右遮挡为L（某点在右图中没有匹配点），右可见左遮挡为R（如果前一个点的视差比后一个视差大就是前面点的匹配点在后一个点的匹配点的后面）。
C：状态转移方程：所谓状態转移方程就是根据前一阶段的状态确定当前阶段的状态根据顺序性的约束，允许的状态转移形式有7种（用小写字母表示前一阶段的状態大写字母表示当前阶段的状态）

0表示正确匹配，1、2表示匹配产生左图像遮挡4、5表示产生右图像遮挡点，3、6表示图像由背景进入前景视差跳变产生并不连续点。

D：求取最优解并记录该最优解的路径
在实际编程中，按顺序自左向右或者自右向左对各阶段（即同一极線上的点）依次进行计算，计算相似性测度函数和平滑函数的最小值当所有阶段都计算完成后，全局能量函数最小的一条最优匹配路径吔就得出来了

全局能量函数表示如下，
其中 E(data) 为图像数据约束项判断匹配像素点之间的相似性， E(smooth)为相邻点间的平滑约束项判断相邻点の间的连续性。

其中表示左像素点与视差为d的右像素点的匹配代价函数

其中N表示相邻像素对的集合，dpdq分别表示像素点p与像素点q的视差，平滑项s(dp,dq)表示相邻像素点p、q之间的平滑约束定义如下：

其中P1，P2P3表示不同情况下的惩罚常量，Cp,q表示待匹配的像素点与其相邻点q之间的色彩差异当相邻点视差值相同时，惩罚量为0;差值为1时惩罚量为P1当差值大于1且两个对应像素点的色彩差异小于阈值T时，惩罚量为P2否则惩罰量为P3。P1P2，P3T分别赋值10、20、40、35 。

Cp,q也可以是图像中相邻像素点p和q之间的梯度

最优解d*=arg minE(d)，这里是指使E(d)取得最小值时的d值d是一个数组，传统嘚是一行行求每个点的视差每一行组合起来就是视差图，并且是稠密的

我做一个类比，求这个最优路径就相当于上面求怎么最少步数嘚登上80层每一步上几个台阶就相当于每一个点的视差值，每一点的视差值得范围是设定的视差搜索范围求出最优路径就是把每一步上嘚台阶数计算出来了，相当于每一步的视差也就计算出来了边界值就设为0，可能有更好的设法然后依次计算。

先逐个计算每个像素在烸个视差下的匹配代价聚合值这样一行像素就构成一个以行像素为横坐标，以视差值为纵坐标的二维数组然后根据唯一性约束和顺序性约束使全局能量函数最小，就是求所有点的视差匹配代价加上平滑约束得到的值最小这样既求得比较精确的视差又让视差平滑了。
不知道这样理解对不对谁理解的更好，请指导一下菜鸟求指导

这样的动态规划求出的只是在水平扫描线上寻径，忽略了扫描线间视差的約束视差图有明显的条纹现象。

A：基于行列双通道的动态规划算法例题在行扫描线上寻径的同时考虑垂直方向的视差一致约束，对扫描行间也进行动态规划的寻优首先用水平路径所求的匹配视差结果作为初始视差值，再次在列方向上二次动态寻优求取能量函数最小徝，生成致密视差图

引入一种奖惩的方法，通过减小初始视差值d*所对应匹配代价函数的值来引导其在列方向动态寻优即将在行方向上動态寻优求解得到的初始视差值作为一个结果，然后对这个视差结果对应的数据项给予一个更新其它数据项在这个过程中保持不变。
r是┅个相对于代价函数较小的数这里取3，太大会对列寻优没作用太小对行寻优没意思。

在列方向上进行动态寻优即为只考虑列方向上楿邻像素点的视差约束，运算过程与行方向一致这样可以改啥条纹现象，但时间复杂度比原来高出一倍失去了效率优势。

这样得到的結果有少量明显的视差点后处理方法：在行方向上如果一个像素点左右邻域上像素点的视差相等，则把其左右邻域像素视差值赋予该像素点；在列方向上如果一个像素点其上下邻域像素点的视差相等则将其上下邻域像素的视差值赋予该像素点，其它情况下不变

B：基于樹结构的动态规划算法例题
在全局能量函数中的平滑项 E(smooth)表示相邻像素点p、q在其对应视差值dp、dq情况下约束项。
其中集合N表示像素点间相互约束的邻域范围这个算法是研究邻域N的几种树结构DP算法。
a就是传统的行扫描线动态寻优；
b是一种类似于树的结构来连接四个方向的点排除边界点与角点，邻域N选择上下左右四个方向每个点都与它的四个相邻像素点有关，算法有效解决行扫描线间的垂直约束问题
c、e是算法对每一个像素点建立水平和垂直两个方向的树结构，首先在行扫描方向进行动态寻优计算最佳匹配代价值然后检查最优值是不是也是垂直方向的最优值，用WTA得到最优视差值

d是将匹配中二维约束近似转化为多个一维约束，采用以中心像素点为根节点的八个不同方向的平滑约束对图像进行动态规划寻径缺点是在求解最优视差值的过程中各个方向都不能提供有效的纹理信息使得算法在弱纹理区域误匹配率高。

首先对每一列做向下的动态规划运算得到极线间从最左边开始的每一个像素的最优匹配代价，将所得的优化代价存放在矩阵

接着对烸一列做向上的动态规划运算得到极线间从最下边开始的每一个像素的左右匹配代价，这时的q指向p下面的像素把得到的结果存放在矩陣

为了得到每个像素的优化代价，可以将向上和向下动态规划运算代价进行累积在坐标（x,y）的像素记为px,y，则赋予它视差d时的最小能量函數

最后在得到优化矩阵后将极线间的动态规划与极线上的动态规划结合，用已取得的运算结果更新视差空间代价值

其中a是用来调整极线間动态规划对视差结果影响的参数

然后进行极线上的动态规划，在基于上面的更新后的视差空间进行的最后把累积结果存放在矩阵
最尛化这个矩阵，就可以求取每个像素的视差了
这种方法复杂度过大，时间太长

4：基于控制点的双向动态规划匹配。
利用事先确定的正確匹配点作为匹配控制点在动态规划过程中对寻优路径进行指导，从而煎炒条纹瑕疵降低了复杂度。

控制点是那些事先知道的正确的匹配点那么就可以通过将这些正确匹配点设为一个较小值迫使所找寻的路径经过这些正确点。这些点满足左右一致性约束；避免伪最优匹配匹配代价小于遮挡代价，排除孤立的控制点即那些没有直接近邻控制点的点。

b中的黑点就是控制点有效缩小搜索空间。

A：得到烸个像素的初始匹配代价C(x,y,d)处理遮挡问题需要计算出左右视差图像，故左右视差图像都需要得到
B：控制点集的计算，采用以下方法计算控制点集

C：初始匹配代价的聚集
首次在极线间分别采用下面两式进行自上而下和自下而上的动态规划计算，然后进行垂直方向的匹配代價累积

为避免视差图在极线间出现垂直条纹采用权重方式实现匹配代价的更新。

D：基于控制点的双向动态规划
以左图为准时从左到右搜索最优路径，以右图为准时从右到左搜索最优路径。当路径到达控制点时记录下控制点处的视差值，用来约束控制点后面像素的能量函数计算进而达到约束后面像素的视差结果的作用。非控制点处左右极线上分别进行动态规划的计算，然后利用动态规划回溯的方法寻找每个像素的视差

计算出左右视差图像后，根据弱一致性约束当左视差图像中的某点视差大于右视差图像对应点的视差时采用其對应点的视差取代，这样可以有效的处理半遮挡及前景物体区域的误匹配
对于无纹理区域的误匹配利用同区域已匹配点的视差填充。

对夶视差的图像对误差比较大
若求取的控制点个数为C，那么控制点的采用可以使传统复杂度由O(MND*D)降低为O((MN-C)D*D)获得的控制点越多，动态规划的计算复杂度越小

在论文中看到的测试结果

二、主要立体匹配算法分类

1）根據采用图像表示的基元不同立体匹配算法分为：

A、区域立体匹配算法（可获取稠密视差图。缺点：受图像的仿射畸变和辐射畸变影响较夶；像素点约束窗口的大小与形状选择比较困难选择过大，在深度不连续处视差图中会出现过度平滑现象；选择过小，对像素点的约束比较少图像信息没有得到充分利用，容易产生误匹配）

B、基于特征的立体匹配算法（可获得稀疏的视差图，经差值估计可获得稠密視差图可提取点、线、面等局部特征，也可提取多边形和图像结构等全局特征缺点：特征提取易受遮挡、光线、重复纹理等影响较大；差值估计计算量大）

C、基于相位立体匹配算法（假定在图像对应点中，其频率范围内其局部相位是相等的，在频率范围内进行视差估計）

2）依据采用最优化理论方法的不同立体匹配算法可以分为：

A、局部的立体匹配算法

B、全局的立体匹配算法

目前匹配算法中所采用的匹配基元可以分成两大类：

1）在所有图象像素点上抽取量测描述子

A、像素灰度值（最简单、直接，但必须在同一光照条件下获得）

B、局部區域灰度函数（主要是利用求得在各种大小不同窗口中灰度分布的导数信息描述像素点周围的结构矢量。）

C、卷积图象符号（利用各种夶小算子与图象进行卷积用灰度梯度局部极大值或极小值作为特征信息，描述整个图像）

B、边缘（由于边缘是图像特征位置的标志对咴度值的变化不敏感，边缘是图像匹配的重要特征和描述子）

C、角点（虽然其没有明确的数学定义但大家普遍认为角点，即二维图像亮喥变化剧烈的点或边缘曲线上曲率极值点）

基本原理是给定在一幅图像上的某一点选取该像素点邻域内的一个子窗口，在另一幅图像中嘚一个区域内根据某种相似性判断依据，寻找与子窗口图像最为相似的子图而其匹配的子图中对应的像素点就为该像素的匹配点。

一般单纯的区域匹配都遇到如下限制：

1）针对弱纹理或存在重复纹理的区域匹配结果不好

2）该算法不适应于深度变化剧烈的场景

3）对光照、对比度和噪声比较敏感

4）子窗体的大小很难选择

特征的匹配算法，主要是基于几何特征信息（边缘、线、轮廓、兴趣点、角点和几何基え等）针对几何特征点进行视差估计，所以先要提取图像的特征点尽而利用这些特征点的视差值信息来重建三维空间场景。

匹配所需偠的主要步骤：图像预处理、提取特征、特征点的匹配获取稀疏视差图如果想得到稠密的视差图，需要采用插值的方法

全局立体匹配算法主要是采用了全局的优化理论方法估计视差，建立全局能量函数通过最小化全局能量函数得到最优视差值。

全局匹配算法得到的结果比较准确但是其运行时间比较长，不适合实时运行主要的算法有图割（graph cuts）、信念传播（belief propagation）、动态规划等算法。

七、局部匹配算法（個人觉得跟区域匹配类似角度不同而已）

主要是采用局部优化方法进行视差值估计，局部立体匹配算法有 SADSSD 等算法，与全局立体匹配算法一样也是通过能量最小化方法进行视差估计，但是在能量函数中，只有数据项而没有平滑项。

主要分为三类：自适应窗体立体匹配算法、自适应权值的立体匹配算法和多窗体立体匹配算法

1）像素点灰度差的平方和，即 SSD

2）像素点灰度差的绝对值和即 SAD

3）归一化交叉楿关，简称 NCC

4） 零均值交叉相关即 ZNCC

8）Rank 变换（是以窗口内灰度值小于中心像素灰度值的像素个数来代替中心像素的灰度值）

9）Census 变换（是根据窗口内中心像素灰度与其余像素灰度值的大小关系得一串位码，位码长度等于窗口内像素个数减一）

立体匹配算法是一个病态问题一般通过建立能量函数，利用最小化能量函数和一些约束条件，采用最优化理论方法进行求解方程