一种基于水平集中心聚类的3D角色模型骨架提取方法

摘要

本发明提供一种基于水平集中心聚类的3D角色模型骨架提取方法，包括以下步骤：利用高度函数作为Morse函数对3D角色模型进行切割处理，得到切割后的交点集合；将切割后的交点集合根据交点之间的连通性来进行聚类，聚类成若干子水平集；将面积大于水平集面积阈值且似圆性大于似圆性阈值的水平集筛选出来；将筛选之后的水平集利用水平集的中心进行聚类，从而将水平集分割为3D角色模型的双臂、双腿以及躯干；将得到的骨架线嵌入到3D角色模型中。本发明能够通过自动为三维动画模型进行骨架的提取，骨架提取所采用的水平集聚类方法，相比于传统的距离变换法，通过使用切割模型，划分模型部位，分别计算各部分关节等方法，其平均所消耗的时间更少，误差更小。

说明书

技术领域

本发明属于三维动画制作技术领域，特别涉及一种基于水平集中心聚类的3D角色 模型骨架提取方法。

背景技术

随着虚拟现实技术以及数字媒体技术的发展，人们对于三维角色模型动画的制作 的需求也越来越多，作为多媒体技术的重要组成部分，三维动画制作的技术在近年来得到 了很大的发展，但是在目前的主流的三维角色制作过程当中仍然以手工制作为主，主要采 用3DMax或者是Maya等商业软件进行设计和制作，但是现阶段的动画创作产业仍面临着缺 少合适的计算机动画制作相关方面知识和经验的优秀的人才资源等问题，因此在当今的三 维动画的制作过程中仍然需要一定的劳动力以及花费大量的脑力。人们现在使用较为广泛 的计算机动画技术有关键帧以及动力学方法等。但是，这些方法都有共同的一个缺陷：制作 耗时耗力，同时需要制作者具备较高程度的制作技巧和专业知识。

随着更多人对于三维角色动画制作出现需求，需要一种简便的方式来进行三维动 画的制作，以让更多缺少三维人物动画制作经验的人参与到这项工作中来，例如用户自己 选择模型，动作等，之后由程序自动生成合适的动画。因此自动进行三维人物动画制作技术 已成为科研工作者或者工程师们的研究热点。这样不仅省时省力，还能让更多人参与到动 画制作中。在这个背景下对运动重定向技术中模型的骨架提取进行简化和自动化，成为了 角色动画领域中非常关键的一环。

发明内容

本发明的目的在于提供一种基于水平集中心聚类的3D角色模型骨架提取方法。

本发明的技术方案是：

一种基于水平集中心聚类的3D角色模型骨架提取方法，包括以下步骤：

步骤1：利用高度函数作为Morse函数对3D角色模型进行切割处理，得到切割后的 交点集合；

步骤2：将切割后的交点集合根据交点之间的连通性来进行聚类，聚类成若干子水 平集：如果某两个交点为高度平面与一个三角网格面相交形成的，则将这两个交点保存成 一个线段，利用线段之间的连接性来进行聚类，得到若干子水平集；

步骤3：将水平集的面积和似圆性作为筛选条件，将面积大于水平集面积阈值且似 圆性大于似圆性阈值的水平集筛选出来；

步骤4：将筛选之后的水平集利用水平集的中心进行聚类，从而将水平集分割为3D 角色模型的双臂、双腿以及躯干；

步骤5：将得到的骨架线嵌入到3D角色模型中。

所述步骤1的具体步骤如下：

步骤1-1：选取高度函数对3D角色模型进行处理得到3D角色模型高度h_model；

步骤1-2：设定3D角色模型切割次数n，从3D角色模型的最上方开始进行切割，每隔 h_model/n距离取一个平面即高度平面；

步骤1-3：读取FBX文件中的三角网格面，将每一个三角网格面在y轴方向的最大值 y_max和最小值y_min保存到数组中，对各三角网格面在y轴方向的最大值y_max进行排序；

步骤1-4：计算3D角色模型的每一个高度平面与三角网格面的交点，得到各高度平 面能够相交的三角网格面列表；

步骤1-5：根据各高度平面能够相交的三角网格面列表，确定各高度平面与其能够 相交的三角网格面之间的交点，即切割后的交点集合。

