基于聚类与重构的河流区域滤波方法

易 航，李 浩，杨 彪，韦立新，蒋建平

（1.河海大学 地球工程与工程学院，江苏 南京 210098；2.长江下游水文水资源勘测局,江苏 南京 210010）

基于聚类与重构的河流区域滤波方法

易 航1，李 浩1，杨 彪1，韦立新2，蒋建平2

（1.河海大学 地球工程与工程学院，江苏 南京 210098；2.长江下游水文水资源勘测局,江苏 南京 210010）

研究河流区域水体点云的分布特征与相互关系，提出基于特征聚类的点云分割与基于LLE算法的邻近点点云重构滤波方法。通过统计网格内点云的特征参数，进行点云分割并滤除水面点，再利用LLE算法的邻近点构建约束条件进行点云重构，分离近岸船只点云与岸堤点云的边缘，最后利用船只点云的独立性进行二值连通域标记与滤除，从而实现河流区域的点云滤波。实验表明，该方法能够滤除90%以上的水面点云与大部分船只点云。

水体点云；特征参数；聚类分析；点云重构

机载激光雷达（LiDAR）技术是目前应用最广泛的高分辨率测量技术之一。LiDAR系统获取到地面的三维点云信息，并记录多次反射的强度信息。由于陆地测量的机载LiDAR工作波长一般为1 040～1 060 nm[1]，位于水体的强吸收带，所以理想条件下不反射激光脉冲。但在实际中，河流区域的船只等物体会产生反射信号形成船只点云，且受到无人机飞行路线与水面反射的影响，在特殊情况下水面也会产生反射信号，形成水面点云。水面点云与船只点云都为非地面点，且相互嵌套，分布较为复杂。河流区域点云滤波的目的就是将河流区域非地面点滤除[2-4]。

河流区域非地面点滤除在水体边缘提取中较为常见[5,6]。本文通过对河流区域的点云分布特性进行研究，利用水面点云均匀分布与船只点云独立性明显的特点，参考杨晓云[7]等所提出描述数据分布形态的统计量偏度与峰值概念，提出了基于特征聚类的点云分割和基于LLE算法的邻近点点云重构的滤波方法。该方法能从河流区域点云数据中有效剔除非地面点云。

1 基于特征聚类的点云分割与LLE算法

1.1 基于特征聚类的点云分割

点云分割是利用目标区域点云的空间、几何和纹理等特征进行划分，使得处于同一区域内的点云具有相似的分布特征。本文利用点云高程分布的偏度、峰度与均值进行特征聚类，实现点云分割。

偏度是统计数据分布偏斜方向和程度的度量。偏度为0时，表示其数据点云分布与正态分布的偏离程度相同，偏度的计算公式如下：

式中，N为格网内的点数；si为格网内点的高程；i∈（1,2,3…N）；σ为格网内点的标准差，u为高程均值。标准差和算术平均值的计算公式如下：

峰度是描述数据点云高程分布形态陡缓程度的量度，峰度为0表示总体数据分布与正态分布的陡缓程度相同。峰度的计算如式如下：

由于水面点高程变化不大，而非水面点大多变化明显，因此利用偏度、峰度与高程均值对格网内的点云进行特征聚类，可有效分割出水面点。

1.2 LLE算法

局部线性嵌入（locally linear embedding，LLE）算法是Roweis和Saul于2000年提出的一种非线性降维方法，基于高维空间中相邻或相关的点映射到低维空间中也同样地相邻或相关的几何思想[8]。LLE算法流程可以归结为以下几步：

1）计算出每个样本点的k个邻近点，把相对于所求样本点欧氏距离最近的k个样本点规定为所求样本点的k个邻近点。k是预先设定的值。

2）计算样本点的局部重建权值矩阵。这里定义一个成本函数，其函数形式如下所示：

式中，xij(j=1,2…,k)为xi的k个邻近点；为xi与xij之间的权值，并满足如下公式：

3）将所有的样本点映射到低维空间中。

1.3 点云重构效率优化与权值选择

在利用k最邻近点实现局部点云重构、分离点云边缘时，本文采用3×3窗口搜索邻近点。如图1所示，点云边缘窗口密度必然小于内部窗口密度，且点云重构的目的是分离边缘，只需处理点云块边缘上的点，因此只对点数量处于一定阈值内的窗口进行处理可以极大地提高效率。重构时根据点号储存两套坐标：原始坐标和重构后坐标。滤波后输出原始坐标，因此在构建重构权值公式时无需考虑点云拓扑结构的变化，但若选权不正确，会导致误分类。如图1所示，中心黑色点为重构点，红色和紫色点为邻近点。由于舰船靠岸较近，下方岸堤上的紫色点也被归为邻近点。若按照将距离向量作为权的原则，岸堤上的点对重构点影响远大于船只上的点。

