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

Optimizing Conical Reconstruction of Linear Point Clouds

作　　者：孙春娟[1,2,3] 朱滨海 王文成[1] 

机构地区：[1]中国科学院软件研究所计算机科学国家重点实验室,北京100190 [2]装备指挥技术学院信息装备系,北京101416 [3]中国科学院研究生院,北京100049 [4]Department of Computer Science, Montana State University, Bozeman, MT59717 USA

出　　处：《计算机辅助设计与图形学学报》2010年第8期1324-1330,共7页Journal of Computer-Aided Design & Computer Graphics

基　　金：国家自然科学基金(60773026,60928006)

摘　　要：针对采用最小圆锥形(包括圆柱、圆锥和圆台)拟合任意轴向的线性模型的点云数据这个NP-难问题,提出一种优化算法.该算法将具有n个点的点云模型自适应地分解成一些子集,并对每个子集用一个圆锥来拟合,使得圆锥包含对应子集内所有点,且拟合圆锥的体积小于最优解的(1+ε)倍.其中圆锥拟合方法的时间复杂度为O(n/ε3),ε是用户给定的拟合误差,优于已有最快拟合方法的复杂度.实验结果表明文中算法是快速有效的.Finding the smallest conical objects （namely cylindrical segments, cones and cone frustums） to enclose a set of linear 3D points is a strong NP-hard problem. In this paper, an approximate algorithm to this NP-problem is presented. The algorithm adaptively divides the set of n points into subsets, and then approximates every subset by a conical object respectively. The algorithm is optimized in the sense that the volume of the approximated conical object is guaranteed to bound at most （1＋ε） times of the actual volume of the point set. The time complexity of the algorithm for producing an approximated cone is O（n ε3）, which improves the time bound in existing methods, where ε is a preset threshold for approximation. Experimental results show that the algorithm is fast and effective.

关 键 词：几何重建 近似算法 最小包围圆锥 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]