Overview

Image Analogies
A. Hertzmann, C. Jacobs, N. Oliver, B. Curless, D. Salesin.
SIGGRAPH 2001 Conference Proceedings.

The following is a list of features that you may implement. You are required to implement the features in bold face -- the others are optional. In addition to implementing these features, you should submit an image generated by your program to the art contest. The winner will get extra credit and a note on the course web page.

Methods:

• Basic algorithm: Implement the basic Image Analogies algorithm as described in the first two paragraphs of Section 3.2 of the Image Analogies paper, using synthesis of pixels in scan-line order with exhaustive search for similar pixels based on luminance values for a KxK neighborhood (e.g., K=5), as described in Section 3.4. This will be slow, and so you will want to test it only with small images.
• Approximate nearest neighbor search acceleration: Augment your program to accelerate search for nearest neighbors. You may utilize code written by others to provide the acceleration structure for this feature (e.g., ANN or FLANN). Provide images and timings for your program showing the differences achieved with and without the acceleration enabled. After this feature is implemented, your program should be fast enough to work on larger images.
• Coherence search: Augment your program to include a "coherence search," as described in the third paragraph of Section 3.2. Experiment with different values of the "coherence parameter" (kappa) and discuss its effect.
• Multiresolution synthesis: Augment your algorithm to create an "image pyramid" and utilize it for both acceleration and global structure preservation during image synthesis, as described in the fourth paragraph of Section 3.2. Investigate the effect of this feature by comparing the quality and compute time for images synthesized with and without it.
• Constrained texture synthesis: Augment your algorithm to synthesize pixels only within a mask region of a given target image B' (e.g., mask pixels are indicated by a specific color). For this feature, your code should synthesize pixels in an order based on the completeness of neighborhoods, filling in pixels from the boundary of the hole first, rather than in scan-line order. Demonstrate this feature in an application that fills holes in images resulting from "scratches" on the image, extrapolation of an image, and/or removal of unwanted objects in a photograph (see examples).
• Luminance remapping: Augment your program to include luminance remapping as described in Section 3.4. Demonstrate the effects of this feature on images with different overall brightness.
• Multiple training pairs: Augment your program to utilize multiple training pairs. Demonstrate this feature in at least one application (see examples).
• Steerable filters: Augment your feature vector for each pixel to include the responses of multi-scale steerable filters, as described in the last paragraph of Section 3.3. You may use code written by others to compute the steerable filters. Investigate the effect of this feature by comparing the quality and compute times for images synthesized with and without it.
• Patch-based synthesis: Augment your algorithm to synthesize images based on partially overlapping patches rather than individual pixels. This will require augmenting the nearest neighbor search to consider similarity of overlapped regions of adjacent patches, implementing a way to blend patches in the overlap area (e.g., a graph cut), and multiple passes to select patches based on similarity to neighbors.

• Image filters: Provide your program with any image pair A and A', where A' was produced with a signal processing filter (e.g., blur), and apply the analogous filter to another input image B, as described in Section 4.1 (see examples here and here).
• Texture synthesis: Provide your program with a small example texture B and synthesize a new larger texture B' that "looks like" B but contains no large patches directly from B, as described in Section 4.2. Show outputs for at least two input textures with outputs twice and four times as large as the input (see examples).
• Texture by numbers: Provide your program with an input image A' and a mask A that indicates a class label for every pixel in A', and use image analogies to infer a new image B' from class labels for every pixel provided in an input image B, as described in Section 4.6 (see examples).
• Image inpainting: Provide your program with an input image A' containing pixels needing repair (e.g., ones that are pure blue) and use constrained texture synthesis to "fix" those pixels. Demonstrate this feature in an application that fills holes in images resulting from "scratches" on the image, extrapolation of an image, and/or removal of unwanted objects in a photograph (see examples).
• Super-resolution: Provide your program with a low-resolution image A, its high-resolution counterpart A', and a low-resolution input B, and use image analogies to infer a high-resolution version of B, as described in Section 4.3 (see examples).
• Texture transfer: Provide your program with a texture A and an image B, and use image analogies to infer a textured version of B, as described in Section 4.4 (see examples).
• Image colorization: Provide your program with a black and white photo A and a colored version A', and use image analogies to infer a color version of black and white image B, as described in (see examples).

To get started, you can use the code in (cos526_assn2.zip). This C++ code provides a simple image class (R2Image.cpp) that can read and write image files in bmp, jpg, and ppm formats and a simple console program (analogy.cpp) for parsing command line arguments and executing the algorithms. You will probably need to augment this program to include command line arguments of your own to turn on and off specific features and/or provide parameters for specific applications.

What to Submit

• PUID_cos526_assn2/
  • writeup.html (your writeup, see the description below)
  • Makefile (a gnu make file that generates all the images in the output directory from the data in the input directory)
  • input/ (all the input data for the examples in your writeup)
  • output/ (all the output images for the examples in your writeup)
  • art/ (all images submitted for the art contest)
  • src/ (the complete source code)

writeup.html should be an HTML document demonstrating the effects of the features you have implemented. There should be one "section" per feature. with a brief description of what you implemented and some images showing your results. For the "method" features (e.g., coherence search), you should include outputs of your algorithn with and without the feature enabled (with timings where appropriate). For the applications (e.g., texture synthesis), you should show results for at least two sets of inputs, preferably with inputs that you have created. In any case, your algorithms should work for the examples provided on the Image Analogies Project Page.

The src directory should have all code required to compile and link your program (including the files provided with the assignment), along with a Makefile to rebuild the code.

The Makefile script should contain the commands that generate all the images in the output directory that are included in the writeup. It should run without crashing when the user types make in the PUID_cos526_assn2/ directory (i.e., it should be possible to delete all the files in the output directory by typing make clean and then make to regenerate them).

You will want to run your algorithm on uncompressed images (not JPEG). However, you may submit images in JPEG format to save space. Also, to further save space, please remove binaries and backup files from the src directory (i.e., run make distclean (under Mac OS).

Useful resources

• Tianqian Liu, Assignment #1 Writeup, COS 526, 2010
• Yiming Liu, Assignment #1 Writeup, COS 526, 2010
• Jinwan Lu, Assignment #1 Writeup, COS 526, 2010
• Thiago Pereira, Assignment #1 Writeup, COS 526, 2010
• Aaron Hertzmann, "Image Analogies", SIGGRAPH, 2001.
• Michael Ashikhmin, "Synthesizing Natural Textures," I3D, 2001.
• Li-Yi Wei and Marc Levoy, "Fast Texture Synthesis Using Tree-structured Vector Quantization", SIGGRAPH 2000.
• Alyosha Efros, "Texture Synthesis by Non-parametric Sampling", ICCV, 1999