All at Once!
Concurrency
Medianizer
Overview
Digital images are often ‘filtered’ to produce a more aesthetic or artistic image than the original. In this problem, you are given the name of a file containing an image in the BadImage file format (described at the end of this document). Given two integer arguments M and N you must write a program to concurrently median filter the input file and save the result to an output file.
Explanation
Digital Image Excursus
A digital image is, as an abstraction, a 2D array of colors. For this assignment, we will describe a digital image in the narrative as a 2D array of integers (each integer denoting a grayscale value in [0, 255]). But note, that your code is required to use 1D arrays rather than the intrinsically awful choice of 2D arrays. This suggests that you must write code that makes a 1D array appear to be a 2D array; most likely by writing a class that contains a 1D array of integers along with methods that operate on that array via two separate indices rather than one.
Median Filter Background
Consider a 2D integer array SRC that is to be median filtered to produce a 2D integer array DEST. Consider an element of SRC that is at location (x,y) such that x is the column and y is the row index. To compute DEST(x,y) we consider those SRC elements that are in the MxN rectangular region centered on SRC(x,y) where M is the width of the rectangular region and N is the height of the rectangular region. DEST(x,y) is computed by finding the median value of these MxN SRC elements. The output image DEST is generated by computing this value for all DEST(x,y). Also, for this problem we will define SRC(A,B) to be zero for any index A or B that is outside of the range of valid indices of the source.
Concurrent Technique
You must write the following classes in order to perform median filtering on a digital image.
•Write a tiler class that takes a 2D array and provides tiles on request. The tiler should support a method named java.awt.Rectangle nextTile(). The size of the tiles should be parameterized such that applications are free to select the size of tiles perhaps (although not necessarily) related to the system on which they are running.
•Write a median thread. Constructing the thread requires that clients supply a 2d source array, a 2d destination array, the values M and N and a tiler. The thread operates by 1) requesting a tile from the tiler, 2) computing the median of all elements in that tile using the SRC and DEST as input/output and 3) repeating this process until there are no more tiles. Each thread should support a “getNumberOfElementsProcessed” which returns the total number of destination cells that were processed by that thread.
•Write a program that can be run from the command line. The name of the program must be Medianize. The arguments must be 1) the name of the input file 2) the name of the output file 3) the number of threads to use 4) two positive integers denoting M and N (the size of the median filter region) and 5) two numbers denoting the tile width and tile height. The input and output files must be in the BadImage format.
Testing
Since testing is one of your favorite activities, this project requires that you complete the following test suite. A single test consists of a SRC file, a median-filter size, a tile-size and a number of threads. You must run your test suite on all possible combinations of input-file, median filter size (i.e. MxN), tile size (i.e. WxH) and number of threads given in the list below.
•SRC files: test1.bif, test2.bif
•Median filter size: (3×3), (13×13), (25×25)
•Tile size: (3×3), (16×16), (32×32), (64×64)
•Number of threads: 1, 2, 4, 8, 16, 32, 64
This test-suite dictates a total of 2x3x4x7=168 tests, each of which must be recorded in tabular form (the format is shown below) and submitted as an HTML document. For each test, you must determine the time your code takes to compute the median of the source and enter the number of milliseconds in the time column. This time should not include the time taken to read in the input file, create the destination, or write to the output file. The value should include only the time taken to compute the median. You must also determine the total number of cells processed by each thread and enter those values in the “Cell Count per Thread” column. In general, these values should be approximately but not necessarily exactly equal. The sum of these values must equal the total number of cells in the source array.
You must also indicate the CPU on which you are running and how many cores your CPU contains. You must use a CPU having at least 4 cores. You must also comment on the way in which the number of threads used and the tile size affects the overall runtime of your program.
SRC
M
N
TileW
TileH
Time (ms)
Cell Count/Thread
The BadImage Format Specification
A BadImage file is a binary file that has the following format
1.The first 14 bytes are encoded as UTF-16 characters containing the literal text BIF2018
2.The next 4 bytes contains two 2-byte signed integers denoting the image width W and image height H.
3.There are W×H 2-byte signed integers that follow. Each value is in the interval [0, 255]. The pixels are arranged in row-major order: top-to-bottom; left-to-right.
I’ve provided a homebrew conversion utility named Biffer that converts from (jpg|png|gif) to bif and also from bif to png. This will make it easier to test your code as you’ll be able to visualize the output of your program (i.e. the bif files).
Requirements
Submit your code in GitLab under a folder named “hw7”. Within this folder you should have your Java project and a file named tests.html.
CS 421 : Programming Languages
© Kenny Hunt
Reviews
There are no reviews yet.