（计算机应用技术专业论文）体绘制传递函数设定方法的研究和应用.pdf

硕士学位论文 摘要 体绘制是一种重要的三维数据场可视化方法，传递函数是体绘制过程中用以 定出体数据与光学特征的对应关系的关键步骤，传递函数的设定对成像的质量具 有重要作用。然而传递函数的设定往往需要大量尝试，困难且不直观，寻找好的 传递函数已被列为体数据可视化中的十大难题之一。 层次聚类应用于传递函数设定领域取得了较好的效果，然而，单处理机以其 有限的运算能力和存储能力难以在有效的时间内完成规模较大的三维体数据的聚 类分析，为此本文设计实现了层次聚类并行算法，并将其与l h 直方图相结合以 指导传递函数的设定。与串行算法相比，并行层次聚类算法能在合理的时间内对 三维体数据进行聚类分析，并以相同聚类效果完成对传递函数设定的指导，最终 得到高质量的图像。 另一方面，若将寻找合适的传递函数的过程视为参数优化问题，则可用全局 最优化的方法来处理，遗传算法应用于传递函数的设定已有相当研究。本文将粒 子群算法以自动式和交互式两种进化方式应用于体绘制传递函数设定领域，且在 交互式实现方式中提出了基于用户的速度更新策略。与遗传算法相比，基本型和 改进型粒子群算法具有更好的性能，能使用户更快的得到更满意的体绘制图像。 最后，在地震数据可视化系统中，将粒子群优化算法、手动调节和多分辨率 显示功能三者相结合，为用户提供了一个自动式与交互式相结合，具有实时反馈 功能的双层结构的传递函数设定工具，使地球物理学家用户在探索地震数据的过 程中更加灵活和便利，从而提高地震勘探的精确度和成功率。 关键词：传递函数：粒子群优化；并行层次聚类；直接体绘制；地震数据 i l 体绘制传递函数设定方法的研究和应用 a b s t r a c t v o l u m er e n d e r i n gi sak e yt e c h n o l o g yf o rt h ev i s u a l i z a t i o no ft h r e e d i m e n s i o n a l d a t a s e t t r a n s f e rf u n c t i o ni su s e dt os p e c i f yt h er e l a t i o n s h i p sb e t w e e nv o l u m ed a t a a n do p t i c a lp r o p e r t i e si nt h ep r o c e s so fv o l u m er e n d e r i n g s p e c i f i c a t i o no ft r a n s f e r f u n c t i o np l a y sa ni m p o r t a n tr o l ei nt h er e n d e r i n g q u a l i t y u n f o r t u n a t e l y ，s p e c i f y i n ga g o o dt r a n s f e rf u n c t i o ni sad i f f i c u l ta n dt e d i o u st a s k ，t h u si th a sb e e nr e f e r r e da so n e o ft h et o pt e np r o b l e m si nv o l u m ev i s u a l i z a t i o n t h ea p p l i c a t i o no fh i e r a r c h i c a lc l u s t e r i n gi n t ot r a n s f e rf u n c t i o ns p e c i f i c a t i o ni s s h o w nt ob ee f f e c t i v e h o w e v e r , w i t ht h el i m i t e d c a p a b i l i t i e so nc o m p u t i n ga n d s t o r a g e ，i ti sv e r yd i f f i c u l tf o ras i n g l ep r o c e s s o rt oa c c o m p l i s hc l u s t e ra n a l y s i so ft h e l a r g es c a l e3dv o l u m ed a t aw i t h i na ne f f e c t i v ep e r i o d 。i nt h i s p a p e r , ap a r a l l e l h i e r a r c h i c a l c l u s t e r i n ga l g o r i t h m ，w h i c hi sc o m b i n e dw i t ht h el hh i s t o g r a m i s d e s i g n e di n o r d e rt oi n s t r u c t e f f e c t i v e l yt h es p e c i f i c a t i o no ft r a n s f e rf u n c t i o n c o m p a r e dw i t ht h es e r i a la l g o r i t h m ，o u rp a r a l l e la l g o r i t h mi sa b l et oa c c o m p l i s ht h e c l u s t e r i n ga n a l y s i so ft h el a r g es c a l e3 dv o l u m ed a t aw i t h i nar e a s o n a b l ep e r i o d t h e i m a g e sw i t hh i g hq u a l i t ya r er e n d e r e df i n a l l y o nt h eo t h e rh a n d ，s u p p o s i n gt h ep r o c e s so f f i n d i n gas u i t a b l et r a n s f e rf u n c t i o n t ob ea p a r a m e t e ro p t i m i z a t i o np r o b l e m ，t h eg l o b a lo p t i m i z a t i o na p p r o a c hi sas o l u t i o n s of a rg e n e t i ca l g o r i t h mh a sb e e na p p l i e di n t ot h er e s e a r c ho nt r a n s f e r f u n c t i o n s p e c i f i c a t i o n i nt h i sp a p e r , t h ep a r t i c l es w a r mo p t i m i z a t i o ni s a p p l i e di n t ot h i sf i e l d w i t ht w od i f f e r e n tk i n d so fe v o l u t i o n a r ya p p r o a c h e so fa u t o m a t i ca n di n t e r a c t i v e b e s i d e s ，t h eu s e r b a s e ds p e e du p d a t es t r a t e g yi ni n t e r a c t i v ea p p r o a c hi sa l s op r o p o s e d t h eb a s i ca n di m p r o v e dp a r t i c l es w a r ma l g o r i t h m s ，w h i c ha r ec a p a b l et op r o v i d eu s e r w i t hs a t i s f y i n gv o l u m er e n d e r i n gi m a g e sm u c hf a s t e r , h a v eb e t t e rp e r f o r m a n c et h a n g e n e t i ca l g o r i t h m t h es y s t e mo fs e i s m i cd a t av i s u a l i z a t i o np r o v i d e su s e r sw i t hat w o 1 e v e lt 0 0 1f o r t r a n s f e rf u n c t i o n s p e c i f i c a t i o nb yc o m b i n i n gt h e p a r t i c l e s w a r m o p t i m i z a t i o n a l g o r i t h m ，m a n u a l l ya d ju s t i n gt r a n s f e rf u n c t i o na n dm u l t i r e s o l u t i o n d i s p l a y i n g t o g e t h e r w i t ht h i st o o l ，w h i c hi st h ec o m b i n a t i o no fa u t o m a t i c i t ya n di n t e r a c t i v i t y ， t h eu s e rc a ng e tr e a l - t i m ef e e d b a c ko ft h e r e n d e r i n gr e s u l t ，w h i c hc a nm a k e g e o p h y s i c i s t se x p l o r et h es e i s m i cd a t am o r ee x p e d i e n t l ya n df l e x i b l y ，a n de n h a n c et h e a c c u r a c ya n ds u c c e s sr a t eo fs e i s m i ce x p l o r a t i o n i l l 硕上学位论文 k e yw o r d s ：t r a n s f e rf u n c t i o n ；p a r t i c l es w a r mo p t i m i z a t i o n ；p a r a l l e lh i e r a r c h i c a l c l u s t e r i n g ；d i r e c tv o l u m er e n d e r i n g ；s e s c i m i cd a t a i v 体绘制传递函数设定方法的研究和应用 插图索引 图1 1 头部数据在不同传递函数下的绘制效果2 图2 1 体数据类型9 图2 2 体绘制算法流程1 0 图3 1 不同时刻各处理器处理的相异度矩阵中的数据块1 7 图3 2 数据划分图。1 8 图3 3 链表的建立与修改2 0 图3 4 最小生成树和剪枝后结果2 4 图3 5 算法3 5 的运行过程2 4 图3 6 基于l h 直方图进行聚类2 5 图3 7 绘制结果2 5 图4 1 粒子移动原理图2 9 图4 2 初始传递函数示例3 0 图4 3 粒子群算法应用于体绘制传递函数设定的流程图3 l 图4 4 实验数据3 3 图4 5 使用三维地震数据的两种算法的迭代次数和平均适应值的对比3 4 图4 6 使用三维头部数据的两种算法的迭代次数和平均适应值的对比一3 4 图4 7 图形用户界面。3 5 图4 8 参数设置界面3 5 图5 1 文件格式v o x e t 3 8 图5 2 四维数据的访问3 9 图5 3 单件模式的结构4 l 图5 4 抽象工厂模式一4 2 图5 5 模块中三部分关系图4 3 图5 6 双层结构的传递函数设定工具4 4 图5 7 初始化4 5 图5 8 双击低分辨图像后显示相应的高分辨率图像4 5 图5 9 传递函数的手动调节工具4 6 图5 1 0 手动调节传递函数的实时绘制效果4 7 图5 1 1 在高分辨率层选择父辈传递函数4 8 图5 1 2 粒子群算法的参数设置界面4 9 v i i 硕士学位论文 附表索引 表3 1 三种数据算法在不同处理器下的运算时间2 6 表4 1 用户使用三种算法进行传递函数设定所耗时间与迭代次数3 6 表4 2 用户使用三种算法完成传递函数设定所经历的代数3 6 v i i i 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 作者签名：祈黟 日期叫年6 月日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇 编本学位论文。 本学位论文属于 l 、保密口，在 年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“”) 作者签名： 导师签名 齐彰 日期：卅年莎月9 日 日期：砷年石月9 日 硕f j ：学位论文 第1 章绪论 1 1 课题来源 本课题来源于国际合作项目“地震数据可视化系统”。 1 2 研究背景 1 9 7 8 年2 月，美国国家科学基金会在华盛顿召开会议；与会者在会上首次提出 了科学计算可视化的概念即“v i s u a l i z a t i o ni ns c i e n t i f i cc o m p u t i n g ”，简称为 “s c i e n t i f i cv i s u a l i z a t i o n ”。不同于人类传统的基于文字、数字符号的通信模式，科 学计算可视化的实质是运用计算机图形学和图像处理技术，将科学计算过程中产 生的数据及计算结果转换为信息量丰富、形象直观的图形、图像，在屏幕上显示 出来并进行交互处理。科学计算可视化作为一门新兴学科，自正式确定以来便得 到了迅猛的发展，欧美发达国家在科学计算可视化的研究应用与培训上投入了大 量的资金和人力，取得了显著的成效。科学计算可视化、多媒体和虚拟现实技术 一同成为了近十年来计算机科学中的研究热点。实际上，随着相关技术的发展， 科学计算可视化已经远远超过了它最初的定义。它不仅仅包括科学数据的可视化， 而且包括工程计算数据的可视化，如有限元分析结果等，也包括测量数据的可视 化，如地震勘探的地震数据和医疗领域的计算机断层扫描( c t ) 数据。 三维空间数据场的可视化是实现科学计算可视化的核心。根据绘制过程中数 据描述方法的不同，三维数据场的可视化方法可以分为二类：面绘制和直接体绘 制。相对于传统的面绘制方法，直接体绘制( 简称体绘制) 技术逐渐成为研究的热 点。因为体绘制不需要需要生成中间图元，而是直接对体数据进行成像，显示全 部的数据信息，不会造成数据的丢失。作为三维数据可视化的重要技术，体绘制 在医学、气象学科学和地球物理学领域的应用相当广泛。 在体绘制中，传递函数将3 维数据场的采样点映射成光学参数，直接决定了绘 制的效果，成为体绘制研究的关键。如图1 1 所示，在不同的传递函数下，头部数 据绘制出效果不同的图像。然而，传递函数的设计存在两个主要问题：缺乏直观 的用户界面，用户通过传递函数定义数据场中感兴趣的对象往往需要大量的尝试， 反复调节可视化参数，花费大量的时间和精力；缺乏数据场的指导信息，使传递 函数的设计存在盲目性，有时即使已经设计出好的传递函数，得到了最好的绘制 结果，可能也不知道。在近十多年来，仍然没有一个很好的办法来解决这个问题。 在一定程度上正是寻找合适传递函数的困难，阻碍了体绘制的更广泛应用。寻找 件绘d 传递自数堙i 往的日究h 用 好的传递函数已被列为体可视化研究中的十大难题之- - 1 ”，传递函数设定方法的 研究具有相当重要性和迫切性的研究意义。 田li 头部数据在不同传递函数下的绘制效果 3 国内外研究现状 目前主要有4 类设计传递函数的方法：手动调节法、数据中心法、图像中心 法、对敦中心法。 l3 l 手动调节法 手动调节法2 3 l 是通过不断的调节传递函数的参数得到不同的绘制结果，达 到对3 维数据场的研究。该方法的优点是用户拥有完全的主动权，可以根据自己 的需求随意的调节传递函数，直到达到满意的效果。k i t w a r e 公司开发了软件 v o l v i e w 提供了手动调节传递函数的用户交互界面。实现了实时观察体绘制的结 果。该系统分别用数据场的灰度直方图和梯度幅值直方图来设计颜色和透明度值， 传递函数的映射关系可以是阶梯函数和斜坡函数。例如，传递函数的定义域为梯 度幅值值域为透明度，映射规则为斜坡函数可以实现大于梯度阈值的采样点 的可视化，突出物质的边界面。 然而手动调节法往往需要大量的尝试和对绘制结果的观察，才能找寻出理想 的传递函数。当自变量的维数超过2 时，参数报难调节和控制。对于未知的3 维 数据场常常需要花费大量的时间和精力去反复的研究大大降低了设计传递函数 的效率。 1 32 数据中心法 在众多数据特征中，控制3 维数据场的等高线的高度参数( 等高线值) 是一种 较简单的特征值。由于等高线只能显示数据场的部分信息，因此。为了了解整个 数据场的信息，可以调蛙等高线值来显示多条等商线信息。b a j a j 等提出了“等高 线谱”的概念”l 。“等岛线诺”定义了数据场中等高线的特征值的度量标准。等高线 硕上学位论文 的特征值包括：等高线的周长、等高线的面积以及沿等高线的梯度积分等，它们 均可由定义在等高线值上的一元b 样条函数计算获得。b o n g s o o 等将“等高线谱” 扩展为“等高线树”，应用到随时间变化的3 维数据场的可视化研究中，通过观察 “等高线树”特征值的变化来研究数据场随时间变化的规律，并根据“等高线树”的 特征值设计传递函数t 5 1 。 物质的等值面和边界面是最常用全局数据属性。周芳芳等提出了基于多尺度 等值面设计传递函数的高效方法【6 l ，该方法通过梯度阈值提取边界体元，然后将 提取等值面的目标函数的计算化简为累加的拉普拉斯加权的直方图极值的计算， 最后对直方图进行多尺度平滑，利用提取出的多尺度等值面来设计高斯型传递函 数。k i n d l m a n n 等通过分析3 维数据场的统计信息来确定物质的边界区域【7 】。该方 法首先假设边界模型为高斯模糊的阶梯函数，然后计算由数据值、梯度幅值、梯 度方向的二阶导数组成的3 维直方图，边界面在由标量和梯度幅值组成的2 维直方 图中表现为弧形结构。为了提高物质边界面提取的准确度，k n i s s 等根据k i n d l m a n n 的3 维直方图理论，设计了多维传递函数1 8 j ，开发了1 组操纵杆来的调节可视化参 数。在用户界面中，既可以在传递函数的定义域内调节操纵杆改变传递函数的参 数得到绘制的结果，也可以在3 维数据场中操纵感兴趣的区域，得到相应的传递函 数。t c n g i n a k a i 等则提出了统计型边界模型【9 j ，通过计算采样点的各阶中心矩及其 它们的相互关系来确定物质的边界面。该边界模型比高斯边界型模型更通用，中 心矩的计算比导数计算更简单，对噪声的鲁棒性也更强。s e r e d a 等提出用l h 直方 图来提取物质的边界面f l0 1 ，解决了在噪声大、模糊情况下边界面准确提取的问题。 李彬1 1 1 等在传递函数预设定时，基于边界模型、结合对象交互式操作，使用户能 方便地找到最优传递函数。彭延军等提出边界模型和局部特征结构相结合的半自 动解决方法l l2 1 ，通过给定的特定体素点，结合边界模型找出特定组织的内部、外 部体素，对边界体素计算汉森矩阵的特征值并按其特征结构进行分割。 除了物质的边界面，3 维数据场的拓扑结构也是一种重要的全局数据属性。 f u j i s h i r o 等提出了通过分析数据场的拓扑结构来设计颜色和透明度传递函数【1 3 】， 其中拓扑结构的分析结果用h y p e r r e e b 图来表示。为了降低了计算量，t a k a h a s h i 等提出直接提取3 维数据场中的关键点，构造出数据场的骨架树，为重要的区域 设计传递函数【l4 。骨架树是描述数据场的关键点和连结关系的抽象图，反应了等 值面在数据场中的分裂或合并的进化过程，强调有意义的等值面。该方法可以检 测出所有的关键点，保证了数学的完备性。l e f o h n 等利用水平集算法提取复杂数 据场中的拓扑结构【l5 1 。水平集算法是处理封闭运动界面随时间演化过程中几何拓 扑变化的有效计算工具，通过最小化基于主曲率的能量函数，迭代的对隐曲面进 行变形。根据水平集算法提取的拓扑结构设计传递函数，能够实现对数据场的等 值面的准确绘制。 体绘制传递函数设定方法的研究和应用 为了更好的提取物质边界设计传递函数，研究者提出在传递函数的定义域中 加入空间信息。h u a n g 等提出利用3 维的区域增长算法来辅助用户快速、准确的 提取物质的边界面设计传递函数l l6 1 。f a n g 等将2 维的图像处理操作，如灰度直方 图、平滑处理、边界检测算子等扩展到3 维数据场，并利用斜坡函数来设计透明 度函数。为了提高等值面的准确性，又提出对3 维数据场的灰度直方图进行多尺 度的平滑来提取多尺度的等值面【l7 1 。 1 3 3 图像中心法 为了提高传递函数设计的效率，研究者提出了图像中心法。图像中心法通过 对投影图像进行评估，自动的调节传递函数的参数直到得到满意的绘制效果。利 用图像中心法来设计传递函数关键是对图像进行评估以及如何有效的调节可视化 参数。 h e 等是最早运用这种方法来设计传递函数的研究者。他们把寻找合适的传递 函数过程看作一个参数优化的过程，并运用随机搜索技术来实现【l 引。首先随机地 产生大量的传递函数，然后用每个传递函数绘制出一个图像，并将这些图像提供 给用户挑选。用户选择较少的能正确显示体数据结构的绘制图像。这样，新一代 的图像就生成了。这个过程反复进行，直到用户满意为止。另外，在这个过程中， 除了用户根据视觉效果手工选择中间图像外，也可以运用目标函数的控制来自动 完成。这个方法不需要用户手工编辑传递函数，大多数情况下能成功地产生满意 的绘制图像，但并不能保证每次都能成功。f r a n c i s c o 等将遗传算法、边界检测和 手动调节三者相结合为用户提供一个半自动的传递函数设定工具1 1 9 1 ，系统初始时 将运用边界检测的方法计算出传递函数，用户可以手动修改传递函数，遗传算法 则是交互式的应用于该系统，由用户选择满意的图像。 设计长廊( d e s i g ng a l l e r y ，简称d g ) 系统【2 0 】由三菱电子研究中心和美国o h i o 大学开发。该系统提供所有可行的绘制效果，自动的产生和组织各种不同视觉效 果的图像，得到传递函数的所有可行解。系统根据传递函数的输入参数，尽可能 多的得到的输出，绘制出所有的投影图像，每个图像代表不同的传递函数设置。 这些图像排列在一个叫设计长廊( d o ) - - 维界面中，用户通过浏览这些图像选出最 好的绘制图像。因为需要绘制成千上万的图像，所以必须采用v o l u m e p r o 硬件加 速。该方法的难点是选择能产生不同输出的输入向量以及如何合理的组织输出的 结果来辅助选择传递函数。k o n i g 等采用与文献 2 0 1 相类似的策略，根据采样点的 数据值的取值范围穷举出各种可能的绘制结果，并用缩略图的形式将各种绘制的 结果排列成组，提供更加直观的体绘制系统【2 。该方法比文献 2 0 】具有更的扩展 性，可以对各种输入参数分别进行研究。 通过对人的感知能力的研究，在可视化中提高人机交互界面的应用受到愈来 4 硕十学位论文 愈多的重视，j a n k u n 等提出了一个以表格形式表示的界面，该界面以一个2 维的窗 口对应一个多维的可视化参数空间来让用户研究可视化的过程【2 2 1 。t o r y 等则提出 了一个基于并行坐标的界面来表示可视化参数空间【2 3 1 ，让用户比较不同的参数。 这些界面虽然功能强大，但由于操作过程复杂，用户未经训练，不容易掌握获得 感兴趣图像的技巧。一个简单且易用的体绘制工具，将会对用户设定传递函数有 很大的帮助。 1 3 4 对象中心法 为了更好的对数据场进行研究，近年出现了以对象为中心的传递函数设计方 法，该方法将传递函数的设计分解为：先对数据场进行分类，然后再对分类的结 果指定光学参数。 t z e n g 等提出用自组织迭代数据分析( i s o d a t a ) 算法对数据场进行分类【2 4 1 ， 并设计了直观、方便的用户界面使用户可以在簇空间中为分类的结果指定颜色和 透明度等光学属性，因此i s o d a t a 聚类算法将传递函数的定义域拓展到了簇空 间，强大的用户界面还允许用户对分类的结果进行修改和调节。然而i s o d a t a 算法对聚类参数敏感，降低了算法的实用性。s e r e d a 等提出分层聚类的思想，将 多种聚类规则相互融合提高了算法的灵活性，并在l h 直方图【lo j 的2 维空间中对 边界面分层聚类，最后根据多层次的边界信息设计传递函数【2 5 1 。 t z e n g 等提出采用神经网络来设计高维的传递函数【2 6 1 。人工神经网络通过训 练得到知识，然后利用获得的知识来解决相似的问题，它既可以学习线性关系也 可以学习非线性关系，功能非常强大。t z e n g 等为该算法开发了功能强大的用户交 互界面，首先由用户在数据场的部分切片上用不同的颜色分别绘制感兴趣和不感 兴趣的采样点，然后根据绘制的采样点训练神经网络得到分类函数。z h a n g 贝l j 采 用回归神经网络( g r n n ) 来设计传递函数【2 7 1 ，g r n n 结合了径向基函数网络和概率 网络的特点，将曲率幅值以及二阶方向导数矩阵的特征值作为神经网络的输入， 通过对输出的绘制效果进行评估来调节可视化参数，提供更好的分类结果和绘制 效果。除了神经网络，支持向量机( s v m ) 也被用来对数据场进行分类【2 引。s v m 是 一类较新的分类方法，该方法不仅将数据分成不同的类别，而且还保证类别之间 的距离最大。当给定的类在源数据空间中不能线性分离时，s v m 可以将数据从低 维数据空间中映射到高维特征空间中，然后在高维空间中用“最优分离超平面”对 数据进行线性分离。 除了利用智能算法来设计高维的传递函数外，k n i s s 等提出了用概率方法的 设计传递函数【2 9 1 ，定量的分析数据场。边界处的采样点常常会属于多个类，而系 统一般将采样点分给一个类，这将导致物质的边界不完整。概率的分类方法则可 以定量的分析出采样点属于某一类的概率，提高了分类的准确性。 体绘制传递函数设定方法的研究和应用 基于对象设计传递函数的第2 步是对分类的物质指定光学参数。h a u s e r 等提 出对不同的种类的物质设计不同的传递函数【3 0 l ，并根据感兴趣物质的特点采用不 同的绘制方法，同时，显示多种物质的内部结构，更好地表现了物质本身的特点 以及物质之间的相互关系。为了绘制数据场的剖面图，v i o l a 等提出了一种与视线 相关的可视化方法【3 1 1 ，根据感兴趣的程度对物质指定重要性，然后根据重要性来 确定物质的可见性的优先级。绘制的可见性可以通过调节透明度或者绘制方法的 稀疏程度来实现，最稀疏的绘制方法就是点绘制和线框模型，最稠密的绘制方法 是面绘制。 1 4 本文主要工作 本文的主要工作体现在以下三个方面： 首先，针对在单处理器上难以在有效的地时间内对较大规模的体数据进行聚 类分析从而设定传递函数的应用难题，设计实现了并行层次聚类算法，将其应用 于l h 直方图以指导传递函数的设定。实验结果表明与串行算法相比，并行层次 聚类算法具有更快的运算速度，能在理想的时间内对体数据进行聚类分析，并以 相同聚类效果完成对传递函数设定的指导，最终得到令人满意的图像，从而验证 了基于并行层次聚类算法的以对象为中心的传递函数设定方法具有较好的运算效 率。 其次，在深入分析进化算法用于体绘制传递函数设定领域的可行性和有效性 的基础上，基于粒子群算法提出了一种新的以图像为中心的传递函数设定方法。 该方法将粒子群算法以自动式和交互式两种实现方式应用于体绘制传递函数设定 领域，并且在交互式实现方式中提出了基于用户的速度更新策略。实验表明：无 论是自动式还是交互式实现方式，与遗传算法相比，粒子群算法具有更好的性能， 能使用户更快的得到更好的体绘制图像。并且，在交互式实现方式中，改进型粒 子群算法具有最快的效率。 最后，本文设计和实现了一个可扩展性强的地震数据可视化系统，“平台+ 插 件的软件开发模式和多种设计模式的应用使系统具有较低的耦合度和较高的可 复用性。系统中，将粒子群优化算法、手动调节和多分辨率显示功能三者相结合， 为用户提供了一个手动与自动相结合，并具有实时反馈功能的双层结构的传递函 数设定工具，使地球物理学家用户在探索地震数据的过程中更加灵活和便利，提 高地震勘探的精确度和成功率。 1 5 本文组织结构 全文分五章，本文的结构安排如下： 6 硕士学位论文 第一章概述了本文的课题来源，研究背景，研究目的及意义，主要工作及其 组织结构。 第二章详细的介绍了背景知识及相关研究，包括科学可视化，体数据，体绘 制，体绘制传递函数的分类和设定方法。 第三章介绍了l h 直方图，从层次聚类的五个方面，设计了并行层次聚类算 法，并将其与l h 直方图相结合，用于指导传递函数的设定，提高聚类算法在传 递函数设定领域的实用性。 第四章介绍了基本粒子群算法，提出了以自动式和交互式两种实现方式将粒 子群算法应用于以图像为中心的传递函数设定领域，并在交互式实现方式中对基 本粒子群算法进行改进，提高其指导传递函数设定的效果。 第五章介绍了地震数据可视化系统，并重点阐述了以多分辨率显示为基础， 将粒子群优化算法与传递函数手动调节工具相结合所设计的双层结构传递函数设 定方法。 最后是对整篇论文进行总结与展望。 1 6 本章小结 本章介绍了论文的选题背景和意义，阐述了传递函数设定方法的国内外研究 现状和本文的主要研究内容，最后给出了本文的组织结构。 7 体绘制传递函数设定方法的研究和应用 2 1 体绘制 第2 章体绘制传递函数 体绘制在一定程度上脱离了传统图形学点、线、面的束缚，对象不再是以点、 线、面等传统图形学表示形体的方法组成的三维实体，而是由体素作为基本的单 元，数据场是由大量的体素组成的。对于此类数据场的绘制方法不同于传统的面 绘制方法，它采用体光照模型直接从三维数据场中绘制出各类物理量的分布情况。 2 1 1 体数据 体数据可以看作是一个三维空间网格上的采样点集，每个采样点包含标量、 向量或者张量值。其来源主要有： ( 1 ) 测量数据：如医学数据包括计算机断层扫描、磁共振成象，超声、正电子 发射成像、单光子发射成像、x 射线。以及地震地质勘探数据、气象监测数据、 天文学射电望远镜获取的星云数据等。 ( 2 ) 科学计算或者仿真数据：如计算流体力学、有限元分析等， ( 3 ) 几何实体的体素化数据：如工业造型设计、游戏、及大规模地形可视化等 领域中将几何实体体素化所获取的数据。 体数据通常定义在空间网格点上，网格结构决定体元的基本形状，也决定体 元之间的相邻关系。网格结构取决于应用，对绘制具有很大的影响。按照采样点 之间的拓扑结构，体数据可以分成结构化数据、非结构化数据和混合型数据： ( 1 ) 结构化数据：对于结构化体数据，采样点之间在各维上存在确定而统一的 邻接关系。按其采样点之间的几何位置关系，结构化体数据可以进一步分为笛卡 尔型、等距型、矩形型和曲线型这四种类型，如图2 1 a ) d ) 所示。 ( 2 ) 非结构化体数据：这类数据中网格间的空间邻接几何关系需要另外提供， 体数据中除了必须存储体素的坐标信息之外，还要存储网格问的连接信息。采样 点之间不存在统一的邻接关系，不同的三角剖分算法将产生不同的邻接关系。有 限元分析和计算流体力学中体数据大多属于这种类型，如图2 1 e ) 所示。 ( 3 ) 混合型数据：在某些应用场合，一个体数据的一部分是结构化的，而另一 部分是非结构化的，从而形成了混合型数据，如图2 1 f ) 所示。该类数据主要出现 在跨学科问题中，如结构仿真数据和流体仿真数据的结合问题。 8 硕七学位论文 a ) 笛卡尔型b ) 等距型c ) 矩形型 d ) 曲线型e ) 非结构化 f ) 混合型 图2 1 体数据类型 2 1 2 体绘制算法 体绘制算法的作用就是将离散分布的三维数据场，按照一定的规则转换为图 形显示设备帧缓存中的二维离散信号，即生成每个象素点颜色的r g b 值。 虽然体绘制算法很多，但是基本步骤大致相同。如图2 2 所示。 ( 1 ) 数据生成：数据可以通过测量仪器或计算机数值模拟产生，比如医学图像 通过c t 和m r i 设备获得，而一些科学计算数据可以由计算机程序模拟产生，文件 格式可以自行定义。 ( 2 ) 数据处理：对于数据量过大的原始数据，需要加以精练和选择，以适当减 少数据量，又要最大限度的减少有用信息的丢失。当数据分布过分稀疏而有可能 影响可视化的效果时，需要进行有效的插值处理，也可以在这一步中对原始数据 进行噪声消除、参数域变换以及法向量计算等。 ( 3 ) 分类映射：这是整个流程的核心，分类映射会对最终的绘制结果产生非常 大的影响。其含义是将经过处理的原始数据转换为可供绘制的光学属性，如颜色、 透明度等。映射的含义包括可视化方案的设计，即需要决定在最后的图象中应该 看到什么，又如何将其表现出来。也就是说，如何用形状、光亮度、颜色以及其 它属性表示出原始数据中人们感兴趣的性质和特点。我们后面要介绍的传递函数 正是这里映射的方法。传递函数将数据值以及其它信息作为输入，将原始数据集 中的物质进行分类，输出每一类物质对应的颜色、透明度等光学属性，供下一步 绘制时使用。 ( 4 ) 绘制合成：将第三步产生的几何图素和属性转换为可供显示的图像。 一 般考虑所有体素对最终绘制结果的影响，并把他们合成在一起，生成结果图像。 9 体绘制传递函数设定方法的研究和应用 ( 5 ) 结果显示：包括图像的交互显示、几何变换、图象压缩、颜色量化、图像 格式转换以及图象的动态输出等。 图2 2 体绘制算法流程 体绘制算法主要分为两大类：图像空间扫描的体绘制技术和物体空间扫描的 体绘制技术。 图像空间扫描的体绘制技术是从图像平面上发出若干条光线，在每条光线上 采样得到很多采样点，将这些采样点对图像空间对应象素的贡献合成起来，得到 该象素的颜色，最终得到整幅图像。图像空间扫描的体绘制技术一般将所有体数 据放入内存，所以对内存容量要求高。进行点采样，走样相对明显。但是由于图 像空间比对象空间小得多，所以计算量较小。光线投射法是这一类的典型代表。 物体空间扫描的体绘制算法则不相同，它是对物体空间的数据网格，逐层、 逐行、逐个地加以处理，计算每一个数据点对屏幕象素的贡献，并加以合成，形 成最后的图像。物体空间扫描的体绘制算法只需当前单元的体数据，相对来说对 内存要求较低。另外，它一般可以得到解析解，这取决于重构核函数精度。不过， 对象空间比图像空间大得多，所以计算量较大。此类算法相对易于并行处理。这 一类算法包括：s p l a t i n g 体绘制算法，基于错切变形技术的体绘制算法和体元投 射法等。 2 2 传递函数 传递函数是体绘制过程中用以定出体数据与光学特征对应关系的关键步骤， 传递函数设定的好坏，对成像质量有着直接的影响。传递函数的设定，往往需要 大量的尝试和对绘制结果的观察，才能获得满意的成像结果或找寻出理想的传递 l o 硕七学位论文 函数。至今，体绘制算法的研究已经相当成熟，但传递函数设定的困难，影响了 体绘制在实际可视化应用中的发展。 在体绘制中，传递函数将3 维数据场的数据值转换为光学成像参数，建立了 采样点与光学特征的映射关系，决定了体绘制的成像质量。数学上，传递函数可 以定义为3 维数据场的数据属性到光学属性的映射【3 2 】： f ：d lx 皿巩专d lx o , ( 2 1 ) 式中，见伪= l ，2 ，) 是传递函数的定义域，表示三维数据场的数据属性。 数据属性是三维数据场自身的数值特征，它可以是采样点的数据值，如c t 图像 的灰度值，也可以是局部采样点数值计算的结果，如梯度幅值、二阶方向导数、 曲率等。d 所( 朋= 1 ，2 ，a t ) 是传递函数的值域，表示进行可视化的光学属性，如颜 色、透明度、阴影参数、反射率、折射率等【3 3 1 。f 表示数据属性转换为光学属性 的映射规则。通过传递函数的定义可知，三维数据场中具有某种数据属性的采样 点将以某种形式显示在二维图像中。设计传递函数就是根据可视化的需求，选择 和设计合适的数据属性和光学属性，并建立它们之间的映射关系。 2 2 1 传递函数的分类 2 2 1 1 一维传递函数 最简单和最通用的传递函数是一维传递函数，它只使用采样点的标量值一个 值。采样点的标量值是3 维空问中多种不同物质的测量结果，如c t 扫描数据， 或者是计算机数值计算的结果，如科学计算的数据。每个采样点标量值的大小取 决于数据的来源，具有一定的含意，可以用来区分不同的物质。例如，在人体的 c t 扫描图像中，对应于骨骼、肌肉和皮肤等不同密度的物质有不同的c t 值，在 c t 图像中表现为具有不同的灰度值，因此，可以根据灰度值来定义颜色传递函 数，利用色彩来表示不同的物质。 一维传递函数满足一个基本的要求，那就是终端用户易于理解传递函数的操 作，所以得到了广泛的应用。使用者只需要考虑采样点标量值和哪些不同水平的 透明度和颜色相关，它的速度很快，易于使用。 但是对于复杂的3 维数据场，仅仅使用标量值作为标准，不能很好的进行区 域隔离。因为在体数据内部，标量值和空间位置之间没有任何联系，同一种物质 往往具有不同的标量值，而具有同一标量值的采样点有可能属于不同的物质，一 维函数就不能正确解决这个问题。因此，用标量值设计传递函数仅仅只能处理简 单的3 维数据场，对于复杂的数据场需要设计更加复杂的定义域。 2 2 1 2 多维传递函数 为了克服一维传递函数的局限，一个很明显的解决方案是扩展传递函数引入 体绘制传递函数设定方法的研究和应用 多维，以下是几种常用的数据属性： 1 梯度幅值 体绘制时，通常假设同一种物质具有相似的标量值，不同的物质具有不同的 标量值，因此，在物质的边界处标量值将发生显著的改变，标量值改变的剧烈程 度可以用梯度幅值来度量。3 维连续空间中，梯度幅值的计算公式为 m = 挣+ ( 鼢参2 ( 2 2 ) 式中，0 v i l 表示“向量取模”，l e v o y 提出将梯度幅值作为传递函数的定义域， 控制不透明度，梯度值越大，表示越重要的物质边界面，赋予越高不透明度【3 4 】。 利用梯度幅值实现了物质边界面的可视化，在空间上更好地表示了物质之间的相 互关系。3 维数据场是由离散的采样点组成，因此采样点的梯度幅值是通过采样 点与邻近的采样点计算获得的。中心差分方法1 3 5 1 是最简单常用的梯度计算方法： o 耵i | _ ( 篆) 2 + ( 考) 2 ( a 笔) 2 ( 2 3 ) 2 高阶导数 高阶导数作为传递函数的定义域可以更准确的提取数据场中的特征。最常用 的高阶导数是梯度方向的二阶导数。在无噪声干扰的理想情况下，边界面的梯度 幅值为最大值，而梯度方向的二阶导数为o 。图像处理中的拉普拉斯算子就是通 过计算二阶导数的零点来检测边界。梯度方向的二阶导数的计算有3 种方法1 3 6 】： 第1 种是用梯度幅值的梯度来计算，在梯度幅值已知的情况下，该计算方法 较好。 厂2 酾1 v ( ) 耵 ( 2 4 ) 第2 种是基于海森矩阵的计算，式中，巧为海森矩阵，该方法计算准确，但 是计算量大。