&6+/3' 6/00/+0 计 算 机 工 程 与 科 学 &74'8!869688!69 : &86&8 0/ 年 第 + 卷 第 期 ;+6;0/ 文 章 编 号 /00/+00/00//0 像 素 的 移 动 体 素 面 绘 制 算 法!#$% 郑 丽 萍 李 光 耀 李 寰! 聊 城 大 学 计 算 机 学 院 山 东 聊 城 "#"$! 同 济 大 学 %&' 研 究 中 心 上 海 ##! (% )*+,+++-.+,/*+#"$!%&'0+/+,%+*+,1-.+,/*##% 摘 要 移 动 立 方 体 算 法 是 最 具 影 响 力 的 等 值 面 构 造 算 法 本 文 以 移 动 立 方 体 算 法 为 基 础 提 出 了 像 素 点 移 动 体 素 面 绘 制 算 法 根 据 物 体 表 面 的 显 示 特 性 和 体 素 特 点 利 用 像 素 点 组 成 的 边 界 体 素 绘 制 物 体 的 等 值 面 实 现 物 体 表 面 的 三 维 重 建 在 实 验 中 对 一 组 &' 图 像 中 的 骨 骼 组 织 进 行 三 维 表 面 重 建 和 显 示 并 与 用 # 绘 制 函 数 重 建 的 三 维 结 果 进 行 比 较 实 验 分 析 表 明 该 算 法 能 对 物 体 进 行 三 维 重 建 避 免 了 二 义 性 问 题 但 重 建 表 面 不 光 滑 重 建 花 费 的 时 间 较 长 &/*,*'$%$ #$%#$%## ###$% #$ %#$% ##$ %$ #$%#$"(#)# $##*#$)# *#$(###$+,#$%####$ #*#$#$#$%#$##-(( %#* %##*$*#$##$#$% ##)#+,"%#(.##$##"+,#%#$#$##"#% 关 键 词 移 动 立 方 体 算 法 面 绘 制 三 维 重 建 等 值 线 二 义 性 +,/%$ #$%+,##%#( /0+11)/00/+00/00 中 图 分 类 号 '+1// 文 献 标 识 码 引 言 面 绘 制 算 法 主 要 是 在 体 数 据 中 构 造 出 等 值 面 等 值 面 的 生 成 方 法 很 多 根 据 生 成 原 理 主 要 可 分 为 三 大 类 / 基 于 等 值 线 的 生 成 方 法 基 于 体 / 素 的 生 成 方 法 + 基 于 能 量 函 数 的 生 成 方 法 面 绘 制 方 法 中 有 多 种 不 同 的 方 法 随 着 新 一 代 &' 和! 设 备 的 出 现 切 片 间 距 及 切 片 内 像 素 间 距 都 达 到 很 小 基 于 体 素 的 面 绘 制 方 法 的 应 用 越 来 越 多 基 于 体 素 的 面 绘 制 方 法 主 要 有 立 方 块 & 方 法 移 动 立 方 体 法 $& 简 称 + & 法 和 分 解 立 方 体 法,"& 等 2 提 出 的 移 动 立 方 体 算 法 是 最 经 典 最 具 影 响 力 的 等 值 面 构 造 算 法 该 方 法 一 直 沿 用 至 今 但 是 最 初 的 & 算 法 不 能 保 证 三 角 片 所 构 成 等 值 面 的 拓 扑 一 致 性 会 造 成 等 值 面 上 出 现 孔 隙 即 存 在 二 义 性 问 题 许 多 研 究 人 员 提 出 了 解 决 二 义 性 的 方 法 如 利 用 双 曲 渐 近 线 的 交 点 来 判 定 二 义 性 面 四 面 体 剖 分 算 法 等 国 内 的 研 究 人 员 也 做 了 收 稿 日 期 0//0+/ 修 订 日 期 0//03 基 金 项 目 国 家 自 然 科 学 基 金 资 助 项 目 0/0 通 讯 地 址 01 山 东 省 聊 城 市 文 化 路 + 号 聊 城 大 学 计 算 机 学 院 计 算 机 系 &,+//$&%#2$4#(+ 5$!"2$$01!&$
/ 计 算 机 工 程 与 科 学 0/+ 相 关 研 究 清 华 大 学 的 唐 泽 圣 周 勇 等 在 & 算 法 的 实 现 上 也 作 了 一 些 改 进 本 文 在 研 究 & 算 法 基 本 原 理 的 基 础 上 根 据 物 体 表 面 的 显 示 特 性 和 体 素 特 点 提 出 了 像 素 点 移 动 体 素 面 绘 制 算 法 利 用 体 素 绘 制 物 体 的 等 直 面 来 实 现 物 体 的 三 维 重 建 等 值 面 上 不 会 出 现 孔 隙 避 免 了 & 算 法 自 身 的 二 义 性 移 动 立 方 体 算 法! 移 动 立 法 体 算 法 的 基 本 原 理 $& 算 法 是 由 2 5 8 和 & 8 在 /13 年 提 出 的 一 种 表 面 重 建 算 法 并 取 得 了 较 好 的 重 建 效 果 & 算 法 是 一 种 在 三 维 数 据 场 内 进 行 等 值 面 构 造 与 显 示 的 方 法 如 图 / 所 示 在 由 二 维 断 层 图 像 序 列 构 成 的 三 维 数 据 场 中 在 上 下 相 邻 的 两 层 图 像 上 各 取 个 像 素 组 成 一 个 长 方 体 体 素 构 成 体 素 的 3 个 像 素 点 称 为 角 点 设 定 等 值 面 常 数 为 分 别 把 每 个 角 点 的 灰 度 值 与 等 值 面 常 数 进 行 比 较 以 判 断 各 角 点 的 类 型 如 果 则 该 角 点 为 外 部 角 点 若 则 该 角 点 为 内 部 角 点 & 算 法 规 定 如 果 体 素 某 条 边 上 的 两 个 角 点 分 别 为 内 部 角 点 和 外 部 角 点 那 么 这 条 边 上 必 然 存 在 一 个 点 的 值 等 于 即 为 等 值 点 三 维 数 据 场 中 的 所 有 等 值 点 的 集 合 就 构 成 了 等 值 面 根 据 体 素 角 点 状 态 的 互 补 对 称 性 和 旋 转 对 称 性 体 素 的 状 态 最 终 可 确 定 / 种 图 / 是 其 中 一 种 构 型 系! 移 动 立 方 体 算 法 的 缺 点 用 & 算 法 可 以 获 得 较 高 分 辨 率 的 三 维 模 型 并 且 模 型 生 成 速 度 快 易 交 互 但 是 & 算 法 也 存 在 一 些 缺 陷 需 要 逐 个 处 理 数 据 场 中 的 所 有 立 方 体 体 素 因 此 计 算 效 率 低 & 算 法 构 造 的 三 角 面 片 是 待 求 等 值 面 的 近 似 表 示 等 值 面 与 体 素 边 界 面 的 交 线 是 双 曲 线 因 此 连 接 方 式 具 有 二 义 性 另 外 原 始 & 算 法 还 存 在 三 角 面 片 数 据 量 巨 大 逼 近 精 度 不 足 和 运 算 效 率 有 待 提 高 等 不 足 针 对 & 算 法 的 局 限 研 究 人 员 也 做 了 大 量 的 改 进 工 作 如 利 用 渐 进 性 法 解 决 面 二 义 性 问 题 利 用 插 值 函 数 空 间 的 连 续 性 消 除 & 的 二 义 性 采 取 区 域 增 长 方 式 搜 索 关 联 体 素 减 少 对 无 关 体 素 的 访 问 以 减 少 生 成 面 片 的 数 量 等 & 算 法 自 身 的 缺 陷 使 它 的 应 用 受 到 限 制 像 素 点 移 动 体 素 面 绘 制 算 法 本 文 在 研 究 & 算 法 的 基 础 上 结 合 阈 值 分 割 的 思 想 物 体 显 示 的 特 性 和 & 算 法 的 基 本 原 理 提 出 了 像 素 点 移 动 体 素 面 绘 制 算 法 $!#$% 简 称 算 法 并 用 # 绘 制 出 重 建 结 果 在 使 用 算 法 的 过 程 中 首 先 采 用 阈 值 分 割 的 方 法 获 得 需 要 重 建 的 目 标 物 体 然 后 对 分 割 所 得 目 标 的 灰 度 值 进 行 设 定 获 得 三 维 体 数 据 确 定 以 3 个 紧 邻 的 像 素 点 为 顶 点 的 体 素 并 确 定 三 维 体 数 据 中 所 有 的 边 界 体 素 根 据 由 点 连 接 成 线 和 由 线 连 接 成 面 的 原 理 利 用 边 界 体 素 绘 制 等 值 面 实 现 物 体 的 三 维 重 建! 像 素 点 体 素 和 边 界 体 素 的 确 定 图 / 体 素 及 其 构 型 & 算 法 使 用 三 角 面 片 作 为 中 间 几 何 图 元 但 它 提 取 额 的 等 值 面 是 散 乱 的 三 角 形 几 何 不 能 区 分 子 等 值 面 也 不 能 反 映 三 角 形 相 互 之 间 的 连 接 关 通 过 阈 值 分 割 后 获 得 需 要 重 建 的 目 标 物 体 此 时 分 割 图 像 中 像 素 的 灰 度 值 在 一 定 的 范 围 内 目 标 物 体 可 以 由 等 值 面 表 示 而 等 值 面 上 的 点 具 有 相 同 的 性 质 因 此 构 成 物 体 的 体 素 应 具 有 相 似 的 密 度 值 根 据 物 体 形 状 特 点 对 像 素 的 灰 度 值 进 行 改 变 把 所 有 像 素 的 灰 度 值 都 设 为 相 同 使 灰 度 值 为 这 样 设 置 不 会 改 变 物 体 的 形 状 因 此 不 会 影 响 三 维 重 建 后 的 物 体 形 状 经 过 灰 度 值 改 变 物 体 所 对 应 的 体 数 据 的 灰 度 值 只 有 0 和 本 文 提 出 的 算 法 以 像 素 点 体 素 为 基 础 假 若 先 通 过 阈 值 分 割 获 得 多 张 分 割 图 像 这 些 图 像 按 顺 序 进 行 分 层 排 列 这 些 图 像 的 尺 寸 相 同 所
郑 丽 萍 等 像 素 的 移 动 体 素 面 绘 制 算 法 含 像 素 点 也 相 同 以 第 层 和 第 / 层 的 两 张 图 像 为 例 按 照 一 一 对 应 的 原 则 以 第 层 图 像 中 的 个 像 素 和 第 / 层 图 像 中 的 个 像 素 点 为 顶 点 构 建 一 个 基 于 像 素 点 的 体 素 由 于 以 单 个 像 素 点 为 顶 点 称 为 像 素 点 体 素 根 据 顶 点 灰 度 值 的 不 同 像 素 点 体 素 可 分 为 两 种 一 种 是 等 值 体 素 一 种 是 边 界 体 素 如 果 八 个 像 素 点 的 灰 度 值 都 相 同 则 该 像 素 点 体 素 为 等 值 体 素 否 则 该 像 素 点 体 素 为 边 界 体 素 由 于 像 素 点 已 经 是 图 像 的 最 小 单 位 所 以 不 需 要 进 行 插 值 计 算 来 生 成 等 值 面 灰 度 值 为 的 等 值 体 素 一 定 位 于 物 体 的 内 部 而 边 界 体 素 位 于 物 体 的 边 界 因 为 面 绘 制 只 是 对 物 体 的 表 面 进 行 重 建 不 需 要 了 解 物 体 的 内 部 信 息 所 以 在 重 建 时 只 需 要 考 虑 边 界 体 素 即 可 不 需 要 考 虑 大 量 的 等 值 体 素 因 此 大 大 减 少 了 数 据 量 在 重 建 过 程 中 按 照 从 左 到 右 从 上 到 下 的 顺 序 对 像 素 体 素 进 行 访 问 由 于 像 素 点 体 素 是 一 个 立 方 体 有 一 定 的 对 称 性 根 据 体 素 自 身 特 性 和 访 问 体 素 的 顺 序 边 界 体 素 上 等 值 线 的 连 接 方 式 可 归 纳 为 种 如 图 所 示 重 建 的 过 程 就 是 对 边 界 体 素 进 行 绘 制 的 过 程 也 就 是 用 等 值 线 来 表 示 边 界 体 素 与 & 算 法 的 / 种 基 本 体 素 构 型 相 比 算 法 的 基 本 构 型 方 式 要 简 单 许 多 因 此 重 建 过 程 中 所 需 绘 制 的 等 值 线 也 相 对 较 少 绘 制 出 来 的 等 值 线 可 以 形 成 等 值 面 利 用 等 值 面 可 以 重 构 物 体 的 三 维 表 面 /+ 对 图 像 进 行 分 割 获 得 需 要 重 建 的 目 标 物 体 对 分 割 图 像 中 目 标 物 体 所 对 应 像 素 的 灰 度 值 进 行 设 置 + 检 测 所 有 的 像 素 点 体 素 确 定 边 界 体 素 和 等 值 体 素 对 边 界 体 素 中 的 等 值 点 进 行 连 接 生 成 等 值 线 等 值 线 连 接 构 成 等 值 面 等 值 面 构 成 物 体 的 三 维 重 建 表 面 并 显 示 重 建 结 果 算 法 像 素 点 移 动 体 素 面 绘 制 算 法. 阈 值 分 割 获 得 目 标 物 体 的 图 像 / 和 为 输 入 图 像 的 尺 寸 / / /0/ 0 / / 3 个 顶 点 的 值 都 为 该 体 素 为 等 值 体 素 该 体 素 为 边 界 体 素 连 接 与 断 层 / 中 的 等 值 点 生 成 等 值 线 和 等 值 面 显 示 重 建 结 果 8 像 素 点 移 动 体 素 面 绘 制 算 法 有 一 定 的 区 域 范 围 因 此 重 建 的 结 果 也 有 一 定 的 厚 度 像 素 点 移 动 体 素 面 绘 制 算 法 的 实 验 验 证 用 算 法 对 一 组 共 / 张 &' 图 像 的 骨 骼 组 织 进 行 三 维 重 建 首 先 通 过 相 关 算 法 计 算 获 得 图 像 的 最 优 分 割 阈 值 并 进 行 骨 骼 组 织 的 分 割 然 后 用 算 法 对 骨 骼 组 织 表 面 进 行 三 维 重 建 图 等 值 线 的 连 接 方 式 在 绘 制 等 值 线 之 前 先 对 体 素 进 行 跟 踪 以 确 定 边 界 体 素 的 位 置 然 后 对 边 界 体 素 进 行 绘 制 在 整 个 绘 制 过 程 中 不 需 要 对 等 值 体 素 进 行 绘 制 因 此 减 少 了 绘 制 体 素 的 个 数 整 个 绘 制 过 程 的 数 据 量 大 大 减 少! 像 素 点 移 动 体 素 面 绘 制 算 法 的 执 行 过 程 本 文 所 提 出 的 像 素 点 移 动 体 素 面 绘 制 算 法 的 执 行 过 程 主 要 包 括 以 下 几 步 / 用 阈 值 分 割 方 法!234 算 法 绘 制 等 值 面 对 / 张 图 像 进 行 重 建 所 花 费 时 间 的 复 杂 度 不 是 很 高 重 建 结 果 的 精 确 度 受 到 图 像 数 目 和 显 示 窗 口 轴 位 置 设 置 的 影 响 图 像 数 目 越 多 层 间 间 距 越 小 重 建 的 结 果 就 越 好 具 体 的 重 建 过 程 用 # 编 程 来 实 现 图 + 是 用 # 编 写 算 法 所 绘 制 的 骨 骼 组 织 三 维 表 面 设 轴 的 显 示 范 围 为 0/00 观 察 角 度 为 0+0 程 序 / 像 素 点 移 动 体 素 面 绘 制 算 法 的 实 现
/ 计 算 机 工 程 与 科 学 0/+ 量 很 大 占 用 内 存 多 给 处 理 带 来 一 定 困 难 根 据 实 际 情 况 在 不 影 响 结 果 的 情 况 下 可 以 对 数 据 进 行 预 处 理 以 减 少 所 处 理 的 数 据 量 利 用 函 数 $%& 图 + 骨 骼 组 织 的 三 维 表 面 重 建 算 法 和 为 图 像 的 尺 寸 为 分 割 组 织 的 阈 值 和 / 为 图 像 的 轴 坐 标 // // *$ / // /// ////// " /!/!&0"0"0" //!//!&0"0"0" '%%#( 和 函 数 )*++#, # 来 减 少 体 数 据 体 数 据 的 绘 制 利 用 函 数 和 函 数 计 算 体 数 据 集 在 显 示 平 面 的 累 计 投 影 和 体 数 据 的 轮 廓 语 句 - ))$-%# )% 可 以 实 现 等 值 面 的 绘 制 其 中 # 在 上 面 已 经 得 到 )% 为 绘 制 等 值 面 时 阈 值 的 大 小 阈 值 的 大 小 可 以 根 据 实 际 情 况 来 设 定 + 构 造 三 维 重 建 碎 片 使 用 #$ 函 数 来 对 图 像 子 区 域 进 行 分 类 可 以 利 用 属 性 -& 和 2$# 来 定 义 重 建 图 像 的 颜 色 光 线 等 信 息 图 是 用 # 的 函 数 函 数 和 #$ 函 数 直 接 对 分 割 获 得 的 体 数 据 进 行 等 值 面 绘 制 获 得 的 骨 骼 组 织 三 维 表 面 重 建 结 果 设 轴 的 显 示 范 围 为 0/00 观 察 角 度 为 //0 +0 /// /!//!&0"0"0" // /!/!&0"0"0"! 用 3* 函 数 绘 制 等 值 面 # 自 身 也 提 供 了 函 数 可 以 实 现 对 一 组 体 数 据 进 行 等 值 面 的 绘 制 对 于 一 组 断 层 图 像 可 以 利 用 函 数 # 组 成 一 个 三 维 体 数 据 集 # 断 层 图 像 三 维 表 面 的 重 建 就 是 绘 制 体 数 据 # 的 等 值 面 具 体 的 重 建 步 骤 如 下 所 示 / 数 据 预 处 理 三 维 体 数 据 # 的 矩 阵 数 据 图 骨 骼 组 织 的 等 值 面 绘 制 # 函 数! 重 建 结 果 分 析 方 法 和 # 函 数 方 法 的 最 初 坐 标 不 相 同 所 以 三 维 重 建 结 果 的 显 示 角 度 不 同 通 过 对 重 建 结 果 比 较 可 以 看 出 算 法 能 实 现 对 断 层 图 像 的 三 维 重 建 避 免 了 二 义 性 问 题 但 重 建 表 面 不 够 光 滑 需 要 对 重 建 结 果 进 行 平 滑 另 外 算 法 的 执 行 时 间 较 长 将 来 还 需 要 对 体 素 的 检 测 方 法 进 行 改 进 提 高 检 测 效 率 减 少 算 法 的 执 行 时 间 " 结 束 语 本 文 主 要 对 面 绘 制 方 法 进 行 研 究 & 算 法 是 一 种 重 要 的 基 于 体 素 的 面 绘 制 方 法 & 算 法 存 在 计 算 量 大 和 二 义 性 的 问 题 根 据 &' 图 像 的
郑 丽 萍 等 像 素 的 移 动 体 素 面 绘 制 算 法 特 点 和 研 究 目 的 本 文 对 & 算 法 进 行 研 究 和 改 进 提 出 了 像 素 点 移 动 体 素 面 绘 制 算 法 并 用 # 编 程 来 实 现 所 提 出 的 重 建 算 法 然 后 对 三 维 重 建 结 果 进 行 显 示 并 分 析 算 法 性 能 像 素 点 移 动 体 素 面 绘 制 算 法 是 根 据 物 体 的 显 示 特 性 和 & 算 法 的 基 本 原 理 确 定 边 界 体 素 的 等 值 点 并 对 等 值 点 进 行 连 接 生 成 等 值 线 利 用 等 值 线 和 等 值 面 来 表 示 重 建 组 织 的 三 维 表 面 实 验 表 明 该 算 法 的 执 行 时 间 长 重 建 表 面 不 够 光 滑 还 需 要 近 一 步 地 改 进 参 考 文 献 / 郭 尚 苏 鸿 根 基 于 距 离 倒 数 加 权 法 的 等 值 面 绘 制 简 化 算 法 计 算 机 工 程 与 设 计 0031/00/0 宫 法 明 赵 兴 龙 基 于 & 算 法 的 医 学 建 模 方 法 与 研 究 微 计 算 机 应 用 0/0+//0 + 程 东 旭 秦 新 强 龚 春 琼 等 一 种 改 进 的 $& 算 法 & 第 十 二 届 全 国 图 像 图 形 学 学 术 会 议 论 文 集 00 王 溪 秦 新 强 党 发 宁 等 医 学 图 像 三 维 重 建 的 规 则 移 动 立 方 体 法 西 安 理 工 大 学 学 报 0010/ 於 时 才 唐 占 红 & 消 除 重 建 算 的 二 义 性 清 除 研 究 微 计 算 机 信 息 0013 69%.'$(%##,"! #$%#( $&& # 1//11/3+1/ / 郑 丽 萍 /11 女 山 东 聊 城 人 博 士 副 教 授 研 究 方 向 为 图 像 处 理 和 人 工 智 能 )$30/+% /11$, #$$## %## 李 光 耀 /1 男 安 徽 安 庆 人 博 士 教 授 研 究 方 向 为 图 形 图 像 &, &8& 和 城 市 仿 真 )( #) /1$, $$##$%&, &8& #(%# 李 寰 /1 男 山 东 聊 城 人 硕 士 副 教 授 研 究 方 向 为 软 件 工 程 和 智 能 优 化 )$(% /1# $ $ ## #*###%#