[SOLVED] SER 334 Parallel Image Filtering

Arizona State University SER334: Operating Systems & System Programming
Lecturer Acua Revised 1/17/2020
Parallel Image Filtering
Summary: In this homework, you will be implementing a threaded program that loads an image le,
applies a lter to it, and saves it back to disk. You will also practice dealing with threaded algorithms that
include both data spliting and data dependency issues.
1 Background
Figure 1: Application of blur algorithm toWonderbread’s resume portrait. (Image from Dr. Filley’s TMC110
slide deck.)
In this assignment you will write a program that applies a lter to an image. The image will be loaded
from a local BMP le, and then transformed using one of two image lters. The blur lter is shown above as
an example. The resulting le will be saved back to a BMP le that can be viewed on the host system. It is
highly suggested that you develop non-multithreaded versions of the lters before beginning
to thread them.
This document is separated into six sections: Background, Requirements, Box Blur Filter, Swiss Cheese
Filter, Include Files, and Submission. You have almost nished reading the Background section already. In
Requirements, we will discuss what is expected of you in this homework. In the Box Blur Filter and Swiss
Cheese Filters sections, we discuss the idea of each of the respective algorithms. In Include Files, we list
several les that may provide useful functions for your algorithms, and suggest two ways to handle BMP le
IO. Lastly, Submission discusses how your source code should be submitted on Canvas.
2 Requirements [40 points]
Your program needs to implement loading a binary BMP le, applying an image lter to its pixel data
(described in the next section), and saving the modied image back into a BMP le. If it helps, you
may assume that images will be no larger than 4096 by 4096 pixels (see the MAXIMUM_IMAGE_SIZE
constant in the base le). Assume that all BMP les are 24-bit uncompressed les (i.e., compression method is
BI_RGB), which have a 14-bit bmp header, a 40-bit dib header, and a variable length pixel array. Regarding
threading: it is suggested that you start by hard-coding your program to use four threads to compute the
result. Later, extend it to allow an arbitrary number (create and use a constant called THREAD_COUNT).
As a base requirement, your program must compile and run under Xubuntu (or another variant of Ubuntu)
18.04. Your program must also support reading and writing uncompressed 24-bit BMP les. Sample output
for for the blur lter is shown on the right side of Figure 1.
Your general approach to parallelizing the algorithms will be to break (decompose) the image into pieces,
in parallel compute the ltered result for the pieces, and then combine the images into a nal result. See
Figure 2 for an example.
1
Figure 2: Example decomposition of input. Notice that data will be balanced among threads.
 Specic Requirements:
 File names and lter selection: Read the input le name, output le name, and image lter from
the command line arguments. Assume that users always provides all three, and the les will be
valid (they exist and are BMPs). Your program must support being used as: ./LastNameFilters
-i in.bmp -o out.bmp -f b. For the lter argument, ‘b’ stands for blur lter and ‘c’ stands for
cheese lter. [2 Points]
 Blur lter lter:
 Apply the box blur algorithm to each pixel in the data.
 Compute the box blur algorithm in parallel with pthreads. It is suggested that you divide
work into columns. Work must be evenly distributed over a number of threads dened by a
constant called THREAD_COUNT. You may assume that is less than the image’s smallest
dimension, but we will pick the specic value (could be anything) when we compile/grade
your program.
 Each thread must use an independent memory allocation of a minimal size. For example: if
you have an image that is 64×64 pixels and it is be run with two threads, you will be creating
two threads where each processes a 32×64 region. Your program needs to perform allocations
for each of the sub-regions, and pass it to the appropriate thread. Note that sub-regions will
not be exactly 32×64 in size – they will be slightly larger. Add exactly the amount of padding
to the region each thread gets in order for the lter to be computed correctly. (So if a lter
requires information from each of the adjacent pixels, then a sub-region would look more like
33×64 to include an extra column of pixels to compute column 32.)
 Swiss cheese lter lter:
 Apply the Swiss cheese lter to the data.
 Compute the Swiss cheese lter in parallel with pthreads. Each thread should only know
about holes that it has to render. Same details apply as for box blur. (Note: a single hole
may be spread across multiple threads if it lies on a column border. This is a data splitting
issue.)
 Each thread must use a independent memory allocation of a minimal size. Same details apply
