Detecting Holes in Point Set Surfaces 论文阅读

下载链接

Detecting Holes in Point Set Surfaces

摘要

• 3D 数据采集过程（例如激光范围扫描）产生的重要物体模型通常包含由于遮挡、反射或透明度而产生的孔洞。本文的目标就是在点集表面上检测存在的孔洞。
• 对于每个点，将多个标准组合成一个综合边界概率。
• 最终的边界环提取步骤使用该概率并利用边界的附加相干特性来导出鲁棒且自动的孔检测算法。

先前工作

• [GWM01]、[LP02]以及[CN04]应用本文所说的角度准则。角度标准考虑每个样本点 p 的一组相邻样本，并检查两个连续相邻样本之间的最大角度。
• [GWM01]使用邻域形成的相关矩阵。该矩阵的特征向量和特征值定义了相关椭球。其形状以特征值的比率表示，用于识别角点、折痕和边界点，并给出折痕和边界方向的近似值。为了找到连续的折痕线，在点集上构建邻域图，并根据折痕概率对其边缘进行加权。然后收集具有高概率的边缘并构成特征模式。
• 在[DG01]中，使用[ABE98]的采样要求检测欠采样区域。该采样条件基于每个样本 Voronoi 单元的所谓极点对中轴的近似。每个点到中轴的距离给出了局部特征尺寸。真实表面上的每一点都需要在由局部特征尺寸和因子 r 定义的球内至少有一个采样点。因此，[DG01]的方法无法识别表面平坦区域中的孔。

综述

• 对于每个点 p ∈ P，计算边界概率 Π§，反映 p 位于表面采样中孔上或孔附近的概率（第 4 节）。
• 此后，利用边界属性是一致的，即边界点具有也是边界的邻近邻居，并以最短成本路径方式构建包围孔的闭环（第 5 节）。
• 本文的孔检测方案的结果和应用在几秒钟内给出。

边界概率

近邻收集

这里本文提出了一种简单的，不受密度影响的近邻方法，而不是简单的R近邻或者K近邻。
对于点p的近邻，首先包括它的k近邻，然后还包含k近邻包含p点的点。也就是说，你是我的近邻，则有我是你的近邻。

用这种策略能够避免单纯R近邻或者K近邻会受点集分布密度的影响。

角度标准

角度准则将 Np 中包含的所有相邻点投影到切平面上，并根据它们围绕中心样本的角度对它们进行排序，并计算两个连续投影相邻点之间的最大间隙 g。基本思想是边界点的 g 明显大于内部点的 g。

边界概率公式为

这里的$|N_p|$个人理解是p点邻域点的数量

半盘标准

在 2D 图像处理中，边缘检测算法识别亮度与其相邻像素的平均亮度有很大偏差的像素。
这里就是用p点近邻的质心和p点的便宜距离作为标准判断p点是否为边界，在点集内部p与p点邻域质心偏移量应该很小，在边缘地区比较大。

在 2-流形上，表面内部点的邻域与圆盘同胚，因此可以预期点 p 本身与其近邻点的平均 ${\mu }_p$ 之间的差异很小，这与圆盘上的点相反边界。它们的邻域与半圆盘同胚（见图 4），因此$|{\mu }_p|$ 将显着偏离 p。因此，为了得出边界概率，我们将 $|{\mu }_p|$ 与切平面中理想半圆盘的质心进行比较。

这里为了减少采样密度的影响，计算质心的公式中附加了一个高斯核。

形状标准

这一部分是根据邻域的协方差矩阵的特征值比例，确定某一个点的形状，作者对结果进行分析并总结了一般性规律，列出了网格。

后面根据表格给出了一个分类公式。

结合标准

每个标准都有自身的优点和缺点，作者经过分析，最后将三种标准结合起来判断。

为了利用标准的不同功能并提高边界概率计算的鲁棒性，我们将组合边界概率导出为加权和

法线估计

这里说是角度和平均标准都比较依赖点集的法线。提出用[HDD+92]论文中的方法，法线作为与 Np 的加权协方差矩阵的最小特征值相对应的特征向量给出。
本文还提出用计算角度准则期间收集的信息集成在一起。

有时，在锐利折痕处，拟合平面与表面垂直。为了检测这种情况，在估计法线后评估角度标准。如果边界概率${\Pi }_{\angle }(p)$ 超过给定阈值，则估计法线将围绕由最大间隙两侧的两点定义的轴旋转 90 度，投影到切平面中。然后再次评估角度标准，这次使用旋转法线，如果边界概率显着降低（即超过 50%），则保留新法线。这有助于形成锐利的折痕，有时拟合平面垂直于表面，见图 9。

边界循环

边界相干性

除了使用上一节中描述的方案计算的边界概率之外，还利用边界点之间的一致性（也就是说边界点的近邻也可能是边界点）。这极大地提高了本文方法的稳健性。此外，还会发现围绕孔的连接点环。
边界环上的任何点在每一侧都至少有一个邻居也属于边界。使用简单的迭代分类步骤可以轻松地利用此属性。

1. 首先，所有边界概率大于用户定义阈值的点都被声明为边界点。
2. 然后，对于这些点中的每一个，找到在角度标准意义上形成最大间隙的两个邻居。当且仅当这两个相邻点也已被声明为边界点时，该点才保持分类为边界点。所有其他点都标记为内点。
3. 重复此过程，直到不再有点改变其状态。注意，只有在上一次迭代中确实改变状态的点的邻居才需要在后续步骤中重新考虑，从而使分类非常有效。

分类后，使用一种基于 [GWM01] 中提出的算法构建的算法，基于邻近图 G 构造最小生成图 (MSG)。
使用 Kruskal 最小生成树算法的扩展。边的权重根据相邻点的边界概率和点邻域密度加权计算得到。

循环提取

有了 MSG，就可以使用广度优先搜索来提取边界循环，得到最终的结果。