Paper Reading: (2014) Highly Accurate Tree Models Derived from Terrestrial Laser Scan Data: A Method Description

Original paper: Hackenberg, Jan, et al. “Highly accurate tree models derived from terrestrial laser scan data: A method description.” Forests 5.5 (2014): 1069-1105. https://doi.org/10.3390/f5051069

This is a record of the reading process, aimed at personal learning, reading and writing practicing.

• Abstract
• 1 Introduction
  • 1.1 Related Work
• 2 Rationale
• 3 Materials and Methods
  • 3.1 Terrestrial Laser Scanner
  • 3.2 Description of the Scanning Campaign
  • 3.3 Artificial Point Cloud
  • 3.4 Software
• 4 Method Description
  • 4.1 De-Noising
  • 4.2 Referencing
  • 4.3 Cylinder Model Creation
  • 4.3.1 Cylinder Detection with the Usage of a Sphere (Refer to Figures 2(a)–2(c))
  • 4.3.2 Initialization and Termination of the Method; the Usage of FIFO-Queues F1 and F2 to Follow the Stem and Branches According to Their Order ( Refer to Figures 2(d)–2(g))
  • 4.3.3 Post-Processing Steps (Refer to Figure 2(i))
  • 4.3.3.1 Hierarchical Tree-Like Data Structure
  • 4.3.3.2 Improvement of Branch Junctions
  • 4.3.3.3 Improvement of Fit Quality
  • 4.3.3.4 Extraction of Tree Parameters
  • 4.4 Implemented Search Structure
  • 4.5 Imperfect Point Clouds
  • 4.6 Circle Fitting
  • 4.7 Cylinder Fitting
• Appendix
  • A Clustering
  • B Least Squares Fit for Cylinders and Circles

Abstract

• This paper presents a method for fitting cylinders into a point cloud, derived from a terrestrial laser-scanned tree.
  • Utilizing high scan quality data as the input, the resulting models describe the branching structure of the tree, capable of detecting branches with a diameter smaller than a centimeter.
  • The cylinders are stored as a hierarchical[adj. 分层的] tree-like data structure encapsulating[v. 封装] parent-child neighbor relations and incorporating[v. 体现] the tree’s direction of growth.
• Tree models were accomplished representing more than 99% of the input point cloud, with an average distance from the cylinder model to the point cloud within sub-millimeter accuracy.

1 Introduction

1.1 Related Work

• Some related works

2 Rationale

• This paper presents the development of a fully automated method for fitting cylinders into a manually pre-processed point cloud obtained using TLS tree data under leaf-off conditions.
• The objective of the methodology is the derivation of gapless tree models, including the remaining branching structure, stored in a hierarchical tree-like data structure.
• Since the NLS-based method [8] provides a high accuracy, but a low level of robustness, we also implemented a second method that is less accurate, but more robust. By comparing the results of two methods, cylinders fitted incorrectly by the NLS method are detected and replaced automatically with cylinders fitted using the robust method.

3 Materials and Methods

3.1 Terrestrial Laser Scanner

3.2 Description of the Scanning Campaign

3.3 Artificial Point Cloud

3.4 Software

• The preprocessing of scan data was performed with the Z+F LaserControl software [41].
• Multiple scans were co-registered with the help of calibration targets into one common coordinate system, and a mixed pixel filter was applied to delete scan points that provided multiple returns.
• In the final step, the individual trees were extracted manually from the surrounding point cloud, and then, these points were exported in an ASCII file format.

• Some thing about calibration.

4 Method Description

4.1 De-Noising

4.2 Referencing

4.3 Cylinder Model Creation

4.3.1 Cylinder Detection with the Usage of a Sphere (Refer to Figures 2(a)–2(c))

• The principal idea of cutting sphere surfaces with tree point clouds [33] is utilized.

• [33] Jayaratna, S. Baumrekonstruktion aus 3D-Punktwolken. Diploma Thesis, Institut f¨ur Informatik, Rheinische Friedrich-Wilhelms-Universit¨at Bonn, Bonn, Germany, 2009.

