Method and apparatus for location and inspecting a two-dimensional image including co-linear features

• US 6,078,700 A
• Filed: 03/13/1997
• Issued: 06/20/2000
• Est. Priority Date: 03/13/1997
• Status: Expired due to Term

• Current Assignee: Karen B. Sarachik
• Original Assignee: Karen B. Sarachik
• Inventors: Sarachik, Karen B.
• Primary Examiner(s): Boudreau, Leo H.
• Assistant Examiner(s): DESIRE, GREGORY M
• Application Number:
  US08/816,279
• Time in Patent Office: 1,195 Days
• Field of Search: 382/145, 382/147, 382/291, 382/190, 348/87
• US Class Current: 382/291
• CPC Class Codes: G06V 10/44 Local feature extraction by analysis of parts of the pattern, e.g. by detecting edges, contours, loops, corners, strokes or intersections; Connectivity analysis, e.g. of connected components

Abstract

A method and apparatus optimizes the process of locating an image of a part by exploiting at least one set of regular co-linear features in the image of the part. A selected one of the at least one set of regular co-linear features is used to quickly correlate a set of image points and a set of model points which are likely to correspond to each other. A one to one correspondence of a subset of model points to a subset of image points yields a single possible location for the part in the image, which location can be quickly and reliably checked for correctness, and if incorrect, a next possible set to set correspondence can be tested until the correct location is found.

Claims

1. A method for locating an object in physical space and manipulating said object based on an image of said object acquired in accordance with image space, said method comprising the steps of:

preprocessing a model of said object by defining co-linear features of said model in accordance with model space, and identifying at least one model set of co-linear feature information;

implementing an image feature finder to find a plurality of features, in image space in a captured image of said object, said plurality of features being substantially similar in character to co-linear features defined in said model during preprocessing;

configuring a co-linear feature finder to receive from said image feature finder point information related to said plurality of features in said captured image and to test said plurality of features for co-linearity and frequency to form a hypothesized line comprised of a first plurality of features;

testing remaining image point information, other than said point information related to said plurality of features forming said hypothesized line, for membership in said hypothesized line until full image line feature information is established;

processing said full image line feature information and said at least one model set of co-linear feature information to generate at least one two dimensional transform mapping said full image line feature information in image space to said at least one model set of co-linear feature information in model space and providing a direct mapping of image space to model space;

using said at least one two dimensional transform to form a hypothesized image including said full image line feature information and projected feature information solved with said direct mapping of image space to model space; and

verifying said hypothesized image against said captured image to determine if each feature is in said captured image and in its proper location.

2. The method of claim 1 wherein said model is a known good or standard representation of said object and said preprocessing step involves constructing a data structure of defined co-linear features, of said model, in model space.

3. The method of claim 1 wherein said preprocessing step involves constructing a data structure of a known good or standard representation of said object to be processed in model space and said data structure includes model characteristics derived from geometric definitions describing features of interest of said model.

4. The method of claim 1 wherein said preprocessing step involves constructing a model data structure including a unique identifier for each of a respective set of co-linear features, and for each said respective set of co-linear features storing in said model data structure characteristics of interest, including a number of features in said set, a spacing between contiguous features in said set, and a location or position of said respective set with respect to a model reference frame.

5. The method of claim 4 wherein said location or position stored in said model data structure is a two dimensional transform relating a set reference frame of said respective set of co-linear features to said model reference frame.

6. The method of claim 5 wherein said two dimensional transform relating said set reference frame of said respective set of co-linear features to said model reference frame includes an X translation coordinate, a Y translation coordinate, and a rotation angle between X axes of said set reference frame and said model reference frame.

7. The method of claim 1 wherein said co-linear feature finder is configured to find all groups of three features and said groups are formed by executing an exhaustive loop which processes all features to form said groups of three features.

8. The method of claim 1 wherein said first plurality of features forming said hypothesized line equals three features.

9. The method of claim 1 wherein said co-linear feature finder is configured to find all groups of three features and said groups of three features are processed by said co-linear feature finder to determine whether they meet co-linearity and frequency criteria based on model features of interest.

10. The method of claim 7 wherein said co-linear feature finder is configured to find all groups of three features and wherein each group of three co-linear features is tested for co-linearity, where co-linearity is determined based on a least squared line along which each feature in said group of three features fits wherein the maximum deviation permissible for a features to fit a line is a function of dimensions of model features of interest.

11. The method of claim 7 wherein said co-linear feature finder is configured to find all groups of three features and wherein each group of three features is tested for frequency, where frequency is defined as spacing between contiguous model features as a function of geometry of said model.

12. The method of claim 1 wherein said full image line is established when a number of features determined to be members of said hypothesized line is greater than or equal to a number of features in a smallest set of a plurality of sets of co-linear features in said model.

