3维模型的分割问题是数字几何处理领域的一个基础性问题，它是通过一定的分割准则将模型分割为若干个各自连通且相互独立的子面片或者部件的过程^[1]。原始的3维模型缺少足够的结构特征和语义信息，对其进行分割有助于模型的后续分析、处理和应用，如模型的参数化、检索和识别等。尽管3维模型分割问题在近些年来一直是一个非常活跃的研究领域，但在已有3维模型分割的研究中，过多的人为设定的参数值抑制了3维模型自动一致性分割的发展。已有的基于知识驱动的3维模型分割方法可分为两类：基于体积信息的分割和基于模型表面信息的分割。基于体积信息的分割利用曲面所围成的空间信息进行3维模型的分割。Shapir等人^[2]提出用于描述模型上每个顶点的直径的形状直径函数(shape diameter function)，并以此完成模型的分割和骨骼提取；文献[3]在获取模型骨骼后，借助模型上顶点与骨骼距离的体半径进行模型的分割。基于模型表面信息的分割利用模型表面的曲率、法向量夹角等信息进行3维模型的分割。文献[4]借助应用于图像分割领域的分水岭算法对模型的曲率信息进行处理，完成了模型的分割，但这种方法在曲率变化平缓的过渡区域容易产生误合并。为了解决分水岭算法中过渡区域误合并的问题，文献[5]将曲面片的合并分为两步进行。首先，计算相邻的两个曲面片的平坦度信号值的差值与两者中信号值较大的一方的比值，然后将比值小于给定值的相邻曲面片优先合并。经过此次合并后，属于不同部分的曲面片的信号值差异将增大，再根据信号值接近原则对剩余曲面片进行合并，得到模型的分割结果。

k-means是一种在多种领域得到广泛应用的经典聚类算法，其理论简单，收敛迅速，很多分割算法都以此为基础。Liu等人^[6]提出的谱聚类分割算法在建立亲和度矩阵后，通过特征值和特征向量构建新的对称矩阵，并在此基础上进行k-means聚类以获得最终的分割结果。Golovinskiy等人^[7]提出了一致性分割的概念，在对模型进行分割的同时，建立起分割部件的对应关系。该方法首先通过刚性对准建立模型间曲面片的对应关系，然后根据模型间曲面片的对应关系和模型内曲面片的邻接关系建立图，并以此进行聚类来获得一致性分割结果。但是基于均方根距离的刚性对准无法有效地处理非刚体变换的模型。近些年随着3维扫描、建模技术的发展，出现了基于数据驱动的分割算法。文献[8]通过对人工分割的模型的边界进行学习，得到模型的边界函数，并以此获得未分割模型的边界，从而实现模型的分割。文献[9]将3维模型的曲面片进行聚类，得到一个初始的分割结果，然后根据上一次的结果迭代建立一个统计模型，用来描述每个分割部件，并通过多标签优化改善分割结果。文献[10]通过训练后的极限学习机分类器对3维模型进行初始分割，然后通过图割优化获得平滑的分割边界。文献[11]借助深度学习网络从3维模型上曲面片的热核签名、形状直径函数和高斯曲率等低级特征中获得高级特征空间，然后在高级特征空间内，使用高斯混合模型定义每个曲面片属于不同分割部件的概率，最后使用图割算法实现了非监督的基于数据的3维模型的分割。然而，此类方法复杂度高，所需训练样本数量大，训练时间长，其通用性较差。

