System and methods for encoding octree structured point cloud data using an entropy model

1. A computer-implemented method for generating entropy encoded representations of point cloud data, the method comprising:

receiving, by a computing system including one or more processors, point cloud data for a three-dimensional space;

generating, by the computing system, a tree-based data structure from the point cloud data, the tree-based data structure comprising a plurality of nodes organized in a hierarchical structure, each node representing a particular area of the three-dimensional space;

generating, by the computing system, a serial representation of the data by traversing the tree-based data structure and adding a plurality of symbols to a serial data structure, each symbol representing a node in the tree-based data structure;

for each respective node represented by a symbol in the serial representation:

determining, by the computing system, contextual information for the respective node,

generating, by the computing system and using the contextual information as input to a machine-learned model, a statistical distribution associated with the respective node, wherein the machine-learned model is a multi-layer perceptron and intermediate layers in the multi-layer perceptron produce an intermediate representation of the contextual information that is usable as input to subsequent layers; and

generating, by the computing system, a compressed representation of the symbol associated with the respective node by encoding the symbol using the statistical distribution for the respective node, and

generating, by the computing system, a compressed bitstream by sequentially ordering a plurality of compressed representations associated with the plurality of symbols.

2. The computer-implemented method of claim 1 , wherein the point cloud data is generated via a LIDAR sensor associated with an autonomous vehicle, and wherein the method further comprises:

accessing, by the computing system, the compressed bitstream;

identifying, by the computing system, one or more objects within a surrounding environment of the autonomous vehicle;

generating, by the computing system, a trajectory for the autonomous vehicle based at least in part on the one or more objects; and

implementing, by the computing system, a motion control for the autonomous vehicle to travel in accordance with the trajectory.

3. The computer-implemented method of claim 1 , wherein the tree-based data structure is structured such that each node in the tree-based data structure has a parent node and one or more children nodes.

4. The computer-implemented method of claim 3 , wherein the tree-based data structure is an octree and is structured such that each node has up to eight child nodes.

5. The computer-implemented method of claim 1 , wherein a respective node is associated with an area in the point cloud data and any child nodes of the respective node are associated with a sub-area within the area in the point cloud data associated with the respective node.

6. The computer-implemented method of claim 1 , wherein generating a tree-based data structure from the point cloud data comprises:

establishing, by the computing system, an initial node representing the three-dimensional space represented by the point cloud data;

dividing, by the computing system, the three-dimensional space into eight sub-areas; and

for each respective sub-area:

determining, by the computing system, whether the respective sub-area includes at least one point in the point cloud data;

in response to determining that the sub-area includes at least one point in the point cloud data, adding, by the computing system, a node representing the respective sub-area as a child node of the initial node in the tree-based data structure;

determining, by the computing system, whether the respective sub-area includes more than one point in the point cloud data; and

in response to determining that the sub-area includes at least on point in the point cloud data, recursively subdividing, by the computing system, the respective sub-areas of the child nodes until no resulting child nodes are associated with a sub-area that represent more than one point in the point cloud data.

7. The computer-implemented method of claim 1 , wherein a symbol is an eight-bit value representing an occupancy of eight sub-areas within the area represented by the respective node.

8. The computer-implemented method of claim 1 , wherein contextual information includes at least one of: a location represented by the respective node, an index of the respective node, a level of the respective node in the tree-based structure, or occupancy data of the parent node of the respective node.

9. The computer-implemented method of claim 1 , wherein multi-layer perceptron includes a plurality of levels and generating, using the contextual information as input to a machine-learned model, a statistical distribution associated with the respective node further comprises:

aggregating, by the computing system, an intermediate representation of contextual information of at least one parent node of the respective node with intermediate representations of the respective node as input to a layer in the multi-layer perceptron.

10. The computer-implemented method of claim 9 , wherein the multi-layer perceptron comprises three layers.

11. The computer-implemented method of claim 1 , wherein encoding the respective symbol using the statistical distribution comprises:

generating, by the computing system, a coded version of the respective symbol using an entropy encoder.

12. The computer-implemented method of claim 11 , wherein the entropy encoder can use an adaptive arithmetic encoding algorithm.

13. A computing system comprising:

one or more processors;

a memory comprising one or more computer-readable media, the memory storing computer-readable instructions that when executed by the one or more processors cause the one or more processors to perform operations comprising:

receiving point cloud data for a three-dimensional space;

generating a tree-based data structure from the point cloud data, the tree-based data structure comprising a plurality of nodes organized in a hierarchical structure, each node representing a particular area of the three-dimensional space;

generating a serial representation of the data by traversing the tree-based data structure and adding a plurality of symbols to a serial data structure, each symbol representing a node in the tree-based data structure;

for each respective node represented by a symbol in the serial representation:

determining contextual information for the respective node;

generating, using the contextual information as input to a machine-learned model, a statistical distribution associated with the respective node, wherein the machine-learned model is a multi-layer perceptron and intermediate layers in the multi-layer perceptron produce an intermediate representation of the contextual information that is usable as input to subsequent layers; and

generating a compressed representation of the symbol associated with the respective node by encoding the symbol using the statistical distribution for the respective node; and

generating a compressed bitstream by sequentially ordering a plurality of compressed representations associated with the plurality of symbols.

14. The computing system of claim 13 , the operations further comprising:

in response to a request to analyze the compressed bitstream, decoding the compressed bitstream to extract the point cloud data.

15. The computing system of claim 13 , wherein the point cloud data include intensity values for points in the point cloud data.

16. The computing system of claim 13 , wherein the contextual information for the respective node can include information based on point cloud data from a previous time period.

17. A non-transitory computer-readable medium storing instruction that, when executed by one or more computing devices, cause the one or more computing devices to perform operations, the operations comprising:

receiving point cloud data for a three-dimensional space;

generating a first tree-based data structure from the point cloud data, the first tree-based data structure comprising a plurality of nodes organized in a hierarchical structure, each node representing a particular area of the three-dimensional space;

generating a serial representation of the data by traversing the first tree-based data structure and adding a plurality of symbols to a serial data structure, each symbol representing a node in the tree-based data structure;

for each respective node represented by a symbol in the serial representation:

determining contextual information for the respective node;

generating, using the contextual information as input to a machine-learned model, a statistical distribution associated with the respective node, wherein the machine-learned model is a multi-layer perceptron and intermediate layers in the multi-layer perceptron produce an intermediate representation of the contextual information that is usable as input to subsequent layers; and

generating a compressed representation of the symbol associated with the respective node by encoding the symbol using the statistical distribution for the respective node; and

generating a compressed bitstream by sequentially ordering a plurality of compressed representations associated with the plurality of symbols;

decoding the plurality of compressed representations associated with the plurality of symbols, wherein decoding comprises:

for each respective compressed representation associated with the plurality of symbols:

determining contextual information for the respective compressed representation;

generating, using the contextual information as input to a machine-learned model, a statistical distribution associated with the respective compressed representation; and

generating an uncompressed symbol based on the respective compressed representation by decoding the compressed representation using the statistical distribution for the compressed representation; and

generating a second tree-based structure using a plurality of uncompressed symbols as nodes such that the second tree-based structure is identical to the first tree-based structure.

18. The non-transitory computer-readable medium of claim 17 , wherein a symbol is an eight-bit value representing an occupancy of eight sub-areas within the area represented by the respective node.