用圆锥体拟合线性模型点云数据的优化计算.pdf

第22卷第8期计算机辅助设计与图形学学报Vol.22No.8
2010年8月JournalofComputer-AidedDesign&ComputerGraphicsAug.2010

用圆锥体拟合线性模型点云数据的优化计算

1,2,3)4)1)
孙春娟,朱滨海,王文成
1)(中国科学院软件研究所计算机科学国家重点实验室北京100190)
2)(装备指挥技术学院信息装备系北京101416)
3)(中国科学院研究生院北京100049)
4)(DepartmentofComputerScience,MontanaStateUniversity,Bozeman,MT59717USA)
([e-mail])

摘要:针对采用最小圆锥形(包括圆柱、圆锥和圆台)拟合任意轴向的线性模型的点云数据这个NP-难问题,提出
一种优化算法.该算法将具有n个点的点云模型自适应地分解成一些子集,并对每个子集用一个圆锥来拟合,
使得圆锥包含对应子集内所有点,且拟合圆锥的体积小于最优解的(1+E)倍.其中圆锥拟合方法的时间复杂度为
O(nPE3),E是用户给定的拟合误差,优于已有最快拟合方法的复杂度.实验结果表明文中算法是快速有效的.

关键词:几何重建;近似算法;最小包围圆锥
中图法分类号:TP391

OptimizingConicalReconstructionofLinearPointClouds

SunChunjuan1,2,3),ZhuBinhai4),andWangWencheng1)
1)(StateKeyLaboratoryofComputerScience,InstituteofSoftwareChineseAcademyofSciences,Beijing100190)
2)(DepartmentofInformationEquipment,AcademyofEquipmentCommandandTechnology,Beijing101416)
3)(GraduateUniversityofChineseAcademyofSciences,Beijing100049)
4)(DepartmentofComputerScience,MontanaStateUniversity,Bozeman,MT59717USA)

Abstract:Findingthesmallestconicalobjects(namelycylindricalsegments,conesandconefrustums)
toencloseasetoflinear3DpointsisastrongNP-hardproblem.Inthispaper,anapproximate
algorithmtothisNP-problemispresented.Thealgorithmadaptivelydividesthesetofnpointsinto
subsets,andthenapproximateseverysubsetbyaconicalobjectrespectively.Thealgorithmis
optimizedinthesensethatthevolumeoftheapproximatedconicalobjectisguaranteedtoboundat
most(1+E)timesoftheactualvolumeofthepointset.Thetimecomplexityofthealgorithmfor
producinganapproximatedconeisO(nPE3),whichimprovesthetimeboundinexistingmethods,
whereEisapresetthresholdforapproximation.Experimentalresultsshowthatthealgorithmisfast
andeffective.

Keywords:geometricreconstruction;approximationalgorithm;thesmallestenclosingcone

随着三维数字化扫描测量设备的发展,人们能曲面是NURBS曲面、B样条曲面等.利用这些曲面
够方便地获得大量的点云数据,加快了对点云数据进行拟合时,往往需要将多张曲面进行拼合,以适应
高效处理技术研究的步伐.对点云数据的一种重要实体曲面切矢变化较大的情况.但这样会导致曲面
处理方法就是对其进行曲面拟合,以减少处理计算拟合的误差较大[1],不能很好地满足应用需求.如在
的开销,并对客观对象进行简洁表达.目前较常用的医学、数字化农林业和制造业等一些应用中,要求有

收稿日期:2009-08-23;修回