三维点云数据的精确快速面图元检测方法

目前在零件模型上容易将低曲率圆柱面的局部区域识别为平面，并且只能做到一种图元的快速准确检测。基于此，提出一种能够同时对平面和圆柱面进行精确快速检测的面向点云数据的面图元快速检测方法。该方法分为粗识别和精化两阶段：首先，将点云划分为小粒度基片，计算基片特征，粗识别出平面基片或圆柱面基片；之后，根据过滤条件将圆柱面基片邻近的平面基片过滤，合并具有相同特征的基片得到完整平面和圆柱面。使用5个机械零件数据进行实验验证，并将其与目前流行的两种识别方法进行比较。结果表明，该方法不会出现其他两种方法存在的遗漏和错误识别现象，同时在多圆柱面相连时的准确分割以及曲面参数精度上，优于其他两种方法。

Abstract

Current detection methods for three dimensional (3D) point cloud data easily identify the local area of low-curvature cylindrical surfaces as planes in a model, but these methods can achieve the fast and accurate identification of only a single element. We propose a fast primitive detection method for point cloud data that can quickly and accurately detect both planar and cylindrical surfaces simultaneously. The proposed method is divided into two stages: coarse recognition and refinement. First, the point cloud is divided into small-grained patches, the patch characteristics are calculated, and the planar and cylindrical patches are roughly identified. Next, according to the filter conditions, the planar patches adjacent to the cylindrical patches are filtered, and then the patches with identical characteristics are combined to obtain the complete planar and cylindrical surfaces. Our experiments show that the proposed method is superior to two popular recognition methods when used to analyze data concerning five mechanical components. Moreover, the proposed method does not exhibit the omission and misidentification errors demonstrated by the other two methods, and the proposed method is more accurate in terms of the surface parameter estimation and segmentation when multiple cylindrical surfaces are connected.

1　引言

在智能工业生产中，零件外观几何形状的基本图元识别是自动测量、焊接、零件分拣以及质检等环节的基础。其中，平面和圆柱面是两种最基本且最常见的几何图元^［1］，识别精度和识别效率将直接影响到工艺流程中后续各操作的精确度。基于三维网络模型进行基本图元识别时通常需要将扫描得到的离散点云数据重构为三角网格模型，再从网格模型中识别^［2］，但网格拓扑化需要较大的计算成本。与之相比，从离散点云中直接提取平面和圆柱面会降低计算成本、提高识别效率。然而，由于离散点云中只包含点的位置信息而缺少点对之间的结构信息，因此从离散点云中直接检测平面或者圆柱面图元具有一定的挑战性。

已有一些工作进行了相关研究，如Araújo等^［3］通过细分策略和统计思想进行平面识别，并通过点云投影和连通性检测方式识别圆柱面^［4］，不足之处是不能同时进行平面和圆柱面的识别，且容易将低曲率圆柱面的局部区域误识别为平面。与之相比，高效的随机采样一致性方法（eRANSAC）^［5］能够同时识别平面和圆柱面，但由于该方法是通过反复随机采样进行平面或圆柱面识别的，因此容易将平面误识别为曲率较大的圆柱面。特别是对于机械零件这种特征复杂的点云模型，直接使用已有几何图元识别方法进行识别时容易混淆。比如，当需要同时识别圆柱面和平面时，圆柱面的某些部分会被错误识别为平面，而小平面或者比较窄的长平面会被错误识别为圆柱面。

本文受Araújo平面检测算法的启发，提出一种从点云进行三维图元识别的方法：首先，对整个空间点云进行体素划分，计算每一个最小基片的特征并进行基片类型初判定；然后，对圆柱面基片所邻接的点云基片类型进行迭代求精，修正被误识别为平面的基片类型，进而准确标识出点云中的平面和圆柱面，从而有效解决低曲率圆柱面被误识别为平面的问题。在5个零件数据上进行了实验验证，没有出现漏识别的情况，整体的识别精度比基于连通性的圆柱面检测方法（CbCD）^［4］高20%。

2　相关工作

关于从离散点云模型中识别几何图元的研究大致可分为以下几类：区域增长法、RANSAC法、霍夫变换（HT）法和深度学习方法。

2.1　区域增长法

