Computer Graphics
Exercise 1
Halftoning and Color Transfer

 

Submission due 24/3/2005



The exercise consists of two parts:

  1. Implementation of halftoning algorithms
  2. Implementation of a color transfer algorithm

See also the presentation given in class: ex1.ppt

1    Halftoning

Write a program that reads a grayscale image and outputs a black-and-white image generated by the two haftoning algorithms learned in class. Name your program  halftoning. The usage should be the following:

  • for the dithering algorithm:           halftoning -d <image_file>
  • for the error diffusion algorithm:   halftoning -e <image_file>

Your program should be able to read at least one of the following common formats: bmp, jpeg, png, pgm. If the program file is run without parameters, please print the usage explanation and which formats your program handles. The output file can also be in any of those formats. Please name the output files as follows: for dithering use prefix  dither_  and then the original filename; for error diffusion use  errdiff_  prefix. For example, if the input file is  shrek.jpg  then the output should be dither_shrek.jpg  for the  -d  option and errdiff_shrek.jpg for the -e option.

Test your program on a purely black image and a purely white image. These trivial cases must give you the expected result (unchanged images). Include at least three non-trivial examples. Nice and original images are preferred (see General Guidelines below).

2    Color transfer

Write a program that performs color transfer as explained in class. The program should be named  ColorTransfer  and its usage should be as follows:

ColorTransfer <image_file_1> <image_file_2>

Again, your program should be able to read at least one of the common image formats. If run without parameters, the program should print a "usage" message and which image formats it can recognize. Your program should transfer the colors of image_file_2 onto the image read from image_file_1. The result should be written to a file with the refix res_. For example, if the command line was
ColorTransfer garfield.bmp blue_monster.bmp
then the output will be a file named res_garfield.bmp, with the image of blue Garfield (see examples below).

Short reminder of the algorithm
Perform Principal Components Analysis (PCA) on the colors of both images, in RGB space. Compute the oriented bounding boxes for the colors of image_1 and image_2, where the bounding boxes are aligned with the axes found by PCA. Compute the affine mapping (a function) that transforms box_1 to box_2. Now, go over all the pixels of image_1, apply the mapping to their colors and record the new colors in the output image. Be sure to restrict the new color values between 0 and 255 for each color channel (assuming you're using an 8-bit per channel image format, which is the standard case).

In the documentation (see below) please discuss the quality of the algorithm by answering the following questions: when do you think it should perform well, when not, and why? Include examples (good and bad) that back up your conclusions. Try to suggest a solution to the problems you see with the current algorithm (a bonus of 3 points will be given for good theoretical suggestions, a bonus of 20 points - for practical implementation).


Examples of color transfer
Click on the small images to get the larger images.

Image_1

Image_2

Result (colors of Image_2 on Image_1)

 

Libraries and useful links

You are welcome to use any open-source image library and linear algebra library. You are not allowed to use the provided advanced functionalities, such as dithering algorithms, because the idea is that you implement them yourself. We recommend the following libraries:

 

  • FreeImage
    For reading, writing and manipulating images of various formats.
    Download the binaries and the manual. The first few pages are all you need to get started. Here's a simple example program that uses this library:
    FreeImageExample.cpp

 

  • NewMat10 (download page, documentation)
    For vectors and matrices, computing eigendecomposition and much more.
    This library is written in C++. Even if you don't know C++, it is very simple to use (and also a good opportunity to start learning something about C++). Note that this library uses 1-based indices, meaning that they start counting from 1 and not from 0. Here is a simple example program to get you started:
    NewMatExample.cpp
  • IrfanView
    A good viewer, editor and converter for images of various formats. Please note that it does not handle alpha-channels (something you don't need in this exercise but might need in the future.

 

General guidelines

What to submit

  1. The code, in electronic form, as described below.
  2. At least 3 working examples, for each part of the project. Submit them together with the code. Note: a bonus of 5 points will be given for especially nice examples. Visual quality is important in graphics!
  3. Hardcopy of the documentation (do not print the code). Explain what you have implemented, describe in short the main parts of your programs and the modules, if any. Also, please mention any nuances of usage, such as the file formats accepted by your program. In addition, include the answers to the questions posed in Part 2 (Color Transfer).


Electronic submission guidelines
 
You may implement the exercise in C or C++. If you work under Linux, please put the code and the examples under your home directory, give read permissions and write the exact location in the documentation hardcopy. If your code consists of several files, be sure to include a makefile. If you work under Windows, you may submit a diskette/CD with the project (Visual C++ 6.0 or .NET) and the examples (or alternatively place the files under your home directory, as described above). Make sure that the submitted media contains your name, ID and e-mail, in a file (and not only on a sticker on the diskette, because they tend to fall!). Also make sure that you include the workspace and project file (*.dsp and *.dsw).

For further questions contact Andrei Sharf (asharf@tau.ac.il)


Good luck!