Boundary analyzer

• US 6,714,679 B1
• Filed: 02/05/1999
• Issued: 03/30/2004
• Est. Priority Date: 02/05/1998
• Status: Expired due to Term

• Current Assignee: Cognex Corporation
• Original Assignee: Cognex Corporation
• Inventors: Scola, Joseph, Jacobson, Lowell
• Primary Examiner(s): Mehta, Bhavesh M.
• Assistant Examiner(s): DESIRE, GREGORY M
• Application Number:
  US09/245,163
• Time in Patent Office: 1,880 Days
• Field of Search: 382/151, 382/153, 382/199, 382/202, 382/203-205, 382/215, 382/241, 382/293, 382/103, 382/294, 345/443, 345/442
• US Class Current: 382/199
• CPC Class Codes: G06V 10/46 Descriptors for shape, contour or point-related descriptors, e.g. scale invariant feature transform [SIFT] or bags of words [BoW]; Salient regional features colour feature extraction G06V10/56
• CPC Class Codes: G06V 10/752 Contour matching

Abstract

A method and apparatus are disclosed for analyzing a boundary of an object. An embodiment for determining defects of a boundary to sub-pixel precision and an embodiment for fast correlation scoring are disclosed. The boundary is analyzed by matching a first boundary, such as a model of an ideal object boundary, to a second boundary, such as the boundary of an object being produced at a factory. The boundaries are represented as a set of indexed vertices, which are generated by parsing the boundaries into a set of segments. One embodiment refines the parse through merging segments and reassigning data points near the endpoints of the segments. The model produced is very accurate and is useful in other applications. To analyze the boundaries, the sets of indexed vertices are matched, and optionally the segmentation of the second boundary is refined to increase the extent of matching. The extent of matching yields a correlation score and/or the matching allows a characteristic class of the first set of segments to be associated with the second set of segments. The class and data points of the runtime segments are used to measure defects in the second set of segments, and thus in the boundary of the object.

Claims

1. A method for measuring deviations in an object boundary of an object within an image, the method comprising:

a. providing a first set of first segments, each first segment having indexed first vertices and a class, the first set representing a first boundary of the object;

b. segmenting a second set of second segments, each second segment having indexed second vertices, the second set representing the object boundary of the object;

c. substantially matching at least some of the second vertices to at least some of the first vertices so as to produce matched second segments, each matched second segment being associated with a class of a corresponding matched first segment; and

d. measuring deviations within the matched second segments using the class.

2. The method of claim 1, wherein the first segments are connected.

3. The method of claim 1, wherein first vertices are approximately end points of each of the first segments.

4. The method of claim 3, wherein the set of first segments include at least one line and at least one arc.

5. The method of claim 4, wherein each of the at least one arc has a radius of curvature.

6. The method of claim 1, wherein generating a first set of first segments includes:

acquiring a first boundary of a first object; and

parsing the first boundary into a set of indexed primitives.

7. The method of claim 1, wherein generating a first set of first segments includes:

applying steps b-d on multiple images of the object; and

choosing as the first boundary the second segments having smaller deviations.

8. The method of claim 1, wherein generating a first set of first segments includes:

merging neighboring first segments having similar statistics; and

refining first segments by reassigning at least one data point of a first segment among neighboring first segments.

9. The method of claim 1, wherein generating a second set of second segments includes:

determining an object boundary of the object; and

parsing the object boundary into second segments each having second vertices.

10. The method of claim 1, wherein the object boundary is determined to sub-pixel precision.

11. The method of claim 1, wherein matching substantially at least some of the second vertices to at least some of the first vertices includes:

matching one of the second vertices with one of the first vertices when the second vertex is indexed similarly to the first vertex.

12. The method of claim 1, wherein matching substantially at least some of the second vertices to at least some of the first vertices includes:

matching one of the second vertices with one of the first vertices when the second vertex is within a predetermined spatial tolerance of the first vertex.

13. The method of claim 1, wherein matching substantially at least some of the second vertices to at least some of the first vertices includes:

ignoring second vertices that are not within a predetermine spatial tolerance of one of the first vertices.

14. The method of claim 1, further comprising:

e. refining the segmentation of the object boundary of the object after matching so as to increase an amount of the matched second segments; and

f. repeating step c after refining.

15. The method of claim 14, wherein the second set of second segments includes the matched second segments and unmatched second segments, and the first vertices includes matched first vertices and unmatched first vertices, and wherein refining includes:

