Methods and apparatus for determining the pose of an object based on point cloud data

• US 10,500,727 B1
• Filed: 11/13/2017
• Issued: 12/10/2019
• Est. Priority Date: 02/18/2016
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: X Development LLC (Alphabet Inc.)
• Inventors: Hinterstoisser, Stefan
• Primary Examiner(s): Tran, Khoi H
• Assistant Examiner(s): Peche, Jorge O
• Application Number:
  US15/811,484
• Time in Patent Office: 757 Days
• CPC Class Codes: B25J 9/1671 characterised by simulation, either to verify existing program or to create and verify new program, CAD/CAM oriented, graphic oriented programming systems
• CPC Class Codes: G05B 2219/40564 Recognize shape, contour of object, extract position and orientation
• CPC Class Codes: G06F 30/00 Computer-aided design [CAD]
• CPC Class Codes: G06T 1/0014 Image feed-back for automatic industrial control, e.g. robot with camera robots B25J19/023

Abstract

Methods, apparatus, and computer readable media that are related to 3D object detection and pose determination and that may optionally increase the robustness and/or efficiency of the 3D object recognition and pose determination. Some implementations are generally directed to techniques for generating an object model of an object based on model point cloud data of the object. Some implementations of the present disclosure are additionally and/or alternatively directed to techniques for application of acquired 3D scene point cloud data to a stored object model of an object to detect the object and/or determine the pose of the object.

Claims

1. A method implemented by one or more processors, comprising:

identifying, by one or more of the processors, scene point cloud data that captures at least a portion of an object in an environment;

selecting, by one or more of the processors and from the scene point cloud data, a plurality of scene point pairs that each include a scene reference point and a corresponding additional scene point;

identifying, by one or more of the processors, a model point pair for each of the scene point pairs, wherein each of the model point pairs is identified from a stored model of the object based on one or more features of a corresponding one of the scene point pairs;

generating, by one or more of the processors, a plurality of scene reference point candidate in-plane rotations based on the model point pairs and the scene point pairs,

wherein each of the scene reference point candidate in-plane rotations is generated based on a corresponding one of the model point pairs and a corresponding one of the scene point pairs;

determining, by one or more of the processors, a candidate pose for a scene reference point, of the scene reference points, based on a group of the scene reference point candidate in-plane rotations and their model reference points,

wherein determining the candidate pose for the scene reference point based on the group of the scene reference point candidate in-plane rotations comprises;

including a first instance of a given candidate scene reference point in-plane rotation of the candidate scene reference point in-plane rotations in the group and excluding a second instance of the given candidate scene reference point in-plane rotations from the group,

wherein the first instance of the given candidate scene reference point in-plane rotation is generated based on a given model point pair of the model point pairs and the second instance is excluded from the group based on the second instance of the given candidate scene reference point in-plane rotation also being based on the given model point pair.

2. The method of claim 1, wherein including the first instance of a given candidate scene reference point in-plane rotation of the candidate scene reference point in-plane rotations in the group comprises:

casting a vote based on the first instance, the vote being for the given candidate scene reference point in-plane rotation for a given model reference point of a given model point pair of the model point pairs, and the given model point pair being utilized to generate the given candidate scene reference point in-plane rotation.

3. The method of claim 2, wherein excluding the second instance of the given candidate scene reference point in-plane rotation from the group comprises:

preventing the casting of an additional vote based on the second instance, the additional vote being for the given candidate scene reference point in-plane rotation for the given model reference point.

4. The method of claim 3, further comprising:

assigning, in response to including the first instance in the group, a value assigned to a database identifier of the given model point pair and the given candidate scene reference point in-plane rotation;

wherein excluding the second instance of the given candidate scene reference point in-plane rotation from the group is based on identifying the value as assigned to the database identifier of the given model point pair and the given candidate scene reference point in-plane rotation.

5. The method of claim 4, wherein the database identifier is a multi-bit value indexed by the given model point pair and the assigning comprises assigning the value to one of the bits of the multi-bit value.

6. The method of claim 1, further comprising:

identifying a bounding measure for one or more dimensions of the object;

wherein selecting the plurality of scene point pairs that each include a scene reference point and a corresponding additional scene point comprises;

selecting the additional scene points based on the additional scene points satisfying the bounding measure.

7. The method of claim 1, further comprising:

determining a pose for the object based on the candidate pose of the scene reference point; and

adjusting one or more actuators of a robot based on the determined pose of the object.

8. A robot, comprising:

one or more actuators;

one or more processors receiving scene point cloud data, the scene point cloud data capturing at least a portion of an object in an environment, wherein the one or more processors are configured to;

select, from the scene point cloud data, a plurality of scene point pairs that each include a scene reference point and a corresponding additional scene point

identify a model point pair for each of the scene point pairs, wherein each of the model point pairs is identified from a stored model of the object based on one or more features of a corresponding one of the scene point pairs;

generate a plurality of scene reference point candidate in-plane rotations based on the model point pairs and the scene point pairs,

wherein each of the scene reference point candidate in-plane rotations is generated based on a corresponding one of the model point pairs and a corresponding one of the scene point pairs;

determine a candidate pose for a scene reference point, of the scene reference points, based on a group of the scene reference point candidate in-plane rotations and their model reference points,

wherein in determining the candidate pose for the scene reference point based on the group of the scene reference point candidate in-plane rotations one or more of the processors are configured to;

