# US 2020/0393268 A1 · Storing normals in compressed octrees representing high definition maps for autonomous vehicles

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

- Number: US 2020/0393268 A1
- Document ID: US20200393268A1
- Status: Published application
- Kind: A1
- Application number: 16/904,259
- Filed: 2020-06-17
- Published: 2020-12-17
- Earliest claimed: 2019-06-17
- Assignees: Deepmap Inc.
- Applicants: DeepMap Inc.
- Inventors: Derik Schroeter
- Web page: https://patentgrep.com/patent/US20200393268A1

## CPC

- G06T 17/005: {Tree description, e.g. octree, quadtree}
- G01C 21/3638: {including 3D objects and buildings (three dimensional [3D] modelling, e.g. data description of 3D objects G06T17/00; geographic models G06T17/05)}
- G01C 21/3841: {Data obtained from two or more sources, e.g. probe vehicles}
- G01C 21/3848: {Data obtained from both position sensors and additional sensors}
- G01C 21/387: {Organisation of map data, e.g. version management or database structures}
- G01C 21/3889: {Transmission of selected map data, e.g. depending on route}
- G06F 18/2323: based on graph theory, e.g. minimum spanning trees [MST] or graph cuts
- G06V 10/757: {Matching configurations of points or features}
- G06V 10/7635: {based on graphs, e.g. graph cuts or spectral clustering}
- G06V 20/56: exterior to a vehicle by using sensors mounted on the vehicle
- G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- G01C: MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY (measuring liquid level G01F; radio navigation, determining distance or velocity by use of propagation effects, e.g. Doppler effects, propagation time, of radio waves, analogous arrangements using other waves G01S)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06V: IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING

## Abstract

According to an aspect of an embodiment, operations may comprise receiving a 3D point cloud representation of a region comprising points, with each point of the 3D point cloud representation associated with a normal value of a surface corresponding to the point, storing a set of discretized normal values, for each point of the 3D point cloud representation, associating the point with one of the discretized normal values in the set of discretized normal values by mapping the normal value associated with the point to the one of the discretized normal values in the set of discretized normal values, and storing a compressed octree representation comprising nodes, with at least a subset of the nodes of the compressed octree representation storing an index value identifying a discretized normal value for points of the 3D point cloud representation represented by the node.

## Claims

### Claim 1

A computer-implemented method, comprising:
receiving a three-dimensional (3D) point cloud representation of a region comprising points, each point of the 3D point cloud representation associated with a normal value of a surface corresponding to the point;
storing a set of discretized normal values;
for each point of the 3D point cloud representation, associating the point with one of the discretized normal values in the set of discretized normal values by mapping the normal value associated with the point to the one of the discretized normal values in the set of discretized normal values;
storing a compressed octree representation comprising nodes, at least a subset of the nodes of the compressed octree representation storing an index value identifying the mapped discretized normal value for points of the 3D point cloud representation represented by the node;
receiving, at an online system, a request for a high definition (HD) map data of the region;
in response to the request, transmitting, from the online system, the set of discretized normal values and the compressed octree representation; and
using the compressed octree representation and the discretized normal values for performing a point cloud operation.

### Claim 2 (depends on 1)

The computer-implemented method of claim 1, wherein the set of discretized normal values and the compressed octree representation takes less storage on an autonomous vehicle than the 3D point cloud representation of the region and the discretized normal values associated with each point of the 3D point cloud representation.

### Claim 3 (depends on 1)

The computer-implemented method of claim 1, wherein the point cloud operation is performed directly on the compressed octree representation at an autonomous vehicle without having to decompress the compressed octree representation.

### Claim 4 (depends on 1)

The computer-implemented method of claim 1, wherein:
prior to each normal value being discretized, the normal value is stored as three floating point values or three integer values; and
after each normal value is discretized, the normal value is stored as three values each having a size of three bits.

### Claim 5 (depends on 1)

The computer-implemented method of claim 1, wherein discretizing the normal values comprises:
determining a target number of discretized normal values for the set of discretized normal values;
identifying normal values that are most likely to be used by each point of the 3D point cloud representation using a statistical distribution of the normal values of the points of the 3D point cloud representation; and
selecting a set of discretized normals that minimizes a total storage of the discretized normal values.

### Claim 6 (depends on 1)

The computer-implemented method of claim 1, wherein each node of the compressed octree representation has up to eight child nodes.

### Claim 7 (depends on 6)

The computer-implemented method of claim 6, wherein each node of the compressed octree representation stores a bit indicating whether a particular child_node is present.

### Claim 8 (depends on 1)

The computer-implemented method of claim 1, further comprising:
analyzing each of the points of the 3D point cloud representation to determine whether storing a normal value for the point helps with localization; and
in response to determining that storing a normal value for any point does not help with localization, not storing the normal value for the point in the compressed octree representation.

### Claim 9 (depends on 1)

The computer-implemented method of claim 1, wherein:
the request is received from an autonomous vehicle;
the set of discretized normal values and the compressed octree representation are transmitted to the autonomous vehicle; and
the point cloud operation comprises performing localization of the autonomous vehicle.

