点云边界检测和边缘重建的新算法

可在ScienceDirect上获得目录列表计算设计与工程杂志首页：www.elsevier.com/locate/jcde计算设计与工程学报6（2019）81三维表面点云边界检测与边缘重建Carmelo Mineo，Stephen Gareth Pierce，Rahul Summan电子和电气工程系，斯特拉斯克莱德大学，皇家学院大楼，204乔治街，格拉斯哥G1 1XW，英国阿提奇莱因福奥文章历史记录：接收日期：2017年2018年2月5日收到修订版，2018年在线提供2018年保留字：点云边界检测边缘重建A B S T R A C T从点云生成的镶嵌曲面通常显示不准确和锯齿状的边界。这可能会导致公差误差和问题，如机器抖动，如果该模型用于正在进行的制造应用。本文介绍了一种新的边界点检测算法和基于空间FFT的滤波方法，这两种方法一起允许从点云数据直接生成低噪声的镶嵌曲面，而不是基于预定义的现有的检测技术被优化以检测属于尖锐边缘和折痕的点。新算法的目标是检测边界点，它能够做到这一点比现有的方法。基于FFT的边缘重建消除了为最佳多项式曲线拟合定义特定多项式函数阶数的问题。对该算法进行了测试，以分析结果，并测量点云的执行时间，这些点云是由具有不同数量的构件点的涡扇发动机涡轮叶片上的激光扫描测量生成的。重建的边缘拟合的边界点的改进因子为4.7，超过了标准的多项式拟合方法。此外，通过添加人工噪声，它已被证明是非常强大的检测算法的面外噪声低于25%的云分辨率，它可以产生令人满意的结果时，噪声低于75%。©2018计算设计与工程学会Elsevier的出版服务这是一个开放在CC BY-NC-ND许可证（http://creativecommons.org/licenses/by-nc-nd/4.0/）下访问文章1. 介绍三维（3D）扫描越来越多地用于分析各种应用中的物体或环境，包括工业设计、矫形器和假肢、游戏和电影制作、逆向工程和原型制作、质量控制以及文化和建筑文物的记录（Curless，1999年; LevoyWhitted，1985年）。传统的重建技术从点云生成镶嵌曲面。这种镶嵌模型通常显示不准确和锯齿状的边界，如果模型用于正在进行的制造应用，则可能导致公差误差和机器抖动等问题（Beard，1997）。这就是为什么许多现有的商业计算机辅助制造（CAM）应用程序无法使用镶嵌模型，而不是使用精确的分析CAD模型，其中表面是数学表示的（Mineo，Pierce，Nicholson，Cooper，2017）。虽然将解析几何形状转换为网格化表面很简单，由计算设计与工程学会负责进行同行评审。*通讯作者。电子邮件地址：carmelo. strath.ac.uk（C. Mineo）。将镶嵌模型转换成分析CAD模型的逆过程是具有挑战性的并且是耗时的。在某些情况下，零部件的原始CAD模型不可用或与实际零件存在偏差 新的CAM软件应用程序，能够使用干净的镶嵌模型，正在出现（Mineo等人，2017年）;他们使直接使用三角点云可通过表面映射技术。然而，通过表面映射获得的点云通常受到噪声的影响。新的算法，最佳的表面网格细化，以提高新兴应用的性能，并克服典型的方法的局限性，多项式平滑的基础上。不同的技术可用于构建坐标测量机（CMM）或3D扫描设备（Curless，1999）。每种技术都有其自身的局限性、优势和成本。许多CMM和3D扫描仪的一个共同点是，它们可以测量物体表面上大量点的坐标，并输出扫描区域的点云。然而，点云通常不能直接用于大多数3D应用中，因此通常被转换为网格模型、NURBS表面模型或CAD模型（Berger等人，2017;Hinks，Carr，Truong-Hong，&Laefer，2012; Truong-Hong，Laefer，Hinks，&Carr，2011）。镶嵌模型已经成为一种受欢迎的技术;它们是最简单的https://doi.org/10.1016/j.jcde.2018.02.0012288-4300/©2018计算设计与工程学会Elsevier的出版服务这是一个在CC BY-NC-ND许可证下的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。82C. Mineo等人/计算设计与工程学报6（2019）81¼以最少的处理从点云获得的虚拟模型的形式从点云生成三角网格曲面有两种不同的方法：三角剖分法和曲面重构法。三角剖分算法使用输入点云的原始点，将它们用作网格三角形的顶点。德劳内三角剖分，命名为鲍里斯德劳内为他的工作主题从1934年（德劳内，1934年），是最流行的算法这类。二维Delaunay三角剖分确保与每个三角形相关联的外接圆在其内部不包含其他点这个定义自然地延伸到三维，考虑球体而不是圆形。曲面重建算法不同于三角剖分方法，因为它们不使用原始点作为网格三角形的顶点，而是计算新的点，其密度可以根据3D几何的局部曲率而变化基于泊松方程，从定向点的表面重建可以被视为空间问题&&这两种方法都不能准确地重构曲面边界，使得曲面细分模型不适合用于CAM刀具轨迹生成。三角剖分方法产生具有锯齿状边界的网格曲面，因为云的原始噪声点被用作网格三角形的顶点重建方法产生平滑的边界，但它们可能与真实曲面的原始边界相差甚远。实际上，泊松云边界点的检测和平滑边界边缘的重建将允许修剪重建的镶嵌模型，以细化网格边界。只有极少数的特征检测方法被优化为只与点采样几何图形一起工作。这些基于点的方法的主要问题这使得特征检测比基于网格的方法更具挑战性Gumhold、Wang和MacLeod（2001）提出了一种算法，该算法首先通过主成分分析（PCA）分析每个点然后，相关矩阵的特征值用于确定点是否属于特征。这种用于检测点云中特征的技术被用作具有尖锐特征的镶嵌表面重建的预处理步骤（Weber，Hahmann，Hagen，2011）。还有几种重建方法可以在不进行预处理的情况下在点云的表面重建过程中保留尖锐特征;例如，Fleishman、Cohen-Or和Silva（2005年）以及Öztireli、Guennebaud和Gross（2009年）所示的方法。上述现有技术被优化以检测属于尖锐边缘的点本文提出了新的算法，有针对性地检测边界点和确定性重建的准确和光滑的表面边界从三维点云。被称为网格跟随技术（MFT）的智能方法（Mineo等人， 2017），用于从STL模型生成机器人工具路径，最近已经出版。该技术需要具有平滑边界边缘的虚拟镶嵌曲面本文提出的算法是从三维扫描点云数据中细化曲面边界的有效工具。它们可用于修剪Delaunay三角剖分或泊松重建的表面网格，便于直接使用镶嵌模型，而不是分析几何。本文的其余部分描述了算法，并显示定性和定量的结果，讨论的优点和缺点。2. 边界点给定点云形式的映射表面，点云边界线的识别，从而边界点的检测，不是一个简单的任务。人脑能够通过简单地查看稀疏点的排列来推断点云的边界在计算机科学和计算几何中，点云是没有明确定义的边界的实体在二维域中，给定一组有限的点，检测包含云的所有给定点 的 最 小 凸 多 边 形 的 问 题 通 过 quickhull 方 法 解 决 （ Barber ，Dobkin，Huhdanpaa，1996）。它采用分而治之的方法。该方法工作良好，但只能检测凸多边形的一部分的边界点，并且仅针对一组点。 能够处理点云中的凹区域和孔的quickhull的一般化是alpha形状方法（Akkiraju等人， 1995 年）。计算几何算法库（CGAL ）（Kettner，Näher，Goodman和二维和三维点云。对于每个实数a，方法为基于半径为1=a的广义圆盘。只要存在一个半径为1=a的包含整个点集的广义圆盘，并且该圆盘具有两个点位于其边界上的性质，则在有限点集的两个成员之间画出包含所有给定点的多边形的边（α形）如果a为0，则与有限点集相关联的α形是由quickhull给出的其常规凸包。阿尔法的局限性形状方法的一个特点是其性能取决于设定值参数a。为点云产生满意结果的a值可能不适合其他点集，因为点云可以表现出不同的点密度。这种不方便性类似于当通过对像素强度进行阈值化而从灰度图像获得黑白图片时发生的情况;最佳阈值受图像的平均亮度影响。此外，当点云的点密度在整个云之间变化时，阿尔法形状的结果在某些区域中可能是令人满意的，而在其他区域中可能很差。基于核回归的非参数边缘提取方法（Öztireli等人，2009）和特征值分析（Bazazian，Casas，&Ruiz-Hidalgo，2015）。然而，这样的方法被优化用于检测内部尖锐边缘，而不是检测点云边界。本文提出的边界点检测算法（简称BPD算法）不需要定义任何阈值。对于云的每个区域，它检测尽可能多的边界点，给定区域的局部三维点云是无组织的，点的邻域比图像中像素的邻域更复杂。通常，在3D点云中，存在三种类型的邻域：球形邻域、圆柱形邻域和基于k-最近邻的邻域（Weinmann，Jutzi，Hinz，Mallet，2015）。这三种邻域基于不同的搜索方法。给定一个点P，一个球面邻域由围绕P的一个固定半径的球面中的所有3D点形成圆柱邻域由其在平面上的2D投影（例如，地平面）在围绕P的投影的固定半径的圆 图图1示出了具有5个点（A到E）的k最近邻域的点云，其中k被设置为30。属于邻域的云的点通过实心圆指示。云的其他点用空表示C. Mineo等人/计算设计与工程学报6（2019）8183^j^jPi的中心与圆心重合，不包含邻域的任何其他点。图1所示的A点和B点就是这种情况。点A和B是两个边界点，因为可以找到至少一个满足上述条件的圆（图1）。 2）的情况。为了避免不必要的计算工作，同时考虑所有可能的圆，通过二项式系数（Biggs，1979）确定所有的使用k-最近邻域并且作为所研究的点Pi始终是三元组的一部分，剩余的点（k-1）以没有重复的方式组合在一起。因此，圆的总数等于：n¼-1000！¼ 二十九！ ¼29·28 ¼406ð1Þ二号！ ·½k-1 -2]！2·27！2Fig. 1.点云，包含凹区域上的两个边界点（A和B）、内部点（C）和凸区域上的两个边界点（D和E）。界以A到E点为中心的半透明圆突出显示每个邻域的最佳拟合平面。这些平面的法线方向也通过从邻近父点向外指向的箭头示出。云的每个成员的本地云分辨率通过以下步骤来估计。给定云的一个点Pi，对于其邻域（ Pi;j）的每个点，计算该点与所有其它邻域之间的最小距离（dj;k）。的当地点云决议（bi）在Pi是估计为bi<$li<$2ri，其中li是最小距离的平均值和ri 是它们的标准差这种计算局部分辨率是鲁棒的，克服了通过光学和摄影测量方法收集的一些点云的有问题的噪声如果距离值（dj;k）按照高斯分布，则向平均值添加2ri可确保考虑97.6%的数据值，并且忽略主要离群值如果α设置得太低，则α形状方法可能无法检测具有高凹曲率的点云边界的某些部分。另一方面，它可以检测不想要的结合-如果a太高，则会有不同的分数这里描述的新方法是帽-能够检测属于凸和凹的边界点地区BPD方法利用了这样一个事实，即存在一个且只有一个尽管满足上述条件的至少一个圆的存在允许将所研究的点分类为属于点云边界，但其不存在不能用于说明该点是云的内部点。实际上，所研究的点Pi可以位于边界的凸区域上，也可以是云的内部点。在这种情况下，尽管可能存在一个半径等于或大于bi，则以圆的中心为中心的Pi的球面将总是包含邻域的一些点这是图1所示的C、D和E点的情况。1.一、对于这类点，因此当该点不能被标记为边界点时，通过上述检测算法的第一部分，该算法继续进一步的操作。根据与该点相关的法向量，将每个调查点及其邻居投影到最佳拟合平面由此产生的二维邻域云可以在极坐标中绘制，其中Pi位于图的极点 图图3显示了点C、D和E及其相邻点的极坐标图。Pi以红色显示，其相邻点以蓝色显示图中的蓝色和红色虚线。 3分别突出显示由邻域中的点所跨越的角扇区的最小和最大角度。BPD算法的最后步骤背后的基本思想是，如果不可能找到围绕云P1的点并穿过相邻点的路径，则云P1的点是边界点。极坐标图上的每个点由到极点的距离（径向坐标，R）和角坐标（h）确定。给定一个邻域，所开发的算法创建一个围绕极点处的父点的路径采用了一种递增的方法相邻点的所有径向和角坐标都被归一化，使得第j个相邻点的坐标为：通过3D空间中三个给定点的圆给定未分类点Pi，计算经过Pi及其邻域内任意两点的所有圆的圆心和半径。如果存在至少一个半径等于或大于bi的圆，并且如果用于rRj-RminR最大值-R最小值#hj-hminh最大-h最小ð2Þð3Þ图二、A和B标记为边界点。84C. Mineo等人/计算设计与工程学报6（2019）81P¼J JJ JP¼j j图三.点C、D和E及其相邻点的极坐标图。实线和虚线说明了算法的应用。其中Rmin、Rmax和hmin、hmax分别是径向坐标和角坐标的最小值和最大值。为了为了选择周围路径的起始点，将特征参数（c）给予每个邻居，使得：CJ #j-#bis j-40其中，θbis是平分包括所有邻居的角间隙的方向的归一化角度（在hminHmax）。c值最小的相邻点，如计算的由方程式（4），被选作周围路径的起始点从起始点开始，算法通过连接邻域的其他点来进行。 交叉的相邻点将从可用点列表中删除。通用第p个剩余点的特征参数计算为：3. 边缘重建将BPD算法应用于图1所示的点云样本可以找到所有边界点，如图4中的空心圆所示。此外，内部圆孔的4个边界点，其半径刚好高于局部点云分辨率，如预期的那样被检测到。需要对检测到的点进行聚类，以便将属于同一边界的点分组在一起。此外，每个簇的点需要正确排序。这些任务可以通过现有的算法来完成。例如，可以通过能够解决所谓的旅行商问题（TSP）的算法来对聚类的点进行排序。给定一个随机的点列表和每对点之间的距离，TSP的解是最短的cprp#p-#最后·c]与每个点只相交一次并返回原点的路径点（Schrijver，2005年）。因此一关闭边界路径其中，#last是最后交叉点的归一化角坐标，并且如果sgn#p-#last=sgn#last-#last-1，则c是等于-1的因子，否则c等于1。因子c便于选择不强制改变周围方向的点。例如，如果上一个选定点产生顺时针旋转，任何逆时针旋转都是不利的。具有c的最小值的邻居，如在Eq. （5），成为路径的新的最后一点。相邻节点的增量连接跟踪极点周围的跨度角。所考虑的角度增量之和与他们的签署（一个Da）和的总和的他们的绝对值Da）每次更新一个新的点，选择在起点之后。当不再有相邻点或当s>2p。如果P2p，则研究点是云的内部点（例如图3中的点C），否则它是边界点（例如图3中的D和E）。增量算法的停止条件（s>2p）避免了多余的计算工作，因为通常可以推断点是否属于边界而不链接所有邻居。图3中的实线示出了直到s>2p所创建的环绕路径。例如，可以确定C不属于边界，仅链接29个邻居中有10个，因为a>2p。可以说，D是一个边界点，通过连接29个相邻点中的18个;它的结果是jaj2p，尽管绝对角增量之和是s>2p。<总之，这里描述的BPD方法是能够确定点Pi是否属于凹边界当局部曲率高达1 =bi时，该方法还能够在孔半径小至bi时推断点是否属于点云中的孔的边界（例如，图1中的点B）。由于bi是局部分辨率，因此该方法在具有可变点密度的点云上工作良好从每个集群中获取。这些边界由通过线段（见图4中的虚线）连接的有序点给出，在某些区域可能非常参差不齐。因此，很明显，这种边界不适合修剪从点云获得的表面网格。边界曲线需要平滑以更好地类似于真实的表面边界线。本文介绍了一种新的原始边界平滑算法RBS算法，通过对原始边界的精确平滑来改善曲面点云边界的重构。见图4。通过对检测到的边界点（锯齿状虚线）和重建的边缘（实线）进行聚类和排序，将闭合边界划分为边缘。C. Mineo等人/计算设计与工程学报6（2019）8185¼ð Þ¼ð Þ我¼3.1. 关键点在对闭环边界曲线应用任何平滑算法之前，有必要强调应保留一些检测到的边界点的位置。对于边界角来说就是这种情况，其中存在边界方向性的急剧变化实际上，这些点通常在CAM应用中的参考系统定义中起着至关重要的作用，用于开发精确的操作，其中需要正确配准因此，边缘重建算法的第一步旨在检测这样的关键点。给定闭合边界路径的第i个点，如果所研究的点、前一点和后一点的圆的半径小于局部点云分辨率的值bi（作为cal），则该点被标记为角点。在检测算法中计算这种方法能够识别-从P1到P5的角点，在图4中用星号突出显示。这里值得注意的是，虽然可以通过对每个调查点的两个边界线段之间的角度应用阈值来找到拐角（Ni，Lin，Ning，Zhang，2016），但这种方法是有利的，并且适合于使用具有可变密度的点云所识别的角用于将闭合回路边界划分为对应于表面几何体的边的区段。图4中的云的外部边界点被分组为5个边缘。4个内部边界点被分组在一个单个闭环边缘中，因为在那里没有发现角。3.2. 传统曲线光顺方法的局限性每一条边缘都可以通过拟合多项式曲线来平滑。多项式曲线拟合是一种常见的平滑方法，其功能也在CAD/CAM商业软件应用程序（例如Rhinoceros®）中实现。曲线拟合是用数学函数逼近点的模式的过程（Arlinghaus，1994）。拟合曲线可用于推断没有数据可用的函数值（Johnson&Williams，1976）（例如，在采样点之间的间隙中）。的曲线拟合的目的是根据自变量（或自变量的向量）x的值来模拟因变量y的期望值。通常，y的期望值可以建模为n次多项式函数，从而基于截断泰勒级数产生通用多项式回归模型域它用于时间序列的频谱分析，并允许应用高通或低通滤波器，以分别衰减低频或高频。这里，FFT被应用于边缘点笛卡尔坐标的图案，以使得能够应用能够改善边界边缘的平滑度的低通滤波器。FFT对空间模式（在笛卡尔域而不是时域中采样的波形）的利用并不新鲜（例如，它已用于图像处理）（Gonzales Woods，1992）。然而，没有记录的FFT被应用于表面边缘重建的问题。本文描述了FFT对该问题的适应的细微差别考虑一个具有N个样本的序列x k。此外，假设在0和N-1之间的范围之外的级数是扩展的N-偶次级数，对于所有k，它是xkxk。该系列的FFT将被表示为X k，它也将具有N个样本。FFT变换意味着序列索引和频域样本索引之间的特定关系。对于常见的情况，其中FFT被应用于表示长度为T的时间序列的序列，频域中的采样间隔为fs1/2=T。变换后的序列的第一个样本X0对应于fNy^N=2T的频率样本称为奈奎斯特频率。这是最高频率的成分，应该存在于FFT的输入序列中，以产生未损坏的结果。更具体地，如果不存在高于奈奎斯特的频率，则可以从频域中的样本精确地重构原始图案。对于边缘重构的空间问题，给定FFT被应用于边缘笛卡尔分量图案，绘制为曲线距离（d）的函数，空间频率是正弦分量（如由FFT确定的）每单位距离重复的频率的量度。半径（R）和长度（2pR）的圆边的任何笛卡尔分量的空间频率域表示仅包含一个频率组件F C1 =2 pR.因此它是可能推导出，表示第i点对于具有Ri的边缘，在该点处出现的主空间频率等于fi1= 2pRi。根据奈奎斯特定理，当在时域中对模拟信号进行采样时，采样率必须至少等于2fmax，其中fmax是最高频率分量。应用于空间域的奈奎斯特规则意味着bi（局部点云分辨率）限制了在第i个点处可能重建的最小边缘半径。可能重建的最小半径将是与长度为2pbi的圆周相关联的半径，y¼a0a1xa2x2.. . anxn2个点，对应于空间频率fω1/2 = 2pbi/ 1=pbi。最大无混叠空间频率其中e是具有零均值的随机误差考虑到一个组成部分将是：边缘和目标多项式函数的阶，可以计算拟合函数的系数的限制FMax<$fω=2< $1= 2pbi：107Ω这种平滑方法的缺点在于目标函数的阶数通常是未知的，并且曲线拟合仍然是用于边缘重建的耗时的迭代试错过程。当没有选择拟合多项式函数阶数的理论基础时，可以用由B样条之和组成的样条函数拟合边缘（Knott，2012）。B样条相交的地方称为节点。应用这一过程的主要困难是确定使用的结的数量和它们应该放置的位置（de Boor，1968）。3.3. 基于FFT的重建本文提出的RBS算法的最后一步，介绍了一种基于快速傅立叶变换（FFT）的鲁棒方法。FFT是将波形中包含的信息从时域转换为频率在第i个点处可能重构的最小边缘曲率半径将等于Rmax¼bi。的地块在图5 a和5b分别考虑的图4中P2和P3之间的边缘和云的闭合环内部孔边缘的x分量图案。图案被绘制为边缘的归一化曲线距离的函数（dωd=D，其中D是边缘的总长度）。原始模式由穿过x分量样本的虚线（通过圆形圆圈显示）给出，非常参差不齐。图5阐明了如何从给定边缘的每个笛卡尔分量的原始图案图案首先沿着纵坐标轴的方向平移，以将图案的第一点移动到绘图的原点然后将图案旋转角度a，以移动水平轴上的图案将所得到的图案的副本反转、翻转并附加到末端;它构成86C. Mineo等人/计算设计与工程学报6（2019）81Þ¼ð·Þ¼图五.创建周期性波形以将空间FFT应用于开放边缘（a）和闭合边缘（b）的x分量图案一个互补的部分与原始图案的平移和旋转版本一起创建一个周期（图5a）。由于FFT假设输入模式的采样率恒定，因此原始随机间隔的样本被插值的等间隔样本替换。适当地选择内插样本的数量（Np）以给出恒定的采样间隔（ds，等于或小于最小原始采样距离。为了保证良好的滤波性能，必须具有足够的空间频率分辨率。 因此，重复该周期以在FFT的输入波形中获得最少1000个样本，从而给出f s的频率分辨率1 = 1000 d s。因此，应用低通滤波器，消除所有空间频率。频率分量高于fmax，如等式中所表示（七）、这产生了边缘分量的平滑波形图5a中所示的FFT输入波形被人工构造以过滤包括在P2和P3之间的开放边缘的x分量，它的平均值为零原始边缘的端点位于水平轴（均值线）上，不受低通滤波的影响保留了端点的笛卡尔分量值波形的第一部分（直到原始图案的总长度D的部分）旋转负a并平移回原始位置。通过对边界的所有边的笛卡尔分量进行滤波，得到光滑边界原始边缘端点的保存确保了当边界由多个边缘组成时，两个连续边缘共享公共点。因此，边链形成闭合边界。如果边界仅由一个闭合边形成，如图4中的内部孔边界的情况，则其每个笛卡尔分量的端点具有相同的值（a0）。此外，构成周期的补充部分仅仅是笛卡尔分量模式的水平平移副本（在其端点被带到水平轴之后）。原始图案的复制品不反转也不翻转以创建互补部分（图5b）。封闭边的所有点都受到过滤的影响的相对于样本点云的边界的平滑边缘通过图1中的实线曲线示出。 四、4. 结果和表现本文的这一部分分析了通过使用引入的BPD和RBS算法所获得的结果。计算性能也检查和定量的数字 图 6示出了算法步骤的示意性概述。粗虚线周长包含本文介绍的新算法组件。BPD算法（图1） 6a）允许将表面点云的未标记点分为两组：边界点和内部点。通过现有算法对边界点进行聚类和排序，以构成原始闭合边界（锯齿状）。RBS算法（图6b）识别边界角，并将每个闭合边界划分为构成边缘。通过基于空间FFT的滤波来平滑每个边缘。所介绍的算法的一个关键优点是，它们不是基于任何阈值，可以适合于一些点云，但不适合于其他人。BPD能够标记所有点，观察每个点的云的局部分辨率。基于FFT的边缘重建消除了为最佳多项式曲线拟合定义特定多项式函数阶数在本文介绍的方法中，最好的边缘平滑性能也确保通过应用空间低通滤波与频率定义在每个边界点作为本地云分辨率的函数。为了显示新算法的潜力，空气-通过坐标测量机扫描了640 mm长和300 mm宽（平均）的工艺涡轮发动机风扇叶片FARO Quantum机械臂与激光轮廓标测探头结合使用（Monchalin，Neron，Bouchard，Heon，1998）。该3D扫描设备具有体积最大偏差±74m。对叶片表面进行扫描，以获得均匀点云与circa14千点（大约每平方厘米72点）。对云点进行抽取以获得四种不同的点云版本，目标分辨率分别等于4、8、16和34 mm。生成的点云具有可变的点分辨率，在2和34mm之间。这样生成的点云允许在受控情况下测试算法为了引入明确界定的内部边界，从云中删除了在以固定位置为中心、半径等于16、32和64 mm的三个球体内发现的点。因此，每个云呈现三个孔（H1、H2和H3），其半径近似等于原始生成球。所得到的五个点云由图7中的顶行图示出。这些图通过较暗的圆形点标记显示检测到的边界点。外部和内部边界点的检测符合预期。在点云中可检测到的孔的最小半径取决于点云分辨率，如第2节所述。在图1的云中仅检测到16 mm和32 mm半径孔（H1和H2）的四个点。 7 c和7 d，因为这些云的分辨率接近它们的半径。 H1无法在34 mm分辨率的云上检测到（图1）。 7 d）。图8显示了在斯坦福兔子（Turk Levoy，1994 a）中检测到的边界点，斯坦福兔子是一种开源计算机图形测试网格模型，通过范围扫描获得（Turk&Levoy，1994 b）。与许多研究人员使用此模型类似，作为表面重建算法的输入，网格连接性已被剥离，顶点已被视为无组织的它提供35，947个点，平均分辨率为1.2 mm。边界C. Mineo等人/计算设计与工程学报6（2019）8187图六、算法步骤的示意性总结：边界点检测（a）和边缘重建（b）。图7.第一次会议。对于具有4（a）、8（b）、16（c）和34 mm（d）的固定分辨率以及具有2和34 mm（e）之间的可变分辨率的点云，检测到的点（顶行）和重建的边界边缘（底行）88C. Mineo等人/计算设计与工程学报6（2019）81见图8。用基于主成分分析的方法检测斯坦福兔子上的点（Turk& Levoy，1994a）（Gumhold等人，2001）（a）和BPD算法（b）。使用基于主成分分析（PCA）的方法检测点（Gumhold等，2001）（图8 a）和新的检测算法（图8 b）。 8 b）。为了理解性能的差异，区分边界点和边缘点是很重要的;后者位于有尖锐波纹的区域PCA方法检测到的点要么是尖锐的折痕线上，要么是在点云孔的边界线上。BPD算法的目标是专门找到边界点;因此它在兔子的基础上找到了两个洞，来自原始粘土模型（它是一个空心模型）。应该注意的是，BPD算法不应该检测由PCA检测到的额外边缘和折痕点（例如，在兔子的耳朵中）。它的目的是检测边界点（孔或点密度急剧下降的区域周围），以便可以重建边界边缘并修剪镶嵌曲面BPD算法能够检测另外四组边界点（一组在兔子胸部下方，一组在兔子前腿之间，两组在基部上），对应于具有较差范围扫描覆盖的区域的边界线这些区域中最小的两个区域没有被PCA方法检测到，这表明BPD算法对于边界点的检测如何图的底行图。 7显示了重建的边界-ary边缘。通过观察边缘的平滑性，证明了基于FFT的滤波算法的有效性内孔的平滑边界由单个闭合边给出，忠实地再现了原始生成球体和叶片表面之间的理论相交的圆度只有H1和H2的边界（仅通过四个检测点重建）显示出可见的失真。 虽然解释网格修剪的工作原理不在本文的范围内，但重构的边界边可用于修剪泊松网格，从而生成图1中突出显示的干净边界网格。7.第一次会议。使用基于具有32 Gb RAM的Intel®测试通过MATLAB® 2016 a进行，在Windows 10 64位操作系统上运行。表1报告了将BPD算法应用于图7中给出的点云所获得的定量结果。表的初始行报告最小、平均、最大云分辨率，（b）及其标准差（r），然后是云中的点因此，该表给出了由检测算法检测到的边界点以及其完全执行所花费的对于所有检查的点云，经过的时间始终小于3秒。通过一些3D扫描方法获得的点云受到面外噪声的影响，这意味着采样点偏离了它们位于表面上的理想版本。重要的是估计所提出的检测算法对这种噪声的容忍程度。因此，检测算法被重复应用于点云的版本，其中增加的随机噪声被添加到原始点。 通过沿局部k-邻域最佳拟合平面的法线方向移动每个点来人工获得噪声云。每个点移动的距离等于当地云分辨率的百分比从0%开始，在检测算法的每次重复时，噪声百分比增加1%在其之后未检测到至少一个边界点（假阴性）的最大百分比值表示为X。X的值大约25%的图的所有云。7.第一次会议。如果噪声百分比为如果增加到X以上，则云的一些内部点可能被标记为边界点（误报）。将内部点中的至少一个在其之后被标记为边界点的最大百分比值表示为W。W的值在表1均在75%以上因此，检测算法非常表1从BPD算法的应用中获得的性能云一BCDe最小b[mm]3.827.7715.5332.291.98平均b[mm]4.198.4416.8734.523.71最大b[mm]4.859.3618.9840.4234.86SD（r）[mm]0.110.200.521.144.30数量的点12,30930957912037458边界点63231515672397检测时间[ms]26069443402891892X[bi%]百分之二十五百分之二十四百分之二十七百分之二十五百分之二十六W[bi%]百分之八十百分之一百一十三百分之八十四百分之一百五十七百分之七十五C. Mineo等人/计算设计与工程学报6（2019）8189对于低于云分辨率的25%的面外噪声是鲁棒的，并且当噪声低于大约75%时，它可以产生令人满意的结果。当噪声值在云分辨率的25%和75%之间时，检测算法将错过一些边界点，但不会生成离群值。图9针对16 mm平均分辨率点云，将多项式拟合和二阶和三阶B样条边缘与通过新RBS方法重建的边缘（如图6b中最粗虚线周界内所述）进行比较。显然，多项式拟合产生不令人满意的边缘，特别是对于内部边界。B样条边存在过度的扭曲，因此平滑性差。表2给出了RBS算法性能的定量结果，与三阶多项式拟合和B样条相比，对于图1中的所有点云。7.第一次会议。虽然新的基于FFT的算法的执行时间总是一个数量级高于多项式拟合和B样条计算的时间，由新方法产生的光滑边缘拟合的表面轮廓比多项式拟合和B样条。该表报告了边界点与平滑边缘之间的距离以及重建表面网格与重建边缘之间的距离的平均值、平均而言，通过新方法计算的重建边缘拟合边界点比三阶多项式边缘好4.7倍此外，他们遵循重建的表面网格轮廓比多项式拟合边缘好77%。虽然B样条似乎比新方法更好地遵循重建的网格，但三阶B样条不会产生显著的平滑效果。图9.第九条。多项式拟合重建边缘（红线）与二阶和三阶B样条边缘（黑线）的比较90C. Mineo等人/计算设计与工程学报6（2019）81表2RBS算法的性能，与三阶多项式拟合相比马克斯区至点[mm] 0 0 0 0平均距离筛孔直径[mm] 0.05 0.11 0.24 0.460.45马克斯区筛孔直径[mm] 0.78 1.12 1.35 3.08 3.30原始边界点; B样条和点之间的距离大约等于0并不是良好性能的标志。多项式和B样条边缘拟合边界点和重建表面的精度可以通过增加函数的阶数来提高，但这会影响计算函数系数所需的时间。此外，高阶多项式经常遭受数据点之间的严重振铃。RBS方法不需要指定任何参数就可以重建最佳边缘，这与多项式和B样条拟合中的函数阶不同。5. 结论从点云生成的镶嵌曲面通常显示不准确和锯齿状的边界。这可能导致公差误差和问题，如机器抖动，如果模型用于正在进行的制造应用程序。这就是为什么许多现有的商业计算机辅助制造（CAM）应用不能使用镶嵌模型的原因本文提出了一种新的算法来细化由三维扫描点云数据得到的网格曲面的边界。BPD算法允许将表面点云的未标记点分为两组：边界点和内部点。现有的检测技术被优化以检测属于尖锐边缘和折痕的点。BPD算法是针对边界点的检测，它能够做到这一点比现有的方法。RBS算法识别边界角点，并将每个闭合边界划分为构成边缘。通过基于空间FFT的滤波来平滑每个边缘所介绍的算法的一个关键优点是，它们不是基于任何阈值，可以适合于一些点云，但不适合于其他人。基于FFT的边缘重建消除了为最佳多项式曲线拟合定义特定多项式函数阶数的问题对该算法进行了测试，以分析结果并测量点云的曝光时间，这些点云是由具有不同数量的构件点的涡扇发动机涡轮叶片上的激光扫描测量产生的。通过添加人工噪声，证明了BPD算法对低于25%云分辨率的面外噪声具有很强的鲁棒性当噪声值在云分辨率的25%和75%文中还给出了RBS算法性能的定量结果。通过新方法计算的重建边缘符合边界点比多项式边缘好4.7倍。此外，他们遵循重建的表面网格轮廓与多项式拟合边缘相比，提高了77%确认这项工作是制造和再制造自主检测（AIMaReM）项目的一部分，该项目由英国工程和物理科学研究委员会（EPSRC）通过EP/N 018427/1资助。作者还要感谢Maxim Morozov博士获得了本文中所考虑的涡轮风扇发动机涡轮叶片的点云。附录A.补充材料与本文相关的补充数据可在https://doi.org/10.1016/j.jcde.2018.02.001的在线版本中找到。引用Akkiraju，N.，Edelsbrunner，H.，Facello，M.，Fu，P.，Mücke，E.，瓦雷拉角，巴西-地（1995年）。Alpha shapes：Definition and Software. 第一届国际计算几何软件研讨会集（p. 第六十六章）Arlinghaus，S. （1994年）。曲线拟合实用手册。 Press.巴伯角B、Dobkin，D. P.的人，&Huhdanpaa，H.（1996年）。凸壳的快速算法。ACMTransactions on Mathematical Software（TOMS），22，469-483. Bazazian，D.，卡萨斯，J.R.，Ruiz-Hidalgo，J.（2015）.散乱点云中快速、稳健的边缘提取。在：国际会议数字图像Computing：Techniques and Applications（计算机技术与应用）第1-8段）。Beard，T. （1997年）。 从STL文件加工。 现代 机 商店， 69，90-99。伯杰，M.，Tagliasacchi，A.，谢韦尔斯基湖M.，阿利斯，P.，Guennebaud，G.，莱文，J。一、等（2017）。基于点云数据的曲面重构研究综述。计算机图形论坛，301-329。Biggs，N. L.（1979年）。组合数学的基础。Historia Mathematica，6，109-136.Calakli，F.，&陶宾湾（2011年）。SSD：平滑符号距离表面重建。计算机图形论坛，1993柯利斯湾（1999年）。从范围扫描到3D模型。ACM SIGGRAPH ComputerGraphics，33，38-41.deBoor，C. （1968年出版）。关于奇次样条插值的收敛性 Journal ofApproximationTheory，1，452-463.德劳奈湾（一九三四年）。“Sur la sphere vide， ”Izv. 阿卡德。Nauk SSSR，Otdelenie Matematicheskii i Estestvennyka Nauk（Vol. 7，pp. 1-2）。Fleishman，S.，Cohen-Or，D. &席尔瓦角，澳-地T.（2005年）。具有尖锐特征的稳健移动最小二乘拟合。在ACM 图形交易（TOG）中，（第0卷，第100页）。544-552）。冈萨雷斯河，巴西-地C.的方法，&伍兹河，巴西-地E.（1992年）。数字图像处理。Reading，MA：Addison& Wesley Publishing Company.Gumhold，S.，王，X.，&麦克劳德河S.（2001年）的第10页。点云特征提取。在IMR。欣克斯，T.，卡尔，H.，Truong-Hong，L. &Laefer，D. F.（2012年）。通过基于点的体素化将点云数据转