JPS59103179A - High speed pattern recognition device - Google Patents

Abstract

(57) [Summary] This bulletin contains application data before electronic filing, so abstract data is not recorded.

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention relates to a fast pattern R travel equipment ftK, and more particularly to a method of memorizing a known scene and searching an unknown scene so as to determine the best matching coordinates in the shortest possible time. and equipment.

IQ turn recognition is used in various industrial fields such as automatic alignment, inspection, manufacturing, counting, and job classification. Turn recognition devices can automatically recognize and inspect parts and control manufacturing operations from a distance without the need for human intervention.

It is important that pattern recognition equipment operate as quickly as possible, be error free, and be accurate to eliminate false alarms and maintain as high throughput of the manufacturing process as possible with minimal downtime.

The present invention provides improvements over the known art primarily in terms of speed of operation.

For prior art, see ViewEngine, Caworth, Calif., the same assignee as the present invention.
Patt9rn Recognizing Device and Method for Patt9rn Recognition
on Apparatus and Method)”
Patent entitled m'1. ．． 200. II, No./No.

This View patent has become the standard by which Ike's no-e-turn recognition system is compared and is widely used in the industry.

In operation, real-time video information is timed and digitized based on brightness, and video threshold levels are determined in response to changes in brightness.

First, digitalized video information is retrieved from a reference scene stored in random access memory.

In search mode, digitized video information is obtained from the scene observed in real time, and the above memorized approximate information of the reference scene is approximated from the field of view of the zone being searched. The information is compared in real time. The coarse information from the reference scene and the coarse information from the observed scene are convolved to form a correlation value that indicates the degree of agreement. After the zones are examined, the X and Y coordinates for the best match are determined. A fine search is then performed in the vicinity of the already determined rough location to increase the accuracy of determining the coordinates that show the best match.

Known systems are very accurate and require approximately 130 m') seconds to complete a search.

When using a known pattern recognition system, - the coordinates of the dots are stored in memory in order to minimize errors in determining the coordinates and to maximize the probability of finding a match at the first location. It is necessary to precisely angularly align the reference scene with the video image of the cow.

In actual operation, the component is placed below the optical device. The alignment or angular orientation of the individual parts is very precise with respect to the stored fiducial orientation, and deviations of more than 50 will affect performance.

Consider case 4 when using a pattern recognition device for automatic alignment in a wire ending device for semiconductor chips (IG).

Inaccuracies caused by the user not properly aligning the microcircuit chip or IC with respect to the lead frame result in errors in the convolution of the reference pattern with the IC to be twisted. Therefore, a perfectly good IC may be improperly bonded, and the part will be rejected from testing. It is clear that the exclusion of good parts is costly and uneconomical for the manufacturer since it leads to high sflug rates and low production rates.

The search time of the known system is always ko/jθ regardless of the state.
It is millisecond.

For those who use pattern recognition devices in automated manufacturing operations, it is desired not only to know the position of a given object, but also to measure its angular orientation to a standard.Known pattern recognition devices In this case, if there is an error in the angular direction of the part being searched, problems will arise in green classification and accuracy.

In wire bonding applications, it is necessary to accurately determine the angular direction of 1C that will benefit the lead frame from which the IC will be placed. In the case of some large scale 1c, such as large scale memory chips or microphones of processors, this angular direction must be known with an accuracy of better than ±0.70.

Therefore, the known gloss turn recognition device, which cannot directly measure the angle due to lack of angle counterfeit measurement ability, accurately measures the X and Y coordinates of a widely separated point on the IC, and from there, determines the angle of the dangling device itself. Angular information must be calculated with sufficient accuracy by software.

To accurately measure these X and Y coordinates, the field of view required by the pattern recognition device is very small. This is because the resolution capacity is limited to 5 pixels. This imposes a condition that J points, which should be precisely located, cannot be simultaneously present within the visual cusp of the pattern introduction device. Therefore, each point must be observed and explored individually without regard to each other, and +C (or the camera) must be physically moved from one position to another.

The time required to physically move it is relatively long, so the final 1c production rate is significantly and unnecessarily lower than that which is possible with a very sophisticated putter/recognition system. .

Wood brother! IJ allows precise angle measurements in a single observation and in real time, which can significantly increase production rates and reliability in the 1c manufacturing process.

In the present invention, we utilize the search capabilities of pattern recognition systems exemplified by the aforementioned View patents,
This is equivalent to electronically rotating and convolving the reference data stored in memory in real time, thereby comparing the stored reference data with the stored data taken from the scene under test. A method and device are devised to demonstrate this ability. The reference scene address is rotated a given number of degrees and the stored data is read and correlated to the scene under test. The comparison is performed essentially as in known systems, producing a count indicating the degree of correlation.

Otohiro Bixel x 1. ≠ pixels and a complete error-free comparison yields a perfect match of l/lo 2, but experiments have shown that a match of 3000 is acceptable.

The basic search continues until the cumulative count exceeds a given threshold value. Once the threshold value is crossed, the rotation of the scan rate of the reference scene in memory is stopped and a fine search is started in a conventional manner to find the XY coordinates that represent the best search conditions for that particular alignment angle. is determined. Since the cumulative count exceeds the threshold value, a qualitatively high match is known to be in the immediate vicinity, and a fine search is initiated to determine the XY coordinates that represent the best search conditions within that region.

Once the x,y sit bones that represent the best search conditions are determined, the alignment angle of the search scene relative to the reference scene can be determined.

The reference scene is rotated repeatedly and compared to the test scene until the match count reaches a minimum, then a maximum, and then a minimum again, at which time the search is stopped. The trajectory of the correlation values forms a bell-shaped curve with a peak at the rotation angle representing the angle at which the best match was obtained.

An interpolated d1 calculation is then performed on the data points to accurately calculate the angle of best match. A particularly useful form of interpolation involves calculating the centroid of a trajectory of data points.

The calculated angle represents the angle at which the agreement is the theoretical maximum. This point occurs at some value that coincides with the printer point or coincides between two data points. Centroid or pond interpolation calculations are equivalent to increasing the resolution of the angle measurement process. Preferably, the increment for rotation is fixed at 2.00 for each data point.

The X and Y coordinates and angles are now determined without regard to the angular orientation of the test part on the lead frame, allowing the actual angular values to be calculated with an accuracy and reproducibility better than 10,100. The chip can be placed on the lead frame at any angle between 00 and 10 degrees out of angular alignment.

