Probable reconstruction of surfaces in occluded regions by computed symmetry

• US 20050128197A1
• Filed: 12/10/2004
• Published: 06/16/2005
• Est. Priority Date: 12/11/2003
• Status: Active Grant

• Current Assignee: Strider Labs, Inc.
• Original Assignee: Strider Labs, Inc.
• Inventors: Wegbreit, Eliot Leonard, Thrun, Sebastian
• Granted Patent: US 7,961,934 B2
• Time in Patent Office: Days
• US Class Current: 345/421
• CPC Class Codes: G01B 21/20 for measuring contours or curvatures, e.g. determining profile
• CPC Class Codes: G06T 2207/10012 Stereo images
• CPC Class Codes: G06T 2207/20116 Active contour; Active surface; Snakes
• CPC Class Codes: G06T 7/55 from multiple images
• CPC Class Codes: G06T 7/68 of symmetry
• CPC Class Codes: G06V 10/42 Global feature extraction by analysis of the whole pattern, e.g. using frequency domain transformations or autocorrelation

Abstract

A system for obtaining a probable 3D map of an occluded surface of an object is provided. The system receives an initial 3D map of a visible surface of the object and identifies one or more symmetries of the initial 3D map. The system computes the probable 3D map of the occluded surface by projecting points of the initial 3D map into occluded regions of space according to the identified symmetries. The system can also comprise an imager for obtaining the initial 3D map. The actual occluded surface cannot be known with absolute certainly because it is occluded; however, the computed 3D map will closely resemble the actual occluded surface in many instances because most objects possess one or more symmetries and the computed 3D map is based on such symmetries that are identified in the initial 3D map of the object.

Claims

1. A system for obtaining a probable 3D map of an occluded surface of an object, the system comprising:

an imager configured to acquire an initial 3D map of a visible surface of the object; and

a computing device configured to

identify one or more symmetries of the initial 3D map, and

compute the probable 3D map of the occluded surface from the one or more identified symmetries and the initial 3D map.

2. The system of claim 1 wherein the imager includes three cameras.

3. The system of claim 1 wherein the imager includes a patterned light projector.

4. The system of claim 1 wherein the imager is configured to acquire the initial 3D map by a dense stereo with active illumination process.

5. The system of claim 1 wherein the imager is configured to acquire the initial 3D map by integrating results from multiple imaging modalities.

6. The system of claim 1 wherein the imager includes a laser range finder.

7. A system for obtaining a probable 3D map of an occluded surface of an object, the system comprising:

means for acquiring an initial 3D map of a visible surface of the object as viewed from a known viewpoint;

means for identifying one or more symmetries of the initial 3D map; and

means for computing the probable 3D map of the occluded surface from the one or more identified symmetries and the initial 3D map.

8. A method for determining a probable 3D map of an occluded surface of an object, comprising the steps of:

acquiring an initial 3D map of a visible surface of the object as viewed from a known viewpoint;

identifying one or more symmetries of the initial 3D map; and

computing the probable 3D map of the occluded surface from the identified one or more symmetries and the initial 3D map.

9. The method of claim 8 wherein identifying the one or more symmetries of the initial 3D map includes finding one or more part symmetries, each of which is local to a portion of the initial 3D map.

10. The method of claim 9 wherein finding one of the part symmetries includes identifying a symmetry type, and calculating a numerical parameter vector and a domain.

11. The method of claim 10 wherein the symmetry type is chosen from a set including mirror plane symmetry, mirror axis symmetry, mirror point symmetry, dual mirror plane symmetry, triple mirror plane symmetry, rotational axis symmetry, rotational point symmetry, and the rotational axis symmetry paired with an orthogonal mirror plane symmetry.

12. The method of claim 10 wherein the symmetry type is chosen from a set including generalized rotational symmetries defined using ellipses for axis rotational symmetries and ellipsoids for point rotational symmetries.

13. The method of claim 10 wherein the symmetry type is chosen from a set including generalized mirror surface symmetries defined through non-planar mirror surfaces.

14. The method of claim 10 wherein the symmetry type is chosen from a set including generalized rotational axis symmetries defined through curved axes and generalized mirror axis symmetries defined through curved axes.

15. The method of claim 10 wherein identifying the symmetry type includes searching according to a hierarchy of candidate symmetry types.

16. The method of claim 15 wherein searching according to the hierarchy of candidate symmetry types begins with searching for a mirror plane symmetry type.