dividing the unmatched second segments to create additional second vertices positioned as close as possible to the unmatched first vertices so as to increase an amount of the matched second vertices.

16. The method of claim 15, wherein each of the additional second vertices is a point on the object boundary of the object as close as possible to one of the unmatched first vertices.

17. The method of claim 14, wherein refining includes:

combining unmatched second segments that neighbor one another so as to increase an amount of the matched second segments.

18. The method of claim 1, wherein the deviations have a sub-pixel magnitude in at least one dimension.

19. The method of claim 1, for automatically inspecting boundaries of multiple objects wherein the image contains more than one object.

20. The method of claim 1, further comprising:

rotationally aligning the object boundary with the first boundary before matching.

21. The method of claim 1, wherein measuring deviations include:

generating an ideal segment using the class and the second vertices; and

measuring any deviation of the second segment from the ideal segment.

22. The method of claim 1, wherein measuring deviations include:

generating an ideal segment using the class and the second segments; and

measuring any deviation of the second segment from the ideal segment.

23. The method of claim 22, wherein generating an ideal segment includes:

determining an equation of a line that best fits data of the second segment.

24. The method of claim 22, wherein generating an ideal segment includes:

determining an equation of an arc that best fits data of the second segment so as to produce a best-fit center and a best-fit radius;

determining radii from the best-fit center to at least two data points on the second segment;

subtracting the best-fit radius from each of the radii so as to produce a delta value over length of the second segment;

plotting the delta value over length of the second segment; and

measuring any deviation of the delta value from a straight line.

25. The method of claim 24, where measuring any deviation from an ideal segment includes:

rotating the delta value so as to somewhat align the delta value with an axis; and

measuring any deviation of the delta value from a straight line includes;

measuring any deviation from the axis.

26. An apparatus for measuring deviations in an object boundary of an object within an image, the apparatus comprising:

an index device adapted to generate a first set of first segments, each first segment having indexed first vertices and a class, the first set representing a first boundary of the object, and the index device also being adapted to generate a second set of second segments, each second segment having indexed second vertices, the second set representing the object boundary of the object;

a matching device, cooperative with the index device, adapted to substantially match at least some of the second vertices to at least some of the first vertices so as to produce matched second segments, each matched second segment associated with a class of matched first segments; and

an analyzer, cooperative with the matching device, adapted to measure deviations in at least some of the second segments having the matched second vertices using the class associated with the matched second vertices and the data points of the second segments.

27. The apparatus of claim 26, further comprising

a resegmenter, cooperative with the matching device, adapted to resegment unmatched second segments so as to increase an amount of the matched second segments.

28. A method for analyzing an object boundary of an object within an image, the method comprising:

a. generating a set of first segments each having indexed first vertices, the set representing a first boundary of the object;

b. generating a set of second segments each having indexed second vertices representing the object boundary of the object;

c. substantially matching at least some of the second vertices to at least some of the first vertices so as to produce matched second and first segments;

d. refining the segmentation of unmatched second segments to match with unmatched first segments so as to produce additional matched second and first segments; and

e. analyzing the object boundary of the object using the matched second and first segments.

29. The method of claim 28, wherein analyzing the object boundary of the object includes:

calculating a number of unmatched second segments so as to generate a score of similarity between the first boundary and the object boundary.

30. The method of claim 28, wherein each first segment has a class and wherein analyzing the object boundary of the object includes:

measuring deviations in at least some of the second segments having the matched second vertices using a class associated with the matched first segments.

31. An apparatus for measuring deviations in an object boundary of an object within an image, the apparatus comprising:

an index device adapted to generate a first set of first segments, each first segment having indexed first vertices, the first set representing a first boundary of the object, and adapted to generate a second set of second segments, each second segment having indexed second vertices, the second set representing the object boundary of the object;

a matching device, cooperative with the indexing device, adapted to substantially match at least some of the second vertices to at least some of the first vertices so as to produce matched second and first segments;

a resegmenter, cooperative with the matching device, adapted to resegment unmatched second segments to match with unmatched first segments so as to produce additional matched second and first segments; and

an analyzer, cooperative with the resegmenter, adapted to analyze the object boundary of the object using the matched second and first segments.

32. The apparatus of claim 31, wherein each first segment has a class and the analyzer further includes:

