Analysis of Algorithms: Project 2

Deadline: March 1

The project involves application of sorting algorithms to median filtering of an image, which is a technique for smoothing a "noisy" image. For each pixel of an image, the filtering procedure considers an (n x n) window centered on that pixel, computes the median of gray-level values in the window, and replaces the original pixel with the median value. The median is defined as the middle value in a sorted sequence. For example, consider the following (3 x 3) window of pixels:
 11  90  74
 71  14  92
 20  87  68
The sorted sequence of these pixels is <11, 14, 20, 68, 71, 74, 87, 90, 92>, and the middle of the sequence is 71, which is the median of the window; thus, the filtering procedure will replace the center pixel with 71.

The result of replacing all pixels with median values is a smoothed image, with almost no background noise, which improves the effectiveness of image-recognition algorithms. On the negative side, the new image is blurrier than the original, that is, it looks like an unfocussed monitor.

Your task is to implement sorting algorithms for median filtering. You should copy the source files median.c and mysort.c to your account; in addition, you need the old files imageio.h and imageio.c. The median.c file contains the filtering procedure, which calls three sorting functions from mysort.c. You should write the code for these functions: insertion_sort, quick_sort, and counting_sort. The mysort.c file already includes the names and argument declarations for the sorting functions, and you need to code their bodies. You should not modify any files except mysort.c, and you should submit only mysort.c to heath@suntan.eng.usf.edu.

You should then apply the filtering procedure to the enb.pgm file, which is a noisy image of the Engineering Building II. To download the image, point the mouse, click the right button, and then select "Save Link As" or "Save Target As" in the resulting menu. To apply the filtering, compile median and use the following syntax to run it:

median -n # [-insertion | -quick | -counting] input.pgm output.pgm

The "-n #" argument specifies the window size, for instance, "-n 5" means the (5 x 5) window; the second argument is the choice of sorting; and the last two arguments are the input and output file. For example, you may run the filtering with a (5 x 5) window, using quick_sort:

median -n 5 -quick enb.pgm filtered.pgm

The procedure produces a smoothed PGM image and displays two numbers: the window area (in pixels) and the filtering time (in seconds). For example, if you run "median -n 5 -quick ...," it may display "25 1.950000," which means that the window is 25 pixels and the running time is 1.95 seconds.

You should run the filtering procedure with different sorting functions, and with window sizes ranging from (2 x 2) to (20 x 20). For each of the three sorting techniques, plot the dependency between the window area and running time, and include it into your report. In addition, answer the following questions in the report:

 Back to the Projects page