Dwayne Phillips works as a computer and electronics engineer with the United States Department of Defense. He has a Ph.D. in electrical and computer engineering at Louisiana State University. His interests include computer vision, artificial intelligence, software engineering, and programming languages.
This is the fifth in a series of articles on images and image processing. The first four articles discussed reading images (TIFF format), displaying them, printing them, and histograms and histogram equalization. This article will cover two topics. The first topic is how to write images to TIFF files on disk. Writing images to disk is a necessity because from now on CIPS (the C Image Processing System) will be able to alter images. You must save the altered images to disk for further processing and display. The second topic is how to detect edges in an image. Edge detection is one of the fundamental operations in image processing. Many other operations are based on edge detection and there has been much written about this subject. This article will discuss the subject and explore some basic techniques. The next article in the series will discuss some advanced forms of edge detection.
One basic ability lacking in CIPS (the C Image Processing System) is writing images to disk. We need this capability because we will now alter images and we must store them for further processing and display. In the past, we processed images with histogram equalization, but did not store them - we only displayed them. The processing we will do from now on requires that we store the results.
The first article in this series discussed the Tag Image File Format (TIFF) and gave the source code needed to read 100 x 100 pixel areas from a file. That article gave the details of the file header and the types of tags or pointers it uses. TIFF files contain a header giving the information necessary to read the image from the file. To write a TIFF file, you must first write such a header to a disk file, and then write the image data to the file in the proper order.
The strategy we'll use in CIPS is if an image processing function (such as the edge detectors discussed later) needs to write results to a disk file, it will check to see if that file exists on disk. If the file exists, the image processing function will call a function that will write a 100 x 100 array of pixels into the disk file. If the file does not exist, the image processing function will first call a function that will create a TIFF disk file large enough to hold an entire image. Then it will call a function that will write a 100 x 100 array of pixels into the disk file.
Listing 1 shows the source code CIPS needs to write TIFF files to disk. The first function in Listing 1 is create_allocate_tiff_file. This function takes in a file name and information about the TIFF file header and creates a file on disk. It allocates disk space by writing enough zeros to the file to hold an image. The image width and length specified in the tiff_header_struct indicate how large an image the disk file must be able to hold. In writing the file header, create_allocate_tiff_file always specifies least-significant-byte-first order. It only writes the image width, length, and bits per pixel to the file header since this information is enough for our purposes. After writing the file header, it goes into a loop and writes out bytes of zeros to the file. It uses the function round_off_image_size (shown near the end of Listing 1) to calculate how large an area to allocate on disk.
The second function in Listing 1 is write_array_into_tiff_image. Image processing functions will use this to write 100 x 100 arrays of pixels into existing TIFF files. It takes in the file name, looks at the file header, and uses the header information to write an array of pixels into the file. Its form is similar to that of the function read_tiff_image given in part 1 of this series of articles. The function write_array_into_tiff_image seeks to the first line and element to which it shall write, writes one line of pixels, seeks to the next line, writes a line, and so on.
The function write_line (shown next in Listing 1) actually writes the bytes into the file. It converts the short values (16 bits) to either eight or four bit values and writes them. The functions insert_short_into_buffer and insert_long_into_buffer are utilities used by the other functions to place values into the proper bytes for the file. The function does_not_exist is a utility that looks for a file on disk. If the file exists, does_not_exist returns a zero. Image processing functions will use does_not_exist to check the disk for a file before writing to it or creating it.
Now that we can create and write to a TIFF file, let's write our first application program. An application program is one that uses the functions of CIPS, but runs independent of CIPS. Our first application program is roundoff. roundoff will not do any processing on an image, but will simply round off an image into multiples of 100. It will take an image that is 613 x 561 pixels and create an image file that is 300 x 300 or 600 x 500 pixels.
Listing 2 shows the source code for roundoff. roundoff does not contain any new functions. The comments at the top of the listing show which functions roundoff calls and the files that contain these functions. The roundoff program asks the user for the names of the input and output files and the desired size of the output file. roundoff could obtain this information from command line parameters instead of question and answer style. After obtaining all the needed information, roundoff creates the output file on disk by calling create_allocate_tiff_file. Then roundoff goes into a loop to read data from the input file and write data to the output file.
The roundoff program demonstrates several system concepts. Application programs will read image data, process the data, and write data to an output file. We now have the necessary read and write functions and an example of how to use them (the remainder of this article will give us our first processing functions). Recall an unwritten rule that CIPS functions should not interact with the user. The main() or controlling function should perform all question and answer tasks. This allows us to string together functions into a program as shown in Listing 2. All we need to do is link the application program to the files containing the read, write, and processing functions, and execute. This point will become more evident with the edge detection application program described later.
Why go to all the trouble to make it easy to write application programs? The main CIPS program is interactive. The user looks at menus, makes selections, and answers questions. This is good for experimenting with processing functions. It allows the user to try an operation on one small area of an image, look at the results, alter the parameters, and try again. Once the user knows which operation to use and the correct parameters, he does not want to go through the question and answer exercise for every 100 x 100 pixel area in the image. The application program allows the user to call the proper processing function in a loop and process an entire image with one command. The user should be able to write application programs quickly and easily.
Now let's move into edge detection. The remainder of this article will introduce the subject and show some basic edge detectors. The next article will continue with some advanced edge detectors. Detecting edges is a basic operation in image processing. The edges of items in an image hold much of the information in the image. The edges tell you where items are, their size, shape, and something about their texture.
The top part of Figure 1 shows the side view of an ideal edge. An edge is where the gray level of the image moves from an area of low values to high values or vice versa. The edge itself is at the center of this transition. You want an edge detector to return an image with gray levels like those shown in the lower part of Figure 1. The detected edge gives a bright spot at the edge and dark areas everywhere else. Calculus fans will note the detected edge is the derivative of the edge. This means it is the slope or rate of change of the gray levels in the edge. The slope of the edge is always positive or zero and it reaches its maximum at the edge. For this reason, edge detection is often called image differentiation.
How do you calculate the derivative (the slope) of an image in all directions? Convolution of the image with masks is the most often used technique of doing this. The article by Wesley Falar in The C Users Journal discussed this technique. The idea is to take a 3 x 3 array of numbers and multiply it point by point with a 3 x 3 section of the image. You sum the products and place the result in the center point of the image.
The question in this operation is how to choose the 3 x 3 mask. Mr. Faler used several masks shown in Figure 2. These are basic masks that amplify the slope of the edge. Take the simple one- dimensional case shown in Figure 1. Look at the points on the ideal edge near the edge. They could have values such as [3 5 7]. The slope through these three points is (7-3)/2 = 2. If you convolve these three points with [-1 0 1] you have -3 + 7 = 4. The convolution amplified the slope and the result is a large number at the transition point in the edge. When you convolve [-1 0 1] with a line, you are performing a form of differentiation or edge detection.
The number of masks used for edge detection is almost limitless. Researchers have used different techniques to derive masks and then experimented with them to discover more masks. Figure 3 shows four types of masks we'll use. The first three masks are the Kirsch, Prewitt, and Sobel masks as given in Levine's text (there are different masks bearing the same name in the literature). The fourth mask, the "quick" mask, is one I "created" while working on this article (there is no doubt that some one else created this mask before me).
The Kirsch, Prewitt, and Sobel masks are compass gradient or directional edge detectors. This means that each of the eight masks detects an edge in one direction. Given a pixel, there are eight directions you can travel to a neighboring pixel (above, below, left, right, upper left, upper right, lower left, and lower right). Therefore, there are eight possible directions for an edge. The directional edge detectors can detect an edge in only one of the eight directions. If you want to detect only left to right edges, you would use only one of the eight masks. If, however, you wanted to detect all of the edges, you would need to perform convolution over an image eight times using each of the eight masks. The quick mask is named so because it can detect edges in all eight directions in one convolution. This has obvious speed advantages when you want to detect all the edges. There are, however, occasions when you only want to detect one type of edge and you should use a directional mask for those occasions.
There are two basic principles for each edge detector mask. The first is that the numbers in the mask sum to zero. If a 3 x 3 area of an image contains a constant value (such as all ones), then there are no edges in that area. The result of convolving that area with a mask should be zero. If the numbers in the mask sum to zero, then convolving the mask with a constant area will result in the correct answer of zero. The second basic principle is the mask should approximate differentiation or amplify the slope of the edge. The simple [-1 0 1] example given earlier showed how to amplify the slope of the edge. The first Kirsch, Prewitt, and Sobel masks use this idea to amplify an edge ramping up from the bottom of an image area to the top.
Listing 3 shows source code that will implement the four edge detectors shown in Figure 3. The first section of code declares the masks shown earlier in Figure 2. The functions detect_edges and perform_convolution implement the Kirsch, Prewitt, and Sobel edge detectors. The detect_edges function first checks to see if the output image exists on disk. If it does not, it calls create_allocate_tiff_file to create it. Next, detect_edges reads an array from the input image and calls perform_convolution to detect the edges. Finally, it "fixes" (more on this later) the edges of the output image and writes it to the output image file.
The function perform_convolution does the convolution operation eight times (once for each direction) to detect all the edges. First, it calls setup_masks to copy the correct masks. The parameter detect_type determines which masks to use. The convention is type 1=Prewitt, 2=Kirsch, and 3=Sobel. The function perform_convolution clears the output image, sets several maximum values, and does the convolution eight times over the entire image array. At each point, the code checks to see if the result of convolution is greater than the maximum allowable value or less than zero, and corrects for these cases.
After convolution, there is the option of thresholding the output of edge detection. Edge detectors produce results that vary from zero to the maximum gray level value. This variation shows the strength of an edge. An edge that changes from 10 to 200 will be stronger that one that changes from 10 to 50. The output of convolution will indicate this strength. It is often desirable to threshold the output so strong edges will appear relatively bright (or dark) and weak edges will not appear at all. This lowers the amount of noise in the edge detector output and yields a better picture of the edges. The detect_edges and perform_convolution functions pass a threshold parameter. If threshold == 1, perform_convolution goes through the output image and sets any pixel above the high parameter to the maximum and any pixel below the high parameter to zero.
The quick_edge function performs edge detection using the single 3 x 3 quick_mask. It first checks to see if the output image exists on disk. If the image does not exist on disk, quick_edge c a l l s create_allocate_tiff_file to create it. Next, quick_edge reads in the input file array and performs convolution over the image array using the quick_mask. It thresholds the output image if requested, fixes the edges of the output image, and writes the result to the output file on disk. All of these operations are the same as in the detect_edges and perform_convolution functions.
Several short utility functions make up the remainder of Listing 3. The setup_masks function copies the desired type of mask (Kirsch, Prewitt, or Sobel) into the mask arrays for the perform_convolution function. The get_edge_options function queries the user for the type of detection, whether or not to threshold the output, and the threshold value.
The fix_edges function corrects the output image after convolution. When you convolve a 3 x 3 mask over a 100 x 100 image array, you do not process the pixels along on the outer edge of the image. The result is a blank line around the 100 x 100 array. This shows up as a distracting grid when you display an entire image. The fix_edges function goes around the edge of the 100 x 100 array and copies valid values out to the edge. This removes the distracting lines.
Now its time to integrate the edge detectors into CIPS. Listing 4 shows the two segments of code we need to add to the main CIPS program. The first segment adds another case to the main switch portion to call the edge detectors. It asks the user for the image names and parameters and the edge detector options. Then, based on the type of edge detection, it calls either the Kirsch, Prewitt, or Sobel detector, or the quick detector. The second code segment shows the addition to the main menu. This allows the user to choose edge detection.
Using the edge detectors is easy. You choose option 8 from the main menu and then answer the edge detection questions. This works fine for experimenting with one 100 x 100 area of an image. If, however, you want to perform edge detection on a 600 x 600 image, you do not want to answer all the questions 36 times. You want an edge detection application program.
Listing 5 shows a simple edge detection application program called mainedge. As in the roundoff program of Listing 2, the mainedge program does not contain any new functions. The comments at the beginning of the listing show which CIPS functions it uses and the files that contain the functions. The mainedge program reads all the needed parameters from the command line (as opposed to the question and answer method). It calculates the required number of iterations and loops. In each loop, it calls the desired edge detector with the correct line and element. The edge detector functions take care of reading from disk, detecting edges, and writing to disk. This is a simple yet powerful program and should serve as a good model for future image processing programs of your own.
Let's close with examples of the edge detectors in action. Photograph 1 shows a house image. Photograph 2 shows the result of applying the Kirsch edge detector masks. Photograph 3 shows the result of the Prewitt masks and photograph 4 shows the result of the Sobel masks. Photograph 2, Photograph 3, and Photograph 4 are outputs that were thresholded. Edge values above a threshold of 33 were set to 255 and all others were set to 0. This gives a clear picture of edges and non-edges. Photograph 5 shows the result of applying the Sobel masks and not thresholding the result. If you look closely, you can see some variations in gray level indicating some edges are stronger than others. Photograph 6 shows the result of applying the quick mask. The results of the quick mask are as good as the other masks and it operates in one eighth the time.
Conclusion
This article discussed writing images out to TIFF disk files and basic edge detection. It also gave two model application programs. The next article in this series will continue the discussion of edge detection. There are many creative methods of detecting edges in images. The next article will discuss the homogeneity operator, the difference operator, contrast based edge detection, and varying the size of the convolution mask to filter out edges of small objects.
References
1. "Image Processing Part 1: Reading the Tag Image File Format," Dwayne Phillips, The C Users Journal, Vol. 9, No. 3, March 1991, pp. 92-100.2. Digital Image Processing, Kenneth R. Castleman, Prentice-Hall, 1979.
3. "Image Manipulation By Convolution," Wesley Faler, The C Users Journal, Vol. 8, No. 8, August 1990, pp. 95-99.
4. Vision in Man and Machine, Martin D. Levine, McGraw-Hill, 1985.