CN109685080B - 基于霍夫变换与区域生长的多尺度平面提取方法 - Google Patents

Abstract

本发明涉及一种基于霍夫变换与区域生长的多尺度平面提取方法。本发明通过引入霍夫变换实现对平面中心区域的有效提取，并利用区域生长实现平面的完整提取；在霍夫投票阶段，通过提前计算出点的局部法向量再结合点在图像空间中的位置可唯一地确定一个平面，仅用法向量空间表示参数空间，也使得参数空间的局部最大值对应平行平面的朝向，从而更加适合岩体点云的几何特点；此外，本文发明没有单纯提取参数空间中的局部最大值，而是对局部最大值及其附近的投票分布进行聚类，再直接找到向聚类投票的图像空间中的平行平面点集。为有效处理提取不同空间尺度平面的问题，本发明通过多次设置点的邻域半径，从而能够迭代地提取具有不同空间尺度的平面。

Description

基于霍夫变换与区域生长的多尺度平面提取方法

技术领域

本发明属于计算机视觉和三维点云数据处理的交叉领域，涉及点云特征提取、岩体三维重建等技术，特别涉及基于主方向估算的3D岩体点云特征面提取方法。

背景技术

三维点云中的平面提取在许多应用领域中往往作为点云处理和分析的初始步骤。在三维城市建模领域，城市道路和建筑物外形等人造物体表面往往呈现出规则的几何形状，其中平面是最常见的几何外形，从城市场景中实现对平面点云的识别与多边形化，可有效提升建模效率并实现高效的数据压缩。在岩石工程领域，从岩体点云中提取的平面可以被用来分析岩石不连续面的产状信息，从而建立不连续面的统计模型。此外，平面提取在点云配准，提升激光扫描仪的扫描速度，室内环境桌面上物体的识别以及增强现实等领域都有广泛的应用。因此，平面提取是点云处理领域的研究热点之一，许多研究者提出了大量的平面提取方法。

在常规的平面提取方法中，常用的有霍夫变换、随机采样一致性和区域生长三种主要的研究方法。霍夫变换具有较高的鲁棒性，但该方法要么容易造成丝带现象要么不能有效地提取完整的平面。随机采样一致性方法(RANSAC)具有较高的执行效率，但是难以处理表面凹凸不平的平面识别问题，尤其是在比较粗糙的物理平面具有较大尺度的情况下，利用该方法难以完整地提取出物理平面。区域生长方法也是被广泛应用的平面提取方法，但是其初始种子点(集)(即生长单元)的选取具有较大的不确定性，而不同的种子点往往生长出质量不同的平面，而且平面提取效果还会受到合并阈值的影响。因而这些方法直接应用在岩体点云的平面提取中往往不能获得理想的效果。

在面向岩体点云的不连续面提取方法中，已有研究主要针对岩体点云的特点，通过引入极点图，聚类分析，点云平滑等发展了一些新的平面提取方法。这些方法均取得了较好的效果，但是它们主要着眼于解决岩体不连续面的分析问题，而不是岩体的三维建模。岩体点云中的平面主要由几组平行平面集合组成，这些平面往往具有不同的空间尺度，不同的粗糙程度，存在数量较多，且分布范围较广。

发明内容

本发明针对岩体表面的平坦部分往往是不连续面，平面提取也可以为后续的不连续面识别提供基础数据，提出了一种基于霍夫变换与区域生长的多尺度平面提取方法。

本发明提供了一种基于霍夫变换与区域生长的多尺度平面提取方法，主要包涵以下步骤：

步骤1、基于密度下降的霍夫变换优化：提出一种基于离散球的参数空间累加器构造策略以及一种基于密度下降的参数空间投票数据聚类策略，从而有效地解决了目前主流的基于霍夫变换的平面提取方法在提取岩体点云中的平面时主要存在两个主要缺陷：(1)无法保证对具有任意朝向的平面的有效提取；(2)容易产生“丝带”现象；

