【算法】PatchMatch立体匹配算法_原理解析

目录

前言

原理解析

1.倾斜支持窗口（Slanted Support Windows）

什么是视差平面？

为什么视差和像素坐标点之间的关系可以解释为平面方程？

视差平面的通用参数方程和点加法向量方程

什么是倾斜支持窗口？

2.基于倾斜窗口的代价计算

3.视差平面的随机初始化

4.基于PatchMatch的迭代传播方法

4.1.空间传播

4.2.视图传播

4.3.时间传播

4.4.平面细化

5.后处理

5.1.一致性检查

5.2.视差填充

PatchMatch相关开源代码

总结

---

前言

PatchMatchStereo是Michael Bleyer等在2011年发表于British Machine Vision Conference（BMVC）上的一篇双目立体匹配算法文章，非常经典，倾斜支持窗的思路打破传统固定窗口式局部匹配的思维桎梏，在Middlebury数据集上获得非常好的匹配效果，一段时间内高居排行榜第一名。更难能可贵的是，它和SGM一样数据泛化能力出色，对大部分数据都能取得不错的结果，所以也被很多商业软件所实现，是真正能够产品化的算法。

Bleyer M, Rhemann C, Rother C. Patchmatch stereo-stereo matching with slanted support windows[C]//Bmvc. 2011, 11: 1-11.

区别于SGM（半全局算法），PatchMatchStereo本身是一种局部算法，可以估计出每个像素上的视差及其所在的3D视差平面，更适用于倾斜表面的视差估计。倾斜窗口的代价可以作为全局方法（比如，Graph Cut）构建代价空间的数据项，从而可以更加鲁棒地恢复出遮挡和大面积无纹理区域的视差。

局部：SAD、SSD、NCC\ZNCC、Census-Transform、Mutual Information、PatchMatch 全局：Graph Cut、Belief Propagation、Dynamic Programming 半全局：SGM、SGBM 参考博文：视觉立体匹配江湖记_扫地机　双目立体匹配_李迎松~的博客-CSDN博客

下图是SGM和PatchMatch的效果对比。基于连续空间的视差平面方法，在精度和效果上有明显的优势。尤其是在边界和细小结构的恢复上，离散空间带来的不精确性以及SGM的代价聚合模型对边界的处理并不清晰（或者说并不精确），使得SGM和PatchMatch差距明显

原理解析

 

1.倾斜支持窗口（Slanted Support Windows）

想要了解倾斜支持窗口，先得知道什么是视差平面。

什么是视差平面？

 

为什么视差和像素坐标点之间的关系可以解释为平面方程？

我们构建针孔相机、成像平面和真实物体表面三者的几何关系如下图所示：

 

 

 

 

视差平面的通用参数方程和点加法向量方程

 

什么是倾斜支持窗口？

 

 

2.基于倾斜窗口的代价计算

 

 

综上，PatchMatch在计算局部窗口的代价的时候，对于窗口内每个像素点会按照独立的视差去计算代价，并且加入自适应支持权重，提高了位于同一平面的匹配点的代价贡献度。  

下面就是PatchMatch的优化方法，其方法最开始是来源于PatchMatch图像融合方法。

最底层的想法是，图像中存在很多区域，在每个区域内，像素之间的视差平面是非常接近的。那么，如果通过随机初始化之后，每个区域至少会有一个像素点具有接近正确视差平面的初始值的话，哪怕只有一个“good”，我们就可以通过迭代传播的方式将这个平面传递到该区域的其他像素上。

3.视差平面的随机初始化

4.基于PatchMatch的迭代传播方法

 

4.1.空间传播

 

  

4.2.视图传播

 

 

4.3.时间传播

4.4.平面细化

这个想法是允许在第一次迭代中进行较大的更改（如果当前视差平面完全错误，那么就非常有意义，相当于遗传算法里面的基因突变）。

在之后的迭代中，我们进行更加精细的采样，这就能允许捕捉到视差细节（比如，圆形表面）。

 

5.后处理

5.1.一致性检查

 

5.2.视差填充

 

 

PatchMatch相关开源代码

[1] GitHub - ethan-li-coding/PatchMatchStereo: PatchMatchStereo，倾斜窗口经典，效果极佳，OpenMVS&Colmap稠密匹配算法。完整实现，代码规范，注释清晰，博客教学，欢迎star！

[2] GitHub - nebula-beta/PatchMatch: PathMatch is the state-of-the-art stereo match algorithm framework.

[3] GitHub - nebula-beta/PatchMatchCuda: The PatchMatch stereo match algorithm implemented by CUDA.

[4] GitHub - cdcseacave/openMVS: open Multi-View Stereo reconstruction library

[1]代码的作者是李迎松，结合他写的博文，可很快地学习和掌握到整个PatchMatch计算过程以及具体实现方法。

[2]和[3]代码的作者是ZhengMao Gong，实现了CPU版本和GPU版本，GPU版本是基于CUDA开发的。

[4]是常用的OpenMVS，可以估计出极线校正前视图的深度，而不需要做极线校正，同样的也有CPU版本和GPU版本。

总结

SGM和PatchMatch本质上都是在求解能够使得代价最小化的视差最优解，最主要的区别是代价计算、优化方法和视差平滑

• 代价计算：SGM所构建的代价空间中的每一个代价是来源于一个基于整像素视差的Fronto-parallel窗口（默认该窗口内所有像素都具有恒定视差），而PatchMatch的代价是来源于基于子像素视差的Slanted support窗口（即，窗口内每个像素点的视差是不一样的），再加上自适应支持权重，使得从局部窗口的代价本身就能反映出不同倾斜表面的细微差别，保证计算的代价具有足够的几何精度。而SGM因为采用的是Fronto-parallel窗口计算代价，不可避免会有视差精度损失的问题。

• 优化方法：SGM采用的是半全局的动态规划方法来近似解决全局代价最小化问题，而PatchMatch是多种方式组合的随机传播方法（空间传播、视图传播、平面细化、时间传播）来近似解决全局代价最小化问题，有点类似遗传算法或者粒子群算法。

• 视差平滑：SGM采用的是添加代价聚合的平滑项和亚像素插值的方式，而PatchMatch是通过空间传播视差平面的方式。

在上述区别中，代价计算的区别使得PatchMatch可以比SGM在精度和效果上有明显的优势，尤其是在边界和细小结构的恢复上。但是优化方法的区别使得PatchMatch的迭代优化次数比SGM高出至少一个数量级，所以在实际运用中多采用棋盘格传播替换原始的串行传播方式，并采用GPU多线程加速计算。