PaperlayerView exact revision on arXiv

Source-linked AI summary

Graph-based compression of dynamic 3D point cloud sequences

Dorina Thanou, Philip A. Chou, Pascal Frossard

arXiv:1506.06096v1cs.CVcs.GR

TL;DR

Dynamic point-cloud sequences are difficult to compress because frames vary in size and lack explicit point correspondences. The paper represents frames as graphs, estimates motion through spectral graph-wavelet feature matching, and uses the result for predictive geometry and color coding. Experiments report accurate motion estimation and improved overall compression, including up to 10 dB color-coding gain, while geometry gains are marginal because of motion-vector overhead.

  • Problem

    Compression is challenging for dynamic colored point-cloud sequences because successive frames have varying numbers of points and no explicit correspondence information.

  • Method

    The method represents occupied voxels as graphs, matches spectral graph-wavelet descriptors across successive graphs, interpolates dense motion, and uses it for predictive geometry and color coding.

  • Results

    Motion compensation accurately estimates motion and improves compression overall, with up to 10 dB gain for color attributes while geometry gains remain marginal because of motion-vector overhead.

  • Takeaways & Limitations

    Jointly exploiting spatial graph structure and temporal motion supports efficient compression of both point-cloud geometry and color attributes.

Abstract

from arXiv · show

This paper addresses the problem of compression of 3D point cloud sequences that are characterized by moving 3D positions and color attributes. As temporally successive point cloud frames are similar, motion estimation is key to effective compression of these sequences. It however remains a challenging problem as the point cloud frames have varying numbers of points without explicit correspondence information. We represent the time-varying geometry of these sequences with a set of graphs, and consider 3D positions and color attributes of the points clouds as signals on the vertices of the graphs. We then cast motion estimation as a feature matching problem between successive graphs. The motion is estimated on a sparse set of representative vertices using new spectral graph wavelet descriptors. A dense motion field is eventually interpolated by solving a graph-based regularization problem. The estimated motion is finally used for removing the temporal redundancy in the predictive coding of the 3D positions and the color characteristics of the point cloud sequences. Experimental results demonstrate that our method is able to accurately estimate the motion between consecutive frames. Moreover, motion estimation is shown to bring significant improvement in terms of the overall compression performance of the sequence. To the best of our knowledge, this is the first paper that exploits both the spatial correlation inside each frame (through the graph) and the temporal correlation between the frames (through the motion estimation) to compress the color and the geometry of 3D point cloud sequences in an efficient way.

I. INTRODUCTION

The paper targets compression of dynamic colored point-cloud sequences, where varying frame sizes and absent point correspondences make motion estimation difficult. It models occupied voxels as graphs and uses graph-based motion estimation to support predictive coding of geometry and color.

  • Dynamic point-cloud frames may contain different numbers of points without explicit temporal associations, complicating motion estimation, compensation, and compression.
  • The sequence is voxelized and represented with octrees, enabling spatial organization and real-time manipulation of occupied 3D regions.Each occupied voxel corresponds to a point-bearing cell in the quantized 3D grid.
  • The proposed method casts motion estimation as feature matching on dynamic graphs using spectral graph-wavelet descriptors.Descriptors are matched across graphs from different frames to obtain point-to-point correspondences.
  • The compression architecture uses estimated motion for predictive coding of both geometry and color attributes.Geometry uses structural differences after motion compensation, while color uses prediction residuals from the motion-compensated reference.
  • Prior work largely addressed static point-cloud compression or encoded temporal structural differences without computing exact voxel motion.Mesh-based alternatives also face computational cost and real-time applicability constraints.

III. STRUCTURAL REPRESENTATION OF 3D POINT CLOUDS

The paper represents voxelized 3D point clouds as weighted graphs, treating geometry and color as graph signals for spectral analysis and coding.

  • Octree representation: Octrees quantize 3D positions onto a regular grid and provide multiresolution representations of point clouds.Occupied voxels are obtained by recursively subdividing space to a chosen depth.
  • Graph representation: The occupied voxels form an irregular subset of the grid, motivating a graph representation.Graph structure captures relationships among non-uniformly distributed occupied voxels.
  • Graph representation: Each graph vertex represents an occupied voxel, while edges connect neighboring occupied voxels using a weighted K-nearest-neighbor graph.The usual setting K=26 covers neighbors within one voxel-grid step along any axis, with weights inversely proportional to voxel distance.
  • Spectral representation: The graph Laplacian supports a Graph Fourier Transform whose eigenvectors and eigenvalues provide a spectral representation of graph signals.The Laplacian is L = D − W, with D the diagonal degree matrix.
  • Spectral representation: 3D coordinates and color components are modeled as signals on graph vertices for feature construction and data coding.The paper uses the GFT both to define motion features and to code graph data.

