摘 要

因树木枝干具有复杂的拓扑结构，所以该重建问题一直是国内外研究的一个热点和难点。在本文中，我们对现有的基于Laplace微分算子的点云骨架化算法进行了改进，主要是修改了Laplace加权矩阵在迭代收缩过程中基于角度度量的加权值，利用本文提出的基于距离度量的点云势函数来替代原有的基于角度度量的加权。再利用聚类和连接算法得到一个初步的树木枝干,最后再通过修复得到最终的树木枝干。本文的算法验证对象是芒果树和胡桃树,实验结果验证了该算法的可行性和高效性。

关键词：拉普拉斯变换；枝干重建；黎曼流形；激光点云处理

Reconstruction Algorithm with Complex Topology of Tree Branches

ABSTRACT

Because of trees with complex topology structure, so the reconstruction problem is a hot and difficult research at home and abroad. In this article, we to the existing of the point cloud based on Laplace differential operator skeletonization algorithm is improved, and modified the Laplace weighted matrix is mainly based on Angle measurement in the process of iteration contraction of weighted value, using the proposed point cloud based on distance measure potential function to replace the original weighted based on Angle measurement. Reuse clustering and the connection algorithm to get a preliminary of trees, and then through the repair to get the final tree branches. In this paper, the algorithm in the mango tree and walnut trees are verified, the experimental results verify the feasibility and efficiency of the algorithm.

Key words：the Laplace transform; branches reconstruction; Riemannian manifold; laser point cloud processing

目 录

第1章 绪论 - 1 -

1.1国内外研究现状 - 1 -

1.2 研究目的和意义 - 1 -

1.3 研究内容 - 2 -

第2章 开发技术介绍 - 3 -

2.1 技术简介 - 3 -

2.2 优势特点 - 3 -

2.3 图形处理 - 3 -

2.4 MATLAB语言基础 - 4 -

2.5 应用方面 - 4 -

第3章 黎曼流形 Delaunay三角化 - 6 -

3.1黎曼流形 - 6 -

3.1.1 概念 - 6 -

3.1.2 定义 - 6 -

3.2 Delaunay三角化 - 7 -

3.3 基于坐标卡的生成算法 - 7 -

3.3.1 建立坐标卡 - 8 -

3.3.2 生成网格 - 9 -

第4章 基于拉普拉斯算子的曲面重建 - 11 -

4.1 Laplace算子和曲面微分 - 11 -

4.2 点的势函数 - 12 -

4.3 基于拉普拉斯算子的曲面重建算法 - 13 -

4.3.1 构建Laplace矩阵 - 13 -

4.3.2 点云收缩 - 13 -

4.3.3 点云聚类 - 15 -

4.3.4 连接关键点 - 15 -

第5章 实验结果 - 16 -

5.1 采集数据 - 16 -

5.2 实验平台 - 17 -

5.3 分析和比较 - 17 -

5.3.1 胡桃树 - 17 -

5.3.2 芒果树 - 18 -

5.3.3 最终重建结果 - 19 -

结 论 - 22 -

致 谢 - 23 -

参考文献 - 24 -

第1章 绪论

1.1国内外研究现状

树木作为自然界中最有代表性的自然景观之一，其形态结构迥异、种类多样，三维的树木模型在很多场景中均有普遍的应用，例如具有真实感的虚拟树木在虚拟景观、智慧林业、虚拟农（林）业生态系统等场景的构建中起着举足轻重的作用。而真实的树木三维模型则有着更加重要的研究价值，比如可以通过真实树木的三维模型模拟林木在自然界中的状态、真实的刻画自然界中林木的属性参数、古木名树的调查研究、表达在自然环境下树木的生长过程等。植物的形态结构特征对不同尺度的生物物理过程起着决定性作用；植物的结构功能模型有助于进一步了解生长过程及环境的影响，例如种群间的竞争、依赖作用等都可以运用到真实树木的三维建模。然而，由于自然环境的复杂多变，导致树木具有非常复杂的拓扑结构和形态特征，比如树干的直径粗细不一、枝干的形势走向不确定、树干之间的缠绕、树叶和树干之间的相互遮挡等，这些都造成对于树木的建模是一个非常棘手的问题。传统的建模方法在面对拓扑结构复杂的树木时建模效果并不如意，因此设计出一种能适应树木复杂结构的建模方法一直是广大科技工作者需要亟待解决的问题。

1.2 研究目的和意义

计算机软硬件技术的飞速发展推动着各行各业的研究进展，其可处理的数据规模无论从单位数量上还是个体维度上都呈现出大的飞跃，其中就包括三维点云数据(Point Cloud)，点云是指通过三维激光雷达扫描仪器获得的研究对象表面点的数据集合^{[1, 2]}。通过三维点云表示研究对象，相比于二维图像有着更加真实、更加直观和更加丰富的结构特征和几何信息，其表现力大大增强，因此在娱乐、工程、教育、虚拟仿真等诸多领域有着广泛的应用。