所述步骤1-4的具体步骤如下：

步骤1-4-1：遍历数组中的每一个三角网格面，如果当前三角网格面的在y轴方向 的最大值y_max大于当前高度平面P_current，则执行步骤1-4-2，否则从当前三角网格面之后的 所有三角网格面都不再与当前高度平面P_current相交，停止遍历，得到的三角网格面列表为 能够与当前高度平面P_current相交的三角网格面列表；

步骤1-4-2：判断当前三角网格面的在y轴方向的最小值y_min是否大于当前高度平 面P_current：是，则当前三角网格面在当前高度平面P_current之上，遍历下一个三角网格面，返回 步骤1-4-1；否则当前三角网格面与当前高度平面P_current能够相交，保存当前三角网格面， 遍历下一个三角网格面，返回步骤1-4-1。

所述步骤3的具体步骤如下：

步骤3-1：设定筛选条件，包括水平集面积阈值和似圆性阈值；

步骤3-2：计算每一个水平集的面积和似圆性；

步骤3-3：将面积大于水平集面积阈值且似圆性大于似圆性阈值的水平集筛选出 来。

所述步骤4的具体步骤如下：

步骤4-1：计算每一个水平集的中心点，形成中心点集；

步骤4-2：对所有中心点按照三维空间中除高度外的另两个方向的轴向长度值进 行排序，轴向长度值最大的方向即3D角色模型的双臂伸展方向；

步骤4-3：计算排序后的中心点集的前5个中心点的相邻中心点间距离的平均值、 后5个中心点的相邻中心点间距离的平均值，分别将这两个平均值的2倍作为两个聚类半 径；

步骤4-4：分别选取排序后的中心点集的第一个中心点、最后一个中心点作为起始 点进行聚类，得到3D角色模型的双臂的水平集；

步骤4-5：对所有中心点按纵轴方向由小到大进行排序，找到双腿的端点值，进行 与步骤4-4相同的聚类，得到3D角色模型的双腿的水平集；

步骤4-6：将中心点集中没被聚类的中心点作为3D角色模型的躯干的水平集的中 心点；

步骤4-7：计算3D角色模型的双臂的水平集的中心点的拟合直线、双腿的水平集的 中心点的拟合直线、躯干的水平集的中心点的拟合直线分别作为双臂的骨架线、双腿的骨 架线、躯干的骨架线。

所述步骤5的具体步骤如下：

步骤5-1：计算关键关节点的位置；

关键关节点包括：头部、颈部、肩关节、肘关节、腕关节、手部、髋关节、大腿关节、踝 关节以及脚部；

步骤5-2：利用关键关节点的位置与标准骨架结构之间进行匹配，通过关节点之间 的位置比例求出其余所有关节点的位置；

步骤5-3：连接所有语义上相关联的关节点得到最终的骨架，嵌入到3D角色模型 中。

所述步骤5-1的具体步骤如下：

步骤5-1-1：由切割后的3D角色模型每一部分的骨架线的末端求得头部、手部、髋 关节、大腿关节以及脚部关节点的位置：腿部骨架线两个末端是大腿关节和脚部；手臂骨架 线下部末端是手部；躯干骨架线两个末端是头部和髋关节；

步骤5-1-2：利用水平面切割3D角色模型的双臂部分的三角网格面得到的水平集 的周长，确定腕关节的位置；

步骤5-1-3：计算颈部关节点的位置：利用步骤5-1-2的方法处理手臂以上的躯干 位置的网格模型的水平集，将周长最小的水平集的中点作为颈部关节点的位置；

步骤5-1-4：计算肩关节的位置：利用双臂的骨架线的方向与肩关节所在平面相交 得到一个初始肩关节位置再进行修正；

步骤5-1-5：计算踝关节的位置：首先选取步骤3筛选出的水平集中腿部对应的水 平集，然后计算所选取的各相邻水平集的中点连接线间夹角，不小于设定阈值的夹角位置 即踝关节位置。

所述步骤5-1-2的具体步骤如下：

步骤5-1-2-1：利用双臂的骨架线的方向与纵轴正方向的夹角计算出一个旋转矩 阵；

旋转矩阵表示如下：