Regarding the basic operation of wire bonding for its intended use, the following sequence of events is taken.

A clean, defect-free semiconductor chip is placed under the camera lens, properly aligned, and illuminated. Put the pattern recognition system into load mode. The image of the seven parts of the semiconductor tesog that serves as a reference body is within a prescribed or specified area within the field of view formed by the Otsugu x Otsuhiro pixel area.
Bring it to a position where you can fit it.

The video information sound contained within this region is converted into a two-level form (consisting of a pattern of m<i and 0) in the video processor of the system.

At the user's option, a reference body evaluation algorithm may be used to determine the suitability of the selected reference body in terms of its uniqueness, noise characteristics, and statistical relevance to accuracy requirements. Criteria used in this evaluation procedure include autocorrelation techniques or other evaluation techniques.

Pond algorithms that can be used include means for determining which segments of the selected reference body are harmful in terms of noise and thus which segments should be excluded from the reference body or masked.

Additionally, a procedure is performed during the loading phase to select a matching threshold value for detecting significant correlations during the exploration phase. The above threshold pole i' is derived by autocorrelating the reference object to its own rotation to determine the degree of agreement. 6 while exploring
．． ±3.00 if 0° rotation increments are used.
It is only necessary to autocorrelate for the rotation of . The threshold is chosen as the worst match value of the pair modified by a constant that anticipates and estimates performance degradation due to noise and small pattern variations in the scene to be searched.

Additionally, a search for the field of view is initiated during the load phase and a maximum redundancy correction value is determined to establish a lower bound on the detection threshold.

The field of view during the search phase covers the area of the semiconductor where a counterpart to the fiducial is expected to be found.

The video from the field of view is straightened, bileveled, and stored in memory. At this point, the angular direction of the search area is unknown.

Starting from a particular reference direction, which is selected based on knowledge of any reference or priority information (which is based on the concept of probability), the reference body is convolved with the stored search field. Ru.

This search is done in a rough manner. This is because the purpose is primarily to detect the presence of a match and determine its approximate coordinates in the search field. If an approximate correlation peak above the threshold is found, the approximate search is terminated and a series of fine searches are performed only in the immediate vicinity of the approximate peak. During each fine search, the reference direction is increased in steps of 2.00 in either direction until the best match is found. The appropriate direction of angular increment is selected by automatically planning the correlation peak value for each fine search to determine whether a particular direction of angular increment results in an increase in the correlation peak value. .

If the match value does not exceed the threshold during the first rough search, the reference body is increased by 16.0° in a particular direction from its starting angle, and the ! A rough search is carried out. If the threshold is still not detected, a second 'g,$ angle search is started in increments of -6,0° with reference to the starting angle. The process of alternating VC rows fZ') in increments of +40 continues in this manner until a detection threshold is exceeded or a predetermined cutoff is reached.

As soon as a rough match is detected, the rough search is terminated, and the second search is continued until the matching coordinates are precisely searched.
A fine search angle reference increase of 0° is initiated.

An example of bracketing the best correlation peak value to determine an accurate angular direction measurement until enough data is obtained.
A fine search can be performed on both sides of the large correlation peak, and when the above data is obtained, an interpolation algorithm can be used to fit the data by curve 1, or the centroid of r calculate. This allows the angle of best match to be calculated with an accuracy of ±0.10 even if the reference body is rotated by only 2.0° increments relative to the fine search.

The search operation is terminated as soon as the desired coordinates and orientation angles are determined, so no additional search or processing time needs to be spent.

An additional savings in search time can be achieved by programming the device to begin searching for the next test object on the lead frame at an angle closest to that found in the previous search.

Although the pattern recognition device of the present invention is capable of searching completely over 3 o0, by starting a second search at the same angle or close to the angle at which the first item was discovered. The time Wfi commitment fulfilled is substantial under the following conditions.

Known A-turn recognizers require iso milliseconds to complete their search before reading.

The turn recognition device of the present invention, which utilizes the apparatus and method described herein, can perform readouts in an average time of only jOmi+) seconds, within which time it also provides angular readout positions from a single observation. This was not possible with known systems.

Known systems that rotate the image 11 times a year require very large H1 calculations and storage capacity. The computational time required and the hardware required to perform rotational operations preclude the use of rotational correlation in known systems.

In the present invention, rotation is performed by calculating only six variables for each angle to be stored in memory. This makes it possible to rotate over 31.00 degrees with a minimal amount of memory, and also eliminates the need for multiplication or trigonometric calculations and requires complex or expensive hardware other than simple accumulators or adders. Since no hardware is required, all steps can be performed on high-speed real-time hardware.

In the description of the invention, all references to digital signals shall include multi-level signals (gray scale) and λ-level signals, often referred to as binary signals or pi-level signals.

Further objects and advantages of the present invention will become apparent from the following detailed description taken in conjunction with the accompanying drawings.

Now, FIG. 1 shows a block diagram of a complete 1,000-turn recognition system constructed according to the principles of the present invention and using the threshold technique adapted to the reference body and the idea of rotating the scan angle of the reference data in the memory. A diagram is shown.

The central processing unit, hereinafter referred to as CPCIIO, is the heart of the system and controls the algorithms necessary to control data processing, data digitization, output data storage, convolution, and comparison. . J'
The system timer 12, in the form of a clock with a frequency on the order of M82, constitutes the basic timer of the system and is used to digitalize human video information and maintain overall system timing. Controls the generation of all necessary timing signals.

All video information is transferred from Video Manpower 14 to Video Memory 2
0, the video power 14 is populated with the necessary sensor elements, including, for example, a vidicon camera and associated timing circuitry for digitizing the video information. The video information is digitized in accordance with the known art, and in the preferred embodiment shown herein, a positive going signal of the form / represents the bright level of the information and a negative going signal of the form O represents the dark level of the information. There is. The pattern recognition device uses a reliable clock block that varies discretely from/to θ with each individual segment optically detected as bright or dark.
It is based on the method of first creating digital video information. Video camera and digitization circuit are video human power 1
4, when observing a scene, generates a sequence of arrows at a specific number of repetitions determined by the system timer 12, and these arrows are based on the scene being scanned. / to θ.