IV. MOTION ESTIMATION IN 3D POINT CLOUD SEQUENCES

Motion estimation is formulated as graph feature matching using orientation-aware, multiscale spectral graph wavelet descriptors derived from geometry and color signals.

  • Feature matching: The approach extends feature-based matching to irregular point-cloud graphs by exploiting graph information and signals residing on vertices.The paper positions this as a graph-domain motion-estimation formulation.
  • Multi-resolution features: For each orientation, descriptors use spectral graph wavelet coefficients computed independently from geometry and color components.The components are x, y, z, r, g, and b, evaluated across discrete wavelet scales.
  • Multi-resolution features: Feature descriptors capture local graph and signal structure in eight spatial orientations around each node.Octant indicator functions partition neighboring nodes according to their 3D coordinate relationships.
  • Spectral graph wavelets: Spectral graph wavelets provide multiscale localized operators on graph signals.A generating kernel acts as a band-pass filter, while a scaling kernel acts as a low-pass filter supporting stable signal recovery.

B. Finding correspondences on dynamic graphs

Correspondences between consecutive point-cloud frames are found by matching vertices of their representative graphs, which may have different sizes, using learned Mahalanobis distances.

  • Graph correspondence: The correspondence problem between consecutive point clouds is converted into correspondence finding between their representative graph vertices.The reference and target graphs can contain different numbers of vertices.
  • Matching criterion: Vertex similarity is measured by the Mahalanobis distance between feature descriptors from the two graphs.The distance compares feature vectors for every candidate node pair.
  • Matching criterion: The positive definite distance matrix is learned from inverse covariance estimates of training features known to correspond.It accounts for relationships among geometry and color components and contributions from different wavelet scales.
  • Best matches: Each target node is assigned the reference node with minimum Mahalanobis distance as its best match.This produces an initial global set of candidate correspondences.
  • Sparse matching: A sparse set of significant, spatially distributed matches is selected to retain accurate correspondences and reject unreliable or unsupported matches.The selection addresses possible descriptor errors under large displacements and target points without true correspondences.

C. Computation of the motion vectors

The method converts sparse graph correspondences into a dense motion field by combining local match-score models with graph-smoothness regularization.

  • Graph regularization: Graph regularization balances fidelity to sparse motion estimates against smoothness of the interpolated field.The parameter µ controls the tradeoff: smaller values favor the initial vectors, while larger values favor smoother solutions.
  • Sparse motion: Motion vectors are first obtained from the displacement between each pair of matched points in the sparse correspondence set.The sparse vectors provide known motion values at selected graph nodes.
  • Dense interpolation: The dense field is interpolated by treating motion as a vector-valued graph signal and estimating each coordinate component independently.The interpolation requires motion to vary smoothly across connected graph vertices.
  • Local score modeling: Local matching scores near each sparse match are modeled with a quadratic approximation based on geometric offsets.The approximation uses neighborhood covariance matrices to capture local score variation.
  • Local score modeling: The covariance-based matrices are positive semidefinite and encode a second-order approximation of neighborhood matching scores.Moment matching is used because it is fast while guaranteeing positive semidefiniteness.
  • Output motion field: The resulting dense motion vectors are represented in a reshaped 3 × N_t form, with one 3D motion vector per graph node.Large optimization systems can be solved iteratively using MINRES-QLP.

V. COMPRESSION OF 3D POINT CLOUD SEQUENCES

The compression architecture codes motion vectors first, then uses motion compensation to predict geometry and color across consecutive point-cloud frames.

  • Motion vectors are transformed into the graph Fourier domain before geometry and color are predictively coded.The sequence is processed in blocks that first code motion, then exploit it for geometry and color compression.

A. Coding of motion vectors

Motion vectors are smoothed, transformed using the reference-frame graph basis, uniformly quantized, entropy coded, and decoded without transmitting graph connectivity.

  • Sparse motion vectors are initially smoothed at the encoder before the dense motion field is transmitted to the decoder.
  • The motion field is transformed separately in each direction using the eigenvectors of the reference-frame graph Laplacian.
  • Transformed coefficients are uniformly quantized with a constant stepsize and independently entropy coded using adaptive RLGR.
  • The decoder reconstructs motion vectors by reversing the transform and coding procedure.
  • Graph connectivity is not transmitted because the decoder can recover the reference-frame K-NN graph from its known 3D positions.

