一种机载激光雷达点云数据边缘提取方法

摘要

本发明公开了一种机载激光雷达点云数据边缘提取方法，它包括以下步骤：步骤一，初始化原始机载激光雷达点云数据，将每一个激光脚点均设置为待判别点；步骤二，提取机载激光雷达点云数据中的边缘点；步骤三，对边缘点进行追踪以形成边缘。本发明不需要借助激光雷达点云数据对应的光学图像，不需要将激光雷达点云数据转化成深度图像，直接从三维点云中提取边缘，有效区分各交叉边缘，有效简化了边缘提取算法复杂度，提高了边缘检测的自动化程度，并且能够有效提取激光雷达点云中所有类型边缘。

说明书

技术领域

本发明涉及一种特征提取方法，具体地说是一种机载激光雷达点云数据边缘提取方法，属于激光雷达点云数据信息提取技术领域。

背景技术

特征提取作为图像分析和计算机视觉的重要研究领域，已经得到了很多学者的关注和研究。边缘作为这些特征的重要组成部分，不仅广泛存在于二维图像中，还存在于各种场景(尤其是含有大量人工建筑物的城市场景)和单个地物的三维点云数据中。相比于点云，图像是一种更常见的数据类型；另外，过去，由于受到激光雷达传感器硬件的限制，过去的三维点云数据中地物的细节结构，尤其是边缘，通常有所缺失或模糊不清。因此，目前大部分边缘检测方法是基于图像的，而且相关的方法已经相对成熟。但是，目前，随着激光雷达传感器硬件的进步，获取可展示地物细节结构信息的高密度点云数据的技术已经成熟，且推出了多种商业化的激光雷达硬件设备。

但是二维图像边缘检测算法并不能直接应用于三维点云数据，主要有以下原因：

(1)激光雷达点云数据通常只具备XYZ坐标信息，有时候会有RGB信息或者回波信息。

(2)激光雷达点云数据所包含的空间几何信息多于二维图像，相应地，其对应的几何结构也更加复杂。

(3)激光雷达获取的点云数据是无组织的三维点云数据，其邻域结构非常复杂且因检索方式不同而存在很大差别；然而，图像成规则栅格排列，邻域的确定非常容易。

目前，已有的激光雷达点云边缘检测方法可以分为两类。第一类方法将激光雷达点云转化为图像，再借助于图像处理领域的边缘检测方法获取二维边缘，进一步将二维边缘与三维点云数据中的边缘相对应，从而提取三维边缘特征，称为“间接法”。第二类方法则直接作用于激光雷达点云数据来提取三维边缘特征，称为“直接法”。其中“直接法”最有代表性的方法为点云库边缘检测方法和自相关矩阵分析边缘追踪方法。

但是，上述边缘检测方法存在以下不足：

(1)“间接法”涉及三维到二维的转换，导致了大量空间几何信息的损失。

(2)“直接法”的适用性有限，仅仅适合于特定类型的边缘提取。

(3)这些方法仅仅适用于局部小范围的无噪声的点云数据，对于大区域、且含有噪声的点云数据不能发挥效力。

(4)这些方法的过程复杂、自动化程度较低，需要借助点云分割、目标提取等预处理，然后针对特定目标提取边缘。

由于以上不足的制约，目前，激光雷达点云数据中的边缘尚不能完整提取出来，且自动化程度低。

发明内容

针对以上现有技术的不足，本发明提出了一种机载激光雷达点云数据边缘提取方法，其能够直接从三维点云中提取边缘，有效简化边缘提取算法复杂度，提高边缘检测的自动化程度。

本发明解决其技术问题采取的技术方案是：一种机载激光雷达点云数据边缘提取方法，其特征是，包括以下步骤：

步骤一，初始化原始机载激光雷达点云数据，将每一个激光脚点均设置为待判别点；

步骤二，提取机载激光雷达点云数据中的边缘点；

