PatchMatch系列算法论文_patchmatch算法

算法起源——Patchmatch

patchmatch算法是为了图像编辑而提出的，通过找到与边缘部分最匹配的其他部分来填补边界区域，从而达到自然的效果。算法的关键是可以通过随机采样找到一些好的补丁匹配，并且由于图像的连续性，我们能够将此类匹配快速传播到周围区域。

如果直接采用枚举的方式来解决这个问题，若B图的大小为M，A中patch的像素数为m，那么一个匹配的计算复杂度是$O(M^{2}m)$

算法的三个事实基础：

1.针对$O(M^{2}m)$的维度，一般算法降低patch空间的为维度（kd-tree，计算复杂度$O(mMlogM)$​），没有改变枚举的本质，只是加快了速度。相比于此，直接在2D空间搜寻可能的偏移相比在树结构上直接匹配更加高效。

2.图像的连续性：对每个像素独立搜索会忽略了图像中的自然结构。以相互依赖的方式搜索相邻像素提高效率。

3.大数定律：大量随机分配的前提下，没有patch获得正确偏移的可能性非常小。

算法详解

以蓝色为主颜色，A代表原图像，其中的矩形框代表待修复的patch块，红色和绿色分别是主patch块向左一个像素和向上一个像素。要修复patch_A，就是要在B图（也是原图）中搜索一个最合适的patch块，最终得到的是patch_A到patch_B的偏移量。

PatchMatch 的核心思想是利用图像的连续性（consistence）， 一个图像A的patch_A（蓝色）附近的Patch块（红色绿色）的最近邻（B中的红色绿色框）最有可能出现在Patch_A的最近邻（B中的蓝色框）附近，利用这种图像的连续性大量减少搜索的范围，通过迭代的方式保证大多数点能尽快收敛。

算法步骤

1.初始化

使用coarse-to-fine的逐渐优化策略，初始估计值可以从上一层中上采样得到。初始化随机偏置使用的方法是独立地从图B范围内均匀采样。

2.传播

传播会计算原图A当前像素块patch_A（蓝色）对应的B中的patch_B_1，patch_A上方（绿色）对应的B中的patch_B_2，patch_A左侧（红色）对应的B中的patch_B_3这三个patch块中与patch_A相似度最高的patch块。（分奇数次迭代和偶数次迭代，奇数次对应上左，偶数次对应下右）

3.随机扰动搜索

为了避免陷入局部极值，再额外再随机生成几个patch位置作为候选patch块，若小于当前patch，则更新。

w是窗口大小，R是均匀分布[-1,1]x[-1,1]，$\alpha$​初始值是0.5，随着i增大逐渐减小，$w{\alpha }^i>=1$

随机扰动会在原图A中，以当前像素为中心点，初始半径区域为全图，在此区域内随机找寻patch块并与patch_A原本对应的B中的patch块对比，若更相似则更新对应关系offset，然后以新的patch_B为中心，半径缩小一倍，继续搜索，直到半径缩小为1，更新完毕。

PatchMatch Stereo _BMVC2011, 引用：555

一般算法：平行与相机光轴构建法向量，视差为整数（构建cost volume）

PatchMatchStereo：寻找每个点的最优的空间面片。

主要难点: 在所有可能无限数量的平面中找到一个像素的最优 3D 平面
解决方法: PatchMatch算法 (空间传播) + 拓展 (图传播，时间传播)

在这里，我们使用随机搜索和传播的 PatchMatch 思想，根据一个平面找到对极线上的最近邻。 这使得处理倾斜表面和亚像素精度成为可能。

算法模型

模型前提，图像已经进行了极线矫正

对于两张图的每个像素p，都寻找对应的平面$f_p$，一旦找到，像素p处的视差$d_p$​为:
$$d_p=a_{f_p}{p}_x+b_{f_p}{p}_y+c_{f_p}$$
其中，

