|Table of Contents|

Reconstruction Algorithm with Complex Topology of Tree Branches(PDF)

《南京师大学报（自然科学版）》[ISSN:1001-4616/CN:32-1239/N]

Issue:
2015年01期
Page:
128-
Research Field:
计算机科学
Publishing date:

Info

Title:
Reconstruction Algorithm with Complex Topology of Tree Branches
Author(s):
Zhang Dong; Yun Ting; Xue Lianfeng; Luo Yi
Department of Information Science and Technology,Nanjing forestry University,Nanjing 210037,China
Keywords:
the Laplace transform; branches reconstruction; laser point cloud processing; Riemannian manifold
PACS:
TP391.9
DOI:
-
Abstract:
Currently,the problem of branches of trees with complex topology reconstruction is a hot and difficult domestic and international research. In this paper,we proposed an effective and robust algorithm for extraction curve-skeletons from point clouds. Firstly based on Riemannian manifolds Delaunay neighborhood relations,and constructed a Laplace matrix. We treated all points as positional constraints. We solved and updated the discrete Laplace system iteratively,until all points contracted to the positions we needed. Then we employed the Principle Component Analysis(PCA)to differentiate between joints and branches of the contracted points. We clustered the two kinds of regions separately to get the key nodes. Then we connected these key nodes by the connection surgery we proposed to get a raw curve-skeleton of the given point cloud. We constructed a graph on the curve-skeleton,and computed the Minimum Spanning Tree(MST). Finally,we refined the MST and gained the final curve-skeleton.

References:

[1] Deok S K,Young S C,Dengue K. Euclidean Voronoi diagram of 3D balls and its computation via tracing edges[J]. Computer-Aided Design,2005,245(20):3 713-3 721.
[2]Cao A W,Yung T. Finding constrained and weighted Voronoi diagrams in the plane[J]. Computational Geometry:Theory and Applications,1998,283(16):1 027-1 035.
[3]Incur C,Deborah S,Xiao S,et al. Computing hierarchical curve-skeletons of 3D objects[J]. The Visual Computer,2005,89(11):895-907.
[4]Lawson W,Richard E P. Automated generation of control skeletons for use in animation[J]. The Visual Computer,2002,275(21):2 175-2 183.
[5]Taube G. A signal processing approach to fair surface design[C]//International Conference on Computer Graphics and Interactive Techniques. Los Angeles:The International Institute for Science,Technology and Education,1995.
[6]王林峰. 加权Laplace-Beltrami算子及相关问题研究[D]. 上海:华东师范大学数学学院,2007.
[7]李义琛. 点云模型骨架提取算法的研究与实现[D]. 南京:南京师范大学教育科学学院,2012.
[8]张亶,陈为,单开佳,等. 基于拉普拉斯算子的Snakes方法分析[J]. 计算机辅助设计与图形学学报,2005,6(20):527-531.
[9]Dieter M,Maria S,Rodrigo I S. On the number of higher order Delaunay triangulations[J]. Theoretical Computer Science,2011,281(45):41 229-41 235.
[10]Jonathan,Richard,Shewchuk. Reprint of:delaunay refinement algorithms for triangular mesh generation[J]. Computational Geometry:Theory and Applications,2014,365(78):15 081-15 090.
[11]Rodrigo I,Silveira,Marc van Kreveld. Towards a definition of higher order constrained Delaunay triangulations[J]. Computational Geometry:Theory and Applications,2008,424(21):1 051-1 059.
[12]Marian N. Delaunay configurations and multivariate splines:a generalization of a result of B N Delaunay[J]. Transactions of the American Mathematical Society,2007,207(20):3 597-3 602.
[13]金龙存. 3D点云复杂点云曲面重构关键算法研究[D]. 上海:上海大学计算机学院,2012.
[14]何学铭. 点云模型的孔洞修补技术研究[D]. 南京:南京师范大学教育科学学院,2013.
[15]丁帆. 点云数据三维网格构造方法研究[D]. 武汉:华中科技大学计算机学院,2007.
[16]Zhou K,Huang J,Snyder J. Large mesh deformation using the volumetric graph Laplacian[J]. ACM Transactions on Graphics,2005,217(20):1 207-1 213.
[17]Lipman Y,Sorkine O,Cohen-or D,et al. Differential coordinates for interactive mesh editing[C]//Proceedings of the International Conference on Shape Modeling and Applications. San Francisco:Morgan Kaufmann,2004.
[18]Gong W,Bertrand G. A simple parallel 3D thinning algorithm[C]//10th International Conference on Pattern Recognition. Istanbul:Nova Science Publishers,1990.
[19]Cornea N D,Demirci M F,Silver D,et al. 3D object retrieval using many-to-many matching of curve skeletons[C]//Proceedings of the International Conference on Shape Modeling and Applications. New York:Los Andes,2005.
[20]Kobatake S,Kawakubo Y,Suzuki S. Laplace pressure measurement on laser textured thin-film disk[J]. Teratology International,2003,364(26):10 631-10 642.
[21]Adam M B. Finite difference methods for the infinity Laplace and p-Laplace equations[J]. Journal of Computational and Applied Mathematics,2013,254(419):1 872-1 882.
[22]Humid R,Soon-Mo J,Themistocles M R. Laplace transform and Hyers-Ulam stability of linear differential equations[J]. Journal of Mathematical Analysis and Applications,2013,381(29):4 031-4 045.
[23]Tomasz J K,Krzysztof P,Igor R. Multivariate generalized Laplace distribution and related random fields[J]. Journal of Multivariate Analysis,2013,113(25):3 085-3 093.

Memo

Memo:
-
Last Update: 2015-03-30