Vision system for distinguishing touching parts

• US 4,876,728 A
• Filed: 11/20/1987
• Issued: 10/24/1989
• Est. Priority Date: 06/04/1985
• Status: Expired due to Term

• Current Assignee: Adept Technology, Inc. (Omron Corporation)
• Original Assignee: Adept Technology, Inc. (Omron Corporation)
• Inventors: Roth, Scott D.
• Primary Examiner(s): Boudreau, Leo H.
• Assistant Examiner(s): Couso, Jose L.
• Application Number:
  US07/124,408
• Time in Patent Office: 704 Days
• Field of Search: 382/8, 382/14-16, 382/21, 382/22, 382/25, 382/28, 382/34, 382/36, 364/513, 358/101, 358/106, 358/107, 901/1, 901/47
• US Class Current: 382/153
• CPC Class Codes: G06V 10/26 Segmentation of patterns in the image field; Cutting or merging of image elements to establish the pattern region, e.g. clustering-based techniques; Detection of occlusion
• 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 20/66 Trinkets, e.g. shirt buttons or jewellery items recognising microscopic objects G06V20/69
• CPC Class Codes: G06V 2201/06 Recognition of objects for industrial automation
• CPC Class Codes: G06V 30/248 involving plural approaches, e.g. verification by template match; Resolving confusion among similar patterns, e.g. "O" versus "Q" G06V30/242 takes precedence

Abstract

A practical vision system for controlling the positioning of a robot arm recognizes and locates objects. The vision system processes binary images, but recognizes objects based on boundary features such as lines, arcs, corners and holes instead of "blob features" such as area and best-fit ellipse. Consequently, the vision system can process two common situations not handled by blob analysis: merged blobs due to touching or overlapping parts and incomplete blobs due to low image contrast. The microprocessor-based system is interfaced to the robot system and can recognize up to five parts per second.

Claims

1. In a vision system for identifying touching parts, a method for identifying an object independent of the orientation of said object, comprising the steps of

(a) developing sensory data comprising an image of said object;

(b) separating closed regions from background by connectivity analysis of the data representing said image;

(c) developing a chain encoded representation of a region boundary of each of said closed regions of said image;

(d) fitting edge segments to the chain encoded representation of each region boundary to produce a more succinct representation of the boundary of each of said closed regions of said image;

(e) fitting straight line and circular arc segments to the edge segments to create edges and corners which characterize said image;

(f) classifying said straight line and circular arc segments by feature classes, each said feature class describing a group of related features with a specific range of lengths, radii, included angles and/or angular ranges, one or more of said feature classes being associated with each of a plurality of prototypes stored in memory of said vision system to facilitate matching said image with one or more of said plurality of prototypes;

(g) proposing a match of an image of said object to said prototype based on said feature present in said object being classified in feature classes associated with said prototype; and

(h) verifying the match of the object and the prototype by translation and rotation of a region boundary of the prototype to align with the image of the object to match features of said image with features of said prototype whereby the object can be identified even when overlying another part.

2. A method as in claim 1 including

the steps of training the system to recognize sample parts characterized by features,

the step of identifying said object comprising comparing features of said object to features of said prototype,

proposing a match when the comparison of one or more features of said prototype matches one or more features of said object, and

placing the prototype in a particular position and orientation relative to the image to confirm the identity of the object.

3. A method as in claim 2 including the step of traversing the complete boundary of said object looking for evidence of its identity based on identified segments, and

summing up said evidence of verified segments and comparing said sum to an acceptance threshold to verify the position and orientation of the object.

4. A method as in claim 2 wherein a camera is positioned to develop sensory data on a line-by-line basis representing images of objects moving past on a conveyor belt, the camera being perpendicular to the travel of the conveyor belt so that scaling may be presumed to be constant for the prototype being used for training and the object to be recognized.

5. A method as in claim 2 wherein following said training step and during the planning step, feature classes are defined,

features of the image with a proper edge type and having dimensions within said specified ranges being associated with said feature class to identify the image.

6. A method as in claim 5 wherein the feature classes comprise classes for identifying corner features of said image, said corner features being defined by adjacent ones of said straight line and circular arc segments as line-line, line-arc, arc-line, and arc-arc, the comparison step comprising comparing boundaries of said corner features defined by said fitted straight line and circular arc segments of said image to said feature classes defining a group of similar corners of said prototype.

