Project1: Image Manipulations

Due Tuesday, October 10th 2006, 9:30am

Updates:

10/3/2006

Clarification on Black-and-White grading. For any error diffusion implementation (not just a color one) you must explain how you deal with overflow. Also, even if you do color output, you still must be able to do black and white.

1.  Introduction

The purpose of this project is to have you implement some image manipulations. This will allow you to demonstrate that you understand image manipulation, and an opportunity to experience some of the pragmatic issues in doing image manipulation.

This project consists of several independent pieces. You can think of it as four separate projects. You can write five separate programs. However, since the parts all have lots in common, you are probably better off thinking about them together so you can share code between them. You could write one program that has some interface for doing all of the options which is an extension to Main.Tutorial 6 .

1. Resize: reduce and enlarge
2. Convert to black and white
3. Impressionist paint
4. Image warping

2.  For all Parts:

Each of these operations should read in a Targa file and write back another Targa file. You may prompt the user (for example, using an FlTk file dialog box), or you may take the file names as command line arguments. Remember, that we define a Targa file to be the images that can read and written with the Libtarga library, so we recommend that you use that.

We do not care what the user interface is for performing the operations. You might have several different command line programs, or 1 program with a GUI, or something in between. You must document your program/programs well enough that we can use it. You must be able to use your program.

2.1  Grading Difficulty Options

For several of the parts of this project, you will have options as to the "difficulty level" of what you try to do. For example there might be an "easy" option and a "difficult option." Each option will be assigned a letter grade that is the highest grade you can get for taking this option. For example, if you take the "B" option on some part and do it really well, you'll get a B for that part. If you take the "A" option and your program doesn't get a correct answer, you might get a "C".

You must tell us which option you chose to do before we do the grading (you must specify it in your README file).

The grading standards are designed such that if you have a correct solution to a lower difficulty option and hand it in as a partial solution to a higher option, you will get a lower grade.

You may choose a different option for each of the parts of the assignment.

For some of the parts of this project, there are "Bonus" or "Extra Credit" options. Remember, that it is course policy that you cannot use extra credit to raise your grade. If you choose to do extra credit, you must also do the normal graded part.

2.2  Grading

Each part the assignment will be graded. Your total grade will be the average of them. The "weights" for different parts are as follows. One third of the project grade (1/3) goes for resizing part. One third (1/3) goes for impressionist painting. The final third (1/3) is for warping and black and white conversion (2/9 for warping and 1/9 for black and white conversion).
The grade for each part ranges from 0 to 4 (F to A). Your overall grade will be multiplied by a "code quality" multiplier.

You will be evaluated on:

• The correctness of your program, as evaluated by your demonstration of it.
• The quality of your code and documentation. (remember your readme).
• The answers that you turn in to the questions that go along with the various parts of the assignment.
• Correctly following directions.
• Existence of examples. We will not grade you on artistic choices.

Note: we will not evaluate the efficiency of your program (within reasonable time). Concentrate on writing programs that get correct answers and are clean and readable code. If your program takes more than 10-20 seconds to process a 600x400 image, then maybe there's something wrong - but don't worry about trying to get into a race with Photoshop.

More specific information on grading will be added later.

2.3  Demonstrations:

The main testing of your program will happen at a scheduled demonstration in B240. You will compile and run your program for us - we'll bring the test data.

3.  The Four Image Processing Operations:

3.1  Resize

You program must be able to change the size of an image by resampling it.

It may be easier to solve the problem by considering enlarging and reducing the image seperately, as their basic challenges are different.

However, to get an A for this part, you must have a single interface where the user enters a scale factor (for example as a percentage) or a new size in pixels for the resulting image.

To get an A your program must also allow for anisotropic scaling. That's a fancy way to say that you can have a different scale factor in each dimension.

Reduce

Our program must take a TGA image and produce a smaller version of it. The hints might help you!

