自适应步长的Alpha?shape表面重建算法  

Surface Reconstruction Algorithm Using Self?adaptive Step Alpha?shape

作　　者：李世林[1] 李红军[1] Li Shilin;Li Hongjun(College of Science,Beijing Forestry University,Beijing,100083,China)

机构地区：[1]北京林业大学理学院

出　　处：《数据采集与处理》2019年第3期491-499,共9页Journal of Data Acquisition and Processing

基　　金：国家自然科学基金(61372190)资助项目

摘　　要：三维物体表面重建在现代临床医学、场景建模和林业测量等方面有着重要应用价值。为了更好地理解三维物体表面形状,本文先介绍了三维空间离散点集的Alpha形状的相关概念。在分析表面重建的Alpha-shape算法的基础上,本文提出一种自适应步长的Alpha-shape算法。通过kd-tree和k近邻平均距离来动态更新α值,使得算法在处理点集密度较大的区域时也能以较少的遍历次数进行表面重建,从而改善了重建效果并提高了算法运行效率。大量随机数据和现实三维采样数据的实验结果表明,本文提出的改进算法与原始算法相比,能大幅度地提高运行效率。3D object surface reconstruction has important applications in modern clinical medicine,scene modeling and forestry survey and so on.In order to better understand the reconstruction of 3D object surface,this paper first introduces the concept of the Alpha shape of the 3D discrete point set.Based on the analysis of surface reconstruction algorithm using self-adaptive step Alpha-shape is proposed.The value of Alpha is updated dynamically using the kd-tree structure and the average distance of k-nearest neighbors,so that the algorithm can reconstruct the surface with less number of times when the density of the point set is larger.Thus,the reconstruction effect is improved and the operation efficiency of the algorithm is improved.The experimental results with a large number of random data and realistic 3D scanning data show that the proposed algorithm can greatly improve the efficiency compared with the original algorithm.

关 键 词：表面重建 Alpha形状 k近邻平均距离 Alpha-shape算法 

分 类 号：TP391[自动化与计算机技术—计算机应用技术] TP311[自动化与计算机技术—计算机科学与技术]