离散点云原始形状及边界曲线提取算法.doc

《离散点云原始形状及边界曲线提取算法.doc》由会员分享，可在线阅读，更多相关《离散点云原始形状及边界曲线提取算法.doc（5页珍藏版）》请在三一办公上搜索。

1、离散点云原始形状及边界曲线提取算法刘光帅 李柏林 何朝明（西南交通大学机械学院成都）摘 要 大规模离散点云包含多种类型的扫描缺陷 ：噪 声 、异 常 数 据 、孔洞及不规则的各向异性采样 ，大 部 分 现 有 的 算法不能够很好地处理这些缺陷 ，这对点云拓扑关系的恢复及特征提取带来了困难 。 针 对 此 问 题 ，提出了一种健 壮 有 效 的点云重构算法 ，首 先 ，计算每个数据点的局部属性 ；然后利用局部属性探测点云中包含的原始形状 ；最 后 利 用 统 计 优 化方法对原始形状中包含的边界曲线进行提取和优化 ，通过优化的边界曲线可以获得分段光滑的网格曲面 。 实 例 证 明 ，该算法实用性

2、好 ，对合成点云及真实场景点云的重构效果理想 。关键词 散 乱 点 云 ，原 始 形 状 ，边 界 曲 线 ，特 征 点 ，多 尺 度 分 析 ，统 计 优 化中图法分类号文献标识码 （，） ， ， ， ， ， 确的边界位置是不确定的。 本文提出的算法对连续曲面表达所需的强制信息进行 计 算，并对局部表面属性（例 如 采 样、噪 声）进行估计，这些属性是探测原始形状及推断表面边界的依 据。 算法包含三个关键 步 骤：首 先，计 算 点 云局部采样属性， 估计点云的噪声特征及每个数据点的粗略法矢；其次，利用随 机抽样一致性算法（）探测点云中包含的原始形状； 最后，对提取的每个原始形状包含的边界曲

3、线进行计算及优 化处理。 下面对算法进行详细描述。引言大部分现有三维表面扫描设备能够获取海量的离散点云数据，但由于物理设备及测量条件的限制，获取数据的过程会 受如下因素影响：强噪声、模型孔洞、异常数据、配准误差及各 向异性采样。 这对点云重构算法的设计至少提出了两个方面 的挑战：其一，如何重构表面的拓扑关系；其二，如何提取散乱 点云包含的原始形状及几何属性。 国内外学者针对此问题做 了大量 的 研 究，提出了许多求解 算 法，诸如隐式曲面方 法，、最小移 动 二 乘 法、单元多层次分 解 方 法、（泊 松 流 ）曲 面 重 构、变 分 方 法、机 器 学 习统 计 学 方法，其中大部分的算法不

4、能够处理质量较 差 的 点 集。 其 原因在于，所有的算法都对曲面做了隐式假设，故其只能用于 实验环境下扫描系统获取的具有均一点采样及低噪声的点 集，而不适用于真实场景数据集的处理。文献提出了探测点云数据包含原始形状的方法，同时 完成清除噪声、修补不完全数据、清除异常数据的工作。 但是 利用该方法探测到的原始形状代表扫描曲面的哪部分及其精算法描述算法的输入数据为离 散 点 云，且点云数据不 包 含 任 何 拓扑及法矢信息。 在对输入点云进行预处理时，将 对 每 个 点 估计采样值 及逼近的法矢方向， 的外边界不仅表示 邻域的平均距 离，而且描述该邻域包含点的最小 影 响 半 径。 的确定依赖于

5、点云的 采 样 率、采样的各向异性因子及局部 噪声分布，同时，需要估计每个数据点噪声分布的 标 准 偏 差 ， 。 此外，估计方差提供了足够的关于局部曲面 属 性 的 信 息，这将有利于原始形状的探测及识别，进而完成原始形状描到稿日期： 返修日期：本文受国家自然 科 学 基 金 （），四川省科技计划项目 （，），中央高校基本科研业务费专项资金项目（）资助。述的边界特征点提取及边界特征曲线优化。 最 后，提 取 每 个原始形状边界封闭部分的网格，并对网格进行缝合得到最终 的曲面重构结果。 算法流程如表 所列。原始几何形状探测对每个点 进行噪声 估 计，以 判 别 该 点 是否适配于某个 原始形状

