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 matching, finding 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.
Texture 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
100 sampled blocks of a fixed size (e.g. 50×50) from the input sampleThe next animation shows how the large output texture gets created (100 times larger than the input sample texture) with the quilting algorithm.
Output Texture (10×10 times larger than the input) created with texture synthesis (quilting)
Input Texture
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
Output Texture (25 times larger than the input) created with quilting
Input Texture
Output Texture (25 times larger than the input) created with quilting
Input Texture
Output Texture (25 times larger than the input) created with quilting
https://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
Output Texture (12 times larger than the input) created with quilting
Input Texture
Output Texture (25 times larger than the input) created with quilting
Input Texture
Output Texture (25 times larger than the input) created with quilting
Input Texture
Output Texture (36 times larger than the input) created with quilting
Input Texture
Output Texture (9 times larger than the input) created with quilting
Input Texture
Output Texture (25 times larger than the input) created with quilting
Input Texture
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
Output Texture (9 times larger than the input) created with quilting
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)
Target Image
Output Image after Texture Transfer
Input Texture (milk)
Target Image
Output Image after Texture Transfer
The following figure show the output image obtained when a few textures were transferred to my image.
Target Image (me)
Input Texture (fire)
Output Image after Texture Transfer (with small block size)
Input Texture (cloud)
Output Image after Texture Transfer (with small block size)
Input Texture (toast)
Output Image after Texture Transfer (with small block size)
Input Texture
Output Image after Texture Transfer (with small block size)
Input Texture
Output Image after Texture Transfer (with small block size)
The following animation shows how the milk texture is being transformed to the target image with the quilting algorithm with modified code.
Input Texture
Target Image (me)
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.
Recent Comments