三维模型的快速重建及简化范文

1问题及解决策略

三维重构的方法可分为面绘制与体绘制两大类。依据两类经典算法的各自特点,针对医学图像数据的三维快速重构与三维模型的简化问题,利用面绘制方法,采用了移动立方体算法MC(marchingcube)产生构成三维体表面的三角面片;再采用Tri-angledecimation算法对生成的模型作约减,约减的目的是用较少的三角面片来保证显示与处理的速度,用空间来换取时间。所提出的重建与组织同时生成的方法与具体算法,实现了三维模型的实时显示和与用户的快速交互。

2三维模型的快速重构、组织与去噪

在三维模型重构中我们选择了文献[1]提出的MC算法来提取三维等值面,MC算法遍历所有立方体的顶点,将顶点的物理量值与等值面值相比较,从而确定顶点与等值面的位置关系,通过线性插值得到等值面与Cube的交点,依次遍历所有的Cube,从而得到给定阈值的等值面。MC算法简单有效,可以有效的应用于密集数据场的三维表面模型重构,但MC算法在实际应用中还存在一些问题[2]:1)MC算法产生的结果为散乱而又大量的三角面片;2)算法对数据场的密集度要求较高;上述两点对三维模型重构与组织的速度、对三维模型真实再现的效果及后继的简化处理的效率影响很大。

2.1数据结构描述

针对上述MC算法,采取将三角面片的生成与组织同步完成的方法思路,在实现中采用顶点-边表的数据结构,即与某顶点共同组成一个三角形的边置于该顶点的边链中,边链按顺序存放。尽管这种顶点-边表结构会产生数据的冗余,同一个三角形被定义了3回,但这种结构突出了对顶点数据的重视,使得对后继处理尤其是约减处理带来很大方便,由于时间是矛盾的焦点,我们采用空间换时间的方法。在顶点-边表结构中每一个顶点对应两个队列:现存边链和删除边链。顶点数据结构中存放了该顶点的x,y,z坐标和顶点的删除次序。当顶点的删除次序为零时代表该点未被删除。边链中每一个Node由4部分组成:边对应的两个下标,该边的插入次序和删除次序。需要注意的是顶点对应的当前边链中边是按顺序存放的。对于上述结构我们可以用类将其封装起来,定义于其上的基本运算包括:插入顶点、删除顶点、插入边、删除边、插入三角面片、删除三角面片、边链顺序整理。

2.2三维模型的组织与快速重构

将MC生成的每一个三角面片插入上述的顶点-边表结构,需要两步工作[3,4]:①三角面片三个顶点的定位与插入;②三角面片的插入。顶点的定位是三角面片插入的基础。为快速的将MC生成的每一个三角面片插入上述顶点-边表结构中,待插入三角面片的三个顶点在顶点链中的定位的速度是关键因素,查找的速度直接影响三角网格生成组织的速度。由于一个三角面片只能与当前处理立方体和周围与该立方体相邻的立方体中的三角面片有共同特点,在查找三角面片三个顶点时可以充分利用MC算法“活动的立方体”的特性,从而大大缩小顶点的搜索范围,加速顶点的搜索定位过程。其算法步骤描述如下:1)分配缓冲区Buffer。假定搜索区域大小为X*Y*Z(X为图像长度,Y为图像宽度,Z为层数),缓冲区Buffer=newint[5*X*Y-2*(X+Y)]。Buffer包含了当前层中所有Cube的边。Buffer[i](0<=i,SIZE)存放的是该边所包含的等值面中顶点的下标。置其初值为零代表该边不与等值面相交。2)在按层遍历每一个Cube时,若某一Cube的某条边与等值面存在交点,则计算交点所在的边在Buffer中的下标N,判断Buffer[N]是否为零,若不为零,则Buffer[N]-1即为该点在顶点数组中的下标;若为零,则在顶点数组最后插入该顶点,并将该顶点在顶点数组中的下标加1存入Buffer[N]。3)将三角面片的三条边插入各自顶点的边链。4)当循环进入新的一层Cube时,更新Buffer。上述处理大大提高了顶点的定位效率,使得三角面片的生成与组织一步完成,节省了处理时间,提高了效率。组织后的三维模型为后继处理带来了很大的方便。

