基于扫描数据线线间关系的曲率压缩新算法

尹相宝，花向红，刘金标，龚子桢，郝旦

(1.武汉大学测绘学院，湖北武汉 430079； 2.武汉大学灾害监测与防治研究中心，湖北 武汉 430079；3.武汉市勘测设计研究院，湖北武汉 430022)

基于扫描数据线线间关系的曲率压缩新算法

尹相宝1，2∗，花向红1，2，刘金标3，龚子桢1，2，郝旦1，2

(1.武汉大学测绘学院，湖北武汉 430079； 2.武汉大学灾害监测与防治研究中心，湖北 武汉 430079；3.武汉市勘测设计研究院，湖北武汉 430022)

针对线型扫描点云数据，本文分析比较了多种压缩算法，提出了一种基于扫描数据线线间关系的曲率压缩新算法，并用VC＋＋编程进行试验分析，取得了较好的压缩效果。

三维点云；扫描线线间关系；曲率压缩新算法

1 引 言

三维激光扫描技术以其具有的速度快、精度高、无接触等优点，在现阶段获得了广泛的应用，而其数据的海量性造成了后续数据处理的繁琐和效率低下，因此，如何在保证模型精度的前提下有效压缩三维激光扫描点云数据，以更少的点精确表征地面、地物特征，降低数据储存和后处理的难度，成为众多国内外学者研究的热点。

针对线型扫描点云数据的压缩，目前国内主要的压缩算法就是基于角度、距离、斜率和曲率等的压缩，许捍卫，周卫娟[2]提出的四点法，吴杭彬，刘春[3]在2006年提出的基于斜率变化的压缩法，王玉国，周来水，安鲁陵[4]在2006年提出的基于曲率的自由曲线自适应压缩法，以及李海英[5]在2008年提出的曲率压缩法等，均是此类压缩算法。可以清楚地发现，在这些针对扫描线点云数据压缩的算法中，往往考虑的只是在扫描剖面上各点之间的关系，考虑的只是在一条扫描线上各点反映的物体表面特征的情况，而并没有考虑到相邻扫描线之间各点的关系，并没有考虑到在垂直于扫描剖面方向上各点反映的物体表面特征的情况，这虽然在扫描线方向上可以取得不错的压缩效果，能很好地反映物体的形状，但在垂直于扫描线方向上就会丧失一些物体的表面特征，从而影响建模精度。针对这种情况，本文在试验了多种想法后，在充分考虑了基于曲率的压缩条件的基础上，提出了一种基于数据扫描线线间关系的曲率压缩新算法。

2 基于扫描数据线线间关系的曲率压缩新算法

2.1 算法基本原理

对于三维激光扫描点云数据的压缩，最理想的效果就是所保留的点能很好地反映物体的表面特征，表面变化剧烈处保留较多的点，表面变化平缓处则保留较少的点。对于点云数据扫描线，相对于角度、距离等，曲率能更好地反映其变化状况，可以用来作为线变化的特征量。为了顾及到垂直于扫描线方向上各点之间的关系，该新的压缩算法的基本原理就是，首先利用导数知识计算出各个点(除第一个点和最后一个点)的曲率，然后顺次搜索各点的K邻域，在K邻域内比较各个点的曲率大小，将曲率最大的点保留，其余点删除。

基于扫描线的点云数据是按照邻接关系存储的，根据相邻3个点的平面坐标可以计算中间点的曲率。如图1所示，假设1、2、3点的平面坐标分别为:1(x1，y1)，2(x2，y2)和3(x3，y3)，不妨设该3点拟合出的扫描曲线方程为y＝ax2＋bx＋c，将点1，点2和点3的平面坐标代入，得一三元方程组:

求解方程组(1)，得系数a，b，c的值，进而根据公式(2)计算扫描曲线在2点的一阶和二阶导数:

根据高等代数的知识，利用公式(3)求出2点的曲率。

同理，可计算出除第一个点和最后一个点之外的其余所有点的曲率，一般情况下，扫描线的第一个点和最后一个点反映了物体的边界信息，需要保留。

图1 扫描线曲率求解示意图

在求出每个点(除第一个点和最后一个点)的曲率后，从第二个点开始，顺次搜索至该点距离为d的所有点，比较这些点的曲率大小，曲率最大的点保留，其余点删除，然后再进行下一点的判断。一般情况下，为了能很好地保留物体的表面特征点，避免信息缺失，根据压缩经验，d取扫描线间距的1倍～3倍。

2.2 算法实现

为了评价该新算法的压缩效果，本文采用VC＋＋语言进行了编程实现，其伪代码流程大致如下:

(1)将点云数据读入数组中，为了后续计算方便，点的x，y和z值分别读入一维数组Xin[]，Yin[]和Zin[]中，并将点的总数赋予变量znum。

