BACKGROUND

Technical Field

This disclosure relates generally to compression and decompression of point clouds or other three-dimensional representations comprising a plurality of points, each having associated attribute information.

Description of the Related Art

Various types of sensors, such as light detection and ranging (LIDAR) systems, 3-D-cameras, 3-D scanners, etc. may capture data indicating positions of points in three dimensional space, for example positions in the X, Y, and Z planes. Also, such systems may further capture attribute information in addition to spatial information for the respective points, such as color information (e.g. RGB values), intensity attributes, reflectivity attributes, motion related attributes, modality attributes, or various other attributes. In some circumstances, additional attributes may be assigned to the respective points, such as a time-stamp when the point was captured. Points captured by such sensors may make up a “point cloud” or other three-dimensional representation comprising a set of points each having associated spatial information and one or more associated attributes. In some circumstances, such a set of points may include thousands of points, hundreds of thousands of points, millions of points, or even more points. Also, in some circumstances, such a set of points may be generated, for example in software, as opposed to being captured by one or more sensors. In either case, such sets of points, such in a point cloud, may include large amounts of data and may be costly and time-consuming to store and transmit.

SUMMARY OF EMBODIMENTS

In some embodiments, a system includes one or more sensors configured to capture points that collectively make up a set of points for which attribute values are to be compressed, such as points of a point cloud, vertices of a mesh, etc. Each of the points comprises spatial information identifying a spatial location of the respective point in 3D space and attribute information defining one or more attributes associated with the respective point.

The system also includes an encoder configured to compress the attribute information for the points. To compress the attribute information, the encoder is configured to organize the points of the set of points into an order based on respective spatial positions of the plurality of points in 3D space. For example, in some embodiments, a space filling curve may be used to determine an ordering of the points. The encoder is also configured to perform one or more transforms on the attribute values of the points in order to compress the attribute information. For example, the encoder may utilize a prediction based transform, a lifting scheme transform, a region-adaptive hierarchical transform, or other suitable transform to compact energy from the source signal by removing redundant low frequency information, and optionally quantizing high frequency information.

As an example, in a prediction based transform an attribute value is assigned to at least one point of the set of points based on the attribute information included in the captured set of points, such as a captured point cloud. Additionally, to perform the prediction based transform, the encoder is configured to, for each of respective other ones of the points of the set of points, identify a set of neighboring points, determine a predicted attribute value for the respective point based, at least in part, on predicted or assigned attributes values for the neighboring points, and determine, based, at least in part, on comparing the predicted attribute value for the respective point to the attribute information for the point included in the captured set of points, an attribute correction value for the point. The encoder is further configured to encode the assigned attribute value for the at least one point and data indicating, for the respective other ones of the points, the respective determined attribute correction values. The determined attribute correction values are the result of applying the prediction transform and are referred to herein as attribute coefficients/transformed attribute values. As mentioned above, in some embodiments, other transforms may be applied to generate attribute coefficients/transformed attribute values, such as a lifting transform or region-adaptive hierarchical transform (RAHT), as a few examples.

In some embodiments, an encoder is further configured to determine, for each point of the set of points, whether respective values of one or more transformed attribute values associated with the respective point comprise one or more significant values or do not comprise a significant value. For example, some attributes such as color may be represented as an attribute tuple for each point, wherein the attribute tuple includes attribute values for multiple color components associated with the respective point, such as red, blue, and green color values. If the transformed color values (e.g. attribute correction values resulting from a prediction based transform or other transform) have significant values, such as a non-zero correction value for red, blue, or green, the points may be determined to have significant transformed attribute values. However, if all the transformed color values for a given point have non-significant values, such as correction values for red, blue, and green all equal to zero, the given point may be determined to have non-significant transformed attribute values. Note, that in various embodiments other thresholds, other than greater than zero, may be used to distinguish between significant and non-significant transformed attribute values.

The encoder is further configured to assign to points that have transformed attribute values that comprise one or more significant values a first binary flag value and assign to points that have transformed attribute values that do not comprise a significant value a second binary flag value. Additionally, the encoder is configured to evaluate the binary flag values assigned to the points of the set of points to identify consecutive points assigned the first binary flag value and consecutive points assigned the second binary flag value. Also, for respective runs of points having the first binary flag value as a same assigned binary flag value and for respective runs of points having the second binary flag value as a same assigned binary flag value, the encoder is configured to encode a value indicating a length of the respective run using a variable-length encoding technique.

In some embodiments, the variable length encoding technique used, may be a kthorder exponential Golomb encoding technique. In such embodiments, the encoder is further configured to maintain a first state for determining a value of k for respective runs having the first binary flag value as a same assigned binary flag value and maintain a second state for determining a value of k for respective runs having the second binary flag value as a same assigned binary flag value. Additionally, the encoder is configured to maintain contexts and associated probabilities for determining pre-fix portions of Golomb code words for the kthorder Golomb encoding technique, wherein whether a run-length value being encoded is for a respective run having the first binary flag value as a same assigned binary flag value or the second binary flag value as a same assigned binary flag value is one of the contexts that is maintained.

In some embodiments, a system includes a decoder configured to receive a sequence of encoded run-length values, encoded using a variable length encoding technique, such as is included in compressed attribute information generated by an encoder as described above. The decoder is configured to decode the encoded values using a variable length decoding technique to determine respective run lengths of the respective runs. Also, for respective runs having a first binary flag value as a same assigned binary flag value, the decoder is configured to mark the points associated with the respective runs for further processing to determine attribute values for the points of the respective runs and for other respective runs having the second binary flag value as a same assigned binary flag value, the decoder is configured to assign a zero value to the attributes coefficients for the points associated with the other respective runs.

The decoder may further process the marked points and include the attribute coefficients determined for the marked points along with the zero value attribute coefficients for the other points in a set of attribute information for set of points whose attribute information is being decompressed.

In some embodiments, wherein a prediction based transform is used, the attribute information resulting from said marking and said assigning zero values may further comprise at least one assigned attribute value for at least one point of the set of points and the determined attribute coefficients/transformed attribute values, for other points of the set of points. The determined attribute coefficients/transformed attribute values may be respective attribute correction values for respective attributes of the other points. The decoder may further be configured to, for each of respective other ones of the points of the set of points other than the at least one point with assigned attribute values, identify a set of neighboring points to a point being evaluated, determine a predicted attribute value for the point being evaluated based, at least in part, on predicted or assigned attribute values for the neighboring points, and adjust the predicted attribute value for the point being evaluated based, at least in part, on an attribute correction value for the point included in the compressed attribute information. The decoder may be further configured to provide attribute information for a decompressed point cloud that is being reconstructed, the attribute information comprising the at least one assigned attribute value for the at least one point and the adjusted predicted attribute values for the other ones of the points.

In some embodiments, a non-transitory computer-readable medium stores program instructions, that when executed by one or more processors, cause the one or more processors to implement an encoder or decoder as described herein.

In some embodiments, a method comprises steps for encoding or decoding a set of points as performed by the encoder and/or the decoder, as described herein.

