Enhanced graph transformation-based point cloud attribute compression method

Abstract

An enhanced graph transformation-based point cloud attribute compression method. For point cloud attribute information, a point cloud is first subjected to airspace division by using a K-dimension (KD) tree; a new graph transformation processing method in combination with spectral analysis is provided; the point cloud is then subjected to spectral clustering on graphs in coded blocks of the point cloud; expansion is performed on the basis of existing graph transformation to implement a local graph transformation scheme; enhanced graph transformation with two transformation modes is formed; the compression performance of graph transformation is improved. The method comprises: performing color space transformation of point cloud attributes; dividing the point cloud by using the KD tree to obtain the coded blocks; performing spectral clustering-based enhanced graph transformation; performing transformation mode decision; and performing uniform quantization and entropy coding. Provided is a new spectral analysis-based enhanced graph transformation scheme, wherein two transformation modes are comprised, and the optimal mode is selected by the mode decision; after the point cloud is divided with the tree, a graph is created in each coded block and the graph transformation is used as transformation mode I; on this basis, graph spectral clustering is implemented; the graph is divided into two local graphs and then local graph transformation is performed to serve as transformation mode II; in the enhanced graph transformation scheme supporting the two transformation modes, the optimal mode is selected by the mode decision to achieve the optimal performance of point cloud attribute compression.

Claims

1. An enhanced graph transformation-based point cloud attribute compression method, comprising, for point cloud attribute information, first subjecting a point cloud to airspace division by using a K-dimension (KD) tree; providing a new graph transformation processing method in combination with spectral analysis; then subjecting the point cloud to spectral clustering on graphs in coded blocks of the point cloud; performing expansion on the basis of existing graph transformation to implement a local graph transformation scheme so as to form enhanced graph transformation with two transformation modes to improve the compression performance of graph transformation; the method comprises the steps of: 1) color space transformation of point cloud attributes reading in point cloud attribute information to be processed, and transforming a point cloud color space from an RGB space to a YUV space according to the visual characteristics of human eyes and the difficulty degree of compression processing; 2) dividing the point cloud by using a KD tree to obtain coded blocks, and numbering the coded blocks according to a breadth traversal sequence reading in geometric information of the point cloud, performing KD tree division on the point cloud according to the geometric information, selecting a coordinate axis with a largest distribution variance in the position coordinate of the point cloud as a division axis each time, selecting a point with the coordinate being a median value as a division point, and performing iterative division until reaching a set KD tree depth; a block obtained from a last layer divided by the KD tree being a coded block of the point cloud, numbering the coded blocks according to a breadth traversal sequence, and the number being used as a sequence for later processing of the coded blocks; 3) constructing a graph within the coded block by using enhanced graph transformation, with two transformation modes in the coded block, connecting every two points n.sub.i and n.sub.j by an edge ε.sub.ij to construct an entire points graph G, wherein each point on the graph has color information, and the weight of the edge is determined by the geometric relative position of the two points; the weight ω.sub.ij of the edge ε.sub.ij reflects geometric correlation between the two points n.sub.i and n.sub.j, and the weights ω of all the edges form an adjacent matrix W of the graph to further obtain a feature vector matrix A; transformation mode I: taking the feature vector A of the entire points graph as a transformation matrix, and transforming the color information of the coded block; transformation mode II: the feature vector matrix A of a graph G reflects the spectrum distribution of the graph, so that spectral clustering is performed on the basis of the matrix A to realize local graph segmentation; clustering all points in the block into two types by using a plus-minus sign of the second dimension column vector of the matrix A; if the number of the two types of points reaches more than 40% of the total number of the points in the block, dividing the graph G into two local graphs G.sub.1, G.sub.2 according to the clustering condition, so as to respectively obtain corresponding feature vector matrix A.sub.1 and A.sub.2; transforming the color information in the two local graphs G.sub.1 and G.sub.2 by using a corresponding transformation matrix; 4) transformation mode decision: providing two modes for transforming the color information of the coded block, and performing a mode decision by estimating the transformation performance to select an optimal transformation mode; calculating the proportion of the sum of absolute values of the previous k maximum coefficients in the transformed coefficients in the sum of the absolute values of the transformed coefficients as the score of the transformation mode; the higher the score is, the higher the proportion of the selected transformation coefficient in the total transformation coefficient is, representing higher transformation efficiency and better performance in the mode, wherein the mode with the highest score is selected as the transformation mode of the current block; 5) generation of a code stream with point cloud attribute compression: processing all the coded blocks according to the coding sequence, quantizing the transformed coefficients, and performing entropy coding by combining the transformation mode information to obtain a final code stream with point cloud attribute compression.

