ICS 432 Fall 2024

Homework Assignment #9 [50 points + 5 points extra credit]

Overview

In this assignment we enhance the ics432imgapp app in two ways:

In this assignment you have to use GitHub Issues as follows:

How/What to turn in

Preliminaries: What is a Median filter?

A median filter works as follows. Given the pixel at coordinates (x,y) in the input image, compute the median value of the Red, Green, and Blue values over the pixel itself and its neighboring pixels, and assigns these median values to the pixel at coordinates (x,y) in the output image. RGB values are between 0 (darkest) and 255 (lightest). We consider only 8 neighbors for each pixel (north, north-east, east, south-east, etc.), noting that pixels on the border of the image have only 5 neighbors, and pixels in the corner of the image have only 3 neighbors. We define the median as the value at index #pixels / 2 (integer division) in the list of sorted pixel values. For a pixel that has 8 neighbors, it’s index 9/2 = 4; for a pixel with 5 neighbors it’s index 6/2=3, and for a pixel with 3 neighbors it’s index 4/2 = 2;

Let’s see this on an example. Say we have the following pixel (in the center) with 8 neighbors, indicating all R values for all pixels (the computation is similar for the G and B values):


R: 120 R: 54 R: 200
R: 187 R: 132 R: 240
R: 240 R: 18 R: 198


The sorted list of R values for the 9 pixels (the center pixel and its 8 neighbors) is: 18, 54, 120, 132, 187, 198, 200, 240, 240. The median value is the value at index 9/2 = 4, that is: 187 (i.e., the 5-th element). So in the output image, instead of 132, we will have an R value of 187.

The purpose of a median filter it often to remove noise in an image. See below a test input image and its transformation using the median filter (click to see full size images):

Original (noisy) image Cleaned up image using a median filter

Question #1 [10 pts]: Add a Median filter to the app

For this question you are given an implementation (I wrote) of a MedianFilter (download MedianFilter.java and RGB.java and add them to your repo). The program below is an example program that uses the MedianFilter class:

import java.io.*;
import java.awt.image.*;
import javax.imageio.*;

public class MedianFilterTest {

  private final static String output_file_name = "processed_image.jpg";

  // Method to save a BufferedImage to a jpg file
  private static void saveImage(BufferedImage image, String filename){
    try {
      ImageIO.write(image, "jpg", new File(filename));
    } catch (IOException e) {
      System.out.println("Cannot write file "+filename);
      System.exit(1);
    }
  }

  // Main method
  public static void main(String args[]) {

    // Parse command-line arguments
    if (args.length != 1) {
      System.err.println("Usage: java MedianFilterExample <jpg file path>");
      System.err.println("       (output image saved to ./" + output_file_name);
      System.exit(1);
    }

    BufferedImage input=null;
    BufferedImage output;
    BufferedImageOp filter;

    // Read input image
    try {
      input = ImageIO.read(new File(args[0]));
    } catch (IOException e) {
      System.err.println("Error: " + e.toString());
      System.exit(1);
    }

    // Create the output image
    output = new BufferedImage(input.getWidth(), input.getHeight(), input.getType());  

    // Apply the Median filter
    filter = new MedianFilter();
    filter.filter(input,output); // output image already allocated

    // Save the image 
    saveImage(output, output_file_name);

  }
}

Create and address the following GitHub issue:

Issue Title: Add a median filter

Issue Label: new feature

Issue Description:

For all testing in this assignment, you can use these noisy sea slug images on Laulima.

Question #2 [40 pts]: Data-parallel Median filter

Create and address the following GitHub issue:

Issue Title: Add a data-parallel median filter

Issue Label: enhancement

Issue Description:

Todo: In your README file, explain what strategy you used (in particular what data decomposition strategy) to implement data parallelism.

Todo: Run your DPMedian filter on the first noisy sea slug image (noisy_slug_01.jpg) using 1, 2, 4, and N data parallel threads and report on the acceleration factor with respect to the execution with 1 data parallel thread. Your answer must be formatted as a table such as:

1 thread      1.00x 
2 threads     1.65x
4 threads     2.30x
12 threads    3.01x

In your README file briefly discuss the results. Are you overall “happy” with the achieved performance? (If you see no performance boost, there is a bug in your code.)

Question #3 [5 pts - EXTRA CREDIT]: Performance study

When applying the DPMedian filter to a set of images, we can now choose the amount of task parallelism (number of processing threads) and the amount of data parallelism (number of data parallel threads, within each processing thread).

Todo: Using the app, apply the DPMedian filter to all 40 noisy sea slugs images on Laulima and report the execution time for the following combinations of task and data parallelism:

In your README file briefly discuss the results by answering this question: Is it better to do pure task parallelism, pure data parallelism, or to mix both? Feel free to experiment and report on other combinations of task and data parallelism amounts.