[论文阅读]Image Quilting for Texture Synthesis and Transfer

《计算机图形与图像处理》课程阅读论文——  Image quilting for texture synthesis and transfer

Alexei A. Efros and William T. Freeman. 2001. Image quilting for texture synthesis and transfer. In Proceedings of the 28th annual conference on Computer graphics and interactive techniques (SIGGRAPH ’01). Association for Computing Machinery, New York, NY, USA, 341–346. 

---

目录

1.image quilting

2.this paper

3.previous work

4.quilting:patch-based synthesis procedure

5.Texture transfer

 

1.image quilting

a new image is synthesized by stitching together small patches of existing images.(将已有图像的小块拼接在一起，合成出新的图像) 

2.this paper

• Texture synthesis algorithm
  • Such an algorithm should be able to take a sample of texture and generate an unlimited amount of image data which, while not exactly like the original, will be  perceived by humans to be the same texture.(提取纹理样本-->生成无限数量的图像数据-->与原图像不同但会被感知为相同的纹理)
  • Main idea:synthesize new texture by taking patches of existing texture and stitching them together in a consistent way.(把现有的纹理以一致的方式拼接在一起生成新的纹理)

    

• Texture transfer-->rendering an object with a texture taken from a different object.(使用来着另外一个物体的纹理来呈现当前物体)

  

3.previous work

(1)Bela Julesz

• Two texture images will be perceived by human observers to be same: some approprite statistics of these images match.（当两幅纹理图像的统计数据相匹配时，人类观察者认为他们是相同的）
• Two tasks in statistical texture synthesis
  • Picking the right set of statistics to match(选择匹配的统计数据集)
  • Finding an algorithm that matches them（找到匹配的算法）

(2)Heegr and Bergen

• Analyze texture in terms of histogram of filter responses at multiple scales and orientations.(根据多个尺度和方向的滤波器响应直方图分析纹理)
• Matching these histograms iteratively-->produce synthesis results for stochastic textures.(迭代匹配直方图-->产生随机纹理合成结果)
• Problem:statistics do not capture important relationships across scales and orientations-->fail for more structured texture.(统计数据不能捕获垮尺度和方向的重要关系，因此算法在更加结构化的纹理数据中表现不好)
• Improve:Portliia and Simoncelli-->use more complicated optimization procedure.

(3)start with an input image and randomize it in such a way that only the statistics to be matched are preserved.(随机化输入图像，只保留匹配的统计信息)

• De Bonet:scramble the input in a coarse-to-fine fashion,preserving the conditional distribution of filter outputs over multiple scales.(以从粗到细的方式打乱输入，在多个尺度上保持过滤器输出的条件概分布)
• Xu el.al:take random square blocks from the input texture and place them randomly onto the synthesized texture.(从输入纹理中随机选择方块并将其随机放到合成纹理中)-->the arrangement of pixels within each block are statistics being preserved.(每个块内的像素排列作为统计信息被保留)

(4)enforce statistics locally, one pixel at a time.

• Efros and Leung:growing texture using non-parametric sampling
  • For a pixel: given all its neighbrs synthesized so far-->searching the sample image and finding all similar neighborhoods to estimate conditional distribution.(对于一个像素，给定到目前为止已经生成的所有邻域，通过搜索样本图像和寻找相似邻域来估计条件分布)
  • Produces good results for a wide range of textures,but is excruciatingly slow.

 

4.quilting:patch-based synthesis procedure

• Quilting

给定已经生成的square block： 和输入图像中的quare blocks：-->合成

 

(a)：simply tile it with blocks taken randomly from (从输入图像的square blocks中随机选择一个block作为，并将其放在右边)

(b)：given the overlap region,searching the input image and finding the most similar square block.（根据给定的重叠区域，从中选择与重叠区域最相似的block作为，并且以重叠区域的中间线为划分，左边使用的像素值，右边使用的像素值）

(c)：look at the error in the overlap region between it and other blocks--->find a minimun cost path through that error surface.(计算重叠区域的误差，找到最小代价的路径将其作为新的边界)

• Dynaminc programming （使用动态规划算法）
• Given block:      Overlap region:    
  • Error surface:   
  • Cumulative minimum error:  
• The minimun value of the last row in E will indicate the end of the minimal vertical path through the surface -->trace back and find the path of the best cut(E最后一行的最小值是通过曲面的最短路径的终点-->通过回溯找到最短的路径)
• Similar procedure can be applied to horizontal overlaps.(使用相同的过程可以找到水平重叠区域的最短路径)

 

• The image quilting algorithm(完整的算法流程)

• Pick size of block and size of overlap.(选择square block和重叠区域的尺寸)
  • In the paper, the size of the overlap was 1/6 of the size of the block（在论文的实验中，重叠区域的尺寸是square block的1/6）
  • The size of block depends on the properties of a given texture（square block的尺寸取决于给定纹理的属性）
  • Big enough-->canpture the relevant structure,small enough-->the interaction between these structures is left up to the algorithm.(足够大-->捕获纹理特征，足够小-->使得结构之间的相互作用取决于算法)

• Go through the image to be synthesized in raster scan order in steps of one block.（以光栅扫描顺序遍历待合成的图像）

  

 

• Search the input texture for a block that satisfy the overlap sonstraints(above and left).(从输入纹理中选择能够满足重叠约束的块)
• Find the minimum cost path and make the boundary of the new block.Paste the block onto the texture.(根据两个block计算误差，找到最短路径代价对应的路径，使其作为block的边界，然后将新的block粘贴到纹理上)
• Repeat.

 

• Result 

• The algorithm is particularly effective for semi-structure textures,the performance is quite good on stochastic texture.(算法在半结构纹理和随机纹理图像中表现良好)
• Problem:excessive repeatition(过度重复)、mismatched or distorted boundaries(不匹配和边界扭曲)

  

 

5.Texture transfer

使用source image的纹理来呈现target image的纹理

 

(1)The corrrespondence map is a spatical map of some corresponding quantitiy over source image and target image. That quantity could include image intensity, blurred image intensity, local image orientation angles, or other derived quantities.(原图像和目标图在某些量的空间映射-->对应图，这些量可能是图像强度、模糊图像强度、局部图像方位角或者其他导出量)

 

(2)error term

????(The block overlap matching error)+(1-????)(the square error between the correspondence map pixel within the source texture block and those at the current target image position)

????倍的重叠区域匹配误差+(1-????)(原纹理块的对应映射像素与目标位置的对应映射像素的平方误差)

 

(3)iteratice scheme

• Sometimes one synthesis pass through the image is not enough to produce a visually pleasing result.(一次合成不能生成视觉上满意的结果)
• Start using large block-->smaller block（使用尺寸较大的block-->尺寸较小的block）
• Use N=3 to N=5 iterations, reducing the block size by a third each time.（3-5次迭代，每次block的尺寸减少1/3）
•