PatchMatch Stereo

Tips

MVS: Multi-View Stereo

Abstract

• 思路：一般的局部立体方法是一个具有整形数值视察（disparity）的支持镜头进行匹配，其中有一个隐藏的假设：再支持区域的像素中具有恒定的视差。这个假设在倾斜的表面是不成立的。
• 每个像素有一个单独的3D平面。
• 除了PatchMatch的空间传播方法外，还有
  • 在立体中左右视图传播的图传播。
  • 时间传播，从视频的前和连续帧中传播平面。
• 倾斜支持窗口可以用来计算全球立体方法的代价，允许明确的遮挡处理，可以处理大的非纹理区域。
• 重构了高度倾斜的表面，并以亚像素精度实现了视差细节。

Introduction

原来局部立体匹配中，恒定时差不太可能发生的原因有二：

• 支持的窗口包含与中心像素位于不同表面的像素。
• 窗口捕捉到倾斜的表面，不是fronto-parallel。
• [ ] ??? 这篇论文提出了一种基于PatchMatch的算法，有效地解决了在每个像素点找到一个“好的”倾斜支持平面的问题。与其他局部算法相比，算法没有构建完整的cost-volume，这在本论文算法中是不可能的，因为标签空间包含了无限个3D平面。相反，算法巧妙地遍历了其中的一部分。这使得一次优化成为可能，平面以及分配给平面的像素能够联合估计，这有效地绕过了错失正确平面的问题。PatchMatch本身就是一个近似稠密的最近邻算法。这篇论文利用随机搜索和传播的PatchMatch思想来寻找平面极线上的最近邻。这使得能够处理倾斜的表面和亚像素精度。

Algorithm

对于两张图像中的每个像素(p), 寻找一个平面(f_p)，视差公式：

[d_p = a_{f_p}p_x+b_{f_p}p_y+c_{f_p} (1) ]

总的优化函数如下：

[f_p = argmin_{finxi}m(p,f)(2) ]

其中(xi)表示所有可能的平面，它的大小是无限的。

代价公式如下：

[m(p,f)=sum_{qin W_p}w(p,q) ho(q, q-d_p) ]

其中(W_p)表示以像素(p)作为中心的方形窗口。但是与现有方法不同，(W_p)不再是2D的，而是3D的。权重函数(w(p,q))用来解决边缘育肥问题，并且实施自适应支持权重的思想，它通过像素之间的颜色来计算他们之间的相似性：

[w(p,q) = e^{-||I_p-I_q||} ]

其中，(||I_p-I_q||)计算像素(p)和(q)在RGB空间的L1距离。

现在来关注( ho(q,q'))部分，首先根据平面(f)计算像素(q)的视差，并且从(q)的x坐标减去这个视差得到在另一张图上的匹配点(q')，函数( ho(q,q'))用来计算像素(q)和(q')之间的不相似性：

[ ho(q,q')=(1-alpha)min(||I_q-I_{q'}||, au_{col})+alpha min(||-||, au_{grad}) ]

2.2 PatchMatch计算视差

随机初始化

给两张图像的一个像素的一个随即平面。

1. Somehow，得到一个随机平面的一个点(P(x_0, y_0, z_0))。
2. 然后计算平面法向量(n=(n_x, n_y, n_z))
   • (a_f=-n_x/n_z)
   • (b_f=-n_y/n_z)
   • (c_f=(n_xx_0 + n_yy_0+n_zz_0)/n_z)

迭代和传播

四种步骤。(1). spatial propagation, (2). view propagation, (3). temporal propagation, (4). plane refinement。

首先处理左图的所有像素，然后处理右图的所有像素。

• 在奇数次迭代中，从左上角的像素开始，逐行遍历。
• 在偶数次迭代中，颠倒顺序。

Search

简单三步骤

• 初始化:两张图A和B，将A图中的每一个像素，随机赋予一个偏移量，在B图中找到一个与之对应。

• 传播：每个像素检查来自相邻块的便宜是否提供了更好的匹配，如果是则采用邻居的偏移量。

• 搜索：每一个像素点在以现在的偏移量位中心的同心圆内部，找到一个更加匹配的偏移量。

搜索的半径以图片为尺寸，然后以1/2的收敛速度减少，直到半径为1.