英语原文共 8 页，剩余内容已隐藏，支付完成后下载完整资料
基于L1中值的点云骨架提取
摘要：
在本文中我们介绍L1中值骨架对于三维点云数据，L1中值方法在一个任意点集中是一个鲁棒的全局中心。我们方法最主要的优势在与它对输入点云的质量、几何构造、拓扑结构没有很高的要求，我们开发的L 1-中值骨架结构算法，可直接应用于有明显噪声、异常点、无方向、大量缺失数据的原始扫描数据。我们展示了我们的L1中值骨架提取方法提取各种各样形状原始扫描数据的结果，它们包括种类很多的3D物体，类似植物的结构以及曲线网络。
- 介绍
L1中值方法是一个简单且强大的统计工具，它拓展了多变量设置下的单变量中值，它以给点点集的全局中心为代表。其突出特性是对异常点和噪声具有鲁棒性。在这篇论文中我们将对采用局部L1中值方法而非全局来表示一组几何形状的点，产生一个一维结构。这个结构可以被用来看做这个几何形状的局部中心。即一个中间曲线骨架。我们成这样的一个结构为L1中值骨架。它相当于一个空间本地化版本有条件正则化的L 1-中值。
定义一个无组织无方向的点集Q = {q j } jisin;J sub;R 3 ,我们调查下面的对于L1中值骨架的定义来获得一个最佳的的投影点集。 X = {x i } iisin;I :
第一项是点集Q在局部条件下的L1中值，第二项R（X）对X的局部分布进行正则化。I为投影点集X的索引，J是输入点集的索引，权重函数theta;(r)=e-r2/(h/2)2是一个快速衰减平滑方程。支持半径h定义为L1中值骨架构建的局部领域。
我们定义的（1）的最大的优点在于它对用于表示输入形状的点的集合质量没有太高的要求。特别地，它能够被直接应用到测距仪获取的原始点云数据上并且使用L1中值的鲁棒性会削减数据的各种缺陷。这种方法与已经存在的需要输入形状完整、无缝、精细镶嵌的主流曲线骨架计算方法相反。 [Chung et al. 2000; Deyand Sun 2006; Au et al. 2008; Hassouna and Farag 2009; Tagliasacchi et al. 2012; Willcocks and Li 2012].
从三维形状中提取骨骼表示已经被认为是一种有效的形状提取方法，从而成为形状分析和操作的有效工具[Cornea et al. 2007]。分析清洁、良好、代表性强的形状对它本身很重要。然而，也有关注于直接处理可能有噪声、异常值、甚至不完整的原始点云。一个迅速从原式扫描提取曲线骨架的应用是表面重构 [Tagliasacchi et al. 2009]，在这篇文章中，值得一提的是，它严重依赖于精确的点方向向量。而这些方向向量通常不可用或者很难从原始点扫描中获取。[Mullen et al. 2010]，我们的L1中值骨架就是被设计来直接应用于原始点云数据。
在为数不多的被提到的曲线骨架提取算法中， Tagliasacchi的方法是最好的。他们定义的曲线骨架依赖于一个叫广义转动对称轴的概念(ROSA)并且它假设输入形状以圆柱形为主。相应的，每一个骨骼点的构建需要对二维相邻点查询。即一个圆形的横截面。这突出了该方法于我们的L1中值操作的不同。我们的方法采用3D并且不需要圆柱形优先。同样重要的是，我们的操作直接在原生输入上，不像ROSA需要法向量信息和对去除噪声、异常点的预处理。实验结果显示我们的算法超越了ROSA甚至当后者采用最好的点云。最后也是最重要的。我们的算法明显比ROSA快。
我们方法最主要的贡献和优势包括：
bull; 从表示3D形状的点云数据中提取曲线骨架不需要在形状的集合上有前提假设。
bull; 直接操作原始数据，那就是不需要包括去噪声、去异常点、正常估计、空间离散化、数据完整化和网格重构、参数化的预处理。
bull; 一个简单的表达式就能够快速、鲁棒的基于默认参数设置的提取骨架。
- 相关工作
骨骼形状表示在各个领域得到了广泛的研究，并在形状建模和分析中得到了广泛的应用。最著名的例子是中轴转换，(MAT) [Blum 1967]它属于更大的中间表示一类[Siddiqi and Pizer 2009]，2形状的MAT是一维骨架，对于一个三维模型，MAT一般是由形成非流形结构的二维表面膜组成。在计算机图形学中，曲线骨架 [Cornea et al. 2007]更多因其结构紧凑、操作方便而被广泛采用，对于角色动画。在本节中，我们只关注关于曲线骨架提取的相关工作。
以往的曲线骨架提取方法大多是基于紧凑表面网格。典型的方法包括通过平均曲率流的表面收缩 [Au et al. 2008; Chuang and Kazhdan 2011; Tagliasacchi et al. 2012],耦合图压缩与曲面聚类 [Jiang et al. 2013],使用距离变换 [Dey and Sun 2006],中心Voronoi细分[Lu et al. 2012], Reeb图构造 [Hilaga et al. 2001], 或者网格分割 [Katz and Tal 2003]. 这些方法都依赖于表面连续性或者基于表面的方法来控制骨骼化的操作。
Sharf et al. [2007]通过追踪前方由点云定义的气泡内平滑生长的团块生成一个曲线骨架。当有明显缺失的数据时，侦测形状的内部并且气泡可能会泄露到形状之外。 Li et
al. [2010]也发展了一种叫做动脉蛇的变形模型，这种模型用于从管状截面形成的扫描形状提取曲线。他们的目标是提取一组功能曲线来捕捉形状的结构，专注于拓扑结构恢复。 Cao
et al. [2010]扩展了对于点云骨架的拉普拉斯收缩。然而，这需要输入点云足够清洁和稠密来建立一个拉普拉斯点集，最近， Livny et al. [2010]提出了一个从树形数据中重构骨架结构的算法。也有过依靠Reeb在点云上构造的图形，以获得形状的零件结构的粗略特征的相关工作。
在不完全点云上Tagliasacchi et al. [2009]所做的工作最相关。他们的等式依赖于一个圆柱优先并且精确的点法线向量来弥补缺失的数据。对于原生输入，噪声和异常点需要被提前过滤，过滤的方法如局部最佳投影（LOP） [Lipman et al. 2007].。相反的，我们的算法直接应用于一个有噪声、异常点、部分数据缺失的原始扫描且不需要可靠法线向量估计或者圆柱形前提的情况计算一个中间曲线骨架。
L 1-中位数的概念早就为人所知 [Weber1909; Small 1990]，最近，L1中值已经被成功应用于点集处理。 [Lipman et al. 2007; Huang et al. 2009;Avron et al. 2010],在稳健数据拟合的背景下。我们工作的一个重要创新之处在于利用了L1中值到新的应用程序，即，从原始点云数据中提取曲线骨架。不需要构建任何点连接或估算点法向量。我们直接把点样本投射到他们的局部中心。当L 1-中值邻点越来越大，推动样本通过条件正则化得到样本沿骨架分支的均匀分布。
3.概述
我们算法的输入是一个无组织的点集 Q ={q j } jisin;J sub; R 3 ，通常无方向性，分布不均，以及包含噪声和异常值，输出是一个表示输入Q形状的局部中心的一维曲线骨架。算法的主要步骤如下 (Section 4)。从原始扫描中随机采样一个点集 (red in Figure 2(c)) ，每个点迭代投影并在其局部邻域内重新分布到输入点的中心，相邻点的数量逐渐增加来处理机构不同层次的细节。生成出一个干净，连接完好的骨骼点集。 Figures 2(d-g).
如果输入点云高度不均匀，从该算法中获取的骨架点也可能不均匀。如图7，对于高度不完整的点云。生成的分支可能会偏离中心，如图8，为了缓解这两个问题。4.3节和4.4节展示了两个改进。基于密度权重和重定中心。最后，改进的L1中值方法如图2
4.L1中值骨架和构建
考虑到寻找包含最小欧拉距离的点集的x坐标。
在统计学中，最优化问题的解决方法是空间中值或者L1中值，由Small[1990]提出，当s {q j } jisin;J 点不共线。L1中值x坐标是唯一的。 [Mila-sevic and Ducharme 1987].
我们基本定义中的第一个参数（1）可以被看作L1中值的局部版本。局部化与权函数theta;中的有限支撑半径h不同于其他的基于L1的方法 [Lipman et al. 2007; Huanget al. 2009],这些方法的目标是组成一个代表一个表面的干净点集。这里的目标是计算一个骨架点云，它控制输入几何体的一维表示。换句话说，我们正在寻找一组由Q定义的底层形状的局部L 1-中值中心。使用l1-中值的一个关键优点是，与通常的平均值不同，l1-中值对数据中的噪声和异常值不敏感，如图3所示。
在这一节，我们展示了L1中值骨架的构建算法，首先我们定义正则项R，它代表点簇的组成。4.2节讲述了曲线骨架生成步骤的细节。最终，我们相应地展示了对于核心算法的两个改进，目的是处理非均匀点密度和偏离中心的问题。
4.1 条件正则化
单独应用L 1-中值往往会得到一个稀疏分布，该分布的局部中心可能聚集成一组点群，
如图4（b）
为了避免这种集群并维持适当的中间几何表示。我们需要进一步防止这种累积当点收缩到它们的局部中心，我们可以通过(1)式的R（X）来实现。R（X）在骨架分支构成的时候添加一个斥力。这样的一个惩罚就被叫做条件正则化。
我们采用传统的PCA权重来发现骨架分支的组成。在每一个点x（一个行向量）我们计算3times;3加权协方差矩阵的特征值和特征向量
所有的特征向量 lambda;0ilt;lambda;1ilt;lambda;2i是真值并且都与特征向量对应组成一个正交帧，即点集的主成分。我们定义值为。
作为x i在一个局部邻域内的方向度。这个sigma;i越接近1，lambda;0i和lambda;1i比lambda;2i越小，因此，x周围的点越多，i就沿着一个分支对齐。
为了有条件地应用斥力，我们定义我们的正则化方程。
其中{gamma;i}iisin;i是X之间的平衡常数。
当（1）式的能量梯度等于0时，在每个固定系数的点位置满足以下关系：
4.2迭代收缩曲线骨架
给定邻域大小为h，上述迭代方案产生一个代表局部邻域的L1中值点集X={xi}iisin;I，
简单来说，这些点直接形成基础形状的骨架。如图4（d），然而，对于更复杂的形状，仅仅只有部分点代表骨架的分支。如图5（c）和图6（e）
接下来，我们首先描述如何识别和标记属于骨骼分支点（分支点且颜色为绿色），然后我们解释如何从剩下的非分支点（标记为红色）选择桥点（标记为蓝色）并且使用它们来维持两组之间的连接性。最后我们通过逐步扩大邻域大小来展示分支是如何迭代地生长和合并。
我们从一组初始样本点开始，这些样本点都被认为是非分支点，基于初始邻域大小收缩样本点
其中dbb表示输入Q的边界盒对角线长度，|J|是Q中点的数量，为了决定是否在收缩后将一个点标记为分支，我们采用相同的方向度度量sigma;(2），具体来讲，我们首先对所有非分支点xi计算sigma;i对于所并且在相应的K邻域（K = 5）进行平滑操作来移除孤立的异常点。
如果在平滑后，sigma;igt;0.9,那么xi就被看作为分支的候选点，因为x i的邻域中的点在骨架上排列得很好。
为了从这些候选点中识别分支点，我们首先定位一个有最大sigma;值的种子点，然后从从它沿着主成分分析的方向发送给附近的满足
候选点。当局部邻域内没有满足标准的候选点时就停止追踪，如果找到了至少5个点，则这些点就被标记为分支点，否则，它们就从候选点中移出，这个步骤又从一个有最大sigma;的新种子开始重复，直到所有候选点都被处理。
如图5（c）和6（e）,上述步骤留下一些标记为非分支点的样本点；它们需要在更大的邻域大小h下进一步收缩才能形成新分支机构，然而，依赖于一个固定的h，无论大小在整个收缩过程中保持不变，不会管用。图6提供了一个使用大h点的示例代表小的子部分是“过度收缩”，以不保持中间结构。我们的解决办法是逐渐增加h同时将已经确定的分支点排除在进一步收缩之外。即，hi=hi-1 Delta;h,i = 1, 2 ...,其中Delta;h = h0/2,直到所有点变为分支点。
在固定分支时投影剩余的非分支点点可以将两个组分开，从而导致断开骨架分支。为了解决这个问题，我们在一个识别的骨架分支断点选择桥点。将分支端点记作e，其对应的桥点b在分支方向上是一个非分支点，eb向量与分支方向的夹角小于90°，比任何非分支点更接近e，并且距离||b-e||小。
这些桥接点在分支之间提供适当的连接点和非分支点：每个桥点链接到分支的相应端点，因此保持与现有的分支机构。另一方面，作为非分支点，它参与进一步收缩，因此是新形成的分支。结果，在不同邻域大小下发现的分支连接起来，形成一个完整的骨架。
在收缩过程中应用了两个附加规则：当一个局部邻域包含两个或多个桥点时，它们被折叠成一个分支点，该分
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[236862]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
