Transcription

1 中 图 分 类 号 :TP391.9 论 文 编 号 :10006SY 硕 士 学 位 论 文 面 向 点 模 型 的 多 尺 度 特 征 分 析 方 法 研 究 作 者 姓 名 学 科 专 业 指 导 教 师 培 养 院 系 阎 亚 杰 计 算 机 应 用 技 术 梁 晓 辉 副 教 授 计 算 机 学 院

2

3 The Research of Method for Analyzng Pont Models Orented Mult-scale Features A Dssertaton Submtted for the Degree of Master Canddate:Yaje Yan Supervsor:Assocate Prof. Lang Xaohu School of Computer Scence & Engneerng Behang Unversty, Bejng, Chna

4 中 图 分 类 号 :TP391.9 论 文 编 号 :10006SY 硕 士 学 位 论 文 面 向 点 模 型 的 多 尺 度 特 征 分 析 方 法 研 究 作 者 姓 名 阎 亚 杰 申 请 学 位 级 别 工 学 硕 士 指 导 教 师 姓 名 梁 晓 辉 职 称 副 教 授 学 科 专 业 计 算 机 应 用 技 术 研 究 方 向 虚 拟 现 实 学 习 时 间 自 年 月 日 起 至 年 月 日 止 论 文 提 交 日 期 年 月 日 论 文 答 辩 日 期 年 月 日 学 位 授 予 单 位 北 京 航 空 航 天 大 学 学 位 授 予 日 期 年 月 日

5 关 于 学 位 论 文 的 独 创 性 声 明 本 人 郑 重 声 明 : 所 呈 交 的 论 文 是 本 人 在 指 导 教 师 指 导 下 独 立 进 行 研 究 工 作 所 取 得 的 成 果, 论 文 中 有 关 资 料 和 数 据 是 实 事 求 是 的 尽 我 所 知, 除 文 中 已 经 加 以 标 注 和 致 谢 外, 本 论 文 不 包 含 其 他 人 已 经 发 表 或 撰 写 的 研 究 成 果, 也 不 包 含 本 人 或 他 人 为 获 得 北 京 航 空 航 天 大 学 或 其 它 教 育 机 构 的 学 位 或 学 历 证 书 而 使 用 过 的 材 料 与 我 一 同 工 作 的 同 志 对 研 究 所 做 的 任 何 贡 献 均 已 在 论 文 中 作 出 了 明 确 的 说 明 若 有 不 实 之 处, 本 人 愿 意 承 担 相 关 法 律 责 任 学 位 论 文 作 者 签 名 : 日 期 : 年 月 日 学 位 论 文 使 用 授 权 书 本 人 完 全 同 意 北 京 航 空 航 天 大 学 有 权 使 用 本 学 位 论 文 ( 包 括 但 不 限 于 其 印 刷 版 和 电 子 版 ), 使 用 方 式 包 括 但 不 限 于 : 保 留 学 位 论 文, 按 规 定 向 国 家 有 关 部 门 ( 机 构 ) 送 交 学 位 论 文, 以 学 术 交 流 为 目 的 赠 送 和 交 换 学 位 论 文, 允 许 学 位 论 文 被 查 阅 借 阅 和 复 印, 将 学 位 论 文 的 全 部 或 部 分 内 容 编 入 有 关 数 据 库 进 行 检 索, 采 用 影 印 缩 印 或 其 他 复 制 手 段 保 存 学 位 论 文 保 密 学 位 论 文 在 解 密 后 的 使 用 授 权 同 上 学 位 论 文 作 者 签 名 : 日 期 : 年 月 日 指 导 教 师 签 名 : 日 期 : 年 月 日

6

7 摘 要 近 年 来, 数 字 几 何 成 为 继 音 频 图 像 视 频 的 第 四 代 媒 体 因 其 与 现 实 世 界 物 体 具 有 相 同 的 维 度, 与 传 统 媒 体 相 比, 可 以 提 供 更 加 丰 富 的 信 息 以 及 更 好 的 交 互 能 力, 深 受 工 业 界 教 育 界 的 欢 迎 由 于 数 字 几 何 的 主 要 作 用 之 一 是 通 过 忠 实 反 映 三 维 物 体 的 外 观 形 态 从 而 帮 助 信 息 交 流, 而 特 征 在 外 形 表 达 过 程 中 非 常 重 要, 在 数 字 几 何 的 研 究 领 域 中, 特 征 分 析 渐 渐 成 为 热 点 现 有 主 流 的 数 字 几 何 表 示 方 法 包 括 参 数 曲 面, 样 条 曲 面, 三 角 面 片, 点 模 型 以 及 隐 式 曲 面 等 点 模 型 相 对 于 其 他 表 示 方 法, 有 其 独 特 的 优 势, 特 别 是 无 拓 扑 结 构 使 其 广 泛 应 用 在 模 型 的 多 分 辨 率 传 输 无 网 格 有 限 元 分 析 等 方 面 然 而, 现 有 的 特 征 分 析 多 集 中 于 面 片 模 型, 基 于 点 模 型 的 特 征 分 析 并 不 多 见 有 鉴 于 此, 本 文 围 绕 点 模 型, 研 究 和 利 用 一 种 基 于 拟 合 的 特 征 线 定 位 与 提 取 方 法 对 模 型 进 行 简 化, 进 一 步 构 建 模 型 的 恢 复 算 法 并 将 其 应 用 在 远 程 绘 制 的 系 统 中, 从 而 在 减 少 传 输 数 据 的 同 时 仍 可 以 为 用 户 展 示 模 型 大 致 轮 廓 和 一 些 关 键 形 状 特 征 首 先, 本 文 针 对 点 模 型 提 出 了 一 种 基 于 拟 合 的 多 尺 度 特 征 线 提 取 算 法, 该 方 法 基 于 Ohtake 2004 年 的 网 格 脊 / 谷 线 提 取 算 法 本 文 将 其 推 广 至 点 模 型, 并 重 点 解 决 了 一 系 列 由 点 模 型 本 身 特 点 带 来 的 问 题 实 验 证 明 本 文 方 法 可 以 较 好 的 从 复 杂 点 模 型 表 面 提 取 特 征, 所 提 取 的 不 同 尺 度 下 的 特 征 线 可 以 反 映 不 同 程 度 的 曲 面 细 节 接 下 来, 由 于 本 文 提 取 的 特 征 线 具 有 很 好 的 曲 面 表 达 能 力, 因 此 本 文 提 出 使 用 特 征 线 构 造 曲 面 的 一 种 简 化 表 示, 应 用 到 远 程 绘 制 系 统 中 为 此, 首 先 给 出 了 一 种 基 于 特 征 的 模 型 表 示 的 定 义 然 后, 使 用 本 文 提 出 的 一 种 基 于 特 征 的 分 割 方 法 以 及 重 拟 合 获 得 满 足 定 义 的 曲 面 表 示 通 过 与 等 值 面 提 取 算 法 的 结 合, 证 明 了 该 表 示 较 好 的 捕 捉 到 了 曲 面 的 整 体 走 势 以 及 一 些 重 要 的 细 节 最 后, 本 文 给 出 了 一 个 集 成 了 以 上 研 究 内 容 的 远 程 绘 制 系 统 该 系 统 的 客 户 端 包 括 主 流 移 动 终 端 和 桌 面 PC 机 实 验 结 果 表 明, 在 保 持 了 较 好 的 视 觉 效 果 的 同 时, 本 文 基 于 特 征 的 研 究 可 以 明 显 减 少 远 程 绘 制 中 的 数 据 传 输 量 关 键 词 : 数 字 几 何 点 模 型 特 征 脊 线 模 型 表 示

8 Abstract In recent years, dgtal geometry (DG) has emerged as the fourth meda succeedng audo, mage, and vdeo. Due to ts same dmensonalty wth the real world and thus enablng better nteracton and rcher content, DG s welcomed everywhere n ndustres and areas of educaton. In addton, snce one of the man purposes of DG s to facltate communcaton by fathfully modelng the appearance of a real-world object, ncreasng attenton has been pad to the analyss of features as features are of vtal poston n conveyng the shape of geometry. Current man stream DG representatons nclude parametrc surface, trangle mesh, pont model, and mplct surface. Among those, pont model stands out for ts wthout topologcal structure, makng t popular n applcatons lke mult-resoluton transmsson, and meshless FEM, etc. Yet, features detecton and extracton on the pont-based representaton are less consdered. Therefore, ths thess studes a feature lnes detecton and extracton method on pont models va mplct fttng. Ths work s lastly appled to a remote renderng system to provde a rough dea of the orgnal model wth key features of the surface preserved usng only very compact set of data. Frst of all, we extend the rdge/valley lnes extracton method proposed by Ohtake et al.n 2004 to the doman of pont models, and above all, address several problems caused by specfc propertes of pont models. The experments valdate that our method can extract good features from complex and large scale pont models. Second, we propose a compact encodng scheme for pont models motvated by the fact that the feature lnes extracted by our method are good surface descrptors. To do ths, the defnton for features-based representaton s frstly gven. An nstance of ths representaton s then constructed by our segmentaton method guded by features, followed by a re-fttng process. Fnally, ths representaton s combned wth os-surface extracton methods to show t well captures the general shape and some crtcal features. At last, we ntegrate above technques nto a remote renderng system we bult, wth manstream moble devce as well as PC as clents. The expermental results show that the

9 proposed methods can mantan a good vsual experence of the pont models, and mean whle substantally reduce amount of transmsson. Keywords: Dgtal Geometry, Pont Model, Feature, Rdge Lne, Model Representaton

10 目 录 第 一 章 绪 论 论 文 的 选 题 背 景 与 意 义 数 字 几 何 数 字 几 何 表 示 及 点 模 型 数 字 几 何 处 理 特 征 在 几 何 处 理 中 的 地 位 本 文 工 作 及 组 织 安 排 论 文 课 题 来 源 论 文 研 究 内 容 论 文 组 织 安 排... 8 第 二 章 几 何 模 型 表 面 特 征 分 析 概 述 特 征 与 传 统 微 分 量 图 像 中 的 特 征 提 取 数 字 几 何 中 的 特 征 提 取 数 学 背 景 知 识 曲 面 法 曲 率, 主 曲 率, 主 方 向 尺 度 空 间 本 章 小 结 第 三 章 基 于 拟 合 的 特 征 提 取 算 法 拟 合 构 造 隐 式 曲 面 拟 合 问 题 描 述 本 文 拟 合 过 程 解 析 计 算 微 分 量 提 取 特 征 线 近 似 恢 复 局 部 拓 扑 提 取 特 征 点 并 连 线 特 征 线 后 处 理 实 验 结 果 与 分 析 本 章 小 结 v

11 第 四 章 基 于 特 征 的 模 型 表 示 与 恢 复 基 于 特 征 的 模 型 表 示 基 于 特 征 的 模 型 恢 复 Marchng Cube Ray Castng 本 章 小 结 第 五 章 基 于 特 征 的 远 程 绘 制 系 统 移 动 终 端 现 状 远 程 绘 制 系 统 体 系 结 构 实 验 结 果 与 分 析 本 章 小 结 结 论 和 展 望 论 文 工 作 总 结 进 一 步 工 作 展 望 参 考 文 献 附 录 A 攻 读 硕 士 学 位 期 间 取 得 的 学 术 成 果 致 谢 v

12 图 目 图 1 几 种 媒 介 的 发 展 [1]... 1 图 2 大 卫 模 型... 2 图 3 几 种 参 数 化 方 法... 4 图 4 特 征 在 几 何 处 理 中 的 地 位 和 作 用... 5 图 5 数 字 几 何 中 的 特 征 线 图 6 局 部 拟 合 ( 左 ) 与 球 体 积 领 域 PCA( 右 ) 的 比 较 图 7 曲 面 上 一 点 处 不 同 度 量 下 的 测 地 线 圈 图 8 La 等 人 的 特 征 提 取 方 法 图 9 AGD 可 视 化 结 果 图 10 使 用 Heat Kernel Sgnature 定 位 突 起 的 地 方 [38] 图 11 曲 面 X 示 意 图 图 12 法 截 面 图 13 基 于 拟 合 的 特 征 提 取 算 法 流 程 图 14 拟 合 中 的 插 值 与 近 似 [41] 图 15 拟 合 流 程 图 图 16 局 部 MLS 拟 合 流 程 图 17 类 高 斯 权 函 数 图 18 投 影 过 程 示 意 图 图 19 提 取 特 征 线 流 程 图 20 对 p 的 邻 域 重 构 局 部 拓 扑 图 21 邻 域 筛 选 前 后 拓 扑 重 构 对 比 图 图 22 近 似 一 环 邻 域 选 取 策 略 [46] 图 23 筛 选 前 后 特 征 线 对 比 图 图 24 脊 点 应 满 足 的 第 三 个 条 件 图 25 三 种 连 接 脊 线 的 方 式 图 26 待 处 理 特 征 线 示 例 图 图 27 后 处 理 特 征 线 流 程 v

13 图 28 去 除 环 路 前 ( 左 ) 与 去 除 环 路 后 ( 右 ) 对 比 图 图 29 去 除 分 叉 前 ( 左 ) 与 去 除 分 叉 后 ( 右 ) 对 比 图 图 30 基 于 PCA 的 平 滑 示 意 图 图 31 平 滑 前 ( 左 ) 与 平 滑 后 ( 右 ) 对 比 图 图 32 过 滤 前 后 对 比 图 图 33 下 采 样 前 ( 左 ) 与 下 采 样 后 ( 右 ) 对 比 图 图 34 计 算 隐 式 曲 面 归 一 化 梯 度 得 到 的 法 向 量 场 图 35 计 算 每 点 在 隐 式 曲 面 上 的 投 影 图 36 多 个 尺 度 下 的 最 大 主 曲 率 kmax 图 37 多 个 尺 度 下 的 最 小 主 曲 率 kmn 图 38 主 方 向 与 脊 线 可 视 化 结 果 图 39 不 同 尺 度 下 提 取 的 特 征 线 图 40 一 组 基 于 特 征 的 点 模 型 分 割 结 果 图 41 Marchng Cubes 中 的 二 义 性 图 42 体 元 的 分 类 [49] 图 43 利 用 空 间 一 致 性 加 速 计 算 图 44 Igea,Armadllo,Dragon 模 型 基 于 特 征 的 模 型 表 示 恢 复 结 果 图 45 Ray Castng 过 程 示 意 图 绿 色 箭 头 表 示 局 部 拟 合 函 数 的 朝 向 图 46 PC 上 Ray Castng 绘 制 结 果 图 47 远 程 绘 制 系 统 体 系 结 构 图 48 客 户 端 恢 复 模 型 流 程 图 图 49 服 务 器 端 处 理 流 程 图 图 50 移 动 终 端 上 的 特 征 线 绘 制 图 51 在 三 种 尺 度 下 对 bunny 模 型 进 行 处 理 的 时 间 效 率 图 52 在 三 种 尺 度 下 对 Igea 模 型 进 行 处 理 的 时 间 效 率 图 53 在 三 种 尺 度 下 对 Dragon 模 型 进 行 处 理 的 时 间 效 率 图 54 在 尺 度 2 下 对 不 同 模 型 进 行 处 理 的 时 间 效 率 比 较 v

14 表 目 表 1 后 处 理 对 特 征 点 数 影 响 表 2 不 同 分 辨 率 重 建 三 角 形 个 数 表 3 不 同 剖 分 策 略 时 间 效 率 ( 单 位 : 秒 ) 表 4 空 间 一 致 性 加 速 效 率 表 5 特 征 对 数 据 传 输 量 的 影 响 v

15 北 京 航 空 航 天 大 学 硕 士 学 文 论 文 第 一 章 绪 论 本 章 节 是 全 文 的 绪 论 部 分 主 要 介 绍 了 与 本 文 研 究 相 关 的 领 域 知 识 和 概 念 首 先 介 绍 了 数 字 几 何 的 缘 起 和 发 展, 数 字 几 何 的 几 种 常 见 表 示 方 法, 数 字 几 何 处 理 算 法 的 目 标 接 着 介 绍 本 文 研 究 对 象 特 征 及 点 模 型 在 整 个 几 何 处 理 领 域 的 重 要 性 最 后 简 要 介 绍 了 文 章 的 主 要 研 究 内 容 和 之 后 的 各 个 章 节 安 排 1.1 论 文 的 选 题 背 景 与 意 义 数 字 几 何 [1] 图 1 几 种 媒 介 的 发 展 自 上 世 纪 80 年 代 后 期, 继 音 频 (sound), 图 像 (mage), 视 频 (vdeo), 数 字 几 何 开 始 作 为 第 四 大 信 息 载 体 跳 出 实 验 室 走 入 工 业 界, 受 到 广 泛 的 关 注 数 字 几 何, 顾 名 思 义, 是 指 借 助 数 字 化 技 术, 在 计 算 机 中 表 示 的 几 何 形 体 自 计 算 机 图 形 学 诞 生 之 日 起, 数 字 几 何 就 已 经 出 现 当 时 的 数 字 几 何 形 体 复 杂 程 度 低, 可 表 示 的 物 体 十 分 有 限, 应 用 也 仅 限 于 计 算 机 图 形 学 本 身 时 至 今 日, 数 字 几 何 本 身 已 经 成 为 计 算 机 图 形 学 和 应 用 数 学 的 重 要 研 究 对 象 之 一 顶 级 会 议 如 SIGGRAPH EuroGraphcs 每 年 录 取 的 论 文 约 四 分 之 一 都 集 中 在 数 字 几 何 的 研 究 同 时, 数 字 几 何 广 泛 应 用 于 工 业 设 计, 游 戏, 电 影, 等 等 其 他 领 域 同 其 他 媒 介 一 样, 数 字 几 何 具 有 传 达 信 息 的 功 能 其 主 要 目 的, 是 通 过 将 客 观 世 界 中 的 数 据 在 计 算 机 中 加 以 表 示 并 呈 现, 从 而 在 沟 通 和 决 策 中 起 到 辅 助 作 用 相 较 于 传 统 媒 介 不 同 的 是, 数 字 几 何 在 图 形 学 技 术 的 辅 助 下, 可 以 提 供 更 多 维 度 的 信 息, 以 及 更 加 丰 富 的 交 互 方 式 理 论 上, 数 字 几 何 可 以 表 示 任 意 维 度 的 信 息 但 实 际 应 用 中, 一 般 用 来 指 代 三 维 几 何 模 型 对 于 数 字 几 何 的 研 究, 主 要 集 中 在 获 取 与 处 理 两 个 方 面 数 字 几 何 之 所 以 兴 起, 除 了 计 算 机 运 算 存 储 能 力 的 提 升, 另 一 个 主 要 原 因 就 是 其 获 取 手 段 更 加 多 样, 获 取 设 备 成 本 更 加 低 廉 2000 年,Stanford 大 学 计 算 机 图 形 学 实 验 室 1

