Pattern recognition apparatus and method

• US 4,853,968 A
• Filed: 09/21/1987
• Issued: 08/01/1989
• 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): Boudreau, Leo H.
• Assistant Examiner(s): Mancuso, Joseph
• Application Number:
  US07/099,398
• Time in Patent Office: 680 Days
• Field of Search: 382/8, 382/45, 382/42, 382/48, 382/14, 382/15, 382/18, 382/30, 382/33, 382/34, 358/101, 358/106, 358/107, 358/137, 358/140, 364/559, 340/731
• US Class Current: 382/151
• 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. Method of operating a vision system of the type employing a camera means for providing an image of at least a portion of an object viewed by the camera means, the image comprising a plurality of adjacent pixels, comprising the steps of:

(a) viewing at least a portion of the object with the camera means and generating a target signature form the image;

(b) comparing at least a portion of the target signature to a plurality of sub pixel signatures, each sub pixel signature corresponding to a unique sub pixel position between pixel positions;

(c) determining which sub pixel signature most closely matches the target signature based upon the result of the comparison; and

(d) providing an indication of position of the object based upon the sub pixel signature determined to most closely match the target signature.

2. Method of according to claim 1 wherein the pixels are arranged in a matrix, each pixel being represented by an output signal having a magnitude indicative of a surface condition of a corresponding portion of the object, the target signature and sub pixel signatures each comprising a series of sums, each sum in the target signature being obtained by totaling magnitudes corresponding to columns of pixels.

3. Method according to claim 2 wherein the sub pixel signatures are generated by linearly ramping at least a portion of a reference signature obtained from viewing a reference object with the camera means.

4. Method according to claim 2 wherein the sub pixel signatures are generated by application of a formula of the following type to the sums comprising the reference signature:

