MC算法在医学图像三维重建中的应用

叶含笑 高智峰 江依法

摘要： 详细介绍了MC算法，提出了优化网格模型简化算法。优化网格模型简化算法选取坐标点的原则是，尽可能地接近原始网格，通常采用子集选择法或优化选择法。在尽可能保证图像精度的前提下，优化网格模型简化算法可以提高运算速度，而单纯的网格算法由于失真严重而缺乏实用价值。基于体绘制的网格化简化算法重建的三维模型比较完全，且算法简单，在多排螺旋CT等医学图像三维重建中有较好的应用。

关键词： 三维重建； 移动立方体算法； 面绘制

中图分类号：TP文献标志码：A文章编号：1006-8228（2012）04-12-03

Application of improved MC algorithm in 3-D reconstruction of medical image

Ye Hanxiao1, Gao ZhiFeng2, Jiang Yifa1

（1. Zhejiang Chinese Medicine University， Hangzhou， Zhejiang 310053， China； 2. Zhejiang XinHua Hospital）

Abstract： 3D reconstructions has been widely used in the field of medical disease diagnosis and Marching Cube algorithm (MC) is the most representative structure in the face of 3D reconstructions. The authors introduce in the paper the principle of MC algorithm, and present a simplified algorithm based on optimized grid model. The simplified algorithm selects points as close to original grid as possible, usually using the subset selection method or the optimized selection method. To ensure the best possible result in image accuracy, the simplified algorithm will improve the computation speed, while the pure grid algorithm is not practical due to serious distortion.The experiments show that the simplified algorithm based on optimized grid is better than pure grid algorithm in 3D reconstruction, and has better application in the reconstruction of multiple detector-row CT images.

Key words： 3d reconstruction； Mobile cube algorithm； Volume rendering

0 引言

医学图像三维重建技术最早可以追溯到20 世纪70 年代初。由于集成三维重建平台的医学影像设备价格昂贵等客观原因，国内医学图像三维可视化诊断起步较晚，到90年代某些高校才开始进行各层面上的研究[1]。随着计算机技术的发展，短短几年，三维重建技术已成为人们探索生命奥秘，以及疾病诊断、手术规划的重要手段。

1 常见的医学三维重建素材

电子计算机断层扫描Computed tomography，简称CT，是电子计算机和X线相结合的一项新颖的诊断新技术。其主要特点是具有高密度分辨率，比普通X线照片高10～20倍[2]。CT能准确测出某一平面各种不同组织之间放射衰减特性的微小差异，并以数字图像方式显示，能极其精细地区分出各种软组织的不同密度，从而形成对比。例如，头颅X线平片不能区分脑组织及脑脊液，但CT不仅能显示出脑室系统、还能分辨出脑实质的灰质与白质。CT如再引入造影剂以增强对比度，其分辨率更为提高，可加宽疾病的诊断范畴，提高诊断正确率。

磁共振成像Magnetic Resonance Imaging ，简称MRI。磁共振成像是断层成像的一种，它利用磁共振现象从人体中获得电磁信号，并重建出人体信息。1946年斯坦福大学的Flelix Bloch和哈佛大学的Edward Purcell各自独立发现了核磁共振现象。1972年Paul Lauterbur 发展了一套对核磁共振信号进行空间编码的方法，这种方法可以重建出人体图像。磁共振成像技术与其他断层成像技术有一些共同点，比如它们都可以显示某种物理量（如密度）在空间中的分布。同时磁共振成像也有自身的特色，可以得到任何方向的断层图像、三维体图像、甚至可以得到空间——波谱分布的四维图像。

目前，医学图像三维重建方法主要有面绘制、体绘制以及由物体表面的二维灰度图像重构其三维几何形状法或称明暗恢复形状法等几种。

2 Marching Cubes算法基本原理

移动立方体Marching Cubes[3]算法是Lorensen等人在1987年提出的等值面构造方法，一直沿用至今，是体素单元内等值面抽取技术的代表[4]。所谓等值面，是指在一个网格空间中由采样值等于某一给定值的所有点组成的集合。该算法的本质是将一系列两维的切片数据看做是一个三维的数据场，从中将具

有某种域值的物质抽取出来，以某种拓扑形式连接成三角面片。

