Fast high-accuracy multi-dimensional pattern inspection

• US 6,836,567 B1
• Filed: 11/10/2003
• Issued: 12/28/2004
• Est. Priority Date: 11/26/1997
• Status: Expired due to Term

• Current Assignee: Cognex Corporation
• Original Assignee: Cognex Corporation
• Inventors: Walleck, Aaron, Silver, William, Wagman, Adam
• Primary Examiner(s): Miriam, Daniel
• Application Number:
  US10/705,495
• Time in Patent Office: 414 Days
• Field of Search: 382/103, 382/151, 382/159, 382/181, 382/190, 382/197, 382/199, 382/203, 382/209, 382/216, 382/218, 382/219, 382/291, 348/135, 348/139
• US Class Current: 382/209
• CPC Class Codes: G06T 7/75 involving models
• CPC Class Codes: G06V 10/24 Aligning, centring, orientation detection or correction of the image
• CPC Class Codes: G06V 10/7515 Shifting the patterns to accommodate for positional errors

Abstract

A method and apparatus are provided for identifying differences between a stored pattern and a matching image subset, where variations in pattern position, orientation, and size do not give rise to false differences. The invention is also a system for analyzing an object image with respect to a model pattern so as to detect flaws in the object image. The system includes extracting pattern features from the model pattern; generating a vector-valued function using the pattern features to provide a pattern field; extracting image features from the object image; evaluating each image feature, using the pattern field and an n-dimensional transformation that associates image features with pattern features, so as to determine at least one associated feature characteristic; and using at least one feature characteristic to identify at least one flaw in the object image. The invention can find at least two distinct kinds of flaws; missing features, and extra features. The invention provides pattern inspection that is faster and more accurate than any known prior art method by using a stored pattern that represents an ideal example of the object to be found and inspected, and that can be translated, rotated, and scaled to arbitrary precision much faster than digital image re-sampling, and without pixel grid quantization errors. Furthermore, since the invention does not use digital image re-sampling, there are no pixel quantization errors to cause false differences between the pattern and image that can limit inspection performance.

Claims

1. In a geometric pattern matching apparatus for refining a starting pose of an object in a run-time image, the object having an expected shape and a true pose in the run-time image, the starting pose representing an initial estimate of the true pose of the object in the run-time image, the geometric pattern matching apparatus having (1) a stored model pattern, the stored model pattern including a geometric description of the expected shape of the object, the geometric description including a plurality of pattern boundary points, and a field of force vectors, the field being a vector-valued function of position that relates force vectors to pattern boundary points, (2) a feature detector configured to detect in the run-time image a plurality of image boundary points, and (3) a sequential pose refinement module having an evaluate module, the evaluate module comprising:

a field strength evaluator configured to receive a force magnitude component of a force vector corresponding to an image boundary point, and an error signal, and configured to provide a confidence factor.

2. The evaluate module of claim 1, further including:

a weight selector configured to receive the confidence factor and a first control code, and configured to provide a weight value if the first control code indicates that the image boundary point is to be used for pose refinement, and to provide a zero value if the first control code indicates that the image boundary point is not to be used for pose refinement.

3. The evaluate module of claim 1, further including:

an eval selector configured to receive the confidence factor and a first control code, and configured to provide an eval value if the first control code indicates that the image boundary point corresponds to a portion of the stored model pattern, and to provide a zero value if the first control code indicates that the image boundary point does not correspond to any portion of the stored model pattern.

4. The evaluate module of claim 1, wherein the confidence factor falls within the range 0 to 1.

5. The evaluate module of claim 1, further including:

a field direction evaluator configured to receive a force direction component of a force vector and a direction (field), and to provide a force direction confidence factor; and

a combiner configured to combine at least the field strength confidence factor, and the force direction confidence factor, so as to provide an overall confidence score.

6. The evaluate module of claim 5, further including a magnitude evaluator configured to receive the gradient magnitude of an image boundary point, and to provide a magnitude confidence factor.

7. The evaluate module of claim 6, wherein the magnitude evaluator includes:

a magnitude threshold; and

a greater-than module that provides the magnitude confidence factor.

8. The evaluate module of claim 7, wherein the magnitude threshold is a fuzzy threshold, and the greater-than module is a fuzzy greater-than module.

9. The evaluate module of claim 5, wherein the field direction evaluator includes:

a subtractor configured to receive an image boundary point direction and a pattern boundary gradient direction based on at least some of the plurality of pattern boundary points, and for providing a direction comparison angle;

