STORING NORMALS IN COMPRESSED OCTREES REPRESENTING HIGH DEFINITION MAPS FOR AUTONOMOUS VEHICLES

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.

2 . 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.

3 . 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.

4 . 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.

5 . 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.

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

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

8 . 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.

9 . 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.

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.

11 . 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.

12 . 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.

13 . 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.

14 . 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.

15 . 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.

16 . 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.

17 . 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.

18 . 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.

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.

20 . 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.

21 . 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.

22 . 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.

23 . 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.

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

25 . 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.

26 . 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.

27 . 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.