### Claim 10

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 three-dimensional (3D) point cloud representation of a region comprising points, each point of the 3D point cloud representation associated with a normal value of a surface corresponding to the point;
storing a set of discretized normal values;
for each point of the 3D point cloud representation, associating the point with one of the discretized normal values in the set of discretized normal values by mapping the normal value associated with the point to the one of the discretized normal values in the set of discretized normal values;
storing a compressed octree representation comprising nodes, at least a subset of the nodes of the compressed octree representation storing an index value identifying the mapped discretized normal value for points of the 3D point cloud representation represented by the node;
receiving, at an online system, a request for a high definition (HD) map data of the region;
in response to the request, transmitting, from the online system, the set of discretized normal values and the compressed octree representation; and
using the compressed octree representation and the discretized normal values for performing, at the autonomous vehicle, a point cloud operation.

### Claim 11 (depends on 10)

The one or more non-transitory computer-readable media of claim 10, wherein the set of discretized normal values and the compressed octree representation takes less storage on an autonomous vehicle than the 3D point cloud representation of the region and the discretized normal values associated with each point of the 3D point cloud representation.

### Claim 12 (depends on 10)

The one or more non-transitory computer-readable media of claim 10, wherein the point cloud operation is performed directly on the compressed octree representation at an autonomous vehicle without having to decompress the compressed octree representation.

### Claim 13 (depends on 10)

The one or more non-transitory computer-readable media of claim 10, wherein:
prior to each normal value being discretized, the normal value is stored as three floating point values or three integer values; and
after each normal value is discretized, the normal value is stored as three values each having a size of three bits.

### Claim 14 (depends on 10)

The one or more non-transitory computer-readable media of claim 10, wherein discretizing the normal values comprises:
determining a target number of discretized normal values for the set of discretized normal values;
identifying normal values that are most likely to be used by each point of the 3D point cloud representation using a statistical distribution of the normal values of the points of the 3D point cloud representation; and
selecting a set of discretized normals that minimizes a total storage of the discretized normal values.

### Claim 15 (depends on 10)

The one or more non-transitory computer-readable media of claim 10, wherein each node of the compressed octree representation has up to eight child nodes.

### Claim 16 (depends on 15)

The one or more non-transitory computer-readable media of claim 15, wherein each node of the compressed octree representation stores a bit indicating whether a particular child_node is present.

### Claim 17 (depends on 10)

The one or more non-transitory computer-readable media of claim 10, wherein the operations further comprise:
analyzing each of the points of the 3D point cloud representation to determine whether storing a normal value for the point helps with localization; and
in response to determining that storing a normal value for any point does not help with localization, not storing the normal value for the point in the compressed octree representation.

### Claim 18 (depends on 10)

The one or more non-transitory computer-readable media of claim 10, wherein:
the request is received from an autonomous vehicle;
the set of discretized normal values and the compressed octree representation are transmitted to the autonomous vehicle; and
the point cloud operation comprises performing localization of the autonomous vehicle.

### Claim 19

A computer system comprising:
one or more processors; and
one or more non-transitory computer readable media storing instructions that in response to being executed by the one or more processors, cause the computer system to perform operations, the operations comprising:
receiving a three-dimensional (3D) point cloud representation of a region comprising points, each point of the 3D point cloud representation associated with a normal value of a surface corresponding to the point;
storing a set of discretized normal values;
for each point of the 3D point cloud representation, associating the point with one of the discretized normal values in the set of discretized normal values by mapping the normal value associated with the point to the one of the discretized normal values in the set of discretized normal values;
storing a compressed octree representation comprising nodes, at least a subset of the nodes of the compressed octree representation storing an index value identifying the mapped discretized normal value for points of the 3D point cloud representation represented by the node;
receiving, at an online system, a request for a high definition (HD) map data of the region;
in response to the request, transmitting, from the online system, the set of discretized normal values and the compressed octree representation; and
using the compressed octree representation and the discretized normal values for performing, at the autonomous vehicle, a point cloud operation.

### Claim 20 (depends on 19)

The computer system of claim 19, wherein the set of discretized normal values and the compressed octree representation takes less storage on an autonomous vehicle than the 3D point cloud representation of the region and the discretized normal values associated with each point of the 3D point cloud representation.

### Claim 21 (depends on 19)

The computer system of claim 19, wherein the point cloud operation is performed directly on the compressed octree representation at an autonomous vehicle without having to decompress the compressed octree representation.

### Claim 22 (depends on 19)

The computer system of claim 19, wherein:
prior to each normal value being discretized, the normal value is stored as three floating point values or three integer values; and
after each normal value is discretized, the normal value is stored as three values each having a size of three bits.

### Claim 23 (depends on 19)

The computer system of claim 19, wherein discretizing the normal values comprises:
determining a target number of discretized normal values for the set of discretized normal values;
identifying normal values that are most likely to be used by each point of the 3D point cloud representation using a statistical distribution of the normal values of the points of the 3D point cloud representation; and
selecting a set of discretized normals that minimizes a total storage of the discretized normal values.

### Claim 24 (depends on 19)

The computer system of claim 19, wherein each node of the compressed octree representation has up to eight child nodes.

### Claim 25 (depends on 24)

The computer system of claim 24, wherein each node of the compressed octree representation stores a bit indicating whether a particular child_node is present.

### Claim 26 (depends on 19)

The computer system of claim 19, wherein the operations further comprise:
analyzing each of the points of the 3D point cloud representation to determine whether storing a normal value for the point helps with localization; and
in response to determining that storing a normal value for any point does not help with localization, not storing the normal value for the point in the compressed octree representation.

### Claim 27 (depends on 19)

The computer system of claim 19, wherein:
the request is received from an autonomous vehicle;
the set of discretized normal values and the compressed octree representation are transmitted to the autonomous vehicle; and
the point cloud operation comprises performing localization of the autonomous vehicle.