The functionality of the pattern recognition device is based on initially loading the reference data for the part in question from the video manual 14 into the reference memory 16 via the cPUlo. Also c
puio controls one rotor 18. This rotor is θ
Reference memory 16 along the scanning line from ° to 3 o θ °
can read the addressed information within. The rotor 18 controls the scan angle and does not physically rotate anything, but only allows the reference memory 16 to be scanned at the selected scan angle.

Video information from the scene is provided from video input 14 to video memory 20 .

Output from reference memory 16 and video memory 10
The output from is constantly fed to the convolution device 22 in real time. The convolution device 22 continuously compares and correlates the video information of the scene retrieved from the video memory 20 with the stored footage in the reference memory 16 and the cPUlo and threshold level controllers 26 .
provides convolved information to an accumulator 24 under the control of .

In the preferred embodiment, a reference body is used in which B≠Vixels×6≠Vixels, and this reference body is such that for a perfect match, the correlation number stored in accumulator 24 is 0.
Give ri2. In practice, a perfect match is unlikely to occur, and for all practical purposes it has been found that a perfect match cannot be obtained. at least 300
A threshold level of 0 is considered a good match and is highly reliable. This value from the threshold level controller 26 is continuously rDk from the convolution device 22 in the accumulator.
Compare the values to #, which are equal to or greater than the threshold level! If the IJi level is found, the search ends. This point is based on accuracy, position,
The angle information t is evaluated in detail here.

Threshold level flilJ Ill device 26
With the use of , it is no longer necessary to explore all search areas. If the first part of the video search matches the reference object, the search ends immediately and a time saving of almost 700% is realized. However, until the last part of the video search, when no match is found, the savings are lowest, but still an average time saving of jO% compared to the prior art is achieved. ;i, is not maintained at a constant level and depends on the quality V of the video information in the reference memory 16. This reference information supplied by CPU10 is evaluated by a suitable algorithm and based on the quality of the information, this CPU10 is assigned to accumulator-2.
4, adjust the new level of the tc, xv hold level controller 26. Generally, if a high quality signal is provided as reference data, the threshold level control 26 will be set to a correspondingly low level. A low quality signal is supplied to the reference body memory 16.
is typically set to a high level. In the preferred embodiment, CPU 10 is programmed to control rotor 18 in 60 segments, so that r-time from reference memory 16 is the first Position 7) ra 0 Scanned along a segment-shifted scanning line. The output reference data O is written into 6' with the video data from the video memory 20, and is then recorded in the Cr accumulator 24. threshold level 1lil
This process continues until the level becomes equal to or greater than the Lettuce Renoschhold level set by K. When this happens, the search ends and the address information at that position is stored in the memory. 28 memories are stored. At this point, CPU 10 programs rotor 18 to repeat in 2 degree segments with the stored address for each match to determine the peak value.

Referring now to the m2a diagram, there is shown a graph 40 in which each segment changes until a count greater than the threshold value is accumulated. The initial search for the accumulators supplied to the memory 28 for the rotational positions of M i starts from an arbitrarily chosen position, ±l, until it is determined that the count of the accumulator is greater than the threshold value.

Change. The search starts at +60, then -6°, then +
Hamu 72° and so on, since it is statistically established that the probability of finding a match is higher by rotating relative to a given reference body and then rotating any 6° in a given direction. Once the high JR dan count is determined, the search stops and the final fffi is determined by its angular displacement in order to determine the X and Y, th marks. i
It starts with Known System 1 Here, the concept of a suit f-vixel is described and used, where seven so-vixels have a square pixel on one side and a ≠ vixel on the other side, thus having an area of 16 pixels. defined as something.

However, in the present invention, a rough search concept is used, and the suit f-vixels are not used, but rather general-sized vixels are used as samples taken from the area of ≠ pixels. In example e, the sample pixels of each area of the Hiro pixel are taken from the same location, and the result obtained is equivalent to actually forming a new pixel with the same area as the ≠ pixel.

It will be obvious to those skilled in the art that it would be more economical in terms of hardware and time to sample the region of a gvixel than to create a new vixel and explore its region.

This rough search here is a search for regions that constitute a single pixel for each ≠ pixel, in other words,
32 pixels on one side and 32 pixels on the other side, ie, a total of 702≠Hixelno coarse reference body searches.

The search continues in a general manner until the CPU determines the X and Y coordinates based on the rough search. Each≠
A rough search using a sample rate, with vixels per pixel, is performed in the same manner as disclosed in known patents that utilize suits and pixels.

Once the coarse search is completed, a fine search is performed with normal pixel size. The reference body is Otsu≠pixel x Otsu≠
The fine X and Y coordinates, expressed in pixels, are determined by the CPU after performing a statistical centroid operation on the maximum accumulation from the accumulator.

Please refer to Figure 2b, where the angle rotator is rotated 2° in the X, Y position, which is found as the best matching position.
A curve 59 representing the accumulation from the accumulator obtained by rotation is shown.

The rotor 18 is set to 2 such as 60.62 by the CPU10.
It is programmed to give one maximum reading. The CPU 10 has a reading of 64 on the 7 side of the reading 60.
．． The rotor 18 is adjusted to an initial value such that the rotor 18 obtains two readings V is programmed to increase by 2 degrees from the starting point.

Reading 66.64, 60°62 shown in Figure 2b
．． The cumulative information represented by 68 and 69 is CPIJ
IO, the CPU 10 performs a centroid operation to determine the maximum point of the curve, which is read out from the CPU as the angle that gives the best match.

The CPU 10 then performs another fine search for the center of rotation found above updating the X and Y coordinates for the best search, and then the cpuio
The X and Y coordinates representing the best position and angle can be read out and the orientation of the video scene relative to the reference body determined.

The concept of using a combined C1 threshold level with rotating read data from the reference memory is an effective means of achieving time savings in the present invention.

The threshold level is used to stop the search sequence when a valid match between the reference body data is achieved. The actual procedure for determining this level is not important to the present invention, as the threshold level can be set arbitrarily or appropriately by the CPU based on the quality of the reference data. In the fine search defined by Otohiro x Otogu Bixel,
Perfect match, θ! It is given by P. It is expected that each pixel of the reference data is preferably compared to each pixel of the video data to give a complete count of ≠,0. Experiments show that it is impractical to predict such counts, but also that values between 3000 and 3!00 indicate a high probability of a good match.

In an ideal situation, all zlltx ot≠ reference data could be matched directly against the ot≠×6≠ video data to determine the actual count.

