MITK

Transcription

1 集 成 化 医 学 影 像 算 法 平 台 MITK 的 研 究 与 实 现 i

2 集 成 化 医 学 影 像 算 法 平 台 MITK 的 研 究 与 实 现 目 录 1 绪 论 医 学 影 像 算 法 平 台 研 究 的 背 景 及 意 义 医 学 影 像 算 法 平 台 研 究 的 内 容 整 体 框 架 的 研 究 医 学 影 像 算 法 的 研 究 医 学 影 像 算 法 平 台 的 国 内 外 研 究 现 状 VTK 简 介 ITK 简 介 VTK 和 ITK 的 局 限 性 本 书 的 主 要 内 容 MITK 的 总 体 设 计 MITK 的 设 计 目 标 统 一 的 风 格 有 限 目 标 可 移 植 性 代 码 优 化 MITK 的 整 体 计 算 框 架 基 于 数 据 流 模 型 的 整 体 框 架 数 据 模 型 算 法 模 型 MITK 的 基 础 设 施 搭 建 Object 提 供 的 服 务 内 存 管 理 跨 平 台 的 实 现 SSE 加 速 的 实 现 小 结...27 ii

3 集 成 化 医 学 影 像 算 法 平 台 MITK 的 研 究 与 实 现 3 面 绘 制 (SURFACE RENDERING) 的 框 架 与 实 现 表 面 重 建 算 法 及 其 在 MITK 中 的 实 现 传 统 的 Marching Cubes 算 法 基 于 分 割 的 Marching Cubes 方 法 [1] MITK 中 的 表 面 绘 制 框 架 表 面 绘 制 框 架 的 设 计 表 面 绘 制 框 架 的 实 现 小 结 体 绘 制 (VOLUME RENDERING) 的 框 架 与 实 现 体 绘 制 算 法 综 述 MITK 中 的 体 绘 制 算 法 框 架 体 绘 制 算 法 在 MITK 中 的 实 现 View 中 绘 制 操 作 的 实 现 VolumeModel 的 实 现 VolumeProperty 的 实 现 VolumeRenderer 的 实 现 Ray Casting 算 法 的 实 现 小 结 三 维 人 机 交 互 的 设 计 与 实 现 背 景 介 绍 以 3D WIDGETS 为 核 心 的 三 维 人 机 交 互 的 框 架 设 计 D Widgets 的 设 计 准 则 以 3D Widgets 为 核 心 的 三 维 交 互 框 架 总 体 结 构 以 3D Widgets 为 核 心 的 三 维 交 互 框 架 设 计 以 3D WIDGETS 为 核 心 的 三 维 人 机 交 互 的 实 现 Manipulator 的 实 现 实 现 具 体 的 WidgetModel 三 维 交 互 的 应 用 实 例 iii

4 集 成 化 医 学 影 像 算 法 平 台 MITK 的 研 究 与 实 现 mitklinewidgetmodel3d 的 应 用 实 例 mitkanglewidgetmodel3d 的 应 用 实 例 mitkclippingplanewidget 的 应 用 实 例 小 结 分 割 算 法 的 设 计 与 实 现 MITK 中 的 分 割 算 法 框 架 数 据 模 块 数 据 获 取 模 块 数 据 输 出 模 块 数 据 处 理 模 块 基 于 阈 值 的 分 割 算 法 在 MITK 中 的 实 现 原 理 概 述 阈 值 分 割 算 法 开 发 包 设 计 与 实 现 阈 值 分 割 结 果 示 意 图 区 域 增 长 算 法 在 MITK 中 的 实 现 原 理 概 述 区 域 生 长 算 法 开 发 包 的 设 计 与 实 现 区 域 生 长 分 割 结 果 交 互 式 分 割 在 MITK 中 的 实 现 原 理 概 述 交 互 式 分 割 算 法 开 发 包 的 设 计 与 实 现 交 互 式 分 割 算 法 的 分 割 结 果 LIVE WIRE 算 法 在 MITK 中 的 实 现 原 理 概 述 live Wire 算 法 包 的 设 计 与 实 现 live wire 分 割 结 果 FAST MARCHING 算 法 在 MITK 中 的 实 现 原 理 概 述 Fast Marching 算 法 开 发 包 的 设 计 与 实 现 iv

5 集 成 化 医 学 影 像 算 法 平 台 MITK 的 研 究 与 实 现 Fast Marching 分 割 结 果 LEVEL SET 算 法 在 MITK 中 的 实 现 原 理 概 述 level set 算 法 开 发 包 的 设 计 与 实 现 level set 分 割 结 果 配 准 算 法 的 设 计 与 实 现 配 准 算 法 简 介 MITK 中 的 配 准 算 法 框 架 几 何 变 换 刚 性 变 换 算 法 线 性 变 换 与 一 对 一 变 换 变 换 算 法 在 MITK 中 的 实 现 图 像 插 值 最 近 邻 插 值 线 性 插 值 PV 插 值 插 值 算 法 在 MITK 中 的 实 现 相 似 性 测 度 灰 度 平 均 差 测 度 归 一 化 相 关 系 数 Pattern Intensity 互 信 息 相 似 性 测 度 在 MITK 中 的 实 现 函 数 优 化 配 准 算 法 实 现 应 用 实 例 小 结 DICOM 标 准 的 实 现 v

6 集 成 化 医 学 影 像 算 法 平 台 MITK 的 研 究 与 实 现 8.1 DICOM 标 准 简 介 DICOM 标 准 的 产 生 和 演 化 DICOM 标 准 的 主 要 特 点 DICOM 标 准 的 总 体 结 构 和 主 要 内 容 MITK 中 DICOM 标 准 的 实 现 DICOM 数 据 编 码 方 式 和 文 件 结 构 [1] [1] DICOM 文 件 读 写 模 块 (DICOM Utility) 的 实 现 DICOM Utility 在 MITK 中 的 封 装 小 结 应 用 MITK 开 发 实 际 项 目 开 发 环 境 的 设 置 一 个 简 单 的 图 像 浏 览 器 用 MITK 进 行 表 面 重 建 一 个 比 较 完 善 的 例 子 扩 充 MITK 功 能 扩 充 MITK 功 能 的 预 备 知 识 实 例 之 一 : 扩 充 READER 功 能 扩 充 Reader 功 能 的 一 般 步 骤 实 例 程 序 的 功 能 实 例 程 序 的 制 作 实 例 之 二 : 扩 充 FILTER 功 能 扩 充 Filter 功 能 的 一 般 步 骤 实 例 程 序 的 功 能 实 例 程 序 的 制 作 小 结 基 于 MITK 的 三 维 医 学 影 像 处 理 与 分 析 系 统 3DMED 的 设 计 与 实 现 背 景 介 绍 相 关 工 作 vi

7 集 成 化 医 学 影 像 算 法 平 台 MITK 的 研 究 与 实 现 DVIEWNIX 系 统 简 介 VolView 系 统 简 介 DMED 的 整 体 设 计 DMed 的 设 计 目 标 DMed 提 供 的 功 能 简 介 DMED 的 PLUGIN 整 体 框 架 的 实 现 Plugin SDK 的 实 现 Plugins 的 实 现 DMed Kernel 的 实 现 应 用 实 例 小 结 开 发 3DMED 的 PLUGIN 总 体 介 绍 PLUGIN 实 例 : 使 用 MITK 工 程 的 建 立 及 设 置 实 例 制 作 插 入 到 3DMed PLUGIN 实 例 : 不 使 用 MITK 工 程 的 建 立 及 设 置 实 例 制 作 插 入 到 3DMed 小 结 附 录 A 医 学 影 像 数 据 集 附 录 B MITK 网 站 介 绍 vii

8 1 绪 论 1 绪 论 1.1 医 学 影 像 算 法 平 台 研 究 的 背 景 及 意 义 自 从 德 国 科 学 家 伦 琴 在 1895 年 发 明 X 射 线 以 来,CT( 计 算 机 断 层 成 像 ) MRI( 核 磁 共 振 成 像 ) CR( 计 算 机 X 线 成 像 ) B 超 电 子 内 窥 镜 等 现 代 医 学 影 像 设 备 先 后 出 现, 使 得 传 统 的 医 学 诊 断 方 式 发 生 了 革 命 性 的 变 化 使 用 计 算 机 对 医 学 影 像 设 备 采 集 到 的 影 像 进 行 处 理 这 一 技 术 被 称 为 医 学 影 像 处 理 与 分 析, 它 可 以 辅 助 医 生 进 行 更 好 更 准 确 的 诊 断 随 着 现 代 计 算 机 科 学 技 术 的 发 展, 医 学 影 像 处 理 与 分 析 越 来 越 多 地 受 到 人 们 的 重 视, 现 在 已 经 成 为 一 门 新 兴 的 发 展 迅 速 的 交 叉 科 学 领 域 [1] 21 世 纪 是 以 人 为 中 心 的 世 纪, 如 何 更 全 面 地 掌 握 和 更 有 效 地 利 用 人 的 信 息 将 成 为 许 多 高 新 技 术 产 业 的 关 键 因 素, 而 跟 全 社 会 人 民 的 医 疗 保 健 和 健 康 事 业 息 息 相 关 的 医 学 影 像 处 理 与 分 析 学 科 也 将 在 21 世 纪 得 到 快 速 的 发 展 医 学 影 像 处 理 与 分 析 是 计 算 机 信 息 学 物 理 学 和 医 学 等 相 结 合 的 产 物, 在 20 世 纪 内 经 历 了 学 科 形 成 发 展 和 快 速 发 展 的 过 程, 如 果 说 20 世 纪 是 医 学 影 像 形 成 和 快 速 发 展 的 世 纪, 在 21 世 纪 就 将 是 医 学 影 像 广 泛 应 用 的 世 纪 目 前 随 着 改 革 开 放 和 国 力 不 断 提 高, 我 国 从 国 外 进 口 了 越 来 越 多 的 高 精 密 的 医 疗 设 备 并 在 医 疗 临 床 上 广 泛 使 用 然 而, 由 于 国 内 缺 乏 配 套 的 开 发 队 伍, 也 没 有 形 成 开 展 跨 学 科 开 发 研 究 的 机 制, 一 般 使 用 的 都 是 国 外 公 司 随 机 器 附 带 的 软 件, 使 得 我 国 对 这 些 高 精 密 医 疗 设 备 利 用 及 研 发 的 速 度 缓 慢 考 虑 到 目 前 以 硬 件 设 备 为 主 的 医 疗 器 械 都 必 须 配 套 相 应 的 计 算 机 软 件, 而 软 件 的 成 本 和 开 支 将 逐 步 超 过 硬 件, 目 前 我 国 已 经 逐 步 具 备 了 医 疗 器 械 的 生 产 能 力, 但 是 高 质 量 的 配 套 软 件 仍 然 相 当 缺 乏, 因 为 软 件 的 编 制 依 赖 于 对 科 学 问 题 的 数 学 描 述 和 计 算 方 法 21 世 纪 的 产 业, 医 学 影 像 的 计 算 模 型 和 计 算 方 法 将 成 为 制 约 医 学 软 件 业 的 首 要 因 素, 抓 住 这 一 契 机 将 成 为 我 国 医 疗 信 息 高 质 量 稳 定 发 展 和 参 与 国 际 竞 争 的 重 中 之 重 而 积 累 发 展 具 有 我 国 自 主 知 识 产 权 的 高 质 量 的 医 学 影 像 软 件 平 台, 尤 其 是 底 层 的 算 法 研 发 平 台, 对 促 进 我 国 医 疗 仪 器 设 备 的 应 用 尤 其 是 医 学 影 像 软 件 业 的 持 续 发 展, 并 直 接 造 福 于 人 民 的 医 疗 保 健 和 健 康 事 业 是 非 常 重 要 的 1