等值面是空间中所有具有某个相同值的体素点的集合，体素点的值采用V0~V7八个点在体素区域内三线性插值的结果。可以表示为：c是常数。F(f)为体数据f中的等值面。计算公式可表达为：

⑴

其中α0,α1,……,α7是由V0~V7八个定点的值决定的常数。

在MC算法中，假定原始数据是离散的三维空间规则数据场如图1所示。用于医疗诊断的断层扫描(CT)及核磁共振成像(MRI) 等产生的图像均属于这一类型。

图1三维空间规则数据场

MC算法的基本思想是逐个处理数据场中的体素，如图2所示，分类出与等值面相交的体素，采用插值计算出等值面与体素棱边的交点(V0~V7) 。根据体素中每一顶点与等值面的相对位置，将等值面与立方体边的交点按一定方式连接生成等值面，作为等值面在该立方体内的一个逼近表示。在计算出关于体数据场内等值面的有关参数后，利用常用的图形软件包或硬件提供的面绘制功能绘制出等值面[5]。

图2体元素图

等值面的绘制一般采用二值化的方法，即通过与给定阀值的比较来确定该点的值(0或1)，顶点密度值＜域值为Outside的为1，顶点密度值≥域值Inside的为0。V0~V7每个顶点有Outside和Inside 2个状态，因此8个顶点共有256种组合状态，根据互补对称性以及旋转对称性，共有15种三角构型。在重建时根据索引进行查找时，每个索引分为索引，旋转，三角模型三部分。Marching Cubes算法主要流程如下：

⑴将三维离散规则数据场分层读入内存。

⑵扫描两层数据，逐个构造体素，每个体素中的8个角点取自相邻的两层；8个定点可定义为(i，j，k)，(i+1，j，k)，(i+1，j+1，k)，(i+1，j，k+1)，(i+1，j+1，k+1)，(i，j+1，k+ 1)，(i，j+1，k)，(i，j，k+1)(如图3所示)。

⑶将体素每个角点的函数值与给定的等值面值c比较，根据比较结果，构造该体素的状态表。

⑷根据状态表，得出将与等值面有交点的边界体素。

⑸通过线性插值方法计算出体素棱边与等值面的交点。

⑹利用中心差分方法，求出体素各角点处的法向量，再通过线性插值方法，求出三角面片各顶点处的法向。

⑺根据各三角面片上各顶点的坐标及法向量绘制等值面图像。

图3体元素坐标点图

3 空间等值点的判断及等值面与体素边界的交点计算

任取一离散网格棱边，设棱边上两结点分别为：Mi(xi, yi, zi, qi)和Mj (xj, yj, zj, qj)；取量值的等值为C，当满足(q-c)(q-c)≤0（等值点判定条件式）则Mi和Mj两点间取等值点Mo。另设等值点Mo的坐标为(xo，yo，zo)，由Mi和Mj两点根据线性插值可得公式⑵：

⑵

式中k=(qi-c)(qj-c)≤0。根据等值面判定条件式⑴，和等值点坐标公式⑵可以按结构离散信息对网格棱边进行搜索判断，从而求出指定域中结构体所有等值点。求出等值点以后，就可以将这些等值点连接成三角形或多边形形成等值面的一部份。

4 等值面的法向量的计算

为了利用图形硬件显示等值面图像，必须给出三角面片等值面的法向，选择适当的光照模型进行渲染，生成真实感图形。对于等值面上的每一点，其沿面的切线方向的梯度分量应该是零，因此沿该点的梯度矢量方向也就代表了等值面在该点的法向。等值面往往是具有不同密度物质的分界面，因而其梯度矢量值不为零，即公式⑶：

⑶

直接计算三角面片的法向是费时的，为了消除各三角面片之间的明暗度的不连续变化，只要给出三角面片各顶点处的法向，并采用Gouraud模型绘制各三角面片。这里我们采用中心插分方法来计算各体素各角点的梯度。在三角形的情况下，计算出每一个三角形面片的法向量，然后用三角面的法向量求得每个顶点的法向量，最后用三角形三个顶点的三个法向量插值求出三角形面上某一点的法向量。对于等值面来说有简单的方法计算顶点的法向量。考虑到等高线的梯度方向与等高线的切线垂直，因此，可以用梯度矢量代替等高线的垂直线。在三维情况下，等值面的梯度方向就是等值面的法向方向。由此，可得到公式⑷：

