CA2015162C - Method of and apparatus for increasing the processing speed in the scanning inspection of circuit boards and other objects - Google Patents

Abstract

To reduce the large number of pixels resulting from camera scanning of objects in which defects, features or differences are to be detected, and thus enhance process-ing speed, larger pixels are generated composed of groups of the smaller pixels, but with the smaller pixel informa-tion obtained from scanning conveyed by neighborhood majority binary value monitoring to the larger pixels, such that increased data rate is effected through process-ing the larger pixels without, however, loss of defect, feature or difference information contained in the small pixels.

Description

METHOD OF AND APPARATUS FOR INCREASING THE PROCESSING
SPEED~IN THE SCANNING INSPECTION OF CIRCUIT BOARDS AND
OTHER OBJECTS
The present invention relates to image-scanning in-spection systems, such as used in the detection of faults or defects in printed circuit bards and other objects, being more particularly directed to systems of the type described, for example, in my earlier U.S. Letters Patent No. 4,589,140, and other inspection systems, as well, and to the improvement in increasing the effective processing speed of operations thereof.
As described in said Letters Patent, for example, techniques are successfully used to scan at rapid speeds printed circuit boards or other surfaces and to monitor the detection of defects, irregularities or other features in the boards that deviate from known or accepted fea-tures. Included in such prior systems are the Circuit One*
apparatus of Beltronics, Inc. of Brookline, Massachusetts, assignee of the present invention, which operates in accordance with the methodology and apparatus disclosed in said above-entitled Letters Patent.
* Trade-Mark There are occasions, however, where it is desired to increase the throughput speed of inspection; and the pre-sent invention is directed to achieving such through a novel pre-processing method or technique that, while pa~-ticularly adapted for inspection systems of the above-described type, are more generally applicable to other types or philosophies of sr_anning inspection, as well.
An object of the invention, accordingly, is to pro-vide a new and improved method of and apparatus for the inspection of defects, irregularities or other features in surfaces and in which increased speed of throughput is attained by novel pixel pre-processing techniques.
Other and further objects will be explained herein-after and are more particularly pointed out in connection with the appended claims.
Brief Description of the Drawings The invention will now be described with reference to the accompanying drawings, Fib. 1 of which is a diagra-matic view of a large pixel composed of small camera pixels for use in accordance with the method underlying the invention;