an angle limiter configured to receive the direction comparison angle and a second control code, and for providing the direction comparison angle unmodified if the second control code indicates that gradient polarity is to be considered, and limits the direction comparison angle if the second control code indicates that gradient polarity is not to be considered;

an absolute value module configured to receive the direction comparison angle, and to provide a magnitude of the direction comparison angle;

a threshold selector configured to receive a third control code, and to provide a field direction threshold if the third control code indicates “

no corner”

, else to provide a field corner threshold; and

a less-than module configured to receive both the threshold from the threshold selector and the absolute value, and for providing the force direction confidence factor.

10. The evaluate module of claim 9, wherein the less-than module is a fuzzy less-than module, and the field direction threshold and the field corner threshold are both fuzzy thresholds.

11. The evaluate module of claim 5, wherein the field strength evaluator includes:

an absolute value module configured to receive a force magnitude component of a force vector corresponding to an image boundary point, and for providing a length of the force magnitude component;

a less-than module configured to receive both the length of the force magnitude component and a field strength threshold, and for providing the force direction confidence factor.

12. The evaluate module of claim 11, wherein the less-than module is a fuzzy less-than module, and the field strength threshold is a fuzzy threshold.

13. The evaluate module of claim 11, wherein the field strength threshold is provided by an adder that receives an error signal, and adds the error signal to a field strength margin.

14. The evaluate module of claim 13, wherein the error signal is from a previous pose refinement step, and the field strength threshold changes after each pose refinement step.

15. The evaluate module of claim 1, further including:

a field direction evaluator configured to receive a force direction component of a force vector and a direction (field), and to provide a force direction confidence factor;

a fuzzy not element configured to receive the force direction confidence factor and provide an inverted force direction confidence factor;

a magnitude evaluator configured to receive the gradient magnitude of an image boundary point, and to provide a magnitude confidence factor; and

a combiner adapted to combine the inverted force direction confidence factor and the magnitude confidence factor, so as to provide an overall clutter confidence score.

17. The evaluate module of claim 15, wherein the magnitude evaluator includes:

a magnitude threshold; and

a greater-than module that receives the gradient magnitude of an image boundary point and the magnitude threshold, and provides the magnitude confidence factor.

18. The evaluate module of claim 17, wherein the magnitude threshold is a fuzzy threshold, the magnitude threshold is a fuzzy magnitude threshold, and the greater-than module is a fuzzy greater-than module.

19. The evaluate module of claim 1, further including:

a field direction evaluator configured to receive a force direction component of a force vector and a direction (field), and to provide a force direction confidence factor;

a ‘

not’

element configured to receive the force direction confidence factor and provide an inversion of the force direction confidence factor; and

a clutter selector configured to receive the inversion of the force direction confidence factor and a first control code, and adapted to provide a clutter value if the first control code does not indicate “

don'"'"'t care”

, and to provide a zero value otherwise.

20. The evaluate module of claim 19, further including:

a magnitude evaluator configured to receive the gradient magnitude of an image boundary point, and to provide a magnitude confidence factor; and

a combiner configured to combine the inverted force direction confidence factor and the magnitude confidence factor, so as to provide an overall clutter confidence score to be received by the clutter selector.

21. The evaluate module of claim 20, wherein the magnitude evaluator includes:

a magnitude threshold; and

a greater-than module that receives the gradient magnitude of an image boundary point and the magnitude threshold, and provides the magnitude confidence factor.

22. The evaluate module of claim 19, wherein the field direction evaluator includes:

a subtractor configured to receive an image boundary point direction and a pattern boundary gradient direction based on at least some of the plurality of pattern boundary points, and for providing a direction comparison angle;

an angle limiter configured receive the direction comparison angle and a second control code, and for providing the direction comparison angle unmodified if the second control code indicates that gradient polarity is to be considered, and limits the direction comparison angle if the second control code indicates that gradient polarity is not to be considered;

an absolute value module configured to receive the direction comparison angle, and to provide a magnitude of the direction comparison angle;

a threshold selector configured to receive a third control code, and to provide a field direction threshold if the third control code indicates “

no corner”

, else to provide a field corner threshold; and

a less-than module configured to receive both the threshold from the threshold selector and the absolute value, and for providing the force direction confidence factor.

23. The evaluate module of claim 22, wherein the less-than module is a fuzzy less-than module, the ‘

not’

element is a fuzzy ‘

not’

element, and the field direction threshold and the field corner threshold are both fuzzy thresholds.

16. The evaluate module of 15, further including:

a clutter selector configured to receive the overall clutter confidence score and a first control code, and configured to provide a clutter value if the first control code does not indicate “

don'"'"'t care”

, and to provide a zero value otherwise.