基于非结构化Delaunay网格的2D点云数据优化技术

可在ScienceDirect上获得目录列表计算设计与工程杂志首页：www.elsevier.com/locate/jcde计算设计与工程学报6（2019）316与输入尺寸无关的2D点云数据Neha Singha，Soha，Tathagata Raya，Soha，Sohu Parimib，Srivastava Kuchibhotlaba印度海得拉巴Birla Institute of Technology and Science Pilani，Hyderabad Campus，Hyderabad，bBirla Institute of Technology and Science Pilani，Hyderabad Campus，Hyderabad，India阿提奇莱因福奥文章历史记录：收到2018年收到修订版，2018年12月8日接受，2018年在线提供2018年保留字：网格生成Delaunay三角剖分点云数据曲线重建预处理技术A B S T R A C T本文描述了一个框架，以产生一个非结构化的Delaunay网格的二维域的边界指定的点云数据（PCD）。假设PCD是从没有边界定义的光滑1-流形中采样的，并且是显著稠密的（至少s-1）。sampled（sampled）1）。<目前，这种域的网格化需要两个明确的步骤，即从PCD中提取模型定义，并使用模型定义来指导非结构化网格生成。对于密集采样的PCD，曲线重建过程取决于输入PCD的大小，并且可能成为耗时的开销。我们提出了一种优化的技术，绕过显式步骤的曲线重建隐式访问的模型信息，从一个良好的采样PCD。这样生成的网格将是最佳的，因为网格的精细度不是由PCD的采样决定的，而是仅由基础曲线的几何复杂性决定的。该框架的实现和实验结果表明，与传统的方法相比，该框架在费用上有了显着的改善。本文的主要贡献是规避了显式耗时的边界计算步骤，边界计算是PCD采样大小的函数，并且直接生成网格，其复杂性由域的几何形状决定©2018计算设计与工程学会Elsevier的出版服务这是一个开放在CC BY-NC-ND许可证（http://creativecommons.org/licenses/by-nc-nd/4.0/）下访问文章1. 介绍在许多科学和工程应用中，可以使用光滑的闭合曲线来定义二维对象的形状，但是表示该曲线的数据是使用有限的点集PR2来捕获的。这样的数据集出现在GIS（地理信息系统）、计算机图形、计算机视觉、计算几何和逆向工程问题中的各种应用工业CT（计算机断层扫描）扫描图像的单个切片是这样的数据集的示例，其中感兴趣区域周围的像素可以被解释为有限的点集（ Yang ， Ohtake ，Moriguchi，&Suzuki，2014）。有两个众所周知的问题与这样的数据集;即，曲线重建和内部的网格化根据应用和数据集的不同，网格化问题首先需要解决重建问题。曲线重构和网格生成都是当前研究的热点由计算设计与工程学会负责进行同行评审。*通讯作者。电 子 邮件 地 址 ：singhgaur. gmail.com ， p2012514@hyderabad.bits-pilani 。 ac.in（N. Singh），rayt@hyderabad.bits-pilani.ac.in（T.Ray），parimi@hyderabad. bits-pilani.ac.in （C. Parimi）。research. 由于数据中的噪声或曲线的过采样，曲线重建可能并不容易，并且可能需要手动干预在这项研究中，网格封闭的域没有明确的曲线重建的点云在一在图像的情况下，有基于四叉树的方法可以实现这一点。然而，它们产生轴对齐的网格，其具有自身的缺点，例如在网格对齐方向上的累积误差的放大，并且通常这种网格太精细而不能开始。此外，对于来自平滑闭合曲线的任何给定的良好采样的有限点集，不一定是单独的图像，这种绕过曲线的显式重建的想法以前没有被研究过。在这项研究中，我们提出了一个算法框架，该算法从一个简单的光滑封闭曲线中获取一组足够密集的采样点P，并在不显式重建整个曲线的情况下对封闭区域进行网格化据观察，密集采样的点云数据固有地捕获其被采样的曲线的拓扑和几何形状。这种观察导致了直接网格生成方法的想法，而无需为点云构建显式模型定义此外，生成的网格需要具有良好的质量，其中质量是使用标准度量来定义的，例如外接圆半径与三角形的最短边长度的https://doi.org/10.1016/j.jcde.2018.12.0012288-4300/©2018计算设计与工程学会Elsevier的出版服务这是一个在CC BY-NC-ND许可证下的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。N. Singh et al./ Journal of Computational Design and Engineering 6（2019）316317任何其他质量标准也可以纳入这一框架。本文提出的新方法直接从点云使用Delaunay三角剖分网格的身体。基于Delau- nay的网格生成方法由于有很强的理论保证，在过去的二十年里得到了广泛的然而，基于Delaunay的算法的输入主要是模型定义。从PCD中提取定义基础曲线的模型定义本身是一个研究问题，并且由于其取决于PCD的大小，因此计算成本很高有可证明的算法s采样曲线的正确曲线重建，其中s是a参数来捕获采样间距离，从而捕获PCD的密度。此外，输入点云数据可以是高度密集的，并且如果网格生成方法如在一些应用中所见的那样依赖于输入点云的密度，则它可能最终在一开始就产生极其精细的网格。对于大多数应用，如FEM（有限元法），这种细化是不需要的，因为几何复杂性可以捕捉到一个粗糙的网格。在所提出的框架，而不是一个明确的计算模型的定义，网格是通过利用曲线重建算法在附近的某些重要的点对于无噪声且至少s采样的PCD，Dey和Kumar（1999）给出的基于Delaunay的曲线重构方法可以用于该框架。如果数据有噪声，则可以实施适当的方法，例如基于最佳传输的曲线重建方法（DeGoes，Cohen-Steiner，Alliez，&Desbrun，2011）这个想法已经分析过了并且在此实现为无噪声且至少s采样PCD。这种算法被称为PCMesh（点云网格）。这项工作的主要贡献是，该框架不需要对整个输入进行曲线重构，并且由于其局部重构曲线，因此在计算上是局部重建和交叉计算与voronoi边缘也是这项工作的贡献（在第5节中描述）。2. 相关工作本节简要概述了多年来提出的各种曲线重建算法和网格生成算法的类型这里的重点是基于Delaunay2.1. 曲线重建曲线重建背后的动机是扫描设备的进步随着对各种形状和大小的对象进行更有效的采样20世纪80年代，出现了一些基于几何图的构造算法。影响图（Avis Horton，1985），b-骨架（KirkpatrickRadke，1985）和a-形状（Edelsbrunner，Kirkpatrick，Seidel，1983）是这些方法的例子从那时起，已经提出了几种曲线重建算法早期提出的重建算法只适用于平滑和均匀的采样点云。α-形状（Edelsbrunner等人，1983年），r-规则形状（Attali，1998年）和 EMST 欧 几 里 得 最 小 生 成 树 （ DeFigueiredo& de MirandaGomes，1994年）是这样的方法的例子。首先提出了一种非均匀采样曲线的算法Amenta，Bern，and Eppstein（1998）. 这是一个基于Delaunay的算法 ， 只适 用 于 封 闭的s 样 本 曲线 ， 其 中s60 ： 252.Dey 和 Kumar（1999）改进了这个算法，它适用于采样密度s1= 3。<该算法由 Dey ， Mehlhorn 和 Ramos （ 1999 ） 进 一 步 发 展 ， 通 过 使 用Gabriel图的概念来处理开放曲线。Giesen（1999）提出了使用旅行商路径（TSP）方法来处理非光滑和均匀采样的单个闭合曲线的重建问题Althaus和Mehlhorn（2001）去掉了均匀采样条件的要求，发现TSP（Giesen，1999）方法可以在多项式时间内构造。Dey和Wenger（2002）进一步改进了这种方法，以处理具有端点但不相交的非相交开放曲线。该算法不提供任何理论保证。Funke和Ramos（2001）提出了一种算法，该算法利用新的采样条件输出多边形重建，该采样条件依赖于重建曲线而不是原始曲线。它适用于一组有角和端点的曲线. Liu，Yang，and Wang（2005）提出了一种重构B样条曲线的算法，以处理具有尖角的自相交曲线。Ruiz、Vanegas和Cadavid（2011）给出了一种算法，该算法适用于自相交曲线，并且能够处理噪声样本。De Goes et al.（2011）提出了一种基于运输的最优方法，用于处理尖锐的交叉点和拐角，以及一定程度上的噪声和离群值。Cheng等人（2005）给出了一种可以处理噪声的非相交光滑曲线算法。Wang等人（2014）还提出了一种从分散的噪声点集重建的鲁棒算法。Peethambaran，Parakkat和Muthuganapathy（2015）提出了一种基于Voronoi的标记方法用于曲线重建。该算法适用于尖角，可以处理异常点和曲线的集合。Parakkat和Muthuganapathy（2016）提出了一种算法，可以处理尖角，离群值，开放曲线和带孔的对象。最近，Parakkat，Pundarikaksha和Muthuganapathy（2018）扩展了基于Delaunay的技术，用于在草图中对笔划进行分组，并使用适当的曲线生 成 了 有 意 义 的 图 形 。 Parakkat ， Methirumangalath 和Muthuganapathy（2018）还提供了一种方法，适用于具有离群值和恢复 自 相 交 曲 线 的 简 单 和 噪 声 点 集 数 据 。 Ohrhallinger 和 Wimmer（2018）提出了一种用于从高噪声点集数据重建的无参数方法。2.2. 网格生成将给定区域离散成简单的元素，这些元素连接而不产生间隙或重叠，称为网格生成。网格生成的算法可以分为：前沿推进，四叉树，和基于Delaunay的网格生成。在Advancing Front中，三角形网格是从边界处的初始三角形集合逐渐 向内 构建 的 （ Owen， 1998 ） 。Bern，Eppstein ， and Gilbert（1994）使用了四叉树数据结构，将平面几何划分成一个正方形盒子的树，直到满足某些条件。该算法为三角形的质量提供了理论保证以Boris Delaunay在1934年的工作命名（Delaunay，1934），点云的Delaunay三角剖分是一种独特的三角剖分，给定四个或更多点不是共圆的。这种三角剖分具有这样的性质：任何三角形的外接圆都是空的。Chew（1989）给出了第一个可证明的Delaunay精化算法，该算法以多边形域为输入，生成的三角形网格的角度都在30°到120°之间。1992年，Ruppert（1993）给出了一个Delaunay加细算法，保证了良好的分级和大小最优性。1995年，Ruppert提出了另一种Delaunay加密算法，该算法生成具有有界长宽比的平面直线图的网格（Ruppert，1995）。基于Delaunay的网格划分技术在三维网格中得到了广泛的应用。详细318N. Singh et al./ Journal of Computational Design and Engineering 6（2019）316ð ÞðÞðÞ基于Delaunay的网格划分技术的历史由Cheng、Dey和Shewchuk（2012）描述。在2016 年，Engelda （2016）描述了一种称为Frontal-Delaunay的混合方法，该方法使用先进的前沿和Delaunay细化算法在分段光滑域中生成网格。更多的方法被开发出来，以提高质量的元素的2D网格所提出的汗等人。（ 2018年）。3. 术语考虑一条简单的光滑闭曲线C。设P是位于C上的点的集合。P被称为从C采样的点云。在实践中，这种采样可以是高度密集的噪声。在这项研究中，我们假设PCD是无噪声的。本文算法的目标是在给定P的情况下，生成C所包围区域的尺寸最优的三角形网格（Delaunay）。该算法的前提条件是P是高稠密的。对于实验，我们假设P至少是C的s-样本，定义如下：C的s-样本是对任意点x2C和给定常数s1的采样，存在点p2P使得，sfq-ska-qk12意味1意味Ska-qk>1s fq 14kq-Lk¼D最小值ð4Þ如果q2C满足Eq. （4）并且选择点a2C使得Eq.（14）满足，则存在至少一个点b2P满足等式（15）。现在要定义一个外部阈值，使得至少一个点（5）和（7）对于每个q。因此，最小外阈值宽度KL是b2P内部这阈值存在时，满足以下定义：给定宽度DL且qi2C，i = 1至n为条件：所有满足Eq. （四）kb-LkPD5000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000最大n2sf q15min设a是曲线C上的一点，使得最小¼1/11秒ði Þ ð Þ一个点集P，K被定义为所有的点，使得ka-LkPD最小值为600 L L现在，基于s-采样的定义，至少存在一个点b2P，使得，ka-bk 6s fa 7假设点h2P存在于q;h2PD，因为kh-Lk 1/4DL。kp-Lk 6KminDmin16定义PK的Delaunay三角剖分为sK。请注意，NN地壳将在P DP K上进行评估，这种近似的结果称为用于相交计算的C~DsK。我们将CK定义为应该注意的是，这是曲线C的所有交叉点的包络情况，其中L=Ve= h，因为h被放置在q处导致CK¼ fx2Cjkx-Lk 6KL最小值g 17最大阈值，因此包括所有相关情况。点h应该使得ka-hk>sfa，使得存在abPRPD满足等式（七）、因此，为了满足这一点，在图4中，我们得到ka-qk>s fa 8根据Lipschitz连续性fq 6fa ka-qk9意味sfq6 sfaska-qk10意味sfap sfq- ska-qk11从Eqs （8）和（11）DLN. Singh et al./ Journal of Computational Design and Engineering 6（2019）316321ð Þ因此，在计算Voronoi边缘的交集中涉及的步骤Ve和CK如下。1. 对Voronoi边Ve附近的点云P的子集进行Delaunay三角剖分以获得sK2. 对内阈值中的所有点进行NN Crust，以局部地获得C~DsK。 这样做是为了忽略NN外壳在三角测量边缘处的虚假结果。3. Voronoi边缘Ve的交点通过在内阈值内的所有局部NN地壳边缘6. 执行所有算法都已使用CGAL库（CGAL项目，2017）在C++中实现。硬件配置为Intel（R）Xeon（R）CPU E5-2695 v4@2.10GHz，32 GB RAM。在322N. Singh et al./ Journal of Computational Design and Engineering 6（2019）316J J在前一节中，阈值大小被定义为s的函数，但是实际上该值是未知的，并且也不容易检测本节描述了阈值在实践中是如何选择的为了检测来自阈值内的P的点，如下所述实现四叉树：6.1. 阈值大小虽然第5节讨论了阈值大小的数学要求，但PCMesh的实现将需要一种策略来计算给定问题的阈值大小。由于每个阈值必须在每个交叉点上至少有一个点，因此将数量Nloc定义为在每个交叉点处落入每个阈值的点的用户定义的近似数量。P是集合P中的点的数量。实施阈值（Dimp）定义为2 jx-xjj y-yjerk图五. 喷嘴的CT扫描。将PCMesh的效率与使用显式曲线重建对PCD内部进行网格划分的标准技术进行D杂质MaxminJPJMaxminNloch180在上述数据集上。在空心圆柱体的情况下，在不同样本量的PCD之间进行比较-其中xmin;xmax;ymin和ymax是P沿x和y方向的上限和下限。该计算假设PCD在周界附近均匀分布作为一个近似的计算-所以，假设是这样就好了类似的方法用于外阈值（Kimp）。6.2. 求P中接近Ve点的四叉树优化在阈值内检测P的点的蛮力算法是非常低效的。为了提高效率，我们使用了四叉树四叉树的根是点云的边界正方形。四叉树的节点根据包围的点数当节点包含用户定义的常量点数或更少时，细分停止仅考虑与针对Voronoi边Ve 定 义的阈值相交的四叉树的叶节点内的点，以测试它们是否在阈值内这允许快速修剪不在阈值内的点;因此导致运行时间的显著改善。7. 结果和讨论在这里，PCMesh的结果和它的比较使用显式曲线重建生成的网格。这些算法使用计算几何算法库（CGAL项目，2017）在C++中实现，并已针对各种PCD进行了测试。以下是使用的输入PCD用于算法的分析。空心圆柱体：由于空心圆柱体的对称性，受到来自内部的均匀压力（Kazhenko，1970），问题可以简化为身体的四分之一部分。图7a示出了生成的网格。应该注意的是，这是一条非平滑曲线.Flower：一条闭合曲线，由极坐标中的r<$Rgcosnh定义坐标用于通过改变h的值而保持其他参数恒定来生成PCD。选择该示例是因为易于改变几何特征尺寸和复杂性。图7CT扫描图像：CT扫描用于制造业，以找到空腔或内部空隙。CT扫描仪输出具有像素的对象的图像（Yang等人，2014年）。从该边界像素数据生成PCD。用于获取样本点的图像取自喷嘴的CT扫描（喷嘴ct样本，2016）（图5），如图6所示。图7改变几何形状。比较结果示于表1中，反映了对于简单几何结构的运行时间的显著改善。在花的情况下，使用不同的g和n值来获得具有不同几何特征的不同样本在这两种变体中，PCD中有8000个输入点表2和表3中显示了PCMesh和传统网格与显式曲线重建的生成网格大小和执行时间之间的比较。最后一个首先将CT扫描图像二值化，然后利用Canny边缘检测算法提取出代表每个采样点的边界像素的PCD。由于分辨率和几何形状的变化，输入PCD尺寸变化。由于缺乏对高分辨率图像的访问，实验在较低分辨率的图像上进行，从而导致较小的输入点集。结果示于表4中。7.1. 基于样本量的比较分析（P）PCMesh生成最佳网格，因为生成的元素数量仅取决于曲线的几何特征，而不是PCD的密度在空心圆柱体示例中，增加PCD的密度不会改变计算时间，而在使用显式曲线重构的传统网格化的情况下，计算时间会改变，如图9所示。对于给定的几何形状，观察到插入点的数量与PCD密度无关相比之下，在使用显式曲线重构的传统网格化技术中，插入点随着PCD的密度而增加，如图所示。8.第八条。此外，应该注意的是，大多数PCD都非常密集，因此使用PCMesh将更有效。输出网格如图所示。早上77.2. 基于C语言的几何比较分析由于PCMesh的目标是为给定的曲线获得尺寸最优的网格，因此网格尺寸和计算费用与C的几何复杂性相关。对于该分析，考虑r¼4gcosmopolymer其中常数4影响闭合曲线的大小，n是花瓣的数量（几何特征）（图7算法PCMesh通过分别改变g和n来执行，保持其他参数不变。对于给定的样本大小，随着曲线的几何复杂度的增加，计算时间为N. Singh et al./ Journal of Computational Design and Engineering 6（2019）316323插入的点随着几何复杂度的增加而增加，该方法仍然比使用显式曲线重构的传统网格化更有效（参见图1A和1B）。14和15）。7.3. PCMesh在CT扫描图像上的性能分析在CT扫描图像的情况下，由于图6所示的低分辨率，输入样本量较小。与使用CT扫描图像的曲线重建的传统网格化相比，PCMesh的性能不佳。PCMesh中的大部分计算时间都被几何近似阶段占用，如图所示。 十六岁这可以归因于大量的点被插入以捕获曲率区域的几何形状，如图1所示。 7个G这与传统的网格技术不同，因为它们使用显式曲线重建方法来获得几何形状。PCMesh预计将在更高分辨率的CT扫描图像的情况下更有效地工作。7.4. PCMesh的性能分析PCMesh分为三个阶段（初始化和拓扑提取被认为是一个阶段）和计算四叉树的预处理步骤。图16示出了针对各种输入样本的PCMesh的每个阶段所花费的时间。在所有示例中，随着几何复杂度的增加，几何近似阶段开始比其他阶段花费更多的时间。总执行时间还包括预处理（四叉树计算）时间。为了分析算法效率对形状的几何复杂度的依赖性，分别在变化的g和变化的n上执行PCMesh随着g和n的值增加，曲线的几何特征尺寸（复杂度）增加。 因此，它可以被视为每图。 17，随着曲线变得更复杂，获得更精细的网格。7.5. 关于非光滑曲线的PCMesh公式的基本假设是C是一条光滑的闭合曲线。基于此假设，如果点云数据P是从非平滑曲线采样的，则将导致平滑曲线近似。如果曲线本质上是非光滑的，为了获得更精确的结果，在初始种子点S中包括导数不连续的曲线上的扭结处的点。即使在种子集中包括这些切线不连续点之后，算法PCMesh也可能不会终止并继续在这些不连续点的邻域中插入点。在我们的实现中，如果顶点间距离太小，我们会强制停止这种插入。事实上，如果这些扭结处的角度本质上是尖锐的，则不平滑的问题可能更严重。需要采取更强有力的办法，以掌握此类情况。8. 结论和今后的工作见图6。 图像样本取自CT扫描。图10和图12所示的网格单元的数量以及图11和图12所示的最终网格单元的数量。 11和13增加，而这种增加是没有看到在传统的网格使用显式曲线rexation。在PCMesh的情况下，即使计算时间和该算法将模型发现与网格生成相结合，减少了从点云数据中计算模型定义的基于该领域和第7节中以前的工作，可以观察到使用PCMesh将生成尺寸最优的高质量网格。更有趣的是，网格的大小与输入点云的大小无关，仅取决于几何特征。此外，在这项研究中，已成功地测试了使用的点云的局部属性，以减少计算费用。该算法的一个问题是，对于具有奇异点的曲线，无法达到几何封闭324N. Singh et al./ Journal of Computational Design and Engineering 6（2019）316见图7。为不同PCD生成网格。表1空心圆柱体的PCMesh与传统网格的显式曲线重构比较显式曲线重构生成PCD PCMesh网格中的输入点总积分执行时间（秒）总积分NN-结皮时间（秒）执行时间（秒）42702188.8785750.17354.982560221811.32311,1860.214100.67676042169.60415,2920.339200.83410,00222911.06920,1340.518335.864N. Singh et al./ Journal of Computational Design and Engineering 6（2019）316325表2比较PCMesh与传统网格，使用显式曲线重建花（8000点），g为1/2。曲线重建后生成的PCMesh网格（NN-外壳）中的花瓣总积分三角形总数执行时间（秒）总积分三角形总数NN-结皮时间（秒）执行时间（秒）21943346.72916,10830,6160.343176.943330255110.81716,08230,9710.344176.47443882116.65816,05831,1100.344177.8885701134723.52916,14131,6430.343179.7176769148226.87516,02031,5120.344177.736表3比较PCMesh与传统网格，使用显式曲线重建花（8000点），n¼5。曲线重建后生成的网格（NN-Crust）总积分三角形总数执行时间（秒）总积分三角形总数NN-结皮时间（秒）执行时间（秒）0.52404258.22416,08231,0430.345181.689141172813.18316,13331,4670.355183.7281.540876220.35116,10631,4290.359181.64243882116.65816,14131,6430.343180.7172.5570108320.4316,08031,5690.344177.328表4比较PCMesh与传统网格，使用显式曲线重建CT扫描图像。喷雾的CT扫描样本决议输入点曲线重建后生成的PCMesh网格（NN-外壳）喷嘴PCD总积分执行时间（秒）总积分NN-结皮时间（秒）执行时间（秒）1（图 7 g）257 × 1407973649.07214740.0351.7742（图2） 7 i）299 × 193114356516.77921800.0534.0953（图7k）312×198 1207 732 18.859 2294 0.055 4.4184（图 7米）322 × 194125761418.14723770.0584.7025（图 7 o）421 × 2902178158548.89639670.10211.668见图8。 空心圆柱体网格剖分的总点数比较。见图9。 空心圆柱体的执行时间比较。见图10。 Flower与g ¼ 2的执行时间比较。见图11。 花与g1/42的网孔尺寸比较。（非平滑）。这是通过选择种子集中的奇异点和第7.5节中讨论的点插入的邻近限制来解决的。需要在奇异曲线领域做更多的工作在这项工作中的固有假设是，输入样本具有最小的噪声。需要进一步研究，为了理解算法对噪声增加的容忍度以及将点云转换为无噪声数据的方法。在这项工作中，这个概念是在二维域解释，但可以扩展到三维。来临326N. Singh et al./ Journal of Computational Design and Engineering 6（2019）316见图12。 Flower与n¼5的执行时间比较。图十三. 花与n¼5的网格尺寸比较。见图14。CT扫描图像的总插入点比