本文全称《PatchMatch Stereo - Stereo Matching with Slanted Support Windows》，在BMVC2011发表的一篇在立体匹配问题中非常经典的方法，论文链接在此。多视图立体技术是从多个视角的彩色影像中利用立体匹配的算法恢复立体结构的三维视觉技术，Patch Match Stereo 以下简称PMS，是立体视觉中的经典之作，提出了基于视差平面概念的方法，其核心的方法在于针对各个像素预测不同的视差平面从而优化局部匹配窗的效果。


Introduction

在立体匹配中，绕不开一个重要概念，即匹配代价函数，与机器学习中提到的损失函数等概念相似，其衡量了对于一种匹配的代价，通常我们希望定义并找到一种匹配代价最小的匹配作为立体匹配的结果。纵观过去的众多匹配方法，基本可以根据其匹配代价函数分为两大类，一种是局部窗匹配方法，另一种与之对应的是全局匹配方法。本文就是一个典型的局部匹配方法，在传统的局部匹配窗方法中，大多都假设匹配窗中的物体处在同一个平行平面上，即在左右视图中这些像素的视差一致。


如上图所示，视差平面示意图，在立体匹配的最终结果中我们得到的是每个像素的视差，再由相机内参恢复出深度，而相机内参通常是常数，因此我们可以简单地将视差这个概念视为一种深度（乘以一个系数的深度）。视差平面实际上就是在三维空间中的一个平面，只不过此处三维空间中的深度是视差而已。

以往的方法会假设每个采样框中的像素处在同一视差平面上，而实际上这是非常少见的，实际拍摄的物体多为曲面和倾斜表面。另一问题是精度问题，很多方法的采样值都是整型数值，即衡量一个像素的视差为多少个像素。本文则提出了可倾斜的视差平面，并在匹配算法中允许浮点数级别的视差采样，在最终效果可以极大提高视差估计的效果，而且对于球面有很好的重建效果。


Method

针对上述问题，本文提出了一种新的，也是本文的核心创新，窗口模型 – 倾斜支持窗口模型，如上中的 (b) 图所示，该模型可以估计子像素级别的视差，比如上图中的 Q 点。

视差平面建模

在视差空间中，对于影像上的每一个像素 $p$， 寻找一个视差平面 $f_p$，即找到这个像素所在的平面，一旦找到这个视差平面，我们就能以下式子计算视差:

$d_p = a_{f_p}p_x + b_{f_p}p_y + c_{f_p}$


上述式子中的 $a_{f_p}, b_{f_p}, c_{f_p}$ 是一个平面的三个参数，正常来讲一个平面的通式可以表示为是 $ax + by + z = c$，上式中的视差 $d_p$ 即一般意义上的 $z$。这样的平面可以有无数个，但我们需要的是一个能让该像素代价聚合函数最小的平面，也就是

$f_p = \arg\min_{f\in F} m(p, f)$


其中 $F$ 是所有可能的视差平面组成的集合，而代价聚合函数 $m$ 在本文中定义为

$m(p, f) = \sum_{q\in W_p} w(p,q)\cdot \rho(q, q^{\prime})$


其中 $W_p$ 表示以像素 $p$ 为中心的一个正方形窗口，$w(p, q)$ 表示一个自适应地权值，其中 $\gamma$ 是一个自定义的参数：

$w(p, q) = e^{-\frac{\| I_p - I_q \|}{\gamma}}$


到现在就只剩一个部分没有解释了，也就是相似度函数 $\rho$，在一个立体匹配问题中少不了衡量左视图和右视图之间的比较问题，我们在上述内容中已经定义了一种匹配方式，那么匹配代价是什么呢，这就是 $\rho$ 要处理的问题。在聚合代价公式中，给定像素 $q$ 点，我们可以通过其视差平面计算出该像素的视差，通过这个视差 $d_q$，我们可以获取到另一视图中的对应点 $q^{\prime}$，通过定义如下公式来确定两者的相似性：

$\rho(q, q^{\prime}) = (1-\alpha)\cdot \min (\| I_q - I_{q^{\prime}} \| , \tau_{col}) + \alpha\cdot\min(\| \nabla I_q - \nabla I_{q^{\prime}} \|, \tau_{grad})$


上式中的 $\tau$ 表示一个自定义的参数，名为截断代价，提升算法鲁棒性，主要用于遮挡区域。两部分分别计算了 RGB 色差的相似度，以及它们梯度上的相似度。

到这里由视差平面建立的聚合匹配代价模型就结束了，值得注意的是，本文估计的视差可以是浮点数，也就是说如果考察一个像素 $q$ 的对应点 $q^{\prime}$，它不一定能够落在一个整型像素上，大概率会是一个亚像素的位置，本文是通过线性插值来计算相似度函数中 $I$ 以及 $\nabla I$ 的。


迭代优化