步骤2、基于平面簇的自适应区域生长：组成平面簇的点集往往无法覆盖整个岩石平面，区域生长法可有效解决这一问题，由于生长出来的一些平面同属于一个岩石平面，因此还需对这些平面执行一个合并操作；

步骤3、平面多边形化及后处理：有效解决对平面点云的数据压缩以及为下一次迭代准备输入点云的问题。

本发明所述的一种基于霍夫变换与区域生长的多尺度平面提取方法，作为优选方式，步骤1进一步包含以下步骤：

步骤1.1、表面法向量估计，构造以点p为圆心，r₁为半径的球所包含的点集计算协方差矩阵∑，具体而言，

最后将∑最小特征值λ₀对应的特征向量v₀作为p的法向量；

步骤1.2、法向量方向校正，首先选择一个点p，在确保其法向量指向物体外部的前提下，检查其近邻点q的法向量/>若/>则改变/>的符号，用q更新p，重复以上过程直到所有的点都被正确地处理；

步骤1.3、基于离散球的参数空间累加器创建，首先用小立方体(体素)分割包含参数空间(即重心在原点的单位球面)的最小立方体空间，即构建体素格网；然后去掉那些不与单位球面接触的体素，剩下的体素集合便构成了累加器，用kdtree将累加器中的单元组织起来；

步骤1.4、在投票阶段，遍历点云中每个点的法向量，利用kdtree找到与其最接近的累加器单元，将累加器单元内的投票数加一，同时存储向该单元投票的点，引入高斯核函数对累加器中的投票数据进行卷积平滑，最终构建出类似正态分布的投票密度分布效果；

步骤1.5、基于密度下降的参数空间聚类，参数空间聚类过程是基于累加器中的局部最大值迭代执行的，在每次迭代中参数空间的当前最大值首先被检测出来，然后以持有该最大值的累加器单元作为种子点(也是聚类中心)，最后利用区域生长法将种子点周围具有较小投票值的累加器单元吸引过来；

步骤1.6、随机选取一个种子点，然后将位于以该种子点为球心、r₂为半径的圆球内的其它点看作种子点的邻居点，接下来将这些邻居点看作新的种子点依次向外扩张，直到当前聚类再也找不到新的邻居点时便可完成聚类的构建。

本发明所述的一种基于霍夫变换与区域生长的多尺度平面提取方法，作为优选方式，步骤2进一步包含以下步骤：

步骤2.1、基于平面簇的区域生长，其生长单元是上一节提取出来的平面簇，生长时逐邻居点进行检测，在检测邻居点与生长单元的共面条件时应同时满足的条件：

(1)更新后平面的法向量与最初生长单元的法向量方向偏差不能过大；

(2)更新后平面的曲率与最初生长单元的曲率差别不能过大；

(3)邻居点的局部法向量(即用更小半径估计出来的法向量)与更新后平面的法向量方向偏差不能过大。

步骤2.2、合并那些由同属于一个平面的生长单元生长出来的平面集合，将每个平面看作图中的顶点，如果两个平面具有较大的公共部分则在平面对应的两个点之间添加一条边，利用关系图表示平面A与平面B是否具有合并关系，如果A与B满足合并条件，则分别在A与B的关联平面列表中加入对彼此的联系，从而可以在任意一点找到所有的关联关系；

步骤2.3、执行平面合并操作，首先对平面对应的原始图像空间中的点集执行并集操作，然后选对应点集数量最大的平面作为更新后的平面，最后去掉其余较小的平面。

本发明所述的一种基于霍夫变换与区域生长的多尺度平面提取方法，作为优选方式，步骤3进一步包含以下步骤：

步骤3.1、边界点提取，首先计算平面点云的最小二乘平面π；然后将点集投影到最小二乘平面构成投影点集/>

步骤3.2、计算的二维凹包得到多边形顶点序列v，基于α-shape方法，该方法首先对平面点集进行Delaunay剖分，从而形成一组三角面片的集合，然后删除那些顶点外接圆半径超过α的三角形，最终通过识别边界处的三角形实现多边形边界的提取；

