SYSTEM AND METHOD FOR THREE-DIMENSIONAL ALIGNMENT OF OBJECTS USING MACHINE VISION

• US 20100166294A1
• Filed: 12/29/2008
• Published: 07/01/2010
• Est. Priority Date: 12/29/2008
• Status: Active Grant

• Current Assignee: Cognex Corporation
• Original Assignee: Cognex Corporation
• Inventors: Foster, Nigel J., Wallack, Aaron S., Ye, Xiangyun, Liu, Lifeng, Marrion, Cyril C., Li, David Y., Shivaram, Guruprasad
• Granted Patent: US 8,442,304 B2
• Time in Patent Office: Days
• US Class Current: 382/154
• CPC Class Codes: G06V 10/757 Matching configurations of points or features
• CPC Class Codes: G06V 20/653 by matching three-dimensional models, e.g. conformal mapping of Riemann surfaces

Abstract

This invention provides a system and method for determining the three-dimensional alignment of a modeledobject or scene. After calibration, a 3D (stereo) sensor system views the object to derive a runtime 3D representation of the scene containing the object. Rectified images from each stereo head are preprocessed to enhance their edge features. A stereo matching process is then performed on at least two (a pair) of the rectified preprocessed images at a time by locating a predetermined feature on a first image and then locating the same feature in the other image. 3D points are computed for each pair of cameras to derive a 3D point cloud. The 3D point cloud is generated by transforming the 3D points of each camera pair into the world 3D space from the world calibration. The amount of 3D data from the point cloud is reduced by extracting higher-level geometric shapes (HLGS), such as line segments. Found HLGS from runtime are corresponded to HLGS on the model to produce candidate 3D poses. A coarse scoring process prunes the number of poses. The remaining candidate poses are then subjected to a further more-refined scoring process. These surviving candidate poses are then verified by, for example, fitting found 3D or 2D points of the candidate poses to a larger set of corresponding three-dimensional or two-dimensional model points, whereby the closest match is the best refined three-dimensional pose.

Claims

1. A system for determining alignment of an object in three dimensional space (3D) comprising:

one or more 3D sensors and one or more processing elements constructed and arranged to generate a 3D representation of a scene;

a feature extraction process that generates found 3D higher level geometric shapes (HLGS) of the scene from the 3D representation; and

a correspondence process that compares the found 3D HLGS to a model 3D HLGS to generate one or more candidate 3D poses of one or more objects in the scene, the correspondence process being constructed and arranged to score the plurality of candidate 3D poses and select at least one high-scoring pose based upon a sufficiently high score.

2. The system as set forth in claim 1 wherein the one or more 3D sensors each comprise an arrangement of a plurality of 2D cameras.

3. The system as set forth in claim 2 wherein the one or more 3D sensors each comprise a stereo camera head.

4. The system as set forth in claim 1 wherein the 3D representation is defined by 3D coordinates and at least one other geometric or non-geometric parameter.

5. The system as set forth in claim 4 wherein the at least one other geometric or non-geometric parameter includes at least one of edge direction, color and intensity.

6. The system as set forth in claim 1 wherein the scene includes a cluttered or confusing background of elements, and the 3D sensors are positioned, and the feature extraction process is constructed and arranged, to distinguish HLGS from the cluttered or confusing background of elements.

7. The system as set forth in claim 1 wherein the scene includes a plurality of the objects therein, and the feature extraction process is constructed and arranged to distinguish HLGS of one or more of the plurality of the objects.

8. The system as set forth in claim 1 wherein the scene includes no resolvable objects therein, and each of the feature extraction process and the correspondence process is constructed and arranged to identify an absence of the resolvable objects in the scene.

9. The system as set forth in claim 1 wherein the correspondence process is constructed and arranged to score the one or more candidate 3D poses using (a) a coarse scoring process that generates a plurality of coarse scored candidate 3D poses, and (b) a fine scoring process that generates one or more fine scored candidate 3D poses from the one or more coarse scored candidate 3D poses.

10. The system as set forth in claim 1 further comprising a verification process that is constructed and arranged to compare at least one of found 2D and found 3D points of the one or more objects with respect to at least one of model 2D and model 3D points, and thereby derive the at least one high-scoring pose.

11. The system as set forth in claim 1 wherein the scoring process is constructed and arranged to (a) compute a model coverage score for the one or more candidate 3D poses, (b) provide one or more high scoring candidate 3D poses each having a high model coverage score, (c) refine respective poses of the high-scoring candidate 3D poses based upon a comparison of found 3D points to model 3D points, and (d) select the at least one high-scoring pose from a combination of the high-scoring candidate 3D poses and the refined candidate 3D poses.

