阶梯垛型点云边界快速提取方法研究

张长勇，饶瑞

阶梯垛型点云边界快速提取方法研究

张长勇，饶瑞

（中国民航大学 电子信息与自动化学院，天津 300300）

针对阶梯垛型点云边界检测中，现有边界提取算法效率不高的问题，提出一种适用于阶梯垛型点云的快速边界提取算法。首先使用Kd–Tree对点云数据进行拓扑关系构建，其次搜索采样点及其近邻点，构建单位平面向量，并进行向量叠加，根据叠加后的向量模长来判断是否为候选边界点，然后使用近邻点最大夹角法来进行边界点精提取，最后使用Kinect相机获取阶梯垛型点云数据，进行算法对比验证。实验结果表明，文中算法在保证垛型边界提取精度的同时，比经典边界提取算法的运行时间缩短了75.14%，比优化前的边界提取算法运行时间缩短了11.06%。提出的边界提取算法能够快速准确地提取阶梯垛型点云边界，可为自动码垛系统的设计提供参考。

边界提取；垛型点云；粗提取；精提取

目前国内货物运输量正在快速增长，但多数物流货运中心依旧使用人工的方式进行货物码放[1]。为了提高物流自动化水平，降低人工成本，货物的自动码垛技术逐渐成为了研究热点。为减少码垛过程中，货物滑落、箱体变形对垛型结构的影响[2]，需要对垛型点云边界进行快速准确检测。对垛型边界提取算法的研究有利于垛型角点坐标的精准查找，以增强码垛算法的工程实践性[3]。

点云数据从维度上主要划分为二维点云数据和三维点云数据。针对不同维度的点云数据，很多学者提出了不同的边界提取方案。二维点云数据的边界提取算法主要有网格法和–Shape法。网格法是将点云按照一定规则分配到网格中，根据网格内是否有点来检索点云边界，该方法提取边界速度快，但是受到点云密度和网格大小影响。齐维毅等[4]提出一种基于四边形网格划分的点云边界快速提取方法。房鸿禧[5]提出了一种基于网格化的边缘二次提取算法，该算法将网格法与点云密度法进行融合，提升了网格法提取精度。–shapes法将一个圆在点云外滚动，根据圆的滚动轨迹来提取点云的边界，其边界受圆半径大小的影响[6]。王宗跃等[7]为提高–shapes法的提取速度，首先对点云数据进行网格化粗提取，剔除大量非边缘点，然后使用–shapes法提取边界。廖中平等[8]通过计算采样点近邻点的平均距离和调节因子，设置滚动圆的半径，实现了–shapes算法的自适应性。

三维点云数据的边界提取算法主要有微切平面法，基于点云特征等方法。微切平面法是以最小二乘法拟合局部点集的微切平面，并将点集在该平面进行投影，最后通过投影点连线的最大夹角来判别采样点是否为边界特征点[9]。刘庆等[10]利用改进的Kd–Tree（K-Dimensional Tree）来搜索采样点的K邻域，并拟合K邻域点集的微切平面，在微切平面上建立局部坐标系，将三维坐标转变为二维坐标，利用场力和判定阈值的大小来识别边界特征点。基于点云特征的方法是指利用点云自身的曲率、深度信息等特征来判断采样点是否为边界点。Xia等[11]通过定义无序点云中的梯度，分析特征值之间的比率来检测边缘候选点。Bazazian等[12]通过分析采样点K邻域点集的协方差矩阵的特征值来检测尖锐边缘的特征点。Xi等[13]根据深度信息将三维点云转换为图像信息，然后再使用二维图像边界提取常用的改进拉普拉斯算法来判断边界。蒋陈纯等[14]首先使用基于法向量叠加的方法进行边界粗提取，然后使用微切平面法进行精提取。韩玉川等[15]在构建Kd–Tree后，通过搜索视角控制边缘点云搜索方向和模拟点与点之间拉力的聚集程度相结合的方式来获取边界点云数据。

在货物码放过程中，货物垛型点云近似为阶梯状，具有多平面不相交的特征，即货物垛型可以看作多个深度不同的平面点云组成的三维点云。二维点云是三维点云边界提取的基础，但二维点云算法不可完全套用于三维垛型点云数据；而现有的三维点云边界提取算法虽然能比较精确地提取阶梯状垛型点云边界，但是判断准则复杂，提取时间较长，整体效率较低，不能很好地满足实际码垛需求。为解决以上问题，增加边界提取算法工程实用性，文中提出了一种阶梯垛型点云边界快速提取方法。该方法利用降维投影的思想，将三维点云简化为二维点云，再使用适用于二维点云的边界粗提取算法来得到点云的边界候选点。这样可以降低粗提取的计算复杂度，缩短精提取的计算时间，进而使边界提取算法运行效率得到提升。

