HIERARCHICAL POINT CLOUD COMPRESSION WITH SMOOTHING

• US 20190311501A1
• Filed: 04/10/2019
• Published: 10/10/2019
• Est. Priority Date: 04/10/2018
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Mammou, Khaled, Tourapis, Alexandros, Kim, Jungsun, Robinet, Fabrice A., Valentin, Valery G., Su, Yeping
• Granted Patent: US 10,909,727 B2
• Time in Patent Office: Days
• CPC Class Codes: G06T 17/00 Three dimensional [3D] modelling, e.g. data description of 3D objects
• CPC Class Codes: G06T 2210/36 Level of detail
• CPC Class Codes: G06T 9/001 Model-based coding, e.g. wire frame

Abstract

A system comprises an encoder configured to compress attribute information for a point cloud and/or a decoder configured to decompress compressed attribute for the point cloud. To compress the attribute information, multiple levels of detail are generated based on spatial information. Also, attribute values are predicted based on the level of details. A decoder follows a similar prediction process based on level of details. Also, attribute correction values may be determined to correct predicted attribute values and may be used by a decoder to decompress a point cloud compressed using level of detail attribute compression. In some embodiments, an update operation is performed to smooth attribute correction values taking into account an influence factor of respective points in a given level of detail on attributes in other levels of detail.

Claims

1. A system comprising:

one or more sensors configured to capture a plurality of points that make up a point cloud, wherein respective ones of the points comprise spatial information for the point and attribute information for the point; and

an encoder configured to;

determine a plurality of levels of detail for the point cloud, wherein different levels of detail include different sub-sets of the plurality of points that make up the point cloud;

assign an attribute value to at least one point of a first level of detail based on the attribute information included in the captured point cloud for the at least one point;

for respective points of the other points of the first level of detail, and points of one or more additional ones of the levels of detail, determine a predicted attribute value for the respective point based on predicted or assigned attributes values for neighboring points in a same level of detail as the point;

for respective points of the other points of the first level of detail, and the points of the one or more additional levels of detail, determine an attribute correction value for the respective point, based on comparing a predicted attribute value for the respective point to the attribute information for the point included in the captured point cloud that corresponds with the respective point;

apply an update operation to smooth the attribute correction values, wherein the update operation takes into account relative influences of the attributes of the points of a given level of detail on attribute values of points included in other levels of detail; and

encode the assigned attribute value and the updated attribute correction values for first level of detail and the one or more additional levels of detail.

2. The system of claim 1, wherein the encoder is configured to determine the update operation based on edge distances of a graph for points of more than one of the levels of detail, wherein:

points of a same level of detail and points of one or more other levels of detail represent vertices in the graph;

the edge distances represent distances between a vertex corresponding to a respective point for which an attribute value is being predicted and vertices for the neighboring points being used in predicting the attribute value for the respective point; and

attribute values of the neighboring points with shorter edges to the respective point are given a greater weight than attribute values of points with longer edges to the respective point.

3. The system of claim 2, wherein the relative influences taken into account by the update operation are based, at least in part, on weights of edges across multiple levels of detail along a path from a point in a lower level of detail to one or more points in a higher level of detail.

4. The system of claim 3, wherein the weights of edges for a given point are determined based on a sum of the squared errors of attribute values for points in other levels of detail with a path of edges connecting to the given point, wherein the sum of the squared errors is calculated using errors in the attribute values for the points in the other levels of detail resulting for a perturbation of the given point by a given amount.

5. The system of claim 4, wherein the encoder is configured to disregard, when determining the weights of edges for the given point, points in the other levels of detail with a path of edge distances that adds up to be greater than a threshold distance from the given point.

6. The system of claim 3, wherein the weights of edges for the points are determined recursively based on assigning an initial same edge weight to the points of the point cloud and iteratively updating the edge weights by traversing the points in an order from highest level of detail to lowest level of detail, wherein the update is determined based on applying an update function that takes into account the edge weights of a set of neighboring points that neighbor a point for which the edge weight is being updated.

7. The system of claim 1, wherein the encoder is configured to utilize a lifting scheme to determine the update operation to be applied to the attribute correction values.

8. The system of claim 1, wherein the update operation comprises:

separating attribute values of the points of the point cloud into a) attribute values for points of a down-sampled level of detail and b) attribute values for points of a higher level of detail comprising points of the point cloud not included in the down-sampled level of detail;

predicting the attribute values for the points of the higher level of detail based on the attribute values for the points of the down-sampled level of detail;

determining prediction residuals by comparing the attribute values for the points of the higher level of detail predicted from the down-sampled level of detail points to the attribute values of the points of the higher level of detail that were separated out via the separating; and

adjusting the attribute correction values of the down-sampled level of detail points based on the determined prediction residuals.

9. A method comprising:

determining a plurality of levels of detail for a captured or generated point cloud, wherein different levels of detail include different sub-sets of a plurality of points that make up the captured or generated point cloud;

assigning an attribute value to at least one point of a first level of detail based on attribute information included in the captured or generated point cloud for the at least one point;