In the preferred embodiment, economic constraints and hardware costs make this impractical. In fact, the rough search, or sampling search, actually consists of sampled pixels, and 32×
It is designed to use the 3.2 reference body. At one time, ///2 of the reference data matches ///6 of the video data, so in order to obtain the total number of matches between the reference body and the data of a particular point, the individual matching sequences of It is necessary to run them and add their results together. The total number of matches, which is the number of correlations, is determined by our g70 (up to 7
0.2 ≠ Throat 5%) kC is compared to an arbitrarily set threshold.

Further savings can be realized when using incremental thresholds to terminate the search at a particular search location.

The time-saving benefit achieved by using a threshold can be understood by assuming that there are no more matches after g of the 76 matching sequences. This means that the fence must add up to a total of 170 in the threshold. This is not possible in practice, since the only perfect match of the reference area half is J/, 2 and 3. To have any chance of reaching the .170 threshold, at least 331 matches (z7o-!r/
, 2) is necessary.

To account for this possibility, the hardware is programmed to evaluate the number of matches after g matching sequences have been completed, and if this is less than 331, the search ends at that point. , the machine is commanded to move on to the next evaluation point. This procedure saves considerable time that would otherwise be wasted in evaluating defects. Same as this 4! The logic is executed at each time of the matching sequence, not only after the JtGth, J(see fence).

The time savings gained by using incremental thresholds can be seen by considering the table below, which includes the minimum thresholds after each sea fence.
From this it will be more fully understood.

＼ ) Takeru Kamo h Jō ＼ ＼ ＼ ＼ ＼ ＼ ＼ ＼ ＼ ＼ ＼ ＼ ＼ 1 between the series of matching sequences of Ozume and the ending -t sequence (note that the number of required matches is larger than the number predicted by random chance) Thus, if averaged with a threshold of 70, the search seafence can end after the fifth series of seafences, and (-] result: !71.5'
This results in time savings of near j%C////l, X100chi). For higher thresholds, the time savings will increase; for lower thresholds, the time savings will decrease.

Increasing threshold hole! 9th level'v M Continuation!
'i! :Calculate, update...-ware is determined as follows.

Table 2 Since incremental threshold = threshold - (% remaining t)) (exact match) and Φ - match h increment threshold (search should continue up to this point), 4 - f (
'5 threshold (% remaining) (exact match), or ≠ - match 1 - (% remaining) (exact match) this threshold, or this threshold, or Match + (Exact Match) - Completion of Match Sequence + Match +K
- Completion of match sequence (K2) h threshold ≠ - match (by threshold - + MSC (K, q
) Toru.

- The incremental threshold is compared with the number of matches in parallel to the comparison of the scatter with the termination threshold. Also Lf
ft threshold is not exceeded, stop considering the current search position and continue searching for the next position.
Hardware is programmed. If the termination threshold is exceeded, the coarse search ends, followed by a fine rotation search.

Song fi in figure 2b! 59 is the CPU of the preferred embodiment
details that the angle rotator 18 is programmed to rotate the scan of the fiducial data in 2° increments as long as the total cumulative pixel count increase increases. Until the CPU output level falls below the maximum level again! It is programmed to control the angle rotator 18 in zero increments.

Once the CPU determines this fact, it stops searching because it is now clear that a match has been achieved, the exact angle from the centroid can be determined, and the exact X and Y coordinate location can be determined.

Please refer to FIG. 3, where a pixel pattern 50 stored in the reference memory 16 is shown. The pattern 50 stored here actually represents each bit of information stored in an addressable memory location.

The angle rotor 18 is connected to the reference memory 1 by the CPU 10r.
The program is programmed to first rotate a scan line of information stored in 6 and read that information along a scan line rotated a given angle theta from the initial reference body.

At any time, the desired data has one length of 4;≠
pixels, the other length is 6 hiro pixels, i.e. total ≠
, 0 is contained within the memory matrix 5o containing the pixels. Examining Figure 3, it is immediately apparent that rotating the reference area by an angle theta to the new position 52 requires a reference area that is substantially wider than the reference area of Otohiro x Otsu≠ pixels. become. In a preferred embodiment, an area of 4 pixels x 6 pixels is selected to ensure that the reference area 50 is not rotated 360 degrees and always maintains a complete reference area of 6 pixels x 4 pixels. be done.

It is emphasized here that, as mentioned above, the term rotating the reference body indicates the result of a manipulation such that information is scanned from the reference area 50 at an angle defined by the rotation angle theta. For purposes of explanation, the reference body is referred to here as being rotated, but rather the information contained in the addressable memory is referred to as the original information - which was inserted into the reference memory 16 and rotated by the reference area. It is read out along the scanning direction shifted by the angle theta.

The basic task is to identify the point 54 on the reference region 50, rotate the point 54'f to point 56 by a given angle theta, and read out the information of the rotated reference region 52.

A known solution to this L7) problem is the Cartesian
The method calculates the position 56 on the mark, converts the position # to a polar mark, and selects the next pixel position along the rotated scan line 58. In this way, for a given angle theta,≠,05? In order to calculate and subdivide the address of the pixel position, a PC requires enormous computing power and memory capacity. Additionally, this procedure must be repeated for all three angles, and all this information must be stored, requiring enormous computational and memory power.

The present invention is a technique for searching and identifying all the pixel positions on the rotating reference body 52, which requires only the calculation of six variables for each angle theta, and which uses this information at the convenience of the CPU 10. Disclose techniques that will help you memorize things better.

Examining Figure 1, it will be appreciated that it is necessary to first calculate the corner position 56 and establish the X and Yll marks within the CPU 10. The scanning of the reference area at angle theta is along scan line 58 at vixel positions 70, 72,
74, then 76, and then sequentially along line 58 to the 64th pixel location, which would be the end of the scan.

Sequential pixel positions 1 to 7 relative to the end point of scan line 58
Examining 0, 72, 74, and 76, it will be seen that there is an equal incremental change in the X direction, defined as delta HX.

Similarly, if we project the incremental vixel position onto the Y-axis, we will see that there is an equal incremental change on the Y-axis, defined as delta HY.

The selected term is the horizontal movement V of the new pixel position going from 56 through 70.72.
It is intended to indicate an incremental change in the X direction or from C to Y direction occurring from C.

In other words, deltaHX-deltaHX" constant 0, while delta HY"' frutaHy=delta HY=constant 2.

Therefore, in order to scan the angle theta line 58, it is only necessary to calculate the X, Y position of the corner position 56 and then add delta Hx and delta HY to obtain the coordinate position # of the pixel 70. It turns out.

Then, the coordinate position of the pixel 72 is the coordinate position 70,
V is obtained by adding delta HX1 delta HY. This process continues for each pixel location along scan line 58.

To obtain position information for each pixel on scan line 58, the X coordinate, Y coordinate, and delta HX of position 56 are
= Only need to calculate delta HY.

Now, explaining Fig. J, the same reference area 52 is shown here.
It is shown. Also described herein are first scan line 58, as well as scan lines 80, 82 and 84, which continue during the first scan within the reference area.

Scan m80 starts from position 56 at angle theta V
♂ Kuseru starts away. Similarly, scan line 82 begins a nopik width away from location 56 at angle theta. −
Force scan line 84 begins at a point 3 pixels away from location 56 at angle theta e. The position of each scan line up to the total Otohiro scan line is at the same angle theta [,
Starting from position 56, the same arrangement is made.

Scan line 80 is intersected at position 90, and -force scan line 82 is scanned at position 92! 84 begins at position 94. The X or horizontal incremental positions from positions 56 to 90, 90 to 92, and 92 to 94 are equal to each other for a given angle theta and are expressed as delta.

This term arose by vertically moving the scan line,
It shows movement in the X direction.

Similarly, between positions 56 and 90, position 1i290. ! =92j
ll.

The vertical increments between positions 92 and 94 are then all equal to each other and are denoted by delta VY. This term refers to the incremental change in the Y direction caused by vertically moving the scan line. When examining the graph, delta vX = delta■
x = delta vx = constant 3, while delta vY = delta v
Y=delta■Y constant number.

It will be understood that

Examining diagram No. 56, we can calculate the initial X and Y positions of point 56, and for each angle theta, we calculate the te
It will be appreciated that any of the ≠, 09B pixel locations can be addressed by simply calculating l delta Y1 delta ■X1 and HH delta VY. In other words, 6 of the information for each angle theta
By simply calculating each of the three, it becomes possible to address all positions.

The general equation for finding any pixel location in Cartesian coordinates is:

YN + / = Y + delta HYxN + / = YN
+TeltaHx To get a search/4' turn from 7 pixel locations to the other pixel location, add its horizontal increment to the direction, add its vertical increment to the direction, and get the new address. Just need it. This process continues by adding the same increments both parallel and perpendicular until all desired positions on the scan line are achieved.

Repeat this procedure for each of the four successive scan lines, adding a new horizontal and vertical increment to establish a new scan line, and then repeating the process of adding each horizontal and vertical increment on the new scan line. Repeat for each new pixel position. Thus, only 6 variables are required for each angle, which means that for an angle V of 3 θ0 only a minimum amount of memory is required. do. Another immediately obvious benefit is that
Because the procedure is done in hardware and requires only adders, point-to-point results can be obtained in real time in a manner that does not require multiplication or trigonometric functions. Although it is a less obvious advantage, it is possible to rotate the reference body and simultaneously read the information from memory and convolve this information with the video data to obtain a cumulative number representing a good match. Since the information is addressed immediately when read from the reference memory, no time is required to store all rotating references.

Please refer now to Figure 1, which shows the implementation of the angle rotor and the CPU at the selected angle, 4L
A block diagram is shown for explaining how to form X and Ym marks for each of the , 0, 6, and 7 pixel positions.

Third. ≠ As mentioned in relation to the figure and the figure on the left, CP
It is only necessary to store six variables in U.

The CPU 90 includes a look-up table, which calculates the initial X and Y coordinates of the starting position for each of the 360° positions by delta HX1, delta Vx, delta VY1, delta HY increment. It includes six variables defined as positions.

The positions of the X address and Y address for each pixel position are the th ≠,! The diagram will be explained.

The initial X and Y coordinates for position 56 are stored in the cPU's memory for each angular position. x
The m mark is provided to an X-ray start position memory 92 which leads to an X output position memory 94.

Similarly, the Y coordinate for the initial starting position 56 is provided to a Y line starting position memory 98 which leads to a Y output position memory 96.

The vertical increment delta It is fed to a summing network 102 which also receives the output of the xi starting position memory 92. addition 102
The output is also provided to the X# start position memory 92 to constantly update the X position. This output is also supplied to the X output position memory 94.

The horizontal incremental delta
104 and in turn to summing circuitry 106 which also receives an input signal from the output of X output position memory 94. The output of the adder 106 is stored in the X output position memory 9
4 is constantly updated to provide updated continuous X coordinate output information of the pixel address.

The output of the Y coordinate is obtained in the same way, and the vertical increment delta Y signal is memorized from the CPU 90! l-108, followed by
and to summing circuitry 110.

This circuitry also receives updated information from the output of YM start position memory 98. The output of adder 110 is always Y
41 start position information memory 98 is constantly supplied to this memory so as to update the output information.

Note the horizontal incremental delta Y signal from the CPU90! J-1
12. This memory 112 includes an adder 114 which also receives input information from the output of the Y output position memory 96.
Supply a signal to. The output of adder 114 is also provided to a Y output location memory 96, which output also provides the Y coordinate of the address of the pixel in question.

In operation, the CPU loads the X coordinate into the X-ray start memory 92. This memory 92 also signals an X output position memory 94. The output of memory 94 represents the X address of initial starting position 56.

Similarly, the initial Y starting coordinate is provided from CPLI 92 to Y line position memory 98. This memory 98 also supplies a signal to the Y output position memory 96.
The output of 6 is Y at,res with respect to the initial coordinate 56.

First, CPU 90 loads memory 100 with the vertical incremental delta-X signal. CPU 90 then loads the horizontal incremental delta-X signal into memory 104. Similarly, CPU 90 loads the vertical incremental memory delta Y signal into memory 108 and subsequently loads the horizontal incremental memory delta Y signal into memory 112e. This is added to the delta X signal and the initial X position of the memory 94 to obtain i? 458
A scan along the line up to the initial pixel point 70 is accomplished.

This updates the X coordinate of position 70 in memory 94. The X output of memory 94 now contains the new X address for pixel 70 based on scan line 58.

Horizontal notes as well! J-Y 112 provides the horizontal increment delta Y to adder 114 where the output of memory 96 is added to this increment and now the Y of pixel 70 on scan line 58 is
The initial Y position is updated by the delta X signal to represent the coordinates.

This process continues all along line 58 up to pixel locations 72, 74, and 76 and the 6th pixel. The output of memory 94 represents the X address, address and the output of memory 96 represents the Y address in each case.

1jFI of 611tth pixel search on scan line 58
After tjJ, vertical memory X100 provides a vertical increment delta-X signal (7' router Vx) to adder 102kc.

This adder 102 adds the X coordinate of the initial memory 92 and the delta
6 to update the X coordinate of position 90.

Memory 92 reads memory 94 and stores this memory 94.
contains the X-coordinate for the initial position 90 on the fixed spot 80.

Similarly, vertical memo v-ytos provides a vertical incremental delta Y signal (delta VY) to adder 110. This adder 110 calculates the initial Y at location 56 stored in memory 98.
The coordinates are updated and this updated Y coordinate signal is stored in the memory 9.
Supply to 6. The output of memory 96 is now scan line 8.
Contains the Y coordinate of position 90 included in 0-hi.

This process of scanning all 64 pixel locations on scan line 80 is accomplished by memory 104 providing horizontal incremental delta
06 is included in memory 94, position 9 on scan line 80
Continued by updating the X fr' information from 0 to the next pixel position 0 Similarly, note! I-112 provides a horizontal incremental delta Y signal to adder 104, causing position 1690 to
Y'l? 1 report is updated, and this adder 104 is
The Y information in memory is updated for the next pixel location on scan line 80. The output of memory 96 now contains the Y address for the next vixel location.

The X and Y address output of memory 94,96 continues in real time, and there is no need for this output to be stored, but rather for the video data contained in memory 20 of daytimer 2, it is stored in memory 16. Those skilled in the art will appreciate that it is necessary to convolve the reference data in real time.

The system described in connection with FIG. 4 is a simple d-section of the preferred embodiment. It will be apparent to those skilled in the art that since there are many ways to read information at a given angle, and new ROMs and FROMs are available, it may be convenient to implement the logic in other ways than that described with respect to FIG. Be recognized instantly.

Referring now to FIG. 7, there is shown a preferred embodiment utilizing at least the turn recognition device of the present invention in a multi-solex operation that improves reliability and speed over single/unit operation. It is shown.

Pattern recognition devices are widely applicable to automating automated manufacturing processes for semiconductors and the like. Semiconductor parts per month t, tooθ
It can be seen that for production of more than 10,000 units, a very large capacity increase of ≠ θ0 million units per month is required with a mere 70% increase. It is clear that in order to maximize the production rate of manufactured units, speed of inspection, reduction of fraud and indiscretion, and high reliability are of paramount importance.

The pattern recognition device works in conjunction with other devices such as a Waigi-bonder. The wire bonder interconnects contact points called pads on an IC with fingers that couple electrical signals to external circuitry. The wire bonder must be operated squarely so that it interconnects with the nozorad.

The z4' turn 1 knowledge device automatically searches for the reference body and supplies position information to the wire bonder. The wire bonder then performs the necessary bonding and processing operations.

Prior to the present invention, known pattern recognition devices required a minimum of iso milliseconds for each search until a portion was verified. Furthermore, regarding the angle information, 1 on the same chip,
In order to be able to perform a logical operation to identify the 2fi-th region, determine the angle between the two identified regions, and provide this angle information to the wire bonder,
An additional step with a microgrocer is required. This additional step also. , izo microseconds plus the mechanical time required to physically move Ic to a new position for the inspection process. The time for the first search, the time for the second search, and the time for the movement operation are such that I
The production of C reduces t'.

When the wire bonder is performing the bonding operation, the gloss turn recognition device is in the stand pie waiting position, and when the wire bonder completes its operation, the turn recognition device places the next chip in the position for confirmation. I'm looking forward to moving it.

A pattern recognition device constructed according to the principles of the present invention includes:
Now that we have the features of the threshold device, the angle rotator, the average time of the search is about j0 milliseconds. As mentioned earlier, the angle rotator provides angular information as a result of the single/position search, while the threshold idea stops the R search in areas where there is little chance of finding a match, and By terminating the rough search when a good match is found, the search time of the pattern recognizer is reduced.

The time savings of the present medaturn recognition device based solely on the rotor is an average inspection time savings of 300+ milliseconds to 10 milliseconds, which represents a huge increase in production output, but the 7th
Prior to the advent of the illustrated multiplex technology, there was no practical way to reduce the latency of turn recognizers during bonding operations or operations that move each IC from location to location.

A typical manufacturing operation combines seven wire bonders and seven pattern recognition devices. The individual chips are typically mounted on a lead frame, and each of the multiple chips mounted on the lead frame is brought within the field of view of a vidicon camera. The information examined by the camera is fed to a pattern recognition device under the control of the wire bonder. The P-turn recognizer then begins searching the scene examined against the scene in memory to determine a match. Then the matching place t
The wire tie is communicated to the wire tie by the setan recognition device. The wire tie performs the necessary manufacturing steps while the pattern recognition device waits for a signal from the wire bonder to indicate completion of the operation. When the wire bonder completes its operation, it then moves the lead frame to the next step of the line, evaluates the scene examined by the vidicon camera, and then repeats this process again. Sends a signal to the Tsuyaturn recognition device to return it.

The multiplex system of FIG. 7 has a common system timing circuitry 134.7 analog arbitration device u 136
The invention relates to the use of at least two individual pattern recognition devices that share a common pattern recognition system.

Because each wire bonder requires waiting time in its manufacturing process...! Experiments have shown that the 8m turn [130°132] can be operated with any of the g wire bonders.

The purpose of having two individual pattern recognition devices operating in parallel is to receive all the information from the wire bonders and from the multiple camera signal generators 138 that feed the signals to the analog arbitrator 136. It is in.

A number of controller command signals 140 originate from g wire bonders, which control the operation of both pattern recognition devices 130,132.

In general, the command signals include words, searches, and these command signals control the operation of the selected turn recognition device.

The seven timing systems 134 ensure that both turn recognizers 130, 132 are synchronized, see the same tone at the same time, and record the same information at the same time. As a result, the commands 1 to f of the large number of controller command inputs 140 can select which pattern (RJ recognition device) to operate without delay or waiting time.

Based on the concept of using two 1,000-turn edict devices in parallel for all g wire bonders, whether each /F turn recognition device 130, 132 is operated is constantly monitored one by one. It became possible. These include the pattern recognition device 130 having a CPU 142 and the turn recognition device 132 having a CPU 142.
This is achieved by starting to send the system timer) and russ, which is commonly referred to as a watchdog timer.

This watchdog timer has a large number of each ξ turn recognition device? +2: Operates in response to a command from the device command input 140,
It serves as a means for making the system timer 134 decide whether it is useful. If either CPU 140 or 144 ceases to send the necessary inputs or ruses to system timer 134 at a given time, the timing signal sent to that pattern recognition device terminates and the timing signal sent to that pattern recognition device ends. Confirmation! ! The 12th position leaves the scan m. This indicates that something went wrong or that the system is unable to receive the input signal. In such a case, the remaining pattern recognizers will perform their full duties until the problem is corrected and the necessary timing signals are again received from the CPU. The watchdog timer sets each CP over a period of time.
It can be thought of as a simple timer that is prepared again by an impulse from U. When the system timer does not receive or receive these impulses, it operates as if it were an off-engine j'·f/g pattern derived from the scan line.

The wire bonder 134 determines which binder among the wire bonders the wire bonder is connected to.
l,ll f! To determine whether you have received a li.
Controls interfaces 146 and 148. Many'
It can be seen that all the power channels of the tlNjH command power 140 are fed in parallel to both interfaces 146, 148, and the purpose of the system timer 134 is to determine which interface is being tuned to which channel at any given time. Dew. This process is C
This continues until the watchdog timer is deactivated by PU 140 or 144 not sending the necessary pulses.

At this point, the system timer then controls the appropriate interface and switches control of the selected channel being fed to the IP turn recognizer that is no longer on the scan line and to the IP turn recognizer that is still working. Convert jobs. Through this procedure, the system timer constantly monitors the operation of both pattern recognition devices and
immediately responds to the watchdog timer, which has been rendered inoperable due to a malfunction, and sends the necessary /'e pulse.

During operation, a number of controller command inputs 140 interface 146, 148 to request any of the g binders.
to both the pattern recognition devices 130 and 132 via. If no command input signal is received, both units will normally be in a self-test mode for their respective CPUs, following operation of watchdog timers indicating that both turn recognizers are operational. A signal is sent to system timer 134. Interface 1
46.148 together communicate requests for information received from command personnel 140 to the relevant CPLj 142.144, and each of these responds to requests for that interface. The /th unit that responds to requests for command manpower is prioritized to handle command manpower,
has been done. Immediately upon receiving the mission from the interface, the CPLJ 142 or 144 then notifies this command input to the system timer 134 that received the mission.

u) True operation of the /4' turn recognizers 130, 132 is similar to that described in connection with FIG. 1, except that the shared system timer 134. And there is a clear difference in the analog arbiter 136.

Video processor 150 is shown for completeness. The video processor stores video information from multiple cameras 158 in a video memory 152 . The video processor is controlled by CPU 142. This CPU 142 also controls a reference memory 154 that stores reference storage information. A rotor 156, controlled by the CPU 42, reads the stored information in real time and a convolver 158.
The information in the reference memory 154 is scanned at the selected angle in order to send the information to the reference memory 154 at the selected angle. The convolver 15B uses the reference memory 1
54 and the information stored in the video memory 152 are convolved. The convolved count is accumulator 1
60 and supplied to the CPU 142. CPU1
42 performs a centroid operation to determine the best match at a particular angle.

The operation of pattern recognizer #132 is similar to that described above, and for completeness the operation of video processor #162 is similar to that described above.
including. This Video Zorocera Two-162 stores video information under the control of the CPU 144 as a video memo! J-164
supply to. The reference storage information is stored in the reference memo')-166, and the CPU 144 controls the rotor 168.

The rotor 168 scans the information of the reference memo')-166 and reads it out to the convolver 170 in real time.
70, information from the reference memory 166 and video memo 1;
The relevant information of 1-164 is convolved. The output of convolver 170 is provided to accumulator 172.

Accumulator 172 accumulates the total counts fed back to CPU 144, which performs the centroid operations to determine matching coordinates and calculations to determine specific angles.

The concept of having two pattern recognition devices capable of fully loading each of the g wire bonders;
Faster production speeds can be achieved by utilizing seven turn recognition devices that can operate all three wire bonders. The ability for each i4 turn recognizer to share the load evenly minimizes downtime5 and minimizes mission latency from the wire bonder. The concomitant increase in speed will result in an increase in the number of manufacturers never before contemplated by the prior art or in the industry.

[Brief explanation of drawings]

Fig. 1 is a block diagram showing important parts of the nozo turn recognition system borrowed according to the present invention, and Fig. 2a and Fig. 2b are graphs showing threshold determination and rotation angle according to conditions for rotation. Figure 3 is a diagram showing the reference data of the storage device and the action of reading out information along a scan line at an angle of . Figure 1 is a diagram showing how to create a fixed constant for each person's scan line, Figure 1 is a diagram showing how to create six constants and the angle rotator FIG. 7 is a block diagram illustrating the formation of addresses for scanning. FIG. 10...CPU, 12...System timer, 14
...Video recording, 16...Reference memory, 1
8...Rotor, 20...Video memory, 22...
・Convolver, 24...Accumulator, 26...
-Threshold level (control), 28...memory, 90...cpu. 92...Xg start position memory, 94...X output position memory, 96...Y output position memory, 98...Y line start position memo, Lee, 100...memory, 102...addition Circuit network, 104...Memo I
J-1106... Addition circuit network, 108... Memory, 110... Addition circuit network (adder), 112... Memo! j-1114...adder, 130
... Pattern recognition device, 132 ... Pattern recognition device, 134 ... System time circuitry, 136 ... Analog arbiter, 138 ... Diverse camera video input, 140 ... Diverse controller command input , 142...CPU
. 144...CPLI, 146...Intermediate surface, 148.
...Intermediate plane, 150...Video processor, 152...Video memory, 154...;h Quasi-memory, 156...Rotator, 158...Convolver, 160...Accumulator, 162 ...Video processor, 164...Video memory, 166...Reference memo'J-1168...Rotor, 1
70...W inclusion-VB, 172...accumulator. Fig 3 Fig, 2b 13728 Moore Park Beer Valley Road, California 93021, United States

Claims (1)

Claims: (1) A pattern recognition method for quickly determining position and orientation between a reference region and a search region, the method comprising: a timed digitized/sequence of video pulses representing the reference region; and recording timed digitized video pulses indicative of said reference region to a plurality of separate addressable memory locations, and generating a series of timed/sequential pulses indicative of the search region. L. recording a timed signal representing said search area in a plurality of separate addressable memory locations, each scan line read from said reference area stored in memory; electronically addressing at a given angle, convolving the stored nofrus in the search area with the stored reference nous, and determining each search position at a plurality of selected angles; obtaining a count indicative of the number of matches of 1; accumulating the counts for a plurality of different angles in separate addressable memories, each associated with a selected angular position; finding the largest cumulative count of the plurality of memory locations; A pattern recognition method Q (2) characterized by determining the address of the search area position with the largest i1 count, and by extension, the position coordinates, as a measure of the search position. Threshold level tw up. When the count cassette hold M is high < q,
The P-turn recognition method according to claim 1, wherein the convolution is stopped at a scanning line angle, and the X and Y coordinates of the search area are determined at that angle. (3) The pattern recognition method according to claim (2), wherein a threshold level is selected for the cumulative count obtained by convolving the stored reference body and the search area. (4) The nozo turn recognition method according to claim (2), which sequentially and selectively addresses various scanning line angles at a considerably large search angle when the threshold is lower than the threshold hold level. . (5) The pattern recognition method according to claim (4), which searches at a substantially large angle of zero. (6) Initially, at an initial large angle from a given starting position,
selectively attributing the scan line to a given scan rotation direction;
Next, the search is performed in the opposite direction from the given starting position at the large angle as described in claim (4).
and turn recognition methods. (7) For the angles used to determine the coordinates of the search area such as to establish the angular alignment of the search area, at a small search angle, selectively the scan line is ) Pattern recognition method described in section. (8) Claim No. 7 recording a cumulative count for each of a plurality of small angles including the maximum count.
) method for recognizing turns. (9) The cumulative count is mathematically evaluated to determine the final angle indicating the angular alignment of the search area [J No. (8)
7-turn edict method described in ). The turn recognition method according to claim (8), wherein each small angle is 2 degrees. Establish an increment threshold defined as the cumulative count with a value such that the remaining search cannot accumulate the desired high search count; and) at a value lower than the incremental threshold, stop the search and A pattern recognition method according to claim 1, characterized by a new position. (2) Continuously comparing the cumulative count to a desired maximum cumulative count to determine whether to continue or stop the search, and evaluating the position relative to position and angular position. A mother turn recognition method according to claim 1. A method for recognizing a mother turn according to claim 1, in which the cumulative count and the threshold value are continuously compared to determine whether to continue searching or to stop, and move to the next selected position. Patent to stop the search when the cumulative count at any given time is such that a complete search of the remaining search positions is not equal to the threshold value. A method for recognizing turns as set forth in claim α1. generating a series of video/F pulses representing the reference region and recording a timed series of pulses representing the reference region in a plurality of separate addressable memory locations; generates a series of timed digital pulses representing the search area described above.
electronically addressing each scan line read from said reference area recorded in memory at a given angle; convolving said recorded pulse with said recorded reference pulse in the search area to obtain a colorant indicating the number of matches for each search position at a number of selected angles, and counting for a plurality of different angles; , accumulate separate addressable memories associated with each selected angular position, evaluate the quality of the reference data, establish a threshold level for the cumulative count VC, and determine whether the count is less than the threshold value. Stop the convolution at the scanline angle when selectively addressing scan line angles in angles, accumulating counts for a plurality of different angles, and mathematically evaluating the accumulated counts to determine an angle indicative of angular alignment of the search area. Characteristic pattern recognition method. The turn recognition method according to claim 09, characterized in that the reference body position coordinates of the search area are determined based on the angular alignment position of the OQ search area. Qη A 1,000-turn recognition device for quickly determining the position and orientation between a reference area and a search area, with a means of generating a series of timed and digitized video pulses indicative of the reference area. A series of timed lines showing the reference area.
means for recording pulses in a plurality of discrete addressable memory locations; means for generating a timed series of digital pulses indicative of a search area; means for recording the noculus in a plurality of separate addressable memory locations; and means for electronically addressing at a given angle each scan line read from said reference area stored in memory. Means for convolving said stored pulse with said stored reference pulse in said search region to obtain a count ft indicating the number of matches for each search position at a plurality of selected angles. means for accumulating counts for different angles in separate addressable memories, each associated with a selected angular position; means for detecting a maximum cumulative count of a plurality of memory locations; A pattern recognition device characterized by comprising means for determining a region position address λ, and thus position coordinates, as a measure of a search position. (II Count rises to threshold value K<t
When it happened! = means for stopping the convolution at the scanning angle; and means for determining the X and Y coordinates of the search area at that angle. Turn recognition device. (2) Nozo turn recognition according to claim 1, which includes means for sequentially and selectively addressing various scan line angles with a considerably large search angle when lower than the rosewood level and the threshold level. Device. ) The pattern recognition device according to claim 0, wherein the large angle is substantially 0. eρ First, address the above scan line in a given scan rotation direction at an initial large angle from a given starting position it, and then search in the opposite direction from the above given starting position it at an equally large angle. Claim No. 11 (11) An i9 turn recognition device for performing search and best comparison with a reference area in real time, which provides timing adjustment for indicating the reference area. A series of digitized video footage of 4
means for recording a series of timed pulses indicative of the reference region in a plurality of separate addressable memory locations; a series of timed digital pulses indicative of the search region; means for generating timed pulses indicative of said search area, means for recording in a plurality of separate addressable memory locations a timed pulse fic indicating said search area read from said reference area stored in memory; means for electronically addressing each scan line at a given angle; in said search region, convolving said stored pulse with said stored reference pulse; means for accumulating counts for a plurality of different angles in separate addressable memories, each associated with a selected angular position; reference data; a means for evaluating the quality of the accumulated counts and setting a threshold level fm, a means for stopping the convolution at the scan line angle when the number becomes higher than the threshold value, and a means for means for determining the X and Y coordinates of the search area, selectively addressing the scan angle at a small search angle and for a plurality of different angles for the angles used to determine the X and Y coordinates of the search area; means for accumulating counts in separate addressable memories associated with each angular position; and means for mathematically evaluating the accumulated counts to determine an angle indicative of angular alignment of the search area. A pattern recognition device comprising: