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