[1]张 冬,云 挺,薛联凤,等.复杂拓扑结构的树木枝干重建算法[J].南京师大学报(自然科学版),2015,38(01):128.
　Zhang Dong,Yun Ting,Xue Lianfeng,et al.Reconstruction Algorithm with Complex Topology of Tree Branches[J].Journal of Nanjing Normal University(Natural Science Edition),2015,38(01):128.
点击复制

复杂拓扑结构的树木枝干重建算法()
分享到：

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

卷:
第38卷
期数:
2015年01期
页码:
128
栏目:
计算机科学
出版日期:
2015-06-30

文章信息/Info

Title:
Reconstruction Algorithm with Complex Topology of Tree Branches
作者:
张 冬; 云 挺; 薛联凤; 罗 毅
南京林业大学信息科学技术学院,江苏 南京210037
Author(s):
Zhang Dong; Yun Ting; Xue Lianfeng; Luo Yi
Department of Information Science and Technology,Nanjing forestry University,Nanjing 210037,China
关键词:
Laplace变换; 枝干重建; 激光点云处理; 黎曼流形
Keywords:
the Laplace transform; branches reconstruction; laser point cloud processing; Riemannian manifold
分类号:
TP391.9
文献标志码:
A
摘要:
具有复杂拓扑结构的树木枝干重建问题是国内外研究的一个热点和难点. 本文提出了一种有效且鲁棒的树木枝干重建算法. 首先在原始树木点云上建立基于黎曼流形的Delaunay邻域关系,然后将所有顶点当作位置约束加Laplace方程,再迭代地解Laplace方程将点云收缩到我们预想的程度,然后利用聚类和连接算法得到一个初步的树木枝干,最后再通过修复得到最终的树木枝干. 本文的算法在对含笑树和樱花树上进行了验证,实验结果表明该算法有很好的重建效果.
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:
收稿日期:2014-06-19.
基金项目:国家自然科学基金(31300472)、江苏省自然科学基金(BK2012418).
通讯联系人:薛联凤,副教授,研究方向:图像处理. E-mail:285201972@qq.com
更新日期/Last Update: 2015-03-30