16 第 一 章 绪 论 领 导 的 Dgtal Mchelangelo 项 目 [2], 利 用 激 光 扫 描 仪 和 三 维 数 据 处 理 软 件, 数 字 化 了 一 批 文 艺 复 新 时 期 的 著 名 雕 像 如 图 2 所 示 的 大 卫 模 型 包 括 20 亿 个 多 边 形 当 前, 各 种 获 取 设 备 规 格 繁 多, 价 格 由 百 万 元 至 十 万 元 不 等, 所 获 取 的 数 字 几 何 模 型 的 数 量 和 精 度 都 有 大 幅 提 高 [2] 图 2 大 卫 模 型 左 : 采 集 模 型 渲 染 结 果 ; 右 : 采 集 过 程 为 使 数 字 几 何 发 挥 其 应 有 的 作 用, 必 须 建 立 一 套 有 效 实 用 的 数 据 结 构 和 算 法 来 对 其 表 示 和 处 理 因 此, 数 字 几 何 处 理 领 域 重 点 研 究 如 何 符 合 特 定 需 求 来 有 效 组 织 表 示 数 字 几 何 形 体, 并 设 计 相 应 算 法 来 处 理 每 个 对 象 在 传 统 媒 介 如 图 像 和 音 频 的 处 理 中 常 见 的 处 理 步 骤 包 括 去 噪 平 滑 增 强 和 编 辑 等 对 于 数 字 几 何 来 说, 仍 需 要 对 几 何 模 型 进 行 这 些 基 本 处 理, 使 其 满 足 更 高 层 应 用, 例 如 分 割 [3] 匹 配 [5] 检 索 [4] 变 形 [12], 等 数 字 几 何 表 示 及 点 模 型 数 字 几 何 模 型 的 表 示 对 于 模 型 处 理 以 及 高 层 应 用 来 说 至 关 重 要 一 般 来 说, 几 何 模 型 的 表 示 可 分 为 体 表 示 和 边 界 表 示 体 表 示 包 括 体 素 (voxel) 和 实 体 几 何 (constructve sold geometry, CSG) 边 界 表 示 有 细 分 曲 面 (subdvson surface) 参 数 曲 面 (parametrc surface) 隐 式 曲 面 (mplct surface) 多 边 形 网 格 (mesh) 和 点 模 型 (pont model) 体 表 示 不 光 可 以 在 关 注 模 型 内 部 数 据 的 应 用 中 发 挥 作 用, 更 重 要 的 是 它 可 以 看 做 二 维 图 2

17 北 京 航 空 航 天 大 学 硕 士 学 文 论 文 像 表 示 在 三 维 空 间 的 推 广 例 如 体 素 表 示 将 空 间 剖 分 成 规 则 体 元, 在 这 些 体 元 顶 点 处 定 义 的 属 性 便 可 看 做 是 三 维 图 像, 从 而 给 具 有 体 表 示 的 图 形 赋 予 了 自 然 的 参 数 域 这 样 的 观 点 将 图 像 和 三 维 几 何 模 型 统 一 在 一 个 框 架 下, 一 些 图 像 上 的 处 理 算 法 即 可 较 为 简 便 的 迁 移 至 这 样 的 框 架 下, 为 处 理 几 何 模 型 服 务 更 多 时 候, 数 字 几 何 表 示 为 一 个 边 界 模 型 其 中, 三 角 网 格 和 点 模 型 为 使 用 最 广 的 表 示 方 法 封 闭 的 几 何 模 型 表 面 可 以 看 做 是 三 维 欧 式 空 间 中 的 薄 膜, 将 空 间 分 为 内 外 两 部 分 其 中 隐 式 曲 面 最 自 然 的 定 义 了 这 种 对 空 间 的 认 知 对 于 点 模 型 和 三 角 网 格 以 及 其 他 表 示 来 说, 更 关 注 的 是 表 面 属 性 在 这 些 边 界 表 示 中, 近 年 来 点 模 型 在 多 个 方 向 受 到 关 注 它 可 直 接 由 激 光 扫 描 获 得 的 点 云 经 处 理 得 到 起 初, 点 模 型 表 示 并 不 直 接 使 用, 而 是 先 转 换 为 多 边 形 表 示 再 进 一 步 处 理 随 着 模 型 精 细 程 度 的 不 断 增 加, 三 角 网 格 模 型 已 经 达 到 几 十 万 或 上 百 万 面 片 的 规 模, 以 至 于 一 个 三 角 形 甚 至 小 于 一 个 像 素 的 大 小 [8], 从 而 带 来 了 许 多 不 必 要 的 绘 制 开 销 ; 另 外, 维 护 三 角 网 格 的 拓 扑 关 系, 使 得 这 种 表 示 在 有 大 型 拓 扑 改 变 的 变 形 出 现 时 十 分 不 便 因 此, 基 于 点 模 型 的 绘 制, 如 QSplat [9],Surface Splattng [10],EWA Splattng [11] [12], 以 及 无 网 格 的 变 形 方 法 应 运 而 生, 点 模 型 也 越 来 越 受 到 研 究 者 们 的 关 注 近 年 来, 由 于 可 忽 略 拓 扑 连 接 关 系 并 可 以 通 过 随 意 聚 类 组 织, 点 模 型 表 示 在 大 场 景 真 实 感 绘 制 中 也 得 到 了 广 泛 的 应 用 [13] 数 字 几 何 处 理 数 字 几 何 处 理 包 括 理 论 框 架 和 应 用 两 部 分 [14] 理 论 框 架 研 究 内 容 和 图 像 处 理 类 似, 即 试 图 将 传 统 信 号 处 理 的 正 交 分 析 工 具, 如 Fourer 变 换 Fast Fourer 变 换 (FFT) 小 波 变 换 等, 加 以 借 鉴 和 扩 展, 作 为 数 字 几 何 处 理 应 用 的 基 础 工 具 但 数 字 几 何 本 身 与 图 像 音 频 视 频 不 同 图 像 本 身 是 定 义 在 二 维 笛 卡 尔 坐 标 系 下 的 二 维 函 数, 音 频 是 定 义 在 时 间 这 个 一 维 空 间 上 的 一 维 函 数, 视 频 是 定 义 在 二 维 空 间 和 一 维 时 间 上 的 三 维 函 数 这 些 函 数 具 有 占 满 整 个 空 间 的 满 维 度 特 性, 即 在 整 个 定 义 域 覆 盖 的 空 间 中 处 处 有 定 义 这 使 得 这 些 信 号 具 有 天 然 的 规 则 参 数 域, 使 得 计 算 机 离 散 处 理 十 分 方 便 而 数 字 几 何 多 是 三 维 空 间 的 边 界, 除 了 特 殊 表 示 法 如 体 素 或 特 定 隐 式 曲 面 外, 大 多 数 数 字 几 何 形 体 在 边 界 的 内 部 及 外 部 都 是 没 有 定 义 的, 并 且 表 面 任 意 弯 曲 复 杂 不 规 则 且 缺 乏 连 续 性 这 些 特 点 使 得 数 字 几 何 很 少 具 有 一 个 自 然 和 规 则 的 参 数 域, 直 接 导 致 上 面 提 到 的 正 交 分 析 工 具 无 法 使 用, 这 也 是 数 字 几 何 处 理 中 的 一 个 基 本 问 题 3

18 第 一 章 绪 论 [7] 图 3 几 种 参 数 化 方 法 由 左 至 右 :{ 平 面 球 面 基 网 格 多 立 方 体 } 参 数 化 基 于 此 根 本 问 题, 以 及 一 些 其 他 应 用 需 求 ( 如, 纹 理 图 像 映 射 至 任 意 表 面 ), 学 者 们 对 参 数 化 这 一 基 本 工 具 做 了 广 泛 研 究 这 一 工 具 提 供 了 任 意 表 面 的 数 字 几 何 形 体 的 参 数 域 如 图 3 所 示, 不 同 参 数 化 过 程, 实 际 上 都 是 将 曲 面 上 每 一 个 点 通 过 一 个 一 一 映 射 对 应 至 参 数 域 ( 平 面 或 球 面 ) 上 的 一 点 在 此 基 础 上, 参 数 化 方 法 还 应 避 免 产 生 较 大 的 扭 曲 ( 表 面 上 同 一 点 在 参 数 域 的 像 映 射 回 表 面 产 生 的 差 ) 有 了 任 意 表 面 的 参 数 域 表 示, 很 多 之 前 提 到 的 正 交 工 具 就 可 以 方 便 的 应 用 在 处 理 几 何 模 型 了 周 昆 在 其 博 士 论 文 中 [14], 提 出 了 使 用 球 面 参 数 化 来 建 立 统 一 的 几 何 处 理 理 论 框 架 具 备 了 理 论 框 架, 就 可 设 计 高 通 或 低 通 滤 波 器, 支 持 常 见 的 几 何 处 理 操 作, 包 括 : 去 噪 和 光 顺 等 在 此 之 上, 几 何 形 体 的 下 采 样 和 上 采 样, 简 化, 分 割, 修 复, 压 缩 和 解 压, 以 及 检 索 等 一 系 列 高 层 次 应 用 才 成 为 可 能 特 征 在 几 何 处 理 中 的 地 位 数 字 几 何 区 别 于 传 统 的 一 个 属 性 是 它 更 多 的 依 赖 于 人 的 视 觉 感 知 系 统 以 及 更 多 的 用 户 交 互, 来 帮 助 传 达 信 息, 构 建 人 对 信 息 的 认 识 因 此, 数 字 几 何 的 表 观 形 态 十 分 重 要 如 何 使 数 字 几 何 更 好 的 表 现 用 户 希 望 的 形 体, 是 数 字 几 何 处 理 算 法 的 主 要 目 标 之 一 我 们 在 观 看 一 个 真 实 世 界 的 物 体 时, 总 是 会 直 接 注 意 到 其 外 观 上 最 醒 目 的 部 分 这 些 信 息 是 人 脑 建 立 和 加 深 对 事 物 的 认 识 的 主 要 信 息 来 源 之 一 数 字 几 何 作 为 真 实 世 界 虚 拟 化 和 数 字 化 的 基 础 工 具 之 一, 应 当 尽 量 准 确 和 真 实 的 反 映 所 表 示 的 物 体, 包 括 形 体 的 拓 扑 以 及 颜 色 等 各 种 表 观 属 性, 尤 其 是 上 文 谈 到 的 视 觉 上 显 著 的 特 点 这 些 显 著 区 域, 统 称 为 特 征 (Feature) 特 征 的 概 念 在 整 个 几 何 处 理 领 域 是 十 分 宽 泛 的 虽 然 特 征 和 视 觉 上 显 著 的 区 域 有 直 接 联 系, 但 又 有 着 各 自 的 特 点 例 如, 有 一 类 算 法 关 注 只 有 顶 点 数 据 而 无 任 何 表 观 信 息 的 几 何 模 型 对 于 这 样 的 算 法 来 说, 在 一 定 范 围 内 的 顶 点 位 置 相 对 差 别 较 大 的 区 域 被 视 4

19 北 京 航 空 航 天 大 学 硕 士 学 文 论 文 作 特 征 [15] ; 而 另 一 些 算 法 关 注 的 是 与 顶 点 位 置 相 关 的 表 观 属 性, 如 颜 色 或 透 明 度 等, 这 些 属 性 值 变 动 大 的 区 域 被 视 作 特 征 但 不 论 哪 一 类 算 法, 都 希 望 得 到 处 理 结 果 的 同 时, 能 够 较 好 的 保 留 表 面 的 特 征 [16] 例 如, 从 扫 描 设 备 获 取 的 点 云 由 于 存 在 噪 声, 需 要 经 过 去 噪 平 滑 操 作 来 使 其 满 足 之 后 的 处 理 需 求 在 此 过 程 中, 不 可 避 免 会 过 滤 掉 表 面 的 细 节 这 时, 算 法 应 具 备 去 噪 同 时 保 留 应 用 关 注 的 特 征 区 域 的 能 力 [17][18] 同 样, 对 于 定 义 在 三 维 体 空 间 的 体 数 据 (CT, 云 ) 的 平 滑 操 作, 也 希 望 具 备 保 留 特 征 的 能 力 (a) (b) (e) (c) (d) (f) 图 4 特 征 在 几 何 处 理 中 的 地 位 和 作 用 除 了 能 够 更 好 的 传 达 视 觉 信 息, 有 效 的 保 留 几 何 模 型 特 征 对 以 后 阶 段 的 处 理 步 骤 和 高 层 的 应 用 有 着 重 要 作 用 例 如, 如 图 4.a 所 示, 重 网 格 化 (remeshng) 中, 可 以 利 用 曲 面 上 的 特 征 ( 如 主 曲 率 线 ) 提 高 重 网 格 化 的 质 量 [19] 如 图 4.b, 在 模 型 分 割 时, 特 征 区 域 也 可 以 起 到 指 导 分 割 的 作 用 [19] 特 征 还 可 以 用 来 恢 复 和 增 强 曲 面 上 被 弱 化 ( 如 经 过 5

20 第 一 章 绪 论 去 噪 操 作 ) 的 区 域, 增 强 视 觉 提 示 [19], 如 图 4.c,4.f 通 过 对 曲 面 上 每 一 个 点 建 立 描 述 符, 计 算 该 点 的 显 著 程 度, 从 而 将 模 型 之 间 的 相 似 性 度 量 转 化 为 每 点 处 标 量 或 向 量 的 相 似 性 度 量 以 此 为 基 础, 可 以 更 好 的 支 持 更 高 层 的 应 用, 如 不 同 模 型 之 间 运 动 姿 态 的 迁 移, 检 索 和 匹 配 [20], 如 图 4.d 特 征 还 能 为 几 何 模 型 简 化, 非 均 匀 采 样 等 应 用 服 务 利 用 特 征 信 息, 非 均 匀 的 分 布 采 样 点, 使 得 特 征 区 域 具 备 更 高 的 采 样 率, 从 而 在 一 定 的 约 束 下 ( 如 采 样 点 数 目 ), 尽 可 能 获 得 好 的 原 始 模 型 的 逼 近 [35], 如 图 4.e 特 征 还 为 三 维 扫 描 仪 获 取 的 模 型 的 高 效 存 储 和 传 输 开 辟 了 一 条 新 的 道 路 如 今 三 维 扫 描 仪 获 取 的 点 云 数 据 可 轻 易 达 到 上 百 万 千 万 规 模 的 点 数 据 过 分 密 集 的 数 据 在 蕴 含 大 量 重 要 细 节 的 同 时, 也 掺 杂 不 必 要 的 噪 声 和 冗 余 这 些 数 据 不 但 对 我 们 理 解 模 型 本 身 造 成 障 碍, 而 且 使 得 对 点 云 存 储 传 输 处 理 及 绘 制 都 极 为 不 便 例 如, 针 对 点 模 型 的 曲 面 重 建 算 法 对 于 输 入 点 模 型 质 量 的 依 赖 很 强 虽 然 一 直 有 学 者 研 究 如 何 从 散 乱 数 据 中 发 现 其 内 蕴 的 关 系 从 而 拟 合 出 更 加 接 近 真 实 的 被 采 样 表 面, 但 毕 竟 在 失 去 曲 面 先 验 知 识 的 情 况 下, 这 种 重 建 能 力 是 有 限 的, 不 可 能 对 点 云 的 杂 乱 程 度 没 有 任 何 限 制, 这 就 要 求 输 入 的 待 重 建 点 云 数 据 尽 可 能 的 反 映 原 曲 面 的 重 要 信 息 另 外, 由 于 移 动 终 端 日 益 凸 显 的 重 要 性, 基 于 移 动 终 端 的 应 用 也 愈 加 广 泛 但 移 动 终 端 本 身 存 在 许 多 限 制, 如 无 线 网 络 带 宽 仍 有 限, 本 身 的 数 据 处 理 和 存 储 能 力 都 不 如 桌 面 PC 直 接 将 如 此 庞 大 的 模 型 传 送 给 移 动 终 端 会 占 用 大 量 带 宽 和 时 间, 同 时 移 动 终 端 本 身 也 无 法 处 理 这 些 数 据 因 此, 这 样 致 密 的 点 模 型 需 经 过 化 简 过 程, 去 粗 存 精, 将 冗 余 度 尽 可 能 降 低, 以 更 好 的 服 务 于 之 后 的 处 理 过 程 显 然, 特 征 是 一 个 很 好 的 切 入 点 特 征 可 以 很 好 的 刻 画 模 型 本 身 的 特 点 如 果 能 有 效 地 保 留 特 征, 将 更 多 的 计 算 存 储 带 宽 资 源 分 配 给 特 征, 减 少 用 于 特 征 以 外 的 部 分 的 表 示 和 处 理 的 资 源, 则 这 样 的 处 理 既 可 以 节 约 计 算 存 储 和 网 络 资 源, 又 保 留 了 模 型 大 部 分 的 表 达 能 力 之 前 谈 到 特 征 定 义 的 宽 泛, 主 要 原 因 在 于 其 尺 度 相 关 性 例 如, 有 些 算 法 着 重 处 理 局 部 特 征, 例 如 曲 面 的 局 部 凹 凸 ; 而 在 另 一 些 算 法 中, 特 征 被 认 为 是 组 成 整 个 模 型 的 几 个 主 要 部 分, 例 如 人 体 的 头 四 肢 躯 干 尽 管 特 征 随 尺 度 而 变 化, 但 一 般 而 言, 一 切 几 何 模 型 的 处 理 都 希 望 尽 可 能 的 保 持 应 用 感 兴 趣 的 尺 度 下 的 特 征 6

