Locating shapes in two-dimensional space curves

• US 5,751,853 A
• Filed: 01/02/1996
• Issued: 05/12/1998
• Est. Priority Date: 01/02/1996
• Status: Expired due to Term

• Current Assignee: Cognex Corporation
• Original Assignee: Cognex Corporation
• Inventors: Michael, David
• Primary Examiner(s): Couso, Jose L.
• Application Number:
  US08/581,955
• Time in Patent Office: 861 Days
• Field of Search: 382/173, 382/177, 382/179, 382/199, 382/203
• US Class Current: 382/203
• 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 is provided for finding a feature of an object by finding at least one instance of a model two-dimensional space curve that represents the feature within a target two-dimensional space curve that represents at least a portion of the object. Unlike previous methods for finding a two-dimensional space curve within another two-dimensional space curve, the method of the invention is able to find any shape at any orientation or position in the two-dimensional space curve. The model and target two-dimensional space curves each include a plurality of points. Each point is characterized by a position in two dimensions, where the position is a function of distance S along the two-dimensional space curve. For each of the plurality of points of the two-dimensional space curve, the position in two dimensions as a function of distance S is converted into an angle as a function of distance S to provide an angle-based space curve. Then, at run-time, the angle-based model space curve is used to find at least one position along the angle-based target space curve that results in a match metric value that exceeds a match threshold. To provide invariance with respect to rotation, translation, and scaling, it is preferred to use normalized correlation as the match metric. The method of the invention can be used to find the notch or flat on the perimeter of a semiconductor wafer.

Claims

1. A method for finding a feature of an object by finding at least one instance of a model two-dimensional space curve that represents the feature within a target two-dimensional space curve in an image that represents at least a portion of the object, the method comprising the steps of:

at train-time;

acquiring said model two-dimensional space curve, said model two-dimensional space curve including a plurality of points, each point being characterized by a position in two dimensions, said position being a function of distance S along said model two-dimensional space curve;

for each of said plurality of points of said model two-dimensional space curve, converting said position in two dimensions as a function of distance S into an angle as a function of distance S to provide an angle-based model space curve; and

at run-time;

acquiring said target two-dimensional space curve, said target two-dimensional space curve including a plurality of points, each point being characterized by a position in two dimensions, said position being a function of distance S along said target two-dimensional space curve;

for each of said plurality of points of said target two-dimensional space curve, converting said position in two dimensions as a function of distance S into an angle as a function of distance S to provide an angle-based target space curve; and

using said angle-based model space curve to find at least one position along said angle-based target space curve that results in a match metric value that exceeds a match threshold.

2. The method of claim 1, further including the step of:

after the step of converting said model two-dimensional space curve into said angle-based model space curve, reducing the dynamic range of said angle-based model space curve.

3. The method of claim 1, further including the step of:

after the step of converting said target two-dimensional space curve into said angle-based target space curve, reducing the dynamic range of said angle-based target space curve.

4. The method of claim 1, wherein said match metric is normalized correlation.

5. The method of claim 1, wherein said match metric is sum of absolute differences.

6. The method of claim 1, wherein said match metric is correlation.

7. The method of claim 1, wherein said object is a semiconductor wafer, and said feature is a notch in the perimeter of said semiconductor wafer.

8. The method of claim 1, wherein the step of acquiring said model two-dimensional space curve includes the step of:

synthetically generating a model two-dimensional space curve.

9. The method of claim 1, wherein the step of acquiring said model two-dimensional space curve includes the step of:

statistically compiling a composite model two-dimensional space curve using an ensemble of exemplar two-dimensional space curves.

10. The method of claim 1, wherein the step of acquiring said model two-dimensional space curve includes the step of:

performing edge detection on an image that represents at least a portion of said object to provide a two-dimensional space curve.

11. The method of claim 1, wherein the step of acquiring said model two-dimensional space curve includes the step of:

performing boundary tracking on an image that represents at least a portion of said object to provide a two-dimensional space curve.

12. The method of claim 1, wherein the step of acquiring said target two-dimensional space curve includes the step of:

performing edge detection on an image that represents at least a portion of said object to provide a two-dimensional space curve.

13. The method of claim 1, wherein the step of acquiring said target two-dimensional space curve includes the step of:

performing boundary tracking on an image that represents at least a portion of said object to provide a two-dimensional space curve.

14. The method of claim 1, wherein each step of converting said position in two dimensions as a function of distance S into an angle as a function of distance S includes the steps of:

performing a first derivative operation with respect to the distance S upon each dimension of said position in two dimensions as a function of distance S to provide a pair of first derivatives;

dividing a first member of said pair by a second member of said pair to provide a quotient; and

providing the arctangent of said quotient as said angle at said distance S.

15. The method of claim 1, wherein each step of converting said position in two dimensions as a function of distance S into an angle as a function of distance S includes the steps of:

for each pair of points along said two-dimensional space curve, computing a change in a first dimension and a change in a second dimension; and

using said change in said first dimension and said change in said second dimension as indices into a look-up table having an array of angle values to provide an angle value that corresponds to said change in said first dimension and said change in said second dimension.

16. The method of claim 2, wherein the step of removing discontinuities includes the step of:

adding 360°

at a point along said angle-based model space curve.

17. The method of claim 1, further including the step of:

generating a multi-scale representation of said angle-based model and target space curves.