(2)自定义求解方程组的函数fgroup，计算相邻3点拟合出的扫描曲线方程y＝ax2＋bx＋c。

(3)From i＝2 To znum－1，调用函数fgroup，获得系数a和b的值，计算变量y′＝2ax＋b和y″＝2a的值，从而根据公式计算出i点的曲率k，并将其赋予给一维数组K[]。

(4)提示“输入阈值d:”，将对话框中数据赋予变量d。

(5)自定义寻找最大曲率的函数max。

(6)From i＝2 To znum－1，遍历寻找距离i点小于d的所有点，并将其加入到数组 L[]中，调用函数max，寻找出曲率最大的点，赋予到数组Xout[]，Yout[]和Zout[]中，并将个数赋予给变量num，其余点删除。

(7)定义变量yasuolv＝num/znum。

(8)输出数组Xout[]，Yout[]，Zout[]至文件outfile，返回变量yasuolv。

3 实例效果分析

为了比较验证该曲率压缩新算法的压缩效果，本文采用了云南省昆明市的金刚塔点云数据，由于数据量过于庞大，为节省压缩时间，只采用了整座塔的60%的点云数据。同时，采用了角度弦高法对其进行了压缩，以达到相互比较的目的。图2、图3、图4分别为原始点云，角度弦高法压缩后的点云和曲率压缩新算法压缩后的点云。

图2 原始点云

图3 角度弦高法压缩后点云，压缩率36%

图4 曲率压缩新算法压缩后点云，压缩率31%

从图2、图3和图4中可以看出，在压缩率大致相同的情况下，角度弦高法虽然也较好地保留了物体的特征点，在变化剧烈的地方保留了较多的点，在变化平缓的地方保留了较少的点，但由于没有考虑到扫描线之间的关系，压缩后的点云分布很不均匀，并且在有些地方出现了信息缺失；曲率压缩新算法在点云的分布上和保留物体的特征点上相对合理一些，提取的点无论在扫描线方向上，还是在垂直于扫描线方向上都很好地反映了物体的表面特征，但由于采用了比较传统的K邻域搜索法，其压缩效率要相对低一点。

4 结 论

曲率作为反映点云数据扫描线变化情况的特征量，在许多压缩算法中起着至关重要作用。本文在以往的曲率压缩算法的基础上，充分考虑了扫描数据线之间的关系，提出了这种新的压缩算法，并通过昆明市的金刚塔点云数据的验证，与角度弦高压缩法进行比较，取得了很好的压缩效果，但压缩效率相对低一点。如何改进点的K邻域搜索算法，如何在保证压缩效果的前提下提高压缩效率，仍是今后研究解决的重点。

[1]S.－M.Hur，H.－C.Kim，S.－H.Lee.STL file generation with data reduction by the delaunay triangulation method in reverse engineering[J].The International Journal of Advanced Manufacturing Technology，2002，19:669～678

[2]许捍卫，周卫娟.一种新的等值线数据压缩算法[J].河海大学，理论研究:5～7

[3]吴杭彬，刘春.三维激光扫描点云数据的空间压缩[J].遥感信息(理论研究)，2006，2:22～24

[4]王玉国，周来水，安鲁陵.一种基于曲线拟合与采样的点云数据压缩方法[J].机械科学与技术，2006，25(8):989～992

[5]李海英，花向红，陈远.三维激光点云扫描线曲率压缩算法研究[J].测绘信息与工程，2009，34(5):43～45

[6]李珂珍，娄小平，吕乃光.用于点云曲面重构的数据精简方法研究[J].北京机械工业学院学报，2009，24(1):17～20

A New Compressing Method of Curvature Based on the Relationship Among Scanning Lines

Yin XiangBao1，2，Hua XiangHong1，2，Liu JinBiao3，Gong ZiZhen1，2，Hao Dan1，2
(1.School of Geodesy and Geomatics，Wuhan University，Wuhan 430079，China；2.Hazard Monitoring and Prevention Research Center，Wuhan University，Wuhan 430079，China；3.Wuhan Geotechnical Engineering and Surveying Institute，Wuhan 430022，China)

On account of scanning line point cloud data，kinds of reducing methods are analyzed.On the basis of the analysis，a new compressing method of curvature based on the relationship among scanning lines is put forward，which aims at point clouds on scanning lines and is tested on data about Jingang tower.

3D point clouds；relationship among scanning lines；new compressing method of curvature

1672－8262(2010)04－100－03

P234.4

A

2010—04—16

尹相宝(1985—)，男，在读硕士研究生，主要研究三维激光扫描点云数据处理、精密工程测量理论与方法等。

国家自然科学基金资助项目40901214(项目批准号)，Project 40901214 supported by NSFC；精密工程与工业测量国家测绘局重点实验室开放基金项目资助(PF2009－2)。