• 首先，假设有一个球体 s，其球心 sc 大致位于树的骨架上，并且球的半径 r 大于 sc 周围横截面的直径。然后，定义一个点集 P，其中包含了球面周围距离 sc 不超过 r 的所有点，这些点代表了距离 sc 处的所有横截面的点。即使在树的分支节点处，如果球 s 足够大，横截面也会出现空间上的不连通。因此，将点集 P 分割成若干子集 Pi，每个子集 Pi 代表一个横截面。由于树干和树枝的横截面可以近似为圆形，所以可以为每个子集 Pi 拟合一个圆 ci，其中圆心为 cci，半径为 cri。接着，根据一个半径的下限，生成新的球体 si，其圆心为 cci，半径为 cri 乘以一个大于 1 的系数 x。此外，还会将以 sc 为起点、cci 为终点、半径为 cri 的圆柱存储在列表中，可以选择设置圆柱半径的阈值。这个过程对于所有的球体 si 都会重复进行。为了避免算法来回跳跃，一旦检测到子球体 si，就会从输入点云中删除所有位于球 s 内部的点。

4.3.2 Initialization and Termination of the Method; the Usage of FIFO-Queues F1 and F2 to Follow the Stem and Branches According to Their Order ( Refer to Figures 2(d)–2(g))

• 由于该方法的递归实现会导致相邻分支之间出现不期望的连接，因此使用两个先进先出（FIFO）队列来存储尚未处理的球体。FIFO队列 F1 初始化为位于茎基部的一个球体。
• 由于去噪过程确保点云中不包含其他树木或地面工件的区段，所以在最小 z 坐标高度处的薄片仅包含目标树干的横截面区域。
• 在该薄片中拟合一个圆并将其转换为球体，然后将其存储在 F1 中。如果在处理过程中检测到多个子球体，则始终先处理最大的子球体。
• 将 n - 1 个较小的子球体存储在另一个 FIFO 队列 F2 中，直到不再检测到沿着跟随的分支或茎的横截面区域（即，主分支或茎已被处理到其顶端）。
• 对所有依次存储在 F1 中的球体重复此过程。当 F1 为空时，将 F2 中包含的所有球体转移到 F1。在此时可以调整最多五个阈值，即两个聚类参数（参见附录 A）、最小球体大小、最小圆柱半径和球体表面的邻域大小。调整的原因是预期处理的分支顺序发生变化。第 n + 1 阶段的分支直径小于其 n 阶段的前体。同时，在顺序更改后，分支的频率变得更高，导致邻域更密集。
• 算法 1 中的循环在当前处理的球体达到终点且 F1 和 F2 为空时终止。终止是确保的，因为在每个子球体生成期间，从输入点云中删除点，而点的数量是有限的。如果扫描质量足够高，即使用非常高分辨率并且具有足够的扫描位置以防止遮挡效果的扫描，则输出将包括覆盖完整树木的圆柱列表。否则，分支的跟踪路径可能会结束在遮挡间隙中，或者表示横截面区域的点数可能太低无法拟合圆，从而难以追踪受影响分支至其顶端。

4.3.3 Post-Processing Steps (Refer to Figure 2(i))

4.3.3.1 Hierarchical Tree-Like Data Structure

• 在生成的列表中，有一个约束保持不变：每个圆柱的起点（除了列表中的第一个圆柱之外）构成了前一个圆柱的终点。这个约束允许构建一个简单的树形数据结构。

• 列表中的第一个圆柱被添加到树结构中并设置为根节点。之后，进行递归搜索，寻找起点等于前一个添加的圆柱的终点的圆柱。这样的圆柱被添加到树中，并在父节点和子节点之间建立链接。递归结束后，所有圆柱都已被添加到树结构中。

• 对于接下来的一些操作，需要将圆柱分配到两个相邻分支节点之间的共同段中。树结构可以有效地检测到这些段。第一个段从根节点开始。沿着树向上移动，所有只有一个或零个子节点的节点都被分配到该段，直到找到至少有两个子节点的节点为止。这是分配给该段的最后一个节点。所有子节点成为新段的起始节点。所有只包含一个圆柱且与任何子圆柱无关的段都从树结构中移除，因为这些段很可能是错误检测到的圆柱。

4.3.3.2 Improvement of Branch Junctions

• 结果的可视化显示，每个段的第一个圆柱往往与其周围的点不一致。虽然半径和端点被很好地近似，但起点可能被错误分配。这可能归因于在算法1中，球体的中心位于树骨架上，但不一定位于骨架线分成两条或更多骨架线的点上。对于这些圆柱，根据以下公式计算一个新的起点 sp，其中 ep 是圆柱的终点，l 是其长度，d 是段中下一个圆柱的归一化方向向量：