• Difficulty options:
  • "C" Option: implement downsizing by integer multiples (e.g. half, third, quarter). Do this by "pixel dropping" (e.g. no reconstruction filter and no sampling filter)
  • "B" Option:
    1. Option number1: implement downsizing by integer multiples using a proper sampling filer to avoid aliasing artifacts.
    2. Option number 2: implement downsizing by an arbitrary fraction using a variable reconstruction filter to provide linear or cubic interpolation between samples.
  • "A" Option: implement downsizing by an arbitrary fraction using a correct reconstruction filter (to provide cubic interpolation) and proper sampling to avoid aliasing.
• Written Questions: (for B and A options only):

Enlarge

This is similar to reduce, except that you should make the image bigger.

• Difficulty Options:
  • "C" Option: implement pixel replication to scale the image by integer multiples.
  • "B" Option: allow the user to scale the image by integer multiples. Allow the user to select between nearest neighbor, linear, and cubic reconstruction kernels.
  • "A" Option: allow the user to scale the image by any fraction greater than 1. Allow the user to select between nearest neighbor, linear, and cubic reconstruction kernels.
    • Recommended: try different cubic kernels to see how they are different.
• Written Questions

3.2  Convert to 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.

• Difficulty Options:
  • "CD" Option: implement simple thresholding
  • "B" Option: implement some form of ordered halftoning or dithering
  • "AB" Option: implement Floyd-Steinberg or some other error diffusion method. If you choose an algorithm other than Floyd-Steinberg (or Ostromoukhov's algorithm), please check with us first.
  • "A" Option: allow your program to read a list of colors from a text file (so black and white is a special case) and do error diffusion to map the image into these colors. Your program will be tested on the black and white case, as well as the color case - so be sure to make the black and white case convenient.
  • "Bonus" Option number 1: use a more sophisticated error diffusion method than Floyd-Steinberg. For example, there are "artistic" halftoning methods in the literature. Or, here is another algorithm that isn't much more complicated to implement than Floyd-Steinberg. Note: you must actually implement the algorithm (since there is code for Ostromoukhov's algorithm on the web).
  • "Bonus" Option number 2: implement Floyd-Steinberg and Ostromoukhov's algorithm. (If you implement FS, you can adapt one of the implementations of Ostromoukhov's that is available on the web). Provide a comparison. Find images that look better with one algorithm or the other.
• Written Questions:

3.3  Impressionist Painting

Your program must take a color image and produce a new color image that is a "painted" version of the original.

The basic idea is that you sample the original image and for each sample you place a "brush stroke" in the destination image. You need to randomize the order of the strokes a little. This is a case where undersampling/aliasing actually creates some nice effects

Here's an example (click on an image to get the bigger versions):

original

straight stroke

curly strokes

One possibility is to have the user specify where the brush strokes go (have them click on the image and brush strokes appear there). The original version of painting did it this way. You can see a Java implementation of it here. Paul Haeberli, the inventor of the technique, is a UW alumn!

Implementing the interactive version is fun. However, you must also have a "batch mode" version that processes a whole picture without any user intervention.

We've seen some pretty creative solutions to this assignment in past years.

• Here are some ideas:
  • The simplest thing to do is to pick a simple brush shape (a small circle or square?) that you can easily draw into the image, and make all the strokes be the same. Get this to work first. The straight and curvy strokes above both do this (for more complicated brush shapes).
  • Try to implement different shapes for the strokes (as the example, or the impressionist demo, shows). You can use lines, circles or squares. My sample implementation read in this image that contained many brush shapes.
  
  • Try adding a little bit of randomness or variety can make your pictures more "painting like". Try adding a little bit of randomness to the color or the position of the strokes. Try adding some randomness to the direction or size of the strokes. My program would randomly choose strokes from a row of the image above.
  • Try adding highlights or shadows to your strokes. The stroke image above shows how my program could mark certain pixels of the stroke to be darker or lighter.
  • (Bonus only) Try adapting the strokes based on the content of the image. For example, where the image has more detail, you might use a larger number of smaller strokes. You might orient the strokes based on the direction of lines in the image. You might cut strokes off if they cross edges in the image. Of course, this would require you to know how to analyze images to determine what's in them, and that's the subject of another course (Computer Vision). We can provide you with some hints if you are motivated.