2. The point cloud attribute compression method of claim 1, wherein the specific process of the color space transformation in the step 1) is as follows: a point p.sub.i in the point cloud has color values r.sub.i, g.sub.i and b.sub.i in an RGB color space; the RGB is transformed into a YUV color space by a formula 1, and the color values thereof are y.sub.i, u.sub.i and v.sub.i. $\begin{array}{cc}\left[y_i,u_i,v_i\right]=\left[r_i,g_i,b_i\right]\times \left\{\begin{array}{ccc}0.2126& 0.7152& 0.0722\\ -0.1146& -0.3854& 0.5\\ 0.5& -0.4542& -0.0458\end{array}\right\}& \left(\mathrm{Formula}1\right)\end{array}$

3. The point cloud attribute compression method of claim 1, wherein the KD tree division method in the step 2) is a binary division method; let the point cloud to be processed have N points, and the division depth set by the KD tree be d, 2.sup.d coded blocks are obtained after the point cloud is divided for d times; and all coded blocks are numbered with b.sub.1, b.sub.2, . . . , b.sub.i, . . . , b.sub.2.sub.d in the breadth traversal sequence.

4. The point cloud attribute compression method of claim 1, wherein the specific process of the enhanced graph transformation in the step 3) comprises: (4-1) constructing a graph G in each transformation block, wherein each two points n.sub.i and n.sub.j are connected by an edge ε.sub.ij, and the weight ω.sub.ij of the edge ε.sub.ij is related to the Euclidean distance between the two points and generally calculated by a formula 2: $\begin{array}{cc}{\omega }_{i,j}=\{\begin{array}{cc}{e}^{-\frac{{.Math.n_i-n_j.Math.}_2^2}{{\sigma }^2}},& {\mathrm{if}||n_i-n_j.Math.}_2^2\le \tau ;\\ 0,& \mathrm{else},\end{array}& \left(\mathrm{Formula}2\right)\end{array}$ wherein the parameter σ reflects the distribution variance of the current point cloud; the parameter τ is a distance threshold for judging whether a connection line is formed between the two points, which determines the sparsity of a graph Laplacian matrix, and an experience set value is generally used; (4-2) the adjacent matrix W of the graph G is a set of edge weights ω.sub.ij and reflects the correlation between each point in the block; the density matrix D of the graph G is a diagonal matrix, wherein D.sub.i is the sum of non-zero elements in the i row of the adjacent matrix and represented by a formula 3, reflecting the density of correlation between the i.sup.th point and other points; the transformation operator of graph G adopts a Laplacian matrix L, and is represented by a formula 4:
D.sub.i=Σ.sub.jω.sub.i,j  (Formula 3)
L=D−W  (Formula 4) (4-3) performing characteristic decomposition on the Laplacian matrix L, which is represented by a formula 5 to obtain a feature vector matrix A, which serves as a global graph transformation matrix in the transformation mode 1 for compressing the point cloud attribute information:
L=AΛA.sup.−1   (Formula 5) wherein A is a feature vector matrix; (4-4) performing spectral clustering on the second dimension column vector V.sub.2 of the feature vector matrix A, and clustering the points into two types C.sub.1 and C.sub.2 according to the plus-minus sign of the vector parameter value, which is represented by a formula 6; dividing the global graph G into two local graphs G.sub.1 and G.sub.2 according to the clustering condition, wherein the two local graphs are composed of corresponding points n and edges e and are represented by a formula 7: $\begin{array}{cc}\{\begin{array}{c}{C}_1=\left(p_i|V_2\left(p_i\right)>0\right),\mathrm{if}\frac{\mathrm{count}\left(C_1\right)}{\mathrm{count}\left(\mathrm{block}\right)}>40\%;\\ C_2=\left(p_i|V_2\left(p_i\right)\le 0\right),\mathrm{if}\frac{\mathrm{count}\left(C_2\right)}{\mathrm{count}\left(\mathrm{block}\right)}>40\%,\end{array}& \left(\mathrm{Formula}6\right)\\ \{\begin{array}{c}{G}_1=\left(n\left(C_1\right),\mathrm{.Math.}\left(C_1\right)\right),\\ G_2=\left(n\left(C_2\right),\mathrm{.Math.}\left(C_2\right)\right),\end{array}& \left(\mathrm{Formula}7\right)\end{array}$ in the formula 6, count(C.sub.1) is used for calculating the number of points in C.sub.1, count(C.sub.2) for calculating the number of points in C.sub.2, and count(block) for calculating the total number of points in the current coded block; (4-5) respectively performing characteristic decomposition on the two local graphs G.sub.1 and G.sub.2 to obtain transformation matrices A.sub.1 and A.sub.2, which are used as local graph transformation matrices in the transformation mode II and used for transformation of color information corresponding to a point in the graph; (4-6) the graph transformation with two transformation modes forms an enhanced graph transformation scheme.

5. The point cloud attribute compression method of claim 1, wherein in the transformation mode decision in the step 4), the key is to calculate the score J of the transformation mode; firstly, the absolute values of the transformed coefficients Trans are arranged in a descending order, and then the sum of the absolute values of the largest coefficients in the previous k-dimension selected is calculated for the proportion in the sum of the absolute values of the transformed coefficients, which is represented by a formula 8: $\begin{array}{cc}J=\frac{\underset{i=1}{\overset{k}{.Math.}}.Math.{\mathrm{Trans}}_{\left(i\right)}.Math.}{\underset{i=1}{\overset{\mathrm{all}}{.Math.}}.Math.{\mathrm{Trans}}_{\left(i\right)}.Math.}.& \left(\mathrm{Formula}8\right)\end{array}$

6. The point cloud attribute compression method of claim 1, wherein the specific details in the step 5) are as follows: (6-1) the code stream of point cloud attribute information is mainly composed of compressed header information and coded block information; wherein the header information mainly comprises quantization step length and the like; the coded block information stream is arranged in the order of coded blocks in units of coded blocks, and each block mainly comprises transformation mode information and color residual information of the coded blocks; (6-2) the performance of point cloud attribute compression is measured by a bitrate and a Peak Signal to Noise Ratio (PSNR), wherein the ode rate is in units of bits per point (bpp), and PSNR is in decibel dB; the smaller the ode rate is, the larger the PSNR is, and the better the performance of point cloud attribute compression is.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) FIG. 1 is a flow block diagram of a method provided by the present invention.