**寻找平面使得窗口的匹配代价最小。**其中$q-(a_f{q}_x+b_f{q}_y+c_f)$是q在另一视图的匹配点，相减指的是x坐标与视差相减。

$w(p,q)$通过查看像素的颜色来计算 p 和 q 位于同一平面上的可能性

匹配代价函数既包括颜色又包括梯度。

算法步骤

算法前提是随机初始化之后，每个区域至少有一个像素带有一个接近正确平面的平面，之后的传播步骤把这个视差传递到该区域的其他像素。

——————————————————————————上述就是Patchmatch的思想。

在此基础上，还引入了两个新的传播步骤：视图传播和时间传播。最后还包括一个平面细化的步骤，优化平面参数以接近最佳平面。

（1）随机初始化

对平面参数进行随机初始化。首先选择随机视差$z_0$(连续值，允许视差范围内)，得到随机平面上的一个点P$(x_0,y_0,z_0)$​，平面的法向量计算为随机向量。

（2）迭代

1.空间传播

评估把p空间邻居q的平面$f_q$分配给p是否会改善$m(p,f_p)$的值，即如果$m(p,f_q)<m(p,f_p)$，那么$f_p:=f_q$​。

偶数次迭代考虑左和上邻居，奇数次迭代考虑右和下邻居。

2.视图传播

利用左右视差图之间的强相关性，评估匹配点的平面是否会改善m值，即如果$m(p,f_{p^{\prime }})<m(p,f_p)$，那么$f_p:=f_{p^{\prime }}$

3.时间传播

前后帧的相同坐标处可能会具有相似的平面。同样，如果$m(p,f_{p^{\prime }})<m(p,f_p)$，那么$f_p:=f_{p^{\prime }}$

4.平面优化

优化平面参数以进一步减小m值。

Gipuma_ICCV2015

主要贡献：

1.计算效率：与PatchMatch相比，提出了一种新的扩散方案，更适合于多核GPU，且速度更快。

2.提高准确性和鲁棒性：把PatchMatch Stereo从双目扩展到了多视图匹配，PatchMatchStereo可以直接计算出来各点的法向平面，避免了对极校正。

但是这个方法仍然需要参考图像来确定表面的参数，因此我们首先计算每张图的深度图，然后对齐进行融合。这个方法在深度计算方面尽可能利用了光照一致性，因此深度图的融合仅需要基本的操作步骤即可。

算法提出的传播策略：根据棋盘模式把像素划分为黑色组和红色组，并同时依次更新所有黑色和红色，并且相邻点的选择方式转变了，使用了20个局部相邻点用于传播。

传播方案：（a）对所有红色像素并行更新深度和法线，使用黑色像素作为候选，反之亦然。 (b) 来自局部邻域的平面（红点）作为更新给定像素（黑色）的候选者。 © 速度设置的修改方案，仅使用图案的内部和最外部像素。

在匹配代价计算方面，由于使用RGB带来得提升很小，因此代价计算变换为了灰度差异，同时为了进一步加快计算速度，采取了Sparse Census Transform的思想，Census Transform举例如下所示：

多视图拓展：

由于视差是极线校正后图像所特有的，这对于多视图来说非常不自然，因此提出在欧氏场景空间中使用patch进行操作。

优点：

1.避免了极线校正

2.可以产生3D场景空间内的密集表面法向场，可用于改进后续的点云融合。

3.允许数据代价直接从多视图聚合而来。

基础公式：

对于任一点$X=[X,Y,Z{]}^T$,若满足$n^{T}X=-d$，则有
Z = − d c [ x − u , α ( y − v ) , c ] ⋅ n , K = [ c 0 u 0 c / α v 0 0 1 ] Z=\frac{-dc}{[x-u,\alpha (y-v),c] \cdot n}, K=

$$\begin{bmatrix} c&0&u\\0&c/\alpha&v\\0&0&1 \end{bmatrix}$$ Z=[x−u,α(y−v),c]⋅n−dc​,K=⎣⎡​c00​0c/α0​uv1​⎦⎤​
同时，平面单应矩阵推导如下：

