摘 要为了精确实现非封闭曲面的三维重建提出一种基于曲面三角面片周长的阈值分割方法首 先 计 算 泊松算法生成曲面的三角面片周长选取采样点 然后通过比较样本点与原始输入点之间的欧氏距离自动计算阈值对生成曲面进行分割 实 验 结 果 表 明 该算法能准确有效地去除伪封闭曲面而不影响原生成曲面的精度 且 算 法 复杂 度 低时 间 效 率 高 鲁 棒 性 强
关 键 词泊 松 算 法三 角 面 片阈 值伪 曲 面曲 面 分 割
　　引言
　　随 着 三 维 扫 描 技 术 的 日 益 发 展三 维 点 云 模 型已大量应用于逆向工 程 计 算 机 辅 助 设 计机械制 造医 学 影 像虚拟现实和动漫等领域 但实际扫描获得的三维点云数目较 为 庞 大 边 缘 模 糊 模型的拓扑结构不清晰给曲面重建带来了很大的困难 尤其是非封闭曲面的三维重建目前仍是计算机图形学领域研究的一个难点问题
　　在 三 维 点 云 模 型 曲 面 重 建 方 法 中 已 有 多 种 曲面模型表达形式 比较常用的是隐式函数表达形式隐式函数方法大致分为全局方法和局部方法 全局拟合法通常定义隐式函数为以样本点为中心的径向基函数 的 加 权 和但易产生平凡解 无法进行重建同时因其全局性对数据的要求是完整的 封闭的对非封闭的模型往往不能重建出模型 的 曲 面 局部拟合方案是利用八叉第 期 温 佩 芝 等 一种自动的非封闭曲面三维重建方法树将散乱数据点 集 分 割 成 多 个 小 区 域 在 每 个 子 区域中应用分段二次曲面函数进行拟合然 后 用函 数 将 各 个 子区域函数加权求和拼接出全局函数 该 方 法 具 有运算速度快的优势 但不具备抗噪性 要求点云模型不能含有 噪 声 然 而采 用 算 法 对 非 封 闭 的模型曲面进行重 建 时 在非封闭的模型边缘易产生大量不规则且不合理的伪面片
　　当前曲面重建技术中的新热点 泊松 算 法结合了全局和局部拟合方法的优点 因为该算法是全局的所以在形成邻近区域和调整权重时不涉及启发式的决策但是其基函数与周围空间相关而不是与数据点相关 是局部的因此泊松重建算法具有多分辨率结构从而产生一个稀疏的矩阵系统 加快了计算的速度泊松算法还能很好地捕捉曲面的细节重建精度高于其他隐式算法 然而泊松曲面重建算法过程不引 入 与 模 型 形 态 相 关 的 信 息 故 泊 松重建的模型是水密 的对不封闭的 点 云模型它会自动重建出封闭的曲面 因此非封闭的模型曲面重建不能直接应用泊松算法
　　针对上 述 问 题 受 二 维 图 像 分 割 大 律 法阈值方 法 的 启 示本 文 提 出 一 种 基 于 曲 面 三角面片周长的阈 值 分 割 方 法引入泊松算法实现了三维非封闭曲 面 的 准 确 重 建 首 先利 用 泊 松 算 法进行三维曲面重 建 然后根据生成曲面的小三角面片的周长大小分 布 概 率 从生成的三角面片中选出比对的样本点计算样本点与原始输入点的距离根据原始点到伪平面三角点的距离明显大于原始点到模型曲面三角点 距 离 的 特 性将三角点分为伪平面三角点和模型曲 面 三 角 点 两 类计算原始输入点到模型曲面三角点 的 平 均 最 大 距 离将其设为分割阈值 保 留 距 离 小 于 的 点 而 去 除 距 离 大 于 的点即可分割出非封闭的模型曲面 实验结果表明该算法能准确有效地去除伪封闭曲面而不影响原生成曲面的精度算 法 复 杂 度 低 时 间 效 率 高 鲁 棒 性强从而解决了非封闭模型曲面三维重建的技术难题拓展了泊松算法的实际应用范围泊松重建方法泊松数学模型是输入三维模型的点集 其中的一个样本每个样本包含一 个 点 和 一 个 内 法 线 给定一个三维实体 其边界为 用 表 示 的指示函数即曲面内的点定义为 曲面外的点为表示 点 的向内曲面法线 为一个平滑滤波器 表示它到 点 的平移 平滑后的指示函数的梯度等于通过曲面法线场获得的向量场 即把物体表面 分 割 为 不 同 的 小 面 片可以根据样本点 的值和小面片面积的乘积近似计算小面片 上的积分在形成向量场 之后希望解得函数 从 而 使然而 通 常 是 不 可 积 的 即 它 是 与 路 径 相关的因此精确解一般不存在 为了找到最佳的最小二乘估计解将应用梯度算子来组成泊松方程给定一个样本点集 和 最 大 深 度 定 义 八 叉树 为每个样 本 点 都 落 在 深 度 为 的 叶 子 节 点 上的最小八叉树定义每个节点上的函数为式中 和 分别是节点 的中心和宽度为 提 高 效 率 本 文 用 一 个 简 化 的 函 数 来 近 似 单位方差滤波器使得计算的散度和拉普拉斯算子都是稀 疏 的 因 此 设 为 一 个 盒 滤 波 器 的 阶卷积其中其他为 了 达 到 子 节 点 的 精 度 避 免 采 用 叶 子 节 点 的中心近似为采样 点 的 位 置 取而代之的是使用三次线性插值法分配样本点到八个最邻近的节点 这 样可以定义曲面函数梯度场的近似值式中 为最 邻 近 的 个 深 度 为 的节点 为三次线性插值的权定义了向量场 之后希 望 求 解 函 数使得 的 梯 度 最 接 近 即 求 泊 松 方 程 的一 个 解 可 通 过 求 解 函 数 的 最 小 值 来 简 化问题给 定 维向量 其第 个坐标为 求解的目标是解 使得在空间 上 的 投计算机集成制造系统 第 卷影尽可能 接 近的 投 影 对 于 每 个 和在 处的元素设为这样解 相当于 找 到 详 细 的 泊松算法的描述请见参考文献重建结果比较图 所 示 为 算 法 和 泊 松 算 法 对 图 模型重建曲面 的 效 果 图 是不封闭的原始点云数据模 型图 是 算 法 重 建 的 模 型 曲 面 在 非封闭模型曲面的 边 界 处 算法生成的曲面不规则且存在较多不合理的伪曲面 图 为泊松算 法 重 建 的效果图 由图 可 见泊松算法重建的曲面效果比重建效果好曲面结构特征符合原始模型所生成的 曲 面 较 光 顺 但 从 实 验 结 果 也 可 以 明 显 看出对于原非封闭的曲面模型泊松算法重建自动生成了封闭的伪曲面 这给实际应用带来了诸多不便从上述实验结果可以看出 对于非封闭的模型图 的 算法重构的曲面不能正确表达原始模型的特征边缘处产生较多不规则的伪曲面 图中泊松重建的曲面 模 型 重 建 曲 面 光 顺 且 能 很 好地反映模型 的 特 征 但 只 能 重 建 出 的 封闭曲面 目前在 实 际 应 用 中 大多采用人工手动割除重建生成的多 余 的 伪 曲 面这不但需要操作人员具有较高的专业水平 而且很难确定准确的边缘 效率较低 对此受二维图像阈值分割思想的启发本文提出一种新的三维非封闭曲面重建自动阈值分割算法三维分割阈值计算为了将非封闭曲面重建出现的伪封闭曲面分割出去借鉴二维图像处 理 中 阈 值 分 割 方 法的 思 想 算法是以图像的一维直方图为依据将图像分成背景和目标两部分 以背景和目标之间的类间方差最 大 为 阈 值 选 取 准 则 此 算 法 在 二 维图像处理中能 取 得 很 好 的 分 割 效 果 但 是本 文 分割的对象是由三维点云模型重构的模型曲面 如 何将二维图像的分割思想转换到三维模型空间 研 究适用于三维模型 的 分 割 阈 值 算 法是本文研究的重点 以下为本算法的主要思想已知隐式曲面可视化是利用很多细小的三角面片去逼近实际模 型 表 面 即重构出的模型曲面由大量的三角面片构成 假设构成三角面片的三个顶点为 和 称为三角点三角面片的三边长 度 分别为 和 则三角面片周长由图 可 见泊 松 算 法 重 建 的 封 闭 曲 面模 型外三角面片的数 目 相 对 较 少构成伪封闭曲面的三角面片周长比模型曲面上的三角面片周长要大 但在模型边缘的曲面 三角面片面积逐渐增大 周长逐渐增加并没有明显的边界区分因此采用人工的方法很难准确地对生成的封闭曲面进行分割原始点云数据与重建曲面时生成的三角面片的三角点存在密 切 的 关 系 一 般 而 言 三 角 点 都 落 在原始 输 入 点 附 近 如 图 所 示 的 半 圆 球 模 型 泊 松重建后得到封闭的圆球曲面 图 中深色点为生成的封闭圆球曲面三角面片的三角点浅 色 点 为 原 始半圆球模型输入数据点 由图可知模型曲面上的三角点分布在原始 输 入 点 附 近且与原始输入点距离第 期 温 佩 芝 等 一种自动的非封闭曲面三维重建方法较近而伪平面三角点分布在原始模型输入点外侧远离 原 始 输 入 点 图 所 示 为 图 中 黑 色 方 框 放大后的点云分布 情 况 浅 色 点 为 原 始 输 入 点和 为三角点其中 为伪平面的三角点 和为模型曲面上的三角点可 见 点 到 和 的距离明显比到 的距离小 利用 这 一 特 性 根 据 重建曲面三角点的 密 度 分 布 求取原始输入点到模型曲面单位圆内三角点的平均最大距离 将 其 设 定 为分割阈值 然后分别计算原始输入点与重建曲面三 角 点 间 的 距 离 将 距 离 大 于 阈 值 的 三 角 点 去掉保留小于 阈 值 的 三 角 点 从 而 准 确 地 重 建 出非封闭模型曲面采集样本点由上述分析可知 要找到分割阈值 必须将模型曲面上的三角点与原始输入点进行距离比较 但是如果将模型曲面上所有三角点与原始输入点进行比较则计算量较大为 了 减 少 内 存 消 耗 采 集 模 型 曲面上的部分三角点作为比较的样本 由 图 可 知模型曲面的三角点基本上都落在原始输入点附近而伪封闭曲面 的 三 角 点 离 原 始 输 入 点 较 远 因 此可以通过采集部分在模型曲面上的三角点作为比较的样本点 因为位于模型曲面上的三角面片周长较小数目较多出 现 相 同 周 长 的 概 率 越 大所 以 可 以通过计算生成三 角 面 片 的 周 长按相同周长出现的概率大小采集样本点来计算阈值假设泊松算法进行模型重建时生成的三角面片的边的集合 为 重 建 模型上全部三角面片的个数 则每个三角面片的周长按以下步骤采集样本点步骤 按 像 素 的 概 念 将 每 个 周 长 同 乘 以一个倍数扩大到整数步骤 将 的 最 小 值 标 记 为 最 大 值标记为 则三角面片 周 长 的 大 小 范 围 为其中周长 为 的三角面片的总个数为分布概率为步骤 将分布概率由大到小进行排列 选 取前面分布概 率 大 的 个 周 长 对 应的三角面片为样本 每个周长对应 个三角点则一共有 个样本点将样本点 集 合 记 为实 际 计 算 时 可根据经验随机选取一个适当的 来采集样本点阈值计算为了割除泊松算法对非封闭点云数据重建生成的伪封闭曲面需要找到一个自适应阈值来自动保留非封闭曲面模 型 边 界 内 的 点而除去模型边界外的点 首先计算 以 上 获 得 的 个样本点与原始输入点的距离假设原始输入 点 的 个 数 为 则 原 始 输入点 的 集 合 对 应 法 向 量 的 集 合则 每 个 样 本 点 到 原 始 输入点集的欧氏距离将 按列固定每列由小 到 大 进 行 排 列 设 生成曲面模型对应 的 点 云 数 目 为 则 生 成 曲 面 前 后点云数目的比例如果输入原始点云数据的密度为 即 以 某 点为中心的单位圆内点的数目 则 生 成 新 的 点 云 密度为取 的第 行计算平均值计算机集成制造系统 第 卷由此可知 为 个采 样 点 到 原 始 输 入 点 的 平均最大距离 因为模型采集得到的点云数据分布较均匀采用 来表 示 整 个 模 型 曲 面 三 角 点 到 原 始 输入点的平均最大 距 离 能够很好地区分模型曲面上的三角点和伪平 面 上 的 三 角 点所 以 将 作 为 封 闭曲面分割的阈值曲面分割对 泊 松 算 法 生 成 的 封 闭 曲 面 进 行 分 割 取 曲 面的分割阈值 分割步骤如下步骤 设 生 成 曲 面 的 点 云 数 据 的 集 合对应法向量的集合遍历每个 如果满足则将 标记为 即保留此点如果不满足则标 记为 即为要割除的点步骤 去除含有标记 为 的 三 角 点 的 三 角 面片保留标记为 的三角点的三角面片 从而完成伪封闭曲面的割除 得到真实的非封闭模型曲面实验结果在 和 环 境 中 实 现 了 上 述算法计 算 机 硬 件 配 置 为内存 对 组非封闭的点云模型进行泊松三维重建及分割 实 验 实 验 结 果 表 明 使 用 本 文 算 法对泊松三维重建生成的伪封闭曲面均能取得较好的分割效果且算法鲁棒性强 稳定可靠 下面给出部分实验结果其中模型的分割阈值如表 所示图 和图 所示为明显的不封闭模型 图 是马体 模 型 的 分 割 效 果 图 从 图 可 以 看 出原 始 点云是不封闭的模型 图 是泊松算法自动重建出的模型封闭曲面利用本文算法计算出分割阈值可以很好地将封闭的曲面分割出来 分割结果准确分割边缘 光 顺 如 图 所 示 对 图 的 髋 部非封闭模型利用本算法也能准确有效地将封闭的伪曲面分割出去 如图 所示表 模 型 分 割 阈 值模 型 模 型 大 小 分 割 阈 值图图图图图图 和图 是一组比较理想的扫描模型使 用本算法对模型进行分割能取得很好的效果 但在实际的三维模型采集中 采集的数据往往各式各样 为了说明本算法的 稳 健 性 采用多组斯坦福大学采集的三维扫 描 数 据 进 行 实 验 本 文 给 出 三 组 数 据的实验结果及对 比 分 析 带有法向量的点云数据如图 所 示图 和 图 为 兔 子 模 型 多 视 角 的 显 示效果 由图 可 知扫描的三维数据由实际数据采集模型都是不封闭且边缘复杂不规则的 明显增加了分割的难度 图 所示为图 中点云模型的泊松重建曲面模型由 图 可 见 重建的模型都是封闭的图 所示为本文分割算法计算获得的曲面模型 由图可知使用本算法能很好地将封闭曲面分割出来且都很好地还原了原始模型复杂不规则的边缘 对比图 图 和图 黑色方框内的曲面部分可知本文算法能够能很好地分割出点云的边界 同 时 重建的曲面仍具有隐式曲面的特点而且能够很好地还原模型的原始边界特征 通过大量实验结果对比分析可知采用本文所提算法能够使绝大部分非封闭三维点云模型都能获得高质量的非封闭曲面模型充分验证了本算法的稳健性为进一步验证本文算法的有效性将图 图第 期 温 佩 芝 等 一种自动的非封闭曲面三维重建方法中的 点 云 数 据 利 用 基 于 的 算 法 进 行 重建 结果 如 图 所 示 基 于 的 算 法 是 一种显示方 法当 点 云 质 量 不 好 或 较 稀 疏 时 基 于的结果并不 理 想 如 图 黑 色 方 框 中模型的耳朵部分重建曲面出现了明显的残缺 而本文所提算法是建立在隐式曲面重建的基础上 因 此对点云质量较差和密度稀疏的情况均能获得理想的结果 对比图 黑 色 方 框 中 模 型 耳 朵 部 分的重建效果可以 看 出 本文方法能取得更好的重建结果计算机集成制造系统 第 卷
　　结束语
　　本文提出一种自动阈值分割的非封闭曲面三维重建方法能快速准确地对泊松算法生成的封闭曲面进行分割自动去除非封闭曲面重建时生成的多余伪曲面 大量 实 验 证 明 使用本算法可得到精确的分割效果算法 的 鲁 棒 性 强 算 法 复 杂 度 低 所 需的时间复杂度为 而且算法简单易实现为 泊松曲面重建算法在逆向工程领域中的非封闭点云数据进行直接重建奠定了良好的基础 本文所提方法是在泊松算法重建得到伪封闭模型曲面的基础上采用阈值分割的方法除去伪曲面而得到与点云一致的非封闭模型 如何能对非封闭点云数据直接进行高质量的曲面重建 进一步提高算法的通用性 是今后研究的重点
    参考文献吕 震柯 映 林孙 庆等反求工程中过渡曲面特征提取算 法 研 究 计算机集成制造系统成 思 源余 国 鑫张 湘 伟逆向系统曲面模型重建方法研究 计算机集成制造系统史 宝 全梁 晋刘 青等基于约束搜索球的点云数据与 模 型 精 确 比 对 检 测计算机集成制造系统张 桃 红韩彦 岭涂 孟 夫等径向基函数网络在虚拟加工对象重构中的应 用 计算机集成制造系统付 忠 良 一些新的图像阈值选取方法 计 算 机 应用