7. A method as in claim 6 wherein the comparison between each said corner feature of said image and said corner defining feature class is made on the basis that said boundaries of said image corner must be of the same type as boundaries of the corner defining feature class.

8. A method as in claim 7 wherein the boundaries of each said corner feature of said image define an included angle, each said corner defining feature class defines a range of included angles, the image corner being assigned to one of said corner defining feature classes as being of the same type only if the included angle of the image corner is within the range of the angles of the corner defining feature class.

9. A method as in claim 8 including the further steps during planning of associating with each said corner defining feature class of said prototype an acceptable maximum/minimum included angle, associating with each line component of a feature class an acceptable maximum/minimum length, and associating with each said arc component of a feature class a minimum/maximum angular range, minimum/maximum radius and concave/convex indication.

10. A method as in claim 9 including the further step of testing the boundaries of each said corner feature of said image as compared to limits established during said planning step for said feature classes, including the steps of testing each line boundary for length, and testing each arc boundary for radius, convexity, and angular range.

11. A method as in claim 10 wherein said step of testing boundaries of image feature corners is carried out only for image features assigned to prototype feature corners as matched features of the same type.

12. A method as in claim 7 wherein said training step includes the further step of assigning weights to each edge of said prototype, so that during said step of verifying a match between said image and said prototype the fact that part or all of an edge of said image is missing can be taken into account.

13. A method in claim 7 wherein said training step includes the step of assigning an effort level to each said prototype including the step of assigning weights to the edges of a prototype and assigning a verify percentage to the prototype, said image of said object being verified as identified with the prototype if a sufficient percentage of the boundary of the prototype is identified with edges in the image.

14. A method as in claim 13 wherein said step of verifying the identification of said object image comprises calculating a minimum verify amount=VP×

E(W×

L) where

VP is the verify percentage of a prototype i.e., the minimum amount to indicate verification;

W is the weight assigned to one edge of said prototype; and

L is the length of said one edge of said prototype.

15. A method as in claim 1 wherein said edge segments are connected at corners, the step of fitting line segments to said image comprising selecting one of said corners as a starting point of a line segment, using a second corner which is a next adjacent corner along the boundary as an initial line estimate, and continuing the line through subsequent corners to establish a continuing direction of the line which falls within a maximum angle variation from an initial direction of said line.

16. A method as in claim 15 wherein the step of fitting a line segment continues for a series of points through which the constraints are satisfied that the continued direction of the line falls within an allowable angular variation in direction from the previous point, and that the length of said continued direction line is increasing, the process including the step of tightening the acceptable angular variation for each said point added to said continued direction line.

17. A method as in claim 15 including the step of fitting arc segments to said image comprising the steps of proposing an arc based on a minimum of four corners of a sequence of three of said edge segments, proposing a center and a radius for said arc, and verifying that said boundary defined by said sequence of edge segments fits the proposed arc.

18. A method as in claim 6 of proposing a match between said image of an object to be recognized and said prototype comprising the steps of selecting one of said corners from said prototype and from said image of said object to be identified, computing a transformation of said selected corner of said prototype to align said corner with said selected corner of said image, and confirming a match between said prototype and said image by the presence of at least one other prototype corner near to and oriented with a corner of said image.

19. A method as in claim 18 wherein said step of verifying the identification of said object image comprises calculating a minimum verify amount=VP×

E(W×

L) where

VP is the verify percentage of a prototype i.e., the minimum amount to indicate verification;

W is the weight assigned to each of said edge segments of said prototype; and

L is the length of said edge segments of said prototype, said image being identified only if said minimum verify amount exceeds a preset minimum.

20. A method as in claim 2 comprising the step of planning for the recognition of said image of said object by the steps of

constructing said feature classes for each pair of said edges of said prototype and for said edges of said prototype,

merging similar ones of said feature classes,

constructing subclasses of said feature classes, said subclasses defining potential ones of said pairs of said edges adapted to fit said feature class,

constructing an image of boundary representation of said prototype consisting of arcs and lines,

assigning features of said prototype to said feature class and subclasses, and

selecting confirming features to use to confirm a match of a feature of said prototype with a feature of said image.