In this project you will write an image editing program that allows you to load in one or more images and perform various operations on them. Consider it to be a miniature Photoshop.
Things on this page may be modified as circumstances warrant it, so check back frequently for changes.
In this project you score points for each image operation you correctly implement. The possible operations and their values are outlined below. Details on implementing them are further down.
| Operation | Points |
| Load | 0, provided |
| Save | 0, provided |
| Difference | 0, provided |
| Run | 0, provided |
| Color to Grayscale | 5 |
| Uniform Quantization | 5 |
| Populosity | 20 |
| Median Cut | 50 |
| Naive Threshold Dithering | 5 |
| Brightness Preserving Threshold Dithering | 5 |
| Random Dithering | 5 |
| Ordered Dithering | 10 |
| Clustered Dithering | 5 |
| Floyd-Steinberg Dithering | 15 |
| Box Filter | 15 or 3 |
| Bartlett Filter | 15 or 3 |
| Gaussian Filter | 15 or 3 |
| Edge Detect (High Pass) Filter | 15 or 3 |
| Edge Enhance Filter | 15 or 3 |
| Half Size | 8 |
| Double Size | 12 |
| Arbitrary Uniform Scale | 25 |
| Composite Over | 15 or 3 |
| Composite Inside | 15 or 3 |
| Composite Outside | 15 or 3 |
| Composite Atop | 15 or 3 |
| Composite Xor | 15 or 3 |
| Arbitrary Rotation | 25 |
| Blue Screen | 10 |
We grade this project by comparing images from the operations you implement with images produced by our reference solution. If you implement an operation, you get points for it based on how closely you match the reference result. We sum up all of the points for the operations you implemented to get your grade. In the detailed description of each operation we indicate what it means to match the reference solution. In some cases the match must be exact, while in others a match means producing an image that looks qualitatively the same.
You may work in pairs for this project, but you are not required to. If you choose to work as a pair, both people must submit a copy in their own handin directory. The project will be graded, and each group member will be given half of the earned points.
The total number of points up for grabs is greater than 200, but the maximum any individual can get is 100. If you are an individual, aim for 100. If you are a pair, aim for 200.
A reference program is provided so that you can check your implementation, although you may still get full points for an operation even if your result doesn't match the reference program's. Many of the operations are sensitive to very subtle differences in coding, and it is not worth anyone's time to try to have everyone implement everything in exactly the same way.
We will look for identical programs. If you are found to have duplicated someone else's work you will be treated as a group and given half the earned points. We will also take steps to ensure that you don't submit the reference program and don't manipulate the system in other ways we anticipate.
Use the handin system to submit your work. The class name is cs559-1 and the project name is proj1. You can hand in your files more than once, so copy early and often up to the deadline. That way, you have something in the directory even if everything goes wrong at the last minute. Do not attempt to hand in images or debugging files. The handin system should reject such files.
When we grade your project, we will compile the code and run the resulting executable. If your project does not compile on the machines in B240 then it will not be graded. We will semi-automate the process of compiling and running your program. It is essential that you only modify those parts of the skeleton that we indicate. It is also helpful if you do not create any additional source files.
The "submission date" will be determined by the latest modification date of any file in your directory. Do not modify files after the deadline unless you wish to incur the late penalty. The late penalty is 10% per day. See the class policies page for details.
The basic program must be controllable through a scripting language, and you should not change this in any way. The project will be graded by running scripts, so the scripting interpreter must function. The scripting language is simply a sequence of lines, each of which has a command and some arguments, generally a filename. The commands for each operations are listed below along with the arguments. You can type in script lines in the window, or load a pre-written script from file.
The program should maintain the current image, which is displayed. The current image is modified by the various operations as outlined below.
All files will be in the Targa (tga) format. LibTarga supports pre-multiplied RGBA images. To load the alpha bits, tell it that you are loading 32 bit data, and it will fill the alpha channel (with ones if necessary) along with the color information. When you read an RGBA image with LibTarga, it returns pre-multiplied alpha pixel data. You must divide out the alpha channel before display, taking care to avoid dividing by zero. The skeleton already does this for display.
A basic program skeleton with the scripting language implemented is available. This program will also load and save images with alpha (if present in the image). You should modify the skeleton by changing the file TargaImage.cpp and/or TargaImage.h to implement the functions. At the moment all the functions change the current image to black.
As it is currently implemented, the skeleton will execute all the commands in a script file that is given as an argument. To specify arguments in Visual C++, go to the Debug part of the project settings dialog. The skeleton also provides a single line command entry dialog. To execute a command, type it in and hit the Enter key. Hitting Enter again will run the same command again. You can of course change the command. Try "load test.tga" to load the test image. "save test-save.tga" also works. (Leave out the quotes when you type things in.)
The skeleton is slightly modular in design. In particular, the widget for displaying an image is separate from the object for storing the image, and both are separate from the main window itself.
The TargaImage class stores RGBA. Many of the operations only need greyscale, so this is a waste. Ignore it for now by storing grey as RGB with R=G=B, or put separate greyscale image information inside the TargaImage class.
Many of the operations you need to implement are very similar. For instance, all the filter operations differ only in the filter mask, not the basic filtering algorithm. Write your program to take advantage of such common operations -- the grading scheme assumes you will.
IMPORTANT: If you choose not to implement a function, it is essential that the function call ClearToBlack and return false. This is the default behavior, so if you don't change it, you should be OK.
ALSO IMPORTANT: Everyone must alter the function TargaImage::MakeNames() in TargaImage.cpp so that the function vsStudentNames.push_back is called with your name as the argument. We will be using this information during the grading process. If you are a group, use multiple calls to vsStudentNames.push_back to add multiple names.
There is a Makefile included in the program skeleton, and the skeleton should compile under Linux. You are welcome to make use of this if you like, but it is an unsupported feature of the project. You should not ask the TAs or the instructor questions about how to make your program run under Linux.
We provide the following programs:
We also provide a whole range of example images, some with non trivial alpha channels. Pay attention to those operations which will be tested with non-trivial alpha and those that will not. Do not be concerned with how your program manages alpha!=1 if we will not test on such images.
Your first stop for help shoudl be the FAQ containing all of the questions and clarifications issued last time this project was assigned, and any from this semester. If you can't find the answer there, then email cs559-1@cs.wisc.edu with your question, or come to office hours.
| Operation | Keyword | Arguments | Details | Points |
| Load | load | filename | Load the specified image file and make it the current image. | 0, provided |
| Save | save | filename | Save the current image to the specified file. | 0, provided |
| Difference | diff | filename | Subtract the given image file from the current image and put the result in the current image. | 0, provided |
| Run | run | filename | Executes the script named filename. The script should contain a sequence of other commands for the program, one per line. The script must end with a newline. | 0, provided |
| Color to Grayscale | gray | Use the formula I = 0.299r + 0.587g + 0.114b to convert color images to grayscale. This will be a key pre-requisite for many other operations. This operation should not affect alpha in any way, and we will only test it on images with alpha=1. | 5 | |
| 24 to 8 bit Color | All of these operations assume that the current image has 24 bits of color information. They should still produce 24 bit images, but there should only be 256 different colors in the resulting image (so the image could be stored as an 8 bit indexed color image). Don't be concerned with what happens if you run these operations on something that is already quantized. These operations should not affect alpha, and we will only test it on images with alpha=1. | |||
| Uniform Quantization | quant-unif | Use the uniform quantization algorithm to convert the current image from a 24 bit color image to an 8 bit color image. Use 4 shades of blue, 8 shades of red, and 8 shades of green in the quantized image. | 5 | Populosity | quant-pop | Use the populosity algorithm to convert the current 24 bit color image to an 8 bit color image. Before building the color usage histogram, do a uniform quantization step down to 32 shades of each color. Then find the 256 most popular colors, then map the original colors onto their closest chosen color. To find the closest color, use the euclidean (L2) distance in RGB space. If (r1,g1,b1) and (r2,g2,b2) are the colors, use sqrt((r1-r2)^2 + (g1-g2)^2 + (b1-b2)^2) suitably converted into C++ code. | 20 |
| Median Cut | quant-med | Use the median cut algorithm to convert the current image to an 8 bit color image. Use the centroid of each box as the color for that box. Each pixel color is mapped to the centroid of the box in which it falls. You actually get better results if you map each color to the nearest centroid (which is not necessarily the box the color falls into). Take the latter approach if you like. There are several other details in the implementation of this algorithm, which you should work out as you choose. | 50 | |
| Dithering | All of these operations should convert the current image into an image that only contains black and white pixels. If the current image is color, you should automatically convert it to grayscale first (in fact, you could convert all images to grayscale - it won't hurt already gray images). These operations should not affect alpha, and we will only test it on images with alpha=1. | |||
| Naive Threshold Dithering | dither-thresh | Dither an image to black and white using threshold dithering with a threshold of 0.5. | 5 | |
| Brightness Preserving Threshold Dithering | dither-bright | Dither an image to black and white using threshold dithering with a threshold chosen to keep the average brightness constant. | 5 | |
| Random Dithering | dither-rand | Dither an image to black and white using random dithering. Add random values chosen uniformly from the range [-0.2,0.2], assuming that the input image intensity runs from 0 to 1 (scale appropriately). There is no easy way to match the reference program with this method, so do not try. Use either a threshold of 0.5 or the brightness preserving threshold. | 5 | |
| Ordered Dithering | dither-order | Dither an image to black and white using ordered dithering with the
matrix shown below. The image pixels should be compared to a threshold
that depends on the
dither matrix below. The pixel should be drawn white if:
I[x][y] >= mask[x%4][y%4]. The matrix is:
0.1250 1.0000 0.1875 0.8125
0.6250 0.3750 0.6875 0.4375
0.2500 0.8750 0.0625 0.9375
0.7500 0.5000 0.5625 0.3125
|
10 | |
| Clustered Dithering | dither-cluster | Dither an image to black and white using cluster dithering with the
matrix shown below. The image pixels should be compared to a threshold
that depends on the
dither matrix below. The pixel should be drawn white if:
I[x][y] >= mask[x%4][y%4]. The matrix is:
0.7500 0.3750 0.6250 0.2500
0.0625 1.0000 0.8750 0.4375
0.5000 0.8125 0.9375 0.1250
0.1875 0.5625 0.3125 0.6875
If you do this one, but not ordered dithering, then you will get 10 points
for it.
|
5 | |
| Floyd-Steinberg Dithering | dither-fs | Dither an image to black and white using Floyd-Steinberg dithering as described in class. (Distribution of error to four neighbors and horizontal zig-zag ordering). | 15 | |
| Filtering | All of these operations should modify the current image, and assume color images. The alpha channel should NOT be filtered. The alpha channel for all the test images will be 1 for all pixels, so you do not need to worry about the differences between filtering regular pixels or pre-multiplied pixels. Implement whichever approach you prefer. | 15 for the first 3 for any additional | ||
| Box Filter | filter-box | Apply a 5x5 box filter. | ||
| Bartlett Filter | filter-bartlett | Apply a 5x5 Bartlett filter. | ||
| Gaussian Filter | filter-gauss | Apply a 5x5 Gaussian filter. | ||
| Edge Detect (High-Pass) | filter-edge | Apply a 5x5 edge detect filter derived from a Gaussian as indicated in the lectures. (Note that the lecture notes derive the edge detect filter from a Bartlett, so the matrix used in this operation should not be identical). Clamp pixel values that fall outside the range 0-255. | ||
| Edge Enhance | filter-enhance | Apply a 5x5 edge enhancement operator, using a Gaussian filter as the underlying smoothing filter. Use the method shown in class to come up with a single filter that does the enhancement in one pass, or use image subtraction operations if you prefer. You should clamp pixel values that fall outside the range 0-255. | ||
| Image Resizing | All of these functions should change the size of the current image by the appropriate amount. They should also operate on the alpha channel. To do this, you remove the pre-multiplication from the color values, you filter the colors and the alpha, and then you re-apply the pre-multiplication with the new alpha values. | |||
| Half Size | half | Halve the image size, using a 5x5 Bartlett filter to perform the smoothing. | 8 | |
| Double Size | double | Double the image size, using a 5x5 Bartlett filter to compute the intermediate pixel values. | 12 | |
| Arbitrary Uniform Scale | scale | amount | Scale the image up or down by the given multiplicative factor. By uniform scaling I mean scale the x and y axes by the same amount, so the aspect ratio does not change. Use Bartlett filters for the reconstruction. The filter size should vary so that you always pick up at least nine (three by three) values from the input image in constructing each pixel of the output image. | 25 |
| Compositing | image | All of these operations should composite the current image, A, with the specified image, B, using A op B, where op is one of the operations below. The result should replace the current image. Obviously, all of these operations must work with the alpha channel. | 15 for the first 3 for any additional | |
| Over | comp-over | image | See class notes | |
| Inside | comp-in | image | ||
| Outside | comp-out | image | ||
| Atop | comp-atop | image | ||
| Xor | comp-xor | image | ||
| Misc | ||||
| Arbitrary Rotation | rotate | amount | Rotate the image clockwise by the given amount, specified in degrees. The output image should be the same size as the imput image, with black pixels where there is no input image data. Use Bartlett filters for the reconstruction. The filter size should vary so that you always pick up at least nine (three by three) values from the input image in constructing each pixel of the output image. The rotate operation will only be tested on images with alpha=1. | 25 |
| Blue Screen | blue-screen | Extract an alpha image from the current image using the blue-screen method. The current image should be replaced by one that has zero alpha where the original image is close to blue. The input images will all have alpha=1, but clearly your output should have alpha=1 or alpha=0. It is up to you to define "close to blue" appropriately. | 10 |
You can use the reference program to generate sample images, and then use the difference operation to compare your results with the sample. The table below summarizes ways in which your results could reasonably differ from the reference program's.
| Operation | Test Images(s) | Notes |
| gray | colors-for-bw.tga | You should be able to reproduce this exactly. |
| quant-unif | church.tga and wiz.tga | You probably cannot re-produce this exactly. Your result should, however, show the same poor quality and color banding effects. |
| quant-popul | church.tga and wiz.tga | You probably cannot re-produce this exactly. A populosity algorithm should do a reasonable job on the gray floor, and not too bad on the browns. It should, however, draw the blue ball as gray, because there are not enough blue pixels to be popular. |
| quant-med | church.tga and wiz.tga | You probably cannot re-produce this exactly. Your result should, however, show the same good quality. In particular, it should show the ball as blue and the floor as gray. |
| dither-thresh | church.tga and checkers.tga | You should be able to reproduce this almost exactly. Some pixels may be different around the boundaries between white and black. |
| dither-bright | church.tga and checkers.tga | You should be able to reproduce this almost exactly. Some pixels may be different around the boundaries between white and black. |
| dither-rand | church.tga and checkers.tga | You have no chance of reproducing this exactly. Instead, you should get an image that is similar in style but not identical. |
| dither-order | church.tga and checkers.tga | You should be able to reproduce this almost exactly. A few borderline pixels (those close to the threshold) may be different. |
| dither-cluster | church.tga and checkers.tga | You should be able to reproduce this almost exactly. A few borderline pixels (those close to the threshold) may be different. |
| dither-fs | church.tga and checkers.tga | There's a good chance you can re-produce this exactly, but it is not essential. The character of your result should be similar. |
| filter-box | church.tga and checkers.tga | You may get different results around the boundary, but interior pixels should be identical. The reference program extended the size of the input image by reflecting it about its edges. |
| filter-bartlett | church.tga and checkers.tga | You may get different results around the boundary, but interior pixels should be identical. The reference program extended the size of the input image by reflecting it about its edges. |
| filter-gauss | church.tga and checkers.tga | You may get different results around the boundary, but interior pixels should be identical. The reference program extended the size of the input image by reflecting it about its edges. |
| filter-edge | church.tga, checkers.tga and gray-checkers.tga | You may get different results around the boundary, but interior pixels should be identical. The reference program extended the size of the input image by reflecting it about its edges. |
| filter-enhance | church.tga, checkers.tga and gray-checkers.tga | You may get different results around the boundary, but interior pixels should be identical. The reference program extended the size of the input image by reflecting it about its edges. |
| half | church.tga and checkers.tga | You may get slightly different results, particularly around the boundary. |
| double | church-small.tga and checkers-small.tga | You may get slightly different results, particularly around the boundary. |
| scale | church.tga and checkers.tga | You may get different results, but they should be qualitatively similar (no banding). |
| comp-over | zcolorcheck.tga and zred.tga | You should get identical results. You need to look at the alpha channel to check. |
| comp-in | zcolorcheck.tga and zred.tga | You should get identical results. You need to look at the alpha channel to check. |
| comp-out | zcolorcheck.tga and zred.tga | You should get identical results. You need to look at the alpha channel to check. |
| comp-atop | zcolorcheck.tga and zred.tga | You should get identical results. You need to look at the alpha channel to check. |
| comp-xor | zcolorcheck.tga and zred.tga | You should get identical results. You need to look at the alpha channel to check. |
| rotate | church.tga and checkers.tga | You may get slightly different results, particularly around the boundary. |
| blue-screen | blue-screen.tga | You may get slightly different results, particularly around the boundary of the blue screen area. |