~01~16, Figs. 2A and 2B are binary representations of an array of pixels representing the optical scanning detec-tion, respectively, of exemplary pinhole and speck de-fects:
Figs. 2C and 2D are diagrams similar to Fig. 1 of the sets of larger pixels of the invention for the respective cases of Figs. 2A and 2B;
Figs. 3A and 3B correspond to the cases of Figs. 2C
and 2D, respectively, with appropriate binary value assignments resulting from majority neighborhood value determination;
Figs: 4A and 4B correspond, respectively, to the cir-cumstances of Figs. 3A and 38, illustrating camera timing and line assignments;
Fig. 5 is similar to Figs. 4A and 4B illustrating two-camera interleaving;
Fig. 6 is a block circuit diagram of a preferred pre-processor operating in accordance with the invention;
Fig. 7 is a similar diagram of a circuit for majority value determination and assignment and including broader ~ol~~sz region majority value determination as shown in Fig. 7A;
ana Fibs. $ and 9 are block and flow diagrams of a pre-(erred implame~tation of the systems o!' Fi~s. 6 and 7.
In summary, from one of its broader aspects, the in-vention embraces a method of increasing the processing speed of optical scanning in which an object is scanned by a camera to determine defects, features. or differences, that comprises, scanning the objects to generate binary value small pixels corresponding to the presence or ab-sence of physical characteristics; generating from the small pixels a set of larger pixels each constitutes of a group of the small pixels; conveying to the larger pixels defect, feature or difference information contained in one or more of the small pixels constituting the same; and processing the larger pixels at a data rate or processing speed that is a multiple of that achievable in processing the small pixels, while maintaining the information from the scanning that is contained in the small pixels. Pre-(erred and best mode embodiments and details will later be presented.
. ; , . ...

Considering the illustration of circuit board inspec-tion as an example, current high-speed inspection systems of the above-described and related types must be designed to detect very small defects, such as hairline breaks, hairline shorts, pinholes, specks and critical minute errors. To do so, very small picture elements must be chosen, referred to as pixels, that are sufficiently small to enable the detection of such small defects. Unfortun-ately, however, when pixel size is very small, and the objects such as the circuit boards are large, there are a very large number of pixels to process. To reduce such , large numbers of pixels, and thus enhance the processing speed, the present invention provides a scheme whereby larger pixels are generated (actually groups of smaller pixels). Inspection is made of the information within the group of smaller pixels to determine whether the same contains a defect or region of difference from its surrounding pixels; and, if so, this information is conveyed to the larger pixel. Thus, the number of pixels .
is reduced by converting the small pixels into larger 201~~.62 pixels or pixel groups, and the data rate is accordingly reduced while still maintaining the information contained in the small pi:cels through conveying such information tn the large pixel group.
Camera pixels P, Fig. 1, have binary values of 1 or 0 to denote the presence or absence of conducting material or other physical characteristics or features. The larger pixel P1 (shown composed of four camera pixels P), like the camera pixel P, has also a binary value of 1 or 0; but the binary value is computed in such a way as to accentu-ate in the large pixel P1 small defects or variations, so that they are detected by the shape-recognition algorithm, as of said Letters Patent, which will then process the larger pixels. .
This process will now be explained with the aid of Figs. 2A and 2B which respectively show a pinhole in a printed circuit line (indicated by a 0) and a speck in the board laminate (indicated as a 1). To compute the value of a large pixel P1 one examines the neighborhood of at least an array of six-by-six camera pixels P which is equivalent to at least a set of three-by-three large pixels P1 Fig. 2C. The value of the neighborhood is said to be the majority value of the camera pixels surrounding the center four camera pixels. For example, ~aith the pinhole, Fig. ZA, the majority equals a 1; and for the speck, Fig. 2D, the majority equals 0. The number of pixels that differ from the majority value are computed.
The value of the center large pixel P~1~ Figs. 2C and 2D, is then set equal to the opposite value of the neighborhood if a certain or some minimum number T of the pixels in the center group differ from the neighborhood to accentuate the pixel that is different. Otherwise, it is set equal to the same value as the neighborhood. Thus, for the pinhole of Fig. 2C, the large pixels P1 will have the values shown in Fig. 3A, where the center larger pixel Pcl is 0 because of the 0 information within the center larger pixel of Fig. 2C. Similarly, the center pixel Pcl of Fig. 3B, for the case of the speck in the laminate, reflects by its 1 value, the information within the cen-ter large pixel Pcl of Fig. 2D.

_8_ Relative to camera timing, the large pixels P1 are computed every other camera pixel and every other camera line. Figs. 4A and 4B indicate the output values of the lar:de pi:cals relative to camera line ni.~mber and pixel timing for the respective pinhole and speck examples of respective Figs. 3A and 3B. Large pixels are shown compu-ted on the occurrence of an even line (line numbers 2, 4, and 6) and pixel number.
The pattern recognition processors of the present in-vention operate at the data rate of the large pixels Pl, which is half the camera pixel data rate. This could correspond to, for example, 10 megahertz for a 20 me~a-hertz camera. In addition, sinee the system must operate on images without missing lines, processor data can only be analyzed on alternate camera lines.
Conceptually, since in a 20-megahertz system, large pixels P1 are produced on alternate or even-numbered camera lines, half the time there is no data to process.
Thus, to utilize this time effectively and to achieve a benefit from the rate reduction of the invention, one . . . . ~ ~ v ~ i . .

_g_ could interleave two cameras to double the throughput rate; one producing large pixels on odd-numbered lines, and the other camera producing pixels on even-numbered lines as illustrated in Fig. 5. In this configuration, the two cameras would view adjacent strips on the printed circuit board.
To take full advantage of the two cameras in conjunc-tion with the processing system, effectively a single pro-cessor is provided in which the memory is subdivided into two halves; one for one camera path A, Fig. 6, and the other side or part of the memory would support camera path B. Thus the two cameras A and B may be interleaved. on alternate lines and place their data, into corresponding MA and MB sides of memory such that the system would process data in the same mode and in conjunction with the same technique described in said Letters Patent and in the previously-mentioned Circuit One system.
The beauty of this technique for interleaving odd and even lines is that, in reality, only one common data pro-cessing channel is required. Since the memory itself is * Trade-Mark divided into that region of memory MA that stores and builds pictures and data from camera A and that part of memory MB that will store the picture from camera B, all that is required is a sufficiently la me memory to store the pictures from the two camera systems. The processing electronics that feeds the memories and all the data pro-cessing electronics around the memories, however, only need to be in a singular form since at no instant in time are both camera A and B large pixel data available simul-taneously. Data is read from camera A, it is processed through the system and it is stored in that region of memory MA allocated for camera A. On the next line, the data from camera B is placed into memory MB allocated for storing its large pixel images. Thus, only one processor is needed and therefore the final result is achieved of being able effectively to process data at four times original speed.
In the example of Fig. 6, the smaller pixels P11-P66 make up the three-by-three larger pixels P1, with the neighborhood majority and center pixel value computation 20~.59.6~

effected as before described; namely, the value of the center larger pixel Pcl is not equal to the majority value iE more than T pixels within the center group differ from the majority value. This accentuates camera pixels P33. P34~ P43~ P44 that differ from their surroundings and which are often defects. This information is thus convey-ed into the large pixel group while dropping the average rate by a factor of four.
As an example of the effective data rate compression from the camera to the final output, assume the two eam-eras are operating at a given data rate N; such as 20 meg-ahertz. The data from the camera, Fig. 6, is subsampled into the larger pixel groups P1 to produce a reduction of at least a factor of two; so that the 20 megahertz data rate with the large pixels P1 is effectively a N/2 data rate, or l0 megahertz on every other line. By interleav-ing the data from the two cameras (Multiplexes, Fig. 6) the processor only runs at a continuous 10 megahertz rate while both cameras A and B are continually running at the 20 megahertz data rate. Thus, two cameras at 20 megahertz :'r . - " . . _ m ~ . .. . ~ '~ ' , ' each produce an effective, true scanning board speed of 40 megahertz, though the processor is only processing data at megahertz.
In this illustration of the technique underlying the invention, the simplest approach has been taken of produc-ing large pixel groups P1 containing only four smaller pixels P which produce a net average data rate reduction of a factor of four. Generally, more than four pixels in a larger pixel group may be employed, if desired; three-by-three, four-by-four,...M-by-14, for that matter; and ' also two-by-three, etc. The reduction would correspond to the number of pixels P in a large pixel group Pl. As a further illustration, if instead of using an array of two-by-two smaller pixels P yielding an average reduction rate of four, if three-by-three were employed, there would be a reduction of nine. Four-by-four would produce a reduction of sixteen, etc., with corresponding processing speed increases.
y ~ . , . .:' . , ,. __.....

20.5162 Furthermore, while the earlier example of Figs. 2A-6 involve a general neighborhood of the set of three-by-three Large pi:cels P1, corresponding to six-bv-six small pixels, other numbers may be used, such as a set of four-by-four large pixels, or five-by-five, as further exam-ples; and the only thing that would increase is some of the processing hardware immediately used to compute the majority value: Since hardware, however, is becoming cheaper and more dense, it appears that in the immediate future, practice will not be limited to using the exem-plary three-by-three large pixels.
Another extremely important aspect is that when the value of the center larger pixel Pcl is computed, it is stated that the value of the center pixel group is not equal to the majority if more than some predetermined number of pixels (T) contained within the center group differs from the majority value. This accentuates pixels that differ from their surroundings and which are fre-quently defects,that it is desired to detect in the inspection process. The specific threshhold value will n ~. ; , 20~5~62 vary and, in fact, can be varied to achieve different results. For example, if it is desired to scan a circuit board and have the system not learn very small defects, such as very small pinholes, the rule may be set that for a large pixel group PZ to be different from its neighbor, a large number of small pixels P in that group must indeed be different from the neighbor; and if only one out of four pixels P is different (say constituting a very small pinhole), this will not be reflected at all, and the threshhold will accordingly be set. Likewise, at the time of inspecting the object, it may be desired to have the exact opposite results; i.e. finding a small pinhole wherein only one pixel differs from the majority. BY
varying the threshhold, the system can be tuned for such different applications.
Another way of fine tuning the results involves selecting the size of the neighborhood. If we start with a large neighborhood, and the number of pixels equal to a l are approximately 50 percent, one can choose a smaller neighborhood that yields a better estimate of the data pixels surrounding the center pixel. For example, if the large neighborhood contains 6X6 (36) pixels and the number of data pixels equalling 1 is 17, a 4X4 (16 pixel) neigh-boyhood may be selected to determine the majority value.
In addition, one can also compute the majority pixel value of the 4 2X2 groups shown in Fig. 7A. These may be re-ferred to as groups A, B, C, D, enlarging and surrounding the four corners of the center pixel group E, using these majority values to help determine the neighborhood major-ity value. The mechanism of selecting smaller neighbor-hoods to eliminate ambiguity increases the intelligence of the algorithm. If the number of pixels in the 6X6 group equal to a 1 is approximately 50~, then the majority value given by the smaller 4X4 local group is selected to yield a better estimate for the pixels around the center group E. If the value is not close to 50r, the binary value of the majority given for the 6X6 group is selected.
Shown in Fig. 7 is a block circuit diagram illustra-ting how the value of the center pixel group Pcl is determined as a function of the majority neighborhood 2015.62 value, the value of the center pi:cels in the center group, and the variable threshhold T. There is provided a compu-tation circuit block lO, called the majority neighborhood value comautation, which determines whether the majority of binary pixels is indeed a 1 or a 0. The center pi:cel group Pcl is accessed and as a function of the majority value. If the majority value is equal to 1, then the sum of points equalling a 0 in the center pixel group is com-puted in the summation circuit 12. If the majority value equals 0, then the ,sum of points equalling 1 in the center pixel group is computed. Thus, the output of the intelli-gent summing section 12 indicates the number of pixels which are not equal to the majority value. A comparison is then made in comparator 14 of the number of different pixels, with a threshhold input T that may be variable as a funetion of defect or detectable size, as before men-tinned. The output of the comparator 14 that compares the majority of different pixels to their threshhold value T
is equal to 1 if the number of pixels that differ from the majority exceeds the threshhold value. The output is 0, otherwise. The logical exclusive output of the comparator ~. i 14 is with the ar_tual majority value itself, yielding the value of the center pixel group Pcl. Whenever the number of differing pixels in that center group Pcl exceeds the threshhold T, then the value of the center group is the opposite value of the majority; and, likewise, when the number of differing pixels is less than this thresh-hold T, the value of the center pixel remains the value of the majority. As before pointed out, a larger neighbor-hood about the center group (A, B, C, D, Fig. 7a) may also be selected.
It is important to emphasize that what has been above described is in essence a pre-processor. It does not assume or make any assumptions as to the type of process-ing to be followed. Thus it can be used as a pre-processor with many types of apparatus, whether it be line width measurement, pattern recognition systems, a system that stores data and desires to decrease the number of data bits that are being stored or other similar applica-lions. The invention provides a rather generic pre-processor that can be applied to a large number of such processing systems.

A preferred method of implementation of the system of Fig. 7 used four CCD cameras A, B, C and D and eight mem-ories ("MEuI" through "MEMR"). Each memory is capable of storing one CCD camera linN of data. This imvLementation used 8Kx8 bit memories (type PC164 mace by the Performance Company) and 2500 element CCD's (CCD Type 181 made by Fairchild Company). During the first CCD clock cycle, the first pixel of each CCD is stored. Pixels App, B00 are stored into MEM1, and C00, D00 into MEM3, as shown in Fig. 8. During the second clock cycle, the second pixel of each CCD is stored; A01, BO1 into MEM2 and CO1, DO1 in-to MEM4, where Cxy denotes camera C, line number x, pixel number y. Memories MEM1, 2, 3 and 4 are filled during the odd-numbered CCD scan lines. In a likewise fashion, memo-ries MEM 5, 6, 7 and 8 are filled during even-numbered CCD
scan lines. During the third CCD scan line, new incoming camera pixels are stored into the free half of memories MEM 1, 2, 3 and 4, while reading out large pixel groups from the previously filled other half of the same memory, corresponding to cameras A and B.
The memories (with a 25 nanosecond (ns) access time) ~01~16~

are sufficiently fast to enable reading large pixel group data from one address and then writing new camera data into another address within one LOOns cycle. Two Large pi:cel groups are read out each clock c~~cle yielding a 2:1 increase per (;CD scan line. The readout format is shown in Fig. 9. During line 4, new pixels are stored from cameras A, B, C, D into the free half of memories MEM 5, 6, 7 and 8, while reading out large pixels corresponding to cameras C and D. The total address space or length of each memory only needs to be one CCD,line long since there are half as many Large pixels as camera pixels per line.
In general, this method can be expanded to handle more cameras by adding more memories.
As the large pixel groups are read out of the memor-ies, they are placed into a vertical and horizontal delay line, (for example, fabricated using PC164 memories and 74374 type latches). These delay lines form the 6X6 pixel neighborhood shown in Fig. 7. The 36 total pixels are in-put to a programmable logic device (such as type EP1200 by Altera Company) which is programmed to compute the major-ity value of the neighborhood, and produce the value of 2~~~~~~

the center pixel P~ in Fig. 7, using the procedure described above.
Further modifications will occur to those skilled in the art, and such are considered to fall within the spirit and scope of the invention as defined in the appended claims.
..,

Claims (11)

1. A method of increasing the processing speed of optical scanning in which an object is scanned by a camera to determine defects, features or differences, that comprises, scanning the object to generate binary value small pixels corresponding to the presence or absence of physical characteristics; generating from the small pixels a set of larger pixels each constituted of a group of the small pixels; incorporating into the larger pixels defect, feature or difference information contained in one or more of the small pixels constituting the larger pixels, by examining a neighborhood within an array of small pixels equivalent to the set of larger pixels to determine the majority binary value of the small pixels constituting the neighborhood, and setting the value of the center larger pixel composed of the center group of small pixels to the said value of the neighborhood if a certain or minimum number of the pixels of the center group is equal to the said value of the neighborhood, and otherwise setting the value of the center larger pixel to the opposite binary value to accentuate at least one small pixel therein that is different; and processing the larger pixels at a data rate or processing speed that is a multiple of that achievable in processing the small pixels, while maintaining the information from the scanning that is contained in the small pixels.

2. A method as claimed in claim 1 and in which the said certain or minimum value is varied correspondingly to vary the increase in processing speed and/or to vary the size of the defect, feature of difference to be detected.

3. A method as claimed in claim 1 and in which the array of small camera pixels is at least six-by-six and the set of larger pixels is at least three-by-three.

4. A method as claimed in claim 1 and in which a pair of cameras is employed for the scanning, with the respective larger pixel sets generated in each camera path being stored, on alternate lines, in separate parts of a memory, and with a single common data processing channel for both camera paths.

5. A method as claimed in claim 1 and in which the small pixel defect, feature or difference is detected by shape recognition.

6. An optical inspection system preprocessing apparatus for use with camera scanning of an object to determine defects, features or differences, said apparatus having, in combination, camera means for generating binary value small pixels corresponding to the detected presence or absence of physical characteristics;
means responsive to said small pixel generating means for developing therefrom a set of larger pixels each constituted of a group of the small pixels; means cooperative with the larger pixel set developing means for determining the majority binary value of a neighborhood comprising small pixels surrounding the center group of small pixels within the set of larger pixels; means for setting the value of the center larger pixel of the set composed of the center group of small pixels to the said value of the neighborhood if a certain or minimum number of the pixels of the center group is equal to the said value, and otherwise setting the value of the center larger pixel to the opposite binary value to accentuate at least one small pixel therein that is different; and means for enabling the processing of the larger pixels at a data rate or processing speed that is a multiple of that achievable in processing the small pixels, while maintaining the information from the scanning that is contained in the small pixels.

7. Apparatus as claimed in claim 6 and in which means is provided for varying said certain or minimum number to effect at least one of varying the increase in processing speed and varying the size of the defect, feature or difference to be detected.

8. Apparatus as claimed in claim 7 and in which the set of larger pixels is at least three-by-three, with the small pixels in each large pixel at least two-by-two.

9. Apparatus as claimed in claim 6 and in which a pair of cameras is employed for the scanning and wherein means is provided for storing in separate parts of memory means, on alternate lines, the respective sets of larger pixel sets developed in each camera path, and with a common data processing channel for both camera paths.

10. Apparatus as claimed in claim 9 and in which four cameras are employed with four odd-line and four even-line memories.

11. Apparatus as claimed in claim 6 and in which said neighborhood is comprised of four adjacent large pixel groups each containing a respective one of four camera pixels of the center larger pixel.