结合语义本体与泊松方程的动画角色模型分割

潘 翔，童伟淮，张三元，郑河荣

（1.浙江工业大学计算机科学与技术学院，浙江杭州310023；2.浙江大学计算机科学与技术学院，浙江杭州310058）

结合语义本体与泊松方程的动画角色模型分割

潘 翔1，童伟淮1，张三元2，郑河荣1

（1.浙江工业大学计算机科学与技术学院，浙江杭州310023；2.浙江大学计算机科学与技术学院，浙江杭州310058）

针对动画角色模型由于姿态变化所导致的分割不一致问题，提出语义本体驱动的层次一致性分割算法.针对三维模型提取出语义标签和局部几何特征之间的映射关系，形成分割本体.在分割过程中，采用支持向量机（SVM）和局部几何特征识别出语义标签，并根据语义标签驱动层次进行分割，保证动画角色模型分割层次的一致性.针对姿态变化下分割边界所具有的等周长性，采用泊松方程定义等值线.此优化方法使分割边界光滑，还使其在姿态变化下具有一致性.在实验部分，对不同姿态下的各类动画角色模型进行验证分析，得到一致的层次分割效果.与已有方法比较，所提出的分割本体能够解决不同类模型优化参数的自适应选择问题，提高了分割质量.

动画角色模型；分割本体；层次分割；泊松方程；支持向量机（SVM）

在动画和游戏等计算机图形学领域，需要通过动画角色模型分割得到不同子部分，才能够对不同子部分的运动特征进行分析.此外，这种分割结果可应用于三维动画建模［1］、多视图重构［2-3］等领域，因此，三维动画角色模型分割引起了研究人员的广泛兴趣.

对于动画角色模型，保证姿态变化下的分割结果一致性是关键问题.图形学领域已有很多研究成果可以借鉴［4-7］.这些研究主要分为2类.一类是采用对姿态变化不敏感的几何特征.测地距离因为在姿态变化下的稳定性已经被广泛应用于模型分割［8］.形状直径函数则是考虑去逼近三维模型的中轴距离，在姿态变化下同样具有稳定性［9］.热核信号不但在姿态变化下具有稳定性，而且提供了从局部到全局的多尺度分析理论框架［10］.另一类则是研究人员提出对模型序列进行共性分割.例如：Lee等［11］通过计算变化梯度来定义姿态变化前、后相邻面片的变化程度，然后通过面片聚类和边界优化完成动画模型分割；Wuhrer等［12］通过计算对偶空间内边的权重值来判断某一帧网格中变化大的部位，然后在对偶空间内完成分割.Marras等［13］提取动态模型不同帧网格的轮廓图像，结合多个姿态下不同视角的图像提取关节部位，根据扩散距离值得到分割结果.Arcila等［14］根据前、后帧模型的几何相似性进行特征匹配，然后采用匹配结果完成一致性分割.类似地，近年来，协同分割工作通过多个模型的形状特征相似性来完成一致性分割［15］.虽然这些研究工作能够提高分割结果的一致性，但是没有考虑分割结果的合理性.为了保证分割结果符合用户的语义感知，研究人员考虑在分割过程中融入语义知识.Xie等［16］提出采用神经网络分类器进行学习，通过分类器理论提高三维模型分割的语义一致性.陈启华等［17］提出采用人体比例和层次特征作为先验知识驱动分割，李琳等［18］对该研究进行了扩展，从而使得分割算法能够适用于三维动画角色模型.

从已有研究来看，对于动画角色模型分割，通过先验知识可以有效地保证分割结果在层次结构上的一致性.但是，已有研究并没有讨论如何构建一个规范的知识结构，用于定义分割所需的各种参数，而这些参数对于分割质量有着非常重要的影响.为此，本文在已有研究基础上，提出构建分割本体，形成适用于动画角色分割的本体知识定义.本文针对动画角色模型提出分割本体这一定义，从而使用户可以对分割的层次结构、形状特征、优化算法、分割边界优化参数进行自定义，得到最优分割效果.在分割边界一致性问题上，针对不同姿态下三维模型的分割边界具有等周长这一特性，提出通过泊松方程进行分割边界优化，从而使得分割边界更为一致.

1 分割本体

