网站建设时间 人力及成本估算,网页实训内容及过程,关键词挖掘ppt,wordpress 文章格式化1、介绍 此程序包实现了一种重建和简化二维点集的方法。输入是一组具有质量属性的二维点#xff0c;可能受到噪声和离群值的干扰。输出是一组线段和孤立点#xff0c;它们近似于输入点#xff0c;如下图所示。质量属性与每个点的近似重要性有关。 左#xff1a;输入点集受到…1、介绍 此程序包实现了一种重建和简化二维点集的方法。输入是一组具有质量属性的二维点可能受到噪声和离群值的干扰。输出是一组线段和孤立点它们近似于输入点如下图所示。质量属性与每个点的近似重要性有关。 左输入点集受到噪声的阻碍。右图由线段组成的相应重建形状。 在内部该算法从所有输入点构建一个初始的二维Delaunay三角剖分然后简化三角剖分使三角剖分的边和顶点子集近似于输入点。近似是指基于最优运输的鲁棒距离。三角剖分通过半边折叠、边翻转和顶点重定位运算符的组合简化。三角剖分在简化过程中保持有效即既没有重叠也没有折叠。 重建算法的输出是三角剖分的边和顶点的子集。下图描绘了一个例子其中输出由绿色边和一个孤立顶点组成。绿色边被认为是相关的因为它们很好地近似了许多输入点。灰色显示的边称为虚边被丢弃没有近似任何输入点。红色显示的边称为不相关也被丢弃近似了一些输入点但不足以被认为是相关的。 a 输入点。b 输入点的Delaunay三角剖分。c 简化后重影边为灰色相关边为绿色不相关边为红色。d最终重建由多条边和一个孤立顶点组成。 输出重构的目标边缘数量与近似误差的概念之间没有直接关系。因此简化算法可以通过与距离相同的最大容限误差来停止。更具体地说公差被指定为每单位质量运输成本的最大平方根在一定距离内是均匀的。 请注意公差是在Wasserstein距离的意义上给出的请参见Wasserstein距。这不是豪斯多夫公差这并不意味着输入样本和输出多段线之间的距离保证小于公差。这意味着每质量运输成本的平方根在一定距离内是均匀的最多是公差。 重建的输出可以通过两种方式获得要么作为2D点和线段的序列要么作为对线段的连通性进行编码的索引格式因此称为顶点和边。索引格式记录点的列表然后在所述列表中记录边的点索引对以及隔离顶点的点索引。
2、API 向用户公开的唯一类是Optimal_transportation_reportion_2类。
2.1、示例调用
Optimal_transportation_reconstruction_2Kotr2(points.begin(), points.end());
otr2.run(100); // perform 100 edge collapse operators 如果输入不仅仅是没有质量的点则可以提供与该输入匹配的特性映射。
Optimal_transportation_reconstruction_2K, Point_property_map, Mass_property_mapotr2(points.begin(), points.end(), point_pmap, mass_pmap);
otr2.run(100); 除了调用run还可以调用run_until并指定要保留的输出顶点数. 来自分别由2000、400和200个输入点组成的数据集的20个顶点重建的示例。这些示例说明了当输入点密度降低时算法的行为。 最后当输出边的数量未知时调用run_under_wasserstein_tolerance允许用户根据距离标准运行算法。 otr2.run_under_wasserstein_tolerance0.1//执行折叠直到在公差范围内无法再执行为止 具有不同Wasserstein耐受阈值的重建示例。顶部输入点设置和重建公差为0.005。底部公差为0.05和0.1的重建。
2.2、全局点重定位 由于噪声和丢失的数据可能会阻止重建的形状在正确的位置具有尖角因此该算法提供了重新定位重建的所有点的功能
otr2.relocate_all_points(); 请注意这些点与基础三角剖分的顶点重合。此函数可以在一次简化后调用也可以与多次简化交错调用。 新的点位置被选择为使得输出分段和孤立点对输入点的近似被提高。更具体地说重新定位过程在计算给定当前重建的最佳运输计划和在保持当前运输计划不变的情况下重新定位三角测量顶点之间迭代。顶点被重新定位以最大限度地减少当前运输计划引起的运输成本。 左点重定位前。右图点重定位后。
3、参数 该算法的行为通过以下参数来控制。
3.1、边翻转 在简化内部三角剖分过程中需要一些递归边翻转算子来确保在应用半边折叠算子时三角剖分保持有效。调用set_use_flipfalse可防止算法使用边翻转以次优结果为代价产生更短的计算时间因为并非所有边缘都可以被认为是可折叠的。 边缘翻转。左图蓝色边会产生折叠因为阻挡边显示为黑色。中间运行递归翻转边过程后蓝色边是可折叠的。右图边塌陷后的三角剖分。
3.2、边缘相关性 从近似观点来看如果一个边1很长2近似很多点或在点具有质量属性时近似大量质量并且3近似误差很小则该边是相关的。更具体地说相关性的概念定义为m(e)*|e|²/cost(e)其中m(e)表示由边近似的点的质量|e|表示边的长度cost(e)表示其近似误差。由于误差由质量时间平方距离定义因此相关性是无单位的。默认值为1因此所有近似某些输入点的边都被认为是相关的。较大的相关性值为我们提供了增加对异常值鲁棒性的手段。
3.3、随机样本大小 默认情况下简化依赖于抽取期间半边缘折叠算子的穷举优先级队列。为了提高效率严格大于0的参数样本大小切换到多选择方法即在大小样本大小的边缘折叠算子的随机样本中的最佳选择。样本大小的典型值是15但当目标是非常粗略的简化时必须放大此值。
3.4、本地点迁移 除了上述全局重定位功能外Optimal_transportation_reconstruction_2 类构造函数的一个可选参数提供了一种在每次边折叠操作后可能结合边翻转在本地重定位点的手段。本地在此处意味着仅在每个边折叠操作周围的三角剖分中重定位局部模板的顶点其过程类似于上述全局重定位函数中描述的过程。将局部模板选择为折叠边后剩余顶点的单环邻域。重定位过程是迭代的一个参数控制重定位步骤的数量。
3.5、详细输出 verbose参数介于0和2之间用于确定算法生成的控制台输出量。0值不生成标准输出的输出。大于0的值将生成标准输出std::cerr的输出。
4、健壮性 该算法的优点是其对噪声和异常值的鲁棒性。下图显示只要异常值的密度与输入点的密度相比较小算法的输出就几乎不受噪声和/或异常值的影响因此算法的输出是稳健的。 对噪声和异常值的鲁棒性。左无噪波点集。中间噪声点集。右图点集受到噪声和异常值的阻碍。
5、变密度 下图说明了算法在具有均匀质量属性的点集上相对于可变密度的行为。由于该算法更加重视密集采样区域这转化为密集采样区域上的较小边缘。在稀疏采样的区域上该算法最初通过一个孤立的顶点对每个点进行近似然后逐渐用边对这些点进行近似。 6、混合维度 描绘了对一组线段和实心区域进行采样的输入点集。根据输出中的目标点数实体区域由一组均匀采样的孤立顶点近似。 7、可变质量 质量属性提供了一种调整每个点的重要性以进行近似的方法。图描述了阈值处理后灰度图像的重建其中像素的灰度被用作质量属性。 可变质量。左输入灰度图像。中阈值处理后的图像以减少用作质量为非零的点的像素数。右最终重建。
8、它是如何工作的 这里要解决的任务是从R2中的噪声点集S重建一个形状即给定平面上的一个点集找到一组点和线段更正式地说一个0-1单纯形复形它最接近S。 近似误差来自几何测度之间的最优传输理论。更具体地说输入点集被视为离散测度即一组逐点质量。目标是找到一个0-1单纯形复杂体其中边是分段均匀连续测度的支撑即线密度质量顶点是离散测度的支撑。在我们的上下文中近似输入点集转化为用由线段和点组成的另一种测度来近似输入离散测度。
8.1、Waterstone距离 直观地说最优传输距离在我们的上下文中为Wasserstein-2距离测量将输入度量传输到三角测量的顶点和边上所需的工作量其中度量在每个边上被约束为均匀且大于或等于零在每个顶点上仅大于或等于0。请注意Wasserstein距离是对称的。 当三角测量的所有顶点与输入点重合时在完全初始化后由于每个输入点免费重新定位到一个顶点并且重建仅由孤立的顶点进行因此总传输成本为零。 现在假设输入点集由在线段上均匀采样的10个点每个点的质量为1组成并且三角测量包含与线段重合的单个边。尽管从点到边缘的单侧欧几里得距离为零反之不为零但从点到边的Wasserstein距离为非零因为我们将边的质量密度约束为均匀并且边的总质量密度积分等于10即输入点的总质量。因此输入点应在边缘上切向传输以匹配均匀密度输入点的最佳传输计划被描述为覆盖边缘的具有相等长度的较小线段。 如果现在在同一边缘上均匀地采样20个点每个点的质量为0.5则Wasserstein距离较小尽管总质量与以前一样为10因为运输计划由较小的线段描述。在20个输入点具有不同质量的略微不同的配置中最佳运输计划由小线段描述其长度与相关输入点的质量成比例。当输入点不严格位于边缘时运输计划既有切线分量也有法线分量。 换言之当输入点密集且均匀地对输入点的边缘进行采样时通过单个边缘很好地近似该输入点。因此除了对称性之外Wasserstein距离的一个优点是量化从点到边的偏差和该边上点的不均匀性。当这些异常值的质量与输入点的总质量相比很小时该距离对异常值远离边缘的点也有弹性。
8.2、重建 该算法对三角剖分进行从细到粗的简化。它首先在输入点S周围构建一个盒子并在S的全部或子集上计算Delaunay三角剖分T0。T0是第一个输出的单形在后续迭代中通过重复的边折叠进行简化。为了选择下一个边对所有可行的边即在三角剖分中既不引入重叠也不引入折叠的边模拟边折叠算子。根据T∖e的运输计划的总成本选择下一个要折叠的边e其中最便宜的总成本是首选。由于忽略不保持三角剖分嵌入的边会严重影响贪婪方法对最优运输的性能因此通过添加使每个边可折叠的局部翻转过程来修改折叠算子。 通过将每个输入点临时分配给最近的单形边来近似运输计划。在将输入点相对于边进行划分之后如果且仅当相应的运输成本小于边两个端点中每个端点的运输成本则临时分配给给定边的所有点将被永久分配给它。否则每个点被分配给两个端点中最便宜的端点。重复边折叠和运输计划更新的过程直到达到用户指定的所需顶点数量。 在过程结束时可以过滤掉质量较小的边缘剩余的相关边缘和孤立顶点被报告为重建输入形状。
9、其他 Wasserstein距离又称Wasserstein距离、Earth-Mover距离是一种衡量两个概率分布之间的距离的度量方法。 在定义Wasserstein距离时首先需要定义两个概率分布之间的所有可能的联合分布的集合。对于每一个可能的联合分布可以从中采样得到一个样本x和y并计算出这对样本的距离||x−y||。然后可以计算该联合分布下样本对距离的期望值E(x,y)∼γ[||x−y||]。在所有可能的联合分布中能够对这个期望值取到的下界就是Wasserstein距离。 直观上可以把E(x,y)∼γ[||x−y||]理解为在γ这个路径规划下把土堆P1挪到土堆P2所需要的消耗。而Wasserstein距离就是在最优路径规划下的最小消耗。
CGAL 6.0 - Optimal Transportation Curve Reconstruction: User Manual