21 北 京 航 空 航 天 大 学 硕 士 学 文 论 文 1.2 本 文 工 作 及 组 织 安 排 综 上 所 述, 对 特 征 的 研 究, 尤 其 是 多 种 尺 度 下 特 征 的 不 同 表 现, 具 有 相 当 重 要 的 意 义 目 前, 主 流 的 模 型 边 界 表 示 中, 对 点 模 型 表 面 的 特 征 研 究 并 不 常 见 除 了 之 前 提 到 的 适 合 大 变 形 和 传 输 等 应 用 以 外, 基 于 点 模 型 的 处 理 算 法 可 以 绕 过 繁 琐 的 网 格 化 过 程, 这 使 得 这 种 模 型 表 示 方 法 具 有 很 强 的 吸 引 力 因 此, 本 论 文 以 点 模 型 为 载 体, 开 展 多 尺 度 的 特 征 提 取 方 法, 以 及 基 于 特 征 的 模 型 表 示 方 法, 并 给 出 本 文 研 究 内 容 在 移 动 终 端 点 模 型 绘 制 以 及 模 型 近 似 中 的 重 要 应 用 论 文 课 题 来 源 本 论 文 是 在 国 家 自 然 科 学 基 金 移 动 终 端 有 限 资 源 下 的 三 维 图 形 处 理 方 法 研 究 的 支 持 下 完 成 的 该 课 题 从 计 算 机 图 形 处 理 的 逼 真 性 与 实 时 性 这 一 基 本 问 题 入 手 开 展 工 作, 基 于 点 模 型 的 表 示 和 绘 制 方 法, 针 对 移 动 终 端 的 特 点 深 入 研 究 三 维 数 字 几 何 处 理 的 若 干 基 础 和 关 键 问 题, 探 索 适 合 移 动 终 端 的 模 型 高 效 表 示 和 实 时 逼 真 绘 制 算 法 随 着 移 动 终 端 的 发 展 和 普 及, 在 有 限 资 源 平 台 上 进 行 三 维 模 型 的 浏 览 逐 渐 成 为 各 行 业 包 括 医 学 教 育 科 研 影 视 的 需 求 由 于 点 模 型 无 拓 扑, 结 构 简 单, 基 于 点 模 型 的 表 示 与 绘 制 方 法 更 加 适 合 应 用 在 移 动 终 端 上 从 项 目 需 求 和 目 前 的 研 究 现 状 出 发, 本 文 将 点 模 型 的 图 形 处 理 技 术 作 为 一 个 研 究 目 标, 并 进 一 步 结 合 移 动 终 端 的 特 点, 研 究 有 限 资 源 下 的 图 形 处 理 技 术 论 文 研 究 内 容 本 文 主 要 研 究 内 容 包 括 以 下 三 个 方 面 : (1) 基 于 拟 合 的 特 征 提 取 研 究 一 种 在 点 模 型 表 面 定 位 与 提 取 特 征 线 的 方 法 一 般 的 几 何 模 型 表 示, 不 论 是 体 表 示 还 是 边 界 表 示, 都 是 对 自 然 界 连 续 变 化 的 事 物 属 性 的 离 散 逼 近 这 种 离 散 表 示, 虽 然 易 于 计 算 机 表 示 和 处 理, 但 不 可 避 免 的 丢 失 了 一 部 分 原 始 信 息, 从 而 会 导 致 进 一 步 处 理 得 到 的 数 值 结 果 无 法 令 人 满 意 对 于 数 字 几 何 的 处 理, 一 般 都 伴 随 有 对 表 面 估 算 一 阶 或 二 阶 微 分 不 变 量 的 过 程 如, 法 向 是 对 几 何 模 型 顶 点 位 置 的 一 阶 微 分 量, 曲 率 是 二 阶 微 分 量 然 而, 微 分 量 对 噪 声 不 连 续 以 及 非 均 匀 采 样 是 十 分 敏 感 的 传 统 方 法 在 几 何 模 型 上 直 接 估 算 微 分 量, 虽 然 速 度 快, 但 是 效 果 并 不 理 想 而 微 分 量 的 估 算 质 量, 直 接 7

22 第 一 章 绪 论 影 响 到 后 期 处 理 阶 段 考 虑 到 以 上 问 题, 本 文 从 函 数 逼 近 的 思 考 角 度 出 发, 选 取 了 一 种 基 于 拟 合 的 方 法 与 传 统 离 散 微 分 几 何 的 计 算 方 法 不 同, 本 文 采 用 的 方 法 对 离 散 表 示 的 几 何 模 型 并 不 直 接 处 理, 而 是 通 过 局 部 拟 合 基 函 数 从 几 何 模 型 的 散 乱 点 中 恢 复 出 内 蕴 关 系 该 方 法 具 有 坚 实 的 数 学 基 础, 借 助 微 分 几 何 中 对 曲 面 曲 率 等 高 阶 微 分 量 的 计 算 与 分 析, 从 理 论 上 保 证 了 提 取 出 的 特 征 点 的 显 著 性, 并 重 点 解 决 了 将 其 迁 移 至 点 模 型 时 由 于 点 模 型 本 身 特 点 带 来 的 问 题 通 过 选 取 适 当 的 拟 合 基 函 数, 本 方 法 可 以 重 建 几 何 模 型 的 高 阶 连 续 表 面 连 续 表 面 的 建 立 为 后 期 的 特 征 提 取 提 供 了 很 好 的 基 础 支 持 因 为 本 文 关 注 的 特 征, 即 脊 / 谷 线, 在 微 分 几 何 中 具 有 良 好 的 数 学 定 义, 连 续 曲 面 可 以 允 许 微 分 算 符 直 接 在 表 面 上 进 行 运 算 同 时, 通 过 不 同 大 小 领 域 定 义 的 多 种 尺 度 使 得 计 算 微 分 量 的 过 程 只 对 某 一 尺 度 的 变 化 较 敏 感, 从 而 过 滤 掉 小 于 该 尺 度 的 局 部 变 动 ( 噪 声 ) 这 样 不 仅 避 免 了 使 用 离 散 微 分 几 何 在 离 散 模 型 上 直 接 计 算 高 阶 微 分 量 的 不 稳 定 和 不 精 确, 使 得 提 取 出 的 特 征 更 加 自 然 和 连 续, 对 噪 声 或 局 部 过 度 微 小 细 节 不 敏 感, 而 且 为 数 字 几 何 提 供 了 更 多 一 层 的 信 息 表 达 ( 即 隐 式 曲 面 ) (2) 基 于 特 征 的 模 型 表 示 与 恢 复 由 于 特 征 蕴 含 了 大 量 的 表 面 信 息, 在 一 定 范 围 内 提 示 了 曲 面 的 变 动 趋 势, 因 此, 特 征 实 际 上 可 以 被 用 来 构 建 一 种 几 何 模 型 的 紧 致 表 示 通 过 这 种 表 示, 其 他 部 分 可 以 由 特 征 预 测 推 出, 而 不 需 要 显 示 的 存 储 本 文 提 出 整 个 曲 面 的 顶 点 信 息 可 以 由 特 征 编 码, 从 而 建 立 紧 致 的 模 型 表 示 这 种 表 示 中, 除 了 特 征 点 处 信 息 被 保 留 外, 周 围 信 息 可 以 由 特 征 处 的 拟 合 函 数 插 值 得 到 这 样 就 定 义 了 一 种 以 特 征 为 指 导 的 隐 式 边 界 模 型 表 示 该 表 示 可 以 使 用 已 有 的 等 值 面 提 取 算 法 ( 如 Marchng-Cube) 或 体 绘 制 算 法 ( 如 Ray-castng) 恢 复 得 到 更 加 适 合 绘 制 的 离 散 表 示 (3) 基 于 以 上 研 究 内 容, 本 论 文 给 出 了 一 个 基 于 特 征 的 点 模 型 远 程 绘 制 系 统 该 系 统 中, 本 论 文 算 法 被 应 用 在 移 动 终 端 的 三 维 模 型 显 示 中 经 过 论 文 算 法 处 理 的 点 模 型 满 足 了 移 动 终 端 的 显 示 限 制, 绘 制 帧 率 达 到 了 实 时 论 文 组 织 安 排 本 论 文 整 体 章 节 组 织 安 排 如 下 : 8

23 北 京 航 空 航 天 大 学 硕 士 学 文 论 文 第 一 章 绪 论 : 首 先 介 绍 数 字 几 何 的 兴 起, 明 确 数 字 几 何 的 含 义, 简 要 介 绍 数 字 几 何 的 几 种 表 示 方 法 然 后, 针 对 数 字 几 何 处 理 这 个 领 域, 阐 述 了 本 文 关 注 点 特 征 的 重 要 性, 以 及 围 绕 点 模 型 设 计 数 字 几 何 处 理 算 法 的 意 义 最 后 给 出 了 本 文 的 研 究 内 容 和 章 节 安 排 第 二 章 几 何 模 型 表 面 特 征 分 析 概 述 : 综 述 了 特 征 分 析 和 提 取 的 研 究 现 状, 介 绍 了 具 有 代 表 性 的 相 关 工 作 然 后, 紧 扣 本 文 研 究 内 容, 介 绍 了 理 解 本 文 内 容 必 须 的 数 学 概 念 和 基 本 知 识 第 三 章 基 于 拟 合 的 特 征 提 取 算 法 : 首 先 分 析 了 全 局 与 局 部 拟 合 的 区 别 接 着 给 出 了 本 文 采 用 的 拟 合 方 法 基 于 拟 合 出 的 连 续 表 面, 计 算 高 阶 微 分 量, 提 取 特 征 点, 形 成 特 征 线 最 后 给 出 实 验 结 果 与 分 析 第 四 章 基 于 特 征 的 模 型 表 示 与 恢 复 : 首 先 定 义 了 基 于 特 征 的 模 型 表 示 方 法 然 后 简 要 总 结 了 不 同 的 恢 复 策 略, 比 较 了 各 自 的 特 点 和 使 用 场 景 最 后 给 出 了 本 文 采 取 的 恢 复 策 略 重 建 得 到 的 结 果 第 五 章 基 于 特 征 的 远 程 绘 制 系 统 : 给 出 了 一 个 以 移 动 终 端 和 传 统 PC 机 为 绘 制 节 点 的 远 程 绘 制 系 统 的 体 系 结 构, 介 绍 了 体 系 结 构 的 组 成 部 分, 以 及 本 文 算 法 集 成 和 应 用 的 情 况 9

24 第 二 章 几 何 模 型 表 面 特 征 分 析 概 述 第 二 章 几 何 模 型 表 面 特 征 分 析 概 述 本 章 介 绍 特 征 分 析 与 提 取 的 相 关 工 作 首 先 给 出 了 特 征 与 传 统 微 分 量 的 关 系 以 及 在 图 像 和 几 何 处 理 中 表 达 形 式 的 区 别 与 联 系 然 后, 概 述 了 具 有 代 表 性 的 特 征 提 取 方 法, 包 括 图 像 和 图 形 中 的 特 征 检 测 方 法 最 后, 介 绍 了 和 本 文 相 关 的 重 要 数 学 概 念 和 工 具 2.1 特 征 与 传 统 微 分 量 很 多 时 候, 特 征 定 义 为 某 种 属 性 的 零 阶 一 阶 或 二 阶 导 数 的 极 值 点, 这 些 属 性 包 括, 顶 点 位 置 颜 色 以 及 亮 度, 图 像 中 多 采 用 亮 度 的 零 阶 极 值 点 来 定 义 因 为 图 像 大 部 分 的 应 用 场 景 在 于 检 索, 匹 配, 这 些 特 征 完 全 可 以 满 足 要 求 图 形 中 的 一 些 特 征 也 可 以 被 法 向 这 样 的 低 阶 微 分 量 的 变 化 极 值 来 描 述 但 大 多 数 情 况 下, 图 形 的 特 征 需 要 满 足 更 高 阶 导 数 的 极 值 [21] 图 5 数 字 几 何 中 的 特 征 线 蓝 色 表 示 脊 线, 橙 色 表 示 谷 线 在 数 字 几 何 中, 最 重 要 的 特 征 是 脊 线 (rdge lnes), 因 为 人 们 研 究 的 大 多 数 曲 面 上 都 遍 布 着 脊 线, 如 图 5 所 示 脊 线 由 脊 点 组 成, 从 传 统 微 分 几 何 观 点 看, 脊 点 是 主 曲 率 沿 曲 率 线 达 到 局 部 极 值 的 点 [21], 这 样 的 极 值 点 组 成 脊 线, 它 是 一 种 重 要 的 特 征 表 示, 也 是 被 研 究 的 最 多 的 特 征 根 据 科 学 家 对 人 眼 感 知 的 研 究, 脊 线 对 我 们 人 脑 认 知 事 物 具 有 重 要 意 义 直 观 上 来 讲, 山 峰 蜿 蜒 的 背 脊, 鼻 梁, 物 体 的 褶 皱 都 是 脊 线 有 的 文 献 中 将 取 正 值 的 脊 点 单 独 区 分 出 来, 称 为 谷 (ravne, valley), 见 图 5 橙 色 部 分 但 由 于 两 者 具 有 相 同 的 性 质, 实 际 中 对 两 者 所 采 用 的 研 究 方 法 并 没 有 什 么 不 同 以 下 我 们 会 看 到, 计 算 机 图 像 处 理 以 及 计 算 机 图 形 学 中 的 特 征 都 可 以 由 我 们 上 面 谈 10

25 北 京 航 空 航 天 大 学 硕 士 学 文 论 文 到 的 基 本 微 分 量 来 定 义, 因 此, 可 以 说 大 多 数 方 法 中 提 取 特 征 的 过 程 就 是 定 位 这 些 微 分 量 极 值 点 的 过 程 2.2 图 像 中 的 特 征 提 取 人 们 对 图 像 和 视 频 的 研 究 要 早 于 对 数 字 几 何 的 研 究, 特 征 实 际 上 已 经 在 这 些 领 域 被 广 泛 研 究, 并 为 计 算 机 视 觉 服 务 由 于 要 使 计 算 机 具 有 人 眼 的 功 能, 去 定 位 分 割 识 别 图 像 中 的 物 体, 于 是 就 提 出 了 特 征 的 概 念 在 计 算 机 视 觉 中, 特 征 广 泛 应 用 于 物 体 识 别 (recognton) 跟 踪 (trackng) 相 机 姿 态 估 计 (pose estmaton) 以 及 参 数 校 正 (calbraton) 计 算 机 视 觉 中 的 低 层 特 征 ( 或 局 部 特 征 ) 包 括 点 (corner) 边 (edge) 球 (blob), 高 层 特 征 包 括 轮 廓 (contour) 和 区 域 (regon) 等 低 层 特 征 都 与 图 像 每 点 处 某 种 属 性 值 ( 颜 色 亮 度 纹 理 ) 在 局 部 区 域 的 跳 变 有 关 一 般 地, 检 测 这 些 跳 变 点, 就 获 得 了 该 类 特 征 高 层 特 征 可 以 被 认 为 是 低 层 特 征 的 一 种 再 组 织 大 多 数 应 用, 需 要 检 测 出 的 特 征 满 足 某 些 或 全 部 不 变 性 (nvarance), 如 仿 射 不 变, 光 照 不 变 或 尺 度 不 变 等 一 般 来 说, 低 层 特 征 比 高 层 特 征 具 有 更 好 的 不 变 性 因 此, 在 这 样 的 应 用 中, 高 层 特 征 不 被 关 心, 只 需 要 特 征 的 位 置 能 在 一 段 图 像 序 列 中 被 稳 定 正 确 的 找 到 即 可 而 在 另 一 些 应 用 中, 如 人 体 识 别, 则 需 要 高 层 特 征 作 为 辅 助 本 文 这 里 只 关 注 低 层 特 征 的 提 取 较 早 的 一 类 特 征 提 取 方 法 基 于 轮 廓 线 曲 率 这 类 方 法 假 定 图 像 中 存 在 大 量 轮 廓 线, 如 规 则 线 框 图 或 CAD 图, 通 过 检 测 沿 轮 廓 线 的 切 线 曲 率 变 化 较 大 的 点 来 提 取 特 征 [22] 由 于 对 特 征 点 的 定 义 过 于 严 格, 因 此 找 出 的 特 征 点 有 时 会 大 量 分 布 于 线 的 交 汇 处, 有 的 还 会 出 现 在 圆 形 的 边 界 上 目 前 则 较 少 关 注 提 取 出 的 特 征 点 是 否 具 有 严 格 的 定 义, 只 要 求 找 出 的 特 征 点 在 单 幅 图 像 中 具 有 足 够 代 表 性 目 前 广 为 使 用 的 基 于 像 素 亮 度 的 方 法 只 具 有 很 弱 的 前 提 假 设, 适 用 于 不 同 图 像 的 特 征 提 取 主 要 思 想 是 基 于 图 像 亮 度 值 定 义 某 种 度 量, 然 后 设 定 阈 值, 留 下 度 量 值 较 大 的 点 作 为 特 征 点 这 些 方 法 本 质 上 基 于 某 种 微 分 算 子, 常 见 的 有 : (1) 基 于 Hessan 的 方 法 : [23] 使 用 二 阶 微 分 量 Hessan 算 子 的 行 列 式 值, 将 图 像 亮 度 场 视 为 表 面, 计 算 其 Gaussan 曲 率 [24] 使 用 Hessan 矩 阵 的 迹 和 行 列 式 使 得 特 征 点 具 有 仿 射 和 尺 度 不 变 性 11

26 第 二 章 几 何 模 型 表 面 特 征 分 析 概 述 SURF(Speed-Up Robust Feature) [25] 是 近 年 来 出 现 的 快 速 Hessan 矩 阵 行 列 式 方 法 该 方 法 比 SIFT(Scale Invarant Feature Transform) 具 有 更 好 的 仿 射 不 变 性 它 使 用 积 分 图 像 (ntegral mage) 来 加 速 Hessan 矩 阵 行 列 式 的 计 算, 并 使 用 可 变 尺 度 的 box flter 来 代 替 SIFT 方 法 中 的 瓶 颈 部 分, 即 生 成 多 个 图 像 金 字 塔 (2) 基 于 梯 度 的 方 法 : 定 义 关 于 亮 度 梯 度 的 度 量 来 提 取 特 征 点 也 是 一 种 常 用 的 技 术 [27] 结 合 Sobel 算 子 和 一 个 高 斯 窗 口 来 计 算 得 到 二 阶 动 量 矩 著 名 的 Harrs 角 点 检 测 算 法 利 用 该 矩 阵 的 行 列 式 以 及 迹 定 义 图 像 每 点 处 的 一 个 函 数 值, 同 时 考 虑 了 该 矩 阵 的 两 个 特 征 值 (3) 基 于 LoG(Laplacan of Gausson): Laplace 算 子 可 以 用 来 检 测 特 征 点 和 边 但 图 像 中 噪 声 或 部 分 细 节 会 影 响 检 测 结 果 因 此, 一 类 方 法 使 用 高 斯 核 来 对 图 像 预 处 理, 对 平 滑 后 的 结 果 应 用 Laplace 算 子 进 一 步 检 测 特 征 根 据 尺 度 空 间 理 论, 不 同 大 小 的 高 斯 核 函 数 生 成 的 一 系 列 平 滑 函 数 构 成 了 一 个 图 像 的 尺 度 空 间 该 空 间 可 以 用 来 做 高 效 特 征 提 取 最 经 典 的 方 法 是 SIFT [26] SIFT 方 法 对 图 像 尺 度 空 间 进 行 离 散 采 样, 生 成 图 像 金 字 塔 对 金 字 塔 每 连 续 两 层 图 像 做 差 得 到 DoG(Dfference of Gaussan), 再 检 测 极 值 点, 从 而 加 速 LoG SIFT 还 对 原 始 图 像 进 行 若 干 次 下 采 样 得 到 多 个 图 像 金 字 塔 以 检 测 经 过 了 不 同 缩 放 系 数 的 同 一 个 特 征 点 可 以 看 出, 图 像 中 的 特 征 的 检 测 多 是 基 于 微 分 量 的 精 确 或 近 似 计 算 在 下 文 将 要 介 绍 的 数 字 几 何 中 的 特 征 提 取 方 法 也 主 要 依 据 类 似 的 微 分 量 和 微 分 算 符 2.3 数 字 几 何 中 的 特 征 提 取 对 于 数 字 几 何 模 型 来 说, 微 分 量 的 计 算 和 微 分 算 子 在 表 面 上 的 运 算 是 很 多 曲 面 上 特 征 提 取 算 法 的 理 论 依 据 在 曲 面 上, 这 些 微 分 量 包 括 : 切 线, 法 向, 主 曲 率, 主 曲 率 方 向 更 高 阶 的 微 分 量 计 算 到 主 曲 率 的 二 阶 导 数 常 见 微 分 算 子 有 Laplace 算 子 和 Laplace-Beltram(LB) 算 子 长 期 以 来 的 研 究 中, 估 算 这 些 微 分 量 和 微 分 算 子 对 于 建 模 研 究 是 最 基 本 和 最 重 要 的 任 务, 也 被 大 量 用 作 定 位 提 取 特 征 由 于 直 接 离 散 这 些 微 分 量 产 生 的 结 果 十 分 不 稳 定, 因 此 三 维 模 型 表 面 的 微 分 量 计 算 一 般 都 伴 随 有 在 某 点 附 近 选 取 适 当 邻 域, 下 面 简 要 介 绍 几 种 具 有 代 表 性 的 特 征 检 测 提 取 方 法 (1) 离 散 微 分 几 何 (Dscrete Dfferental Geometry): 12

