利用改进的热核特征分析三维网格的局部对应

杨 熙 黄健民(广西师范大学计算机科学与信息工程学院 广西 桂林 541004) (广西师范大学虚拟现实重点实验室 广西 桂林 541001)

0 引 言

在计算机图形学和几何处理中，形状对应是最基本的问题之一，随着微软Kinect扫描仪、3D等技术的发展，在许多领域(如分子生物学、机械工程、医学图像分析)中形状对应越来越受到人们的重视，找到内在的三维形状之间的对应关系可应用于三维扫描对齐、纹理映射、形状变形和动画等[1]。

由于形状具有较大的非刚性变形，使得寻找到一种较好的对应具有很大的挑战性，在过去的几十年里，大量的研究学者致力于三维形状的对应关系。早期的形状对应方法侧重于刚性形状，而刚性形状之间的转换可以通过平移、旋转和比例因子等参数来参数化，因此，这些参数可以通过迭代等优化方法进行评估。随着研究的深入，一大批学者开始把目光转移到非刚体的形状对应，与刚性形状对应相比，建立非刚体形状之间的对应关系更具挑战性。其中非刚性的形状匹配可以表述为图匹配问题，即点对点对应，而等距属性是寻找模型间对应关系的一个重要依据[2]。文献[3]通过寻找测地属性来试图建立对应关系，但对于三维网格模型之间拓扑结构变化比较大的情况下，仍然不能取得让人满意的结果。文献[4]提出了一种新的多维尺度分析算法(Multi-dimensional scale，MDS)，并将此算法与扩散距离相结合去解决测地距离对于拓扑结构变化较大而不能取得良好效果的问题。虽然结果令人满意，但是该算法效率较低。Ovsjanikov等[5]提出了新的方法去解决三维网格模型的对应问题，即通过拉普拉斯-贝尔特拉米算子嵌入谱空间，以简化对应关系去提高计算的效率，但嵌入对应对于顶点数目比较多的模型会存在一定的误差，不能达到精确的对应。为了解决形状对应所存在的一系列问题，Sun等[6]提出了新的等距属性，即热核特征描述符(Heatkernel signatures，HKS)，它能够赋予模型顶点一个特定的函数值，以覆盖模型的整体，通过匹配对应源模型与目标模型之间不同部位的函数值以达到对应匹配关系。但热核特征对于模型的尺度变化比较敏感，具有不稳定性。Aubry等[7]根据热核特征也提出了一个相似的波核特征(Wave kernel signatures，WKS)，波核特征反映了三维网格模型上不同顶点作为量子能量的分布情况，每个顶点的波核特征对应着这个量子的剩余能量以及量子对应的能量等级，是对热核特征的一种局部的补偿。文献[8]首次提出了函数映射(Functional maps，FM)理论，通过分别将源模型与目标模型映射到谱空间去寻找真实的对应关系，虽然能够得到比较精准的对应关系，但却解决不了模型自身的对称性问题。文献[9]提出了一种网格压缩流形模式，可以压缩模型的整体特征以获得局部的支持，并且具有很好的噪声干扰及对不同的拓扑结构很好的鲁棒性，但是不能满足精确的插值约束。随后Houston等[10]提出了一种快速计算与自然排序的算法，通过对模态的改进，加快了模型的压缩速度。文献[11]通过改进函数映射理论，来重新计算三维网格模型的对应关系，减少了点到点对应关系的等距误差。文献[12]介绍了一种新的基于神经网络方法的密集形状对应，通过将对应关系的计算直接作为学习过程的一部分，以达到端到端的培训并返回匹配结果。

为了有效解决同一种经过非刚体变换模型之间的对应问题，本文通过对参考文献[6,9-10]的研究，将压缩流形模式应用到非刚体模型变换之间，并且取得了非常好的对应局部压缩部位，从而能够根据压缩特征函数设置不同的阈值，得到不同的压缩部位，取得确定的压缩局部顶点数量与位置，从而进行下一步的局部对应匹配。在局部对应匹配中，本文将离散化的压缩流形基替换传统的离散化拉普拉斯算子以改进热核特征，改进之后的热核特征与原来的相比在局部对应上有更加明显的效果。本文贡献如下：(1) 将压缩流形模式应用到新的领域以解决非刚体模型之间的形状对应问题；(2) 解决了非刚体三维网格模型之间的局部特征提取问题；(3) 对热核特征进行了改进，改进之后的效果明显优于之前。

1 拉普拉斯算子

