Image Quilting 🧶

This project implements the image quilting algorithm from the SIGGRAPH 2001 paper by Efros and Freeman. The goal of texture synthesis is to generate a larger texture image from a small sample, while texture transfer involves applying a given texture to an object while preserving its original shape. The technique relies on sampling patches and arranging them with overlapping regions.

Part 1: Randomly Sampled Texture

First we developed a random sampling function, quilt_random(sample, out_size, patch_size), which extracts small patches from an input image and arranges them as tiles to construct a larger image.

Original samples

Results (out_size = 200, patch_size = 15)

Part 2: Overlapping Patches

We developed an overlapping patches method, quilt_simple(sample, out_size, patch_size, overlap, tol), which generates an output image of size out_size by randomly sampling square patches of size patch_size from a given sample. This method uses two helper functions:

• ssd_patch(T, M, I): Computes the sum of squared differences (SSD) between a template (T), mask (M), and image (I) for each color channel.
• choose_sample(cost, tol): Randomly selects patch indices from among the lowest-cost values based on a tolerance (tol).

The quilt_simple function synthesizes the final image by iteratively selecting and placing patches into the output based on the minimum SSD and the overlap parameter. The result is a "quilted" texture with reduced visible seams compared to purely random sampling. While the seams remain slightly noticeable on close inspection, this approach significantly improves the quality of the synthesized texture.

Results (overlap_size = 11, patch_size = 25, tol = 3)

Part 3: Seam Finding

After implementing the overlapping patches method, the next step is to reduce and minimize the appearance of edge artifacts that commonly occur when using overlapping patches. To address this, we implemented a seam finding technique to minimize the visual seams between overlapping patches.

The seam finding process tackles edge artifacts by addressing the horizontal and vertical seams between two overlapping patches. We employ a min-cost algorithm based on dynamic programming, where the resulting minimum-cost path helps generate a mask that determines which pixels should be overlapped.

We created the quilt_cut(sample, out_size, patch_size, overlap, tol) method to integrate seam finding into the patch synthesis. The quilt_cut algorithm initializes the result image and selects a random initial patch from the input texture. It then defines masks for the top, left, and other regions of each patch. The function processes patches row by row and column by column, applying seam finding at each step to update the result image with reduced visible seams. This process significantly enhances the visual quality of the synthesized image, making the seams less noticeable and producing a more cohesive output.

Results (overlap_size = 11, patch_size = 25, tol = 3)

Zooming into the Seams

Here are two sampled patches where the left has already been placed and the right has been chosen by ssd_patch (first two images). It then shows the seam mask that is calculated as well as the final min cut result respectively.

Part 4: Texture Transfer

Finally, we explored texture transferring, which utilizes the quilt_cut function for texture synthesis with respect to a target reference image. The texture_transfer function takes parameters (sample, patch_size, overlap, tol, guidance_im, alpha)

In this function, we initialize masks for the left, top, and corner regions and then iteratively process patches in rows and columns. For each patch, the SSD is computed between the overlapping patches in the sample and the corresponding patches from the reference image. The resulting alpha-weighted sum of these costs is used to guide the selection of new patches. We also incorperate the seam finding for a smoother transition between texture patches.

Result 1: Feynman + sketch texture

Result 2: Michelle + toast texture

Result 3: Duck + large brush strokes