27 北 京 航 空 航 天 大 学 硕 士 学 文 论 文 由 于 数 字 几 何 多 是 离 散 表 示 的, 而 微 分 量 和 微 分 算 子 在 该 表 示 上 没 有 解 析 解, 因 此 为 了 求 解 这 些 微 分 量, 必 须 将 其 原 始 定 义 离 散 化 离 散 微 分 几 何 一 般 应 用 在 三 角 网 格 模 型 求 取 表 面 每 点 处 法 向 量 和 曲 率 等 微 分 量 Desbrun [28] 认 为 对 微 分 几 何 中 某 种 微 分 量 的 定 义 离 散 化 的 最 好 方 法 是 考 虑 该 量 在 顶 点 周 围 一 定 区 域 内 的 平 均, 这 一 区 域 一 般 选 为 计 算 点 的 一 环 邻 域 (1-rng neghborhood) 内 的 某 种 区 域 Desbrun 给 出 了 两 种 区 域 : barycentrc cells 以 及 vorono cells, 并 给 出 平 均 曲 率 在 这 两 种 区 域 上 的 计 算 方 式 同 时, 高 斯 曲 率 的 计 算 可 通 过 将 高 斯 伯 内 特 定 理 (Gauss-Bonnet theorem) 在 区 域 上 离 散 得 到 [29] Taubn 在 论 文 中 将 一 点 处 曲 率 张 量 重 写 为 : T T m kn() d t tt (2.1) 0 m2 并 证 明 了 重 写 后 的 特 征 分 解 成 分 与 主 曲 率 和 主 方 向 的 关 系 : [ e, e ]; k 3m m, k 3m m. (2.2) 计 算 出 主 曲 率, 就 可 以 设 定 阈 值, 滤 出 曲 率 值 较 大 的 点 作 为 特 征 研 究 最 广 泛 离 散 化 的 算 符 是 LB 算 符 所 有 离 散 格 式 都 采 取 如 下 形 式 : M f ( j f j f jn () x ) [ ( x ) ( x )] (2.3) M 表 示 在 离 散 网 格 M 上 LB 算 符 s 的 逼 近, N() 表 示 点 x 的 邻 域 不 同 之 处 在 于 对 权 值 的 选 取 策 略, 并 要 求 j j 1 jn () (2) 隐 式 曲 面 拟 合 (Implct Surface Fttng) 这 种 方 法 在 每 点 一 定 邻 域 内 拟 合 函 数 ( 多 为 二 次 ), 对 拟 合 函 数 的 曲 率 等 微 分 量 进 行 显 式 求 取, 并 将 此 结 果 赋 予 被 拟 合 点 拟 合 方 法 主 要 分 为 局 部 与 全 局 两 种, 对 于 局 部 拟 合, 每 点 的 微 分 量 计 算 与 其 他 点 的 拟 合 函 数 无 关 这 种 方 法 计 算 量 小, 但 只 考 虑 了 局 部 的 信 息, 产 生 的 结 果 往 往 不 连 续 ; 全 局 拟 合 策 略 中 所 有 点 都 参 与 拟 合, 并 参 与 拟 合 后 微 分 量 的 计 算 本 文 基 于 的 拟 合 方 法 介 于 全 局 与 局 部 拟 合 策 略 之 间, 是 一 种 类 全 局 的 拟 合 策 略 相 关 工 作 将 在 第 三 章 介 绍 (3) 积 分 不 变 量 (Integral Invarant) 积 分 不 变 量 的 提 出 主 要 是 为 了 避 免 在 离 散 几 何 模 型 上 直 接 求 解 微 分 量 带 来 的 不 稳 定 和 不 连 续 积 分 不 变 量 数 学 描 述 如 下 : 13

28 第 二 章 几 何 模 型 表 面 特 征 分 析 概 述 Ir ( p) f( x) dx (2.4) 其 中,D 为 点 p 处 局 部 邻 域,f 为 定 义 在 x 处 的 标 量 / 向 量 函 数 可 以 看 到, 与 微 分 量 定 义 不 同, 积 分 不 变 量 由 局 部 邻 域 积 分 定 义 通 过 改 变 邻 域 大 小, 可 得 到 多 尺 度 下 的 特 征 描 述 D 图 6 局 部 拟 合 ( 左 ) 与 球 体 积 领 域 PCA( 右 ) 的 比 较 在 Mannay 等 人 的 论 文 中 [30], 积 分 不 变 量 第 一 次 被 用 于 二 维 平 面 曲 线 Pottmann 等 [31][32] 人 将 积 分 不 变 量 推 广 至 三 维 几 何 模 型, 定 义 了 基 于 主 分 量 分 析 (PCA) 的 球 体 积 积 分 不 变 量 和 基 于 主 分 量 分 析 的 球 面 积 分 不 变 量, 并 系 统 的 证 明 了 积 分 值 与 曲 面 某 点 处 的 [34] 主 曲 率 和 主 方 向 密 切 相 关 La 等 人 在 中 提 出 自 适 应 的 选 取 邻 域 来 计 算 多 个 尺 度 下 的 积 分 不 变 量, 从 而 提 取 更 加 全 面 的 特 征 点 图 6 展 示 了 由 积 分 不 变 量 间 接 计 算 得 到 的 最 大 主 曲 率 的 可 视 化 结 果 可 以 看 到, 相 较 于 局 部 拟 合 方 法, 积 分 不 变 量 估 算 出 的 曲 率 具 有 更 好 的 连 续 性 和 稳 定 性 (4) 定 义 新 的 表 面 距 离 度 量 这 一 类 方 法 通 过 定 义 新 的 曲 面 表 面 上 的 距 离 度 量 准 则 来 发 掘 几 何 上 显 著 和 特 殊 的 点 或 区 域 其 中, 典 型 的 有 : 1) 等 照 线 度 量 (Isophotc Metrc) [33] Pottmann 在 中 引 入 等 照 线 度 量 这 一 新 的 距 离 度 量 准 则, 用 于 更 好 的 发 现 特 征 和 处 理 特 征, 并 给 出 了 该 准 则 指 引 下 的 作 用 于 曲 面 的 形 态 学 操 作 这 种 形 态 学 操 作 可 以 很 好 的 找 到 特 征 在 该 准 则 的 度 量 下, 整 个 曲 面 被 转 而 在 它 对 应 的 Gauss Map 上 进 行 描 述 由 Gauss Map 的 定 义 可 知, 曲 面 的 一 些 区 域 在 该 Map 上 被 相 对 的 放 大, 一 些 区 域 则 保 持 14

29 北 京 航 空 航 天 大 学 硕 士 学 文 论 文 相 对 的 稳 定 不 变, 且 放 大 的 区 域 都 是 那 些 法 向 量 变 动 较 大 的 区 域 而 法 向 量 变 动 较 大 的 区 域 又 往 往 是 我 们 关 注 的 特 征 区 域 这 意 味 着, 在 Gauss Map 上, 特 征 区 域 被 放 大 了, 从 而 可 以 更 加 容 易 的 提 取 到 感 兴 趣 的 特 征 区 域 图 7 曲 面 上 一 点 处 不 同 度 量 下 的 测 地 线 圈 左 : 欧 氏 度 量 ; 中 : 纯 等 照 线 度 量 ; 右 规 范 化 等 照 线 度 量 可 以 发 现, 在 等 照 线 度 量 准 则 计 算 的 测 地 线 圈 没 有 随 意 跨 过 特 征 区 域 如 图 7 所 示, 是 在 不 同 度 量 准 则 下 计 算 出 的 曲 面 一 点 周 围 的 测 地 线 圈 (geodesc crcle) 其 中, 纯 等 照 线 度 量 是 指 只 考 虑 曲 线 在 Gauss Map 的 像 的 距 离 由 于 高 斯 曲 率 为 零 处 纯 等 照 线 度 量 发 生 退 化, 因 此,[33] 建 议 使 用 将 欧 氏 距 离 与 Gauss Map 距 离 一 起 考 虑 的 规 范 化 后 的 度 量 准 则 2007 年,La 等 人 与 Pottmann 合 作 发 表 了 完 整 的 采 用 [34] 等 照 线 度 量 准 则 理 论 来 提 取 和 分 类 特 征 的 文 章 首 先 给 出 了 一 个 在 该 准 则 (La 等 人 称 为 特 征 敏 感 准 则 ) 下 的 重 网 格 化 技 术, 使 得 原 模 型 的 非 特 征 区 域 被 近 似 等 边 网 格 化, 而 其 特 征 区 域, 类 似 于 脊 谷 和 尖 叉 等 处 则 被 密 集 的 网 格 覆 盖, 如 图 8 中 左 图 所 示 根 据 此 重 网 格 化 结 果, 结 合 每 点 处 的 测 地 圆 的 形 变, 最 终 检 测 出 特 征, 如 图 8 中 右 图 所 示 图 8 La 等 人 的 特 征 提 取 方 法 ( 左 ) 特 征 敏 感 的 重 网 格 化 相 对 平 坦 区 域, 网 格 近 似 等 边 三 角, 且 分 布 均 匀 形 变 较 大 区 域 网 格 致 密, 且 多 不 规 则 ( 右 ) 基 于 重 网 格 化 结 果 的 特 征 提 取 粉 色 : 刺 ; [34] 橙 色 : 脊 ; 蓝 色 : 谷 [35] 给 出 了 在 特 征 敏 感 准 则 下 对 点 模 型 的 重 采 样 策 略 类 似 于 [34] 中 的 重 网 格 化 后 的 结 果, 该 方 法 重 采 样 后 的 点 模 型 在 特 征 区 域, 如 脊 线 处 分 布 的 区 域, 相 较 平 坦 区 域 要 更 加 密 集 15

30 第 二 章 几 何 模 型 表 面 特 征 分 析 概 述 2) 平 均 测 地 距 离 (Geodesc Dstance) 这 一 类 方 法 基 于 两 点 之 间 的 测 地 距 离, 在 每 点 处 定 义 新 的 距 离 函 数, 一 般 取 该 点 至 模 型 其 他 点 的 测 地 距 离 平 均 值, 称 为 平 均 测 地 距 离 (Averaged Geodesc Dstance,AGD) 这 样 的 距 离 函 数 可 以 侦 测 出 与 邻 域 点 几 何 上 相 差 较 大 的 点, 尖 点 处 的 函 数 值 大 于 平 点 处, 且 具 有 尺 度 不 变 的 性 质, 因 而 能 比 较 不 同 模 型 之 间 提 取 的 特 征 文 献 [37] 使 用 该 距 离 度 量 来 定 位 模 型 上 的 特 征 点, 之 后 基 于 这 些 点 分 割 模 型, 并 做 参 数 化 图 9 给 出 了 在 三 维 模 型 上 计 算 AGD 的 结 果 [36] 在 AGD 的 基 础 上 还 计 算 了 每 点 处 的 AGD 梯 度, 并 提 取 梯 度 极 值 点 作 为 特 征 点 图 9 AGD 可 视 化 结 果 红 色 绿 色 蓝 色 表 示 的 AGD 值 由 低 到 高 [37] (5) 热 方 程 (Dffuson Equaton) 求 解 热 方 程 是 定 义 在 空 间 和 时 间 上 的 偏 微 分 方 程 [40] : f( t, x) t kf ( t, x ),k 为 常 数 (2.5) 方 程 的 解 写 作 : f( t, x) Kt (, y, x) dy (2.6) Ktyx (,, ) 被 称 作 热 核 (heat kernel) 直 观 上 讲, 热 核 描 述 了 在 位 置 x 放 置 一 单 位 热 源 经 过 时 间 t 后 在 点 y 处 测 得 的 热 量 热 核 可 以 被 Laplace 矩 阵 的 无 穷 个 特 征 函 数 (egenfuncton) 表 示 : t K( t, y, x) e ( x ) ( y), 为 特 征 函 数 (2.7) 0 但 计 算 无 穷 个 特 征 函 数 现 实 中 是 不 可 能 的 基 于 该 理 论 框 架, 学 者 们 提 出 了 在 表 面 上 高 效 离 散 热 核 的 方 法, 以 此 来 提 取 特 征 点, 或 完 成 分 割 模 型 等 高 层 应 用 Sun [38] 提 出 使 用 t 时 间 后 的 x 处 的 热 残 留 值 作 为 每 点 的 描 述, 应 用 于 三 角 网 格 模 型, 见 图 10 表 面 上 突 16

31 北 京 航 空 航 天 大 学 硕 士 学 文 论 文 出 的 点 处 对 应 局 部 极 值 选 取 较 小 的 t 可 检 测 到 较 多 的 极 值, 而 放 大 t 则 可 检 测 到 较 少 但 在 更 大 尺 度 上 显 著 的 点 因 此,t 可 以 被 看 做 是 一 个 平 滑 参 数, 调 整 t 即 可 得 到 在 表 面 上 定 义 的 heat kernel 的 尺 度 空 间, 同 时 可 以 抵 抗 小 于 该 尺 度 的 表 面 细 节 或 噪 声 图 10 [38] 使 用 Heat Kernel Sgnature 定 位 突 起 的 地 方 2.4 数 学 背 景 知 识 微 分 几 何 提 供 了 方 便 的 描 述 曲 面 局 部 和 全 局 性 质 的 数 学 基 础 在 计 算 机 图 形 学 计 算 机 视 觉 以 及 模 式 识 别 中, 大 量 采 用 微 分 几 何 的 表 示 方 法 来 描 述 曲 面 如 前 所 述, 本 文 研 究 的 特 征 是 基 于 微 分 量 定 义 的 因 此, 本 节 给 出 一 些 必 备 的 微 分 几 何 基 础 知 识, 以 供 读 者 更 好 的 了 解 本 文 的 研 究 内 容 曲 面 定 义 2.1: 给 定 一 开 集 2, 点 u 3 若 有 一 映 射 X :, 开 集, 将 u 映 射 至 p, 则 称 X 为 曲 面 p 的 法 向 定 义 为 : Xu Xv x y z n X X, x y z 其 中 X u (,, ), X v (,, ). (2.8) u u u v v v u v 当 X X 大 于 0 时, 曲 面 为 常 规 曲 面, 也 就 是 指 法 向 处 处 有 定 义 且 连 续 u v 可 以 看 到, 曲 面 参 数 域 为 二 维, 值 域 是 三 维, 但 没 有 占 满 整 个 三 维 空 间, 称 为 一 个 嵌 入 (embeddng) 除 了 简 单 的 曲 面, 如 平 面 柱 面 和 球 面 等, 一 般 曲 面 的 参 数 域 都 很 难 定 义 17

32 第 二 章 几 何 模 型 表 面 特 征 分 析 概 述 X p u 2 图 11 曲 面 X 示 意 图 法 曲 率, 主 曲 率, 主 方 向 在 对 曲 线 的 研 究 中, 曲 线 切 线 由 单 一 方 向 和 正 负 号 决 定, 曲 率 也 因 此 唯 一 确 定 而 曲 面 上 任 意 点 都 有 无 数 切 线 方 向, 为 了 唯 一 确 定 曲 面 上 某 一 点 的 曲 率, 引 入 法 曲 率 的 概 念 N(p) E p C X 图 12 法 截 面 如 图 12 所 示 是 一 个 有 着 连 续 光 滑 的 法 向 量 场 的 曲 面 S N(p) 为 点 p 处 的 法 向 量 给 定 一 平 面 包 含 N, 则 它 同 时 包 含 p, 记 该 平 面 为 E, 其 与 X 的 相 交 曲 线 C 称 作 法 截 线 则 曲 线 C 在 点 p 处 的 曲 率 就 是 法 曲 率, 平 面 E 为 法 截 面 绕 着 法 向 量 N 旋 转 可 以 找 到 无 数 个 这 样 的 法 截 面, 并 由 此 定 义 相 应 的 法 曲 率 在 所 有 法 曲 率 中, 必 有 一 个 最 大 值 和 一 个 最 小 值 ( 带 符 号 ), 分 别 就 是 最 大 主 曲 率 k max 和 最 小 18

33 北 京 航 空 航 天 大 学 硕 士 学 文 论 文 主 曲 率 k mn, 而 各 自 对 应 的 切 线 分 别 为 最 大 主 方 向 t max 和 最 小 主 方 向 t mn, 且 两 个 方 向 恰 好 正 交 这 两 个 主 曲 率 实 际 描 述 了 曲 面 上 一 点 处 法 向 朝 各 个 方 向 的 变 动 范 围, 从 而 可 用 1 来 量 化 一 点 的 显 著 性 而 在 这 两 个 量 上 定 义 出 的 平 均 曲 率 : H ( kmn kmax ), 以 及 高 2 斯 曲 率 : G kmn kmax, 经 常 被 用 来 作 为 曲 面 上 每 个 点 的 描 述 符, 进 而 通 过 阈 值 筛 选 出 值 较 大 的 点 作 为 特 征 点 主 曲 率 的 定 义 还 可 以 从 另 一 方 面 出 发 曲 面 S 上 一 点 p 处 给 定 一 切 向 量 t, 法 向 量 n 沿 t 的 方 向 导 数 即 为 Wengarten 映 射, 或 Shape Operator, 记 作 : n( p t) n( p) () t tn, 其 中 tnp ( ) lm, p p ( uv, ). (2.9) 0 可 以 看 出, tnp ( ) 与 n 垂 直, 因 此 该 算 符 将 p, p p 为 S 在 p 处 的 切 向 量 空 间 显 然,Wengarten 映 射 从 另 一 个 角 度 度 量 了 朝 某 个 方 向 的 法 向 变 动 率 由 于 其 中 的 梯 度 算 子, 法 向 量 升 为 二 维 张 量, 因 此 该 映 射 对 应 一 矩 阵 直 观 上 讲, 一 个 线 性 变 换 的 特 征 向 量 可 以 刻 画 线 性 变 换 产 生 的 畸 变 方 向, 特 征 值 刻 画 畸 变 程 度 对 Wengarten 映 射 做 特 征 分 解 后 得 到 的 特 征 向 量 和 特 征 值 正 好 对 应 了 两 个 主 方 向 和 主 曲 率 第 三 个 特 征 值 恒 为 0, 特 征 方 向 与 n 平 行 一 般 计 算 中, 大 多 采 用 该 方 法 来 计 算 某 点 处 主 曲 率 和 主 方 向 需 要 注 意 的 是,Wengarten 映 射 是 定 义 在 二 维 参 数 域 上 的 一 般 来 说, 对 于 一 个 三 维 模 型 表 面, 并 不 能 容 易 的 找 到 一 个 完 整 连 续 的 二 维 参 数 域 不 过 幸 运 的 是, 以 上 算 子 在 三 维 空 间 的 定 义 域 内 依 然 成 立, 这 样 就 免 去 了 参 数 化 的 过 程 尺 度 空 间 之 前 我 们 谈 到 了 多 尺 度 的 概 念, 并 且 本 文 所 提 取 的 也 是 不 同 尺 度 下 的 特 征 尺 度 可 以 粗 浅 的 理 解 为 观 察 者 所 能 注 意 到 的 最 小 的 事 物 的 规 模 例 如, 在 搜 索 一 个 几 何 模 型 数 据 库 时, 可 以 通 过 指 定 模 型 种 类 搜 索 到 凳 子 的 模 型, 也 可 以 在 此 基 础 上 指 定 搜 索 有 四 条 腿 的 凳 子 模 型, 还 可 以 更 加 详 细 的 指 定 搜 索 凳 子 腿 表 面 具 有 特 定 花 纹 样 式 的 凳 子 模 型 这 种 所 关 注 的 精 细 程 度 由 粗 到 细 的 过 程 体 现 了 多 尺 度 的 概 念 尺 度 的 理 论 是 由 计 算 机 视 觉, 图 像 处 理, 以 及 信 号 处 理 邻 域 共 同 建 立 的 1983 年 Wtkn 的 文 章 [39] 第 一 次 将 其 引 入 图 像 信 号 的 处 理 中, 用 来 为 信 号 多 次 微 分 时 所 考 虑 的 19

