基于快速成型技术的点云压缩算法研究

万程辉，程效军，贾东峰

(1.同济大学测量与国土信息工程系，上海200092;2.南昌工程学院水利与环境工程学院，江西南昌330099)

基于快速成型技术的点云压缩算法研究

万程辉1，2，程效军1，贾东峰1

(1.同济大学测量与国土信息工程系，上海200092;2.南昌工程学院水利与环境工程学院，江西南昌330099)

研究一种两次分层压缩点云数据的方法，将等高距和其允许误差设为阈值压缩数据。试验证明，通过设置适当的切片厚度，该方法数据压缩率大、算法执行效率高、特征保持较好、三维模型表面光滑，具有良好的应用价值。

快速成型技术;切片厚度;压缩率;三维模型

一、引 言

在逆向工程和快速成型技术中，海量散乱点云的特征提取较为复杂和困难。基于点云数据的特征提取主要有以下方式:① 点云数据建立网格模型，在三角面片上提取特征点和特征线等［1-3］，其优点是算法成熟，但从总体建模来讲，计算时间较长，且三角面片建立有一些缺陷;②从点云直接提取特征点，主要通过法矢或平面截取等方式获取特征线、轮廓线和骨架线等［4-8］，特点是算法相对复杂，但计算时间较长;③由于前两种算法计算时间都较长，可对海量点云数据先进行压缩，再对特征线进行提取，这样可节省计算时间［9-10］。

本文提出一种两次分层提取数据的方法，即一种微小切片方法，用于提取特定方向的点云数据，对海量数据压缩时可提高计算速度，且能较好地保留特征。

二、点云数据压缩算法

1.点云压缩的算法

点云压缩的算法很多，不同类型的点云数据可以采取相应的压缩方法。常用的算法有:最小距离法、均匀网格采样法、平均距离压缩算法、八叉树压缩算法等。这些算法对海量点云数据的压缩主要考虑3个方面:①压缩量;②数据的曲率特征保留;③算法执行效率。这些算法存在的问题是:执行效率高、压缩量大的算法，往往特征保留少，如最小距离法、均匀采样法等;考虑曲率特征保留，算法相对复杂，计算执行效率低，如八叉树、自适应曲率等压缩算法。本文通过基于快速成型技术方法，对数据进行分层，在每层中提取一定厚度的数据，切片厚度在点云之间距离范围时，提取距离小于该厚度的数据，以达到压缩数据的效果，并能较好地保留物体轮廓特征，且算法执行效率高，压缩率大。

2.快速成型技术原理

快速成型技术原理是“分层制造，逐层叠加”，快速建立模型。根据模具的形状，每次做成一个具有一定微小厚度和特定形状的截面，称为切片，再把切片逐层粘结起来得到立体的模具［11］。三维激光扫描得到的点云数据具有海量、散乱、线性扫描和三维算法复杂等特点，将点云数据根据物体的特征方向，进行切片提取数据，投影到平面上获取物体的特征线［12］。为了生成等高线，点云数据用了分层平面投影的方法［5］，将Z+1和Z层之间的数据平面投影到高程平面Z上，如图1所示。从图1得知，分层的宽度会影响点云数据的提取。宽度过大时，点云投影过密，形成平面上的点云带，不利于提取等高线特征，在等高线的特征细节上有差异;宽度小时，点云产生断裂，形成不连续的数据，造成等高线的特征丢失。

图1 分层提取的点云

三、基于快速成型技术的压缩算法

1.点云切片的生成

根据快速成型技术，本文提出利用微小切片来提取点云进行数据压缩的方法，以克服分层剖切造成的点云数据不均匀问题，从而控制分层的厚度，避免分层过厚或过薄，同时舍去特征线提取时的冗余数据。

点云数据经过预处理后，得到以高程方向为序的点云数据。为了快速提取所需点云数据，对其进行两次分层。

第一次分层，算出坐标范围为(Xmin，Ymin，Zmin)～(Xmax，Ymax，Zmax)，生成最小包围盒，如图2(a)所示。按Z方向高度H和等高距h，进行第一次分层，每一层大小为(Xmax－Xmin，Ymax－Ymin，h)，每层的Z坐标范围为(Z，Z+h)，将符合要求的数据存入每层矩形包围盒中，如图2(b)所示。

第二次分层，在第一次分层包围盒内的数据中，提取等高线上下允许厚度的点云数据，形成一条微小切片，带宽大小为等高线的容许误差Δ，微小带状包围盒的大小为(Xmax－Xmin，Ymax－ Ymin，Z± Δ)，将符合要求的数据存入每层的微小切片中，如图2(c)所示。

图2 点云数据的分层切片

2.切片厚度设置

点云数据提取数据宽度设置在属性允许误差Δ内。这是一个关键阈值，提取的点云数据宽度与点云数据的分布密度有关，而点云数据分布密度与扫描密度设置和扫描对象的远近相关。为了便于调节，在算法中设置范围为等高距大小的 1/10～1/20，如图3所示。如等高线在数字地形测量中的容许误差为等高距的1/15，若等高距为0.5 m时，提取的范围为Z±(0.5×1/15)的高程厚度，根据大比例尺地形图机助制图规范，图根点高程中误差不大于等高距的1/10，满足等高线精度要求［13］。微小切片的宽度由等高距和设定的阈值两个值组成。

图3 等高距与阈值设置

3.算法流程

两次分层压缩数据的算法流程图如图4所示。

图4 算法流程图

四、实例分析

