吴建伟 ，王子牛

(1. 贵州大学计算机科学与信息学院，贵州贵阳550025;2. 贵州大学网络与信息化管理中心中心，贵州贵阳550003)

医学图像三维重建就是利用二维医学图像序列(如CT 切片，即计算机断层扫描切片)重建出三维图像模型，图像三维重建的常用算法主要包括体绘制和面绘制。体绘制能表现更多结构上的细节，但要达到满意的精度则需要很大的运算量，运行和存储性能难以得到满足。于是，面绘制成为医学图像三维重建的主流算法。MC(Marching Cubes)算法是面绘制中的经典算法，由W.E.Lorenson 和H.E.Cline 在1987 年提出［1］。MC 算法较好的解决了在标量数据场中抽取等值面的问题，适合在不规则的医学体数据场中进行等值面重建，并以大量的三角面片逼近真实的医学三维图像。但是，MC 算法也有一些缺点，主要在于抽取等值面时存在拓扑结构二义性［2-5］，处理的数据量大时对处理速度和存储空间要求很高。随着计算机硬件和并行计算的发展，后一问题得到了一定程度的缓和，而本文主要关注前一问题。作为MC 算法的发展，MT(Marching Tetrahedrons)算法［6］没有等值面抽取的二义性问题，但计算量是MC 算法的好几倍。为了在不明显增加计算量的前提下，较好的解决MC 算法的二义性问题，本文结合两种算法的优点，提出一种改进算法，在CT 图像三维重建的实验中进行了验证，并得到了较好的结果。

1 MC 算法

1.1 MC 算法的基本原理

假设有一个CT 切片数据集，可以看作是一个三维标量数据场，其中每一个切片其实是一个二维数组，数组中的某一位置的值即该标量数据场中该位置的标量值。在相邻两层切片中分别各取4 个数据点，构成一个小立方体，称为立方体素，而整个标量数据场可由这些立方体素的集合表示。MC算法就是对这些立方体素一个一个的进行处理，抽取等值面。首先设定一个等值面值，对每一个立方体素的8 个顶点，若其顶点的标量值:

(1)小于等值面值，则该顶点在等值面内部;

(2)等于等值面值，则该顶点在等值面上;

(3)大于等值面值，则该顶点在等值面外部。

可将在等值面内部的顶点标记为1，其余顶点标记为0，然后将8 个标记值按一定顺序排列，可由一个字节表示。由于每个顶点的标记值有两种可能，故每个立方体素的顶点状态共有28=256 种可能。而每一个顶点状态确定了立方体素各边是否与等值面相交，从而确定立方体素三角面片的拓扑状态。通过旋转对称性和互补对称性可将一个立方体素的拓扑状态归纳为以下15 种情形，如图1 所示:

图1 立方体素15 种基本拓扑状态

1.2 立方体素的边与等值面的交点

在确定立方体素的拓扑结构后，应该计算出立方体素与等值面的交点。可以假设数据场中各点的值沿立方体素边界呈线性变化，这样就可以通过线性插值的方法求出立方体素的边与等值面的交点，即三角面片的顶点。设立方体素某边与等值面相交于一点P，该边的两个端点坐标为(x1，y1，z1)，(x2，y2，z2)，标量值为V1，V2，等值面值为V，那么P点的坐标(x，y，z)为:

1.3 三角面片的顶点法向量

在OpenGL 中绘制三角面片需要提供三角面片顶点的法向量，从而可以使用光照效果。由于数据场中各数据点的标量值的梯度垂直于等值面，所以数据场中某点P 的法向量可用该点处的梯度代替。设P 点处的法向量为n(x，y，z)，其计算公式为:

其中，V(i，j，k)代表点(i，j，k)处的标量值，Δx，Δy，Δz 为三个方向上的立方体素的边长。

三角面片的顶点是通过对边上两端点坐标进行插补得到的，如式(1)。同样，在已经求得各数据点的法向量后，可以通过对边上两端点的法向量进行插补来得到三角片顶点的法向量。顶点法向量的计算公式仍为式(1)，但(x1，y1，z1)，(x2，y2，z2)分别表示两端点的法向量，(x，y，z)为要求的顶点法向量。

1.4 MC 算法的二义性

在图1 中，有些顶点状态下，可以有两种不同的交点连接方式，也就会得到不同的三角面片，即存在二义性问题。MC 算法的二义性问题包括立方体素面二义性和体二义性。

(1)立方体素面二义性

在立方体某一面的两个对角顶点的标量值小于等值面值，而另外两个对角顶点的标量值大于等值面值时，就会有两种交点连接方式，如图2 所示:

图2 立方体素表面的不同交点连接方式

(2)立方体素体二义性

正如立方体素表面存在不同的交点连接方式，立方体素内部也有类似情况，比如当立方体素的两个体对角顶点在等值面内部，而其余顶点均在等值面外部时，有如图3 所示两种连接方式:

图3 立方体素内部的不同交点连接方式

2 MT 算法

MT 算法与MC 算法的不同在于它把一个立方体再细分为若干个四面体，常见的划分方法将一个立方体划分为5 个，6 个或24 个四面体。四面体是最简单的多面体，其等值面拓扑结构可归结为3种，如图4 所示:

图4 四面体素的3 种拓扑状态