1 边界提取算法

图1为边界提取算法框图，首先使用Kd–Tree对获取的点云数据进行点云拓扑关系构建，以减少近邻点的查找时间，进而提高点云边界的提取速度。然后使用优化的K邻域的向量叠加边界提取算法进行点云边界的粗提取，得到候选边界点。最后对候选边界点使用基于微切平面的近邻点最大夹角法进行精提取。

1.1 边界点粗提取

因为深度相机或三维激光扫描仪获取的原始点云数据通常是呈现离散无序状态并且数据量极为庞大，所以需要建立三维点云数据的空间拓扑关系来减少近邻点的查找时间[16]。常见的用于构建点云拓扑关系的方法有Kd–Tree、Oc–Tree和空间单元格法[16]。上述3种方法中，Kd–Tree法的本质是一种高维的二叉树结构，可以快速查找近邻点，与文中提取算法适配度最高，因此文中采用Kd–Tree法来构建点云间拓扑关系。

图1 边界提取算法框图

图2 单位化向量叠加示意图

文中的向量叠加算法流程如下。

1）构建点云拓扑关系。采用Kd–Tree来构建点云拓扑关系。

4）遍历所有点云数据。选取下一个采样点，重复步骤2和步骤3，直至完成所有点的判定，得到边界候选点。

1.2 边界点精提取

因为经过粗提取后得到的边界候选点中包含了边界点、邻近边界点和部分毛刺噪点，所以需要使用精准的边界提取算法，将边界点从边界候选点中提取出来。文献[9]中提出的基于微切平面投影的近邻点最大夹角边界提取算法可以准确地提取出点云边界点。文献[10]也证明该算法的有效性。文中选择基于微切平面投影的近邻点最大夹角算法作为边界点精提取算法。该算法的主要原理：用最小二乘法拟合采样点及其近邻点的微切平面，并向微切平面投影，根据采样点与投影点的夹角大小来判定该采样点是否为边界点[9]。

2 实验结果分析

为测试文中算法的可行性和运行效率，采用Kinect v1相机搭建垛型点云检测平台来获取阶梯垛型点云数据。Kinect v1相机的颜色分辨率为640×480，深度分辨率为320×240，深度误差为2～20 mm[17]。实验以Visual Studio 2019结合PCL（Point Cloud Library, PCL）为平台，在硬件配置为i5–8500 CPU@3.00 GHz、8 GB内存、Windows 10、64位系统的计算机上运行。

2.1 可行性分析

Kinect v1相机置于垛型正上方1.5 m处，采集如图4a所示的阶梯状复杂垛型点云数据。该点云数据包含300 754个点，图4b为初始垛型点云俯视图，图4c为初始垛型点云前视图。从图4c中可以看出，该垛型点云平面凹凸点较多，即深度相机采集的点云数据存在不容忽视的深度误差，而这些误差会导致现有点云边界提取算法效果不佳。

为了方便后续的处理，使用直通滤波算法来限制垛型点云数据的坐标范围，分离地面点云，得到11 044个垛型点云数据，见图5a。文中算法的粗提取参数=40，模长阈值为0.039，精提取参数=20，最大夹角设为90°。用文献[9]、文献[14]与文中算法进行对比实验，文献[9]算法是基于微切平面投影的近邻点最大夹角法，文献[14]同样采用先粗提取后精提取的思路，其粗提取算法为传统向量叠加算法，精提取算法为基于微切平面投影的近邻点最大夹角法。

图4 原始点云数据

从实验结果可以看出，相较于文献[14]，文中算法的粗提取结果可以较好地剔除点云内部点，准确保留点云边界点；精提取后的点云数据毛刺点噪点较小，边界点保存也更为完整。这是因为深度相机受测量原理和外界环境因素影响，会产生系统误差和场景误差，这些误差主要体现在深度偏移，即轴坐标存在误差[18]。文中粗提取采用降维投影，简化了点云数据，简化后的点云数据不包含轴坐标，消除了深度误差的影响。文献[9]由于直接采用精提取算法，虽然具有较好的边界提取效果，但其运算时间远大于文中算法。

图5 不同算法边界点提取结果

2.2 运行效率分析

