基于树型结构网格矢量量化的点云渲染算法
|
摘要
针对3D模型海量点云数据存在的空间冗余问题,提出一种基于TSLVQ (tree structure lattice vector quantization)的静态点云有损渲染算法。算法旨在利用层级嵌套网格的集合,解决渲染低效的问题。首先对整个点云进行包围盒封装,多层量化,把数个较小尺度的截断包围盒嵌入到一个较高尺度的截断包围盒单元中,每一步量化过程采用8叉树方法将包围盒分割为八个最佳尺寸的空或非空小包围盒;最后在最高深度的层级里,用包围盒来代替整个小包围盒中全部的点。同时,算法可自行设定8叉树的深度,从而任意控制编码的复杂度和精度,满足渲染的实时性要求。实验结果表明,与现有的网格有损压缩算法相比,提出的算法能在保证模型重建精度的基础上具有较好的空间分解优势,实现实时渲染效果。
Concerning the problems that in point cloud with a lot of temporal redundancy,this paper presented a novel lossy compression approach based on tree-structure lattice vector quantization for static point cloud. The proposed approach utilized the hierarchical packing of embed truncated lattices,which could solve the problem of representation inefficiency. Firstly,it enclosed the point cloud with a cube,then truncated the point cloud,embedded smaller-scale cubes into the bigger-scale cube,the multi-stage procedure of quantization,in every level,this method divided the cube to 8 sub-cutes or voxels as empty or non-empty subspace. Finally,in the predefined max level,it used the cube to represent all the other points in the same cube. Furthermore,it allowed for predefining max level to control coding complexity and coding precision to meet the real-time rendering requirement. Experimental results show that the octree decomposition has obvious advantages in 3 D object real-time representation comparing with the existing gridding lossy compression,guaranteeing 3 D model reconstruction precision.
Concerning the problems that in point cloud with a lot of temporal redundancy,this paper presented a novel lossy compression approach based on tree-structure lattice vector quantization for static point cloud. The proposed approach utilized the hierarchical packing of embed truncated lattices,which could solve the problem of representation inefficiency. Firstly,it enclosed the point cloud with a cube,then truncated the point cloud,embedded smaller-scale cubes into the bigger-scale cube,the multi-stage procedure of quantization,in every level,this method divided the cube to 8 sub-cutes or voxels as empty or non-empty subspace. Finally,in the predefined max level,it used the cube to represent all the other points in the same cube. Furthermore,it allowed for predefining max level to control coding complexity and coding precision to meet the real-time rendering requirement. Experimental results show that the octree decomposition has obvious advantages in 3 D object real-time representation comparing with the existing gridding lossy compression,guaranteeing 3 D model reconstruction precision.
引文
[1] Jensen F V,Nielsen T D. Bayesian networks and decision graphs[M]. New York:Springer,2007.
[2] Wainwright M J,Jordan M I. Graphical models,exponential families,and variational inference[M].[S. l.]:Now Publishers Inc.,2008.
[3] Koller D,Friedman N. Probabilistic graphical models:principles and techniques-adaptive computation and machine learning[M]. Cambridge,MA:MIT Press,2009.
[4] Edwards D. Introduction to graphical modelling[M]. Berlin:Springer,2000.
[5] Bang-Jensen J,Gutin G Z. Digraphs:theory,algorithms and applications[M]. Berlin:Springer Publishing Company,2008.
[6] Kalaiah A,Varshney A. Statistical geometry representation for efficient transmission and rendering[M]. New York:ACM Press,2005.
[7] Willsky A S. Multiresolution Markov models for signal and image processing[J]. Proceedings of the IEEE,2002,90(8):1396-1458.
[8] Hornung A,Wurm K M,Bennewitz M,et al. Octo Map:an efficient probabilistic 3D mapping framework based on octrees[J]. Autonomous Robots,2013,34(3):189-206.
[9]赵尔平,刘炜,党红恩.海量3D点云数据压缩与空间索引技术[J].计算机应用,2018,38(1):146-151.(Zhao Erping,Liu Wei,Dang Hong’en. Data compression and spatial indexing technology for massive 3D point cloud[J]. Journal of Computer Applications,2018,38(1):146-151.)
[10]裴书玉,杜宁,王莉,等.基于自适应分层的文物点云数据压缩算法[J].计算机应用研究,2018,35(11):3500-3503,3507.(Pei Shuyu,Du Ning,Wang Li,et al. Adaptive slicing-based compression algorithm with cultural relics point clouds[J]. Application Research of Computers,2018,35(11):3500-3503,3507.)
[11]Weir D J,Milroy M J,Bradley C,et al. Reverse engineering physical models employing wrap-around B-spline surfaces and quadrics[J].Journal of Engineering Manufacture,1996,210(22):147-157.
[12]Martin R R,Stroud I A,Marshall A D. Data reduction for reverse engineering[C]//Proc of the 7th IMA Conference. 1997:111.
[13]孟娜.基于激光扫描点云的数据处理技术研究[D].济南:山东大学,2009.(Meng Na. Point cloud data process based on laser scanning[D]. Jinan:Shandong University,2009.)
[14]王平江,黄雪梅,陈吉红,等.曲面激光密集测量三维数据的三角片逼近方法[J].工程图学学报,1998(1):17-27.(Wang Pingjiang,Huang Xuemei Chen Jihong,et al. Triangular slice approximation for 3D data with laser intensity measurement[J]. Journal of Engineering Graphics,1988(1):17-27.)
[15]Chen Y H,Ng C T,Wang Y Z. Generation of an STL file from 3D measurement data with user-controlled data reduction[J]. International Journal of Advanced Manufacturing Technology,1999,15(2):127-131.
[16]Taubin G,Zhang T,Golub G. Optimal surface smoothing as filter design[C]//Proc of European Conference on Computer Vision. Berlin:Springer-Verlag,1996:283-292.
[17]王向阳,杨红颖,高存臣.基于小波变换的有损图像压缩算法研究[J].计算机工程与应用,2001,37(15):82-84.(Wang Xiangyang,Yang Hongying,Gao Cunchen. The image compression based on wavelet transform[J]. Journal of Computer Engineering and Applications,2001,37(15):82-84.)
[18]Ochotta T,Saupe D. Compression of point-based 3D models by shape-adaptive wavelet coding of multi-height fields[C]//Proc of Eurographics Conference on Point-based Graphics.[S. l.]:Eurographics Association,2004:103-112.
[19]Kammerl J,Blodow N,Rusu R B,et al. Real-time compression of point cloud streams[C]//Proc of IEEE International Conference on Robotics and Automation. Piscataway,NJ:IEEE Press,2012:778-785.
[20]Berger T. Rate-distortion theory[M].[S. l.]:Prentice-Hall,1971.
[21]Shannon C E A. A mathematical theory of communication[J]. ACM SIGMOBILE Mobile Computing&Communications Review,2001,5(1):3-55.
[22] Gersho A,Gray R M. Vector quantization and signal compression[J]. Springer International,1992,159(1):407-485.
[23]Ricordel V. Etude d’un schéma de quantification vectorielle algébrique et arborescente. Applicationàla compression de séquences d’images numériques[D]. Rennes,French:UniversitéRennes,1996.
[24]Conway J H,Sloane N J A. Sphere packing,lattices and groups[J].American Mathematical Monthly,1989,96(6):538-544.
[25]Linde Y,Buzo A,Gray R M. An algorithm for vector quantizer design[J]. IEEE Trans on Communications,1980,28(1):84-95.
[26]Conway J,Sloane N. Fast quantizing and decoding and algorithms for lattice quantizers and codes[J]. IEEE Trans on Information Theory,1982,28(2):227-232.
[27] Ricordel V,Labit C. Vector quantization by packing of embedded truncated lattices[C]//Proc of International Conference on Image Processing. Piscataway,NJ:IEEE Press,2010.
[28]Ricordel V, Labit C. Tree-structured lattice vector quantization[C]//Proc of European Signal Processing Conference. Piscataway,NJ:IEEE Press,1996:1-4.
[29]Torralba A,Murphy K P,Freeman T W. The MIT-CSAIL database of objects and scenes[DB/OL].(2009). http://people. csail. mit.edu/tmertens/textransfer/data/.
[30]The Stanford 3D scanning repository[DB/OL].(2005). http://www-graphics. stanford. edu/data/3dscanrep.
[2] Wainwright M J,Jordan M I. Graphical models,exponential families,and variational inference[M].[S. l.]:Now Publishers Inc.,2008.
[3] Koller D,Friedman N. Probabilistic graphical models:principles and techniques-adaptive computation and machine learning[M]. Cambridge,MA:MIT Press,2009.
[4] Edwards D. Introduction to graphical modelling[M]. Berlin:Springer,2000.
[5] Bang-Jensen J,Gutin G Z. Digraphs:theory,algorithms and applications[M]. Berlin:Springer Publishing Company,2008.
[6] Kalaiah A,Varshney A. Statistical geometry representation for efficient transmission and rendering[M]. New York:ACM Press,2005.
[7] Willsky A S. Multiresolution Markov models for signal and image processing[J]. Proceedings of the IEEE,2002,90(8):1396-1458.
[8] Hornung A,Wurm K M,Bennewitz M,et al. Octo Map:an efficient probabilistic 3D mapping framework based on octrees[J]. Autonomous Robots,2013,34(3):189-206.
[9]赵尔平,刘炜,党红恩.海量3D点云数据压缩与空间索引技术[J].计算机应用,2018,38(1):146-151.(Zhao Erping,Liu Wei,Dang Hong’en. Data compression and spatial indexing technology for massive 3D point cloud[J]. Journal of Computer Applications,2018,38(1):146-151.)
[10]裴书玉,杜宁,王莉,等.基于自适应分层的文物点云数据压缩算法[J].计算机应用研究,2018,35(11):3500-3503,3507.(Pei Shuyu,Du Ning,Wang Li,et al. Adaptive slicing-based compression algorithm with cultural relics point clouds[J]. Application Research of Computers,2018,35(11):3500-3503,3507.)
[11]Weir D J,Milroy M J,Bradley C,et al. Reverse engineering physical models employing wrap-around B-spline surfaces and quadrics[J].Journal of Engineering Manufacture,1996,210(22):147-157.
[12]Martin R R,Stroud I A,Marshall A D. Data reduction for reverse engineering[C]//Proc of the 7th IMA Conference. 1997:111.
[13]孟娜.基于激光扫描点云的数据处理技术研究[D].济南:山东大学,2009.(Meng Na. Point cloud data process based on laser scanning[D]. Jinan:Shandong University,2009.)
[14]王平江,黄雪梅,陈吉红,等.曲面激光密集测量三维数据的三角片逼近方法[J].工程图学学报,1998(1):17-27.(Wang Pingjiang,Huang Xuemei Chen Jihong,et al. Triangular slice approximation for 3D data with laser intensity measurement[J]. Journal of Engineering Graphics,1988(1):17-27.)
[15]Chen Y H,Ng C T,Wang Y Z. Generation of an STL file from 3D measurement data with user-controlled data reduction[J]. International Journal of Advanced Manufacturing Technology,1999,15(2):127-131.
[16]Taubin G,Zhang T,Golub G. Optimal surface smoothing as filter design[C]//Proc of European Conference on Computer Vision. Berlin:Springer-Verlag,1996:283-292.
[17]王向阳,杨红颖,高存臣.基于小波变换的有损图像压缩算法研究[J].计算机工程与应用,2001,37(15):82-84.(Wang Xiangyang,Yang Hongying,Gao Cunchen. The image compression based on wavelet transform[J]. Journal of Computer Engineering and Applications,2001,37(15):82-84.)
[18]Ochotta T,Saupe D. Compression of point-based 3D models by shape-adaptive wavelet coding of multi-height fields[C]//Proc of Eurographics Conference on Point-based Graphics.[S. l.]:Eurographics Association,2004:103-112.
[19]Kammerl J,Blodow N,Rusu R B,et al. Real-time compression of point cloud streams[C]//Proc of IEEE International Conference on Robotics and Automation. Piscataway,NJ:IEEE Press,2012:778-785.
[20]Berger T. Rate-distortion theory[M].[S. l.]:Prentice-Hall,1971.
[21]Shannon C E A. A mathematical theory of communication[J]. ACM SIGMOBILE Mobile Computing&Communications Review,2001,5(1):3-55.
[22] Gersho A,Gray R M. Vector quantization and signal compression[J]. Springer International,1992,159(1):407-485.
[23]Ricordel V. Etude d’un schéma de quantification vectorielle algébrique et arborescente. Applicationàla compression de séquences d’images numériques[D]. Rennes,French:UniversitéRennes,1996.
[24]Conway J H,Sloane N J A. Sphere packing,lattices and groups[J].American Mathematical Monthly,1989,96(6):538-544.
[25]Linde Y,Buzo A,Gray R M. An algorithm for vector quantizer design[J]. IEEE Trans on Communications,1980,28(1):84-95.
[26]Conway J,Sloane N. Fast quantizing and decoding and algorithms for lattice quantizers and codes[J]. IEEE Trans on Information Theory,1982,28(2):227-232.
[27] Ricordel V,Labit C. Vector quantization by packing of embedded truncated lattices[C]//Proc of International Conference on Image Processing. Piscataway,NJ:IEEE Press,2010.
[28]Ricordel V, Labit C. Tree-structured lattice vector quantization[C]//Proc of European Signal Processing Conference. Piscataway,NJ:IEEE Press,1996:1-4.
[29]Torralba A,Murphy K P,Freeman T W. The MIT-CSAIL database of objects and scenes[DB/OL].(2009). http://people. csail. mit.edu/tmertens/textransfer/data/.
[30]The Stanford 3D scanning repository[DB/OL].(2005). http://www-graphics. stanford. edu/data/3dscanrep.