Machine vision methods for determining characteristics of an object using boundary points and bounding regions

• US 5,974,169 A
• Filed: 03/20/1997
• Issued: 10/26/1999
• Est. Priority Date: 03/20/1997
• Status: Expired due to Term

• Current Assignee: Cognex Corporation
• Original Assignee: Cognex Corporation
• Inventors: Bachelder, Ivan A.
• Primary Examiner(s): Boudreau, Leo H.
• Assistant Examiner(s): MEHTA, BHAVESH M
• Application Number:
  US08/820,870
• Time in Patent Office: 950 Days
• Field of Search: 382/151, 382/254, 382/141, 382/145, 382/147, 382/199, 382/286, 382/288, 382/291, 364/570, 348/87-89, 348/124-126
• US Class Current: 382/151
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 2207/30141 Printed circuit board [PCB]
• CPC Class Codes: G06T 7/12 Edge-based segmentation

Abstract

Machine vision methods for determining a characteristic (such as position, orientation, size, center of mass, and boundary) of an object in an image include finding points in the image on the boundary of the object; identifying bounding boxes, or regions, in the image that correspond to edges of the object; and labeling boundary points to denote which respective edges, if any, to which they belong based on (i) the locations and orientations of those points, and (ii) locations of the plural bounding boxes. Points apparently lying on a boundary of the object, but outside a bounding box, can be ignored--and, more particularly, are denoted as not corresponding to an edge. Likewise, apparent boundary points lying within a bounding box, but at an angle not associated with the corresponding to the respective edge of the object, can also be ignored. Characteristics of the imaged object are determined as a function of those boundary points found to correspond to an edge of the object (e.g., points lying within a bounding box, at the expected angle, and not too far from a line connecting similarly situated points). Characteristics of the object, such as position, orientation, size, center of mass, and boundary points, can be determined in the image reference frame.

Claims

1. A method of determining a characteristic of an object in an image, comprising the steps of

A. finding, in the image, points on a boundary of the object;

B. identifying, in the image, plural bounding boxes corresponding to each of plural respective edges of the object;

C. determining a correspondence, if any, between points in the image on the boundary of the object and respective edges of the object, such determination being based on at least (i) locations and orientations in the image of the points on the boundary of the object, and (ii) locations in the image of the plural bounding boxes;

D. determining a characteristic of the object based on those points in the image on the boundary of the object that correspond to edges of the object.

2. A method according to claim 1, wherein step (B) includes the step of identifying bounding boxes in the image corresponding to any of a top, bottom and side edges of the object.

3. A method according to claim 1, wherein step (B) includes the steps of

determining (i) at least a coarse location of the object in the image, and (ii) an estimate of uncertainty of that location;

and

identifying the bounding boxes in the image as a function of at least the coarse location and the estimate of the uncertainty thereof.

4. A method according to claim 3, wherein step (B) includes the step of determining the coarse location of the object in the image as a function of its center of mass in the image.

5. A method according to claim 3, wherein step (B) includes the step of determining the estimate of the uncertainty of the coarse location as a function of characteristics of features in the image other than the object.

6. A method according to claim 5,wherein step (B) includes the step of determining the estimate of the uncertainty of the coarse location as a function of an estimated size of a device for handling the object, which device may appear in the image along with the object.

7. A method according to claim 6, wherein step (B) includes the step of determining the estimate of the uncertainty of the coarse location as a function of an estimated size of a pick-up nozzle that may appear in the image along with the object.

8. A method according to claim 3, wherein step (B) includes determining the estimated uncertainty as a function of potential variations in the size of the object that are not related imaging.

9. A method according to claim 1, wherein step (C) includes the steps

determining the locations and orientations in the image of points on the boundary of the object,

for each of at least selected ones of those points:

(i) determining which bounding box, if any, in the image the point resides in, (ii) comparing the orientation of the point with an expected orientation of the edge of the object corresponding to that bounding box.

10. A method according to claim 9, wherein step (C) includes the step of identifying as corresponding to a respective edge of the object a point that (i) resides in a bounding box corresponding to that edge, (ii) has an orientation that compares favorably with the expected orientation of that edge.

