The present invention relates to systems for correlating patterns with images.
In image correlation, a desired pattern (e.g., a desired object to be picked up by a robot arm) is compared with an image from some source (e.g., a camera in an automated assembly line). Because of the large amount of data in the form of pixels in an image to be processed for image correlation, the employment of parallel processing for this comparison is desirable.
There exists a great commercial need for faster and more flexible computer vision systems. For many applications within automated assembly lines, existing computer vision systems are too slow, too limited, or both. Highly parallel VLSI (very large scale integration) based vision systems have the potential for achieving the speed and complexity advances required. Unfortunately, most computational systems do not do well in terms of system performance when applied in parallel. In the general case this is usually due to the lack of sufficient realizable parallelism in the problem to be solved, but vision is a high parallel activity. Existing parallel vision systems are able to do the initial massive parallel computation of the raw image data, but are ineffective in combining the results of the low level computations, analyzing the results, and passing the results of the analysis on to higher processing stages. Indeed complex vision processing can produce much more intermediate data than the amount of data in the initial image. If the architecture of the VLSI vision system is not designed correctly, the fundamental processing bottleneck in the system can be the passing of the intermediate data to the chips where it is needed.
The Fairchild Bit-plane Area Correlator (BAC) is an example of a circuit which does the actual comparison of image pixels to pattern pixels. The BAC was designed with the above problems in mind, and processes most of the image data directly on one chip, passing only limited higher level results back outside the chip. The BAC is a high speed engine for computing correlation style match functions between two images passed to it and was designed with parallel deployment in mind. To utilize the BAC in a pattern recognition system, a method of rapidly supplying a number of BACs in parallel with input images and stored patterns is needed.
Many image processing applications involve simply looking for the presence (or absence) of a known pattern and determining its location. Examples include locating parts on a conveyor belt, verifying the presence of parts during assembly operations, locating bonding pads and alignment marks on semiconductor chips, locating landmarks or targets in aerial imagery, and optical character recognition. Many video signal processing applications involve the computationally related process of convolving a two-dimensional signal array with a mask (e.g., to remove noise or enhance edges).
Both above classes of application require high-speed correlation (or matching) of a mask with an image. In addition, for the image processing examples, it is also necessary to determine the location with the best match. Traditionally, such functions have been implemented in special purpose boards using off-the-shelf components, resulting in large, expensive systems.
An example of how a correlation might be done is shown in FIGS. 7 and 7A. A rectangular image 210 in an image field 212 is captured by a video camera or other means, preprocessed to remove noise or other distortion or enhance edges, etc., and is then presented to a correlator. The image field 212 is represented as a series of binary digits as shown in field 214. Here the zeroes would represent a white background while the ones would represent the dark object.
In the correlation process, image 210 is compared with a series of masks 216, 218, 220, 222, and 224, which are stored in memory as an array of zeroes and ones. The masks have stored different orientations of an ideal image about one axis. The remaining two axes can be matched by moving the image horizontally and vertically, as shown in FIG. 7A. In FIG. 7A, image field 212 with image 210 is being matched against mask 220. As can be seen, the image is first shifted to the right as shown by fields 226, 228, and 230, and then is shifted upward until a best match is obtained. A simple way of determining a match is to compare each digital bit in image field 212 to each digital bit in mask 210 and produce a count of the number of bits which match. This count can then be compared with a threshold value which is chosen for a count which is close enough to indicate a match of the image with the mask. In one alternate method, a small portion of the ideal image could be stored as a mask (such as a 64.times.64 mask for a 128.times.128 image). Portions of the image can then be compared with the mask to determine where a match occurs.
Each line of the digital representation shown in field 214 is referred to as a scan line and the entire field 214 is referred to as a frame. The traditional method of shifting the image as shown in FIG. 7A is to input the digits of a scan line into a series of shift registers and shift the digits to the right sequentially and compare the digits to the mask at each shift position. Such a correlation method is shown in U.S. Pat. No. 4,200,861 to Hubach, et al. As can be seen, this requirement of shifting the bits of an image slows down the processing time due to the requirement for doing a comparison at each shift position.
The processing time required is further increased if one attempts to do gray scale matching. For gray scale matching, rather than each pixel of the image field 212 being either a digital zero or one, each pixel will be a binary number ranging, for instance, from zero to sixteen. Zero could represent white, with sixteen representing black, and the numbers in between representing different shades of grey. Each pixel is then represented by a four bit binary code as illustrated in FIG. 8. The correlation can then be done by comparing bits in a bit plane which consists of a corresponding bit in each of the pixels. The bit planes compared would be first the most significant bit in every pixel, with subsequent comparisons being made of the lesser significant bits. As can be seen, the number of shifts through a shift register required for a correlation is increased by severalfold, with a corresponding increase in processing time.