Texture Transfer using Efros & Freeman's Image Quilting Algorithm

• Download Source code version 1 (uses BackgroundWorker) - this is the recommended version to use - 191 KB
• Download Source code version 2 (uses Task Parallel Library) - new code added on 7/26/10 - 86.62 KB

Introduction

This article describes a texture transfer program I developed based on Efros & Freeman's SIGGRAPH 2001 paper:

• Image Quilting for texture synthesis and transfer: pdf, ppt

Texture transfer is the process by which the texture of a source image is transferred to a target image. The result is that we get an image that looks like the target image but it is made out of the texture of the source image e.g. below are shown two images -- source, target and the result of transferring the texture of the source onto the target:

source		target		first iteration		second iteration		third iteration

The source is an image of rice and the target is the man's face. After texture transfer we get a face that looks as though it is made out of rice. How do we do this? The idea is to take patches of rice and weave them together seamlessly into the image of the face. Bright patches of rice will goto areas where the face is bright and dark patches will goto areas where the face is dark. To illustrate the concept, in the image below the boundaries of the individual patches have been colored in red. You can find each of these patches in the rice image if you look for them hard enough.

The Texture Transfer Algorithm

The texture transfer algorithm has to synthesize an image from the pixels of the source. Locally the result should have the appearance of the source texture but when looked at globally the result should look like the target. The texture transfer proceeds by synthesizing an image in faster scan order in units of block. You can control the size of the block in the setting window and it is set to 27x27 pixels by default. Whenever a block in the result has to be synthesized the algorithm needs to find a suitable block in the source texture that satisfies two criteria:

1. The block should match the target, meaning bright patches of rice should go to bright patches on the man's face.
2. After making some cuts, the block should fit in seamlessly with its adjoining neighbors so that we don't see any visual discontinuities and don't even realize that the result is actually made up of many blocks put size by side like a jigsaw puzzle.

To this end for every patch in the source image the algorithm computes two difference measures d₁, d₂ that quantify how well criterion 1 and 2 above are satisfied and their weighted sum

• d = (1-a)d₁ + ad₂

The algorithm chooses the patch that minimizes d. The function GetMatchingBlock in TextureTransferTool.cs does this computation. The next step after choosing a matching block is to cut it appropriately so that it fits in seamlessly with the adjoining neighbors. It is because of these cuts that the patches in figure have jagged boundaries. If no cuts were made the boundaries would be straight lines and we would get something that looked like following image:

The algorithm synthesizes the result in several passes or iterations starting with a low value of a (a=0.1) and initial block size set to 27x27 pixels by default and decreasing block size by 1/3 rd in every iteration and increasing alpha until a=0.9 in the final iteration. The number of iterations to do is set to 3 by default. The following code snippet from function OnDoWork in TextureTransferTool.cs shows the main texture transfer code. The texture transfer runs in a separate BackgroundWorker thread so that it does not block the UI thread from processing keyboard and mouse events.

for (int i = 0; i < numIterations; i++)
            {
                bool isFirstIteration = i == 0;
                // from Alyosha's paper
                double alpha = 0.8 * i / (numIterations - 1) + 0.1;     
                nextX = 0; nextY = 0; nextBlockWidth = blockWidth; nextBlockHeight = 
                    blockHeight; nextOverlapX = 0; nextOverlapY = 0;
                bool completed = false;
                while (!completed && !CancellationPending)
                {
                    Point q = new Point(nextX, nextY);  
                    // get matching block from src which will be pasted at location q in img
                    p = GetMatchingBlock(img, src, target, q, nextOverlapX, nextOverlapY,
                        nextBlockWidth, nextBlockHeight, alpha, isFirstIteration, probe,
                        out eh, out ev);                    
                    // the horizontal and vertical cuts will ensure that the patch
                    // from src will fit in seamlessly when it is pasted onto img
                    int[] Hcut = findHcut(eh);  // compute the horizontal cut
                    int[] Vcut = findVcut(ev);  // compute the vertical cut
                    // cut the block per the horizontal and vertical cuts and then
                    // paste it onto img
                    cutandpaste(src, p, img, q, Hcut, Vcut, nextBlockWidth,
                        nextBlockHeight, displayBoundaryCut);
                    // calculate how much of texture transfer is complete; 1->fully 
                    // completed
                    double fractionComplete = CalculateFractionComplete(i, numIterations, 
                        nextX, nextY, nextBlockWidth,
                        nextBlockHeight, imgWidth, imgHeight);
                    int percentComplete = (int)Math.Round(fractionComplete * 100);
                    // send progress report to UI thread
                    ReportProgress(percentComplete, new ProgressReport(fractionComplete, 
                        rgb.ToBitmap(img)));
                    // (nextX, nextY): coordinates of top left corner in img where next 
                    // block is to be synthesized;
                    // (nextBlockWidth, nextBlockHeight): dimensions of block to be 
                    // synthesized
                    // (nextOverlapX, nextOverlapY): the amount by which block will will 
                    // overlap neighbors completed: is this iteration complete
                    Next(X, Y, blockWidth, blockHeight, imgWidth, imgHeight, overlapX, 
                        overlapY, out nextX, out nextY, out nextBlockWidth,
                        out nextBlockHeight, out nextOverlapX, out nextOverlapY,
                        out completed);                    
                    X = nextX; Y = nextY;                    
                }
                if (CancellationPending)
                {
                    e.Cancel = true;
                    return;
                }
                X = 0; Y = 0;
                blockWidth = (int)Math.Round(blockWidth * blockReductionFactor);
                blockHeight = (int)Math.Round(blockHeight * blockReductionFactor);
                probeWidth = srcWidth - blockWidth;
                probeHeight = srcHeight - blockHeight;
                probe.Reset(probeWidth, probeHeight);
                overlapX = (int)Math.Round(overlapX * blockReductionFactor);
                overlapY = (int)Math.Round(overlapY * blockReductionFactor);
                if (overlapX >= blockWidth || overlapY >= blockHeight || blockWidth == 
                    0 || blockHeight == 0)
                    break;
            }