为了保证不同姿态下的三维网格模型分割结果的一致性，在分割过程中需要使用不同层次的域知识.这些域知识包括模型的层次结构定义、不同子部分的语义标签、分割算法、边界优化算法以及优化参数设置.通过定义分割本体，形成分割域知识的本体化表示，从而通过规范化的域知识定义解决以下2方面的问题.

1）层次结构一致.不同姿态的模型的几何形状特征具有差异性，因此只采用形状特征控制分割层次，会导致层次结构的不一致性.需要通过一些先验知识来控制层次结果，保证分割结果的一致性.

2）分割边界位置近似一致.对于层次结构一致的分割结果，需要考虑如何保证分割边界的一致性，因为任何一个分割结果都需要采用优化算法来得到光滑边界，对于不同的动画模型序列，通过有效地组织优化算法和配套参数，从而保证特定模型的优化分割边界一致.

根据本体定义，分割本体把域知识分解为层次结构特征和分割所需的形状描述符两部分，如图1所示.这2部分知识之间形成“包括”和“使用”2种关系：“包括”关系用于表示分割中层次结构的继承关系，保证分割过程的层次结构一致性，该知识定义了语义标签的层次继承关系，保证不同姿态下的层次结构一致性；

图1 分割本体概念图Fig.1 Concept map of segmentation ontology

“使用”关系用于分割过程的局部优化，定义分割参数以及形状特征描述符，包括分类器定义、形状特征定义、分割优化时所需的优化参数等，从而完成语义标签识别和分割边界优化，得到最优分割结果.

如图2所示为上述知识结构的分割本体定义以及分割结果，可以发现，分割本体是一个具有扩展性的知识结构.这种结构不仅定义了分割对象采用的语义标签识别方法，还定义了不同的优化方法.与文献［17］的研究方法相似，本文将语义知识作为分割准则.不同点在于：1）本文所定义的分割本体采用统计分类替代文献［17］所采用的人体比例知识，主要考虑到同一个子部分的几何特征具有聚类性，可以通过训练建立几何特征和语义标签之间的映射关系，而很难对这种映射关系采用参数进行量化，这种定义使分割本体更具有一般性；2）针对分割边界优化所需的参数设置问题，本文提出把优化方法和参数定义独立出来，形成域知识，从而能够针对不同模型定义个性化参数，得到最优分割边界.

图2 分割本体驱动的人体角色模型分割Fig.2 Human role models segment driven by segmentation ontology

2 语义本体驱动的动画角色模型层次分割

在上述分割本体定义下，采用如下几个步骤完成对任意一个模型的分割：1）提取外部特征点，根据本体知识得到第一层粗分割；2）采用支持向量机识别出不同子部分的语义标签；3）根据语义标签和外部特征点得到输入模型的层次结构；4）根据分割本体所定义的优化参数对分割边界进行优化.

2.1 第一层粗分割

考虑到结构特征非常明显的动画角色模型，其外部结构点的测地距离之和具有极值特性，因此，通过突出度函数能够很好地检测外部结构点，而这些稳定特征点可以用来驱动第一层粗分割.突出度函数是测地距离沿着三维模型表面的积分［19］，定义为

式中：pi、pj为模型顶点，i、j为模型顶点的索引序号，g（ pi，pj）为2点间的测地距离，N为三维模型表面顶点的个数.对于网格上的顶点，如果其突出度函数值大于相邻顶点ψi，则表明这是一个外部特征点.求得一系列局部最值点li，局部特征点的集合为L，定义如下：

式中：NL为局部最值点的个数，V为模型顶点集合.突出度函数是一个对测地距离非常敏感的特征点检测函数，因此会导致过检测（很多局部突出点也被检测出来，如图3所示）.在这里，需要结合分割本体中所定义的子部分数目，采用K-均值聚类，得到NE－1个聚类集合（中心点集合不具有突出点，NE为模型外部特征点个数）.对于每个区域中出现多个局部的情况，选取该区域内突出度函数值最大的顶点lm作为聚类初始点，同时外部特征点定义为

图3 马头部多个局部特征点Fig.3 Multiple local feature points on horse's head

式中：ei为检测到的外部特征点.至此，模型外部特征点的集合定义为E＝｛ei∈V，0＜i＜NE｝.

