Compression of dense and regular point clouds

ABSTRACT

We present a simple technique for single-rate compression of point clouds sampled from a surface, based on a spanning tree of the points. Unlike previous methods, we predict future vertices using both a linear predictor, which uses the previous edge as a predictor for the current edge, and lateral predictors that rotate the previous edge 90° left or right about an estimated normal.By careful construction of the spanning tree and choice of prediction rules, our method improves upon existing compression rates when applied to regularly sampled point sets, such as those produced by laser range scanning or uniform tesselation of higher-order surfaces. For less regular sets of points, the compression rate is still generally within 1.5 bits per point of other compression algorithms.

REFERENCES

• 1: Alliez, P., and Gotsman, C. 2004. Recent advances in compression of 3D meshes. In Advances in Multiresolution for Geometric Modelling. Springer.
• 2: Mario Botsch , Andreas Wiratanaya , Leif Kobbelt, Efficient high quality rendering of point sampled geometry, Proceedings of the 13th Eurographics workshop on Rendering, June 26-28, 2002, Pisa, Italy
• 3: Matthias Eck , Tony DeRose , Tom Duchamp , Hugues Hoppe , Michael Lounsbery , Werner Stuetzle, Multiresolution analysis of arbitrary meshes, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.173-182, September 1995 [doi>10.1145/218380.218440]
• 4: Olivier Faugeras, Three-dimensional computer vision: a geometric viewpoint, MIT Press, Cambridge, MA, 1993
• 5: Shachar Fleishman , Daniel Cohen-Or , Marc Alexa , Cláudio T. Silva, Progressive point set surfaces, ACM Transactions on Graphics (TOG), v.22 n.4, p.997-1011, October 2003 [doi>10.1145/944020.944023]
• 6: Pierre-Marie Gandoin , Olivier Devillers, Progressive lossless compression of arbitrary simplicial complexes, Proceedings of the 29th annual conference on Computer graphics and interactive techniques, July 23-26, 2002, San Antonio, Texas
• 7: Gumhold, S., Karni, Z., Isenburg, M., and Seidel, H.-P. 2004. Predictive point-cloud compression. In ACM SIGGRAPH Conference Abstracts and Applications.
• 8: Lee, H., Alliez, P., and Desbrun, M. 2002. Angle-analyzer: A triangle-quad mesh codec. In Eurographics conference proceedings, 383--392.
• 9: Marc Levoy , Kari Pulli , Brian Curless , Szymon Rusinkiewicz , David Koller , Lucas Pereira , Matt Ginzton , Sean Anderson , James Davis , Jeremy Ginsberg , Jonathan Shade , Duane Fulk, The digital Michelangelo project: 3D scanning of large statues, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.131-144, July 2000 [doi>10.1145/344779.344849]
• 10: William E. Lorensen , Harvey E. Cline, Marching cubes: A high resolution 3D surface construction algorithm, Proceedings of the 14th annual conference on Computer graphics and interactive techniques, p.163-169, August 1987
• 11: Ochotta, T., and Saupe, D. 2004. Compression of point-based 3d models by shape-adaptive wavelet coding of multi-height fields. In Proceedings Symposium on Point-Based Graphics.
• 12: Peng, J., and Kuo, C. C. J. 2003. Octree-based progressive geometry encoder. In Internet Multimedia Management Systems IV. Edited by Smith, John R.; Panchanathan, Sethuraman; Zhang, Tong. Proceedings of the SPIE, Volume 5242, pp. 301--311 (2003)., 301--311.
• 13: Randers-Pehrson, G. 2003. Portable Network Graphics (PNG) Specification, 2nd ed. W3C, October. http://www.w3.org/TR/PNG/.
• 14: Szymon Rusinkiewicz , Marc Levoy, QSplat: a multiresolution point rendering system for large meshes, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.343-352, July 2000 [doi>10.1145/344779.344940]
• 15: Robert Sedgewick, Algorithms in C, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 16: Gabriel Taubin , Jarek Rossignac, Geometric compression through topological surgery, ACM Transactions on Graphics (TOG), v.17 n.2, p.84-115, April 1998 [doi>10.1145/274363.274365]
• 17: Touma, C., and Gotsman, C. 1998. Triangle mesh compression. In Proc Graphics Interface, 26--34.
• 18: Greg Turk , Marc Levoy, Zippered polygon meshes from range images, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, p.311-318, July 1994 [doi>10.1145/192161.192241]
• 19: Wardetzky, M., Kaelberer, F., Polthier, K., and Reitebuch, U. 2005. Freelence --- coding with free valences. In Eurographics.
• 20: Waschbüsch, M., Gross, M., Eberhard, F., Lamboray, E., and Würmlin, S. 2004. Progressive compression of point-sampled models. In Eurographics Symposium on Point-Based Graphics, 95--102.
• 21: Ian H. Witten , Radford M. Neal , John G. Cleary, Arithmetic coding for data compression, Communications of the ACM, v.30 n.6, p.520-540, June 1987 [doi>10.1145/214762.214771]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS

Additional Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY
      Subjects: Data compaction and compression

Keywords:
compression, point clouds, range scanning, spanning tree