基于快速行进最远点的点云精简算法研究.docVIP

 基于快速行进最远点的点云精简算法研究# 严成，朱昊，杨安康，刘京南** （东南大学自动化学院，南京 210096） 5 10 15 20 25 30 35 摘要：在逆向工程中，冗余数据会影响三维重建效率，因此对原始数据进行精简非常重要。 本文提出一种点云精简算法，采用快速行进最远点采样算法对点云数据进行精简，保证了 原始数据的特征并且可由用户设置精简度。通过分析实验数据，结果证明本算法具有计算 速度快、内存消耗少、对点云数据可多分辨率显示的特点。 关键词：点云精简；快速行进；最远点采样 中图分类号：TP274+.5 The research on point cloud simplification based on Fast Marching farthest point sampling YAN cheng, ZHU Hao, YANG Ankang, LIU Jinnan (School of Automation, Southeast University, Nanjing 210096) Abstract: Excessive data will influence the efficiency of three dimension reconstruction in reverse engineering ,so it is important to simplify the initial data. We present a new technique for the simplification of point sampled geometry by using Fast Marching farthest point sampling for point clouds, in order to devise a feature-sensitive simplification algorithm with user-controlled density guarantee. Through the analysis of experiment data, we proved that the algorithm is computationally and memory efficient and multiresolution representations of the input point set. Key words: Point cloud simplification; Fast Marching; Farthest point sample 0 引言 目前在三维检测领域，数据获取所得的数据信息量多，过多的点云数据成为数据计算和 存储的负担，并且并不是所有点对后续建模都是有用的。因此在保证数据精度的前提下，有 效地简化点云数据是点云预处理的重要内容，也是逆向工程前期步骤中的重点。对于点云精 简，目前已有不少常用算法。迭代法[1]不断精简点云，直至精简结果与原来点云相计算后的 误差在一定限度内。该方法能保证较好的误差精度，但随着迭代次数的增加，花费时间较多。 粒子仿真[2]是Turk引入的一种用于重采样多边形面的方法。该方法可根据曲率等属性的变化 自适应重采样密度，能很好的控制采样结果，但速度相对较慢。聚类法[3]是把点云划分成一 些小的子集，再对子集采用简单的方法进行精简，该算法对内存的利用率较高，但对精度和 简度稍有欠缺。本文在保证精简结果特性要求的同时，针对工程实践中点云精简的实时性及 内存消耗的要求，提出基于快速推进最远点算法的精简算法，最终实现了一种计算快速、内 存消耗少的精简算法。同时引入用户控制精简密度，实现了点云数据的多分辨率显示。 1 算法介绍 1.1  快速行进最远点采样算法 快速行进最远点采样算法由 C.Moenning 和 N.A.Dodgson 提出[4]，该算法利用快速行进 基金项目：高等学校博士学科点专项科研基金（20090092110052） 作者简介：严成(1987- ) 男,硕士,主要研究方向:逆向工程 通信联系人：刘京南（1955-），男，教授，博导，主要研究方向：检测技术与自动化装置. E-mail: liujn@seu.edu.cn -1-  40 45  算法来不断扩展采样区域，同时利用最远点采样条件来筛选出符合条件的采样点。最远点采 样法不断地在未知地区域中寻找符合条件的下一个采样点，以此来完成整个目标点云的采 样。Elder 等人证明了在最远点队列中选取下一个采样点既是在已选择点云 S 的带边界 Voronoi 图上(简称 BVD(S))选取满足最远点条件的顶点[5]。因此，不断扩展 Voronoi 图是最 远点采