a measuring device adapted to measure deviations in at least some of the second segments having the matched second vertices using a class associated with the matched first segments and data points of the runtime segments.

33. The apparatus of claim 31, wherein the analyzer further includes:

a scoring device for calculating a number of unmatched second segments so as to generate a score of similarity between the first boundary and the object boundary.

34. A method for measuring deviations in an object boundary of an object within an image, the method comprising:

providing a first set of first segments, each one of the first segments having indexed first vertices and a class, the first set representing a trained boundary of the object;

providing a second set of second segments, each one of the second segments having indexed second vertices, the second set representing the object boundary of the object in the image;

substantially matching at least some of the indexed second vertices with at least some of the indexed first vertices so as to produce matches for at least a portion of the second segments, each of the matches including at least two of the indexed first vertices, and each of the matches being associated with the class of the one of the first segments having the respective at least two of the indexed first vertices; and

measuring deviations within each of the at least a portion of the second segments of the matches using the respective class associated with each of the matches.

35. The method of claim 34, further comprising:

refining the second set of second segments before measuring the deviations so as to allow additional matches; and

substantially matching at least some of the indexed second vertices with at least some of the indexed first vertices after the refining so as to produce the additional matches for at least a portion of the second segments, each of the additional matches having at least two of the indexed first vertices, and each of the additional matches being associated with the class of the one of the first segments having the respective at least two of the indexed first vertices, and

wherein measuring the deviations further includes;

measuring the deviations within each of the at least a portion of the second segments of the matches and within each of the at least a portion of the second segments of the additional matches.

36. The method of claim 35, wherein the second set of second segments includes the at least a portion of the second segments in the matches and unmatched second segments, and the indexed first vertices includes matched first vertices and unmatched first vertices, and wherein refining further includes:

dividing at least a portion of the unmatched second segments to create additional second vertices positioned on the object boundary as close as possible to the unmatched first vertices.

37. The method of claim 35, wherein the second set of second segments includes the at least a portion of the second segments in the matches and unmatched second segments, and wherein refining includes:

combining any of the unmatched second segments that neighbor one another.

38. The method of claim 34, wherein the set of first segments include at least one line and at least one arc.

39. The method of claim 34, wherein providing the first set of first segments further includes:

merging neighboring first segments within the set of first segments having similar statistics.

40. The method of claim 34, wherein the first segments have data points and wherein providing the first set of first segments further includes:

refining the data points within at least one of the first segments by reassigning at least one of the data points of the at least one of the first segments to a neighboring one of the first segments.

41. The method of claim 34, wherein substantially matching the at least some of the indexed second vertices with the at least some of the indexed first vertices includes:

matching an indexed second vertex with an indexed first vertex when the indexed second vertex is within a predetermined spatial tolerance of the indexed first vertex.

42. The method of claim 34, wherein providing the second set of second segments further includes:

providing a fourth set of unrefined segments, each one of the unrefined segments having indexed unrefined vertices, the unrefined set representing the object boundary of the object in the image;

substantially matching at least some of the indexed unrefined vertices with at least some of the indexed first vertices, any potential matches for a portion of the unrefined segments having at least two of the indexed first vertices; and

combining at least a portion of the unrefined segments that neighbor one another and that are not in the any potential matches so as to produce combined segments and so as to provide the second set of second segments, where the second segments include the portion of the unrefined segments in the any of the potential matches and the combined segments.

43. The method of claim 34, wherein providing the second set of second segments further includes:

providing a third set of unrefined segments, each one of the unrefined segments having indexed unrefined vertices, the unrefined set representing the object boundary of the object in the image;

substantially matching at least some of the indexed unrefined vertices with at least some of the indexed first vertices, any potential matches for a portion of unrefined segments having at least two of the indexed first vertices; and

creating additional indexed vertices within at least a portion of the unrefined segments that are not in the any potential matches, the additional indexed vertices positioned on the object boundary as close as possible to one of the indexed first vertices, so as to provide the second set of second segments, where the indexed second vertices include the indexed unrefined vertices and the additional indexed vertices, and where the second segments are defined thereby.

44. The method of claim 34, further comprising:

rotationally aligning the object boundary with the trained boundary before matching.

45. The method of claim 34, wherein measuring the deviations further includes:

generating an ideal segment between the indexed second vertices, using the respective class, for each of the at least a portion of the second segments of the matches; and

measuring any deviation of each of the at least a portion of the second segments from the respective ideal segment.