space="preserve" listing-type="equation">[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.

5. Method according to claim 1 wherein the sub pixel signatures are generated in response to viewing a reference object with a camera means.

6. Method according to claim 1 wherein the sub pixel signatures are generated when the vision system is in a teach mode of operation.

7. Method according to claim 1 wherein the target signature is generated in response to viewing a target object with the camera means.

8. Method according to claim 1 wherein the target signature is generated when the vision system is in a run mode of operation.

9. Method according to claim 1 wherein the target signature that is compared to the sub pixel signatures is a target sub signature, the target sub signature being a selected portion of a larger target signature that is obtained when a target object is viewed by the camera means.

10. Method according to claim 9 wherein the sub pixel signatures that are compared with the sub target signature are sub pixel sub signatures, each sub pixel sub signature being obtained by linearly ramping a selected portion of a reference signature obtained when a reference object is viewed by the camera means.

11. Method according to claim 1 wherein the position of the object that is provided is relative to the position of a reference object that has been viewed by the camera means.

12. Method according to claim 11 wherein a reference signature is generated from the reference object and the sub pixel signatures are generated from the reference signature.

13. Method according to claim 12 wherein the relative position of a target object is provided.

14. Method according to claim 1 wherein four sub pixel signatures are generated and correspond to +20%, +40%, -20%, and -40% displacement relative to integer pixel boundaries.

15. Method according to claim 1 wherein position of the object is determined to within 1/5 of a pixel distance.

16. Method according to claim 1 further comprising the step of altering the position of a work table based upon the provided indication of position of the object.

17. Method of operating a vision system of the type employing a camera for providing an image comprising a plurality of adjacent pixels arranged in a matrix, each pixel being represented by an output signal having a magnitude indicative of a surface condition of a corresponding portion of an object viewed by the camera, and means receiving the output signals for providing a digital image of at least a portion of the object comprising the steps of:

(a) viewing at least a portion of a target object with the camera and generating a target signature from the image, the signature comprising a series of sums, each sum in the series being obtained by totaling digital image data corresponding to columns of pixels;

(b) selecting a particular portion of the target signature, and defining the selected portion as a target sub signature;

(c) comparing the target sub signature to a plurality of sub pixel sub signatures, each sub pixel sub signature corresponding to a unique sub pixel position and being obtained mathematically from a reference sub signature, the reference sub signature being obtained from a selected portion of a reference signature generated in response to viewing a reference object with a camera, the sub pixel sub signatures being obtained by linearly ramping the reference sub signature;

(d) determining with sub pixel sub signature most closely matches the target sub signature;

(e) providing an indication of the position of the target object relative to the reference object based upon the sub pixel sub signature determined to most closely match the target sub signature.

18. Method according to claim 17 wherein the sub pixel sub signatures are generated by application of a formula of the following type to the sums comprising the reference sub signature:

space="preserve" listing-type="equation">[V.sub.(N+1) 31 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 sub 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.

19. Method according to claim 17 wherein the vision system alters the position of a work table based upon the provided indication of position of the target object.

20. Method according to claim 17 wherein the reference signature is generated when the vision system is in a teach mode of operation.

21. Method according to claim 20 wherein the signature for the target object is generated when the vision system is in a run mode of operation.

22. Method according to claim 17 wherein four sub pixel sub signatures are generated and correspond to +20%, +40%, 20% and -40% displacement relative to integer pixel boundaries.

23. Method according to claim 17 wherein the position of the target object relative to the reference object is determined to within 1/5 of a pixel distance.

24. Method of operating a vision system of the type employing a camera for providing an image comprising a plurality of adjacent pixels arranged in a matrix, each pixel being represented by an output signal having a magnitude indicative of a surface condition of a corresponding portion of an object viewed by the camera, and means for digitizing the output signals and providing a digital image of at least a portion of the object, comprising the steps of:

(a) operating the vision system in a teach mode wherein the following steps are performed;

(i) viewing a reference object with the camera;

(ii) generating a reference signature from the digital image of the reference object, the reference signature comprising a series of sums, each sum being obtained by totaling digital image data corresponding to columns of pixels;

(iii) selecting a portion of the reference signature that corresponds to a unique portion of the image of the reference object and defining the selected portion as a reference sub signature; and

(iv) generating a plurality of sub pixel sub signatures from the reference sub signature, each sub pixel sub signature corresponding to a unique sub pixel position and being obtained by linearly ramping the reference sub signature; and

,

(b) operating the vision system in a run mode wherein the following steps are performed;

(i) viewing a target object with the camera;

(ii) generating a plurality of target sub signatures from the digital image of the target object, the target image comprising a series of sums, each sum being obtained by totaling digital image data corresponding to columns of pixels;

(iii) comparing the target sub signatures with the reference sub signature in a selected range of integer pixel positions to locate the particular integer pixel position providing the best match, the result defining a target sub signature and indicating the amount of displacement, in integer pixels, of the target object relative to the reference object.

(iv) comparing the target sub signature to the sub pixel sub signatures to determine the sub pixel sub signatures that most closely matches the target sub signature, the result indicating the amount of displacement, in a fraction of a pixel, of the target object relative to the reference object; and

(v) providing an indication of position of the target object relative to the reference object based upon the result of the determination of steps (iii) and (iv).

25. Method according to claim 24 further comprising the step of moving a work table according to the result of step (b) (v).

26. Method according to claim 24 wherein four sub pixel sub signatures are generated and correspond to +20%, +40%, -20% and -40% displacement relative to integer pixel boundaries.

27. Method according to claim 24 wherein the position of the target object relative to the reference object is determined to within 1/5 of a pixel.

28. Method according to claim 24 wherein the sub pixel signatures are generated by application of a formula of the following type to the sums comprising the reference sub signature:

space="preserve" listing-type="equation">[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 sub 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.

29. Vision system apparatus comprising:

(a) means for viewing at least a portion of an object with a camera means for providing an image of the object, the image comprising a plurality of adjacent pixels;

(b) means for generating a target signature from the image of the object;

(c) means for comparing at least a portion of the target signature to a plurality of sub pixel signatures, each sub pixel signature corresponding to a unique sub pixel position;

(d) means for determining which sub pixel signature most closely matches the target signature based upon the result of the comparison; and

(e) means for providing an indication of position of the target object based upon the sub pixel signature determined to most closely match the signature.

30. Apparatus according to claim 29 wherein the pixels are arranged in a matrix, each pixel being represented by an output signal having a magnitude indicative of a surface condition of a corresponding portion of the object, and wherein the means for generating a signature comprises means for generating a series of sums by totaling magnitudes corresponding to columns of pixels.

31. Apparatus according to claim 29 further comprising means for generating the sub pixel signatures from an image generated in response to viewing a reference object with the camera means.

32. Apparatus according to claim 31 wherein the means for generating the target signature is responsive to viewing a target object with the camera means.

33. Apparatus according to claim 31 wherein the means for generating the sub pixel signatures comprises means for linearly ramping at least a portion of a reference signature obtained from viewing the reference object.

34. Apparatus according to claim 29 further comprising means, responsive to the means for providing an indication of position, for altering the position of a work table on which the object is placed.

35. Vision system apparatus comprising:

(a) camera means for providing an image comprising a plurality of adjacent pixels arranged in a matrix, each pixel being represented by an output signal having a magnitude indicative of a surface condition of a corresponding portion of an object viewed by the camera means; and

(b) processing means operatively coupled to the camera means and receiving the output signals from the pixels, the processing means being operable in a teach mode, when a reference object has been viewed by the camera means, to;

(i) sum the magnitudes corresponding to columns of pixels in a predetermined manner to provide a series of sums defining a teach signature;

(ii) select a portion of the teach signature that is most unlike any other portion of the teach signature, the selected portion defining a teach sub signature;

(iii) linearly ramp the teach sub signature to provide a plurality of sub pixel sub signatures, each sub pixel sub signature corresponding to a sub pixel position;

the processing means further being operable in a run mode, when a target object has been viewed by the camera means to;

(iv) sum the magnitudes corresponding to columns of pixels in a predetermined manner to provide a series of sums defining a target signature;

(v) compare the target signature with the teach signature in a selected range of integer pixel positions to locate the particular integer pixel position providing the best match, the result defining a target sub signature and indicating the amount of displacement, in integer pixels, of the target object relative to the reference object;

(vi) compare the target sub signature to the sub pixel sub signatures to determine the sub pixel sub signature that most closely matches the target sub signature, the result indicating the amount of displacement, in fraction of a pixel, of the target object relative to the reference object; and

(vii) provide an indication of the result of the determination of steps (v) and (vi).

36. Apparatus according to 35 wherein the processing means is further operable in the run mode to move a work table according to the result of the determination.