李昕

摘要：提出一种以梯田田坎面特征为提取依据的改进法矢向量点云提取算法。该算法以梯田的点云的法矢向量为主要特征，根据需要梯田点云的特征，提出了一种基于距离权重的法矢向量计算方法，将梯田数据的坎面快速准确的提取出来。

关键词：点云；法向量；田坎面

中图分类号：TP391.41 文献标识码：A 文章编号：1007-9416（2017）04-0099-02

在如今数字化世界的时代中，随着计算机技术和传感技术等领域的快速发展，极大促进了测量测绘以及逆向工程等的发展[1]。在野外测量中，对复杂地形的信息采集以及数据建模等需求也越来越高，随着机载雷达、车载雷达、无人机等工具的进步，采集的地形信息也越来越全面，如何合理高效的利用这些数据来提取所需要的信息，对后续的三维建模，土地面积计算发挥着至关重要的作用[2][3]。

在对散乱三维点云的信息研究的过程中，三维点云的法向量作为三维点云空间的重要几何特征，是点云信息提取尤其是三维边界以及特征面提取的一个重要指标，同时也有许多与之相关的研究方法[4][5]。因此本文提出一种基于距离权重的法矢向量计算方法，针对所要求的提取梯田坎面的目标，对点云数据进行K邻域搜索，通过基于Delaunay的方法对数据点建立三角网，并基于邻域点与目标点的距离来重新对法矢向量值进行估算，提高梯田田坎面提取的精度。

1 研究方法

由于散乱三维点云在空间分布上呈无序状态，为提高计算效率，保证目标特征点的提取，可对点云建立kd树索引。K近邻算法一般是通过计算与目标点的距离，对采样点搜索出最临近的K个点。通过K近邻算法对目标点及其进行拟合进而计算出法矢向量，通过设置特征值来提取符合要求的数据点。

1.1 K邻近点的搜索

Kd树是一种分割K维数据空间的数据结构，是二进制空间分割树的特殊情况。 在三维无序点云数据处理中，三维kd树索引的建立能够极大的提升临近点的搜索效率[6]。

其基本构建思路：首先对三维点云数据进行遍历，对X、Y、Z坐标进行方差计算，并以大小进行排序来对分割轴进行编号；依据编号选定坐标域，以位于正中间的数据点为节点，对位于分割轴两侧的点进行分割，确定左右空间；按照编号大小，对剩下的坐标域以位于正中间的数据点为节点分割；递归上述过程，直至空間中只包含一个数据点为止。

在通过无序的点云数据建立Kd索引之后，通过目标点P（PX、PY、PZ）坐标与节点的坐标值进行比较，选取最近的根节点作为目标节点进行遍历，搜索出的最近的K个点，即为目标的K邻域点集Pk={P1、P2、P3……Pk}。

1.2 改进的法矢向量提取方法

1.2.1 法矢向量提取方法

法矢向量是离散空间点云的一个重要空间几何特征，因此在三维点云空间特征提取中，估算点的法矢向量是一个关键的过程[6]。常见的点云法矢向量计算方法有：通过对点云进行局部表面拟合和基于Delaunay的方法[7]。

本文利用基于Delaunay的方法来估算目标点P的法矢向量，通常采用的办法为：首先对P及其K邻域点集Pk构建Delaunay三角网；计算所有通过P点的三角面的法向量，并进行法向量一致化处理，得到过P点的三角网的法向量集；通过三角面的法向量集Nk={N1、N2、N3}加权平均的方式对P点的法向量进行估算。P点的法向量Np的估算表达式为：。

1.2.2 改进算法

在基于Delaunay的方法过程中，法矢向量是由邻近三角网的法矢向量加权平均进行估算的，点云法向量的估算的准确性和三角网的法矢向量有极高的关联性。

在提取梯田田坎特征面的过程中，需将田坎点云数据中的田坎面点保留，同时尽可能的除去边坡面点。为了更好的提取梯田田坎边点以及保留梯田田坎面的特征，本文对点云估算方法进行改进：在目标点进行法向量估算构建三角网的过程中，对通过目标点三角网的法向量进行加权，依据构建三角网的点与目标点的距离进行权重赋值，降低远点对目标点法矢向量计算的影响，得到新的点云法向量估算公式如下：

式中：L为点集Pk中与目标点P欧式距离的最大值，La、Lb分别问过P点三角网的其余两顶点与点P的欧式距离。

1.2.3 梯田田坎特征面提取

根据得到的梯田点云法矢向量，对梯田数据点的法向量与其K邻近点的法向量的夹角αi计算得到夹角集A，A={α1、α2、α3……αk}，并进行加权运算得到该点与K邻域点的法向量夹角的均值αp；同时计算出点法向量与Z坐标轴的夹角βp。通过设置阈值k1和k2，可根据αp与k1以及βp与k2的对比结果进行分类，并进行分类，当αp>k1将其视为田坎边界点，当αpk2时，将其视为边坡点，其余点则为田坎表面点。

2 实验分析

硬件为CPU为Intel双核20G，操作系统为Windows 10，软件为VC++6.0和GeomagicStudio2013，机载激光扫描数据为Riegle公司的 VZ-4000获取的贵州某梯田三维点云数据。

2.1 数据预处理

首先将数据导入到GeomagicStudio2013里，通过软件现有算法对数据进行降噪处理，得到实验用数据（图1）。

2.2 实验过程

（1）读取处理后的梯田点云数据并表达（图2），建立kd树索引组织点云数据。

（2）对数据点P求出点的K邻域点集，并依据改进算法进行法向量计算得到结果N。

（3）对目标点P及其K邻域点的法矢向量依据公式得到其与邻域点法向量夹角均值αp和其与Z坐标轴的夹角βp和设置的阈值进行比较，这里k1取45°，k2取5°。

（4）对所有数据点依次遍历进行上述过程得到实验结果并表达（图3）。

（5）通过GeomagicStudio进行点云矢量数据操作，根据设置的阈值提取目标点，得到结果（图4），并通过人工识别的方法对两数据结果进行比对，检验其保留的边坡点。

得到的比对结果如表1。

3 结语

本文通过K邻域算法，求取点云数据点及其邻域并生成三角网得到相关面的法向量，通过赋予权值的方式对点云的法向量估算方法进行改进，设置合理的阈值同目标点及其邻域的法矢向量夹角均值比较来提取符合要求的点，从实验结果以及相关软件的处理结果来看，该算法能够相对快速的提取梯田田坎的表面点数据，且达到较小的误差。

参考文献

[1]Masatoshi Hikizu. Motion Planning System for Bin Picking Using 3-D Point Cloud[J]. Intelligent Control and Automation，2016，07（03）：73-83.

[2]王丽辉.三维点云数据处理的技术研究[D].北京：北京交通大学，2011.

[3]安毅.三维点云数据的几何特性估算与特征识别[D].大连：大连理工大学，2011.

[4]赵卫东，汤国安，徐媛，周春寅，钱家忠，马雷.梯田地形形态特征及其综合数字分类研究[J].水土保持通报，2013，01（056）：295-300.

[5]刘正.三维点云法向量估计方法研究[D].华北电力大学，2015.

[6]雷玉珍.三维点云数据处理中的若干关键技术研究[D].华中科技大学，2013.

[7]李宝，程志全，党岗，金士尧.三维点云法向量估计综述[J].计算机工程与应用，2010，（23）：1-7.