基于不规则三角网的渐进加密滤波算法研究
2017-01-07邵为真赵富燕梁周雁
邵为真 赵富燕 梁周雁
(1.山东科技大学 测绘科学与工程学院, 山东 青岛 266000；2.浙江省第一测绘院, 浙江 杭州 310012)
基于不规则三角网的渐进加密滤波算法研究
邵为真1赵富燕2梁周雁1
(1.山东科技大学 测绘科学与工程学院, 山东 青岛 266000；2.浙江省第一测绘院, 浙江 杭州 310012)
在基于点云的地面变形分析中，往往会获取与地面变形监测无关的点云数据，如植被、建筑物和电力线等。为了更好的分析地面变形的程度，需要对非地面点进行剔除。本文应用了一种基于不规则三角网(TIN)的渐进加密滤波算法，并在TerraScan中对该算法进行验证。结果证明该算法非常适用于地表变形监测中滤波处理。
点云 变形分析 TIN 滤波 算法
1 引言
三维激光扫描仪可以快速、高精度、密集地获取研究对象表面的原始点云数据，但是在扫描过程中，对于点的获取却是盲目的，凡是激光脉冲扫到的点都会被获取。所以扫描仪在扫描变形监测区的数据时，不仅扫描了变形区表面的地面点云数据，还扫描了与地面变形监测无关的地物点数据，如植被、建筑物和电力线等[1]。想要对地表进行变形监测就需要把地物点剔除，而且地物点剔除的好坏将直接影响监测结果，这个将地物点去除只保留地面点的过程称为滤波。所以点云滤波是地面变形监测中点云处理的一项关键工作。
目前滤波算法比较多，经典的有基于不规则三角网(TIN)的渐进加密滤波算法、数学形态学滤波算法、移动窗口滤波算法、基于坡度变化的滤波算法、移动曲面滤波算法、迭代最小二乘滤波算法等。本文使用的是由Axelsson于2000年提出的一种基于不规则三角网(TIN)的渐进加密滤波算法[2]。
2 基于TIN的渐进加密滤波算法
2.1 基本原理
该算法的基本思路是：
(1)首先选择种子点，将区域内的点划分成单位间距较大的规则格网，该格网的大小基于该区域的最大结构类型，比如60米×60米为一个单元；
(2)然后寻找每个格网中的最低点作为初始的种子点，使用这些初始的种子点生成一个稀疏的TIN；
(3)之后将满足条件的点不断的加入对TIN加密；
(4)最初，TIN位于这些点的下方，并且TIN的曲率受到参数的限制。在加密过程中，判断如果一个点到最近三角面的垂直距离以及该点到最近顶点连线与三角面的最大夹角小于设定的阈值，则将该点加入地面点集合，接着重新计算TIN，然后再对非地面点集合内的点进行判别。如此迭代处理逐层加密，直到遍历完所有的点，不再增加新的地面点为止，把原始的点云数据分为地面点和非地面点[3]。
该算法克服了传统算法只针对某些特定的连续表面区域有效的局限性，对于城市地形以及复杂的山区地形、森林地区的点云数据都具有适用性[4]。
2.2 基于TerraScan的算法分析
TerraScan是芬兰TerraSolid公司开发的一套专门处理LiDAR点云数据的软件，根据对TerraScan中基于不规则三角网(TIN)的渐进加密滤波算法的分析可知，在利用该算法对点云数据滤波时，滤波参数的设置的恰当与否会对滤波的结果产生重要的影响，其中重要的滤波参数有最大建筑物尺寸的大小、迭代角、迭代距离和最大地形坡度角等。其中，最大建筑物尺寸可以理解为选取种子点的格网大小，若设置的偏小，则可能将非地面点提取到地面点图层中，若偏大，则可能漏掉地形复杂处的地面点，一般在地形较陡的山区设置的参数较小，在建筑物密集的城区则设置的参数较大；迭代角是一个点到三角形最近顶点的连线与这个三角形构成平面的最大夹角值，通常的取值范围在4-10度，值越小，点云里面起伏的变化越小。在平坦地区使用小值(接近4.0)，在山区地形使用较大角度(接近10.0)；迭代距离是迭代时点到三角形平面的最大距离，它可以确保当三角形过大时迭代的起伏不会太大，这样有助于把低矮的建筑物排除在外，迭代距离过大可能会导致低矮建筑物等错分到地面点中，迭代距离过小可能会使地势较陡区域的地面点而被分到了非地面点[5]，迭代距离还与点云的密度有关，但点云密度较大即点云间距较小时，迭代距离一般设置稍小的值；最大地形角即地形中允许出现的最陡的坡度值，对于地形较陡的区域设置的参数应该较大，地势平坦区域设置的参数要小。因此，在对点云进行滤波时，应该针对不同地形选择不同大小的参数，当然在选择参数时还需要对不同的参数进行不断的实验和比较，最终使滤波效果尽量达到最好[6]。
3 基于TerraScan的算法实例
TerraScan中提供了大量的分类工具，包括分离低点、地面点、孤立点、空中点、建筑物点、模型关键点、铁路点等[7]。在TerraScan进行滤波的过程即为分离点云获取地面点的过程。
本文选取了一块既有树木又有房屋的比较典型的点云数据作为实验数据，对其进行点云数据滤波。图1显示的是未分类的原始点云数据，点云个数为4316999，点云的平均密度是4.3pts/m2。
3.1 分离低点
分离低点即把较低的点从其相邻的点中分离出来。经常用于搜索明显低于地面的点，这些点可能是错误的。分离低点的基本原理是：用一个点的高程值与给定距离范围内的每一个点的高程作比较，如果中心点明显低于其他点，这个点将被分离出来。
因为分离地面点，选取种子点时选取的是最低点，但当最低点是错误点而不是地面点时将会影响分类的效果，所以在分离地面点之前分离低点是有必要的。分离低点的具体操作及参数设置如表1所示。
表1 分离低点窗口
对实验数据首先选取表1中参数进行了分离低点操作，然后反复进行了几次，且每次也改变了相应的参数，通过截面图来看分离低点的情况，直到达到了较好的分离结果。图2显示了分离低点后某位置点云的截面图，图中黑色的点表示未分类的点，红色为分离出的低点，由图可以看出成功地将明显低于周围点云的三个点分离了出来。
3.2 地面点分类
通过设置最大建筑物尺寸的大小、迭代角、迭代距离和最大地形坡度角等参数分离地面点。在地面点分类时，针对不同的地形设置不同的参数，在设置参数时可以对不同的参数进行不断的实验和比较，最终达到较好的滤波效果。
通过量距工具大致量取了点云中建筑物的长度，测得最大长度不超过30米，通过旋转观察可知该实验区域坡度也不大，所以分离地面点时设置的参数为：最大建筑物尺寸为30米，迭代角为4度，迭代距离1.4米，最大坡度角为88度。图3显示的是滤波的效果图，其中黄色点为分离出的地面点，黑色点为非地面点，a是滤波后点云俯视图，b是滤波后点云截面图。
4 点云滤波的质量评价
对于点云数据滤波效果的好坏，有定性和定量两种评价指标[8]。
4.1 定性评价
定性评价是通过滤波完成后点云数据的截面图或生成的DEM情况来观察滤波结果的好坏，从而评价算法的优劣，这种方法是在真实地面点不知道的情况下的一种人工评定方法。图4(a)是对滤波后的点云数据生成的DEM图，从图中可以看出比较符合真实地形情况，且很少有毛刺现象，所以滤波效果不错。图4(b)是滤波后某位置点云数据的截面图，其中黄色点是地面点，黑色点是非地面点，可以看出有几个地面点被分在了非地面点中，但是总体滤波效果还不错。
2003年美国国际摄影测量与遥感协会下设的第三委员会提出了交叉表的评价体系，如表2所示。
表2 交叉表结构
表中，a表示正确分类的地面点数，b表示地面点被错分到非地面点中的个数，c表示非地面点被错误分到地面点中的个数，d表示正确分类的非地面点数，e表示参考数据中地面点个数，f表示参考数据中非地面点个数，g表示滤波结果中非地面点数，h则表示滤波结果中非地面点数，n表示总点数。
根据交叉表结构，可以将误差定义为三类：
这种评定方法是假设已知实验数据中每个点的真实类别， 但是现实中的需处理的数据中点的真实类别是不知道的，所以算法的好坏较难这样直观地评价。但是当测区中点云数据的真实点类不知道时，可以将通过人工逐点选择精确分类数据作为参考数据。本实验数据不知道点云的真实类别，只能通过人工的逐点编辑进行精确分类，将精确分类后的数据作为参考数据。由于实验区域点云数据比较多，全部进行逐点分类非常费时，因此定量评价只选取了一部分数据。
使用matlab编程计算一类误差、二类误差和总误差。下面列出了计算第一类误差的程序代码：
西南联大时期，大家生活都很困难，难以为继。梅贻琦校长千辛万苦向教育部要来一笔学生补助金，按规定，他家四个孩子都有资格申请，可是他却一个不准沾边，就是为了避嫌，不让人说闲话。其实，那个时候他的家用相当拮据，早已捉襟见肘，寅吃卯粮，可他宁肯举债，变卖家产，或让夫人磨米粉，做米糕，提篮小卖去补贴家用，也不涉“瓜田李下”之地。因而他在师生中享有崇高威望，带领大家共度时艰，培养了大批优秀人才，铸就了中国教育的一段辉煌历史。
clear all;
clc;
format
first_import=importdata('参考数据地面点.txt');
second_import=importdata('滤波数据非地面点.txt');
[first_m,first_n]=size(first_import);
[second_m,second_n]=size(second_import);
counter=0;
same_coord=[];
for i=1:first_m
for j=1:second_m
if(first_import(i,1)==second_import(j,1)&&first_import(i,2)==second_import(j,2))&&(first_import(i,3)==second_import(j,3))
counter=counter+1;
%same_coord=[same_coord;first_import(i,:)];
end
end
end
firsterror_percent=counter/first_m
计算的一类误差是5.3%，二类误差是0.26%，总误差为2.3%。从误差的结果可知这种算法的一类误差比较大，即将地面点误分为非地面点的概率比较高，而二类误差非常小，即将非地面点误分为地面点的概率非常小。在进行地表的变形监测时，如果将非地面点数据误分为地面点对变形监测的结果影响比较大，而由于地面点的密度比较大，将地面点误分为非地面点则对变形监测的结果影响相对较小，所以该种算法非常适用于地表变形监测中滤波处理。
上面是对使用TerraScan自动滤波算法滤波效果的评价，当然在使用TerraScan滤波时，在自动滤波后还应该通过人工交互的方式进行人工分类，使滤波效果达到满意的水平。
5 结束语
本文针对三维激光扫描技术在地表变形监测中，为剔除多余的非地面点，借鉴了一种基于不规则三角网(TIN)的渐进加密滤波算法，对一块典型的数据通过TerraScan进行了滤波处理和滤波的质量评价，验证了该算法非常适用于地表变形监测中滤波处理。
[1] 丁延辉, 汤羽扬, 周克勤,等. 基于地面三维激光技术的建筑物变形监测研究[J]. 北京测绘, 2011(2):4-6.
[2] Peter Axelsson. DEM generation from laser scanner data using adaptive TIN models [J]. International Archives of Photogrammetry and Remote Sensing, 2000, 33(B4):110-117.
[3] 史建青, 史照良. TerraScan在LiDAR点云滤波中的应用研究[J]. 淮海工学院学报(自然科学版), 2011, 20(3): 46-49.
[4] 曾静静. 基于LiDAR点云与CCD影像的建筑物特征提取[D]. 山东青岛: 山东科技大学, 2011.
[5] 黄金浪. 基于TerraScan的LiDAR数据处理[J]. 测绘通报, 2007(10):13-16.
[6] 蔡庆生. 基于机载LiDAR点云数据滤波方法研究[J]. 北京测绘, 2015(2):25-29.
[7] 黄金浪. 基于TerraScan的LiDAR数据处理[J]. 测绘通报, 2007, (10): 13-16.
[8] 高志国. 海量点云数据滤波处理方法研究[J]. 测绘工程, 2013, 01: 35-38.
The Research of Improved Progressive Triangulated Irregular Network Densification Filtering Algorithm
SHAO Wei-zhen1,ZHAO Fu-yan2,LIANG Zhou-yan1
(1.School of Surveying and Mapping Science and Engineering, Shan dong University of science and Technology, Qingdao Shandong 266000, China；2.The First Surveying and Mapping Institute of Zhejiang Province, Hangzhou Zhejiang 310012,China)
The point cloud data is usually irrelevant to ground deformation monitoring was captured in ground deformation analysis based on point clouds, such as vegetation, bulidings and power line, etc. In order to distinguish the degree of ground deformation effectively, non-terrain point should be rejected. This paper employ the filtering algorithm based on Triangular Irregular Networks, and verify the algorithm in TerraScan. The results well demonstrate this algorithm apply to the filtering of ground deformation monitoring.
point cloud; deformation analysis; TIN; filtering; algorithm
2016-06-14
P221+.1
B
1007-3000(2016)06-5