⑷

5 Marching Cubes的优化--网格模型简化算法

网格模型简化算法已经取得了一系列的成果。目前的简化算法大多考虑以边折叠前后的模型几何位置变化为折叠代价，从而减少多边形的数量，以达到提高运算效率的目的。网格简化算法的目的是在尽可能保证图像精度的前提下提高效率。因此，选取坐标点的原则是尽可能接近原始网格，一般有子集选择法和优化选择法[6]两种子集选择法即简单地在边的两个端点中选择代价较小的那一个，优化选择法则是选取二次误差最小的点v作为折叠点，该点所对应的二次误差测度为，而点v的二次误差是二次方程，求其最小值就是求方程对x，y，z偏导为零的点，解出的x，y，z即为新的顶点坐标。这一过程等价于公式⑸的矩阵方程求解。

⑸

折叠代价的度量

折叠代价的计算分为两步。第一步：计算每个顶点的二次误差侧度时，以Garland的标准二次误差测度为基础，同时考虑周边三角形面积的影响，计算每个顶点的二次误差测度均值；第二步：计算边折叠代价时，以边的长度和边折叠后所引起的三角形形态变化的程度作为加权因子。

具体计算方法为：在三维空间中，平面P可以表示为ax+by+cz+d=0，也可以表示为PTv=0.其中P=[a，b，c]T是平面P的单位法向量，且有，d为常量。模型空间中任一点v=[x，y，z，1]T到该平面的距离的平方为公式⑹：

⑹

网格模型中的任意点v=[x，y，z，1]T的二次误差Δ(v)的定义为该顶点到与该定点相关的平面的平方和，可以表示为公式⑺：

⑺

其中，planes(v)表示所有包含定点v的三角平面构成的一个集合，称为顶点v的相关平面集。初始状态下网格模型中每个点的二次误差为0，上式变形后可以得到公式⑻。

⑻

其中kp为平面P的二次误差测度。

⑼

而，

称为v=[x，y，z，1]T的二次矩阵。

称为点v的二次误差。当进行边折叠时，可使用一个附加规则(Garland et al. ， 1987)获得点v处的二次误差测度，该顶点的二次误差值为，也就是该边的折叠代价。

6 网格简化算法在医学三维重建上的应用

网格算法一般应用于加快三维重建的速度，但是单纯的网格算法却缺乏实用价值。相对于其高速的绘制，损失的精度是无法接受的。因此，对网格简化算法又进行了进一步的优化—基于体绘制的网格简化算法。

体绘制是将切片中所有的物质（皮肤、骨骼、肌肉等）集中在一幅图中显示。但在只需要观察骨骼的情况下，很多的三角面绘制都是没有意义的。忽略那些不必要的三角面可在保证精度的同时有效地提高重建速度。

7 结束语

MC算法通过对比阀值来确定体素的多边形，在面对大容量数据时往往有着速度慢这一无法回避的缺点，但现在各种有针对性的改进使得它有了更大的发展潜力，所以MC算法不仅仅是个单纯的算法，它更接近于“体素” 这个概念。现在流行的很多三维重建算法都是基于MC进行改良的，目的是为了获得所需要的特定的三维模型。象基于小波变换的医学图像融合算法，断层医学图像插值算法等，则主要是为了使CT等数据容易受到MC算法中阀值的分割。现在，OpenGL，VTK等图像函数库的使用已使得三维图像建模变得简单期望三维重建技术在医学上的应用会有更大的发展。

参考文献：

[1] 蒲超,张育民.医学图象三维处理算法与应用[J].兵工自动化,2004.6:210~212

[2] 罗述谦,周果宏,石教英.基于三角形移去准则的多面体简化模型[J].计算机学报,2008.2:135~138

[3] Nielson GM.Dual Marching Cubes.IEEE Visualization 2004.

[4] 田捷,包尚联,周明全. 医学图像处理与分析[M].电子工业出版社2003.

[5] 金天弘,刘振宅. 医学图像三维重建的研究[J].医疗卫生装备,2008.2:34

[6] 杨加,吴祈耀,田捷.几何图像的分割法在CT图像分割上的实现和比较[J].北京理工大学学报,20.6:720~724