Making good paintings from images is a hard problem. There is actually a lot of research out there. Haeberli's original paper is easy (and fun) to read. Here is another old (but good) source of lots of ideas. The version of this project that was assigned at U. Texas has even more ideas. (note: the Texas project has students use the OpenGL graphics library to render the brush strokes. You must render the brush strokes yourself (actually writing the pixels into the image). Graphics classes at other universities give variants of the impressionist painting as an assignment. Often, they ask students to use a graphics library (OpenGL) to draw the brush strokes. We don't recommend you do this: you should draw the brush strokes by actually setting the pixels in the image.

• University of Washington, Winter Quarter 2005
  • Assignment description
  • Examples of student's results
• University of Texas (seems to be exactly the same)
  • http://www-csl.csres.utexas.edu/users/billmark/teach/cs384g-04-fall/projects/impressionist/handout.html

A note on expectations:

We don't expect you to do cutting edge research - its a part of a 
class project for an undergrad graphics class.

Many of the techniques that adapt the strokes to the image require a tiny 
bit of computer vision know-how. (OK - easy version - a high-pass filter 
can tell you when there's detail in an image, and that you should use more 
small strokes).

What's cool about impressionist painting, however, is how cool you can make
it look just doing the basic stuff. Most people find doing it really fun.

• Difficulty Options:
  • "B" Option: implement the "basic idea" using a single brush shape. To get full credit, it should be clear from the results that your resulting image is "painted" (made of many brush strokes).
  • "A" Option: do something more creative to make better looking paintings. Implement some of the suggestions above.
  • Bonus Option: you can go totally crazy with this, trying to recreate different artistic styles, automatically choosing different brush strokes over the image, ... - There's a whole literature of artistic drawing techniques that you could implement!
• Written Question:

3.4  Non-linear warping

Warps are simply mappings from a source image to a destination images. This mapping takes the form

Where (x',y') describe the position in the destination image. (x,y) is the position in the original image. A non-linear warp means that the function is not linear.

There are lots of ideas for non-linear warping. This includes Swirling, Creating waves, Turning an image into a diamond or fisheye warping.

