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. Botsch, M., Wiratanaya, A., and Kobbelt, L. 2002. Efficient high quality rendering of point sampled geometry. In EGRW '02: Proceedings of the 13th Eurographics workshop on Rendering, Eurographics Association, Aire-la-Ville, Switzerland, 53--64.
3. Eck, M., DeRose, T., Duchamp, T., Hoppe, H., Lounsbery, M., and Stuetzle, W. 1995. Multiresolution analysis of arbitrary meshes. In SIGGRAPH '95: Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, ACM Press, New York, NY, USA, 173--182.
4. Faugeras, O. 1993. Three-Dimensional Computer Vision: a Geometric Viewpoint. MIT Press, Cambridge, Mass.
5. Fleishman, S., Cohen-Or, D., Alexa, M., and Silva, C. T. 2003. Progressive point set surfaces. ACM Trans. Graph, 22, 4, 997--1011.
6. Gandoin, P.-M., and Devillers, O. 2002. Progressive lossless compression of arbitrary simplicial complexes. In SIGGRAPH '02: Proceedings of the 29th annual conference on Computer graphics and interactive techniques, ACM Press, New York, NY, USA, 372--379.
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. Levoy, M., Pulli, K., Curless, B., Rusinkiewicz, S., Koller, D., Pereira, L., Ginzton, M., Anderson, S., Davis, J., Ginsberg, J., Shade, J., and Fulk, D. 2000. The digital Michelangelo project: 3D scanning of large statues. In SIGGRAPH '00: Proceedings of the 27th annual conference on Computer graphics and interactive techniques, ACM Press/Addison-Wesley Publishing Co., New York, NY, USA, 131--144.
10. Lorensen, W. E., and Cline, H. E. 1987. Marching cubes: A high resolution 3D surface construction algorithm. In SIGGRAPH '87: Proceedings of the 14th annual conference on Computer graphics and interactive techniques, ACM Press, New York, NY, USA, 163--169.
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. Rusinkiewicz, S., and Levoy, M. 2000. QSplat: a multiresolution point rendering system for large meshes. In SIGGRAPH '00: Proceedings of the 27th annual conference on Computer graphics and interactive techniques, ACM Press/Addison-Wesley Publishing Co., New York, NY, USA, 343--352.
15. Sedgewick, R. 1990. Algorithms in C, 2nd ed. Addison-Wesley.
16. Taubin, G., and Rossignac, J. 1998. Geometric compression through topological surgery. ACM Transactions on Graphics 17, 2, 84--115.
17. Touma, C., and Gotsman, C. 1998. Triangle mesh compression. In Proc Graphics Interface, 26--34.
18. Turk, G., and Levoy, M. 1994. Zippered polygon meshes from range images. In SIGGRAPH '94: Proceedings of the 21st annual conference on Computer graphics and interactive techniques, ACM Press, New York, NY, USA, 311--318.
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. Witten, I. H., Neal, R. M., and Cleary, J. G. 1987. Arithmetic coding for data compression. Commun. ACM 30, 6, 520--540.

Index Terms

• Computing methodologies

  • Computer graphics

• Information systems

  • Data management systems

    • Data structures

      • Data layout

        • Data compression