Fall 2003



9/24/03 - added information about converting from color to grayscale

Project 1: Image Manipulation

This project is due on Tuesday, October 7th at 2:30pm. Late assignments will be accepted for a penalty until Sunday, October 12th at 5pm.

For this project (and this project only) there will be a 48 hour grace period. While there is a penalty for late projects, we will not deduct from your grade providing your project is turned in by Thursday, October 9th at 2:30. However, turning in a project late may impact your ability to turn projects in late in the future. (You may only use the grace period once.)


The goal of this project is to give you practice working with images, using what you have learned in class to implement some useful operations on them. We are only asking you to implement 4 imaging operations - all of which do something that is really useful.

Your program must be able to read in a Targa image (we recommend using our LibTarga), allow the user to select one of the 4 operations, provide the parameters for those operations, and then write the image back out as a new Targa file. The actual user interface doesn't matter - you can have the user put arguments on the command line, you can make a nice GUI, you can prompt the user for input, ...

The four operations that you must implement (all will be explained in detail later) are:

  1. Convert to Black and White
  2. Reduce / Enlarge / Scale
  3. Impressionist Paint
  4. Remove Red-Eye

For removing red-eye, you will probably want to make a GUI that allows the user to click on the eyes. You might find other aspects of this project easier if you at least allow your program to display its results. However, it is totally possible to complete this assignment without any GUI - you can use Photoshop (or some image program) to view your results, and can use it to figure out where the user would want to click in the image and type those coordinates into your program.

What is most critical in this project is that you successfully complete all of the parts. Having a basic implementation of all 4 required features will receive a better grade than a project that does an amazing Impressionist Paint feature, but does not convert to black and white correctly.

For each part, there is a wide range of possible solutions. You will receive a better grade for correctly implementing a more sophisticated solution. It is better to correctly implement a simple solution than to have an incorrect fancy solution.

Note: a critical part of this assignment is the documentation.

Feature 1: Black and White

Your program must be able to convert a color image to a black and white one. That is, the result of this command must be an image where each pixel is either black or white (0,0,0 or 255,255,255).

In making the conversion, your program should account for the perceptual sensitivities of the human eye. (e.g. we are more sensitive to green than to red, and more sensitive to red than to blue).

Because our eyes are more sensitive to green, an equally bright green, blue, and red will not appear equally bright. This means that if you are converting between color and grayscale, the color red (255,0,0) should not turn into the same brightness as the color green (0,255,0).

The exact ratios vary. One simple one is to say that green is twice as sensitive as red is twice as sensitive as blue, which gives the rations for R,G,B as 2/7, 4/7, 1/7, or .28, .57, .14. I have also seen systems that use r = 0.212671, g = 0.715160, b = 0.072169.

The closest thing to an "official" standard is what is used in NTSC (the North American video standard) to compute brightness from colors. That's: Y = 0.30R + 0.59G + 0.11B.

There are many possible quantization algorithms. Several were discussed in class, or in the readings. You should pick the best one that you can implement. However, it is better to have a correctly working simple threshold than an incorrectly working error diffusion method.

The basic "signs of life" required for this part is that your program successfully creates a valid black and white image, and that the image resembles the input. Your program's ability to capture gradations in tone will get you a better grade.

Feature 2: Reduce/Enlarge/Scale

Your program must be able to change the size of an image.

At a minimum, your program must be able to halve the size of the image as well as double it.

Better implementations will allow for more arbitrary scale factors. In order of challenge:

  • Factors of two only (halve, double)
  • Factors of two or three
  • Any integer scale factor
  • Arbitrary scale factors (e.g. .61 or 1.32)
  • Arbitrary, non-uniform scale factors (seperate numbers for X and Y)

It is more important that your program does a good job of resampling the images than that it handles the harder scale factors. Therefore, a program that does a good job at scaling by factors of two is better than one that does a bad job at scaling, but can do factors of two or three.

Your program might do a good job sampling at some scale factors and a worse job at others. While this is less desirable than being right all the time, it is a good starting pont. In the questions, you will be required to explain when your program is right and when it is not.

The basic "signs of life" required for this part is to have your program be able to halve/double an image, even if it uses point sampling.

Feature 3: Painting

You must implement a feature that turns a picture into a painting. For example, my demo solution from a few years ago turned the picture on my web page into this:

This kind of "painterly technique" was introduced by Paul Haeberli (who was a UW alumn!). The original paper about the technique (which is quite a fun paper) is in the reader. To try this out, look at the online Java demo. Basically,you sample the original image, and for each sample, you make a brush stroke in the result. By controlling the shape, size, and color of the brush strokes you get some really cool effects. In my example, the brush strokes are squigglies.

Haeberli's online demo is interactive - the user controls the sampling by moving a "paintbursh". To do this as an automatic command, you should have the program randomly make enough brush strokes to cover the image.

