（计算机应用技术专业论文）基于面绘制的虚拟内窥镜系统.pdf

浙江大学硕士学位论文 摘要 虚拟内窥镜技术是随着计算机图形学、图像处理、医学可视化和虚拟现实等学 科的发展而逐步形成的一种独特的技术。它克服了传统内窥镜需要插入人体体内的 缺点，是一种完全无接触式的检查方法。 本文对虚拟内窥镜的起源、原理、优点、发展、应用作了一个较为全面的综述， 介绍了虚拟内窥镜系统的技术组成。在此基础上，对部分关键技术进行了研究和探 索。 m a r c h i 几gc u b 鹪是三维表面重建的经典算法。本文详细阐述了该算法的原理 和过程，并应用扩展的m a 吣h i n gc u b e s 算法解决了二义性问题。为了提高算法的 效率，本文在区域增长的基础上，设计了一张邻接共用表，提出了一种优化方法， 避免了对空体素的不必要检测和相邻体素共用等值点的重复计算。由于m a r c h i n g c u b e s 算法抽取等值面构建的表面模型所包含的三角面片数量巨大，难以实现实时 绘制显示。本文采用基于顶点删除的网格简化算法。运行实例表明，三角面片大量 化简后，依然能保持原模型的特征和较好的视觉效果。 在路径规划方面，深入研究了拓扑细化算法，在事先建立查找表思想的基础上， 提出了一种结合最小堆和区域增长的快速中心路径抽取算法。为了保持漫游过程中 的连续性，用c a r d i n a i 三次样条曲线对中心路径进行了平滑处理。 在导航交互方面，用虚拟探头来模拟传统内窥镜的各种行为，实现了人工、自 动和交互三种漫游方式。为了逼真地模拟用传统内窥镜进行医疗检查时的一些约束， 利用抽取中心路径时得到的各体素点距器官表面的距离值，提出了一种简单、快速、 有效的表面碰撞检测方法。 关键词：虚拟内窥镜三维表面重建网格简化路径规划虚拟漫游 浙江大学硕士学位论文 图1 1 光导纤维内窥镜图1 2 电子内窥镜 电子内窥镜是继光导纤维内窥镜之后的新一代内窥镜，主要由内窥镜、电视信 息系统中心和电视监视器三个主要部分组成( 图1 2 ) 。它的成像主要依赖于镜身前 端装备的微型图像传感器，其作用就像一台微型摄像机，将图像经过图像处理器处 理后，显示在电视监视器的屏幕上。与普通光导纤维内窥镜相比，电子内窥镜图像 更清晰，色泽更逼真，分辨率更高，而且可供多人同时观看。 随着技术的发展，内窥镜应用越来越广泛，但它属于一种侵入式的检测手段， 病人受到的痛苦比较大，并有可能发生严重的剐作用，像穿孔、感染、出血等。除 了给病人造成痛苦之外，这种技术还依赖于操作者的技术经验及病人的配合程度， 经验不足或是配合不好都会对检查质量产生较大影响。个别体质敏感的病人甚至因 身体的不适应反应而无法进行检查。 1 1 2 医学图像的三维可视化 医学图像成像是另一种有效检查人体内部肿瘤的方法，像计算机断层扫描( c t ) 及核磁共振( m r i ) 等。但这些医疗仪器绝大部分只能提供人体内部的二维断层图像。 医生只能凭借经验由多幅二维图像去估计病灶的大小和形状，想象病灶与周围组织 的三维几何关系。这种方法极大程度地依赖于医生的主观想象和临床经验，缺乏直 观性和准确性。因此，自9 0 年代起，医学图像的三维可视化技术成了国内外计算机 研究与应用的热点。 医学图像的三维可视化技术【3 】f 4 】就是指利用一系列的二维断层图像重建三维图 像模型并进行定性定量分析的技术。该技术可以从二维图像中获取三维的结构信息， 浙江大学硕士学位论文 而且为医生提供更逼真的显示手段和定量分析工具。三维医学图像可视化技术作为 有力的辅助手段能够弥补影像成像设备在成像上的不足，能够为用户提供具有真实 感的三维医学图像，便于医生从多角度、多层次进行观察和分析，并且能够使医生 有效地参与数据的处理分析过程，在辅助医生诊断、手术仿真、引导治疗等方面都 可以发挥重要的作用。 虚拟内窥镜( v i r t u a le n d o s c o p y ) 睁哪技术结合了上述两者的优点，利用医学图 像的三维可视化技术，将通过c t 和m r i 获得的二维断层图像进行三维重建，从而显 示出身体内部结构，然后再用虚拟现实的手段，在三维内部空腔进行漫游，模拟传 统内窥镜的各种行为。和传统的内窥镜技术相比，虚拟内窥镜有其独特的优点：虚 拟内窥镜为无接触式检查，具有无创性，避免了传统内窥镜技术给病人带来的痛苦， 检查过程中也不会产生像穿孔、感染或出血等副作用：医生可以从不同角度和方位 对病灶进行观察，并能同时提供内外腔的情况，有助于发现更多的病灶信息；虚拟 内窥镜比传统技术有着更加广阔的适用范围，理论上讲，身体任何部位都可以用虚 拟内窥镜进行检查，些重要的器官，像心脏、内耳、大的动脉等，都是虚拟内窥 镜理想的重要模拟对象；此外，同一个数据可以针对不同的漫游计划把虚拟内窥过 程重复任意多次，降低了医疗检查的复杂性、危险性和医疗成本；它还可以指导病 人了解自己的病情，也可用于教学目的。 1 。2 虚拟内窥镜 1 2 1 虚拟内窥镜的国内外发展现状 虚拟内窥镜在医学领域是一种新兴的技术，主要起源于数字医学成像如c r 和 m r i 图像的可视化，特别是由于1 9 9 4 年v i s i b l eh 蛐1 锄数据集的出现，使研究取 得了较大的发展。 9 0 年代中期，有人提出虚拟现实技术在医学上的应用。而后，随着计算机性能 的大幅度提高，探测手段的进一步发展，虚拟内窥镜技术受到了更多的关注。很多 研究机构、医疗单位在进行临床实验。目前的研究方向主要有：更加真实地重建内 浙江大学硕士学位论文 部器官的三维结构，使其不仅能反映大体情况，还要反映出复杂的表面结构：增强 交互功能；改进算法，如寻找更好的路径规划方法，进行组织自动分割。 欧美发达国家及日本比较关注该技术的研究。目前，美国通用电气公司开发出 一套虚拟内窥镜后期处理平台一r t u a l e n d o s c 叩y m e d i c a l a p p c a t 蛔n 【1 0 l ，包括虚拟 结肠镜检查、虚拟支气管镜检查、虚拟血管检查等。斯坦福大学开发了一套多视图 广角虚拟内窥镜系统【1 1 1 ，采用多视图显示技术，建立了一种模拟在内腔飞行的虚拟 座舱，解决了因照相机视场相对较小造成的视图变形的问题。w b s tf 0 r 鹉t 大学的虚 拟内窥镜研究中心开发了一套名为f r e e r i g l l d l 2 l 的虚拟内窥镜软件系统。纽约州立 大学s t o i l yb r o o k 分校开发了一个三维虚拟结肠内窥镜系统【“，基于删i s 体绘制 可视化平台，主要用于结肠的内窥。波士顿外科手术规划实验室建立了一种虚拟耳 窥镜系鲥1 4 1 ，以三维形式显示耳的解剖结构，来模拟传统内窥镜对内耳的检查过程。 宾语法尼亚大学电子工程系研制了一套虚拟内窥镜系统q u i c l 【s e e 【1 5 1 ，用于非侵入式 地观察和分析肺部结构。法国l a e 眦h 0 p i t a l 开发了虚拟食管一支气管内窥镜【“， 采用喉部c t 图像，并在视图中提供解剖结构的三维提示功能，具有广泛的临床应用 潜力。 国内1 1 7 j 主要研究机构有：东南大学、中科院自动化所、西北大学、东软北京研 究中心等，目前基本上处于探索阶段。台湾台大医院于2 0 0 4 年开发出首套“虚拟内 窥镜检查”教学系统，包括虚拟支气管镜、胃镜以及大肠镜检查。 虚拟内窥镜技术发展至今，历史虽然较短，但发展迅速。美国的r a r d b b ( 1 8 】 总结了虚拟内窥镜在不同时期的应用情况，并把它分成5 代，每代不仅包含了前 一代的功能，还提供了更为复杂的功能。第一代完成了基本的3 d 几何造型上的解 剖形态，具有一些简单的交互能力：它允许对解剖结构进行总体上的辨别，提供简 单的角度变换和非常粗糙的器官旋转操作。第二代和前一代相比，有了更加真实的 组织解剖结构，包括组织的物理性质，比如伸展性和可塑性，并且对解剖机构进行 交互式的定位，在虚拟器官的任何部分可进行各种各样的操作。第三代利用了来自 病人c t 、m 图像的详细数据，这些具有相当高解析度的真实数据集显著地提高 了重现精度及i 临床上的有效性。第四代的目的是给模拟组织以显微级的细节，绘制 出极为逼真的微小结构，比如神经血管束，有粘膜表面的腺体结构，甚至是一些独 4 浙江大学硕士学位论文 立的细胞；最早的第四代技术出现于一个空间生理学上的新的应用程序，它由m a y o 诊所生物医学成像研究所开发，建模过程详细而精确地再现出了物体复杂的表面结 构( 图1 ，3 ) 。第五代将会包括带有复杂的生物化学参数的多组织综合系统来表达 身体组织的整体功能，像神经内分泌和免疫促进功能或是一些病理状态。当第四代 第五代或是再往后的技术实现后，虚拟现实将会变得更加真实和有效。而在这种程 度下，医生将无法区分虚拟内窥镜产生的图像和真实景象，使用虚拟内窥镜就如同 操纵传统内窥镜在真实人体内漫游。 图1 3 来自肠胃系统低等肠系膜神经中枢的一个神经细胞的3 d 模型及其内部结构 1 2 2 虚拟内窥镜的关键技术 虚拟内窥镜虽然发展迅速，有传统内窥镜无法比拟的优势，但受软硬件条件的 限制，目前还无法完全替代传统内窥镜在临床方面的应用，很多时候只是作为传统 内窥镜补充的角色出现在实际应用中。为了进一步发展虚拟内窥镜就要重点解决 以下几个关键技术i 1 勉1 】： 1 图像分割 医学图像分割是医学图像处理和分析中的关键技术。它是一个根据区域内的相 5 浙江大学硕士学位论文 似性以及区域间的相异性把图像分割成若干区域的过程。从图像中把有关结构或感 兴趣的区域分离出来是图像分析与识别首要解决的问题，也是制约医学图像处理中 其他相关技术发展和应用的瓶颈f 捌。早期的图像分割完全是靠人工完成的，在原始 图像上由人直接画出期望的边界。这种方法费时费力，且分割结果难以再现。半自 动的分割方法是随着计算机技术的发展产生的，它把操作者的知识和计算机的数据 处理能力有机地结合起来，从而完成对医学图像的交互分割。近年来，由于大量的 新兴技术如模糊技术和人工智能技术在图像分割中的应用，图像分割领域中涌现出 一些自动的分割技术，这些技术能完全脱离人为干预，由计算机实现医学图像分割 的全过程。今后图像分割的研究目标主要是自动、精确、快速、自适应性和鲁棒性 等几个方向。 2 三维绘制 如何真实媲再现内部器官，甚至绘制出极为逼真的微小结构，使医生能从计算 机屏幕上获取更多的信息，是医学可视化的研究重点。但同时，无论硬件如何发展， 数据量的急剧增加都会远远超出硬件的处理能力，因为人们对细节和精度的追求是 无止境的，这给实时性带来了很大的挑战。而实时显示是虚拟内窥镜走向临床应用 的关键问题，虚拟内窥镜产品必须达到实时显示或者接近实时显示才有更大的实用 价值。真实性和实时性对虚拟内窥镜来说缺一不可。如何在这两者之间找到平衡， 或者找到一种真实性和实时性都能较好满足的绘制算法就成了一个很现实的问题。 在实际应用中，三维绘制算法分为体绘制算法和面绘制算法。体绘制方法能够 显示出非常丰富的信息，甚至连数据场中细微的特征都不会丢失。但是体绘制的致 命缺陷也源于此，大量计算带来了令用户无法忍受的等待时间。面绘制方法生成的 图形质量不如体绘制，但面绘制方法计算量较小，速度较快。从交互性能和算法效 率上讲，至少在目前的硬件平台上，面绘制要优于体绘制。而且面绘制生成了物体 的几何和拓扑信息，可以进行定量分析，为以后的手术模拟提供了可能。 3 路径规划 路径规划就是预先抽取特定组织的中心路径作为漫游路径，然后计算机沿着给 定的路径生成相应的动画。对于像结肠一类具有管状路径的器官，手工指定路径是 可能的。对于支气管一类具有多分支、树状的复杂踌径的器官，人工无法、也不可 6 浙江 翼霎皇謇豸霎翼荔。墓霾。囊霆萎霎蠹黧霪像斡犋豁筮剖珐；梦誊烈堑鬻懋警慑净 净澎谤；支蔫| 茸强缘磕煽曙南瓒悭螽吲罐堙；澶一源藩鬈予实际的i 攀豳疆弱箱翟 窭翥龄鐾疆獾露鬣臀篇翟；描醵甜璧裤融秘瓠程越溺铩彰犁曼a 略艨罐憎淫掣占苍 评；哩遵礓蔓硝噬瞧薯忑磁蔼，燮系攫噱随慢。氆圆糯唪噶沼德湖译喉诵灞滢 滢襄蒿栋瓣鹾砑；棒堪备撵供殴辱；分割、插值等预处理。本章主要讨论虚拟内窥镜系统所需预 处理中的图像分割技术。只有将特定的组织、器官从医学图像数据中准确地分割出 来，才能实现三维重建。 2 1 分割技术综述 医学图像分割的研究多年来一直受到人们的高度重视，分割算法也是层出不穷。 但是由于图像分割问题所面向领域的特殊性，至今尚未得到圆满的具有普适性的解 决方法。图像分割技术发展至今已在灰度阈值分割法、边缘检测分割法、区域跟踪 分割法的基础上结合特定的理论工具有了更进一步的发展l 州。 灰度阚值分割算法主要根据图像灰度分布直方图，通过设置阈值把像素点按灰 度级分为内部点集和外部点集，实现图像分割。常见的主要有以下几种： 全局单阈值法： 把整个细胞图像的灰度密度函数看成两个单峰密度函数 ( 目标、背景) 的总和，根据使总错误率降到最小来确定阈值。 双阈值法：通过设置两个阈值，以防单阈值设置阈值过高。误把目标像素 归为背景像素，或反之阚值设置过低，则误把背景像素归为目标像素。 自适应阈值法：通过对医学图像分块，对每一块局部阈值进行分割，对既 有背景又有目标的块直接设置阈值进行分割：对只有目标或只有背景的块， 根据邻域各块定出的局部阈值，通过内插求出阚值，对该块进行分割， 区域跟踪分割算法是近 悄芰煊蛱乇鹗羌扑慊泳跹芯恐惺止刈 x 浙江大学硕士学位论文 图像分割算法，常见的有区域生长方法、区域分裂方法以及区域生长与分裂相结合 的方法等。 区域生长法的基本思想是将具有相似性质的像素合起来构成区域，具体做 法是选取给定图像中要分割的目标物体内的一个小块或者说种子区域，再 在种子区域的基础上不断将其周围的像素点以一定的规则加入其中，达到 最终将代表该物体的所有像素点结合成一个区域的目的。 分裂合并法是先将图像分割成很多的一致性较强的小区域，再按一定的规 则将小区域融合成大区域，达到分割图像的目的。 医学图像分割的其他方法： l e v ds e t ( 水平集) 方法：其主要思想是将移动的界面作为零水平集嵌入高一 维的水平集函数中，这样由闭超曲面的演化方程可得到水平集函数的演化方程，而 嵌入的闭超曲面总是其零水平集，最终只要确定零水平集即可确定移动界面演化的 结果。l e v e ls e t 方法的优点在于：可以处理尖锐的角落，并具有很强的改变拓扑的 能力。它可以把具有相当复杂的物体边界分割出来。 另外，近年来随着一些新兴技术( 如模糊数学、数学形态学、数字拓扑学、人 工智能等) 在图像处理中的应用，一些全薪的图像自动分割技术应运而生f 4 2 ”，如 模糊分割技术，基于知识的分割技术，人工神经网络分割技术等。但于自动分割方 法的运算量较大，目前大部分的自动分割方法都是在工作站上实现的。 2 2 图像分割的方法 我们的虚拟内窥镜平台在图像分割方面应用了u s i s 系统的图像分割模块，该 模块由我同组的另外一个同学开发，其主要思想为： 将灰度阙值分割算法和区域生长算法结合起来，实现优势互补。先利用双阈 生长 到整个目标区域，从而剔除多余区域。 运用灰度阈值分割和区域生长相结 x 浙江大学硕士学位论文 来了。但考虑到精度要求，光用灰度阈值分割和区域生长方法进行处理可能还达不 到要求。因此还利用灰度阈值分割和区域生长方法对图像进行预处理，以此为基础， 再用l e v e ls e t 方法对图像进行处理，从而得到更精确的分割效果。 l e v e ls e t 的主要思想嘲是一个虚构的边界以一个初始速度进行运动，最终扩展 成所需的轮廓边界。所需要的技巧是调整速度f 以探测轮廓边界： 边界经过的区域的梯度值( 即一个像素到相邻像素的值的变化) 较小的话， 。 算法认为还没有接近边界，因此使边界运动得较快。 边界经过的区域的梯度值较大时，算法认为已经接近边界，因此放慢速度。 另外，附加的表面张力( 曲率的变化) 也要考虑在内以稍微延缓边界的进化。 我们利用了f a s tm a r c h i n g 版本的水平集方法来得到最优的结果。 最后，如果医生对经过上述算法分割后的图像数据还不满意的话，系统还提供 了方便的手动修改机制，使医生能根据自己丰富的临床经验对分割后的图像做补充 处理，使得到的轮廓更为精确。 2 3 图像分割结果 我们用2 2 节的方法对大肠数据进行了分割( 数据来源：杭州召g 逸夫医院，数 据规模：5 1 2 5 1 2 1 7 2 ) ，图2 1 2 3 分别显示了第1 2 张、第5 5 张和第1 2 0 张c t 切片的分割结果。 图2 1 ( a ) 第1 2 张c t 切片( b ) 第1 2 张c t 切片分割结果 浙江大学硕士学位论文 图2 2a ) 第5 5 张c t 切片( b ) 第5 5 张c t 切片分割结果 图2 3 ( a ) 第1 2 0 张c t 切片( b ) 第1 2 0 张凹切片分割结果 浙江大学硕士学位论文 3 1 引言 第3 章三维绘制 医学图像数据经上一章的分割处理后，形成了一个非常规整的分布在三维空间 上的体数据。体数据是3 d 实体，包含了丰富的信息。医学图像的可视化就是对这个 体数据进行处理，把有意义的信息抽取出来，构造出三维几何模型，将看不见的人 体器官能以三维形式“真实”地显示出来，便于医生从多角度、多层次进行观察和 分析。 医学图像的可视化算法一般分为两类：体绘制和面绘制。 体绘制算法嗍刚又称直接体绘制法，由d r e b i n 和k v y 在8 0 年代末提出，其 中心思想是为每一个体素指定一个不透明度，并考虑每一个体素对光线的透度、发 射和反射作用，把数据场中不同层次的内容在一幅图像中同时显示出来。这种方法 优点在于能产生三维数据场的整体图像，包括每一个细节，并且图像质量高，便于 并行处理，符合虚拟内窥镜的真实性要求。但这种方法往往计算量非常大，难以实 时处理。同时它产生的显示不能很好地表现空f 霹层次，给人们理解体数据的内容造 成困难。 面绘制先由三维空间数据场构造出中间几何图元( 如曲面、平面等) ，然后再由 传统的计算机图形学技术实现画面的绘制。它可以产生比较清晰的等值面图像，计 算量相对体绘制数据量要小，而且该方法很成熟，可以利用现有的图形硬件实现绘 制功能，使图像生成以及变换的速度加快，更适合于实时性要求高的地方。另外， 面绘制由于生成了物体的几何和拓扑信息，可以实现体积、面积等定量分析的任务， 也可以实施求交、求和等操作，为手术模拟提供了可能。但面绘制丢失了三维数据 场中的细节信息，缺乏内部信息的表达。 我们 x 浙江大学硕士学位论文 3 2m a m h i n gc u b e s 算法 在面绘制算法方面，1 9 7 5 年k c p p e l l 3 1 】最早提出表面重建方法，采用基于轮廓线 的表示方式，根据体数据由多张平行切片组成的特点，先求出每张切片中物体的闭 合轮廓，然后将相邻切片之间的轮廓连接起来，生成物体表面。但是它确定多分支 等值线在相邻切片间的拓扑关系以及分支顶点的连接关系比较困难，至今尚未彻底 解决。1 9 7 7 年f u c h s l 3 2 j 提出基于多边形的方法，根据在不同切片上提取出的轮廓线， 用三角面片网格拟合轮廓曲面。这种方法属于面向曲面的方法，通过构造实体表面 来实现对象重建。1 9 8 3 年s bx u 【3 3 1 提出由c t 断层图像序列进行物体三维表面重建 方法，他对物体的插值表面增加了一个附加约束，即插值表面在每一轮廓点上的曲 率之和为最小值。1 9 8 5 年b u s s 伽n “3 4 墟出了另外一种基于表面轮廓的d e l a u n a v 三 角化方法，懈决了系列表面轮廓的三维连通性问题。用三角形或多边形的小平面在 相邻的边界轮廓线间填充形成物体的表面，但是这种方法所得出的只是分片光滑的 表面。1 9 8 7 年l 0 r e n 蝴【3 5 】等人提出了m a r 曲i n gc i l b 船算法，是至今为止最有影响的 等值面构造方法。最初的m a 曲i n gc u b e s 算法不能保证三角片所构成的等值面的拓 扑一致性，会造成等值面上出现孔隙。m j d u 指d 3 6 l 首先提出了m a r c h i l l gc i l b e s 算 法中的二义性，后来许多人在e d r c n s 方法的基础上做了许多改进。m a f c h i l l gc u b e s 如今已经成为最流行的三维重建算法之一。 3 2 1 基本原理和过程 在m a r c l 血gc u b e s 算法【3 7 州中，假定原始数据是离散的三维空间规则数据场， 计算机断层扫描( c t ) 及核磁共振成像( m r j ) 等产生的图像均属于这一类型。算法的 基本思想是逐个处理数据场中的体素，从中分类出与等值面相交的，然后采用插值 计算出等值面与体素边界的交点。再根据体素的每一顶点与等值面 x 浙江大学硕士学位论文 体素是逻辑上的六面体，由c t 或m r i 等断层图像相邻层上的各4 个像素组成 体素上的8 个顶点。这8 个顶点称为该体素的角点，它们的坐标分别为( i ，j ，k ) ， ( i + l ，j ，k ) ，( i 。j + l ，k ) ，( i + l 。j + l ，k ) ，( i ，j ，k 十1 ) ( i + 1 ，j k 十1 ) 。( i ，j + l ，k + 1 ) 和( i + l ，j + 1 ，k + 1 ) o 对体素内的任一点，其值只能从体素的8 个顶点的采样值来估算。 等值面是空阐中所有具有某个相同值的点的集合。它可以表示成： 帖，y ，2 ) i ，o ，y ，2 ) = c c 是常数 这里的( x ，y z ) 是空间点的坐标，f ( x ，y z ) 是对应体数据的值。常数c 就是三维 重构过程中给定的闽值。并不是每个体素内都有等值面，当体素的8 个顶点都大于 c 或者都小于c 时，其内部就不存在等值面。只有那些既有大于c 的顶点又有小于c 的顶点的体素才含有等值面，我们称这样的体素为边界体索( 也日q 非空体素) 。等值 面在一个边界体素内的部分称为该体素内的等值面片。等值面是一个三次曲面，它 与边界体素面的交线是一条双曲线，且这条双曲线仅由该面上的4 个顶点决定。这 些等值面片之间具有拓扑一致性，即它们可以构成连续的、无孔的、无悬浮面的曲 面。因为对于任何两个共面的边界体素，如果等值面与它们的公共面有交线，则该 交线就是这两个边界体素中等值面片与公共面的交线。也就是说这两个等值面片完 全吻合。所以，可以认为等值面是由许多个等值面片组成的连续曲面。由于等值面 是三次代数曲面，构造等值面的计算复杂，也不便于显示，而多边形的显示非常方 便，所以，等值面的三角片拟合是常用的手段。本章论述的m a r c h i n gc u b e s 算法就 是在边界体素中生成三角面片，以三角面片拟合等值面。 m 眦h i n gc u b e s 算法的基本思 x 浙江大学硕士学位论文 素的8 个顶点的情况。因此。先对体素的8 个顶点进行分类，以判定每个顶点是位 于等值面之外，还是位于等值面之内。然后再根据8 个顶点的状态，把交点按一定 方式连接成等值面，并同时完成等值面在这个体素内的三角剖分。 顶点分类规则为： ( 1 ) 如体素顶点的数据值 = 阚值，则定义该顶点位于等值面之外； ( 2 ) 如体素顶点的数据值( 阈值，则定义该顶点位于等值面之内。 在三维空间中，由于每体素共有8 个顶点，每个顶点共有2 个状态( 等值面 内和等值面外) ，因此共有2 5 6 种组合状态。分析立方体体素的2 种对称性： ( 1 ) 顶点状态反转，等值三角面片的拓扑结构不变，也就是讲，8 个顶点的状 态同时反转不影响拓扑结构。 ( 2 ) 旋转对称性，根据体素3 个方向旋转上的对称性，即体素绕3 个方向任意 旋转9 0 。的倍数，体素内等值面片的拓扑结构不变。 这样，可归纳出交点连接方式，即等值面三角荆分方式的1 5 种基本模式。图3 1 给出了这1 5 种基本模式的三角剖分( 黑点表示该顶点在等值面之外) 。 图3 11 5 种基本模式 1 7 浙江大学硕士学位论文 密度的物质的分界面，因而其梯度矢量不为零值。但直接计算三角面片的法向是费 时的，而且，为了消除各三角面片之间明暗度的不连续变化，只要给出三角面片各 顶点处的法向量并采用g o 岫u d 光照模型绘制各三角面片就行了。这里算法采用中 心差分计算出体索各顶点处的梯度，然后再一次通过体素棱边两个端点处梯度的线 性插值求出三角面片各项点的梯度，也就是各顶点处的法向，从而实现等值面的绘 制。体素顶点的中心差分公式如下： 盟坐掣 驴盟巫堕型 ”塑型吃掣 对于三角面片的各个顶点( 即等值点) ，其梯度( 法向量) 为： n = n 1 + ( c - v 1 ) ( n 2 - n 1 ) ，( v2 - v 1 ) 其中n 代表等值点梯度，n 1 、n 2 代表棱边的两个端点的梯度，v 1 、v 2 代表两 个端点处的体数据值，c 代表阈值。 3 2 2 二义性问题 m a r c l l i l l gc u b e s 算法提出后不久，就有人发现了它的歧义性【矧。让我们先来看 一下图3 1 ( 1 5 种基本模式) 中的模式7 的上表面。其4 个等值点的连接方式为： 图 其实这只是其中一种连接方式， 图3 5 连接方式2 对= 日 浙江大学硕士学位论文 圈3 8 模式6 和模式3 的顶点状态反转模式组合产生孔隙问题 3 2 3 二义性问题的解决 在二义性问题提出来后，很多人对传统的m a r c l l i n gc 曲e s 算法进行了各种方法 的改进 3 8 4 1 】1 4 2 l ，其中包括渐近线判别法、移动四面体法以及扩展的m 眦gc u b 算法。 1 渐近线判别法 渐近线判别法由n i e i s o n i “蝽入提出，通过计算等值面与体素边界面的交线( 双 曲线) 的渐进线与体素的边界面的相互位置关系来判断等值面的正确连接方式。在 一般情况下，用三角面片来拟合等值面，等值点之间的连线用直线近似。但准确得 来讲，等值面与体素边界面的交线是双曲线。该双曲线的两支及其渐近线与体素的 一个边界的相互位置关系可用图3 9 来表示。在该图所列的4 种状态中，当双曲线 的两支均与某边界面相交时，就产生了连接方式的二义性。此时，双曲线的两支将 边界面划分为3 个区域并且双曲线中两条渐近线的交点必然与边界面中位于对角 线上的一对顶点落在同一个区域内。 带择铲击 圈3 9 双曲线与体紊边界的相互位置关系 设双曲线的两条渐近线的交点坐标为( x ，y ，z ) 。当出现二义性时，需要计算 浙江大学硕士学位论文 f ( x ，y jz ) 的值，并与阈值c 比较。如果f ( x ，y z ) = c ，则渐近线的交点应 与其函数值大于等于c 的一对角点( 体素的顶点) 落在同一区域内。如果f ( x ，y ，z ) c ，则渐近线的交点应与其函数值小于c 的一对角点落在同一区域内。这就是当 出现二义性时，等值点之间的连接准则，如图3 1 0 所示( + 代表大于等于c ，一代 表小于c ) 。 + 囹圈 图3 1 0 二义性面等值点的连接准则 在1 5 种基本模式中，第0 ，1 ，2 ，4 ，5 ，8 ，9 ，l l ，1 4 等9 种模式不存在二义性面，只 存在1 种连接方式。第3 ，6 两种模式，各存在一个二义性面，各有两种连接方式。 第1 0 ，1 2 两种模式，各存在两个二义性面，各有4 种连接方式。第7 种模式存在3 个二义性面，有8 种连接方式。第1 3 种模式存在6 个二义性面，有6 4 种连接方式。 n i c l s o n 在他的文章n e 黯y m p l o t i cd e c i d e f ：f c s o l v i n gt l 地a m b i g i l i t yi l im a r c h i i i g c u b e s 【4 1 】中对各种连接方式进行了总结。以第1 0 种模式为例，n i e l s o n 计算的4 种 连接方式为： 图3 1 1 基本模式l o 的4 种三角剖分方式 将1 5 种模式的各种情况加在一起，共有9 3 种不同的连接方式，除去对称的和 浙江大学硕士学位论文 相同的方式，共有3 4 种不同的连接方式。所以，虽然这种方法可以正确地修正二义 性，但是需要额外的计算，并且比较繁琐，要产生更多的三角面片。 2 移动四面体法 这是在m a r c h i n gc u b e s 算法基础上发展起来的一种算法，较简单的解决了歧义 性问题。算法把一个立方体分割为若干个四面体，再在每个四面体上提取等值面。 对于一个四面体，共有4 个顶点、1 6 种情况。考虑对称性，最后只有5 种基本 模式( 图3 1 2 ) 。 图3 1 2 移动四面体的5 种模式 根据二义性的定义可知，上面5 种模式没有歧义性。 把一个立方体划分为多个四面体有多种方法。图3 1 3 展示了一个立方体分成5 个四面体的两秘方法，图3 - 1 4 展示了一个立方体划分为6 个四面体的方法。 圆圆圆圆圆 回国圃圆画 图3 13 把立方体分成5 个四面体的两种方法 画画圆 圆画圆 图3 1 4 把立方体划分为6 个四面体的方法 浙江大学硕士学位论文 这种方法产生的3 d 表面要比m a r c h i n gc u b e s 的光滑，而且解决了歧义性问题。 但同时产生了比m a r c h i n gc u b e s 算法多得多的三角面片。 3 扩展的m a r c h i n gc u b e s 算法 这类算法解决二义性的方法说起来其实很简单，就是把所有的二义性面都按连 接方式1 或连接方式2 来处理。 若都按连接方式l 处理，则立方体体素的顶点状态反转对称性不再满足，三角 面片的连接方式也从1 5 种基本模式扩展成为2 3 种： 图3 1 5 连接方式1 的2 3 种模式 浙江大学硬士学位论文 在图3 1 的1 5 种基本模式中，模式3 和它的顶点状态反转模式有着相同的三角 剖分方式，而在上图中两者( 模式3 和3 c ) 就不一样了。现在把它们再次组合起来， 就不会出现图3 7 中的孔隙了： 图3 16 模式3 和其顶点状态反转模式( 3 c 组合不会产生孔隙问题 同样，把模式6 和模式3 c 组合起来也不再会出现图3 8 中的孔隙 圈3 1 7 模式8 和模式3 的项点状态反转模式3 c 组合不会产生孔隙闯题 同理，若把所有的二义性面都按连接方式2 来处理，也可得到2 3 种模式( 图 浙江太学硕士学位论文 3 1 8 ) ，也能有效地解决孔隙问题。 图3 1 8 连接方式2 的2 3 种模式 扩展的m a r c h i n gc u b e s 算法虽然解决了孔隙闻题，但有种强制性的意味，并没 有从图形本身出发。然而与渐近线判别法、移动四面体法相比，扩展的m a r c h i n g c u b e s 算法计算量小，产生的三凭面片数目也要小得多，而且与传统m a r c h i n gc u b e s 算法“兼容性”较好，只需修改查找表，可以说是性价比最高的一种改进方法。 本文采用的就是扩展的m a r c h i n gc u b e s 算法，所有二义性面都采用连接方式1 ， 并按图3 1 5 的2 3 种三角荆分模式建立了2 5 6 个索引项的查找表，较快而且较好地 浙江大学硕士学位论文 解决了可能出现的孔隙问题。该查找表的每一项都由数字组成，每个数字表示编号 为该数字的边上的等值点。每三个数字为一组，表示由这三条边上的等值点组成的 一个三角面片。对应的三角剖分模式有多少个三角面片，这一项就有多少组这样的 数字。 3 2 4 算法优化 经观察，在实际情况中，只有少量体素与等值面相交，绝大多数都是窑体素， 即图3 1 5 中的模式0 或模式0 c 。而传统m a r c h i n gc u b e s 算法的基本思想是逐个处 理数据场中的体素，这样就浪费了很多时间在空体紊的检测上面，考虑到等值面的 封闭性和连续性，一个体素内的三角面片确定以后，其相邻非空体素内的三角面片 会按一定方向延伸，而且相邻的两个非空体素至少共用条等值边。因此，可采用 区域增长的方法，先找到第一个跟等值面相交的体素，加入堆栈。然后开始迭代过 程，每次从堆栈中弹出一个种子体素，处理完毕后考察其前、后、左、右、上、下 6 个面，若这个面上至少有一条等值边，则这个方向上与它相邻的体素肯定为非空 体素，需把它加入堆栈里面。等堆栈为空时，所有非空体素都被处理完毕，等值面 也被抽取了出来。这样我们就有效地避免了对大量空体素的检测。 另一方面，对于每个体素，原来的m a r c h i n gc u b e s 算法先根据其8 个顶点计算 其索引值，利用查找表得到此体素的哪些边上有等值点，以及等值点的连接方式等 信息，然后通过线性插值计 x 浙江大学硕士学位论文 的所有元素都标记为0 ，同时将体素等值表初始化。然后通过遍历的方法找到第一 个非空体素，并加入堆栈。以后每次从堆栈中取出一个体素进行处理，每次处理包 括两次查表。第1次查表，是通过该体素8个顶点的组合状态得到索引值，由此通 过三角割分查找表来确定该体素在哪些边上有等值点，以及它们的连接方式。在计算等值点坐蒌人为指定葫蘸j 弱聪雕逍希篷鼻嫱骚器t 翁缮器翁酝列茜秭粹懿繇 乳强垄赣鞠弱鲤醛稻翟嚣臻蛩孬骼尝晶强搐戳。莆f i 罐壕潲碓墨嗌i 紧魁二 嘣增澎贯响灏唾馕灌了罐踩囊嗣j 馒淄陪津琊湾；样煮处的视绣方向铺i 矍垂螽 辅蔽戳箱h 泊酾辇嚣烈酣；群g 驰融鸵：绕视绩一夏露跫蓬；恕誊爨静翮撕鼬 瓣髓睛西赫茹“醐钉骺酞鳍；囊誉一奏黼獾灌瞄甑蠹；童瞩陵荫醛p 函鲽“骺鞘 爱拿：靶挺 并以虚拟探头在该点的视线方向为 法向量的平面，然后把前一个采样点的v j e wu p 向量投影到这个平面上，得到新的 c wu p 向量。这样可使e wu p 向量在前后两帧之间比较连续，实现平稳过渡。 下图是在大肠内部自动漫游时内时内窥镜视图中生成的部分帧图像： x 浙江大学硕士学位论文 读入体 数据 n 逐个构造体素，每个体素中的8 个顶点取自相邻的睡层c t 图像 将体素每个顶点的数据值与给定的等值面闽值c 做比较， 并根据比较结果，计算该体素的索引 根据索引从查找表中得出将与等值面有交 点的体素棱边以及等值面片的连接方式p 由线性插值计算出体素棱边上等 值面交点的位置和相应法向量 由p 确定的次序构造等值面的 三角面片并放入输出的等值面几何表示中 所有体素有否处理完毕? y 图3 2 0 扩展的m 甜c h i n gc u b 算法( 优化前) 的实现流程 浙江大学硕士学位论文 3 3 三维模型的网格简化 3 3 1 概述 给定适当的阈值，用上一节论述的m a r c h i n gc u b e s 算法抽取等值面得到的三维 表面模型，所含的三角面片数量是非常巨大的。巨大数量的三角面片对计算机的存 储容量、处理速度、传输效率等都提出了很高的要求，更重要的是无法对三维重建 出来的模型进行实时绘制，而实时性是虚拟内窥镜的基本要求之一。因此，有必要 对重建的表蕊模型进行简化处理，在保证视觉效果的前提下，尽量减少模型三角面 片的数量，提高交互绘制速度。 研究人员已提出了多种网格简化算法，这些简化算法主要有以下几类： ( 1 ) 顶点聚类法】 这类算法首先用一个包围盒将原始三维模型包围起来，然后通过空间划分将包 围盒分成若干个区域。这样，原始模型的所有顶点就分别落在这些小区域内，将区 域内的顶点合并成一个新顶点，再根据原始三维网格的拓扑关系对这些新顶点进行 三角化，就得到简化模型。 ( 2 ) 区域合并法脚】 这种方法先选择一个三角面片为种子面，然后根据一定的准则将周围的面合并 起来形成一个更大的超面，再将超面边界拉直，并对其重新三角化，从而达到面片 化简的目的。 ( 3 ) 重新布点法【4 5 j 算法先将由用户指定数目的顶点根据各个三角面片的面积大小分布在模型表面 上，再根据模型表面上顶点之阆的斥力使顶点在表面上的分布更均匀，然后将模型 上的原始顶点与新加入的顶点混合在一起进行三角剖分，最后将原始顶点一个个地 删去，并及时地对删除顶点所造成的空洞进行三角化。 ( 4 ) 逐步求精法【娟1 逐步求精方法首先给出一个原始网格的逼近网格，然后逐步增加细节，并重新 进行局部三角化，直到近似模型达到用户满意的精度为止，它包括贪婪插入法和层 浙江大学硕士学位论文 次细分法。 ( 5 ) 小波分解算法f 4 7 l 基于小波变换的多分辨率模型使用了带有修正项的基本网格，修正项称为小波 系数，用来表示模型在不同分辨率情况下的细节特征。算法分为分割、参数化、重 新采样三个主要步骤。此算法可以处理任意拓扑结构的网格，而且可以提供有界误 差、紧凑的多分辨率表示和多分辨率尺度下的网格编辑。 ( 6 ) 几何元素删除法 1 9 9 2 年，s c h r o e d e r 提出了基于顶点删除的网格简化方法【耜】。此后，基于边折 叠f 4 9 】刚、基于三角形删除f 5 1 】等几何元素删除方法被相继提出。这些方法的共同特点 是以几何元素的删除实现模型的简化，即根据原模型的几何拓扑信息，在保持一定 的几何误差的前提下删除对模型几何特征影响相对较小的几何“图元”( 点、边、 面) 。它包括顶点删除法、边折叠法、三角形简化方法等。 3 3 2 顶点删除法 顶点删除法是指在三角形网格中，若一个顶点与它周围三角面片可以被认为是 共面的( 这可以通过计算点到平面的距离值等方法来判断) ，且这一顶点的删除不会 带来拓扑结构的改变，那么就可将这一点删除，同时与该顶点相连的面均被从原始 模型中删除，然后对其领域重新三角化，以填补由于这一点被删除所带来的空洞。 这种操作一直继续到三角网格中无满足上述条件的顶点为止。 顶点删除法的优点在于它是拓扑保证的，简化后模型的顶点是原模型顶点的子 集，能较好的保持原模型的特征。 在阐述算法之前，先介绍几个重要的定义： 定义l 三角面片的相邻关系：给定任意2 个三角形t i 、1 ) ，若t i 、再具有 1 条公共边则称三角形t i 、t j 是相邻的，否则就是不相邻的。 定义2 星形区域：以模型上v 点为顶点的所有三角形组成的区域定义为v 点 的星形邻域，记为s t a r ( v ) 。 浙江大学硕士学位论文 定义3 顶点的自由度：顶点v 的星形区域中的三角形个数称为该点的自由度。 定义4 顶点的平均平面：设s t a r ( v ) 中每个三角形的法向量为m ，中心坐标 为c i ，面积为4 ，那么下面式子定义的法向量n 和中心c 构造的平面定义为v 点星 形邻域的平均平面。 ； ”丽 c 单 顶点删除算法主要有3 个步骤： 1 根据顶点的几何和拓扑对顶点进行分类 顶点分类分为二步： 第一步是按顶点周围的拓扑来划分的。分为以下三类： s i m p u e b o u n 吼蛐吖c 0 m p u 图3 2 2 顶点的三种类型 ( 1 ) s i m p l e 顶点周围的三角形可构成一个闭合的环，而且与此顶点连接的所有边正好都被 两个三角 x 浙江大学硕士学位论文 3 重新三角化 当我们把符合删除标准的顶点v 及其相关的三角面片删除后，会留下以下“空 洞”( 图3 2 5 ) ： 顶点v 图3 2 5 删除顶点v 后留下的“空洞”( 多边形) 接下来就是要对这些“空洞”进行三角化。为此，我们采取了递归算法：先把 “空洞”分成两部份，得到两个多边形；这两个多边形继续分裂，直到所有的多边 形都分裂成三角形。但一个多边形分裂的方法有多种，为此，我们给出了一个缴横 比( a s p e c tr a t i o ) 的标准，其计算方法如下： 在一个多边形中，连接两个非相邻顶点的边叫做分裂线，有多少种分裂方法就 有多少条分裂线。对每种分裂方法，我们构造一个经过分裂线并垂直于删除顶点v 的平均平面的分裂面( 图3 2 6 ) 。然后计算多边形的各个顶点到分裂面的距离，并 定义其中的最小值d 与分裂线长度的比值为纵横比。最后，取纵横比最大的分裂方 法。用这种方法重新三角化后得到的三角面片泷较均匀和规则。 图3 2 6 分裂线和分裂面 浙江大学硕十学位论文 下表给出了用优化前后的扩展m a r c h i n gc u b e s 算法进行三维重建的对比，特别 是算法执行的时间( 机器配置：p i v2 o g ，1 g 内存) ： 数据名称数据规模顶点数三角面片数执行时间( m s ) 优化前6 2 4 3 7 0 1 2 4 8 9 9 61 2 0 6 3 大肠5 1 2 x 5 1 2 1 7 2 优化后6 2 3 9 4 81 2 4 8 1 6 84 3 9 l 优化前 9 8 4 7 01 9 6 2 6 22 2 9 7 下颌骨5 1 2 5 1 2 1 0 3 优化后9 8 4 7 01 9 6 2 6 21 2 1 9 优化前4 4 1 1 68 s 2 2 81 1 7 2 腿骨1 5 0 x 1 5 0 x 2 1 0 优化后4 4 1 1 6 8 8 2 2 8 6 2 5 从上表中的执行时间对比可见，利用我们设计的邻接共用表，确实能有效地避 免对空体素的不必要检测和相邻体素共用等值点的重复计算，大大提高了扩展的 m a r c h i n gc u b e s 算法的效率。 图3 2 7 中的大肠三维模型总共包含6 2 3 9 4 8 个点、1 2 4 8 1 6 8 个三角面片，在p i v 2 o g ，1 g 内存的p c 上进行人工交互时，响应速度比较幔。为此，我们用顶点删除 算法对该三维表面模型进行了网格简化。图3 3 0 旷e 展示了不同精度控制下的网格 简化结果( 线框模型) ，表3 2 给出了每个结果的顶点数目和三角面片数目。图3 3 0 f 显示了只剩1 0 8 4 3 2 个三角面片时的表面模型，和图3 2 7 a 比较后可知，项点删除算 法能较好的保留原模型的表面特征。 ( a ) 未简化( 1 2 4 8 1 6 8 个三角面片)( b ) 4 8 3 1 0 4 个三角面片