9 1 绪 论 由 于 医 学 影 像 领 域 的 研 究 涉 及 的 面 非 常 宽, 研 究 本 身 需 要 多 学 科 的 交 叉, 这 就 导 致 开 发 医 学 影 像 领 域 的 高 质 量 软 件, 尤 其 是 算 法 研 发 平 台 非 常 困 难 但 是 一 旦 研 究 成 功 之 后, 受 益 面 将 会 非 常 大, 今 后 的 发 展 前 途 非 常 广 阔 中 国 是 世 界 上 人 口 最 多 的 国 家, 国 际 间 的 竞 争, 国 家 的 安 全 本 质 上 是 国 民 平 均 素 质 之 间 的 竞 争 利 用 现 代 信 息 学 已 取 得 的 科 学 成 果, 对 人 体 医 学 影 像 信 息 进 行 挖 掘, 建 立 相 应 的 理 论 方 法 并 开 发 相 应 的 软 件 开 发 平 台, 必 将 为 人 类 对 自 身 的 认 知 疾 病 的 诊 断 和 治 疗 国 民 教 育 及 商 业 软 件 的 开 发 提 供 极 好 的 机 会, 使 得 医 学 影 像 信 息 学 科 在 中 国 的 发 展 奠 定 良 好 基 础 可 以 预 计 : 医 学 影 像 将 会 扩 展 到 医 院 的 每 个 科 室, 每 个 病 人, 以 至 全 社 会 每 个 家 庭 成 员, 成 为 每 个 人 健 康 状 况 记 录 的 基 本 信 息 源 之 一 在 发 达 国 家, 尤 其 是 美 国 对 开 发 高 质 量 的 医 学 影 像 软 件 和 算 法 研 发 平 台 非 常 重 视 美 国 国 家 卫 生 院 下 属 的 国 立 医 学 图 书 馆 近 年 投 入 巨 资 支 持 三 家 科 研 机 构 ( 包 括 University of North Carolina University of Utah University of Pennsylvania) 开 发 医 学 影 像 分 割 与 配 准 算 法 的 研 发 平 台 ITK ( Insight Segmentation and Registration Toolkit)[2], 现 在 已 经 开 发 出 初 步 的 版 本 在 医 学 影 像 领 域 的 主 流 国 际 会 议 SPIE Medical Imaging 在 2004 年 的 年 会 上 有 一 个 专 门 的 Session, 叫 做 Visualization Toolkits, 探 讨 医 学 影 像 领 域 内 算 法 研 发 平 台 的 研 究 ; 而 在 Medical Image Computing & Computer Assisted Intervention(MICCAI)2003 会 议 上 有 一 个 专 门 的 Workshop, 叫 做 Software Development Issues for Medical Imaging Computing & Computer Assisted Interventions, 也 是 探 讨 未 来 在 医 学 影 像 领 域 内 高 质 量 软 件, 尤 其 是 算 法 研 发 平 台 (Toolkits) 的 研 究 问 题 考 虑 到 医 学 影 像 技 术 在 未 来 世 纪 的 重 要 性, 以 及 国 内 外 相 关 研 究 人 员 对 一 个 集 成 化 的 医 学 影 像 算 法 研 发 平 台 的 需 求, 本 书 的 工 作 是 希 望 通 过 MITK 的 研 究 与 开 发 以 及 免 费 发 行, 能 够 推 广 医 学 影 像 软 件 在 国 内 的 广 泛 使 用, 为 我 国 民 族 软 件 事 业 和 医 疗 事 业 做 出 自 己 微 薄 的 贡 献 1.2 医 学 影 像 算 法 平 台 研 究 的 内 容 对 于 一 个 实 用 的 医 学 影 像 算 法 平 台 来 说, 有 两 个 大 的 方 面 需 要 研 究 : 第 一 个 方 面 是 整 体 框 架 的 研 究 ; 第 二 个 方 面 是 医 学 影 像 算 法 方 面 的 研 究, 又 包 括 医 学 影 像 分 割 医 学 影 像 配 准 三 维 可 视 化 这 三 大 研 究 领 域 2

10 1 绪 论 整 体 框 架 的 研 究 医 学 影 像 处 理 与 分 析 的 目 的 是 从 数 据 到 知 识, 其 中 在 算 法 层 面 包 含 医 学 影 像 分 割 医 学 影 像 配 准 ( 包 括 图 像 信 息 融 合 ) 三 维 可 视 化 ( 包 括 表 面 绘 制 体 绘 制 和 数 字 几 何 处 理 ) 等 ; 在 数 据 表 达 层 面, 医 学 影 像 数 据 具 有 多 源 (CT MRI PET 等 ) 多 维 ( 二 维 三 维 四 维 及 更 高 维 ) 多 模 态 ( 形 态 生 理 心 理 病 理 ) 异 构 信 息 ( 像 素 矩 阵 表 示 的 图 像 像 素 集 合 表 示 的 目 标 符 号 表 示 的 知 识 ) 等 特 点 如 何 对 这 么 多 的 算 法 以 及 这 么 复 杂 的 数 据 进 行 抽 象, 得 到 统 一 的 数 据 表 达 和 高 效 处 理 方 法, 以 便 能 够 在 一 个 统 一 的 软 件 框 架 中 高 效 精 确 地 来 处 理 是 一 个 比 较 困 难 的 问 题 另 外, 目 前 研 究 人 员 在 各 个 算 法 分 支 已 经 提 出 了 多 种 算 法, 并 且 现 在 对 于 各 种 算 法 性 能 的 评 价 的 研 究 也 越 来 越 受 到 重 视, 比 如 对 分 割 算 法 准 确 性 的 评 价 已 经 成 为 一 个 非 常 前 沿 的 问 题 如 果 将 这 些 算 法 置 入 一 个 统 一 的 计 算 框 架, 组 成 一 条 管 道 式 的 流 水 线, 在 统 一 的 数 据 表 达 统 一 的 算 法 框 架 以 及 统 一 的 参 数 设 置 下, 去 研 究 各 个 算 法 的 性 能 前 一 算 法 对 后 续 算 法 性 能 的 影 响 等 等, 不 仅 能 更 好 地 在 局 部 上 去 理 解 单 个 算 法 的 性 能 指 标 不 同 算 法 的 性 能 差 异, 还 有 助 于 在 整 体 上 去 理 解 和 把 握 不 同 算 法 之 间 的 影 响 整 体 的 瓶 颈 所 在 不 同 信 息 的 整 合 等 医 学 影 像 算 法 的 研 究 目 前 医 学 影 像 算 法 方 面 的 研 究 主 要 分 为 医 学 影 像 分 割 医 学 影 像 配 准 三 维 可 视 化 这 三 大 研 究 领 域, 其 中 每 一 类 下 面 又 可 根 据 一 定 的 原 则 分 为 不 同 的 子 类, 并 且 每 一 个 子 类 都 有 非 常 多 不 同 的 算 法 (1) 医 学 影 像 分 割 算 法 医 学 影 像 分 割 的 主 要 目 的 是 将 医 学 影 像 中 感 兴 趣 的 物 体 ( 一 般 是 病 灶 区 ) 提 取 出 来, 以 前 医 生 往 往 是 通 过 自 己 的 经 验 手 工 分 割 病 灶 区, 而 分 割 的 目 的 就 是 尽 量 自 动 准 确 地 将 这 些 病 灶 区 提 取 出 来 图 像 分 割 是 图 像 处 理 图 像 分 析 和 计 算 机 视 觉 等 领 域 最 经 典 的 研 究 课 题 之 一, 也 是 最 大 的 难 点 之 一, 其 理 论 和 方 法 至 今 尚 未 获 得 圆 满 的 解 决 在 医 学 领 域, 图 像 分 割 也 一 直 是 一 个 非 常 活 跃 的 研 究 课 题, 吸 引 着 很 多 的 研 究 人 员 去 探 索 这 个 问 题 医 学 影 像 分 割 可 以 大 致 分 为 以 下 几 种 类 型 : 基 于 区 域 的 分 割 方 法, 包 括 阈 值 分 割 [3][4] 区 域 生 长 等 [5]; 基 于 边 缘 的 分 割 方 法, 包 括 梯 度 算 子 Roberts 算 子 3

11 1 绪 论 Sobel 算 子 Prewitt 算 子 Laplacian 算 子 和 Kirsch 算 子 等 [1]; 基 于 形 变 模 型 的 方 法, 包 括 Active Contour[6] Level Set[7] Fast Marching[8] 等 ; 基 于 人 机 交 互 的 方 法, 包 括 手 工 交 互 式 分 割 Live Wire 分 割 [9] 等 (2) 医 学 影 像 配 准 算 法 医 学 影 像 配 准 的 主 要 目 的 是 将 两 幅 医 学 影 像 上 的 对 应 点 达 到 空 间 上 的 一 致, 也 就 是 找 出 两 幅 图 像 中 对 应 于 人 体 同 一 位 置 的 点 的 对 应 关 系, 从 而 可 以 让 医 生 把 多 幅 不 同 模 态 的 图 像 融 合 起 来 获 得 更 多 的 信 息 目 前 对 于 多 模 态 医 学 影 像 的 配 准, 以 及 对 具 有 弹 性 形 变 的 图 像 之 间 的 配 准 都 是 非 常 热 门 的 研 究 领 域 医 学 影 像 配 准 算 法 也 有 很 多 不 同 的 类 型, 根 据 空 间 维 数 的 数 目 和 时 间 是 否 为 附 加 维 这 两 点 可 以 分 为 2D/2D 2D/3D 3D/3D 图 像 配 准 ; 根 据 配 准 所 依 据 的 特 征 可 分 为 基 于 外 部 特 征 和 基 于 内 部 特 征 两 大 类 ; 根 据 变 换 的 性 质 可 分 为 刚 性 变 换 仿 射 变 换 投 影 变 换 和 曲 线 变 换 四 种 ; 根 据 用 户 交 互 性 的 多 少, 可 分 为 交 互 的, 半 自 动 的 和 自 动 的 三 种 ; 根 据 配 准 的 医 学 图 像 模 态 可 以 分 为 单 模 图 像 之 间 的 配 准 多 模 图 像 之 间 的 配 准 和 患 者 和 模 态 之 间 的 配 准 这 四 种 ; 根 据 配 准 过 程 中 变 换 参 数 确 定 的 方 式 可 以 分 为 两 种, 一 种 是 通 过 直 接 计 算 公 式 来 得 到, 另 一 种 是 通 过 在 参 数 空 间 中 寻 求 某 个 函 数 的 最 优 解 来 得 到 [10] (3) 三 维 可 视 化 算 法 三 维 可 视 化 的 主 要 目 的 是 将 医 学 影 像 设 备 得 到 的 一 系 列 的 二 维 的 切 片, 使 用 计 算 机 图 形 学 的 技 术, 构 造 出 一 个 器 官 的 三 维 模 型, 并 且 非 常 逼 真 地 显 示 给 医 生, 它 是 科 学 可 视 化 研 究 的 一 个 重 要 的 分 支 目 前 随 着 医 疗 设 备 的 进 展, 医 学 影 像 数 据 集 越 来 越 大, 海 量 的 数 据 给 传 统 的 三 维 重 建 与 绘 制 技 术 带 来 了 非 常 大 的 挑 战, 所 以 目 前 大 数 据 量 的 三 维 医 学 影 像 的 快 速 重 建 和 绘 制 技 术 也 是 一 个 非 常 有 挑 战 性 的 问 题 三 维 可 视 化 可 以 分 为 三 个 大 类 : 表 面 绘 制 (Surface Rendering) 体 绘 制 (Volume Rendering) 和 数 字 几 何 处 理 表 面 绘 制 包 括 经 典 的 Marching Cubes 算 法 [11][12],Cuberille[13] 算 法 等 ; 体 绘 制 包 括 经 典 的 Ray Casting[14] 算 法 Splatting[15] 算 法 Shear Warp[16] 算 法, 以 及 新 近 出 现 的 基 于 图 形 硬 件 GPU 的 加 速 算 法 [17][18] 等 ; 而 数 字 几 何 处 理 [19][20] 是 在 SigGraph 2001 上 才 提 出 的 一 个 新 概 念, 用 于 对 表 面 绘 制 产 生 的 网 格 进 行 处 理, 包 括 网 格 化 简 网 格 细 分 网 4