由于每个外部特征点代表了模型的一个子部分，通过区域增长把这部特征点分割成不同的子部分.突出度函数的值越小，该顶点属于模型刚体部分的概率越大.因此，先根据模型顶点的突出度函数值构造优先队列，再进行顶点扩展，直到所有的凸出子部分被划分成一系列互不连通的区域，第一层粗分割完成.在算法实现［8］上，为了避免多维定标提取刚体部分的高复杂度，首先构造外部特征点之间的测地路径，然后在测地路径上进行顶点跟踪，直到提取出来的刚体区域已有效地分离出不同子部分，算法结束.

2.2 语义标签识别

采用形状直径函数（shape diameter function，SDF）定义每个子部分的局部几何特征.形状直径函数在每个面的中点处构造一个圆锥，然后从中点出发，向该圆锥内发射光线，通过光线与内向量的夹角和一定的标准差筛选光线，最后对一系列的目标光线求加权平均值d，将该值的集合记为D.这种计算方式使得形状直径函数在姿态变化、旋转等变换下保持稳定的值.形状直径函数是用射线的距离特征，不具有尺度不变性，因此，采用下式求得面fi的SDF归一化值［20］为

式中：∂为标准化参数，对数变换使较小SDF归一化值变大，能最大限度地保留一些细节特征［20］.通过实验分析，设置∂＝4.对特征点ei所在的子部分，结合SDF归一化形状特征值，可构造直方图特征向量：

式中：元素μj为SDF特征值落入区间（j－（ ）1／t，j／t］（t为［0，1.0］的等分个数）的个数.为了进一步说明SDF直方图的类内聚类性和类间可分性，如图4所示为人体手臂子部分和腿部的直方图分布.可以发现，在图4（a）～（c）中，人体手臂具有明显的变化，但是其构造的SDF直方图基本上保持稳定，具有很好的类内聚类性，主要是因为SDF特征是模型局部区域直径的逼近，在姿态改变下具有稳定性.对于图4（d）所示的另一个子部分腿部，得到的SDF直方图和手臂具有明显的差异性，保证分类器能够准确区分出人体不同子部分的语义标签.

图4 SDF直方图的类内聚类性和类间可分性Fig.4 Clustering in one class and divisibility between classes shown by SDF histogram

根据模型子部分的局部直方图，采用支持向量机识别出所对应的语义标签，根据语义标签驱动下一层分割.（yi，Fi） 表示直方图特征向量Fi的语义标签为yi.定义二值分类器为

式中：K为核函数，b为截距，n为支持向量的个数，t为对应于每一个支持向量的索引号，其中αt为拉格朗日乘子，Ft为支持向量，yt为语义标签.ℓ只是一个二值分类器，而语义标签识别是一个多值分类器问题，因此，在式（6）的基础上，通过两两组合形成多值分类器：

式中：ym表示投票次数最多的标签，VT表示属于标签yi的投票数.首先对SDF特征向量采用二值分类器得到判决结果，然后按照投票数最多原则识别最终的语义标签.

2.3 等周长边界分割优化

上述过程通过本体知识得到了层次结构分割结果，但是存在一个主要问题：分割边界粗糙不光滑，需要进行优化［16，21-22］.本文根据角色模型在姿态变化下的等周长特性，采用泊松方程定义优化算法.泊松方程所采用的等值线理论可以有效地避免局部曲率噪声对分割边界的影响，而分割本体所定义的优化参数可以求解最优边界.如图5（a）、（d）所示为手臂分割边界优化前、后的结果比较.

图5 等周长边界分割优化流程Fig.5 Flowchart of equal-perimeter boundary refinement

1）模糊区域提取.模糊区域采用某一特定部位的特征点eg和边界顶点进行定义，最远点定义为

式中：BR为eg所在的局部区域顶点集合.对于给定阈值参数Tr，可以得到模糊区域，如图5（b）所示.模糊区域中的顶点pi需要满足如下条件：

2）等值线提取.模糊区域的顶点集合中，远离eg的上边缘顶点集合为U，靠近eg的下边缘的集合为K，定义泊松方程为

式中：Δ为拉普拉斯算子.边界约束为

通过线性方程求解得到一系列相邻光滑的等值线集合｛I1，…，Ii，…，Iz｝，其中z为分割线条数.

3）最优分割线选择.在等值线提取的基础上，考虑位置信息和形状特征得到最优分割线.形成如下最优决策函数：

