Machine vision methods and systems for boundary feature comparison of patterns and images

• US 6,687,402 B1
• Filed: 10/23/2001
• Issued: 02/03/2004
• Est. Priority Date: 12/18/1998
• Status: Expired due to Term

• Current Assignee: Cognex Corporation
• Original Assignee: Cognex Corporation
• Inventors: Taycher, Leonid, Garakani, Arman
• Primary Examiner(s): Patel, Jayanti K.
• Assistant Examiner(s): AZARIAN, SEYED H
• Application Number:
  US10/000,761
• Time in Patent Office: 833 Days
• Field of Search: 382/199, 382/200, 382/201, 382/198, 382/145, 382/151, 382/152, 382/202, 382/203, 382/204, 382/141, 382/195, 382/144, 382/143, 382/172, 382/216, 382/224, 382/291, 382/305, 382/306, 382/286, 382/287, 235/462.01, 235/462.08, 235/456
• US Class Current: 382/199
• CPC Class Codes: G06T 2207/30148 Semiconductor; IC; Wafer
• CPC Class Codes: G06T 7/001 using an image reference approach
• CPC Class Codes: G06V 10/752 Contour matching

Abstract

The invention provides boundary-based machine vision methods and systems for comparing a pattern to an image. These contemplate the steps of finding points on a boundary in the image; identifying one or more boundary features, at least one of which is made up of multiple such points; determining point-by-point relationships, if any, between each point defining the boundary feature in the image and points on a boundary in the pattern; and determining a relationship between the boundary feature in the image and the pattern (e.g., whether the boundary feature in the image matches a corresponding feature in the pattern) as a function of the point-by-point relationships.

Claims

1. In a machine vision method for comparing a pattern and an image, the improvement comprising:

A. finding points on a boundary in the image,

B. identifying a boundary feature in the image, the boundary feature being defined by a plurality of the points on the boundary in the image,

C. determining one or more point-to-point relationships, if any, between each point defining the boundary feature and a corresponding point, if any, on a boundary in the pattern, and

C1. step (c) including assigning a numerical score that is a function of differences in any of location, angle or contrast of the point on the boundary feature in the image and the corresponding point, if any, on the boundary in the boundary in the pattern,

D. determining a relationship between the boundary feature in the image and the pattern as a function of the relationship determined in step (C),

D1. step (D) includes determining whether the boundary feature in the image is extra with respect to the pattern as a function of whether the numerical score determined in step (C1) falls below either a first threshold or a second threshold.

2. In a machine vision method according to claim 1, the further improvement wherein step (C) includes identifying as corresponding a point on the pattern that is within a designated distance of a point in the image.

3. In a machine vision method according to claim 2, the further improvement wherein step (D) includes determining whether the boundary feature in the image matches the pattern by counting a number of the points on the boundary feature in the image that match points on a boundary in the pattern.

4. In a machine vision method according to claim 1, the further improvement wherein step (C) includes determining whether each of the points on the boundary feature in the image either (i) matches a corresponding point on a boundary in the pattern, or (ii) is extra with respect to points on a boundary in the pattern.

5. In a machine vision method according to claim 4, the further improvement wherein step (D) includes determining whether the boundary feature in the image either matches or is extra with respect to the pattern based a count of a number of the points on the boundary feature in the image that either match or extra with respect to points on a boundary in the pattern.

6. In a machine vision method according to claim 1, the further improvement comprising the steps of:

E. identifying a boundary feature in the pattern, the boundary feature being defined by a plurality of the points in the pattern;

F. determining one or more point-to-point relationships, if any, between each point defining the boundary in the pattern and a corresponding point on the boundary in the image, and

G. determining a relationship between the boundary feature in the pattern and the boundary in the image as a function of the relationships determined in step (F).

7. In a machine vision method according to claim 6, the further improvement wherein step (F) includes determining whether a point on the boundary feature in the pattern is missing from the boundary in the image.