B. Motion compensated differential coding of 3D geometries

Geometry prediction warps the reference frame using decoded motion, then encodes structural differences between the warped reference and target frames through octree-based XOR coding.

  • Decoded motion vectors are combined with reference-frame positions to obtain a motion-compensated frame for predicting the target geometry.The warped frame remains a signal on the reference graph.
  • The warped reference and target point clouds are spatially decomposed into octrees at a predefined depth before differential coding.
  • Occupied-voxel differences are encoded as the exclusive-OR between indicator functions for the motion-compensated reference and target frames.The XOR structure is represented through octree decomposition and transmitted as a bit stream.
  • Motion compensation is expected to reduce the occupied-voxel set difference and therefore the number of bits required by octree decomposition.

C. Motion compensated differential coding of color attributes

Color prediction transfers reference colors through the warped frame, averages nearby colors for each target point, and codes only the resulting residuals with graph-based compression.

  • Reference colors are transferred to the motion-compensated frame and used to predict colors in the target frame.
  • Each target point receives the average color of nearby warped-frame points selected by Euclidean proximity.The neighborhood cardinality is usually set to 3.
  • Temporal color redundancy is removed by coding the residual between target colors and their motion-compensated predictions.
  • Graph-based color compression further removes within-frame spatial correlation by coding residual color components in the graph Fourier domain.
  • DC and AC graph-Fourier coefficients are treated differently during entropy coding because they represent averages and higher graph oscillations, respectively.

VI. EXPERIMENTAL RESULTS

Experiments evaluate motion estimation and compression on two voxelized human-motion sequences, the yellow dress and the man sequences.

  • The experiments use the yellow dress and man sequences, both capturing human bodies in motion.The sequences are voxelized for compression and motion-compensation evaluation.
  • Figure 7 illustrates motion estimation and compensation for both sequences using frame superimpositions, point correspondences, and motion-compensated reference frames.Small cubes represent voxels in the motion-compensated frame.
  • The first sequence contains 64 frames and the second contains 30 frames, with approximately 8,500 occupied voxels per frame at voxel stepsize 20.The voxelized data originate from approximately 75,000 initial 3D points with color attributes.

A. Motion estimation

Motion is estimated from sparse graph-feature matches, interpolated across the graph, and evaluated for both compensation quality and geometry-compression rate.

  • A. Motion estimation: Four-scale spectral graph wavelets are approximated with degree-30 Chebyshev polynomials, and motion is computed on about 500 representative points before graph smoothing.The representative points comprise fewer than 10% of occupied voxels.
  • A. Motion estimation: Motion-compensated reference frames are much closer to target frames than simple reference frames for both tested sequences.The results confirm accurate motion estimation in the reported experiments.
  • B. 3D geometry compression: The motion-compensated dual octree scheme achieves 3.3 bpv for the man sequence when motion vectors are coded at 0.1 bpv.Simple octree and dual octree coding require approximately 3.42 and 3.5 bpv, respectively.
  • B. 3D geometry compression: At approximately 0.1 bpv for motion vectors, motion-compensated dual octree coding slightly outperforms simple octree and dual octree compression.Lower motion-vector rates reduce the compensation benefit, while finer rates increase total geometry-coding overhead.

C. Color compression

Motion compensation supports predictive coding of color and geometry, with the strongest reported compression benefit occurring for color attributes.

  • C. Color compression: Color prediction warps the reference frame using the smoothed motion field and averages the three nearest warped-frame points.Experiments fix the motion-vector coding rate at 0.1 bpv.
  • C. Color compression: Motion compensation improves average color-prediction gain by 2.5 dB over nearest-neighbor prediction and 8–10 dB over average reference-frame color.Reported SNR values are 13, 10.5, and 4 dB for the man sequence and 17, 15, and 6.5 dB for yellow dress.
  • C. Color compression: At Δ=1024, differential color coding gains approximately 10 dB over independent coding for both sequences.At higher bit rates, the difference between the two coding methods becomes smaller.
  • C. Color compression: Longer prediction paths can cause gradual PSNR degradation from accumulated quantization error, especially at low bit rates.Periodic reference frames and optimized prediction-path lengths can mitigate this degradation.
  • D. Discussion: Overall, motion compensation provides up to 10 dB gain for color, while geometry gains are marginal because of motion-vector coding overhead.For the man sequence, motion vectors use 0.1–0.2 bits per vertex, color residuals 0.1–0.3 bits, and geometry 3.3 bits.
Loading 1506.06096v1…