一种基于Graham扫描算法的空间点云结构化算法研究  

Research on space point cloud structuring algorithm based on Graham scanning algorithm

作　　者：王凯 支煜[2] 陈浩 张毅坤[2] WANG Kai;ZHI Yu;CHEN Hao;ZHANG Yikun(Xi＇an Institute of Measurement and Testing Technology,Xi＇an 710068,China;Xi＇an University of Technology,Xi＇an 710048,China)

机构地区：[1]西安计量技术研究院,陕西西安710068 [2]西安理工大学,陕西西安710048

出　　处：《现代电子技术》2018年第14期139-142,146,共5页Modern Electronics Technique

基　　金：陕西省工业科技攻关项目(2014K05-33)~~

摘　　要：在过度包装检测过程中,针对商品三维重建后的散乱点云无法进行后续空隙率判定的问题,提出一种基于Denaunay三角化和凸包算法的散乱点云结构化方法。首先,因为空间点云结构复杂,所以将空间点云进行切片和投影操作,也就是降维操作;其次,对投影数据点进行结构化处理,寻找初始点,依次对投影点按照极角大小进行排序;最后利用所构造的扫描线对数据点进行筛选和结构化。实验表明,基于Denaunay三角化和凸包算法的散乱点云结构化方法处理时间短,稳定性和精度高、适用性强,完全满足过度包装检测系统。与目前方法相比,该方法有更好的适用性,能够满足大多数平台的需求。In allusion to the problem that the subsequent voidage judgment cannot be performed due to the scattered point cloud after 3 D reconstruction of commodities during the excessive packaging detection process,a scattered point cloud structuring method based on Denaunay triangularization and convex hull algorithm is proposed. As the structure of the space point cloud is complex,the slicing and projection operations（also called dimensionality reduction operations）are conducted. The projected data points are structured,the initial point is searched out,and the projected points are orderly ranked according to the size of the polar angle. The data points are filtered and structured by using the constructed scanning line. The experimental results show that the scattered point cloud structuring method based on Denaunay triangularization and convex hull algorithm has short processing time,high stability and accuracy,and strong applicability,and can fully satisfy the excessive packaging detection system. In comparison with the current method,the method has better applicability,and can meet the needs of most platforms.

关 键 词：过度包装 散乱点云 Graham扫描算法 Denaunay三角化 凸包算法 点云结构化 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术]