拉普拉斯算子被定义为梯度(▽f)的散度(▽·f)，是一个二阶微分算子。在n维欧几里得空间中，拉普拉斯算子也可以推广为定义在黎曼流形上的椭圆型算子，称为Laplace-Beltrami算子。

Laplace-Beltrami算子[13]是拉普拉斯算子从平面空间到黎曼流形的一般化，在计算机图形学中有着广泛的用途，由于其具有良好的等距不变性，并对三维模型的网格面收敛，因此可以应用到任意的三维模型上[14-15]。

三维网格模型是可以离散化的，根据已有的理论及定义在三维网格模型上的函数，可以得到一个线性的拉普拉斯-贝尔特拉米算子，根据算子可以构建一个算子矩阵。本文在余切权重法的基础之上，又多增加了一个三维网格模型的顶点面积，来构造标准的拉普拉斯-贝尔特拉米算子[16]，即：

L=A-1W

(1)

式中：A是一个对角矩阵,A的对角元素Aii等于与顶点i相邻的三角形面积之和的三分之一。

如图1所示，顶点i的面积等于其周围5个三角形面积之和的三分之一，其中每一个三角形面积的计算方法是根据向量积法求面积，即向量临边构成的三角形面积等于向量临边构成平行四边形面积的一半。

W是一个对称的稀疏矩阵，矩阵W的计算方法一般为余切权重法[13]，i、j分别为三维网格模型的顶点，如图2所示。

其对应的公式如下：

(2)

对得到的Laplace算子矩阵L进行特征分解，即可得到所需要的特征值和特征向量。

2 热核特征

热核特征描述符，又称为HKS描述符，是用于非刚体网格模型形状分析的特征描述子，属于谱形状分析方法。对于三维网格模型形状上的每个点，HKS定义了它的特征向量用于表示点的局部和全局属性。HKS[6]是基于热核属性提出来的，是基于拉普拉斯-贝尔特拉米算子的形状描述符。通过计算模型上各点的热量分布最大值，来得到模型表面的几何特征[17]。

HKS是基于表面热扩散的概念产生的，给定一个表面初始热量分布为U0(X)。式(3)表示t时间内热量从x点转移到y点所需要的热量。

(3)

式中：Δ是一个拉普拉斯算子所构成的矩阵；u(x,t)是点x在时间t的热分布。

热核对等距变化是不变的，而且对小的扰动稳定。另外，热核能完全等距表征一个形状，并且随着时间t的增加，就越能表示形状的全局属性。因为ht(x,y)为一个时间域内的一对点(x,y)的定义，需要计算两两之间的数据，因此使用热核直接作为特征将导致较高的复杂度。而HKS只考虑ht(x,y)，将其自身限制在时间域内，在特定的条件下保留了热核大部分属性。对于黎曼流形M上的热扩散方法如下：

(4)

式(4)的解可以表示为：

(5)

对热核进行特征分解得到：

(6)

式中：λi和Φi是Δ的第i个特征值和特征向量。对于一个简单的特征描述子，HKS将热核限制到时间域内，即：

(7)

热核特征是会随着时间的流逝而有所改变，时间的不同，热核值也就不同。通常经过一段时间之后，就可以得到三维网格模型的扩散信息以获得模型的几何信息[18]。然而，由于热核特征方程是随着时间变化的函数，时间不同，每个模型顶点的热核特征值也不同。为了给每个模型一个准确不变并且区分变化最大的顶点，需要找到一个有利的确定的时间，来有效区分模型的每个顶点，根据已有的理论及证明，将时间设定为0.01，这样根据式(7)的热核方程就可以给每个模型顶点一个确定的值。

由于热核是模型的内在属性，对模型的等距等容变换具有尺度不变性，并且对畸变噪声有良好的稳定性。此外热核特征也使得模型的顶点具有时域的多尺度特性，这些特性使得热核特征可以成为非刚体模型对应的有利依据。

3 压缩流形模式

Ozolins等[17]提出了一种求一般微分算子压缩特征函数的方法。为此，他们添加了一个稀疏诱导l1范数的变分公式，即给定一个参数μ∈R+控制稀疏，就会有：

〈φk,φj〉=δkj

(8)

式中：δkj是克罗内克函数，这里用来加强特征函数的正交性。这些压缩的特征函数被证明具有紧凑的支持：它们只在有限的区域是非零的。紧凑的大小可以由μ控制，一个较大的值会导致小地区的支持。为了计算压缩流形基，将式(8)扩展到适用于三角形网格。这里要特别考虑面积矩阵D。没有D，特征基不独立于网格分辨率，三维网格的离散化如下：

