-
对应关系的构建通常是根据局部特征寻找两个或多个模型之间的相同或相似的对应元素，这些元素可以是直接相关的，也可以是语义相关的。在两个或多个三维几何模型之间建立正确的对应关系是一项重要的基础性研究工作[1]。对应关系在计算机图形学和计算机视觉等领域有广泛的应用，例如模型变形[2]、模型分割[3]、模型插值[4]、模型分析与检索[5]、网格参数化[6]等。
一般情况下，根据模型表面的距离度量，三维模型的变换分为等距变换(isometric transformation)和非等距变换(non-isometric transformation)。在模型的对应关系中，等距被定义为给定点集上对应点在其度量空间上的距离保持映射，并且是对应点(该点在变换空间下具有不变性)之间的近似距离度量。三维模型形变方式又可分为刚性(rigid)变换和非刚性(non-rigid)变换，其中刚性变换有平移、旋转等，而非刚性变换有弯曲、缩放等。具有等距变换特性的模型，在经过非刚性变换后，其相应两点间的距离度量近似保持等距不变，因此，等距属性就是寻找模型间对应关系的一个重要依据。由于三维模型是离散的，因而计算最优的模型间对应关系等价于最小化两个或多个模型间所有对应点之间的距离度量差值，并用距离度量来存储模型的等距属性[7]。
在实际研究中，许多研究者都关注非刚性等距变换的模型间的对应关系计算，并取得了一些有意义的研究成果。文献[8]通过测地距离建立一个由概率统计方法得到的描述符进行配准，但是测地距离对于模型的拓扑结构变化比较敏感，不能得到良好的配准结果。文献[9]提出基于扩散距离和多维尺度分析(multi-dimensional scale, MDS)的非刚性变换模型相似性分析，解决了测地距离对拓扑结构变化的敏感性，较好地将扩散距离与MDS结合，通过计算嵌入模型的相似性来实现非刚性变换的模型之间的相似性分析，但是算法效率并不理想。文献[10]通过Laplace-Beltrami算子的特征方程来定义植入空间，并将模型进行谱植入来降维以达到简化对应关系计算的目的，提高了计算效率，但植入过程会存在误差而不能得到完全准确的对应关系。文献[11]在谱植入的基础上，通过稀疏到稠密的匹配策略建立模型间稠密对应关系，但这个过程需要一个良好的初始对应关系做保障。文献[12]提出了具有多尺度特性的热核签名描述符(heat kernel signatures, HKS)，能够有效区分模型的特征，利用特征相似性建立对应关系。但HKS有一个显著的缺点，就是它对模型尺度的变化比较敏感。文献[13]提出了尺度不变的热核签名(scale-invariant heat kernel signatures, SI-HKS)，在模型尺度因子中消除对一些参数的依赖，从而获得了尺度不变的热核签名。基于HKS计算的模型特征值分布可得到模型间整体的特征相关性，但对于构建模型间局部的特征相关性效果不是很好。为了解决这一问题，文献[14]提出了波核签名(wave kernel signatures, WKS)的算法，利用粒子能量的概率分布来测量不同模型上的分布点，对模型局部的特征定位进行了补偿。文献[15]提出了基于热核签名和波核签名的谱特征描述符(spectral descriptors)，该描述符结合了热核签名和波核签名的特性，具有多维性、等距不变性, 对网格拓扑改变不敏感, 能够表现模型全局结构和局部特性之间的差异，但是算法需要选择合适的基进行运算，且不能区分模型的对称性。文献[16]提出了函数映射(functional maps，FM)理论，将模型间对应关系转变为模型间函数映射问题，能够得到比较准确的模型间对应关系，但也不能有效地解决模型的自身对称性干扰对应关系计算的问题。文献[17]在函数映射的基础上，提出熵空间的函数映射方法，解决了对称性干扰问题，但是需要将模型间的函数映射分解成几部分，由于映射的分解必然引导模型函数空间的分解，因而还需要将函数空间分解成对称子空间和非对称子空间两部分，该处理过程十分繁琐。文献[18]通过统计方法校准Laplace-Beltrami算子建立对应关系，比较有效地解决了模型自身对称性的干扰问题，但必须要预先对模型进行分割处理。
此外，采用特征点标记算法[19-20]同时对源模型和目标模型进行相同的标记点采样可以减少匹配的时间复杂度，也可以有效地避免因对称性干扰而影响模型间对应关系的构建，但利用采样点集约束的方法有许多不足。一方面，基于标记点的方法需要大量的人工干预，无法适应现代技术的发展趋势；另一方面，利用采样点集约束目标模型上的搜索空间，再通过点与点之间的匹配来构建模型间对应关系的方法缺乏可靠性，当采样点集超过一定数量时，模型自身对称性仍然会影响模型间对应关系。
为了有效地解决模型自身对称性影响模型间对应关系计算的问题，本文在文献[16]与文献[18]的基础上提出了一种新的校准三维几何模型之间基矩阵的方法，用以计算非刚性变换的三维模型间的对应关系。首先，计算三维模型的Laplace算子，获得模型的特征值和特征向量，将特征向量作为函数空间，使得不同欧氏空间下的原始模型转换到同一Laplace空间中，并选取少量的特征向量构建一个基矩阵；其次，利用所得到的特征向量构建基矩阵，并提出协方差的最小值校准算法计算模型基矩阵之间的校准矩阵，该过程使模型间的对应关系计算问题转化为模型基矩阵之间的校准矩阵的计算，并且该过程省略了许多约束，如函数约束、描述符约束、标记点对应关系约束和模型分割部件的对应关系约束等；再次，计算源模型上各点的高斯曲率以采样尖端特征点，并在校准后的目标模型上对所有点进行遍历寻找最优对应点；最后，计算采样点与最优对应点之间的测地错误来衡量所构建的三维模型间的对应关系的准确性。
HTML
-
给定两个三维模型M和N，它们之间的对应关系可以表示为M和N的双边映射问题T：M→N，也就是说，T可以诱导一个可以推导计算的线性变换。给定源模型M上的标量函数f:M→R，根据映射T，通过复合变换g=f ∘ T-1可以获得模型N上的一个对应的标量函数g:N→R。用TF:F(M, R)→F(N, R)表示这个诱导变换过程，其中，F(M, R)和F(N, R)分别表示M和N的实值函数的类属空间，TF就称为映射T的函数表示[16]。
初始的模型映射T可以由T的函数TF来计算得到。给定模型M上任一点a，由T(a)构建一个标量函数f:M→R，则有f(a)=1且f(x)=0，其中∀x≠a∈M。若存在函数g=TF(f)，那么g(y)=f ∘ T-1(y)=0，其中T-1(y)≠a或1。该过程中的映射T可以被认为是可逆的，那么有唯一点y∈N使得T(a)=y。因此，g必须是T(a)的一个标量函数，且g(y)=1。
综上所述，对于任何确定的点与点之间的映射T：M→N, TF在函数空间之间都可以被线性地表示。假设模型M的函数空间有一个基{φiM}，使得M上任意标量函数f:M→R能够表示为该基下的一个线性函数的集合$f = \sum\limits_i {{a_i}\varphi _i^M} $，其中ai是系数，则可以将M上标量函数f线性表示为TF(f)，即：
若模型N有一组基函数{φjN}，那么对于{cij}有${T_F}\left( {\varphi _i^M} \right) = \sum\limits_i {{c_{ij}}\varphi _j^N} $，且有：
因此，函数f可以用一个系数向量a={a0, a1…ai…}表示，g=TF(f)同样可以用一个系数向量b={b0, b1…bi…}来表示，则式(2)可以简化为${b_j} = \sum\limits_i {{a_i}{c_{ij}}} $，其中cij独立于f并可以完全由空间基和映射T决定。如果基函数{φjN}是关于内积空间正交的，则矩阵C可以简单表示为{cij=〈TF(φiX), φjY〉}。
对于模型上任何函数f如果可以表示为一个系数向量a，则映射TF能够表示为一个矩阵C，即：
综上所述，通过矩阵C就能构建原始的模型映射T。函数映射就是将复杂的模型对应关系的构建转化为矩阵C的计算，通过优化计算矩阵C就可以准确地获得满意的模型间对应关系。
-
三维几何模型通常可以被认为是定义在Rie-mannian流形上的一个离散的网格曲面，因此，根据定义在该网格上的函数，可获得一个线性的Laplace算子，该算子表示一个顶点的函数值和它的第一环邻接点的平均权值，则网格上顶点i的Laplace算子可表示为[21]：
式中，N(i)为顶点i的第一环邻接顶点集合；fi为顶点i的函数值；因子di-1为正值；wij为连接顶点i和j的边权值。
由于文中使用的网格模型三角面片比较多，故可以使用几何网格Laplace近似表示一个Riemannian流形的Laplace-Beltrami算子。对于任意的标量函数f:V→R，基于边权重的几何网格Laplace算子P，则有[21]：
式中，l(eij)是边(i, j)的长度；σ为宽度参数。根据式(4)的定义，式(5)对所有的i有di=1，且对所有的i和j都有：
由式(6)可定义一个由dij构成的稀疏Laplace矩阵L。若i和j邻接，则dij=-wij；若i=j，则dii是L上i行i列的对角线元素，则有${d_{ij}} = \sum\limits_j {{w_{ij}}} $。
对得到的Laplace矩阵L进行特征分解，就可以得到三维模型函数空间的基，选取前n个特征向量组成m×n阶基矩阵，其中m为模型点的个数，基矩阵的每列为一个特征向量，每行可以认为是模型Laplace空间中对应点的坐标。
-
根据文献[16]中的介绍，选取Laplace-Beltrami算子分解得到的前n个特征函数作为模型的函数基，因而模型间原始的函数映射T就可以表示为n×n阶的稀疏矩阵Cn×n。但文献[16]在计算矩阵C时利用了函数约束、描述符约束、标记点对应关系约束和模型分割部件的对应关系约束等一系列线性约束。
为了避免过多的约束条件对构建原始的稀疏矩阵C的影响，根据函数映射理论所描述的模型间的初始映射关系T：M→N，分别计算源模型M与目标模型N的Laplace-Beltrami算子的特征函数{φiM}和{φjN}，并用这两个特征函数作为该函数空间下的基函数，这样不仅可以使两个不同欧氏空间的原始模型转化到相同的Laplace空间中，也可以认为模型M和N的基函数是同一个函数空间下的不同的基，则给定源模型M和目标模型N上的标量函数f和g可以分别表示为$f = \sum\limits_i {\varphi _i^M} $和$g = \sum\limits_j {\varphi _i^N} $。那么，模型M与模型N构建的相关函数g=f ∘ T-1可以表示为：
由于该方程可将模型间的函数映射关系TF:F(M, R)→F(N, R)变为同一个函数空间下的矩阵线性变换问题，且可以由特征函数组$\sum\limits_i {\varphi _i^M} $构建矩阵AM作为源模型M的函数空间基矩阵，同理可用特征函数组$\sum\limits_j {\varphi _i^N} $构建矩阵BN作为目标模型N的函数空间基矩阵，所以，在同一基下，两个矩阵之间的线性变换可以用一个矩阵S来表示，因而式(7)可由下式表示：
式中，矩阵S仅依赖于模型的基矩阵。
根据以上分析，将两个模型间的基函数映射问题转化为两个基矩阵之间的线性变换问题，即存在一个S使得源模型M与目标模型N之间的基矩阵可以相互转化，从而通过S的校准使得两个模型具有近似相同的特征函数。
由于源模型M与目标模型N的基矩阵分别是由Laplace-Beltrami算子分解得到的特征向量构建的，设LM和LN分别表示模型M和N的Laplace矩阵，根据所选取的特征向量的数量，对LM和LN进行特征分解，求得特征值和对应的特征向量，由特征向量分别构建M和N在Laplace空间的基矩阵AM和BN。根据概率统计理论，协方差可以衡量两个变量之间的总体误差，即两个变量之间的协方差值可以衡量两个变量之间的相似度。为了避免过多的约束条件影响校准S的计算，本文提出协方差最小值校准算法来计算S。设基矩阵AM和BN的每一列向量都为一个变量，那么计算校准S的步骤如下：
1) 计算源模型基矩阵AM中第i列向量ai与目标模型基矩阵BN中第j列向量bj的协方差，由式(9)所示：
式中，r11代表列向量ai自身的协方差值; r12和r21相同，表示列向量ai与列向量bj之间的差异值; r22代表列向量bj自身的协方差值。
2) 由式(9)计算基矩阵AM与BN中每列向量之间的差异值r12与r22，并分别构建基矩阵AM与BN之间的关系矩阵R和基矩阵BN的自身关系矩阵Rs。
3) 取关系矩阵R的绝对值，计算最小值矩阵：
再对最小值矩阵Rmin取绝对值并归一化；然后对最小值矩阵Rmin使用匈牙利算法获得校准S′。其中，匈牙利算法是一种用增广路径计算二分图最大匹配的算法，其时间复杂度为O(n3)，n为模型采样点个数。在模型对应关系的计算中，该算法能够根据一维或多维模型特征提供一一对应的模型对应关系。
4) 当校准S′中的元素与关系矩阵R中对应的元素值为-1时，则将S′中该元素的符号修改为-1，其余元素则保持不变。以该方法获取校准S′中各元素的符号后，也就得到了最终的校准S。
使用TOSCA模型库中的狼模型，对源模型与目标模型的Laplace-Beltrami算子进行特征分解，取特征函数的数量为50来构建基矩阵。图 1为模型表面某一特征函数分布的颜色渲染图，图为协方差最小值方法得到的两模型间校准S。如图 3所示，根据校准S对两个模型基矩阵AM与BN进行校准后，得到了模型表面某一特征函数分布的相同颜色渲染图，这表明S可以有效地校准模型间的特征函数。
Figure 1. Distribution of the Initial Eigenfunctions of Laplace-Beltrami Operator of the Wolf Model
Figure 2. The Calibration Matrix S Between Wolf Models
Figure 3. Distribution of the Eigenfunctions of the Wolf Model After Calibration
2.1. 模型的基矩阵
2.2. 基函数的校准
-
三维模型一般为离散的点云模型，该类模型有几千甚至几十万个离散点，对两个模型所有对应点进行一一匹配是非常耗时的，于是在计算源模型M与目标模型N的对应关系时，可以采样源模型M中任意数量的点，再对目标模型N中的所有点进行遍历寻求最优匹配点。
-
通常，采样点的数量都会低于模型总点数，因而选择具有代表性的局部特征点可以更好地构建模型间的对应关系。由于模型的尖端点(如动物模型的爪子、耳朵、鼻头、尾巴等；人模型的手、足、额头等)可以获取更多的模型局部特征信息，因此本文对源模型进行尖端点采样以获得一个对应关系候选点集。一般情况下，高斯曲率可以反映曲面的弯曲程度，因此采样尖端点的方法主要是依赖于模型上各点的高斯曲率。该方法步骤如下：
1) 读入模型，记录模型的点、面、边信息，并对模型进行标准化处理；
2) 计算模型中每个点的高斯曲率，将计算得到的每个点按高斯曲率值的大小进行排序；
3) 根据采样需要，由式(11)依次选取I个采样点：
式中，xi是采样的第i个点; X是根据高斯曲率值从大到小排序后的总点数集。如图 4所示，红色圆点为人体源模型进行尖端点采样后得到的采样点。
Figure 4. Feature Points on Source Model Sampled by UsingTip Points Method (Represented by the Red Dot)
-
对源模型M和目标模型N的特征函数进行了校准，并通过尖端点采样得到源模型M的采样点集Im后，就需要使用该采样点集Im中每一个点的特征函数，在目标模型N的所有点中遍历搜寻以求取最优的对应点。理论上，点匹配的问题类似于最近邻(K近邻)搜索问题。由于k-d树(k-dimensional tree)[22]可以分割k维数据空间的数据结构，主要应用于多维空间关键数据的搜索(如范围搜索和最近邻搜索)，因此本文采用k-d树寻找最优对应点。该方法的具体步骤如下：
1) 校准后的源模型M和目标模型N的基矩阵分别为AM和BN′，其中BN′= BNS，S为校准矩阵。对源模型M采样得到采样点集Im，再根据采样点构建基矩阵AM的子矩阵，即I×m的子矩阵E1，其中每行中的每个元素对应采样点集Im中的采样点，每个列向量代表每个点对应的特征向量。
2) 为目标模型N的基矩阵BN′构建一个k-d树treeB，并在treeB中寻找E1中每个点的最优对应点，如式(12)所示：
3) 用得到的Result中的点集构建基矩阵BN′的子矩阵E2，其中每个列向量表示计算得到的每个对应点的特征向量，其个数应与采样点集Im中的采样点个数相同。
4) 如果‖E2T/E1T ‖ < 1，则所得Result中的点为最优对应点，否则继续寻找。
综上所述，由于校准S可以较为准确地校准基矩阵，使匹配过程仅单独使用k-d树就可完成，省去了许多约束条件，所以该方法提高了构建模型对应关系的效率。
3.1. 特征点采样
3.2. 遍历匹配
-
使用TOSCA模型库对文中提出的方法进行了验证。TOSCA模型库由80个不同姿态的人物和动物模型组成，共8类模型，每一类模型具有相同的拓扑结构，能够提供一类模型中任意一对模型间的任意点与真实对应点之间的正确对应关系[21]。
-
文献[23]给出了一种衡量模型对应关系准确性的评价标准。给定源模型M和目标模型N，由某一算法计算得到的对应关系为f：M→N，而标准的对应关系为fture：M→N。对于源模型M上的任一点p，f(p)表示计算出的p点在目标模型N上的对应点，fture(p)表示p点在目标模型N上的标准对应点。那么，可以用测地距离dN(f(p)，fture(p))来表示p点对应关系的准确性，可用下式表示：
式中，dN(f(p)，fture(p))一般要通过除以目标模型面积的开方$\sqrt {{\rm{Area}}\left( N \right)} $来标准化。
-
本文的算法采用MATLAB结合C++编程实现。实验中，取Laplace算子的特征向量的个数为50，尖端点的采样个数为20。图 5(a)显示了一组校准前的半人马模型，可以明显地看到该组模型在同一特征函数下有不同的特征分布，而图 5(b)是对这组模型校准后，同一特征函数在该组模型上得到了相同的特征分布，并准确地显示了模型间近似特征点(特征点选取以模型间的测地错误不大于0.01为标准)的对应关系。图 6显示了一组人体模型在校准前与校准后的特征函数分布和对应关系构建结果。图 5和图 6的实验结果表明，本文提出的协方差最小值方法能准确地校准模型间特征函数。当选取模型间特征点的测地错误不大于0.01的标准下，半人马模型的近似对应点数量略多于人体模型。
Figure 5. Distribution of the Eigenfunctions and Correspondences of the Centaur Model
Figure 6. Distribution of the Eigenfunctions and Correspondences of the Human Model
分别计算TOSCA模型库中的5类动物模型与3类人体模型所有采样点间的平均测地误差，使用折线图来表示测地错误的分布。如图 7所示，图中x轴表示测地错误的阈值，y轴表示小于一定阈值的对应关系百分比(对应关系率)，实线表示5类动物模型的平均测地错误，点虚线表示3类人体模型的平均测地错误，可以看出在同一实验条件下动物模型间的对应关系要优于人体模型，主要原因是由于人体模型的点云数量较多，使得点遍历搜索的难度较大，因而证明模型上点的数量规模会对本文方法计算模型间对应关系的准确率产生影响。
Figure 7. Performance of Our Algorithm on Nearly Isometric Human and Animal Models from the TOSCA Dataset
-
在TOSCA模型库中，本文算法分别与HKS[12]、FM[16]和Machting Eigenfunction[18]等方法进行了对应关系的准确率比较，如图 8所示。实线为本文算法，点虚线为利用统计学校准Laplace-Beltrami算子并进行特征分解计算特征匹配函数的方法(Machting Eigenfunction)，虚线为函数映射理论方法(FM)，点画线为热核签名方法(HKS)。可以看出，本文方法有8.79%的对应关系没有测地错误，有60.15%的对应关系的测地错误小于0.025，当测地错误等于0.125时，对应关系率达到了96.89%，这些都优于HKS方法。与Machting Eigenfunction、FM方法相比，本文方法除了在测地错误为0时对应关系率略小外，在其他阈值范围的对应关系率都优于这两种方法。实验发现，当测地错误超过0.25，但对应关系率仍然低于80%时，表示模型间的对应关系受模型的对称性影响，如图 8中的FM、HKS方法，而本文方法在测地错误等于0.25时，对应关系率近似达到100%，相比Machting Eigenfunction的方法能更有效地解决了模型自身对称性影响模型间对应关系计算的问题。
Figure 8. Comparison of Our Method with the State-of-the-Art Methods of Matching Eigenfunction, HKS and FM on the TOSCA Dataset
4.1. 对应关系的评价方法
4.2. 实验结果分析
4.3. 实验结果对比
-
模型间的对应关系问题是计算机图形学和计算机视觉领域的一个基本问题，更是一个难点问题。本文提出了在函数映射理论框架下校准三维几何模型基矩阵的新方法，将模型间的对应关系的构建转化为校准矩阵的计算，并通过尖端点遍历匹配方法获取较优的匹配结果。同时，本文方法较好地解决了模型自身对称性影响对应关系计算的问题，提高了模型对应关系的准确性。此外，为了解决特殊情况下的模型间对应关系问题，例如部分与完整模型的对应关系或不同比例的模型间对应关系等，需要对本文方法进行扩展才能实现，这也是今后要继续研究的问题。
DownLoad:
