纹理合成论文解读(附PPT):Image Quilting for Texture Synthesis and Transfer

0. Sources

原文：Efros A A, Freeman W T. Image quilting for texture synthesis and transfer[C]//Proceedings of the 28th annual conference on Computer graphics and interactive techniques. 2001: 341-346.

paper pdf:

https://dl.acm.org/doi/abs/10.1145/383259.383296

Matlab code:

http://jmecom.github.io/projects/computational-photography/texture-synthesis/

1.背景

纹理合成是用少量的源纹理样本生成大片的纹理图案，这在纹理渲染中可以节省大量的工作量。本文提出了一种图像缝合（Image Quilting）的算法来实现此目的，图像缝合，字面意思就是把小块的图像补丁像拼图游戏一样无缝衔接到一起，拼成一块大纹理。如下图所示：

顺便一提，本文是纹理合成领域非常经典的一篇文章，它甚至还启发了后来的patch-based的图像修复算法系列，以至于几乎每篇图像修复的论文都会引用本文。

最后，本文算法还可以实现纹理迁移（Texture Transfer），例如下图融合了米饭的纹理和人脸的结构，生成了人脸形状的米饭图：

2. 缝合算法（Quilting）

下面介绍本文算法的无缝缝合，其实非常简单：

就是在（2）的基础上，把重合部分的直线切割改进为曲线切割，如图3（c）所示，这一切割称为最小误差切割。在重合区域内，分割线左侧取B1，右侧取B2，这样可以最大程度地保证B1到B2纹理的连续性。那么现在问题的关键就是这一刀是如何切割出来的，我们以图3（c）为例说明这一过程：