综上所述，已有的3维模型分割方法人为设定参数过多，鲁棒性不高。为此，本文提出了一种基于拓扑持续性、热核签名和热亲和度矩阵的非刚体3维模型的分割方法。与已有算法相比，本文算法的主要贡献和创新点有：1)将拓扑持续性引入显著特征点的选取过程。在给定分割部件数的前提下，使显著特征点的选取可以自动完成，并且显著特征点的选取算法不受模型姿态的影响，对模型表面噪声具有较好的鲁棒性。2)使用反映3维模型两点间热量传递量的热核特征构建一种多尺度、具有等距不变性的热亲和度矩阵，将其用于3维模型的k-means聚类。3)提取同一模型在不同扩散时间参数下分割结果的两次聚类中心的偏移量和边界值，即分割边界所有顶点的热核签名之和，经过多次实验，发现存在两个规律：一是两次聚类中心的偏移量较小时，模型的分割结果较为优良；二是在模型取得较好分割结果的扩散时间内，边界值先单调下降，后单调上升，形成一个最小值。当边界值取得极小值时，模型的分割边界在视觉上是相对正确的。

为了解决特征点选取过程中需要修改筛选半径来规避迭代不收敛的问题，引入了拓扑持续性^[12]。拓扑持续性使用特定的密度函数 $f$ 获得3维数据 $X$ 的密度后，探查密度峰的突出，并建立密度峰的分层关系。

密度峰的突出定义为密度峰的峰值与一个更高的密度峰连通部分值的差值。更确切地说，对于任意一个函数在空间 $\left({X, {\rm{ }}f} \right)$ 上，使用 ${X^\alpha } = {f^{ - 1}}\left({\left[ {\alpha, + \infty } \right)} \right)$ 追溯 $X$ 上的所有点， $\alpha $ 的定义域为 $f$ 的值域。如图 1所示，当 $\alpha $ 与 $z$ 所在的密度峰接触时，该密度峰诞生；同理可诞生 $y$ 所在的密度峰。当 $\alpha $ 与两者的连通部分接触时，较小的一方会被吞并，这意味着它的死亡。密度峰的出生值与死亡值的差值定义为它的生存期，生存期可以用来描述密度峰的突出的大小。本文将密度峰的最大值点定义为密度峰的特征点，密度峰的特征点继承了它所在密度峰的拓扑关系。随着 $\alpha $ 值的不断减小，最终所有的密度峰将会被合并成一个密度峰，同时可建立起密度峰的分层关系。相应地，密度峰的特征点也分层地建立起与其他点的联系。

最初被定义在莫尔斯理论的密度峰的突出是一种比绝对高度稳定的度量^[13]。因为当密度值较高时，如果出现一个小的突起在绝对高度上会引起很大的波动，但是在密度峰的突出上这个波动将会很微小。

Sun等人^[14]提出了基于Laplace-Beltrami算子的多尺度特征描述符，即热核签名(HKS)。它描述了曲面上一点作为热源，在时间的推移中，曲面上的热量逐渐达到热平衡的过程。

给定一个拥有狄利克雷边界的紧致黎曼流形 $M$ ，则 $M$ 上的热扩散过程可表示为

$ {\Delta _M}\mu \left( {x,t} \right) = \frac{{ - \partial \mu \left( {x,t} \right)}}{{\partial t}} $

(1)

式中， ${\Delta _M}$ 是 $M$ 的Laplace-Beltrami算子， ${\mu \left({x, t} \right)}$ 表示 $M$ 上的点 $x$ 在 $t$ 时刻的热量分布。给定一个初始的热量分布函数 $f:M \to R$ ， ${H_t}\left(f \right)$ 表示在时间t的热量分布。存在一个最小函数 ${k_t}\left({x, y} \right)$ ，满足 ${H_t}f\left(x \right) = \int_M {{k_t}\left({x, y} \right)f\left(y \right){\rm{d}}y} $ 。 ${k_t}\left({x, y} \right)$ 称为热核特征，表示时间 $t$ 内热量从点 $x$ 到点 $y$ 的传输量。

对热核特征方程进行Laplace分解可得

$ {k_t}\left( {x,y} \right) = \sum\limits_{i = 0}^\infty {{{\rm{e}}^{ - {\lambda _i}t}}{\phi _i}\left( x \right){\phi _i}\left( y \right)} $

