Project 6 (extra): Texture Assigned : -- Due : --   March/April S M T W T F S 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 1 2 3 4 5

Quick Links

1. Lecture notes texture synthesis
2. Project 2 grading scheme
3. Project 2 grading images
4. X-Win32 official homepage
5. Displaying X applications to PC running X-Win32
6. Sample solution (only runs on Linux!)
7. Sample texture (parameters: window size=11, sigma = 10.0, sampling distance = 1, epsilon = 0.10)
8. Qt all class
9. Texture library
10. bitmap.h bitmap.cpp (use this or QImage to load image, updated Mar 6, 2007)
11. Algorithm description (read section 2.1)

Project Description

Texture synthesis algorithm

The algorithm can be summarized as below:

1. Randomly choose a 3x3 patch in the sample image and place it in the middle of the new image.

2. Find all the boundary points.

3. For each boundary point,

    3.1. Calculate the distance to each sample point using normalized sum of squared differences.

    3.2. Pick all the samples that have distance less than (1+e)d_min.

    3.3. From those samples selected, randomly pick one as the color of the new synthesized pixel.

4. Repeat step 2 until all the pixels are synthesized.

Two-dimensional Gaussian kernel

You can let G = exp( -(x² + y²) / s² ) where (x, y) is the position and s is the standard deviation. If white represent 1 and black represent 0, the Gaussian kernel will look like the following if you view it as an image.

s = 5     s = 10     s = 15     s = 20

Sum of squared differences

To calculate the distance of two images, all you need to do is to calculate the difference of each corresponding pixel and sum all the differences to get the distance. Let the color of two corresponding pixels be (R₁, G₁, B₁) and (R₂, G₂, B₂). Then the difference is (R₁-R₂)² + (G₁-G₂)² + (B₁-B₂)².

To give more weight to the nearby pixels, remember to multiply the corresponding value of the Gaussian kernel at each pixel.

Implementation Details

Step 1

Easy.

Step 2

This step is easy, the boundary points of the current synthesized image are all the pixels that

    1. its color is equal to the background color, and

    2. there exist one or more pixels in its 8-neighbour that is not a background pixel

Step 3.1

This step is the core part of the algorithm and you may spend most of your time on it.

First, you need to know where does your sample point come from. As stated in the paper, the sample points are simply all the pixels on your original image. To avoid exceeding the image boundary when calculating the distance, you can exclude the pixels within half of the window size near the boundary.

Next, you have to find the distance of all the sample points to your current synthesizing pixel. Here we will talk about the details on how to find the distance of one sample point.

The green square in the above images is your window and its width is equal to the window size. In the sample image, the window is centered at the sample point and the window is centered at the current synthesizing pixel in the current synthesized image. To calculate the distance, first you have to find the difference of the two sub-images formed by the two windows. However, there are some background pixels in the current synthesized image. All you need to do is to ignore them in the calculation, that is, you only needed to take the difference at the pixels in the red region shown above. After that, add 1 to the difference to make it non-zero.

After taking the difference (using sum of squared difference stated above), you will have a number at each pixel in the red region. Now, imagine that the center of the Gaussian kernel is moved to align with the center of the window (shown as above). Then you need to multiply the corresponding value in the Gaussian kernel to the difference at the corresponding pixel in the window. Doing this will give a higher weight to the pixels that are closer to the current synthesizing point. Summing all the value at each pixel gives a single number that represent the distance between the two red regions.

The final goal is to find the distance between two windows (the final distance you want). Since there exist some background pixels in the synthesized image, we will use an approximation by normalizing the distance of the two red regions. For example, if your window size is 21 x 21 = 441 pixels and you have 100 pixels in the red region, divide the distance of the two red regions by (100 / 441) to get the final distance.

Step 3.2

After Step 2.1, you obtain the distance for each sample point. Among these samples, there will be one sample that has the minimum distance (most likely to be the color of the synthesizing pixel). To make the synthesized image different from the original image, we select the samples which have distance less than (1+e)d_min as the candidates for the color.

Step 3.3

Easy.

Project Requirement

Your program should

1. be able to load a sample image (BMP) and save the synthesized image (BMP).
2. contains some UI to change the parameters of the algorithm (window size, sigma, epsilon, background color).
3. output a bitmap file called "result.bmp" for every 100 pixels you synthesized.
4. of course, implement the algorithm correctly.

If you have any difficulties in understanding the project requirement, please take a look at the sample solution.

Hints

1. Make sure you understand the algorithm before implementation.
2. Read Qt documentation. Here are some classes that you may need to use, QPainter, QPixmap, QImage, QLabel, QSlider, QPushButton, QVBox, QHBox, QFileDialog.
3. Separate the implementation of your algorithm and the UI.
4. Do your project earlier because the algorithm is slow and you need more time to wait for the result.
5. You are not required to implement the status bar and timer in your program (I implement it for fun).
6. You may find that your program looks hanged when you start the algorithm. It is normal because I used some techniques you didn't learn before.
7. Create some simple texture by your own to test your program before running real textures.
8. See the example code in Qt API if you still have difficulties in understanding the Qt API.
9. Test and fix all the bugs before submission.

Grading Scheme

A main objective of this course is to learn and practice good design principles so that you can eventually write very large programs comfortably and professionally. As such, you should not just turn in a program that works. You are expected to have a good design too so that your program is comprehensible and can be extended easily in case the specification changes later. Whether you like it or not, it is a fact in life that user requirements keep changing while a program is being developed. Your design should be flexible enough to cater for such possibilities. You should describe your design clearly in a separate file, named README.txt.

As it is always the case, you should use meaningful identifier names in your program so that other people can understand your code easily. You are also expected to break your program into functionally distinct pieces kept in different files, with the C++ source files compiled separately. Brief yet informative comments should be added throughout the program to improve its comprehensibility.

The grading scheme is as follows:

• Program correctness in satisfying specification (70%)
• Object-oriented programming style and use of separate compilation (15%)
• Documentation and comprehensibility (15%)

What to submit

1. All the source code (.cpp and .h), but not the object code or executable
2. Makefile and README.txt
3. Zip (1) and (2) inside a zip file (use the "zip" command in Unix) and upload your texture.zip before 23:59 on the due date
   Warning: If your submitted project fails to compile, or you put your zip file in the wrong directory (note that the Unix filenames are case-sensitive), your assignment will be treated as late (late policy will apply).