来源：/dulingwen/article/details/104128503
作者：dulingwen@CSDN（已授权）
编辑：3D视觉开发者社区
一、简介
ELAS是由Andreas Geiger于提出的一种比较新颖的立体匹配算法，全称为《Efficient Large Scale Stereo Matching》。这种算法的优点是对于高分辨率的图像，能够兼顾较高的匹配速度和匹配精度，在许多公开的数据集中ELAS的平均匹配精度十分接近SGM，但是速度却比SGM更快。ELAS算法并没有遵循典型的代价计算、代价聚合、视差优化、视差细化的过程，而是将立体匹配过程建模成为贝叶斯最优估计理论，通过最大后验概率估计方法推理视差。该算法利用图像中一些稀疏的能够鲁棒匹配的支持点作为先验，并将这些支持点进行Delaunay三角化，从而可以降低剩余像素点的匹配歧义，不需要进行全局优化。该算法可以自动决定每一个像素点的视差搜索范围，并且很容易实现并行操作。仅使用单核CPU的话，ELAS算法对于一百万像素分辨率的图像进行匹配需要仅仅大概1s左右的时间。
ELAS算法的基本流程是：
(1) 对左右图像进行sobel滤波，生成sobel特征图；
(2) 基于sobel特征进行匹配，筛选出其中具有较高置信度的匹配点，作为"support points"，即支持点；
(3) 对支持点构建Delaunay三角网格；
(4) 构建立体匹配的概率生成模型；
(5) 基于最大后验概率密度估计(MAP)进行稠密立体匹配，获取初始视差图；
(6) 视差后处理：无效孔洞插值、（自适应)中值滤波、连通域噪声剔除、左右一致性检验。
二、计算支持点
在计算支持点之前，需要设置一个全局可靠的视差搜索范围：， 一般最小视差设置为0，最大视差需要根据所使用的场景来调整。首先对左图像采用3X3的sobel算子进行滤波，获取每一个像素点的水平和垂直响应值Gx和Gy。然后对每一个像素，从其周围5X5邻域中的水平方向响应值选取12个，垂直方向响应值选取4个，构成一个16维的特征向量：
特征匹配时，对左图中的每一个像素，使用右图中对应的每一个像素5X5邻域中的四个角的特征向量、、、、，进行匹配，匹配对的相似性度量值的计算方式如下：
从中选取相似度最高的像素作为匹配对（同样的方法可以获取右图所有像素的匹配），然后采用ratio test对匹配进行筛选，即最低匹配值和次低匹配值的比值小于设定阈值时才认为是正确的匹配。为了进一步保证匹配的置信度，采用左右一致性检验和支持点周围一定邻域内其它支持点数量的判断(数量太少，认为该支持点不可靠)，继续筛选剩余匹配。经过以上几个步骤就可以得到所有的支持点了。
作者还指出sobel滤波对于特征匹配是十分高效的，虽然有很多可以进行鲁棒匹配的描述子，比如SIFT、SURF等，但是他们对于整个立体匹配的精度并没有带来提升，而且还会拖累运行速度。
三、立体匹配的概率生成模型
所谓概率生成模型就是将视差和左右图的像素看作随机变量，根据贝叶斯理论对视差的概率分布进行建模，根据概率生成模型，给定参考图像和支持点，可以从另外一副图像中进行采样。令表示支持点的集合，每一个支持点令表示观测点的集合，每一个观测点其中为特征向量。令和表示左右图像中对应像素点。不失一般性，将左图作为参考图。在给定视差条件下，观测对和支持点集S是条件独立的，他们的联合分布可以被分解为：
其中称为先验概率，称为似然概率。
（1）先验概率建模
作者认为先验概率与均匀分布和高斯分布的组合成比例：
其中为观测点基于周围支持点的平均值，为观测点周围20X20邻域内所有支持点的视差值所构成的取值范围。为了进一步缩小取值范围，所有与均值之差大于的视差都被排除了。表示为一个分段线性函数，可以通过基于支持点构建的delaunay三角形来进行视差插值得到。对每一个三角形，其所在的视差平面定义如下：
其中i是所属三角形的索引，对每一个三角形，平面参数可以由三角形的三个顶点通过求解线性方程求得。
（2）似然概率建模
作者认为图像似然概率可以表示成一个拉普拉斯分布：
其中和为特征向量，是一个常数。if条件保证似然概率约束在左右图像的同一行上。特征向量由观测点周围5X5邻域内像素的sobel响应值拼接而成，故其维数2X5X5=50（实际使用的特征向量依然按照上一节所引入的16维特征向量）。作者在文中特别指出基于sobel滤波的特征性能明显好于基于LoG滤波的特征。
（3）基于概率生成模型的采样
概率生成模型的优点是给定支持点集合和左图参考点，可以从右图采样对应的像素点，方法如下：
1）给定S和可以根据先验概率分布，随机采样视差；
2）给定和，可以根据似然概率分布得到右图对应点。
如下图所示是采样过程示意图：
为了更好的理解这个过程，下图展示了使用灰度值作为特征，对左图每一个像素重复上述过程采样一百次，取平均之后得到一个新图，从图中可以看到，正如所预料的那样，新图相当于一个模糊版本的右图。
四、视差计算
第三节讲述了概率生成模型：
（1）提出一个先验概率分布和图像似然概率分布，并基于此进行立体匹配，先验分布决定视差采样的范围，似然概率提供了视差采样可靠性的判断；
（2）根据概率生成模型，给定左图和支持点，可以从右图中进行采样。
然而更为重要的是如何根据概率生成模型来计算视差图。作者提出可以使用最大后验概率估计(MAP)的方法估计视差：
其中，，........表示右图中位于对极线上的观测点。后验概率表示给定左图观测点、支持点集和右图观测点，左图观测点取视差的概率。后验概率可以被分解为：
将先验概率和似然概率带入上式，并取负对数可以得到一个能量函数：
能量函数的第一部分表示似然项，第二部分为先验项或平滑项。通过最小化能量函数，可以得到观测点的视差。出于编程的考虑，实际当中应用的能量函数为：
这样可以预计算先验项。最小化能量函数时，将视差分成了两个部分：
(1)基于先验分布，仅考虑观测点经插值后的平均视差的局部范围，即sradius一般取2或3；
(2)基于像素周围20X20邻域内的所有支撑点的视差构成的视差搜索范围（如下图所示），这部分视差在最小化能量函数时不考虑先验项。（Note：最小化搜索过程中考虑了纹理，对于太弱的纹理直接跳过计算视差）
同样的方法可以计算右图的视差图。
五、后处理
后处理部分采用无效区域孔洞插值、左右一致性检验、连通域噪声剔除、中值滤波、自适应中值滤波。
1.左右一致性检测
设左图像素点的视差为，则右图的对应点的视差为，若，则认为视差是可靠的，否则将其置为-1或其他无效值。其中一般取1或2，可适当调整。
2.孔洞插值
在对立体匹配的过程中，有多种情况会使得视差图中某点的像素被置为无效值，如纹理不足、左右一致性检验等。对于这些点处的视差往往需要通过插值给予其一个合理的视差值。首先考虑水平方向，若某个无效区域的最左侧和最右侧的视差值为和考虑深度突变，则其中所有点的视差的插值公式如下：
其中表示深度不连续的阈值。垂直方向也以同样的方法进行一次插值。
3.中值滤波与自适应中值滤波
中值滤波可以消除视差图中的孤立噪点，而自适应中值滤波类似于双边滤波，在平滑去噪的同时，还能较好的保留视差图的边缘。
4.连通域噪声剔除
视差图中总是包含着错误的视差，由于弱纹理、反射、噪声等诸多因素，这些错误的视差往往成聚集成小的块状区域，使用该方法可以有效去除视差图中块状噪声区域。给定连通域的灰度阈值和尺寸阈值，通过检测连通域的尺寸是否满足尺寸阈值条件，来判断该连通域是否为噪声。若为噪声，将该连通域中的所有视差置为无效值。
六、代码实现
作者已经开源了C++源代码，并提供了Matlab接口，下载地址为/download.php?file=libelas.zip。源码如下：
下载源码后，导入visual studio工程，编写main函数(代码使用了第三方库opencv来读取图片)：
#include <iostream>#include <time.h>#include "elas.h"#include "image.h"#include <opencv2/opencv.hpp>using namespace std;using namespace cv;int main(int argc, char** argv){string path1 = "C:/Users/thinkpad/Desktop/left/000003.png";string path2 = "C:/Users/thinkpad/Desktop/right/000003.png";//读取左右视图 Mat left = imread(path1, -1);Mat right = imread(path2, -1);if (left.size != right.size) {cerr << "左右视图必须拥有相同的尺寸" << endl;return -1;}if (left.channels() == 3)cvtColor(left, left, COLOR_RGB2GRAY);if (right.channels() == 3)cvtColor(right, right, COLOR_RGB2GRAY);int width = left.cols;int height = left.rows;int dim[3] = { width, height, width };Mat disp_left = Mat::zeros(Size(width, height), CV_32FC1);Mat disp_right = Mat::zeros(Size(width, height), CV_32FC1);// 参数设置 Elas::parameters param;param.disp_min = 0; // 最小视差 param.disp_max = 256; // 最大视差 param.support_threshold = 0.85; // 比率测试：最低match VS 次低matchparam.support_texture = 10; // 支持点的最小纹理param.candidate_stepsize = 5; // 用于支持点的sobel特征匹配的邻域半径param.incon_window_size = 5; // 不连续性窗口的尺寸param.incon_threshold = 5; // 不连续性窗口内的视差范围阈值param.incon_min_support = 5; // 不连续性窗口内的最低支持点数量param.add_corners = true; // 是否添加角点param.grid_size = 20; // 网格尺寸param.beta = 0.02; // 图像相似性度量的参数param.gamma = 3; // 先验概率常数param.sigma = 1; // 先验概率的标准差param.sradius = 3; // 标准差半径param.match_texture = 1;// 最低纹理param.lr_threshold = 1; // 左右一致性检验阈值param.speckle_sim_threshold = 1;// 连通域判断阈值param.speckle_size = 200; // 连通域噪声尺寸判断阈值param.ipol_gap_width = 3; // 空洞宽param.filter_median = false; // 是否中值滤波param.filter_adaptive_mean = true; // 是否自适应中值滤波param.postprocess_only_left = true;// 是否只对左视差图后处理，设置为True可以节省时间param.subsampling = false; // 每个两个像素进行视差计算，设置为True可以节省时间，但是传入的D1和D2的分辨率必须为(w/2) x (h/2)clock_t start = clock();Elas elas(param);elas.process(left.data, right.data, disp_left.ptr<float>(0), disp_right.ptr<float>(0), dim);clock_t end = clock();cout << "running time：" << (double)(1000 * (end - start) / CLOCKS_PER_SEC) << endl;disp_left = disp_left * 3;imwrite("C:/Users/thinkpad/Desktop/disparity.jpg", disp_left);}
七、实验效果
这里随机选择了KITTI双目数据集中的几张图片，下面是左视图及使用ELAS算法生成的对应的视差图：
八、总结
ELAS算法的最大优点就是匹配速度快的同时又有较高的匹配精度，这是因为它通过鲁棒匹配的支持点作为先验，降低了剩余像素点视差的搜索范围。所有视差平面实际上代表了场景的几何结构，因此位于某视差平面内的点的视差必定与附近的支持点具有相近的视差。
获取支撑点的过程实际上就是传统的不包含代价聚合的局部立体匹配算法，这一步骤耗时较短，所以ELAS算法的运行时间下限不会比最快的局部匹配算法更少。
先验概率和似然概率的建模似乎还有可以改造的空间。
虽然在公开数据集中ELAS匹配都能够取得很好的效果。但是对于实际场景的图像特别是室外图像，当传感器噪声较高、存在大面积无纹理区域时，ELAS算法依然不能处理的很好，原因在于在这种情况下sobel算子从图像中不能获得足够多的精确支持点，后续的匹配性能就会大打折扣。
到目前为止，关于ELAS算法的变种不是太多，其中较好的改进有LS-ELAS。
本文仅做学术分享，如有侵权，请联系删文。
下载1
在「3D视觉工坊」公众号后台回复：3D视觉，即可下载 3D视觉相关资料干货，涉及相机标定、三维重建、立体视觉、SLAM、深度学习、点云后处理、多视图几何等方向。
下载2
在「3D视觉工坊」公众号后台回复：3D视觉github资源汇总，即可下载包括结构光、标定源码、缺陷检测源码、深度估计与深度补全源码、点云处理相关源码、立体匹配源码、单目、双目3D检测、基于点云的3D检测、6D姿态估计源码汇总等。
下载3
在「3D视觉工坊」公众号后台回复：相机标定，即可下载独家相机标定学习课件与视频网址；后台回复：立体匹配，即可下载独家立体匹配学习课件与视频网址。
重磅！3DCVer-学术论文写作投稿交流群已成立
扫码添加小助手微信，可申请加入3D视觉工坊-学术论文写作与投稿微信交流群，旨在交流顶会、顶刊、SCI、EI等写作与投稿事宜。
同时也可申请加入我们的细分方向交流群，目前主要有3D视觉、CV&深度学习、SLAM、三维重建、点云后处理、自动驾驶、多传感器融合、CV入门、三维测量、VR/AR、3D人脸识别、医疗影像、缺陷检测、行人重识别、目标跟踪、视觉产品落地、视觉竞赛、车牌识别、硬件选型、学术交流、求职交流、ORB-SLAM系列源码交流、深度估计等微信群。
一定要备注：研究方向+学校/公司+昵称，例如：”3D视觉+ 上海交大 + 静静“。请按照格式备注，可快速被通过且邀请进群。原创投稿也请联系。
▲长按加微信群或投稿
▲长按关注公众号
3D视觉从入门到精通知识星球：针对3D视觉领域的视频课程（三维重建系列、三维点云系列、结构光系列、手眼标定、相机标定、orb-slam3等视频课程）、知识点汇总、入门进阶学习路线、最新paper分享、疑问解答五个方面进行深耕，更有各类大厂的算法工程人员进行技术指导。与此同时，星球将联合知名企业发布3D视觉相关算法开发岗位以及项目对接信息，打造成集技术与就业为一体的铁杆粉丝聚集区，近2000星球成员为创造更好的AI世界共同进步，知识星球入口：
学习3D视觉核心技术，扫描查看介绍，3天内无条件退款
圈里有高质量教程资料、可答疑解惑、助你高效解决问题
觉得有用，麻烦给个赞和在看~