34 第 二 章 几 何 模 型 表 面 特 征 分 析 概 述 邻 域 提 供 框 架, 将 信 号 组 织 在 尺 度 空 间 中, 并 对 其 进 行 量 化 分 析 给 定 一 信 号 f ( x ): d d,( 其 中 x ), 以 及 一 高 斯 滤 波 核 G( x, t),( 其 中 t 为 方 差 ), 可 得 到 该 信 号 的 尺 度 空 间 : L : d, L( x, t) G( x, t) f ( x ) (2.10) 因 此, 在 一 个 基 信 号 上 作 用 一 系 列 方 差 不 同 的 高 斯 滤 波 核 函 数, 就 得 到 了 不 同 尺 度 下 的 信 号 表 示 该 定 义 可 以 延 拓 至 包 括 图 像 音 频 和 数 字 几 何 在 内 的 所 有 信 号 类 型 在 第 三 章 中, 可 以 看 到 本 文 通 过 调 整 拟 合 时 的 邻 域 大 小 以 及 拟 合 权 函 数 参 数, 即 可 类 似 定 义 出 数 字 几 何 模 型 的 尺 度 空 间, 并 在 该 空 间 下 不 同 的 离 散 尺 度 上 求 出 多 尺 度 特 征 2.5 本 章 小 结 本 章 讨 论 了 特 征 在 图 像 和 图 形 中 的 存 在 形 式 和 提 取 方 法, 以 及 彼 此 间 的 联 系, 并 给 出 了 理 解 本 文 工 作 所 必 须 的 数 学 基 础 可 以 看 到, 图 像 和 图 形 两 个 领 域 各 自 的 特 征 定 义 及 提 取 都 基 本 依 赖 于 微 分 几 何 等 数 学 基 础, 去 精 确 或 近 似 计 算 极 值 点, 从 而 找 到 视 觉 上 显 著 且 具 有 代 表 性 的 特 征, 并 且, 尺 度 是 这 两 个 领 域 都 比 较 关 注 的 概 念 其 中, 使 用 曲 面 拟 合 的 方 法 试 图 从 散 乱 数 据 中 恢 复 出 内 在 的 函 数 关 系, 并 以 此 为 基 础 解 析 的 计 算 微 分 量, 很 好 的 借 助 了 微 分 几 何 理 论 该 类 方 法 是 本 文 提 取 特 征 的 基 本 工 具 和 出 发 点 在 下 一 章 节 中 可 以 看 到, 本 文 基 于 拟 合 的 特 征 提 取 可 以 很 好 的 从 点 模 型 的 散 乱 点 数 据 中 恢 复 出 内 蕴 的 函 数 表 达, 特 征 提 取 过 程 具 有 严 格 的 数 学 依 据 相 较 其 他 方 法 而 言, 本 文 方 法 可 以 提 取 一 些 对 本 文 展 示 的 应 用 场 景 十 分 重 要 的 特 征, 而 这 些 特 征 会 被 其 他 特 征 提 取 算 法 忽 略 20

35 北 京 航 空 航 天 大 学 硕 士 学 文 论 文 第 三 章 基 于 拟 合 的 特 征 提 取 算 法 本 章 开 始 介 绍 本 文 的 研 究 内 容 之 一, 基 于 拟 合 的 特 征 提 取 本 文 采 取 的 提 取 算 法 首 先 对 整 个 点 模 型 拟 合 构 造 出 隐 式 曲 面, 以 此 连 续 表 达 为 基 础, 在 其 上 解 析 计 算 微 分 量, 最 后 分 析 微 分 量, 定 位 和 提 取 特 征 点 并 连 线, 由 流 程 图 13 所 示 拟 合 构 造 隐 式 曲 面 解 析 计 算 微 分 量 提 取 特 征 线 图 13 基 于 拟 合 的 特 征 提 取 算 法 流 程 3.1 拟 合 构 造 隐 式 曲 面 本 文 的 特 征 提 取 算 法 严 格 从 曲 率 等 高 阶 微 分 量 的 数 学 定 义 出 发 求 解 一 直 以 来, 在 离 散 数 字 几 何 模 型 上 很 好 的 求 解 高 阶 微 分 量 是 非 常 困 难 的, 主 要 原 因 在 于 模 型 本 身 没 有 连 续 定 义, 除 非 采 样 非 常 致 密 和 均 匀, 否 则 顶 点 和 顶 点 之 间 的 变 化 会 对 微 分 量 的 求 解 产 生 很 大 影 响 即 便 是 对 于 模 型 几 何 位 置 的 一 阶 微 分 量 ( 法 线 ), 或 是 二 阶 微 分 量 ( 曲 率 ), 使 用 直 接 作 用 在 几 何 模 型 上 的 离 散 算 子 求 解 时, 都 会 在 不 同 采 样 率 的 区 域 显 出 不 连 续 的 情 形 因 此, 一 些 学 者 认 为 该 问 题 应 该 从 函 数 逼 近 的 角 度 去 考 虑 假 设 几 何 模 型 是 对 一 个 本 身 连 续 的 表 面 的 数 字 表 达, 则 可 认 为 模 型 上 的 所 有 点 是 从 这 个 连 续 变 化 的 表 面 上 采 样 得 到 的, 是 连 续 表 面 的 一 种 近 似 或 逼 近 如 果 可 以 近 似 恢 复 出 潜 藏 在 模 型 下 的 表 面 的 一 些 参 数, 用 这 些 参 数 提 供 离 散 模 型 的 连 续 刻 画, 则 一 二 阶 微 分 量, 甚 至 是 更 加 高 阶 的 微 分 量 就 可 以 在 这 个 连 续 表 达 上 解 析 的 求 解 问 题 由 此 转 化 成 如 何 从 给 定 的 有 限 数 据 中 找 到 隐 含 的 函 数 关 系 隐 式 函 数 拟 合 是 解 决 该 问 题 常 用 的 工 具 之 一 d d 定 义 在 d 维 空 间 的 隐 式 函 数 f ( x ):, x 满 足 : f( x ) c. (3.1) 21

36 第 三 章 基 于 拟 合 的 特 征 提 取 算 法 c 为 常 数 所 有 满 足 该 方 程 的 点 组 成 的 集 合 称 为 c 等 值 面, 或 c 水 平 集 因 此, 点 模 型 就 可 以 认 为 是 所 有 满 足 以 上 形 式 的 某 个 函 数 的 点 集 合 接 下 来, 就 是 用 拟 合 的 方 法 确 定 隐 式 函 数 的 具 体 形 式 一 般 来 说,c 选 为 0 图 14 拟 合 中 的 插 值 与 近 似 [41] ( a) 近 似,(b) 拟 合 根 据 拟 合 函 数 是 否 通 过 给 定 点, 拟 合 可 分 为 插 值 ( Interpolaton ) 与 近 似 (Approxmaton) 两 种, 见 图 14 之 后 可 以 看 到, 拟 合 的 类 型 可 由 权 函 数 的 选 取 决 定 拟 合 问 题 描 述 给 定 数 据 集 合 P { p [1, N] }, 构 建 函 数 f ( x ) 0, 使 所 有 给 定 数 据 满 足 方 程 组 : T b ( p1) f1 C T b ( N ) p f N. (3.2) 其 中,C 为 要 确 定 的 拟 合 函 数 的 参 数 向 量, b 为 选 取 的 基 函 数 例 如, 二 元 一 次 函 数 的 函 数 空 间 由 (1, xy, ) T 这 样 的 基 函 数 向 量 张 成 f 为 拟 合 函 数 在 p 处 的 取 值 一 般 情 况 下, N 大 于 C 中 元 素 个 数, 因 此 这 是 个 过 定 方 程 组, 求 出 的 只 能 是 最 小 二 乘 意 义 下 的 解 对 于 复 杂 的 数 据 集, 单 纯 用 某 一 个 函 数 对 所 有 数 据 做 拟 合 一 般 都 得 不 到 满 意 的 结 果, 因 为 数 据 本 身 的 变 动 细 节 很 多, 且 分 布 在 多 种 尺 度 上, 一 个 函 数 难 以 刻 画 这 些 特 点 因 此, 在 数 字 几 何 处 理 中, 整 个 模 型 的 拟 合 分 解 为 在 模 型 每 个 顶 点 处 的 拟 合, 并 最 小 化 局 部 拟 合 误 差 这 样, 由 于 拟 合 过 程 与 另 一 个 变 量, 即 拟 合 点 x 相 关, 该 技 术 称 为 移 动 最 小 二 乘 (Movng Least Squares Ft, MLS): T ( x, p1) b ( p1) f1 Cx T ( xp, N ) b ( N ) p f N. (3.3) 其 中, 为 在 点 x 处 拟 合 时 作 用 的 一 个 权 函 数, 或 惩 罚 函 数 该 函 数 一 般 依 照 距 离 来 对 权 值 做 相 应 调 整 通 过 选 取 不 同 的 权 函 数, 可 以 得 到 近 似 拟 合 或 模 拟 出 插 值 拟 合 两 种 不 22

37 北 京 航 空 航 天 大 学 硕 士 学 文 论 文 同 的 拟 合 行 为 以 上 介 绍 中, 拟 合 过 程 使 用 了 给 定 数 据 集 的 每 一 个 点 这 样 的 拟 合 称 为 全 局 拟 合 (global fttng) 另 一 种 拟 合 策 略 只 利 用 被 拟 合 点 x 周 围 的 局 部 信 息, 称 为 局 部 拟 合 (local fttng) 除 了 拟 合 步 骤 的 不 同 外, 局 部 拟 合 在 计 算 局 部 的 隐 式 表 达 式 在 某 点 处 微 分 量 时, 只 和 当 前 点 处 的 局 部 拟 合 函 数 有 关 ; 而 全 局 隐 式 函 数 需 要 考 虑 周 围 处 于 拟 合 区 域 内 的 所 有 局 部 拟 合 函 数 因 此, 基 于 全 局 拟 合 的 微 分 量 更 加 精 确 且 具 有 较 好 的 连 续 性 然 而 直 接 使 用 全 局 拟 合 计 算 复 杂 度 太 高, 需 要 复 杂 的 数 学 技 巧 加 速 计 算 本 文 采 用 [42] 中 介 绍 的 径 向 基 函 数 (Radal Bass Functon,RBF) 拟 合 方 法 这 是 一 种 类 全 局 的 MLS 拟 合 法, 可 以 理 解 为 是 全 局 拟 合 函 数 的 松 弛 版 本, 使 用 的 拟 合 函 数 具 有 紧 支 撑 (compact support) 拟 合 过 程 是 局 部 进 行 的, 即 只 考 虑 局 部 邻 域 内 ( 而 非 全 部 ) 的 点 对 拟 合 函 数 的 约 束, 具 有 较 低 的 计 算 复 杂 度, 但 在 计 算 某 点 处 微 分 量 时, 仍 考 虑 了 所 有 周 围 的 拟 合 函 数 的 影 响, 所 以, 精 确 性 有 所 保 证 局 部 拟 合 方 法 在 构 建 点 模 型 连 续 表 达 时 被 广 泛 采 用 [43] 提 出 pont set surfaces 的 概 念, 使 用 局 部 拟 合 函 数 重 建 点 模 型 采 样 的 连 续 表 面 之 后 涌 现 出 一 些 列 基 于 局 部 MLS 思 想 的 点 模 型 表 面 定 义 方 法 [44][45] 这 些 方 法 的 应 用 场 景 一 般 为 绘 制 和 上 / 下 采 样 [46] 用 球 作 为 局 部 拟 合 函 数, 在 应 用 中 给 出 了 一 个 平 均 曲 率 的 自 然 的 近 似, 但 计 算 时 仍 只 考 虑 被 计 算 点 处 的 拟 合 函 数 [42] 的 研 究 与 本 文 的 方 法 关 联 最 大, 也 是 基 于 隐 式 曲 面 去 计 算 高 阶 微 分 量 不 同 的 是 [42] 针 对 三 角 网 格 表 示, 而 本 文 针 对 点 模 型 这 一 特 殊 表 示, 在 特 征 提 取 过 程 中 解 决 了 一 系 列 点 模 型 特 有 的 问 题 同 时, 本 文 对 [42] 中 的 拟 合 策 略 进 行 了 化 简, 免 去 了 迭 代 的 步 骤, 将 算 法 降 至 O(N) 复 杂 度,N 为 拟 合 点 个 数 RBF 函 数 在 函 数 逼 近 中 广 为 使 用, 多 用 于 近 似 某 一 复 杂 无 解 析 形 式 的 函 数 关 系 若 函 数 ( x) 为 一 RBF, 则 满 足 以 下 性 质 : ( x) ( x ). (3.4) 即 函 数 值 只 与 某 一 标 量 值 有 关 在 我 们 的 拟 合 过 程 中, 这 一 标 量 值 选 为 三 维 欧 式 空 间 二 范 数 满 足 该 性 质 的 函 数 有 很 多, 根 据 具 体 应 用 可 选 取 不 同 函 数 使 用 最 广 泛 的 是 Wendland 紧 支 撑 RBF 这 也 是 [42] 中 选 取 的 函 数 由 于 和 问 题 场 景 紧 密 相 关, 本 节 的 讨 论 先 不 给 出 具 体 函 数 形 式 23

38 第 三 章 基 于 拟 合 的 特 征 提 取 算 法 本 文 拟 合 过 程 f 1 拟 合 分 解 拟 合 f f n 拟 合 图 15 拟 合 流 程 图 图 15 为 本 文 采 取 的 拟 合 方 法 的 流 程 输 入 为 点 模 型 P { p, n [1... N]}, 是 顶 点 位 置 和 法 向 量 的 集 合 拟 合 采 用 MLS 方 法 : T ( x, p1) b ( p1) f1 Cx T ( xp, N ) b ( N ) p f N. (3.5) 对 每 个 点 x p 都 进 行 一 遍 可 以 看 到, 随 着 x 变 化 的 量 有 : 权 重 函 数 值, 局 部 拟 合 函 数 的 系 数 C x, 以 及 局 部 拟 合 函 数 值 f 对 于 全 局 MLS, 选 取 的 权 重 函 数 在 所 有 的 点 处 具 有 非 负 影 响 本 处 采 用 具 有 紧 支 撑 的 RBF 权 函 数, 从 而 参 与 拟 合 的 点 处 于 拟 合 位 置 局 部 的 某 一 邻 域 所 谓 紧 支 撑, 可 以 理 解 为 函 数 值 在 一 定 范 围 r 内 非 负, 在 r 外 为 零 : 0, x r r ( x). (3.6) 0, x r 同 时, 为 拟 合 选 取 的 权 函 数 还 应 满 足 : r( x1) r( x2), f x1 x2. (3.7) 选 取 这 样 的 权 函 数 后, 传 统 MLS 拟 合 方 程 组 矩 阵 就 变 成 了 一 个 十 分 稀 疏 的 矩 阵, 对 整 个 点 模 型 的 拟 合 就 可 以 分 为 流 程 图 所 示 的 三 个 步 骤 : 步 骤 (1) 分 解 : 为 每 点 确 定 拟 合 邻 域 ; 步 骤 (2) 拟 合 : 在 确 定 的 邻 域 内 拟 合 给 定 形 式 的 函 数 ( 即 基 函 数 已 经 确 定 ), 确 定 函 数 参 数 ; 24

39 北 京 航 空 航 天 大 学 硕 士 学 文 论 文 步 骤 (3) 组 合 : 将 每 点 的 拟 合 函 数 组 合 成 整 体 模 型 的 隐 式 表 达 这 是 一 个 动 态 过 程, 需 要 在 求 解 整 体 隐 式 函 数 值 和 微 分 量 时 对 每 一 个 求 解 位 置 进 行 (1) 分 解 分 解 将 原 始 的 对 整 个 模 型 的 拟 合 分 成 多 次 局 部 拟 合, 即 将 大 规 模 的 问 题 转 换 为 多 个 局 部 化 的 小 规 模 问 题 求 解 本 文 中 采 用 k 近 邻 法 确 定 邻 域 范 围, 即 选 取 拟 合 位 置 的 k 个 最 近 邻 居 点, 令 pq k, q k 为 k 个 邻 居 中 最 远 的 邻 居 选 取 k 近 邻 可 以 使 得 与 拟 合 处 采 样 率 无 关, 即 采 样 密 度 大 则 拟 合 范 围 小, 反 之 则 相 反, 从 而 一 定 程 度 上 做 到 了 的 自 适 应 选 取 (2) 拟 合 邻 域 大 小 确 定 了 以 后, 接 下 来 就 需 要 把 邻 域 内 的 所 有 邻 居 点 当 做 给 定 数 据 点, 实 施 MLS 拟 合 过 程 为 便 于 描 述, 以 下, 我 们 把 实 施 拟 合 的 位 置 c 称 为 拟 合 中 心 在 c 处 的 MLS 过 程 如 下 流 程 图 所 示 : 建 立 局 部 坐 标 系, 执 行 坐 标 系 转 换 选 取 局 部 拟 合 基 函 数 最 小 化 局 部 拟 合 误 差 求 解 局 部 拟 合 函 数 参 数 图 16 局 部 MLS 拟 合 流 程 由 于 拟 合 在 局 部 进 行, 因 此 首 先 要 建 立 拟 合 中 心 的 局 部 坐 标 系, 并 将 邻 域 内 所 有 参 与 拟 合 过 程 的 邻 居 转 换 至 该 坐 标 系 下 构 建 方 式 如 下 : 对 于 c, 其 邻 域 为 { x x c }, 局 部 坐 标 系 为 ( u, v, w ) w 由 邻 域 内 所 有 点 的 法 线 量 加 权 平 均 决 定 : 其 中, w n. (3.8) 为 c 处 权 函 数, 描 述 了 拟 合 中 心 对 周 围 点 施 加 的 影 响, 一 定 程 度 起 到 减 弱 异 常 点 (outler) 对 拟 合 的 影 响 这 也 是 为 什 么 加 权 最 小 二 乘 ( 例 如 MLS) 在 抵 抗 噪 声 和 异 常 点 方 面 优 于 朴 素 最 小 二 乘 的 原 因 本 文 选 取 右 手 坐 标 系 进 一 步 确 定 u v 坐 标 轴 给 定 坐 标 系 后, 可 定 义 映 射 : 25

