一种改进的Ensembles点云法向估计算法
|
摘要
近年来点采样几何作为一种新的曲面表示方式,受到了广泛的关注。它无需存储和维护全局一致的拓扑信息,能对复杂的三维模型进行高效的绘制和灵活的几何处理,因此在处理复杂的或者动态改变形状的模型时,基于点的技术较之基于网格的技术有更高的灵活性。法向是点云的一个非常重要的几何信息,对点云的法向进行准确的估计,是在点云上进行其它操作的一个重要的基础步骤,因此对点云法向估计的研究具有重要的实际意义。
给定一个从未知曲面上采样得到的点云,问题是如何准确估计点云中每一个点的法向。一些目前存在的算法,如基于拟合平面的法向估计算法,基于主成分分析的法向估计算法,基于标准奇异值分解的法向估计算法,基于Voronoi的法向估计算法等都可以对点云法向进行估计。但是通过采样得到的点云往往都伴随着大量的噪声,从而影响法向估计的准确性,这就要求点云法向估计的算法要具有较强的鲁棒性。然而上述这些算法的鲁棒性不强,因而导致法向估计的效果不理想。
一种基于统计学习的Ensembles点云法向估计算法,在克服噪声和外部干扰上取得了很好的效果,但是由于其采样的随机性并且采用了相同的采样率,从而容易造成采样不均匀和局部信息丢失,导致估计结果不准确。本文提出了一种改进的Ensembles算法,通过引进分块采样策略及采用自适应的采样率,基本克服了原Ensembles算法的不足。同时,给出了一种新的带有权的平均公式,提高了算法的鲁棒性。
As an alternative surface representation,point-based geometry has been drawn increased attention in recent years.Since this method does not have to store or maintain globally consistent topological information,and can provide efficient rendering and flexible geometry processing of highly complex 3D-models,it is more flexible than triangle meshes while handling highly complex or dynamically changing shapes.For point cloud data,the normal,a geometry information,is so important that the accurate estimation of it is a basic step for the operations on point clouds.
Given a point cloud that presumably sampled from an unknown surface,the important is how to estimate the normal of each point.Some subsistent algorithms,the fitting surface based algorithm;principal component based algorithm;the standard singular value decomposition based algorithm;the Voronoi based algorithm,for example,give the methods that estimate the normal of point clouds.But a point cloud sampled is usually together with noise which affects the accuracy of estimation of normal.So this kind of algorithm requires strong robust.However,the robust of algorithms mentioned above are not strong so that the estimation of normal is not good.
An ensemble normal estimation algorithm based on statistical learning gets a good effect on the data with noise and outliers.But due to the randomicity and the same rate of sample,it is easy to cause non-uniform sample and lose local information,which makes the estimation incorrect.The paper introduces an improved ensembles algorithm.By adding both a sub-block sample strategy and an adaptive sample rate,it covers the shortage of original algorithm.At the same time,the improved algorithm shows a new average formula with weight which enhances the robust of it.
给定一个从未知曲面上采样得到的点云,问题是如何准确估计点云中每一个点的法向。一些目前存在的算法,如基于拟合平面的法向估计算法,基于主成分分析的法向估计算法,基于标准奇异值分解的法向估计算法,基于Voronoi的法向估计算法等都可以对点云法向进行估计。但是通过采样得到的点云往往都伴随着大量的噪声,从而影响法向估计的准确性,这就要求点云法向估计的算法要具有较强的鲁棒性。然而上述这些算法的鲁棒性不强,因而导致法向估计的效果不理想。
一种基于统计学习的Ensembles点云法向估计算法,在克服噪声和外部干扰上取得了很好的效果,但是由于其采样的随机性并且采用了相同的采样率,从而容易造成采样不均匀和局部信息丢失,导致估计结果不准确。本文提出了一种改进的Ensembles算法,通过引进分块采样策略及采用自适应的采样率,基本克服了原Ensembles算法的不足。同时,给出了一种新的带有权的平均公式,提高了算法的鲁棒性。
As an alternative surface representation,point-based geometry has been drawn increased attention in recent years.Since this method does not have to store or maintain globally consistent topological information,and can provide efficient rendering and flexible geometry processing of highly complex 3D-models,it is more flexible than triangle meshes while handling highly complex or dynamically changing shapes.For point cloud data,the normal,a geometry information,is so important that the accurate estimation of it is a basic step for the operations on point clouds.
Given a point cloud that presumably sampled from an unknown surface,the important is how to estimate the normal of each point.Some subsistent algorithms,the fitting surface based algorithm;principal component based algorithm;the standard singular value decomposition based algorithm;the Voronoi based algorithm,for example,give the methods that estimate the normal of point clouds.But a point cloud sampled is usually together with noise which affects the accuracy of estimation of normal.So this kind of algorithm requires strong robust.However,the robust of algorithms mentioned above are not strong so that the estimation of normal is not good.
An ensemble normal estimation algorithm based on statistical learning gets a good effect on the data with noise and outliers.But due to the randomicity and the same rate of sample,it is easy to cause non-uniform sample and lose local information,which makes the estimation incorrect.The paper introduces an improved ensembles algorithm.By adding both a sub-block sample strategy and an adaptive sample rate,it covers the shortage of original algorithm.At the same time,the improved algorithm shows a new average formula with weight which enhances the robust of it.
引文
[1]武剑洁.基于点的散乱点云处理技术的研究[D].武汉:华中科技大学,2004.
[2]Leif Kobbelt,Mario Borsch.A survey of point based techniques in computer graphics [J].Computers & Graphics,2004,28:801-814.
[3]Levoy M,Whitted T.The use of points as display primitives[R].Technical Report TR 85-022.University of North Carolina at Chapel Hill,1985.
[4]Gross M,Pfister H.Point Based Graphics[M].Morgan Kaufmann,2007.
[5]田海山,何援军,蔡鸿明.基于点的计算机图形学综述[J].系统仿真学报Journal of System Simulation,Vol.18,Suppl.1,Aug,2006.
[6]缪永伟.点模型的几何处理和形状编辑[D].浙江:浙江大学,2007.
[7]Mark Pauly.Point Primitives for Interactive Modeling and Processing of 3D Geometry [D].Zurich:Federal Institute of Technology,2003.
[8]Puaty,M,Gross M.Spectral processing of point-sampled geometry[J].In SIGGRAPH,2001:37986.
[9]Jones T,Durand F,Zwicker M.Normal improvement for point rendering[J].IEEE Computer Graphics and Applications,2004,24(4):53-56.
[10]苗兰芳.点模型的表面几何建模和绘制[D].浙江:浙江大学,2005.
[11]邹万红.大规模点云模型几何造型技术研究[D].浙江:浙江大学,2007.
[12]Carr J.C,Beatson R.K,Cherrie,J.B.Reconstruction and representation of 3D objects with radial basis functions[C].In:Proc.Of ACM SIGGRAPH,2001:67-76.
[13]Sharf A,Alexa M,Cohen-Or,D.Context-based surface completion[J].ACM Transaction on Graphics 2004,23(3):878-887.
[14]Ohtake Y,Belyaev A,Alexa M et al.Multi-Level partition of unity implicits[C].Proc.of the ACM SIGGRAPH,2003,22(3):463-470.
[15]Park S,Guo X,Shin Het al.Shape and appearance repair for incomplete Point surfaces [C].In:International Conference on Computer Vision 2005:1260-1267.
[16]Hoppe H,DeRose T,Duchamp T et al.Surface reconstruction from unorganized points [J].Computer Graphics,1992:71-8.
[17]田海山.基于点元的几何造型与绘制[D].上海:上海交通大学,2007.
[18]Zwicker M,Pfister H,van Baar Jet al.Surface splatting[C].In:Proceedings of ACM SIGGRAPH 01,2001:371-378.
[19]Levin D.The approximation power of moving least squares[J].Mathematics of Computation,1998,67(224):1517-1531.
[20]Levin D.Mesh independent surface interpolation[J].Geometric Modeling for Scientific Visualization,2003:37-49.
[21]Alexa M,Behr J,Cohen-Or D et al.Point set surface[C].Proc.of the conference on Visualization 01:21-28.
[22]Alexa M,Behr J,Cohen-Or D et al.Computing and rendering point set surface[J].IEEE Transactions on Visualization and Computer Graphics 9(1):3-15.
[23]Blinn,J.F.A generalization of algebraic surface drawing[J].ACM Transactions on Graphics,1982,1(3):235-256.
[24]Muraki,S.Volumetric shape description of range data using'Blobby Model'[C].In:Proc.of ACM SIGGRAPH,1991:227-235.
[25]Curless B,Levoy M.A volumetric method for building complex models from range images[C].In:Proc.of SIGGRAPH,1996:303-512.
[26]Kazhdan M,Bolitho M,Hoppe H.Poisson surface reconstruction[C].Eurographics Symposium on Geometry Processing,2006:61-70.
[27]Pauly M,Gross M,Kobbelt L.Efficient simplification of point-sampled surfaces [C].Proceedings of IEEE Visualization,2002:163-170.
[28]Pauly M,Keiser R,Kobbelt L et al.Shape modeling with Point-sampled geometry [C].ACM Trnas.GraPh,2003,22(3):641-650.(In Proceedings of Siggraph 2003,Pages 641-650,2003).
[29]Adams B,Dutre P.Interactive Boolean operations on surfel-bounded solids[C].In:Proe.of ACM SIGGRAPH 03:651-656.
[30]Alexa M,Behr J,Cohen-Or D et al.Points set surface[C].In:Proe.Of IEEE Visualization 01,2001:21-28.
[31]Fleishman S,Cohen-Or D,Alexa M et al.Progressive point set surface[J].ACM Trans.Graph,2003,22(4):997-1011.
[32]Heckbert P.S.Fundamentals of texture mapping and image warping[D].University of California at Berkley,1989.
[33]Botsch M,Spernat M,Kobbelt L.Phong splatting[C].In:Proe.of SymP.On Point-Based Graphics 04,2004.
[34]贺美芳.基于散乱点云数据的曲面重建关键技术研究[D].南京:南京航空航天大学,2006.
[35]Guo B.Surface reconstruction:from points to splines[J].Computer Aided Design,1997,29(4):269-277.
[36]Chen X.Surface modeling of range data by constrained triangulation[J].Computer Aided Design,1994,26(3):632-645.
[37]姜寿山,Peter Eberhard.多边形和多面体顶点法矢的数值估计[J].计算机辅助设计与图形学学报,2002,14(8):763-767.
[38]PAULY M,KEISER R,KOBBELT L et al.Shape modeling with point-sampled geometry [C].In Proceedings of ACM SIGGRAPH,2003,ACM Pres:641.650.
[39]Mitra NJ,Nguyen A,Guibas L.Estimating surface normals in noisy point cloud data[J].Specia]Issue of International Journal of Computational Geometry and Applications 2004;14(4-5):261-276.
[40]Dey TK,Li G,Sun J.Normal estimation for point clouds:A comparison study for a Voronoi based method[C].In:Proc.Eurographics symposium on point-based graphics 2005,2005:39-46.
[41]Gopi M,Krishnan S,Silva C.Surface reconstruction based on lower dimensional localized Delaunay triangulation[J].Computer Graphics Forum,2000,19(3):467-78.
[42]Hu G,Xu J,Miao L,Peng Q.Bilateral estimation of vertex normal for point-sampled models[C].In:Proc.computational science and its applications(ICCSA 2005),2005:758-68.
[43]Lee Y,Yoon M,Lee S,Ivrissimtzis I et al.Ensembles for surface reconstruction [C].In:Proc.Pacific graphics,2005:115-7.
[44]Mincheol Yoon,Yunjin Lee,Seungyong Lee et al.Surface and normal ensembles for surface reconstruction[J].Computer-Aided Design,2007,39(5):408-420.
[45]钱锦锋.逆向工程中的点云处理[D].浙江:浙江大学,2008.
[46]王仁宏.数值逼近[M].北京:高等教育出版社,1999.
[47]赵任亮.基于Voronoi图的空间关系计算研究[D].长沙:中南大学,2002.
[48]求伟,郭伟青,李韦良,利用Voronoi图改进离散数据重构曲面算法[J].计算机系统应用,2009年第1期.
[49]Vladimir N.Vapnik.统计学习理论的本质[M].清华大学出版社,2000.
[50]Vapnik V.Statistical Learning Theory[M].John Wiley,New York,1998.
[51]AMENTA N.,BERN M.Surface reconstruction by voronoi filtering[J].Discr.Comput.Geom.22,1999:481-504.
[52]DEY T.K.,GOSWAMI S.Provable surface reconstruction from noisy samples[C].In Proc.20th.Annu.Sympos.Comput.Geom,2004:330.
[53]Buss SR,Fillmore JP.Spherical averages and applications to spherical splines and interpolation[J].ACM Transactions on Graphics,2001,20(2):95-126.
[2]Leif Kobbelt,Mario Borsch.A survey of point based techniques in computer graphics [J].Computers & Graphics,2004,28:801-814.
[3]Levoy M,Whitted T.The use of points as display primitives[R].Technical Report TR 85-022.University of North Carolina at Chapel Hill,1985.
[4]Gross M,Pfister H.Point Based Graphics[M].Morgan Kaufmann,2007.
[5]田海山,何援军,蔡鸿明.基于点的计算机图形学综述[J].系统仿真学报Journal of System Simulation,Vol.18,Suppl.1,Aug,2006.
[6]缪永伟.点模型的几何处理和形状编辑[D].浙江:浙江大学,2007.
[7]Mark Pauly.Point Primitives for Interactive Modeling and Processing of 3D Geometry [D].Zurich:Federal Institute of Technology,2003.
[8]Puaty,M,Gross M.Spectral processing of point-sampled geometry[J].In SIGGRAPH,2001:37986.
[9]Jones T,Durand F,Zwicker M.Normal improvement for point rendering[J].IEEE Computer Graphics and Applications,2004,24(4):53-56.
[10]苗兰芳.点模型的表面几何建模和绘制[D].浙江:浙江大学,2005.
[11]邹万红.大规模点云模型几何造型技术研究[D].浙江:浙江大学,2007.
[12]Carr J.C,Beatson R.K,Cherrie,J.B.Reconstruction and representation of 3D objects with radial basis functions[C].In:Proc.Of ACM SIGGRAPH,2001:67-76.
[13]Sharf A,Alexa M,Cohen-Or,D.Context-based surface completion[J].ACM Transaction on Graphics 2004,23(3):878-887.
[14]Ohtake Y,Belyaev A,Alexa M et al.Multi-Level partition of unity implicits[C].Proc.of the ACM SIGGRAPH,2003,22(3):463-470.
[15]Park S,Guo X,Shin Het al.Shape and appearance repair for incomplete Point surfaces [C].In:International Conference on Computer Vision 2005:1260-1267.
[16]Hoppe H,DeRose T,Duchamp T et al.Surface reconstruction from unorganized points [J].Computer Graphics,1992:71-8.
[17]田海山.基于点元的几何造型与绘制[D].上海:上海交通大学,2007.
[18]Zwicker M,Pfister H,van Baar Jet al.Surface splatting[C].In:Proceedings of ACM SIGGRAPH 01,2001:371-378.
[19]Levin D.The approximation power of moving least squares[J].Mathematics of Computation,1998,67(224):1517-1531.
[20]Levin D.Mesh independent surface interpolation[J].Geometric Modeling for Scientific Visualization,2003:37-49.
[21]Alexa M,Behr J,Cohen-Or D et al.Point set surface[C].Proc.of the conference on Visualization 01:21-28.
[22]Alexa M,Behr J,Cohen-Or D et al.Computing and rendering point set surface[J].IEEE Transactions on Visualization and Computer Graphics 9(1):3-15.
[23]Blinn,J.F.A generalization of algebraic surface drawing[J].ACM Transactions on Graphics,1982,1(3):235-256.
[24]Muraki,S.Volumetric shape description of range data using'Blobby Model'[C].In:Proc.of ACM SIGGRAPH,1991:227-235.
[25]Curless B,Levoy M.A volumetric method for building complex models from range images[C].In:Proc.of SIGGRAPH,1996:303-512.
[26]Kazhdan M,Bolitho M,Hoppe H.Poisson surface reconstruction[C].Eurographics Symposium on Geometry Processing,2006:61-70.
[27]Pauly M,Gross M,Kobbelt L.Efficient simplification of point-sampled surfaces [C].Proceedings of IEEE Visualization,2002:163-170.
[28]Pauly M,Keiser R,Kobbelt L et al.Shape modeling with Point-sampled geometry [C].ACM Trnas.GraPh,2003,22(3):641-650.(In Proceedings of Siggraph 2003,Pages 641-650,2003).
[29]Adams B,Dutre P.Interactive Boolean operations on surfel-bounded solids[C].In:Proe.of ACM SIGGRAPH 03:651-656.
[30]Alexa M,Behr J,Cohen-Or D et al.Points set surface[C].In:Proe.Of IEEE Visualization 01,2001:21-28.
[31]Fleishman S,Cohen-Or D,Alexa M et al.Progressive point set surface[J].ACM Trans.Graph,2003,22(4):997-1011.
[32]Heckbert P.S.Fundamentals of texture mapping and image warping[D].University of California at Berkley,1989.
[33]Botsch M,Spernat M,Kobbelt L.Phong splatting[C].In:Proe.of SymP.On Point-Based Graphics 04,2004.
[34]贺美芳.基于散乱点云数据的曲面重建关键技术研究[D].南京:南京航空航天大学,2006.
[35]Guo B.Surface reconstruction:from points to splines[J].Computer Aided Design,1997,29(4):269-277.
[36]Chen X.Surface modeling of range data by constrained triangulation[J].Computer Aided Design,1994,26(3):632-645.
[37]姜寿山,Peter Eberhard.多边形和多面体顶点法矢的数值估计[J].计算机辅助设计与图形学学报,2002,14(8):763-767.
[38]PAULY M,KEISER R,KOBBELT L et al.Shape modeling with point-sampled geometry [C].In Proceedings of ACM SIGGRAPH,2003,ACM Pres:641.650.
[39]Mitra NJ,Nguyen A,Guibas L.Estimating surface normals in noisy point cloud data[J].Specia]Issue of International Journal of Computational Geometry and Applications 2004;14(4-5):261-276.
[40]Dey TK,Li G,Sun J.Normal estimation for point clouds:A comparison study for a Voronoi based method[C].In:Proc.Eurographics symposium on point-based graphics 2005,2005:39-46.
[41]Gopi M,Krishnan S,Silva C.Surface reconstruction based on lower dimensional localized Delaunay triangulation[J].Computer Graphics Forum,2000,19(3):467-78.
[42]Hu G,Xu J,Miao L,Peng Q.Bilateral estimation of vertex normal for point-sampled models[C].In:Proc.computational science and its applications(ICCSA 2005),2005:758-68.
[43]Lee Y,Yoon M,Lee S,Ivrissimtzis I et al.Ensembles for surface reconstruction [C].In:Proc.Pacific graphics,2005:115-7.
[44]Mincheol Yoon,Yunjin Lee,Seungyong Lee et al.Surface and normal ensembles for surface reconstruction[J].Computer-Aided Design,2007,39(5):408-420.
[45]钱锦锋.逆向工程中的点云处理[D].浙江:浙江大学,2008.
[46]王仁宏.数值逼近[M].北京:高等教育出版社,1999.
[47]赵任亮.基于Voronoi图的空间关系计算研究[D].长沙:中南大学,2002.
[48]求伟,郭伟青,李韦良,利用Voronoi图改进离散数据重构曲面算法[J].计算机系统应用,2009年第1期.
[49]Vladimir N.Vapnik.统计学习理论的本质[M].清华大学出版社,2000.
[50]Vapnik V.Statistical Learning Theory[M].John Wiley,New York,1998.
[51]AMENTA N.,BERN M.Surface reconstruction by voronoi filtering[J].Discr.Comput.Geom.22,1999:481-504.
[52]DEY T.K.,GOSWAMI S.Provable surface reconstruction from noisy samples[C].In Proc.20th.Annu.Sympos.Comput.Geom,2004:330.
[53]Buss SR,Fillmore JP.Spherical averages and applications to spherical splines and interpolation[J].ACM Transactions on Graphics,2001,20(2):95-126.