8. In a machine vision method according to claim 7, the further improvement wherein step (G) includes determining whether the boundary feature in the pattern is missing from the image based on a count of a number of the points on the boundary feature in the pattern that are missing from the boundary in the image.

9. In a machine vision method for comparing a pattern and an image, the improvement comprising:

A. finding points on a boundary in the image,

B. identifying a boundary feature in the image, the boundary feature being defined by a plurality of the points on the boundary in the image,

C. determining a quantitative point-to-point relationships, if any, between each point defining the boundary feature and a corresponding point, if any, on a boundary in the pattern, and

C1. step (C) includes assigning a numerical score that is a function of differences in any of the location, angle or contrast of the point on the boundary feature in the image and the corresponding point, if any, on the boundary in the boundary in the pattern,

D. determining a relationship between the boundary feature in the image and the patterns a function of the quantitative relationships determined in step (C),

D1. step (D) includes determining whether the boundary feature in the image is extra with respect to the pattern as a function of whether the score determined in step (C1) falls below either a first threshold or a second threshold.

10. In a machine vision method according to claim 9, the further improvement wherein step (C) comprises assigning a numerical score to each point on the boundary feature in the image as a function of a difference in any of a location, angle and contrast of that point and a corresponding point if any, on the boundary in the pattern.

11. In a machine vision method according to claim 10, the further improvement wherein step (D) comprises determining a relationship between the boundary feature in the image and the pattern as a statistical function of the numerical scores determined in step (C).

12. In a machine vision method according to claim 11, the further improvement wherein step (D) includes determining whether the boundary feature in the image matches the pattern based on whether the statistical function of the numerical scores determined in step (C) exceeds a first threshold.

13. In a machine vision method according to claim 9, the further improvement comprising the steps of:

E. identifying a boundary feature in the pattern, the boundary feature being defined by a plurality of the points on the boundary in the pattern,

F. determining a quantitative point-to-point relationship between each point defining the boundary feature in the pattern and a corresponding point, if any, on a boundary in the image, and

G. determining a relationship between the boundary feature in the pattern and the image as a function of the quantitative relationships determined in step (F).

14. In a machine vision method according to claim 13, further improvement wherein step (F) comprises assigning a numerical score to each point on the boundary feature in the pattern based on a difference in any of a location, angle and contrast of that point and a corresponding point, if any, on the boundary in the image.

15. In a machine vision method according to claim 14, the further improvement wherein step (G) includes determining whether the boundary feature in the image is missing with respect to to the pattern as a function of whether a statistical measure of the numerical score determined in step (F) falls below a threshold.

16. In a machine vision method for comparing a pattern and an image, the improvement comprising:

A. finding points on a boundary in the image,

B. identifying a boundary feature in the image, the boundary feature being defined by a plurality of the points on the boundary in the image,

C. determining one or more point-to-point relationships, if any, between each point defining the boundary feature and a corresponding point, if any, on a boundary in the pattern, and

C1. step (c) including assigning a numerical score that is a function of differences in any of location, angle or contrast of the point on the boundary feature in the image and the corresponding point, if any, on the boundary in the boundary in the pattern,

D. determining a relationship between the boundary feature in the image and the pattern as a function of the relationship determined in step (C),

D1. step (D) includes determining whether the boundary feature in the image is extra with respect to the pattern as a function of whether the score determined in step (C1) falls below either a first threshold or a second threshold.

17. In a machine vision system according to claim 16, the further improvement wherein step (C) includes identifying as corresponding a within a designated distance of a point in the image.

18. In a machine vision system according to claim 17, the further improvement wherein step (D) includes determining whether the boundary feature in the image matches the pattern as a function of a number of the points on the boundary feature in the image that match points on a boundary in the pattern.

19. In a machine vision system according to claim 16, the further improvement wherein step (C) includes determining whether each of the points on the boundary feature in the image any of (i) matches a corresponding point on a boundary in the pattern and (ii) is extra with respect to points on a boundary in the pattern.