基于距离场求解点云树木骨架的方法，不同于微分算子通过迭代的方法收缩求解，是一种通过物理学中场的概念。距离场是介于物理场和静电场的一种概念模型，距离场只考虑距离所要研究点最近的局部点之间的相互影响，因此在局部上可以很好的保留树木的原始形态特征。距离场的方法应用比较广泛，因为利用该方法求得的骨架包含距离度量值，所以可以用来对模型重建，在构建骨架点的准确度上，基于距离变换的方法优势非常显著。基于力场的方法是基于距离场求解模型骨架法的一种，运用距离场局部点互相可见的特征求解模型中轴。通过定义一个距离函数，根据欧氏距离判断模型内部到边界点的最小点，然后通过给定阈值检测模型的“脊点”来判断预选节点，其次通过顺次连接这些节点得到模型的粗略骨架。本文中运用力场求解树木骨架的思路主要如下所述：首先对原始的点云树木运用空间层次剖分的方法进行分层，对于每一个分层依据点云的邻域关系做一个简化;然后运用高斯法向聚类算法确定点云树木当中的特征点，其次根据侧地距离构建初始表面骨架模型;最后运用力场将位于树木表面的骨架压缩至内部，并根据均值法对树木骨架顺滑后得到最终的树木骨架。

1.3 研究内容

本文提出了一种新的具有复杂拓扑结构的树木枝干重建算法^{[3, 4]},大致可分为以下两个步骤:

1. 首先对原始点云进行三角化剖分。采用黎曼流形的思想来描述原始点云数据，根据点云建立单木的坐标卡，利用坐标卡将黎曼流形进行分解，在局部构建黎曼流形和欧式空间之间的映射关系，摒弃了原有的只在在参数空间中运用黎曼流形的思路，并在此基础上生成Delaunay三角网格。该方法可以很好的处理具有亏格以及拓扑结构复杂的树木模型，在运用流行概念解决问题的同时，可以提高算法的处理效率。
2. 构建拉普拉斯加权矩阵。在本文中，我们对现有的基于Laplace微分算子的点云骨架化算法进行了改进，主要是修改了Laplace加权矩阵在迭代收缩过程中基于角度度量的加权值，利用本文提出的基于距离度量的点云势函数来替代原有的基于角度度量的加权。该方法可以很好地规避角度度量带来的误差和不适用性等缺点，从而提升模型重构的准确率和计算效率。

第2章 开发技术介绍

2.1 技术简介

MATLAB是matrix amp; amp；laboratory的组合，意思为矩阵工厂，亦可称为矩阵实验室。它是专门以矩阵的形式处理数据的当今较为流行的科学计算软件。MATLAB是自然科学和工程领域非常著名的一种计算和编程语言,它的应用领域非常广泛，能够解决数值分析、矩阵计算、系统仿真、图像信号处理等方面的计算问题，为科学研究、工程设计等领域提供了一种有效的解决方法，并在一定程度上摒弃了传统的非交互式程序设计语言，它简单高效，相比其他计算机语言(比如说C语言或Fortran语言)，它更接近自然语言，而且它拥有很多预定义函数(接近2000个)和工具箱。给人们提供一个方便的数值计算平台。

2.2 优势特点

1. 具有强大的数值计算和符号计算功能，能让用户在复杂的数学运算分析中得以解脱出来；
2. 能够对图形进行很好处理,对计算的结果、编程的可视化分析；
3. 易于用户接受的界面和接近数学表达式的自然化语言,便于学者理解和掌握；
4. 应用工具箱功能极其丰富,如信号处理工具箱、通信工具箱等；对用户来说，提供了许多既方便又实用的处理工具。

2.3 图形处理

MATLAB从产生出来开始就具备方便的数据可视化功能，能够把向量和矩阵用图形的方式表示出来，而且能对图形标注、打印。二维和三维的可视化、图象处理、动画和表达式作图都属于高层次的作图。能够科学计算和工程绘图。MATLAB不仅起点低、功能强大，而且易学易用。MATLAB可以绘制出你想要的各种二维图形或者三维图形,也可以对图形进行修饰和控制。

2.4 MATLAB语言基础

• 变量、常量
• 字符串类型：每个字符占两个字节。
• 变量默认为double型，包括由64 位双精度浮点数构成的标量或数组。
• 变量默认为double类型，即双精度,正负10^308~-10^308，拥有15 到16 位有效数字,占4个字节。

图2.1 数据类型体系图

2.5 应用方面

MATLAB首先被研究人员和从业人员用于控制工程 ,但迅速传播到许多其他领域。它现在也用于教育,特别是线性代数的教学,数值分析,并且在涉及图像处理的科学家中受到欢迎。

MATLAB 产品能用来做下面各种工作：

• 数值分析
• 数值和符号计算
• 工程与科学绘图
• 控制系统的设计与仿真
• 数字图像处理技术
• 数字信号处理技术
• 通讯系统设计与仿真
• 财务与金融工程
• 管理与调度优化计算（运筹学）

第3章 黎曼流形 Delaunay三角化

基于Delaunay重建方法是三角剖分方法，此方法已经较为成熟，经常被使用而且具有严格的数学理论基础，一般能准确地对物体表面进行重构,但由于计算量过大，对带有噪声和尖锐特征的模型处理有一定局限性，不能取得较为理想的结果。

3.1黎曼流形

3.1.1 概念

通过测量表面上的路径的距离来完全确定表面的曲率，也就是说，曲率不依赖于表面如何嵌入在三维空间中^[5]。伯恩哈德·黎曼将高斯理论扩展到称为歧管的更高维度空间，其方式也允许测量距离和角度，并且可以以多边形内在的方式再次定义曲率的概念，而不依赖于其嵌入更高维的空间。爱因斯坦爱因斯坦利用黎曼多元论的理论来发展他的普遍的相对论。特别地，他的引力方程是空间曲率的约束。

3.1.2 定义

定义1 给定一个有n个数顶点的点云数据,设顶点集合M是该点云数据集合的一个三维拓扑流形A是M 的一个C微分结构,则称是一个三维C微分流形。C微分流形也叫作光滑流形。