具体推导：https://blog.csdn.net/qq_25638133/article/details/88353125

算法创新点：

1.初始化：为了产生可见半球内均匀分布的随机法向量，做法如下：

$q_1,q_2$来自均匀分布$(-1,1)$内的随机采样，并且$S=q_1^2+q_2^2<1$,那么法向量表示为
$$n=[1-2S,2q_1\sqrt{1-S},2q_2\sqrt{1-S}{]}^T$$
这样就能产生均匀分布在球体上的单位向量。 如果在主光线上的投影 $[u,v,c{]}^{T}n>0$ ，则向量 n 反转。

同时，这里认为深度分辨率是各向异性的：相似性仍然是在图像空间中测量的，因此测量的精度在视差范围内近似恒定，但是与深度是成反比的。因此提出从可能的视差范围均匀的抽取样本并把它们转换为深度值。（近处提供更密集的采样深度，图像中差异可能会更加明显；远处的采样深度更加稀疏，因为可视差异并不大）。出于同样的原因，平面细化步骤的搜索间隔设置也应该与深度成正比。

2.多视图代价聚合：

（1）相邻视图选取，选择观察角度${\alpha }_{min}<\alpha <{\alpha }_{max}$，$\alpha$太小，三角化区域太小，深度不确定性增高；$\alpha$​ 太大，​存在较大的透视扭曲，无法可靠比较外观。

（2）代价聚合：如果只是简单的聚合的话，即使是正确重建的patch，如果处于遮挡部分也使得cost升高，从而导致物体变得模糊。为了解决这种情况，Kang【Handling occlusions in dense multi-view stereo】等人的做法，假设至少存在一半的图像对于重建patch部分是可见的，只选取N个cost中的最好的50%。

该文把固定的50%变成参数K，K确定了要考虑的cost数目。K的选择取决于不同的因素：较高的K值会增加冗余并提升准确度，但也存在包含不匹配的风险，进而影响鲁棒性。根据经验来说，对于比较稀疏的数据集往往相对较低的K值表现会更好，因此这里的K=3

ACMH_Arxiv2018

建立在PatchMatchStereo之上，采用非对称棋盘传播策略，可以根据当前邻居假设的置信度自适应地使有效假设进一步扩展；为了更好聚合来自多个图像的视觉信息，为每个像素提供了多假设联合视图选择，利用了基于多个传播假设的成本矩阵来稳健推断出合适的聚合子集并行。

DeepPruner_ICCV2019

目标：显著加快算法运行时间，以便实现实时推理———————————————————————————KITTI和Scene-Flow 62ms

工作：开发了一个可微分的PatchMatch模块，允许丢弃大多数差异而不用进行完整的cost volume计算。利用这种表示来学习每个像素要修剪的范围，通过逐步减小搜索空间并有效传播此类信息，能够有效地计算高似然假设的成本量。

给定一对立体图像，我们首先提取深度多尺度特征。 然后我们利用可微 PatchMatch 来估计每个像素的一小部分视差，并利用置信范围预测器进一步修剪解空间。 与在整个视差搜索范围内操作的其他方法 [8, 15] 不同，我们只在缩小的搜索范围内聚合成本。 最后，我们利用轻量级网络来优化立体声输出

算法详解

patchmatch估计视差图+置信范围估计缩小视差范围+3D costvolume计算

1. 特征提取

   给定一对图像 { x 0 , x 1 } \{x_0,x_1\} {x0​,x1​},输出一组对匹配有用的深度特征 { f 0 , f 1 } \{f_0,f_1\} {f0​,f1​}​

   通过SPP网络提取特征。

