The objective of this assignment is to implement the image quilting algorithm for texture synthesis and transfer, as outlined in the seminal SIGGRAPH 2001 paper by Efros and Freeman. Texture synthesis involves generating a larger texture image from a small sample by sampling patches and arranging them in overlapping patterns, ensuring the overlapping regions are similar. When perfect matches are not possible, edges may appear in the texture, which are mitigated by computing a seam through pixels with similar intensities in the overlap. Texture transfer extends this concept to give an object the appearance of the texture sample while preserving its original shape, by ensuring sampled patches match both the target image and the overlapping regions. This project integrates essential techniques like template matching, seam finding, and masking, which are fundamental in applications such as image stitching, completion, retargeting, and blending, demonstrating their broad relevance in computational photography and computer graphics.
In this step of the project, I implemented the `quilt_random` function, which generates a synthesized texture by randomly sampling square patches from a given sample image and arranging them to fill an output image of a specified size. The function takes in the sample image, the desired output size, and the patch size as inputs. Starting from the upper-left corner, it tiles the sampled patches sequentially, leaving black borders at the edges if the patches do not fit evenly into the output dimensions. This approach, while straightforward, is the simplest and least effective method for texture synthesis, as it does not ensure continuity or seamless blending between adjacent patches. Nonetheless, I saved the result from this method to use as a baseline for comparison with more advanced techniques in subsequent steps.
In this phase of the project, I implemented the quilt_simple function, an enhancement over the random quilting method, designed to produce a more seamless synthesized texture. This function constructs the output image by sampling square patches from a given texture sample while accounting for overlapping regions between patches. Starting with a random patch for the upper-left corner, subsequent patches are placed with horizontal and/or vertical overlaps, depending on their position in the output grid.
To evaluate potential patches for placement, I created two helper functions: ssd_patch and choose_sample. The ssd_patch function computes the cost of a patch based on the sum of squared differences (SSD) between the overlapping regions of the output and sample patches. Using a masked template approach, the SSD is efficiently calculated with filtering operations to determine the best matches. The choose_sample function selects a patch from the sample image by considering the costs and randomly picking one from among the lowest costs, as controlled by a tolerance parameter (tol). This allows for balancing deterministic and stochastic texture generation.
Once a patch is selected, its pixels are copied into the corresponding position in the output image. Care was taken to debug alignment, ensuring that overlapping regions in the output matched their computed SSD costs. I validated the implementation by generating small textures with a low tolerance (tol=1) to verify partial copying of the input texture and saved results with higher tolerance to demonstrate stochastic texture synthesis. This method significantly improves on the random approach, yielding textures with smoother transitions between patches.
In this step, I implemented the quilt_cut function to further refine the texture synthesis process by incorporating seam finding, addressing edge artifacts that arise from overlapping patches. This method builds on the previous quilt_simple function by minimizing visible seams in the overlapping regions of adjacent patches.
The key enhancement involves using the provided cut function, which computes the minimum-cost contiguous path through a region based on the boundary cost (bndcost). The cost is calculated as the squared differences (summed over RGB channels for color images) between the output image and the newly sampled patch in the overlapping areas. For patches with overlaps on both the top and left, two seams are computed—one for the vertical overlap and one for the horizontal overlap. The final mask for blending is derived from the intersection of these two seam masks using logical operations.
To integrate the seam finding into the quilting process, I modified the overlapping regions of each patch to follow the optimal paths determined by the cut function. Vertical seams were handled by transposing the boundary cost before applying the cut, ensuring flexibility for both horizontal and vertical directions. The result was a much more visually appealing synthesized texture, with reduced edge artifacts and smoother transitions between patches. By comparing the output of quilt_cut to the earlier methods, it was evident that seam finding significantly enhanced the quality of the texture, providing a more seamless and realistic result.
For the final task, I implemented the texture_transfer function, which adapts the quilt_cut method to perform texture transfer by incorporating guidance from a pair of sample and target correspondence images. This function allows for synthesizing textures that not only maintain the properties of the source texture but also align with the structural features of the target image, as described in section 3 of the paper.
The main enhancement in this function is the introduction of an additional cost term. While quilt_cut focused on minimizing edge artifacts in overlapping regions, texture_transfer adds a penalty based on the difference between the sampled source patch and the corresponding region in the target image at the same location. This ensures that the resulting texture aligns with the shape and structure of the target, enabling a more meaningful transfer of texture.
The function calculates the overall cost for each potential patch as a weighted combination of the boundary cost (used in quilt_cut) and the appearance cost from the target correspondence. By adjusting the relative importance of these terms, the texture synthesis can balance between preserving the source texture's characteristics and adhering to the target's structure. The patches are then sampled and blended using seam finding, as in quilt_cut, ensuring smooth transitions between adjacent patches. The resulting output preserves the visual coherence of the source texture while effectively transferring it onto the target image. This method demonstrates the versatility of texture synthesis techniques and highlights how adding context-aware cost terms can guide the process to produce tailored, visually compelling results.