区域增长法从点云中随机选择一个种子点，从种子点开始进行图搜索，按照区域增长的约束条件迭代地将点云中符合条件的点加入，直到获得最终的聚类结果。但对于稠密点云，逐点搜索与聚类非常耗时。为了降低计算成本，Deschaud等^［6］将点云空间划分为体素，以体素为单位进行图搜索。Farid等^［7］提出一种基于平滑约束的区域增长方法进行平面检测。Maalek等^［8］将鲁棒主成分分析法（R-PCA）应用于每个点周围的邻域区域，通过分析特征值之间的比例以确定该区域是线型、平面或者其他类型。Pham等^［9］和Vo等^［10］采用分区策略提取小平面，所不同的是，前者使用基于图聚类的边缘分割，而后者则使用八叉树将点云空间分割成多个小块进行特征识别。Araújo等^［3］则在文献［10］方法的基础上加入稳健统计的思想，改进方法能够进行平面提取，局限性是容易将低曲率圆柱面的局部区域误识别为平面。

对于圆柱面检测，Tran等^［11］使用主曲率信息选择潜在的圆柱面种子点，通过迭代拟合扩展到完整的圆柱面。然而主曲率的精确估计很难，圆柱面上有多个种子点需要迭代拟合，该算法计算成本高。Nurunnabi等^［12］提出一种基于R-PCA和鲁棒回归的方法，但只适用于包含单个圆柱面的场景。Araújo等^［4］提出一种快速的圆柱检测方法，该方法在单位半球上设置一组均匀分布的方向，每个方向定义一个切平面，将点云投影到切平面上，通过线性时间的圆拟合算法检测切平面上的圆形投影，以快速识别圆柱面。

2.2　RANSAC法

RANSAC是目前最流行的多种图元提取方法。该方法包括两步：首先，从输入点集中随机提取估计平面或圆柱面所需的最小点集并进行拟合；然后，依据点到拟合面之间的距离将剩余点归类为内点和外点。迭代进行上述两步后选择内点个数最大的采样面作为平面或圆柱面的识别结果。

Schnabel等^［5］提出一种高效的RANSAC方法，该方法使用空间信息描述点的邻域，并使用法线信息改进内点函数，能够识别5种基本图元。Li等^［13］引入基于RANSAC的正态分布变换单元，以避免从点云中提取杂散平面。上述两种方法都容易识别到虚假图元。因此，王洋等^［14］提出最小平方中值（LMedS）算法替代RANSAC来检测点云平面，并结合PCA算法进行参数估计。

2.3　霍夫变换法

霍夫变换^［15］是一种探测参数化目标的方法，将点云从原始空间转换到参数空间，并在参数空间中投票来提取特征。由于霍夫变换的计算成本会随着特征空间的维数增加而指数级增长，当对圆柱面进行霍夫变换时特征空间达到五维，直接应用霍夫变换的计算成本非常高。因此，研究者们关注计算的加速问题。

随机霍夫变换（RHT）^［16］是一种加速方法，通过随机选择的3个非共线点定义平面，3点1组进行投票，大大降低了投票成本，实现了加速。但是该方法不能保证所有平面都被检测到，并且多次执行的结果往往不一致。

Leng等^［17］将区域增长和霍夫变换结合起来，利用霍夫变换提取生长单元，通过区域增长提取平面，但该方法对于平面较少的点云容易漏检。

Rabbani等^［18］提出两步霍夫变换方法以降低检测圆柱面所需的特征空间维数。首先，将霍夫变换应用于点法向量的高斯图像，以估计圆柱轴的方向；然后，将与之相关的点投影到与圆柱轴垂直的平面上，再应用霍夫变换检测圆，并估计圆柱半径和中心。但该方法会将第一步的错误传播到第二步，同时由于两步霍夫变换不同，因此需要调整参数才能获得良好的结果。

Ahmed等^［19］通过在坐标轴方向上进行预间隔切片来分割点云，每个间隔内的点投影在相应切片上，通过霍夫变换检测圆，将同一切片且具有相似中心的圆进行合并得到圆柱面，该方法只能提取与坐标轴对齐的圆柱面。

已有方法主要用于外观形状相对简单的三维模型，而对于外观特征复杂的零件点云模型，直接使用已有方法则很容易导致图元识别混淆。

2.4　深度学习方法