40 第 三 章 基 于 拟 合 的 特 征 提 取 算 法 R 0 T T T u u T T, 其 中 旋 转 量 R33 v, 平 移 量 T31 v c T T w w (3.9) 将 世 界 坐 标 转 换 至 局 部 坐 标 接 下 来, 选 取 局 部 拟 合 使 用 的 基 函 数 局 部 拟 合 基 函 数 的 作 用 是 近 似 局 部 区 域 的 变 动 趋 势 一 般 来 说 局 部 邻 域 内 包 含 的 数 据 量 远 大 于 拟 合 函 数 参 数 的 数 据 量 但 对 于 激 光 扫 描 获 取 的 点 数 据 来 说, 过 多 的 数 据 信 息 很 多 时 候 只 能 为 处 理 阶 段 带 来 噪 声 等 不 利 影 响, 而 局 部 拟 合 可 以 消 弭 这 些 过 多 的 细 节 一 般 来 说, 局 部 拟 合 基 函 数 应 该 具 备 两 个 性 质 : 较 好 的 贴 合 给 定 数 据 集, 同 时 滤 除 不 必 要 的 噪 声, 起 到 平 滑 作 用 可 以 看 到, 用 基 函 数 的 少 量 信 息 来 表 示 更 多 的 局 部 领 域 信 息, 实 质 上 可 用 作 一 种 有 损 的 压 缩 编 码 方 式 这 也 是 本 文 后 面 章 节 提 出 使 用 特 征 的 近 似 恢 复 模 型 时 所 依 据 的 考 虑 二 次 函 数 是 一 种 大 量 使 用 的 拟 合 基 函 数 文 献 [43] 表 示, 更 高 (3 4) 阶 的 函 数 并 没 有 起 到 比 2 阶 函 数 更 好 的 拟 合 效 果, 同 时 会 增 加 计 算 时 间 因 此, 本 文 选 取 [42] 中 给 出 的 二 阶 函 数 : b h x, y T bc, 2 2 T (,, xy ) C (,2,,,, x xy y,,,1, A B C D E F) T (3.10) 将 一 点 p 映 射 至 局 部 坐 标 系 下 的 像 表 示 为 p ' ( u, v, w) 定 义 映 射 后 的 像 与 原 象 的 误 差 度 量 准 则 如 下 [42] : g ( x ) wh u, v (3.11) 拟 合 的 目 标 就 是 调 整 基 函 数 参 数, 从 而 对 局 部 邻 域 最 小 化 这 样 的 误 差 : 亦 即 令 对 C 的 一 阶 导 数 为 零, 则 有 : 2 [ ( x) g ( )] mn x, 自 变 量 为 参 数 C (3.12) 2 2 T ( ( ) ) ( ) w,. x A C x b A bb (3.13) 因 为 总 误 差 不 小 于 零, 因 此 当 一 阶 导 数 等 于 零 处 的 C 取 值 一 定 使 该 误 差 度 量 达 到 最 小 需 要 注 意 : 其 中 矩 阵 A 是 对 称 阵, 不 一 定 可 逆 因 此, 应 当 使 用 SVD 法 稳 定 的 获 取 其 伪 逆 [42] ( 实 际 上, 该 过 程 也 可 理 解 为 拟 合 函 数 是 0 等 值 面 g ( x ) 0, 相 应 的, 误 差 度 量 准 则 可 定 义 为 g' g ( x ) 0 ) 由 此, 就 得 到 了 对 拟 合 中 心 c 的 拟 合 函 数 参 数 26

41 北 京 航 空 航 天 大 学 硕 士 学 文 论 文 以 上 两 个 过 程 对 每 个 点 都 实 施 完 成 后, 就 得 到 了 所 有 的 局 部 拟 合 函 数 这 时 进 入 第 三 步 骤 : 组 合 在 这 一 步 骤, 所 有 的 局 部 拟 合 函 数 共 同 定 义 了 整 个 曲 面 的 隐 式 表 达 式 : 其 中, 权 重 函 数 F( x ) g, ( xc ) ( x c ) j ( x c ) j j (3.14) 已 被 归 一 化, c j 表 示 对 x 有 影 响 的 拟 合 中 心 在 之 后 介 绍 的 微 分 量 计 算 中 可 以 看 到, 通 过 将 所 有 拟 合 中 心 用 KD-tree 组 织, 并 不 是 所 有 拟 合 中 心 的 权 函 数 都 需 要 参 与 归 一 化 过 程 3.2 解 析 计 算 微 分 量 构 建 好 隐 式 曲 面 后, 就 获 得 了 原 始 离 散 点 云 的 一 种 连 续 表 示 在 这 种 连 续 表 示 的 基 础 之 上, 一 些 高 阶 微 分 量 就 可 以 根 据 定 义 解 析 计 算 得 到 因 为 以 上 确 定 的 表 达 式 需 要 为 微 分 量 的 解 析 计 算 服 务, 必 须 达 到 阶 数 要 求 所 以, 首 先 确 定 为 了 提 取 特 征 需 要 计 算 的 微 分 量 的 最 高 阶 数 本 文 中 关 注 的 特 征 是 脊 ( 谷 ) 线 (rdge/valley lnes) 脊 ( 谷 ) 线 的 定 义 如 下 [21] : 最 大 ( 最 小 ) 主 曲 率 沿 其 对 应 主 方 向 上 达 到 极 大 ( 极 小 ) 值 的 点 的 连 线 脊 线 和 谷 线 呈 对 偶 关 系, 改 变 脊 线 处 曲 面 朝 向 ( 法 线 方 向 ) 即 可 得 到 谷 线 因 此, 以 下 用 脊 线 统 一 指 代 两 种 特 征 由 定 义 可 知, 脊 线 至 少 是 四 阶 微 分 量 : 主 曲 率 为 二 阶 微 分 量, 而 判 断 是 否 达 到 极 值 需 要 在 此 基 础 上 再 求 一 阶 和 二 阶 微 分 量 : 一 阶 为 零, 且 二 阶 不 等 于 零 : e e emax 0, 0, t k, max max mn max e 0, 0, k k. mn mn mn max t mn k (3.15) 其 中, e max k t max max, e mn k t mn mn 是 两 个 主 曲 率 沿 各 自 主 方 向 的 导 数, 称 为 extremalty 系 数 由 于 已 经 选 取 了 二 次 的 局 部 拟 合 基 函 数, 所 以 权 函 数 应 当 选 择 连 续 性 满 足 此 阶 数 要 求 的 函 数, 才 能 使 整 个 隐 式 曲 面 F( x ) 支 持 这 样 的 高 阶 微 分 量 的 计 算 本 文 参 考 的 拟 合 方 27