12 1 绪 论 格 平 滑 等 算 法 1.3 医 学 影 像 算 法 平 台 的 国 内 外 研 究 现 状 如 上 所 述, 医 学 影 像 处 理 算 法 的 三 个 主 要 研 究 领 域 目 前 都 已 经 有 非 常 多 的 成 熟 的 算 法, 并 且 新 的 算 法 还 在 不 断 出 现 除 了 在 算 法 研 究 方 面 的 努 力 外, 一 些 研 究 组 织 为 了 更 好 地 利 用 现 有 的 算 法, 避 免 重 复 的 劳 动, 开 发 了 许 多 算 法 平 台 (Algorithms Toolkit), 这 些 算 法 平 台 不 仅 封 装 了 他 们 自 己 的 算 法, 还 封 装 了 很 多 已 经 成 熟 的 相 关 算 法 这 些 算 法 平 台 极 大 地 便 利 了 医 学 影 像 领 域 的 研 究 者, 他 们 可 以 在 这 些 平 台 上 来 创 建 自 己 的 实 验 环 境, 验 证 自 己 的 算 法, 而 不 用 从 头 再 写 一 些 已 经 成 熟 的 算 法 可 以 作 个 比 喻, 这 些 平 台 的 作 用 就 相 当 于 Matlab 对 于 研 究 人 员 的 作 用 一 样, 不 过 它 们 是 专 门 针 对 医 学 影 像 领 域 的 目 前 在 医 学 影 像 研 究 人 员 中 使 用 最 广 泛 的 两 个 算 法 平 台 是 VTK(Visualization Toolkit) 和 ITK, 虽 然 还 有 其 它 一 些 平 台, 但 是 它 们 都 不 系 统, 只 是 针 对 某 一 个 特 定 的 领 域 的, 另 外,VTK 和 ITK 也 是 对 MITK 的 设 计 影 响 最 大, 最 相 关 的 两 个 算 法 平 台, 所 以 下 面 分 别 介 绍 一 下 它 们 的 发 展 历 程 和 发 展 现 状, 并 给 出 它 们 的 局 限 性 VTK 简 介 VTK(Visualization ToolKit)[21] 是 一 套 进 行 数 据 可 视 化 的 开 发 工 具 包, 最 早 在 1993 年 12 月 由 美 国 GE 公 司 研 发 部 门 的 Will Schroeder 和 Ken Martin 首 次 发 布, 当 时 是 作 为 The Visualization Toolkit: An Object-Oriented Approach to 3D Graphics 这 本 书 的 配 套 软 件 赠 送, 后 来 在 1998 年 时, 此 书 出 版 第 二 版, 并 且 在 此 五 年 期 间 使 用 VTK 的 人 数 不 断 增 加, 形 成 了 一 个 社 区,VTK 也 以 开 放 源 码 (Open Source) 的 形 式 开 发 现 在 这 本 书 已 经 出 到 第 三 版 [22], 同 时 VTK 也 由 美 国 Kitware 公 司 负 责 维 护, 全 世 界 的 开 发 人 员 都 可 以 贡 献 自 己 的 力 量 VTK 完 全 采 用 面 向 对 象 的 设 计 思 想 来 设 计 与 开 发 [23], 其 提 供 了 非 常 强 大 的 功 能, 提 供 了 超 过 300 个 C++ 类, 并 且 可 以 支 持 跨 平 台 开 发, 支 持 Windows Unix Linux 等 多 种 平 台 [24] 值 得 一 提 的 是,VTK 并 不 是 专 门 针 对 医 学 影 像 领 域 开 发 的 平 台, 它 的 主 要 目 标 是 通 用 可 视 化 领 域, 但 是 它 仍 然 在 医 学 影 像 领 域 得 到 了 比 较 广 泛 的 应 用, 这 一 方 面 与 其 几 个 主 力 研 发 人 员 在 GE 公 司 的 背 景 分 不 开 ( 他 们 是 表 面 绘 制 经 典 算 法 Marching Cubes 算 法 的 发 明 人 ), 另 外 一 个 方 面 是 因 为 VTK 里 面 提 供 了 表 面 绘 制 体 绘 制 一 部 分 数 字 几 何 处 理 算 法, 这 些 都 对 医 学 5

13 1 绪 论 影 像 领 域 内 的 研 究 有 所 帮 助 发 展 到 现 在,VTK 的 稳 定 版 本 已 经 发 行 到 4.2 版 本, 并 且 新 的 5.0 版 本 也 在 持 续 地 开 发 中, 已 经 成 为 通 用 可 视 化 领 域 内 最 负 盛 名 的 软 件 开 发 包, 也 在 医 学 影 像 领 域 内 赢 得 了 尊 敬 ITK 简 介 ITK(Insight Segmentation and Registration Toolkit)[2] 的 主 要 目 的 是 提 供 一 个 医 学 影 像 分 割 与 配 准 的 算 法 平 台, 它 的 起 源 还 是 基 于 美 国 的 可 视 人 体 项 目 [25], 当 可 视 人 体 的 数 据 采 集 完 成 以 后, 对 这 些 数 据 进 行 配 准 并 分 割 就 形 成 了 迫 切 的 需 求, 因 此 在 1999 年, 由 美 国 NIH( 国 家 卫 生 院 ) 下 属 的 NLM( 国 立 医 学 图 书 馆 ) 发 起 了 一 个 投 标 活 动, 要 出 资 资 助 开 发 一 个 分 割 与 配 准 的 算 法 研 发 平 台, 作 为 可 视 人 体 项 目 的 一 个 工 具, 对 可 视 人 体 项 目 得 到 的 数 据 进 行 处 理 与 分 析 最 终 选 中 六 家 单 位 合 作 开 发, 包 括 University of North Carolina,University of Utah,University of Pennsylvania 三 个 大 学, 以 及 Kitware GE Insightful 三 个 商 业 公 司 从 1999 年 10 月 开 始, 到 2002 年 10 月, 已 经 完 成 了 第 一 个 三 年 计 划, 并 成 功 发 行 了 ITK 1.0 与 VTK 相 同 的 是,ITK 的 框 架 设 计 也 是 由 Kitware 公 司 来 完 成 的 ; 但 是 与 VTK 严 重 不 同 的 是, 它 们 的 设 计 风 格 截 然 不 同 ITK 大 量 使 用 了 1998 年 以 后 ANSI C++ 标 准 里 面 的 新 特 性, 尤 其 是 Template( 模 板 ), 并 且 ITK 整 个 就 是 基 于 范 型 编 程 (Generic Programming)[26] 这 种 设 计 思 想 来 设 计 与 实 现 的 ITK 也 可 以 支 持 跨 平 台 开 发, 支 持 Windows Unix Linux 等 多 种 平 台, 目 前 也 是 采 用 Open Source 的 形 式 发 行, 最 大 限 度 地 推 广 它 经 过 四 年 多 的 开 发, 目 前 ITK 的 稳 定 版 本 已 经 发 行 到 1.6, 提 供 了 几 乎 所 有 主 流 的 医 学 影 像 分 割 与 配 准 算 法 [27], 并 且 现 在 还 一 直 在 持 续 地 进 化, 它 已 经 并 且 将 继 续 为 医 学 影 像 领 域 内 的 研 究 人 员 提 供 一 个 分 割 与 配 准 算 法 的 仓 库 和 基 础 VTK 和 ITK 的 局 限 性 VTK 和 ITK 目 前 已 经 成 为 国 际 上 非 常 知 名 的 可 视 化 与 医 学 影 像 分 割 与 配 准 的 算 法 研 发 平 台, 已 经 并 且 正 在 为 研 究 人 员 提 供 着 非 常 多 的 便 利 但 是 由 于 一 些 原 因, 导 致 VTK 或 者 ITK 或 者 VTK+ITK 有 一 些 自 己 的 缺 陷, 影 响 了 其 在 更 大 范 围 的 广 泛 使 用 首 先, 因 为 ITK 并 不 提 供 可 视 化 的 能 力, 所 以 一 般 要 与 VTK 联 合 起 来 使 用 6

14 1 绪 论 才 能 构 成 一 个 比 较 完 整 的 医 学 影 像 的 处 理 与 分 析 系 统 首 先 使 用 ITK 进 行 影 像 的 配 准 分 割, 然 后 再 使 用 VTK 进 行 三 维 可 视 化, 观 看 结 果, 这 样 就 极 大 地 增 加 了 复 杂 度 尤 其 是 VTK 和 ITK 所 使 用 的 编 程 风 格 完 全 不 同,VTK 开 发 的 比 较 早, 在 1998 年 ANSI C++ 标 准 制 定 之 前 就 已 经 比 较 成 型, 所 以 使 用 的 是 传 统 的 Object-Oriented( 面 向 对 象 ) 的 设 计 和 开 发 方 法 ; 而 ITK 是 在 1999 年 才 开 始 开 发 的, 所 以 运 用 了 许 多 新 的 C++ 语 言 的 特 性, 以 及 Generic Programming( 范 型 编 程 ) 的 设 计 和 开 发 方 法 这 种 编 程 风 格 上 的 不 一 致, 导 致 了 同 时 使 用 VTK 和 ITK 时, 必 须 学 习 两 套 规 模 都 相 当 庞 大 的 开 发 平 台, 对 使 用 者 造 成 了 一 定 的 学 习 难 度 其 次,VTK 是 一 个 面 向 通 用 可 视 化 领 域 的 一 个 开 发 平 台, 并 不 是 专 门 针 对 医 学 领 域 的 VTK 的 规 模 相 当 庞 大, 里 面 的 算 法 也 很 多, 这 样 一 方 面 使 得 它 的 适 用 面 非 常 宽, 有 很 多 领 域 的 研 究 人 员 都 可 以 使 用 它, 但 是 另 外 一 方 面 也 使 得 它 的 复 杂 度 大 大 增 加 同 时 因 为 要 照 顾 到 各 个 领 域, 在 设 计 VTK 的 时 候, 主 要 目 标 是 一 个 通 用 的 灵 活 的 框 架, 并 没 有 对 某 一 个 特 定 的 算 法 进 行 优 化, 因 此 VTK 的 速 度 并 不 是 太 令 人 满 意 最 后,ITK 是 专 门 针 对 医 学 影 像 的 分 割 和 配 准 而 实 现 的 一 个 开 发 平 台, 因 为 历 史 性 的 原 因,ITK 并 没 有 重 新 实 现 可 视 化 的 功 能, 而 是 利 用 VTK 的 可 视 化 的 功 能 对 ITK 来 说, 设 计 的 时 候 利 用 了 非 常 多 的 现 代 C++ 语 言 的 新 特 性, 并 且 大 量 使 用 了 模 板 这 本 来 是 一 件 非 常 好 的 事 情, 但 是 因 为 C++ 的 新 标 准 刚 颁 布 没 有 几 年, 导 致 现 在 有 很 多 编 译 器 不 能 完 全 编 译 ITK; 并 且 因 为 ITK 里 面 大 量 依 赖 于 STL 和 模 板, 导 致 最 终 只 能 编 译 成 一 个 静 态 的 函 数 库, 而 不 能 实 现 动 态 的 加 载 ; 同 时 最 重 要 的 一 点 是, 有 很 多 医 学 影 像 领 域 的 研 究 人 员 对 C++ 的 新 标 准 以 及 模 板 编 程 技 术 了 解 的 不 是 很 深 入, 导 致 他 们 在 使 用 ITK 时 感 觉 就 象 在 学 习 一 门 新 的 编 程 语 言 由 于 上 面 的 这 些 原 因, 现 在 ITK 还 只 是 在 一 个 比 较 小 的 范 围 内 被 使 用 1.4 本 书 的 主 要 内 容 考 虑 到 上 面 这 些 因 素, 本 书 介 绍 的 主 要 是 我 们 实 验 室 研 发 的 集 成 化 的 医 学 影 像 处 理 与 分 析 算 法 研 发 平 台 MITK(Medical Imaging ToolKit) 其 目 的 很 简 单, 所 谓 集 成 化, 就 是 指 在 一 个 统 一 的 框 架 里 面 来 实 现 医 学 影 像 分 割 配 准 7