图1 点云边缘密度、内部密度和k邻近点

针对构建权值公式这个问题，考虑到一般情况下邻近点群内同类型点占大多数，所以，不应以距离大小作为权，而是将方向作为权，并与邻近k个点的方向的权等价再进行重构。先将重构点与邻近点的方向向量单位化，并分别用与坐标轴平行的向量表示，单位化公式如下：

表示每个邻近点对重构点造成影响的方向； (xi、yi)(i=1,2…,N)表示重构点原始坐标；(xij、yij)(j=1,2…,k)表示重构点的k个邻近点坐标，重构点的位移距离为中心点与这k个点的平均距离：

重构点重构方向向量为：

重构点重构后坐标（xi'，yi'）为：

2 基于特征聚类与点云重构的滤波方法

2.1 算法原理

河流区域点云数据中，非地面点主要包括水面与船只等非地面点云，其特性为非连续性块状孤立存在或相互嵌套，主要有4种分布情况:①图2左上方区域水面点云独立存在；②图2右下方区域船只点云独立存在；③图2中心区域水面与船只点云相互嵌套；④图2左下方近岸船只点云。而传统滤波算法大多针对的是连续表面区域，带有一定的局限性[9]。

图2 水面点云与船只点云嵌套存在

本文通过分析水体区域非地面点云分布特征，利用水面点云均匀分布、高差变化较小和船只点云独立性明显的特点，利用基于偏度与峰度的特征聚类，将大部分水面点云滤除。剩下的非地面点大部分为孤立船只点云与近岸船只点云，利用其独立性可通过二值连通域标记的方法将独立性明显的船只点云进行滤除,但近岸船只离岸较近难以标记。本文算法通过先利用点云k最邻近点间欧氏距离构建约束条件进行点云重构，对独立点云块边缘的激光点重新赋予三维坐标，使其向点云块内部聚拢，近岸船只与岸堤点云边缘相互远离，从而增强点云块的独立性。若一次重构独立性还不明显，可进行多次重构，最后利用二值连通域的方法对孤立船只与近岸船只点云进行标记与滤除。

2.2 算法具体过程

本文算法的基本描述思路如下：

1）首先对点云进行分块。为保证格网内有足够多的点进行参数统计与足够多的邻近点，且格网应当尽量小以提高精度，通过统计陆地与水体杂质点云密度得出格网大小。

2）利用偏度与峰度和高程均值进行特征聚类，设定阈值，并选取一块典型水体杂质区域统计其特征参数作为标准，实现点云分割，从而滤除水面点。

3）利用k最邻近点实现局部点云重构提高近岸船只点云独立性，分离船只点云与地面点云边缘。

4）最后对重构后的点云数据提取其离群点集，将点云数据按照格网块转化为二值图像，再利用王静等二值图像连通域的分段标记算法[10]对二值图像进行连通域标记，滤除格网数量处于一定阈值内的点云块，将滤除后的点云块数据进行显示。观察滤除效果是否明显，若不明显，重复第3～5步。对重构后的点云图像进行迭代，多次重构分离边缘，直至达到理想滤除效果。算法主要流程如图3所示。

图3 基于特征聚类与邻近点重构的算法流程

3 实验分析

3.1 本文算法整体滤波效果

为了判断本文算法的有效性，采用长江河道九江至湖口张家洲河段点云数据，累计扫描面积约15×4 km2，共采集 6 586 465个激光点，平均点距1．4 m，点云密度0．51 个/m2。图4为总体滤波效果图，图中独立块状点云一般为船只，且存在较多近岸船只点云，带状点云一般为水面点，其中镶嵌大量船只等非水面点云。实验区域总体上点云分布情况较为复杂，滤波后共滤除134 917个点（图中红色点），可观察到非地面点已基本被滤除。

图4 总体滤波效果图

3.2 基于偏度与峰度的特征聚类效果

图5为对图2中相互嵌套的船只与水面点云进行特征聚类前后的对比图，可明显观察到水体区域内水面点已基本滤除，且特征聚类后的水体区域仅存在孤立船只点云和少量与孤立船只点云较近的水面点，但在之后的二值连通域标记中被一同滤除。