11. A method according to claim 10, wherein step (C) includes the steps of

fitting a line to the points in the image that correspond to a respective edge of the object, and

identifying as not corresponding to an edge any of those points that resides more than a specified distance from that line.

12. A method according to claim 9, wherein step (C) includes the step of identifying as not corresponding to an edge of the object a point in the image that (i) is not in any bounding box, or (ii) does not have an orientation that compares favorably with the expected orientation of the edge of the object corresponding to the bounding box in which the point resides.

13. A method according to claim 1, wherein step (D) includes the step of using point-line correspondences to fit to respective edges of a model of the object those points in the image that correspond to those edges.

14. A method according to claim 13, wherein step (D) includes the step of determining a characteristic of the object from the points subsequent to their being fit to the respective edges of the model.

15. A method according to claim 13, wherein step (D) includes the step of determining as the characteristic of the object any of a position, orientation, size, center of mass, and boundary of the object.

16. A method of determining a characteristic of a backlit rectangular object in an image, comprising the steps of

A. finding in the image points on a boundary of the object;

B. determining at least a coarse location of the object in the image, and an estimate of uncertainty of that location;

C. identifying as a function of at least the coarse location and the estimate of the uncertainty thereof bounding boxes in the image corresponding to any of a top, bottom and side edges of the object;

D. determining the locations and orientations in the image of points on the boundary of the object, and for each of at least selected ones of those points (i) determining which bounding box, if any, in the image the point resides in, (ii) comparing the orientation of the point with an expected orientation of the edge of the object corresponding to that bounding box;

E. identifying as corresponding to a respective edge of the object a point that (i) resides in a bounding box corresponding to that edge, (ii) has an orientation that compares favorably with the expected orientation of that edge;

F. determining a characteristic of the object based on those points in the image on the boundary of the object that correspond to edges of the object.

17. A method according to claim 16, wherein step (A) includes the step of determining a region of interest in the image and performing the remaining steps of the method on that region of interest.

18. A method according to claim 17, wherein step (A) includes the step of determining that region of interest based on any of an estimated position and uncertainty of the object in the image.

19. A method according to claim 16, wherein step (A) includes the step of smoothing the region of interest prior to performing the remaining steps the remaining steps of the method thereon.

20. A method according to claim 16, wherein step (B) includes the step of determining the coarse location of the object in the image as a function of its center of mass in the image.

21. A method according to claim 16, wherein step (B) includes the step of determining the estimate of the uncertainty of the coarse location as a function of characteristics of other features of the image.

22. A method according to claim 21, wherein step (B) includes the step of determining the estimate of the uncertainty of the coarse location as a function of an estimated size of a device for handling the object, which device may appear in the image along with the object.

23. A method according to claim 22, wherein step (B) includes the step of determining the estimate of the uncertainty of the coarse location as a function of an estimated size of a pick-up nozzle that may appear in the image along with the object.

24. A method according to claim 16, wherein step (E) includes the steps of

fitting a line to the points in the image that correspond to a respective edge of the object, and

identifying as not corresponding to an edge any of those points that resides more than a specified distance from that line.

25. A method of determining a characteristic of an object in an image, comprising the steps of

A. finding, in the image, points on a boundary of the object;

B. identifying, in the image, plural bounding boxes corresponding to each of plural respective edges of the object;

C. determining a correspondence, if any, between points in the image on the boundary the object and respective edges of the object, such determination being based on at least (i) locations in the image of the points on the boundary of the object, and (ii) locations in the image of the plural bounding boxes;

D. determining a characteristic of the object based on those points in the image on the boundary of the object that correspond to edges of the object.

26. A method of determining a characteristic of an object in an image, comprising the steps of

A. finding, in the image, points on a boundary of the object;

B. determining angular orientations of the points on the boundary of the object;

C. determining a correspondence, if any, between points in the image on the boundary of the object and respective edges of the object, such determination being based on at least (i) the angular orientations of the points on the boundary of the object, and (ii) the expected angular orientations of the edges of the object; and

D. determining a characteristic of the object based on those points in the image on the boundary of the object that correspond to edges of the object.