6、，假如点到某原始形状的距离小于 ，则该点被 认 为适配于该原 始 形 状。 给 赋 值 为 ，假 设 原 始 形 状 有 效 及 噪声估计正确，这意味着超过 属于原始形状的点 将 被 保 留。探测过程将返回原始形状的一个集合 及对应的 数据集 。 原始形状识别停止准则的确定是 一件困难的事情，其依赖于多种因素，诸 如 点 的 数 量、场 景 的 总体结构以 及重构的复杂程度。 因为探测过程不 能 自 动 终 止，当识别表面包含的点 数 量大于用户定义的阈值 的 概 率表算法处理流程自然语言描述算法流程预处理输入的离散点云数据； 探测原始形状，原始形状数记为；执行循环：（； ）探测边界候选特征点

7、；筛选边界候选特征点；提取候选边界 ；筛选候选边界 ；初始化边界拓扑结构；提取边界闭环 ；优化边界曲线；提取闭环 的三角网格；小于 时，则停止搜索过程取值范围为：。 在本文提出的算法中的特征边界探测即使知道识别出来的原始形状包含了曲面（或 曲 面 的 逼 近），但是这些信息对点云数据的可视化及进一步的处理依旧 不充分，因为原始几何形状本身不包括被描述曲面的边界信 息。 因此，本文提出需要显式抽取和处 理 这 些 边 界，同 时 并行利用原始形状及其分叉点的信息。 对 于 每 种 原 始 形 状， 抽取一个关于边界曲线的非空集，这些曲线通过前一段曲线 的拓扑连通性和下一邻域的切线方向来描述点集。

8、 抽取边界 曲线可通过下面步骤来描述。（）提取边界候选 点。 边界点的特点是在切 线 空 间 上 缺 少邻接点，根据文献中提出的方法，在 距离内对点 的邻域进行排序，并在切平面将 的邻域划成 个锥形。 假 结束循环；输出优化处理后的分段光滑曲面重构结果 ；输入数据预处理在缺乏先验知识 的 前 提 下，搜索每个数据点的 采 样 是一件极其困 难 的 事 情。 本文采用多尺度分析模 式 找 到 每个点 的影响半径 ，以便获得法矢方向的 稳 健 估 计。 因 此，通过至 邻域最远点的距离来计算初始采样参数 ，同 时，采用 倍的迭代因子来递增该半径，对于每一次迭代， 采用主元分析法（即 法）分析 邻域

9、包含点的权重 收敛矩阵 ， ： （ ）（ ）， 如两个及以上相邻的锥形未被填充，则将 被标识为边界候 （）补点，如图 所示。 图（）的中心点 为内点，图 （ ）的中 式中， 表示点 上影响半径小于 的邻 域 集， 是 的心点 为边界候补点。 通过将与原始形状关 联 的 所 有 点 映质心。 如果给定相邻迭代和，矩阵特 征 值， 满 足射到原始形状空间可增强该步骤的健壮性，并可根据映射位置进行点法矢推断。条件：， ，则接受外边界尺度 。 此外，要， ， 求特 征 向 量 ， 和， 分 别 对 应 最 小 特 征 值 ， 和， ，并保证两 者 充 分 并 行，即 满 足。 ， ，其关键在于：假如获

10、得充分的外边界尺度 ，特征向量， 表示的法矢方向不再变化。为了建立采样模型并估计每个点的噪声方差，需对， 邻域的一个二阶多项式曲面进行拟合，描述如下：图边界候选点探测 （）， （）筛分边界候选 点。 为了使下一步的拓扑 构 造 能 够 顺利完成，需对边界候选点定义的一维曲线进行重采样及光顺：式中，（）返回点 到拟合多项式曲面的距离。 图 显示了合成数据集的分析结果：图（）显示沿着 轴方向采样各向 异性递增，沿着 轴方向噪声水平递增；图 （）显 示 采 样 点 沿着 轴和 轴同时递增；但是图（）显示采样点沿着 轴 方向递增才能正确地 估 计 噪 声。 注 意，该 方 法 亦 可 用 于 异 常

11、数据的识别，假如迭代模式在规定的迭代次数下不收敛或 邻域的 点 收 敛 于 更 小 的，则可以将对应数据点进行清 剔除距离某候选 边 界 点 小 于 的 所 有 其 它 边 界 候 选点，并对筛分后的每个边界候选点及其 个最近的邻接点 进行最小二乘拟合。 拟合过程给出了每个边界候选点的切线方 向，如图 所示。除。 并采用点 方差 的高斯核来进行采样场及 噪 声 场的光顺处理以提高算法的健壮性。图遴选边界候选点及拓扑初始化图采样及噪声估计（）拓扑初始化。 对于每个边界候选点，在通过切线方向定义的一维曲线上选取与其前后距离最近的 个邻接点，并以拓扑图的形式将它们连接起来。 图 显示了拓扑初始化过

