階梯垛型點云邊界快速提取方法研究

張長勇，饒瑞

階梯垛型點云邊界快速提取方法研究

張長勇，饒瑞

（中國民航大學 電子信息與自動化學院，天津 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—），男，博士，副教授，主要研究方向為智能電器與機場自動化。

責任編輯：曾鈺嬋