(2)

式中， ${{\lambda _i}}$ 和 ${{\phi _i}\left(x \right)}$ 分别是Laplace-Beltrami算子的第 $i$ 个特征值和相应的特征函数。

黎曼流形 $M$ 上任意一点 $x$ 的热核签名(HKS)定义为此点上的剩余热量表示为

$ {k_t}\left( {x,x} \right) = \sum\limits_{i = 0}^\infty {{{\rm{e}}^{ - {\lambda _i}t}}{\phi _i}\left( x \right){\phi _i}\left( x \right)} $

(3)

即 ${\rm{HKS}}\left({x, t} \right) = {k_t}\left({x, x} \right)$ 。

热核特征 ${k_t}\left({x, y} \right)$ 和热核签名 ${\rm{HKS}}\left({x, t} \right)$ 具有很多优良的性质，如等距不变性、多尺度性和近等距扰动下的稳定性。此外，热核签名在较小的t时，与高斯曲率紧密相关。

已有的显著特征提取算法，一般使用局部极值点作为特征点，如文献[15]将曲率的局部极值点选取为特征点，文献[16]将热均值签名的极值点选取为特征点，文献[17]将波核签名的极值点选取为特征点，但是这些方法在获得有效的显著特征点时，往往需要给定筛选半径。当自主确定筛选半径时，经常会陷入迭代不收敛。而本文算法在获得模型上每一个顶点的热核签名的基础上，采用拓扑持续性构建3维模型上密度峰的分层关系，同时可获得3维模型上的特征点与其他点的联系。最后，根据拓扑持续性和热核签名，选取模型上生存期最长的几个特征点作为模型上被分割部件的显著特征点，选取模型上热核签名的最小值所对应的顶点作为模型躯干部分的显著特征点。图 2为人体模型的热核签名和提取的显著特征点。由图 2(a)可以看出人体的四肢和头部能量值较高，而躯干处的能量值较低，所以，选取语义部件热核签名的极大值点为被分割部件的显著特征点，选取语义部件热核签名的极小值点为躯干部分的显著特征点。图 2(b)为人体模型的显著特征点的选取结果，红色的点为显著特征点。显著特征点的选取过程如算法1所示。

算法1显著特征点选取算法

1) 获取模型顶点信息和面片信息，并给定被分割部件数N；

2) 计算3维模型的余弦Laplacian；

3) 获取余弦Laplacian的前30个最大特征值及其对应的特征函数；

4) 计算每个顶点的热核签名；

5) 热核签名定义为计算拓扑持续性的函数映射；

6) 获取顶点的连接关系；

7) 根据顶点的连接关系和函数映射计算拓扑持续性；

8) 选取生存期最长的 $N$ 个特征点作为被分割部件的显著特征点；

9) 选取热核签名的最小值所对应的顶点作为模型躯干部分的显著特征点；

10)合并被分割部件和躯干部分的显著特征点并返回。

3维模型的分割问题是将模型上相似的顶点聚类为有意义的分割部件。本文算法在k-means聚类的基础上进行模型的分割。由于热核特征描述了模型上两个顶点之间在时间 $t$ 内的热量传递，它在一定程度上反映了模型上两个顶点之间的亲疏关系，所以使用热核特征建立亲和度矩阵，并命名为热亲和度矩阵。本文使用热亲和度矩阵代替k-means聚类中常用的距离度量进行聚类。由于热核特征具有多尺度性，当扩散时间 $t$ 较小时，模型上任意一点的热亲和度主要由该点附近的少量邻接点决定，反映了流形 $M$ 在此点附近的局部特征；当扩散时间增大时，决定热核特征的邻接点的数量也随之增大，最终可以反映流形 $M$ 的全局特征。而测地距离等描述符只能反映流形 $M$ 的全局特征，不具备多尺度性，通过它进行聚类所获得的边界往往在不恰当的位置。从热亲和度矩阵中筛选出最佳的扩散时间所对应的热亲和度矩阵，可以获得较好的分割结果，聚类分割过程如算法2所示。模型的热核特征和相应的分割结果如图 3所示。图 3(a)是位于右手上的显著特征点的热核特征，显著特征点处热量值最高。随着与显著特征点距离的增大，传递到此的热量随之降低。本文方法用热量值的高低定义模型上的顶点与显著特征点的亲疏关系。图 3(b)是所有显著特征点的热核特征的叠加结果，每个顶点显示的热量为所有的显著特征点传递到此的热量的最大值。图 3(c)是在此热量分布对应的热亲和度矩阵下的分割结果。

