基于层次聚类的网格模型自动分割方法

第３０卷增刊２　计算机应用　Ｖｏ１．３０　Ｓｕｐｐ１．２　２０１０年１２月　Ｊｏｕｒｎａｌ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ａｐｐｌｉｃａｔｉｏｎｓ　Ｄｅｅ．２０１０　文章编号：１００１—９０８１（２０１０）Ｓ２—０００１—０４　基于层次聚类的网格模型自动分割方法　张森　，　，　，韩其才　，２＇　，闫琨鹏　，　一，张　慧　。　，雍俊海　’４　（１．清华大学软件学院，北京１０００８４；２．清华大学计算机科学与技术系，北京１０００８４；　３．清华大学信息系统安全教育部重点实验室，北京１０００８４；４．清华大学信息科学与技术国家实验室，北京１０００８４）　（ｓｔｅｐｈｅｎｇｅｎｉｕｓ＠ｇｍａｉｌ．ｃｏｎ）　摘要：将网格模型按照表面特征进行分割，在计算机图形学中有着广泛的应用。在传统的网格分割层次聚类　算法的基础上，利用相邻聚类公共边的长度，公共顶点的曲率，以及聚类的面积对聚类之间的合并成本进行加权，提　出新的合并成本函数，更好地利用网格表面特征指导聚类之间的合并过程。同时，针对传统分割算法中分割区域边　界存在的锯齿现象，针对每一个分割区域，全局考虑其与相邻分割区域的模糊地带，利用最大流最小割的方法优化分　割区域边界，从而消除锯齿，平滑边界。　关键词：表面特征；自动分割；层次聚类；合并成本函数；最小割　中图分类号：ＴＰ３９１．７２　文献标志码：Ａ　Ａｕｔｏｍａｔｉｃ　ｍｅｓｈ　ｓｅｇｍｅｎｔａｔｉｏｎ　ｂａｓｅｄ　ｏｎ　ｈｉｅｒａｒｃｈｉｃａｌ　ｃｌｕｓｔｅｒｉｎｇ　ＺＨＡＮＧ　Ｓｅｎ　＇　・　一，ＨＡＮ　Ｑｉ—ｃａｉ　＇　一，ＹＡＮ　Ｋｕｎ。ｐｅｎｇ　’。一，ＺＨＡＮＧ　Ｈｕｉ　，　，ＹＯＮＧ　Ｊｕｎ　ｈａｉ　’。，　（１．Ｓｃｈｏｏｌ　ｏｆＳｏｔｆｗａｒｅ，Ｔｓｉｎｇｈｕａ　Ｕｎｉｖｅｒｓｉｔｙ，Ｂｅｉｊｉｎｇ　１０００８４，Ｃｈｉｎａ；　２，Ｄｅｐａｒｔｍｅｎｔ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ，Ｔｓｉｎｇｈｕａ　Ｕｎｉｔｅｒｓｉｔｙ，Ｂｅｉｊｉｎｇ　１０００８４，Ｃｈｉｎａ；　３．Ｋｅｙ　Ｌａｂｏｒａｔｏｒｙｆｏｒ　Ｉｎｆｏｒｍａｔｉｏｎ跏　ｍ　Ｓｅｃｕｒｉｔｙ　ｏｆＭｉｎｉｓｔｙｒ　ｆｏＥｄｕｃａｔｉｏｎ，Ｔｓｉｎｇｈｕａ　Ｕｎｉｖｅｒｓｉｔｙ，Ｂｅｉｊｉｎｇ　１０００８４，Ｃｈｉｎａ；　・４．Ｎａｔｉｏｎａｌ　ＬａｂｏｒａｔｏｒｙｆｏｒＩｎｆｏｒｍａｔｉｏｎ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ，Ｔｓｉｎｇｈｎａ　Ｕｎｉｖｅｒｓｉｔｙ，Ｂｅｒｉｎｇ　１０００８４，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：Ａｕｔｏｍａｔｉｃ　ｍｅｓｈ　ｓｅｇｍｅｎｔａｔｉｏｎ　ｈａｓ　ｂｅｅｎ　ｗｉｄｅｌｙ　ｕｓｅｄ　ｉｎ　ｃｏｍｐｕｔｅｒ　ｇｒａｐｈｉｃｓ．Ｂａｓｅｄ　ｏｎ　ｔｒａｄｉｔｉｏｎａｌ　ｈｉｅｒａｒｃｈｉｃａｌ　ｃｌｕｓｔｅｒｉｎｇ　ｓｅｇｍｅｎｔａｔｉｏｎ　ｍｅｔｈｏｄｓ，ａ　ｎｅｗ　ｃｏｓｔ　ｆｕｎｃｔｉｏｎ　Ｗａｓ　ｐｒｅｓｅｎｔｅｄ　ｗｈｉｃｈ　ｃｏｍｂｉｎｅｄ　ｔｈｅ　ｌｅｎｇｔｈ　ｏｆ　ｃｏｍｍｏｎ　ｂｏｕｎｄａｒｙ　ｏｆ　ａｄｊａｃｅｎｔ　ｃｌｕｓｔｅｒｓ，ｔｈｅ　ｃｕｒｖａｔｕｒｅ　ｏｆ　ｃｏｍｍｏｎ　ｖｅｒｔｉｃｅｓ　ａｎｄ　ｔｈｅ　ａｒｅａ　ｏｆ　ｅａｃｈ　ｃｌｕｓｔｅｒ．Ｔｈｅ　ｎｅｗ　ｃｏｓｔ　ｆｕｎｃｔｉｏｎ　ｃｏｕｌｄ　ｍｏｒｅ　ｃｌｅａｒｌｙ　ｒｅｐｒｅｓｅｎｔ　ｔｈｅ　ｐｒｏｐｅｒｔｉｅｓ　ｏｆ　ｔｈｅ　ｍｅｓｈ，ａｎｄ　ｐｅｒｆｏｒｍ　ｂｅｔｔｅｒ　ｉｎ　ｔｈｅ　ｃｌｕｓｔｅｒｓ　ｍｅｒｇｉｎｇ　ｐｒｏｃｅｓｓ．Ｂｅｓｉｄｅｓ，ｃｏｎｓｉｄｅｒｉｎｇ　ｔｈｅ　ｊａｇｇｅｄ　ｃｏｍｍｏｎ　ｂｏｕｎｄａｒｉｅｓ，ａ　ｌｆｏｗ　ｎｅｔｗｏｒｋ　Ｗａｓ　ｃｏｎｓｔｒｕｃｔｅｄ　ｉｎ　ｔｈｅ　ｆｕｚｚｙ　ａｒｅａ　ｏｆ　ｅａｃｈ　ｃｌｕｓｔｅｒ　ａｎｄ　ａｌｌ　ｏｆ　ｉｔｓ　ａｄｊａｃｅｎｔ　ｏｎｅｓ　ｔｏ　ｏｐｔｉｍｉｚｅ　ａｎｄ　ｓｍｏｏｔｈ　ｔｈｅ　ｂｏｕｎｄａｒｉｅｓ　ｂｙ　ｍｉｎｉｍｕｍ　ｃｕｔ　ａｌｇｏｒｉｔｈｍ．　Ｋｅｙ　ｗｏｒｄｓ：Ｓｕｌ￣ａｃｅ　ｆｅａｔｕｒｅ；ａｕｔｏｍａｔｉｃ　ｓｅｇｍｅｎｔａｔｉｏｎ；ｈｉｅｒａｒｃｈｉｃａｌ　ｃｌｕｓｔｅｒｉｎｇ；ｍｅｒｇｉｎｇ　ｃｏｓｔ　ｆｕｎｃｔｉｏｎ；ｍｉｎｉｍｕｍ　ｃｕｔ　０　引言　价分析Ｋ均值聚类、层次聚类和最小割等三种方法所得分割　线的重合程度，综合确定分割区域的边界线。随机分割算法　在计算机图形学领域中，模型的自动分割技术有着越来　的分割效果能够较好地反映网格表面特征，但由于其综合了　越重要的意义。网格模型分割技术在模型简化、参数化及纹　多种聚类方法，算法效率较低。此外，Ｌａｉ等人　利用随机游　理映射ｌ１　等方面有着广泛应用。网格分割有利于实现网格　动方法，ｎｕ等人　、Ｌｉｎ等人　］、Ａｔｔｅｎｅ等人　“　和Ｓｈａｐｉｒａ等　操作的区域化及并行化，提高网格处理的效率，而其中符合模　人Ｌ】　分别基于光谱分析、临界点分析、拟合基元、形状直径函　型表面特征的网格分割，能够利用网格的特征线和特征点生　数提出了相应的网格分割算法。Ｃｈｅｎ等人　利用对ｌ９类　成网格分割边界线，降低网格分割所带来的失真及信息丢失。　３８０个曲面模型进行的４３００次人工分割的效果，建立了衡量　近年来，基于聚类的基本思想，对于模型分割的研究取　模型分割效果的基准，并对文献［５，７—１２］中的分割算法进行　得了显著的进展。Ｋａｔｚ等人　先对模型进行初始分割，生成　的测试比较。其结果表明，各种网格分割算法的适用范围不　模型的明显特征和特征间的模糊区域，然后基于最小割算法　同，没有一种自动分割算法能对所有类型的模型进行最理想的　对模糊区域进行优化，从而实现对于模型的分割。Ｓｈｌａｆｍａｎ　分割。　等人　和Ｋａｔｚ等人　分别采用Ｋ均值聚类以及基于特征点　本文基于聚类的思想对网格模型自动分割。主要的贡献　和核心提取的方法对模型进行初始分割，然后利用最小割算　在于：首先利用相邻聚类公共边的长度，公共顶点的曲率，以　法对得到的分割线进行优化。然而以上文献的最小割算法　及聚类的面积对聚类之间的合并成本加权，提出新的合并成　中，每次仅针对一对相邻分割区域的公共边界线进行平滑及　本函数；其次在相邻分割区域间的模糊地带构建流网络，利用　优化，并未考虑整个分割区域的整体边界线的平滑。　最小割的方法更新模糊地带面片所属聚类，优化和平滑分割　Ｇｏｌｏｖｉｎｓｋｉｙ等人　采用随机分割的方法分割模型，其通过评　区域边界。　收稿日期：２０１０—０７—１２；修回日期：２０１０—０８～０４。　基金项目：国家自然科学基金资助项目（６０９０３１０６；６０６３５０２０）；国家８６３计划项目（２００７ＡＡ０４０４０１）；国家９７３计划项目（２０１０ＣＢ３２８００１）。　作者简介：张森（１９８５～），男，山东平度人，博士研究生，主要研究方向：网格处理、计算机辅助设计；韩其才（１９８４一），男，山东费县人，硕士研　究生，主要研究方向：网格分割；闫琨鹏（１９８７一），男，山西高平人，硕士研究生，主要研究方向：网格分割；张慧（１９７４一），女，江苏无锡人，副教　授，主要研究方向：计算机图形学、计算机辅助设计；雍俊海（１９７３一），男，福建莆田人，教授，主要研究方向：计算机图形学、计算机辅助设计。　２　计算机应用　２０１０正　１　基于分割曲面面积以及曲率特征的层次聚类　１．１层次聚类基本原理　疏情况和网格面片的基本几何属性对合并成本的影响，文献　［７］在方程（１）的基础上，加入了聚类的面积的因素；文献　［１３］虽然考虑到网格凹凸程度会对聚类周长产生影响，但没　有给出具体的分析及函数公式。　通常情况下，理想的网格分割边界线应该通过网格的特　征线，并位于网格表面凹陷的部分。而网格顶点的曲率特征　层次聚类方法有两种：聚合法和分裂法。聚合的层次聚　类是一种自下而上的方法，开始时将每个对象当做一个聚类，　然后不断地对聚类进行合并，直到将所有的对象合并为一个　聚类为止。分裂的层次聚类是一种自上而下的方法，开始时　是衡量网格凹凸程度的重要因素，凸起点处曲率值较大，凹陷　点出曲率值较小。所以，本文利用网格表面的凹凸属性，网格　面片的面积以及边界处公共边长度对合并成本函数进行加　所有的对象同属于一个聚类，然后将该聚类分裂成两个聚类，　再将分裂得到的聚类进行不断地分裂，直到每个对象成为一　个聚类。本文采用的是聚合式的层次聚类方法。　Ｓｉｔｆ等人　提出了数据划分的层次聚类方法，并给出了　聚合式层次聚类方法的基本步骤。给定Ⅳ个聚类对象，以及　一个Ｎ×Ｎ的合并成本矩阵，聚合式层次聚类方法的基本步　骤如下：　１）将每个对象分别作为一个聚类，构建Ⅳ个聚类的合并　成本矩阵；　２）遍历相似度矩阵，合并合并成本最小（即相似度最高）　的两个聚类；　３）计算新聚类与所有旧的聚类之间的合并成本，更新合　并成本矩阵；　４）不断重复２）～３），直到最终得到一个包含Ⅳ个对象的　聚类。　利用此聚类过程，可以建立所有对象之问的层次关系。　但在实际应用当中，往往需要将所有对象进行一定数量的分　类，所以，上述迭代过程的终止条件可以相应调整为聚类数目　达到了某个期望值则停止迭代。　在利用聚合式层次聚类分割网格的过程中，通常先将每　个三角网格当做一个聚类，利用网格面片之间的拓扑关系和　几何属性，计算不同距离之间的合并成本，构建聚类间的合并　成本矩阵，然后迭代地合并相邻聚类以及更新合并成本矩阵，　直到聚类数目达到某个期望值为止。在网格分割的过程中，　聚类之间合并成本函数的选择决定了分割结果质量。好的合　并成本应该综合考虑网格表面属性，能够优先合并具有相似　属性的面片，并保留网格特征部分。因此，本文将在下面对传　统的合并成本函数进行讨论，并综合考虑网格属性，提出新的　函数形式。　１．２合并成本函数　合并成本是衡量不同聚类之间相似度的函数。合并成本　越小，不同聚类之间的相似度就越高，合并的优先级也就越　高。聚类间合并成本的确定通常可以分为四种ｎ　：最小距离　（Ｓｉｎｇｌｅ—ｌｉｎｋ），用两个聚类所包含对象之间的最小距离来表　示；最大距离（Ｃｏｍｐｌｅｔｅ—ｌｉｎｋ），用两个聚类所包含对象之间的　最大距离来表示；平均值距离，用两个聚类各自中心点之间的　距离表示；平均距离（Ａｖｅｒａｇｅ—ｌｉｎｋ），用两个聚类包含的对象　之间的平均距离来表示。　对于两个相邻聚类　和Ｙ，Ｓｈｉ等人　对其合并成本的　定义如下：　１　ｃ。ｓ　（　，ｙ）　＿＿丽　（　）　一ａＳＳＯＶ（　，Ｖ）。ａｓ十一ｓｏｖ（Ｙ，Ｖ）　　其中：ＣＵｔ（Ｘ，ｙ）表示　和ｙ的公共边的长度，ａｓｓｏｖ（Ｘ，Ｖ）和　ａｓ￥ｏｖ（】／，Ｖ）分别表示　和ｌ，各自边界的周长。　在利用层次聚类进行网格分割的过程中，考虑到网格稀　权，定义两个聚类　和ｙ之间的合并成本函数：　（２）　其中：ｅ＠ｅ（Ｘ，ｌ，）＝　Ｗ　×ｅ　，Ｗ　为公共边ｉ两个顶点曲率的　平均值，ｅ　为公共边ｉ的物理长度，ａｒｅａ（　）和ａｒｅａ（Ｙ）分别为　聚类　和Ｙ的面积。　在新的合并成本函数中，公共边长（曲率加权值）越大、　面积越小的相邻聚类，其合并成本越小，合并的优先级越高。　这使得网格模型表面面积较小的区域不断被合并，而凹陷程　度较大的边界得以保留，最终分割区域的边界线趋向于位于　模型表面的凹陷处，符合人工的分割模型的结果。　２　边界优化　利用层次聚类方法按照模型表面特征对网格进行自动分　割所得的结果中，分割区域的边界线会存在锯齿现象。针对　此问题，本文采用最大流最小割的方法，针对每一个分割区　域，全局地考虑其相邻区域，在它们的模糊地带构建流网络，　利用最小割的方法优化分割边界线，平滑分割边界。　２．１最大流最ｄ，ｔ￣ｌ基本原理　在流网络中寻找一条从原点到汇点的最大流路径是图论　中的基本问题之一。流网络是一个连通的加权有向图，每条　弧都有一个非负的容量值，顶点集合中的源点和汇点分别代　表网络的起点和终点。网络中的流就是从源点流向汇点的可　行流，是定义在网络上的一个非负函数。流网络的割集是从　源点到汇点的必须经过的边的集合，若去除割集中的边，则流　无法从源点到达汇点。最大流理论指出，任意一个流网络的　最大流量等于该网络的最小的割的容量。　在平滑和优化初始分割区域边界的过程中，利用模型的　对偶图构成一个流网络，流网络中的节点对应网格模型中的　面片，每条弧连接一对相邻面片。若拆除流网络割集中的弧，　即割断所有相应网格的相邻关系，则可以对模型进行分割。　由于最小割集中弧的数量最少，所以利用最小割集进行分割，　可以得到最短的分割线，能够对分割边界进行平滑和优化。　在此过程中，初始流网络的建立以及流网络中弧的容量　的定义直接影响到最小割所得边界质量，因此将在下面对这　两个问题进行详细的描述。　２．２构建流网络　针对每一个初始分割区域，全局地考虑其相邻的区域，在　它们之间的模糊地带，基于模型的对偶图构建流网络。具体　的构建方法可以描述为：当前被优化的分片记为　，其网格　数目记为ｍ（　），　的边界线记为Ｂ，与　相邻的所有分片　记为Ｐ　，Ｐｓ和Ｐ　之问的流网络记为Ｆ（　，ｔ）。流网络Ｆ（ｓ，ｔ）的　构建过程如下。　增刊２　张森等：基于层次聚类的网格模型自动分割方法　３　１）遍历Ｐ　中的所有网格，得到在边界线　上的网格集　４）将最小割集中的面片划归到　中，完成对分片　的　边界优化；　合，记为　，其网格数目记为ｍ（Ｂ　）。　２）构建Ｐ　一侧的流网络，记为Ｆ（ｓ）。首先，将　；中的网　格并入Ｆ（ｓ）；然后，将　中与Ｆ（ｓ）相邻的网格迭代地并入　５）迭代步骤１）～４），直到所有分片的边界线被优化为　止。　Ｆ（ｓ），直到Ｆ（　）中的网格数目达到一定数量，记为　．ｎ　的　值可以根据ｍ（Ｂ　）和ｍ（　）确定，本文取　＝ｍｉｎ｛５×　ｍ（Ｂ；），ｍ（Ｐ　）／３｝。　图１（ａ）和图２（ａ）为模型利用层次聚类得到的初始分割　结果，图１（ｃ）和图２（ｂ）为模型利用最小割算法对分割区域　边界线平滑优化后的结果，图２中间为模型分割区域边界局　部放大的对比。其中第二组对比中，模型腰部曲线的平滑效　果比较明显，不再详细比较。经过对比可以看出，利用边界平　３）遍历Ｂ　，得到与其相邻的Ｐ　中的所有网格，即Ｐ　中在　边界线　上的网格集合，记为Ｂ　，其网格数Ｅｌ记为ｍ（Ｂ　）。　４）构建尸ｌ－－Ｎ的流网络，记为Ｆ（ｔ）。首先，将　中的网　滑优化算法能够针对每一个分片区域全局的改善其边界线的　格并入Ｆ（ｔ）；然后，将Ｐ　中与Ｆ（ｔ）相邻的网格迭代地并入　Ｆ（ｔ），直到Ｆ（ｔ）中的网格数目达到一定数量，记为／／，　．ｎ　的　值可以根据　和ｍ（Ｂ　）确定，本文取ｎ　＝ｍａｘ｛　，１０×　ｍ（Ｂ　）｝。　５）加入虚拟的源点　和汇点ｔ，并设定ｓ与Ｆ（ｓ）的边界　网格相邻，ｔ与Ｆ（ｔ）的边界网格相邻。此时，Ｆ（ｓ，ｔ）＝｛ｓ，　Ｆ（　），，（ｔ），ｔ｝，流网络构建完毕。Ｆ（ｓ，ｔ）中的网格对应流网　络的节点，相邻网格之间有一条连接相应节点的弧。　图１（ａ）所示为将Ａｒｍａｄｉｌｌｏ模型分割成３片的初始分割　效果，图１（ｂ）为对上半身的边界线构建全局流网络的示意　图。　（ａ）初始分割效果　（ｂ）流网络　（ｃ）边界优化后效果　图１　最小割算法平滑优化边界效果　２．３容量的定义　理想情况下，最小割集应该位于模型表面的凹陷特征处，　根据容量小的弧构成最小割集的原则　Ｊ，在定义弧的容量　时，相邻网格所在区域的凹陷越明显，其对应的弧的容量应该　越小。对于弧的容量，文献［４］采用相邻网格间的二面角来　定义，文献［６］采用相邻网格间的二面角和公共边长来定义。　由于相邻网格间的二面角只能反映局部的凸凹特征，而顶点的　曲率却能很好地反映全局的凸凹特征，所以，本文采用相邻网　格间公共边的顶点曲率和公共长度来定义相应的容量。　对于两个相邻网格ａ和ｂ，其公共边记为ｅ，ｅ的物理长度　记为ｄｉｓｔ（ｅ），ｅ的两个顶点的曲率的平均值记为ｃｌ￣ｒ１）（ｅ），则　ａ和ｂ之间的弧的容量为：　ｃａｐ（口，６）：６．￡些　＋（１一占）．—ｄｉ。ｓ萎ｔ　（ｅ）　（３）　Ｃ“，　“　其中：６为顶点曲率在容量中的权重，其取值范围为（０，１）；　ＣＵ／＂Ｕ和ｄｉｓｔ分别为整个流网络中所有公共边的曲率和物理长　度的平均值。　２．４边界平滑优化算法　边界优化的算法流程为：　１）选取待优化的分片　；　２）建立当前分片的全局流网络，计算流网络中所有弧的　容量；　３）利用最小割算法中的标号法求取当前流网络的最小　割集；　形状，使得边界线位于模型的特征处，并通过模型表面凹陷的　地方。　一　（ａ）初始分割的结果　（ｂ）边界优化后的结果　图２分割区域边界优化效果　３　实验结果及分析　本文的实验环境为ＣＰＵ频率２　ＧＨｚ，内存大小２　ＧＢ，操作　系统Ｗｉｎｄｏｗｓ　ＸＰ。　图３和图４中展示了利用本文提出的层次聚类分割以及　最小割算法优化平滑分割区域边界线的方法实现的对网格模　型的自动分割结果。图３为Ａｒｍａｄｉｌｏ模型在分片数目为３、　５、６和７，Ｄｉｎｏ模型在分片数目为３、６、１ｌ和１４时的自动分割　结果。通过实验结果可以看出，该算法能够根据模型的表面　特征实现网格的自动分割，同时分割区域的边界线光滑，分布　于网格的特征处。图４中展示了此算法在处理复杂拓扑模型　的自动分割时，同样具有良好的适应性。　分片数目为３　分片数目为５　分片数目为６　分片数目为７　（ａ）Ａｎｎａｄｉｌ１ｏ模型　分片数目为３　分片数目为６　分片数目为ｌ１　分片数目为ｌ４　（ｂ）Ｄｉｎｏ模型　图３　Ａｒｍａｄｉｌｌｏ以及Ｄｉｎｏ模型自动分割结果　基于文献［１３］的分割基准，在不考虑算法效率的情况　下，文献［７］中的随机分割算法能够得到最佳的最接近人工　分割的分割效果。利用本文中的算法分别对相应的模型进行　自动分割，图５（ａ）中是利用文献［７］中的部分分割结果，图５　（ｂ）中是利用本文中的算法得到的分割结果。通过对比可以　看出，本文算法的效果接近人工分割的结果。　表１中是不同模型进行分割所需要的时间。由于随机分　割的算法需要评价和综合多种分割算法，在将输入网格模型　简化到４０００并确定分割数目后，依然需要多次迭代消耗　４　ａｒｉｎ左右时间才能够得到较优的边界分割线。本文在聚类　４　计算机应用　２０１０盘　ｍｅｓｈ　ｐａｒａｍｅｔｅｒｉｚａｔｉｏｎ　ｕｓｉｎｇ　ｓｐｅｃｔｒａｌ　ａｎａｌｙｓｉｓ【Ｃ】／／Ｅｕｒｏｇｒａｐｈｉｃｓ　Ｓｙｍｐｏｓｉｕｍ　ｏｎ　Ｇｅｏｍｅｔｒｙ　Ｐｒｏｃｅｓｓｉｎｇ．Ｎｅｗ　Ｙｏｒｋ：ＡＣＭ，２００４：４５—　过程中利用新的合并成本函数得到初始分割结果，然后利用　最小割方法全局优化平滑分割区域边界线，避免了迭代过程，　提高了分割算法的效率，而且分割结果接近人工分割结果。　（ａ）　（ｂ）　（ｃ）　（ｄ）　（ｅ）　（ｆ）　图４复杂拓扑模型的网格分割结果　？　ｊ　ｔ　、ｌ　（ａ）随机分割法　（ｂ）本文算法　图５与随机分割算法的效果对比　表１网格分割时间　网格数目　分割时间／ｓ　４０００　０．４３７　ｌ００００　３．０３１　２００００　１１．６０９　３００００　２５．１５６　４００００　５９．４ｏ６　４　结语　本文在传统的网格分割层次聚类算法的基础上，采用层　次聚类的方法对网格模型进行了初始分割，在构建合并成本　矩阵的过程中，利用相邻聚类公共边的长度，公共顶点的曲　率，以及聚类的面积对聚类之问的合并成本进行加权，提出新　的合并成本函数，从而在聚类过程中优先合并面积较小的非　网格特征处的面片，保留了网格表面凹陷的特征线，更好地利　用网格表面特征指导层次聚类。然后在层次聚类所得初始分　割的基础上，针对分割区域边界存在的锯齿现象，对于每一个　分割区域，全局考虑与其相邻的分割区域，在它们的模糊地带　构建流网络，基于区域内网格曲率等几何属性构建流网络中　弧的容量，利用最小割的方法更新模糊地带面片所属聚类，从　而优化分割区域边界，消除锯齿，平滑边界。　参考文献：　【１　１　ＧＡＲＬＡＮＤ　Ｍ，ＷＩＬＩ　ＭＯ　ＦＴ　Ａ，ＨＥＣＫＢＥＲＴ　Ｐ　Ｓ．Ｈ｛ｅｒａｒｃｈｉｃａｌ　ｆａｃｅ　ｃｌｕｓｔｅｒｉｎｇ　ｏｎ　ｐｏｌｙｇｏｎａｌ　ｓｕｒｆａｃｅｓ［Ｃｌ／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ＡＣＭ　Ｓｙｍｐｏｓｉ—　ｕｎｌ　ｏｎ　Ｉｎｔｅｒａｃｔｉｖｅ　３Ｄ　Ｇｒａｐｈｉｃｓ．Ｎｅｗ　Ｙｏｒｋ：ＡＣＭ．２００１：４９—５８．　ｆ　２１　ＺＨＯＵ　Ｋ，ＳＹＮＤＥＲ　Ｊ，ＧＵＯ　Ｂ，ｅｔ　ａ１．Ｉｓｏ—ｃｈａｒｔｓ：Ｓｔｒｅｔｃｈ—ｄｒｉｖｅｎ　５４．　［３】ＬＥＶＹ　Ｂ，ＰＥＴＩＴＪＥＡＮ　Ｓ，ＲＡＹ　Ｎ，ｅｔ　ａ１．Ｌｅａｓｔ　ｓｑｕａｒｅｓ　ｃｏｕｆｏｒｍａｌ　ｍａｐｓ　ｆｏｒ　ａｕｔｏｍａｔｉｃ　ｔｅｘｔｕｒｅ　ａｔｌａｓ　ｇｅｎｅｒａｔｉｏｎ［ＣＪ／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　２９ｔｈ　Ａｎｎｕａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｃｏｍｐｕｔｅｒ　Ｇｒａｐｈｉｃｓ　ａｎｄ　Ｉｎｔｅｒａｃｔｉｖｅ　Ｔｅｅｈ—　ｎｉｑｕｅｓ．Ｎｅｗ　Ｙｏｒｋ：ＡＣＭ．２００２：３６２—３７１．　［４］ＫＡＴＺ　Ｓ，ＴＡＬ　Ａ．Ｈｉｅｒａｒｃｈｉｃａｌ　ｍｅｓｈ　ｄｅｃｏｍｐｏｓｉｔｉｏｎ　ｕｓｉｎｇ　ｆｕｚｚｙ　ｃｌｕｓ－　ｔｅｒｉｎｇ　ａｎｄ　ｃｕｔｓ【Ｊ】．ＡＣＭ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　Ｇｒａｐｈｉｃｓ，２００３，２２（３）：　９５４—９６１．　［５］　ＳＨＬＡＦＭＡＮ　Ｓ，ＴＡＬ　Ａ，ＫＡＴＺ　Ｓ．Ｍｅｔａｍｏｒｐｈｏｓｉｓ　ｏｆ　ｐｏｌｙｈｅｄｒａｌ　ＳＵＥ－　ｆａｃｅｓ　ｕｓｉｎｇ　ｄｅｃｏｍｐｏｓｉｔｉｏｎ［Ｊ】．Ｃｏｍｐｕｔｅｒ　Ｇｒａｐｈｉｃｓ　Ｆｏｒｕｍ，２００２，２１　（３）：２１９—２２８．　ｆ　６】　ＫＡＴＺ　Ｓ，ＬＥＩＦＭＡＮ　Ｇ，ＴＡＬ　Ａ．Ｍｅｓｈ　ｓｅｇｍｅｎｔａｔｉｏｎ　ｕｓｉｎｇ　ｆｕａｍｒｅ　ｐｏｉｎｔ　ａｎｄ　ｃｏｒｅ　ｅｘｔｒａｃｔｉｏｎ【ｊ】．Ｔｈｅ　Ｖｉｓｕａｌ　Ｃｏｍｐｕｔｅｒ，２００５，２１（８／　１Ｏ１１：６４９—６５８．　【７】　ＧＯＬＯＶ１ＮＳＫＩＹ　Ａ，ＦＵＮＫＨＯＵＳＥＲ　Ｔ．Ｒａｎｄｏｍｉｚｅｄ　ｃｕｔｓ　ｆｕｒ　３　Ｄ　ｍｅｓｈ　ａｎａｌｙｓｉｓ［Ｃ】／／Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｃｏｍｐｕｔｅｒ　Ｇｒａｐｈｉｃｓ　ａｎｄ　Ｉｎｔｅｒａｃｔｉｖｅ　Ｔｅｃｈｎｉｑｕｅｓ．Ｎｅｗ　Ｙｏｒｋ：ＡＣＭ，２００８：１４５．　【８１　Ｉ　Ｉ　Ｙ　Ｋ，ＨＵ　Ｓ　Ｍ，ＭＡＲＴＩＮ　Ｒ　Ｒ，ｅｔ　ａ１．Ｆａｓｔ　ｍｅｓｈ　ｓｅｇｍｅｎｔａｔｉｏｎ　ｕ—　ｓｉｎｇ　ｒａｎｄｏｍ　ｗａｌｋｓ【Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　２００８　ＡＣＭ　ＳＤｎｐｏｓｉｕｍ　ｏｎ　Ｓｏｌｉｄ　ａｎｄ　Ｐｈｙｓｉｃａｌ　Ｍｏｄｅｌｉｎｇ．Ｎｅｗ　Ｙｏｒｋ：ＡＣＭ，２００８：１８３—１９１．　【９】ＬＩＵ　Ｒ，ＺＨＡＮＧ　Ｈ．Ｓｅｇｍｅｎｔａｔｉｏｎ　ｎｆ　３Ｄ　ｍｅｓｈｅｓ　ｔｈｒｎｕｇｈ　ｓｐｅｃｔｒａｌ　ｃｌｕｓｔｅｒｉｎｇ【Ｃ　Ｊ／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆｔｈｅ　１２ｔｈ　Ｐａｃｉｉｆｃ　Ｃｏｎｆｅｒｅｎｃｅ　ＯＤ　Ｃｏｍ—　ｐｕｔｅｒ　Ｇｒａｐｈｉｃｓ　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎｓ．Ｗａｓｈｉｎｇｔｏｎ，ＤＣ：ＩＥＥＥ　Ｃｏｍｐｕｔｅｒ　Ｓｏｃｉｅｔｙ，２００４：２９８—３０５．　【１０］Ｌ１Ｎ　Ｈ　Ｙ　Ｓ，ＨＡ０　Ｈ　Ｙ　Ｍ，ＬＩＮ　Ｊ　Ｃ．Ｖｉｓｕａｌ　ｓａｌｉｅｎｃｅ—ｇｕｉｄｅｄ　ｍｅｓｈ　ｄｅｃｏｍｐｏｓｉｔｉｏｎ［Ｃ】／／２０００　ＩＥＥＥ　６ｔｈ　Ｗｏｒｋｓｈｏｐ　ｏｎ　Ｍｕｌｔｉｍｅｄｉａ　Ｓｉｇｎａｌ　Ｐｒｏｃｅｓｓｉｎｇ．Ｗａｓｈｉｎｇｔｏｎ，ＤＣ：ＩＥＥＥ　Ｃｏｍｐｕｔｅｒ　Ｓｏｃｉｅｔｙ，２００４：３３１—　３３４．　ｆ　１　１】ＡＴＴＥＮＥ　Ｍ，ＦＡＬＣＩＤＩＥＮＯ　Ｂ，ＳＰＡＧＮＵＯＬＯ　Ｍ．Ｈｉｅｒａｒｃｈｉｃａｌ　ｍｅｓｈ　ｓｅｇｍｅｎｔａｔｉｏｎ　ｂａｓｅｄ　ｏｎ　ｆｉｔｔｉｎｇ　ｐｒｉｍｉｔｉｖｅｓ［Ｊ】．Ｔｈｅ　Ｖｉｓｕａｌ　Ｃｏｍｐｕｔｅｒ，　２００６，２２（３）：１８１—１９３．　【１　２】ＳＨＡＰＩＲＡ　Ｌ，ＳＨＡＭＩＲ　Ａ，ＣＨＯＨＥＮ－ＯＲ　Ｄ．Ｃｏｎｓｉｓｔｅｎｔ　ｍｅｓｈ　ｐａｔｔｉ—　ｔｉｏｎｉｎｇ　ａｎｄ　ｓｋｅｌｅｔｏｎｉｓａｔｉｏｎ　ｕｓｉｎｇ　ｔｈｅ　ｓｈａｐｅ　ｄｉａｍｅｔｅｒ　ｆｕｎｃｔｉｏｎ【Ｊ】．　Ｔｈｅ　Ｖｉｓｕａｌ　Ｃｏｍｐｕｔｅｒ，２００８，２４（４）：２４９—２５９．　［１３】ＣＨＥＮ　Ｘ，ＧＯＬＯＶＩＮＳＫＩＹ　Ａ，ＦＵＮＫＨＯＵＳＥＲ　Ｔ．Ａ　ｂｅｎｃｈｍａｒｋ　ｆｕｒ　３Ｄ　ｍｅｓｈ　ｓｅｇｍｅｎｔａｔｉｏｎ【Ｃ】／／Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｃｏｍｐｕｔｅｒ　Ｇｒａｐｈｉｃｓ　ａｎｄ　Ｉｎｔｅｒａｃｔｉｖｅ　Ｔｅｃｈｎｉｑｕｅｓ．ＮｅⅥＹｏｒｋ：ＡＣＭ．２００９：７３．　【１４］ＪＯＨＮＳＯＮ　Ｓ　Ｃ．Ｈｉｅｒａｒｃｈｉｃａｌ　ｃｌｕｓｔｅｒｉｎｇ　ｓｃｈｅｍｅｓ［Ｊ】．Ｐｓｙｃｈｏｍｅｔｒｉ—　ｋａ，１９６７，３２（３）：２４１—２５４．　［１５】ＹＡＭＡＵＣＨＩ　Ｈ，ＧＵＭＨＯＬＤ　Ｓ，ＺＡＹＥＲ　Ｒ，ｅｔ　ａ１．Ｍｅｓｈ　ｓｅｇｍｅｎｔａ—　ｔｉｏｎ　ｄｒｉｖｅｎ　ｂｙ　Ｇａｕｓｓｉａｎ　ｃｕｒｖａｔｕｒｅ【Ｊ］．Ｔｈｅ　Ｖｉｓｕａｌ　Ｃｏｍｐｕｔｅｒ，２００５，　２１（８／１０）：６５９—６６８．　［１６］ＳＨＩ　Ｊ，ＭＡＨＫ　Ｊ．Ｎｏｒｍａｌｉｚｅｄ　ｃｕｔｓ　ａｎｄ　ｉｍａｇｅ　ｓｅｇｍｅｎｔａｔｉｏｎ【Ｊ］．　ＩＥＥＥ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　Ｐａｔｔｅｒｎ　Ａｎａｌｙｓｉｓ　ａｎｄ　Ｍａｃｈｉｎｅ　Ｉｎｔｅｌｌｉｇｅｎｃｅ，　２０００，２２（８）：８８８—９０５．　［１７１　ＳＨＡＭＩＲ　Ａ．Ａ　ｓｕｒｖｅｙ　ｏｆｆ　ｍｅｓｈ　ｓｅｇｍｅｎｔａｔｉｏｎ　ｔｅｃｈｎｉｑｕｅｓ［Ｊ］．Ｃｏｒｎ—　ｐｕｔｅｒ　Ｇｒａｐｈｉｃｓ　Ｆｏｒｕｍ，２００８，２７（６）：１５３９—１５５６．　［１　８］ＭＩＡＯ　ＹＯＮＧＷＥ１，ＦＥＮＧ　ＪＩＥＱＩＮＧ　Ｘ１ＡＯ　ＣＨＵＮＸ１Ａ，ｅｔ　ａ１．Ｄｉｆｅｒ－　ｅｎｔｉｌａｓ－－ｂａｓｅｄ　ｓｅｇｍｅｎｔａｔｉｏｎ　ａｎｄ　ｐａｒａｍｅｔｅｆｉｚａｔｉｏｎ　ｆｏｒ　ｐｏｉｎｔ・－ｓａｍｐｌｅｄ　ｓｕｒｆａｃｅｓ『Ｊ】．Ｊｏｕｒｎａｌ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ，２００７，　２２（５）：７４９—７６０．　［１９】ＬＩＵ　Ｒ，ＺＨＡＮＧ　Ｈ．Ｍｅｓｈ　ｓｅｇｍｅｎｔａｔｉｏｎ　ｖｉａ　ｓｐｅｃｔｒａ１　ｅｍｂｅｄｄｉｎｇ　ａｎｄ　ｃｏｎｔｏｕｒ　ａｎａｌｙｓｉｓ［Ｊｊ．ＣｏｍｐｕｔｅｒＧｒａｐｈｉｃｓ　Ｆｏｒｕｍ，２００７，２６（３）：３８５　—３９４．　【２Ｏ］段明秀．层次聚类算法的研究及应用［Ｄ］．长沙：中南大学，　２００９：１６—１７