Autumn 2000

CSE 373: Programing Project #1
due Monday, October 16
Connected Components Algorithm for Labeling Binary Images

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 with 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 operations for an image ADT and, in particular, the operations that implement a connected components algorithm, both recursively and non-recursively (using a stack).

Details

1. The header data structure has 3 fields: row, col, and max_value, and the image data structure has 2 fields: p_array and header.

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);

p_array is a 2D integer array that has row rows and col columns.

2. We will give you files that contain test images (see at the end). These files are in a 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 struct that stores the row, col, and max_value. We will also provide you with a function to read the image data. Your job will be to write out a newly created image into an output PGM file. (Note: PGM files can be viewed on Windows systems with the PGM viewer we provide - see the download link off the class web page.) In order to see the labeled image as distinctly different gray tone values, we will also give you a function 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 to store the data items mentioned above, as well as define functions for each the following:

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

e. writing an image to a new output PGM file

f. any other utility functions needed

4. The connected components algorithm starts out 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. Searching for and assigning a new label to all the pixels of the current component.

We ask you to write the search procedure in two different ways:

I. Use recursion to perform the search: This means that after you label a pixel, you call your search recursively for each of its unlabeled neighbors.

II. Do not use recursion to perform the search. Instead, write your code using a linked stack. The control structure will be a loop that pops a pixel from the stack, labels it, and pushes its unlabeled neighbors onto the stack. Linked stack operations are given in your book - read it before starting on this part.

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

6. You will be required to turn-in a paper copy of your code, as well as submit your source code electronically (see below). Your code should include the following block at the top of each source file:

TITLE:

AUTHOR:

DATE:

PURPOSE:

ARGUMENTS:

COMPILER/SYSTEM:

and for each function or class:

TITLE:

PURPOSE:

ARGUMENTS:

Use your common sense as to what else needs to be commented in your code.

Electronic turn-in procedures

Before you submit your code, make sure it compiles on Windows. Also, make sure you have followed all the guidelines about well documented code. If you think you have already done this, then you may proceed to the electronic turn-in.
Make sure to submit your source code as well as other relevant (image) files electronically!

Due dates

Input source and image files

Source files if you program in C:
header.h
func.h
func.c

Source files if you program in C++:
Title.cpp
Title.h
Image.cpp
Image.h

We advise AGAINST the use of other programming languages. Although Java is acceptable, there are no prepared routines we could give you, so you would have to write your own.

Sample image files:
img1.pgm
img2.pgm
img3.pgm