$M=\left(\begin{array}{ccc}{n}_x^2(1-\cos \theta )+\cos \theta & n_x{n}_y(1-\cos \theta )+n_z\sin \theta & n_x{n}_z(1-\cos \theta )-n_y\sin \theta \\ n_x{n}_y(1-\cos \theta )-n_z\sin \theta & n_y^2(1-\cos \theta )+\cos \theta & n_y{n}_z(1-\cos \theta )-n_z\sin \theta \\ n_x{n}_z(1-\cos \theta )+n_y\sin \theta & n_y{n}_z(1-\cos \theta )-n_x\sin \theta & n_z^2(1-\cos \theta )+\cos \theta \end{array}\right)$

其中，θ为双臂的骨架线的方向与纵轴正方向的夹角，(n_x,n_y,n_z)为旋转轴，利用双 臂的骨架线与纵轴正方向叉乘求得；

步骤5-1-2-2：将双臂网格模型乘以该旋转矩阵，将双臂网格模型直立；

步骤5-1-2-3：利用水平面对双臂网格模型进行横切操作，利用步骤2的方法得到 一系列水平集；

步骤5-1-2-4：如果某一个高度平面下有多个水平集，则将所有水平集的顶点视为 一个点集，利用Graham算法计算该点集的凸包，用该凸包作为该高度平面下的唯一水平集；

步骤5-1-2-5：计算每一个水平集的周长，将周长最小的水平集的中点作为手腕关 节点的位置。

所述步骤5-1-4的具体步骤如下：

步骤5-1-4-1：利用双臂的骨架线纵轴值最大的点确定的平面以及颈部关节点纵 轴值确定的平面的中间平面，得到肩关节所处平面；

步骤5-1-4-2：利用双臂的骨架线的方向与肩关节所在的平面相交得到一个交点， 该交点为肩关节的位置；

步骤5-1-4-3：利用肩关节的位置以及手腕关节点的位置，通过标准骨架结构中肘 关节与肩关节、手腕关节点的位置比例得到肘关节的初始位置；

步骤5-1-4-4：将位于肘关节纵轴值确定的平面以上的点作为上臂部分，将上臂部 分的中心点重新进行直线拟合，令该直线与肩关节所在平面相交得到修正的肩关节位置， 重复执行5-1-4-3直至肩关节的位置不再发生变化，此时得到的肩关节点为最终的肩关节 位置。

有益效果：

本发明能够通过自动为三维动画模型进行骨架的提取，骨架提取所采用的水平集 聚类方法，相比于传统的距离变换法，通过使用切割模型，划分模型部位，分别计算各部分 关节等方法，其平均所消耗的时间更少，误差更小。通过本方法来代替传统手工进行计算， 能够使用户门槛降低，方便使用，提高骨架提取的精度和效率。

附图说明

图1为本发明具体实施方式的对水平集中心点进行聚类的方法的示意图；

图2为本发明具体实施方式将切割后的交点集合根据交点之间的连通性来进行聚 类的流程图；

图3为本发明具体实施方式对水平集中心点进行聚类的流程图；

图4(a)～(d)分别为本发明具体实施方式中对本方法与现有技术的距离变换方法 对比所采用的四个模型；

图5(a)～(h)为本发明具体实施方式中本方法与现有技术的距离变换方法对比实 验结果图；

图6为本发明具体实施方式基于水平集中心聚类的3D角色模型骨架提取方法流程 图；

图7为本发明具体实施方式步骤1的具体流程图；

图8为本发明具体实施方式步骤1-4的具体流程图；

图9为本发明具体实施方式步骤4的具体流程图；

图10为本发明具体实施方式步骤5的具体流程图；

图11为本发明具体实施方式步骤5-1-2的具体流程图。

具体实施方式

下面结合附图对本发明的具体实施方式做详细说明。

一种基于水平集中心聚类的3D角色模型骨架提取方法，如图6所示，包括以下步 骤：

步骤1：利用高度函数作为Morse函数对3D角色模型进行切割处理，得到切割后的 交点集合；

如图7所示，具体步骤如下：

步骤1-1：选取高度函数对3D角色模型进行处理得到3D角色模型高度h_model；

步骤1-2：设定3D角色模型切割次数n＝80，从3D角色模型的最上方(头顶)开始进 行切割，每隔h_model/n距离取一个平面即高度平面；