There are many possible "painterly" techniques. Use your imagination to try to invent some transformations that make interesting images! There is actually a whole literature on this kind of stuff.

The basic requirement here is that you have a command that creates something that looks "painterly." Because we want to grade you on your knowledge of graphics, not your artistic judgement, better painting methods must explain why their methods work so well, as well as show some cool examples.

To encourage you to create a cool painting algorithm, there will be a contest for the best result. (details to be determined)

The basic "signs of life" for this feature is that you produce some image that resembles the input, but is somewhat different (in an intentional way).

Feature 4: Red-Eye Removal

When you take a picture of a person with a flash that is too close to the lens, the light bounces off their retina (which is red from all the blood vessels) and back into the camera, causing their eyes to glow red. There are various ways to avoid this, such as moving the flash away from the lens (which is hard on a small camera) or making a few pre-flashes to cause the person's pupils to close so no light gets inside to the retina. (this latter effect doesn't work with babies, who don't have that reflex, or drunk or stoned people, who lose that reflex).

Needless to say, sometime, you get pictures where the person's eyes are glowing red. For this part of the project, you must make a tool that fixes the problem.

There are two parts to fixing red-eye:

  1. Determining which pixels to change
  2. Determining what color to change them to

Each part is suprisingly hard. The reason we're giving you this project is we want you to experiment to realize how hard it is to find colors and things like that.

A simple solution would require the user to specify each pixel by painting (now you know why I gave you the ZoomerWindow example), and paint it black. Not only is this a lot of work for the user, it also looks bad.

The ultimate solution would automatically find the red eyes and change the pixels in a realistic manner so you couldn't tell the image had been manipulated. This is really hard. Even commercial software doesn't do it perfectly.

Realistic good solutions require the user to point to where the eye is, have the system figure out the problematic pixels near where the user points, and does some set of color corrections to get the red out without making the eyes look "wrong" (hint: black eyes look almost as wierd as red eyes).

Your solution will be evaluated by how much effort it is for the user, and how good the eyes look on some test cases. So, for example:

  • The ZoomerDemo is a lot of work for the user (they have to paint each pixel), and it doesn't look too good (since it makes the eyes green), so it qualifies for the "signs of life" level, but not much more.
  • Liz's sample solution allowed the user to draw a box around the eyes. It found all of the "bright red" pixels in the box, and dimmed them. This was easy for the user, and gives pretty good results.
  • The solution that I am trying makes the user click once somewhere inside the eye (very easy for the user). It searches outward to figure out the region of the eye, and does some things to get rid of the red, but keep the shiny "glint". This would be an excellent solution, except that since it still has lots of bugs, so it doesn't really work. (i wanted to write up the assignment first - i'll fix the program later). So the basic signs of life of the ZoomerWindow would actually be worth a better grade.

Note: we will test your program by having you give a demo of it. We will provide some test images for you to practice on - check the class announcements web page for details.

The basic "signs of life" for this part is to have some way to "get the red out" of the eyes in an image.


You must turn in a file called "questions.txt" and answer the following questions.
(note: in some parts we ask you to describe ways to test an implementation - we are not asking you if your algorithm passes the test. In other parts we ask you to describe your implementation)

Question 1:
What method did you implement for Feature 1?
Describe how you could test it. You testing should demonstrate that your algorithm gives a better result than a worse method (or a worse result than a better method).
Your answer should describe an image (or set of images), as well as the results you would expect to see on these images.
Question 2A:
What amounts of scaling does your Feature 2 support?
What interpolation methods do you use?
What filtering / sampling methods do you use?
Question 2B:
Describe a procedure to test that a size reduction method is doing the proper filtering. For a scale factor of 1/N, describe an image that would show that the filtering is neither too "low pass" or not "low pass enough."
Question 3:
Describe how your painting algorithms works. What types of images is it most likely to produce interesting results on?
Question 4:
Describe how your red-eye elimination method works.

Turning things in

In your handin directory, you should turn in:

  • All source code (c++ and header files, interface description files, ...)
  • Project and Solution Files
  • A README.txt explaining what everything is - this should detail what code (if any) is borrowed
  • Your questions.txt file
  • Your sample images for Feature 3. The files should have names of the form f3-login-1.tga (where 1 becomes 2 for the second image, ...)

Please do not turn in more than 2MB worth of stuff. Because libtarga does not compress the images, the sample images you turn in might be big - be careful.

We will check the timestamps to determine when your files were turned in.


The projects will be graded.

We will schedule short demo sessions in which you will show off your program. The demo session will ask you to copy your assignment out of AFS onto the local disk of a B240 machine, build your program, and run it on some test images. We will also read the answers to your questions, and look at your code.

In general, complete and correct is more important than fancy. It is better to have a basic implementation of each feature that works, than a fancy implementation of some subset. Basic versions of each part are easy to do, so we recommend that you implement a basic version of each feature, and then go on to implement fancier versions if time allows.