12. The system as set forth in claim 1 wherein the scoring process is constructed and arranged to define predetermined geometric regions that surround each of the model 3D HLGS and remove at least one candidate 3D pose whose found 3D HLGS include portions thereof outside of the predetermined geometric regions respectively.

13. The system as set forth in claim 12 wherein a refined set of candidate 3D poses are generated based upon a fit of portions of the found 3D HLGS within the geometric regions.

14. The system as set forth in claim 13 wherein each of the found 3D HLGS and model 3D HLGS are line segments, the predetermined geometric regions are pipes having a cross sectional shape that is at least one of circular, ovular, polygonal, or an irregular enclosed shape, and wherein the portions are line segment endpoints.

15. The system as set forth in claim 13 wherein the portions comprise all or a predetermined proportion of found 3D points with respect to the found 3D HLGS.

16. The system as set forth in claim 1 wherein the found 3D HLGS and the model 3D HLGS are based upon at least one of a line segment, an edgelet, a spline and a curve.

17. The system as set forth in claim 1 wherein the one or more 3D sensors include at least one trinocular camera head.

18. A method for determining alignment of an object in three dimensional (3D) space comprising:

generating, with one or more 3D sensors and one or more processing elements, a 3D representation of a scene;

extracting features so as to generate found 3D higher level geometric shapes (HLGS) of the scene from the 3D representation; and

corresponding the found 3D HLGS to a model 3D HLGS to generate one or more candidate 3D poses of one or more objects in the scene, including scoring the one or more candidate 3D poses and selecting at least one high-scoring pose based upon a sufficiently high score.

19. The method as set forth in claim 18 wherein the 3D sensors comprise each of a plurality of stereo camera heads, and further comprising arranging each of the plurality of stereo camera heads at respective vantage points with respect to the scene so as to provide a less occluded and less obstructed view of the one or more objects in the scene.

20. The method as set forth in claim 18 wherein the step of corresponding includes scoring the one or more candidate 3D poses by (a) coarse scoring that generates one or more coarse scored candidate 3D poses, and (b) fine scoring that generates one or more fine scored candidate 3D poses from the one or more coarse scored candidate 3D poses.

21. The method as set forth in claim 20 further comprising comparing at least one of found 2D and found 3D points of the one or more objects with respect to at least one of model 2D and model 3D points to thereby derive the at least one high-scoring pose.

22. The method as set forth in claim 18 wherein the scoring step includes (a) computing a model coverage score for the one or more of the candidate 3D poses, (b) providing one or more high-scoring candidate 3D poses each having a high model coverage score, (c) refining respective poses of the high-scoring candidate 3D poses based upon a comparison of found 3D points to model 3D points, and (d) selecting the at least one high-scoring pose from a combination of the high-scoring candidate 3D poses and the refined candidate 3D poses.

23. The method as set forth in claim 18 wherein the scoring step includes defining predetermined geometric regions that surround each of the model 3D HLGS and removing at least one candidate 3D pose whose found 3D HLGS include portions thereof outside of the predetermined geometric regions respectively.

24. The method as set forth in claim 23 further comprising generating the a refined set of candidate 3D poses from the one or more candidate 3D poses based upon a fit of portions of the found 3D HLGS within the geometric regions.

25. The method as set forth in claim 24 wherein each of the found 3D HLGS and model 3D HLGS are line segments, the predetermined geometric regions are pipes having a cross sectional shape that is at least one of circular, ovular, polygonal, or an irregular enclosed shape, and wherein the portions are line segment endpoints.

26. The method as set forth in claim 24 wherein the portions comprise all or a predetermined proportion of found 3D points with respect to the found 3D HLGS.

27. The method as set forth in claim 18 wherein the found 3D HLGS and the model 3D HLGS are based upon at least one of a line segment, an edgelet, a spline or a curve.

28. A method for determining alignment of an object in three dimensional (3D) space comprising:

generating, with one or more 3D sensors and one or more processing elements, a 3D representation of a scene;

extracting features so as to generate found 3D higher level geometric shapes (HLGS) of the scene from the 3D representation; and

corresponding the found 3D HLGS to a model 3D HLGS to generate one or more candidate 3D poses of one or more objects in the scene, including scoring the one or more candidate 3D poses and selecting at least one high-scoring pose based upon a sufficiently high score.