步骤3.3、多边形顶点排列顺序校正，基于ear clipping的多边形三角化算法中，为计算多边形顶点内角需要多边形顶点绕着法向量呈逆时针排序，保证每个多边形的顶点排序均围绕多边形法向量呈逆时针方向，即符合右手法则；

步骤3.4、基于ear clipping算法实现多边形三角化。

附图说明

图1是基于霍夫变换与区域生长的多尺度平面提取方法流程图。

图2是法向量校正示意图。

图3是霍夫累加器中的投票密度示意图，其中(a)是最初投票密度，(b)是过滤后的投票密度。

图4是一维参数空间中的聚类效果示意图。

图5是平面合并示意图。

图6是平面多边形化效果图。

图7是与不同内角关联有向线段的叉积与法向量的朝向关系示意图。

图8是平面提取结果示意图。

具体实施方式

本发明主要基于计算机视觉和点云处理技术，提出一种基于霍夫变换与区域生长的多尺度平面提取方法。本发明综合利用霍夫变换和区域生长进行特征面提取，提高了特征面提取的效率和准确性，扩展了现有特征面提取方法的适用范围。

为了使本发明的目的、技术方案及优点更加清楚，以下结合附图和实施例，对本发明作进一步详细说明。本发明提供的方法能够用计算机软件技术实现流程，整体技术流程图参见图1，包括以下步骤：

步骤1、基于密度下降的霍夫变换优化：提出一种基于离散球的参数空间累加器构造策略以及一种基于密度下降的参数空间投票数据聚类策略。实施例的具体实施过程说明如下：

步骤1.1、表面法向量估计，构造以点p为圆心，r₁为半径的球所包含的点集计算协方差矩阵∑，具体而言，

最后将∑最小特征值λ₀对应的特征向量υ₀作为P的法向量；

步骤1.2、法向量方向校正，图2展示了本文提出的法向量校正策略：首先选择一个点p，在确保其法向量指向物体外部的前提下，检查其近邻点q的法向量/>若则改变/>的符号，用q更新p，重复以上过程直到所有的点都被正确地处理；

步骤1.3、基于离散球的参数空间累加器创建，首先用小立方体(体素)分割包含参数空间(即重心在原点的单位球面)的最小立方体空间，即构建体素格网；然后去掉那些不与单位球面接触的体素，剩下的体素集合便构成了累加器，用kdtree将累加器中的单元组织起来；

步骤1.4、在投票阶段，遍历点云中每个点的法向量，利用kdtree找到与其最接近的累加器单元，将累加器单元内的投票数加一，同时存储向该单元投票的点，引入高斯核函数(本实施例滤波的标准差σ根据经验设置为0.05m)，对累加器中的投票数据进行卷积平滑，最终构建出类似正态分布的投票密度分布效果，如图3所示；

步骤1.5、基于密度下降的参数空间聚类，参数空间聚类过程是基于累加器中的局部最大值迭代执行的，在每次迭代中参数空间的当前最大值首先被检测出来，然后以持有该最大值的累加器单元作为种子点(也是聚类中心)，最后利用区域生长法将种子点周围具有较小投票值的累加器单元吸引过来(如图4所示)；

步骤1.6、随机选取一个种子点，然后将位于以该种子点为球心、r_2为半径的圆球内的其它点看作种子点的邻居点，接下来将这些邻居点看作新的种子点依次向外扩张，直到当前聚类再也找不到新的邻居点时便可完成聚类的构建，提取出的平面簇还需满足以下两个条件：点的数量足够多以及表面足够平坦，这可以通过设置数量阈值T_num2以及曲率阈值T_curvature来完成，曲率阈值T_curvature的设置基于平面的粗糙程度，本文将其默认设置为0.0015。只有那些点的数量不少于T_num2同时曲率不大于T_curvature的点簇才被识别为平面簇，曲率的近似计算基于如下。

curvature＝λ₀/(λ₀+λ₁+λ₂)