• 圆柱的长度与茎或分支截面的直径成比例。因此，进行合并操作以延长和减少圆柱的数量，从而可以将更多的点分配给单个圆柱。只有属于同一段的圆柱才会被合并。最多将三个圆柱合并为一个圆柱；合并后的圆柱的半径由原始圆柱的中位半径计算得出。

4.3.3.3 Improvement of Fit Quality

• 在接下来的步骤中，将更新后的圆柱分配给 TLS（地面激光扫描）点数据。圆柱的半径被临时放大，然后将位于放大圆柱内部的点分配给该圆柱。分配的点以及未放大的圆柱被用作改进圆柱拟合的输入数据。

4.3.3.4 Extraction of Tree Parameters

• 对树模型进行后处理，以丰富其中包含的信息。主要包括以下几个步骤：

• 茎柱确定： 首先，利用树结构确定茎柱。通过计算从叶节点到根节点的路径长度，识别沿着最长路径的茎柱。如果自动化过程失败，可以通过可视化检查手动选择叶柱状物。

• 分支提取： 对于所有不包含其他茎柱的茎柱的子节点，将其作为分支的起始节点。从以起始节点为根节点的子树中提取所有属于一个茎柱的分支。

• 冠底确定： 通过沿着从树底开始的茎进行搜索，确定冠底。搜索终止于第一个分支，其分支 branch collar 直径和长度达到预定义的最小阈值。由于阈值可能随着树龄和树种的不同而变化，因此无法找到通用阈值。如果自动化失败，用户可以手动确定分支基底。

• 冠的确定： 将冠底柱状物作为根节点，确定包含在其子树中的所有柱体作为冠的一部分。提取柱体端点作为冠建模的输入数据。

• 凸包计算： 使用 Chand 等人提出的 “gift-wrapping” 算法确定3D凸包[48]。该算法简单易用，适用于较小规模的输入数据。在此过程中，将输入点投影到二维平面，并计算冠投影的面积。

• Chand, Donald R., and Sham S. Kapur. “An algorithm for convex polytopes.” Journal of the ACM (JACM) 17.1 (1970): 78-86. PDF

• 最终的树模型允许提取出各种参数，这些参数在文本的表3中列出。

• Not totally understand.

4.4 Implemented Search Structure

• 在理论上可以通过暴力搜索来运行某种方法的所有实现。但是，随着输入数据大小的增加，达到最多 2000 万个数据点，时间复杂度达到 O(n^2) 或更高是不切实际的。因此，为了更高效地处理大规模数据，在 3D 数据中通常会使用 kD 树或八叉树。实现的搜索结构需要提供两个时间有效的操作：返回所有包含在球体内的点（通常称为范围搜索）和删除所有包含在球体内的点。
• 虽然二叉树（如 kD 树）可以保证基本操作（例如查找最近邻居或删除点）的时间复杂度为 O(log(n))，但三维数据的范围搜索的复杂度为 O(n^(2/3))（对于平衡树）和 O(n)（对于不平衡版本）。为了始终保证 O(n^(2/3))，删除操作需要耗费时间进行重新平衡。
• 而在八叉树中，范围搜索的最坏情况时间复杂度始终为 O(n)，但预期运行时间是次线性的；尽管在运行时间复杂度方面不如 kD 树高效，但八叉树提供了其他优势。它可以包含除了点之外的其他几何对象（例如柱体），并且删除对象从不需要重新平衡。在八叉树中，检测八叉树单元格是否与球体相交是直接的，这使得能够有效地搜索位于柱体内的点，因为它们大致由其边界球体表示。

4.5 Imperfect Point Clouds

• 在算法1中未使用的点：

  • 在八叉树中保留的所有点都会被聚类（参见附录A）；非常小的聚类将被删除。对于每个聚类，将再次应用所描述的方法，从而为每个聚类生成一个柱体列表。

  • 假设c是这种列表中的第一个柱体。执行搜索以找到一个柱体c’，以连接到c的起始点。确定起始点sp到主列表中所有柱体端点epi之间的距离di。令ep’为具有最小距离的端点；然后选择具有端点ep’的柱体作为c’。

  • 生成一个新的柱体，假定填充遮挡间隙的体积，以ep’作为起始点，sp作为端点，以c的半径作为半径。必须在构建树结构之前执行此过程，以包括新检测到的柱体。

• Not totally understand.

4.6 Circle Fitting

