【毕业学位论文】（Word原稿）针对资料视觉化所设计之简单及快速的种子集建构系统-信息管理与系统

国 立 台 湾 科 技 大 学 资 讯 管 理 系 硕 士 学 位 论 文 学号： 对资料视觉化所设计之简单及快速的种子集建构系统 A 究 生： 指导教授： 博士 年 七 月 十五 日 I 针对资料视觉化所设计之简单及 快速的种子集建构系统 研究生： 指导教授： 博士 国立台湾科技大学资讯管理学系 摘要 在实体资料的呈像 (，撷取等值面 (相当重要的方法，而在撷取等值面的方法中以同值扩展 (算法最有效率。同值扩展演算法不似其他方法需在整个实体资料 (进行搜寻，而仅需搜寻其某一子集合即可完整地找到所有等值面 (我们称此子集合为种子集(其特性为实体资料内的所有等值面皆会与此种子 集相交，而且此种子集是在前置处理时间 (即可建立完成。 当我们在执行阶段 (给定一个等值 (同值扩展演算法即可开始执行，从种子集中有包含等值的单元格子 (始逐渐扩展而形成整个等值面。如果我们在前置处理时间内所找到的种子集愈小，则在执行阶段所花的搜寻时间也将会减少。因此在其他探讨同值扩展演算法的论文中，大都将焦点关注于如何找到较小的种子集。 本研究中我们提出一个新颖且有效率的方法来建立种子集，此方法不但能降低种子集的大小 ，而且也能提升撷取等值面的速度。 关键字： 撷取等值面方法、实体资料的呈像、同值扩展演算法、种子集 is of is of to be on a of a it be at an is at in to As on to an In we a of up 谢 首先要感谢指导教授 杨传凯 博士，在过去的两年里，给予我课业与研究上的细心指导，使得本论文得以顺利完成。并在解决问题的过程中，引导学生独立思考之能力，在此向老师致上最诚挚的谢意。同时也感谢口试委员 项天瑞 博士与 李育杰 博士，拨冗在论文上所给予的评阅与建议。 本论文的完成，要谢谢我的朋友及同学们 幸卿 学姐、 佑玮 、 升元 、家玮 、 惠琳 、 威廷 ，在平日生活及课业上的协助，在此一并致谢。 最后，将此论文成果献给我的家人与所有关心我的人，希望大家与我分享这份喜悦，谢谢你们。 录索引 中文摘 要 . 错误 !未定义书签。 英文摘要 . 错误 !未定义书签。 誌謝 . 错误 !未定义书签。 目錄索引 . 错误 !未定义书签。 圖表索引 . 错误 !未定义书签。 第一章 導論 . 错误 !未定义书签。 言 . 错误 !未定义书签。 究目的 . 错误 !未定义书签。 文架構 . 错误 !未定义书签。 第二章 相關工作 . 错误 !未定义书签。 學視覺化 (. 错误 !未定义书签。 體資料 (. 错误 !未定义书签。 則實體資料在三維空間中的定義 . 错误 !未定义书签。 體資料的取得 . 错误 !未定义书签。 體資料的呈像 (. 错误 !未定义书签。 體資料呈像方法的分類 . 错误 !未定义书签。 較直接式呈像與非直接式呈像方法的優缺點 . 错误 !未定义书签。 值面的擷取 (. 错误 !未定义书签。 元格子的三角化 (. 错误 !未定义书签。 算法 . 错误 !未定义书签。 元格子的搜尋 (. 错误 !未定义书签。 . 错误 !未定义书签。 . 错误 !未定义书签。 子集 (. 错误 !未定义书签。 值擴展演算法 (. 错误 !未定义书签。 算法 . 错误 !未定义书签。 算法 . 错误 !未定义书签。 第三章 新種子集演算法 . 错误 !未定义书签。 述 . 错误 !未定义书签。 法的起源 . 错误 !未定义书签。 元格子的分群 . 错误 !未定义书签。 取種子集程序 . 错误 !未定义书签。 V . 错误 !未定义书签。 . 错误 !未定义书签。 算法 . 错误 !未定义书签。 過離散集合 (增進效能 . 错误 !未定义书签。 第四章 實驗結果及分析 . 错误 !未定义书签。 驗環境 . 错误 !未定义书签。 驗結果 . 错误 !未定义书签。 種子集演算法的實驗結果 . 错误 !未定义书签。 作 算法的實驗結果 . 错误 !未定义书 签。 種子集演算法與其它種子集擷取方法之比較 . 错误 !未定义书签。 第五章 結論 . 错误 !未定义书签。 參考文獻 . 错误 !未定义书签。 表索引 圖 面 Z = 3. 4 圖 維實體資料 . 6 圖 體資料在三維空間中的定義 . 7 圖 體資料呈像流程圖 . 8 圖 維實體資料陣列 . 值面的擷取 . 元格子 . 值輪廓線 . 維資料的 . 元格子與等值面相交 . 元格子三角化 . 元樹分解方法 . 元樹分解方法 . 1D . 2D . 值擴展演算法 . 值擴展演算法的程式描述 . 端點的定義 . 像瘦身方法 . 算法的整體描述 . 維瘦身方法 . 維資料集合與其等值輪廓線 . 點的擷取 . 分圖 . 算法的整體描述 . 值輪廓線的拓 樸 改變過程 . 廓樹的建構程序 . 廓樹 . 廓樹與雙分圖的對應 . 演算法的主要步驟 . 上封套 (. 元格子間的局部連接性 (一 ) . 元格子間的局部連接性 (二 ) . 元格子的分群 . 元格子的分群過程 . 比較 . . 元格子化簡過程 . . 元格子化簡過程 . 蹤祖先 . 算法 . 序 (一 ) . 序 (二 ) . 散集合的聯集運算 . 散集合的路徑壓縮 . 過離散集合找尋源頭祖先，並進行路徑壓 縮 . 元格子的連接性 . 法下，從不同的座標方向順序來進行刪除動 作 . 值單元格子的刪除 . 腦圖學與科學 視覺化的比較 . 5 表 接式呈像與非直接式呈像的差異 . 11 表 驗所用的實體資料集合 . 驗結果表格 中，各名詞縮寫的意義 . 的種子集大小之比較 . 方法下，討論 及 接性對種子集大小的影響 . 法下，以不同的座標方向順序尋訪對種子集 大小的影響 . 較 使用 蹤組先與使用 花的時間 . 種子集演算法中各階段所花的時間 . 端點個數與骨架的單元格子個數 . 較移除同值單元格子前後之骨架的單元格 子個數 . 種子集演算法與其它種子集擷取方法之比 較 .1 第一章 导论 言 近年来，随着电脑图学 (术的发展，科学视觉化(应用也随之快速地兴起，相较于传统上使用一堆数字的表示方式，科学视觉化利用图形、颜色及影像来呈现三维资料的内容，使人更容易印象深刻且一目了然。 由于实体资料呈像 (技术广泛地应用于各个领域，使得实体呈像方法成为科学视觉化中相当重要的研究主题，而且其应用范围非常广泛，包括医学诊断、数值模拟、教学及娱乐等。实体呈像技术的方法有很多，其中以撷取等值面 (最普遍且热门的一种方法。一般说来，撷取等值面的方法包含两个阶段，单元格子的寻找 (三角形的产生 (到目前为止，由于第二阶段的研究已经相当普遍且固定，现在大部份的研究都专注于如何 降低第一阶段中搜寻单元格子所花的时间，而其中又以同值扩展法 (有效率。 究目的 由于电脑断层扫瞄 (技的进步与影像处理 (术的创新，使得透过专业的影像工作站，即可获得十分精确的二维切片影像 (2D 也可再将相关的影像资讯提供给专家做分析及决策之用。又随着三维立体重构 (3D 电脑图学技术水准的提升，许多论文开始着重于科学视觉化的应用。 在撷 取等值面的各方法中，同值扩展法不像其他方法需在整个实体资 2 料 (进行搜寻，而仅需搜寻其某一子集合即可完整地找到所有的等值面 (我们称此子集合为种子集 (其特性为实体资料内的所有等值面都会与此种子集相交，而且此种子集在前置处理时间(即可建构完成。 当我们在执行阶段 (给定一个等值 (同值扩展法即可开始执行，从种子集中有包含等值的单元格子 (始，逐渐地扩展而形 成完整的等值面。如果我们在前置处理找到的种子集愈小，则在执行阶段时，就能够更快速地找到起始单元格子，其所花的搜寻时间也将会减少。因此，在其他探讨同值扩展法的论文中，大部份都将焦点关注于如何找到最佳的种子集来提升整体效能。我们拿同值扩展法与其他撷取等值面的方法做比较，可发现其有两项显著的优点： 产生出来的等值面能够立即地转换为一连串的三角形带 (如此一来能够在呈像阶段 (大量地降低传送至显示卡的资料量，进而加速呈像效率。 等值面的撷取不需将整个实 体资料拿来搜寻，只需搜寻整个实体资料的部份子集合 (种子集 )，大量地降低了搜寻的时间。 到目前为止有许多其他的方法，像是 P. 人提出的区间树(6或是 J. 17，皆能够减少寻找单元格子所花的时间，增进整体的效能。除此之外，由 Y. 14，更使我们从中得到一些灵感。在本研究中，我们将提出一个新颖且有效率的方法来建立种子集，此方法不但能降 低种子集的大小，提升等值面撷取的速度，而且十分简单易于实作。 3 文架构 本论文的架构与章节如下： 第一章：介绍本论文之研究背景及目的。 第二章：主要在解释论文中所提及的重要名词，及回顾与撷取等值面方法 (关的文献。 第三章：本论文的重点所在，在该章中，我们将提出一个崭新的演算法流程来有效率地建立极小的种子集。 第四章：分析及讨论本论文所得的实验结果，并与其他文献的方法做比较。 第五章：结论与未来方向。 4 第二章 相关工作 学视觉化 (科学视觉化 (或称科学试算 )最主要的目的是透过电脑图学的绘图技术来呈现立体的三维实体资料 (在 ，让研究者能够容易操作且清楚地从大量资料中观察到我们想得知的讯息。在二维的表示法中，我们一般常透过长条图、折线图及圆饼图等来了解资料的分布状况，而对于三维资料的表示，我们可以藉由三维几何模型的操作 (旋转、平移、缩放 )，加上颜色的分布，使得资料里不易观察的讯息能更完整的呈现。以图 图形为三次曲面，若我们只有曲面方式程，则很难去想象曲面在空间中 的分布情形，因此，透过电脑绘图让我们对此曲面一目了然，对于教学方面将有相当贡献。 图 面 Z = 3学视觉化的应用相当广泛，包含医学诊断、大气模拟、风洞测试 (观测气流及阻力系数，可以用多种颜色来表示气流的动态变化 )、生物分子结构、地理表面重建及数学领域等，其中以医学的诊断治疗应用最广。 5 科学视觉化利用电脑图学技术，将电脑模拟运算所产生出的大量数据资料转成图形或动画，来呈现及诠释其内容。虚拟实境 (数位多媒体 (可增强科学试算成果的表现，让它的呈现方式更多元化。科学视觉化必须结合多个领域的技术，主要包括下列几项： 电脑图学 ( 影像处理 ( 电脑视觉 ( 电脑辅助设计 ( 讯号处理 ( 图形使用者介面 (下表为电脑图学与科学视觉化的比较： 电脑图学 科学视觉化 目的 建立逼真的影像 了 解资料内容 物件的表达方式 多边形网格 实体资料 维度 3D 2D、 3D (或更高 ) 互动性 有 有 是否观看内部结构 没有 有 评估准则 与真实景物或相片做比较 无比较对象，愈容易让使用者了解资料内容愈好 表 脑图学与科学视觉化的比较 6 体资料 (实体资料是由许多连续的二维影像所重迭而成的三维立体资料 (示 )，例如使用电脑断层扫瞄技术将人类的头颅进行分层扫瞄，可得到多张连续的二维灰阶影像 (图 b、图 c)，再将这些连续的影像重迭而形成三 维的实体资料 (图 d)，又称为资料集 (其中要特别注意的是，这些灰阶影像中像素值 (高低与真实物件的密度值相关。举例来说，人类头颅中骨胳的密度大于软骨组织 (密度，而软骨组织的密度又大于皮肤的密度，因此在灰阶影像中骨胳所在位置的像素值高于软骨组织