为验证边界提取算法的运行效率，利用图5a垛型点云数据对3种算法运行时间进行测试，得到实验结果见表1。从表1中数据可以看出，由于文献[9]省去了粗提取过程，直接使用精提取算法对垛型点云边界进行提取，运算时间达到15.85 s，远高于另外2种算法；文中算法的总运行时间比文献[14]减少11.06%，粗提取时间减少10.38%，这是因为文中粗提取算法简化了点云数据，降低了粗提取的计算维度，使得边界候选点数量有所下降。

表1 不同边界提取算法运行时间

Tab.1 Running time of different boundary extraction algorithms

3 结语

针对货物垛型检测中，现有点云边界提取算法效率不高的问题，提出了一种适用于阶梯状垛型的边界快速提取算法。在粗提取中，使用降维投影思想，将局部三维点云数据简化为二维点云数据，再使用二维点云边界提取算法，提取出边界候选点。该粗提取方法在保证粗提取精度前提下，缩短了粗提取时间。在精提取中，使用近邻点最大夹角法保证了边界点的精准性。采用Kinect v1相机搭建垛型点云检测平台，对算法进行测试验证，结果表明，文中算法能够快速准确地获取阶梯垛型点云的边界，具有一定的工程应用价值，可为货物自动码垛系统的设计提供参考。

[1] 张长勇, 吴智博. 基于K-means与关键点的组合行李码放算法[J]. 包装工程, 2019, 40(9): 90-95.

ZHANG Chang-yong, WU Zhi-bo. Combined Luggage Stacking Algorithm Based on K-means and Key Points[J]. Packaging Engineering, 2019, 40(9): 90-95.

[2] ANGELOPOULOS S, DÜRR C, KAMALI S, et al. Online Bin Packing with Advice of Small Size[J]. Theory of Computing Systems, 2018, 62(4): 2006-2034.

[3] KLEPPE A L, EGELAND O. A Curvature-Based Descriptor for Point Cloud Alignment Using Conformal Geometric Algebra[J]. Advances in Applied Clifford Algebras, 2018, 28(2): 1-16.

[4] 齐维毅, 丁言镁, 吴丽娟. 四边形网格划分过程中的边界提取与优化算法的实现[J]. 小型微型计算机系统, 2007, 28(10): 1861-1864.

QI Wei-yi, DING Yan-mei, WU Li-juan. Realization of the Edge Points Searching and Edges Optimization Algorithm in Quadrangular Meshes Generation Process[J]. Journal of Chinese Computer Systems, 2007, 28(10): 1861-1864.

[5] 房鸿禧. 基于三维点云的多目标分割与边缘提取[D]. 上海: 上海师范大学, 2020: 42-45.

FANG Hong-xi. Multi-Target Segmentation and Edge Extraction Based on 3D Point Cloud[D]. Shanghai: Shanghai Normal University, 2020: 42-45.

[6] YAN Ke, CHENG H L, HUANG Jing. Representing Implicit Surfaces Satisfying Lipschitz Conditions by 4-Dimensional Point Sets[J]. Applied Mathematics and Computation, 2019, 354: 42-57.

[7] 王宗跃, 马洪超, 徐宏根, 等. 海量点云的边缘快速提取算法[J]. 计算机工程与应用, 2010, 46(36): 213-215.

WANG Zong-yue, MA Hong-chao, XU Hong-gen, et al. Novel Algorithm for Fast Extracting Edges from Massive Point Clouds[J]. Computer Engineering and Applications, 2010, 46(36): 213-215.

[8] 廖中平, 陈立, 白慧鹏, 等. 自适应α-shapes平面点云边界提取方法[J]. 长沙理工大学学报(自然科学版), 2019, 16(2): 15-21.

LIAO Zhong-ping, CHEN Li, BAI Hui-peng, et al. Adaptive Alpha-Shapes Plane Point Cloud Boundary Extraction Method[J]. Journal of Changsha University of Science & Technology (Natural Science), 2019, 16(2): 15-21.

[9] 孙殿柱, 范志先, 李延瑞. 散乱数据点云边界特征自动提取算法[J]. 华中科技大学学报(自然科学版), 2008, 36(8): 82-84.

SUN Dian-zhu, FAN Zhi-xian, LI Yan-rui. Automatic Extraction of Boundary Characteristic from Scatter Data[J]. Journal of Huazhong University of Science and Technology (Nature Science Edition), 2008, 36(8): 82-84.

