CS448f: Assignment 1

Your task

Your task this week is to implement a fast, accurate rotation algorithm. ImageStack's current algorithm uses the lanczos filter described in class for sampling. It looks like this:

And its Fourier transform looks like this:

Notice that it amplifies some frequencies.

This isn't a big deal if you just resample once or twice, but if you resample a lot, it starts to become noticeable. Here's what happens if you rotate our favorite dog by 5 degrees 72 times:

The amplified frequencies are starting to look nasty. If we rotate the image by 1 degree 360 times, you get this:

Ugh... the amplified frequencies have dominated everything else. Your task is to make rotate better. Firstly, it should preserve as many frequencies as possible, without amplifying any. Secondly, try and make it run faster. If you search online for ways to make image rotation fast, you might find some neat tricks to try. Don't use SSE however - your code must still be clean and readable.

Getting Started

Download ImageStack. There are makefiles for various systems in the "makefiles" directory. Copy one that looks plausible into the objs directory and modify it to work on your system. If you have trouble getting ImageStack compiled, come to office hours for help.

Once you have ImageStack working, you can start to modify it. The -rotate operation is in Geometry.cpp. Make a new rotate operation called "-rotate2" so that you can compare the old and new versions easily. To make a new operation, you need to add a class declaration to Geometry.h, an implementation to Geometry.cpp, and you need to hook your new operation into the list of available operations (operationMap) in Operation.cpp.

Grading Criteria

20% of your grade is for clean readable code - the point of making -rotate better is so we'll all have a better rotation algorithm. If we can't read the code, we can't really benefit from it.

20% of your grade is for making a -rotate operation that is correct. We'll test that by visually inspecting the output:

ImageStack -load a.jpg -rotate2 some number of degrees -display

20% of your grade is for making a rotate operation that's faster than -rotate. It should be at least as fast, and you should aim for making it about 50% faster while meeting the accuracy requirement.

-ImageStack -load a.jpg -time --loop 360 ---rotate2

40% of your grade is for making a much more accurate rotate operation. We'll measure the accuracy using the root-mean-square difference between the input image and the result of rotating an image 360 times by 1 degree using your algorithm. To remove any possibility of using sneaky tricks to save the original image somewhere, your operation will not be allowed to access disk, and we'll test it using 360 distinct invocations of ImageStack like so:

for ((i=0;i<360;i++)); do
	ImageStack -load im.png -rotate2 1 -save im.png
done
ImageStack -load orig.png -crop width/4 height/4 width/2 height/2 \
           -load im.png -crop width/4 height/4 width/2 height/2 \ 
           -subtract -rms

Note that we only compare the middle portion of the image, so you can do whatever you like for a boundary condition. You should achieve an RMS of at most 0.07, and you should aim for something closer to 0.05.

Due Date and Submission

Email your modified ImageStack files, in a zip archive, to cs448f-aut0910-staff@lists.stanford.edu by midnight on Thursday Oct 1, with the subject "cs448f assignment 1 submission".

Competition

We'll take the fastest and most accurate entries, and have a run-off in class between them to see whose is the fastest (while meeting the RMS limit of at most 0.07) and whose is the most accurate (while running at least as quickly as the original -rotate). Competition placement does not affect grades. We'll hold the competition on the Tuesday after the due date.