2. 可微patchmatch剪枝模块

   一共包括三层：

   粒子采样层：对于每个像素，从预测/预定义搜索空间上的均匀分布随机生成k个视差值。

   传播层：根据预先定义的滤波模式，相邻像素间的粒子相互传播

   评估层：对于每个像素i，通过像素内积计算候选粒子j的匹配分数，每个像素的最佳k个视差值会在下一轮中使用
   $$s_{i,j}=<f_0(i),f_1(i+d_{i,j})>$$
   整个设计架构在底部有一个粒子采样层，然后循环迭代传播和评估层，由于评估时的argmax算子不可微，因此把它替换为soft版本：
   $$\widehat{d_i}=\frac{{\sum }_j{s}_{i,j}\cdot d_{i,j}}{{\sum }_j{s}_{i,j}}$$
   

   上述图像描述了可微剪枝的模块的允许，在实践中，我们不是让每个粒子都驻留在完整的视差空间中，而是将搜索空间划分为 k 个间隔，并强制第 i 个粒子位于第 i 个间隔中。 这保证了粒子的多样性，并有助于提高以后计算的准确性

   置信范围预测：

   对所有像素而言，初始的搜索空间时相同的，但是对于每一个像素而言，更可能的视差值通常在很小的一个范围内。使用从PatchMatch阶段估计的小视差子集，可以有足够的信息来估计真实视差所在的范围。

   做法：使用置信范围预测网络调整每个像素的搜索空间。该网络是encoder-decoder结构，它把来自可微PatchMatch的稀疏视差估计、左图和扭曲的右图（根据稀疏视差估计扭曲）作为输入，并为每个像素i输出置信范围$R_i=[l_i,u_i]$​.

   第二个PatchMatch：

   这个地方严格来说并没有做Patch match 的搜索，只是根据之前算出来的置信范围上下限，为每一个pixel，在上下限中均匀地取候选点(uniform sampler)。

   可以理解为，第一次patch match 的点，很多都在置信范围之外，这些点对于最后计算视差其实参考意义不大。那么在置信范围之内的点会比较少，用来回归的点就很少了。所以这个时候需要在置信范围内，重新采样，最后通过soft argmin来回归视差。

3. 代价聚合和优化

   代价聚合：

   right_feature_map, left_feature_map = self.spatial_transformer(left_input,right_input, disparity_samples)
   disparity_samples = disparity_samples.unsqueeze(1).float()
   cost_volume = torch.cat((left_feature_map, right_feature_map, disparity_samples), dim=1)
1
2
3

直接把特征图和视差样本concatenate在一起作为costvolume，$B\times R\times H\times W$,其中R为视差样本数目

优化：

通过FCN提升效果，输入加入了低级特征信息以减小噪声并提高边界处的视差图质量。

Planar Prior Assisted PatchMatch Multi-View Stereo _AAAI2020

利用平面模型和PatchMatch，提出了一种平面先验辅助的PatchMatch-MVS，利用概率图模型把平面模型嵌入到PatchMatchMVS中。

1.平面先验信息：

传统的PatchMatch多视图立体方法中，可以在边缘和角落等判别区域建立稀疏可信的对应关系，并且这些对应关系总是与3D模型的mesh表示中的顶点重合，这意味着这些稀疏可信的对应关系几乎构成了整个3D模型的骨架。——>对这些对应关系进行三角化从而得到平面模型。

2.平面先验辅助的多视图聚合匹配代价

利用概率图模型同时模拟光度一致性和平面兼容性，平面兼容性限制预测深度的范围，光度一致性反应纹理良好区域的深度变化。

3.减轻不可靠的平面先验的影响

强制执行多视图几何一致性纠正错误的深度估计。

算法详解

算法输入：

I = { I m ∣ m = 1... N } I = \{ I_m|m=1...N\} I={Im​∣m=1...N}​, 逐次取为参考图$I_{ref}$​,那么对应的源图像 I s r c = { I j ∣ ( I j ∈ I ) ∩ ( I j ≠ I r e f ) } I_{src}=\{I_j|(I_j\in I)\cap (I_j\not= I_{ref})\} Isrc​={Ij​∣(Ij​∈I)∩(Ij​​=Iref​)}