• 已经实现了三种不同的方法（最小二乘拟合、平面拟合和中值拟合）来将一个圆 c(x0, y0, r) 拟合到 TLS 点的子集 P 中，这些点表示树枝或茎的横截面区域。

• 圆 c 可以通过最小二乘方法拟合到包含 n ≥ 3 个点 pi(xi, yi) ∈ R2 的集合中。在将 P 转换为 R2 后，应用高斯-牛顿算法 [53]。有关实现细节，请参阅附录 B.2。

• 第二种方法由 Jayaranata 提出 [33]。将一个平面 Pl 拟合到 P 中（参见附录 C），并计算交点，即所需的圆 c，该圆位于 Pl 和用于算法 1 中的球 s 之间。圆 c 的中心点 cc(x0, y0) 是球心 sc 在平面上的正交投影。利用 sc 和 cc 之间的距离 d，以及球半径 sr，我们可以应用方程 (8) 来计算圆的半径 cr：

• 第三种方法很简单，使用 P 的质心作为中心点 cc(x0, y0)，并将所有分配点到 cc 的中位距离作为半径 cr。

4.7 Cylinder Fitting

在代表树枝或茎截面的至少包含 n ≥ 5 个 TLS 点云的子集 P 中，可以利用最小二乘法拟合出一个圆柱 c(x0, y0, z0, a, b, c, r) [8]；其中，p0(x0, y0, z0) 是轴上的一个点，d a = (a, b, c)T 是轴的方向向量，r 是圆柱的半径。所应用的高斯-牛顿算法 [53] 的实现细节见附录 B.1。

利用最小二乘法拟合圆柱有时会导致拟合错误。已拟合圆柱的可视化显示： • 拟合错误的圆柱通常位于代表非常小的树枝或覆盖点较少的区域中； • 在每次拟合迭代中，圆柱的直径迅速增长。

每当初始圆柱半径小于某个阈值或分配点数量太少时，都会应用另一种圆柱拟合方法。当最小二乘拟合的圆柱直径远大于初始参数时也是如此。

第二种方法（分位数方法）很简单。在假设圆柱轴已经很好地拟合的前提下，唯一需要改进的参数是半径。对于每个分配点，计算到圆柱轴的距离 di。根据所有 di 的一个分位数来更新圆柱半径（详见第 5.1 节中的分位数调整过程）。

TLS 点云与圆柱模型之间的距离 dij 定义如附录 B.1 中方程 (A4) 中的距离 di，如果点 pi 在圆柱轴上的投影 p∗i 位于圆柱的起始点 cs 和结束点 ce 之间。否则，我们定义 d∗i 如方程 (9) 所示：

并应用方程 (10)：

其中 di 定义如方程 (A4) 中的距离。pi 和模型中每个圆柱之间所有可能距离的最小值是 pi 和圆柱模型之间的距离。假设 n 是输入点的数量，n∗ 是距离模型小于 3 厘米的点的数量，我们定义模型的覆盖率（用于衡量拟合的完整性）如方程 (11) 所示：

此外，我们对距离直方图中与圆柱模型的 n∗ 个最近点进行正态分布拟合，以获得不同的拟合质量度量，即原始距离数据的标准偏差 sd 和平均值 x，以及拟合后的正态分布的标准偏差 σ 和平均值 μ。

使用 3 厘米作为覆盖接受的阈值是合理的，因为 Group II 树木和圆形的茎形式有很大偏差。尽管这个相对较高的值会错误地以积极的方式提高覆盖率值，但所有四个拟合质量参数，即 sd、x、σ 和 μ，都受到负面影响，并呈递增趋势。Group III 模型的平均标准偏差为 3.82 毫米（参见图 3），这表明被认为由圆柱拟合的点数据中有 99.73% 落入 1.14 厘米的范围内。

Appendix

A Clustering

• Density-based spatial clustering of applications with noise (DBSCAN) is an efficient way to cluster spatial data.
• The algorithm is deterministic in calculating the number of clusters and also in the determination of core and noise points. The allocation of density-reachable points to a cluster is non-deterministic.
• Pseudo code and a detailed description are available [57].

• Algorithm: Density-based spatial clustering of applications with noise (DBSCAN)
• [57] Ester, Martin, et al. “A density-based algorithm for discovering clusters in large spatial databases with noise.” kdd. Vol. 96. No. 34. 1996. PDF

B Least Squares Fit for Cylinders and Circles