(2) FIG. 2 is an example flow diagram of an enhanced graph transformation process for a point cloud coded block.

(3) wherein, (a) a point cloud example; (b) coded blocks obtained by KD tree division; (c) a coded block example; (d) performing enhanced graph transformation on the current coded block: if the clustering condition is met, the entire points graph is segmented into two local graphs; otherwise, no segmentation is performed.

(4) FIG. 3 is an example diagram of a code stream structure after point cloud attribute information compression.

(5) FIGS. 4a, 4b and 4c are comparison diagrams comparing the compression performance of the method of the present invention with that of a conventional method.

(6) Wherein:

(7) FIG. 4a is a comparison diagram for testing the compression performance of longdress_vox10_1300.ply;

(8) FIG. 4b is a comparison diagram for testing the compression performance of Queen_frame_0200.ply;

(9) FIG. 4c is a comparison diagram for testing the compression performance of soldier_vox10_0690.ply.

DETAILED DESCRIPTION

(10) The invention will now be further described, by way of example, with reference to the accompanying drawings, which do not limit the scope of the invention in any way.

(11) A point cloud attribute compression method based on enhanced graph transformation of the present invention is provided, comprising, for point cloud data, first subjecting a point cloud to airspace division by using a K-dimension (KD) tree; providing a new graph transformation processing method in combination with spectral analysis; then subjecting the point cloud to spectral clustering on graphs in coded blocks of the point cloud; performing expansion on the basis of existing graph transformation to implement a local graph transformation scheme so as to form enhanced graph transformation with two transformation modes to improve the compression performance of graph transformation; and FIG. 1 is a flow block diagram of the method of the present invention.

