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.
Introduction
This is the sixth in a series of articles on images and image processing. The first five articles in the series discussed reading and writing images (TIFF format), displaying them, printing them, histograms and histogram equalization, and basic edge detection. This article will cover some advanced techniques in edge detection.There are many different methods of edge detection. Image Processing Part 5: Writing Images to Files and Basic Edge Detection (CUJ, October 1991) discussed some basic techniques. This article discusses some unusual and advanced ideas and looks at four edge detectors. The first two do not use the convolution operation — they use only subtraction. The third edge detector can vary the level of detail of the edges it will detect. The fourth edge detector will detect edges in unevenly lit images. Then an edge detector is used to enhance the appearance of an original image. Finally, these new operators are integrated into the C Image Processing System (CIPS). Photograph 1 shows the original image used by all the operators.
The first edge detector is the homogeneity operator[1] which uses subtraction to find an edge. Figure 1 shows an example of this operator. The operator subtracts each of the pixels next to the center of a 3x3 area from the center pixel. The result is the maximum of the absolute value of these subtractions. Subtraction in a homogeneous region (one that is a solid gray level) produces zero and indicates an absence of edges. A region containing sharp edges, such as area 2 of Figure 1, has a large maximum.
The first section of Listing 1 shows the homogeneity function. This function is similar in form to the edge detectors discussed in the previous article of this series. First, the function checks to see if the output image exists. If the output image does not exist, the homogeneity function creates it by calling create_allocate_tiff_file. The homogeneity function reads in the image array and goes into the processing loop.
In the loop over ROWS and COLS, the code performs the subtraction and finds the maximum absolute value of the subtractions. The homogeneity operator requires thresholding (which you can specify). A perfectly homogeneous 3x3 area is rare in an image. If you do not threshold, the result looks like a faded copy of the original. Thresholding at 30 to 50 for a 256 gray level image gives good results.
Photograph 2 shows the result of the homogeneity operator. This operator gives a good rendition of the edges in the original house image. This is a quick operator that performs only subtraction — eight operations per pixel — and no multiplication.
The next edge detector is the difference operator, another simple operator that uses subtraction. Recall that edge detection is often called image differentiation (detecting the slope of the gray levels in the image). The difference operator performs differentiation by calculating the differences between the pixels that surround the center of a 3x3 area.
Figure 2 shows an example of the difference operator. The difference operator finds the absolute value of the differences between opposite pixels, the upper left minus lower right, upper right minus lower left, left minus right, and top minus bottom. The result is the maximum absolute value. The results shown in Figure 2 are similar but not exactly equal to those from the homogeneity operator in Figure 1.
The second part of Listing 1 shows the difference_edge function, which is similar to the homogeneity function. The routine creates an output image file if necessary and reads in the input image array. The difference_edge function loops over the input image array and calculates the absolute values of the four differences. You can specify that difference_edge threshold the output. As in the homogeneity case, the difference operator requires thresholding.
Photograph 3 shows the result of the difference edge detector. This result is similar to the shown in Photograph 2. The difference edge detector did detect more of the brick and mortar lines than the homogeneity operator. You can choose between the two edge detectors depending on how much detail you want. The difference operator is faster than the homogeneity operator. The difference operator uses only four integer subtractions per pixel, while the homogeneity operator uses eight subtractions per pixel. These compare to the nine multiplications and additions for the convolution-based edge detectors discussed in the fifth article.
The next operator to examine is the difference of Gaussians edge detector, which allows you to vary the width of a convolution mask and adjust the detail in the output[2,3]. The results in Photograph 2 and Photograph 3 are good. Suppose, however, we wanted to detect only the edges of the large objects in the house image (door, windows, etc.) and not detect the small objects (bricks, leaves, etc.).
You can use convolution masks and vary the width of the mask to eliminate details. If a mask is wide, then convolving an image will smooth out details, much like averaging. If you look at stock market prices by the minute, you see many variations. If you look at the average stock market price over each hour, the variations begin to disappear. If you look at the average stock market price over each week, then the variations disappear and you see general trends in prices. If you convolve an image with a wide, constant mask, you smooth the image. If you use a narrower, varying mask, the details remain.
Figure 3 shows two example masks. These masks are difference of Gaussians or Mexican hat functions. The center of the masks is a positive peak (16 in the 7x7 masks — 19 in the 9x9 mask). The masks slope downward to a small negative peak (-3 in both masks) and back up to zero. The curve in the 9x9 mask is wider than that in the 3x3 mask. Notice how the 9x9 mask hits its negative peak 3 pixels away from the center while the 7x7 masks hits its peak 2 pixels away from the center. Also, notice these masks use integer values. Most edge detectors of this type use floating point numbers that peak at +1. Using integers greatly increases the speed; my 80286 machine does not have a math co-processor and numerous floating point calculations are out of the question.
Figure 4 illustrates how the narrower mask will detect small edges the wide mask misses. Each area in Figure 4 has a small pattern similar to the brick and mortar pattern in the house image. This pattern has small objects (bricks) with many edges. If you convolve the 7x7 mask in Figure 3 with the 7x7 area in Figure 4, the result is +40; the 7x7 mask detected an edge at the center of the 7x7 area. If you convolve the 9x9 mask in Figure 3 with the 9x9 area in Figure 4, the result is -20; the 9x9 mask did not detect any edges. The "hat" in the 9x9 mask was wide enough to smooth out the edges and not detect them.
The first section of Listing 2 shows the two masks and the function gaussian_edge. gaussian_edge has the same form as the other edge detectors. The routine creates an output image file if necessary and reads the input image array. An additional size parameter (either 7 or 9) specifies mask width. The inner loop over a and b varies with this parameter. The processing portion is the same as the other convolution mask edge detectors presented in "Image Processing, Part 5." With gaussian_edge, you can use thresholding to produce a clear edge image or you can leave it off to show the strength of the edges.
Photograph 4 shows the result of edge detection using the narrower 7x7 mask and Photograph 5 shows the result of the wider 9x9 mask. The narrower mask (Photograph 4) detected all the edges of the bricks, roof shingles, and leaves. The wider mask (Photograph 5) did not detect the edges of small objects, only edges of the larger objects. Photograph 4 may be too cluttered for your application, so you would use the wider mask. If you want fine detail, then the narrower mask is the one to choose.
You can modify other edge detectors to detect edges on different size objects. The homogeneity operator can take the difference of the center pixel and a pixel that is two or three pixels away. The difference edge detector can take the difference of opposite pixels in a 5x5 or 7x7 area instead of a 3x3 area. The quick mask (see Part 5) can change from 3x3 to 5x5 with the center value equal to 4 and the four corners equal to -1. Try these changes as a homework project. You need the code in gaussian_edge that changes the size of the convolution and the call to the fix_edges function.
One problem with detecting edges involves uneven lighting in images. The contrast-based edge detector[4] helps take care of this problem. In well lit areas of an image the edges have large differences in gray levels. If the same edge occurs in a poorly lit area of the image, the difference in gray levels is much smaller. Most edge detectors result in a strong edge in the well-lit area and a weak edge in the poorly-lit area.
The contrast-based edge detector takes the result of any edge detector and divides it by the average value of the area. This division removes the effect of uneven lighting in the image. You find the average value of an area by convolving the area with a mask containing all 1s and dividing by the size of the area.
Figure 5 illustrates the contrast-based edge detector. You can use almost any edge detector as the basis for this operation. Figure 5 uses the quick edge detector from the last article (Part 5). The edge in the well-lit area is an obvious and strong edge. Convolving the quick mask with this area yields 100. The edge in the poorly-lit area is easy to see, but convolving with the quick mask results in 10, a weak edge that thresholding would probably eliminate. This distinction should be avoided. The well-lit and poorly-lit edges are very similar; both change from one gray level to another gray level that is twice as bright.
Dividing by the average gray level in the area corrects this discrepancy. Figure 5 shows the smoothing mask that calculates the average gray level. Convolving the well-lit area yields an average value of 83. Convolving the poorly-lit area yields an average value of 8. Dividing (integer division) the strong edge in the well-lit area by 83 yields 1. Dividing the weak edge by 8 also result of 1. The two edges from unevenly-lit areas yield the same answer and you have consistent edge detection.
The last section of Listing 1 shows the contrast_edge function that follows the same steps as the other edge detector functions. The difference is in the processing loop over a and b, which calculates two convolutions: sum_n (the numerator or quick edge output) and sum_d (the smoothing output). After the loops over a and b, divide sum_d by 9 and divide sum_n by this result. The e_mask at the beginning of Listing 1 replaces the quick mask (from Part 5), with every element in the quick mask multiplied by 9. You need the larger values — dividing by the average gray level could reduce the strength of all edges to zero.
Photograph 6 shows the result of the regular quick edge detector. Photograph 7 shows the result of dividing the quick edge result by the average value to produce contrast-based edge detection. Notice the inside of the upstairs and downstairs windows. Photograph 6 (quick edge) shows edges inside the downstairs windows, but not inside the upstairs windows. Photograph 7 (contrast-based) shows details inside the downstairs and upstairs windows. Refer to the original image (Photograph 1) . The downstairs windows are shaded and the upstairs windows are not. Contrast-based edge detection gives better results in uneven lighting.
You can use contrast-based edge detection with any edge detector. As a project, try modifying the homogeneity edge detector by dividing its result by the average gray level. But first multiply the result of homogeneity by a factor (9 or more) so dividing does not reduce edge strengths to zero. Modify any of the other edge detectors in a similar manner.
A good application of edge detectors is to enhance edges and improve the appearance of an original image. Detect the edges in an image and then overlay these edges on top of the original image to accent its edges. The last section of Listing 2 shows the enhance_edges function, which repeats the quick_edge function from the last article with a few added lines of code. Examine the code right after the loops over a and b. If the result of convolution (the sum variable) is greater than a user-chosen threshold, then the output image is assigned that value. If not, then the output image is assigned the value from the input image. The result is the input image with its strong edges accented.
Photograph 8 shows the result of enhancing the edges of Photograph 1. The edges of the bricks, the siding in the left, and the lines on the garage door are all sharper.
You can use any edge detector to enhance the edges in an input image. You just add the option of taking the edge detector result or a value from the input image. An interesting project would be to use the 9x9 Gaussian mask to detect the edges of large objects and use these edges to enhance the input image.
Some new code incorporates these edge detectors into the C Image Processing System (CIPS). Listing 3 shows the changes to the main program file cips.c. I modified case 8 to include the new types of edge detection (detect_type == 5, 6, 7, or 8). I also added case 9 for edge enhancement. The last part of Listing 3 shows the new version of show_menu that allows the user to select case 8 or 9.
Listing 4 shows the new version of get_edge_options (file edge.c from Part 5). The new version allows you to select from among eight available edge detectors. You can select thresholding, specify a threshold value, and specify 7x7 or 9x9 Gaussian edge detection.
Listing 4 shows the new version of the mainedge application program discussed in Part 5. You can run an edge detector over all of the 100x100 sections of an image without interacting with CIPS; instead mainedge uses command-line parameters. There are seven command-line parameters — I can never remember the correct order. Just type mainedge <return> and the program will remind you of the order. mainedge loops over the 100x100 blocks and calls the specified edge detector function. The edge detector does the rest.
Try these edge detectors and do a few of the projects. There a countless combinations to try and you can no doubt invent an edge detector tailored for your application.
References
1. "Recognizing Objects in a Natural Environment: A Contextual Vision System (CVS)," Martin A. Fischler, Thomas M. Strat, Proceedings Image Understanding Workshop, pp. 774-796, Morgan Kaufman Publishers, May 1989.2. Digital Image Processing, Kenneth R. Castleman, Prentice-Hall, 1979.
3. Vision in Man and Machine, Martin D. Levine, McGraw-Hill, 1985.
4. Contrast Based Edge Detection, R.P. Johnson, Pattern Recognition, Vol. 23, No. 3/4, pp. 311-318, 1990.