步骤2、基于平面簇的自适应区域生长：组成平面簇的点集往往无法覆盖整个岩石平面，区域生长法可有效解决这一问题，由于生长出来的一些平面同属于一个岩石平面，因此还需对这些平面执行一个合并操作。实施例的具体实施过程说明如下：

步骤2.1、基于平面簇的区域生长，其生长单元是上一节提取出来的平面簇，生长时逐邻居点进行检测，在检测邻居点与生长单元的共面条件时应同时满足的条件：

(1)更新后平面的法向量与最初生长单元的法向量方向偏差不能过大；

(2)更新后平面的曲率与最初生长单元的曲率差别不能过大；

(3)邻居点的局部法向量(即用更小半径估计出来的法向量)与更新后平面的法向量方向偏差不能过大。

步骤2.2、合并那些由同属于一个平面的生长单元生长出来的平面集合，将每个平面看作图中的顶点，如果两个平面具有较大的公共部分则在平面对应的两个点之间添加一条边，对于连通的点集则表明它们的对应平面同属于一个岩石平面(如图5所示，A不做处理，分别合并BCDE和FGH)，因此最终仅合并这些相互关联的平面；

步骤2.3、利用关系图表示平面A与平面B是否具有合并关系，如果A与B满足合并条件，则分别在A与B的关联平面列表中加入对彼此的联系，从而可以在任意一点找到所有的关联关系；

步骤2.4、基于广度优先搜索实现对相互关联平面集合的有效提取，利用队列Q1进行广度优先搜索，并利用队列Q2保存每次找到的关联平面；

步骤2.5、执行平面合并操作，首先对平面对应的原始图像空间中的点集执行并集操作，然后选对应点集数量最大的平面作为更新后的平面，最后去掉其余较小的平面。

步骤3、平面多边形化及后处理：有效解决对平面点云的数据压缩以及为下一次迭代准备输入点云的问题。实施例的具体实施过程说明如下：

步骤3.1、边界点提取，首先计算平面点云的最小二乘平面π；然后将点集投影到最小二乘平面构成投影点集/>

步骤3.2、计算的二维凹包得到多边形顶点序列v，基于α-shape方法，该方法首先对平面点集进行Delaunay剖分，从而形成一组三角面片的集合，然后删除那些顶点外接圆半径超过α的三角形，最终通过识别边界处的三角形实现多边形边界的提取(本实施例基于经验将参数α的值设置为法向量估计半径r₁的一半)，图6展示了平面边界提取效果，其中与每个多边形关联的直线段表示多边形的法向量，可以发现它们都指向岩体外部；

步骤3.3、多边形顶点排列顺序校正，基于ear clipping的多边形三角化算法中，为计算多边形顶点内角需要多边形顶点绕着法向量呈逆时针排序，保证每个多边形的顶点排序均围绕多边形法向量呈逆时针方向，即符合右手法则，如图7所示，对于顶点顺序正确排列的多边形，若某个顶点p的内角小于π，那么与p关联的两条有向线段e₁与e₂的叉积与多边形法向量n同向(图7(a))，但是对于内角大于π的顶点q而言，其关联的有向线段e₃与e₄的叉积与多边形法向量n反向(图7(b))；

步骤3.4、基于ear clipping算法实现多边形三角化，图6(c)展示了平面多边形三角化线框图，图6(d)展示了加入光照之后的渲染效果，图8展示了平面提取的结果。

本文以上所述仅的具体实施例仅仅是对本发明精神做举例说明，应当指出：本领域技术人员在不脱离发明原理的前提下可以对所描述的具体实施例做出任何修改、变化或等效，但这些修改、变化和等效都将落入本发明的保护范围之内。

Claims (3)

1.一种基于霍夫变换与区域生长的多尺度平面提取方法，其特征在于包涵以下步骤：

步骤1、基于密度下降的霍夫变换优化：提出一种基于离散球的参数空间累加器构造策略以及一种基于密度下降的参数空间投票数据聚类策略，提取任意朝向的平面，避免“丝带”现象，具体如下：

