CROSS-REFERENCE TO RELATED PATENT APPLICATIONS

The present application is a U.S. national stage application under 35 U.S.C. § 371 of PCT Application No. PCT/CN2018/086793, filed May 15, 2018, which claims priority to Chinese Patent Application No. 2018104128182, filed May 3, 2018. The disclosures of the aforementioned priority applications are incorporated herein by reference in their entireties.

TECHNICAL FIELD OF THE DISCLOSURE

The present disclosure belongs to the point cloud data processing field, relates to a point cloud data compression method, and particularly to a point cloud attribute compression method based on deleting 0 elements in a quantisation matrix.

BACKGROUND

A three-dimensional point cloud is an important manifestation of real-world digitization. With the rapid advancements of three-dimensional scanning devices (lasers, radars, etc.), the accuracy and resolution of a point cloud become higher. The high-precision point clouds are widely applied to the construction of urban digitized map and play a technical support role in numerous hot studies, such as the studies of smart city, unmanned driving, cultural relic protection and the like. The point cloud is obtained by sampling the object surface using a three-dimensional scanning device, and the number of points of one frame of point cloud is generally on the order of million, where each point includes geometric information and attribute information such as a color, a texture and the like, and the amount of data is very large. The large amount of data of the three-dimensional point cloud can be quite challenges for data storage, transmission and the like, so that point cloud compression is very necessary.

The point cloud compression is mainly divided into a geometric compression and an attribute compression, and the frameworks of existing point cloud attribute compression mainly comprise several types of methods as follows:

A. The compression method based on an octree decomposition and a DCT: performing a spatial decomposition on the point cloud by using an octree to obtain a coding block, then performing a depth preferential traversal on the tree, writing the traversed node color value into a two-dimensional JPEG table in a serpentine order, and encoding the obtained point cloud color table by using an existing JPEG encoder, where the JPEG encoder uses a DCT. Although this method uses the existing encoder and the calculation complexity thereof is low, the spatial correlation between two points is not fully utilized, and the compression performance needs to be improved;

B. The compression method based on an octree decomposition and a graph transformation: performing a spatial decomposition on a point cloud by using an octree, then dividing the decomposed spaces into a certain level to obtain a transformed block; forming a graph in each transformed block, connecting two points along any coordinate axis and the distance therebetween not more than 1 by one edge, where the weight of the edge is inversely proportional to its Euclidean distance; and carrying out a graph transformation on the attribute information of the node in the graph. Although the compression performance of this method is good, its operation complexity is higher, and its composition manner may give rise to a sub-graph problem, its efficiency of the graph transformation is affected, so there still remains room for improvement;

C. The compression method based on a KD tree decomposition and a graph transformation: performing a spatial decomposition on the point cloud by using a KD tree, and dividing the decomposed space into a certain depth to obtain a transformed block, where the number of points included in each transformed block is substantially the same; connecting every two points by one edge in the transformed block, where the weight of the edge is related to its Euclidean distance, and the set Euclidean distance threshold of the edge determines the sparsity of the graph; and then carrying out a graph transformation on the attribute information of the point in the graph. The sub-graph problem is thoroughly solved by this method, while the compression performance thereof is greatly improved on aforesaid two methods, but the operation complexity thereof is higher, and its performance needs to be improved.

SUMMARY

In order to further improve the performance of the above technology, under the condition that the calculation complexity is taken into consideration, 7 types of traversal sequences are employed at an encoding end of the point cloud attribute compression according to the present disclosure, which enables that the distribution of 0 elements in the data stream is more concentrated at the end thereof. The 0 elements at the end of the data stream are deleted, thus reducing the quantity of data that needs to be entropy encoded. At a decoding end, point cloud geometric information is incorporated to supplement the deleted 0 elements, thus restoring the quantisation matrix according to the traversal sequence, which enables the improving of compression performance without introducing new errors.

A technical proposal provided by the present disclosure is as follows:

The present disclosure provides a point cloud attribution compression method based on deleting 0 elements in a quantisation matrix; for a quantisation matrix in a point cloud attribute compression process, using an optimal traversal sequence at an encoding end to concentrate 0 elements at the end of a generated data stream and implementing an entropy encoding after deleting the 0 elements, reducing the data quantity of the data stream and reducing the code streams generated after encoding; at a decoding end, incorporating point cloud geometric information to restore the deleted 0 elements, ensuring that the present method does not introduce additional error; comprising the following steps:

1) Point Cloud Attribute Compression Encoding Process

Implementing a KD tree division on the point cloud data to be compressed based on the geometric information, where the blocks generated at the final layer of the KD tree division are point cloud coding blocks, generating a quantisation matrix by implementing an intra-frame prediction, a residual transformation, and a quantisation on the attribute information in each coding block.

2) Optimising the Traversal Sequence for a Quantisation Matrix at the Encoding End:

Applying 7 types of different traversal sequences to each quantisation matrix, transforming the two-dimensional matrix into a one-dimensional data stream, comparing the numbers of 0 elements appeared in succession at the end of the data streams, selecting the data stream in which the number of 0 elements appeared in succession at the end thereof is most as an optimal data stream, while recording the corresponding traversal pattern.

3) Deleting the 0 Elements at the End of the Data Stream:

Deleting all 0 elements appeared in succession at the end thereof after resulting in an optimal data stream, thus obtaining a clipped data stream, after implementing the same operations on all coding blocks, performing an entropy coding in a unified manner, thus resulting in a point cloud attribute compressed code stream.

4) Referring to the Geometric Information to Restore the Quantisation Matrix at a Decoding End:

Carrying out an entropy decoding on a code stream to obtain the clipped data stream at a decoding end, incorporating the point cloud geometric information to solve for the number of deleted 0 elements and implementing a supplement, thus resulting in an original data stream, restoring a two-dimensional quantisation matrix from the one-dimensional data stream according to the traversal sequence.

5) Point Cloud Attribute Compression Decoding Process:

Performing an inverse quantisation, an inverse transformation, and a prediction compensation on the restored quantisation matrix sequentially, thus obtaining the decoding result that is point cloud attribute information.

At aforesaid step 1), a point KD tree division method is a binary division method; supposing that there is a total of N points in the point cloud to be processed, and the KD tree division depth is set to d, obtaining 2dcoding blocks after dividing the point cloud d times, where the number of points in each block is close, and is n or n+1, the calculation method of n shown as in formula 1; and numbering all coding blocks according to a breadth preferential traversal sequence, where the coding block number will be the order of post-processing of the coding blocks.

n=⌊N2d⌋(formula⁢⁢1)

The size of the quantisation matrix obtained at aforesaid step 1) is related to the number of the points in the coding block, i.e. n×3 or (n+1)×3.

At aforesaid step 2), 7 types of traversal sequences are applied to each quantisation matrix, where 7 types of traversal sequences are a YUV progressive scan, a YUV column by column scan, a YVU column by column scan, a UYV column by column scan, a UVY column by column scan, a VYU column by column scan, and a VUY column by column scan, respectively. After scanning, the n×3 two-dimensional matrix is transformed to an one-dimensional data stream having a length of 3n; and the data stream in which the number of 0 elements appeared in succession at the end thereof is most is selected as an optimal data stream, while recording the corresponding traversal pattern.

The length of the optimal data stream selected at aforesaid step 3) is 3n, supposing that the number of 0 elements appeared in succession at the end of the data stream is li, the length of the clipped data stream is 3n−li.

The clipped data streams having the length of lcis obtained after performing an entropy decoding at aforesaid step 4), and the number of deleted 0 elements needs to be known to restore the original data stream. The same KD tree division is implemented on the point cloud geometric information at a decoding end as at the encoding end to obtain 2dcoding block, including n (or n+1) points in each block; then numbering all coding blocks according to breadth preferential traversal sequence, obtaining a result in one-to-one correspondence with the encoding end, and solving for the number of deleted 0 elements l0according to formula 2. The length of the data stream after the 0 elements are supplemented is 3n, and transforming the data stream to a n×3 quantisation matrix according to the saved traversal pattern mi.
l0=3n−lc(formula 2)

Details at aforesaid step 5) are as follows:

(5-1) After obtaining a quantisation matrix at step 4), performing an inverse quantisation, an inverse transformation, and a prediction compensation on the quantisation matrix, thus obtaining the decoding result that is point cloud attribute information;

(5-2) The code stream according to the point cloud attribute compression method based on deleting 0 elements in a quantisation matrix is mainly composed of two parts: compressed header information and coding block information. The header information mainly comprise a quantisation step size, prediction pattern information, traversal pattern information of a quantisation matrix and the like; and the coding block information in a coding block unit is arranged in accordance with the sequence of the coding blocks, where mainly comprised within each coding block is the color residual information of the coding block;

(5-3) The performance of the point cloud attribute compression is measured by a code rate and a PSNR (Peak Signal-to-Noise Ratio), where the unit of code rate is bpp (bits per point), the unit of PSNR is decibels (dB), and the smaller the code rate, the greater the PSNR, and the better the point cloud attribute compression performance.

In comparison with prior arts, the advantageous effects of the present disclosure are as follows:

The present disclosure provides a point cloud attribution compression method based on deleting 0 elements in a quantisation matrix, which gives the following technical advantages:

(A) For a quantisation matrix in a point cloud attribute compression process, at an encoding end, an optimal traversal sequence is used to concentrate the 0 elements at the end of a generated data stream and implement an entropy encoding after deleting the 0 elements, thus reducing the data quantity of the data stream and reducing the code streams generated after encoding.

(B) At a decoding end, the point cloud geometric information is incorporated to supplement the deleted 0 elements, restoring the quantisation matrix according to the traversal sequence, which enables the improving of compression performance without introducing new errors.