for respective ones of points of the first level of detail, or points of one or more additional ones of the levels of detail, determining predicted attribute values for the respective points based on predicted or assigned attributes values for neighboring points of the respective point;

for the respective ones of the points of the first level of detail, or the points of one or more of the additional levels of detail, determining respective attribute correction values for the respective points, based on comparing the predicted attribute values for the respective points to the attribute information for corresponding points included in the captured or generated point cloud; and

applying an update operation to smooth the attribute correction values, wherein the update operation takes into account relative influences of the attributes of the points of a given level of detail on attribute values of the points in other levels of detail; and

encoding the assigned attribute value and the updated attribute correction values for first level of detail and the one or more additional levels of detail.

10. The method of claim 9, wherein applying the update operation comprises:

separating attribute values of the points of the point cloud into a) attribute values for points of a down-sampled level of detail and b) attribute values for points of a higher level of detail comprising points of the point cloud not included in the down-sampled level of detail;

predicting the attribute values for the points of the higher level of detail based on the attribute values for the points of the down-sampled level of detail;

determining prediction residuals by comparing the attribute values for the points of the higher level of detail predicted from the down-sampled level of detail points to the attribute values of the points of the higher level of detail that were separated out via the separating; and

adjusting the attribute correction values of the down-sampled level of detail points based on the determined prediction residuals.

11. The method of claim 10, wherein the predicted attribute values are predicted based on

edge distance weightings for edges between a vertex corresponding to a respective point for which an attribute value is being predicted and vertices for the neighboring points being used in predicting the attribute value for the respective point,

wherein attribute values of the neighboring points with shorter edges to the respective point are given a greater edge distance weighting than attribute values of points with longer edges to the respective point.

12. The method of claim 11, wherein the predicting of the update operation is based, at least in part, on the edge distance weightings for the points of the point cloud.

13. The method of claim 11, wherein quantization is applied to the edge distance weightings, and wherein edge distance weightings with less weights are quantized to a greater degree than edge distance weightings with greater weights.

14. The method of claim 13, wherein the quantization differs based on edge distance weighting by an exponential relationship known by an encoder performing the encoding and a decoder that decodes the encoded point cloud.

15. The method of claim 13, wherein an exponential coefficient for determining the quantization is included in a bit stream encoded by an encoder performing the encoding and received in the bit stream by a decoder that decodes the encoded point cloud.

16. The method of claim 11, wherein the edge distance weightings are represented as fixed-point numbers, wherein an encoder performing the encoding or a decoder that decodes the encoded point cloud utilizes a look-up table to perform non-linear operations for the fixed-point numbers.

17. A non-transitory computer-readable medium storing program instructions, that when executed by one or more processors, cause the one or more processors to:

receive compressed attribute information for a point cloud comprising at least one assigned attribute value for at least one point of a first level of detail of the point cloud and data indicating attribute correction values for attributes of the other points of the point cloud in the first level of detail and in one or more additional levels of detail;

determine attribute information for a decompressed point cloud comprising the first level of detail, wherein said determining the attribute information comprises performing an update operation to adjust for attribute value smoothing applied at an encoder; and

update the decompressed point cloud to include attribute information for additional sub-sets of points included in the one or more additional levels of detail, wherein said updating comprises determining attribute values for the sub-sets of points in the one or more additional levels of detail and performing an update operation to adjust for attribute value smoothing applied at the encoder for the points in the one or more additional levels of detail.

18. The non-transitory computer-readable medium of claim 17, wherein to determine the attribute information for the first level of detail of the decompressed point cloud, or the one or more additional levels of detail, the program instructions, when executed on the one or more processors, cause the one or more processors to:

assign the attribute value for the at least one point of the point cloud to a corresponding point of the decompressed point cloud;

for respective points of the other points of the first level of detail of the decompressed point cloud, or points of the one or more additional levels of detail of the decompressed point cloud, determine a predicted attribute value for the respective point based on predicted or assigned attributes values for neighboring points in a same level of detail as the point;

apply an update operation to smooth the predicted attribute values, wherein the update operation takes into account relative influences of the attributes of the points of a given level of detail on attribute values of points included in other levels of detail; and

for respective points of the other points of the first level of detail, and the points of the one or more additional levels of detail, correct the updated predicated attribute value for the respective point based on the attribute correction value for the respective point included in the received compressed attribute information for the point cloud.

19. The non-transitory computer-readable medium of claim 18, wherein the predicted attribute values are determined based on edge distances of a graph for points of the point cloud, wherein:

edge distances represent distances between a vertex corresponding to a respective point for which an attribute value is being predicted and vertices for the neighboring points being used in predicting the attribute value for the respective point; and

attribute values of the neighboring points with shorter edges to the respective point are given a greater weight than attribute values of points with longer edges to the respective point.

20. The non-transitory computer-readable medium of claim 19, wherein, when determining the edge weights for the respective point, points in other levels of detail with a path of edge distances that adds up to be greater than a threshold distance are not taken into account.