(12) For official point cloud data sets longdress_vox10_1300.ply, Queen_frame_0200.ply and soldier_vox10_0690.ply in an MPEG point cloud compression working group, performing point cloud attribute compression by the method provided by the invention as shown in FIG. 1 includes the specific implementation steps as follows:

(13) (1) Color space transformation of point cloud attributes: reading in cloud attribute information to-be-processed point, wherein a point p.sub.i in the point cloud has color values r.sub.j, g.sub.i, and b.sub.i in an RGB color space, the RGB is transformed into a YUV color space by a color space transformation matrix, and the color value thereof are y.sub.i, u.sub.i, and v.sub.i, as shown in a formula 1:

(14) $\begin{array}{cc}\left[y_i,u_i,v_i\right]=\left[r_i,g_i,b_i\right]\times \left[\begin{array}{ccc}0.2126& 0.7152& 0.0722\\ -0.1146& -0.3854& 0.5\\ 0.5& -0.4542& -0.0458\end{array}\right].& \left(\mathrm{Formula}1\right)\end{array}$

(15) The RGB color values of the first point p.sub.1 of the point cloud longdress_vox10_1300.ply are (102, 94, 87), and the YUV color values are (54.4128, −2.7926, 50.3798) obtained by the color transformation matrix processing.

(16) The RGB color values of the first point p.sub.1 of the point cloud Queen_frame_0200.ply are (102, 80, 71), and the YUV color values are (48.0172, 9.8702, 44.1126) obtained by the color transformation matrix processing.

(17) The RGB color values of the first point p.sub.1 of the point cloud soldier_vox10_0690.ply are (68, 65, 64), and the YUV color values are (39.0078, −5.4862, 34.4784) obtained by the color transformation matrix processing.

(18) (2) Dividing the point cloud by using a KD tree to obtain coded blocks: the KD tree is essentially a binary tree; when the point cloud is divided by the KD tree, selecting a coordinate axis with a largest distribution variance in the position coordinate of the point cloud as a division axis each time, selecting a point with the coordinate being a median value on the axis as a division point, and performing iterative division until reaching a set KD tree depth, the KD trees after division and coded blocks with numbers.

(19) The point cloud longdress_vox10_1300.ply has 857966 points, the KD tree division depth d is set to 13, and the number of points in the divided block is 104 or 105.

(20) The point cloud Queen_frame_0200.ply has 1000993 points, the KD tree division depth d is set to 13, and the number of points in the divided block is 122 or 123.

(21) The point cloud soldier_vox10_0690.ply has 1089091 points, the KD tree division depth d is set to 13, and the number of points in the divided block is 132 or 133.

(22) (3) Spectral clustering-based enhanced graph transformation: the point cloud is divided by the KD tree in the step (2) to obtain coded blocks, and then the coded blocks are processed by using enhanced graph transformation with two transformation modes, wherein the processing flow is shown in FIG. 2. The essence of the enhanced graph transformation is to expand the spectral clustering of the graph into another transformation mode on the basis of the current graph transformation, and the specific details are as follows:
(3-1) constructing a graph: connecting every two points in a block by an edge to form a graph G consisting of points n and edges ε.
(3-2) adjacent matrices of the graph: the adjacent matrices W of the graph G is a set of edge weights ω.sub.ij between two points n.sub.i and n.sub.j and reflects the correlation between the points in the transformation block, and the weight of the edge is determined by formula 2:

