CSE 160 – Spring 2000
Berman/Papadopoulos
Program #2 – DUE May 19, 2000
1)
Read
ll.5 to learn about Edge Detection and the Sobel operator.
2)
Write
a Master/Worker PVM with a master called edgeMaster and a worker called edgeWorker.
EdgeMaster takes four arguments.
a.
P
– Number of workers
b.
K
– strip size of decomposition
c.
Input
image file
d.
Output
image file
Example: edgeMaster
4 8 fido.image fido.out
Start 4 workers and divide fido.image into 8 strips.
Fido.out is the output file
3)
EdgeWorker
takes no arguments with all configuration data passed to it by its master program.
4)
The
output file is PGM-formatted file that contains the transformed image
The Sobel algorithm: Each image is an NxM
matrix of pixel values. Consider an arbitrary pixel x4 and it’s immediate
neighbors:
----------------
| x0 | x1 | x2 |
----------------
| x3 | x4 | x5 |
----------------
| x6 | x7 | x8 |
----------------
To compute a new value, x4’, in place of
x4, the following weighted average formula is used
x4
‘ = (w0 * x0) + (w1 * x1) + (w2 * x2) + (w3 * x3) + (w4 * x4) + (w5 * x5) +
(w6 * x6) + (w7 *
x7) + (w8 * x8)
---------------------------------------------------------------------------------------------------------
9
The values w0,...,w8 are referred to as a
mask.
----------------
| w0 | w1 | w2 |
----------------
| w3 | w4 | w5 |
----------------
| w6 | w7 | w8 |
----------------
The edge detection algorithm using the Sobel
operators requires 2 masks
---------------- ----------------
| -1 | -2 | -1 | | -1 | 0 | 1 |
---------------- ----------------
| 0
| 0 | 0 |
and | -2 | 0 | 2
|
---------------- ----------------
| 1
| 2 | 1 | | -1 | 0 | 1
|
---------------- ----------------
mask 1 mask 2
Each mask is performed on the original
values of the image. Say the result of the value of a pixel after applying mask
1 is x4'' and the result of the value of a pixel after applying mask 2 is
x4'''. Then the value of x4' is the addition of the absolute values of x4'' and
x4''':
x4' = |x4''| + |x4'''|
How do you handle the border values? Just
put a border of 0's around the image (also known as ghost cells).
For
this implementation, you will decompose the NxM image into K horizontal
strips. EdgeMaster will read the input
file and start up P edgeWorker tasks. The master will send strips of size M/K to a
worker task. The first worker will get the first strip, the second the second
strip and so on up to the first P strips. Each edgeWorker task will calculate
the Sobel transform for its strip and send back the results. As workers finish
a strip, more work is handed out to it by the master until all K strips have
been transformed.
One
thing to think about. If you label the horizontal strips as
S0
S1
S2
S3
.
.
.
SK
Then,
the top row of block S1 will need information from the bottom row of S0 in order
to calculate its transform. The bottom row of S1 will need the top row of S2 to
calculates its transform. It is easier if the master simply sends the top and
bottom rows of the lower and upper strip neighbor along with the strip’s data.
Hence if a strip has R rows, then the master will send R+2 rows of data to the
worker. This “trick” keeps the workers from communicating with other workers to
get the needed information.
Images:
Input
and output images will be in ASCII PGM (Portable graymap file format). You can
find more information about PGM in the man pages by typing 'man pgm'. Briefly,
a PGM file looks something like the following.
<magic
number><whitespace><width><whitespace><height><whitespace><max
gray value><whitespace><width*height gray pixel values>
So, for example,
P2
1024 768
255
168 169 169 169 169 169 169 169 169 169
170 170 171 171 171 171 176
...
magic number: The file format id...P2
stands for PGM in ASCII format
width/height: The dimensions of the
image in ASCII format
max gray value: in ASCII format
width*height gray pixel values:
Integers from 0 to <max gray value> separated by whitespace
Note: Lines should not exceed 70
characters
Timing:
You should time the total execution time
of your program (the master can handle this).
Feel free to insert any other
additional timing messages that you think are important.