include a first instance of a given candidate scene reference point in-plane rotation of the candidate scene reference point in-plane rotations in the group and exclude a second instance of the given candidate scene reference point in-plane rotations from the group,

wherein the first instance of the given candidate scene reference point in-plane rotation is generated based on a given model point pair of the model point pairs and the second instance is excluded from the group based on the second instance of the given candidate scene reference point in-plane rotation also being based on the given model point pair;

determine a pose for the object based on the candidate pose of the scene reference point; and

provide, to one or more of the actuators, control commands that are based on the determined pose.

9. The robot of claim 8, wherein in including the first instance of a given candidate scene reference point in-plane rotation of the candidate scene reference point in-plane rotations in the group, one or more of the processors are configured to:

cast a vote based on the first instance, the vote being for the given candidate scene reference point in-plane rotation for a given model reference point of a given model point pair of the model point pairs, and the given model point pair being utilized to generate the given candidate scene reference point in-plane rotation.

10. The robot of claim 9, wherein in excluding the second instance of the given candidate scene reference point in-plane rotation from the group, one or more of the processors are configured to:

prevent the casting of an additional vote based on the second instance, the additional vote being for the given candidate scene reference point in-plane rotation for the given model reference point.

11. The robot of claim 10, wherein one or more of the processors are further configured to:

assign, in response to including the first instance in the group, a value assigned to a database identifier of the given model point pair and the given candidate scene reference point in-plane rotation;

wherein excluding the second instance of the given candidate scene reference point in-plane rotation from the group is based on identifying the value as assigned to the database identifier of the given model point pair and the given candidate scene reference point in-plane rotation.

12. The robot of claim 11, wherein the database identifier is a multi-bit value indexed by the given model point pair and wherein in assigning the value to the database identifier, one or more of the processors are configured to assign the value to one of the bits of the multi-bit value.

13. The robot of claim 8, wherein one or more of the processors are further configured to:

identify a bounding measure for one or more dimensions of the object;

wherein in selecting the plurality of scene point pairs that each include a scene reference point and a corresponding additional scene point, one or more of the processors are configured to;

select the additional scene points based on the additional scene points satisfying the bounding measure.

14. One or more non-transitory computer-readable media comprising instructions that, in response to execution of the instructions by one or more processors, cause the one or more processors to perform the following operations:

identifying scene point cloud data that captures at least a portion of an object in an environment;

selecting, from the scene point cloud data, a plurality of scene point pairs that each include a scene reference point and a corresponding additional scene point;

identifying a model point pair for each of the scene point pairs, wherein each of the model point pairs is identified from a stored model of the object based on one or more features of a corresponding one of the scene point pairs;

generating a plurality of scene reference point candidate in-plane rotations based on the model point pairs and the scene point pairs,

wherein each of the scene reference point candidate in-plane rotations is generated based on a corresponding one of the model point pairs and a corresponding one of the scene point pairs;

determining a candidate pose for a scene reference point, of the scene reference points, based on a group of the scene reference point candidate in-plane rotations and their model reference points,

wherein determining the candidate pose for the scene reference point based on the group of the scene reference point candidate in-plane rotations comprises;

including a first instance of a given candidate scene reference point in-plane rotation of the candidate scene reference point in-plane rotations in the group and excluding a second instance of the given candidate scene reference point in-plane rotations from the group,

wherein the first instance of the given candidate scene reference point in-plane rotation is generated based on a given model point pair of the model point pairs and the second instance is excluded from the group based on the second instance of the given candidate scene reference point in-plane rotation also being based on the given model point pair.

15. The non-transitory computer-readable media of claim 14, wherein including the first instance of a given candidate scene reference point in-plane rotation of the candidate scene reference point in-plane rotations in the group comprises:

casting a vote based on the first instance, the vote being for the given candidate scene reference point in-plane rotation for a given model reference point of a given model point pair of the model point pairs, and the given model point pair being utilized to generate the given candidate scene reference point in-plane rotation.

16. The non-transitory computer-readable media of claim 15, wherein excluding the second instance of the given candidate scene reference point in-plane rotation from the group comprises:

preventing the casting of an additional vote based on the second instance, the additional vote being for the given candidate scene reference point in-plane rotation for the given model reference point.

17. The non-transitory computer-readable media of claim 16, wherein execution of the instructions further cause the one or more processors to perform the following operation:

assigning, in response to including the first instance in the group, a value assigned to a database identifier of the given model point pair and the given candidate scene reference point in-plane rotation;

wherein excluding the second instance of the given candidate scene reference point in-plane rotation from the group is based on identifying the value as assigned to the database identifier of the given model point pair and the given candidate scene reference point in-plane rotation.

18. The non-transitory computer-readable media of claim 17, wherein the database identifier is a multi-bit value indexed by the given model point pair and the assigning comprises assigning the value to one of the bits of the multi-bit value.

19. The non-transitory computer-readable media of claim 14, wherein execution of the instructions further cause the one or more processors to perform the following operation:

identifying a bounding measure for one or more dimensions of the object;

wherein selecting the plurality of scene point pairs that each include a scene reference point and a corresponding additional scene point comprises;

selecting the additional scene points based on the additional scene points satisfying the bounding measure.

20. The non-transitory computer-readable media of claim 14, wherein execution of the instructions further cause the one or more processors to perform the following operations:

determining a pose for the object based on the candidate pose of the scene reference point; and

adjusting one or more actuators of a robot based on the determined pose of the object.