17. The method of claim 10 wherein calculating the numerical parameter vector includes searching a numerical parameter vector space at discrete points over the space, scoring the discrete points, and finding those discrete points that are local maxima with respect to the discrete points over the space.

18. The method of claim 17 wherein calculating the numerical parameter vector further includes a step of local parameter optimization wherein the initial values are the discrete points that are local maxima.

19. The method of claim 18 wherein the step of local parameter optimization includes performing a sequence of hill climbing steps.

20. The method of claim 18 wherein the step of local parameter optimization includes performing a conjugate gradient descent.

21. The method of claim 18 wherein the step of local parameter optimization includes performing a quasi-Newton method.

22. The method of claim 10 wherein calculating the numerical parameter vector and calculating the domain are performed by a joint optimization.

23. The method of claim 22 wherein the joint optimization is performed by interleaving the optimization of the numerical parameter vector and the optimizing of the domain in a joint optimization loop.

24. The method of claim 10 wherein calculating the domain includes calculating an initial domain, setting the domain equal to the initial domain, growing the domain by recursively adding points that adjoin the domain, and shrinking the domain by recursively removing points from the domain that adjoin points outside of the domain.

25. The method of claim 10 wherein computing the probable 3D map of the occluded surface includes projecting points in the domain according to the symmetry type and the numerical parameter vector.

26. The method of claim 9 wherein finding a part symmetry of the one or more part symmetries of the initial 3D map includes identifying a candidate domain, determining a symmetry feature for the candidate domain, and jointly optimizing the domain and the symmetry feature.

27. The method of claim 26 wherein identifying the candidate domain includes skeletonization.

28. The method of claim 26 wherein identifying the candidate domain includes searching for a region with a large interior and few points of adjacency with the rest of the object.

29. The method of claim 26 wherein identifying the candidate domain includes computing surface patches that conform to part-like areas.

30. The method of claim 8 wherein identifying the one or more symmetries of the initial 3D map includes selecting initial locations within the initial 3D map from which to begin a search for the symmetries.

31. The method of claim 30 wherein selecting initial locations includes using a grid of initial locations.

32. The method of claim 30 wherein selecting initial locations includes employing a Hough transform.

33. The method of claim 30 wherein selecting initial locations includes analyzing shape features of the initial 3D map.

34. The method of claim 33 wherein analyzing shape features includes analyzing visible surface normals for possible locations of rotational symmetry features.

35. The method of claim 30 wherein selecting initial locations includes searching for vertical features in the initial 3D map.

36. The method of claim 30 wherein selecting initial locations includes searching for local shape features.

37. The method of claim 36 wherein searching for local shape features includes searching for lines.

38. The method of claim 10 wherein the domain is represented by the union of multiple contiguous point sets.

39. The method of claim 10 wherein the domain is represented by an implicit function.

40. The method of claim 39 wherein the implicit function defines an ellipsoid.

41. The method of claim 10 wherein the domain is represented by an active contour.

42. The method of claim 10 wherein the domain is represented by a spline.

43. The method of claim 8 wherein the probable 3D map of the occluded surface comprises one or more probable surface regions and a measure of confidence is computed for each of the probable surface regions.

44. A system for obtaining a probable 3D map of an occluded surface of an object, the system comprising:

a computing device configured to

receive an initial 3D map of a visible surface of the object as viewed from a known viewpoint;

identify one or more symmetries of the initial 3D map; and

compute the probable 3D map of the occluded surface from the identified one or more symmetries and the initial 3D map.

45. A computer-readable medium comprising program instructions for computing a probable 3D map of an occluded surface of an object, the program instructions comprising the steps of:

receiving an initial 3D map of a visible surface of the object as viewed from a known viewpoint;

identifying one or more symmetries of the initial 3D map; and

computing the probable 3D map of the occluded surface from the identified one or more symmetries and the initial 3D map.

46. A robotic system comprising:

an arm terminating in an end-effector having components for grasping an object;

an imager configured to acquire an initial 3D map of a visible surface of the object; and

a computing device configured to

identify one or more symmetries of the initial 3D map,

compute a probable 3D map of the occluded surface from the identified one or more symmetries and the initial 3D map, and

compute a grasp for the end-effector, the grasp describing positions of one or more of the components for grasping relative to the probable 3D map of the occluded surface.