as for box blur (but you won’t need padding).
3 Box Blur Filter
The rst lter we will be applying in this assignment is called a box blur. It takes a specic neighborhood of
pixels and processes it (this is a so-called stencil operation). A given output pixel is computed as the average
2
of itself and each of its neighbors. This is an example of data dependency. We will use a neighborhood size
of 3×3. In the following example, we are looking at a pixel (the 100, 0, 0 one) at the bottom of an image.
There are 6 valid pixels in the neighbor, so we add them and divide by 6 to produce the output pixel for
that position in the output image.
!
(0, 0, 0) (0, 0, 0) (0, 0, 0) (0, 0, 0) (0, 0, 200)
(0, 0, 0) (0, 0, 0) (0 ,0, 0) (0, 0, 0) (0, 0, 200)
(0, 0, 0) (0, 0, 0) (100, 0, 0) (0, 0, 200) (0, 0, 200)
! (0;0;0)+(0;0;0)+(0;0;0)+(0;0;0)+(100;0;0)+(0;0;200)
6 = (16; 0; 33)
Figure 3: Computing blur result for pixel at (2, 2) in an image.
4 Swiss Cheese Filter
This lter is designed to make the input image appear to be a piece of Swiss cheese. The Swiss cheese lter
has two steps:
1. Tint the image (at the pixel level) towards being slightly yellow. The exact tint is left as a design
choice – you may use any method (or RGB shift) provided that it results in an output image that is
noticeably more yellow (or buttery yellow).
2. Randomly draw black circles in the image. See Figure 4. Holes should be uniformly distributed along
the x- and y-axis. Holes must be circles. The radius of the holes should be computed in a such a way
that average sized holes are most common, and then smaller or larger holes are less common. The
average radius in pixels of a hole should be 10% of the smallest side of the input image (e.g., if an
image is 130 pixels, then the average radius is 13). The number of holes should also be 10% of the
smallest side (e.g., if an image is 130 pixels, then there will be 13 holes).
Figure 4: Cheesebread example. Holes only, no tinting. (Exact results will dier.)
5 Include Files
To complete this assignment, you may nd the following include les useful:
 stdio.h: Denes standard IO functions.
 stdlib.h: Denes memory allocation functions.
 int rand() – returns a number between 0 and RAND_MAX.
 void srand( int seed) – seeds the random number generator.
 pthread.h: Denes functionality for manipulating threads.
 Useful functions:
3
 int pthread_attr_init(pthread_attr_t *attr) – Populates a pthreads attribute struct (pthread_attr_t)
with default settings.
 int pthread_create(pthread_t *thread, const pthread_attr_t *attr, void *(*start_routine)
(void *), void *arg) – Creates a new thread with the id of thread, attributes specied by
attr, and some data arg.
 int pthread_join(pthread_t thread, void **value_ptr) – Blocks until the specied pthread_t
thread has terminated.
 Useful types:
 pthread_attr_t – Contains attributes for a pthread thread.
 pthread_t – Contains a pthread thread id.
 math.h: Denes additional functionality for manipulating strings.
 Useful functions:
 double sqrt(double x) – Takes the square root of a number.
Note that this assignment does not require mutexes or other locks. If you want to include any
other les, please check with the instructor or TA before doing so.
5.1 Loading Binary Files
It is not expected that you implement a BMP reader/writing for this assignment, instead you should use an
already existing one. For loading the BMP les, you have two options:
1. Reuse your own personal code from the SER334 CP3 programming assignment.
2. You may use the object le that we created, and which contains an already implemented BMP reader/
writer. (Think of it as a package in Java.) An object le is a binary representation of a source le,
used prior to linking it to other resources (e.g., standard libraries) to create a nal executable le. In
order to use the object le, you must be under the VM setup described at beginning of
the course. Specically, (x)Ubuntu 18.04 with 64-bit gcc. Using the library has three steps:
(a) Add BmpProcessor.o, PixelProcessor.h, BmpProcessor.h to your source code folder.
(b) Include the BmpProcessor.h header in your main le.
(c) When you compile your project, you will need to set up your linker to include the object le
(BmpProcessor.o), otherwise if you call the functions from the For example, if you’re using GCC
and your main le is called LastNameFilters.c, you will run the command gcc LastNameFilters.c
BmpProcessor.o -o LastNameFilters to compiler your .c le, link it with the .o, and produce
the LastNameFilters nal executable. LastNameFilters can then be run using commands such as
./LastNameFilters -i wonderbread.bmp -o blurrybread.bm p -f b.
5.2 Linking with External Libraries (pthreads)
By default, including a header le into your project only adds the code associated with that le to your
project. For les like stdio.h or stdlib.h, which are self contained, that is enough. However, for other include
les like pthread.h or math.h, we need to make sure that our object les (produced from our .c) is also linked
with the library object le that supports that functionality. In GCC, we will do this with the -lm argument
for math.h and -pthread argument for pthread.h.
If you are using the command-line to compile, or a makele, then these arguments should be appended
to the end of your GCC command. For example:
gcc c s ome f i l e . c lm pthread
4
NetBeans is a little more complicated Open your project in Netbeans. Right click the title of the project
and select Properties. This will open up a new window called Project Properties. Select the Linker page
from the left categories menu. At the bottom is a Additional Options line, which you can edit or open with
the ellipsis button. There you can add any arguments that you need. In the sample screen shot, both the
math and pthread libraries have been enabled.
6 Submission
The submission for this assignment has one part: a zip le for all your written code and header les
submission. The le should be attached to the homework submission link on Canvas.
Writeup: For this assignment, no write up is required.
Source Code: Please name your main class as “LastNameFilters.c” (e.g. “AcunaBoxFilters.c”) inside
the zip le.
5
If your program fails to compile out-of-the-box, there will be a mandatory deduction 20% from the
assignment points.
If you do not follow the file submission standards (e.g., the submission contains project files, lacks a
proper header), there will be a mandatory deduction of 10% from the assignment points.
If compiling or running your program differs from stated on the assignment and it is not specified as a
requirement, please include a readme file with steps to execute the program. If you do not, there will be a
mandatory 10% deduction from the assignment points.
Example readme
gcc ForresterFilters.c BmpProcessor.h BmpProcessor.o PixelProcessor.h -lm -lpthread -o ForresterFilters
./ForresterFilters -i in.bmp -o out.bmp -f c
where “c” is for swiss cheese filter or “b” for box blur filter
This implementation uses the 64bit BmpProcessor.o object file.