PatchMatch:针对结构图片编辑的随机对应算法

前情提要

图像补全（image inpainting）最初是一个传统图形学的问题。问题本身很直观：在一幅图像上挖一个洞，如何利用其它的信息将这个洞补全，并且让人眼无法辨别出补全的部分。这个问题对我们人类似乎很容易，比如下面图。但是这个任务对于计算机却显得格外困难，首先这个问题没有唯一确定的解，其次如何利用其它的信息？如何判断补全结果是否足够真实？

Region Filling and Object Removal by Exemplar-Based Image Inpainting
这篇文章是2004年的工作，核心思想就是利用图像本身的冗余性(redundancy)，用图像已知部分的信息来补全未知部分。算法的流程大致如下：

1. 对待补全区域边界的像素依次计算补全的优先度(priority)，这个优先度主要考虑2个因素。一个是周围像素可信度高的位置要优先补，另一个是位于图像梯度变化剧烈的位置要优先补。综合二者得到所有优先度之后，挑选优先度最高的像素来补
2. 对于上一步找到的待补全像素，考虑它周围的一个小patch(比如3*3)。在图像已知部分搜索所有的patch，找到最相似的patch

3. 用找到的best match来补全未知部分，并更新相关数值

   
   
   

   算法概述
   
   

   其中存在这样的问题：
   1、如果图像已知部分找不到相似的patch，那算法将无法进行；
   2、这个方法只适用于补全背景以低频信息和重复性纹理为主的图像；
   3、搜索相似的patch计算复杂度非常高，算法运行效率低。
   最后一个问题的解决方案就是用patchmatch来解决的。

摘要

这篇文章提出了一种交互式图片编辑方法。在图像块之间，通过随机算法来快速的找到最近邻相似的图片匹配部分。
Patchmatch算法的核心目的是在两张图片之间快速寻找对应的小区域。
Patchmatch算法可以结合图像重组等技术，来实现诸如图像修复、图片融合、去水印等功能。Adobe Photoshop CS5之后提供的修复画刷、内容感知移动功能就是基于patchmatch算法实现的。

The key insights driving the algorithm are that some good patch matches can be found via random sampling, and that natural coherence in the imagery allows us to propagate such matches quickly to surrounding areas

通过随机初始化，只要有一个patch匹配正确，就可以传播给周围的patch，通过迭代，最终所有的patch都找到最相似的匹配。
Patch match利用概率的思想进行快匹配。

算法描述

1、初始化：随机初始化

2、迭代：
（1）propagation：Propagation: 算法在偶数次对一个Patch查找其原对应点左(x-1,y)上(x,y-1)的Patch，奇数次查找右(x+1,y)下(x,y+1)。

（2）Random search: 加上一定的随机扰动，在一定范围内查找.

贡献

1、通过快速的随即近似算法，计算两个相斥图片区域的最近邻区域。
2、结构化图片的编辑框架，(image retargeting,completion,reshuffling)。
3、直接的交互控制，使得能得到理想的创作结果。

---

最近邻搜索

对于T中的每个patch，都要在S中找到最匹配的对应patch。ANN输出的就是一张记录对应位置的偏移矩阵--offsetmap。
由于两张照片大小一样，只需要记录patchA对应patchB的偏移量即可。
最近邻算法的精妙在于：其利用了如果在S中找到的PatchA与target的PatchB相匹配，那么PatchB周围的区域也很可能与PatchA周围的区域相匹配，即图像的局部相关性。
如下图所示：

1、片段最初的随机分布
2、蓝色的patch检查红色紧邻和绿色近邻，看是否它们会提升蓝色的匹配，生成更好的匹配
3、该patch随机搜索同心圆区域，进一步改进

---

基本概念

patch 块

图像一片正方形的区域，如3x3,5x5,此为PatchMatch算法的最小操作单位。作为一个块，其比单个像素所包含的信息更多，因此更好用。

reshuffle 图像重组

reshuffle将一张图片进行重新组合，如将右上角的塔贴到左边，实质更自然。

图1中可以看到塔的边缘有很明显的边界，为了消除边界，需要进行边缘的融合等操作来完成，一般方法有解泊松方程。PatchMatch中的reshuffle并不解方程，而是找到边缘部分与图片其他部分最匹配的（match）区域，利用此区域来填补边界，达到自然的效果，结果图2。

参考:
PatchMatch核心算法（一)
PatchMatch算法
PatchMatch分析
Patchmatch算法简单实现
PatchMatch github代码实现