（计算机科学与技术专业论文）基于小波变换的单机上大规模数据集体绘制的研究与应用.pdf

国防科学技术大学研究生院硕士学位论文 摘要 体绘制是科学计算可视化的重要手段之一，目前体绘制存在的问题主要是数 据量的巨大与计算机实现效率之间的矛盾。体绘制算法自身的复杂性与体数据的 庞大导致大规模体数据集实时、交互体绘制的实现仍十分困难，因此，大规模数 据集体绘制是国际上科学计算可视化领域的研究难点与热点。 本文主要针对数据预处理要解决的问题，系统地研究与分析了在单机上实现 大规模数据集体绘制的相关技术，提出了较好的基于小波变换的数据组织模型， 并通过采用改良9 7 小波而得到的新滤波器来进行体数据的变换，获得较好的效 果；同时在数据编码方面提出了基于块结构的深度优先二叉树数据编码方法，实 现了体数据集的有效组织，最后实现了集成上述两种技术的体绘制系统框架结构。 本文的主要工作以及取得的主要研究成果包括： 1 ) 提出了一种较好的体数据组织模型，不仅实现了数据的多分辨率分析，而 且对数据编码和内存缓冲等都提供较好的支撑，可以在有限资源的设备如单机 上实现数据的随机存取，获得较好的性能。 2 ) 改良经典9 7 小波滤波器系数而得到了新的滤波器，结合g p u 的强大并行 计算能力，弥补其计算开销，得到较好的效果，有效解决h a a r 小波在对数据 进行多次变换之后方块效应较明显的缺陷，并克服经典提升9 7 小波滤波器系 数是无理数而导致的计算难以实现等问题。新滤波器在保持数据低频压缩率以 1 8 的幂次递进倍增的前提下，获得了较好的绘制效果，并经过g p u 的硬件加 速，使其处理速度无论是在正向编码或是逆向解码中比经典提升9 7 小波快约 2 7 。 3 ) 提出了基于块结构的二叉树数据组织方法，针对实现多分辨率体绘制的目 的，把二叉树结构与小波系数之间的相关性自然衔接起来，有效地解决了体数 据经小波变换后的数据编码和调度问题，实现了数据的灵活调度、随机存取， 有效地缓解了i o 瓶颈，使得单机上的大规模数据体绘制得以高效实现。 4 ) 依照现代软件工程的目标和原则，构建了大规模数据集可视化框架结构， 给出了完整的包图和类结构图，明确了模块的功能，阐明了模块与模块之间的 关系。通过对框架结构的分析，说明了框架良好的功能及可扩展性和可重用性， 通过对框架结构的优化，进步提高了框架的运行效率。 主题词：大规模数据集可视化，体绘制，小波变换，体数据编码，二叉树， 单机 第i 页 国防科学技术大学研究生院硕士学位论文 a b s t r a c t d i r e c tv o l u m er e n d e r i n gi so n eo ft h em o s ti m p o r t a n tm e a n sf o ra n a l y z i n ga n d p r o c e s s i n gl a r g e - s c a l ed a t a s e t s 1 1 1 ep r i m a r yp r o b l e mo fd v r i st h em o a tb e t w e e nt h e l a r g e - s c a l ed a t a s e t sa n dt h ee f f i c i e n c yo ft h ei m p l e m e n t n l ec o m p l e x i t yo ft h ed v r i t s e l fa n dt h eh u g e n e s so ft h ed a t a s e t sl e a d st ot h ed i f f i c l u t yi nt h ei n p l e m e n to f r e a l t i m ea n di n t e r a c t i v ev i s u a l i z a t i o no fl a r g es c a l ed a t a s e t s s ot h ed v ro fl a r g es c a l e d a t a s e t sh a sb e c o m eah o tt o p i co fs c i e n t i f i cv i s u a l i z a t i o n w ew i l ld i s c u s st h et e c h o n o l o g yo ft h ei n p l e m e n to fd v ro ft h el a r g es c a l e d a t a s e t so nt h es t a n d - a l o n gm o s t l ya i m i n ga tt h ep r o b l e me x i s t i n gi nt h ep r e t r e a t m e n to f v o l u m ed a t a s e t s i nt h i sp a p e rw eb r i n gf o r w a r dag o o dm o d e lo fd a t ao r g a n i z a t i o n b a s e do nt h et h e s i so fw a v e l e tt r a n s f o r r na n dc o n s t r u c tan e wf i l t e rt ot r a n s f o r mo ft h e d a t a s e t sa c c o r d i n gt ot h ec l a s s i cl 9 7w a v e l e t m e a n w h i l e ，w eb r i n gf o r w a r daa r i t h m e t i c f o rt h ec o d i n go ft h ed a t a s e t sa f t e rt h ec o m p l e t i o no ft h ew a v e l e tt r a n f o r m i nt h ee n d ，a l a r g e - s c a l ed a t e s e td v rf r a m ew i l lb er e a l i z e di n t e g r a t e i n gt w om e t h o dw ep u t f o r w a r d e d t h ec o n t r i b u t i o n sa n dr e l e v a n tw o r ki nt h ep a d e ra r ea sf o l l o w s f i r s t l y ，ag o o dm o d e lf o rt h eo r g n i z a t i o no fv o l u m ed a t a s e t si sb e e np u tf o r w a r d t h i sm o d e ln o to n l yr e a l i z e st h em u l t i r e s o l u t i o nb u ta l s oo f f e rt h es u p p o r tt ot h ed a t a c o d i n ga n dt h em e m o r yb u f f e r s e c o n d l y ，w ec o n s t r u c t o ran e wf i l t e rb ye x p e r i m e n t si nt h ep r o c e s so fa n a l y z i n g t h ew a v e l e tl 9 7 n l ep o w e r f u lc a p a b i l i t yo fp a r a l l e lc o m p u t a t i o no fg p um a k e su pf o r t h ec o s t so fl 9 7 sc o m p l e x yc o m p u t a t i o n t h i sf i l t e rs o l v e sp r o b l e mo f t h ed e f a u l tw h e n h a a rt r a n s f 0 1 t i i ss e v e r a lt i m e sa n dc o n q u e r st h ed i f f i c u l t yo ft h ec o m p u t a t i o no ft h e c l a s s i cl 9 7 i tc o m p r e s s e st h ed a t a s e t sa tt h er a t eo ft h ep o w e ro f1 8a n df i n a lr e s u l to f t h er e n d e r i n gl o o k sb e t t e r a c c e l e r a t e db yt h ec p u ，t h i sm e t h o dr u n sf a s t e ra b o u t2 7 m o r et h a nt h ec l a s s i cl 9 7w a v e l e t t 1 1 i r d l y w ep u tf o r w a r dan e wm e t h o do fd a t ao r g a n i z a t i o nb a s e do nt h eb l o c k s t r u c t u r e a i m i n ga tt h em u l t i r e s o l u t i o no fd v r t h i sm e t h o dl i n k st h eb i n a r yt r e ea n d t h ew a v e l e tc o e f j f i c i e n t sn a t u r a l l y i ts l o v e se f f i c i e n t l yt h ep r o b l e m so fd a t ac o d i n ga n d t h ea t t e m p e r a t i o n t h i sm e t h o dl e a d st ot h er a n d o ma c c e s sa n ds o l e v e st h ep r o b l e mo f i oi nac e r t a i ne x t e n t f o r t h l y ，t h ep a p e rr e a l i z e do fa l lm e t h o dd i s c u s s i n ga b o v e f o l l o w e db yt h eg o a l s a n dt h ep r i n c i p i ao fm o d e ms o f t w a r ee n g i n e e r i n g ，w eb u i l dal a r g e s c a l ed a t a s e t v i s u a l i z i n gf r a m e a n di ti sas c a l a b l ea n de a s y r e u s e df r a m es t r u c t k e yw o r d s ：l a r g e - s c a l ed a t av i s u a l i z a t i o n ，d v r 。w a v e l e tt r a n s f o r m ，d a t a c o d i n g ，b i n a r yt r e e ，s t a n d a l o n e 第i i 页 国防科学技术大学研究生院硕士学位论文 表目录 表3 1 绘制成像质量对比3 9 表3 2 实验结果分析4 0 第1 v 页 国防科学技术大学研究生院硕士学位论文 图目录 图2 1 三维数据场的小波变换8 图2 2 采用q u i n c u n x 次序进行体数据的小波变换9 图2 3 体数据编码的基本流程图。9 图2 4 小波变换系数的层次结构图l o 图2 5 体绘制基本流程图13 图2 6 光线投射采样过程示意图1 4 图2 7 光线投射算法基本流程1 4 图2 8 改进的光线投射算法基本流程1 5 图2 9 采用包围盒方法的光线投射算法1 5 图2 1 0s p l a t t i n g 算法中的体素投射1 6 图2 1 1g p u 与c p u 近年性能提高情况对照图1 8 图2 1 2c u d a 架构中线程分配组织示意图1 9 图3 1 小波系数的分解2 4 图3 2 小波系数的多级分解2 4 图3 3 基于提升方法的正向小波变换流程图2 5 图3 4 基于提升方法的逆向小波变换流程图2 5 图3 5 小波变换实现信号的能量分2 7 图3 6 小波变换对体数据的三次分解2 7 图3 7h a a r 小波变换的滤波器实现2 9 图3 8h a a r 滤波器三次滤波示例2 9 图3 9s p l a t t i n g 算法绘制的体数据经小波变换后不同分辨率下效果图2 9 图3 1 0 提升小波分解正向过程3 2 图3 1 l 提升小波分解逆向过程3 2 图3 1 2 新滤波器实现过程。3 5 图3 1 3 实验程序流程3 6 图3 1 4 实验结果图一3 8 图3 1 5 实验结果图二3 9 图4 1 二叉树的五种形态4 1 图4 2 二叉树的顺序存储4 2 图4 3 二叉链表和三叉链表4 3 图4 4 数据划分与量化组织4 4 第v 页 国防科学技术大学研究生院硕士学位论文 图4 5i n s u n gl h m 提出的数据组织方案4 6 图4 6 本文提出的基于块的二叉树结构4 6 图4 7 分级细化文件组织4 7 图5 1 系统模块关系图5 0 图5 2 单机上基于小波变换大规模数据体绘制处理流程图51 图5 3 模式级的用例视图5 3 图5 4 带接口的模式级视图5 3 图5 5 系统关系详图5 4 第v i 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得 的研究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示谢意。 学位论文题目：基土4 1 遮变逸的望扭土太赶搓熬塑篡签绘剑的砑究生廛周 学位论文作者签名：压幽鬯l 日期： 少7年，2 月2 7 日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权 国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子 文档，允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 日期：刎7 年1 2 - 月2 7 日 日期：加7 年，乙月7 日 国防科学技术大学研究生院硕士学位论文 1 1 1 科学计算可视化 第一章绪论 1 1 课题研究背景 科学计算可视化【l 】是运用计算机图形学知识、数学理论和计算机相关技术，结 合具体领域的知识，将该领域实验数据或是测量数据进行处理，通过各种表现技 术将数据所包含的信息进行表达，并最终在计算机屏幕上显示或者进行交互处理 的理论、方法和技术。科学计算可视化( 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 ) 是人 类进行科学研究和探索的重要技术手段，无论是实验研究还是工农业生产，科学 计算可视化一直是不可或缺的工具，因此已经成为当今研究的热门领域之一。 在以前的科学研究中，往往需要处理大量的实验数据或者量测数据，浩瀚的 数据往往成为科学家进行分析和研究的一个难题。随着计算机图形学的发展与成 熟以及科研对科学数据可视化的需求，科学计算可视化自2 0 世纪8 0 年代末被提 出后，一直在快速发展，无论是理论还是技术，都在逐渐成熟和丰富。通过科学 计算可视化，可以将数据直观可视地表现出来，大大节省了研究者提取有效信息 的时间，显著提高研究效率，同时，一些不能通过数据发现的规律或者现象，也 能够通过科学计算可视化发现。当前，随着航天科学、气象、海洋科学、医学、 以及石油地质勘探等领域的发展，尤其伴随着计算机的性能的提高，大量的数据 等待研究和分析，由此决定了科学计算可视化的研究需求和必要性。 科学计算可视化将原始数据转换成在屏幕上像素点构成的图形，它的具体流 程包括的数据的采集与处理、映射、绘制和显示等过程。目前，科学计算可视化 主要的表现手段有等值面、流线、体绘制等等。科学计算可视化的发展和丰富与 计算机图形学的发展是密不可分的，但是它与传统计算机图形学不同之处在于， 科学计算可视化需要表现形式的丰富、美观和人性化，但它更侧重于对数据信息 表达的准确性和表达性。准确提取数据的有效信息并人性化地表现出来，帮助科 研人员有效进行数据的分析和交互处理，提高研究效率，是科学计算可视化的首 要目的。 1 1 2 体绘制 体绘依l j ( v o l u m n er e n d e r i n g ) 是科学计算可视化中重要的方法之一，它不构造中 间几何图元，而是直接由三维数据场产生屏幕上的二维像素。体数据是一系列包 含信息的3 d 点阵列，传统的等值面或者流线的可视化方法主要是通过对原始数据 第l 页 国防科学技术大学研究生院硕士学位论文 进行重构生成一些几何体元来对数据进行分析以获取信息。重构出几何体元的过 程会有大量信息的丢失，不能完整地传递原始数据所包含的信息，而且一些特定 的信息也是无法用等值面或者流线的方式进行表达和分析的，譬如云以及水汽等 物理值，其本身独特的存在发式决定了其表现方式的局限性。因此体绘制是一种 比较好的可视化技术，能够完整和如实直观地还原数据中所包含的原始信息。与 其他可视化手段相比，体绘制更能完整地产生三维数据场的整体图像，具有更高 的表达力和直观全面以及便于并行处理等优点，是气象领域、航天科学、地球科 学、海洋科学、制造科学、医学等领域以及工农业生产中实现科学数据分析的重 要工具之一。体绘制不仅能够直观地进行科学数据分析工作，而且可通过可视化 来能够帮助发现一些不能通过直接数据分析或者等值面和流线发现的许多规律和 现象，也就是说，体绘制的直观、方式多样以及有效性是其他可视化手段所不能 比拟的。 体绘制所处理的对象数据场，根据不同的划分依据可以做如下简要划分： 1 从数据值的属性来看分为标量数据场、矢量数据场和张量数据场。 2 从数据分布和拓扑关系来看包括结构化数据和非结构化数据以及混合数 据场。其中，结构化数据场是指有一定逻辑组织规律的三维数据场。非结 构化数据场是由一系列的单元构成的，但不能组织成三维数组的数据场， 非结构化数据场每个数据点的没有规则的空间位置和拓扑关系，需要另外 给出。混合混合数据场即为结构化与非结构化数据结合而形成的数据 场。 体绘制与科学计算可视化中其它手段等值面和流线不同，它不需要通过三维 数据场构造出中间几何图元，而是通过直接绘制的方法，将数据场直接映射到屏 幕。体绘制比其它可视化手段更具有直观性和全面性，它无遗漏地对整个数据场 进行表达，能最大化地保留数据信息。目前体绘制算法主要包括基于图像序列的 体绘制算法、基于物体空间序列的体绘制算法、混合体绘制算法、基于域转换的 体绘制算法等。 体绘制的在医学、气象学、海洋科学、工业制造以及地质勘探等诸多领域得 到了广泛的应用。在医学领域，由核磁共振、c t 扫描等设备产生的人体器官密度 场均为三维空间数据场，对于不同的组织，表现出不同的密度值，通过从多个方 面来表现病变区域，使医生对病灶部位的大小、位置等，+ 都有定性及定量的认识， 尤其是对大脑等复杂区域，可视化所带来的效果尤其明显。借助虚拟现实的手段， 医生可以对病变的部位进行确诊，制定出有效的手术方案，并在手术之前模拟手 术。在临床上也可以应用在放射诊断、制定放射治疗计划等。在气象领域，三维 数据场可视化技术可以将大量的天文气象数据转换为直观的图像，使预报人员能 第2 页 国防科学技术大学研究生院硕士学位论文 对未来的天气做出准确的分析和预测。在地质勘探领域，利用模拟人工地震的方 法，可以获得地震岩层信息。通过数据特征的抽取和匹配，可以确定地下的矿藏 资源。由于地震数据的数据量及其庞大，而且分布高度不均匀，因而根本无法从 纸面数据做出分析。利用可视化方法对模拟地震数据进行解释，可以得到矿藏是 否存在、矿藏位置及储量大小等重要信息，大大提高地质勘探的效率和安全性。 另外，体绘制还能表达出其它可视化手段所不能表达的信息。例如，在气象领域， 对云雾以及一些特殊自然体是无法通过等值面或者流线进行完整描述的，但是通 过体绘制就能形象直观的掌握整个数据场所表达的信息。综上所述，三维数据场 可视化具有重要的研究意义，是科学技术发展的重要研究方向。 科学计算可视化作为计算机图形学的重要分支，它的发展和丰富与计算机图形 学的发展是密不可分的，与其它分支不同，科学计算可视化不仅需要表现形式的丰 富、美观和人性化，而且更侧重于对数据信息表达的准确性和表达性。体绘制与 其他可视化手段相比，存在的最大问题就是计算的复杂向何计算量的庞大，准确 提取数据的有效信息并人性化地表现出来，帮助科研人员有效进行数据的分析和 交互处理，提高研究效率，是科学计算可视化的首要目的。如何在提高体绘制表 达信息的准确性和美观性的同时提高体绘制的效率是当前体绘制的研究熟点之 1 1 3 单机上大规模数据集体绘制 当前，随着微处理器技术的迅速发展，计算机的计算能力得到迅猛提高，系 统性能已经达到万亿拍的能力，在不久的将来，甚至能达到千兆拍的能力。在此 强大的计算能力支撑之下，天气预报、地球科学等等领域的仿真系统的实验数据 的产生呈几何级增长，因此，对数据分析和操控的难度和要求越来越高，而目前 我们对数据的管理和分析能力远远达不到数据的生产能力。导致这一结果的因素 是多方面的，其中最主要的原因是：一股数值仿真适合于大量批工作量的处理， 而数据分析却具有交互性，在数量上这两者之间就存在明显的差距；其次，从设 备上看，当前进行数据分析的速度瓶颈通常不在c p u 或者g p u 上，而是在这两 者之间的数据传输上。虽然微处理器的性能以摩尔规律增长，但是对于大量数据 集的传输起着关键作用的i o 带宽的性能的增长速率却是相对平缓，另外主存以及 磁盘的随机存取能力的发展也不是很快。 很明显，体绘制迫切需要解决的是数据量带来的庞大计算量与高效体绘制实 现之间的矛盾。当前，解决的主要手段是通过机群的并行技术，但是并行技术加 大了编程难度，而且对物体平台要求较高，存在复杂性和难普及性，因此在单机 上进行高效的体绘制，其所带来的便捷性和高效性对于科学数据可视化是具有较 第3 页 国防科学技术大学研究生院硕士学位论文 大意义的。 在普通p c 机上实现交互式的大规模三维数据的体绘制是当前科学计算可视 化研究的热门领域之一。个人p c 机普及很广泛，如果能够在之上进行高效的交互 式的三维数据体绘制，必然对科学数据可视化的广泛应用产生重大意义。另外， 由于p c 的显示区域及分辨率有限，对海量数据的较大尺度的显示时存在相对的数 据冗余，因此可以对数据进行合理的组织和安排，在不影响最终绘制的显示效果 的情况下将数据开销减少到最低，由于显示区域有限，在对整体进行分析的时候 采用低分辨率，并不影响观察效果，而对局部区域进行细节分析的时候则采用高 分辨率进行观察，这样，在结合现实条件的情况下，仍然得到最终的正确分析结 果，但效率却显著提高7 - t 4 j 。因此，基于单机的大规模数据体绘制是科学计算可视 化领域中具有较大价值的研究方向之一。 1 2 国内外研究现状 要实现普通p c 机上大规模三维数据的体绘制，就必须在速度上找到解决办 法。目前针对大规模数据的体绘制的绘制速度的提高提出了许多解决办法，按照 体绘制的流程来看，从数据预处理到体绘制算法再到g p u 的开发都有不同优化方 法及新的解决思路，本节主要从数据预处理和算法两方面对当前国内外的研究现 状进行介绍。 1 2 1 体数据预处理技术 体数据的预处理是可视化流水线中的开头环节，其重要性是不言而喻的，因 此，针对单机上的大规模体数据的体绘制，有效地组织和管理数据是非常重要的。 目前，为了减少计算的复杂性，不少体数据预处理技术被提出。 l i n s t r o m 和s i l v a 发明了o u t o f - c o r e 网格简化方法。网格简化方法能够在保留 表面的逼真度的前提下，大量地减少网格数量，并且能满足逐次显示，但是它们 需要较长的预处理时间，而且如果需要全解析率显示时，需要另外存储原始数据。 另外，除了减少网格数量，对于后面的绘制环节就没有较大了的益处了1 3 j ，更不能 帮助灵活地控制数据。l e v o y 通过层次分解，使用八叉树以方便地跳过透明度为零 的区域，从而加速光线投射法；i h m 和p a r k 提出了3 d 小波压缩策略【1 4 j ，能够允 许对数据的随机存取，这是第一个能实现对数据随机存取的方法；r o d l e r 提出一 种用视频编码的方法【l 引，将三维体数据看成一个2 d 的面片集，对这些面片采用视 频编码的方法，而且对每一个面片内部采用2 d 小波变换，该方法还允许对任意体 元的获取。g u t h e 2 l j 等等还针对交互式进行大规模数据的体绘制提出了一个较为完 第4 页 国防科学技术大学研究生院硕士学位论文 整的方案，提出了基于小波压缩而构建的八叉树的数据组织模型，再以此数据组 织模型为基础，针对数据压缩、绘制、缓冲、投影分类等等各个阶段提出优化策 略。另外，还有一些常用的数据简化办法，例如c i g n o n i 等等和w i l h e l m s 、v a n g e l d e r l 2 2 】提出了一种使用层次逼近的方法去以变化的解析率表示数据集的常用的 策略。c i g n o n i 等等是通过一个经过粗糙化的初始近似值的连续四面体改良来生成 离散数据的多分辨率表达。虽然c i g n o n i 的方法除了支持规则网格之外同样还能 支持非规则化网格，但是，它不能保留粗糙化表达的规则性，即使它是存在于原 始数据中。w i l h e l m sa n dv a ng e l d e r 的逼近策略不是基于小波理论，它开发了小数 目的基本函数去重构域。z h o u 2 0 】的方法是基于四面体的，但是它介绍了基于四面 体的另一种体系，与c i g n o n i 有所不同，因为它用过二次采样避免了插值，因此， 他们的方法更加有效( 该方法只能用于规则网格) ，而且，z h o u 的算法保留了连续 性，因此避免了裂缝问题的产生。而上述这些方法却又是大部分都是集中在c p u 和内存上，不支持区域子集化，而且对存储要求很大。p a s c u c c i 和f r a n k 1 7 】开发了 另一种数据组织策略，这种策略非常善于提供渐次数据存取，但是这种数据组织 策略并不是基于小波理论，而是基于填充曲线( f i l l i n gc u r v e s ) 1 1 1 】，通过仅仅重组织 数据存储的布局来改进数据子集化的效率和细节层次存取。这些方法没有改变数 据，因此是可逆的。但是，较粗略的分辨率必需由最近临采样生成，从而导致了 较差的重采样结果。 大规模规则网格数据集的层次表示模式有很多优点，建立层次模型所需要的 数据策略有多种类型，要达高效且能够提供逐次的数据存取以调节速度与质量的 权衡，当前，针对数据编码具体的层次结构一般采用二叉树或者八叉树。 小波变换的多分辨率特性，对可视化有着独特的自然便利性，采用基于小波 的数据压缩方法去构建一个层次数据模型是较好的方法，不仅能够对数据进行无 损压缩，逐次显示，算法可逆，而且还能够数据传输的瓶颈问题，快速高效地实 现对数据的随机存取。 1 2 2 体绘制算法 体绘制算法研究现状 体绘制算法【2 】是近年来迅速发展起来的一种三维数据场可视化方法，有多种算 法被提出以及优化。其主要分类有基于图像序列的体绘制算法、基于物体序列的 体绘制算法、基于域的体绘制算法以及混合体绘制算法等。光线投射算法一直是 体绘制景点算法之一，其成像质量高，但是其速度较慢，目前常用的改进基本上 是基于g p u 硬件加速【7 】【8 】【2 1 1 。s p l a t t i n g 算法成像速度快【3 3 】，一直是大规模数据体 绘制的常用算法，不少研究人员对s p l a t t i n g 的重构核进行研究【5 1 ，改进其投射边缘 第5 页 国防科学技术大学研究生院硕士学位论文 颜色溢出或者跳跃的缺点，另外，s h e a r w a r p 也是目前较活跃的体绘制算法之一。 体绘制与并行技术研究现状 针对大规模体数据集存储困难的问题，p h i l i p 等提出了可视化桌面投递方法， 建立了远程可视化系统平台，实现了可视化服务器与用户的分离，使用户远程使 用可视化服务器以及远程办公成为可能。可视化桌面投递技术又分为原始数据投 递、几何数据投递以及像素投递三种方式，三种方法投递的内容不同，导致对于 传输带宽、传输数据大小等的要求各异，适用于不同的需求。 当前对于大规模体数据集的可视化目前常采用并行处理绘制技术，经典的并 行绘制技术主要有s o r t f i r s t ，s o r t m i d d l e 和s o r t l a s t 方法，三种方法都基于图形 绘制流水线技术，广泛应用于大规模体数据集的绘制与显示过程中。 由于海量数据往往需要进行高分辨率显示，因此国内外通常采用多通道显示 环境实现图像的高分辨率显示。多通道显示墙是一种大尺寸、高分辨率、低成本、 高性能的可视化设备，它能将复杂的数据以图形图像的形式在高度沉浸感的显示 环境中实时展现出来，是虚拟实验室和可视化应用环境的重要组成部分。 1 3 论文结构 全文共分六章： 第一章为绪论，主要介绍论文的研究背景与意义，阐述了国内外在大规模 体数据的预处理和体绘制算法等方面的研究现状。最后对论文工作与研究 成果进行了总结。 第二章介绍了有关单机上实现大规模数据场体绘制的相关技术。主要从数 据的处理方法上分有损数据压缩和无损数据压缩进行阐述，并介绍了体绘 制比较常用的算法及其优化。 第三章对基于小波变换的数据预处理方法进行了研究。首先介绍了小波基 础理论，并阐述了提升9 7 小波基的推导过程；研究了小波变换在数据预 处理中的应用，并采用h a a r 小波为例进行了论述：接下来针对h a a r 小波 函数在多级变换中的信息提取能力弱而导致绘制效果差的问题，引进了经 典提升9 7 小波，并改进了滤波器系数而得到了一种新的滤波器，不仅运 算开销低于经典小波变换，而且成像效果好。最后，采用g p u 进行加速， 提高新滤波器的速度并对一个较大规模的时变三维医学数据场进行了实 验，结果证明新滤波器的综合性能要高于h a a r 小波函数、经典9 7 小波 函数以及s p l i n e 小波函数，能够在实现多分辨率分析的同时获得了好的压 缩效果。 第四章提出基于块深度优先二叉树编码方法，对基于小波变换的三维数据 第6 页 国防科学技术大学研究生院硕士学位论文 场产生的小波系数进行科学编码，实现编码与解码的高效，并能灵活管控 数据以及实现数据的随机存取。 第五章提出了一个基于小波变换的单机上大规模体绘制的实现框架，系统 地描述了体绘制在该框架下的绘制流程，结合合理的文件组织方式和基于 c u d a 的加速方案，对框架结构进行优化，使得框架具有实用性和高效性。 第六章为结束语。总结了论文主要工作，并对未来工作进行了展望。 1 4 论文研究成果 本文完成的主要工作和取得的主要研究成果包括： 介绍了体绘制的基本流程和常用的体绘制算法，针对体数据预处理所要用 到的一些方法和概念进行了较详尽的阐述，并提出了一种基于小波变换的 数据处理方案。另外，对于小波变换的基本原理进行了阐述，并结合体数 据预处理的相关问题对小波基的选取原则进行了讨论。 对经典提升9 7 小波进行了改良，通过实验修改了其滤波器系数，得到新 的滤波器，经实验结果检验，新的滤波器在实现多分辨率分析的同时获得 了较好的压缩效果。 将深度优先的二叉树编码方法推广到三维体数据场，提出了基于块的深度 优先二叉树编码方法，对小波系数进行合理编码和组织，实现编码与解码 的高效，从而实现对数据的高效管理和随机存取。 以本文所提出的体数据处理方案，对单机上基于小波变换的大规模数据体 绘制进行了系统框架的设计与实现。 第7 页 国防科学技术大学研究生院硕士学位论文 第二章大规模数据集体绘制相关技术研究 体绘制一直是科学数据可视化的研究热点之一，基于单机的大规模数据体绘 制更是具有挑战性的方向之一，因此，围绕体绘制的高效高质实现一直进行着各 个方面的研究。目前，基于小波变换的数据预处理技术得到广泛应用【9 】【1 2 】 1 4 】，其 多分辨率分析思想以及较好的可操作性使得越来越多的体数据预处理研究集中在 基于小波变换的数据预处理技术上【1 5 1 。本章对与基于小波变换的单机上大规模数 据体绘制联系较紧密的相关技术做一些介绍，包括基本的体绘制算法、基于小波 变换的数据编码技术以及硬件方面的优化。 2 1 体数据预处理 目前，主存或磁盘的随机存储能力的发展还不是很快，外围存储与主存之间、 主板与图形加速器之间的传输速率仍不够理想，所以，要解决单机上大规模数据 场体绘制的效率问题，尤其是需要进行快速或者实时传输以及大量存储时，数据 的组织非常重要。本节结合三维数据场的小波变换对基于小波变换的数据压缩和 编码技术【1 7 】f 1 8 】【2 3 1 进行讨论。 2 1 1 体数据基本压缩方案 在计算机上实施的离散小波变换，就是根据利用小波函数，将数据的能量进 行重新分配，即数据按照低频和高频进行二进分解，这样将原始数据一分为二。 将变换依次在三个坐标轴方向进行将体数据进行，得到一次变换的小波系数，其 一次分解过程如下图所示： l 0 0 h 0 0 x 方向变羧y 方内变换z 方向变换 图2 1 三维数据场的小波变换 如此完成一级变换之后，然后逐级反复进行类似变换，根据需要将原始数据 生成多级显示，如下图所示为变换级数n 为3 时的小波分解过程( 图中l 表示低 频，h 表示高频) ： 第8 页 国防科学技术大学研究生院硕士学位论文 为： 图2 2 采用q u i n e u n x 次序进行体数据的小波变换 接下来就对变换得到的系数进行编码，无论是哪种编码算法，其编码流程图 图2 3 体数据编码的基本流程图 进行小波变换后所得的小波系数需要进行合理的处理，在变换完成之后，需 要进行量化，然后采用熵编码。一般来说主要有以下几种压缩方案 1 6 】： 采用有损压缩的思想，由于体数据中的主要信息体是低频部分，因此在不 要求精确重构原始数据的情况写可以舍弃高频部分之保留低频部分，如上 图所表示的变换结果中，可以只保留低频部分l l l o ，达到1 3 2 的压缩比； 完成小波变换之后，保留低频部分，选取一个全局阈值，用于各级高频系 数，或者对不同级别的变换系数采用不用的阈值，将低于阈值的值全置零， 从而达到压缩目的。 将小波系数按照一定次序排列，只保留某范围内的系数，将剩余的系数置 零。 以上是采用有损压缩的方法，但是在存储空间足够的情况下或者需要精确重 构原始数据的情况下，将小波变换系数进行合理编码，可以实现数据的精确重构， 其压缩体现在低级分辨率上。下面介绍几种基于小波变换的编码算法。 2 1 2 三维数据场e z w 编码算法 嵌入式零树小波编码简称为e z w 算法，是s h a p i r o 在1 9 9 3 年针对零树编码产 生的孤立零点的情况而提出的改进算法口6 1 。它的基本思想是：对于取定的一个阈 值7 ，若小波系数x 满足h 丁，则称x 关于r 是重要的系数，否则关于r 是不重 第9 页 国防科学技术大学研究生院硕士学位论文 要的系数；若x 是不重要的系数，并且它的所有子孙都是不重要的，则称x 是关于 丁的零树根；如果x 本身是不重要的系数，但它存在重要的子孙，则称x 是关于丁 的孤立零点。将小波变换后的各子带组成成树状结构，如图2 4 所示： 羹一 一誓l l 一l 一 l ( 2 七) 3 一矿个单元块 口j 口口 口j 口口 口0 口口 口口口口 图2 4 小波变换系数的层次结构图 对于给定的阈值对数据进行量化后，采用以下方法从下往上( 从父级到子级) 进行扫描，而且各个层级是有序逐级扫描的，每个层级间也是有序扫描的。每次 扫描包括以下步骤【2 6 】： 1 选择阈值 如果各变换级的阈值取值不同，那么对n 级小波变换选择z ，z ，正来 确定小波系数的取舍。其中乃= 霉一l 2 ，i 为扫描次数，总数为n 1 次。选 择初始阈值的方法是：瓦：2 【1 0 8 2 船机 i j ，其中q ，七是第n 级小波变换的变 换系数。 2 主扫描 按照从父级到子级的扫描次序，将小波系数与该级的阈值进行比较，用主 扫描表记录一些视为已处理的元素：p 表示正的重要元素，n 表示负的重 要元素，t 表示零树根，z 表示孤立零点。扫描结束后，将输出符号为p 和n 的相应位置加标记或者置零，下次主扫描时跳过它们。 3 辅扫描 对主扫描表进行顺序扫描，对其中输出符号为p 或者n 的小波系数进行量 化。量化器的构造方法是将输入间隔 z 叩2 r , 一1 ) 等分成两个量化区间 z _ l 1 5 巧一1 ) ，若系数在区间 巧- l 1 5 巧一1 ) 中，则输出量化符号“0 ”，重 第1 0 页 国防科学技术大学研究生院硕士学位论文 构值为1 2 5 t _ f l ，否则输出量化符号“1 ”，重构值为1 7 s t , 一l ，输出的量 化符号由一个辅扫描表纪录。 4 重新排序 为了便于设置第i + 1 次扫描所用的量化间隔，以提高解码精度，对输出符 号为p 或n 的对应的数据进行重新排序，将幅值在 1 5 z l ，2 石一1 ) 中的数据 排在幅值在区间 t - l , 1 5 互一1 ) 的数据之前。 5 输出编码信号 编码完成后输出两类信息：一类是给解码器的信息，包括阈值、主扫描表 和辅扫描表；第二类是用于下次扫描的信息，包括阈值及第4 步中重新排 列过的重要系数序列。 e z w 算法的解码过程是e z w 编码的逆过程，主要步骤包括：接收编码器发 送的解码信息、设置阈值、构造逆量化器、解读编码器输出位流中包含的位置信 息和小波系数信息。 嵌入零树小波编码综合应用了离散小波变换技术、零树编码技术、累进逼近 技术和自适应算法编码技术，具有较好的性能。 2 1 3 三维数据场s p i h t 编码算法 s p i h t 编码算法( s e tp a r t i t i o n i n gi nh i e r a r c h i c a lt r e e s ) 是对e z w 算法的改进 1 2 7 2 s 】，是目前为止影响最大的小波压缩算法之一，它能够生成一个嵌入位流，使 接收的位流在任意点中断时，都可以解压和重构图像，因而具有很好的渐进传输 特性。s p i h t 可以获得较好高的峰值比较高的峰值信噪比( p s n r ) ，同时具有计 算复杂度较低、位速率容易控制等优点。 s p i h t 算法采用的零树结构与e z w 的相似，但是它在系数子集的分割和重要 信息的传输方向上采用了独特方法，将小波系数按照能量大小或者重要性程度编 码输出，隐藏了扫描路径，其具体方法是：任何排序算法的执行路径都是使用分 支点的比较结果进行定义的，如果解码器和编码器使用相同的排序算法，则对于 编码器使用的系数比较结果，解码器通过执行相同的路径就可排序信息。 s p i h t 编码过程如下【2 6 】【2 7 】： 1 对构建树结构 s p i h t 树结构中每个节点对应一个小波系数，而且用坐标来标识节点 或对应的系数。在对三维数据场进行小波变换所生成的系数中，最低频子 带中的系数和最