基于细分的树干三维表面重建算法_尤磊.pdf

：文章编号：（）基于细分的树干三维表面重建算法尤磊，艾新程，冯岩，苏晓珂（信阳师范学院 计算机与信息技术学院，河南 信阳 ；郑州轻工业大学 计算机与通信工程学院，河南 郑州 ）摘要：为提高树干三维表面模型重建精度，使其能更有效反映树干表面特征，提出基于细分的树干三维表面重建算法。根据给定分段高度，对树干点云垂直分段；在计算每个分段质心的基础上，根据给定角度参数将每个垂直分段划分为若干角度分区，并得到角度分区中心点点集；以该点集为输入，使用基于切平面投影的树干三维表面重建算法，得到粗粒度树干表面模型；分别在改进 细分算法和 细分算法的基础上，对粗粒度表面模型细分得到细粒度表面模型。实验结果表明，改进 细分算法和改进 细分算法重建的树干表面模型，更能有效反映树干表面的凹凸不平特征；改进 细分算法比改进 细分算法重建的树干表面模型具有更小的 距离。改进算法构建的树干表面模型能有效反映树干表面不规则的几何特征，构建模型更精确；实际应用中应优先使用改进 细分方法重建树干表面模型。关键词：树干；点云；细分；树干模型；表面重建中图分类号：文献标识码：开放科学（资源服务）标识码（）：o o o o ，o （，；，）：，；，o ：；引言随着计算机图形学以及激光扫描技术的快速发展，使用三维激光扫描技术获取数据，进而构建植物三维模型是近些年林业科学和计算机视觉领域研究的热点。由于树木种类多、拓扑结构复杂，收稿日期：；修订日期：；通信联系人，：；基金项目：国家自然科学基金项目（）；河南省高等学校青年骨干教师培养计划（）；信阳师范学院“南湖学者奖励计划”青年项目；信阳师范学院研究生科研创新基金项目（）作者简介：尤磊（），男，河南罗山人，副教授，博士，主要从事计算机图形学与三维点云分析与应用研究。信阳师范学院学报（自然科学版）第 卷第期 年月 构建高效精确、真实性强的树木的三维模型是一个极具挑战性的工作。等通过提取树木枝干参数，提出沿树木枝干方向自动跟踪匹配拟合圆柱体构建树木模型的方法。等采用 样条曲线拟合构建树枝和树干横断面模型。等首先对原始点云数据进行过滤，然后拟合茎干模型，重建树干三维表面。等将树木形态学的方法 应 用 于 树 木 三 维 表 面 重 建 中。等通过分段拟合圆柱体，构建树木三维空间中的几何拓扑结构。高士增等基于凸包算法拟合树木高度不同位置的等值线，采用生长算法在相邻等值线间生成树木表面模型。尤磊等在切平面投影算法的基础上，将三维空间中的树干点云投影至二维平面进行构网计算，再将平面点集构建的三角网映射到三维空间实现树干的表面重建；尤磊等在三维空间中将树干点云分为多个连续重建单元，将重建单元以圆柱面为投影面投影二维平面构网，由平面点集的连接关系构建树干的三维表面模型。唐丽玉等 以 软件为基础，采用多种算法分离枝干与树叶，分别提取枝干骨架点与冠层特征点，根据上述点集构建树木的三维网格模型。裴魏魏等 在三次样条算法的基础上，采用节点插值的方法，设计一种树干的三维表面重建算法。杨玉泽等 以局部凸包连接算法对枝干和树叶点云进行分割，以基于贪婪投影三角化算法对枝干和树叶点云重建三维表面。上述基于圆柱体的方法无法反映树干表面的不规则特征，基于凸包的方法可以反映树干凸起部位的特征，但会弱化凹陷区域的特征。将原始树干点云投影至二维平面构网的方法，会导致树干表面模型存在空洞或相交现象。以提取树干特征点或节点插值方式构建的表面模型与原始表面间存在一定程度的误差，无法真实反映树干表面的几何特征。网格细分是以一个初始网格模型作为输入数据，根据规定细分法则，经过迭代细化，构建顶点更加密集的网格模型且其构建的表面也变得更加平滑。其理想特性（如局部可控性、全局连续性等）使得网格细分已广泛涉及于计算机图形学和曲面模型构建等许多领域。目前，网格细分方法分为两种：插值型细分和逼近型细分。典型的插值型细分是把旧顶点与新顶点始终保留在每次细分后的网格中，最经典的插值型算法是 细分 及其改进算法，其极限曲面精确地包含所有初始顶点。经典逼近型细分算法包括 细分、细 分、细 分 以 及 细分。其中三角形网格细分多使用 细分 和 细 分，而 、细分则普遍用于四边形网格细分中。本文选取逼近型 细分算法与 细分算法作为经典算法，并以此为基础，进行构建树干表面更加精细的三角网格的研究。在尤磊等、等 与 等 的基础上，本文采用基于切平面投影的表面重建算法、细分算法或 细分算法，提出一种基于细分的树干三维表面重建算法。该算法使用尤磊等 文献中树干点云垂直分段、角度分区的方法得到角度分区的中心点点集，之后采用如下策略：首先，利用切平面投影的树干三维表面重建算法对角度分区的中心点集表面重建，得到粗粒度的树干表面模型；然后分别采用如下改进方法：（）计算每个三角面片边的中心点，对此中心点搜索树干点云中最近的树干点，得到树干点点集，以此树干点点集作为细分节点，采用 细分算法对粗粒度模型细分得到细粒度的树干表面模型；（）计算每个粗粒度模型三角面片的重心点，对重心点搜索树干点云中最近的树干点，得到树干点点集，以此树干点点集作为细分节点，采用 细分算法对粗粒度模型细分，得到细粒度的树干表面模型。由于 细分算法和 细分算法多是面向三角形的网格细分，如果没有特别指明，重建的树干表面模型是指不规则的三角网格模型。表面重建算法相关定义（）粗粒度表面模型。采用三维表面重建算法对树干点云数据进行表面重建，所构建的初始树干表面模型称为粗粒度的网格模型。（）细粒度表面模型。采用细分算法对粗粒度表面模型进行细分，得到的三角形网格称为细粒度的网格模型。算法主要步骤及其相关计算图是基于点云数据的树干三维表面重建算法流程。对于输入的树木点云，点的坐标为（，），树木点云的第个分段用表示，是分段的第个角度分区的中心点，树干点云中所有角度分区的中心点点集表示为，（表示所有角度尤磊，艾新程，冯岩，等 基于细分的树干三维表面重建算法分区中心点的总个数）。是粗粒度树干表面模型，是细粒度树干表面模型。算法的主要步骤如下：在树干点云垂直分段的基础上，对每一个分段点云进行角度分区（点云垂直分段、角度分区的计算过程见节）；根据每一个角度分区中的点云计算角度分区的中心点，得到角度分区的中心点点集（角度分区计算过程见节）；以角度分区中心点点集为数据进行粗粒度的表面重建算法（粗粒度的表面重建计算过程见 节），得 到 粗 粒 度 的 树 干 表 面 模 型 ；对粗粒度树干表面模型 采用改进 细分算法和改进 细分算法，分别进行细粒度的表面重建（细粒度的表面重建计算过程 见节），得 到 细 粒 度 的 树 干 表 面 模 型 。图算法流程 o o o 树干点云垂直分段及角度分区的计算计算树干点云垂直分段及角度分区，采用尤磊等 基于切平面分割的树干点云提取算法中的方法：根据树木点云在轴的最大值、最小值及给定分段的高度值，计算分段个数，得到每个树木点云分段的范围；得到分段之后，对每个分段角度分区。关于角度分区中心点的计算角度分区的中心点是根据树干点云数据提取的点。在角度分区的基础上，对每一个角度分区计算重心点作为角度分区的中心点。对于 段角度分区的点云，点的坐标为（，），的中心点为，的计算公式如式（）所示：，（，）。（）同理即可得到所有角度分区中心点的点集。.粗粒度的表面重建算法粗粒度重建表面模型的计算以树干点云中角度分区的中心点为基础进行逐点计算。采用尤磊等基于切平面投影的树干三维表面重建算法中的方法：首先，以半径值为参数，计算角度分区中心点的三维邻域点集；接着，以上述点集为数据构建过点的切平面，将此切平面投影至二维平面，在二维平面构建 三角网；最后，将点与其 近邻点的连接关系映射到树干点云上，从而完成对点的表面重建。对所有角度分区中心点计算树干粗粒度表面模型，得到在三维空间的粗粒度树干表面模型。.细粒度的表面重建算法由于树木表面的形状复杂，存在凹陷等凹凸不平的表面特征。为了更加清晰地描述树干的表面特征，在构建粗粒度表面模型的基础上分别采用：（）改进 细分算法，即对于 细分算法提出利用三角面片中每个边的中心点作为新的细分节点构网，使用 树的 近邻搜索方法，搜索粗粒度模型三角面片中每个边的中心点所对应的最近的树干点云，对此树干点点集采用 细分算法进行 构 网；（）改 进 细 分 算 法，即 对 于 细分算法提出利用三角形的重心点作为新的细分节点构网，使用 树的 近邻搜索的方法，搜索重心点所对应的最近的树干点，对此树干点作为新的节点采用 细分算法进行构网。改进 细分算法步骤如下：输入树干点云，粗粒度的三角网格模型 。输出表 示 树 干 的 细 粒 度 的 三 角 网 格 模 型 。对树干点云建立 树，对于个粗粒度表面模型三角面片 ，首先计算此三角面片的个边的中心点；将搜索点设置为个边的中心点，分别对树干点云进行 树的近邻搜索，得到中心点所对应的最近的个树干点；对于平面 ，将上述个树干点使用 细分的方法进行细分操作。对所有的粗粒度表面模型三角面片，采用上述方法构建新的三角网格，得到细粒度的表面模型 。改进 细分算法步骤如下：输入 树干点云，粗粒度的三角网格模型 。输出 表 示 树 干 的 细 粒 度 的 三 角 网 格 模 型 。对树干点云建立 树，计算粗粒度表面模型三角面片 的重心点；第 卷第期信阳师范学院学报（自然科学版）：年月 将搜索点设置为三角面片 重心点，进行 树的近邻搜索，得到重心点对应的最近的树干点；对于平面 ，将上述树干点采用 细分的方法进行细分操作。对所有的粗粒度表面模型三角面片采用上述方法构建新的三角网格，得到细粒度的表面重建模型 。实验在型号 、内存 、处理器 的笔记本电脑上，采用 开发环境，使用 点云库及 开发环境中点云数据处理相关类开发测试程序，从室外环境扫描的树木点云中提取树干点云作为试验数据集。使用 地面三维激光扫描仪多次扫描获取的树木点云为实验数据。使用 软件对扫描点云进行配准，然后移除地表及树枝点云后得到树干点云。设备扫描时可能受到风扰产生噪声，考虑点云配准等因素，需要对树干点云数据进行预处理，这是作为点云表面重建的基础环节之一。树干模型重建过程容易受到树枝叶等元素的影响，还需要对树干进行削枝操作，提取树干点云。本文中，如不做特别说明，选取的树干点云是指点云较为密集的树干部分。与经典算法的对比试验分析将 等 与 等 描述的经典细分算法与改进 细分算法、改进 细分算法进行对比分析。以个树干点云进行细粒度重建，重建可视化效果分别如图图所示。图编号为 的树干点云部分重建结果 o o o o o o 树干点云数据分别临时编号为 。树干点云原始数据为截取部分长度前的数据，为方便介绍，截取了部分树干点云重建后的效果作为细粒度表面重建的展示。图编号为 的树干点云部分重建结果 o o o o o o 图编号为 的树干点云部分重建结果 o o o o o o 图编号为 的树干点云部分重建结果 o o o o o o 图编号为 的树干点云部分重建结果 o o o o o o 尤磊，艾新程，冯岩，等 基于细分的树干三维表面重建算法图编号为 的树干点云部分重建结果 o o o o o o 从表面重建效果来看，本文改进 细分算法和 细分算法得到的树干细粒度表面模型具有凹凸不平的表面特征。而 细分算法和 细分算法得到的树干细粒度表面模型过于平滑，不能有效展示树干表面的凹凸不平特征。重建表面的评价给定欧式空间中的两点集，则与两点集之间的 距离定义公式如下：（，）（，），（，），其中：（，），（，）。函数（，）称为与两点集之间的双向 距离，函数（，）和（，）分别表示前向和后向 距离。采用树干点云到细粒度表面模型的距离，作为重建表面模型是否更贴近于树干真实表面的评价依据。采用经典 细分算法、经典 细分算法、改进 细分算法和改进 细分算法重建树干细粒度表面模型并计算 距离值（分别记为、），如表所示。从表可以看出，在经典细分算法中，细分算法的 距离值较小，说明 细分算法重建的树干表面较为精确。在改进细分算法中，改进 细分算法与树干真实表面差距最小，说明改进