基于Crust算法的主枝干三维重建算法开题报告

1. 研究目的与意义

激光扫描获得的是大量物体表面的三维信息，亦称点云数据。利用激光扫描仪获取的点云数据来测量和提取植物生长的几何形态和生理参数并用来构建三维模型，已成为最近10年来的一个研究热点。从三维分布的点云数据进行重建准确的树木三维模型并非易事。激光扫描需要克服一系列的挑战：树枝与树叶的相互遮蔽使树体内部不易被观测到而导致数据缺失；在野外即使微风也会使枝叶摇摆，给获取的数据带来误差和噪音。由于扫描仪自身的特征(光束的发散性)和树木的形态差异，获取的数据通常分布不均(位于扫描仪不同距离、不同部位的目标，其采样间距或点密度不同)和含有噪音或误差。为了克服相互遮蔽现象，通常从不同的视角对树木进行多次扫描，并通过一定的技术实现数据匹配叠加。从多角度扫描获取的每棵树的点云数据可包含数百万个点甚至更多，如何高效地处理这么大数据则对算法提出更高要求。

三维重建过程需要树木的点云数据作为输入，因此点云数据的获取及预处理过程包括利用激光扫描仪从不同方位角度对场景进行扫描，以获得比较完整的树木的枝干表面数据；其后利用高反射率标靶等各种自然或人为的特征点、线或面，将不同站点获取的点云数据进行配准平差，使它们处于统一的坐标体系内；点云的去噪、修补以及简化等预处理都将对数据的质量产生影响。

对常绿和在生长季节的落叶乔木进行数字化扫描获得的点云数据通常包含树枝和树叶的表面信息，而树干三维建模时通常只需要来自于枝干的反射数据，因此需在原始点云中分离出枝干点云和树叶点云，即实施点云数据分割或分类处理。点云的分割可以通过人工手动或经由计算机算法自动进行。点云分割的另一种释义是数据的简化，即只选择其中关键的部分数据进行分析处理。

2. 国内外研究现状分析

从点云数据中提取骨架的绝大多数算法都有利用点的邻域信息，骨架是每个邻域里点集的中心的集合。目前，从树枝点云中提取骨架或点云骨架化的主要算法可归纳为基于水平集的方法、基于聚类的方法和基于图论的方法、基于拉普拉斯算子的方法。

verroust 等(2000)较早提出了从三维点数据中利用水平集提取骨架曲线的方法。首先，对每个点找到它的k 个最近邻点，连接这些近邻点形成一个邻域图。接着，根据每个点到用户设定的根节点距离(称之为测地距离，geodesicdistance)，用最短路径算法计算出它的最新生成树图。具有相同测地距离值的点构成了水平集，而连接邻近水平集的中心点即可得到点云的初步骨架。该方法的基本要求是相对于物体的宽度，其表面的三维采样点的密度足够大或样点间的距离足够小。对于远端末梢的细枝，其样点密度目前还达不到要求，因此树木细枝的虚拟模型还需要补充添加到骨架上使其更完整真实。cot 等(2009; 2011)采用了该方法，数据是从3个以上的视角对针叶木扫描得到的。delagrange等(2011)将点云在垂直方向上以1 cm 的间隔进行水平切片，找出每一层数据点构成的一个或多个多边形及其中心点，然后由底向上通过最小生成树将这些中心点连接构成骨架。显然，该方法难以准确处理枝条出现水平生长的树木。

xu 等(2007)开展了基于聚类方法的开创性工作。作者首先找出每个点的欧式近邻并构造邻域图，把点根据图的邻近关系以及各点到根节点的最短距离进行聚类，连接相邻类的中心点便得出树枝骨架。这类方法中，根节点的选择会对提取的骨架有影响，而且骨架图里可能会包含回线( loop)。这种情况可用最小生成树或最短路径等图论方法加以解决。yan 等(2009)考虑到树木的枝干外形多为圆柱形，因此把点云分解为互相连接的类组，每一类组的点可紧密地定义一圆柱的外形。若各点到与其拟合的圆柱形的均方差大于某一阈值，则表明可能有分叉存在，需要将类组继续分解，再进行一次圆柱拟合检验。通过联合k － 均值聚类和圆柱体拟合检验，得到各圆柱体分区域以及分支点，最后依据邻域图的规则连接各类组的中心点便得到树枝骨架。

3. 研究的基本内容与计划

研究内容：

1、学习matlab编程，计算机图形学和数字图像处理的基础知识与应用；

2、查阅相关资料，了解三维点云树木重建的研究现状，完成文献综述与开题报告；

4. 研究创新点

通过选取合适的方法从激光扫描获得的点云数据中提取树木枝干的骨架，重建三维树木的主枝干。