Spring 2000

An image is a 2D array of values called pixels. A binary image is a 2D array of 0's and 1's where the 0 pixels represent background and the 1 pixels represent objects of interest. For example, the following image contains three objects of interest.

As you can see, a region of interest is a connected set of 1 pixels. The connected property means that from any 1 pixel, there is a path of 1's to any other 1 pixel in its region of interest. The path can be found by starting at the starting 1 pixel and trying each of its 8 neighbor pixels (recursively) until the destination 1 pixel is reached. The path from pixel [1,3] to pixel [3,2] in the first connected region is shown below.

The connected regions of 1 pixels are called connected components . A labeling of a binary image is a new image of the same size where the separate connected components are each given distinct numeric labels. In our image that has three connected components, the first found would be given label 1, the second found would be given label 2, and the third found would be given label 3, as shown below.

An algorithm that takes in a binary image and outputs a new labeled image with distinct labels for each connected component is called a connected components labeling algorithm . In this assignment, you will design methods for an image class and, in particular, the methods that implement a recursive connected components algorithm.

Details

1. The image class has 4 fields: row, col, max_value, and array.

row is the (integer) number of rows in the image.
col is the (integer) number of columns in the image.
max_value is the largest value in the image (the smallest is assumed to be zero).
array is a 2D integer array that has row rows and col columns.

2. We will give you files that contain test images. These files are in PGM (Portable Gray Map) format. They contain header information (information about the image format and size) followed by the actual image data. We will provide you with a routine to read the header information that you need from a disk file into a header class that stores the row, col, and max_value. We will also provide you with a method to read the image data, but you will provide the method to write out a newly created image to create a new output PGM file. PGM files may be viewed on UNIX systems at command level with the xv command: ie. xv myimage.pgm will display the image in file myimage.pgm. In order to see the labeled image as distictly different gray tone values, we will also give you a method to convert your labeled image to one that stretches out the gray tones to use the full range between 0 and 255, instead of just the first few integers, which tend to all look black in displays.

3. You will need to write the code for the image class, including the data items mentioned above, and the methods for

a. creating a new image given values for row, col, and max_value

b. negating a binary image

c. finding the beginning of a new component

d. searching for and labeling the rest of a given component (recursively)

e. any utility methods needed

f. the method to write an image to a new output PGM file

4. The connected components algorithm starts with a binary image and has three parts:

a. Negating the binary image so that all the 1's become -1's

b. Moving through the negated binary image to find the first -1 in a not yet labeled connected component

c. Recursively searching for and assigning a new label to all the pixels of the current component.

5. Test your program on each of the supplied input files, and optionally on input files of your own design.

Turn-in procedures

Files