视觉信息学5（2021）1噪声点云中曲线结构的鲁棒重建Marcel Rittera，b，D.C.，Daniel Schiffnerc，Matthias Hardersa奥地利因斯布鲁克大学计算机科学系交互式图形与仿真组bAirborne Hydromapping GmbH，Innsbruck，Austriac DIPF|德国法兰克福莱布尼茨研究和信息教育学院ar t i cl e i nf o文章历史记录：2021年1月28日收到收到修订版，2021年4月13日接受，2021年2021年5月14日网上发售关键词：计算几何噪声点云自动自适应控制a b st ra ct基于点的几何表示已经在许多上下文中变得广泛使用，范围从基于粒子的模拟、立体图像匹配到经由光检测和测距的深度感测。我们的应用重点是在有噪声的三维点云数据的曲线结构的重建。在这样的点云上操作的相应算法通常依赖于局部邻域的概念。对于后者，我们的方法采用多尺度邻域，其中加权协方差局部点的措施是确定的。曲线结构通过矢量场跟踪重建，使用双向分段流线积分。我们还介绍通过多尺度几何测量自动选择最佳起始点。管道的开发和参数的选择是由超过一百万个原型测试用例的广泛的自动化初始分析过程驱动的。我们的方法的行为由几个参数控制- 大多数是自动设置的，只留下三个由用户控制在广泛的，通过自动化的最终评估，我们涵盖了超过10万个参数集，包括具有不同曲率、尖角、交叉点、数据孔和系统应用的不同类型噪声的3D测试几何形状。此外，我们分析了协方差计算中参考点的不同选择;在大多数情况下，使用加权平均值表现最好。此外，我们将我们的方法与当前公开可用的线重建框架进行了比较。在某些情况下，在类似的错误测量下，执行时间快了30倍。最后，我们还展示了一个示例性的应用程序在四个现实世界的3D光检测和测距数据集，提取电力线电缆。版权所有2021作者。由爱思唯尔公司出版我代表浙江大学和浙江大学出版社有限公司这是CC BY许可下的开放获取文章（http://creativecommons.org/licenses/by/4.0/）。1. 介绍近年来，基于点作为几何图元的数据集变得例如，在立体匹配期间或在光检测和测距（LiDAR）扫描仪（例如，激光雷达）中从 不 同 的 捕 获 设 备 （ 诸 如 深 度 相 机 ） 获 得 Toth and Jókw（2016），Foix et al. （2011））。此外，这种数据在基于粒子的模拟中也很常见（例如， Ihmsen等人 （2014））。在这种情况下，我们目前专注于从嘈杂的2D/3D点云数据的曲线结构的自动重建。为此，我们研究了分析这些数据的几何措施的发展，以及自动选择最佳的局部点邻域进行进一步处理。通讯作者：奥地利因斯布鲁克大学计算机科学系交互式图形与仿真组。电子邮件地址：marcel. uibk.ac.at（M。 Ritter），Schiffner@dipf.de（D.Schiffner），matthias. uibk.ac.at（M. Harders）。https://doi.org/10.1016/j.visinf.2021.05.001我们的应用领域是航空扫描的重建。在这些情况下，数据具有高噪声、不确定性、几何多样性以及高容量。正如德沃尔所说，等人 （2013），空中扫描的重建比小尺寸物体的重建受到较少的关注。相关的工作通常集中在小的和明确定义的对象，其法向量甚至可能是已知的（参见例如， Lu等人 （2017））。Berger等人（2013）的综述也支持这一观点，其中作者指出缺乏针对重建算法不同子类的综合评价在我们的框架中，曲线结构是基于无网格流线重建策略（例如，Tao et al. （2013））。从自动确定的初始种子位置开始，在点云邻域中识别重要方向和主导方向后者是基于加权二阶张量的局部点协方差。通过在多个尺度上的分析来捕获几何特征中的尺寸变化。基于确定的几何测度，我们自动设置算法参数：起点和积分方向的选择，方向2468- 502 X/©2021作者。由爱思唯尔公司出版代表浙江大学和浙江大学出版社。这是CC BY许可下的开放获取文章（http://creativecommons.org/licenses/by/4.0/）。可在ScienceDirect上获得目录列表视觉信息学期刊主页：www.elsevier.com/locate/visinfM. Ritter，D. Schiffner和M. 哈德斯视觉信息学5（2021）12搜索邻域以及方向评估。大量不同的2D和3D几何图形可用作自动分析的测试平台重建误差量化的度量，比较原始的未失真的点云几何。我们的启发式框架能够从扭曲的点集稳健地重建3D曲线;具有以下主要贡献：分析点云中的几何测量以自动设置邻域半径。自动选择积分起点和优化积分半径的评分功能。使用混合矢量场，通过流线积分进行重建。通过几何测量的噪声率估计。线重构评价的新误差度量。对参数选择进行广泛的自动分析，如协方差质心和加权因子。在介绍了相关工作之后，我们首先在第3节中概述了完整的重建管道。之后，我们将在第4节中介绍该框架的关键要素。首先，距离加权的几何措施进行了讨论;其次，我们提出了混合矢量场用于流线积分，基于特征向量和角加权方向;最后，使用多个线的流线积分介绍。在第5节中，我们专注于该方法的自动化：检测良好的起始点候选者并识别用于特征向量预计算的最佳半径最后，性能评估和曲线重建结果在第6节中给出。我们介绍了足够的错误度量，比较最近提出的替代技术，并indi- cate现实世界的应用。在下一节中，我们将介绍以前的研究结果，分为几个相关的领域。2. 相关工作点云中的线重建：在Dey和Wenger（2001）中，引入了一种基于点云的Voronoi图的算法;最近的邻居使用角度与Voronoi边缘比和拓扑条件连接。他们能够将不规则的点样本与尖角连接起来;然而，现有的点是直接连接的，这不适合我们工作中的噪声和密集采样的几何体基于Voronoi的方法也在Zenget al. （2008），增加了人类视觉启发的crite- rion，直接连接点。他们还提供了曲线重建算法的概述，如CRUST或NN;并通过DISCUR算法优于这些算法。他们成功地进行了小点集的线重建，包括尖角，边界和多个组件。然而，它们无法处理大量和非常嘈杂的数据，样本之间的插值或3D重建。Lin等人开发了一种基于均匀网格的方法。（2005年）。计算包含云的点的拟合矩形的序列。然后连接矩形的中心点，并与边界交点一起用于控制B样条曲线逼近。虽然该方法可以处理抖动数据，但它对斑点噪声不鲁棒;而且，不支持分支或尖角。其他工作集中在拟合多项式噪声点云。在鲁伊斯。等人（2013）在曲线拟合中添加了噪声自适应平滑项;他们在预处理步骤中采用了主成分分析（PCA）进行分割，并构建了分段曲线，支持分支和交叉。虽然我们的方法遵循不同的方向，但在使用加权PCA以及分段重建策略方面存在相似之处。然而，他们只提供了2D的例子，该方法受到离群值和数据漏洞的阻碍。Flöry（2009）采用了拟合B样条然而，对于3D，他们专注于表面，而不是线;并且分支或交叉点在他们的工作中没有针对性在Philsu和Hyoungseok（2010）中提出了基于半圆盘和角度加权概率函数的线重建算法从一个起点开始，选择其他的并连接成一行。该方法可以处理线交叉;此外，当引入噪声时，仍然可以重建线但是，结果将始终位于弯曲点云的最外边界。在我们的方法中，我们还采用了角度加权的方向分量。在Hasirci和Ozturk（2011）中，使用自适应半径选择经由PCA他们采用归一化的最大特征值来确定最佳半径，然后生成三阶多项式来重建一条线。尽管如此，他们的方法仅限于平滑的线条，无法处理交叉、分支或数据漏洞。他们扩展了Ozturk和Hasirci（2013）的工作，通过应用最小欧氏生成树进行点细化。这为分支和交叉口提供了强有力的支持，但也在交叉口引入了缺口。在不同的背景下，Jaw和Sohn（2017）通过分段和分段回归重建了传输他们专注于一种自动，鲁棒和精确的方法来处理风引起的噪声;他们与Hough变换进行了比较并优于Hough变换。关于点云的2D线重建的最新出版物可以在Ohrhallinger等人中找 到 。 （ 2016 ） ， Ohrhallinger 和 Wimmer （ 2018 ） ， 以 及Ohrhallinger和Wimmer（2019）。首先，扩展了CRUST和NN方法，专注于非常稀疏的采样数据。他们选择一个本地最近的邻居和相反的半空间邻居，并证明这允许连接多达60个锐角，采样范围大于以前的方法。作者进一步将他们引入的HNN-CRUST算法扩展到FitConnect，首先估计局部特征大小并通过在噪声区域中混合生成新点。对许多实例进行了广泛的分析，并与其他在线重建工作进行了他们能够成功地处理尖锐的角落和不同的噪音。进一步的然而，他们的重点是2D流形; T型接头，交叉和3D重建没有涵盖。点云中的曲面重建：在20世纪90年代早期，Hoppe等人引入了通过协方差分析计算的正切平面来定义隐式曲面函数。（1992年）。使用这些，他们重建表面与行进立方体等表面算法.然而，协方差没有加权，因此更容易产生噪声。在McIvor和Valkenburg（1997）中，比较了几种用于局部表面和法线估计的方法。他们分析了人工几何形状的估计性能，并添加了不断增长的噪声。他们专注于二次拟合，并提到了基于协方差的技术，但没有将其纳入比较。Berger等人提供了表面重建算法的基准。 （2013），比较了具有定义法线的点云的十种最先进的方法;其中包括：紧支撑径 向 基 函 数 （ CSRBF ） （ Ohtake et al. ， 2005; Wendland ，2005）、简单点集曲面（SPSS）、隐式移动最小二乘（IMLS）、多级单位分割（MPU）。结果表明，目前还没有一种优越的、通用的曲面重建技术。用于距离加权的多项式基函数例如在Wendland（2005）的CSRBF中，也被包括在我们的工作中作为在Giraudot et al. （2013）他们还旨在重建点集，自动调整局部变化的采样和噪声属性。噪声自适应······M. Ritter，D. Schiffner和M. 哈德斯视觉信息学5（2021）13×∑∑˜距离函数，并找到一个隐式函数作为一个零等值线（或表面）。该方法对离群值和抖动点集产生了鲁棒的结果，但不同之处在于它需要封闭的光滑形状作为先决条件。张量和协方差技术：Taubin（1995）提出了一种计算多边形网格上的高斯曲率和平均曲率的算法，其中引入了相邻顶点的方向向量的张量积来估计表面曲率。他们构建了一个曲率表示的2 - 2矩阵在当地的表面切平面。方法有限不适用于3D点云数据。在Berkmann和Caelli（1994）中，基于局部邻域的协方差，引入了曲面的第二基本形式和高斯映射估计。他们检测深度图像中的区域，并在平面、抛物线和曲线段之间进行区分。他们表示，由于使用了而不是封闭的基本形式。然而，这仅适用于低噪声比。类似的加权乘积在Alexa和Adamson（2004）中提出了计算点云邻域中的协方差矩阵来估计法线。该方法在点云上操作，但点是已知的 从表面的几何形状出发，同样，在数据中具有低噪声。Liu等人所（2012）应用投票技术以使法向量估计对噪声具有鲁棒性。他们采用形状因子进行着色并作为置信度测量。在我们的工作中，形状因子的定义不同，我们的方法通过加权协方差实现鲁棒性。张量场中的直线跟随：从扩散中在医学领域中已经使用了磁共振张量场来可视化磁共振图像中的特征。在这里，大脑不同区域之间的连接是有趣的，通过纤维跟踪来说明。早期的方法采用本征矢量流线的主要特征向量的二阶张量（巴瑟等人。，2000），或向量张量乘法以计算下一个步骤方向（Chou et al. ，2006年）。交叉光纤可以吸引流线整合以切换到不同的光纤。因此，已经提出了扩展，以有利于原来的方向，当在一个十字路口（温斯坦等。，1999年）。我们还研究了方向选择策略，但在无网格数据上操作，而不是扩散张量工作中的均匀网格。点云分类：在Natale等人。 2010年：形状因素利用决策网络对室内三维闪光LiDAR图像进行主成分分析他们通过在相当小的邻域中的邻域数量Fig. 1. 改造管线的主要工艺步骤。4. 修剪线：对不断增长的小线进行交叉和拐角测试，并进行扩展以克服数据漏洞。最后，它们被修剪，然后连接成曲线结构作为输出。每个流水线步骤涉及用于控制结果的多个参数对于其中的大多数，我们已经进行了广泛的自动化初始测试，以确定和修复最佳性能参数。如果需要，仍有一些参数可以手动调整，为管道输出提供一些用户控制（见第5.3节）。在下文中，我们将首先更详细地描述各个步骤，然后解决自动化问题4. 线性结构4.1. 几何测度我们的重建框架的中心元素是数值几何测量，表征局部线性、平面性和球形度;遵循Westin等人（Westin et al. ，1997）。为了获得点云中任何位置的这些测量，我们首先计算加权二阶张量t，其被构造为从邻近邻域内的所有方向向量1兜帽我们使用不同的形状因子定义和参数，半径。同样，在Weinmann et al. 04 The Fall（2015）使用变量作为随机森林分类器的输入他们Ni=1 ω（di）Ni=1 ω（di）（vi<$vi），其中（1）通过依赖于数据中的几何中位数，将其真阳性提高了3%。3. 重建管线概述我们在噪声点云数据中提取曲线结构的框架由几个单独的关键步骤组成（另见图1）。 1）、1. 几何测量：几何测量在点云数据的多尺度邻域中通过加权协方差局部计算。基于这些局部测量，以逐点方式确定最佳邻域半径。2. 起始点：分段流线积分的种子位置根据精确计算的测量值自动选择。3. 增长线：从起点开始，线并行增长，在混合向量场中遵循流线它们遵循点样本，这些点样本可能是从连续线几何中采样的。vi=pi−c，di=|vi|/r，其中c是具体确定的3D中心位置（以下表示为质心），p是邻域半径r内c的局部邻域中的点，N是该半径的相邻点的数量，d 是归一化距离，ω（x）是径向距离加权函数。注意，在不使用加权函数和采用c的平均位置的情况下，我们将获得局部点云的标准协方差矩阵作为这些张量，然后可以对其进行主成分分析。还要注意，点云中的距离查询和计算是使用八叉树数据结构加速的我们测试了30个不同的归一化标量函数，用于等式中的权重。（一）.例如，可能的候选者是二次、三次、紧支撑RBF或SPH平滑核。在最初的控制，自动化研究中，我们计算这些候选函数的重建误差;不同的参数，如邻域半径，点的数量，抖动噪声强度等，总共有135万个参数组合进行了自动测试，在一个圆形和矩形测试形状，在大约7小时的运行时间。最后，最好的表现=M. Ritter，D. Schiffner和M. 哈德斯视觉信息学5（2021）14[0个=++∈] ∈ []发现了一个类似于费米-狄拉克分布的加权函数（源于量子统计，但这里没有物理常数）（McDougall et al. ，1938年）：（二）图的形状由两个参数T控制. 0，0。4和m0的情况。0，1。0的情况。前者从一个步骤混合到线性函数，而后者沿x轴移动函数。在我们的自动化实验中，我们发现加权曲线（I），参数（0。1、0. 6）最适合张量计算（也见上面的图）。请注意，下面我们还将使用类似的加权函数进行无网格插值;在这种情况下，曲线（II），参数为（0.05，0。（35）表现最好。这些值是通过分析在上述自动测试中获得最佳重建。1可以通过选择用于确定质心c的合适方法来实现针对噪声的进一步稳定。在上述张量计算中，过去已经提出了几种特别是噪声的存在对计算有很大的影响，这使得使用均值（MN）不一定是最佳选择。当量（1）是当采用MN时的加权PCA另一种选择是替代地采用几何中值（MD），已经发现其对噪声数据是鲁棒的（Lip_man et al. ，2007; Lin et al. ，2014年）。此外，我们还研究了将加权引入均值和中值计算（WMN，WMD）的选项;然后质心位置根据所选的权重函数而变化。为了计算几何中值，我们采用Weiszfeld算法（Plastria，2011），其在其迭代中使用指数函数。在算法中添加权重函数控制迭代移位的强度。这种加权质心变体产生几何中值和平均值之间的位置。最后，另一种选择可以是使用点云本身的实际点作为张量估计中的我们在性能测试中使用不同的3D测试几何形状比较了这些不同的选项（参见第6.5节）。作为一个普遍表现良好的候选人，WMN与二次逆脱颖而出。以WMN为质心，在张量计算中采用几何测量t的特征向量分解产生局部线性度、平面度和球度的度量，Westin et al. （1997年）：CL= （ λ3−λ2 ） /L ，CP=2 （ λ2−λ1 ） /L ， CS=3λ1/L ，（3）特征值为t：λ3> λ2> λ1，Lλ1λ2λ3和相关的本征矢量e3、e2、e1。特征值和特征向量将是中心的曲线结构的重建通过矢量场积分。应该注意的是，两者都依赖于邻域半径，这控制了计算所考虑的点集。两者都可以根据如何选择邻域半径而显著变化。因此，我们进一步探讨了作为半径函数的测度1 更多详情见补充材料。图二. 几何测量，在小型示例2D点云的质心处计算，有噪声和无噪声（顶部）。几何测量值（底部）随半径变化;线性度最初很高，当达到拐角时会降低4.2. 邻域半径在上面的张量计算中，可以对某个点的邻域采用固定的半径然而，取决于局部特征尺度，这可以包括或可以不包括代表性几何信息。此外，如果存在3D抖动噪声，其幅度大于半径，则球形度测量将占主导地位，与其他结构无关。因此，仅找到在所有情况下都是最佳的单个半径将是具有挑战性的，甚至是不可能的;特别是当采样分辨率改变时;或者线性特征出现在不同尺度时。取决于所选半径的几何测量的变化在图2中可视化;针对两个示例性2D点云计算三个测量（顶部），产生作为增长半径的函数的图（底部）。请注意，对于这种2D情况，球度测量结果为零;而测量结果之和为1。计算度量的质心（橙色）位于点采样矩形角（蓝色）的一部分上，一次没有（左侧），一次有抖动噪声（右侧）。在前一种此时，线性度开始降低，而平面度增加。在后一种有噪声的情况下，小尺度的初始峰值标记半径，在该半径处覆盖两个最近的点，从而产生高线性度。这个测量值下降到抖动噪声幅度;然后增加，也直到达到拐角。使用不同的加权函数在方程。（1）导致线性图的变化因此，我们还评估了加权函数在线性图属性方面的适应性：小半径处的最大值/最小值，大半径处的平台，以及所得图的整体平滑度。关于平滑性，Fermi-Dirac二次加权也表现良好，但偶尔会产生几何测量图中的不连续工件。此外，开发了多尺度空间的直接可视化，示出了Ritter等人的不同参数选择。 （2021年）。4.3. 矢量场积分为了重建点云中的曲线结构，我们采用矢量场积分（参见例如Tao et al. （2013））。这表示流线在无网格数据中沿着特定方向发展，遵循原始几何形状。积分步骤的数值计算使用显式我们测试了各种变体，最多可达五阶，但M. Ritter，D. Schiffner和M. 哈德斯视觉信息学5（2021）15∑∑=−=vj，i图三. 角度加权方向向量;以前的积分方向（灰色）用作参考。有了它，使用角度的余弦，通过与所有相邻方向的点积获得（一个示例以蓝色显示）。最后一个方向（红色）是邻域中加权向量的归一化均值。这被发现是小的;因此，对于我们的实验，我们依赖于简单和快速的三阶RK 32方案。对于积分过程，需要局部方向向量，其将基于先前计算的特征向量来确定（注意，后者是双向的并且可能必须翻转）。我们已经分析了不同的方法来计算方向，在最后两个组合成一个混合的方法。由于我们使用无网格数据，因此我们必须：在现有数据云点pi处计算的方向之间进行插值，或者直接计算任意位置xj处的方向。第一种方法用于在位置xj处找到积分方向，计算相邻主特征向量的平均值;基于归一化距离加权：14.4. 分段重构作为前面概述的矢量场集成的改进，我们进一步建议以宽度优先的方式同时生长多个较小从不同的点开始，积分平行地向前和向后发展，产生所谓的线。在每个积分步骤中，针对各种条件（并且可能终止）检查演变的细线条：即，超过最大步数、离开点云的边界框、超过最大距离阈值、与另一细线条端部冲突或与另一细线条段相交。的情况下碰撞时，线的端点被合并;在相交的情况下，线的端点被放置在相交点处。在3D中，通过检查它们的最近点来确定倾斜线（即段）的相交。当线段端点和最近的倾斜线段点的距离低于距离阈值时，它们将被合并：mrgh，其中h是积分步长，mrg是加权因子（设置为1.4）。此外，如果在集成期间，从一个步骤到下一个步骤的线方向的变化超过70μ m，则会植入新的线并创建分支。在交点、碰撞以及分支种子处的端点被标记为闭合;而由于超出边界框或距离阈值而生成的线段端点被标记为开放。在最后一步（修剪）中，从所有线段中删除点，从开放的端点开始。删除过程向后传播，直到到点云中最近点的距离小于用户定义的阈值。第二个用户控制参数是最大积分距离。增加后者能够克服数据漏洞，dE（xj）=Ni=1 ω（di）Ni=1 ω（di）e3，i，（4）前者允许删除长的开放分支。最后，请注意，对于有效的相交计算，其中N个相邻点的主特征向量e3，i由所选半径给出;并且di是归一化距离。特征向量根据在前面的中间中使用的方向对齐梯度步长dt-1;即，如果它们与当前流线主方向相反，则它们被翻转。对于加权函数ω（. ）我们使用上面提到的插值结果略有改善。该第一种方法对于噪声数据和较大尺度特征是有用的，提供了非常平滑和鲁棒的方向选择。由于本征分析已经完成，不需要额外的计算用于找到积分方向的第二选项是采用角度加权局部差向量的（归一化）和：也被组织在单独的八叉树中。在下一节中，将讨论该过程的自动化。5. 过程自动化5.1. 起点的选择在我们的分段重建的一个关键因素是多行let创建的起始点的设置。我们建议根据上面介绍的线性图自动化。开始矢量场积分的点应位于点云中的“良好"线性区域。因此，我们分析每个线性图以确定这样的位置。如上所述，针对不同半径确定线性度量首先，为了加快这一进程，（2）N（ωj=1cos（φj）+1））不同的尺度，我们建议增加搜索半径rk，根据指数函数计算（而不是线性增加）：vj， iXJpi是位置xj和N个相邻点pi之间的差向量，同样对于给定的半径。余弦项使用归一化向量dt−1和vj，i之间的角度i计算（另见图10）。 3）;最后，ω（. ）再次是费米-狄拉克（II）加权函数，这次用基于角度的项进行计算。使用第二种方法计算的方向更接近几何形状，并且整体重建对于较小规模的特征，性能更好。由于该方法包括当前流线积分位置处的角度计算，因此必须在每个积分步骤的“运行时”执行该稍后，我们将得到最终的积分方向，作为dE和dA的加权平均值（见5.2节）。为此，将基于预先计算的几何测量自动确定最佳权重和半径。rk=1。5k，（ 6）其中，k可以被认为是与log（r）成比例的所测量的半径的集合的离散索引;参数k表示点云中的任何两个点之间的（近似）中值最小距离（针对整个云或针对随机子集计算）。 计算第N个最近邻居的距离（我们使用N6）。根据这些数据，已确定的。我们发现在一个特定部分下面的积分面积线性曲线图CL已经表示用于起点选择的鲁棒特征。为了说明这个图。图4示出了矩形的示例性噪声点云上的六个位置的曲线图（注意，子图中的坐标采用rk的对数标度）。云的线性部分上的位置表现出较大的积分dA（xj）=nrm1−2、M. Ritter，D. Schiffner和M. 哈德斯视觉信息学5（2021）16一（）下一页=·=1、见图4。不同位置的矩形上的六个线性图形。该公司采用对数尺度的半径。近似积分A，直到最后局部最小值以及最大值CL，max用于起始点检测。图五. （左：）（有序）点索引上的线性积分和值，针对图中所示的两个点云确定。六、（右图：）三个选定点的线性图示例。具有高总和的位置（由椭圆表示）在线性区域中，并且被认为是流线积分的良好起点。(see 2、4、5）。相反，角点（6）和噪声中的点（1，3）通常示出较小的积分和图形最大值。因此，我们建议估计云中点的线性图CL的近似积分A它是通过对半径rk（指数增长）的线性值求和计算的，从零到图中最后出现的局部最小值;数值上近似解析积分（图中的灰色阴影区域）。注意，从某个最大半径开始，线性值将保持恒定。作为所提出的特征的进一步说明，图5示出了在图1中描绘的开放矩形的质心处计算的线性积分值。六、这个例子是在没有噪声（上图）和有噪声（下图）的情况下计算的。可以看出，具有大积分值的区域（由椭圆标记）保持相对稳健。因此，较大的值可能会在线性区域中产生点。基于以上所述，为了获得良好的起点，我们采用了一个得分函数，该得分函数可以针对所有点或针对减少的随机子集（最初将距离参数d设置为1.0）进行计算Os=d·N0。01（CLmax·A）4，（7）见图6。为两个示例几何体选择的起点-无噪 波 和有噪波。点的选择取决于它们的得分Os;数字指示选择的顺序。位置（a）和（b）的线性积分如图所示。五、对右边描绘了连续候选者的递减评分函数达到（默认2分）。在非常嘈杂的数据中，采用最少6个点改善了结果。然后，将当前点中具有最高得分Os的如果已找到最大数量的起始点，则该过程停止。图图6示出了两个几何形状上的所识别的起始点，一个几何形状没有抖动噪声，一个几何形状具有抖动噪声。图中的数字指示根据得分Os选择候选者的顺序。可以看出，在两种情况下，第一起始点都是在长矩形边缘的中心处找到的，而避免了拐角位置和噪声点对于初始点（1），到开始点候选的距离距离越远越好。因此，起点彼此保持合理的右边的图显示了对于逐渐增加的所选起始点的数量，分数Os递减。分数函数被设计为乘法，因为d的标度不能被归一化;这仍然允许相对排序。5.2. 积分方向如上所述，当前步骤dt的最终流线积分方向将被确定为向量dE和dA的加权平均：dt=µdE+1−µdA，（ 8）其中μ是混合重量。两个方向向量的计算取决于邻域半径，我们也建议自动确定类似于自动起始点选择，线性测量的曲线图可用于此。在单个数值积分步骤之后，流线结束位置通常不会精确地位于点云的点处。因此，我们首先在r t 1的搜索半径内找到最接近当前积分位置xt的点p i。25mdn.在这一点上，预先计算的线性图将进一步考察 这允许找到最佳邻域半径，其中，CL，max是所检查样品中的最大线性值半径的间隔和N1的邻居在第一个非空的邻居遇到的数量（当增长的半径）。因此，孤立的点会略微被否决。此外，在该特定情况下，可以通过使用用于计算CL，max的PDT而不是使用其他质心计算方法之一来实现小的计算改进。运用评分函数，确定得分最高的初始点，设d1. 接下来，使用后者作为种子，然后我们通过评估相同的（缓存的）等式来逐步识别其他起始点，现在d被设置为到目前为止所有选定起点的最短距离。请注意，如果N1中的最小数量不满足，则在精简整合过程中的当前步骤在具有噪声和粗糙结构的点云区域中，大半径将是一个很好的选择，而对于具有精细结构的区域，应选择小半径。作为前者的示例，考虑图4中点4的线性图中的最大值（用 * 标记）;对于后者，考虑图中位置6处的图中的（第一）最大值。8.第八条。因此，分析线性图中的极值将是用于自动选择邻域半径的手段。线性图通常会在不同的半径处表现出几个局部最小值和最大值;通常，在我们检查的几何形状中存在多达四个极值。因此，我们设计了第二个评分函数。对每个局部最大值M. Ritter，D. Schiffner和M. 哈德斯视觉信息学5（2021）17=[客户端]+−=−一K2、一2见图7。评分函数的元素，基于线性图的k j处的局部最大值和k j−和k j+处 的相邻最小值。见图8。通过两个示例性点云几何形状上的线段示出的最佳半径和方向dE。在线性图中，在对应于该特定最大值的半径（具有索引kjO m=（1−kj）C Lj+Aj -δ。（九）见图9。（上/左）：六个测试“ 2 D" 几 何 形 状 ： 圆 形 、 矩 形 、 三 角 形 、 直线 、 波 浪 形 和 交 叉 。(Top/右）：四个3D几何体：Elbow、Mikado、Humble和Crossing 3D（深度由灰色渐变表示）。（底部）：添加的噪声类型;从左到右：未失真参考、抖动噪声、分布噪声、离群值噪声和孔洞。此外，为了确保方向选择的两种方法仍然影响最终结果，我们还将此混合因子箝位到区间0。05，0。九十五。最后，数值流线积分的步长也自动设置为h0的情况。5.注意，这可以确保平均而言，邻域大小约为六个点。为了提高计算效率，我们并行地进行几何测度和特征向量的计算，以及半径选择。方向dE在电流下确定，这里，j表示当前检查的局部最大值的半径索引，对于由kj给出的半径。CL，j表示相应的线性度值，K表示针对当前线性度图考虑的离散半径索引的总数。此外，A和Aj 又是（数值近似）图的积分前者跨越相同的半径间隔，如上所述;然而，后者仅针对j的左侧和右侧（分别由j和j表示）的最近局部最小值之间的间隔计算。最后，δ表示CL，j与相邻局部最小值处的两个线性度值中的较大者之间的差，即 δC L，jmax（C L，j−，C L，j+）. 为了更好地说明，所涉及的量如图11所示。7.第一次会议。评分函数由三项组成，取值范围为0.0到1.0;越高越好。注意，在第一项中，小半径是优选的（即，小kj），因为它如果存在小尺度特征的话，则对调整到小尺度特征是有益的。另外，较大的线性度值CL，j通常也指示良好的半径候选。在第二项中，大的局部积分Aj是有利的，这也暗示了线性结构。最后，在第三项中，峰值最大值将通过δ被投票否决将为所有局部最大值计算分数Om，并且将保留与最高分数相关联的半径以用于计算dE和dA。 为了说明这一步骤，图。图8描绘了两个示例点云的所获得的半径和方向dE。示出了线段，每个线段具有由所确定的最佳半径给出的长度和由矢量dE给出的方向。在大型线性结构（1）、噪声（2）和低曲率（3）的区域中，线段的半径和长度会增加;相反，在拐角（4）、交叉点（5）和细节（6）处，线段的半径和长度会较小。我们通过μ混合两个方向向量。当线性度和所选最优局部最大值j处的积分较大时，则dE将是稳定的选择;否则dA应优先遵循附近的几何图形。因此，我们建议将混合参数自动设置为：积分邻域和插值的预先计算使用费米-狄拉克（II）加权的本征向量。为了计算dA，必须知道先前的积分方向和当前的流线位置;因此，它是逐步获得5.3. 用户控制虽然我们的框架展示了几个参数，但我们建议修复其中的大部分。这可以通过概述的自动选择过程或通过广泛的先前自动参数分析运行来实现。在我们当前的框架中，用户必须手动控制主要三个参数：MaxIterations：流线型集成步骤的最大数量。StartPointsNr：line-let积分的起始点数量。DistanceCutoff：从积分点到最近数据点的最大允许距离;用于克服漏洞。所有剩余的参数都是预定义的;尽管如此，如果需要，用户例如修剪距离DistancePrune：从线端到云中最近点的最大允许距离asMaxRadius：最大几何分析半径（设置为 60欧元）。我们为用户提供了一个交互式的可视化界面，便于控制和评估的重建。6. 分析和结果6.1. 点云测试几何在我们的分析中，我们采用了六种“2D "和四种3D测试几何形状：圆形、矩形、三角形、直线、波浪形和十字形;以及肘形、障碍形、天皇形和十字形3D（见图1）。（9）这些1µ=2Aj+（CL，j-1）。（十）表现出诸如变化的曲率、尖角和线交叉的特征。所有这些都被采样为3D点云（···M. Ritter，D. Schiffner和M. 哈德斯视觉信息学5（2021）18/i=1E[客户端]∑Ex∈Λy∈y∈x∈Λ、∑等（2017），我们的曲线几何形状的情况下。尽管如此，我们还是决定开发针对点采样线性结构的度量标准，比较几何结构、重建长度以及覆盖范围的差异。首先，几何差异进行量化使用一个适应的Hausdorff度量和平均最小距离度量。为了进行比较，我们采用（已知）测试几何上的等距离点样本Λ作为地面实况。这些是比较我们的重建所给出的流线积分点，获得恒定的步长。对于这些，我们计算两个误差-首先，基于点的Hausdorff度量：EH=max{max mind （ x ， y ） ， max mind （ x ， y ）}，（ 12）每个抖动噪声的几何度量平均最小球度在较低温度下线性增长对于d（.，. ）是两点之间的欧几里得距离;以及第二，平均最小距离度量：抖动值。因此，它被选为噪声率测量值，并按比例进行归一化，参见等式10。（十一）、EV=1（∑mind（x，y）+∑mind（x，y））、（十三）N+ NΛx∈Λy∈y∈<$x∈Λ几何形状用余弦函数移出平面不同类型的噪声被添加到这些几何形状中;我们采用了四种类别，灵感来自真实世界数据捕获期间可能发生的噪声：不稳定的轨迹和振动可能会产生抖动噪声;阴影或多次扫描可能会引入密度分布噪声;悬浮颗粒或其他小物体可能会产生随机离群值;传感器或遮挡中的强度截止可能会导致孔。图图9还说明了这些对线段的影响（底部）。在我们的框架中，所有的效果都可以通过适当的参数来控制：抖动幅度Sj，其中，N1和N2是两个比较集合中的点的数量。这两个度量指示重建的局部几何质量。由于这两个指标保持稳定，即使只有一部分的点云重建，我们开发了两个额外的措施，占重建的完整性。第一个是重建的（估计）长度与原始线的（已知）长度之比：ELen=len（） 透镜（Λ），其中（14）N−1分布混合Sd，数据孔开始ta和结束te，以及附加的随机离群值M的数量。6.2. 噪声估计下面，我们将在各种有噪声的示例几何体上测试重建过程。请注意，只有对于我们自己的人工生成的数据，这些噪声参数才能准确地知道。相反，对于任意点云，后者必须估计。我们发现，所有球度图最小值的平均值与数据中的噪声直接相关。因此，我们提出了一个度量量化任意数据中的噪声强度nR1len（）=|xi+1− xi|、其中xi是重建的连续点。如果重建的直线比原来的直线短，则ELen<1. 0;我们认为这是不完整的覆盖范围。此外，如果Len> 1。0，则重建可以以某种形式多次覆盖原始几何形状（注意，它可能仍然没有被完全重建）。第二个完整性度量确定覆盖的量。对于每一个小线，计算对应的弧长间隔s、el，其中s和e是Λ的开始和结束参数（以弧长计），并且l是小线索引。所有间隔的并集除以原始点云的长度，nR=c·NNi=1 minCS，i（r），（11）R完整性度量：1其中CS，i（r）表示在多尺度半径r处具有指标i的点的球度。此外，恒定缩放因子c = 3。第15号已ECom=len（Λ）Σ|U|（e i−s i），ei，si∈Ui（15）U=[s e]增加3D抖动噪声。图中显示了矩形和圆形的此外，还指出了三种形状测度的最小值和最大值的变化在底部，提供了噪声不断增加的矩形点云视图。对于这两种几何形状，nR最初主要线性增加，随后趋于平稳，以获得更高、更极端的噪声。噪声率nR与分布噪声和数据空洞无关。下面，我们将使用此度量来评估和比较结果，这取决于噪声幅度。如所指示的，也可以是真实世界数据集，对于真实世界数据集，噪声参数不可以这样比较6.3. 误差度量为了评估噪声点云的自动重建，我们需要适当的误差度量。一种选择是调整现有的误差测量方法，例如Berger如果所有弧长的并集覆盖整个原始几何形状，则E Com接近1.0;如果Com<1。0，则重建再次不完整。使用这两个额外的度量，如果ELen=ECom，则重建被认为是唯一的。6.4. 初步示范重建为了说明我们完整的重建管道的性能，我们首先展示了一组较小的定性结果。先前描述的测试几何形状的示例被重建（参见图1A和1B）。11和12），两者都没有如不同程度的噪音。如果没有明确指示，