在三维点云语义分割上，PointNet^［20］的提出是开创性工作，其直接应用深度学习网络来处理三维点云，但在特征提取过程中并未考虑局部邻域信息。为此，杨晓文等^［21］在PointNet的基础上提出一种结合改进K近邻（KNN）算法的局部特征提取方法。刘友群等^［22］则设计了一种新的图卷积网络架构DGPoint，通过建立查询点的动态图结构，使用边缘卷积以获得强大的局部特征。

对于更进一步的图元分割，Li等^［23］引入有监督的图元拟合网络（SPFN），该网络可以自动预测不同尺度的图元。但是，此方法假定几个图元的种类是已知的，并且对在真实环境中扫描获得的不完整数据敏感。除此之外，Sharma等^［24］提出一种新颖的、端到端的、可训练的深度网络（ParSeNet），将3D点云分解为参数化曲面。然而，该方法的分解模块仍然依赖于给定的图元种类。此外，Huang等^［25］提出一个对抗网络（PrimitiveNet），将全局分割问题分解为局部任务并进行几何图元参数拟合。但是，上述方法仍然需要使用RANSAC来进行图元识别或使用区域增长来确定边界，与此同时，设计的深度神经网络大大增加了图元识别的复杂性。

3　问题描述

本研究需要根据输入的离散点云识别出平面和圆柱面两种类型的三维基本图元。首先，将整个点云空间划分多个体素块，对各体素块内的点云基片进行特征计算，并将同类型相邻的点云基片拼接为完整的图元，进而标识出点云中的完整的平面和圆柱面。该问题可描述为

f (S) = {P_{i}, i \in N_{+}} ⋃ {C_{j}, j \in N_{+}}

，（1）

式中： $S$ 为离散点云数据； $P_{i}$ 为识别到的平面； $C_{j}$ 为识别到的圆柱面。

平面由平面上的点和平面法线定义，平面上任意一点 $p_{i}$ 满足：

(p_{i} - p_{0}) \cdot N = 0

（2）

式中： $p_{0}$ 是平面上确定的一点；N是平面法向量，且满足：

{‖N‖}_{2}^{2} = 1

。（3）

那么，n（n≥3）个点拟合平面的问题即等价于式（4）所示的最小二乘优化问题：

J : m i n \sum_{i = 1}^{n} {[(p_{i} - p_{0}) \cdot N]}^{2}

。（4）

圆柱面可用中轴方向向量 $a$ 、中轴上一点 $p_{0}$ 以及圆柱半径 $R_{0}$ 表示。任意点 $p_{i}$ 到中轴的垂直距离记为 $R_{i}$ ， $R_{0}$ 和 $R_{i}$ 两者误差可以用式（5）求得：

v_{i} = |R_{i} - R_{0}|

，（5）

R_{i} = \sqrt[]{| | p_{i} - p_{0} | |_{2}^{2} - {[(p_{i} - p_{0}) \cdot a]}^{2}}

。（6）

对于 $n (n \geq 6)$ 个点，引入最小二乘约束：

J : m i n \sum_{i = 1}^{n} v_{i}

，（7）

s t : | | a | |_{2}^{2} = 1

。（8）

4　点云基片特征参数

为了识别三维点云中的平面和圆柱面，定义了两个基片特征参数：平面度和法向偏差。

4.1　平面度

平面度是指点云基片具有的宏观凹凸高度相对理想平面的偏差，用来控制被测实际平面的形状误差。

点云基片的平面度可以通过求基片上各点到已拟合平面的距离近似估计，距离在一定阈值范围之内，便认为是平面。对于不同基片，需要设定不同的距离阈值，基片越大，设定的阈值也应越大。

通过计算向量 $F$ 和拟合平面法向 $N$ 之间的夹角 $θ$ 来估计平面度^［3］：

θ = a r c c o s (F \cdot N)

，（9）

F = \frac{1}{2} l U + l_{M D P} N

，（10）

式中： $N$ 为点云基片拟合所得平面的法向 $; U$ 为经过平面上的点且与平面法向 $N$ 垂直的单位向量； $l_{M D P}$ 表示基片上的点到平面的最大距离； $l$ 是基片有向包围盒的长边。 $θ$ 角越大越趋于平面，如图1所示。