自适应步长的Alpha?shape表面重建算法
|
摘要
三维物体表面重建在现代临床医学、场景建模和林业测量等方面有着重要应用价值。为了更好地理解三维物体表面形状,本文先介绍了三维空间离散点集的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.
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.
引文
[1]刘进.基于MVS点云的城市建筑三维重建应用研究[D].南宁:广西大学, 2015.Liu Jin. Applied research on 3D reconstruction of urban building based on MVS point cloud[D]. Nanning:Guangxi University,2015.
[2]喻垚慎,云挺,杨绪兵.基于激光点云数据的植物器官多维特征分割方法[J].数据采集与处理, 2015, 30(5):1054-1061.Yu Yaoshen, Yun Ting, Yang Xubing. Multi-dimension feature segmentation method of foliage organs based on laser point cloud data[J]. Journal of Data Acquisition and Processing, 2015, 30(5):1054-1061.
[3]邹豪, Heang K Ty,刘积仁.医学图像三维表面模型重建[J]. CT理论与应用研究, 2000, 9(S1):23-28.Zou Hao, Heang K Ty, Liu Jiren. Surface shading of three-dimensional medical objects[J]. CT Theory and Applications,2000, 9(S1):23-28.
[4]孙家泽,陈皓,耿国华.三维文物点云模型配准优化算法[J].计算机辅助设计与图形学学报, 2016, 28(7):1068-1074.Sun Jiaze, Chen Hao, Geng Guohua. Registration optimization algorithm for 3D cultural relics point clouds model[J]. Journal of Computer-Aided Design&Computer Graphics, 2016, 28(7):1068-1074.
[5] Jarvis R A. Computing the shape hull of points in the plane[C]//Proceedings of the IEEE Computing Society Conference on Pattern Recognition and Image Processing. New York:IEEE, 1977:231-241.
[6] Edelsbrunner H, Kirkpatrick D, Seidel R. On the shape of a set of points in the plane[J]. IEEE Transactions on Information Theory, 1983, 29(4):551-559.
[7] Boissonnat J D. Geometric structures for three-dimensional shape representation[J]. ACM Transactions on Graphics, 1984, 3(4):266-286.
[8] Edelsbrunner H, Mücke E P. Three-dimensional Alpha shapes[J]. ACM Transactions on Graphics, 1994, 13(1):43-72.
[9] Teichmann M, Capps M. Surface reconstruction with anisotropic density-scaled Alpha shapes[C]//Proceedings of Visualization.[S.l.]:IEEE Xplore, 1998:67-72.
[10] Xu X, Harada K. Automatic surface reconstruction with Alpha-shape method[J]. The Visual Computer, 2003, 19(7):431-443.
[11]李云帆,谭德宝,高广,等.双阈值Alpha Shapes算法提取点云建筑物轮廓研究[J].长江科学院院报, 2016, 33(11):1-4.Li Yunfan, Tan Debao, Gao Guang, et al. Extraction of building contour from point clouds using dual threshold Alpha shapes algorithm[J]. Journal of Yangtze River Scientific Research Institute, 2016, 33(11):1-4.
[12] Weinmann M, Jutzi B, Hinz S, et al. Semantic point cloud interpretation based on optimal neighborhoods, relevant features and efficient classifiers[J]. ISPRS Journal of Photogrammetry&Remote Sensing, 2015, 105:286-304.
[13]李红军,刘欣莹,张晓鹏,等.局部形状特征概率混合的半自动三维点云分类[J].浙江大学学报:理学版, 2017, 44(1):1-9.Li Hongjun, Liu Xinying, Zhang Xiaopeng, et al. A semi-automatic 3D point cloud classification method based on the probability mixture of local shape features[J]. Journal of Zhejiang University:Science Edition, 2017, 44(1):1-9.
[14] Arias-Castro E, Casal A R. On estimating the perimeter using the alpha-shape[J]. Annales de l'Institut Henri Poincaré,Probabilités et Statistiques, 2017, 53(3):1051-1068.
[15] Zhu C, Zhang X, Hu B G, et al. Reconstruction of tree crown shape from scanned data[C]//International Conference on Technologies for E-learning&Digital Entertainment, Edutainment 2008, Lecture Notes in Computer Science. Berlin,Heidelberg:Springer, 2008:745-756.
[16] Ariascastro E, Pateirolópez B, Rodríguezcasal A. Minimax estimation of the volume of a set under the rolling ball condition[J].Journal of the American Statistical Association, 2018:1-37.
[17]张晓,张媛媛,高阳,等.一种基于密度的快速聚类方法[J].数据采集与处理, 2015,30(4):888-895.Zhang Xiao, Zhang Yuanyuan, Gao Yang, et al. Fast density-based clustering approach[J]. Journal of Data Acquisition and Processing, 2015,30(4):888-895.
[2]喻垚慎,云挺,杨绪兵.基于激光点云数据的植物器官多维特征分割方法[J].数据采集与处理, 2015, 30(5):1054-1061.Yu Yaoshen, Yun Ting, Yang Xubing. Multi-dimension feature segmentation method of foliage organs based on laser point cloud data[J]. Journal of Data Acquisition and Processing, 2015, 30(5):1054-1061.
[3]邹豪, Heang K Ty,刘积仁.医学图像三维表面模型重建[J]. CT理论与应用研究, 2000, 9(S1):23-28.Zou Hao, Heang K Ty, Liu Jiren. Surface shading of three-dimensional medical objects[J]. CT Theory and Applications,2000, 9(S1):23-28.
[4]孙家泽,陈皓,耿国华.三维文物点云模型配准优化算法[J].计算机辅助设计与图形学学报, 2016, 28(7):1068-1074.Sun Jiaze, Chen Hao, Geng Guohua. Registration optimization algorithm for 3D cultural relics point clouds model[J]. Journal of Computer-Aided Design&Computer Graphics, 2016, 28(7):1068-1074.
[5] Jarvis R A. Computing the shape hull of points in the plane[C]//Proceedings of the IEEE Computing Society Conference on Pattern Recognition and Image Processing. New York:IEEE, 1977:231-241.
[6] Edelsbrunner H, Kirkpatrick D, Seidel R. On the shape of a set of points in the plane[J]. IEEE Transactions on Information Theory, 1983, 29(4):551-559.
[7] Boissonnat J D. Geometric structures for three-dimensional shape representation[J]. ACM Transactions on Graphics, 1984, 3(4):266-286.
[8] Edelsbrunner H, Mücke E P. Three-dimensional Alpha shapes[J]. ACM Transactions on Graphics, 1994, 13(1):43-72.
[9] Teichmann M, Capps M. Surface reconstruction with anisotropic density-scaled Alpha shapes[C]//Proceedings of Visualization.[S.l.]:IEEE Xplore, 1998:67-72.
[10] Xu X, Harada K. Automatic surface reconstruction with Alpha-shape method[J]. The Visual Computer, 2003, 19(7):431-443.
[11]李云帆,谭德宝,高广,等.双阈值Alpha Shapes算法提取点云建筑物轮廓研究[J].长江科学院院报, 2016, 33(11):1-4.Li Yunfan, Tan Debao, Gao Guang, et al. Extraction of building contour from point clouds using dual threshold Alpha shapes algorithm[J]. Journal of Yangtze River Scientific Research Institute, 2016, 33(11):1-4.
[12] Weinmann M, Jutzi B, Hinz S, et al. Semantic point cloud interpretation based on optimal neighborhoods, relevant features and efficient classifiers[J]. ISPRS Journal of Photogrammetry&Remote Sensing, 2015, 105:286-304.
[13]李红军,刘欣莹,张晓鹏,等.局部形状特征概率混合的半自动三维点云分类[J].浙江大学学报:理学版, 2017, 44(1):1-9.Li Hongjun, Liu Xinying, Zhang Xiaopeng, et al. A semi-automatic 3D point cloud classification method based on the probability mixture of local shape features[J]. Journal of Zhejiang University:Science Edition, 2017, 44(1):1-9.
[14] Arias-Castro E, Casal A R. On estimating the perimeter using the alpha-shape[J]. Annales de l'Institut Henri Poincaré,Probabilités et Statistiques, 2017, 53(3):1051-1068.
[15] Zhu C, Zhang X, Hu B G, et al. Reconstruction of tree crown shape from scanned data[C]//International Conference on Technologies for E-learning&Digital Entertainment, Edutainment 2008, Lecture Notes in Computer Science. Berlin,Heidelberg:Springer, 2008:745-756.
[16] Ariascastro E, Pateirolópez B, Rodríguezcasal A. Minimax estimation of the volume of a set under the rolling ball condition[J].Journal of the American Statistical Association, 2018:1-37.
[17]张晓,张媛媛,高阳,等.一种基于密度的快速聚类方法[J].数据采集与处理, 2015,30(4):888-895.Zhang Xiao, Zhang Yuanyuan, Gao Yang, et al. Fast density-based clustering approach[J]. Journal of Data Acquisition and Processing, 2015,30(4):888-895.