类似于MC 算法，只要确定了四面体的4 个顶点的标记状态，就可以确定等值面与四面体边的交点的连接方式，也就得到了用来逼近等值面的三角面片。重要的是，对于一个四面体来说，其边上的交点的连接方式是唯一的，即对于单个四面体来说其交点的连接不存在二义性。但是若相邻两个立方体的剖分为四面体的方式不一致，则会产生剖分二义性。如图5 所示，这两个立方体剖分后，在其相接的面上两条剖分线并不重合，这可能使得两个立方体中生成的三角面片不能以一致的方式进行连接，导致空洞的产生。

图5 相邻两立方体剖分不一致

3 基于MC 和MT 算法的改进算法

为了避免MC 算法的面和体二义性，需先判断立方体是否具有面和体二义性，这可以用一个二义性表来枚举所有256 种情况。若立方体不具有面和体二义性，可以用MC 算法进行处理;否则，对立方体执行MT 算法，把立方体剖分为多个四面体进行处理［7］。然而，对立方体进行剖分会产生剖分二义性问题:一方面，相邻的两个剖分立方体之间可能拓扑不一致，如前面的图5 所示;另一方面，剖分立方体也可能与相邻的未剖分的立方体拓扑不一致。如图6 所示，两个相邻的立方体中的三角面片没有严密的连接起来，从而形成了中间白色区域的空洞。

图6 剖分立方体与相邻的未剖分立方体拓扑不一致

下面将分别讨论这两种情形。

3.1 相邻两剖分立方体之间拓扑不一致

图7 立方体6 -剖分的一种方式

MT 算法常用的立方体剖分方式有5 -剖分，6-剖分和24 -剖分。为了避免相邻两个剖分立方体之间的拓扑不一致性，可以使用一种6 -剖分方式，如图7 所示:在这种剖分方式下，立方体的左右两面的剖分线方向相同，因此在横向方向上的两个相邻剖分立方体之间是拓扑一致的。同理，在另外两个方向上，两个相邻剖分立方体之间也是拓扑一致的。所以，只要相邻的剖分立方体的剖分都使用如图7 所示的方式，就可以避免它们之间的剖分二义性问题。

3.2 剖分立方体与相邻的未剖分立方体拓扑不一致

对于相邻两个立方体中一个是有二义性需要剖分成四面体，另一个是没有二义性不需要剖分成四面体的情形。可以将没有二义性的立方体在每个面上作一条对角线，该对角线的方向需与图7 中的一致。这样，剖分立方体和未剖分立方体在其相接的表面上的拓扑是完全一致的，也就不存在剖分二义性了，如图8 所示:

图8 两个不同立方体的拓扑一致性

需要注意的是，当一个立方体在每个面上各增加一条对角线之后，立方体的边由12 条增加到18条。因此，MC 算法原有的相交边索引表不再适用，需要重新生成。同样，原有的三角面片索引表也需要根据新的立方体结构重新生成。

4 实验结果及分析

本文的实验环境为:CPU 为AMD Athlon II X4 640 Processor，800 MHz × 4;内 存2G;显 卡 为NVIDIA GeForce GTS 450;操作系统为32 位Ubuntu14.04;编译器为gcc 4.6。

使用的CT 数据为:大脑，200 ×160 ×160，8位;腹部及骨盆，512 ×512 ×174，8 位。传统的MC算法，MT 算法与改进后的算法的三维重建效果如图9，图10 所示。

实验结果数据的比较见表1。

图9 大脑表面三维重建图像

图10 腹部及骨盆部位三维重建图像

表1 传统算法与改进算法的实验结果数据

对比图9 右边的局部放大图可以看出，MC 算法生成了不正确的三角面片，而MT 算法和本文的改进算法均生成了正确的三角面片。另外，MT 算法和本文改进算法的重建图像显示了更多的细节，在重建精度上比MC 算法高。从表1 可知，本文改进算法的执行时间介于MC 算法和MT 算法之间，并且更接近于MC 算法。

5 结语

针对MC 算法二义性和MT 算法计算量大的问题，提出了一种结合两种算法优点的改进算法。该算法解决了MC 算法的二义性问题，三维重建效果更接近于MT 算法，而计算量更接近于MC 算法，从整体上优于这两种算法。本文实现了传统的MC 算法，MT 算法和本文提出的改进算法，实验结果与预想的效果一致。

［1］Lerensen W E，Cline H E. Marching cubes:A high resolution 3D surface construction algorithm［J］. Computer Graphics，1987，21(3):163 -169.

［2］T S Newman，H Li.A survey of the marching cubes algorithm［J］.Computers Graphics，2006，30(5):854 -879.

［3］王晓，何建英.考虑MC 算法二义性后的三角化方法［J］.湖北工业大学学报，2007，22(6):65 -68.

［4］杨吉宏，薛凌燕，张民，等.基于Double Marching Cubes 的表面重建算法［J］.计算机工程与设计，2010，31(4):795 -797.

［5］A Gueziec，R Hummel.Exploiting Triangulated Surface Extraction using Tetrahedral Decomposition［J］.IEEE Transactions on Visualisation and Computer Graphics，1995(4):328 -342.

［6］Nielson G M，Hamann B. The asymptotic decider:Resolving the ambiguity in marching cubes［C］//Proceedings of Visualization ’91，San Diego:IEEE，1991:83 -91.

［7］Huiyan Jiang，Ye Zhang，Yudong Zhao.A medical image 3D reconstruction method based on improved MC and MT algorithms［J］.Industrial Electronics and Applications，2009(25 -27):3765 -3768.