步骤1-3：为了提高效率，读取FBX文件中的三角网格面时，将每一个三角网格面在 y轴方向的最大值y_max和最小值y_min保存到数组中，对各三角网格面在y轴方向的最大值y_max进行排序；

步骤1-4：计算3D角色模型的每一个高度平面与三角网格面的交点，得到各高度平 面能够相交的三角网格面列表；

如图8所示，具体步骤如下：

步骤1-4-1：遍历数组中的每一个三角网格面，如果当前三角网格面的在y轴方向 的最大值y_max大于当前高度平面P_current，则执行步骤1-4-2，否则从当前三角网格面之后的 所有三角网格面都不再与当前高度平面P_current相交，停止遍历，得到的三角网格面列表为 能够与当前高度平面P_current相交的三角网格面列表，执行步骤1-5；

步骤1-4-2：判断当前三角网格面的在y轴方向的最小值y_min是否大于当前高度平 面P_current：是，则当前三角网格面在当前高度平面P_current之上，遍历下一个三角网格面，返回 步骤1-4-1；否则当前三角网格面与当前高度平面P_current能够相交，保存当前三角网格面， 遍历下一个三角网格面，返回步骤1-4-1。

高度平面与三角网格面交点有两个交点，计算交点公式如下：

x＝x₁+(P_current-y₁)*(x₂-x₁)÷(y₂-y₁)

z＝z₁+(P_current-y₁)*(z₂-z₁)÷(y₂-y₁)

其中，x与z分别表示三角网格面的一条边与当前高度平面P_current的交点的x与z轴 值，x₁与x₂分别表示该条边的两个端点的x轴值，z₁与z₂表示这该条边的两个端点的z轴值， 交点的y值为当前高度平面P_current的值。

步骤1-5：根据各高度平面能够相交的三角网格面列表，确定各高度平面与其能够 相交的三角网格面之间的交点，即切割后的交点集合。

步骤2：将切割后的交点集合根据交点之间的连通性来进行聚类，聚类成若干子水 平集：如果某两个交点为高度平面与一个三角网格面相交形成的，则将这两个交点保存成 一个线段，利用线段之间的连接性来进行聚类，得到若干子水平集；

图2中描述了将切割后的交点集合根据交点之间的连通性来进行聚类的流程图， 具体的方法流程如下：

步骤2-1：记录当前高度平面P_current与三角网格面相交形成的线段集合L{l₁, l₂,…,l_n}；

步骤2-2：任意取l_k,k∈[1,n]，记录l_k的一个端点为v_start，即为整个遍历过程的起 点，其另一个端点为v_current，即为当前搜索的点，记当前的聚类点集合为E_i，i＝1，将v_start添 加到当前集合当中；

步骤2-3：遍历线段集合L中的其余所有线段，若l_i的其中某一个顶点值 等于v_current，则取l_i的另一个端点为v_current，同时在线段集合L中删除l_i，同时在E_i中添加 v_current，如果此时L为空则进行步骤2-4，如果v_current＝v_start，则跳转到步骤2-2，并将i加1， 如果遍历结束仍未形成闭合曲线，则设v_current为新的v_start，重复执行步骤2-3，遍历到最后 连接曲线的首尾形成一个闭合曲线，并将该曲线保存，如果L为空跳则跳转到步骤2-4，否则 转到步骤2-2；

步骤2-4：得到各闭合曲线对应的交点集合作为各子水平集。

步骤3：将水平集的面积和似圆性作为筛选条件，将面积大于水平集面积阈值且似 圆性大于似圆性阈值的水平集筛选出来；

步骤3-1：设定筛选条件，包括水平集面积阈值和似圆性阈值；

水平集面积阈值T的计算公式如下：

$T={\left[Round\left(\frac{h_{\mathrm{mod}el}}{h_{s\tan dard}}\right)\right]}^2*ST$

其中，h_model为3D角色模型的高度，h_standard为预先设定的标准模型高度，在本实施 方式中取为160，Round()函数为四舍五入函数，ST为标准模型中取得的水平集面积阈值，本 实施方式中取ST＝0.2。

步骤3-2：计算每一个水平集的面积和似圆性；

