一种改进的基于二次误差测度的网格简化算法

维普资讯 http://www.cqvip.com 第４６卷第３期　厦门大学学报（自然科学版）　Ｊｏｕｒｎａｌ　ｏｆ　Ｘｉａｍｅｎ　Ｕｎｉｖｅｒｓｉｔｙ（Ｎａｔｕｒａｌ　Ｓｃｉｅｎｃｅ）　Ｖｏ１．４６　Ｎｏ．３　Ｍａｙ　２００７　２００７年５月　一种改进的基于二次误差测度的　网格简化算法　吴韦力，王博亮　，黄绍辉　（厦门大学计算机科学系，福建厦ｆ－ｊ　３６１００５）　摘要：在医学图像三维表面建模中，会产生大量的三角面，难以在普通ＰＣ机上进行实时渲染．为了解决这个问题，本文　作者提出一种改进的基于二次误差测度的网格简化算法．通过对顶点进行分类。在简化过程中更好地保持了模型的细节　特征，同时考虑了网格中三角面的分布情况，减小了几何误差．结果表明，算法既保持了原算法快速的优点。又满足了医　学图像处理对逼真度和网格质量的较高要求．　关键词：网格简化；边折叠；二次误差测度　中图分类号：ＴＰ　３９１．４２　文献标识码：Ａ　文章编号：０４３８—０４７９（２００７）０３—０３３７—０５　在医学手术仿真系统中，需要把采集到的各类医　学图像进行三维重建得到三角网格模型，并允许医生　完成一些交互性的操作．但是医学图像的数据量很大，　用移动立方体（Ｍａｒｃｈｉｎｇ　Ｃｕｂｅｓ，ＭＣ）等算法进行三维　重建产生的三角面数量之多甚至达到百万级，超过了　一相关三角平面距离的平方和作为误差测度，算法速度　快，而且能生成高质量的简化模型．但是ＱＥＭ算法的　误差测度标准过于单一，有时模型表面的细节特征会　发生变形甚至丢失，本文对此提出了一些改进．　般计算机的实时显示能力．此外，进行切割模型等交　２　ＱＥＭ算法　２．１边折叠操作　如图ｌ所示，边折叠操作是将一条满足条件的边　（　。，＂０２）简化为一个顶点　，通常一次边折叠可以减少　１个顶点、２个三角形、３条边．　互性操作时，需要对三角面进行碰撞检测及形变处理，　但即便是工作站也难以负荷上百万三角面的相关计　算．因此，有必要对重建所得的三角网格进行简化．　１　网格简化算法　现有的网格简化策略［１　中，几何元素删除法应用　最为广泛，它包括顶点删除法、三角形折叠法、边折叠　法等．其中，前两种方法需要对产生的空洞重新三角　化，处理比较费时．相比之下，边折叠法只需将相连的　两个顶点合并到一个新顶点上，并延续原有的拓扑关　系，效率大大提高，而且鲁棒性更好．　边折叠法是Ｈｏｐｐｅ［２　在１９９３年提出来的，其关键　是确定边折叠的次序和折叠后新顶点的位置，Ｈｏｐｐｅ　使用能量函数作为误差测度得到了很好的简化效果，　但由于考虑了全局信息，计算量太大．Ｇａｒｌａｎｄ【３　于　１９９７年提出基于二次误差测度（Ｑｕａｄｒｉｃ　Ｅｒｒｏｒ　Ｍｅｔ—　折叠前　折叠后　图１边折叠操作　Ｆｉｇ．１　Ｅｄｇｅ　ｃｏｌｌａｐｓｅ　２．２二次误差测度　为了达到较好的简化效果，需要评价边折叠前后　产生的模型误差情况，即折叠代价．通过每次取出代价　最小的边进行折叠，有助于减少模型简化过程中产生　ｒｉｃ）的边折叠简化算法（简称ＱＥＭ算法），他以顶点到　的误差．Ｇａｒｌａｎｄ【３　使用边折叠操作生成的新顶点到相　收稿日期：２００６—０８—２８　关三角面距离的平方和作为误差度量．　在三维空间中，一个三角平面可以用平面方程甜　＋６３，＋　＋ｄ一０（ａ。＋ｂ。＋ｃ。一１）来表示．　基金项目：国家自然科学基金（６０３７１０１２）。卫生部联合基金　（ＷＫＪ２ＯＯ５—２—００１），福建省科技重点项目（２００５Ｙ００１８）　和厦门市科技计划项目（３５０２Ｚ２００５１０１５）资助　＊通讯作者：ｂｌｗａｎｇ＠ｘｍｔ１．ｅｄｕ．ａｎ　令Ｐ＝［口ｂ　ｃ　］　代表该平面，点　的坐标为［仉　维普资讯 http://www.cqvip.com 厦门大学学报（自然科学版）　１］　，则点　到平面Ｐ距离的平方为：　≥０，因此△　是半正定二次型，二次误差测度矩阵　Ｄ；（　）一（　１’　）　一　１’（ＰＰ１’）　：＝＝ＶＴＫｐ　其中：　（１）　　Ｑ（口）是实对称的半正定矩阵．这样，所有误差为叩的　点构成的等值面△　：＝＝叩是一个椭圆曲面（也可能退化　成圆柱面或者两个平行平面），其形状与模型表面在该　ａ０　ａｂ　ａｃ　ａｄ　］●●●●●　●ｊａｂ　ｂ　ｂｃ　ｂｄ　Ｋｐ—ＰＰ　：＝＝　ｒ　Ａ　Ｂ］　Ｂ　ａｃ　ｂｃ　ｃｄ　一ｌＢｒ　ＣＪ『　ｌｃ　ｒＬ　　ｎｄ　ｂｄ　ｃｄ　ｄ　６　ｆ　］　　ｒ　Ａ一巨耄Ｃ　ｌ　ｌ（　２　２．　Ｑ（ｖ１）一　∑Ｋｐ　（３）　ｐＥｐｌａｎｅｓ（ｖ１）　为点　的二次误差测度矩阵，其中ｐｌａｎｅｓ（口　）为所有　包含顶点　。的三角面的集合．　根据Ｇａｒｌａｎｄ的定义，由式（１）可得折叠代价：　Ａｖ＝　∑　Ｄ；（口）＝　ｐ∈ｐｌａｎｅｓ（ｖ１）Ｕｐｌａｎｅｓ（ｖ２）　∑　Ｋ　一　ｐ∈ｐｌａｎｅ￥（　１）Ｕｐｌａｎｅｓ（ｖ２）　ｖｒ（　Ｋｐ）　．　ｐ∈加　（ｖ—１）Ｕ　ｅｓ（　２）　但在实际应用中，为了减少储存空间并加快计算　速度，折叠代价，３ｖ通常使用　ＶＴ（∑Ｋ　＋∑Ｋ　）　，　ｐ∈ｐｌａｎｅｓ（ｖＩ）　ｐ∈ｐｌａｎｅｓ（　）　来进行估算，即：　＝　（Ｑ（　１）＋Ｑ（　））　，　新顶点口的二次误差测度矩阵由　、　的二次误差测　度矩阵线性相加得到．这样就能快速计算出折叠所影　响到的边的误差代价，并进行相关的更新操作．　２．３　新顶点的位置　点口位置的选取对折叠代价的计算也有很大的影　响，容易想到应计算使折叠代价最小化的点　坐标．由　式（２）、（３）可知Ｑ（　）是对称矩阵，再仿照式（２）的划　分方式，可得：　Ａｖ一口　Ｑ（　）口一ｖｒＡｖ＋２Ｂ　＋Ｃ　（４）　对上式求偏导数并令其为０，得　＝一Ａ　Ｂ．即当　Ａ可逆时，点　坐标取一Ａ　Ｂ，使得折叠代价最小化，　若Ａ不可逆，则在　、口　中取折叠代价相对较小的点．　３　算法改进　ＱＥＭ算法虽然有效，但其误差测度标准过于单　一，仅仅考虑新顶点与相关三角面的距离平方和．由式　（２）～（４）可知　是实二次型，再由△　的定义得Ａｖ　局部区域的曲率相关．若为薄饼状，则该处表面较为平　滑；若为细长形，则该处曲率较大，且主要是在扁平方　向上的法向量变化较快；若近似球形，则该处曲率大，　且法向量沿各个方向的变化都较快．这样可以在一定　程度上保证边折叠操作主要往曲率较小的方向进行，　但它并没有对模型表面的细节特征进行识别．因此当　细节特征发生在曲率较小的方向时，如果毫无区分地　加以折叠，多次操作之后，可能导致细节特征出现形变　或丢失，这在医学模型中可能涉及一些重要组织或病　变区域，必须尽量避免．　３．１　顶点分类　为了保持细节特征，我们需要先对其进行识别．　Ｈｏｐｐｅ［４　等将模型的细节特征分为：①折痕，两个三　角面相交形成的尖锐边；②角点，３条或３条以上折痕　的交点；③尖刺，模型表面内部折痕的终止点．在此基　础上，我们增加一些定义和新的策略．　１）首先，将所有的顶点划分为独立点、简单点、边　界点和复杂点．　独立点：没有相邻三角面的点，对模型没有贡献，　不参与边折叠，可以直接删除．　简单点：被包围在一个闭合的环中，且每条和该顶　点相连的边都恰好被两个三角形共用．　边界点：当一条边只有一个相邻三角面时，则该边　的两个顶点都为边界点．　复杂点：除独立点、简单点和边界点之外的其它顶　点．　２）再从简单点中进一步划分出尖刺点、公共尖刺　点和角点．　当一条边恰好有两个相邻三角面（设夹角为　）　时，我们计算它们的单位法向量并进行点乘，即得　ＣＯＳ（＇Ｋ一日）．实践中，当ｃｏｓ（　一　）＜一０．１时，我们判断　此边为折痕．　对所有边进行遍历，当发现某条边为折痕时，对其　两个端点设定标记．若之前顶点标记为简单点，则重新　标记为尖刺点；若之前标记为尖刺点，则重新标记为公　共尖刺点；若之前标记为公共尖刺点，则重新标记为角　点．　３．２　基于顶点分类的边折叠　将细节特征通过顶点分类进行识别之后，需要针　对各种细节特征的特点调整相关边的折叠策略，以更　好地在简化过程中将其保留下来．为了节约空间和增　维普资讯 http://www.cqvip.com 第３期　吴韦力等：一种改进的基于二次误差测度的网格简化算法　加灵活性，我们并没有设置边的类型，而是直接根据边　数分别为，ｚ　、，ｚ　，则新顶点　的相关三角面面积平均值　的两个顶点的分类来判断．　可近似为（Ｓ　－ｉ－Ｓ　）／（，ｚ　＋，ｚ　），类似二次误差测度矩阵　首先，当边的两个顶点中有一个为公共尖刺点或　的累加方法，我们只要设置点　的相关面积和为Ｓ　＋　角点时，为了保持折痕的特征，我们仅在该边的连线上　Ｓ　，个数为７ｌ　－ｉ－　，就可以随时计算出面积平均值．　寻找使折叠代价Ａｖ最小化的点．接着，我们为角点、公　我们把边折叠相关三角面的面积平均值与原折叠　共尖刺点和复杂点各分配一个权值以降低其相连边的　代价相乘作为最终的折叠代价，这样原来三角面较密　折叠优先权．其中，角点的特征最为突出，应尽量保留，　集的局部区域进行边折叠的优先级将有所提高，可以　实践中使用ｉｎｔ类型的最大表示值作为其权值．公共尖　改善简化模型中三角面的分布情况．　刺点和复杂点经多次试验，权值分别取为１．８和３．２．　这样，边的初始权值为１．０，每当有一个顶点为角点、　４　算法描述　公共尖刺点或复杂点时，就把相应的权值累加上去，得　到的权值再与之前计算出的边折叠代价相乘作为新的　４．１　算法步骤　折叠代价．　１）读入模型数据并对顶点进行分类．　但注意到公共尖刺点应避免往非折痕方向的折　２）计算出每个顶点的二次误差测度矩阵Ｑ、相邻　叠，因此当边的一个顶点为公共尖刺点，另一个顶点为　三角面的面积和Ｓ及个数，ｚ．我们先清空各顶点的Ｑ和　简单点时，要另外增加其权值以使这类折叠的优先权　Ｓ，接着对每个三角形　计算其二次误差测度矩阵Ｑ　降低，实践中取公共尖刺点权值的２倍作为附加权值．　和面积Ｓ　，并在其三个顶点的Ｑ及Ｓ中分别加入Ｑ　和　至于边界点，在我们需要处理的医学模型中是相　Ｓ　，遍历所有三角形之后即完成了Ｑ和Ｓ的初始化，而　对较少的．而Ｇａｒｌａｎｄ［３　提出的方法已经可以得到相　可以从数据结构中直接得到．　当不错的效果，即通过边界边作一个垂直于边界三角　３）计算每一条边的折叠代价：先按顶点的分类选　形的平面，在计算边界点的误差矩阵时，将其考虑在内　择新顶点的位置，确定其权值Ｗｅｉｇｈｔ，计算二次误差　并赋予一个较大的系数ｋ．实践中我们设置ｋ为１　０２４．　折叠代价ＱＥＭｖａＩｕｅ，再得到相关三角面面积平均值　对于边折叠生成的新顶点，我们由高到低定义如　，则最终折叠代价Ｙａｌｕｅ＝ＱＥＭｖａｌｕｅ×Ｗｅｉｇｈｔ×　下优先级：角点、边界点、复杂点、公共尖刺点、尖刺点、　．将所有的边按折叠代价放入优先队列中．　简单点．当发生边折叠时，取该边两个顶点中优先级较　４）从优先队列里取出折叠代价最小的边完成边　高的类别来对新顶点进行分类设置，该方法简单快速，　折叠的操作，重新计算该过程中受影响的边的折叠代　且有利于细节特征的继续保持．　价并更新其在优先队列中的位置．　３．３　网格分布的调整　５）若达到简化要求或优先队列为空，转６），否则　注意到对于大多数模型来说，涉及细节特征的区　转４）．　域往往只占整个模型的小部分，模型的大部分区域都　６）删除不存在邻接三角面的独立点，输出简化模　比较平坦．前面的方法虽然保持了模型的细节特征，但　型，结束．　也会使简化得到的网格花费过多的三角面来描述细节　４．２　算法复杂度　集中的区域，从而其它区域的三角面较为稀疏，整体上　ＱＥＭ算法已经由Ｇａｒｌａｎｄ【３］证明其初始化及执　可能导致体积等几何误差增大，这将影响医学模型在　行的时间复杂度均为Ｏ（ｎｌｏｇｎ），空间复杂度为０（　）．　实际应用中的各种相关测算．　而我们的方法中，主要是增加了顶点分类和面积平均　为了缓解这种情况，需要对简化模型中三角面的　值的计算．顶点分类是通过分析顶点的邻接三角面信　分布进行调整．我们希望在细节集中的区域仍然保留　息来进行的：独立点没有邻接三角面；简单点的邻接三　用来描述细节特征的三角面，但对该区域的其它三角　角面构成一个闭合面；两个相邻点若只有一个公共邻　面加强简化力度，以节省出一些三角面来描述细节较　接三角面则为边界点；两个相邻点若恰有两个公共邻　少但对体积等几何误差影响较大的其它区域．前面　接三角面且其夹角０满足ＣＯＳ（￣一　）＜一０．１时，以累　Ｇａｒｌａｎｄ使用边折叠操作生成的新顶点到相关三角面　计的方法设置顶点的类型；其余为复杂点．这些都可以　距离的平方和作为误差度量，这里我们使用相关三角　视为常数时间的操作，因此顶点分类总的时间复杂度　面的面积平均值作为局部区域三角面密集程度的度　为０（，ｚ）．在初始化过程中，一个三角形的面积计算及　量．　在边折叠的过程中新顶点的相关三角面面积平均值计　设点　、　的相关三角面面积和分别为Ｓ　、Ｓ。，个　算都可以在常数时间内完成，这样，所有与面积平均值　维普资讯 http://www.cqvip.com 维普资讯 http://www.cqvip.com 第３期　吴韦力等：一种改进的基于二次误差测度的网格简化算法　・３４１・　电子工业出版社，２００３．　６　结　论　本文在二次误差测度方法的基础上通过对顶点进　行分类加权，较好地实现了网格简化过程中细节特征　的保持，同时为了克服该方法引起的局部区域三角面　过于密集的问题，加入相关三角面面积平均值作为网　格调整依据，取得了不错的效果．本算法不但适用于医　学图像处理，也具有一定的通用性．通过记录简化过程　［２］Ｈｏｐｐｅ　Ｈ，ＤｅＲｏｓｅ　Ｔ。Ｄｕｃｈａｍｐ　Ｔ，ｅｔ　ａ１．Ｍｅｓｈ　ｏｐｔｉｍｉｚａ－＿　ｉｔｏｎ［Ｃ］／／Ｃｕｎｎｉｎｇｈａｍ　Ｓ　ＳＩＧＧＲＡＰＨ　９３．Ａｎａｈｅｉｍ：ＡＣＭ　Ｐｒｅｓｓ，１９９３：９—２６．　［３］　Ｇａｒｌａｎｄ　Ｍ，Ｈｅｃｋｂｅｒｔ　Ｐ　Ｓ．Ｓｕｒｆａｃｅ　ｓｉｍｐｌｉｉｆｃａｔｉｏｎ　ｕｓｉｎｇ　ｑｕａｄｒｉｃ　ｅｒｒｏｒ　ｍｅｔｌｔｅｓ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ＳＩＧＧＲＡＰＨ　９７．Ｃｏｍｐｕｔｅｒ　Ｇｒａｐｈｉｃｓ　Ｐｒｏｃｅｅｄｉｎｇｓ，Ａｎｎｕａｌ　Ｃｏｎｆｅｒｅｎｃｅ　Ｓｅｒｉｅｓ，．Ｌｏｓ　Ａｎｇｅｌｅｓ：Ａｄｄｉｓｏｎ　Ｗｅｓｌｅｙ，１９９７：２Ｏ９—２１６．　［４］Ｈｏｐｐｅ　Ｈ，ＤｅＲｏｓｅ　Ｔ，Ｄｕｃｈａｍｐ　Ｔ，ｅｔ　ａ１．Ｐｉｅｃｅｗｉｓｅ　ｓｍｏｏｔｈ　中的相关信息，将来还可以用于构造层次细节模型　ｓｕｒｆａｃｅ　ｒｅｃｏｎｓｔｒｕｃｔｉｏｎ［Ｃ］／／Ａｎｄｒｅｗ　Ｇｌａｓｓｎｅｒ　ＳＩＧ－。　（Ｌ　ＯＤ）．ｑ　ＧＲＡＰＨ　９４．Ｏｒｌａｎｄｏ：ＡＣＭ　Ｐｒｅｓｓ，１９９４：２９５—３０２．　［５］Ｌｉｎｄｓｔｒｏｍ　Ｐ，Ｔｕｒｋ　Ｇ．Ｆａｓｔ　ａｎｄ　ｍｅｍｏｒｙ　ｅｆｉｆｃｉｅｎｔ　ｐｏｌｙｇｏ－・　ｈａｌ　ｓｉｍｐｌｉｉｆｃａｔｉｏｎ［Ｃ］／／ＩＥＥＥ　Ｖｉｓｕａｌｉｚａｔｉｏｎ　９８．Ｎｏｒｔｈ　Ｃａｒｏ—　参考文献：　ｌｉｎａ：ＩＥＥＥ，１９９８：２７９—２８６．　［１－１　田捷，包尚联。周明全．医学影像处理与分析ｌ－Ｍ－］．北京　Ａ　Ｎｅｗ　Ｍｅｓｈ　Ｓｉｍｐｌｉｆｉｃａｔｉｏｎ　Ａｌｇｏｒｉｔｈｍ　Ｂａｓｅｄ　ｏｎ　Ｑｕａｄｒｉｃ　Ｅｒｒｏｒ　Ｍｅｔｒｉｃｓ　ＷＵ　Ｗｅｉ－一ｌｉ，ＷＡＮＧ　Ｂｏ－一ｌｉａｎｇ　，ＨＵＡＮＧ　Ｓｈａｏ—ｈｕｉ　（Ｄｅｐａｒｔｍｅｎｔ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｓｄｅｎｃｅ，Ｘｉａｒｎｅｎ　Ｕｎｉｖｅｒｓｉｔｙ，Ｘｉａｍｅｎ　３６１００５，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：Ｄｕｒｉｎｇ　３Ｄ　ｍｅｄｉｃａｌ　ｉｍａｇｅ　ｒｅｃｏｎｓｔｒｕｃｔｉｏｎ，ｍａｎｙ　ｔｒｉａｎｇｌｅｓ　ｗｅｒｅ　ｐｒｏｄｕｃｅｄ，ｗｈｉｃｈ　ｗｅｒｅ　ｂｅｙｏｎｄ　ｔｈｅ　ｒｅｎｄｅｒｉｎｇ　ｃａｐａｂｉｌｉｔｙ　ｏｆ　ｃｏｒｆｌｒｔｌｃｎ　ＦＣ．．Ｉｎ　ｏｒｄｅｒ　ｔｏ　ｓｏｌｖｅ　ｔｈｅ　ｐｒｏｂｌｅｍ，ｔｈｉｓ　ｐａｐｅｒ　ｐｕｔ　ｆｏｒｗａｒｄ　ａｎ　ｉｍｐｒｏｖｅｄ　ｍｅｓｈ　ｓｉｍｐｌｉｆｉｃａｔｉｏｎ　ａｌｇｏｒｉｔｈｍ　ｂａｓｅｄ　ｏｎ　ｑｕａｄｒｉｃ　ｅｒｒｏｒ　ｍｅｔｒｉｃｓ．Ｔｈｅ　ａｌｇｏｒｉｔｈｍ，ｂｙ　ｃｌａｓｓｉｆｙｉｎｇ　ｔｈ　ｅ　ｖｅｒｔｉｃｅｓ，ｐｒｅｓｅｒｖｅｄ　ｔ　ｈｅ　ｓｐｅｃｉｆｉｃ　ｆｅａｔｕｒｅｓ　ｏｆ　１　ｈｅ　ｍｏｄｅｌ　ｄｕｒｉｎｇ　ｔｈｅ　ｐｒｏｃｅｓｓ　ｏｆ　ｓｉｍｐｌｉｆｉｃａｔｉｏｎ．　Ｍｅａｎｗｈｉｌｅ。ｈｏｗ　ｔｒｉａｎｇｌｅｓ　ｗｅｒｅ　ｄｉｓｔｒｉｂｕｔｅｄ　ｉｎ　ｔｈｅ　ｍｅｓｈ　ｗａｓ　ａｌｓｏ　ｔａｋｅｎ　ｉｎｔｏ　ｃｏｎｓｉｄｅｒａｔｉｏｎ　ａｎｄ　ｔｈｕｓ　ｒｅｄｕｃｅｄ　ｇｅｏｍｅｔｒｉｃ　ｅｒｒｏｒ．Ｉｔ　ｈａｓ　ｂｅｅｎ　ｐｒｏｖｅｄ　ｔｈａｔ　１ｈｅ　ｎｅｗ　ａｌｇｏｒｉｔｈｍ　ｎｏｔ　ｏｎｌｙ　ｍａｉｎｔａｉｎｓ　ｈｉｇｈ　ｅｆｆｉｉｃｅｎｃｙ　ｏｆ　ｔｈｅ　ｏｒｉｇｉｎａｌ　ａｌｇｏｒｉｔｈｍ，ｂｕｔ　ａｌｓｏ　ｍｅｅｔｓ　ｈｉｇｈｅｒ　ｒｅｑｕｉｒｅｍｅｎｔｓ　ｏｆ　ｍｅｄ—　ｉｅａｌ　ｉｍａｇｅ　ｐｒｏｃｅｓｓｉｎｇ　ｉｎ　ｔｅｒｍｓ　ｏｆ　ｆｉｄｅｌｉｔｙ　ａｎｄ　ｍｅｓｈ　ｑｕａｌｉｔｙ，　．Ｋｅｙ　ｗｏｒｄｓ：ｍｅｓｈ　ｓｉｍｐｌｉｆｉｃａｔｉｏｎ；ｅｄｇｅ　ｃｏｌｌａｐｓｅ；ｑｕａｄｒｉｃ　ｅｒｒｏｒ　ｍｅｔｒｉｃｓ