13. The method of claim 1 wherein said step of testing remaining image point information involves testing said remaining image point information for co-linearity and frequency in accordance with said first plurality of features of said hypothesized line.

14. The method of claim 1, further including a step of refining position information of features in said hypothesized image to ensure optimal positioning of said features in said hypothesized image based on information from said captured image.

15. The method of claim 14 wherein said step of refining involves updating said at least one two dimensional transform by computing a refined transform which minimizes a sum of squared distances between each corresponding model feature and image feature.

16. The method of claim 1, wherein said step of processing said full image line feature information and said at least one model set of co-linear feature information to generate at least one two dimensional transform mapping said full image line feature information in image space to said at least one model set of co-linear feature information in model space involves steps of:

sorting features comprising said full image line feature information in order of relative position along said hypothesized line to form ordered image line features;

sorting co-linear model features comprising said at least one model set of co-linear feature information in order of relative set position to form ordered model set features;

generating a first position hypothesis by effecting a one-to-one correspondence between a first feature in said ordered image line features and a first feature in said ordered model set features, and successively corresponding remaining features in each of said ordered image line features and said ordered model set features;

generating a second position hypothesis by effecting a one-to-one correspondence between a first feature in said ordered image line features and a last feature in said ordered model set features, and successively corresponding remaining features in each of said ordered image line features and said ordered model set features; and

generating said at least one two dimensional transform from said first position hypothesis and said second position hypothesis.

17. The method of claim 16 wherein other position hypotheses are formed by one cf incrementing or decrementing a position of said first feature in said ordered image line features relative to said first feature in said ordered model set features, and successively corresponding remaining features in each of said ordered image line features and said ordered model set features effecting one-to-one correspondence of all remaining features in forward and backward directions, and generating said at least one two dimensional transform from said other position hypotheses.

18. An apparatus for inspecting and locating a two dimensional representation of an object within a captured image, comprising:

an image feature finder configured to find a plurality of features, in image space in said captured image of said object, each of said plurality of features being substantially similar in character to features in at least one model set of co-linear features present in a model of said object in accordance with model space;

a co-linear feature finder configured to receive from said image feature finder point information related to said plurality of features in said captured image and to test said plurality of features for co-linearity and frequency, said co-linear feature finder configured to form a hypothesized line comprised of a first plurality of features and to identify all features belonging to said hypothesized line in order to obtain full image line feature information;

a position hypothesis generator configured to receive said full image line feature information from said co-linear feature finder and said at least one model set of co-linear feature information, and to generate at least one two dimensional transform mapping said full image line feature information in image space to said at least one model set of co-linear feature information in model space effecting a direct mapping of image space to model space;

a verification processor configured to receive said at least one two dimensional transform from said position hypothesis generator and to form a hypothesized image including said full image line feature information and projected feature information solved with said direct mapping of image space to model space, said verification processor being further configured to verify said hypothesized image against said captured image to determine if each feature is in said captured image and in its proper location.

19. The apparatus of claim 18 further including a preprocessor configured to preprocess said model of said object by defining co-linear features of said model in accordance with model space, and to identify at least one model set of co-linear feature information to pass to said position hypothesis generator.

20. The apparatus of claim 19 wherein said preprocessor is configured to constructing a data structure of co-linear features of said model, in model space, said data structure including model characteristics derived from geometric definitions describing features of interest of said model and including a unique identifier for each of a respective set of co-linear features, and for each said respective set of co-linear features, a number of features in said set, a spacing between contiguous features in said set, and a location or position of said respective set with respect to a model reference frame, said location or position being a two dimensional transform relating a set reference frame of said respective set of co-linear features to said model reference frame and having an X translation coordinate, a Y translation coordinate, and a rotation angle between X axes of said set reference frame and said model reference frame.

21. The apparatus of claim 18 wherein said co-linear feature finder is configured to test remaining image point information, other than said point information related to said plurality of features forming said hypothesized line, for membership in said hypothesized line until full image line feature information is established.

22. The apparatus of claim 18 wherein said co-linear feature finder is configured to find all groups of three features and said groups are formed by executing an exhaustive loop which processes all features to form said groups of three features.

23. The apparatus of claim 18 wherein said first plurality of features forming said hypothesized line equals three features.

24. The apparatus of claim 18 wherein said co-linear feature finder is configured to find all groups of three features and said groups of three features are processed by said co-linear feature finder to determine whether they meet co-linearity and frequency criteria based on model features of interest.

25. The apparatus of claim 18 wherein a vision system is implemented incorporating said image feature finder, said co-linear feature finder, said position hypothesis generator and said verification processor, in a mechanism for picking and placing electronic components on a printed circuit board.