式中：exp［－（i－z／2）2／（2τ2）］是位置约束条件，使最优分割线靠近中间位置；第二项是形状特征约束，使最优分割线处于凹区域［23］，即最优分割线周长小于相邻区域的等值线k；ri为等值线Ii的局部半径，ri＝mi／（2π） ，mi为周长；R（ k） 为一个高斯函数，用以惩罚周长比较大的等值线，定义为

3 实验分析和讨论

实验数据采用TOSCA数据库，包括人、马、狮子、半人马等动画角色模型.首先，对用于语义标签的分类器进行参数及性能分析；其次，对算法的稳定性进行验证；最后，与已有类似算法进行对比分析.

3.1 分类器参数选择及性能分析

核函数作用是将线性不可分的向量映射至高维空间，而后在高维空间中构造分类面.本文选用收敛域宽、性能好、参数少的高斯核函数：

核参数σ和误差惩罚参数C对分类器的性能有重要的影响.采用网格搜索算法查找最优参数，如图6所示为分类器在［2－10，210］内逐步学习迭代识别正确率的分布.当（log2C，log2σ）＝ （－ 1，－5） 时，正确率达到100%，通过这种方式，分别对4类模型进行最优参数选取.如表1所示为不同类模型的分类器参数及识别率：

图6 分类器参数和对应的正确率Fig.6 Classifier's parameters and corresponding accuracy

式中：RS、TS分别为正确样本数和测试样本数.在测试集中，只有半人马模型的分类器识别率为92.59%，其他模型均达到了100%，表示识别正确.结果表明：本体可以采用统计分类完成语义标签识别.识别错误的原因主要是SDF形状对于半人马的腿部和尾巴的类间区分度不够，从而导致部分尾巴识别错误.在后续研究中，需要考虑使用区分度更好的特征，从而使识别精度更高.

3.2 稳定性分析

如图7所示为不同姿态下的各类动画角色模型分割结果，相同的灰度程度代表相同的语义标签.可以发现，这些角色模型在运动过程中所产生的姿态差异非常明显（例如：图7（h）、（i）），但分割结果一致，这是由于一方面形状直径函数具有姿态稳定性，以及直方图表示对局部变化的不敏感性，使支持向量机能够正确地识别出语义标签.另一方面，在姿态变化过程中关节周长基本保持不变，本文算法在边界优化上采用等周长特征，从而使得分割边界上也具有较好的一致性.

表1 不同类模型的分类器参数及识别率Tab.1 Classifier's parameters and recognition rates of different kinds of meshes

图7 动画角色模型的一致性分割结果Fig.7 Consistent segmentation results of animation role models

3.3 分割一致性比较分析

为进一步验证算法性能，对本文方法和文献［17］方法进行分割质量比较.分割质量的好坏主要取决于2个方面：1）分割结果在语义结构上是否具有全局一致性；2）模型序列的分割边界是否一致.设第x帧模型分割结果为

式中：Fx为面索引，Cx为每个面片所对应的分割索引.定义分割序列一致性相似度YF为（假设2个模型有相同的点面数，而且任意2帧模型的子部位的点面索引也相同）：

式中：Cx－Cy表示2个模型分割结果的差异性，GT用于统计元素个数.通过式（17）可以很好地度量出2个模型之间的分割一致性.YF值越大，表明两者的分割一致性越高.将M帧的模型与参考分割结果Sf计算相似度，并将M个相似度的均值作为该类模型的一致性评价指标ξ：

如表2所示为采用不同模型和参考模型得到的一致性分割结果.可以发现，文献［17］只是采用面片之间的法向夹角作为优化约束条件，因此，很难保证分割边界收敛到关节位置.本文方法采用等周长线提取，分割边界不仅非常平滑，而且具有更好的一致性.另外，文献［17］采用人体比例作为语义知识用于语义标签识别，这种方法具有很大的局限性，只能适用于人体模型.本文方法构建语义标签识别器，只需要更新训练数据就可以得到不同模型的层次一致性分割.综上，本文方法具有更好的普遍性和适用性.

图8 3种不同算法得到的人体分割结果比较Fig.8 Comparison of human segmentation results by three different algorithms

