Subscribe to DSC Newsletter

Some Computational Photography: Image Quilting (Texture Synthesis) with Dynamic Programming and Texture Transfer in Python

The following problems appeared as a programming assignment in the Computation Photography course (CS445) at UIUC. The description of the problem is taken from the assignment itself. In this assignment, a python implementation of the problems will be described instead of matlab, as expected in the course.

 

The Problems

  • The goal of this assignment is to implement the image quilting algorithm for
    texture synthesis and transfer, described in this SIGGRAPH 2001 paper by Efros
    and Freeman.
  • Texture synthesis is the creation of a larger texture image from a small sample.
  • Texture transfer is giving an object the appearance of having the
    same texture as a sample while preserving its basic shape.
  • For texture synthesis, the main idea is to sample patches and lay them down in overlapping patterns, such that the overlapping regions are similar.
  • The overlapping regions may not match exactly, which will result in noticeable
    edges artifact. To fix this, we need to compute a path along pixels with similar intensities through the overlapping region and use it to select which overlapping patch from which to draw each pixel.
  • Texture transfer is achieved by encouraging sampled patches to have similar appearance to a given target image, as well as matching overlapping regions of already sampled patches.
  • In this project, we need to apply important techniques such as template matchingfinding seams, and masking. These techniques are also useful for image stitching, image completion, image retargeting and blending.

 

Randomly Sampled Texture

First let’s randomly samples square patches of size patchsize from sample in order to create an output image of size outsize. Start from the upper-left corner, and tile samples until the image is full. If the patches don’t fit evenly into the output image, we can leave black borders at the edges. This is the simplest but least effective method. Save a result from a sample image to compare to the next two methods.

 

Overlapping Patches

Let’s start by sampling a random patch for the upper-left corner. Then sample new patches to overlap with existing ones. For example, the second patch along the top row will overlap by patchsize pixels in the vertical direction and overlap pixels in the horizontal direction. Patches in the first column will overlap by patchsize pixels in the horizontal direction and overlap pixels in the vertical direction. Other patches will have two overlapping regions (on the top and left) which should both be taken into account. Once the cost of each patch has been computed, randomly choose on patch whose cost is
less than a threshold determined by some tolerance value.

As described in the paper, the size of the block is the only parameter controlled by the user and it depends on the properties of a given texture; the block must be big enough to capture the relevant structures in the texture, but small enough so that the interaction between these structures is left up to the algorithm. The overlap size is taken to be one-sixth of the block size (B/6) in general.

 

Seam Finding

Next we need to find the min-cost contiguous path from the left to right side of the patch according to the cost. The cost of a path through each pixel is the square differences (summed over RGB for color images) of the output image and the newly
sampled patch. Use dynamic programming to find the min-cost path.

The following figure describes the algorithm to be implemented for image quilting.

f20.pngTexture Transfer

The final task is to implement texture transfer, based on the quilt implementation for creating a texture sample that is guided by a pair of sample/target correspondence images (section 3 of the paper). The main difference between this function and
quilt function is that there is an additional cost term based on the difference between
the sampled source patch and the target patch at the location to be filled.

Image quilting (texture synthesis) results

The following figures and animations show the results of the outputs obtained with the quilting algorithm. The input texture images are mostly taken from the paper .

Input sample Texture
q2.png

100 sampled blocks of a fixed size (e.g. 50×50) from the input sample
samples_q2.pngThe next animation shows how the large output texture gets created (100 times larger than the input sample texture) with the quilting algorithm.

quilt.gif

Output Texture (10×10 times larger than the input) created with texture synthesis (quilting)
quilt_q2.png

 

Input Texture

q6.png

Output Texture (25 times larger than the input) created with texture synthesis (quilting) with the minimum cost seams (showed as red lines) computed with dynamic programming

quilt_boundary_q6

Output Texture (25 times larger than the input) created with quiltingquilt_q6

 

Input Texture

q1

Output Texture (25 times larger than the input) created with quilting

quilt_q1_.png

Input Texture

q3

Output Texture (25 times larger than the input) created with quilting

quilt_q3.pnghttps://sandipanweb.files.wordpress.com/2017/10/quilt_q3.png?w=150 150w, https://sandipanweb.files.wordpress.com/2017/10/quilt_q3.png?w=300 300w" sizes="(max-width: 632px) 100vw, 632px" />

Input Texture

q4

Output Texture (12 times larger than the input) created with quilting

quilt_q4.png

Input Texture

q5

Output Texture (25 times larger than the input) created with quilting

quilt_q5.png

Input Texture

q7

Output Texture (25 times larger than the input) created with quilting

quilt_q7_.png

Input Texture

q9

Output Texture (36 times larger than the input) created with quilting

quilt_q9.png

Input Texture

q11

Output Texture (9 times larger than the input) created with quilting

quilt_q11_.png

Input Texture

q12

Output Texture (25 times larger than the input) created with quilting

quilt_q12.png

Input Texture

q13

Output Texture (9 times larger than the input) created with quilting along with the min-cost seams (shown as red lines) computed with dynamic programming 

quilt_boundary_q13

Output Texture (9 times larger than the input) created with quilting

quilt_q13

 

Texture transfer results

The following figures and animations show how the texture from an input image can be transferred to the target image using the above-mentioned simple modification of the quilting algorithm. Again, some of the images are taken from the paper.

Input Texture (milk)

q14.png

Target Image

qt1.png

Output Image after Texture Transfer

text_tran_q14

 

Input Texture (milk)

q14.png

Target Image

mona

Output Image after Texture Transfer

text_tran_q14_

 

The following figure show the output image obtained when a few textures were transferred to my image.

Target Image (me)

me1.png

 

Input Texture (fire)

fire.png

Output Image after Texture Transfer  (with small block size)

text_tran_fire

 

 

Input Texture (cloud)

cloud1.png

Output Image after Texture Transfer  (with small block size)

text_tran_cloud1

 

Input Texture (toast)
toast.png

Output Image after Texture Transfer  (with small block size)text_tran_toast

 

Input Texture
q7.png

Output Image after Texture Transfer  (with small block size)

text_tran_q7

 

Input Texture

draw.png

Output Image after Texture Transfer  (with small block size)text_tran_draw

 

The following animation shows how the milk texture is being transformed to the target image with the quilting algorithm with modified code.

Input Texture

q14

Target Image (me)

ttmea

 

The next figures and animations show the output image obtained after milk texture gets transferred to the target image of mine, for different block size of the samples(shown in red). As can be seen from the following outputs, the target image gets more and more prominent as the sampling block size gets smaller and smaller.

text_tran_036_q14

text_tran_804_q14

ttme

Views: 760

Comment

You need to be a member of Data Science Central to add comments!

Join Data Science Central

© 2019   Data Science Central ®   Powered by

Badges  |  Report an Issue  |  Privacy Policy  |  Terms of Service