算法2基于热亲和度矩阵的k-means聚类

1) 获取初始聚类中心Cen (即显著特征点)；

2) 设定 $t$ 值的上、下限： ${t_{\min }}$ 和 ${t_{\max }}$ ；

3) 以 ${t_{\min }}$ 为起始点， ${t_{\max }}$ 为终点，0.001为遍历间隔，并和初始聚类中心Cen以及 $t$ 值对应的热亲和度矩阵HKM进行k-means聚类得到聚类标号Label；

4) 计算分割部件的热核签名，并寻找部件内与其均值最接近的点，将其作为第2次聚类中心，记作Cen’；

5) 计算第2次聚类的边界值；

6) 选取边界值最小时对应的 $t$ 值，并标记为 ${t'}$ ；

7) 使用 ${t'}$ 对应的Cen’及热亲和度矩阵HKM进行k-means聚类得到最终聚类标号Label’；

8) 返回Label’并显示。

实验选择的数据库为Tosca Dataset^[18]和Princeton Mesh Segmentation Benchmark^[19], 主要测试了文中算法的一致性分割效果。实验中，选取了Laplace-Beltrami算子的前30个最大特征值及其对应的特征函数，HKS的扩散时间设置为 $t = 0.01\; {\rm{s}}$ ，HK中的扩散时间 ${t_{\min }} = 0.01\; {\rm{s}}$ ， ${t_{\max }} = 0.04\; {\rm{s}}$ ，这是一个适用于常见非刚性3维模型热核特征描述的经验值。

当3维模型发生弯曲、伸展等非刚性变换时，其几何形状发生了较大变化，需要具有等距不变性的描述符对其进行分析。热核特征和热核签名继承了Laplace-Beltrami算子的等距等容不变性，它们的值与模型的姿态无关。下面的实验验证了本文方法对3维模型姿态变化的鲁棒性。

图 4为不同姿态的人体模型的显著特征点的分布，图中用红色标记点表示。可以看出，在确定分割数目之后，不同姿态的人体模型的每个部件的显著特征点的位置基本一致，显示出本文以具有等距不变性的热核签名为基础的显著特征点的选取算法对姿态变化具有高度鲁棒性。图 5为不同姿态的人体模型的分割结果。可以看出，不同姿态的人体模型的分割边界基本一致。实验结果证明，在获得一致的显著特征点的基础上，由具有等距不变性的热亲和度矩阵进行聚类，可以获得一致性的分割结果。因此，本文方法对3维模型的姿态变化具有高度的鲁棒性。

特征提取是基于k-means聚类的3维模型分割的核心过程。相对于本文的基于Laplace-Beltrami算子的热核特征，测地距离是应用广泛的等距不变描述符，它描述了模型上任意两个顶点之间的最短路径，在计算时需要遍历两点之间的所有路径，并取最短路径，这一遍历过程非常耗时。文献[6]在得到模型上任意两个顶点之间的欧氏距离后，通过幂指数核获取任意两点之间的亲和度的过程也较为繁琐。为进一步验证本文方法的高效性，将热亲和度、测地距离、幂指数核的提取时间进行了对比，实验结果如表 1所示。可以看出，本文所用的热亲和度矩阵的特征提取速度远高于文献[20]所用的测地距离和文献[6]所用的幂指数核。

