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

Optimizing Conical Reconstruction of Linear Point Clouds

针对采用最小圆锥形(包括圆柱、圆锥和圆台)拟合任意轴向的线性模型的点云数据这个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.