Wesley Faler is a senior Manufacturing Systems Engineering student at GMI Engineering & Management Institute in Flint, MI. He has worked with C for 2 years now, and interests include user interface coding, AI, and scientific computing. He is presently on the programming team that is writing the GMI CIM Lab system code. All comments should be sent to 1409 New York Ave., Flint, MI 48506.
Several months ago, a project led me to a particularly interesting image manipulation algorithm called convolution, which is capable of finding edges, horizontal lines, vertical lines, and even diagonal lines in an image.
Convolution is a reasonably simple process whereby we interpret an image's pixels in terms of how they fit with their neighbors. In other words, the image's pixels after convolution represent some function of their original neighbors. The following pseudocode makes the process a little clearer:
This algorithm doesn't choose the function involving the original neighbors. I chose a simple and effective function: a weighted sum, including the original pixel.
- For every pixel in the original image, redraw the pixel with a color that is a function of the colors of the original pixel's neighbors.
- Continue the first step until the original image has been completely "convolved" into the new image.
In a simple, one-dimentional example, a row of pixels is represented by (1 2 3 4), with each integer defining a pixel's color. The pixel colored (2) is the first that can be redrawn since it is the first (left to right) with left and right neighbors. Assume we apply a "convolution matrix" of (-5 0 6) to the pixel and its neighbors. The pixel's new color will be
(1)(-5)+(2)(0)+(3)(6)or (13). The convolved value for the original pixel colored (3) will be
(2)(-5)+(3)(0)+(4)(6)or (14). The two end pixels (1) and (4) cannot be convolved since there are no left or right points to which to apply the convolution matrix. They are assigned a value of (0). The new row of pixels is now (0 13 14 0).The two-dimentional case is similar, involving 2-D regions of pixels and a 2-D convolution matrix.
Choosing A Convolution Matrix
How you choose the convolution matrix determines the final picture's appearance. The program in Listing 1 accepts a file named matrix.dat that has the following format:
<matrix width> <matrix height> <row 1,col 1 factor> ... <row 1,col w factor> ... ... ... <row h,col 1 factor> ... <row h,col w factor>Note that both the width and height must be odd, since the matrix must have a center point.Some sample matrices will give you a feel for what convolution can do. For example, the matrix file
3 3 -1 0 1 -1 0 1 -1 0 1will light pixels that were on only the left edge of a dark-to-light transition on the screen (see Figure 1) . Reversing the 1s and -1s will detect a light-to-dark transition (i.e. lighting the "right" side of the object). Likewise, the matrix file:
3 3 1 1 1 0 0 0 -1 -1 -1will detect a dark-to-light transition from top to bottom (Figure 2) . Switching the 1s and -1s here allows you to detect top-side lines. To generate a picture of only an object's edges (like the image on this issue's cover), use the matrix file:
3 3 -1 -1 -1 -1 8 -1 -1 -1 -1Diagonal lines can be detected by using a matrix such as
3 3 0 1 0 -1 0 1 0 -1 0In choosing your own matrix, observe the following simple rules for best results:
- Make sure the sum of the factors in the matrix is positive or zero. A zero sum will eliminate extraneous pixels, while a small net positive sum can seem to fill in missing pixels. A negative sum usually filters out too many pixels (especially on a monochrome screen).
- Use a zero in matrix locations where you are ambivalent about the color.
- Use negative numbers for locations where you wish not to have color.
- Use positive numbers for locations where you want a non-zero value.
The Program
Listing 1 contains a program that accepts images in the CUT file format used by the Dr. Halo products. This format was easy to use with a hand scanner, but you may substitute any other means of getting a picture onto the screen. If you should replace the present routine for loading images (load_cut (...) ), be sure to set the global variables minx, miny, maxx, maxy to the image's location on the screen, but do not change the display page. To keep the convolution code reasonably clean, the program also requires that you leave at least <matrix height+1>/2 and <matrix width+1 >/2 margin on the top and left side of the image, respectively.CONVOLVE.C was written in Turbo C 2.0 and the graphics calls should be fairly portable to other Cs. I frequently used pointers to minimize the execution time that several hundred thousand array accesses would normally take. The program could be further optimized by forcing it to ignore matrix entries of zero.
When you run the program, it asks for the name of a CUT file to load and some information about image cleanup. If the file is not in the same directory, enter the path and the filename (including the .CUT extension).
The image cleanup option will delete stray pixels before convolution. A single pixel with zero neighbors usually does not belong to a surface of interest. You can delete such pixels before convolution by answering 0 at the cleanup prompt. To disable the cleanup process, respond with -1.
Once the image has been convolved, press the space bar to switch between the original image (or cleaned image) and the convolved image. The effects of convolution become very apparent by simply holding down the space bar! Should you be fortunate enough to use the program on a color system, you can toggle colors by pressing the letters A-P (A=black, B=blue, etc...). Finally, hitting the ESC key will get you out (as will pressing any key during convolution).
Conclusion
The program works fine now, though you may wish to add the capability for single page display modes, developing a method to save convolved images, further optimization (assembly?), and the use of other image file formats.Convolution is an amazingly straightforward algorithm for image manipulation and can serve as the starting point for AI programs, contour analysis, or image recognition.