Patch Match

A Randomized Correspondence Algorithm for Structural Image Editing

Approximate nearest-neighbor algorithm

算法核心在于计算 patch 的对应关系(correspondences)。作者定义了一个关于偏移量(offsets)的映射函数 f : A —> R2 来表示最近邻域(NNF),其定义了图片 A 中所有可能的 patch 坐标(记录 patch 的中心坐标),以及两个 patch 之间的距离。假设图片 A 中有个 patch 的坐标为 a,这个 patch 在图片 B 中的对应 patch 坐标为 b,那么 f(a) 就是 b-a。作者把这个f(a) 就叫做偏移量,并且把它存在与图片 A 同维度的数组里。

本文提出一个逼近 NNF 的随机算法。所谓的随机,值得是如果你在图片 B 的某一区域找到与图片 A 中 patch a 对应的 patch b,那么 patch a 附近的 patch 应该也在 patch b 的附近,这样就避免了在整张图片 B 里面去做 match。

该算法包含三个主要的部分,见图 2。第一点,NNF随机填充或者依据先验知识填充。第二点,对 NNF 进行迭代更新,就是把匹配度高的 patch offsets propagete 到临近的位置。第三点,在目前为止发现的最佳偏移附近进行随机搜索。

  1. Initialization

NNF 可以采取随机填充或者依据先验知识填充。对于随机填充,我们在图片 B 的全尺寸上使用独立均匀分布来填充。对于先验知识,如果我们只用它,我们会时不时的进入一个次优局部最小值。为了保持先验知识的质量,同时保有逃离局部最优的问题。

  1. Iteration

初始化后,执行迭代来改善 NNF。迭代算法如下:

以 scan order 检测 offsets,然后每一个 offset 经过两次处理,先是 propagation 然后接着 random search。这俩操作在 patch level 上交替进行:用 Pj 和 Sj 来标识 patch j 进行对应的 propagation 和 random search 处理。然后整个处理依序进行:P1,S1,P2,S2,… , Pn, Sn

  1. Propagation

我们假设 patch offsets很有可能一样,并尝试使用已知的偏移量 f(x-1, y) 以及 f(x, y-1) 改善 f(x,y)。例如,如果在 (x-1, y) 有一个 good mapping,我们试着右移一个单位到 (x, y)。D(v) 表示图片 A 中坐标 (x, y) 处的 patch 与图片 B 中坐标 (x, y) + v 的 patch 之间的距离误差(其实就是各通道上的 L2 距离)。然后从  {D( f(x,y)), D( f(x−1,y)), D( f(x,y−1))} 中挑选一个最小值赋给 f(x,y)。

注释:类似 f(x−1,y) 的函数值是一个二维的位移量,也就是分别对应 x 方向,y 方向的位移。所以上面 D(v) 中的 v 就是这么一个二维位移量。

如果 (x, y) 有一个正确的 mapping 并且在一个一致的区域 R,然后 R 下方的区域到 (x,y) 右边就会被正确的 mapping 填充。在偶数次迭代时我们以反 scan order 向上及向左propagete 信息,这时 f(x+1, y) 和 f(x, y+1) 作为候选 offsets。 

  1. Random search

令 V0 = f(x, y)。我们尝试通过从 V0 开始的一系列指数下降的候选偏移量来提高 f(x, y):

Ui = v0 + wαiRi

其中 Ri 是在 [-1, 1] * [-1, 1] 中均匀采样出来的二维随机偏移量,w 是最大搜索半径,α 是 search window sezes 之间的固定的比例。我们从 i = 0,1,2,… 直到当前的搜索半径 wαi 小于 1 pixel。在作者的工作中,w 为图片 dimension 的最大值,α = 0.5。

终止标准:不同的应用有不同的终止标准,实践中发现算法在某个固定的迭代次数后效果不错。通常 4–5 个迭代即可。

效率:原始算法通过几个小 trick 可以提高效率。在 propagation 个 random search 阶段,当我们希望通过候选偏移量 u 来改善 f(v) 时,如果发现 D(u) 的部分和已经超过当前已有的距离值 D(f(v)) 的时候就可以提前停止了。同样,在 propagation 阶段,

Share this to:

发表评论

电子邮件地址不会被公开。 必填项已用*标注