Marching Cube 算法综述.doc

《Marching Cube 算法综述.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、MarchingCubes算法MarchingCubes算法是三维规则数据场等值面生成的经典算法，于1987年由Lorensen和Cline两人在SiggraphProceedings(pp.163-169)提出。处理的对象一般是断层扫描（CT），或是核磁共振成像（MRI）等产生的图像。一、基本概念在MarchingCube算法中，体素是以逻辑上的六面体，由相邻层上的各四个像素组成的立方体上的八个顶点。等值面是空间中所有具有某个相同值的点的集合。它可以表示成这里的c是我们在三维重构过程中给定的阈值。二、算法简介算法的基

2、本思想是逐个处理数据场中的立方体（体素），分类出与等值面相交的立方体，采用插值计算出等值面与立方体边的交点。根据立方体每一顶点与等值面的相对位置，将等值面与立方体边的交点按一定方式连接生成等值面，作为等值面在该立方体内的一个逼近表示。之所以这样，是由于MarchingCubes有个基本假设：沿六面体边的数据场呈连续性变化。也就是讲，如果一条边的两个顶点分别大于或小于等值面的值，则在该条边上有且仅有一点是这条边与等值面的交点。为了说明一下算法，先从2D图像开始。图1（a）是一张像素灰度值为0～3的图像。给定阈值1.5，黑

3、色的点表示像素值大于1.5的像素。图1（b）（c）描述了等值线的抽取过程。图1（a）图1（b）：用空心小圈表示图1（c）：进行线性插值，求等值线与这条边相交出交点位置对于某棱边，如果它的两个端点v1、v2标记不同，那么等值面一定与此棱边相交。且交点坐标为：P=P1+(isovalue-V1)(P2-P1)/(V2-V1)其中P代表等值点坐标，P1、P2代表两个端点的坐标，V1、V2代表两个端点的灰度值，isovalue代表阈值。对于每个四边形来说，每个顶点两种情况（大于或小于），4个顶点共16种情况（图2a），考虑到旋

4、转对称性，从新分类后可得4种基本模式（图2b）。图2这些2D图像正是3DMarchingCubes算法中立方体各个表面的等值线抽取情况。在3D中，由于每一立方体共有8个顶点，每个顶点共有2个状态（物体内和物体外），因此共有256种组合状态，分析立方体体素的2种对称性：（1）顶点状态反转，等值三角面片的拓扑结构不变，也就是讲，大于等值面与小于等值面的点是可以相互替换的。（2）旋转对称性，经过适当旋转，有许多状态是一致的。这样，可归纳出15种模式（见图3a）。对于模式0－7，其补充模式见图3b，而模式8－14，由于有4个顶

5、点，本身就包括了自己的互补模式。图3a15种模式图3b0-7的补充模式在实现时，可按照立方体顶点状态构造等值面连接模式的查找表，并可直接由立方体各顶点的状态检索出其中等值面的分布模式，确定该立方体体素内的等值面三角片连接方式。三、算法歧义性及其解决MarchingCubes算法提出不久，就有人发现了它的歧义性。跟上面一样，还是从2D开始说起。先看一下图2b中的Pattern3。对这种Pattern，等值线的连接方式除了上图所标识的外，还有另外一种（见图4a）。图4对图4a的两种连接方式的不同选择，在同一张图像上可导致完

6、全不同的结果（见图4b）。经过观察我们可知，这种歧义性只发生在：一个面上，如果一条对角线的两端点大于阈值，另一条对角线的两端点小于阈值的情况。在立方体中，我们把这种面称作歧义面。把这个问题放到3D上就产生了Hole问题。先回头看图3中的Patten3和它的补充模式3c。按上面的歧义面定义可知，Pattern3的底面Direct类型，而Pattern3c是Reverse类型。当我们把Pattern3c倒过来以后放到Pattern3下面就会产生下图最左边所示情况：图5图5还显示了Pattern10在Pattern6c上面（

7、中间）和Pattern6在Pattern3c上面的情况。这种歧义性导致的结果可见图6。图6从上面可知，产生歧义性的原因是我们把3c等这些补充模式等同于对应的基本模式，从而导致在歧义面上Direct类型和Reverse类型交错使用。为了解决这个问题，提出两种扩展的MarchingCubes算法。第一种是把所有的歧义面都按Direct类型来连接。这样产生了23中模式（图7）。图7另一种刚好相反，所有歧义面都为Reverse类型，也有23中模式。图8和图9分别显示了产用上面两种扩展算法后，对应于图5和图6的结果：图8图9扩展

8、的MarchingCubes算法虽然解决了Hole问题，但并没有解决歧义性问题。因为无论是Direct还是Reverse都是强制性的，并没有从图形本身出发。为此，G.M.Nielson等人提出了渐近线判别法。它通过计算等值面与体素边界面的交线（双曲线）的渐进线与体素的边界面的相互位置关系来判断等值面的正确连接方式。在一般情况下，等