参考图像$I_{ref}$的稀疏可信对应关系。

算法步骤：

1.由传统的PatchMatchMVS方法和阈值生成稀疏对应，根据这些对应关系进行三角化从而得到平面模型。

2.通过构建概率图模型共同考虑先前获得的平面模型和光度一致性，通过这种新的匹配代价完成对低纹理区域的良好深度估计。

（由e可看出，先验的平面参数与低纹理区域的最佳估计几乎一致。）

1.平面模型构建

稀疏重建结果虽然丢失了低纹理区域的深度估计结果，但是可以被用来想象整个场景的3D模型。因此首先对稀疏重建结果进行三角跑分，自适应生成不同大小的三角形基元，由于纹理良好区域的三角形基元相对较小，因此可以保留非平面区域的结构；并且在低纹理区域，三角形基元会尽可能大以利用可信的稀疏重建关系。基元的深度和法向可以由顶点的三个向量计算得到。

2.平面先验协同

平面鲜艳假设会在纹理良好区域产生许多伪影，特别是在边界处。…
（未完待续）

PatchMatchNet

算法步骤

1.初始化和局部扰动

在第一个阶段，基于预定义的深度范围$[d_{min},d_{max}]$,在逆深度范围内对每个像素的$D_f$深度假设进行采样，对应图像空间中的均匀采样。为了均匀确保均匀覆盖深度范围，将（逆）范围划分为$D_f$​个区间，并确保每个区间都被一个假设覆盖。

————————————————————类似于在该点对应的极线上进行均匀采样

在接下来的第k个阶段执行局部扰动，在归一化的反深度范围$R_k$中每个像素产生$N_k$个假设，其中$ R_k$会随着阶段增加而逐渐减小。$ R_k $​的中间值是上一阶段该点的深度值上采样。这比起PatchMatch提供了更多的假设。围绕先前估计进行采样也可以细化局部结果并进行错误的纠正。

2.自适应传播

深度图的空间一致性仅存在于同一个物理表面的像素之间。因此从同一个表面收集深度假设有助于PatchMatch更快收敛并且提供更准确的深度图。通过位移估计的方式产生了$K_p$个深度待选值。

综合12步骤，产生的深度待选值为为$D_f+K_p$个

3.可微映射

4.匹配代价计算

把任意视图的source Images信息及其对应的深度假设整合到reference Image 中。

——————————————————————通过分组相关性计算每个假设的成本，在此基础上通过视图权重加以聚合。

$F_0(p),F_i(p_{i,j})\in R^c$分别代表了参考特征图和源特征图上的点p，把特征通道平均划分为G组，那么第G组的相似性$S_i(p,j{)}^g\in R$的定义式如下

$S_i(p,j{)}^g=G/C<F_0(p),F_i(p_{i,j}{)}^g>$ ， 其中<>代表内积，输出$S_i\in R^{W\ast H\ast D\ast G}$

在获取分组相关性之后，需要计算得到像素级视图权重$(w_i(p){)}_{i=1}^{N-1}$。

打算利用$w_i(p)$来表示像素p在源图像中的可见性，权重计算一次并且保持固定，在更精细的阶段上采样。逐像素视图权重网络由1x1x1内核和sigmoid非线性

3D卷积层组成，输入初始相似度$S_i$，输出0到1的数字和深度假设从而产生$P_i\in R^{W\ast H\ast D}$。

$w_i(p)=max(P_i(p,j)|j=0,1,...,D-1)$

其中 $P_i(p,j)$ 直观地表示 p 处第 j 个深度假设所覆盖范围的可见性置信度

最终每组相似性的计算公式如下所示。

5.自适应空间代价聚合

$p_k$代表了p周围的相邻点，$\Delta p_k$代表了利用2D CNN卷积参考特征图$F_0$在该点学到的偏置