1、第 卷 第 期 年 月测绘与空间地理信息 ,收稿日期:基金项目:国家自然科学基金()资助作者简介:王 康(),男,安徽肥西人,测绘工程专业硕士研究生,主要研究方向为点云数据处理。基于点云三维重建的参数敏感性分析王 康(福州大学 数字中国研究院(福建),福建 福州)摘要:随着三维激光扫描技术的不断发展,基于点云的曲面重建技术被广泛应用于城市规划与管理、虚拟旅游、环境模拟等领域。目前经典的曲面重建算法在高精度与高效率之间并不能两全,针对不同的数据特征,应选择不同的重建算法。本文通过比较泊松曲面重建、贪婪三角曲面重建算法,探讨在不同参数阈值下对重建算法的选择。实验表明,泊松重建算法重建精度更高,但其
2、用于间距较大的点云数据建模精度较差,其重建效率较低。贪婪三角投影重建算法的重建效率较高,对于形态简单的数据重建精度高,但对于复杂形态数据的重建精度较差,难以重建精确表面模型。关键词:点云数据;贪婪三角投影重建;泊松曲面重建;参数敏感性分析中图分类号:文献标识码:文章编号:()(,(),):,:;引 言随着数字化的深入发展,以及人们对虚拟现实、游戏等需求的日益增长,基于传统倾斜影像构建的三维模型精度已经远远无法满足应用市场的需求,高精度、高效率的建模数据逐渐受到人们的重视。与传统基于倾斜影像的建模不同,基于点云数据的三维模型因其精度、效率更高,可根据不同的市场需求,能够实现多样的三维重建模型,因
3、此在计算机仿真、设备自主导航、工业控制等领域得到了广泛应用。基于点云数据的曲面重建是针对点集使用插值或曲面逼近的方式,构建三维空间采样点的正确几何拓扑关系,获取与真实物体表面拓扑相似的网络模型。目前,主流的点云重建方法依据建模方式可分为多边形网格法、参数曲面重建法及隐函数法。多边形网格曲面重建算法中以三角剖分应用最为广泛。等首次提出三维 三角化。在此基础上,等实现了二维空间 图及 三角化,该算法对闭合点云重建曲面精细度高,但该算法对采样密度具有较高的要求;张明军等基于 库实现了 点云三角面片重建,使其能够适应不同密度的点云曲面重建。多边形网格曲面重建算法复杂度高,对点云数据量有一定要求,难以应
4、对多噪声数据的建模。参数建模基本思想是通过给定函数,将二维参数域映射到三维空间,求取曲面方程参数,逼近原始曲面,达到曲面重建的效果。等基于改进 样条进行曲面重建,取得了较好的效果;之后,等提出利用局部约束进行 样条表示曲面,并利用最小二乘实现曲面平滑。参数曲面重建中局部分片使得重建曲面光滑性差。为构建光滑性曲面,等提出隐函数曲面重建,基本思想是通过三维标量场函数零水平集表示模型,能够构建任意拓扑结构的曲面重建技术,为隐函数曲面重建技术奠定了基础;等提出泊松曲面重建,通过分层局部基函数控制曲面方程,将曲面重建问题转化为泊松问题,利用离散化的方法求取曲面隐函数。伴随着数字化进程的深入,结合重建算法
5、精度、重建效率等多方面问题进行改进等研究成为一个必然的发展方向。但目前针对重建算法的参数敏感性分析仍较为缺乏。因此,本文选择点云重建算法中最经典的泊松重建、贪婪三角投影重建算法,在不同的参数阈值下,进行重建对比试验,以期得到 种算法在不同参数阈值下的重建精度和效率的差异,并根据分析结果,为点云重建的算法选择以及后续改进优化提供依据。重建算法原理介绍 泊松曲面重建泊松曲面重建为隐式函数的网格重建算法,其原理是将曲面重建的问题转换为求解泊松方程问题,进而求解曲面指示函数,最后通过提取等值面得到曲面模型。具体步骤如下:)数据离散化泊松曲面重建的关键是确定模型表面的隐函数。采用八叉树表示数据,进而转化
6、为求解泊松方程。基于点云构建八叉树,树深度为,令数据处于八叉树的节点 之上,在节点 上添加函数,函数 为可旋转、平移的基函数,进而求解基函数。|()式中:为节点 的中心;为节点 的宽度。)创建向量场其次将点云均匀划分为块区,求解向量场 指示函数梯度。引入基函数 来描述节点函数 和向量场 的关系:()|()将重建问题转换为高维泊松问题是曲面重建的关键,其函数表示如式():(,)()()()()式中:表示卷积符号,表示有 个相同的函数进行卷积操作,子项()定义如式():()()对点云的 个邻近节点线性插值,用()表示结点 个邻近节点,用,表示插值的权重,最后利用指示函数代表的表面梯度向量场近似估计
7、模型表面。()(),()()式中,为点云数据集合;是点集中任一点 的 邻域点;()为节点 的 邻域范围内深度为 的 个节点;是 的顶点法向量。)求解泊松方程利用梯度向量场求解泊松方程,得到等值面。采用拉普拉斯变换矩阵求出方程解。其中,泊松方程 求解即转化为求解最小函数:,()对于给定的 维向量,节点 的坐标为 ,函数的求解通过函数在函数空间投影的拉普拉斯算 子 与 构 成的 向 量 逼 近 解 决,即 转 换 成 ,最后求解 。)提取等值面为得到重构表面,设置等值面提取阈值,通过估计采样点 的位置,然后采用平均值提取等值面,最终得到曲面模型。贪婪三角投影重建贪婪三角投影算法是迭代生长的曲面重建
8、算法,将空间中的点及邻域内的点投影到该点到该点的切平面上进行局部二维三角剖分,从而得到各点的连接关系。首先随机选取一个种子点与邻域内最近的 个点,在种子点与邻域点确定初始三角形,从 个近邻点选择与生长边夹角余弦值最小的点加入到三角网中,三角网不断增长,根据投影点的拓扑关系确定各点在三维空间中的拓扑结构,最后形成完整的曲面模型。具体流程如下:)首先构建 索引,获取种子点及周围邻域点的信息;)根据种子点和其邻域点获得生长边的投影面,将种子点及 个邻域点投影到二维平面上三角化;)选择二维平面的种子点以及其生长边所构成的法线夹角余弦值最小的点作为扩展点;)将)中确定的扩展点映射回三维空间中,将其连接为
9、三角网,作为初始三角网,在三角网的基础之上再选择一点作为下一次三角格网扩散的初始点;)重复),在三维空间中不断形成三角格网,逐点遍历,直到数据点全部遍历完成,最终形成完整格网曲面。测绘与空间地理信息 年 实验与分析 实验数据本文选取了 组点云数据,分别为、,组数据点数覆盖了低、中、高 个层次,数据表面复杂度逐步递增,数据来源于斯坦福大学计算机图形实验室。如图 所示。图 不同采样间距点云数据 为探究点云间距对重建算法精度的影响,本文基于原始点云数据采样为方案、方案 种点云间距。评价准则为了评价重建曲面的精度,本文将点云与重建曲面的误差定义为数据点与重建曲面的平均距离,定义如式():(,)()()
10、式中,为数据点;为重建曲面;(,)为数据点 到重建曲面的距离;对原始点云中的每一点,分别求出其到最近重建曲面的距离;表示取均值。实例分析)泊松重建误差分析实验 在 相 同 的 配 置 环 境 下 进 行,分 别 对、组数据集进行泊松重建,每组数据包含 种点云间距,对比分析泊松重建在不同八叉树深度、不同点云间距、不同形态数据的重建误差,采用泊松重建,并统计出相应的误差。如图 所示。图 中横坐标表示不同的八叉树深度,纵坐标为泊松重建误差,图中方案、方案 的点云间距为原始间距的 倍、倍重建结果。从图 可以看出,首先,随着八叉树深度参数的变化,组原始间距点集的重建误差结果具有一定的相似性。在八叉树深度
11、 时,泊松重建误差呈现下降趋势,其中图 泊松重建误差分析 树深度 时误差下降最快,树深度 时误差下降相对缓慢;树深度在 时,重建误差开始稳定在较低的值。随着八叉树深度的增加,组点集的重建误差呈现先减小后缓慢下降的趋势。这是由于八叉树深度控制重建模型的精细程度,八叉树深度达到 时重建模型最接近真实模型,重建误差最小,受数据分辨率的限制,再增加八叉树深度难以建立比真实模型更为精细的模型。其次,组不同点云间距的重建误差结果呈现相似的变化规律,方案、方案 点云间距与原始间距重建结果的变化具有相似性,表明点云间距对泊松重建误差影响较小。最后,、组数据形态复杂度呈现递增趋势,而 组数据泊松重建结果呈现相似
12、的变化规律,表明数据形态复杂度对泊松重建误差影响较小。综上,影响泊松重建误差的因素为八叉树深度,且八叉树深度达到 时,重建误差最小。)贪婪三角投影重建误差分析贪婪三角投影重建时,初始设定的种子点搜索距离参数会对重建误差产生影响。本文探索不同搜索距离对其重建精度的影响,分别设置了与上述相同的策略进行实验。如图 所示。图 贪婪三角投影重建误差分析 图 中横坐标表示不同的搜索距离,纵坐标为贪婪三角投影重建误差。由图 可以看出,首先,随着搜索距离的增加,组原第 期王 康:基于点云三维重建的参数敏感性分析始间距点集的重建误差结果呈现相似的变化规律:在搜索距离为 时,重建误差呈现下降趋势,其中搜索距离在
13、范围内重建误差下降最快;搜索距离在 时,重建误差稳定在一定较低的值。随着搜索距离的增加,组点集重建误差呈现先减小后缓慢趋于某一较低值的规律。这是由于贪婪三角投影算法投影到平面三角化时,初始设定的搜索距离过小未能建立局部最佳三角网,导致生成模型出现空洞,重建误差较大,随着搜索距离的增加,点集及邻域点逐渐建立最优局部三角网,生成模型空洞较少,误差减小,直至所有点集均建立最优三角网,重建误差稳定在较低的值,不再发生较大变化。其次,组不同点云间距的重建误差结果呈现相似的变化规律,随着点云间距的增大,重建误差呈现减小趋势,点云间距越小,重建误差越小。这是由于贪婪三角投影要求处理的点云数据密度均匀,当对
14、组点集进行方案、方案 采样后,点集的数据点密度较原始点集更为均匀,且经过采样后的点集表面更为光滑,减小了三角化的复杂度,因此重建精度更高。最后,组不同点云间距的重建误差结果呈现相似的变化规律,方案、方案 点云间距与原始间距重建结果的变化具有相似性,表明点云间距对贪婪三角投影重建误差影响较小。)种算法重建精度比较分析根据上述 种算法选取的最佳阈值,比较泊松重建算法与贪婪三角投影重建算法的重建误差及两者适用性。泊松重建参数八叉树深度设置为,贪婪三角重建中搜索距离为 。分别选取 种原始采样间距点云数据重建,分析泊松重建与贪婪三角投影重建的误差及重建时间,比较 种重建算法的优劣(见表)。表 种算法重建
15、结果对比 数据误差()时间()泊松重建贪婪三角重建泊松重建 贪婪三角重建 由表 可知,当点集为表面光滑的 数据时,贪婪三角投影重建误差为,重建精度最高,随着点集表面复杂程度的递增,贪婪三角投影平面三角化无法维持投影点与原有点之间的相对位置关系,无法从二维数据转换为三维数据,会丢失许多二维空间重叠点,导致信息不完整,增大重建误差。当点集为表面复杂度较高的数据时,泊松重建误差比贪婪三角误差小,重建精度高,这是由于泊松基于每个点计算其法向量构建隐式方程逼近模型,能够较好地贴近真实模型。泊松重建时间均大于贪婪三角投影重建时间,这是由于泊松重建需要计算每个点的法向量用于求解泊松方程,增加了重建时间。综上
16、,泊松重建算法与贪婪三角投影算法相比,两者均能实现点云的有效重建,其中,泊松重建总体精度更高,但效率较低;贪婪三角投影重建误差较大,但其效率更高。结束语本文选取了 组点云数据,采用泊松重建、贪婪三角重建 种算法进行重建实验,统计实验结果并进行了比较分析。实验表明,泊松重建算法优点在于重建精度高,且对于表面复杂的物体重建结果具有鲁棒性,缺点在于速度较慢,且计算法向量占据内存大,对平台要求高;与之相比,贪婪三角投影算法在牺牲一部分精度的情况下,取得了较高的重建效率,应对表面较简单的数据时,其重建精度更高,适用范围更广。充分了解每个算法对不同数据的适用性及其原因,不仅有助于选择最为合适的算法来处理问题,也对算法的融合改进具有指导作用。实验中采用的算法都是原始经典重建算法,近年来部分学者对此类重建算法进行了改进以提高重建精度和效率,对这些改进算法进行不同条件下的实验对比与分析,将是下一步的研究工作。参考文献:朱晓溪,杨东润基于虚拟现实技术的激光三维动画优化系统激光杂志,():张德先侠盗猎车 游戏自动驾驶系统配置和分析武汉:武汉大学,罗冬宇,王江锋,陈景雅,等三维点云环境下基于动视野的运行速度预