点云边界线的提取.ppt

点云曲面边界线的提取 潘荣江 panrj@sdu.edu.cn 山东大学计算机科学与技术学院 2005年11月 引言 用三维扫描仪对物体表面采样，可以得到稠密、均匀、散乱的采样点集，称为点云，其中每一个点Pi=(xi,yi,zi)。 点云与深度图像（距离图像） 点云 {p1,p2,…,pn}: 散乱点的集合，描述一个物体或其中的一部分 深度图像 zi=f(xi,yi)：有规律，描述物体的一个侧面视图 点云的优点 曲面的点云表示可以转化为网格表示。 近年来基于采样点的数字几何处理研究逐渐深入，用点云表示三维碎片比用网格表示具有很多优势 点云是最原始、最真实的数据，没有加入任何人为因素； 采样点的几何结构简单，处理所需的时空代价较低； 可以直接应用扫描所获取的稠密均匀的采样点集，回避了复杂的网格生成过程； 对模型表面的离散表示，有助于数据处理中的并行处理和算法的优化设计，特别是分割、合并处理比较简单等。 点云描述的曲面可以分为两类 点集开曲面 点集闭曲面：由封闭表面围成的具有一定体积的物体 边界线 边界线是描述开曲面的一个重要特征。 在许多问题中都需要提取点云表示的开曲面的边界线： 物体分割 目标识别 文物复原 碎片拼接 点云补洞 …… 点云是散乱点集，属于非结构化数据，不具备连接性信息，定义和提取其边界线并不简单。 定义 曲面的边界线问题：给定一个有边界的曲面片S的采样点集P，找出代表曲面片边界的采样点子集B。 曲面片S表示一个有边界的流形曲面，它的每一个点都有一个邻域，或者同胚于开圆盘，或者同胚于半圆盘。 这些定义适用于连续的曲面片S。对于曲面片的有限采样点集P， 某个点相邻的k个最邻近点 均匀栅格 KD-树结构 近似最近邻库ANN 已有方法 Emelyanov提出了一种利用贪心三角化提取曲面边界线的方法，把没有被三角形链包围的点看作是边界点。 在三角化时需要进行复杂的判断，保证与一条边关联的三角形不能多于两个，而且不能形成四面体，因此计算较复杂。 Orriols利用递归最小二乘法提取曲面边界线。 采用了全局方法，计算速度快； 得到的边界线不够精确，没有找出所有的边界点。 Floater在无网格参数化中采用了一种简单的边界检测方法，把位于局部三角化边界上的点作为边界点。 在点集采样不均匀的情况下会把很多内部点错误地判断为边界点 Dey基于采样点的Voronoi图提出了一种边界检测算法 在满足一定采样条件下这种方法可以从理论上保证其有效性。但是计算采样点的Voronoi图比较复杂，而且对采样条件有严格限制。 Maes利用Pearson检验和遗传算法检测边界线 在遗传算法计算过程中不能保证最后得到的边界线的封闭性，而且需要针对不同的数据集调整参数。 Gumhold讨论了从曲面点云中直接提取特征线的方法， 首先构造点集的邻近关系图，然后计算邻近关系图的最小生成图，并对较短的特征线进行剪枝处理，提取封闭的特征线。 Bendels为了检测点云数据的空洞边界，计算邻近关系图的最小生成树，然后添加其他边，寻找长度大于某个阀值的最小圈。 最小生成图和最小生成树方法都是贪心算法，不能保证提取的封闭边界线的整体最优性。 主要步骤 根据一个点周围的k个最邻近点，计算每个点的边界概率。 为了找到真正的边界点，根据点的边界概率和局部邻近关系构造一个赋权无向图。 利用最大圈算法寻找边界线，保证提取的边界线是封闭的，且是整体最优的。 均匀栅格结构 计算整个点集的包围盒 计算网格单元的边长 把每个数据点放入唯一一个网格单元中 一个网格单元对应一个链表，其结点结构如下： structure NODE { flag: 标志 dataPointPointer: 指向数据点的指针 nextNodePointer: 指向链表中的下一个结点 } 度量标准1－最大角度量 利用完全最小二乘平面计算通过某点p且拟合邻近数据点的平面。 把每个点投影到拟合平面上，用极坐标表示。 按照夹角从小到大的顺序对所有投影点排序。 固定阈值不精确 边界概率 度量标准2－半圆盘度量 度量标准3－形状度量 特征向量对应椭球的主方向，特征值决定了椭球的大小和形状 对三个特征值进行归一化处理，构成一个判断向量 综合度量标准 典型数据的边界概率值 典型数据的边界概率值 典型数据的边界概率值 封闭边界线的提取 对邻近点在最小二乘平面上的投影进行Delaunay三角化，如果两个点属于同一个三角形，则定义为相邻。 点云作为无向图的顶点集合 点的相邻关系作为无向图的边集合 边的权值 提取封闭边界曲线就转换为在赋权无向图中寻找最大圈问题 最大圈算法 赋权无向图的构造