如图8所示为采用文献［17］、［20］所述方法得到的分割结果比较，其中文献［20］直接采用SDF特征进行聚类分析.可以发现，SDF特征具有很好的聚类性，对于不同姿态的角色模型有类似的分割结果.但是这种分割并不符合语义结构，如图8（c）所示.文献［17］的方法能够正确地识别人体语义结构特征，但是该算法采用人体比例作为域知识，不具有一般性.另外，文献［17］的方法虽然也能够得到比较光滑的边界，但是其收敛位置明显不一致，例如：对于人体模型腿部的第二层分割，该方法主要是采用三角形夹角作为约束条件，导致收敛边界不一致.本文方法基本上收敛到膝盖位置，这是因为本文的分割边界采用周长作为收敛条件，能够得到比较一致的结果，如表2所示.

表2 一致性评价指标的计算结果Tab.2 Calculation of consistency evaluation index%

4 结 语

通过实验可以发现，通过本体选择最优参数可以明显地提高分割质量.本文研究存在的主要不足是：所提出的算法无法稳定、可靠地适用于遮挡严重的动画角色模型，并且分割边界需要进一步优化.需要在以下2个方面进一步研究.

1）遮挡情况下的三维动态数据一致性分割.对于局部遮挡的三维数据，会存在数据丢失.在这种情况下，无论是局部特征还是子部分结构都有可能发生明显的变化，因此，对于这类数据，需要在已有研究基础上，提出更为稳定的局部特征，用于语义子标签识别，并定义拒取率，用于移除不稳定子部分.

2）协同边界优化.对于边界一致性，虽然采用等周长能得到更好的一致性分割结果，但是本文方法并没有考虑采用模型之间的相关性特征.在后续研究中，可以考虑针对多个模型定义协同边界优化算法，从而通过聚类分析得到更为一致的分割边界.

（References）：

［1］JAMES D L，TWIGG C D.Skinning mesh animations［J］.ACM Transactions on Graphics，2005，24（3）：399- 407.

［2］VLASTIC D，BARAN I，MATUSIK W，et al.Articulated mesh animation from multi-view silhouettes［J］.ACM Transactions on Graphics，2008，27（3）：97.

［3］XU F，LIU Y B，STOLL C，et al.Video-based characters-creating new human performances from a multi-view video database［J］.ACM Transactions on Graphics，2011，30（4）：76- 79.

［4］孙晓鹏，李华.三维网格模型的分割及应用技术综述［J］.计算机辅助设计与图形学学报，2005，17（8）：1647- 1655.

SUN Xiao-peng，LI Hua.A survey of 3D mesh model segmentation and application［J］.Journal of Computer-Aided Design and Computer Graphics，2005，17（8）：1647 -1655.

［5］ATTENE M，KATZ S，MORTARA M，et al.Mesh segmentation：a comparative study［C］∥Proceedings of the International Conference on Shape Modeling and Applications.Matsushima：IEEE，2006：14- 25.

［6］SHAMIR A.A survey on mesh segmentation techniques［J］.Computer Graphics Forum，2008，27（6）：1539- 1556.

［7］ZHENG Y，TAI C L，AU K C.Dot Scissor：a singleclick interface for mesh segmentation［J］.IEEE Transactions on Visualization and Computer Graphics，2012，18（8）：1304- 1312.

［8］AGATHOS A，PRATIKAKIS I，PERANTONIS S，et al.Protrusion-oriented 3D mesh segmentation［J］.The Visual Computer，2010，26（1）：63- 81.

［9］SHAPIRA L，SHALOM S，SHAMIR A，et al.Contextual part analogies in 3D objects［J］.International Journal of Computer Vision，2010，89（2／3）：309- 326.

［10］SUN J，OVSJANIKOV M，GUIBAS L.A concise and provably informative multi-scale signature based on heat diffusion［J］.Computer Graphics Forum，2009，28（5）：1383- 1392.

［11］LEE T Y，WANG Y S，CHEN T G.Segmenting a deforming mesh into near-rigid components［J］.The Visual Computer，2006，22（9- 11）：729- 739.

［12］WUHRER S，BRUNTON A.Segmenting animated objects into near-rigid components［J］.The Visual Computer，2010，26（2）：147- 155.

［13］MARRAS S，BRONSTEIN M M，HORMANN K，et al.Motion-based mesh segmentation using augmented silhouettes［J］.Graphical Models，2012，74（4）：164- 172.

