This assignment is concerned with low-level vision.  Note that we recommend you to do this assignment in groups of two. However, you can also do it by yourself if you prefer.

In this assignment you will implement a non-parametric density estimation method that you will use for texture synthesis. You can benchmark the implementation against the images below.

It is important to note that the assignment is somewhat under-specified, in that you have some freedom in terms of choosing underlying parameters (e.g: the order in which points are considered, the exact weighting function, etc). However, it is important that your design choices be documented, so that we can understand them, and that they be deterministic so that results are reproducible. Therefore, any functions that make use of a random number generator will need to take a seed value as an input, and for any output that you show you must provide the seed value that generated it.

Your output should follow these same standards. To simplify the grading process, your code must run under Windows-XP. However, you will write straightforward C or C++ code, and can therefore do development on any platform that you wish. But the code you turn in must generate the results you show under Windows-XP.

What to turn in:  a) your source code b) Windows executable c) a write-up explaining how to run your program and an explanation of your design choices and results. You will submit these using CMS, the course management system.

Your programs will need to input and output files in PPM (color) format. You can obtain information on these file formats, as well as a number of libraries and tools, from the CS664 library page here.

Problem: Texture Synthesis. Implement Texture Synthesis by non-parametric sampling using the scheme suggested by Efros and Leung, as discussed in class. More precisely, your program should take the following command-line arguments:

Efros.exe input.ppm r startx starty width height output.ppm

Here, input.ppm is the name of the input image file, and output.ppm is the name of the output image file. The parameter r specifies the window to be used to predict the local estimate of the patch, which is a square of width 2r+1. The numbers (startx,starty,width,height ) specify a rectangle of size (width,height) whose upper left coordinate is at position (startx, starty). This rectangle should be considered to be "missing" in the input data; your code should ignore what is there, and instead use texture synthesis to replace it. Note: be sure to use the coordinate system specified by the NTadt library, where the origin is at the top left of the image.

You can experiment with the test images below. (Be careful not to specify a large rectangle, as the algorithm is not very fast).

Example images: