Pattern recognition apparatus and method

• US 5,119,435 A
• Filed: 02/23/1989
• Issued: 06/02/1992
• Est. Priority Date: 09/21/1987
• Status: Expired due to Term

• Current Assignee: Kulicke and Soffa Industries Incorporated
• Original Assignee: Kulicke and Soffa Industries Incorporated
• Inventors: Berkin, George M.
• Primary Examiner(s): Mancuso, Joseph
• Application Number:
  US07/314,403
• Time in Patent Office: 1,195 Days
• Field of Search: 382/8, 382/14, 382/15, 382/18, 382/42, 382/45, 382/18, 382/30, 382/33, 382/34, 358/101, 358/106, 358/107, 358/137, 358/140, 364/559, 364/728.03, 340/731
• US Class Current: 382/145
• CPC Class Codes: G06V 10/7515 Shifting the patterns to accommodate for positional errors

Abstract

A method of operating a pattern recognition apparatus comprises generating a plurality of sub pixel sub signatures from a reference signature, wherein the sub pixel sub signatures correspond to fractional pixel (sub pixel) positions. A target sub signature is compared to each of the sub pixel sub signatures to determine the relative placement of a target object to within a fraction of a pixel.

Claims

1. A method of generating sub-pixel signatures for use in a pattern recognition system (PRS), comprising the steps of:

storing individual pixel image information indicative of an object and its position as digital gray scale intensity values in the memory of said PRS,

generating a digital signature of said object comprising a linear series of sums of said gray scale intensity values indicative of the position of said object,

generating from said digital signature of said series of sums of said digital gray scale intensity values a plurality of digital sub-pixel signatures indicative of fractions of integral pixel positions between individual pixels, and

storing said plurality of sub-pixel signatures in said memory of said PRS so that a standard PRS is enhanced to provide sub-pixel positioning accuracy.

2. Method according to claim 1 wherein said step of generating a plurality of sub pixel signatures comprises the step of generating now sums of digital values of said digital sub pixel signatures with respect to adjacent sums of said gray scale values of said signature.

3. Method according to claim 2 wherein the step of generating new sums of digital values of said sub pixel signatures comprises the step of linear ramping with respect to adjacent sums of gray scale values of said signature to provide said plurality of said sub pixel signatures.

4. Method according to claim 1 wherein the step of generating a plurality of sub pixel signatures comprises the step of optically changing the position of said image and at least a portion of said signature to provide a plurality of sub pixel signatures.

5. A method of generating sub-pixel signatures for use in a pattern recognition system (PRS) comprising the steps of:

(a) generating a one dimensional signature comprising a series of sums of digital values of pixel intensity of an object in a PRS,

(b) storing the one dimensional signature which is representative of the single pixel accuracy of the position of an object relative to a plurality of pixels in a memory of a PRS,

(c) generating a plurality of new sums of digital values which lie between adjacent ones of said series of sums of digital values that are representative of sub-pixel accuracy of the position of an object relative to said plurality of pixels stored in the memory of said PRS,

(d) expanding the series of sums of digital values to include said new sums of digital values by,

(e) linear ramping at least a portion of said signature to provide at least one sub-pixel signature, whereby the sub-pixel signature corresponds the sub-pixel accuracy of the position between integer pixel positions of said object relative to said pixels stored in said memory, and

storing said sub-pixel signature in the memory of said PRS so that a standard PRS system is enhanced to provide sub-pixel positioning accuracy.

6. Method according to claim 5 further comprising the step of generating a plurality of sub pixel signatures unlike any other sub pixel signature defining sub pixel positions of said object.

7. Method according to claim 6 wherein the step of linearly ramping comprises the step of calculating one dimensional digital values for said sub pixel signatures.

8. Method according to claim 7 wherein the step of calculated values for sub pixel signatures further comprises calculating digital gray scale values for integer pixels to be summed.

9. Method according to claim 8 wherein the step of calculating values for sub pixel signatures comprises calculating fractional amounts of adjacent digital pixel values to provide displaced integer pixel values and then calculating sub pixel signature values.

10. Method according to claim 7 wherein the step of calculating values of sub pixel signatures values comprise the step of summing columns or rows of partial pixel values displaced from integer pixel values.

11. Method according to claim 6 wherein the step of generating a plurality of sub pixel signatures comprises the step of optically changing positions of at least a portion of the provided signature to provide a plurality of sub pixel signatures.

12. Method according to claim 5 wherein the step of linearly ramping at least a portion of the signature comprises linearly ramping a portion of the provided signature, the sub pixel signature being a sub pixel sub signature.

13. Method according to claim 12 wherein the step of calculating the sub pixel signatures are generated mathematically by application of a formula of the following type to sums comprising the provided signature:

space="preserve" listing-type="equation">SUM=[V.sub.(N+1) -V.sub.N ]×

F+V.sub.N

where;

N=the number of the column in the matrix;

V=the value of the sum in the reference signature corresponding to the column number specified; and

,

F=the result of 1 minus the decimal value of the sub pixel position for which it is desired to generate a sub pixel signature.

14. Method according to claim 5 wherein the step of linearly ramping comprises the step of optically changing the position of at least a portion of the provided signature to provide at least one sub pixel signature.