基于改进移动立方体算法的三维重建

胡凌燕，史康柏，徐少平，刘小平

(南昌大学信息工程学院，江西 南昌 330031)

医学图像三维重建技术已广泛应用于医疗诊断和构建高精度虚拟三维模型等领域。随着CT、MRI等医学成像技术的飞速发展，空间数据采集量越来越大，高精度大数据的医学影像三维绘制技术一直是研究热点[1]。三维重建技术所用主要算法是三维面绘制中的移动立方体(marching cubes， MC)算法[2]，其核心是从体数据中提取出由面片模拟的阈值面，再将所有阈值面按照一定拓扑关系组成等值面，因此也被称为等值面提取算法。MC算法原理简单、应用广泛，但当体数据密度较大时，体元产生的面片面积较小，导致面片运算量过大，拓扑结构复杂，渲染时间较长，影响生成组织三维模型的精确性和真实性。

目前许多虚拟现实平台采用改良MC算法进行组织器官图像三维重建。Du等[3]采用多边形等值面扩展算法来遍历相邻立方体，使渲染时间缩短，存储空间减少。Mun等[4]采用基于二次误差度量技术的三角面片抽取方法减少了MC算法生成的三角面片数量。高峰等[5]采用种子体元衍生等值面方法，以避免对无用体元的遍历，减少渲染时间。但这些算法重建过程中的模型精确性和交互性相对较弱，对于后续虚拟康复训练和医学辅助诊治的作用有待提高。Wijewickrema等[6]将改进的MC算法用于分段离散的体数据，生成了光滑的三维曲面。Chen[7]采用等间距阈值法代替传统的等值面阈值法，使改进的MC算法更适用于材质移除的虚拟仿真平台上。但这些相关MC算法需要生成大量的多边形面片，拓扑结构复杂，计算量大。本研究提出一种基于区域增长法的通用树结构和移动等值点法的自适应改进MC算法。

1 原理与方法

基于区域增长法的通用树结构和移动等值点法的改进MC算法包括基于交互式区域增长算法的医学图像分割、建立通用树结构、移动等值点合并三角面片法三部分，具体流程见图1。

1.1 基于交互式区域增长算法的医学图像分割 在医学图像上选取1个或多个种子点，种子点自适应地向相邻空间剖分，遍历周边体元，寻找并标记所有与指定阈值相交的体元，生成三角面片，完成相关组织器官的分割。

选取种子点时，需要根据指定阈值选择1个或多个体素。先找到需要三维建模组织轮廓的切片层，对切片层进行边沿轮廓提取，将边沿点或相邻切片层对应的边沿点设为种子点。在种子点处进行相邻8领域的扩展，计算待加入像素点灰度值与所有种子点平均灰度值的差，当其绝对值小于或等于设定的灰度值阈值时，将该像素点并入种子点区域(图2)。当不再有符合区域生长条件的像素点时，终止区域增长算法。至此，与阈值相交的所有体元标记完成，三角面片全部生成，组织器官分割完毕。

图1 基于交互式区域增长法的通用树结构和移动等值点结合的改进MC算法流程图

1.2 建立通用树结构 根据分割的相关组织器官的空间大小，确定所建通用树结构的层数和子节点个数，制定体元顶点索引方式。将与阈值相交的体元全部插入到创建的通用树结构中。

创建通用树需要确定树的层数和每一层的子节点个数。根据基于区域增长算法分割好的组织器官的空间范围，找到最小2的幂的包围盒[8]。假设分割好的组织范围是(200，220，240)，3个坐标值中最大的数为240，而比240大的最小2的幂为28，通用树算法可调用相关的库函数来设定树包围盒为(256，256，256)，树层数为8，每层子节点为8个。同理，若分割好的组织空间范围为(400，300，200)，则树包围盒为(512，512，512)，树层数为9，每层子节点数为9个。

为更直观、形象地说明通用树结构的创建和顶点索引方式，以层数为8的通用树结构举例说明。子节点的编号顺序采用按0～7的二进制位cba分配法，a=1表示沿x轴的正方向，a=0表示沿x轴的负方向；b=1表示沿y轴的正方向，b=0表示沿y轴的负方向；c=1表示沿z轴的正方向，c=0表示沿z轴的负方向。子节点的编号顺序见图3。

通过交互式区域增长算法选定的体元中的角点(A，B，C)插入通用树的步骤如下：①将A、B、C均按二进制展开为8位(A1A2A3A4A5A6A7A8，B1B2B3B4B5B6B7B8，C1C2C3C4C5C6C7C8)；②将(A，B，C)插入n层的第An+2Bn+4Cn个子节点(n为0～7)。

图2 区域增长算法示意图 A.体素灰度值图，其中红色区域为原始种子点； B.区域增长算法的生长轨迹图，种子点区域沿黑色箭头生长，当灰度值为32的种子点进行相邻区域衍生时，灰度值为33的体素符合门限灰度值的界定，因此将灰度值为33的体素并入种子点区域。同理，灰度值为35和34的体素也成为种子区域 图3 通用树子节点的编号顺序

若这些子节点为空，则将(A，B，C)插入；若有些子节点不为空，表示子节点已经有其他体素插入，则(A，B，C)跳过不为空的子节点，插入为空的子节点，以此避免多次插入遍历，减少算法执行时间[9]。将所选定体元的角点坐标依次插入通用树中，每个包含等值面的体元都处在树的子节点上，通用树结构创建完成。

