# US 10,500,727 B1 · Methods and apparatus for determining the pose of an object based on point cloud data

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 10,500,727 B1
- Document ID: US10500727B1
- Status: Granted
- Kind: B1
- Application number: 15/811,484
- Filed: 2017-11-13
- Granted: 2019-12-10
- Earliest claimed: 2016-02-18
- Assignees: X Development LLC
- Applicants: X Development LLC
- Inventors: Stefan Hinterstoisser
- Web page: https://patentgrep.com/patent/US10500727B1

## CPC

- 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}
- G06F 30/00: Computer-aided design [CAD]
- G06T 1/0014: {Image feed-back for automatic industrial control, e.g. robot with camera (robots B25J19/023)}
- G05B 2219/40564: Recognize shape, contour of object, extract position and orientation
- B25J: MANIPULATORS; CHAMBERS PROVIDED WITH MANIPULATION DEVICES ({manipulators specially adapted for use in surgery A61B34/70; manipulators used in cleaning hollow articles B08B9/04}; manipulators associated with rolling mills B21B39/20; manipulators associated with forging machines B21J13/10; {manipulators associated with picking-up and placing mechanisms B23P19/007}; means for holding wheels or parts thereof B60B30/00; {vehicles with ground-engaging propulsion means, e.g. walking members B62D57/02, B62D57/032; devices for picking-up and depositing articles or materials between conveyors B65G47/90, B65G47/91; manipulators with gripping or holding means for transferring packages B65H67/065}; cranes B66C; {manipulators used in the protection or supervision of pipe-line installations F17D5/00; walking equipment adapted for nuclear steam-generators F22B37/006}; manipulators specially adapted for, or associated with, nuclear reactors G21C; {apparatus used for handling wafers during manufacture or treatment of semiconductor H10P72/50})
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- G05B: CONTROL OR REGULATING SYSTEMS IN GENERAL; FUNCTIONAL ELEMENTS OF SUCH SYSTEMS; MONITORING OR TESTING ARRANGEMENTS FOR SUCH SYSTEMS OR ELEMENTS (systems for controlling or regulating non-electric variables G05D; systems for regulating electric or magnetic variables G05F; control devices or systems insofar as characterised by mechanical features only G05G)

## 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

### Claim 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.

### Claim 2 (depends on 1)

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.

### Claim 3 (depends on 2)

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.

### Claim 4 (depends on 3)

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.

### Claim 5 (depends on 4)

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.

### Claim 6 (depends on 1)

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.

### Claim 7 (depends on 1)

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.

### Claim 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.

### Claim 9 (depends on 8)

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.

### Claim 10 (depends on 9)

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.

### Claim 11 (depends on 10)

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.

### Claim 12 (depends on 11)

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.

### Claim 13 (depends on 8)

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.

### Claim 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.

### Claim 15 (depends on 14)

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.

### Claim 16 (depends on 15)

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.

### Claim 17 (depends on 16)

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.

### Claim 18 (depends on 17)

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.

### Claim 19 (depends on 14)

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.

### Claim 20 (depends on 14)

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.