s.t.ΦTDΦ=I

(9)

接下来使用乘法器(ADMM)的交替方向优化求解，为了能够有效地利用ADMM，需要对式(9)进行重新表述[9]：

s.t.Φ=S,Φ=E

(10)

注意这两个独立的耦合约束是如何迫使变量Φ等于S和E的，如果恰好满足了这些约束，那么我们就又回到了式(9)。将原来的最小化问题重新表述使我们能够应用ADMM方法，为此引入了对偶变量U∈R2N×k，U=[UE,US]对应于两个辅助变量E和S。给定Φ的初始值，令E=S=Φ，U=0，然后该算法将迭代以下步骤求解：

(11)

(12)

(13)

(14)

4 压缩局部的形状对应

4.1 压缩三维网格模型

压缩流形模式能够自动识别网格的关键形状特征。它们会自动将局限的局部区域分组，比如突出物并将脊线分为单独的基函数。由于其独特的空间局部性，它们对重要的几何和拓扑噪声(如局部扫描所产生的噪声)具有很强的鲁棒性。因此，CMB(Compressed manifold basis)可以作为鲁棒形状分析和匹配的工具。同时，CMB是正交基，可以重构任意形状上定义的函数，精度可达任意程度。因此，利用压缩流形基压缩三维网格的非刚体变换之间的特征表示，使得非刚体模型之间的压缩部位相同，找到相同部位的相等顶点，可应用于三维网格的局部对应匹配。效果如图3-图5所示。

图3 半人马的局部压缩对应1

图5 狼的不同位置的局部压缩对应

通过两种不同动物的不同部位，可以看出，压缩的部位是由φ和μ共同控制的，参数的不同，模型的压缩部位就会不同。其中没有颜色的部分特征函数无限接近于0，因此可以随意按照自己的需求去压缩任意局部(可以是一个手指的局部，例如图4；也可以是手、手臂等)，之后对热核特征的改进也是任意局部。

同时也可以通过设置不同的压缩特征函数的大小，来截取相同部位的不同大小，一般设置特征函数的绝对值大于0.001以上。压缩的大小范围也是可以通过参数控制的，一般参数μ的值越大，压缩的局部支持就会越小，当μ等于0时，所有的特征函数为0。本文通过设置阈值的大小，得到具体的局部压缩顶点的位置及个数以后，就可以进行接下来的局部对应匹配。

4.2 改进HKS

热核特征是三维网格模型的内在属性，对模型的等距等容变化具有尺度不变性。而HKS特征是由热量在模型表面逐渐传递得到的，是构成三维网格模型点信息的集合表现。HKS作为三维网格模型的特征选择，其计算方式一般是通过相应的离散化拉普拉斯-贝尔特拉米算子得到的，即首先计算三维网格模型的顶点面积和余切权重，通过顶点面积和余切权重构建拉普拉斯算子，然后对拉普拉斯算子进行特征值和特征向量的分解，通过分解所得到的特征值与特征向量，一般选取前30～300之间的特征值及所对应的特征向量，通过代入热核特征的公式来计算相应的热核值。本文通过对热核特征的学习与研究，利用离散化的压缩流形模式去替换传统离散化拉普拉斯算子以改进HKS,改进之后的热核特征，在三维网格模型的形状对应匹配上有更加准确的效果。局部压缩对比图如图6-图7所示。

(a) 原始 (b) 改进图7 狼嘴巴的局部HKS

图6、图7的对比图中，大部分的暗黑色为HKS设置为0的可视化，狼局部的高亮白色为正常的HKS计算及改进的计算对比显示。可以看出，改进之后的HKS在局部的分层更加细腻，在更小的区域区分更加明显(如图7中：改进之前的HKS只有高亮白色到淡白色的潜在变化，而改进之后明显出现了暗色系的淡黑色，层次上也是从高亮白色到淡黑色的渐变，细节分层明显更加细腻)。因此通过对比图的可视化，可以看出本文算法改进的可行性及鲁棒性。

4.3 局部对应匹配

由于局部压缩以后，顶点数量比较少，因此本文就选用了热核特征来寻找对应的真实匹配。然而，由于热核特征方程是随着时间变化的函数，时间不同，每个模型顶点的热核特征值也不同。为了有效区分模型的每个顶点，需要找到一个有利的确定的时间。根据文献[6]已有的理论及证明，我们把时间t设定为0.01，这样根据热核方程式(7)，就可以给每个模型顶点一个确定的值，这同样为模型的对应匹配提供了有利的依据。具体步骤如下：

