（系统分析与集成专业论文）海量断层数据的三维重建算法优化.pdf

华 华 中中 科科 技技 大大 学学 硕硕 士士 学学 位位 论论 文文 i 摘摘 要要 mc（marching cubes）算法作为一种经典的三维重建算法，得到了广泛的应用。 但针对海量断层数据，采用 mc 算法进行三维重建时，存在很多问题：如拓扑关系 的求解，算法程序效率的提高等等。因此，三维重建算法的优化问题便成为当前研 究的一个热点。 文章首先介绍 mc 算法的基本原理与实现流程，然后介绍采用 mc 算法进行三 维重建的主要流程，并简单介绍了构网、平滑、简化、合并这几个关键步骤。其中， 平滑、简化、合并这三个步骤都是基于包含拓扑信息的网格数据进行的，因此需要 对传统的构网算法实施改进：使之能够在构网的同时同步取得各三角面片间的拓扑 关系。 拓扑关系的取得，比较有效的方法是边构网边获取，但对于海量断层数据，这 一方法面临计算资源与计算规模之间的矛盾，为了解决这一矛盾，文章提出了 “双 缓存、三层交换”的方法对构网关键算法进行优化，使得算法程序既能满足海量断 层数据处理的要求，又能满足算法程序性能的要求。文章着重分析了这一方法的机 理与实现流程，最后结合实际数据对算法程序性能进行对比分析，得出结论。 从结论分析可以得出，针对海量断层数据处理，利用 mc 算法进行三维重建时， “双缓存、三层交换”的机制确实能在一定程度上给算法程序的性能带来提升，能 够达到优化算法的目的。 关键词：关键词： mc 算法优化 三维重建 双缓存 三层交换 华 华 中中 科科 技技 大大 学学 硕硕 士士 学学 位位 论论 文文 ii abstract mc (marching cubes) is a popular 3-d surfaces reconstruction algorithm. but for huge segment datasets, thers is many problems for this typical algorithm, such as realized method is complex and performance of algorithm program is inefficient. so how to improve the effect of the algorithm program is a hot topic. because the data used for reconstruction is very huge, the reconstruction and its optimizing operation base on these data is very complex and inefficient. so its very important to study 3-d surfaces reconstruction algorithm optimization. this paper introduces the basic principles of mc algorithm and implementation processes firstly. secondly, it introduces the key steps of digital virtual human 3-d surfaces reconstruction using mc algorithm， which includes reconstruction，smooth, simplification，combinations and so on. the implementation of last three steps bases on the topological relationship of the triangles， so we must obtain the topological relationship of triangles while reconstructing. the more effective method of obtaining the triangles topological relationship is computing while creating triangles. but for massive slice dataset processing，this method is inefficient. in order to solve this problem，this paper presents a double cache，three layer switching method. practice shows it can make a high performance while processing massive slice dataset. keywords: marching cubes algorithm 3-d reconstruction double cache three layer switching 独创性声明 本人声明所呈交的学位论文是我个人在导师的指导下进行的研究工作及取 得的研究成果。尽我所知，除文中已标明引用的内容外，本论文不包含任何其他 人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体， 均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名： 日期： 年 月 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有 权保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和 借阅。 本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密，在_年解密后适用本授权数。 本论文属于 不保密。 （请在以上方框内打“” ） 学位论文作者签名： 指导教师签名： 日期： 年 月 日 日期： 年 月 华 华 中中 科科 技技 大大 学学 硕硕 士士 学学 位位 论论 文文 1 1 绪论绪论 1.1 研究的目的和意义研究的目的和意义 近年来，在计算机图形学领域，三维重建技术作为一门新兴技术越来越收到人 们的关注，这类研究虽然有着广阔的前景，但都面临数据集巨大，重建算法复杂等 特点。因此，在现有的硬件条件下，研究如何提高重建算法程序的效率，如何对重 建算法进行优化便成为一个十分重要的问题。 本文主要针对海量断层数据，研究三维重建算法的优化问题。当我们采用mc （marching cubes）算法1 2进行三维重建3 4时，如果要利用构网产生的结果数据 进行平滑5、简化6、合并7等进一步处理，就需要取得各三角面片的拓扑关系。拓 扑关系的取得，比较有效的方法是边构网边计算，但对于海量断层数据，这一方法 面临计算资源与计算规模之间的矛盾，为了解决这一矛盾，本文提出了“双缓存、 三层交换” 的机制对构网关键算法进行优化，使得算法程序既能满足海量断层数据 处理的要求，又能满足算法程序性能的要求。 mc 算法作为一种经典的三维重建的算法， 在很多方面有着广泛的应用。 本文提 出的“双缓存、三层交换”的机制，为对针对海量断层数据的三维重建算法优化问 题提供了一条途径，也为 mc 算法优化问题提供了一种新的思路。 1.2 研究背景及现状研究背景及现状 1.2.1 海量断层数据海量断层数据 海量断层数据的特点一个是“海量” ，一个是“断层” 。所谓“海量”也就是数 据量巨大，所谓“断层”指的是数据信息的“间断连续”性。如“虚拟中国人 1 号” 标本为一具 28 岁，身高 1.66 米，体重 112 斤的男性尸体，切片共 9,215 片，每片厚 0.2 毫米，分辩率 40405880 像素，原始数据容量 540g。 “虚拟中国人 2 号”标本 为一具 19 岁，身高 1.56 米，体重 92 斤的女性尸体，切片共 8,556 片，每片厚 0.2 毫 米，分辩率 30242016 像素原始数据容量 150g。这两组数据的特点都是数据量巨 大，而且是“间断连续”的切片数据，因此它们也就是我们所说的海量断层数据。 华 华 中中 科科 技技 大大 学学 硕硕 士士 学学 位位 论论 文文 2 1.2.2 三维重建的原理三维重建的原理 由于图像的象素总是有限的，因此用计算机进行图像重建的时候，首先总是需 要对图像进行离散取样和量化。无论是采用借助计算机断层扫描技术、还是核磁共 振技术，我们都能够得到一个三维物体的断面扫描图片。但是在这种获取过程中是 很容易造成图像失真，因此我们应该首先通过滤波来提高图像的信操比，再利用插 值来建造新的二维图形以近似补偿在扫描后丢失的部分物体的信息，以完成以后的 工作。另外，数据的分类是很重要的步骤，通过对数据的分类，我们得到三维灰度 (rgba)图像以外，还得到了一个三维属性图像。而这个属性图像表达的才是需要传 递给用户的真正信息。 对于三维物体的几种比较典型的描述方法有：骨架描述法，体元描述法和表面 描述法等等。同一种物体可以有不同的描述方法，各自具有不同的特性，需要根据 实际问题来选择相对简洁而有效的表示方法，在此基础上构造模型，以便于识别和 理解。 骨架描述法，也称线条描述法，是采用线条来表示物体茼单轮廓的方法，这种 方法简单易于实现，但是比较粗糙，无法细致地描述物体的许多特点，方法难满足 系统的要求。 体元描述法，采用空间分解的方法。对空间体元进行不断的切割处理，最后得 到一个由规则体构成的非规则复杂物体的近似。这种方法包括有物体的内在信息， 从而实现体数据的表达。 表面描述法，采用多边形来对物体的表面进行拟台，这是最常用的一种方法， 由于空间任意三点总能找到通过它们的平面，因此经常被选用的多边形是三角形。 相对于体元描述法计算量也比较小，但是忽略了物体内部的信息，这是它的一个缺 点。 contour connecting 是较早提出根据体数据绘制三维图形的一个算法，它是在二 维数据切片(data slice)中逐一提取闭台的等值线，然后将相邻切片的等值线相连接， 形成曲面网格逼近等值表面。所以这是一个基于面的体视化算法，依物体空间序遍 历体数据。对每个数据切片，定义一个闽值，找出与闻值相对应的等值闭合曲线， 这个过程对相临切片而言是独立的。这种方法比较简单，但是有很大的实用性，在 很多领域都有应用。 另外，对于一般的表面描述方法构造的三维图形，总要通过一定的方法进行平 华 华 中中 科科 技技 大大 学学 硕硕 士士 学学 位位 论论 文文 3 滑处理，才能达到比较满意的效果，显然攫取的数据越多，重建后物体的平滑程度 就越高，然而攫取数据总是有限度的。另外无论采用哪种图片输人方法都会造成一 定的信息丢失，所以需要采用一定的插值方法来近似丢失的数据选取一个好的插值 算法，既能弥补丢失的数据又能够达到物体平滑的目的。当然在选取表面平滑算法 的时候，需要对速度和精度同时进行权衡，以得到一个更合理的效果。 1.2.3 经典三维重建方法经典三维重建方法 图像的三维重建就是根据输入的断层图像序列，经分割和提取后，构建出待建 组织的三维几何表示。 目前图像三维重建的方法8主要有两大类： 一类是三维面绘制， 另一类是三维体绘制。体绘制更能反应真实的人体结构，但是由于体绘制算法运算 量太大，即使利用高性能的计算机，仍然无法满足实际应用中交互操作的需要，因 此面绘制仍是目前的主流算法。下面对这两种绘制方法作简单的介绍。 1.2.3.1 三维面绘制三维面绘制 表面表示是表示三维物质形状最基本的方法，它可以提供三维物体的全面信息， 其具体形式有两种：边界轮廓线表示和表面曲面表示。 最初的表面重建方法采用基于轮廓线9的描述方式，即在断层图像中，通过手工 或自动方式实现目标轮廓的确定性分割，然后用各层的轮廓线“堆砌”在一起表示 感兴趣物体的边界，这种轮廓线表示方法简单且数据量小，但是不很直观。 除了以轮廓线表示物体外，还可以由轮廓重建物体的表面来表示。最早的方法 是基于多边形技术，主要采用平面轮廓的三角形算法，用三角片拟合这组表面轮廓 的曲面 bussonnat 提出了另外一种基于表面轮廓的 delaunay 三角形方法，解决了系 列表面轮廓的三维连通性问题。用三角形或多边形的小平面(或曲面) 在相邻的边界 轮廓线间填充形成物体的表面，所得出的只是分片光滑的表面，l in 采用从轮廓出 发的 b 样条插值重建算法， 得到了整体光滑的表面。lorenesen 提出了一种称为 “marching cube”的算法，这是一种基于体素的表面重建方法，该方法先确定一个 表面阈值，计算每一个体素内的梯度值，并与表面阈值进行比较判断，找出那些含 有表面的立方体，利用插值的方法求出这些表面，这其实是抽取等值面的过程。 基于表面的方法，其主要优点是可以采用比较成熟的计算机图形学方法进行显 示（如裁剪、隐藏面和浓淡计算等，而这些都可以通过 opengl10来实现） ，计算量 华 华 中中 科科 技技 大大 学学 硕硕 士士 学学 位位 论论 文文 4 小，运行速度快，借助于专用硬件支持，在高性能 pc 上面绘制完全可以实现实时 交互显示。 1.2.3.2 三维体绘制三维体绘制 体绘制11由于直接研究光线通过体数据场与体素的相互关系， 无需构造中间面， 体素的许多细节信息得以保留，结果的保真性大为提高。从结果图像的质量上讲， 体绘制要优于面绘制，但从交互性能和算法效率上讲，至少在目前的硬件平台上， 面绘制还是要优于体绘制的。比较流行的体绘制方法有投影法、光线跟踪法等。 投影法12（projection）是根据视点位置确定每一体素的可见性优先级，然后按 优先级由低到高或由高到低的次序将所有体素投影到二维像平面上，在投影过程中， 利用光学中的透明公式计算当前颜色与阻光度，依投影顺序（即体素可见性优先级） 的不同，投影法分为从前至后算法与从后至前算法。一般说来，前一种算法运算速 度快，但除需一个颜色缓存区外，还需要一个阻光度缓存区；后一种算法仅需一个 颜色缓存区，并在执行过程中产生不同层面的图像，有助医生更好地理解医学图像。 光线跟踪法13（ray-casting）是在体数据进行分类后，从象空间的每一体素出 发，根据设定的方法反射一条光线，在其穿过各个切片组成的体域的过程中，等间 距地进行二次采样，由每个二次采样点的 8 个领域体素用三次线性插值方法得到采 样点的颜色和阻光度值，依据光照模型求出各采样点的光亮度值，从而得到三维数 据图象。直接体视法所面临的问题是运行速度慢，利用空间相关性可提高算法的效 率。 1.3 选题来源及论文结构选题来源及论文结构 1.3.1 选题来源选题来源 本课题的来源是“中国教育科研网格计划14”，图像处理网格应用平台建设子 项目“网格环境下数字化虚拟人的三维重建”。 采用由中国第一军医大提供的中国虚拟人15 ii 号（女性）数据集，该数据集切 削间距精度为 0.2 毫米， 由计算机 x 线断层摄影术 ct （computerized tomography） 、 mri 核磁共振成像（magnetic resonance imaging）和人体二维断层图像序列三套数 据集组成，其中人体二维断层图像包括低分辨率、中分辨率和高分辨率三种各 8556 张。 华 华 中中 科科 技技 大大 学学 硕硕 士士 学学 位位 论论 文文 5 1.3.2 论文结构论文结构 本文在研究三维表面重建算法的基础上，以数字化虚拟中国人为实例，结合数 字虚拟人原始数据数据量大、重建算法复杂的特点，重点研究采用 mc 算法进行三 维表面重建时的算法优化问题。 全文共分为五章，第一章为绪论，简要介绍了课题研究的目的和意义；概述了 三维表面重建技术的国内外发展现状。本章为论文的研究背景。 第二章主要介绍 mc 算法的基本原理，概述了 mc 算法的实现流程。在介绍算 法关键流程时，本文还用了一些算法程序伪代码对几个关键点作了详细分析。本章 为论文的理论基础。 第三章首先简单介绍了三维重建的主要流程（包括构网、平滑、简化、合并） ， 在这些流程中，平滑、简化、合并这三个流程都是基于包含拓扑信息的网格数据进 行的，因此进行三维表面重建时，在构网的同时还必须取得各三角面片间拓扑信息。 紧接着介绍了表达与保存拓扑信息的文件格式：mesh 文件格式，并对这一文件格 式如何表达和保存三角网格的拓扑信息作了详描述。本章是论文的提出问题的章节， 因为由于构网的同时需要取得并保存三角网格的拓扑信息，因此需要对 mc 算法传 统流程实施改进。从第四节开始，着重讲解 mc 算法的优化问题，针对海量断层数 据处理，如何解决边构网边获取三角网格拓扑信息时计算资源与算法程序效率的矛 盾，提出了“双缓存、三层交换”的思想，对 mc 算法实施优化，并用图表、算法 程序伪代码对这一机制的实现作了深入的剖析。本章是论文的最关键部分，是论文 的创新点，也是论文解决问题的部分。 第四章得出结论，针对数字虚拟中国人的数据集，对采用“双缓存、三层交换” 优化策略和不采用时算法程序的效率进行对比分析，得出结论。 第五章对全文的工作进行了总结，针对目前的缺点和不足之处，提出了一些看 法，并且对未来的发展趋势作了展望。 华 华 中中 科科 技技 大大 学学 硕硕 士士 学学 位位 论论 文文 6 2 mc 算法简介与实现流程算法简介与实现流程 2.1 mc 算法简介算法简介 2.1.1 基本原理基本原理 mc 算法16 17 18是三维数据场19等值面生成的经典算法， 也是体素单元内等值 面抽取技术20的代表。其基本思想是逐个处理数据场中的立方体（体素） ，分类出与 等值面相交的立方体，采用插值计算21出等值面与立方体边的交点，根据立方体每 一顶点与等值面的相对位置，将等值面与立方体边的交点按一定方式连接生成等值 面，作为等值面在该立方体内的一个逼近表示。在 mc 算法中，体素是一逻辑上的 立方体，由相邻层上的各四个象素组成立方体上的八个顶点，算法以扫描线方法逐 个处理数据场中每一立方体体素，求出每一体素内包含的等值面，由此生成整个数 据场的等值面。这一类算法所处理的数据一般是三维正交的数据场，可以适用于医 学图像序列。 mc 算法的基本假设是沿着立方体的边数据场呈连续线性变化， 也就是说， 如一 条边的两个顶点分别大于和小于等值面的值，则在条边上必有也仅有一点是这条边 与等值面的交点。确定立方体体素中等值面的分布是该算法的基础。算法中使用的 顶点及边的索引定义如图 2-1 所示。我们采用查表的方式，建立多个索引表，这样可 以加快程序的速度，可以直接由立方体各顶点的状态检索出其中等值面的分布模式， 从而确定该立方体体素内的等值面三角片连接方式。然后我们还得计算每个三角片 顶点的位置及其法向量，从而取得这个立方体的等值面（通过求得对应的标准型进 行旋转变换取得对应的三角面片序列来表达） 。 图 2-1 cube 的 8 个顶点在 cube 标准型中的位置 7 10 23 45 6 华 华 中中 科科 技技 大大 学学 硕硕 士士 学学 位位 论论 文文 7 mc 算法中， cube 的基本构型有 15 种， 如图 2-2 所示， 但有些构型存在二义性， 如图 2-3 所示，二义性的消除是将其中的某些构型再进行细分，以至最后产生 33 种 异构的构型，因此我们也经常将 mc 算法称为 mc33 算法22 23。 图 2-2 体元的 15 种构型及三角剖分图 图 2-3 连接方式二义性的二维表示 0 1 234 5 876 9 10 11 131214 华 华 中中 科科 技技 大大 学学 硕硕 士士 学学 位位 论论 文文 8 2.2 mc 算法流程实现算法流程实现 下面以 mc33 算法（每个体元有 8 个顶点，每个顶点用 0-1 两种状态来表示是 否落在等值面内，因此有 2 种状态，所以 8 个顶点共可以表达 28共 256 种组合状 态，但经过多种旋转，有许多种构型是一致的，去除这些同构的类型，最后得到 33 种异构的构型， 因此称之为 mc33 算法， 图 2-2 所示为其中的 15 种构型三角剖分图） 为例，对采用 mc 算法进行三维重建24时的算法流程做一个简单的介绍。 程序初始化 预读入一张图片 进行构网循环 再读入一张图片 分割成等长等宽等高 的小 cubes 进行构网 x、y 全 0 或者全为 15？ 开 始 否 是 分别求取 cube 的四个顶 点构成的十进制数 x、y 华 华 中中 科科 技技 大大 学学 硕硕 士士 学学 位位 论论 文文 9 图 2-4 mc 构网算法流程图 上图为 mc 算法实现流程，下面对其中各关键步骤做一个简单的介绍。 2.2.1 初始化初始化 用 mc 算法进行构网时，在构网过程中，每产生一个 cube，都需对其构型进行 判断，从而取得 cube 的标准构型，取得了标准构型后还需对 cube 进行旋转变换， 将 cube 旋转到实际状态，最后从 33 种状态表2中取得此种构型各个三角形的分布 状态。因此，初始化的时候需要构建三个表： （1）cubes 标准构型查询表 （2）cubes 旋转变换表 （3）cubes 33 种状态表 初始化这三个表后，就可方便算法程序的查询，这三个表是 mc 算法的核心所 在，在后面的部分将对这三个表做详细的阐述。 回 到 构 网 循 环 否 缓冲区已经满？ 把 数 据 写 入 txt 文件。 是 否 构网已经结束？ 结 束 是 求取 cube 所包含的三角面片的各顶点 实际坐标，并将它们写入文件缓冲区 对 cube 进行旋转变换 取得这一小 cube 的标准类型 华 华 中中 科科 技技 大大 学学 硕硕 士士 学学 位位 论论 文文 10 2.2.2 cubes 划分划分 采用 mc 算法进行三维表面重建是以物体表面轮廓数据为基础的，如数字化虚 拟中国人，基础数据是人体表面轮廓数据（对人体器官进行重建时，基础数据为人 体器官表面轮廓数据，如图 2-5 所示为人体的三张外轮廓数据） 。由于 mc 是一个等 值面重构算法，需要重构的整个外表面可以看作为一个等值面，在等值面内和在等 值面外我们用二进制数字 0 和 1 来区分，在图片上可用黑白来反映，因此基础数据 是经过数字化处理的黑白二值图片。每次构网，至少需要读入上下两张图片，构成 一个大的长方体，如采用 1200800 像素的图片进行构网时，切片之间的距离为 5 像素时，这个长方体的长、宽、高分别为 1200、800、5 像素。构网时需要将这一长 方体划分成若干个小的 cubes， 每个小 cube 也为 nn5 像素的长方体， 然后进行 下面的构网流程。因此图片读入的时候，我们需要将图片的每个像素都全部读入， 如采用 1200800 像素的图片时，每次构网就需要 12008002（每次构网需要两 张图片）的数组来保存。读入图片程序函数为： 【 方法 】void inline readbmp(unsigned char，bmpdata12008002，int floor，int index，char *path); 【 描述 】用于从 path 路径读取第 floor 层，编号为 index 的图片，并将其保存在 onebmpdata 三维数组里面 【 参数 】 bmpdata8002：三维数组，用于保存读入的两张图片的二进制信息 floor：读入图片的层数 index：读入图片的编号，0 表上面的一张，1 表下面的一张 path：字符串指针，指向读入图片的路径 由于每一张图片包含的信息量比较大，特别是采用高分辨率图片进行构网时， 因此保存图片像素信息的数组 bmpdata2的内存空间是交替使用的， 构网自上而 下进行时，假若开始读入的为 bmpdata0，第二次读入图片为 bmpdata1， 那么第一次构网就在 bmpdata0和 bmpdata1之间进行。 待这次构网完成后， 新读入的图片就存储在 bmpdata0里面，将第一张图片数据覆盖掉，因此第二次 构网就在 bmpdata1和 bmpdata0之间进行，如此类推，直至整个构网完成 为止。 采用这种方法降低内存是使用，提高构网算法程序的效率，每次构网的 cubes 划分就是在 bmpdata0和 bmpdata1或 bmpdata1和 bmpdata0之间 华 华 中中 科科 技技 大大 学学 硕硕 士士 学学 位位 论论 文文 11 进行。 图 2-5 从左至右依次为手、腹部、双腿的横界面黑白二值图 2.2.3 标准构型判断标准构型判断 每个 cube 有八个顶点，如图 2-1 所示，由 0、1、2、3 四个顶点的二进制数构 成十进制数 x 的四个位，由 4、5、6、7 四个顶点的二进制数构成十进制数 y 的四 个位，通过 x、y 这两个数（由四个二进制位构成的十进制数） ，就可以在标准构型 查询表中取得此种 cube 的标准构型。cubes 标准构型查询表如图 2-6 所示。 图 2-6 cubes 标准构型查询表 在这一表中，横、纵坐标（横坐标 x 对应表中的 msb 项，纵坐标 y 对应 lsb 项） 分别用四个二进制位来表示，其对应的十进制数分别位 x、y，每当产生一个 cube， 就可以通过 x、y 从标准构型表中查询出两个数，如 x=5，y=6 时，查询出的是 19： 12，其表达的意思是，当前 cube 的构型，经过第 19 种旋转变换，旋转后的状态为 33 种状态表中的第 12 种标准构型。后面的章节，将继续介绍旋转变换表以及 cubes 状态表的使用方法以及它们所表达的含义。 华 华 中中 科科 技技 大大 学学 硕硕 士士 学学 位位 论论 文文 12 2.2.4 旋转变换旋转变换 每个 cube 有八个顶点，如图 2-1 所示，每个顶点有 0、1 两种状态（0 表示在 等值面内，1 表示在等值面外） ，因此一个 cube 共可以表达 28即 256 种状态。在这 256 种状态中，有很多可以通过旋转顶点的方位达到一致，去除同构的 cubes，最 后得到 33 种异构的 cubes。但在每产生一个 cube 进行判断时，不是直接取得它的 最后构型状态，而是先根据各个顶点的分布，求取其对应的标准构型，因此在 2.2.3 中，x、y 查询出来的两个数中，y 表示旋转后的状态，也就经过旋转后对应的标 准型。而实际上，最终要取得的数据，是这个 cube 的实际情形，因此需要把通过 标准型所取得的各个三角面片的坐标通过旋转变换转变成当前实际坐标。 这一转变 的实现，是通过 2.2.3 中提到的 x、y 查询出来的 x 来决定采用哪一种旋转变换， 而旋转变换具体的旋转方式，就需要查询 cubes 旋转变换表，cubes 旋转变换表2 如图 2-7 所示。 图 2-7 cubes 旋转变换表 在图 2-7 中，index 表示旋转方式，如 index 为 6 时，表示采用第 6 种旋转方式 对 cube 进行旋转变换。旋转变换的进行，也通过查询此表实现，只需将 cube 的 8 个顶点按照表中所列举的规律进行互换即可。 如进行第 6 种旋转变换， 只需要将 cube 的第 7 个顶点变换到 3 的位置 （假如 7 变换到 3 我们采用 73 来表示， 如此类推） ， 接着是 67， 51，45如此类推，直至 cube 的 8 个顶点变换过来，这 就实现了 cube 的旋转变换。 华 华 中中 科科 技技 大大 学学 硕硕 士士 学学 位位 论论 文文 13 2.2.5 cube 三角面片信息的获取三角面片信息的获取 每产生一个 cube， 我们最终要获取的是这个 cube 所包含的三角面片的信息 （也 就是组成各个三角形的顶点的坐标2） ，通过这些三角面片的信息来表达这个 cube 所包含的等值面信息，因为最终可以通过绘制这些三角形来近似表达等值面，也就 是物体的外轮廓。下面以一个实例来对 cube 三角面片信息的获取做详细的阐述。 在程序初始化的时候，我们提到，需要对标准构型查询表进行初始化，其函数 原型如下： 【 方法 】void inicubestatetab(cube_state cubestatetab33); 【 描述 】对 33 种状态表中的每个状态进行初始设定值 【 参数 】cubestatetab：33 种状态表 其中包含的数据结构如下： typedef struct /定义边数据类型 int xend; /点的一个端 int yend; /点的另一个端 xy_edge; typedef struct /定义 cube 状态表类型 int len; /一种状态表的边的条数 xy_edge edge36; /状态中各条边的构成 cube_state; 在 cubestatetab33数组中，表达了 cubes 的 33 种标准状态。如在程序种，状态 2 的定义如下： /-状态二- cubestatetab1.len=3; cubestatetab1.edge0.xend=3; cubestatetab1.edge0.yend=7; cubestatetab1.edge1.xend=3; cubestatetab1.edge1.yend=2; cubestatetab1.edge2.xend=3; cubestatetab1.edge2.yend=1; cubestatetab1.len 为 3 表示第二种标准构型所包含边数，每条边取中点构成三角形 华 华 中中 科科 技技 大大 学学 硕硕 士士 学学 位位 论论 文文 14 的一个顶点， 每条边用它的两个端点来表示， 如图 2-8 所示的情形， 其表达的信息是： 第二种标准构型包含一个三角形，三角形的三个顶点分别在 37、23 和 31 所 在的边上。 图 2-8 cubes 的标准构型状态二 结合 2.2.3 以及 2.2.4 所讲解的， 假如新产生的一个 cube 的 x、 y 值分别为 1、 1， 那么查询 cubes 标准构型表得到的两个数字为：4：2，这说明，当前的 cube 是通过 第 4 种旋转， 旋转后的状态为 33 种状态表中的标准状态 2 （也就是第二种标准构型） ， 然后查询标准状态表得， 其三角形的三个顶点分别所在的边为 37、 23、 13 （如 图 2-8 所示） ，但这是标准状态，是通过第 4 种旋转变换得到的，因此不是当前 cube 的实际情形，因此我们还需要查询旋转变换表（如图 2-7 所示） ，将所取得的三角形 的三个顶点所在边旋转回实际状，通过查旋转变换表进行替换即可得到，因此，实 际 cube 的三个顶点分别所在的边为 76、37、57（因为查询旋转变换表可得， 第四种选择变换规则是：76、62、54、40、37、23、15、0 1） 。在构网时，每个 cube 的长宽高都是确定的，因此可以取一个三维绝对坐标 系计算出每个 cube 的每个顶点的坐标，从而可以取得任意一条边的中点（通常情况 下，可以近似取边的中点来求解三角形的坐标，但有些情况下，比如在数字化虚拟 中国人三维重建中，为了更准确的表达三角面片的信息，使得重构的外表面更加光 滑，三角形的顶点我们取的是这条边上表达像素信息的 0、1 的交界，因为这儿是像 素梯度变换最大的地方，最接近于等值面，也就是外轮廓） ，也就可以取得最终得到 的三角形的三个顶点的三维坐标。 2.2.6 构网循环构网循环 以上所述的是从读入两张图片到分割成若干 cubes，然后对其中的每个 cube 进 行标准构型判断，取得标准型的各个三角面片信息（也就是各个形的顶点所在边的 1 0 23 45 6 7 华 华 中中 科科 技技 大大 学学 硕硕 士士 学学 位位 论论 文文 15 端点信息） ，然后进行旋转变换，变换到实际的情形，最后获取各个顶点的三维绝对 坐标，到这一步，对一个 cube 的处理才完成，然后对后续读入的图片再划分成若干 cubes，继续进行如上类似操作，取得各个 cube 所包含的三角形坐标，直至整个构 网完成。 多层构网时，交替读入图片（如 2.2.2 节所述） ，然后进行划分，再对每个 cubes 进行如上同样的操作，当构网完成时，就可以取得所有三角面片的信息，将这些信 息保存到一个文件中，三维表面重建数据就生成了，如果我们将这些三角形绘制出 来，就可以产生如图 2-9 所示的人体外形（采用数字化虚拟中国人数据） ，这就是通 常 mc 算法进行三维重建的流程。 图 2-9 采用 mc 算法重建数字虚拟中国人的上半身图形 2.3 本章小结本章小结 本章介绍了 mc 算法的基本原理和概念，并且对算法实现的关键步骤作了比较 详细的阐述，从初始化到到 cubes 的划分，再从 cubes 标准构型判断到 cubes 的旋 转变换，到最后的 cubes 包含的三角行的顶点三维坐标的取得，这些步骤的实现， 就是一个通常意义的 mc 算法的流程实现。 在本章中，已经介绍了从原始外形轮廓数据（见图 2-5）到最终结果数据（见图 2-9）生成的整个过程，似乎利用 mc 算法进行三维表面重建的工作已经全部完成， 但实际上，本章所介绍的 mc 算法只能粗略地重建出外轮廓，如果需要进行平滑、 简化等进一步处理，仅凭这些三角形的坐标是做不到的。后续章节将阐述如何在构 网的同时获取各三角面片间的拓扑信息， 如何表达和存储这些拓扑信息， 如果对 mc 算法进行优化等问题 华 华 中中 科科 技技 大大 学学 硕硕 士士 学学 位位 论论 文文 16 3 mc 算法优化算法优化 3.1 三维重建流程三维重建流程 下面以医学图像三维重建为例来讲解三维重建的流程。医学图像三维重建是研 究由各种医疗成像设备获取的二维图像序列，构建组织或器官的三维几何模型，并 在计算机屏幕上“真实”绘制与显示的过程。 在进行重建之前，针对医学图像的特点，需要对原始数据进行初步处理，包括 对输入图像的预处理、图像分割25、模型构建、模型网格简化26等。预处理的目的 就是对其进行滤波（filtering）或平滑（smoothing） ，以实现抑制噪声，增强图像特 征，提高信噪比。先后经过手工和算法程序的处理，成为重建算法的输入数据。 1）数据预处理 对于计算机模拟或实验、测量获得的数据通常需对其进行必要的变换处理。对 原始数据的变换处理包括：（1）数据规范化；（2）滤波处；（3）平滑；（4）网 格重新划分；（5）坐标变换、几何变换、线性变换；（6）分割与边缘检测；（7） 特征检测、增强和提取等。 2）三维建模27 在利用计算机对客观事物进行分析和研究时，需要建立相应的模型来表示实际 或抽象的对象或现象，模型是客观事物的抽象表示，它描述对象的结构、属性、变 化规律或各个组成部分之间的关系。在数据可视化的建模过程中，即是将处理的数 据转变为用几何描述，建立起描述数据的几何模型。对三维标量数据，可建立表面 几何模型来表示，也可以用体素模型来表达，或者建立实体几何模型表达。 本文采用 marching cube 方法，对二维人体断层图像序列进行三维建模，得到由 三角面片组成的人体和部分器官的模型。 3）三角网格的简化 医学图像的三维重建根据输入的断层图像序列， 经分割和提取后， 构建出待建组织 的三维几何表达。本文采用mc算法重建得到的表面模型以三角面片来逼近表示。 用 mc 方法构造的组织或器官的表面模型一般都有数十万甚至上百万个三角面 片。模型的三角数量巨大，占据大量的存储容量，且难以实现对模型的实时交互绘 华 华 中中 科科 技技 大大 学学 硕硕 士士 学学 位位 论论 文文 17 制。因此，就必须对模型进行网格简化。 4）三角网格的平滑 本文采用拉普拉斯28 29（laplacian）光顺法实现网格数据的平滑。拉普拉斯光 顺法通过对每个顶点定义一个拉普拉斯算子来确定调整方向，然后沿此方向以一定 的速度移动顶点达到调整网格的目的。该方法能有效调整网格至规则形状，网格密 度与形状都趋于均匀。但对网格分布不均匀及含有大量不规则三角片的模型，这种 均一化的调整往往会导致原始模型的大范围变形。 如中国虚拟人女 ii 号三维重建流程30如图 3-1 所示。 图 3-1 数字虚拟中国人三维重建流程 输入数据集 开 始 构构 网网 平 滑 简 化 合 并 文件格式转换 结束 注释： 经过预处理的人体断层图像， 采用黑白位图文件格式存储 结果为自定义的 mesh 文件格式， 该格式保存了重建结果的拓扑信 息，采用边构网边存 mesh 方法 改善重建结果不够光顺 的情况，可选择平滑次数 减少表面模型的三角面数 量，简化程度由参数输入 将重建的人体不同部分数据无 缝合并起来，不破坏拓扑关系 最终结果为 txt 文本格式文件，每 行分别存储三角面片的三个顶点 坐标，通过绘制三角形显示人体 华 华 中中 科科 技技 大大 学学 硕硕 士士 学学 位位 论论 文文 18 3.2 mc 算法流程改进算法流程改进 在图 2-4 中介绍了 mc 算法的实现流程，在整个三维重建流程中，它所实现的 是“构网” （如图 3-1 所示）步骤，但在三维重建的过程中，还有几个至关重要的步 骤：平滑、简化以及合并。 平滑就是采用一些平滑算法，将原来由大量小三角面片构成的等值面归并成由 较少的多边形面片构成的等值面，从而改善三维重建的效果，提高三维绘制的速度。 对于数字虚拟人而言，就是要让最后绘制出的人体，表明比较光滑，尽量降低表明 的粗糙度，尽可能呈现一个良好的视觉效果。 简化就是采用一些简化算法，去除冗余信息（mc 算法产生的三角形数量巨大， 其中包含了大量冗余信息） ， 从而提高三维重建的速度。 对最终结果最直接的影响是： 几乎可以绘制出简化前的效果，但数据量大为减小。 合并是当我们将程序并行化，进行分布式计算时，如进行数字虚拟中国人三维 重建时，需要把一个人体的重建工作分配到集群计算机的各个不同的结点，最后把 不同部分的人体数据无缝拼接起来。由于程序最终会在集群计算机上并行运行，人 体的不同部分会分配到不同的结点计算，因此这一工作对于整个数字虚拟人三维重 建显得十分重要。 图 3-2 数字虚拟中国人三维重建数据流示意图 上面提到的三个重要步骤：平滑、简化和合并，它们是基于三角面片间的拓扑 关系进行的，也就是说，要进行平滑、简化操作，首先我们得取得各三角面片间的 节点 1 节点 2 节点 n 断层数据 集群计算网格数据 平滑 简化 平滑 简化 平滑 简化 合并成 一个 mesh 华 华 中中 科科 技技 大大 学学 硕硕 士士 学学 位位 论论 文文 19 拓扑关系。拓扑关系的取得，常见的有两种方法：第一种就是先对整体构网，然后 再从构网产生的三角面片中提取拓扑信息；第二种是边构网边产生。这两种方法， 前者为两个分开的步骤进行的，效率相对比较低下；后者是构网和求拓扑关系同时 进行，效率相对比较高。因此在处理实际问题时，我们通常取后者来求解拓扑关系。 所以，要想同步取得各个三角面片间的拓扑关系，我们需对 mc 算法关键流程作一 定的改进：增加拓扑关系求解这一步骤。此时新的 mc 算法流程如下： 否 程序初始化 预读入一张图片 进行构网循环 再读入一张图片 分割成等长等宽等高 的小 cubes 进行构网 x、y 全 0 或者全为 15？ 取得这一小 cube 的标准类型 开 始 是 分别求取 cube 的四个顶 点构成的十进制数 x、y 华 华 中中 科科 技技 大大 学学 硕硕 士士 学学 位位 论论 文文 20 图 3-3 mc 构网算法流程改进图 由图 3-3 跟图 2-4 对比可以看出，对 mc 流程的改进主要表现在图 3-3 中加黑的 部分，也就是求解三角面片拓扑关系的这部分，在后面的章节，将详细阐述如果表 示和求解各个三角面片之间的拓扑关系。 3.3 三角面片间拓扑关系的表示与存储三角面片间拓扑关系的表示与存储 3.3.1 三角面片拓扑关系的表示三角面片拓扑关系的表示 一般来讲，网格数据应包含有空间信息（顶点的坐标）和拓扑信息（各三角形、 边及顶点之间关系） 。 耿国华等人31针对断层数据的三角网格构造32 33， 对 marching cubes 算法进行了改进，通过分配一个缓冲区 buffer 来存储当前层中每条 cube 边上 的顶点的编号，从而实现了三角面片的生成与组织同步完成。此方法的原理是根据 回 到 构 网 循 环 否 缓冲区已经满？ 把数据写入 mesh 文件。 是 否 构网已经结束？ 结 束 是 求取这些顶点以及它们构成的边、三角形之间的拓扑求取这些顶点以及它们构成的边、三角形之间的拓扑 关系，并将点、边、三角形及拓扑关系写入缓冲区关系，并将点、边、三角形及拓扑关系写入缓冲区 对 cube 进行旋转变换 求取 cube 所包含的三角 面片的各顶点实际三维坐标 华 华 中中 科科 技技 大大 学学 硕硕 士士 学学 位位 论论 文文 21 一个三角面片只能与当前处理立方体和周围与该立方体相邻的立方体中的三角面片 有共同特点，在查找三