home *** CD-ROM | disk | FTP | other *** search
/ The C Users' Group Library 1994 August / wc-cdrom-cusersgrouplibrary-1994-08.iso / vol_300 / 320_01 / convolve.txt < prev    next >
Text File  |  1990-08-06  |  6KB  |  149 lines
  1. Image Manipulation by Convolution
  2.  
  3. Several months ago, some work of mine required me to learn a little about
  4. image processing.  The project led to a dead end, but not before a
  5. particularly interesting image manipulation algorithm had come to my
  6. attention.  The algorithm is called convolution and is capable of finding
  7. edges, horizontal lines, vertical lines, and even diagonal lines in an image.
  8.  
  9. Convolution is a fancy word for a reasonably simple process.  The underlying
  10. philosophy of convolution is that when analyzing a picture, we interpret
  11. pixels in terms of how they fit with their neighbors, rather than as little
  12. specs of color.  What this translates into in the computer world is an image
  13. whose pixels represent some function of their original neighbors.  This is all
  14. fine and dandy, but still a little hard to code, even in C, until the
  15. following pseudocode becomes apparent:
  16.  
  17. For every pixel in the original image:
  18.  
  19. Place a pixel on the new image whose color is a function of the colors of the
  20. original pixel's neighbors.
  21.  
  22. Keep going until the original image has been completely "convolved" into the
  23. new image.
  24.  
  25. Well, this certainly sounds reasonable to code.  Now, what function of the
  26. original neighbors do we choose?  One of the simplest functions turns out to
  27. be one of the best: a weighted sum, including the original pixel.  Let's
  28. look at a simple 1D example:
  29.  
  30. Consider the row of pixels (1 2 3 4), with the pixel colored (2) being the
  31. pixel of interest.  Assume we have a "convolution matrix" of (-5 0 6).  The
  32. new pixel's color will be (1)(-5)+(2)(0)+(3)(6) or (13).  The convolved value
  33. for the original pixel colored (3) will be (2)(-5)+(3)(0)+(4)(6) or (14).  The
  34. two end pixels of (1) and (4) cannot be convolved since there are no left or
  35. right points to apply the convolution matrix to, and are assigned a value of
  36. (0).  The new row of pixels now looks like (0 13 14 0).
  37.  
  38. The 2D case is similar, involving 2D regions of pixels and a 2D convolution
  39. matrix.
  40.  
  41.  
  42. Choosing a Convolution matrix
  43.  
  44.  
  45. The convolution matrix you choose determines what the final picture will look
  46. like.  The program in Listing 1 accepts a file named matrix.dat that has the
  47. following format:
  48.  
  49. <matrix width> <matrix height>
  50. <row 1,col 1 factor> ... <row 1,col w factor>
  51. ...                  ...                  ...
  52. <row h,col 1 factor> ... <row h,col w factor>
  53.  
  54. Note that both the width and height must be odd, as the matrix needs to have a
  55. center point.
  56.  
  57. Some sample matrices will give you a feel for what convolution can do.  For
  58. example, the matrix file of:
  59.  
  60. 3 3
  61. -1 0 1
  62. -1 0 1
  63. -1 0 1
  64.  
  65. will generate pixels only on the edge of a dark-to-light transition going
  66. left-to-right on the screen.  Reversing the 1's and -1's will generate pixels
  67. on the edge of a light-to-dark transition (i.e. the "right" side of an
  68. object).  Likewise, the matrix file of:
  69.  
  70. 3 3
  71.  1  1  1
  72.  0  0  0
  73. -1 -1 -1
  74.  
  75. will generate pixels only on the edge of a dark-to-light transition going from
  76. top to bottom of the screen.  Switching the 1's and -1's here allows for the
  77. detection of topside lines.  To generate a picture that consists of only the
  78. edges of objects, use the matrix file of:
  79.  
  80. 3 3
  81. -1 -1 -1
  82. -1  8 -1
  83. -1 -1 -1
  84.  
  85. Diagonal lines can be detected by using matrices like:
  86.  
  87. 3 3
  88.  0  1 0
  89. -1  0 1
  90.  0 -1 0
  91.  
  92. In choosing your own matrix, follow these simple rules for best results:
  93. 1) Make sure the factors in the matrix add up to zero or more.  A zero sum
  94. will help to eliminate extraneous pixels, while a small net positive sum can
  95. help fill in missing pixels.  A negative sum usually filters out too many
  96. pixels (especially on a monochrome screen).
  97. 2) Use a zero in matrix locations where you don't care what is in that spot.
  98. 3) Use negative numbers for locations that you strongly desire not to have any
  99. color.
  100. 4) Use positive numbers for locations that you strongly desire to have a non-
  101. zero value.
  102.  
  103.  
  104. The program
  105.  
  106.  
  107. The program in Listing 1 accepts images in the CUT file format used by the
  108. Dr.Halo products.  I use a hand scanner for acquiring images and this was the
  109. format that was easiest to use, however, you can substitute any other means of
  110. getting a picture onto the screen.  If you should replace the present routine
  111. for loading images (load_cut(...)), be sure to set the global variables minx,
  112. miny, maxx, maxy to the image's location on the screen but do not change the
  113. display page.  To keep the convolution code reasonably clean, the program
  114. also requires that you leave at least <matrix height+1>/2 and <matrix width+1
  115. >/2 gap on the top and left side of the image respectively.
  116.  
  117. The program was written in Turbo C 2.0 and the graphics calls should be fairly
  118. portable to other C's.  Pointers are used frequently to minimize the time that
  119. several hundred thousand array accesses would normally take.  Though somewhat
  120. optimized, the program could still use a good kick, perhaps by forcing it to
  121. ignore matrix entries of zero.
  122.  
  123. When run, the program asks for the name of a CUT file to load and some
  124. information about image cleanup.  Enter the path to the file, if the file is
  125. not in the same directory, and the name of the file (including the .CUT on the
  126. end).  The image cleanup option will let the computer delete stray pixels
  127. before convolution.  A single pixel with zero neighbors usually does not
  128. belong to a surface of interest and can be deleted before convolution by
  129. answering 0 at the cleanup prompt.  The cleanup process is disabled by a
  130. response of -1.
  131.  
  132. Once the image has been convolved, press the space bar to flip between the
  133. original image (or cleaned image) and the convolved image.  The effects of
  134. convolution become very apparent by just holding down the space bar!  Should
  135. you be fortunate enough to be using the program on a color system, you can
  136. toggle colors by pressing the letters A-P (A=black, B=blue, etc...).  Finally,
  137. the ESC key will get you out (as will pressing any key during convolution).
  138.  
  139.  
  140. Conclusion
  141.  
  142.  
  143. The program works fine now, though you may wish to consider working on a
  144. method of saving convolved images, further optimization (assembly?) of the
  145. convolution routine, and the use of other image file formats.
  146.  
  147. Convolution is an amazingly straight forward algorithm for image manipulation
  148. and can serve as the starting point for AI programs, contour analysis, image
  149. recognition, etc.  I hope you find it as interesting as I did.