Another interesting idea is that you can impose a grid on the source image. The user is allowed to move the points on the grid around, and the image is warped accordingly. This specific warp is interesting because it is the basis on which some morphing systems work (thought not exactly that way). You can find an illustration of this method here (http://freespace.virgin.net/hugo.elias/graphics/x_warp.htm)

Implementing non-linear warping requires performing image resampling. The positions of the samples are determined by the warping function.

Warping can be done using either one of two methods, the forward method, and the reverse method (or backwards method). For the forward method, we scan the source image pixel by pixel, moving this pixel to its target in the destination image. In the reverse method, we scan the destination image pixel by pixel figuring out where each pixel came from in the source image.

Forward warps are hard to implement because we need to find a logical way to fill in the gaps. Therefore, for this project we recommend that you implement reverse warping. Notice that when doing an reverse warping, you need to be able to computer the inverse of the function f.

In reverse warping, for each pixel of the target image you sample the source image. The position of this sample is given by the inverse of the warp function. Note that there are two issues that make this sampling difficult:

1. the sample point might not be in an integer position
2. the sample might correspond to a large, odd-shaped region of the source

These issues are similar to resampling for resizing. One way to think of how non-linear warping is harder is that for every pixel, the amount of resizing is different. And those nice, round (or elliptical) gaussian kernels can get warped into wierd shapes.

There are many choices in how you implement the resampling. The easiest method would be to point sample and use nearest neighbor interpolation. Better solutions would use interpolation and variable size sampling filters (where the filter kernel changes size depending on the warp). Implementing a variable shape filter kernel is harder.

• Difficulty Options
  • "C" option: implement two warps using only point sampling and nearest neighbor interpolation
  • "B" option: implement two warps using point sampling and better interpolation
  • "AB" option: implement two warps using a better sampling kernel than point sampling and some form of interpolation
  • "A" option: implement two warps using variable size kernels and interpolation
  • Bonus: Do forward warping or do more interesting warps than those mentioned above. Or try variable shape filter kernels.

Note: if you implement a harder version, you should also implement the easier version so that you can show the difference.

Here are some examples for nonlinear warps. Starting from this input picture

Here are examples of warps done using point sampling

Notice the jagged edges in the pictures. This is not always desirable.

Using bilinear interpolation instead produces smoother results

However, notice that the blurriness in the center of the fisheye warp is incorrect. This area should be sharper.

We get similar effects using gaussian kernel with fixed radius.

Finally, here are two examples done using a variable gaussian filter. These were produced using simple isotropic filtering

• Written Questions
  • How did you handle coordinates outside images?
  • If you did interpolation, describe the method that you used.
  • If you did variable size or shape kernels, how did you do it? How did you choose your kernel size, and what kernels did you use?

4.  Handing in your assignment

Your assignment will be handed in by placing files into your handin directory (P:/course/cs559-gleicher/handin/LOGIN/p1). The "effective date" of your handin will the be timestamp of the last file put into this directory.

Your handin must include:

• A README file that describes each file that you handed in. It must also say which grading option you have chosen for each part. Note: this may be a text file or html. Be sure to explain any code that you've taken from other sources.
• An INSTRUCTIONS file that tell us how to use your program. This may be a text file or html.
• All source code (.cpp, ..h, ...). You should include libtarga.c and libtarga.h.
• The visual studio solution and project files (.sln, .vcproj) requires to build your program.
• A text file called "answers.txt" with your answers to the questions that you have to answer.
• Your sample painted and warped results.

You should not include any of the intermediate files or an executable.

Note: when we test your program, we will copy your handin directory to the local disk of a STORM machine, load the solution file into Visual Studio, and hit compile. You should check to make sure this will work.

5.  Some Implementation Hints

Some hints to make your life easier:

1. The resizing operations are seperable. (see page 104 of the text)
2. On a modern processor (like the Pentium 4s in the Storm lab), floating point is really fast. Doing all of your computations in floating point may make things easier (especially for the resampling operations). The thing that is NOT fast is converting between integers and floats. If you choose to do floating point computations, you should convert the image, do the computation, and convert it back at the end.
3. One thing missing from our (intentionally hand-wavy) discussion of image processing was the connection between frequency and the actual kernel widths. Qualitatively, the radius of the resampling kernel (or at least the main hump of it) should be the same as the distance between the samples.
4. If hints 3 wasn't concrete enough for you, here's a specific thing: for halving an image (taking every other pixel) the 2nd binomial filter 1/4 (1 2 1) seems about right. For sampling every third pixel the 4th one 1/16 (1 4 6 4 1) is OK. Notice how these kernels overlap just enough that all pixels get an even weight. You can generate kernels in between by interpolating the kernels (so, if you want to divide by 2.5, you might take 1/2 of filter 2 and 1/2 of filter 4 - remember that 1 2 1 is 0 1 2 1 0)
5. If you really want to understand the rammifications of #4, what you should do is try different filters and see what happens. Pick one that's a little too narrow and see the aliasing. Pick one that's a little too wide and see the excess blurring.

6.  Projects Given by this Course in the Past

Back in 2001, we gave a project that required students to create a much more complete imaging system with a lot more features. Here are some of the pictures that they made with their projects.

7.  Material for Help Session

1. Project 1 Discussion Slide
2. Project 1 Related Data
3. Note on Floyd-Steinberg Dithering method
4. Filter Examples