Programming Assignment 4 - Computer-Aided Tomography

Introduction to Computer Science II, Summer 2001

Due Date
Background
The Problem
Testing

Due Date

This assignment is due on Tuesday, 17 July, no later than 2:00 p.m.

See the assignment turn-in page for instructions on turning in your assignment.

Background

Computer-aided tomography is a non-destructive technique for taking pictures of the insides of objects, including people (computer-aided tomography is the CAT in CAT scan).

Computer-aided tomography works by shooting beams of energy through the object to be imaged. An object's insides absorb varying amounts of the beam's energy, and the beam exits the object having less energy then it had when it entered the object. By repeatedly and regularly varying the location of the beam as it passes through the object, it is possible to build up an energy-absorption profile of the object's insides.

Once enough energy absorption data has been collected, it, along with the beam location information, is given to a computer program that generates an image of the object's insides consistent with the energy-absorption and location data.

The Problem

Write a procedure that accepts beam energy-absorption and location data and outputs an image of the object consistent with the input data. The data are generated from a simple CAT scan: the object being scanned is rectangular, and the beams are parallel to the sides of the object and scan it at regular intervals:

The x-axis (horizontal) beams enter the object from the left and scan from top to bottom; the y-axis (vertical) beams enter the object from the top and scan from left to right. The beams enter the object with a positive energy x and leave the object with either the same energy x or zero energy.

An object's insides consists of two kinds of material, one absorbs no energy and the other absorbs all energy.

The procedure's prototype is

void generate_image(
  const int x_energy[],  // The output energy of the x-axis beams.
  int x_size;            // The number of values in x_energy.
  const int y_energy[],  // The output energy of the y-axis beams.
  int y_size		 // The number of values in y_energy.
  int image[25][25]      // The generated image.
  );

x_energy[i] contains the output energy for x-axis beam i, 0 <= i < x_size; y_energy[i] contains the output energy for y-axis beam i, 0 <= i < y_size. The output-energy value is either 0 or some positive integer.

The generated image is an x_size-by-y_size matrix stored in image with the image's upper-left element at image[0][0]. The value at image[x][y] for 0 <= x < x_size and 0 <= y < y_size is either 0 if the data indicates the object has non-abosrbing material at that location or 1 if the data indicates the object has absorbing material at that location. The values in the elements of image outside the object are ignored and can have any values.

As an example, the picture above would create the following input data for generate_image():

x_energy[] = { 1, 0, 1 }
x_size = 3
y_energy[] = { 1, 0, 0, 1 }
y_size = 4

From this input data generate_image() will store the following data in image:

image[][] = {
  { 0, 0, 0, 0, /* whatever */ },
  { 0, 1, 1, 0, /* whatever */ },
  { 0, 0, 0, 0, /* whatever */ },
  /* whatever */
  }

This set of data are consistent with the input data and the object image

Testing

You can compile your generate_image() source with the test file test-gi.o to test your code. You can download test-gi.o from a browser (shift-left-click on the link) or access it directly at


/export/home/us/csfac/cs176-summer2001/pa/4/test-gi.o

from any PC lab machine running linux or from rockhopper.