[10] 刘庆, 章光, 陈西江. 融合改进场力和判定准则的点云特征规则化[J]. 中国激光, 2019, 46(4): 200-209.

LIU Qing, ZHANG Guang, CHEN Xi-jiang. Point Cloud Feature Regularization Based on Fusion of Improved Field Force and Judging Criterion[J]. Chinese Journal of Lasers, 2019, 46(4): 200-209.

[11] XIA Shao-bo, WANG Rui-sheng. A Fast Edge Extraction Method for Mobile Lidar Point Clouds[J]. IEEE Geoscience and Remote Sensing Letters, 2017, 14(8): 1288-1292.

[12] BAZAZIAN D, CASAS J R, RUIZ-HIDALGO J. Fast and Robust Edge Extraction in Unorganized Point Clouds[C]// 2015 International Conference on Digital Image Computing: Techniques and Applications (DICTA),Adelaide, 2015: 1-8.

[13] XI X, WAN Y, CHENG W. Building Boundaries Extraction from Points Cloud Using an Image Edge Detection Method[C]// 2016 IEEE International Geoscience and Remote Sensing Symposium (IGARSS), Beijing, 2016: 1270-1273.

[14] 蒋陈纯, 刘科, 舒敏. 点云边界快速精确提取算法[J]. 光电子·激光, 2020, 31(5): 531-538.

JIANG Chen-chun, LIU Ke, SHU Min. Algorithm for Fast and Accurate Boundary Points Extraction[J]. Journal of Optoelectronics·Laser, 2020, 31(5): 531-538.

[15] 韩玉川, 侯贺, 白云瑞, 等. 一种基于边缘系数的闭合点云边缘提取算法[J]. 激光与光电子学进展, 2018, 55(11): 161-166.

HAN Yu-chuan, HOU He, BAI Yun-rui, et al. A Closed Point Cloud Edge Extraction Algorithm Using Edge Coefficient[J]. Laser & Optoelectronics Progress, 2018, 55(11): 161-166.

[16] SHI Gui-gang, GAO Xu-guang, DANG Xing-hua. Improved ICP Point Cloud Registration Based on KDTree[J]. International Journal of Earth Sciences and Engineering, 2016, 9(5): 2195-2199.

[17] YUAN Zhi-lu, LI You, TANG Sheng-jun, et al. A Survey on Indoor 3D Modeling and Applications via RGB-D Devices[J]. Frontiers of Information Technology & Electronic Engineering, 2021, 22(6): 815-826.

[18] 卢纯青, 宋玉志, 武延鹏, 等. 基于TOF计算成像的三维信息获取与误差分析[J]. 红外与激光工程, 2018, 47(10): 160-166.

LU Chun-qing, SONG Yu-zhi, WU Yan-peng, et al. 3D Information Acquisition and Error Analysis Based on TOF Computational Imaging[J]. Infrared and Laser Engineering, 2018, 47(10): 160-166.

Fast Boundary Extraction Method of Stepped Stack Point Cloud

ZHANG Chang-yong, RAO Rui

(School of Electronic Information and Automation, Civil Aviation University of China, Tianjin 300300, China)

The work aims to propose a fast boundary extraction algorithm applicable to stepped stack point cloud, so as to solve the problem of low efficiency of existing boundary extraction algorithm in stepped stack point cloud boundary detection. Firstly, Kd-Tree was used to construct the topological relationship of point cloud data. Then, the sampling point and its adjacent point were searched to construct the unit plane vector and perform vector superposition. The candidate boundary point was judged according to the vector modulus length after superposition. Finally, the maximum angle method of adjacent points was used to extract the boundary point accurately. Kinect camera was applied to obtain the stepped stack point cloud data to verify the algorithm. The experimental results showed that the proposed algorithm could shorten the running time by 75.14% compared with the classical boundary extraction algorithm when ensuring the extraction accuracy of stack boundary, and shorten the running time by 11.06% compared with the boundary extraction algorithm before optimization. The proposed boundary extraction algorithm can quickly and accurately extract the stepped stack point cloud boundary, which can provide reference for the design of automatic stack system.

boundary extraction; stack point cloud; rough extraction; fine extraction

TN98

A

1001-3563(2022)17-0190-06

10.19554/j.cnki.1001-3563.2022.17.024

2021–07–14

国家自然科学基金青年基金（51707195）；中央高校基本科研业务费专项基金A类（3122016A009）

张长勇（1978—），男，博士，副教授，主要研究方向为智能电器与机场自动化。

责任编辑：曾钰婵