［14］ARCILA R，CAGNIART C，HÉTROY F，et al.Segmentation of temporal mesh sequences into rigidly moving components［J］.Graphical Models，2013，75（1）：10- 22.

［15］HU R Z，FAN L B，LIU L G.Co-segmentation of 3D shapes via subspace clustering［J］.Computer Graphics Forum，2012，31（5）：1703- 1713.

［16］XIE Z G，XU K，LIU L G，et al.3D shape segmentation and labeling via extreme learning machine［J］.Computer Graphics Forum，2014，33（5）：85- 95.

［17］陈启华，潘翔，张三元.语义知识约束的三维人体特征点检测和分割［J］.计算机辅助设计与图形学学报，2011，23（6）：1061- 1068.

CHEN Qi-hua，PAN Xiang，ZHANG San-yuan.3D human landmark detection and segmentation with semantic knowledge［J］.Journal of Computer-Aided Design and Computer Graphics，2011，23（6）：1061- 1068.

［18］李琳，陶涛，刘晓平.层次结构导向下的动画角色模型分割与标记［J］.中国图象图形学报，2014，19（6）：955- 963.

LI Lin，TAO Tao，LIU Xiao-ping.Animation character model segmentation and labeling approach under the guidance of hierarchical structures［J］.Journal of Image and Graphics，2014，19（6）：955- 963.

［19］AGATHOS A，PRATIKAKIS I，PERANTONIS S，et al.3D mesh segmentation methodologies for CAD applications［J］.Computer-Aided Design and Applications，2007，4（6）：827- 841.

［20］SHAPIRA L，SHAMIR A，COHEN-OR D.Consistent mesh partitioning and skeletonisation using the shape diameter function［J］.The Visual Computer，2008，24（4）：249- 259.

［21］GHOSH M，AMATO N M，LU Y，et al.Fast approximate convex decomposition using relative concavity［J］.Computer-Aided Design，2013，45（2）：494- 504.

［22］ZHENG Y Y，TAI C L.Mesh decomposition with cross-boundary brushes［J］.Computer Graphics Forum，2010，29（2）：527- 535.

［23］HOFFMAN D D，SINGH M.Salience of visual parts［J］.Cognition，1997，63（1）：29- 78.

Segmentation of animation character model by combining semantic ontology and Poisson equation

PAN Xiang1，TONG Wei-huai1，ZHANG San-yuan2，ZHENG He-rong1
（1.College of Computer Science and Technology，Zhejiang University of Technology，Hangzhou 310023，China；2.College of Computer Science and Technology，Zhejiang University，Hangzhou 310058，China）

A segmentation algorithm was proposed based on semantic ontology to solve the problem that animation character model is inconsistent because of the changing of poses.The segmentation ontology was constructed according to the map between semantic label and geometrical characteristic.In the process of segmentation，the semantic label of segmented parts was recognized using support vector machine（SVM）and geometrical characteristic.In this way，the hierarchical segmentation of dynamic models could be consistent with the help of semantic label.In addition，the length of boundary was almost equal under different poses，therefore，segmenting boundary was refined by Poisson equation.The refined method made the animation character models smooth and consistent.In experiment，the segmenting result of the tested dynamic models show that the proposed algorithm is very stable.Compared with the existing methods，segmentation ontology can select optimizing parameters for different 3D shapes.As a result，the proposed method can achieve boundary of segmenting quality over the exiting methods.

animation character model；segmenting ontology；hierarchical segmentation；Poisson equation；support vector machine（SVM）

10.3785／j.issn.1008-973X.2015.09.004

TP 391

A

1008- 973X（2015）09- 1634- 08

2014- 10- 17. 浙江大学学报（工学版）网址：www.journals.zju.edu.cn／eng

国家自然科学基金资助项目（61272304）；浙江省自然科学基金资助项目（LY15F020024）；浙江省文物局资助项目（2014014）.

潘翔（1977－），男，教授，博导，从事计算机图形学与图像处理技术研究.ORCID：0000-0003-2291-4201.E-mail：panx＠zjut.edu.cn

张三元，男，教授，博导.ORCID：0000-0001-8604-874X.E-mail：syzhang＠cs.zju.edu.cn