记B1，B2重叠部分为 ，(ov代表overlap)，如图4（a）所示。那么两者之间的差异定义为 ，如图4（b）所示。现在我们要在重叠区域找一条从上边缘到底部边缘的路径，该路径每一步只能选择往左，往下或往右走一格。要求该路径经过的像素的累计误差最小，该路径正是所求的最小误差切割。这可以用迪杰斯特拉最短路径算法或动态规划求解。图4（b）中红线标出的路径就是累计误差最小的最佳分割线，切割结果见图4(c），这两片纹理拼在一起肉眼几乎察觉不出缝隙。

上面讲完了第一行patches的缝合，那么对于第一列patches，它们的重叠部分位于上下侧，思路也是类似的，只不过切割变成水平方向的而已；

对于不在第一行也不在第一列的绝大多数patches，它们的重叠部分位于左侧和上侧，此时需要分别计算竖直和水平的切割线，设两条切割线相交于一点，以该点为界，丢弃掉两条割线的末端（图5虚线），其余部分融合成一条总的割线（图5实线），总割线的右下侧取当前patch的像素，其余取已有区域的像素。

算法流程小结

循环：按光栅顺序遍历待合成图像，步长为一个patch的尺寸减去重叠宽度
    - 在每个位置，在输入的源纹理中搜索一系列满足重合区域相似度约束的候选样本块，从中随机选取一个。
    - 计算已有区域和所选patch重合部分的误差，并计算穿过重合部分的最小累计误差割线，粘贴所选patch分割后的新纹理。
结束循环

参数选取细节：

• patch的尺寸由用户指定，因图而异，不能太小，否则无法捕捉纹理结构，但也不能太大，否则纹理样本数量减少，合成纹理的随机性会变差。

• 作者推荐重合区域的宽度取patch尺寸的1/6。

• 重合区域相似度约束为：待选纹理块在重叠部分的误差和最佳匹配误差的差距在10%以内。

3. 部分缝合结果展示

过去的纹理合成算法会逐个像素地创建新的纹理，但 Efros 和 Freeman 注意到大多数像素本质上是由先前选择的像素预先确定的。相反，纹理应该用更大的单位生成，我们称之为块。

该算法为左上角选择一个随机块。对于下一个可以放置的每个新潜在块，我们评估现有块和新块重叠之间的误差。使用简单的平方差总和来评估误差。该块是在最佳匹配块的某个用户定义边界内的块中随机选择的。以这种方式随机选择块可以防止重复选择相同的块。这个过程一直持续到整个所需的输出图像被填满。

演示算法的伪代码如下：

for i = number of rows to fill  for j = number of columns to fill    if i==1 and j==1      choose a random block    else if i==1    # first column      for each possible block in source image        evaluate top edge overlap error    else if j==1    # first row      for each possible block in source image        evaluate left edge overlap error    else       for each possible block in source image        evaluate top and left overlap errors  pick a random block out of set of potential matches  perform minimum boundary cut  place the chosen block in the output image

算法的运行时间取决于纹理的大小、所需的输出图像和块大小。在 2011 年的 Macbook Pro 上，大约 125 像素 x 125 像素的图像、20 块大小以及大约 250 像素 x 250 像素的输出图像大小平均需要 25 秒才能完成。

我们最大的挑战是了解对块进行采样的最佳方式。我们都假设样本纹理中的块应该有规律地间隔。相反，可以从样本纹理的任何点获取块。这个错误让我们困扰了大约一天，但在修复此错误后，我们轻松地完成了实验室的这一部分。

我们的图像绗缝实现的结果如下。显示原始源纹理，然后是没有最小边界切割的图像绗缝，最后是具有最小边界切割的图像绗缝。

4. 纹理迁移（Texture Transfer）

纹理迁移就是，利用源图像的纹理作为原料，仿照目标图像的结构合成新的图像，新的图像整体观感看起来像目标图片，但是内容却来自于源图片。合成图片和目标图片尺寸是一致的，但不必和源图尺寸一致。如下图所示：

看起来很厉害，但其实也很简单。只要理解了纹理缝合的过程，纹理迁移就很好理解了——就多了一项约束而已。

纹理缝合在选取候选样本块的时候，需要在重合部分满足一定的相似度约束，以保证合成的纹理过度平滑。在纹理迁移中，除了该相似度约束以外，还需要满足一致性约束（correspondence constraint）。该一致性约束又增加了一个筛选条件：只有特定属性和目标图对应位置相似的纹理块才能成为候选纹理块，这里的特定属性包括不限于：灰度值、高斯模糊后的灰度值（抗噪）、梯度以及其它统计特征。一致性约束是为了让合成图片的观感和目标图片相似。

我们以上图来说明该项约束，在本例中选用的是亮度判据：当我们在合成图中遍历到红框所在的位置时，显然这个位置需要和目标图红框位置相似，由于目标图在这个位置亮度很低，因此源图像中只有那些亮度也很低纹理块（比如标红的三个红块）的一致性误差就比较低。

总的来说，我们将重叠区域误差约束和一致性约束通过加权融合形成一个总的约束，用以调节两者的平衡，只有总误差在一定阈值以下的纹理块才有资格成为候选：

然而作者指出，一次遍历不能获得比较满意的纹理迁移效果。如果要想获得更好的效果，应该遍历3-5次，作者提供了多次遍历的一些实现细节：

• 在第二次遍历（含）以后，迭代在上一次合成结果的基础上进行，具体体现在计算纹理匹配误差的时候，候选块的筛选除了需要和当前遍历的邻居计算重叠区域误差之外，还需要和上一次合成结果在当前位置计算匹配误差。

• 随遍历次数的增加，纹理块的尺寸应该越来越小以满足由粗到精的纹理合成（纹理块尺寸每次迭代减少1/3）；

• 随遍历次数的增加，也应该越来越小以增大一致性约束的权重，促进合成图和目标图的相似（第i次迭代的取  ，其中N是迭代总次数）。

使用上述多次遍历的策略，作者称纹理迁移可以达到非常好的效果。本文内容到此结束。

PPT附件：