图5 特征聚类后点云图

3.3 点云重构分离边缘效果

图6为使用基于参数统计的点云分割算法对水面点进行滤除之后的数据进行基于k最邻近点点云重构前后的局部效果对比图，可观察到近岸船只点云与岸堤点云边缘被分离开来，近岸舰船点云与岸边最近距离从4 m扩大到10 m，边缘明显分离。

图6 点云重构效果对比图

观察特征聚类分割后的图6可知，非近岸点云的滤波效果较好，整体滤波的主要误差来自于近岸船只点云的误分类。为验证本算法的有效性，从实验区域中选取一块含有近岸船只点云的典型区域进行验证。图7为所选取的典型区域，有大量船只停靠在岸边，大部分船只点云与岸边有一明显的窄缝，部分船只点云与岸堤相连。图中共有10个近岸点云块。将重构前和重构后的点云分别进行二值连通域标记与提取，共滤除602个点（图中红色点），9个近岸船只点云块；不进行重构而直接提取二值连通域的方法共滤除211个点（图中蓝色矩形区域内的红色点），3个近岸船只点云块。

图7 滤波后点云图像

通过人工对比实时光学影像资料与点云数据，可准确区分河流点云数据地面点与非地面点，并进行统计。共滤出非地面点654个，一共10个船只点云块。由于地面点大多相连，所以不会导致地面点误分类为非地面点。将人工滤除结果作为标准对实验结果进行评价。本文的重构方法显著提高了非地面点云的滤除效果。

表1 重构前后近岸船只点云滤波指标统计/%

4 结 语

通过分析河流区域非地面点云的类型，主要包括水面点云与船只点云，且船只点云分为孤立船只点云与近岸船只点云，利用水面点的均匀分布和高差变化小以及船只点云独立性明显的特点，通过特征聚类标记水面点云并利用k最邻近点点云重构分离点云块边缘，提高近岸船只点云独立性，最后使用二值连通域标记，最终实现河流区域非地面点的滤除。由于地面点大多相连，所以不会导致地面点误分类为非地面点，能够有效保留地面点信息。该算法能将90%以上的水面点云、孤立船只点云和镶嵌在水面点云中的船只点云滤除，从总体上实现河流区域非地面点云的有效滤除。

[1] 舒宁 ． 激光成像 [M]． 武汉 ：武汉大学出版社 ,2005

[2] Kraus K, Pfeifer N． Determination of Terrain Models in Wooded Areas with Airborne Laser Scanner Data[J]． ISPRS Journal of Photogrammetry & Remote Sensing, 1998, 53(4):193-203

[3] Axelsson P． DEM Generation from Laser Scanner Data Using Adaptive TIN Models[J]．International Archives of Photogrammetry & Remote Sensing,2000,33

[4] Vosselman G． Slope Based Filtering of Laser Altimetry Data[J]．International Archives of Photogrammetry & Remote Sensing,2000, 33(B3):935-942

[5] 王宗跃, 马洪超, 徐宏根,等． 基于LiDAR点云数据的水体轮廓线提取方法研究[J]．武汉大学学报(信息科学版),2010(4):432-435

[6] 张永军,吴磊,林立文,等． 基于LiDAR数据和航空影像的水体自动提取[J]．武汉大学学报(信息科学版), 2010(8):936-940

[7] 杨晓云,岑敏仪,贾洪果． 基于参数统计的LiDAR数据分割算法[J]．测绘通报, 2013(10):20-22

[8] Kanade T, Tian Y, Cohn J F． Comprehensive Database for Facial Expression Analysis[C]．IEEE International Conference on Automatic Face and Gesture Recognition, 2000

[9] 李卉, 李德仁, 黄先锋,等． 一种渐进加密三角网LIDAR点云滤波的改进算法[J]．测绘科学,2009, 34(3):39-40

[10] 王静． 二值图像连通域的分段标记算法及实现[J]．红外与激光工程, 2010, 39(4):761-765

P237

B

1672-4623（2017）10-0032-04

10.3969/j.issn.1672-4623.2017.10.010

2016-09-12。

项目来源：国家自然科学基金资助项目（41471276）；水利部黄土高原水土流失过程与控制重点实验室开放基金课题（2015001）。

易航，硕士研究生，研究方向为摄影测量与遥感。