步骤三，对边缘点进行追踪以形成边缘。

优选地，在步骤二中，将机载激光雷达点云数据中的边缘分成表面轮廓和表面相交边缘，并分析表面轮廓和表面相交边缘的特点，最终形成一套可以同时提取表面轮廓和表面相交边缘的完整流程。

优选地，在步骤三中，根据机载激光雷达点云的空间邻域特点对边缘点进行追踪来区分相交边缘和方向相同的相邻边缘。

优选地，所述步骤二具体包括以下步骤：

(1)按顺序从点云数据中取出一个激光脚点，并以该点作为当前点；

(2)搜索当前点的邻域点集：利用kd_tree索引进行空间邻域搜索，kd_tree索引结构以当前点为中心，按距离搜索当前点周边的临近点；

(3)根据邻域点集拟合局部平面：在拟合局部平面时采用随机采样一致性方法来拟合局部平面，将邻域点集分成位于局部平面上的内点和位于局部平面以外的外点；

(4)构建空间直角坐标系，连接当前点与位于局部拟合平面上的邻域点，从而构成多条空间向量；

(5)在生成的空间直角坐标系中计算空间向量所形成的角度阶跃：假设坐标系的三个轴的单位方向向量分别为：为多条空间向量，则角度阶跃值G_θ由以下公式计算：

$>{\theta }_i=\arctan (d_i^u/d_i^v)---\left(3\right)$>

G_θ＝max(θ_i+1-θ_i)(i＝1…N_r-1)(4)

式中，θ为空间向量在空间直角坐标系中的角度，Nr为正整数；

(6)检测角度阶跃是否大于阈值，从而判定当前点是否为边缘点：如果则当前点被判别为边缘点，否则不被判别为边缘点；

(7)迭代执行上述步骤(1)至(6)，直到所有点都被判定为止。

优选地，所述构成多条空间向量的过程为：首选利用根据邻域点集拟合局部平面过程中所找到的内点，计算该局部平面的法线向量；然后根据该法线向量和局部拟合平面构建空间三维直角坐标系，该坐标系与法线向量垂直的两个轴均位于局部拟合平面上；最后连接当前内点与位于局部拟合平面上的邻域点，从而构成多条空间向量。

优选地，所述步骤三具体包括以下步骤：

(1)按顺序从提取出边缘点集中取出一个点，并以该点作为当前点；

(2)搜索当前点的邻域点集：利用kd_tree索引进行空间邻域搜索，kd_tree索引结构以当前点为中心，按距离搜索当前点周边的临近点；

(3)拟合空间直线：根据当前点的邻域点集，利用随机采样一致性原理拟合空间直线，并将邻域点集划分成位于拟合空间直线上的内点和位于拟合空间直线以外的外点；

(4)定义生长准则：定义相邻准则和方向相似准则，所述相邻准则为：只有与当前点相邻的点才可以作为压入当前边缘队列的候选点，所述与当前点相邻的点为位于拟合空间直线上的内点点集中且与当前点相邻的点；所述方向相似准则为：如果与当前点相邻的某一点的邻域点集拟合直线的主方向与当前点邻域拟合直线的主方向相近，则该点可以作为压入当前边缘队列的候选点；

(5)采用区域生长方法追踪边缘：采用相邻准则和方向相似准则对当前点进行生长分割，直到所有邻域点不能同时满足相邻准则和方向相似准则为止，被生长到的激光脚点，视为这条边缘上的点；

(6)迭代执行上述步骤(1)至(5)，直到所有边缘点都被追踪为止。

优选地，所述kd_tree索引采用按邻域点个数进行按距离搜索或以当前点为中心的求半径范围进行搜索的检索方式。

本发明的有益效果如下：