步骤1假设源模型为A，目标模型为B，它们具有相同的顶点数N，以及面片数M。首先读取模型各自的顶点信息与面片信息，根据顶点信息与面片信息，利用向量积(叉积)法计算三维模型每一个顶点相邻的三角面片的面积之和的三分之一，即为每一个顶点所赋予的面积值，利用每一个顶点所赋予的面积值，构建对角矩阵A，其中要对每一个模型的顶点面积进行标准化处理。然后根据式(2)计算各自的稀疏矩阵W，最后通过式(1)构建拉普拉斯算子矩阵LA、LB，矩阵大小为N×N。

步骤2对各自的拉普拉斯矩阵LA、LB分别进行特征值与特征向量的分解，分解之后的特征值一般从大到小排序，其中每一个特征值都对应一列的特征向量。本文选取前30个大于0的特征值以及所对应的特征向量，用来计算三维网格模型的热核特征值。

步骤3通过压缩流形基压缩不同的模型得到不同的压缩部位，设置特征函数的阈值，截取相应部分的顶点数量及位置。读取相应顶点的热核特征来做具体的形状对应，对应方法由大到小排序即可。

步骤4以压缩流形基所优化求解的特征值及其特征向量替换离散化的拉普拉斯算子以改进热核特征，同样读取相应顶点的热核特征值以相同的方法进行局部的对应匹配。

步骤5最后通过改进前后各自的匹配结果来评估效果的好坏。

本文中图形的展示分别采用了稠密对应以及稀疏对应匹配，效果图如图8-图12所示。

图8 半人马原始局部对应 图9 半人马改进局部对应

图10 猫的原始局部对应 图11 猫的改进局部对应

(a) 原始 (b) 改进图12 狼的局部对应

为了更加直观地表现对比效果，图中只有猫是稠密对应，其他都为稀疏对应。

4.4 实验结果与分析

由于TOSCA模型库中的模型给出了准确的一一对应关系，以及TOSCA模型库中包含了动物和人类七种不同的模型，并且每一种模型都有不同的经过非刚体变换之后所形成的不同姿态，因此本文随机选取TOSCA模型库中的模型对本文算法进行验证，并与改进之后的算法进行对比实验。

给定一种衡量模型对应关系的准确性评价标准。即给定源模型A和目标模型B，由某一方法计算得到的对应关系为f：A→B，而非刚体模型之间的准确对应关系为fture：A→B。对于源模型A上的任一点P，f(P)表示计算出的P点在目标模型B上的对应点，fture(p)表示P点在目标模型B上的真实对应点。那么可以用测地距离dN(f(p),fture(p))来表示P点对应关系的准确性，即在误差允许的情况下，源模型与目标模型之间的对应匹配，其中Area(B)表示目标模型的面积，公式如下：

(15)

由于本文压缩顶点数量相较于整体而言比较少，因此，本文对比数据均采用真实的对比匹配，即在没有测地误差的情况下所表示的匹配率，实验结果如表1所示。

可以看出，无论是不同模型之间压缩相同的部位(例如猫的尾巴和狼的尾巴)，还是同一种模型压缩不同的部位(例如狼的下巴及狼的尾巴)，改进之后的真实对应匹配都要优于之前。由此可以看出本文算法具有很好的鲁棒性。同时，在非刚体模型之间压缩模型的局部，本文算法能够精准地找到相同的压缩顶点，从而能够准确地进行局部的对应匹配。

5 结 语

本文提出的利用压缩流形模式应用于非刚体三维网格模型变换之间，解决了非刚体三维网格模型之间的形状对应问题。同时在现实运用中，对于非刚体模型的形状对应也并不一定需要整体的全部对应，有的可能仅仅是需要对应于某一局部，本文算法正好解决了这一问题，并且提高了算法的效率以及局部的精准匹配。同时在匹配过程中改进了热核特征，使其局部对应效果更加突出。与已有算法相比，本文算法具有以下几个优点：(1) 本文算法在非刚体模型之间可以精确地确定某一部位的精准顶点数量与位置，缩短了局部对应的时间与效率，同时为局部对应提供了一个新的解决思路；(2) 本文算法改进了热核特征，为以后的整体对应匹配埋下了伏笔。