12、程。（）边界封闭环提取。 为了达成边界封闭环提取之目的， 本文采用了深度 优 先 泛 洪 （）算 法。 以任意一个边界 点为起始点，沿着该点的所有拓扑邻接点进行环 的 增 长。 对 于每个被遍历到的边 界 点，记住其遍历路径。 假 如 第 二 次 遍 历到同一个点，则将通过回溯选择更长的遍历路径，当遍历达 到起始点时终止该泛洪。 再次选择任意 个种子点，重启该 泛洪确保提取了可能最长的封闭环。 重 复 上 述 处 理 过 程，直 至完成所有封 闭 环 的 识 别。 图 （）显 示 了 本 文 算 法 对 复 杂 初始拓扑的处理，因边界候补点存在误识别的现象，故处理过程中小于 个点组成的封闭环被

13、清除。如果一个边界点， （ ）接近原始形状 ，同时接近原始形状 的边界点，则该边界点被标记为两原始形状的交叉边界点，交叉边界点同时被所属的原始形状及相邻原始形状吸引， 并保证交叉原始形状之间一致性。 通过应用上述光滑势到所 有的边界点，边界曲线上的拐角将被光顺处理。 为 了 避 免 这 种影响，探测角点并将其投影到所有邻接的原始形状上，当排 列在相邻原始形状上的交叉边界点发生改变时，角点被探测 到。 在整个优化处理过程中，角点位置不会再发生 改 变，图 （）的黑色小球表示被探测到 的 角 点。 如果因为其他势能够 将一些点移动到更靠近交叉线的地方，这将改变点的标识，则 需要对交叉边界点或角点进

14、行重新排列。权重系数 表示独立势高斯分布的标准偏离值， 和这两个权重系 数 被 赋 值 为 。 因为边界曲线是嵌在 空 间的一维曲线，故 采 用 基 于 线性搜索的共轭 梯度法对其优化问题进行求解，并设定迭代次数 小 于 。 图（）显示了边界提取及优化结果。网格化处理最后，采用前向增长算法由原始形状和优化边界曲线 建立三角网格。 对于任意原始形状 的每个边界区域，通过 隶属于 且离边界最远的点 ，生成边长为 的种子三角面片。 假如前向边接近边界（），则前向增长终止，并 将 前 向顶点与边界点融合。 对于包含多条边界的原始形状，该 过 程必须执行数次。 当所有原始形状点集都至少接近一个三角面 片

15、（），则将终止网格化处理，同时完成孤立网格面片的缝 合操作。 网格化仅依赖于原始形状和优化后的边 界 曲 线，而不会因输入数据残缺而影响其进程。图边界点优化及边界封闭环提取上述处理过程获得的边界曲线通常呈锯齿状，更 为 重 要的是，这些边界曲线通常不等价于不同曲面间的交线。 因此，需要对边界曲线的点位置进行优化调整。优化处理采用文献提到的基于贝叶斯规则的统计学公式 进 行 优化，描述如下：（）（）处理实例（）（）本文提出的算法通常处理的是分段光滑曲面，且 这 些 分段能够被原始形状描 述。 图 显示了合成点集 的 曲 面 重 构，该点集加入了高斯噪声（标准偏差大约是包围盒对角线长的 ），图 描

16、述了边界探测和优化的 具 体 细 节。 在 图 （）中 显示的是加入了高斯噪声后的输入点云，通过边界候补特征 点探测建立边界及初始拓扑结构，采用统计优化方法得到图（）显示的经过优化后的边 界 曲 线，黑色小球代表角点。 图（）是三角网格化后的效果。式中， 代表原始几何形状 边界点的集合， 为包含的点集合，条件（）是 后 验 概 率，（）是 似 然 度，（）是先验概 率。 在 优 化 过 程 中，舍 弃 常 判 据 （）将 导致极大值后验（）优化问题：（）（）为了更有效率地优化，将所有组元转换到负对数空间，综合势用 表示。为了计算似然度，直接采用点集 ，惩罚任一边界点，至其最近邻接点 的距离 ，

17、描述如下： （） ， ，为了达到边界曲线光顺之目的，采用了两个光滑势：通用光滑条件 （）和原始形状约束条件 （），光滑条件描述如下：图合成点云处理实例 （） ， （ ）本文算法更关心的处理对象是从真实扫描系统中获得的点集。 处理的关键在于对完整场景的识别，包括室外和室内。 真实扫描系统提供的点集是各向异性的，同时包含噪声及异 常数据或噪声带来的配准误差。 图 （）所 示 的 房 间 点 集 需 要通过安装在竖直轴可 度旋转的云台上的激光扫描仪获 得。 利用本文算法，在给定视角上成功地提取了所 有 主 要 的 原始形状，同时成功提取了所有边界。 提 取 的 边 界 候 选 点 及 优化后的边界曲