(1)本发明提出了一种从大范围无组织噪声点云中提取边缘的方法，直接作用于三维点云数据，提取效果稳健并且效率高。本发明不限定边缘类型，且能很好的适应不同密度和多种传感器获取的三维点云数据，所有边缘都可以得到检测。此外，本发明在提取边缘过程中仅采用两个参数，参数少，使用方便，并且参数设置相对稳定。

(2)本发明提出了一种三维边缘追踪算法来确定离散边缘点的归属信息，可以在边缘点中快速追踪边缘，并且能有效区分相交边缘和方向相同的相邻边缘。本发明算法稳健性较高，提取的边缘点位置精确，漏检现象较少，可以适用于多个边缘相互交叉的复杂边缘点追踪。

(3)本发明不需要借助激光雷达点云数据对应的光学图像，不需要将激光雷达点云数据转化成深度图像，直接从三维点云中提取边缘，有效区分各交叉边缘，有效简化了边缘提取算法复杂度，提高了边缘检测的自动化程度，并且能够有效提取激光雷达点云中所有类型边缘。

附图说明

图1为本发明的方法流程图；

图2(a)为实验数据一的示意图；

图2(b)为实验数据二的示意图；

图3(a)为实验数据一边缘点检测结果的示意图；

图3(b)为实验数据一边缘追踪结果的示意图；

图3(c)为实验数据一边缘点检测结果细节图；

图3(d)为实验数据一边缘追踪结果细节图；

图4(a)为实验数据二边缘点检测结果的示意图；

图4(b)为实验数据二边缘追踪结果的示意图；

图4(c)为实验数据二边缘点检测结果细节图；

图4(d)为实验数据二边缘追踪结果细节图；

图5(a)为步骤二方法与点云库方法对比的实验数据的示意图；

图5(b)为图5(a)中数据的边缘点提取结果的示意图(步骤二方法)；

图5(c)为图5(a)中数据的边缘点提取结果的示意图(点云库方法)；

图6(a)为步骤三方法追踪到的边缘的示意图；

图6(b)为自相关矩阵方法追踪到的边缘的示意图。

具体实施方式

为能清楚说明本方案的技术特点，下面通过具体实施方式，并结合其附图，对本发明进行详细阐述。下文的公开提供了许多不同的实施例或例子用来实现本发明的不同结构。为了简化本发明的公开，下文中对特定例子的部件和设置进行描述。此外，本发明可以在不同例子中重复参考数字和/或字母。这种重复是为了简化和清楚的目的，其本身不指示所讨论各种实施例和/或设置之间的关系。应当注意，在附图中所图示的部件不一定按比例绘制。本发明省略了对公知组件和处理技术及工艺的描述以避免不必要地限制本发明。

针对激光雷达点云数据特征提取的研究以及应用的需要，本发明提供了一种基于三维点云数据空间邻域几何结构分析的激光雷达点云数据边缘提取方法。尤其是该发明可以提取激光雷达点云中所有类型边缘，有效弥补了现有方法只能提取一种特定目标边缘的不足。该发明直接作用于激光雷达点云，从三维直接提取点云的边缘，有效弥补了现有方法从三维转换到二维会造成信息缺失的不足。该发明参数少，稳健性强，有效弥补了现有方法自动化程度低的不足。该发明可以处理大范围、无组织、含有噪声、未经过预处理的初始点云数据，有效弥补了现有方法需要借助点云预处理步骤的不足。

如图1所示，本发明是一种机载激光雷达点云数据边缘提取方法，它包括以下步骤：

步骤一，初始化原始机载激光雷达点云数据，将每一个激光脚点均设置为待判别点。首选需要加载激光雷达点云数据，如图2(a)和图2(b)所示，两景数据是未经过任何预处理的激光雷达点云数据，两景数据是两栋建筑物的墙面，所包含的人工地物结构非常复杂，如老虎窗、阳台、拱形窗户等，两景数据的点云密度较大，平均点间隔为0.01米；然后对加载的原始机载激光雷达点云数据进行初始化处理，将每一个激光脚点均设置为待判别点。

