PatchMatch算法原理

??以下图为例，c_i,c_j是一对图像的中心，p是c_i上的一个像素点，在该点的viewray(c_i,p)上找到一个平面使得与邻域帧c_j的聚合代价最小，这个平面f₂就是我们要重建的曲面的切平面。

PatchMatch算法详情

>深度图初始化

??与SGM中深度图初始化一致，不再赘述。

>patch初始化

??利用上述初始化的深度图，我们初始化每个像素的patch平面(用3D点X_i和法向量n_i表示，f_p = [X_i,n_i])。以下图为例，平面是在相机坐标系就是曲面的切平面。

??平面参数X_i计算方式：
??

??式中，K是相机内参，p是像素点坐标，d是p点的深度图。
??法向量n_i计算：
??

??上式中，是用以C_i为中心的球坐标系计算。

??在这里，匹配代价计算方法采用的是基于权重的NCC算法，主要是参考两个因素：与邻域帧的灰度差、与邻域帧的像素距离。具体代价计算公式如下所示：

>深度图传播优化

??迭代传播是重头戏，它的基本思想是把初始的所有视差平面中的正确的视差平面传播至同一视差平面内的其他像素。算法执行多次迭代，每次迭代执行四个步骤：(1)空间传播(Spatial Propagation)；(2)视图传播(View Propagation);(3)时序传播(Temporal Propagation)。其中，偶数次迭代是从图像左上角像素沿行方向传播至右下角像素；奇数次迭代则和偶数次迭代传播顺序相反，即从右下角像素沿行方向传播至左上角像素。
在这里插入图片描述

??1.空间传播：相邻像素很可能在同一平面，查找当前像素p的邻域像素q的平面f_q是否更适合p。如果m(p,f_q) < m(p,f_p),则把f_q作为p的新平面。在偶数次迭代时，q是p的左上边像素，奇数次迭代时，q是p的右下方像素。

??2.视图传播：p在邻域帧对应位置的像素p’的平面应该是比较相似的。所以把p’的平面转换到当前帧下f_p’比较，m(p,f_p’)是否小于m(p,f_p)，若是，则替换当前平面。

??3.时序传播：视频序列相邻两帧同一位置在同一个平面的可能性比较大。所以也可以比较取代价更小的作为p的平面。

??4.随机分配：在每次传播后，对当前像素的平面在一定范围内随机生成一个调整量( $\Delta$ d, $\Delta$ $\theta$ , $\Delta$ $\phi$ )，找代价最小的那个平面。可以加速找到真实的平面。

>深度图获取与优化

??深度一致性检查：判断图像I与邻域的共视区域的深度是否一致。
??实现方法：把图像I_i中的点p投影到世界坐标系下，反投影到对应邻域帧N_k上，得到深度值d(X,N_k)，与邻域帧N_k的深度 $\lambda$ (X,N_k)进行比较，如果与至少k个邻域的深度比较接近则认为p点是个正确点。
在这里插入图片描述

参考文献与代码框架

参考文献：[1].Accurate Multiple View 3D Reconstruction Using Patch-Based Stereo for Large-Scale Scenes.
?????[2].PatchMatch Stereo - Stereo Matching with Slanted Support Windows
代码框架：
在这里插入图片描述