利用定理“由任意一点与多边形上依次两点连线构成的三角形矢量面积和求得”， 计算每一个水平集的面积，使用如下公式进行计算：

其中，S(P)表示子水平集P组成的多边形的面积，M为任意一点，为点M与子水 平集P中第i个点连接形成的向量，为点M点与子水平集P中的第i+1个交点连接形 成的向量。

水平集的似圆性的计算公式是：

$C\left(P\right)=\frac{4*\pi *S\left(P\right)}{P{\left(P\right)}^2}$

其中，C(P)表示子水平集P组成的多边形的似圆性，S(P)为子水平集P组成的多边 形的面积，P(P)表示子水平集P组成的多边形的周长。

步骤3-3：将面积大于水平集面积阈值且似圆性大于似圆性阈值的水平集筛选出 来。本实施方式中似圆性的阈值根据经验，取为0.4。

步骤4：将筛选之后的水平集利用水平集的中心进行聚类，从而将水平集分割为3D 角色模型的双臂、双腿以及躯干；

如图9所示，具体步骤如下：

步骤4-1：计算每一个水平集的中心点，形成中心点集；

$C=\frac{1}{n}\underset{i=1}{\overset{n}{\Sigma }}{P}_i$

其中C为水平集P的中心点。

步骤4-2：对所有中心点按照三维空间中除高度外的另两个方向的轴向长度值进 行排序，轴向长度值最大的方向即3D角色模型的双臂伸展方向；

步骤4-3：计算排序后的中心点集C_all的前5个中心点的相邻中心点间距离的平均 值、后5个中心点的相邻中心点间距离的平均值，分别将这两个平均值的2倍作为两个聚类 半径；

步骤4-4：分别选取排序后的中心点集C_all的第一个中心点、最后一个中心点作为 起始点进行聚类，得到3D角色模型的双臂的水平集；

图1是描述了对水平集中心点进行聚类的方法的示意图，其中，将起始点T1加入聚 类集合中，判断T2与聚类集合中的元素距离是否在给定聚类半径之内，假如存在至少一个 满足条件的情况，则将T2加入聚类集合中，接下来的元素以此类推。

图3是对水平集中心点进行聚类的具体流程图，具体执行步骤如下：

步骤4-4-1：建立队列Q，将起始点Cstart加入到队列Q当中，并将Cstart标记为已 经处理；

步骤4-4-2：取队列Q的首元素作为当前判定的点Ccurrent，并将Ccurrent添加到 聚类结果集合Cresult中；

步骤4-4-3：遍历中心点集C_all，如果当前被遍历到的中心点距离Ccurrent的距离 小于聚类半径R且未被处理过，则将该中心点加入到队列Q当中，并将该中心点标记为已经 处理；

步骤4-4-4：判定队列Q是否为空，如果不为空则执行步骤4-4-2；否则，执行步骤4- 4-5；

步骤4-4-5：Cresult为最终的聚类结果，即3D角色模型的双臂的水平集；

步骤4-5：对所有中心点按纵轴方向由小到大进行排序，找到双腿的端点值，进行 与步骤4-4相同的聚类，得到3D角色模型的双腿的水平集；

步骤4-6：将中心点集中没被聚类的中心点作为3D角色模型的躯干的水平集的中 心点；

步骤4-7：计算3D角色模型的双臂的水平集的中心点的拟合直线、双腿的水平集的 中心点的拟合直线、躯干的水平集的中心点的拟合直线分别作为双臂的骨架线、双腿的骨 架线、躯干的骨架线。

步骤5：将得到的骨架线嵌入到3D角色模型中。

如图10所示，具体步骤如下：

步骤5-1：计算关键关节点的位置；

关键关节点包括：头部、颈部、肩关节、肘关节、腕关节、手部、髋关节、大腿关节、踝 关节以及脚部；

步骤5-1-1：由切割后的3D角色模型每一部分的骨架线的末端求得头部、手部、髋 关节、大腿关节以及脚部关节点的位置：腿部骨架线两个末端是大腿关节和脚部；手臂骨架 线下部末端是手部；躯干骨架线两个末端是头部和髋关节；

步骤5-1-2：利用水平面切割3D角色模型的双臂部分的三角网格面得到的水平集 的周长，确定腕关节的位置；

