Horizontal Image Blur

Due: November 2

Objective

To gain experience writing multi-threaded programs with OpenMP, and applying Amdahl's Law to a program

Task

For this assignment, you will write a parallel program to load an image file, add a horizontal blur, and save the blurred image to a file.

You will also apply Amdahl's Law to predict the expected speedup and compare this to the actual performance of your program.

The PPM Image Format

Most image file formats write the image data in binary, and utilize compression in order to keep the file sizes small. Unfortunately, this makes reading them in quite difficult. In contrast, the PPM image format is quite simple and easy to work with.

A PPM image file starts with a line containing "P3". This is a marker that identifies the file as being a PPM image.

The second line contains two integers, separated by a space. These are the width and the height of the image.

The third line contains one integer, the maximum color value for the image. This should be the value 255, the largest value that fits into an unsigned byte.

The rest of the file is composed of $3 \times W \times H$ values which give the color data of the image. There is one set of three values for each pixel. The first of these is the red component, the second is the green, and the third is the blue.

The color values will be separated by whitespace.

Because PPM images are textual, you can open them with a text editor such as Vim.

You should load the PPM image into your program:

Read the "P3" identifier. If it's not there, print an error and exit.
Read the width and height of the image.
Read the max color value. If it's not 255, print an error and exit.
Allocate space to hold the color data.
Read all of the values of the file into your program.

You will also need to write a PPM file:

Print the "P3" identifier, then a new line.
Print the width and height of the image, then a new line.
Print the max color value of 255, then a new line.
Print all of the color values to the file, separated by white space. To make the file easier to read with a text editor, you can insert new lines every so often.

Horizontal Blur Algorithm

Any kind of blur is essentially making every pixel more similar to those around it. In a horizontal blur, we can average each pixel with those in a specific direction, which gives the illusion of motion.

For this program, we will calculate each new pixel's value as half of its original value. The other half is averaged from a fixed number of pixels to the right. This fixed number can be called the BLUR_AMOUNT. The larger the value, the more blurring that will occur.

This is done independently for the red, green, and blue components of each pixel.

This is expressed in the following algorithm:

For each row of the image:
- For each pixel in the row:
  - Set $r$ to be half the pixels red component.
  - Set $g$ to be half the pixels green component.
  - Set $b$ to be half the pixels blue component.
  - For $i$ from 1 up to BLUR_AMOUNT:
    - Increment $r$ by $R \times \frac{0.5}{BLUR\_AMOUNT}$, where $R$ is the red component of the pixel $i$ to the right of the current pixel.
    - Increment $g$ by $G \times \frac{0.5}{BLUR\_AMOUNT}$, where $G$ is the green component of the pixel $i$ to the right of the current pixel.
    - Increment $b$ by $B \times \frac{0.5}{BLUR\_AMOUNT}$, where $B$ is the blue component of the pixel $i$ to the right of the current pixel.
  - Save $r, g, b$ as the new color values for this pixel.

You must also ensure you don't access pixels off the bounds of the image. For example, the third pixel from the right should only average itself (half weight), and the next two (at a quarter weight each).

For this program, set the BLUR_AMOUNT variable to 50.

Test Files

You can test your program with the following input files. You will load the file in the PPM format. Also included below are online viewable JPG versions of the original, and what the result should look like after the horizontal blur has been added.

PPM File	JPEG Version	Blurred Version
eagle.ppm	eagle.jpg	eagle-blur.jpg
car.ppm	car.jpg	car-blur.jpg
farmer.ppm.gz	farmer.jpg	farmer-blur.jpg
tower.ppm.gz	tower.jpg	tower-blur.jpg

The two largest files have been compressed with gzip so they will download more quickly. Uncompress them with the gunzip command.

To create your own PPM images, you can use the following command:

$ convert -compress none [input] [output]

Where [input] is replaced by any PNG, JPG etc. file, and [output] is replaced by the name of the PPM you wish to produce. You must use the correct extensions for this to work.

To convert from a PPM image to another format, you can also use the convert function:

$ convert [input] [output]

Where, in this case, [input] is your PPM image, and [output] is the file you wish to create (e.g. some file that ends in .jpg or .png).

It is recommended that you convert your PPM images to JPG to view your results as the PPM format is not widely supported, and is also much larger.

The convert command is part of ImageMagick.

Step 1: The Sequential Version

First, create a sequential version of this program in C or C++. The program should take the name of the input PPM image file as the first parameter, and the output file name as the second.

It should load the image, apply the blur effect, and then save the image.

You can test your program on the test images above to ensure that it works.

Step 2: Applying Amdahl's Law

This program has portions which can be easily parallelized (the blur effect), and portions which cannot (loading and saving the files).

Add timing calls into your program so that you calculate the amount of time each of the three major operations takes (loading the file, applying the blur, and saving the file).

Run your program on the "tower.ppm" input file and record the amount of time each portion takes.

Next, apply Amdahl's Law. Given the time each portion takes, what speedup can you expect in the best case, if we run this program with 2, 4, 8, and 16 threads?

Answer these questions in a separate document using complete sentences.

Step 3: Parallelizing with OpenMP

Next parallelize the blur effect code with OpenMP. Be sure to do it in such a way that it does not change the behavior of the program.

Step 4: Performance Analysis

Finally, run your parallel program with 2, 4, 8 and 16 threads. Add to your report the actual speedup you achieved in each case, with the "tower.ppm" image. How close was Amdahl's law to the actual results?

Submitting

When your program works, submit the source code of the parallelized version and the analysis to Canvas.