步骤1.1、表面法向量估计，构造以点p为圆心，r₁为半径的球所包含的点集P，计算协方差矩阵Σ，具体而言，

将Σ最小特征值λ₀对应的特征向量v₀作为p的法向量；

步骤1.2、法向量方向校正，首先选择一个点p，在确保其法向量指向物体外部的前提下，检查其近邻点q的法向量/>若/>则改变/>的符号，用q更新p，重复以上过程直到所有的点都被正确地处理；

步骤1.3、基于离散球的参数空间累加器创建，首先用小立方体体素分割重心在原点的单位球面，即构建体素格网，然后去掉不与单位球面接触的体素，剩余体素集合便构成了累加器，用kdtree将累加器中的单元组织起来；

步骤1.4、在投票阶段，遍历点云中每个点的法向量，利用kdtree找到与其最接近的累加器单元，将累加器单元内的投票数加一，同时存储为该单元投票的点，引入高斯核函数对累加器中的投票数据进行卷积平滑，最终构建出类似正态分布的投票密度分布效果；

步骤1.5、基于密度下降的参数空间聚类，参数空间聚类过程是基于累加器中的局部最大值迭代执行，在每次迭代中参数空间的当前最大值被检测出来，然后以持有该最大值的累加器单元作为种子点，最后利用区域生长法将种子点周围具有较小投票值的累加器单元聚类；

步骤1.6、随机选取一个种子点，将位于以该种子点为球心、r₂为半径的圆球内的其它点看作种子点的邻居点，将这些邻居点看作新的种子点依次向外扩张，直至当前聚类无法找到新的邻居点；

步骤2、基于平面簇的自适应区域生长：组成平面簇的点集无法覆盖整个平面，由于生长出来的部分平面属于同一个平面，因此还需对这些平面执行合并操作；

步骤3、平面多边形化及后处理：对平面点云进行数据压缩以及为下一次迭代准备输入点云。

2.根据权利要求1所述的一种基于霍夫变换与区域生长的多尺度平面提取方法，其特征在于所述步骤2进一步包括以下步骤：

步骤2.1、基于平面簇的区域生长，其生长单元是步骤1提取出来的平面簇，生长时逐邻居点进行检测，在检测邻居点与生长单元是否共面时应同时满足以下条件：

(1)更新后平面的法向量与初始生长单元的法向量方向偏差不能过大；

(2)更新后平面的曲率与初始生长单元的曲率差别不能过大；

(3)邻居点的局部法向量与更新后平面的法向量方向偏差不能过大；

步骤2.2、合并由属于同一个平面的生长单元生长出来的平面集合，将每个平面看作关系图的顶点，如果两个平面具有较大的公共部分则在平面对应的两个点之间添加一条边，利用关系图表示平面A与平面B是否具有合并关系，如果A与B满足合并条件，则分别在A与B的关联平面列表中加入对彼此的联系，从而在任意一点找到所有的关联关系；

步骤2.3、执行平面合并操作，首先对平面对应的原始空间中的点集执行并集操作，然后选对应点集数量最大的平面作为更新后的平面，最后去掉其余较小的平面。

3.根据权利要求1所述的一种基于霍夫变换与区域生长的多尺度平面提取方法，其特征在于所述步骤3进一步包括以下步骤：

步骤3.1、边界点提取，首先计算平面点云的最小二乘平面π，然后将点集P投影到最小二乘平面构成投影点集

步骤3.2、计算的二维凹包，得到多边形顶点序列V，基于α-shape方法对平面点集进行Delaunay剖分，形成一组三角面片的集合，删除顶点外接圆半径超过α的三角形，通过识别边界处的三角形实现多边形边界的提取；

步骤3.3、多边形顶点排列顺序校正，基于ear clipping的多边形三角化算法中，为计算多边形顶点内角需要多边形顶点绕着法向量呈逆时针排序，保证每个多边形的顶点排序均围绕多边形法向量呈逆时针方向，即符合右手法则；

步骤3.4、基于ear clipping算法实现多边形三角化。