如图11所示，具体步骤如下：

步骤5-1-2-1：利用双臂的骨架线的方向与纵轴正方向的夹角计算出一个旋转矩 阵；

旋转矩阵表示如下：

$M=\left(\begin{array}{ccc}{n}_x^2(1-\cos \theta )+\cos \theta & n_x{n}_y(1-\cos \theta )+n_z\sin \theta & n_x{n}_z(1-\cos \theta )-n_y\sin \theta \\ n_x{n}_y(1-\cos \theta )-n_z\sin \theta & n_y^2(1-\cos \theta )+\cos \theta & n_y{n}_z(1-\cos \theta )-n_z\sin \theta \\ n_x{n}_z(1-\cos \theta )+n_y\sin \theta & n_y{n}_z(1-\cos \theta )-n_x\sin \theta & n_z^2(1-\cos \theta )+\cos \theta \end{array}\right)$

其中，θ为双臂的骨架线的方向与纵轴正方向的夹角，(n_x,n_y,n_z)为旋转轴，利用双 臂的骨架线与纵轴正方向叉乘求得；

步骤5-1-2-2：将双臂网格模型乘以该旋转矩阵，将双臂网格模型直立；

步骤5-1-2-3：利用水平面对双臂网格模型进行横切操作，利用步骤2的方法得到 一系列水平集；

步骤5-1-2-4：如果某一个高度平面下有多个水平集，则将所有水平集的顶点视为 一个点集，利用Graham算法计算该点集的凸包，用该凸包作为该高度平面下的唯一水平集；

步骤5-1-2-5：计算每一个水平集的周长，将周长最小的水平集的中点作为手腕关 节点的位置。

步骤5-1-3：计算颈部关节点的位置：利用步骤5-1-2的方法处理手臂以上的躯干 位置的网格模型的水平集，将周长最小的水平集的中点作为颈部关节点的位置；

步骤5-1-4：计算肩关节的位置：利用双臂的骨架线的方向与肩关节所在平面相交 得到一个初始肩关节位置再进行修正；

步骤5-1-4-1：利用双臂的骨架线纵轴值最大的点确定的平面以及颈部关节点纵 轴值确定的平面的中间平面，得到肩关节所处平面；

步骤5-1-4-2：利用双臂的骨架线的方向与肩关节所在的平面相交得到一个交点， 该交点为肩关节的位置；

步骤5-1-4-3：利用肩关节的位置以及手腕关节点的位置，通过标准骨架结构中肘 关节与肩关节、手腕关节点的位置比例得到肘关节的初始位置；

步骤5-1-4-4：将位于肘关节纵轴值确定的平面以上的点作为上臂部分，将上臂部 分的中心点重新进行直线拟合，令该直线与肩关节所在平面相交得到修正的肩关节位置， 重复执行5-1-4-3直至肩关节的位置不再发生变化，此时得到的肩关节点为最终的肩关节 位置。

步骤5-1-5：计算踝关节的位置：首先选取步骤3筛选出的水平集中腿部对应的水 平集，然后计算所选取的各相邻水平集的中点连接线间夹角，不小于设定阈值70度的夹角 位置即踝关节位置。

步骤5-2：利用关键关节点的位置与标准骨架结构之间进行匹配，通过关节点之间 的位置比例求出其余所有关节点的位置；

步骤5-3：连接所有语义上相关联的关节点得到最终的骨架，嵌入到3D角色模型 中。

利用本方法与现有技术的距离变换方法进行对比，针对于图4(a)～(d)中的四个 模型进行比较，两种方法获得的骨架如图5所示。其中图5(a)(c)(e)(g)中为距离变换方法 获得的骨架，图5(b)(d)(f)(h)中为本方法获得的骨架。分别比较计这两种方法的时间效率 以及精确度两种参数，表1中展示了两种方法的时间比较，表2中展示了两种方法针对于臂 长的误差的比较，表3中展示了两种方法针对于腿长的误差比较。

表1两种方法的时间比较

表2两种方法针对于臂长的误差的比较

表3两种方法针对于腿长的误差比较

通过对比可以看出，本发明方法针对于距离变换的方法在时间效率以及精确度上 都有一定的优势。