那么对于一个像素而言该如何寻找最优的视差平面呢，理论上来说视差平面可能有无数个，暴力搜索显然是不可能的，本文采取了 PatchMatch 提出的随机搜索方法。PatchMatch 算法通过初始化、代价传播、随机搜索等迭代步骤可以快速找到像素块匹配。


如上图所示，加入我们要找到蓝色块在另一张图上的匹配块，我们先在另一张图像上随机采样，完成初始化；然后检查蓝色块的左边和上边的红绿色块与蓝色块的匹配代价，如果匹配代价小于蓝色块本身，说明匹配块更靠近代价小的像素块 (b)，经此代价传播就能知道蓝色匹配块的大致搜索区域 (c)，在该区域中搜索得到最优匹配。

本文的思路是类似的，在代价传播中考虑了空间传播、视角传播以及序列传播等，其中序列传播主要用于视频序列的视差估计，本文着重介绍空间和视角传播。

  • 随机初始化

对于一个像素坐标 $(x_0, y_0)$，我们随机给它分配一个视差值 $z_0$，那么我们就有了一个三维（视差）空间点 $P = (x_0, y_0, z_0)$，同时我们需要假设这个点处在一个视差平面上，对于一个平面有三个参数，也就是这个平面的法向量 $\vec{n} = (n_x, n_y, n_z)$，转化成我们需要的 $a, b, c$ 就是：

$ a_f = -\frac{n_x}{n_z} $
$ b_f = -\frac{n_y}{n_z} $
$ c_f = \frac{n_xx_0 + n_yy_0 + n_zz_0}{n_z} $


  • 迭代

在一次迭代中，每个像素要经历三个过程（序列匹配要走四个流程），也就是空间传播，视角传播，平面优化。先处理左图像的所有像素，再处理右图像的所有像素。偶数次迭代中，会从左上角的像素一行一行从左到右从上到下地处理；奇数次迭代中，则把刚才的顺序反过来。


  • 空间传播

我们以偶数次迭代为例，传播从左上角开始，每个像素 $p$ 点和自己左边以及右边的像素的视差平面进行代价比较，$p, q$ 分别为原始像素和待比较像素，$f_p, f_q$ 是两像素的视差平面，若果待比较像素的视差平面的代价更小则更新 $p$ 点的视差平面，也就是 $m(p, f_p) > m(p, f_q)$ 时，更新 $f_q$ 为 $p$ 的新视差平面，并由该视差平面的公式获得新的视差值。（如上图中的绿色箭头所示）

  • 视角传播

视角传播是一个左右视差值得强连续性检查，我们需要假设一个立体像对中的同名像素点有一样的视差。所以这个步骤中我们对于一个像素 $p$，我们在其另一视图中找到所有匹配点为 $p$ 的点，称其为 $p^{\prime}$，我们检查 $p$ 点在这两个视差平面上的代价，如果 $m(p, f_p) > m(p, f_{p^{\prime}})$，那么 $f_{p^{\prime}}$ 就更新为 $p$ 的新视差平面。

  • 平面优化

这一步的目标是要优化 $p$ 点的视差平面 $f_p$ 的参数，不难注意之前两步都是对视差平面的选择来优化视差值，此步则是对视差平面本身进行调整。先回到用法向量表示平面的模式，我们定义两个参数，$\Delta_{z_0}^{max}$ 表示最大可调的 $z_0$ 值，$\Delta_{n}^{max}$ 表示最大可调的法向量每个元素的值。

接着我们从 $[-\Delta_{z_0}^{max},\Delta_{z_0}^{max}]$ 区间中随机挑一个 $\Delta_{z_0}$ 使得 $z^{\prime} = z + \Delta_{z_0}$。同理，我们微调出一个新的法向量 $\vec{n^{\prime}}$。依照此法我们获得了一个新的视差平面 $f_{p^{\prime}}$，比较两者的代价函数，如果 $m(p, f_{p_{\prime}}) < m(p, f_p)$，我们就把 $p$ 点的视差平面更新为 $f_{p^{\prime}}$。

这个过程也是迭代完成的，设置初始值 $\Delta_{z_0}^{max} = maxdisp / 2$，其中 $maxdisp$ 是最大允许的视差值，再有 $\Delta_{n}^{max} = 1$。每进行一次优化，都对 $\Delta$值除以 2 直到 $\Delta_{z_0}^{max} < 0.1$。

Post Process

这部分主要针对遮挡像素，对于每个像素 $p$ 检查它与匹配点的视差是否一致，即 $| d_p - d_{p^{\prime}}| \leq 1$。若上述条件不满足说明匹配无效，算法会向左向右索索最接近的有效像素，记录它们的两个点的视差平面 $f_l, f_r$，根据视差平面公式计算 $p$ 点的视差并选择较小的那个视差值作为 $p$ 的填充。

Conclusion

这篇笔记对 PatchMatch Stereo 的整体算法流程做了一个详解，参考了部分博文的讲解，即此文《传统多视图立体算法：PatchMatchStereo详解》。本文的代码实践由李迎松博士开源。