CS448f: Assignment 2

Your task

Your task this week is to implement a fast Gaussian blur.

ImageStack's current algorithm takes a floating point frames, width, and height, and performs a gaussian blur with those standard deviations. The blur is performed out to three standard deviations. If given only two arguments, it performs a blur in x and y only. If given one argument, it performs the blur in x and y with filter width the same as height. While this method is accurate, it is not fast.

Although this assignment still has a bound on RMS error with respect to the current gaussian blur implementation, the emphasis of this assignment is an increase in speed. Your task is to approximate the effects of convolving with a Gaussian in the spatial domain (and multiplying with a Gaussian in the frequency domain). Don't use SSE however - your code must still be clean and readable.

[credit: Wikipedia]

The figure above shows the Gaussian function in the spatial domain with 4 different standard deviations. Remember, the Fourier transform of a Gaussian is also a Gaussian.

Getting Started

You should all have ImageStack working from the previous assignment, but if for some reason you don't, refer to the instructions in Assignment 1.

The -gaussianblur operation is in Filter.cpp. Make a new gaussianblur operation called "-gaussianblur2" so that you can compare the old and new versions easily. To make a new operation, you need to add a class declaration to Filter.h, an implementation to Filter.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 -gaussianblur better is so we'll all have a better gaussianblur algorithm. If we can't read the code, we can't really benefit from it.

20% of your grade is for making a -gaussianblur operation that is correct and artifact-free --that is, it we don't want something that produces a low root-mean-square (RMS) difference with respect to ground truth, but doesn't actually do the right thing (yes, this is possible!). We'll test that by visually inspecting the output:

ImageStack -load somerandomjpeg.jpg -gaussianblur2 [some standard deviations] -display

40% of your grade is for making a gaussianblur2 operation that's faster than the current gaussianblur. You should aim for making it at least 5x faster than "-gaussianblur 6" regardless of what filter size we choose. For example, "-gaussianblur2 128" should run 5 times faster than "-gaussianblur 6".

20% of your grade is for maintaining the accuracy of your new gaussianblur2. We'll measure the accuracy using the RMS difference between the output of the original gaussianblur method and the result of gaussianblur2, at a variety of randomly chosen standard deviations between 2 and 64. We won't consider values within three standard deviations of the image boundaries. You should try to keep the RMS difference between your method and the original gaussian blur below 0.005.

Note that the current -gaussianblur is not completely accurate - it truncates the Gaussian at 3 standard deviations. If your method approximates the Gaussian to more than 3 standard deviations, that is, your are MORE accurate in approximating a Gaussian convolution than the original method, calculating the RMS with respect to the current gaussianblur will not be a good metric of your success. In that case, for calculating your RMS score, you can extend the support of the original -gaussianblur for accuracy comparison purposes. You should then submit your modified -gaussianblur as well so we can do the comparison on your terms. We still, however, expect you to surpass the speed of the original -gaussianblur.

Here's how we will test speed:

for R in (a range of numbers between 2 and 128); do
  ImageStack -load pics/dog1.jpg -time --gaussianblur 6 -time --gaussianblur2 $R

Here's how we will test accuracy:

for R in (a range of numbers between 2 and 64); do
  ImageStack -load pics/dog1.jpg -dup -gaussianblur $R -pull 1 -gaussianblur2 $R \
             -subtract -crop $R*3 $R*3 width-$R*6 height-$R*6 -rms

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 8, with the subject "cs448f assignment 2 submission".


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) and whose is the most accurate (while running at least 5x faster than "-gaussianblur 6" regardless of parameter settings). We'll use a variety of standard deviations, between 2 and 128 for speed and 2 and 64 for accuracy. Competition placement does not affect grades. We'll hold the competition on the Tuesday after the due date.