15 1 绪 论 三 维 可 视 化 等 算 法, 弥 补 VTK+ITK 的 缺 憾 MITK 并 不 是 要 取 代 VTK 和 ITK, 而 只 是 给 医 学 影 像 领 域 内 的 研 究 人 员 和 开 发 人 员 提 供 另 外 的 一 个 可 用 选 择, 用 来 丰 富 国 际 上 的 医 学 影 像 算 法 平 台 另 外, 为 了 验 证 使 用 MITK 开 发 复 杂 医 学 影 像 实 用 系 统 的 能 力, 我 们 还 基 于 MITK 设 计 并 实 现 了 三 维 医 学 影 像 处 理 与 分 析 系 统 3DMed Kitware 公 司 也 曾 经 使 用 VTK 来 开 发 了 一 个 医 学 影 像 可 视 化 系 统 VolView, 但 可 惜 的 是 这 是 一 个 商 业 软 件, 即 使 用 于 科 研 目 的 也 是 需 要 购 买 License 的 MITK 和 3DMed 均 作 为 免 费 软 件 (Freeware) 在 Internet 上 发 布 ( 本 书 工 作 的 另 外 一 层 意 义 就 是 希 望 能 够 推 广 医 学 影 像 软 件 在 国 内 的 广 泛 使 用 具 体 来 讲, 本 书 介 绍 的 内 容 主 要 集 中 在 两 个 方 面 : 第 一 个 方 面 是 算 法 研 究 方 面, 在 表 面 绘 制 的 算 法 尤 其 是 大 规 模 医 学 数 据 的 可 视 化 算 法 的 研 究 方 面 作 了 一 些 探 讨, 这 个 部 分 主 要 在 第 三 章 中 介 绍 ; 第 二 个 方 面 是 平 台 的 框 架 设 计 以 及 分 割 配 准 可 视 化 算 法 在 MITK 中 的 实 现 方 面, 主 要 是 设 计 并 实 现 集 成 化 的 医 学 影 像 处 理 与 分 析 算 法 平 台 MITK, 这 个 部 分 的 内 容 分 散 在 本 书 的 各 个 章 节 本 书 的 主 要 内 容 包 括 两 个 方 面 : 一 是 研 究 并 设 计 实 现 了 一 个 集 成 化 的 医 学 影 像 处 理 与 分 析 算 法 平 台 MITK(Medical Imaging ToolKit) MITK 在 一 个 统 一 的 框 架 里 面 实 现 了 医 学 影 像 处 理 与 分 析 的 三 大 研 究 领 域 的 算 法, 包 括 医 学 影 像 分 割 医 学 影 像 配 准 以 及 三 维 可 视 化, 而 国 际 上 相 同 类 型 的 平 台 如 VTK 和 ITK 均 只 实 现 了 一 部 分 功 能, 并 且 它 们 还 具 有 完 全 不 同 的 框 架 和 风 格 另 外,MITK 是 专 门 针 对 医 学 影 像 这 一 特 定 领 域 的, 遵 循 小 而 精 的 原 则, 对 一 些 重 要 算 法 作 了 特 定 的 优 化, 支 持 新 的 CPU 指 令 集 SSE 的 优 化 以 及 新 的 显 卡 中 的 GPU 的 利 用 为 了 最 大 限 度 地 使 MITK 得 到 使 用, 其 在 Internet 上 面 向 国 际 免 费 发 行, 相 关 科 研 人 员 可 以 免 费 地 下 载 并 在 自 己 的 科 研 工 作 中 进 行 二 次 开 发 二 是 基 于 MITK 设 计 并 开 发 了 三 维 医 学 影 像 处 理 与 分 析 系 统 3DMed, 一 方 面 证 明 了 MITK 可 以 胜 任 现 实 世 界 当 中 医 学 影 像 领 域 复 杂 软 件 系 统 对 算 法 平 台 的 需 求, 另 一 方 面 的 目 的 是 为 相 关 科 研 人 员 和 普 通 用 户 提 供 一 个 易 于 使 用 的 软 件 工 具 目 前 3DMed 也 作 为 免 费 软 件 发 行, 如 果 MITK 和 3DMed 能 够 推 广 医 学 影 像 软 件 在 国 内 的 广 泛 使 用, 那 么 也 就 体 现 出 本 书 工 作 的 意 义 所 在 了 本 书 以 MITK 的 研 究 与 设 计 为 主 线 贯 穿 始 终, 在 软 件 设 计 框 图 的 绘 制 上, 始 8

16 1 绪 论 终 遵 循 UML( 统 一 建 模 语 言 )[28] 的 规 范 内 容 安 排 如 下 : 第 二 章 介 绍 MITK 的 总 体 框 架 的 设 计 ; 第 三 章 侧 重 介 绍 在 面 绘 制 算 法 研 究 方 面 的 工 作, 包 括 基 于 单 层 表 面 跟 踪 的 重 建 算 法 和 基 于 点 的 重 建 算 法, 并 且 给 出 了 面 绘 制 算 法 在 MITK 中 的 实 现 ; 第 四 章 介 绍 MITK 中 的 一 个 重 要 部 分, 即 体 绘 制 的 框 架 设 计 及 具 体 的 算 法 实 现 ; 第 五 章 给 出 了 在 三 维 人 机 交 互 方 面 的 一 些 探 索, 并 给 出 了 其 在 MITK 中 的 框 架 和 实 现 ; 第 六 七 章 分 别 给 出 了 不 同 的 分 割 算 法 和 配 准 算 法 在 MITK 中 的 实 现 ; 第 八 章 介 绍 了 DICOM 标 准 以 及 其 在 MITK 中 的 实 现, 第 九, 十 两 章 分 别 介 绍 应 用 MITK 开 发 项 目 和 MITK 的 扩 展 功 能, 以 便 读 者 可 以 方 便 的 使 用 MITK; 第 十 一 章 介 绍 基 于 MITK 算 法 平 台 的 三 维 医 学 影 像 处 理 与 分 析 实 用 软 件 系 统 3DMed 的 设 计 与 实 现 ; 第 十 二 章 介 绍 了 3DMed 中 的 Plugin, 这 样 读 者 也 可 以 将 自 己 的 算 法 用 plugin 开 发 出 来, 集 成 到 3dMed 中 附 录 A 介 绍 一 些 医 学 影 像 数 据 集 的 资 源, 方 便 读 者 用 来 测 试 自 己 算 法 附 录 B 介 绍 了 MITK 论 坛 的 情 况 参 考 文 献 1. 田 捷, 包 尚 联, 周 明 全. 医 学 影 像 处 理 与 分 析. 北 京 : 电 子 工 业 出 版 社, Insight Segmentation and Registration Toolkit, 3. Y. J. Zhang, J. J. Gerbrands. Transition region determination based thresholding. Pattern Recognition Letter, 1991, 12: P.Sahoo, C.Wilkins and J.Yeager, Threshold selection using Renyi's entropy. Pattern Recognition, 1997, 30(1): I.N. Manousakas, P.E. Undrill, G.G. Cameron, T.W. Redpath, Split-and-merge segmentation of magnetic resonance medical images: performance evaluation and extension to three dimensions. Computers and Biomedical Research, 1998, 31: M. Kass, A. Witkin, and D. Terzopoulos, Snakes - Active Contour Models, International Journal of Computer Vision, 1(4): , S. Osher and J. Sethian, Fronts propagating with curvature dependent speed, J. Comput. Phys., Vol.79, pp.12-49, J.A.Sethian, Fast marching methods, SIAM Rev., 41(1999), pp A. X. Falcao, J. K. Udupa, S. Samarasekera, Shoba Sharma, User-steered Image Segmentation Paradigms : Live Wire and Live Lane, Graphic models and Image Processing, 1998, 60: J. B. A. Maintz and M. A. Viergever, A survey of medical image registration, Medical Image Analysis, 2(1):1-36,

17 1 绪 论 11. W. Lorensen and H. Cline, Marching cubes: a high resolution 3D surface construction algorithm. ACM Computer Graphics, 21(4): pp , Gregory M. Nielson, On Marching Cubes, IEEE Transaction on Visualization and Computer Graphics, Vol. 9, No. 3, pp , G. T. Herman, H. K. Liu, Three-Dimensional Display of Human Organs form Computed Tomography, Computer Graphics & Image Processing, 1979, Vol. 9, pp M. Levoy, Display of surfaces from volume data, IEEE Transaction on Computer Graphics and Applications, 1988, 8(3): D. Laur and P. Hanrahan, Hierarchical Splatting: A Progressive Refinement Algorithm for Volume Rendering, ACM Computer Graphics, Proc. SIGGRAPH 93, 25(4): , July P. Lacroute and M. Levoy, Fast volume rendering using a shear-warp factorization of the viewing transformation, Proc. SIGGRAPH 94, pp , K. Engel, M. Kraus, and T. Ertl, High-quality pre-integrated volume rendering using hardware accelerated pixel shading, in Proc. Eurographics/SIGGRAPH Workshop on Graphics Hardware C. Resk-Salama, K. Engel, M. Bauer, G. Greiner, T. Ertl, Interactive Volume Rendering on Standard PC Graphics Hardware Using Multi-Textures and Multi-Stage-Rasterization,in Proc. Eurographics/SIGGRAPH Workshop on Graphics Hardware Wim Sweldens, Peter Schr oder, Digital Geometry Processing, Course Notes for SigGraph'2001, Los Angeles, California, Aug. 12, 何 晖 光, 数 字 几 何 的 研 究 及 其 在 医 学 可 视 化 中 的 应 用,[ 博 士 论 文 ], 北 京 : 中 科 院 自 动 化 所, Visualization Toolkit, Will Schroeder, Ken Martin, Bill Lorensen Schroeder, The Visualization Toolkit: An Object Oriented Approach to 3D Graphics 3rd Edition, Kitware, Inc. Publisher, William J. Schroeder, Kenneth M. Martin, William E. Lorensen, The Design and Implementation Of An Object-Oriented Toolkit For 3D Graphics And Visualization, Proc. Of IEEE Visualization ' William J. Schroeder, Lisa S. Avila, William Hoffman, Visualizing with VTK: A Tutorial, IEEE Transaction on Computer Graphics and Applications, Vol. 20, No. 5, pp , Ackerman, M. J., The Visible Human Project, Medicine Meets Virtual Reality II: Interactive Technology and Healthcare, pp Matthew H. Austern, Generic Programming and the Stl : Using and Extending the C++ 10

18 1 绪 论 Standard Template Library, Addison-Wesley Professional Computing Series, Luis Ibanez, Will Schroeder, Lydia Ng, Josh Cates. The ITK Software Guide: The Insight Segmentation and Registration Toolkit (version 1.4), Kitware, Inc. Publisher, Fowler M., Scott K. UML Distilled Second Edition: A Brief Guide to the Standard Object Modeling Language, Addison Wesley,

19 2 MITK 的 总 体 设 计 2 MITK 的 总 体 设 计 为 了 在 一 个 统 一 的 框 架 里 面 实 现 一 个 具 有 一 致 接 口 的 可 复 用 的 包 括 可 视 化 分 割 配 准 功 能 的 集 成 化 的 医 学 影 像 算 法 平 台,MITK 使 用 了 基 于 数 据 流 的 模 型 [1], 把 算 法 对 象 和 数 据 对 象 分 开 来 考 虑, 减 少 它 们 之 间 的 藕 合 性, 同 时 形 成 一 个 优 雅 的 算 法 的 计 算 框 架 另 外, 为 了 增 加 其 易 用 性,MITK 并 没 有 象 ITK 那 样 使 用 范 型 编 程 和 模 板, 而 是 采 用 的 传 统 的 面 向 对 象 的 设 计 方 法 [2] 另 外,MITK 的 设 计 还 吸 收 了 近 几 年 流 行 起 来 的 基 于 Design Pattern[3] 的 设 计 方 法 所 谓 Design Pattern, 就 是 软 件 工 业 界 在 长 期 的 编 写 大 型 复 杂 软 件 的 过 程 中 总 结 出 来 的 一 些 经 典 的 解 决 问 题 的 方 法, 其 中 每 个 都 是 行 之 有 效 的, 经 过 实 践 的 检 验 Design Pattern 结 合 了 面 向 对 象 设 计 与 分 析, 面 向 特 定 问 题 的 分 析 等 设 计 方 法, 可 以 很 大 程 度 地 提 高 软 件 开 发 的 质 量 和 效 率 虽 然 已 经 有 研 究 者 总 结 了 流 行 最 广 泛 的 Design Pattern, 但 是 这 些 都 是 面 向 通 用 领 域 的 比 较 成 功 的 设 计 软 件 的 方 法, 面 向 医 学 影 像 处 理 与 分 析 这 一 特 定 领 域 的 软 件 设 计 的 Design Pattern 还 没 有 得 到 充 分 的 重 视 本 书 通 过 对 MITK 的 研 究 与 设 计, 同 时 还 探 讨 了 Design Pattern 在 医 学 影 像 领 域 内 软 件 开 发 的 应 用 本 章 首 先 给 出 了 MITK 的 总 体 设 计 目 标, 然 后 介 绍 它 的 总 体 框 架, 从 数 据 模 型 和 算 法 模 型 两 个 方 面 给 出 说 明, 最 后 给 出 了 MITK 整 体 框 架 里 面 的 一 些 基 础 设 施, 便 于 后 续 章 节 的 描 述 2.1 MITK 的 设 计 目 标 对 于 软 件 设 计, 尤 其 是 特 定 领 域 内 的 复 杂 软 件 设 计, 必 须 事 先 有 一 个 非 常 明 确 的 设 计 目 标 MITK 从 一 开 始 设 计, 就 始 终 追 求 以 下 几 个 高 层 的 设 计 目 标 : 统 一 的 风 格 VTK 和 ITK 由 于 历 史 性 的 原 因, 使 用 了 不 同 的 编 程 风 格 VTK 在 1998 年 ANSI C++ 标 准 制 定 之 前 就 已 经 比 较 成 型, 所 以 使 用 的 是 传 统 的 Object-Oriented( 面 向 对 象 ) 的 设 计 和 开 发 方 法 ; 而 ITK 是 在 1999 年 才 开 始 开 发 的, 所 以 运 用 了 许 多 新 的 C++ 标 准 规 定 的 语 言 特 性, 以 及 Generic Programming( 范 型 编 程 ) 的 设 计 和 开 发 方 法 这 种 编 程 风 格 上 的 不 一 致, 给 VTK+ITK 的 使 用 者 带 来 了 很 大 的 不 方 12

20 2 MITK 的 总 体 设 计 便 而 MITK 使 用 统 一 的 面 向 对 象 的 设 计 方 法, 再 加 上 一 些 Design Patterns( 设 计 模 式 )[3] 的 使 用, 提 供 一 个 统 一 的 编 程 风 格 和 整 体 框 架 有 限 目 标 MITK 是 专 门 面 向 医 学 影 像 领 域 的, 只 关 注 于 这 一 特 定 领 域 内 的 算 法, 不 追 求 大 而 全, 只 追 求 少 而 精 例 如 MITK 中 可 视 化 算 法 只 包 括 规 则 数 据 场 ( 医 学 影 像 设 备 得 到 的 数 据 场 即 为 此 类 ) 的 支 持, 分 割 算 法 的 输 出 也 只 限 于 是 一 个 二 值 数 据 场 这 样 的 设 计 准 则 简 化 了 整 个 MITK, 使 得 其 保 持 在 一 个 中 等 的 规 模, 但 同 时 提 供 了 必 须 的 功 能, 包 括 主 流 的 可 视 化 分 割 和 配 准 算 法 的 实 现 可 移 植 性 为 了 使 MITK 能 够 得 到 最 广 泛 的 应 用, 可 移 植 性 是 非 常 重 要 的 一 个 环 节 整 个 MITK 的 代 码 全 部 使 用 ANSI C++ 编 写, 没 有 使 用 任 何 编 译 器 提 供 的 特 殊 关 键 字 或 者 特 殊 函 数, 并 且 尽 量 降 低 平 台 相 关 的 代 码 量 在 整 个 MITK 中, 与 平 台 相 关 的 部 分 就 是 与 窗 口 系 统 打 交 道 的 部 分, 此 处 针 对 不 同 的 操 作 系 统 写 了 不 同 的 代 码, 目 前 支 持 Windows 系 列 操 作 系 统 Unix Linux 等 而 MITK 目 前 可 以 在 多 数 主 流 的 C++ 编 译 器 下 编 译 通 过, 包 括 对 模 板 支 持 不 完 善 的 编 译 器 代 码 优 化 因 为 医 学 影 像 处 理 与 分 析 算 法 中 很 多 算 法 计 算 量 大, 尤 其 是 可 视 化 算 法, 对 实 时 性 要 求 很 高, 这 些 就 需 要 对 代 码 进 行 优 化 因 为 MITK 的 规 模 保 持 在 中 等, 这 就 使 得 对 一 些 关 键 算 法 进 行 优 化 成 为 可 能 MITK 支 持 对 CPU 的 扩 展 指 令 集 的 使 用, 比 如 Intel 的 MMX SSE 指 令 集, 为 了 不 至 于 违 背 可 移 植 性 目 标,MITK 中 在 使 用 SSE 等 指 令 集 时, 并 没 有 直 接 使 用 汇 编 语 言, 而 是 使 用 了 编 译 器 提 供 的 Intrinsics 指 令, 目 前 MITK 当 中 实 现 了 SSE 加 速 的 矩 阵 和 矢 量 运 算 双 线 性 和 三 线 性 插 值 计 算 等 ; 另 外 MITK 还 支 持 对 目 前 主 流 显 卡 中 GPU 的 编 程, 实 现 了 使 用 纹 理 映 射 进 行 Volume Rendering( 体 绘 制 ) 的 加 速 算 法 [4][5] 2.2 MITK 的 整 体 计 算 框 架 医 学 影 像 处 理 与 分 析 技 术 包 含 可 视 化 分 割 配 准 三 大 类 算 法, 每 一 类 下 面 又 都 有 很 多 不 同 的 方 法, 医 学 影 像 数 据 本 身 也 包 含 多 维 ( 一 维 二 维 三 维 ) 多 源 (CT MRI 等 ) 多 态 ( 以 像 素 矩 阵 形 式 表 达 的 图 像 信 息 以 像 素 集 合 形 式 13

21 2 MITK 的 总 体 设 计 表 达 的 目 标 信 息 以 及 以 几 何 形 状 形 式 表 达 的 知 识 信 息 ) 的 特 点, 这 些 都 决 定 了 将 其 整 合 进 一 个 统 一 的 框 架 之 内 是 一 个 比 较 复 杂 的 过 程, 必 须 经 过 抽 象 建 模, 才 能 得 到 一 个 比 较 灵 活 可 用 的 整 体 计 算 框 架 有 了 计 算 框 架 以 后, 还 可 以 在 相 同 的 条 件 之 下 比 较 同 一 种 类 不 同 算 法 的 性 能 效 果, 进 行 算 法 的 比 较 ; 另 外 还 可 以 进 行 算 法 的 评 价, 比 如 对 分 割 算 法 配 准 算 法 的 准 确 性 进 行 评 价 基 于 数 据 流 模 型 的 整 体 框 架 正 如 前 面 提 到 的 一 样,MITK 的 计 算 框 架 采 用 基 于 数 据 流 的 模 型, 以 数 据 处 理 为 中 心, 将 算 法 和 数 据 对 象 分 开 考 虑, 这 种 模 型 很 适 合 那 些 牵 涉 大 量 不 同 的 算 法 需 要 处 理 不 同 类 型 数 据 的 领 域 的 应 用 在 MITK 的 数 据 流 模 型 中, 数 据 和 算 法 均 使 用 对 象 表 示 ; 一 个 算 法 被 抽 象 成 一 个 滤 波 器 (Filter), 它 接 受 一 个 输 入, 生 成 一 个 输 出, 其 中 输 入 和 输 出 均 为 数 据 对 象 (Data), 一 个 算 法 的 输 出 可 以 作 为 另 外 一 个 算 法 的 输 入 通 过 这 样 的 模 型, 一 连 串 的 算 法 可 以 被 串 成 一 个 流 水 线, 组 成 统 一 的 计 算 框 架, 如 图 2-1 所 示 图 2-1 MITK 的 计 算 框 架 在 图 中,Data 表 示 抽 象 的 数 据 对 象,Source Filter 和 Target 分 别 表 示 三 种 不 同 的 抽 象 算 法 对 象, 它 们 的 意 义 分 别 如 下 所 示 : Data: Data 是 对 医 学 影 像 领 域 内 要 处 理 的 数 据 所 进 行 的 抽 象 对 于 医 学 影 像 处 理 与 分 析 系 统 来 说, 要 能 够 处 理 多 种 不 同 的 数 据, 在 MITK 中 通 过 Data 的 各 个 具 体 的 子 类 来 描 述 不 同 的 数 据 对 象, 代 表 了 数 据 流 模 型 中 最 重 要 的 数 据 对 象 在 下 一 小 节 将 会 具 体 讲 述 MITK 中 的 数 据 模 型 Source: Source 是 算 法 类 的 一 种, 但 是 它 只 有 输 出, 没 有 输 入, 代 表 一 个 流 水 线 的 起 源 Source 的 作 用 是 负 责 生 成 整 个 流 水 线 的 起 始 数 据, 比 如 从 磁 盘 上 14

22 2 MITK 的 总 体 设 计 读 文 件, 或 者 用 某 些 算 法 生 成 数 据 Filter: Filter 是 算 法 类 的 一 种, 它 负 责 对 数 据 对 象 进 行 处 理, 代 表 各 种 各 样 的 算 法 Filter 有 一 个 输 入, 一 个 输 出, 为 了 概 念 上 简 单,MITK 中 不 支 持 多 输 入 多 输 出 的 Filter, 而 是 通 过 Filter 的 具 体 子 类 提 供 的 辅 助 函 数 来 实 现 在 小 节 中 将 具 体 讲 述 MITK 中 的 算 法 模 型 Target:Target 是 算 法 类 的 一 种, 顾 名 思 义, 它 代 表 整 个 流 水 线 数 据 的 终 点 Target 只 有 输 入, 没 有 输 出, 它 的 作 用 是 将 最 后 的 数 据 放 在 一 个 合 适 的 位 置, 终 止 流 水 线 的 执 行 比 如 将 得 到 的 结 果 数 据 保 存 至 磁 盘, 或 者 将 得 到 的 结 果 在 屏 幕 上 显 示 出 来 有 了 这 些 高 层 的 概 念 以 后, 就 可 以 很 容 易 地 将 这 些 组 件 联 系 在 一 块, 组 成 一 个 实 用 的 系 统 如 图 2-1 所 示, 整 个 流 水 线 从 一 个 Source 开 始, 经 过 中 间 n 个 Filter 的 处 理, 最 终 终 结 于 Target 这 种 抽 象 关 系 足 以 描 述 医 学 影 像 处 理 与 分 析 这 类 以 数 据 处 理 为 中 心 的 应 用 程 序 的 需 求, 并 且 在 概 念 上 非 常 简 洁 清 晰, 可 以 提 供 一 个 统 一 的 模 型 来 设 计 MITK 的 整 个 计 算 框 架 数 据 模 型 数 据 表 达 是 数 据 流 模 型 中 的 一 个 核 心 的 内 容, 数 据 对 象 起 着 连 接 算 法 流 水 线 的 重 要 作 用 考 虑 到 MITK 的 设 计 目 标 之 一 是 有 限 目 标, 只 关 注 于 医 学 影 像 这 个 特 定 的 领 域, 此 处 就 简 化 了 数 据 模 型 的 建 立 通 过 对 医 学 影 像 数 据 进 行 仔 细 的 分 析 以 后,MITK 中 的 数 据 对 象 (Data) 可 以 被 具 体 化 为 Volume 和 Mesh 两 种 不 同 的 具 体 数 据 对 象,Data 的 类 继 承 关 系 如 图 2-2 所 示 : 图 2-2 MITK 的 数 据 模 型 在 图 中,Volume 用 来 表 达 一 个 医 学 影 像 数 据 集, 提 供 一 个 多 维 ( 包 括 一 15

23 2 MITK 的 总 体 设 计 二 三 维 ) 多 模 态 (CT MRI 等 ) 的 规 则 数 据 场 的 抽 象 Volume 提 供 了 丰 富 的 接 口 来 给 算 法 对 象 使 用, 图 中 给 出 了 一 部 分 最 常 用 的 函 数 接 口, 这 些 接 口 可 以 使 得 其 它 的 对 象 可 以 很 方 便 地 访 问 其 内 部 的 实 际 数 据 Volume 是 MITK 中 的 核 心 对 象 之 一 Mesh 用 来 表 达 一 个 几 何 数 据, 尤 其 是 以 三 角 面 片 网 格 形 式 表 达 的 几 何 模 型 Mesh 内 部 的 结 构 基 于 半 边 数 据 结 构 [6], 它 提 供 了 对 一 维 线 段 二 维 平 面 图 形 三 维 三 角 网 格 以 及 通 用 多 边 形 的 支 持, 提 供 了 丰 富 的 接 口 来 给 相 关 的 算 法 对 象 使 用, 上 图 中 给 出 了 一 部 分 最 常 用 的 函 数 接 口 不 同 于 Volume,Mesh 并 不 对 应 于 医 学 影 像 设 备 所 直 接 采 集 得 到 的 数 据, 而 是 对 医 学 影 像 数 据 集 处 理 后 得 到 的 结 果 所 依 赖 的 表 达 形 式, 它 是 可 视 化 算 法 中 面 绘 制 和 某 些 分 割 算 法 所 处 理 的 对 象, 是 MITK 中 的 核 心 对 象 之 一 算 法 模 型 有 了 一 个 设 计 良 好 的 数 据 模 型, 下 一 步 就 是 算 法 模 型 的 抽 象 了 因 为 Source 和 Target 只 是 特 殊 目 的 的 算 法 对 象, 真 正 的 算 法 是 由 Filter 对 象 来 代 表 的 按 照 一 个 Filter 的 输 入 和 输 出 数 据 对 象 的 类 型, 它 可 以 被 具 体 化 为 四 种 不 同 的 算 法 种 类, Filter 的 类 继 承 关 系 如 图 2-3 所 示 : 图 2-3 MITK 的 算 法 模 型 从 图 中 可 以 看 出 Filter 被 具 体 化 为 四 种 不 同 的 种 类 :VolumeToVolumeFilter 指 的 是 输 入 数 据 和 输 出 数 据 都 为 Volume 数 据 对 象 的 算 法, 在 其 下 可 以 更 细 分 出 图 像 处 理 算 法 图 像 配 准 算 法 一 部 分 图 像 分 割 算 法 等, 在 第 六 七 章 中 实 现 的 算 法 就 全 部 是 从 VolumeToVolumeFilter 继 承 下 来 的 ;VolumeToMeshFilter 指 的 是 输 入 数 据 为 Volume 数 据 对 象, 而 输 出 数 据 为 Mesh 数 据 对 象 的 算 法, 包 括 三 维 可 视 化 中 的 面 重 建 算 法 一 部 分 图 像 分 割 算 法, 在 第 三 章 中 实 现 的 算 法 就 是 16

24 2 MITK 的 总 体 设 计 从 VolumeToMeshFilter 继 承 下 来 的 ;MeshToMeshFilter 指 的 是 输 入 数 据 为 Mesh 数 据 对 象, 而 输 出 数 据 为 Mesh 数 据 对 象 的 算 法, 包 括 三 维 可 视 化 中 的 面 片 网 格 化 简 平 滑 细 分 等 数 字 几 何 处 理 算 法 ;MeshToVolumeFilter 指 的 是 输 入 数 据 为 Mesh 数 据 对 象, 而 输 出 数 据 为 Volume 数 据 对 象 的 算 法, 包 括 三 维 可 视 化 中 的 基 于 距 离 场 的 算 法 隐 式 曲 面 算 法 等 这 四 种 Filter 也 只 是 一 种 高 层 的 抽 象, 其 中 每 一 个 种 类 下 面 都 包 含 很 多 具 体 的 算 法, 但 是 这 些 具 体 的 算 法 的 实 现 将 只 能 在 高 层 的 模 型 规 定 的 框 架 下 进 行 通 过 这 样 的 算 法 模 型,MITK 不 仅 为 可 视 化 分 割 配 准 等 算 法 提 供 了 一 个 框 架, 而 且 可 以 很 方 便 地 往 里 面 扩 充 新 的 算 法, 而 不 需 要 改 变 上 层 的 接 口 除 了 Filter 所 规 定 的 四 种 不 同 的 算 法 大 类 以 外, 在 MITK 里 面 还 有 一 种 特 殊 的 算 法, 就 是 体 绘 制 (Volume Rendering) 算 法, 它 的 输 入 是 一 个 Volume, 通 过 算 法 直 接 将 整 个 Volume 绘 制 到 最 终 的 图 像 中, 在 屏 幕 的 窗 口 ( 属 于 一 个 Target) 里 面 显 示 在 第 四 章 中 将 详 细 介 绍 MITK 中 的 体 绘 制 算 法 的 框 架 2.3 MITK 的 基 础 设 施 搭 建 遵 循 面 向 对 象 设 计 的 准 则, 整 个 MITK 的 类 层 次 结 构 从 mitkobject 开 始 开 枝 散 叶, 另 外,MITK 框 架 里 面 的 类 的 命 名 遵 循 一 定 的 原 则, 每 个 类 都 以 小 写 的 mitk 为 前 缀, 后 面 再 跟 上 自 己 这 个 类 的 名 字, 每 个 单 层 的 第 一 个 字 母 大 写, 例 如 mitkvolumetovolumefilter 在 下 面 正 文 里 面 的 描 述 中, 为 了 方 便 起 见, 在 不 引 起 混 淆 的 情 况 下, 通 常 把 类 名 字 前 面 的 mitk 前 缀 省 掉 Object 提 供 的 服 务 为 了 给 整 个 MITK 框 架 中 的 类 提 供 基 础 服 务, 在 Object 里 面 实 现 了 五 大 基 础 设 施, 分 别 是 RTTI(Run-Time Type Information, 运 行 时 信 息 ) 调 试 信 息 对 象 引 用 计 数 (Reference Counting) 智 能 指 针 (Smart Pointer) 观 察 者 (Observer), 下 面 分 别 给 予 介 绍 (1) RTTI( 运 行 时 信 息 ) 为 了 提 供 更 高 的 效 率,MITK 中 没 有 使 用 ANSI C++ 语 言 所 提 供 的 RTTI 特 性, 而 是 自 己 实 现 了 一 套 RTTI 的 机 制, 提 供 对 象 在 运 行 时 查 询 自 己 的 类 型 信 息 Object 里 面 与 RTTI 有 关 的 函 数 如 图 2-4 所 示, 其 中 GetClassname 函 数 以 字 符 串 的 17

25 2 MITK 的 总 体 设 计 形 式 返 回 当 前 类 的 名 字, 比 如 mitkobject 类 返 回 的 就 是 mitkobject ;IsTypeOf 和 IsA 函 数 判 断 当 前 的 类 是 否 是 与 typename 同 种 类 型 的 类 或 者 是 其 子 类, 两 者 的 差 异 在 于 IsTypeOf 是 静 态 函 数, 可 以 在 没 有 对 象 生 成 的 时 候 调 用, 而 IsA 是 个 成 员 函 数, 只 能 在 对 象 存 在 的 时 候 被 调 用 ;SafeDownCast 将 object 安 全 地 转 换 为 自 身 的 类 型 为 了 实 现 这 些 基 础 服 务,Object 要 求 它 的 每 个 子 类 都 必 须 实 现 GetClassname 和 IsA 这 两 个 虚 函 数, 以 及 IsTypeOf 和 SafeDownCast 这 两 个 静 态 函 数 为 了 减 少 子 类 的 工 作 量,MITK 里 面 用 C++ 的 宏 作 为 代 码 生 成 器 来 自 动 为 子 类 生 成 这 些 函 数, 这 个 宏 的 代 码 如 下 : #define MITK_TYPE(thisClass,superclass) \ virtual const char *GetClassname() const return #thisclass; \ static int IsTypeOf(const char *type) \ \ if (!strcmp(#thisclass,type) ) \ \ return 1; \ \ return superclass::istypeof(type); \ \ virtual int IsA(const char *type) \ \ return this->thisclass::istypeof(type); \ \ static thisclass* SafeDownCast(mitkObject *o) \ \ if ( o && o->isa(#thisclass) ) \ \ return static_cast<thisclass *>(o); \ \ return NULL;\ 在 这 个 宏 中,thisClass 是 类 自 身 的 类 名, 而 superclass 是 父 类 的 类 名 有 了 这 个 宏, 在 Object 的 子 类 里 面 就 只 需 写 下 这 个 宏 的 名 字 就 行 了, 省 去 很 多 烦 琐 的 工 作 比 如 DataObject 是 Object 的 一 个 子 类, 那 么 在 DataObject 的 声 明 里 面 18

26 2 MITK 的 总 体 设 计 就 只 用 写 下 下 面 的 代 码 即 可 : MITK_TYPE(mitkDataObject,mitkObject) 图 2-4 Object 提 供 的 RTTI 服 务 (2) 调 试 信 息 Object 里 面 还 为 算 法 提 供 了 调 试 信 息 的 支 持, 与 调 试 信 息 有 关 的 函 数 如 图 2-5 所 示, 其 中 SetDebug 函 数 用 来 设 置 是 否 打 开 调 试 信 息 支 持 ; 而 GetDebug 函 数 用 来 获 得 当 前 调 试 信 息 支 持 是 否 打 开 ;DebugOn 函 数 用 来 打 开 调 试 信 息 支 持 ; 而 DebugOff 函 数 用 来 关 闭 调 试 信 息 支 持 ;Print 函 数 用 来 将 对 象 内 部 的 状 态 输 送 到 os 指 定 的 设 备 上 显 示, 其 内 部 要 调 用 虚 函 数 PrintSelf, 将 实 际 调 试 信 息 的 输 出 工 作 委 托 给 PrintSelf 函 数 来 实 现, 所 以 Object 的 每 个 子 类 必 须 实 现 虚 函 数 PrintSelf 除 了 提 供 这 些 接 口 函 数 以 外,MITK 还 定 义 了 一 些 宏 来 输 出 调 试 信 息 或 者 出 错 信 息, 这 些 宏 的 定 义 如 下 : #define mitkgenericmessage(x) \ char *mitkmsgbuff; \ ostrstream mitkmsg; \ mitkmsg << x << "\n" << ends; \ mitkmsgbuff = mitkmsg.str(); \ mitkdisplaymessage(mitkmsgbuff);\ mitkmsg.rdbuf()->freeze(0); #define mitkdebugmessage(x) \ if (this->m_debug ) \ char *mitkmsgbuff; \ ostrstream mitkmsg; \ 19

27 2 MITK 的 总 体 设 计 mitkmsg << "Debug: In " FILE ", line " << LINE << "\n" << this->getclassname() << " (" << this << "): " << x << "\n\n" << ends; \ mitkmsgbuff = mitkmsg.str(); \ mitkdisplaymessage(mitkmsgbuff);\ mitkmsg.rdbuf()->freeze(0); #define mitkwarningmessage(x) \ char *mitkmsgbuff; \ ostrstream mitkmsg; \ mitkmsg << "Warning: In " FILE ", line " << LINE << "\n" << this->getclassname() << " (" << this << "): " << x << "\n\n" << ends; \ mitkmsgbuff = mitkmsg.str(); \ mitkdisplaymessage(mitkmsgbuff);\ mitkmsg.rdbuf()->freeze(0); #define mitkerrormessage(x) \ char *mitkmsgbuff; \ ostrstream mitkmsg; \ mitkmsg << "ERROR: In " FILE ", line " << LINE << "\n" << this->getclassname() << " (" << this << "): " << x << "\n\n" << ends; \ mitkmsgbuff = mitkmsg.str(); \ mitkdisplaymessage(mitkmsgbuff);\ mitkmsg.rdbuf()->freeze(0); mitkobject::breakonerror(); 其 中 mitkgenericmessage 是 用 来 输 出 通 用 的 消 息, 其 可 以 在 任 意 位 置 被 调 用 ; 而 mitkdebugmessage,mitkwarningmessage 和 mitkerrormessage 都 只 能 在 Object 及 其 子 类 的 成 员 函 数 里 面 被 调 用, 分 别 用 来 输 出 调 试 信 息, 警 告 信 息 和 严 重 错 误 信 息 它 们 和 Object 里 面 的 相 关 函 数 一 起, 提 供 了 MITK 里 面 提 供 调 试 信 息 的 基 础 服 务 20

28 2 MITK 的 总 体 设 计 图 2-5 Object 提 供 的 调 试 信 息 服 务 (3) Reference Counting( 引 用 计 数 ) 引 用 计 数 是 实 现 内 存 管 理 的 一 种 手 段, 它 的 目 的 是 将 内 存 中 不 再 被 其 它 对 象 引 用 的 对 象 给 自 动 释 放 掉, 从 而 达 到 节 省 内 存 并 保 证 内 存 不 产 生 泄 漏 Object 里 面 与 引 用 计 数 有 关 的 函 数 如 图 2-6 所 示, 其 中 AddReference 函 数 将 本 身 被 其 它 对 象 引 用 的 次 数 加 一 ;RemoveReference 函 数 将 本 身 被 其 它 对 象 引 用 的 次 数 减 一 ;GetReferenceCount 函 数 返 回 本 身 被 其 它 对 象 引 用 的 次 数 ;Delete 函 数 将 本 身 从 内 存 中 删 除, 但 是 前 提 是 本 身 被 其 它 对 象 引 用 的 次 数 小 于 或 者 等 于 零 为 了 实 现 引 用 计 数,MITK 还 使 用 了 设 计 模 式 来 限 制 所 有 从 Object 继 承 下 来 的 子 类 都 必 须 在 堆 (Heap) 上 来 分 配 内 存, 而 不 能 从 栈 (Stack) 上 来 分 配 内 存 为 了 达 到 这 个 目 的,Object 和 所 有 从 Object 继 承 下 来 的 类 的 析 构 函 数 都 必 须 是 Protected 的 在 删 除 一 个 从 Object 继 承 下 来 的 对 象 时, 必 须 调 用 其 Delete 函 数, 而 不 能 直 接 使 用 delete 操 作 符 图 2-6 Object 提 供 的 引 用 计 数 服 务 21

29 2 MITK 的 总 体 设 计 (4) Smart Pointer( 智 能 指 针 ) 智 能 指 针 和 引 用 计 数 合 起 来 构 成 了 MITK 中 内 存 管 理 的 基 础, 所 谓 智 能 指 针, 就 是 其 行 为 模 仿 普 通 的 指 针, 但 是 可 以 通 过 运 算 符 重 载 来 进 行 一 些 必 要 的 操 作, 从 而 可 以 减 少 不 必 要 的 代 码 在 MITK 中 提 供 了 一 个 模 板 类 SmartPointer 用 来 实 现 智 能 指 针, 它 的 内 部 维 护 着 一 个 成 员 变 量 realptr, 可 以 被 具 体 的 模 板 参 数 T 来 具 体 化, 这 里 要 求 类 型 T 必 须 是 Object 的 子 类, 其 提 供 的 主 要 功 能 请 参 看 图 2-7 为 了 实 现 普 通 的 指 针 行 为, 它 重 载 了 -> 和 * 运 算 符, 分 别 返 回 实 际 指 针 的 地 址 和 引 用 ; 为 了 实 现 其 智 能 的 行 为, 它 重 载 了 = 运 算 符, 用 于 在 把 一 个 Object 的 子 类 的 指 针 赋 值 给 智 能 指 针 时, 来 自 动 地 进 行 引 用 计 数 的 工 作, 其 实 现 代 码 如 下 : template<class T> inline mitksmartpointer<t>& mitksmartpointer<t>::operator=(t* realptr) if(realptr == NULL) return *this; if(realptr == m_pointee) return *this; if(m_pointee) m_pointee->removereference(); m_pointee = realptr; m_pointee->addreference(); return *this; 图 2-7 MITK 中 的 智 能 指 针 (5) Observer( 观 察 者 ) MITK 是 一 个 底 层 的 算 法 库, 但 是 在 基 于 MITK 开 发 实 际 应 用 程 序 时, 有 时 22

30 2 MITK 的 总 体 设 计 必 须 知 道 内 部 算 法 的 状 态, 比 如 算 法 执 行 的 进 度 等 信 息 为 了 达 到 MITK 底 层 算 法 库 和 上 层 的 应 用 程 序 之 间 的 通 信,MITK 里 面 实 现 了 Observer 这 一 设 计 模 式, 其 在 Object 里 面 的 函 数 如 图 2-8 所 示,AddObserver 将 一 个 Observer 插 入 到 内 部 维 护 的 一 个 队 列 中 ;RemoveObserver 将 一 个 指 定 的 Observer 从 内 部 的 队 列 中 删 除 ;RemoveAllObservers 将 内 部 的 队 列 清 空 而 MITK 中 也 单 独 定 义 了 Observer 这 个 类 层 次, 所 有 从 Observer 继 承 的 子 类 必 须 实 现 其 虚 函 数 Update, 从 而 更 新 界 面 元 素 一 个 Observer 就 是 一 个 单 独 的 对 象, 在 外 面 观 察 一 个 MITK 对 象 的 内 部 状 态, 并 且 在 必 要 的 时 候 被 更 新 图 2-8 Object 中 提 供 的 Observer 设 计 模 式 实 现 内 存 管 理 因 为 MITK 的 结 构 比 较 复 杂, 所 以 实 现 一 个 有 效 的 内 存 管 理 方 案 是 非 常 必 要 的 上 面 介 绍 的 引 用 计 数 和 智 能 指 针 的 联 合 使 用, 形 成 了 MITK 中 的 第 一 层 内 存 管 理, 用 来 保 证 不 出 现 内 存 泄 漏 另 外,MITK 中 实 现 了 一 个 简 单 的 垃 圾 回 收 (Garbage Collection) 机 制, 用 于 在 程 序 退 出 之 前 将 所 有 可 能 泄 漏 的 内 存 释 放 掉, 此 功 能 是 在 GarbageCollection 类 里 面 实 现 的, 它 的 接 口 函 数 如 图 2-9 所 示, AddObject 函 数 将 一 个 MITK 的 对 象 的 指 针 加 入 到 内 部 维 护 的 一 张 列 表 中, 而 RemoveObject 函 数 将 指 定 的 对 象 从 内 部 的 列 表 中 删 除 由 于 GarbageCollection 在 整 个 系 统 中 只 能 存 在 一 份 实 例, 所 以 MITK 中 使 用 了 设 计 模 式 中 的 Singleton 来 达 到 这 一 目 的 有 了 GarbageCollection 类 提 供 的 基 本 功 能 以 后,Object 里 面 也 必 须 提 供 相 应 的 配 合 才 能 实 现 垃 圾 回 收 机 制 在 Object 的 构 造 函 数 里 面, 通 过 GetGarbageCollector 函 数 来 得 到 系 统 里 面 唯 一 的 GarbageCollection 实 例, 并 且 将 自 身 加 入 到 GarbageCollection 的 列 表 里 面, 代 码 如 下 : 23

31 2 MITK 的 总 体 设 计 GetGarbageCollector()->AddObject(this); 在 Object 的 析 构 函 数 里 面, 也 同 样 通 过 GetGarbageCollector 函 数 来 得 到 系 统 里 面 唯 一 的 GarbageCollection 实 例, 并 且 通 过 RemoveObject 将 自 身 从 GarbageCollection 的 列 表 里 面 删 除, 代 码 如 下 : GetGarbageCollector()->RemoveObject(this); 在 整 个 系 统 退 出 的 时 候, 系 统 里 面 唯 一 的 GarbageCollection 实 例 的 析 构 函 数 被 调 用, 检 查 自 己 维 护 的 列 表 中 是 否 为 空, 如 果 不 为 空, 则 说 明 有 内 存 泄 漏, 同 时 考 虑 到 引 用 计 数 这 一 服 务, 按 照 一 定 的 规 则 将 泄 漏 的 内 存 清 空, 代 码 如 下 所 示 : if(m_objectcollection->count() <= 0) m_objectcollection->delete(); return; mitkobject *aobject; while(m_objectcollection->count() > 0) for(m_objectcollection->inittraversal(); aobject = m_objectcollection->getnextitem(); ) if(aobject->getreferencecount() <= 0) aobject->delete(); break; 24

32 2 MITK 的 总 体 设 计 m_objectcollection->clear(); m_objectcollection->delete(); 图 2-9 MITK 中 的 垃 圾 回 收 接 口 跨 平 台 的 实 现 MITK 的 所 有 代 码 均 使 用 符 合 ANSI C++ 标 准 的 特 性, 这 保 证 了 代 码 的 可 移 植 性 但 是 对 一 些 操 作 系 统 相 关 的 代 码, 比 如 窗 口 的 事 件 处 理 虚 拟 内 存 管 理 等, 必 须 对 每 一 个 操 作 系 统 写 一 套 代 码 为 了 能 够 透 明 地 封 装 这 些 操 作 系 统 相 关 的 代 码, 得 到 一 个 优 雅 的 解 决 方 案,MITK 中 再 次 使 用 了 一 种 设 计 模 式, 名 字 为 桥 (Bridge), 下 面 以 View 这 一 对 象 为 例 进 行 介 绍 在 MITK 中,View 这 一 对 象 是 唯 一 跟 图 形 用 户 界 面 相 关 的 部 分, 给 用 户 提 供 了 一 个 用 来 显 示 图 像 或 者 三 维 图 形 的 窗 口, 这 也 就 必 然 导 致 它 跟 具 体 的 操 作 系 统 相 关 为 了 使 操 作 系 统 相 关 的 代 码 相 对 独 立, 并 且 添 加 对 新 的 操 作 系 统 的 支 持 的 时 候 也 不 影 响 到 客 户 端 的 代 码,View 这 一 部 分 的 框 架 结 构 图 如 图 2-10 所 示 25

33 2 MITK 的 总 体 设 计 图 2-10 MITK 中 View 的 结 构 从 图 中 可 以 看 出,View 里 面 维 护 着 Implementor 基 类 的 指 针, 并 且 View 把 所 有 与 操 作 系 统 相 关 的 代 码 都 委 托 给 Implementor 来 实 现,Implementor 通 过 其 子 类 来 实 现 具 体 的 代 码 通 过 这 种 结 构, 客 户 端 只 知 道 有 View, 而 不 知 道 有 Implementor 的 存 在, 因 此 降 低 了 藕 合 ; 并 且 要 添 加 对 一 个 新 的 操 作 系 统 的 支 持 的 时 候, 只 需 要 在 Implementor 分 支 下 面 再 增 加 对 应 的 子 类 即 可, 无 需 更 改 客 户 端 的 代 码 SSE 加 速 的 实 现 Intel 在 其 奔 腾 3 以 后 的 CPU 中 增 加 了 SSE 扩 展 指 令 集, 用 以 提 高 三 维 程 序 以 及 多 媒 体 程 序 的 性 能 因 为 MITK 中 三 维 可 视 化 是 一 个 比 较 重 要 的 部 分, 对 性 能 要 求 也 比 较 高, 因 此 内 部 提 供 了 对 SSE 的 支 持, 并 且 已 经 实 现 了 一 部 分 算 法 的 SSE 优 化 加 速 实 现 SSE 指 令 集 的 支 持 有 一 些 问 题 必 须 考 虑, 因 为 传 统 上 是 使 用 汇 编 语 言 对 SSE 指 令 集 进 行 编 程, 这 显 然 将 会 违 背 MITK 的 可 移 植 性 这 一 设 计 目 标 ; 另 外, 并 不 是 所 有 的 CPU 都 支 持 SSE 指 令 集, 因 此 必 须 有 一 种 手 段 能 在 运 行 时 检 测 当 前 CPU 信 息, 并 动 态 决 定 使 用 SSE 加 速 版 本 还 是 使 用 普 通 版 本 在 MITK 中, 对 第 一 个 问 题 的 解 决 方 案 是 使 用 编 译 器 提 供 的 Intrinsics 去 对 SSE 指 令 集 进 行 编 程, 这 样 虽 然 没 有 使 用 汇 编 语 言 的 效 率 高, 但 是 目 前 的 主 流 编 译 器 ( 包 括 Visual C Processor Pack,Visual C++ 7.0,gcc,Intel Compiler 等 ) 都 提 供 了 对 Intrinsics 的 支 持, 因 此 可 移 植 性 得 到 了 保 证 ; 对 第 二 个 问 题 的 解 决 方 案 是 提 供 了 两 套 分 离 的 动 态 链 接 库, 一 套 是 包 含 SSE 加 速 算 法 26

34 2 MITK 的 总 体 设 计 的, 一 套 是 非 SSE 加 速 算 法 的, 由 客 户 端 在 使 用 时 进 行 判 断 并 动 态 加 载 2.4 小 结 本 章 的 第 一 部 分 介 绍 了 MITK 的 设 计 目 标, 其 目 的 是 为 了 给 医 学 影 像 领 域 的 研 究 者 提 供 一 套 具 有 一 致 接 口 的, 可 复 用 的, 结 合 了 VTK 和 ITK 中 可 视 化 分 割 配 准 等 功 能 的 开 发 工 具 包 本 章 的 第 二 部 分 介 绍 了 MITK 的 整 体 计 算 框 架, 其 中 包 括 基 于 数 据 流 模 型 的 整 体 框 架, 数 据 模 型 和 算 法 模 型 第 三 部 分 介 绍 的 是 MITK 的 基 础 设 施 搭 建, 包 括 基 类 Object 所 提 供 的 服 务 以 及 相 关 信 息, 内 存 管 理, 跨 平 台 实 现 和 SSE 加 速 的 实 现 目 前 MITK 的 整 体 框 架 已 经 基 本 稳 定, 在 保 持 MITK 的 整 体 框 架 的 稳 定 性 的 基 础 上, 下 一 步 可 以 不 断 地 完 善 和 添 加 MITK 的 各 种 算 法, 使 其 越 来 越 丰 富, 越 来 越 实 用 接 下 来 的 几 章 将 会 介 绍 具 体 的 算 法 在 MITK 中 的 实 现 参 考 文 献 1. J. Rumbaugh, M. Blaha, W. Premerlani, et al. Object-Oriented Modeling and Design. Prentice-Hall, Meyer, B. Object-Oriented Software Construction. Prentice Hall, Erich Gamma, Richard Helm, Ralph Johnson, et al. Design Patterns, Elements of Reusable Object-Oriented Software. Pearson Education Publisher, K. Engel, M. Kraus, and T. Ertl, High-quality pre-integrated volume rendering using hardware accelerated pixel shading, in Proc. Eurographics/SIGGRAPH Workshop on Graphics Hardware C. Resk-Salama, K. Engel, M. Bauer, G. Greiner, T. Ertl, Interactive Volume Rendering on Standard PC Graphics Hardware Using Multi-Textures and Multi-Stage-Rasterization,in Proc. Eurographics/SIGGRAPH Workshop on Graphics Hardware S. Campagna, L. Kobbelt, H. P. Seidel. Directed Edges - A Scalable Representation For Triangle Meshes. ACM Journal of Graphics Tools 3 (4), 1998, pp

35 3 面 绘 制 (Surface Rendering) 的 框 架 与 实 现 面 绘 制 是 医 学 图 像 三 维 可 视 化 的 重 要 手 段 之 一, 它 通 过 对 一 系 列 的 二 维 图 像 进 行 边 界 识 别 等 分 割 处 理, 重 新 还 原 出 被 检 物 体 的 三 维 模 型, 并 以 表 面 的 方 式 显 示 出 来, 从 而 为 用 户 提 供 具 有 较 强 真 实 感 的 三 维 医 学 图 像, 便 于 医 生 从 多 角 度 多 层 次 进 行 观 察 和 分 析, 并 且 能 够 使 医 生 有 效 地 参 与 数 据 的 处 理 分 析 过 程, 在 辅 助 医 生 诊 断 手 术 仿 真 引 导 治 疗 等 方 面 都 可 以 发 挥 重 要 的 作 用 本 章 主 要 介 绍 MITK 中 的 面 绘 制 框 架 的 设 计 和 实 现, 包 括 两 大 部 分 : 表 面 重 建 和 表 面 绘 制, 在 下 面 两 节 中 将 分 别 予 以 详 细 介 绍 3.1 表 面 重 建 算 法 及 其 在 MITK 中 的 实 现 所 示 在 MITK 中, 表 面 重 建 算 法 被 抽 象 成 一 个 VolumeToMeshFilter, 如 图 3-1 Filter VolumeToVolumeFilter MeshToMeshFilter VolumeToMeshFilter m_indata : Volume m_outdata : Mesh +SetInput(in Data : Mesh) +GetOutput() : Volume MeshToVolumeFilter 图 3-2 VolumeToMeshFilter 其 输 入 数 据 是 N 张 两 维 的 切 片 生 数 据 ( 如 图 3-3 所 示 ), 表 示 为 一 个 mitkvolume; 经 处 理 后 的 输 出 数 据 是 一 个 以 三 角 网 格 来 表 示 的 三 维 表 面 模 型 ( 如 图 3-4 所 示 ), 表 示 为 mitkmesh 28

36 图 3-3 体 数 据 示 意 图 图 3-4 以 三 角 网 格 表 示 的 表 面 模 型 mitkmesh 中 的 三 角 面 片 数 据 以 点 表 和 面 表 来 组 织 点 表 是 一 个 float 型 数 组, 每 6 个 数 保 存 一 个 顶 点 的 信 息, 包 括 顶 点 坐 标 和 法 向 量, 按 (x, y, z; nx, ny, nz) 存 放 ; 面 表 是 一 个 unsigned int 型 数 组, 每 3 个 数 保 存 一 个 三 角 片 的 信 息, 分 别 是 组 成 该 三 角 片 的 3 个 顶 点 在 点 表 中 的 索 引 MITK 中 的 表 面 重 建 主 要 采 用 了 目 前 得 到 广 泛 应 用 的 Marching Cubes 算 法, 下 面 几 节 就 对 该 算 法 的 原 理 和 实 现 做 一 个 介 绍 传 统 的 Marching Cubes 算 法 Marching Cubes 算 法 是 W. Lorensen 等 人 于 1987 年 提 出 来 的 一 种 三 维 重 建 方 法 [1], 因 为 它 的 原 理 简 单, 并 且 很 容 易 实 现, 因 此 得 到 了 广 泛 的 应 用, 并 且 此 算 法 在 美 国 已 经 申 请 专 利, 它 被 认 为 是 至 今 为 止 最 流 行 的 面 显 示 算 法 之 一 Marching Cubes 算 法 是 面 显 示 算 法 中 的 一 种, 因 为 它 的 本 质 是 从 一 个 三 维 的 29

37 数 据 场 中 抽 取 出 一 个 等 值 面, 所 以 也 被 称 为 等 值 面 提 取 (Isosurface Extraction) 算 法 对 于 一 个 标 准 的 医 学 图 像 的 体 数 据 集, 它 往 往 是 由 一 系 列 的 二 维 切 片 数 据 组 成 的, 而 每 张 切 片 都 有 空 间 上 的 分 辨 率 假 设 有 一 个 体 数 据 集, 包 含 58 张 切 片, 每 张 切 片 的 分 辨 率 是 , 那 么 它 可 以 被 认 为 是 一 个 连 续 函 数 f(x,y,z) 在 x y z 三 个 方 向 上 按 一 定 的 间 隔 分 别 采 样 了 次 所 得 到 的 而 所 谓 的 等 值 面, 实 际 上 是 指 空 间 中 的 一 张 曲 面, 在 该 曲 面 上 函 数 f(x,y,z) 的 值 等 于 某 一 给 定 值 等 值 面 提 取 算 法 的 核 心 就 是 要 从 给 定 的 采 样 点 中 找 出 等 值 面 来, 这 时 最 容 易 想 到 的 方 法 就 是 首 先 由 采 样 点 恢 复 出 连 续 函 数 f(x,y,z) 来, 然 后 由 f(x,y,z) 和 某 一 给 定 的 值 ( 通 常 叫 域 值 ) 来 得 出 等 值 面, 这 种 方 法 一 般 被 称 为 显 式 的 等 值 面 提 取 算 法, 它 的 计 算 复 杂 度 比 较 高, 并 且 由 于 重 构 和 重 采 样 所 带 来 的 误 差 比 较 大, 所 以 精 度 也 得 不 到 保 证 与 此 相 反,Marching Cubes 算 法 采 用 了 隐 式 的 等 值 面 提 取 方 法, 它 不 直 接 计 算 f(x,y,z), 而 是 直 接 从 体 数 据 中 获 取 等 值 面 的 信 息 算 法 需 要 用 户 提 供 一 个 域 值, 也 就 是 所 希 望 提 取 出 来 的 物 质 的 密 度 值, 比 如 要 提 取 出 骨 骼, 域 值 就 要 相 对 大 一 些, 然 后 根 据 体 数 据 的 信 息, 就 可 以 提 取 出 来 等 值 面 的 三 角 网 格 表 达 Marching Cubes 算 法 的 过 程 可 以 描 述 如 下 : 1. 每 次 读 出 两 张 切 片, 形 成 一 层 (Layer); 2. 两 张 切 片 上 下 相 对 应 的 四 个 点 构 成 一 个 立 方 体 (Cube), 也 叫 Cell, Voxel 等, 如 图 3-5 所 示 ; 3. 从 左 至 右, 从 前 到 后 顺 序 处 理 一 层 中 的 Cubes( 抽 取 每 个 Cube 中 的 等 值 面 ), 然 后 从 下 到 上 顺 序 处 理 (n-1) 层, 算 法 就 结 束, 故 名 为 Marching Cubes 30

38 图 3-5 Cubes 示 意 图 对 于 每 一 个 Cube 而 言, 它 的 八 个 顶 点 的 灰 度 值 可 以 直 接 从 输 入 数 据 中 得 到, 要 抽 取 的 等 值 面 的 域 值 也 已 经 知 道 如 果 一 个 顶 点 的 灰 度 值 大 于 域 值, 则 将 它 标 记 为 黑 色 (Marked Vertex), 而 小 于 的 不 标 (Unmarked Vertex), 如 错 误! 未 找 到 引 用 源 所 示 图 3-6 Marked Vertex 与 Unmarked Vertex 因 为 一 个 Cube 有 8 个 顶 点, 每 个 顶 点 有 Marked Unmarked 两 种 状 态, 所 以 等 值 面 的 分 布 总 共 可 能 有 28=256 种 但 是 考 虑 到 Cube 有 旋 转 (Rotation) 对 称 性, 旋 转 不 影 响 等 值 面 的 拓 扑 结 构, 另 外, 所 有 的 Marked Vertex 变 为 Unmarked Vertex, 或 者 反 过 来 (Invertion 对 称 ), 等 值 面 的 连 接 方 式 也 不 会 改 变 考 虑 了 Rotation 和 Invertion 两 种 情 况 后, 原 作 者 总 结 了 15 种 Basic Cube, 它 们 覆 盖 了 所 有 256 种 可 能 的 情 况, 如 图 3-7 所 示 31

39 图 种 基 本 Cubes 的 拓 扑 形 状 根 据 这 15 种 基 本 的 Cubes, 可 以 造 出 一 个 查 找 表 (Look-up Table) 表 的 长 度 为 256, 记 录 了 所 有 情 况 下 的 等 值 面 连 接 方 式 所 以 此 时 只 需 分 别 比 较 一 个 Cube 的 八 个 顶 点 与 域 值 之 间 的 大 小 关 系, 即 可 得 出 一 个 之 间 的 索 引 值 (CubeIndex), 然 后 直 接 查 表 就 可 得 到 此 Cube 在 那 条 边 上 有 等 值 点, 并 且 还 能 得 到 等 值 点 的 连 接 方 式 等 信 息, 这 时 候 就 可 以 将 等 值 点 连 接 起 来 以 形 成 等 值 面 要 想 用 真 实 感 图 形 学 技 术 将 等 值 面 显 示 出 来, 除 了 要 知 道 每 个 等 值 点 的 坐 标 外, 还 必 须 知 道 每 个 等 值 点 的 法 向 量 在 计 算 Cube 某 条 边 上 的 等 值 点 坐 标 与 法 向 量 时, 有 两 种 方 法, 一 种 是 线 性 插 值, 另 外 一 种 是 中 点 选 择 (MidPoint Selection) 线 性 插 值 的 公 式 如 下 所 示 : P = P 1 + (isovalue - V 1 ) (P 2 - P 1 ) / (V 2 - V 1 ) (3-1) N = N 1 + (isovalue - V 1 ) (N 2 - N 1 ) / (V 2 - V 1 ) (3-2) 其 中 P 代 表 等 值 点 坐 标,P 1 P 2 代 表 两 个 端 点 的 坐 标,V 1 V 2 代 表 两 个 端 点 的 灰 度 值, isovalue 代 表 阈 值 ;N 代 表 等 值 点 法 向 量,N 1 N 2 代 表 两 个 端 点 的 法 向 量 中 点 选 择 的 公 式 如 下 所 示 : 32

40 P = (P 1 + P 2 )/ 2 (3-3) N = (N 1 + N 2 )/ 2 (3-4) 其 中 P 和 N P 1 P 2 N 1 N 2 所 代 表 的 意 义 同 上 中 点 选 择 所 具 有 的 优 点 是 : 1. 引 起 的 误 差 低 于 1/2 Cube 边 长, 这 在 医 学 图 像 的 解 析 度 越 来 越 高 的 情 况 下, 所 重 建 出 来 的 图 像 与 线 性 插 值 得 到 的 图 像 并 没 有 明 显 的 视 觉 上 的 差 异 2. 如 果 先 放 大 10 倍 再 进 行 运 算, 就 可 以 完 全 采 用 整 数 运 算, 避 免 浮 点 运 算 3. 可 以 使 得 局 部 表 面 更 平 坦, 有 利 于 后 续 的 化 简 过 程, 如 图 3-8 所 示 : 图 3-8 局 部 表 面 的 平 坦 化 MITK 中 的 mitkmarchingcubes 类 实 现 的 表 面 重 建 算 法 基 于 传 统 的 Marching Cubes 算 法, 它 可 以 接 受 高 低 两 个 阈 值, 把 灰 度 在 这 两 个 阈 值 之 间 的 组 织 分 界 面 提 取 出 来, 从 而 达 到 物 体 表 面 重 建 的 目 的 该 算 法 使 用 了 如 下 所 示 的 查 找 表 : short g_edgetable[256] = 0x0, 0x109, 0x203, 0x30a, 0x406, 0x50f, 0x605, 0x70c, 0x80c, 0x905, 0xa0f, 0xb06, 0xc0a, 0xd03, 0xe09, 0xf00, 0x190, 0x99, 0x393, 0x29a, 0x596, 0x49f, 0x795, 0x69c, 0x99c, 0x895, 0xb9f, 0xa96, 0xd9a, 0xc93, 0xf99, 0xe90, 0x230, 0x339, 0x33, 0x13a, 0x636, 0x73f, 0x435, 0x53c, 0xa3c, 0xb35, 0x83f, 0x936, 0xe3a, 0xf33, 0xc39, 0xd30, 0x3a0, 0x2a9, 0x1a3, 0xaa, 0x7a6, 0x6af, 0x5a5, 0x4ac, 0xbac, 0xaa5, 0x9af, 0x8a6, 0xfaa, 0xea3, 0xda9, 0xca0, 33

41 ; 0x460, 0x569, 0x663, 0x76a, 0x66, 0x16f, 0x265, 0x36c, 0xc6c, 0xd65, 0xe6f, 0xf66, 0x86a, 0x963, 0xa69, 0xb60, 0x5f0, 0x4f9, 0x7f3, 0x6fa, 0x1f6, 0xff, 0x3f5, 0x2fc, 0xdfc, 0xcf5, 0xfff, 0xef6, 0x9fa, 0x8f3, 0xbf9, 0xaf0, 0x650, 0x759, 0x453, 0x55a, 0x256, 0x35f, 0x55, 0x15c, 0xe5c, 0xf55, 0xc5f, 0xd56, 0xa5a, 0xb53, 0x859, 0x950, 0x7c0, 0x6c9, 0x5c3, 0x4ca, 0x3c6, 0x2cf, 0x1c5, 0xcc, 0xfcc, 0xec5, 0xdcf, 0xcc6, 0xbca, 0xac3, 0x9c9, 0x8c0, 0x8c0, 0x9c9, 0xac3, 0xbca, 0xcc6, 0xdcf, 0xec5, 0xfcc, 0xcc, 0x1c5, 0x2cf, 0x3c6, 0x4ca, 0x5c3, 0x6c9, 0x7c0, 0x950, 0x859, 0xb53, 0xa5a, 0xd56, 0xc5f, 0xf55, 0xe5c, 0x15c, 0x55, 0x35f, 0x256, 0x55a, 0x453, 0x759, 0x650, 0xaf0, 0xbf9, 0x8f3, 0x9fa, 0xef6, 0xfff, 0xcf5, 0xdfc, 0x2fc, 0x3f5, 0xff, 0x1f6, 0x6fa, 0x7f3, 0x4f9, 0x5f0, 0xb60, 0xa69, 0x963, 0x86a, 0xf66, 0xe6f, 0xd65, 0xc6c, 0x36c, 0x265, 0x16f, 0x66, 0x76a, 0x663, 0x569, 0x460, 0xca0, 0xda9, 0xea3, 0xfaa, 0x8a6, 0x9af, 0xaa5, 0xbac, 0x4ac, 0x5a5, 0x6af, 0x7a6, 0xaa, 0x1a3, 0x2a9, 0x3a0, 0xd30, 0xc39, 0xf33, 0xe3a, 0x936, 0x83f, 0xb35, 0xa3c, 0x53c, 0x435, 0x73f, 0x636, 0x13a, 0x33, 0x339, 0x230, 0xe90, 0xf99, 0xc93, 0xd9a, 0xa96, 0xb9f, 0x895, 0x99c, 0x69c, 0x795, 0x49f, 0x596, 0x29a, 0x393, 0x99, 0x190, 0xf00, 0xe09, 0xd03, 0xc0a, 0xb06, 0xa0f, 0x905, 0x80c, 0x70c, 0x605, 0x50f, 0x406, 0x30a, 0x203, 0x109, 0x0 char g_tritable[256][16] = -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, 8, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, 1, 9, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 1, 8, 3, 9, 8, 1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 1, 2, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, 8, 3, 1, 2, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 9, 2, 10, 0, 2, 9, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 2, 8, 3, 2, 10, 8, 10, 9, 8, -1, -1, -1, -1, -1, -1, -1, 3, 11, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, 11, 2, 8, 11, 0, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,... 34