Steps to Perform Texture Transfer

• Step 1: Select source image. Note that only 24 bit RGB images are supported (most jpegs will fall in this category). Indexed images (most gifs fall in this category) are not supported.
• Step 2: Select target image. Note that only 24 bit RGB images are supported (most jpegs will fall in this category). Indexed images (most gifs fall in this category) are not supported.
• Step 3: (Optional) change settings if you have to. Clicking on the settings button will pop up a window that looks like this:

  

  Here is what the various parameters mean:

  • Number of iterations: the number of iterations to do
  • Block width: width of the block in the 1st iteration; units:pixels
  • Block height: height of the block in 1st iteration; units: pixels
  • Overlap in X: percentage of overlap along X dimension
  • Overlap in Y: percentage of overlap along Y dimension
  • Block reduction factor: percentage by which block size is reduced in each iteration. New block size = old block size * Block reduction factor
  • Fraction of source image to probe: Texture transfer is a time consuming process and can easily take a couple of hours for a large source and/or target. The code is not optimized for performance and is written for ease of use and understanding. By changing this setting it is possible to change the extent by which the source image is probed or searched to find matching texture blocks. When this parameter is set to 100% the entire source image is searched to find the matching block in function GetMatchingBlock. When the parameter is set to 10% only 10% of the source image is probed in a random fashion to search for a matching block. Thus the function GetMatchingBlock runs 10 times faster when this parameter is set to 10% vs. when it is set to 100%. Note that decreasing the amount to probe does not necessarily decrease the visual quality of the result but is guaranteed to speed up the texture transfer.
  • Display boundary cut: If this box is checked then the boundaries of the individual patches are colored in red
  • Difference metric: The program allows the user to select between two distance metrics when computing the difference between source and target:
    • Option 1: SSD (sum of squared differences) metric which computes the sum of squared R,G,B differences; see function Diff in rgb.cs
    • Option 2: Intensity difference squared which computes the square of the intensity difference; see function Diffi in rgb.cs
• Step 4: if you like the result you can save the resulting image by clicking on the "Save Result As" button. Note that it is also possible to save the intermediate results when the texture transfer is in progress using this button.

Results

In the following table I show some results I have obtained using the texture transfer program. These results are generated with amount to probe set to 10% and distance metric set to SSD. Note that the images have been resized to fit on the screen. Therefore if you download these images and run the program it is likely that you may not get the exact same results.

Source	Target	Difference=SSD; Amount to probe=10%

Wrap Up

This was a fun project for me as it introduced me to Computer Graphics and some neat features in C# 2.0 such as the BackgroundWorker class, dynamic layout and panels. I hope some of you find it useful in your work. Suggestions for improvement and bug reports are always welcome.

Updates & Revision history

3/7/08: I created this project using Visual C# Express Edition 2008 and have noticed if you attempt to open the solution using VS 2005 it gives an error message. If you encounter this just create a new project and add the source code contained in the zip file, compile and run. The only references you should need are System, System.Windows.Forms and System.Drawing.

3/11/08: Related links: Rob Burke's C# texture transfer code

7/26/10: I am attaching a zip file that has source code + Visual Studio Project for my texture transfer article. What I have done here is ported the application to use .NET 4.0 TPL (Task Parallel Library). My hope was that the application would run faster as it consumes all the CPUs of the machine. However, the new code's performance is only marginally better and in many cases even worse. Taking advantage of parallelism is no easy task, and full of gotcha's e.g. who knows maybe my new code is suffering from false sharing. But I would still like to upload this source code as a TPL tutorial, and maybe someone can make it faster.