1.3 移动等值点合并三角面片法 将体元棱边上的等值点移动至最近的体元顶点，合并存储在通用树结构中体元内的共面三角面片，以减少三角面片个数。选择顶点代替原等值点，顶点信息储存在通用树结构的子节点中，不需要计算等值点的坐标和法向量，大大提高了算法执行效率。连接新的三角面片，形成最终的三维组织模型。

每个体元对于体数据而言都是一个微小的空间，与阈值相交的体元最多含有4个三角面片，每个三角面片都很小，甚至可与显示屏的像素点大小相似，因此，三角面片的顶点在体元插值边上局部移动对三维重建整体视觉化影响很小。本研究将等值点按照就近原则移动到插值边的相邻端点，即体元的顶点；将相同平面上的小三角面片合并，形成大三角形面片，以减少共面三角面片数量和拓扑结构复杂性，部分三角面片合并示意图见图4。在传统MC算法中，每次线性插值需要数次代数运算，而本文选择用体元顶点代替等值点，直接调用通用树结构中的子节点信息，避免了通过线性插值等算法计算等值点的法向量和坐标点，可大大减少算法执行时间。获取三角面片的顶点的坐标和法向量后，即可将所有新三角面片提取出来，连接成统一的等值面，完成基于医学图像的三维组织重建。

2 结果

本文算法实验仿真编译采用Microsoft Visual Studio 2012和OpenGL库，操作系统为64位win7系统，CPU为英特尔i7-6700，8.00GB内存。数据来自1名29岁男性志愿者的腹部CT扫描图像。采用Siemens Force双源CT扫描仪，电压120 kV，电流240 mA，图像层厚1 mm，像素512×512，共361幅图像。从该CT数据文件中提取肾脏数据(图5)，并进行三维重建，以便后续进行虚拟手术。

基于CT数据，分别采用传统MC算法和改进MC算法构建肾脏三维模型。基于传统MC算法生成的肾脏三角面片拓扑结构复杂，三角面片数量较多；与之相比，基于改进MC算法生成的肾脏三角面片拓扑结构简单，三角面片较少(图6)。基于传统MC算法生成的肾脏三维模型表面存在许多凸凹，模型精确度较差；而基于改进MC算法生成的肾脏模型渲染效果较好，三维模型表面平滑逼真，局部细节真实性较好(图7)。对于同样的CT扫描数据和相同的阈值分割提取，改进MC算法遍历体元个数明显减少，生成三角面片个数减少39.20%，算法执行效率提高37.59%(表1)。将基于改进MC算法生成的肾脏组织三维模型应用于虚拟手术平台，操作者可以通过该模型进行虚拟手术操作(图8)。

图4 三角面片合并示意图 A、B.合并前的两种共面三角面片； C、D.合并后的两种共面三角面片

表1 传统MC算法和改进MC算法性能对比

图5 志愿者CT图像，白色轮廓是即将分割重建的肾脏组织 A.冠状位； B.矢状位； C.轴位 图6 肾脏的同一区域的三角面片图 A.传统MC算法； B.改进MC算法

图7 肾脏组织三维重建效果图 A.传统MC算法； B.改进MC算法 图8 肾脏三维重建模型应用于虚拟手术平台

3 讨论

本文提出了一种基于区域增长法的通用树结构和移动等值点的自适应改进MC算法，用于对组织器官构建三维模型。传统MC算法大多采用阈值分割方法对体数据进行预处理，需要遍历体数据中的所有体元，算法执行时间较长，效率较低，分割后数据细节处理不足、像素信息不全。本研究采用交互式区域增长算法，依据数字图像灰度值的相似性和连通性将图像分割成相似的区域[10]。区域增长算法设计有3点：生长种子点的选取、区域生长的条件和终止算法执行的条件。该算法无需遍历所有体元，执行时间较短，分割后的像素信息较全，组织器官的细节处理较好。

通用树结构与传统MC算法中直接在体数据上进行操作运算相比，具有以下优势：①通用树的存储方法利用了其结构在空间的合理相关性，具有良好的空间利用率和查询率，可以高效地对体元进行并、交等集合运算，提高了运算和渲染效率；而传统MC算法空间结构性较差，体元之间的集合运算时间相对较长[11-12]。②体数据通用树剖分的空间具有较好的层次性和有序性，有助于消除网格中多余的隐线和隐面，减少无效三角面片，提高网格显示精度[13]。消隐方法的核心是排序，即将待三维重建组织的点、线、面按离观察点的远近排序，近的三角面片遮挡较远的三角面片。通用树结构将与阈值相交的体元按顺序排列，有助于消除隐线和隐面，从而提高三维模型的显示精度。而传统MC算法有序性较差，数据存储相对散乱，网格显示精度明显弱于通用树结构。

本研究结果显示改进MC算法的三维重建效果较好，拓扑结构简单，三角面片个数减少，算法执行效率有较大提高，能够高精度地展示出肾脏细节，并成功应用于虚拟手术平台，为基于医学图像的三维重建和虚拟手术研究提供更加有效的方法。本研究所用算法渲染效果好，真实性和精确性均达到虚拟手术平台要求。改进MC算法减少了对空体元的遍历和生成的三角面片数量，简化等值面抽取过程，大大提高了算法执行效率。但上述研究仅改进了虚拟手术平台中软组织的几何建模，今后将对软组织的物理建模展开更深研究，为搭建更加符合真实手术情况的虚拟手术平台提供帮助。