本文选取典型的点云数据，用Visual C++6.0在PC上编程实现和验证本文算法。以三维激光扫描仪扫描的华佗雕像为例，扫描的海量点云数据总数为708 987个，整个雕像的高度为3.239 5 m。为观察效果，截取雕像头部数据，图5为不同等高距获取的压缩点云数据，图6为不同等高距的建模效果。

1)利用快速成型技术压缩点云数据，两次分层可以选取等高距h与允许误差Δ的大小灵活改变切片厚度。为了比较压缩效果，固定选取1/15阈值计算切片厚度，如图5所示，不同的等高距压缩数据，等高距与阈值的乘积使切片厚度不同，比较可知，特征保留也不同。

图5 微小分层切片对点云的压缩

从图5可以看出适当的切片厚度能保持较好的特征，如0.002 m与0.005 m的等高距，压缩数据均匀，保持较好的轮廓特征。0.001 m的等高距压缩数据过大，特征损失也大。0.01 m与0.02 m的等高距过大，数据抽取间隔过大，数据特征损失大。

2)利用Geomagic软件对压缩数据进行建模。记录建模时间，建模耗时如表1所示，阈值为等高距1/15的压缩数据与全部数据比较，压缩率达到85%以上，压缩数据建模耗时少74 s。建模效果如图6所示。

图6 利用Geomagic建模比较

图5(a)为用全部数据所建模型，细节详细但数据冗余，三角面片建模复杂，耗时长，且模型不光滑，表面粗糙。

图5(c)为0.002 m等高距压缩数据，建模速度快，特征保持良好，模型光滑，具有较好的模型效果。

图5(b)至图5(e)压缩数据量稍少，建模效果次之;图5(f)等高距过大，建模特征效果较差。

3)图4压缩数据与图5建模效果得到的微小切片的厚度是压缩的关键因素。

当等高距过大时，如图5(f)，分层切片中数据提取厚度变大，压缩厚度也过大，物体的特征损失较多，建模效果差，需要调节阈值，如变大1/10，切片压缩厚度变小，使点云数据更好地保留特征。

图5(c)为0.002 m等高距，分层与压缩间距适当，压缩数据均匀，较好地保留了特征，本实例设置0.002 m等高距和1/15的允许误差是压缩数据的合适阈值。

表1 点云数据压缩率

五、结束语

快速成型技术主要应用在模型的分层建模叠加成型方面，利用两次分层来压缩点云数据，设定等高距与切片厚度阈值来压缩数据。通过不同的等高距，得到不同的压缩数据，对数据压缩率、建模时间和建模效果进行了比较，可知设置适当的等高距和分层阈值，可使压缩数据保持良好的特征，压缩数据率大，且算法简单，执行效率高。利用快速成型技术对点云数据进行压缩，可较好地保留整个特征，对分层提取物体的特征具有良好的应用价值。

［1］ 任自珍，岑敏仪，张同刚，等.基于等高线形状分析的LiDAR建筑物提取［J］.西南交通大学学报，2009，44(1):83-88.

［2］ 姜琳琳，赵晓明，洪波.LiDAR数据结合特征线获取高精度DEM及DOM［J］.黑龙江工程学院学报:自然科学版，2009，23(2):33-35.

［3］ KILIAN J，HAALA N，ENGLICH M.Capture and Evaluation of Airborne Laser scanner Data［C］∥International Archives of Photogrammetry and Remote Sensing.Vienna:［s.n.］，1996.

［4］ 王亚美，赵萍.一种基于点云数据的直接分层算法［J］.沈阳理工大学学报，2009，28(3):39-41.

［5］ 吴杭彬，刘春.激光扫描数据的等值线分层提取和多细节表达［J］.同济大学学报:自然科学版，2009，37(2):267-271.

［6］ VERROUST A，LAZARUS F.Extracting Skeletal Curves from 3D Scattered Data［C］∥Shape Modeling International’99.Aizu Wakamatsu:［s.n.］，1999.

［7］ RIANMORA S，KOOMSAP P，HAI D P V.Selective Data Acquisition for Direct Integration of Reverse Engineering and Rapid Prototyping［J］.Virtual and Physical Prototyping，2009，4(4):227-239.

［8］ KUMBHAR V K，PANDEY P M，RAO P V M.Improved Intermediate Point Curve Model for Integrating Reverse Engineering and Rapid Prototyping［J］.Int J Adv Manuf Technol，2008(37):553-562.

［9］ 刘春，陆春.三维激光扫描数据的压缩与地形采样［J］.遥感信息，2005，2(2):96-102.

［10］ 徐景中，万幼川，张圣望.LiDAR地面点云的简化方法研究［J］.测绘信息与工程，2008，33(1):32-34.

［11］ 焦向东，佟泽民.分层制造法的材料技术及其发展［J］.中国机械工程，2000，11(5):582-584.

［12］ 王亚美，赵萍.一种基于点云数据的直接分层算法［J］.沈阳理工大学学报，2009，28(3):39-41.

［13］ 国家技术监督局.GB14912-94大比例尺地形图机助制图规范［S］.北京:中国标准出版社，1994.

A Point Cloud Compression Algorithm Based on Rapid Prototyping

WAN Chenghui，CHENG Xiaojun，JIA Dongfeng

0494-0911(2012)06-0010-03

P208

B

2011-07-15

国家自然基金项目(40971241)

万程辉(1975—)，男，江西南城人，讲师，博士生，主要研究方向为三维激光扫描数据处理。