Fifth Homework
Posted 19 Oct 2004 by herman

Use agenda-style parallel programming, with the Python version of Linda, to do some image processing.

Python is hardly the ideal language for image processing, where efficiency is an important concern, however this is a creative exercise for agenda-style parallel programming.

The homework is due anytime on Thursday 4 November.

Submit your homework using the submit command. The submit command (executed on a CS department machine) will copy a directory containing your homework programs. The command will ask you for a target directory: respond c118/hw5 to that question.

To do this homework, you'll need Linda.py and some other files mentioned below.

Agenda-Style

Remember, in this style, the number of threads is not important: your program will work with one thread, two threads, or any number of threads. The run method for each thread is the same: the thread looks for something to do (encoded as some kind of "work" tuple), then removes that tuple, possibly creates new work tuples and adds them to the tuplespace, and also uses the tuplespace to store results of calculations.

One difficulty about the agenda style is the problem of termination. How do the worker threads ever know they are done, and can stop looking for work (ending the thread)? Typically, this is done by the main program. After it starts the threads, it has to look for some indication in the tuplespace (possibly using T.Rd) that the entire computation is complete. Then it can add a special tuple(s) so that the "work" which each thread finds is essentially a command to quit working.

Image Processing

For this assignment, we use one of the simplest image files, a PGM-file with pixels encoded in greyscale values ranging from 0 (darkest) to 255 (lightest). Here is a Python module to read and write PGM files: pgm.py. An example of a program using the module is: testpgm.py. It takes input, a file named blob.pgm, and writes a new version of this to newblog.pgm: the output is reverse video of the input. Sample of PGM files are given below you can experiment with.

Side remark: if you're interested in actually viewing the image, the xv command (available on some Linux systems) can display pgm files; on Linux systems without the xv command, the command "ppmtogif newblob.pgm > newblob.gif" may produce a GIF file from the pgm, and then you could use a browser or other program to view the result. I didn't figure out how to view the images in Windows.

The Problem: Darken an Area in the Image

The programming problem, to be solved using Linda tuples and the agenda style, is to identify the largest contiguous area in the input image that is "darker than average" and then make that area twice as dark in the output. Here is a working program that does just that (but not using parallel programming or tuples): avgpgm.py. Input is a file blob.pgm and output is written to the file newblob.pgm.

Samples of Input and Output

Here are some examples of input and output (the output was generated by avgpgm.py).

  1. Input: a 64-pixel (very tiny) image consisting of a single row of 64 pixels: line-pgm.txt. The output for this is newline-pgm.txt. This tiny image is not easily viewable, but it is sometimes important to have a very small example of input and output during initial debugging.

  2. Input: a 32 by 32 pixel image: smallblob-pgm.txt, and the output, newsmallblob-pgm.txt. This small example exercises the two-dimensional aspect of the problem, but is still small enough for debugging purposes (only 1024 pixels).

  3. Input: a 120 by 120 pixel image: blobs-pgm.txt, with output newblobs-pgm.txt. Here is the same, shown as images: before -- blobs.gif, and after -- newblobs.gif.

Of course, for any of the above inputs, after downloading, you would have to rename them to "blob.pgm" in order to run testpgm.py or avgpgm.py, because these two examples are two primitive to have filename parameters.

Hints, Advice

  • Start with a less ambitious task: just write a program that computes the average pixel value, using the agenda-style of parallel programming. Even if that is all you accomplish, turning this in will show some progress on the homework.

  • You'll receive very little credit for a solution that always does the work in one thread. Such a solution would violate the spirit of parallel programming.

  • Try adding print statements to avgpgm.py if you don't understand how it works (your own version will likely copy much of the logic of avgpgm.py). You can have the program print dictionaries, lists, and other variables as it runs. The print output can be overwhelming, but not so much if you use the small line-pgm.txt as input.

Home PageHelp PageView ArticlesView Public DocumentsLogin, do stuff (record diaries)List Group MembersList of Projects