42 第 三 章 基 于 拟 合 的 特 征 提 取 算 法 [42] 法 中 使 用 的 是 Wendland RBF 基 函 数 : 4 ( r) (1 r) 4(4r 1), r xc. (3.16) 该 函 数 对 x 一 阶 导 在 r=0 处 不 连 续, 不 满 足 本 文 应 用 的 需 求 因 此, 我 们 使 用 [43] 中 给 出 的 一 种 类 高 斯 RBF 权 值 函 数 ( 图 17): 2 x c 2 2, ) e ( xc, (3.17) 来 替 代 Wendland RBF 该 函 数 具 有 C 连 续 性 下 面 给 出 需 要 计 算 的 微 分 量 以 及 中 间 量 的 简 写 表 达 式, 具 体 推 导 见 附 录 所 基 于 的 参 数 空 间 是 (x,y,z) 三 维 欧 式 空 间 (1) 梯 度 图 17 类 高 斯 权 函 数 ( 左 上 ) 二 维 全 局 定 义 ( 右 上 ) 二 维 紧 支 撑 ( 左 下 ) 三 维 全 局 定 义 横 截 面 ( 右 下 ) 三 维 紧 支 撑 横 截 面 梯 度 是 一 阶 微 分 量, 是 计 算 其 他 微 分 量 的 基 础 根 据 水 平 集 (level-set) 理 论, 梯 度 是 某 点 处 水 平 集 值 增 加 速 率 最 快 的 方 向 因 此, 隐 式 曲 面 的 法 向 量 应 该 由 梯 度 表 示 根 据 向 量 求 导 法 则, 隐 式 曲 面 的 梯 度 场 为 : Sph Sph Fnpu Fnpu F x (3.18) Sph F npu 其 中 Sph F, F npu f Sph 表 示 权 值 函 数 未 归 一 化 的 隐 式 函 数, f g. 法 向 场 为 场 值 归 一 化 的 梯 度 场 : F n (3.19) F 28

43 北 京 航 空 航 天 大 学 硕 士 学 文 论 文 (2) 主 曲 率 主 方 向 在 第 二 章 介 绍 的 主 曲 率 基 本 概 念 给 出 了 主 曲 率 kmax, kmn 和 主 方 向 tmax, tmn 的 定 义 但 一 般 求 解 并 不 直 接 从 定 义 出 发 从 前 面 介 绍 的 微 分 几 何 基 础 可 知, 定 义 在 ( uv, ) 参 数 域 的 Wengarten 算 子 的 特 征 值 与 特 征 向 量 对 应 与 最 大 最 小 主 曲 率 和 其 各 自 主 方 向 而 [47] 中 也 已 给 出 证 明, 以 上 结 论 可 以 推 广 到 三 维 ( x, y, z ) 空 间 中 在 三 维 空 间 中, Wengarten 算 子 对 应 法 向 量 场 的 梯 度 : 对 该 矩 阵 进 行 特 征 值 分 解, 转 为 求 解 以 下 特 征 方 程 : n t t k, 特 征 值 k, 特 征 向 量 t 为 主 曲 率 和 主 方 向 (3)extremalty 系 数 F n. (3.20) F 由 式 (3.21) 看 到, 最 大 ( 最 小 )extremalty 系 数 是 两 个 主 曲 率 沿 各 自 的 主 方 向 的 方 向 导 数 由 [48] 的 推 导 可 知, 对 于 隐 式 曲 面 F 其 extremalty 系 数 有 以 下 形 式 : j l j Fjl t t t 3kFj t n e k t (3.21) F 表 达 式 使 用 了 Ensten 记 法 隐 去 了 下 表, 重 复 出 现 的 下 标 与 上 标 表 示 对 该 指 标 求 和 图 18 投 影 过 程 示 意 图 由 于 类 高 斯 权 函 数 的 性 质 决 定 了 拟 合 过 程 是 对 原 始 数 据 的 近 似, 而 不 是 插 值, 即 得 到 的 最 终 隐 式 曲 面 F 不 保 证 过 每 一 个 给 定 数 据 点, 如 图 18 中 上 图 所 示 因 此, 在 每 点 29

44 第 三 章 基 于 拟 合 的 特 征 提 取 算 法 处 按 照 以 上 过 程 计 算 曲 率 等 微 分 量 之 前, 需 要 将 原 始 数 据 点 投 影 至 隐 式 曲 面 上, 如 图 18 中 下 图, 以 保 证 微 分 量 的 计 算 是 在 足 够 接 近 隐 式 曲 面 上 的 位 置 进 行 的 投 影 过 程 使 用 牛 顿 迭 代 法 : p p, p p F( p) F( p ) F( p ) F( p ), 直 至 threshold F( p ) (3.22) F( p ) 即 不 断 的 沿 当 前 位 置 处 法 向 量 反 方 向 行 驶 距 离, 直 至 该 距 离 小 于 阈 值 阈 值 F( p ) 的 选 取 与 模 型 大 小 相 关 本 文 实 验 中, 该 阈 值 一 般 选 择 为 模 型 包 围 盒 最 长 轴 大 小 的 倍 在 计 算 以 上 微 分 量 的 过 程 中, 如 何 选 择 权 值 函 数 参 与 计 算 是 个 需 要 注 意 的 问 题 理 论 上, 所 有 的 权 函 数 都 参 与 了 计 算 但 由 于 我 们 选 取 的 是 紧 支 撑 权 函 数, 每 个 拟 合 中 心 c 权 函 数 对 周 围 点 的 影 响 只 囿 于 范 围 内 因 此, 在 某 点 p 计 算 时 应 该 有 一 种 策 略, 将 影 响 大 于 0 的 权 函 数 加 入, 剔 除 那 些 影 响 为 0 的 实 际 上, 每 个 拟 合 中 心 定 义 的 权 函 数 相 当 于 把 整 个 曲 面 包 裹 在 了 一 个 球 集 合 中, 如 图 18 所 示 即, 可 以 定 义 球 集 合 S: N S V, V { x x c }. (3.23) 1 则 有 点 模 型 P S 为 加 速 计 算, 将 这 些 所 有 权 函 数 的 球 表 示 使 用 KD-tree 聚 类 组 织 起 来 每 当 计 算 p 处 微 分 量 时, 就 以 max 为 半 径 p 为 球 心, 执 行 范 围 搜 索 (range query) 所 有 落 在 搜 索 范 围 内 的 球 中 心 才 有 可 能 是 对 计 算 有 影 响 的 权 函 数 而 被 高 效 的 KD-tree 搜 索 ( 时 间 复 杂 度 为 O(logN), N 为 拟 合 中 心 个 数 ) 剔 除 的 拟 合 中 心 处 的 权 函 数 一 定 影 响 为 0 从 以 上 的 分 析 可 以 看 到, 本 文 方 法 之 所 以 可 以 支 持 多 尺 度 的 特 征 提 取, 是 由 拟 合 时 所 选 取 的 局 部 邻 域 的 大 小 决 定 的 本 文 使 用 的 权 函 数 相 当 于 一 个 高 斯 低 通 滤 波 器, 其 方 差 会 根 据 大 小 的 不 同 而 变 化 同 时, 在 不 同 邻 域 内 的 拟 合 会 滤 去 大 部 分 小 于 邻 域 尺 寸 的 细 节 结 合 将 所 有 点 投 影 到 拟 合 上 得 到 的 隐 式 函 数, 整 个 拟 合 过 程 相 当 于 对 整 个 模 型 施 加 了 一 次 卷 积 操 作, 得 到 了 某 个 尺 度 下 的 原 模 型 的 表 示 这 个 尺 度 就 可 以 由 参 量 唯 一 表 示 进 一 步, 就 可 以 提 取 出 尺 度 上 的 特 征 线 30

45 北 京 航 空 航 天 大 学 硕 士 学 文 论 文 3.3 提 取 特 征 线 提 取 特 征 线 共 分 为 三 个 步 骤 首 先 通 过 验 证 是 否 达 到 曲 率 极 值 定 位 特 征 点 位 置, 然 后 根 据 特 征 点 位 置 连 接 特 征 线, 最 后 对 得 到 的 特 征 线 进 行 剪 枝 过 滤 等 后 处 理, 如 图 19 [48] 所 示 Ohtake 等 人 对 网 格 模 型 提 取 了 脊 线 由 于 网 格 模 型 有 定 义 很 好 的 连 接 关 系, 定 位 和 提 取 特 征 时 可 以 很 方 便 的 利 用 这 些 连 接 关 系, 只 需 针 对 每 个 三 角 形 进 行 处 理 即 可 例 如 在 判 断 主 曲 率 是 否 达 到 方 向 极 值, 以 及 将 特 征 点 连 成 线 时, 这 样 的 连 接 关 系 都 能 够 提 供 重 要 的 指 导 而 点 模 型 无 拓 扑 连 接, 因 此 如 何 有 效 的 在 这 样 的 表 面 上 进 行 特 征 提 取 进 而 形 成 特 征 线 是 本 节 解 决 的 关 键 问 题 近 似 恢 复 局 部 拓 扑 提 取 特 征 点 并 连 线 特 征 线 后 处 理 图 19 提 取 特 征 线 流 程 近 似 恢 复 局 部 拓 扑 为 了 解 决 以 上 问 题, 本 文 局 部 恢 复 了 顶 点 之 间 的 拓 扑 连 接 关 系 但 这 种 恢 复 只 是 对 原 始 拓 扑 的 近 似 这 里 所 说 的 原 始 拓 扑, 是 指 通 过 三 角 化 算 法 生 成 的 模 型 三 角 网 格 表 示 但 这 样 的 拓 扑 重 构 复 杂 度 高, 且 本 文 的 目 的 不 是 为 了 精 确 得 到 全 部 拓 扑 连 接 因 此 本 文 避 免 使 用 三 角 化 算 法 恢 复 连 接 关 系 在 每 一 点 p 处, 考 虑 其 k 近 邻 构 成 的 邻 居 集 合 Q 为 了 检 测 p 处 可 能 的 脊 点, 需 要 考 虑 到 p 周 围 360 所 有 方 向 因 此,k 应 当 足 够 大 以 较 好 的 覆 盖 所 有 方 向 一 般 来 说, k 取 选 定 k 后, 需 要 重 构 出 一 种 局 部 三 角 形 连 接 关 系 假 定 Q 中 所 有 点 构 成 p 的 一 环 近 邻 为 了 重 构 此 一 环 邻 域, 需 要 以 p 为 中 心, 将 k 个 邻 居 沿 顺 时 针 ( 或 逆 时 针 ) 方 向 排 序, 然 后 按 照 排 序 顺 序 将 p 与 每 两 个 连 续 顶 点 连 成 三 角 形 此 过 程 如 图 20 所 示 31

46 第 三 章 基 于 拟 合 的 特 征 提 取 算 法 图 20 对 p 的 邻 域 重 构 局 部 拓 扑 这 里 需 要 注 意 : 一 般 p 的 真 正 一 环 邻 域 可 能 远 小 于 指 定 的 k 如 果 此 时 直 接 建 立 拓 扑 连 接, 则 会 将 较 一 环 邻 域 更 远 的 点 也 考 虑 到 局 部 拓 扑 重 构 的 过 程 中 这 样 会 导 致 局 部 的 拓 扑 连 接 存 在 很 多 的 冗 余, 不 但 会 执 行 很 多 次 无 谓 的 计 算, 同 时 也 会 对 之 后 基 于 此 拓 扑 连 接 的 特 征 点 提 取 造 成 影 响 具 体 情 况 如 图 (21 23) 所 示 图 21 邻 域 筛 选 前 后 拓 扑 重 构 对 比 图 上 : 筛 选 前 的 拓 扑 连 接 ; 下 : 剔 除 较 远 点 之 后 的 拓 扑 连 接 因 此, 本 文 首 先 对 局 部 的 k 个 邻 居 进 行 筛 选, 剔 除 掉 较 远 的 邻 居 之 后, 再 做 局 部 连 接 关 系 重 构 至 于 筛 选 策 略, 希 望 能 够 尽 可 能 多 的 保 留 真 正 意 义 上 的 一 环 邻 域 内 的 邻 居, 同 时 尽 量 剔 除 一 环 邻 域 外 的 点 因 此, 本 文 选 择 了 [46] 中 近 似 一 环 邻 域 保 留 的 策 略 该 策 略 如 图 22 所 示 : 32

47 北 京 航 空 航 天 大 学 硕 士 学 文 论 文 图 22 [46] 近 似 一 环 邻 域 选 取 策 略 图 中 p 周 围 蓝 色 的 点 表 示 按 照 欧 氏 距 离 直 接 选 取 的 k 个 近 邻 有 一 些 点 明 显 不 属 于 一 环 邻 域 内 该 策 略 伪 码 如 下 : 算 法 3.1: 剔 除 较 远 邻 居 FlterFartherNebs 输 入 : p 与 其 k 近 邻 Q 输 出 : 剔 除 远 邻 的 Q 1 for each p h Q 2 for each p j Q, j!=h 3 f normalze(p j - p h ) * normalze(p - p h ) < 0 4 Q Q { p j } 5 end f 6 end for 7 end for 其 中 normalze 子 例 程 表 示 对 向 量 的 归 一 化 操 作 由 于 每 个 邻 居 与 中 心 点 的 连 线 实 际 定 义 了 一 个 半 空 间 的 朝 向, 因 此 只 要 是 不 在 这 个 朝 向 的 半 空 间 的 点 都 应 该 认 为 是 较 远 的 点, 并 从 初 始 k 近 邻 集 合 Q 中 删 除 图 21 给 出 的 结 果 展 示 了 每 次 直 接 使 用 k 近 邻 和 使 用 了 筛 选 后 的 近 邻 恢 复 出 的 拓 扑 连 接 可 以 看 出, 执 行 了 这 样 的 筛 选 策 略 后, 恢 复 的 局 部 拓 扑 连 接 更 加 整 洁 和 紧 致, 几 乎 没 有 冗 余 而 未 使 用 筛 选 策 略 的 情 况 恢 复 出 的 连 接 杂 乱, 冗 余 较 多 筛 选 同 时 还 为 后 来 的 特 征 提 取 提 供 了 良 好 的 基 础 如 图 23 所 示, 未 进 行 筛 选 后 提 取 的 特 征 线 过 多, 且 有 许 多 分 叉, 即 便 是 已 经 执 行 了 后 处 理, 仍 然 残 留 许 多 细 碎 的 分 叉 执 行 了 筛 选 的 结 果 就 要 好 很 多 33

48 第 三 章 基 于 拟 合 的 特 征 提 取 算 法 图 23 筛 选 前 后 特 征 线 对 比 图 上 : 过 多 的 拓 扑 连 接 造 成 特 征 线 杂 乱 ; 下 : 剔 除 较 远 点 之 后 的 拓 扑 连 接 基 础 上 提 取 出 较 光 顺 的 特 征 线 提 取 特 征 点 并 连 线 局 部 拓 扑 恢 复 出 来 后, 就 可 以 检 测 特 征 点 了 因 为 恢 复 的 局 部 拓 扑 是 由 三 角 形 构 成 的, 本 文 直 接 使 用 [48] 的 检 测 方 法 对 每 个 三 角 形, 检 测 每 条 边 上 是 否 存 在 脊 点, 亦 即 边 上 是 否 存 在 一 点, 该 点 extremalty 系 数 为 零, 且 extremalty 系 数 沿 主 方 向 导 数 非 零 首 先, 调 整 当 前 边 edge 的 顶 点 v1 v2 的 主 方 向 的 朝 向 使 两 者 一 致 因 为 在 局 部 三 角 形 上, 曲 率 应 该 是 连 续 变 化 的, 且 由 于 三 角 形 很 小, 可 以 假 定 三 角 形 内 主 方 向 不 会 发 生 大 的 改 变 若 tmax(v1) 和 tmax(v2) 呈 钝 角, 则 tmax(v2) -tmax(v2), 相 应 的 也 要 改 变 extremalty 系 数 的 符 号 :emax(v2) -emax(v2) 接 下 来, 如 果 同 时 满 足 以 下 三 个 条 件, 则 认 为 edge 上 有 脊 点 存 在 : 条 件 1. kmax(v) > kmn(v),v=v1, v2; 条 件 2. emax ( v1) emax ( v 2) 0 ; 条 件 3. { emax ( v1)[( v2 v1) tmax ( v1 )]} { emax ( v2)[( v1 v2) t ( max v 2)] } 0 条 件 1 表 示 曲 面 沿 最 大 主 曲 率 方 向 弯 曲 程 度 最 大 条 件 2 中 边 上 两 个 顶 点 的 emax 值 异 号, 也 就 是 说 边 上 存 在 最 大 主 曲 率 沿 其 主 方 向 的 方 向 导 数 为 零 的 点, 该 点 极 有 可 能 是 脊 点 此 时, 还 需 判 断 方 向 导 数 的 导 数 在 emax 的 拐 点 是 否 存 在, 且 不 为 零 对 于 脊 点, 34

49 北 京 航 空 航 天 大 学 硕 士 学 文 论 文 因 满 足 条 件 3 这 里 的 条 件 3 和 [48] 中 给 出 的 : e ( )[( ) ( )] 0 max v1 v2 v1 tmax v 1 且 max max 2 e ( v )[( v v ) t ( v )] 0 (3.24) 并 不 一 样 本 文 通 过 分 析 和 实 验 发 现 式 3.24 中 给 出 的 条 件 并 不 合 理 以 下 本 文 给 出 修 改 后 条 件 的 合 理 解 释 v2 k k p e v1 p v2 e v2 p v1 v1 v1 p v2 v2 p v1 图 24 脊 点 应 满 足 的 第 三 个 条 件 如 图 24 所 示, 是 一 条 脊 线 穿 过 当 前 考 察 的 边 v1v2 的 情 形, 则 v1v2 边 上 曲 率 的 变 化 情 况 应 该 如 图 24 中 间 所 示, 即 在 v1v2 之 间 p 处 达 到 曲 率 极 值 其 中 横 坐 标 表 示 曲 线 C 上 的 弧 长 参 数,C 由 v1v2 连 线 与 p 的 法 向 所 成 平 面 与 曲 面 的 交 线 假 设 在 v1 与 v2 处 的 主 方 向 如 图 所 示, 且 v1v2 与 极 值 点 p 的 相 对 位 置 如 图 24 中 间 给 出 的 情 况, 则 式 3.24 满 足 但 当 v1v2 互 换 位 置, 即 变 为 图 24 右 侧 给 出 的 情 况, 则 式 3.24 不 成 立 实 验 结 果 也 证 明 ( 见 3.4 节 ), 使 用 式 3.24 作 为 判 定 条 件 后 大 部 分 特 征 线 都 缺 失 了 而 本 文 给 出 的 条 件 考 虑 到 以 上 的 两 个 情 况, 实 验 证 明, 使 用 了 修 改 后 的 条 件 可 以 正 确 提 取 特 征 线 如 果 以 上 三 个 条 件 均 满 足, 则 使 用 线 性 插 值 找 到 脊 点 的 位 置 插 值 的 权 重 分 别 为 两 个 端 点 处 的 emax 值 设 脊 点 坐 标 为 p: emax ( v ) v e ( v ) v p e ( v ) e ( v ) max 2 1 max max 2 (3.25) 同 理, 使 用 同 样 的 权 重 方 式 线 性 插 值 确 定 p 的 主 曲 率 : emax ( v2) kmax ( v1) emax ( v1) kmax ( v2) p. e ( v ) e ( v ) max 1 max 2 (3.26) 该 主 曲 率 在 后 面 小 节 中 发 挥 特 征 线 后 处 理 的 作 用 35

50 第 三 章 基 于 拟 合 的 特 征 提 取 算 法 对 三 角 形 的 每 个 边 如 上 检 测 后, 将 脊 点 连 线 如 果 检 测 出 了 一 个 脊 点, 则 只 保 存, 不 作 处 理 ; 若 在 两 条 边 上 都 各 自 检 测 出 一 个 脊 点, 则 两 者 之 间 建 立 连 接 关 系 ; 若 三 条 边 都 检 测 出 脊 点, 则 找 到 三 个 点 的 中 心, 将 每 个 点 与 中 心 建 立 连 接 关 系 该 过 程 如 图 25 所 示 图 25 三 种 连 接 脊 线 的 方 式 (a) (b) (c) (d) 图 26 待 处 理 特 征 线 示 例 图 (a) 细 碎 部 分 ;(b) 不 光 滑 ;(c) 细 小 分 叉 ;(d) 环 特 征 线 后 处 理 以 上 步 骤 完 成 后 提 取 出 的 特 征 线 如 图 26 所 示, 可 以 看 到, 特 征 线 整 体 的 趋 势 很 好 的 依 附 了 变 动 大 的 凸 起 和 凹 陷 部 分 但 仍 然 存 在 以 下 几 个 问 题 : (1) 连 通 区 域 中 有 环 ; (2) 存 在 很 多 细 小 分 叉 ; (3) 某 些 区 域 的 特 征 线 不 够 平 滑 ; (4) 存 在 很 多 细 碎 的 特 征 区 域 ; 36

51 北 京 航 空 航 天 大 学 硕 士 学 文 论 文 本 节 提 出 通 过 五 个 后 处 理 步 骤 较 好 的 解 决 以 上 问 题 整 个 流 程 如 图 27 所 示 首 先 破 除 环 路 环 路 破 除 后, 立 即 会 形 成 一 些 细 小 的 分 叉 此 时, 连 同 之 前 本 身 存 在 的 分 叉, 通 过 分 叉 剔 除 算 法 统 一 剔 除 接 下 来 对 所 有 剩 余 特 征 线 进 行 基 于 PCA 的 平 滑 为 了 去 除 余 下 的 不 重 要 的 细 碎 的 特 征 线, 使 用 [48] 中 的 沿 特 征 线 计 算 曲 率 积 分 过 滤 方 法, 与 阈 值 进 行 比 较 剔 除 如 果 特 征 点 数 依 然 较 多, 则 对 较 长 的 特 征 线 进 行 下 采 样 图 27 后 处 理 特 征 线 流 程 为 达 到 去 除 环 路 的 目 的, 采 取 生 成 树 算 法 该 算 法 可 以 检 测 并 断 开 一 个 连 通 域 内 的 所 有 环 在 特 征 点 之 间 连 接 关 系 建 立 后, 遍 历 每 个 特 征 线 连 通 区 域, 执 行 生 成 树 算 法 减 去 环 路 算 法 伪 码 如 下 : 算 法 3.2: 去 除 环 路 CutLoops 输 入 : 特 征 线 连 通 区 域 component 输 出 : 去 环 的 component 1 E ; // 边 集 2 V p ; // 使 用 连 通 域 中 任 意 点 初 始 化 顶 点 集 3 Qp ; // 使 用 连 通 域 中 任 意 点 初 始 化 队 列 4 whle (Q s not empty) 5 pq.pop(); 6 Nebsfnd adjacent of p; 7 for each qnebs 8 f (qv && <p, q>e) // 检 测 到 环, 除 去 该 边 37

52 第 三 章 基 于 拟 合 的 特 征 提 取 算 法 9 component.e-{<p, q>}; 10 else 11 f (qv) // t s safe to add ths neghbor to V set 12 V {q}; 13 E {<p, q>}; 14 Q.push(q); 15 end f 16 end f 17 end for 18 end whle 去 环 结 果 如 图 28 所 示, 所 有 的 环 均 被 打 破, 形 成 的 分 叉 将 被 下 一 阶 段 处 理 图 28 去 除 环 路 前 ( 左 ) 与 去 除 环 路 后 ( 右 ) 对 比 图 图 29 去 除 分 叉 前 ( 左 ) 与 去 除 分 叉 后 ( 右 ) 对 比 图 去 除 分 叉 比 较 简 单, 只 需 去 掉 满 足 以 下 0 两 个 条 件 的 分 支 即 可 : 条 件 1. 该 特 征 线 一 端 点 度 为 1, 另 一 端 点 度 大 于 2; 条 件 2. 特 征 线 长 度 小 于 l(l 为 自 定 义 阈 值, 一 般 选 1-2); 第 一 条 件 保 证 只 去 除 在 特 征 线 内 部 的 分 叉, 而 不 会 去 掉 特 征 线 端 点 的 线 段 去 除 分 叉 前 38

53 北 京 航 空 航 天 大 学 硕 士 学 文 论 文 后 的 效 果 比 较 如 图 29 所 示, 可 以 看 到 去 除 分 叉 后 线 条 流 畅 平 整 了 许 多 p L p 图 30 基 于 PCA 的 平 滑 示 意 图 接 下 来 的 阶 段 使 用 PCA 平 滑 所 有 剩 余 的 特 征 线 该 过 程 如 图 30 所 示 在 特 征 线 的 每 点 p 处 找 到 一 邻 域 ( 红 色 所 示 ), 对 其 实 施 PCA, 得 到 最 大 特 征 值 对 应 的 特 征 向 量, 过 邻 域 中 心 并 沿 向 量 构 造 一 直 线 L( 蓝 色 ), 然 后 将 p 投 影 至 该 直 线 上, 获 得 其 平 滑 后 的 位 置 p 平 滑 前 后 的 对 比 图 如 下 : 图 31 平 滑 前 ( 左 ) 与 平 滑 后 ( 右 ) 对 比 图 上 图 给 出 了 Bunny 模 型 的 前 部 脖 颈 以 下 的 特 征 线 平 滑 对 比 图, 可 以 看 到, 平 滑 后 的 特 征 线 确 实 比 未 平 滑 的 特 征 线 要 流 畅 许 多, 尤 其 是 脖 颈 部 分 的 连 线 接 下 来 计 算 通 过 以 上 后 处 理 的 特 征 连 通 域 的 主 曲 率 积 分, 将 其 与 预 设 阈 值 T 相 比 较, 若 小 于 则 剔 除 这 里, 曲 率 积 分 根 据 以 下 公 式 计 算 : k ( p ) k ( p ) max max 1 k ds, (3.27) 2 39

54 第 三 章 基 于 拟 合 的 特 征 提 取 算 法 其 中 p 和 p+1 是 线 段 两 个 端 点 T 与 模 型 大 小 成 正 比, 与 主 曲 率 成 反 比 可 以 想 到, 由 于 模 型 大 小 与 曲 率 是 一 对 相 互 制 约 的 量, 因 此 T 与 模 型 大 小 无 关, 一 般 设 为 过 滤 后 的 结 果 如 下 图 所 示 图 32 过 滤 前 后 对 比 图 ( 左 ) 未 过 滤 ( 右 )T=1 时 的 基 于 曲 率 积 分 过 滤 结 果 最 后 一 个 阶 段 下 采 样 过 程, 主 要 是 为 了 降 低 特 征 点 的 密 度, 为 后 续 应 用 实 例 服 务 算 法 从 特 征 线 的 一 端 开 始, 每 隔 一 定 数 量 的 点 就 进 行 一 次 特 征 边 的 塌 缩, 直 至 遇 到 或 超 过 特 征 线 的 另 一 个 端 点 伪 码 如 下 所 示 : 算 法 3.3: 下 采 样 DownSample 输 入 : 未 下 采 样 feature_lne, 采 样 步 长 step 输 出 : 下 采 样 后 的 feature_lne 1 new_lne empty; 2 cur_node feature_lne.start; 3 whle (cur_node <= feature_lne.last) 4 new_lne.add(cur_node); 5 cur_node cur_node+step; 6 end whle 7 f (new_lne.last!= feature_lne.last) 8 new_lne.add(feature_lne.last); 40

55 北 京 航 空 航 天 大 学 硕 士 学 文 论 文 9 end f 10 feature_lne new_lne; 下 采 样 后 的 结 果 如 下 图 所 示 : 图 33 下 采 样 前 ( 左 ) 与 下 采 样 后 ( 右 ) 对 比 图 步 长 :5 可 以 看 到, 下 采 样 后 的 特 征 线 仍 然 较 好 的 保 持 了 原 先 的 形 状, 但 特 征 点 的 数 量 已 经 大 大 减 少 了, 具 体 数 据 见 3.4 节 实 验 分 析 部 分 3.4 实 验 结 果 与 分 析 这 一 节 我 们 给 出 以 上 微 分 量 估 算 及 特 征 提 取 的 结 果 在 以 下 可 视 化 结 果 中, 颜 色 由 绿 到 蓝 到 红 表 示 可 视 化 的 值 由 小 到 大 递 增 特 征 线 绘 制 中, 红 色 线 表 示 脊 线, 蓝 色 线 表 示 谷 线 从 图 34 中 看 出, 梯 度 的 方 向 与 期 待 的 法 向 方 向 完 全 一 致, 并 且 整 个 法 向 量 场 均 匀 连 续, 说 明 底 层 的 隐 式 曲 面 也 是 连 续 光 滑 的, 较 好 的 支 持 了 一 阶 微 分 量 的 计 算 图 35 给 出 了 原 模 型 在 不 同 尺 度 下 拟 合 得 到 的 隐 式 曲 面 上 的 投 影 从 左 至 右, 尺 度 为 可 以 很 清 楚 的 看 到, 较 小 的 尺 度 可 以 更 多 的 保 留 曲 面 的 局 部 细 节 ; 较 大 尺 度 的 拟 合 则 更 好 的 平 滑 了 模 型 的 表 面, 较 小 范 围 内 的 曲 面 变 动 被 有 效 抑 制 41

56 第 三 章 基 于 拟 合 的 特 征 提 取 算 法 图 34 计 算 隐 式 曲 面 归 一 化 梯 度 得 到 的 法 向 量 场 图 35 计 算 每 点 在 隐 式 曲 面 上 的 投 影 从 图 看 到, 在 这 些 投 影 点 位 置 上 计 算 得 到 的 主 曲 率 也 呈 现 相 应 的 趋 势 : 在 较 小 尺 度 下, 局 部 细 节 如 身 上 的 褶 皱 处 主 曲 率 值 较 大, 但 这 些 部 分 在 较 大 尺 度 下 的 主 曲 率 就 呈 现 不 出 显 著 性 了 ; 反 之, 一 些 变 动 较 大 的 部 位, 如 Bunny 的 耳 朵,MaxPlanck 的 鼻 梁, Armadllo 的 耳 朵 则 随 着 尺 度 的 增 大 而 变 得 更 加 显 著, 曲 率 值 也 更 趋 于 稳 定 42

57 北 京 航 空 航 天 大 学 硕 士 学 文 论 文 图 36 多 个 尺 度 下 的 最 大 主 曲 率 kmax Max Planck 以 及 Armadllo:( 左 ) 尺 度 1,( 右 ) 尺 度 3; Bunny:( 上 ) 尺 度 1,( 下 ) 尺 度 3 图 37 多 个 尺 度 下 的 最 小 主 曲 率 kmn ( 上 ) 尺 度 1,( 下 ) 尺 度 3 在 图 38 中, 在 bunny 表 面 同 时 可 视 化 出 了 t max 与 脊 线, 在 gea 模 型 上 同 时 可 视 化 出 了 t mn 与 谷 线 可 以 看 到, 脊 线 与 谷 线 与 附 近 的 相 应 的 主 曲 率 线 基 本 正 交, 符 合 脊 / 谷 线 的 数 学 定 义, 充 分 说 明 了 基 于 拟 合 的 特 征 提 取 方 法 较 稳 定 的 计 算 了 高 阶 微 分 量, 正 确 的 判 定 了 特 征 点 的 位 置 43

58 第 三 章 基 于 拟 合 的 特 征 提 取 算 法 图 38 主 方 向 与 脊 线 可 视 化 结 果 左 : 主 方 向 tmax 与 脊 线 右 : 主 方 向 tmn 与 谷 线 从 图 39 中 可 以 看 出, 尺 度 的 变 化 最 终 影 响 到 特 征 线 的 提 取, 即 小 尺 度 下 可 以 提 取 更 多 更 细 节 的 特 征, 但 整 体 特 征 线 走 势 较 不 光 滑 ; 大 尺 度 下 的 特 征 不 如 小 尺 度 的 丰 富, 但 更 加 鲁 棒 从 视 觉 上 讲, 小 尺 度 的 特 征 可 用 来 传 达 更 多 的 细 节 信 息, 大 尺 度 特 征 则 有 助 于 传 达 形 体 的 整 体 信 息 尤 为 重 要 的 是, 因 为 基 于 拟 合 的 特 征 提 取 方 法 所 提 取 的 特 征 是 经 过 高 阶 微 分 量 计 算 得 出 的, 具 有 严 格 的 数 学 定 义, 即 使 是 曲 面 上 曲 率 不 大 的 地 方, 由 于 也 满 足 曲 率 极 值 点 的 条 件, 也 会 提 取 特 征 线, 从 而 提 供 了 对 曲 面 更 加 全 面 的 描 述 而 其 他 大 部 分 方 法, 例 如 积 分 不 变 量 等, 只 估 算 曲 率, 然 后 设 定 阈 值 留 下 曲 率 较 大 的 区 域 作 为 特 征, 因 此 对 曲 面 的 描 述 十 分 不 全 面 例 如 MaxPlanck 人 头 模 型 的 头 顶 区 域, 曲 率 并 不 大, 若 此 时 使 用 其 他 基 于 曲 率 阈 值 的 方 法, 则 不 会 在 此 处 提 取 任 何 特 征 线 在 下 一 章 节 可 以 看 到, 这 些 不 易 察 觉 的 特 征 线 对 模 型 表 示 恢 复 有 至 关 重 要 的 作 用 因 此, 基 于 拟 合 的 特 征 提 取 能 较 好 的 适 应 于 本 文 下 一 章 要 介 绍 的 重 要 应 用 图 39 不 同 尺 度 下 提 取 的 特 征 线 44

59 北 京 航 空 航 天 大 学 硕 士 学 文 论 文 表 1 后 处 理 对 特 征 点 数 影 响 模 型 后 处 理 前 后 处 理 后 特 征 点 数 特 征 连 通 域 数 特 征 点 数 特 征 连 通 域 数 Bunny Max Planck Igea Santa Dragon Armadllo 表 1 给 出 了 特 征 后 处 理 步 骤 对 特 征 点 数 的 影 响 直 接 提 取 的 特 征 点 非 常 多, 而 过 多 的 特 征 点 虽 然 加 强 了 对 模 型 表 面 信 息 的 捕 捉 能 力, 却 降 低 了 模 型 表 示 的 效 率, 同 时 为 特 征 线 的 可 视 化 带 来 了 很 多 影 响, 而 经 过 后 处 理 后 的 特 征 点 数 目 显 著 下 降 根 据 我 们 的 实 验 中 的 经 验 来 看, 这 些 减 少 主 要 是 由 于 去 掉 了 细 小 的 分 叉 和 不 重 要 的 小 段 特 征 之 前 的 介 绍 也 可 以 看 出, 处 理 后 的 特 征 线 更 加 简 洁 清 晰, 可 以 更 好 的 用 于 提 示 模 型 的 曲 面 走 向 并 帮 助 建 立 积 极 的 视 觉 刺 激 3.5 本 章 小 结 本 章 介 绍 了 针 对 点 模 型 提 取 多 尺 度 特 征 线 的 算 法 过 程 首 先, 采 用 类 全 局 的 MLS 拟 合 基 函 数 的 方 法 来 构 建 点 模 型 的 连 续 表 达 式, 在 此 基 础 上, 再 解 析 的 求 解 高 阶 微 分 量, 并 通 过 定 位 曲 率 极 值 提 取 特 征 点 随 后, 对 特 征 点 连 线 并 后 处 理, 得 到 光 滑 平 整 的 特 征 线 其 中, 多 尺 度 由 拟 合 时 的 邻 域 大 小 体 现 实 验 结 果 说 明 本 文 算 法 可 有 效 提 取 表 面 不 同 关 注 尺 度 下 的 特 征 线 45

60 第 四 章 基 于 特 征 的 模 型 表 示 与 恢 复 第 四 章 基 于 特 征 的 模 型 表 示 与 恢 复 以 上 章 节 我 们 讲 解 了 如 何 通 过 建 立 曲 面 的 隐 式 函 数 来 解 析 的 计 算 高 阶 微 分 量, 以 及 如 何 对 高 阶 微 分 量 的 分 析 进 而 得 到 我 们 关 注 的 特 征, 亦 即 脊 / 谷 线 本 章 我 们 讨 论 特 征 线 以 及 几 何 模 型 的 隐 式 曲 面 表 示 的 重 要 应 用 : 模 型 恢 复 结 合 特 征 点 处 的 局 部 隐 式 函 数, 本 文 提 出 基 于 特 征 的 曲 面 表 示 方 法, 并 将 其 应 用 在 模 型 恢 复 中 首 先, 本 章 定 义 了 基 于 特 征 的 模 型 表 示 然 后, 在 该 定 义 的 指 导 下, 通 过 本 章 提 出 的 一 种 以 特 征 为 中 心 的 迭 代 分 割 算 法 以 及 二 次 拟 合 步 骤 构 建 特 征 点 与 局 部 拟 合 函 数 组 成 的 简 化 表 示 最 后, 给 出 了 该 表 示 如 何 与 等 值 面 提 取 算 法 结 合 以 恢 复 得 到 几 何 模 型 的 离 散 表 示 并 绘 制 4.1 基 于 特 征 的 模 型 表 示 在 第 三 章 得 到 的 特 征 线 还 不 能 立 即 应 用 到 模 型 恢 复 中 必 须 建 立 一 种 相 应 的 模 型 表 示, 作 为 恢 复 的 基 础 和 依 据 本 文 定 义 了 这 样 的 一 种 模 型 表 示 定 义 4.1: 令 F 为 模 型 P 采 用 第 三 章 算 法 提 取 得 到 的 特 征 点 集 合 对 F 中 每 点 q 确 定 其 对 P 的 一 拟 合 函 数 f ( x), xr, R 满 足 于 特 征 的 表 示 R P 称 F 与 { f ( x) [1,2,..., F ]} 为 模 型 P 的 基 本 文 认 为, 如 果 能 构 建 满 足 以 上 要 求 的 表 示, 则 该 表 示 就 可 以 一 定 程 度 表 达 原 始 模 型, 并 通 过 常 用 的 模 型 重 构 算 法 近 似 恢 复 原 模 型 显 然, 基 于 特 征 的 模 型 表 示 是 一 个 二 元 组, 即 基 础 结 构 F 和 拟 合 函 数 集 合 我 们 已 经 得 到 了 特 征 点 集 合, 因 此 只 需 确 定 拟 合 函 数 集 合, 使 其 定 义 域 能 够 包 含 整 个 被 表 示 的 模 型 这 里, 本 文 采 用 一 种 基 于 特 征 线 的 分 割 方 法, 并 结 合 上 一 章 介 绍 的 拟 合 策 略 来 确 定 每 个 特 征 点 的 拟 合 函 数 区 域 本 文 使 用 经 典 的 区 域 增 长 (regon-growng) 又 称 泛 洪 (floodng) 的 方 法 作 为 基 本 的 迭 代 单 元 来 构 建 分 割 方 法 为 了 使 特 征 作 为 拟 合 中 心, 确 定 特 征 在 模 型 P 上 的 影 响 范 围, 区 域 增 长 算 法 从 特 征 点 处 开 始, 以 特 征 线 作 为 最 大 的 基 本 单 元, 将 模 型 P 划 分 为 多 个 以 特 征 连 通 域 为 中 心 的 近 似 Vorono 区 域, 并 在 此 过 程 中 跟 踪 每 个 特 征 点 的 区 域, 就 46

61 北 京 航 空 航 天 大 学 硕 士 学 文 论 文 可 以 确 定 出 拟 合 范 围 整 个 算 法 的 伪 码 如 下 : 算 法 4.1: 基 于 特 征 线 的 分 割 Segment 输 入 : 特 征 点 集 合 F, 点 模 型 P 输 出 : 聚 类 结 果 clusters 变 量 :clusters[ 特 征 连 通 域 个 数 ], Q[ 特 征 连 通 域 个 数 ]. // 初 始 化 聚 类 clusters 及 队 列 Q 1 for each = [0 clusters ) 2 clusters[]f.feat_component[]; 3 Q[] F.feat_component[] 4 end for // 分 割 模 型 5 whle (there are unclustered ponts) 6 for each = [0 clusters ) 7 f (clusters[] s not fnshed) 8 GrowFeatComponent(P, clusters[], Q[]); 9 end f 10 end for 11 end whle 算 法 4.2: 以 特 征 连 通 域 为 中 心 的 区 域 增 长 GrowFeatComponent 输 入 :P, 待 增 长 cluster, 队 列 Q 输 出 : 更 新 后 的 cluster 及 Q 1 per_cntq.sze(); 2 whle (per_cnt-- > 0) 3 p Q.pop(); 47

62 第 四 章 基 于 特 征 的 模 型 表 示 与 恢 复 4 nebs search neghbors of p wthn a small range; 5 for each qnebs 6 f (qcluster) 7 cluster.add(q); 8 p.rmax(p.r, p-q ); // 更 新 p 的 影 响 半 径 9 Q.push(q); 10 end f 11 end for 12 end whle 13 f (Q s empty) 14 cluster.fnshedtrue; 15 end f 以 上 算 法 通 过 每 次 将 特 征 连 通 域 的 覆 盖 范 围 边 界 向 外 扩 展 很 小 的 范 围, 来 达 到 将 整 个 曲 面 自 动 划 分 给 每 个 特 征 连 通 域 而 特 征 连 通 域 的 边 界 扩 张 又 是 通 过 对 其 中 每 个 特 征 点 的 扩 张 达 到 的 图 40 一 组 基 于 特 征 的 点 模 型 分 割 结 果 由 以 上 算 法 得 到 的 分 割 结 果 如 图 40 所 示 可 以 看 到, 原 模 型 的 点 都 被 唯 一 划 分 至 某 48

63 北 京 航 空 航 天 大 学 硕 士 学 文 论 文 个 特 征 连 通 域 的 区 域 内 同 时, 每 个 特 征 点 的 影 响 范 围 也 都 在 这 个 过 程 中 确 定 了 下 来 在 图 中 用 球 可 视 化 出 了 每 个 点 的 影 响 范 围 图 中 相 同 颜 色 表 示 点 / 球 属 于 同 一 个 聚 类 中 心 ( 注 : 点 表 示 和 球 表 示 的 颜 色 并 不 一 一 对 应 ) 使 用 区 域 增 长 的 分 割, 保 证 了 最 终 获 得 的 拟 合 范 围 的 并 集 包 含 原 始 模 型, 从 而 满 足 基 于 特 征 的 模 型 表 示 的 定 义 有 了 拟 合 范 围, 就 可 以 利 用 第 三 章 介 绍 过 的 拟 合 方 法 这 里, 将 每 个 特 征 点 作 为 一 个 拟 合 中 心, 刚 刚 确 定 的 范 围 作 为 紧 支 撑 的 权 函 数 定 义 域 半 径, 区 域 增 长 确 定 的 归 属 于 该 特 征 点 的 模 型 点 参 与 重 拟 合 过 程 最 终 得 到 的 基 于 特 征 的 模 型 表 示 是 近 似 原 模 型 的 隐 式 函 数 的 集 合 4.2 基 于 特 征 的 模 型 恢 复 以 上 获 得 的 模 型 表 示, 只 包 括 模 型 特 征 点 位 置 法 向 以 及 特 征 处 的 局 部 拟 合 曲 面 参 数 本 节 利 用 现 有 的 模 型 重 构 算 法, 说 明 基 于 特 征 的 紧 致 模 型 表 示 如 何 有 效 提 供 和 构 建 认 知 模 型 整 体 所 必 须 的 信 息 隐 式 曲 面 虽 然 具 有 连 续 的 优 势, 但 终 究 只 是 作 为 一 种 高 效 存 储 方 式 存 在 真 正 在 使 用 时, 很 多 应 用, 包 括 绘 制 等, 大 多 要 求 将 隐 式 曲 面 转 为 离 散 模 型 例 如 网 格 来 表 达 目 前, 常 见 的 隐 式 曲 面 模 型 转 换 方 式 有 Marchng Cube,Ray Castng, 以 及 Splattng Marchng Cube 预 先 将 隐 式 函 数 转 换 为 三 角 网 格 表 示, 以 后 每 帧 高 效 绘 制 网 格 模 型 Splattng 绘 制 物 体 时 需 要 物 体 以 离 散 形 式 表 示, 因 此 对 于 隐 式 曲 面 来 说, 要 求 先 要 对 其 离 散 采 样 得 到 点 表 示, 绘 制 时 在 每 点 增 加 物 体 空 间 重 构 函 数, 投 影 到 屏 幕 空 间, 再 对 整 个 屏 幕 像 素 实 施 卷 积 操 作 ; 或 着 直 接 叠 加 图 像 空 间 重 构 核 [10], 免 除 物 体 空 间 核 函 数 向 屏 幕 空 间 投 影 操 作 但 Splattng 需 要 足 够 致 密 的 点 云 表 示 才 能 得 到 较 好 的 绘 制 效 果 Ray Castng 没 有 预 计 算 过 程, 每 帧 都 对 函 数 采 样, 是 一 种 常 用 来 可 视 化 体 数 据 的 绘 制 方 法 本 文 选 取 了 Marchng Cube 以 及 Ray Castng 算 法 对 基 于 特 征 的 模 型 表 示 进 行 了 恢 复 和 显 示 Marchng Cube [49] Marchng Cube 方 法 常 见 于 三 维 隐 式 曲 面 绘 制 和 网 格 模 型 提 取 等 应 用 场 景 中 该 方 法 的 主 要 思 想 是 将 隐 式 曲 面 所 定 义 的 空 间 剖 分 成 离 散 的 规 则 大 小 的 体 元 (cell), 从 而 将 隐 式 函 数 在 空 间 中 的 连 续 定 义 离 散 化 在 每 个 体 元 的 八 个 顶 点 上 通 过 判 断 八 个 顶 点 49

64 第 四 章 基 于 特 征 的 模 型 表 示 与 恢 复 的 隐 式 曲 面 函 数 值, 可 以 判 断 出 隐 式 曲 面 与 体 元 的 位 置 关 系 针 对 与 隐 式 面 相 交 的 体 元, 提 取 体 元 内 的 部 分 最 后 所 有 体 元 中 提 取 的 表 面 拼 接 起 来 便 构 成 了 物 体 完 整 的 表 面 对 于 每 个 体 元, 该 算 法 做 了 两 点 假 设 :(1) 有 向 距 离 场 函 数 沿 体 元 的 边 呈 线 性 变 化 ; (2) 在 体 元 内 物 体 的 表 面 是 分 段 线 性 的, 即 由 三 角 面 片 组 成 由 假 设 (1) 可 知 体 元 的 边 与 表 面 相 交 的 充 要 条 件 是 边 的 两 个 顶 点 距 离 场 值 异 号, 由 此 可 以 找 到 所 有 含 有 表 面 的 体 元 并 计 算 出 物 体 表 面 与 体 元 边 的 交 点 根 据 假 设 (2) 只 需 将 这 些 交 点 连 接 成 若 干 个 三 角 形 便 能 完 成 一 个 体 元 中 的 表 面 提 取 工 作 然 而 这 并 不 是 一 件 简 单 的 工 作 Marchng Cube 算 法 的 主 要 难 点 就 是 解 决 交 点 连 接 的 问 题, 即 连 接 的 二 义 性 问 题 图 41 说 明 了 二 维 下 的 二 义 性 情 况, 即 对 于 体 元 顶 点 的 符 号, 会 存 在 (a) (b) 两 种 表 面 连 接 的 可 能 性 根 据 假 设 (1) 可 以 证 明, 体 元 内 的 表 面 是 双 曲 面 ( 二 维 情 况 为 双 曲 线 ), 根 据 这 一 点 只 需 判 断 双 曲 面 中 心 点 的 场 值 符 号 便 能 解 决 二 义 性 的 问 题 若 渐 近 线 中 心 处 场 值 为 负, 则 应 按 照 左 图 连 接, 否 则 应 按 右 图 连 接 a b 图 41 Marchng Cubes 中 的 二 义 性 然 而 对 于 三 维 的 情 况, 问 题 变 得 很 复 杂 有 学 者 提 出 使 用 四 面 体 代 替 六 面 体 的 体 元 虽 然 一 定 程 度 解 决 了 二 义 性, 但 提 取 出 的 三 角 形 个 数 过 多, 且 多 不 规 则 因 此, 人 们 还 是 广 泛 采 用 六 面 体 体 元 一 种 可 行 的 方 法 是 根 据 已 有 的 经 验 将 体 元 分 类, 每 一 类 体 元 对 应 一 种 确 定 的 连 接 方 式, 可 以 预 先 将 每 一 类 的 连 接 方 式 计 算 好 做 成 模 板, 则 任 给 一 个 体 元 只 需 首 先 进 行 类 型 匹 配 再 根 据 匹 配 的 模 板 进 行 连 接 便 能 构 造 出 连 接 正 确 的 三 角 面 片 体 元 8 个 顶 点 中 的 每 个 顶 点 场 值 符 号 都 可 能 有 正 负 两 种 可 能, 则 体 元 根 据 顶 点 场 值 的 符 号 可 以 分 为 2 8 =256 种 状 态 可 以 将 每 种 状 态 作 为 模 板 的 一 个 表 项 考 虑 到 旋 转 对 称 性, 即 很 多 体 元 经 过 旋 转 后 ( 有 24 种 旋 转 方 式 ) 能 得 到 相 同 的 状 态, 因 此 有 研 究 者 在 考 虑 旋 转 对 称 性 的 情 况 下 将 体 元 分 为 本 质 上 不 同 的 类 如 文 献 [49] 将 体 元 分 为 图 42 中 的 15 类, 图 中 每 个 体 元 标 黑 的 点 与 未 标 黑 的 点 表 明 不 同 的 符 号 类 型 对 任 意 体 元, 首 50