12,627,377 members (37,708 online)
Add your own
alternative version

108.4K views
2.1K downloads
37 bookmarked
Posted

# Texture Transfer using Efros & Freeman's Image Quilting Algorithm

, 11 Mar 2008 CPOL
 Rate this:
Please Sign up or sign in to vote.
A texture transfer program that implements Efros & Freeman's texture transfer algorithm

## 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 d1, d2 that quantify how well criterion 1 and 2 above are satisfied and their weighted sum

• d = (1-a)d1 + ad2

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.

## License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

## About the Author

 Software Developer United States
Creator of bookmine.net

## You may also be interested in...

 Pro Pro

## Comments and Discussions

 First Prev Next
 question: is iteration used for refining the texture transfer result? HCYU29-Jan-09 7:23 HCYU 29-Jan-09 7:23
 Re: question: is iteration used for refining the texture transfer result? SIDDHARTH JAIN (fd97207)29-Jan-09 7:32 SIDDHARTH JAIN (fd97207) 29-Jan-09 7:32
 Re: question: is iteration used for refining the texture transfer result? HCYU29-Jan-09 9:10 HCYU 29-Jan-09 9:10
 Re: question: is iteration used for refining the texture transfer result? Member 826253020-Apr-12 12:54 Member 8262530 20-Apr-12 12:54
 Cool pictures Roberto Collina26-Aug-08 0:58 Roberto Collina 26-Aug-08 0:58
 Very Slow Aamir Mustafa8-Mar-08 2:20 Aamir Mustafa 8-Mar-08 2:20
 Re: Very Slow SIDDHARTH JAIN (fd97207)8-Mar-08 5:46 SIDDHARTH JAIN (fd97207) 8-Mar-08 5:46
 Re: Very Slow Wong Shao Voon17-Mar-08 0:55 Wong Shao Voon 17-Mar-08 0:55
 Re: Very Slow SIDDHARTH JAIN (fd97207)17-Mar-08 7:37 SIDDHARTH JAIN (fd97207) 17-Mar-08 7:37
 Tidy the article formatting norm .net6-Mar-08 22:08 norm .net 6-Mar-08 22:08
 Re: Tidy the article formatting SIDDHARTH JAIN (fd97207)7-Mar-08 8:44 SIDDHARTH JAIN (fd97207) 7-Mar-08 8:44
 Source Code Not Available Aamir Mustafa6-Mar-08 20:51 Aamir Mustafa 6-Mar-08 20:51
 Re: Source Code Not Available `leppie`6-Mar-08 21:35 `leppie` 6-Mar-08 21:35
 Last Visit: 31-Dec-99 19:00     Last Update: 6-Dec-16 2:03 Refresh 1

General    News    Suggestion    Question    Bug    Answer    Joke    Praise    Rant    Admin

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Terms of Use | Mobile
Web02 | 2.8.161205.3 | Last Updated 11 Mar 2008
Article Copyright 2008 by SIDDHARTH_JAIN
Everything else Copyright © CodeProject, 1999-2016
Layout: fixed | fluid