Progressive encoding and compression of surfaces generated from point cloud data

We present a new algorithm for compressing surfaces created from oriented points, sampled using a laser range scanner or created from polygonal surfaces. We first use the input data to build an octree whose nodes contain planes that are constructed as the least square fit of the data within that node. Then, given an error threshold, we prune this octree to remove redundant data while avoiding topological changes created by merging disjoint linear pieces. From this octree representation, we provide a progressive encoding technique that encodes the octree structure as well as the plane equations. We encode the planes using distances to three points and a single bit. To decode these planes, we solve a constrained optimization problem that has closed-form solution. We then reconstruct the surface from this representation by implicitizing the discontinuous linear pieces at the leaves of the octree and take a level set of this implicit representation. Our tests show that the proposed method compresses surfaces with higher accuracy and smaller file sizes than other methods.

Figure optionsDownload high-quality image (329 K)Download as PowerPoint slideHighlights
► Our algorithm compresses an intermediate data structure built from oriented points.
► We provide an adaptive pruning method that removes redundant geometric information.
► We estimate Hausdorff distance to avoid extrapolation/merging of different regions.
► We encode the octree with the planes in each node using distance from three points.
► We decode the planes using a closed-form solution for a constrained optimization.