步骤二，提取机载激光雷达点云数据中的边缘点。将机载激光雷达点云数据中的边缘划分为两类：一类是表面轮廓，一类是表面相交边缘。经过对其邻域空间几何结构的分析，最终形成一套可以同时提取两类边缘点的完整流程。

步骤三，对边缘点进行追踪以形成边缘。采用二维图像区域生长分割方法的思想，根据机载激光雷达点云的空间邻域特点对边缘点进行追踪来区分相交边缘和方向相同的相邻边缘，首先优化每一个边缘点的邻域，然后定义适合激光雷达点云数据的生长准则，最后逐点进行生长，以追踪边缘。

进一步地，所述步骤二具体包括以下步骤：

(1)按顺序从点云数据中取出一个激光脚点，并以该点作为当前点。

(2)搜索当前点的邻域点集

利用kd_tree索引进行空间邻域搜索，该kd_tree索引结构以当前点为中心，按距离搜索当前点周边的临近点。该kd_tree索引有两种检索方式，即按邻域点个数进行按距离搜索和以当前点为中心的球半径范围进行搜索。对于本发明而言，两种检索方式均适用于提取边缘点。

(3)根据邻域点集拟合局部平面

由于邻域点集内部可能含有噪声点，或者存在几个表面相交结构，本发明在拟合局部平面时采用随机采样一致性方法来拟合局部平面。进而，将邻域点集分成内点(位于局部平面上的点)和外点(位于局部平面以外的点)。

(4)构建空间直角坐标系，连接当前点与位于局部拟合平面上的邻域点，从而构成多条空间向量

首选利用根据邻域点集拟合局部平面过程中所找到的内点，计算该局部平面的法线向量；然后根据该法线向量和局部拟合平面构建空间三维直角坐标系，该坐标系与法线向量垂直的两个轴均位于局部拟合平面上；最后连接当前内点与位于局部拟合平面上的邻域点，从而构成多条空间向量。

(5)在生成的空间直角坐标系中计算空间向量所形成的角度阶跃

假设坐标系的三个轴的单位方向向量分别为：是在步骤(4)中构成的多条空间向量。则角度阶跃值G_θ由以下公式计算：

$>{\theta }_i=\arctan (d_i^u/d_i^v)---\left(3\right)$>

G_θ＝max(θ_i+1-θ_i)(i＝1…N_r-1)(4)

式中，θ为空间向量在空间直角坐标系中的角度，Nr为正整数；

(6)检测角度阶跃是否大于阈值，从而判定当前点是否为边缘点

如果则当前点被判别为边缘点，否则不被判别为边缘点。

(7)迭代执行上述步骤(1)至(6)，直到所有点都被判定为止。

进一步地，所述步骤三具体包括以下步骤：

(1)按顺序从提取出的边缘点集中取出一个点，并以该点作为当前点。

(2)搜索当前点的邻域点集

利用kd_tree索引进行空间邻域搜索，该kd_tree索引结构以当前点为中心，按距离搜索当前点周边的临近点。该索引有两种检索方式，即按邻域点个数进行按距离搜索和以当前点为中心的求半径范围进行搜索。对于本发明而言，两种检索方式均适用于提取边缘点。

(3)拟合空间直线

根据当前点的邻域点集，利用随机采样一致性原理拟合空间直线，并将邻域点集划分成内点(位于拟合空间直线上的点)和外点(位于空间直线以外的点)。

(4)定义生长准则

定义相邻准则和方向相似准则：

相邻准则：只有与当前点相邻的点才可以作为压入当前边缘队列的候选点。这里的相邻指位于步骤(3)中内点点集中的点与当前点相邻。

B方向相似准则：若某一与当前点相邻的点，其邻域点集拟合直线的主方向与当前点邻域拟合直线的主方向相近，则该点可以作为压入当前边缘队列的候选点。

(5)采用区域生长方法追踪边缘

