（计算机应用技术专业论文）shearwarp算法的改进(1).pdf

山东大学硕士学位论文 摘要 本文主要基于c t 医学断层数据来研究三维体绘制算法。三维体绘制算法是 直接将体数据按一定的采样和映射规则合成，生成的图像具有更丰富的表现力。 三维体绘制算法是当前研究的一个热点，被广泛应用于医学图像、c h d c h m 造 型、工业设计、资源探测、虚拟现实等信息可视化领域。因此对三维可视化的研 究，具有重要的学术意义和应用价值。 s h e a r w a r p 算法是被认为基于软件加速的最快的体绘制算法。本文主要对 s h e a r w a r p 算法的绘制质量和绘制速度两方面进行了深入的研究和探讨。 在绘制图像质量方面，s h e a r w a r p 算法为了取得较快的绘制速度而牺牲了图 像质量。当用s h e a r w a r p 算法进行绘制图像时，视线角度过大会使绘制生成的图 像出现明显的波纹失真现象。主要原因是由于在重采样的过程中采样距离过大， 违背t n y q u i s t 采样定理，使得利用重采样的数据点无法恢复原来的数据信息。 针对这个缺点，本文提出了一种消除s h e a r w a r p 算法中波纹失真现象的新方法： 基于插值逼近原理，先利用沿着主视方向相邻的四个原始采样点构造二次曲线； 然后在构造的二次曲线上获得新采样点，再将新采样点添加相邻两层体切片之间 来提高采样精度，达到消除波纹失真的目的。文中给出了加层原理、具体实现算 法以及算法复杂度的分析。当然，在采用该方法改善绘制图像质量的同时，会影 响到算法的绘制速度和消耗的空间。如何取得整体效果最佳的改进方法是我们以 后要继续研究的问题。 在绘制速度方面，s h e a r w a r p 算法是最快的基于软件的体绘制算法，它对数 据场和生成的图像采用一种巧妙的编码方式，在绘制的过程中，同时遍历数据场 和图像，跳过数据场中透明的体素和图像中不透明的区域。这样大大加快了绘制 速度。s h e a r w a r p 是在单核c p u 基础上，完全基于数据结构对算法的一种改进， 与硬件完全无关。但是最近几年，随着多核c p u 的普及，多核c p u 在多任务处理 和并行计算上体现出单核处理器无法比拟的优势，多核c p u 逐渐取代单核c p u 成 为桌面和移动计算机的主流配置。因此针对多核c p u 对体绘制算法进行速度优化 十分必要。本文利用多线程、向量化运算等技术加速s h e a r w a r p 算法，充分发挥 多核c p u 的特点，使其能够适应当前c p u 的发展趋势，被更广泛的应用推广。 山东大学硕士学位论文 本文利用c t 医学断层数据对改进后的s h e a r w a r p 算法进行了实验，实验结果 表明，改进后的算法不论在图像质量方面还是绘制速度方面都取得了显著的改 进。 关键词：s h e a r - w a r p 算法波纹失真二次曲线插值多核c p u a b s t r a c t t h em a i nr e s e a r c ho f t h i st h e s i si so nt h ed i r e c tv o l u m er e n d e r i n g ( o v r ) b a s e d o nt h ec tv o l u m ed a t as e t s a c c o r d i n gt ot h ec e r t a i ns a m p l i n ga n dr e n d e r i n gr u l e s ， d i r e c tv o l u m er e n d e r i n ga l g o r i t h md i r e c t l yr e n d e rt h ev o l u m ed a t at og e ta n1 r n a g e d v r i so n eo ft h en 的s ti m p o r t a n tt e c h n i q u e si nt h ef i e l do fi n f o r m a t i o nv i s u a l i z a t i o n 、珈i c hi s 嘶d e l vu s e di nm e d i c a li m a g e ，c a d c a mp r o t o t y p i n g ，i n d u s t r i a ld e s i g n , o i l a n dg a se x p l o r a t i o mv i r t u a lr e a l i t ya n ds oo n s ot h er e s e g x c h o nd v ri sv e r y s i g n i f i c a n ti na c a d e m i aa n d p r a c t i c e s h e a r 唧a l g o r i t h mh a s b e e nr e c o g n i z e d a s t h ef a s t e s ts o f t w a r e 。b a s e d r e n d e r i n gm e t h o d t h i sp a p e rm a i n l y d o e ss o m er e s e a r c ho nt w oa s p e c t so f s h e a r w a r p ：t h er e n d e r i n gq u a l i t ya n d t h er e n d e r i n gs p e e d h lt h er e n d e r i n gq u a l 畸a s p e c t ，s h e a r - w a r pa l g o r i t h ml o s st h eq u a l i t yo f t h e i m a g ef o ri m p r o v i n gr e n d e r i n gs p e e d t h eb i gv i e wo r i e n t a t i o na n g l e w i l lc a u s e s e r i 0 1 l ss t a i r c a s m gp h e n o m e n o ni nt h ef i n a li m a g ew h e nw e r e n d e rt h ev o l u m ed a t a s e tb ys h e a r - w a r pa l g o r i t h mt h ep r i m a r yc a u s ei st h a tt h er e s a m p l i n gd i s t a n c e 1 ss 0 1 0 n gt h a tv i o l a t et h en y q u i s tt h e o r e mi nt h er e s a r n p l i n gp r o c e s s s ot h er e s 鲫叩l m g d a t aa r e 眦a b l et or e s t o r et h eo r i g i n a ld a t am e s s a g e i nt h i sp a p e rw e b r o u g h tan e w n l e t h o df o rr e m o 沛gt h es t a i r c a s i n gp h e n o m e n o n b a s e do nt h et h e o r yo f m e r p o l a t i o na n da p p r o x i m a t i o n , aq u a d r a t i cc u r v ei s c o n s t r u c t e df r o mf o u ro r d i n a l o 堍i n a ls a m p l i n gp o i n t sa l o n gt h ev i e w i n go r i e n t a t i o n an e w r e s a m p l i n gv o x 。i l s o b t a i n e d 舶mt h eq u a d r a t i cc t l l w e t h e nan e ws l i c e i sc o n s t r u c t e db e t w e e n 啪 o r i g i n a ln e i g h b o r i n g s l i c e ss ot h a tt h es a m p l i n gp r e c i s i o nc a nb ei m p r o v e d b a s e do n t h en e ws a m p l i n gs l i c e s ，s t a i r c a s i n gp h e n o m e n o nc a nb e r e d u c e di ns h e a r - w a 印 r e n d e r i n g i nt h ep a p e rw ew i l ls h o wt h ea d d i n gs l i c e sp r i n c i p l e ，t h es p e c i f i ca l g o r i t h m a 1 1 dt h ec 0 唧l e 妯ya n a l y s i s s u r e l y , w h a tw ed ot oi m p r o v et h ei m a g eq u a l i t yw i l l 世i e c tt h er 印d e r i n gs p e e da n dc o n s u m em o r es p a c e h o w t og e tt h eb e s te f f e c to ft h e a l g o r i t h mi ss t i l lo u rf u r t h e rr e s e a r c h h lt h er e n d e r i n gs p e e da s p e c t ，s h e a r - w a r pa l g o r i t h me m p l o y e da c l e v e rv o l u m e a n di m a g ee n c o d i n g s c h e m e , 一c o u p l e d w i t h a s i m u k a n e o u s t r a v e r s a l o f v o l u m e a n d _ _ 一一一 t lf 东大学硕七学位论文 i m a g et h a ts k i p so p a q u ei m a g er e g i o n sa n dt r a n s p a r e n tv o x e l s t h i sw i l ls p e e du pt h e r e n d e r i n gs p e e d s h e a r - w a r pi st o t a l l yb a s e do nt h ed a t as t r u c t u r e st od os o m e i m p r o v e m e n t st h a th a v en o t h i n gt o d ow i t ht h eh a r d w a r e b u tr e c e n t l y , a st h e m u l t i - c o r ep r o c e s s o ri sm o r ea n dm o r ep o p u l a r , i tb e c o m e st h em a i ns t r e a mp r o c e s s o r i nc o i l l l l o np ca n dn o t e b o o k t h em u l t i c x ) r ep r o c e s s o rh a si n c o m p a r a b l ea d v a n t a g e s t os i n g l e - c o r ep r o c e s s o ri nt h ea s p e c to fm u l t i p r o c e s s i n ga n dp a r a l l e lc o m p u t a t i o n i t sv e r yn e c e s s a r yf o rt h ev o l u m er e n d e r i n ga l g o r i t h mt ob eo p t i m i z e db a s e do n m u l t i - c o r ec p u i nt h i sp a p e rw eu s em u l t i - t h r e a da n dv e c t o r i z a t i o nm e t h o d st o a c c e l e r a t et h es h e a r - w a r pa l g o r i t h mw h i c hm a k ef u l lu s eo ft h em u l t i - c o r ec p u c h a r a c t e r i s t i c s t h a t 础e si tp o s s i b l ef o rt h es h e a r - w a r pa l g o r i t h mt ob e c o m em o r e a n dm o r ep o p u l a r i nt h i sp a p e r , w ed os o m ee x p e r i m e n t so nt h ei m p r o v e ds h e a r - w a r pa l g o r i t h m 、析t hc tv o l u m ed a t as e t s t h ee x p e r i m e n tr e s u l t ss h o wt h ee f f i c i e n c yo ft h e i m p r o v e m e n t so nb o mr e n d e r i n gq u a l i t ya n dr e n d e r i n gs p e e d k e yw o r d s ：s h e a r - w a r pa l g o r i t h m ，s t a i r c a s i n gp h e n o m e n o n ，q u a d r a t i cc u r v e ， i n t e r p o l a t i o n ，m u l t i - c o r ep r o c e s s o r i v 原创性声明和关于论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：圭璺盗鱼 日 期：丝2 ：垒： 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：童目透逸 导师签名： 日 期：2 翌2 ：垒芏 山东大学硕士学位论文 第一章前言 1 1 医学图像三维可视化技术概述 上世7 0 年代以后，伴随计算机x 射线断层投影( c o m p u t e dt o m o g r a p h y ，c t ) 、 核磁共振成像( m a g n e t i cr e s o n a n c ei m a g i n g ，m p 4 ) 、超声波成像( u l t r a s o u n d i m a g i n g ，u s ) 等先进的医学成像技术的发展，使得人们可以得到人体及其内部器 官的二维数字断层图像序列。但是二维断层图像只是表达某一截面的解剖信息， 在医学治疗过程中，仅由二维断层图像上某些解剖部位进行简单的坐标叠加，不 能准确的得到三维影像，这就会造成病变部位的定位的失真与变形。因此，为了 提高医疗诊断和治疗的准确性，需将二维断层图像序列转变成为具有直观立体效 果的图像，以展现人体器官的三维结构与形态，从而提供若干用传统手段无法获 得的解剖结构信息，并为进一步模拟操作提供视觉交互手段。医学图像三维重建 与可视化技术就是基于这一要求而提出的。它是医学影像处理与分析技术的一个 重要分支【1 。5 1 。 计算机体视化及医学体数据三维重建技术的研究是伴随着影像技术和计算 机软硬件技术的发展而发展起来的。7 0 年代，由于受当时计算机断层扫描技术 发展水平的限制，切片的厚度和切片之间的间距都很大，因此早期的研究工作主 要集中在轮廓连接的表面重建。这一时期，三维重建的基本思想己初步建立起来， 但由于当时计算机的存储量还比较小，c p u 的运算速度比较慢，因此处理大容 量的多层医学图像显得力不从心，而且图像显示质量比较低。 8 0 年代是三维体视化技术迅速发展的年代。在这十年中，各种影像技术不 断出现，如核磁共振成像、超声、正电子辐射断层摄像( p e t ) 和单电子辐射断层 摄像( s p e c t ) 等影像技术逐渐成熟，他们能产生高分辨率低噪声的三维图像。此 外，计算机的性能大幅提高，计算机图形学技术也不断成熟，这些都极大的促进 了体数据三维可视化技术的发展。在这一时期，研究人员提出了大量优秀的算法， 使三维显示的速度和显示质量都取得了巨大提高【3 j 。 9 0 年代三维重建技术逐渐趋向实用化，相继出现了一些成熟的产品，临床 应用越来越广泛。三维医学图像较之二维图像有着无可比拟的优势，它可以为医 生提供直观、清晰的器官和组织的三维结构信息，辅助医生准确、科学的确定病 1 i i 东大学硕十学位论文 变体的空间位置、大小、几何形状以及与周围组织之间的空间关系，这些使得三 维医学图像在医疗诊断、手术规划与模拟、放射治疗、医学教学和研究中发挥重 要作用。目前，国外三维重建技术的研究正朝着与临床应用结合，与虚拟现实技 术结合以及专用三维显示硬件等几个方向发展。国内在这方面的研究始于9 0 年 代，目前己经有了一些产品，但由于三维重建技术的研究成本高，周期长，而且 在医学方面上的应用要求非常高，这些都制约了该领域在国内的发展。因此，开 展三维重建方面的研究，具有重要意义。 1 2 医学图像三维可视化存在的问题 医学体数据三维可视化方法分为两大类：表面绘制方法和体绘制方法。表面 绘制方法的主要优点是计算量小，运行速度快，可以实现实时显示，但必须通过 图像分割，由于目前缺少准确有效的分割方法，导致生成图像的保真性较差。目 前己有许多科研人员在从事这方面的研究，但至今还没出现一种可靠的分割分类 方法适用于任何数据。由于分割是一个不适定性问题，不可能存在一种全自动的 分割方法把分割问题彻底解决好，人工干预是不可避免的。体绘制方法通常不要 求做精确的分割，而是对体数据场中的每个体素分别进行处理，合成具有三维效 果的图像。因此，体绘制方法对噪声有一定的韧性，适合于对形状特征模糊不清 的组织和器官进行三维可视化。此外，体绘制方法中不透明度的引入大大增强了 数据整体显示效果。 然而，由于体绘制方法要处理大量的数据，很难实现图像的实时显示。例如 美国国立医学图书馆实施了一项可视人体的项目( v i s i b l eh u m a np r o j e c t ，v i - w ) ， 该项目具体由科罗拉多大学实施，对人体进行了大规模的扫描和数据采集，所得 的数据共5 6 g b ，称为v i s i b l eh u m a n 共享的数据集。如此庞大的数据量就对体 绘制算法的速度和质量提出了很高的要求。因此，改进软件算法，提高绘制速度， 成为体绘制方法研究中的核心课题。 解决这课题主要可以从以下三个方面入手： 第一，在医学体数据三维可视化技术的发展过程中，计算机硬件水平始终是 一个关键的制约因素。尽管计算机速度、内存容量以及其他图像加速设备的发展 日新月异，但是面对庞大的医学体数据，可视化速度始终难尽人意。所以提高计 2 l l j 东大学硕士学位论文 算机的硬件配置将有利于提高体绘制的速度。 第二，在医学体数据三维可视化过程中，要研究采用尽可能快的重建算法。 以此来提高重建的算法和效果。 第三，大规模科学和工程计算问题对计算机的速度提出了非常高的要求。在 图像处理方面，大规模的地形匹配、神经网络计算及其它计算量大的任务都需要 计算机具有强大的计算性能。近年来，微处理器性能不断提高，高速局域网不断 发展，可以利用相对廉价的微机通过高速局域网构建高性能的并行机群计算系 统。与传统的超级计算机相比，并行机群计算系统具有较高的性价比和良好的可 扩展性，可以满足不同规模的大型计算问题。 医学体数据三维可视化算法性能主要是从绘制速度和生成三维图像的质量 这两方面来评价的。绘制速度一般是以绘制一组体数据所消耗的计算时间或每秒 钟显示帧的数目作为定量衡量指标的。而生成图像的质量却难以定量评价。准确 的说，三维可视化生成的图像不是自然图像，而是通过计算机合成的，合成过程 中的参数是用户根据视觉需要选取和调整的，所以对于图像质量很难找到一个明 确的、切实有效的衡量指标。目前主要的标准是人的视觉感受，这虽然是一个主 观的评价标准，无法定量表示，具有很大模糊性，但却有其合理性，因此也是最 常采用的标准。 一般来说，图像的质量越好，精确度越高，则绘制时间越长，事实上，不同 在评价一种算法的性能时不能完全脱离其适用环境，提高算法性能应当是根据应 用的具体需求，在图像质量与绘制速度间进行折衷，在保证一定质量的前提下尽 可能的提高绘制速度，或者在达到一定速度的基础上尽可能的改善图像质量。 1 3 本文的主要内容及创新点 本文主要介绍多种体绘制算法来实现三维重建。由于s h e a r w a r p 算法是目 前公认的最快的体绘制算法，所以本文的主要工作是对该算法进行了较为深入的 研究，提出了一些新的改进思想，取得了较好的效果。概括起来，本文的主要工 作有： 1 对s h e a r w a r p 图像的质量进行改进：分析s h e a r w a r p 算法产生波纹失真 的原因。然后基于插值逼近原理，先利用沿着主视方向相邻的四个原始采样点构 3 山东大学硕士学位论文 造二次曲线；然后在构造的二次曲线上获得新采样点，再将新采样点添加相邻两 层体切片之间来提高采样精度，达到消除波纹失真的目的。文中给出了加层原理 和具体实现算法，以及算法复杂度的分析，通过实例比较说明新方法在消除波纹 失真上的有效性。 2 对s h e a r - w a r p 的绘制速度进行改进：随着多核c p u 的普及，多核c p u 在多任务处理和并行计算上体现出单核处理器无法比拟的优势。本文利用多线 程、向量化运算等技术加速s h e a r w a r p 算法，充分发挥多核c p u 的特点，使其 能够适应当前c p u 的发展趋势，被更广泛的应用推广。 1 4 各章节安排 第一章简单介绍当前三维重建技术的发展现状以及存在的问题。并对本论文 的主要工作进行了概要总结。 第二章介绍了传统的体绘制方法。对体绘制的光照模型、体绘制的分类进行 了详细阐述，并介绍了几种体绘制的加速方法。 第三章详细讲述了s h e a r w a r p 方法。阐述了s h e a r w a r p 算法的基本原理， 具体实现、加速的技巧，并对算法的复杂性进行了分析。 第四章对s h e a r w a r p 图像质量的改进进行了深入的研究和探讨。分析了 s h e a r w a r p 算法产生波纹失真的原因，阐述了消除波纹失真的新方法，并对改进 后的s h e a r - w a r p 算法的复杂性进行了分析。 第五章介绍了对s h e a r w a r p 的绘制速度的改进。根据多核c p u 的特点，讲 述了利用多线程、向量化运算等加速方法，并对加速前后的绘制时间进行了比较。 第六章总结了本文所提出改进方面的优缺点，并对未来进行了展望。 4 山东大学硕士学位论文 第二章传统的体绘制方法 对于三维数据场6 11 7 1 ，根据图像表达的方式，其成像方法通常可分为面绘制 方法( s u r f a c ef i t t i n g ) 、直接体绘制方法( d i r e c tv o l u m er e n d e r i n g ) 两大类【引。 使用面绘制方法，首先对整个体数据进行等值表面分割定义，接着用各种几 何元拟和表面，最后绘制出所有的几何元。在医学图像可视化中常用的几何原有 体素级大小的平面多边形、多边形网格、三角片等。代表性的面绘制方法是等值 面法。该方法主要适用于在体数据中显示等值面。其特点是计算量大，但可以用 来显示高质量的图像。典型的等值面算法是移动立方体法( m a r c h i n gc u b e s ) ，它 把原始体数据的体素逐个进行处理，把物体边界体素转换为很细密的便于计算机 图形硬件绘制的多边形网格。边界表面的拓扑结构由上下相邻断层的8 个体素确 定的逻辑立方体来限制。当给定一个门限值，逻辑立方体体内的具体位置由8 个 体素的灰度值插值来确定。移动立方体等值面连接方式上存在二义性问题，可能 会造成等值面连接的错误。对等值面连接问题的进一步研究引出了其他改进算 法，如分解立方体( d i v i d i n gc u b e s ) 、m a r c h i n gt e t r a h e d r a 方法1 9 1 。 直接体绘制法把体素当作基本元。认为体素是一种本身既可发光又可吸收光 线的半透明物质，体绘制时根据体素的灰度值对每一体素赋予不透明度值( 阻光 度，o p a c i t y ) 和颜色值，再根据各体素的灰度梯度及光照模型( ! t n p h o n e 模型) 计 算出各体素的光照强度，然后将投射到图像平面上同一像素点的各体素的不透明 度值和颜色值综合在一起，形成最终的三维图像。这种算法产生的图像，可以包 括每一个细节，具有图像质量高，便于并行处理等优点。被广泛应用于医学断层 图像的三维重建等领域。 本文主要是针对直接体绘制算法进行研究。因为直接体绘制是一种重要的可 视化方法。它不使用中间面的几何数据，而是直接将体数据按一定的采样和映射 规则合成，具有更丰富的表现力。与基于多边形的面绘制相比，体绘制具有数据 类型特殊、存储量大、绘制方法多样、计算强度高等特点。所以本文中所指的体 绘制未经说明都是指的直接体绘制。 山东大学硕士学位论文 2 1 体光照模型 由于体绘制方法要反映光线在三维数据场中所穿过路径上的所有体素的物 理学的性质，因此他的光照模型1 0 1 与仅反映面的性质的表面光照模型有很大的差 异。目前体绘制方法中，主要有源一衰减( s o u r c e a t t e n u a t i o n ) 模型、变密度发射 ( v a r y i n g - e m i t t e r s ) 模型以及材料分类及组合( c l a s s i f i c a t i n ga n dm i x r a t e ) 模型。 2 1 1 源一衰减模型 源一衰减模型【1 1 1 为每一个体素分配一个源强度和衰减系数。当光线通过空间 时，按每个体素的源强度及光线沿距离的衰减分配一个亮度值投射到图像平面上 形成结果图像，图像上每个像素的亮度是连接视点与该像素中心的光线所穿过的 所有体素在屏幕上投影的贡献之和。其计算公式为 一+ 曲， j = i 【s ( t ) e x p ( - lm ( p ) d p ) 】折 ( 2 1 ) 一一曲 其中s 是体素的源强度，m 是衰减系数。由于源衰减模型建立在精确的物理方 程的基础上，有较可靠的数学基础，因而成为最常用的体光照模型。但可以看出 它的公式形式比较复杂，不宜理解和使用。因而应用中常把公式( 2 1 ) 写为如下 形式吲： n - if - i ，= c ，q 兀( 卜哆) ( 2 2 ) i = 0 j o 其中g 是采样点i 的颜色值，是采样点i 的不透明度。这也是本文所有体 绘制算法使用的像素光亮度计算方程。 2 1 2 变密度发射模型 变密度发射模型1 3 1 将表达云、烟等雾状自然景观的粒子系统用于体数据显 示，它假定体空间中充满了粒子云，粒子均可发光，这样就构成了粒子光源系统。 在空间每一点的一个小的闭合体元中，均定义一个无量纲的粒子密度。在由某视 点观察体数据时，每一粒子所发出的光能在向视点传播的过程中被其他粒子散射 掉一部分，到达视点的光强是衰减后的光强。可沿视线积分求出各粒子云对像素 6 山东大学硕上学位论文 光亮度的贡献，从而得到体数据的可视化图像。 2 1 3 材料分类及混合模型 在一些领域的体数据中，每一采样点上常对应多个物理量，如有限元分析的 数据中包括应力及应变，医学图像中每一体素可能包含骨、软组织及脂肪等。若 要同时观察这些量，则首先需要把体数据表达为各种材料所占的百分比，此百分 比可以直接输入或用最大似然分类法求得。对不同材料分别计算其密度分布及其 色彩和不透明度，根据密度分布函数可提取不同材料的分界面，再进行光照计算。 由于同时考虑了材料分界面及不同材料的分布，因而可得到体数据的全局图像。 2 2 体绘制方法的分类与比较 体绘制方法并不生产等值面，而是给数据场中的体元赋予一定的色彩和透明 度，由光线穿越半透明物质时能量集聚的光学原理，进行色彩合成的成像操作。 体绘制算法可根据所用的投影策略不同加以分类1 4 1 ，大致可以分为以下四大类： 1 图像空间扫描的体绘制技术光线投射体绘制算法 光线投射体绘制算法( r a y - c a s t i n g ) 1 5 1 1 6 1 是m l e v o y 于1 9 8 8 年提出的，该算 法是基于图像空间扫描实现体绘制的经典算法。其算法为：图像平面的每个像素 都沿着视线方向发出一条射线，且此射线穿过体数据集，沿着这条射线选择k 个 等距采样点，并由距离某一采样点最近的8 个数据点的颜色值和不透明度值作三 线性插值，求出该采样点的不透明度和颜色值，最后将这条射线上的各采样点的 颜色及不透明度值由前向后或由后向前加以合成，即可得到该像素的颜色值，形 成最终的可视图。一般地说，该方法可以方便地利用光照计算生成细腻的可视图， 但速度较慢。在非规则场中应用比较普遍。 光线投射法的主要步骤： f o r 每条光线d o f o r 每个于光线相交的体素d o 计算该体素对图像空间对应像素的贡献 2 物体空间扫描的体绘制技术 物体空间扫描算法 1 1 9 1 是对物体空间的数据网格，逐层、逐行、逐个的加以 7 山东大学硕十学位论文 处理，计算每一个数据点对屏幕像素的贡献，并加以合成，形成最后的图像。体 数据可以按照距图像平面由近到远的顺序投影，也可以按照由远到近的顺序进行 投影。目前，国内外已经提出了许多物体空间扫描的体绘制算法，下面介绍比较 常用的四种： ( 1 ) 足迹表法( f o o t p r i n tm e t h o d ) 足迹表法【2 0 1 又称s p l a t t i n g 方法，和图像空间扫描的体绘制算法一样，足迹表 法首先需要对数据进行分类，根据分类结果赋以颜色值及不透明度值，并进行明 暗计算，从而得到一个离散的三维光强度场。将其重构为连续场，并决定每一个 三维采样点对屏幕像素点有所贡献的范围。某一个像素点的最终光强度值可以通 过对像素点有所贡献的全部采样点重构核的空间卷积域作积分求得。因此总的积 分次数将等于三维采样点数乘以重构核空间卷积域的平面投影区域内的像素数。 显然这一计算量是相当大的。足迹表法正是为了解决这一问题而提出来的。其目 的在于快速决定在任意观察方向三维采样点重构核空间卷积域的平面投影域及 对每个像素的贡献大小。其步骤为首先选择重构核，预计算通用足迹表，然后将 体数据转换到图像空间，查表找出体素对于像素的贡献值，最后合成图像。 对于光线投射法来说，当观察方向改变后，就需要重新采样并进行插值运算， 而对于s p l a t t i n g 方法，若视线方向发生变化，就需要重新计算重构核空间卷积域 的椭圆投影，投影中的每个像素都需进行旋转和比例变换，以便查找通用足迹表， 因此针对以上问题提出了错切变形( s h e a r w a r p ) 算法2 1 1 2 2 1 。 ( 2 ) 基于错切变形技术( s h e a r w a r p ) 的体绘制算法 该算法将三维视觉变换分解成三维错切变换和二维的变形变换。体数据按照 错切变换矩阵进行错切，投影到错切空间形成一个中间图像，然后，中间图像经 变形生成最后的结果像。这种算法最重要的特点就是按照主要的视线方向( x ，y ， z ) 选择切片数据集和投影数据，当视线的方向发生变化后，投影方向不一定变化。 其优点为当不透明转换函数保持不变时算法速度很快。但是，不透明转换函数每 转变一次需要重新给体积编码，每一个主要的观察轴需要一个编码体积。z 轴采 样率由于错切而变化，因此总是违反t n y q u i s t 定理，同时导致了对角线视角的 梯级伪影，只有由前向后没有由后向前的遮蔽，视线模糊、陡直上升。 ( 3 ) 体元投射法 8 山东大学硕士学位论文 前面讲过的图像空间扫描的光线投射法，是通过逐条处理由屏幕像素点发出 的光线而得到最终图像的。在足迹表法及投影变换的错切一变换等物体空间的扫 描的体绘制算法中，则是通过逐点计算二维离散采样点对屏幕像素的贡献而得到 最终图像的。以上算法的一个不足之处在于没有利用三维空间中相邻的采样点之 间的空间相关性来减少计算量。所谓空间相关性指的是三维空间中相邻的采样点 往往有着相同或相近的函数值，或者说，大多数相邻的采样点的函数值变化不大。 体元投射 2 1 是基于这个目的而提出的。 ( 4 ) 子区域投射法 前面介绍的体元投射法利用了体元内部函数值的相关性，与逐一处理每条射 线的光线投射法及逐点投射采样点的足迹表法相比较，趋势减少了计算量，且对 体元较大的数据场较为有效。但是，在体元投射法中，屏幕上任何一个像素的光 强度值，都是将多个体元分别计算得到的结果再合成后得到的。即使多个体元具 有相同的颜色值和不透明值也是必须如此。显然，计算量是与数据场的大小成正 比的。也就是说，体元投射法并没有利用各体元之间函数值分布的相关性。子区 域投射法【2 4 1 【2 5 1 正是针对这一问题而提出的。 由于基于图像空间的体绘制算法比较容易理解，各种加速方法和提高图像质 量的方法比较多，目前应用的数量比较多、范围比较大。但基于对象空间的体绘 制方法直接存取体数据，不存在类似基于图像空间的体绘制方法那样的因采样数 据而产生的走样，它逐个切片的处理体数据，所以能够十分方便地优化体数据的 存储( 压缩、索引、存储分块) ，以避免不必要的体数据遍历。在预处理阶段就可 以为数据的投影做加速准备( 优化足迹表、设计各种合适的数据结构) 。上述的优 点决定了以后的研究方向主要集中在基于对象空间的体绘制算法。 3 频域体绘制技术 与光线投射方法和投影成像方法不同，频域体绘制技术瞄】1 2 7 1 不是在空间域 进行操作，而是先利用f o u r i e r 变换，将三维的数据场空间转化为三维的频域空 间，然后由频域的切片原理可知，过频域中心且垂直某个方向的二维切片经过反 f o u r i e r 变换所得的图像，就是沿该方向进行光线投射方法或投影成像方法所产 生的可视图。虽然该方法产生频域空间时开销较大，但频域空间与视点无关，可 以反复使用，而由频域空间的二维切片获得三维数据场空间的可视图，则更体现 9 山东大学硕士学位论文 曼曼曼曼鼍鼍曼寡量曼鼍鼍i i i 喜量暮皇曼皇曼曼曼喜鲁曼曼曼曼詈皇曼曼曼曼曼曼曼曼曼曼曼鼍曼曼曼曼曼曼皇曼曼曼曼曼曼曼毫曼皇皇曼曼曼曼曼! ! 曼量皇曼曼曼曼量曼量烹曼皇 了该方法的优越性。但该方法所生成的可视图不能反映空间域中色彩合成时的遮 挡关系，使观察者难以判断物质分布的前后关系。 4 纹理映射硬件支持的直接体绘制 利用三维纹理映射技术，在进行三维规则数据场的直接体绘制时，首先应将 数据值进行分类，并按照给定的转换函数将每个数据点转换为相应的颜色值及不 透明度值，形成三维纹理图。其次，在确定了观察方向之后，给出被绘制数据场 中的采样点与纹理空间坐标的映射关系。最后，在纹理空间中进行重采样，并按 照从后往前的顺序进行图像合成，以形成最终图像。所谓三维纹理映射的硬件实 现是指在纹理空间中实现重采样的插值运算及具有不透明度值的图像合成等均 由硬件完成，从而大大提高了运算速度。目前，能提供这种功能的图形工作站中 常用的是s g i 公司的r e a l i t ye n g i n e t 2 8 1 。 纹理映射7 1 的优点为硬件能快速进行体积大小排列，没有断续的影响。然而， 每一个视角都需要计算切片平面必须有高速的终端硬件支持才可以。不管是二维 还是三维的硬件纹理映射方法都不能立即计算明暗，输入的纹理必须进行明暗预 处理，多纹理函数使得每个像素的明暗和分类变得可能。 直接体制方法，可以将数据场中的多种分类物质在一张可视图中显示，揭示 它们的相互关系。但由于缺乏棱角明显的中间几何图元的表达，其可视图通常比 较模糊。常常要从不同角度观察多幅可视图，才能对数据场有较好的认识。而且 计算量很大。 2 3 体绘制的加速方法 体绘制需要对整个体数据进行处理，计算量巨大。所以医学体数据三维可视 化的关键问题是图像的质量和绘制速度，通常只能是在两者之间折中。如何快速 的绘制体数据场，一直是可视化技术的研究热点。目前有五种主要的方法加速体 绘制：通过提取模型来对体数据进行简化；实现特殊目的的体绘制引擎；基于软 件算法的优化；使用并行计算；使用图形加速卡。这里，将主要介绍基于软件算 法的优化。 目前最有效的软件加速技术是利用空间数据结构来减少处理过程中需要计 算的体素数量，从而减少重建过程中的计算量。现在主要加速算法有以下两种： 1 0 山东大学硕士学位论文 提前光线终止和八叉树法。 2 3 1 提前光线结束 光线穿过一个不透明体素( 见图2 - 1 ) ，合成的方向有从前到后及从后到前 两种方式1 2 1 皿1 1 。设光线穿过体素前颜色和不透明度分别为g ，穿过体素 后为气，埘，体素的颜色和不透明度为q ，q 。那么从前到后的光线合成计 算公式为： jc 删a 叫= c 加a 加+ c v a 1 a 加)( 2 3 ) 【0 f 叫= 口加+ 口，( 1 - 口加) 、 。 当光线的不透明度值累积到 一定程度之后，例如达到一个阈 值，这时再对后面的体素进行合 成已无意义，所以有必要提前结 束光线。这种加速思想就叫做提 前光线结束，可以很方便的采用c 一，口 到以图像为序的体绘制方法中图2 - 1 光线穿过不透明体素 去。 2 3 2 八叉树 体的八叉树表示是一种层次数据结构【3 2 1 。首先在空间中定义一个能够包含所 表示物体的立方体。立方体的三条棱边分别于x ，y ，z 轴平行，边长为2 ”。若立方 体内所有体素均为不透明体素，则物体可用这个立方体表示。否则将立方体等分 为八个小块，每块仍为一个立方体，其边长为原立方体边长的1 2 。将这八个小 立方体依序编号为0 ，1 ，2 ，7 ，如图2 - 2 所示。若某一立方体内的体素均 为不透明体素，则该立方体标识为“f u l l ；若体素均为透明体素，则该立方体 标识为“e m p t y ”；否则标识为“p a r t i a l ”，并继续分割下去。依此方式，体可 以表示成一个八叉树。 山东大学硕士学位论文 将透明体素尽可能归结在一 起，以便在绘制中快速略过，这 是八叉树方法加速的基本原理。 利用八叉树可以快速略过大片透 明体素，所以八叉树方法在以对 象空间为序的绘制方法中得到了 广泛应用。下面是在绘制过程中 的具体应用。首先检查原始立方 体的标识，若为“f u l l ”，这是 图2 2 将大立方体剖分成8 个小立方体 最坏情况，只能依次遍历所有体素，因为没有一个体素是透明的；若为“e m p t y ”， 这是最好情况，全都是透明体素，不需要绘制；通常情况为“p a r t i a l ”，在这 种情况下需要依次遍历它的八个子立方体，将标识为“e m p t y ”的立方体略过， 将标识为“f u l l ”的立方体依次处理，将标识为“p a r t i a l ”的立方体按同样方 法遍历它的子立方体。 除了上述两种典型的加速技术外，还有许多的加速技术被提出，其中大多数 是利用体数据的数据一致性，采取类似八叉树的方法对物体分层存储。这些加速 办法都依赖于具体数据。 1 2 1j 东大学硕士学位论文 第三章s h e a r - w a r p 方法 s h e a r - w a r p 算法是被认为基于软件加速的最快的体绘制算法，在没有图形加 速器的情况下在普通台式电脑上可以取得秒数量级的重建速度。该算法能够取得 这样的速度主要是因为它高水平的算法优化。 s h e a r - w a r p 算法的平行投影算法由f k l e i n 和g g c a m e r o n 提出1 2 2 1 ，1 9 9 4 年p l a c r o u t e 将该算法应用于体绘制，取得了良好效果，而且将它推广到了透 视投影。基于s h e a r - w a r p 算法，目前已对不同的应用提出多种改进。在本文的 研究中，主