18、线如图（）所示，黑色小球代表角点。 式中， 和 是边界点， 的两个最近邻接点。 （）将确保探测到的原始形状的 几 何 连 续 性，描 述如下： （） （， ） 式中，（）是点 到原始形状 距离函数的返 回 值；初 始 时，势 （）仅吸引与其对应原始形状关联的 边 界 点。 然 而，： ， ， （）： ， ， （ ）： ， ，： 胡事民，杨永亮，来煜坤数字几何处理研究进展 计 算 机 学 报，（）： ，（）：， ， ， （），（）：， ，：， ，：， ，：图真实场景点云处理实例结束语 本文提出了一种离散点云原始几何形状及特征曲线抽取算法，这将有利于分段光滑的表面网格 建 立。 该 算 法能够正确

19、地估计离散点云的法矢及噪声，高效地抽取任意 原始形状，并利用统计优化模式处理原始形状边界及原始形 状交叉处的尖锐特征 线。 在将来的工作中，可 考 虑 将 本 文 提 出的算法与其他重构技术融合以对曲面区域的细部特征进行 处理，以避免细部原始形状探测失败及遗失问题。参 考 文 献 ， ，： 邱航，陈雷霆基于点的计算机图形学研究与进展计算机科学，（）： ， ，： ， ，结束语 本文通过对现有分水岭算法的分析，将 进 化 规划和标记提取方法结合使用对图像进行预处理，再进行分水 岭分割。 这种方法有效地解决了过分割问题，同 时 采 取 的 所 有措施都放在分水岭分割之前的预处理中进行，分水岭变换 之

20、后没有区域合并操作，方法比较简便。 同时，本方法基于进 化规划的概念进行区域标记符的提取，快捷而有效；其演化规 则还可以对内外标记符进行预先整合，使其更加符合分割的 视觉特性。 该方法既有效解决分水岭算法的过分 割 问 题，又 保留了显著区域的重 要 目 标。 另 外，可以根据图像 特 点 和 具 体的分割要求，调整分割过程中所选参数，得到不同的图像分 割效果，具有一定的灵活性。（上 接 第 页 ）结构元素的最大半径 、 邻域像素中活着的像素数 以 及 演化所用时间。 如果分割过程中选用的参数不同，分割结果 也有很大不同。 如 的选取将影响图像 分割的区域个数和 分割细节，参数取值越小，被形态

21、学开闭重构运算滤除的小于 结构元素的细小成分越少，在标记过程中标记出的大于阈值 的极小值越多，所以图像分割出的区域数目越多，分割出的细 节越多。 在此试验中， 依据所选图像的 灰度直方图的最小 阈值来选取，对于图（）的“”图像，。 结构 元素 的选择，由于提取的是区域的边缘特征，所 以 需 要 把 的值固定化。 当 时，对于提取区域的边 缘 特 征 比 较 有利。 而 和 的选择是紧密相连的，如式（）那样。 经过算 法自动进化试验，证明当 时，所提取出的区域边缘特征 连续性最佳，过小则边缘上的断点增加，过大则会产生大量的 不必要的特征。 至于 演 化 时 间 的 选 择，经过对多幅图像的 演化

22、试验证明，当时，对区域的边缘特征 的 演 化 结 果 最为理想，过小则演化出的边缘特征模糊杂乱，时间过长则演 化的边缘特征过于宽 泛，会失去许多其它特征。 因 此 设 置 仿 真系统的最大演化时间为。 图（）为采用控 制 标 记 符方法，当 ，时 对 “”图像进行分割的 结果。 图（）为 采 用 本 文 方 法，当 ， ， 时对“”图像进行分割的结果。可以看到本 文方法的分割结果更符合人的视觉特性。参 考 文 献 数 字 图 像 处 理 （ 版 ）阮 秋 琦，等译北京：电子工业出版社，： ，： ，（）： 王宇，陈殿仁，沈美丽，等基于形态学梯度重构和标记提取的分 水岭图像分割中国图象图形报，（）

23、： ： ， ： 吴昊，刘正熙，罗以宁，等改进多尺度分水岭算法在医学图像分 割中的应用计算机应用，（）： 孔俊，张竞丹，吕英华，等一种基于规则的脑组织磁共振图像分 割新方法计算机科学，（）：图分割实验结果file:/D|/我的资料/Desktop/新建文本文档.txtAppliance Error (configuration_error)Your request could not be processed because of a configuration error: Could not connect to LDAP server.For assistance, contact your network support team.file:/D|/我的资料/Desktop/新建文本文档.txt2012-07-12 20:42:52