该追踪过程采用图像处理的区域生长分割方法的思想。采用相邻准则和方向相似准则两项准则，对当前点进行生长，直到所有邻域点不能同时满足这两项准则为止，被生长到的激光脚点，视为这条边缘上的点。

(6)迭代执行上述步骤(1)至(5)，直到所有边缘点都被追踪为止。

为了充分分析和表述本发明所提出算法的性能，本发明对两景来自3DTookit网址(http://slam6d.sourceforge.net)的公开数据(如图2(a和b)所示)进行了试验。本发明所采用的数据均由地面RieglVZ400扫描仪获取，再经过拼接处理得到。分别是德国不来梅港市中心区域和不来梅各布大学校园，这些区域人工建筑物非常复杂，但是，点云数据密度较大(平均点云间隔0.005m)，可以充分表征复杂人工地面目标各种细节特征。

本发明的步骤二和步骤三共有五个参数。其中，步骤二含有两个参数，即邻域点个数K和随机采样一致性算法的距离阈值d_r；步骤三含有三个参数，即邻域点个数K、随机采样一致性算法的距离阈值d_r和平滑阈值sm_thr。两景数据的参数设置如表1所示。

表1：

为了衡量本发明方法的可靠性，本发明提出了一种衡量边缘提取精度的四种指标，分别为边缘点提取(步骤二)的正确率p_dc、误判率p_mj，以及边缘追踪(步骤三)的正确率p_dct、误判率p_mjt。这四项指标由以下四个公式计算得到

其中，N_dc是步骤二结果中正确提取到的边缘个数，N_gc是边缘真值个数，N_mj是步骤二结果中误判的边缘个数，N_tc是步骤三结果中正确追踪到的边缘个数，N_mjt是步骤三结果中错误追踪的边缘个数。

两组数据的处理结果的定性分析如图3(a-d)和图4(a-d)所示，两组数据处理结果的定量分析如表2所示。

表2：

为了对比本发明方法的优势，本说明将本方法与现有方法进行了对比。其中步骤二方法与点云库中的边缘提取方法进行了对比，定量对比结果如表3所示，定性对比结果如图5(a-c)所示。其中选择实验数据2中的四个子区域进行分析。从图5中可以发现，本发明方法的提取结果明显优于现有的点云库方法。

步骤三方法与自相关矩阵分析方法进行了对比，定量对比结果如表4所示，定性对比结果如图6(a和b)所示。其中选择实验数据2中的四个子区域进行分析。从表4和图6中可以发现，本发明方法的追踪精度明显高于现有的自相关矩阵分析方法，尤其是可以区分多个相交边缘或方向相近的相邻边缘。

表3：

表4：

可见，从表3和表4可以发现，本发明的方法有效提高了边缘提取的精度，降低了边缘提取的错误率。从图3(a-d)和图4(a-d)可以发现，本发明方法可以有效提取各类边缘点，追踪各类边缘(尤其是可以区分多条相交边缘以及方向相近的相邻边缘)。

总体而言，本发明方法不需要借助于点云分割和目标识别等预处理步骤，也不需要借助图像处理方法，直接从点云中检测和追踪边缘，减小了算法复杂度，提高了参数稳定性，具备很高的工程应用价值。

总结来看，该方法具备以下优势：

(1)不限定边缘类型，所有边缘都可以得到检测。

(2)参数少，对于不同类型的输入三维点云具有相对稳定的参数设置。

(3)算法稳健性较高，提取的边缘点位置精确，漏检现象较少。

(4)可以有效区分各交叉边缘，适用于多个边缘相互交叉的复杂边缘点追踪。

(5)可以有效区分多条主方向相同的临近边缘。

以上所述只是本发明的优选实施方式，对于本技术领域的普通技术人员来说，在不脱离本发明原理的前提下，还可以做出若干改进和润饰，这些改进和润饰也被视为本发明的保护范围。