(23) $\begin{array}{cc}{\omega }_{i,j}=\{\begin{array}{cc}{e}^{-\frac{{.Math.n_i-n_j.Math.}_2^2}{{\sigma }^2}},& \mathrm{if}.Math.n_i-n_j.Math.\le \tau ;\\ 0,& \mathrm{else},\end{array}& \left(\mathrm{Formula}2\right)\end{array}$
here, the parameter σ is the variance of the geometric coordinates of the point cloud, and the parameter τ is the distance threshold for determining the correlation between two points, affecting the generation of the transformation matrix, τ being generally represented by

(24) ${\tau }^{\prime }=e^{-\frac{\tau }{{\sigma }^2}},$
τ′ set to 0.8.
(3-3) density matrix of the graph: the density matrix D of the graph G is a diagonal matrix, with the expression as shown in a formula 3, wherein D.sub.i is the sum of nonzero elements in the i.sup.th row of the adjacent matrices and reflects the correlation density of the i.sup.th point and other points;
D.sub.i=Σ.sub.jω.sub.i,j  (Formula 3)
(3-4) Laplacian matrix of the graph: the transformation operator of graph G generally uses a Laplacian matrix L, with expression of a formula 4:
L=D−W  (Formula 4)
(3-5) the graph transformation matrix in transformation mode I: performing characteristic decomposition on the Laplacian matrix L to obtain a feature vector matrix A, which serves as a graph transformation matrix of the transformation mode I for compressing attribute information of the point cloud, wherein the characteristic decomposition is as follows:
L=AΛA.sup.−1   (Formula 5)
(3-6) the graph transformation matrix-based spectral clustering: performing spectral clustering on the second dimension column vector V.sub.2 of the feature vector matrix A, and clustering the points into two types C.sub.1 and C.sub.2 according to the plus-minus sign of the vector parameter values p.sub.i, which is represented by a formula 6; dividing the global graph G into two local graphs G.sub.1 and G.sub.2 according to the clustering condition, wherein the two local graphs are composed of corresponding points n and edges e and are represented by a formula 7:

(25) $\begin{array}{cc}\{\begin{array}{cc}{C}_1=\left(p_i.Math.V_2\left(p_i\right)>0\right),& \mathrm{if}\frac{\mathrm{count}\left(C_1\right)}{\mathrm{count}\left(\mathrm{block}\right)}>40\%;\\ C_2=\left(p_i.Math.V_2\left(p_i\right)\le 0\right),& \mathrm{if}\frac{\mathrm{count}\left(C_2\right)}{\mathrm{count}\left(\mathrm{block}\right)}>40\%\end{array},& \left(\mathrm{Formula}6\right)\\ \{\begin{array}{c}{G}_1=\left(n\left(C_1\right),\mathrm{.Math.}\left(C_1\right)\right),\\ G_2=\left(n\left(C_2\right),\mathrm{.Math.}\left(C_2\right)\right)\end{array},& \left(\mathrm{Formula}7\right)\end{array}$
in the formula 6, count(C.sub.1) is used for calculating the number of points in C.sub.1, count(C.sub.2) for calculating the number of points in C.sub.2, and count(block) for calculating the total number of points in the current coded block;
(3-7) the graph transformation matrix in transformation mode II: respectively performing characteristic decomposition on the two local graphs G.sub.1 and G.sub.2 to obtain transformation matrices A.sub.1 and A.sub.2, which are used as local graph transformation matrices in the transformation mode II and used for transformation of color information corresponding to a point in the graph;
(3-8) the graph transformation with the two transformation modes forms an enhanced graph transformation scheme;
(4) transformation mode decision:
providing two modes for transforming the color information of the coded block, and performing a mode decision by estimating the transformation performance to select an optimal transformation mode; calculating the proportion of the sum of absolute values of the previous k maximum coefficients in the transformed coefficients in the sum of the absolute values of the transformed coefficients as the score of the transformation mode, as shown in a formula 8; the higher the score is, the higher the proportion is, representing higher transformation efficiency and better performance in the mode, wherein the mode with the highest score is selected as the transformation mode of the current block;

(26) $\begin{array}{cc}J=\frac{\underset{i=1}{\overset{k}{.Math.}}.Math.{\mathrm{Trans}}_{\left(i\right)}.Math.}{\underset{i=1}{\overset{\mathrm{all}}{.Math.}}.Math.{\mathrm{Trans}}_{\left(i\right)}.Math.}& \left(\mathrm{Formula}8\right)\end{array}$
for example, the first coded block b.sub.1 of the point cloud longdress_vox10_1300.ply uses scores J in transformation modes I and II of 0.58 and 0.4, respectively, so a mode with a larger J is selected as the optimal transformation mode for the block b.sub.1;
(5) generation of a code stream with point cloud attribute compression: for 8192 coded blocks of the point cloud longdress_vox10_1300.ply, 8192 coded blocks of the Queen_frame_0200.ply and 8192 coded blocks of the soldier_vox10_0690.ply, color information in the block is subjected to enhanced graph transformation, quantization and entropy coding in sequence, combined with the code stream information in the transformation mode, and then written into a code stream file according to the sequence of the coded blocks, with the structure of the final code stream file as shown in FIG. 3. The performance of point cloud attribute compression is measured by the bitrate in units of bits per point (bpp) and Peak Signal to Noise Ratio (PSNR) in units of decibel dB.

(27) In order to verify the effect of the enhanced graph transformation-based point cloud attribute compression method of the present invention, experiments are carried out using the above three data sets longdress_vox10_1300.ply, Queen_frame_0200.ply, soldier_vox10_0690.ply, and the compression performance is compared with the existing method as shown in FIGS. 4a, 4b and 4c.

(28) As can be seen from FIGS. 4a, 4b and 4c, the method of the present invention is significantly superior in attribute compression performance over the existing mainstream method in the three typical point cloud sequences tested (Octree and DCT based attribute compression, R. N. Mekuria, K. Blom, and P. Cesar, “Design, Implementation and Evaluation of a Point Cloud Codec for Tele-Immersive Video”, IEEE Trans. CSVT, vol. PP, no. 99, pp. 1-1, 2016.), PSNR improves by 1-4 dB at the same bitrate. Although the calculation amount of the method is slightly larger than that of the current method, the compression performance has obvious advantages, the sub-graph problem in previous graph transformation is overcome, and the advantages are prominent.

(29) It should be noted that the examples are disclosed to aid in a further understanding of the present invention, but those skilled in the art will appreciate that various alternatives and modifications are possible without departing from the spirit and scope of the invention and the appended claims. Therefore, the invention should not be limited to the embodiments disclosed, but that the scope of the invention be defined by the claims.

INDUSTRIAL APPLICABILITY

(30) The invention provides a point cloud attribute compression method based on enhanced graph transformation, which comprises the steps of, firstly, subjecting a point cloud to airspace division by using a K-dimension (KD) tree; then, subjecting graphs in coded blocks to spectral clustering by using spectral analysis-based graph transformation processing; performing expansion on the basis of existing graph transformation to implement a local graph transformation scheme; and forming enhanced graph transformation with two transformation modes to improve the compression performance of graph transformation. With the rapid development of three-dimensional scanning devices (laser, radar, etc.), the precision and resolution of point cloud are higher, which makes it possible to digitalize three-dimensional information in real world with high efficiency and precision. The invention can be widely applied to intelligent cities, driverlessness, cultural relics protection and other hot fields.