2.3三维模型中噪声点的去除

MC算法对数据场的密集度要求较高,实际应用中由于一些医学图像层间数据密集度较低,造成了用MC算法提取等值面的过程中产生了一些像“台阶”一样的中间层,影响了模型的真实再现。其实这些处于中间层上的点是由MC算法线性插值而得到的,但对生成的模型而言它们是噪点[5,6]。针对此问题,在具体实现过程中我们并没有采取插值的方法增加原始数据的密集度,以消除算法产生的“台阶”,而是充分利用上述已经得到的三维模型基础,方便的解决点去噪处理的问题。具体解决办法是:①遍历所有顶点,找出在输入数据密集度较低方向上的处于中间层的顶点;②给找出顶点做删除标记;③对删除顶点后得到的“洞”进行三角剖分处理,然后调整顶点-边表结构;④重复1)到3)步,直到满足的“中间层”顶点全部删光。模型经上述处理后,“台阶”自然不复存在,模型也“光滑”了,同时三角面片也得到相当程度(50%以上)的减少。其实这种做法与先在各层求出等值轮廓线、再在相邻两层的等值轮廓线间通过三角剖分得到三维模型的方法相比有异曲同工之处。在后续的约减算法中,也需要利用三角剖分算法,所以在去噪工作中无须新增添代码模块,依赖于在约减之前对数据所作的预处理。

3三维模型的简化与多分辨率模型的生成

由于绘制时间和存储量与三角形的数目成正比,而MC算法产生的三角面片很多,约减至关重—222要。约减的方法很多,我们采用了基于TD(triangledecimation)算法的思路,TD算法是通过不断删去重要度低的顶点来完成约减过程,所以约减模型是在连续的变化(每次删除1到2个三角形),为此我们提出了一种适用于顶点删除约减方法的多分辨率模型的生成算法,借助上述数据结构和TD算法的特点,在约减的同时还保留了中间结果,从而产生了一个多分辨率模型,不仅方便用户对所需模型不同程度的需求,而且提高了TD算法的效率。具体做法是:在每删除一个顶点后,包含此顶点的三角形均被删除,剖分后又有一批新的三角形被插入。在上述结构中对三角面片的删除具体表现为对边的删除,对三角形的插入体现为对边的插入。设立了一个计数器,其初值为零。每删除一个顶点之后计数器加1,并记录在该顶点的删除次序字段。删除顶点之后会有一批三角面片被删除和插入。当边被删除时只将其移入删除链,并不在边链中物理删除该节点,同时在该节点中记录计数器的值。在删除顶点后的对删除后留下的“洞”进行剖分,将新产生的三角形的三条边插入其对应的顶点当前边链,同时在插入节点中记录计数器的值。最后,调整当前边链中节点的顺序。1)能很方便的判断顶点类型,确定边界顶点,边界边。2)在约减中通过顶点-边表结构能快速找到一个顶点周围的所有邻点。3)由于顶点周围的边均按序排列,加快了判断顶点重要度和三角剖分的过程。等约减完成得到了该被简化模型的多分辨率模型。这样模型的减化与多个不同细节层次模型同时产生,大大节省了时间,提高了效率,但该方法对内存的消耗过大,数据存储量也相应较大。在显示模型时,可以根据用户的需要动态调整模型的大小。由于每次顶点删除总是删去1到2个三角形,所以顶点的删除顺序与模型的大小有直接关系。在计算所需显示的三角面片时,根据删除的次序可以在顶点-边表的一次遍历中迅速定位在该顶点被删除以前的模型包含的所有三角面片。4结果上述方法,适合于使模型连续变化、基于顶点删除的约减,该算法产生多分辨率模型。操作系统为WindowsNT4.0,开发工具采用BCB3.0,我们提出的方法用实验验证,取得了令人满意的效果。以提取的颅骨模型为例,原始数据为脑部CT切片,像素数256×256×69。

上述方法应用于脑部三维图像医学处理平台中三维表面的构造,结果表明:三维模型的重建与组织时间大为减少,上述方法对于基于断层数据的三维快速重建、简化具有通用性。