本文方法进行了两次聚类，第1次由生存期最大的几个特征点和一个热核签名最小值点作为聚类中心，获得初步的分割结果；第2次由热核特征最接近所在部件的平均热核特征值的点作为聚类中心进行聚类，获得更为恰当的分割边界。将两次聚类中心的欧氏距离之和作为一个参考值与分割结果进行对比分析。本文在不同姿态的多个人体模型上进行实验，实验结果表明，当分割结果较好时，参考值较小。扩散时间 $t$ 从0.015 s开始，以0.005 s为间隔取值到0.030 s。所有人体模型上的两次聚类中心的欧氏距离之和的均值分别为1.864 5、16 552、1.727 0、2.063 8。当扩散时间在0.020 s至0.025 s之间时，模型的分割结果较好。提取每次分割结果的分割边界，并计算边界上顶点的热核签名之和，发现存在如下规律：在取得较好的分割结果的扩散时间内，随着扩散时间的增大，所有人体模型的热核签名之和先单调递减，后单调递增，形成了一个极小值。表 2给出了其中一个人体模型的边界值的数据，由表 2可以看出，当 $t$ 取0.024 s时，第一次聚类取得最小的边界值；当 $t$ 取0.025 s时，第二次聚类取得最小的边界值。由观察验证，当边界值取得极小值时，模型的分割在视觉上也处于相对正确的边界。

基于模型表面信息的分割容易受到模型表面噪声的影响，为验证本文方法对模型表面噪声的鲁棒性，实验中对模型添加了不同程度的高斯噪声后执行分割算法。图 6(a)—(d)分别是人体模型添加了1%、5%、10%、20%的高斯噪声后的分割结果，可以看出，当添加10%的高斯噪声时，本文方法依旧取得了较为准确的分割边界；当高斯噪声增加到20%时，仍获得了相对恰当的分割部件。实验结果证明了使用拓扑持续性处理热核签名后，本文方法对模型表面噪声具有极高的鲁棒性。

图 7给出了一些常见四足兽模型的分割结果。可以看出，这些模型的分割结果较为准确，说明本文基于拓扑持续性的显著特征点选取算法对常见的动物模型的分割具有非常好的适用性。在给出分割部件数的前提下，可以准确地找到每个分割部件的显著特征点。

图 8给出了本文算法与文献[21]、基于测地距离^[20]的算法的分割结果对比。可以看出，本文算法可以分割出人体的躯干部分，并获得了比较恰当的分割边界。因为相对于热亲和度，测地距离不具备多尺度性，导致它只能得到一种分割结果，而这种分割结果往往无法获得较为准确的模型分割边界。而文献[21]所使用的持续性聚类只能从热核签名的峰值处展开吞并，无法有效识别热核签名值较低的躯干部分，导致躯干部分被四肢吞并。

本文提出了基于拓扑持续性、热核签名和热亲和度矩阵的3维模型的分割方法。首先使用拓扑持续性和热核签名获得显著特征点作为初始聚类中心，然后使用基于热核特征的热亲和度矩阵进行k-means聚类，最后根据聚类中心的偏移距离等参数筛选分割结果。该方法的优点有：1)使用拓扑持续性处理具有等距不变性的热核签名，提高了其对模型表面噪声和姿态变换的鲁棒性，能够获得稳定的显著特征点，有利于后续k-means聚类；2)热亲和度矩阵提取时间短，具有等距不变性，对不同姿态的模型能够获得一致性的分割结果；3)热亲和度矩阵具有多尺度性，有利于后期筛选出较好的分割结果。

然而，本文方法还存在一些问题，如分割边界有时存在锯齿，需要进一步优化，获得平滑的分割边界；获取特征点时，无法做到语义对应，不利于在此基础之上的模型检索。这些也是今后要继续研究的问题。