20. In a machine vision system according to claim 19, the further improvement wherein step (D) includes determining whether the boundary feature in the image any of matches and is extra with respect to the pattern as a function of a number of the points on the boundary feature in the image that any of match and are extra with respect to points on a boundary in the pattern.

21. In a machine vision system according to claim 16, the further improvement comprising the steps of:

E. identifying a boundary feature in the pattern, the boundary feature being defined by a plurality of the points in the pattern;

F. determining one or more point-to-point relationships, if any, between each point defining the boundary in the pattern and a corresponding point, if any, on the boundary feature in the image, and

G. determining a relationship between the boundary feature in the pattern and the boundary in the image as a function of the relationships determined in step (F).

22. In a machine vision system according to claim 21, the further improvement wherein step (F) includes determining whether the points on the boundary feature in the pattern are missing from the boundary in the image.

23. In a machine vision system according to claim 22, the further improvement wherein step (G) includes determining whether the boundary feature in the pattern is missing from the image as a function of a number of the points on the boundary feature in the pattern that are missing from the boundary in the image.

24. In a machine vision method for comparing a pattern and an image, the improvement comprising:

A. finding points on a boundary in the image,

B. identifying a boundary feature in the image, the boundary feature being defined by a plurality of the points on the boundary in the image,

C. determining a quantitative point-to-point relationships, if any, between each point defining the boundary feature and a corresponding point, if any, on a boundary in the pattern, and

C1. step (C) includes assigning a numerical score that is a function of differences in any of the location, angle or contrast of the point on the boundary feature in the image and the corresponding point, if any, on the boundary in the boundary in the pattern,

D. determining a relationship between the boundary feature in the image and the patterns a function of the quantitative relationships determined in step (C),

D1. step (D) includes determining whether the boundary feature in the image is extra with respect to the pattern as a function of whether the score determined in step (C1) falls below either a first threshold or a second threshold.

25. In a machine vision system according to claim 24, the further improvement wherein step (C) comprises assigning a numerical score to each point on the boundary feature in the image as a function of a difference in any of a location, angle and contrast of that point and a corresponding point, if any, on the boundary in the pattern.

26. In a machine vision system according to claim 25, the further improvement wherein step (C) comprises assigning the numerical score as a fuzzy logic function of differences in the location, angle and contrast of the point on the boundary feature in the image and the corresponding point, if any, on the boundary in the boundary in the pattern.

27. In a machine vision system according to claim 25, the further improvement wherein step (D) comprises determining a relationship between the boundary feature in the image and the pattern as a statistical function of the quantitative relationships determined in step (C).

28. In a machine vision system according to claim 27, the further improvement wherein step (D) includes determining whether the boundary feature in the image matches the pattern as a function of whether a statistical measure of the quantitative relationships determined in step (C) exceeds a first threshold.

29. In a machine vision system according to claim 27, the further improvement wherein step (D) includes determining whether the boundary feature in the image is extra with respect to to the pattern as a function of whether a statistical measure of the quantitative relationships determined in step (C) falls below any of a first threshold and a second threshold.

30. In a machine vision system according to claim 24, the further improvement comprising the steps of:

E. identifying a boundary feature in the pattern, the boundary feature being defined by a plurality of the points on the boundary in pattern,

F. determining a quantitative point-to-point relationship between each point defining the boundary feature in the pattern and points on a boundary in the image, and

G. determining a relationship between the boundary feature in the pattern and the image as a function of the quantitative relationships determined in step (F).

31. In a machine vision system according to claim 30, the further improvement wherein step (F) comprises assigning a numerical score to each point on the boundary feature in the pattern as a function of a difference in any of a location, angle and contrast of that point and a corresponding point, if any, on the boundary in the image.

32. In a machine vision system according to claim 31, the further improvement wherein step (G) includes determining whether the boundary feature in the image is missing with respect to to the pattern as a function of whether a statistical measure of the quantitative relationships determined in step (F) falls below a threshold.