Region-adaptive hierarchical transform and entropy coding for point cloud compression, and corresponding decompression

Patent metadata

Field	Value
Publication number	US-10223810-B2
Application number	US-201615168016-A
Country	US
Kind code	B2
Filing date	May 28, 2016
Priority date	May 28, 2016
Publication date	Mar 5, 2019
Grant date	Mar 5, 2019

Abstract

Innovations in compression and decompression of point cloud data are described. For example, an encoder is configured to encode point cloud data, thereby producing encoded data. In particular, the encoder applies a region-adaptive hierarchical transform (“RAHT”) to attributes of occupied points, thereby producing transform coefficients. The encoder can also quantize the transform coefficients and perform adaptive entropy coding of the quantized transform coefficients. For corresponding decoding, a decoder is configured to decode the encoded data to reconstruct point cloud data. In particular, the decoder applies an inverse RAHT to transform coefficients for attributes of occupied points. The decoder can also perform adaptive entropy decoding and inverse quantization of the quantized transform coefficients. The adaptive entropy coding/decoding can use estimates of the distribution of values for the quantized transform coefficients. In this case, the encoder calculates the estimates and signals them to the decoder.

First claim

We claim:

1. A computer system comprising:
an input buffer configured to receive point cloud data comprising multiple points in three-dimensional (“3D”) space, each of the multiple points being associated with an indicator of whether the point is occupied and, if the point is occupied, an attribute of the occupied point;
an encoder configured to encode the point cloud data, thereby producing encoded data, by performing operations that include:
applying a region-adaptive hierarchical transform (“RAHT”) to attributes of occupied points among the multiple points, thereby producing transform coefficients, wherein the applying the RAHT includes, at a given level of a hierarchy for the point cloud data, for each given group of one or more groups of points at the given level:
transforming any attributes of occupied points of the given group, thereby producing one or more values for the given group, the one or more values including any of the transform coefficients that are associated with the given group at the given level; and
if the given level is not bottom level of the hierarchy, reserving one or more values for the given group, for use as an attribute of an occupied point at a next lower level than the given level in the hierarchy, in successive application of the RAHT at the next lower level; and

an output buffer configured to store the encoded data as part of a bitstream for output.

2. The computer system of claim 1 , wherein, if the given level is not top level of the hierarchy, each of the any attributes of occupied points of the given group is a reserve value from a next higher level than the given level in the hierarchy.

3. The computer system of claim 1 , wherein, for two adjacent points of the given group, the transforming includes:
if both of the two adjacent points are occupied, converting the attributes of the two adjacent points into a lowpass coefficient and a highpass coefficient, wherein the highpass coefficient is one of the transform coefficients, and wherein the lowpass coefficient is the reserved value or is an intermediate attribute for additional transforming at the given level; and
if only one of the two adjacent points is occupied, passing through the attribute of the occupied point to be the reserved value or the intermediate attribute.

4. The computer system of claim 1 , wherein the transforming includes applying a weighted transform, and wherein weights of the weighted transform depend at least in part on counts of occupied points that contribute to the occupied points of the given group.

5. The computer system of claim 1 , wherein the transforming includes iteratively applying a weighted transform along each of three axes in the 3D space.

6. The computer system of claim 1 , wherein the hierarchy includes a bottom level, zero or more intermediate levels, and the top level, and wherein the applying the RAHT includes:
for each of the top level and zero or more intermediate levels, as the given level, performing the transforming and the reserving for each given group of the one or more groups of points at the given level, thereby providing at least one reserved value for the next lower level and providing any of the transform coefficients that are associated with the given level; and
at the bottom level of the hierarchy, for a group of points at the bottom level, transforming any attributes of occupied points of the group at the bottom level, thereby producing one or more of the transform coefficients.

7. The computer system of claim 1 , wherein the applying the RAHT includes using the indicators to determine which of the multiple points, respectively, are occupied.

8. The computer system of claim 1 , wherein, to encode the point cloud data, the operations further include:
quantizing the transform coefficients; and
entropy coding the quantized transform coefficients.

9. The computer system of claim 8 , wherein, to encode the point cloud data, the operations further include:
splitting the quantized transform coefficients between multiple buckets; and
for each of at least some of the multiple buckets, calculating an estimate of distribution of values of the quantized transform coefficients in the bucket.

10. The computer system of claim 9 , wherein the quantized transform coefficients are split between the multiple buckets depending on weights associated with the quantized transform coefficients, respectively, the weights depending at least in part on counts of occupied points that contribute to the quantized transform coefficients.

11. The computer system of claim 9 , wherein, to encode the point cloud data, the operations further include:
quantizing the estimates;
entropy coding the quantized estimates; and
reconstructing the estimates, wherein the reconstructed estimates are used by the entropy coding of the quantized transform coefficients.

12. The computer system of claim 8 , wherein the entropy coding of the quantized transform coefficients is arithmetic coding or run-length Golomb-Rice coding.

13. The computer system of claim 1 , wherein the attribute is selected from the group consisting of:
a sample value defining, at least in part, a color associated with the occupied point;
an opacity value defining, at least in part, an opacity associated with the occupied point;
a specularity value defining, at least in part, a specularity coefficient associated with the occupied point;
a surface normal value defining, at least in part, direction of a flat surface associated with the occupied point;
a motion vector defining, at least in part, motion associated with the occupied point; and
a light field defining, at least in part, a set of light rays passing through or reflected from the occupied point.

14. The computer system of claim 1 , wherein, to encode the point cloud data, the operations further include applying octtree compression to the indicators of whether the multiple points, respectively, are occupied.

15. One or more computer-readable media storing computer-executable instructions for causing a computer system, when programmed thereby, to perform operations comprising:
receiving encoded data as part of a bitstream;
decoding the encoded data to reconstruct point cloud data, the point cloud data comprising multiple points in three-dimensional (“3D”) space, each of the multiple points being associated with an indicator of whether the point is occupied and, if the point is occupied, an attribute of the occupied point, wherein the decoding the encoded data includes:
applying an inverse region-adaptive hierarchical transform (“RAHT) to transform coefficients for attributes of occupied points among the multiple points, wherein the applying the inverse RAHT includes, at a given level of a hierarchy for the point cloud data, for each given group of one or more groups of points at the given level:
inverse transforming one or more values for the given group, thereby producing any attributes of occupied points of the given group, wherein the one or more values include any of the transform coefficients that are associated with the given group at the given level; and
if the given level is not top level of the hierarchy, reserving the any attributes of occupied points of the given group, for use as attributes at a next higher level than the given level in the hierarchy, in successive application of the inverse RAHT at the next higher level; and

storing the reconstructed point cloud data.

16. The one or more computer-readable media of claim 15 , wherein the inverse transforming includes applying a weighted inverse transform, wherein weights of th

Assignees

• Microsoft Technology Licensing Llc

Inventors

• Chou Philip A
• De Queiroz Ricardo L

Classifications

• G06T9/001 Primary

  Model-based coding, e.g. wire frame · CPC title

• H04N19/597

  specially adapted for multi-view video sequence encoding · CPC title

• H04N19/54

  using feature points or meshes · CPC title

• H04N19/61

  in combination with predictive coding · CPC title

• H03M7/3059

  Digital compression and data reduction techniques where the original information is represented by a subset or similar information, e.g. lossy compression · CPC title