Nearest neighbor search using compressed octrees representing high definition maps for autonomous vehicles

Patent metadata

Field	Value
Publication number	US-11460580-B2
Application number	US-202016904238-A
Country	US
Kind code	B2
Filing date	Jun 17, 2020
Priority date	Jun 17, 2019
Publication date	Oct 4, 2022
Grant date	Oct 4, 2022

Abstract

According to an aspect of an embodiment, operations may comprise receiving a search query for points near a query-point, accessing a compressed octree representation of a point cloud comprising 3D points of a region, and traversing the compressed octree representation to identify regions that overlap a search space by, marking a current node as overlapping the search space responsive to determining that the current node is a leaf node, identifying a child node of the current node and performing a nearest neighbor search in the child node responsive to determining that a region represented by the current node overlaps the search space, and identifying a sibling node of the current node and performing the nearest neighbor search in the sibling node responsive to determining that a region represented by the current node does not overlap the search space.

First claim

What is claimed is:

1. A computer-implemented method, comprising:
receiving a search query, the search query specifying a search space comprising a query-point and a search range, the query-point being included in a first point cloud comprising a first set of three-dimensional (3D) points that correspond to at least a portion of a region;
accessing a compressed octree representation of a second point cloud comprising a second set of 3D points that correspond to the region, the compressed octree representation comprising nodes, at least some of the nodes storing a sibling link to a sibling node having the same parent node;
traversing the compressed octree representation to identify one or more nodes that correspond to the search space, the traversing comprising selecting a current node of the compressed octree representation and performing traversing operations, the traversing operations including:
responsive to determining that the current node is a leaf node and that one or more coordinates associated with the current node are included in the search space, marking the current node as corresponding to the search space,
responsive to determining that the current node is not a leaf node and determining that one or more coordinates associated with the current node are included in the search space, identifying a child node of the current node and performing the traversing operations with respect to the identified child node in which the identified child node is selected as the next current node used in the traversing operations, and
responsive to determining that no coordinates associated with the current node are included in the search space, identifying a sibling node of the current node using a corresponding sibling link of the current node and performing the traversing operations with respect to the identified sibling node in which the identified sibling node is selected as the next current node used in the traversing operations and in which no traversing operations are performed for any child node of the current node responsive to determining that no coordinates associated with the current node are included in the search space;

identifying at least one nearest neighbor node in a set of leaf nodes identified, by the traversing operations, as corresponding to the search space; and
using the query point and a particular second point of the second point cloud that corresponds to the at least one nearest neighbor node for performing an operation.

2. The computer-implemented method of claim 1 , wherein the traversing operations are performed directly on the compressed octree representation without having to decompress the compressed octree representation.

3. The computer-implemented method of claim 1 , wherein the sibling link stores an index of the sibling node, the index identifying the sibling node in a linear array.

4. The computer-implemented method of claim 1 , wherein the sibling link stores an offset value that stores a relative position of the sibling node with respect to the current node.

5. The computer-implemented method of claim 1 , wherein the compressed octree representation is represented as a linear array of structures, each structure representing a node.

6. The computer-implemented method of claim 5 , wherein the linear array of structures stores the nodes in a depth first search order of traversal of the compressed octree representation.

7. The computer-implemented method of claim 1 , wherein each node is represented as a byte such that each bit of the byte indicates whether a child node is present.

8. The computer-implemented method of claim 1 , wherein:
the search query is received by an autonomous vehicle; and
the operation comprises performing localization of the autonomous vehicle.

9. One or more non-transitory computer readable media storing instructions that in response to being executed by one or more processors, cause a computer system to perform operations, the operations comprising:
receiving a search query, the search query specifying a search space comprising a query-point and a search range, the query-point being included in a first point cloud comprising a first set of three-dimensional (3D) points that correspond to at least a portion of a region;
accessing a compressed octree representation of a second point cloud comprising a second set of 3D points that correspond to the region, the compressed octree representation comprising nodes, at least some of the nodes storing a sibling link to a sibling node having the same parent node;
traversing the compressed octree representation to identify one or more nodes that correspond to the search space, the traversing comprising selecting a current node of the compressed octree representation and performing traversing operations, the traversing operations including:
responsive to determining that the current node is a leaf node, marking the current node as corresponding to the search space,
responsive to determining that the current node is not a leaf node and determining that one or more coordinates associated with the current node are included in the search space, identifying a child node of the current node and performing the traversing operations with respect to the identified child node in which the identified child node is selected as the next current node used in the traversing operations, and
responsive to determining that no coordinates associated with the current node are included in the search space, identifying a sibling node of the current node using a corresponding sibling link of the current node and performing the in the traversing operations with respect to the identified sibling node in which the identified sibling node is selected as the next current node used in the traversing operations and in which no traversing operations are performed for any child node of the current node responsive to determining that no coordinates associated with the current node are included in the search space;

identifying at least one nearest neighbor node in a set of leaf nodes identified, by the traversing operations, as corresponding to the search space; and
using the query point and a particular second point of the second point cloud that corresponds to the at least one nearest neighbor node for performing an operation.

10. The one or more non-transitory computer-readable media of claim 9 , wherein the traversing operations are performed directly on the compressed octree representation without having to decompress the compressed octree representation.

11. The one or more non-transitory computer-readable media of claim 9 , wherein the sibling link stores an index of the sibling node, the index identifying the sibling node in a linear array.

12. The one or more non-transitory computer-readable media of claim 9 , wherein the sibling link stores an offset value that stores a relative position of the sibling node with respect to the current node.

13. The one or more non-transitory computer-readable media of claim 9 , wherein the compressed octree representation is represented as a linear array of structures, each structure representing a node.

14. The one or more non-transitory computer-readable media of claim 13 , wherein the linear array of structures stores the nodes in a depth first search order of traversal of the compressed octree representation.

15. The one or more non-transitory computer-readable media of claim 9 , wherein each node is represented as a byte such that each bit of the byte indicates whether a child node is present.

16. The one or more non-transitory computer-readable media of claim 9 , wherein:
th

Assignees

• Deepmap Inc
• Nvidia Corp

Inventors

• Schroeter Derik

Classifications

• G06F16/2246

  Trees, e.g. B+trees · CPC title

• G06F16/29

  Geographical information databases · CPC title

• G01C21/3878

  Hierarchical structures, e.g. layering · CPC title

• G06F16/24575

  using context · CPC title

• G01S17/931 Primary

  of land vehicles · CPC title