基于谱变换的非刚性模型局部匹配

韩丽 徐圣斯 朴京钰

摘  要： 面向海量复杂的非刚性三维模型的匹配与检索需求，提出了基于谱变换的局部匹配方法，有效提高了局部检索的性能，为进一步实现三维模型的形状编辑、修补以及创新合成奠定了坚实的基础。首先，基于离散拉普拉斯映射方法，通过ICP配准方法有效分析二维谱图，提取最优的谱特征表示;其次，构建谱特征的形状描述算子，计算谱空间的几何变换参数;进而，引入区域查询实现基于谱变换的区域配准;最终，通过区域搜索与相似性度量实现高效的非刚性模型局部匹配。实验结果表明，本方法不仅能够有效识别同一类非刚性模型的局部结构，而且对于不完整的模型匹配具有较强的鲁棒性，具有更优的局部检索性能。

关键词： 谱变换;局部匹配;非刚性模型;区域配准

中图分类号： TP391.41    文献标识码： A    DOI：10.3969/j.issn.1003-6970.2020.10.006

本文著录格式：韩丽，徐圣斯，朴京钰. 基于谱变换的非刚性模型局部匹配[J]. 软件，2020，41（10）：2226

【Abstract】： Aiming at the requirements of shape matching and shape retrieval of massive non-rigid 3D shapes， a novel partial matching method based on spectral transformation was proposed， it effectively improved the performance of shape retrieval and provided a solid foundation for further shape editing， mending and innovative synthesis of 3D models. First， the optimal two-dimensional spectral feature representation of non-rigid 3D shape is extracted based on the spectrum theory. Secondly， we construct shape context description of the spectral features and calculate the geometric transformation parameters of two spectral graphs; Furthermore， a region query is introduced to implement local region registration based on spectral transformation; Finally， partial matching of non-rigid shapes is achieved through local region searching and similarity estimation. Experimental results show that our method not only effectively improves the efficiency of model matching， but also can effectively identify the structural features of the same type of shape， and at the same time has strong robustness for matching between incomplete shapes.

【Key words】： Spectral transformation; Partial matching; Non-rigid shape; Region registration

0  引言

随着三维模型获取以及建模技术的发展，针对海量、异构三维模型的形状分析、配准、检索等应用研究日益广泛。尤其，三维模型的局部匹配与检索在实现快速的大规模场景重构[1]、三维模型恢复、三维创新设计[2]等应用中具有重要意义[3]。

Paul J. Besl等[4]最先提出了迭代最近点算法（ICP），估计匹配最近点的最优刚性变换，实现不同三维形状之间的配准，对三维点集、线段集和网络实体模型均适用，但时间复杂度较高，且不能达到全局最优解。Ferreira等[5]利用层次分割树将网格模型迭代地分为子部件，然后再进行相似性匹配。Wessel等[6]提出用图元（圆柱、圆环、球等）对模型局部做匹配。这类基于子部件的局部匹配方法需要解决模型部件分割问题，由于要设置多个阈值而失去健壮性。Stephen等[7-8]提出了利用模型拓扑结构的检索方法，但拓扑结构提取算法一般对噪声敏感，所以难以獲得稳定的部件分割结果。

Funkhouser等和Shilane等[9-10]提出了优先队列比较法。该方法在模型上生成大量采样点，然后提取采样点周围的形状特征，构建一个优先级队列以选取形状区别力强的向量来计算相似度。其方法虽不需要对模型做部件分割，但是特征提取和区分度排序的计算量较大，因此该方法也难以应用于检索结构复杂的非刚性模型。

近年来，谱分析的方法被广泛应用于非刚性三维模型的检索与匹配。其利用拉普拉斯算子将三维模型映射到谱特征空间，揭示了模型的内蕴属性，能够有效提高非刚性模型的匹配精度。例如，Lipman等[11]基于谱方法实现全局内蕴的检测;Sahillioglu等[12]在谱域构造初始化匹配，并采用贪婪算法结合等距性优化匹配结果;Sun等[13]基于模型表面热扩散方程提出了热核特征（HKS：Heat Kernel Signature）表示及形状分析方法;Aubry等[14]将波动方程引入模型，提出波核特征（WKS：Wave Kernel Signature）的形状分析方法。

然而，目前的谱分析方法主要基于构建的局部描述符或全局点特征表示实现整体形状分析与检索，对于局部匹配的研究还不是十分广泛。

本文提出了一种基于谱变换的非刚性三维模型局部匹配算法。我们通过将非刚性三维模型映射到谱特征空间，提取稳定的二维谱特征表示;基于谱空间变换来实现模型的谱图配准。进而，引入区域查询与相似性度量，实现基于谱变换的局部区域匹配。该算法无需对模型进行分割，避免了三维模型中的大量点云计算，一系列实验验证了算法的高效性与稳定性。

1  基于谱变换的局部匹配

本方法主要由三步骤组成：首先，通过拉普拉斯映射提取最优的二维谱特征描述;其次，采用Shape-Context方法[15]，实现二维谱图的局部轮廓匹配，并基于区域查询点计算谱图的几何变换参数，建立局部区域的谱对应;最终，通过局部区域优化实现非刚性模型的局部匹配。

1.1  最优二维谱特征表示

基于拉普拉斯映射的谱嵌入将高维数据嵌入到低维空间，有效保持模型的内蕴形状特性（等距不变性、拓扑不变性），不仅使计算更有效，而且对物体的姿态变化与局部形变不敏感，可有效用于非刚性模型的匹配与分类。

设无向带权图G=（V，E）表示网格模型M，其中，vi∈V代表模型顶点，eij∈E表示图中任意顶点vi和vj的连接边。顶点之间的相似性可由两点之间的测地线距离表示Wij∈[0，1]：

模型的谱特征表示中，特征维数越高，其形状描述能力越强，但同时也带来了计算时间和存储空间的更大开销。前k个特征基有效揭示了模型的内蕴结构特征，被广泛应用于形状匹配与检索中[16]。然而，特征基分布存在扭曲、次序翻转等若干问题，给形状匹配带来了极大的困难。本文进一步提出了最优二维谱嵌入表示方法，通过低维的谱空间变换，实现高效的非刚性模型局部形状匹配。

我们提取模型的前k=4个特征向量，利用两两特征基构建二维谱图候选集;进而，基于ICP（Iterative Closest Point）方法[4]进行谱图相似性分析，建立稳定的二维谱特征表示。

其中，为两个模型对应的二维谱特征基，R 和t为旋转、平移几何变换，通过公式5，迭代最近距离点集，求解四元转换矩阵R和t，最终，通过判断阈值内的匹配对数，有效获取候选谱图的形状相似度。

图1（a）为两个不同姿态蚂蚁模型的二维谱图候选集（1-2、1-3、1-4、2-3、2-4和3-4），通过ICP迭代匹配算法衡量谱图之间的形状相似性。如图1（b）所示，其中，由2-3特征基构建的二维谱图的匹配精度最高（红框内所示）。通过实验统计分析，我们发现由2-3特征基构造的二维谱图在非刚性变换模型中具有更强的稳定性。因此我们将其作为模型的最优二维谱特征表示。

1.2  基于谱变换的局部区域匹配方法

利用稳定的二维谱特征表示，我们进一步提出了基于谱变换的形状匹配方法。通过建立谱图的轮廓配准与区域查询，有效获取谱空间的几何变换参数;进而，基于区域几何变换与相似性度量，实现高效的非刚性模型局部形状匹配。

1.2.1  局部谱图轮廓配准

首先，我们采用Alpha-Shape算法提取二维谱图轮廓点集（如图2（a，b）所示），依据形状上下文（Shape-Context）算法[15]构建谱图之间的局部轮廓对应，如图2c，蓝点是局部模型的谱图轮廓点，红点是完整模型谱图轮廓点。

我们以轮廓点为中心建立同心圆，以圆心为中心按照，12个方向，将空间分为60个区域（60个bin）。根据轮廓点在bin中的分布，利用直方图表示其上下文形状信息。

设和分别为源模型与目标模型的最优二维谱图上的轮廓点。采用代价矩阵 计算形状相似度：

分别表示和归一化后的形状直方图的第k级，k为形状直方图的量化等级。的值越小，说明两点之间越相似;反之，两者之间相差越大。通过公式6可获得两个谱图上所有轮廓点的匹配点对。

1.2.2  基于谱变换的区域配准

为了有效获得模型的区域匹配，我们在二维谱图中引入区域查询点，有效建立谱图空间的几何变换，并运用均值聚类及谱变换高效实现谱图局部区域的配准。

首先，建立源模型谱图的包围盒（BoundingBox），均匀放置m×m个查询点，确定轮廓内有效查询点集。进而，为每个有效查询点依据半径r进行邻域搜索，提取该查询点所对应的轮廓点集。其次，根据源模型的轮廓点及已经建立的与目标模型的配准点对，计算谱图的几何变换：

搜索区域内所有轮廓点，构建变换空间Φ：，采用Mean-shift算法获得变换空间Φ的中心变换参数，确定为当前查询点Si的几何变换参数。通过查询点Si以及几何变换参数，我们获得目标模型的区域匹配点。

进而，所有的查询点及其变换参数，即可得到目标谱图区域中的对应点集合Fs。

图3（a）左图中的绿色点为谱图轮廓内的区域查询点，通过设置每个查询点的搜索区域（如黑色圆所示），确定搜索区域的轮廓点。进而，通过轮廓点集及谱配准点对，计算变换空间，通过聚类获得变换空间的中心参数，作为查询点变换参数，从而获得目标模型的内部区域点，如图3（a）右图所示。

图3（b）为人马的上半身局部模型及其完整模型的二维谱图表示，依据轮廓对应以及谱图变换，获得的有效局部匹配区域，如图中黄色为局部模型的谱图，蓝色区域为完整模型中对应的局部区域。图3（c）为从谱域到空域的转换，非刚性模型在空域中局部区域的提取。

最终，依据所确定的源模型与目标模型所对应的谱图区域，我们通过区域搜索与特征相似性度量，实现空域中模型的局部结构匹配。

Hausdorff距离是描述两组点集之间相似程度的一种量度，计算时首先要计算两组点集之间的有向Hausdorff距離，有向的Hausdorff距离被定义为：

其中d（x， y）表示點集X与点集Y间的马氏距离（公式10）。公式10中，是源模型的点集，是目标模型中对应的局部区域的点集，S是和的协方差矩阵。

如图4为两组非刚性模型的局部匹配实验结果。

本文的算法主要步骤可归纳如下：

输入：源模型M1和目标模型M2

输出：局部区域匹配点对D（M1，M2）

Step1：最优二维谱图提取：通过拉普拉斯映射及ICP方法，提取模型的最优二维谱图表示（P，Q）。

Step2：谱图轮廓配准：通过轮廓提取与形状上下文算法得到模型的谱图轮廓点集与配准点对C。

Step3：谱变换：设置源模型的查询点集Si，计算邻域内轮廓点的几何变换空间，通过Mean-shift获得中心变换点集参数。

Step4：谱图区域配准：通过谱变换函数，计算目标模型的对应区域点集，

Step5：模型局部匹配：采用区域搜素与相似性特征度量，计算模型的区域匹配点对D。

2  实验及结果分析

本文方法的实验平台为Intel（R）Core（TM）3.2 GHz CPU，8 GB内存的惠普PC，并使用VC++6.0，Matlab图形可视化软件开发环境。

实验中，我们使用标准的非刚性三维模型数据库SHREC2010、SHREC2011。SHREC2010数据库中包含10个类，每类中含有20个姿态各异的三维模型，SHREC2011数据库包含600个非刚性三维模型，分为30类，每类有20种不同姿态模型。

我们分别对本文算法、ICP[4]、文献[17]、SGC[18]和SHOT[19]进行了综合分析。图5显示了基于SHREC2010数据库与SHREC2011数据库的PR曲线结果。

ICP的基本原理是通过就近点之间的最小距离约束模型的配准过程，要求配准ICP的基本原理是通过就近点之间的最小距离约束模型的配准过程，要求配准模型具有较高的相似性，而对于不相似的模型会出现较大误差。同时，该方法只能实现刚性配准，对于具有不同姿态及局部形变的同类模型会产生较大差异。

文献[17]的算法使用了融合空间结构特征的方法，通过提取模型优化后的骨架，转换为骨架树进行基于图结构的筛选，并融入空间结构特征与几何细节，最后利用EMD距离方法实现模型匹配，这一算法可以有效的实现局部匹配，但是总体匹配时间较长。

SGC[18]是对于三维点云的稳定几何质心特征进行编码的局部描述符，如图8中PR曲线可见，其在三维模型局部匹配中具有较好的效果，但是，由于需要从每个体素提取的几何质心和点密度特征来构造描述符，需要消耗大量时间。

SHOT[19]通过查询点的空间方向直方图特征实现局部匹配，对于扭曲比较大的非刚性三维模型，会产生较大的差异，而且对于有噪声的模型鲁棒性比较差。

本文提出了基于谱空间变换的局部匹配方法，将复杂的三维模型通过拉普拉斯算子映射到谱空间，建立最优的二维谱特征表示，其有效保持了模型的内蕴形状特性。进而，基于谱空间的几何变换，实现二维谱图配准。最终通过查询点及区域搜索，实现局部区域匹配。本方法基于二维谱图进行区域搜索与匹配，不仅大幅度减少计算时间，而且对于非刚性变换及噪声模型具有极强的鲁棒性。

图6（a）分别是SHREC2010数据库中人马和蚂蚁的局部匹配结果，图6（b）是SHREC2011数据库中恐龙1和恐龙2的局部匹配结果。可见，本文方法在不同种类的非刚性模型局部匹配中具有极强的稳定性。

表1是ICP算法、SHOT算法、SGC算法以及本文算法在不同模型上的检索率;图7为不同方法在不同测地误差下的配准率。可以看出，本算法的性能明显优于其他算法。

为了验证本文算法的鲁棒性，本文在实验中对原模型随机加入高斯噪声。如图7（a）为蚂蚁模型以及加入4%，8%，12%的随机高斯噪声的模型。图7（b）为对应模型的最优二维谱图表示，可见，不同噪声的蚂蚁模型的二维谱图变化非常小，具有较强的鲁棒性。图7（c）为每个算法对噪声的鲁棒性测试结果。

3  结语

本文面向非刚性三维模型的局部匹配与检索的需求，提出高效、稳定的三维模型形状分析与局部匹配方法。通过基于拉普拉斯映射的谱嵌入，构建最优二维谱特征描述，其不仅实现了有效降维，而且有效保留了模型的统一内蕴结构特征。我们通过二维谱空间进行局部轮廓配准，有效建立谱空间的几何变换，实现区域的配准与相似性度量。一系列实验验证了本方法对于不同姿态及不同种类模型的识别具有较强的稳定性与高效性。在未来的工作中，我们将深度开展模型的协同分割与语义标注的研究，建立高层次的模型结构分割与描述机制，并对残缺模型修补进行更进一步的研究。

参考文献

[1]张数， 杨德宏. 数字近景摄影测量的二维影像三维建模的关键技术应用[J]. 软件， 2018， 39（2）： 133-138.

[2]刘尚武， 魏巍， 矫宇鹏. 三维模型的规格化表示与存储方法研究[J]. 软件， 2016， 37（4）： 29-31.

[3]李慧霞， 高梓豪. 室内智能移动机器人规则物体识别与抓取[J]. 软件， 2016， 37（02）： 89-92.

[4]Besl P， Mckay N. A method for registration of 3-d shapes. IEEE Transon PAMI， 1992， 14（2）： 239-256.

[5]Ferreira A， Marini S， Attene M， et al. The saurus based 3D Object Retrieval with Parin whole Matching[J]. Int. J. Comput. Vis. 2009， 89（2/3）： 1405-1573.

[6]Wessel R， Klein R. Learning the compositional structure of manmade objects for 3D shape retrieval[C]//Proceedings of Euro graphics 2010 Workshop on 3D Object Retrieva1. Norrk-oping， Sweden： Springer， 2010： 39-46.

[7]Barequet G， Sharir M. Partial surface matching by using directed footprints[J]. Computational Geometry： Theory and Applications， 1999， 12（1-2）： 45-62.

[8]Barequet G， Sharir M. Partial surface and volume matching in three dimensions[J]. IEEE Transactions on Pattern Analy sis and Machine Intelligence， 1997， 19（9）： 929-948.

[9]Shilane P， Funkhouser T. Selecting distinctive 3D shape descriptors for similarity retrieval[C]//IEEE International Conference on Shape Modeling And Applications. Matsushima， Japan： IEEE Cornputer Society， 2006， ： 108-117.

[10]Shilane P， Funkhouser T. Distinctive Regions of 3D Surfaces[J]. ACM Transactionson Graphics， 2007， 26（2）： 1-15.

[11]Lipman Y， Chen X， Daubechies I， et al. Symmetry factored embeding and distance[J]. ACM Transactions on Graphics， 2010， 29（4）： Article No. 103.

[12]Sahillioglu Y， Yemfz Y. Minimum-distortion isometric shape correspondence using EM algorithm[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2012， 34（11）： 2203-2215.

[13]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.

[14]Aubry M， Schlickewei U， Cremers D. The wave kernel signature： a quantum mechanical approach to shape analysis[C]// Computer Vision Workshop. Washington， DC： IEEE Computer Society， 2011： 1626-1633.

[15]Belongies， Malikj. Shape matching and object recognition using shape contexts. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2002， 24： 509-52.

[16]Yusuke Yoshiyasu A， Eiichi Yoshida A， Leonidas Guibas B. Symmetry aware embedding for shape correspondence [J]. National Institute of Advanced Industrial Science and Technology. 2016.

[17]韓丽， 程远， 融合空间结构特征的三维模型局部检索方法[J]. 微型机与应用， 2013， 32（15）.

[18]Tang K， Song P， Chen X. Signature of geometric centroids for 3d local shape description and partial shape matching[J]. Asian Conference on Computer Vision， 2016： 311-326.

[19]Tombari F， Salti S， Stefano. Unique signatures of histograms for local surface description[J]. ECCV. 2010： 356-369.

[20]卢超， 黄蔚， 胡国超. 基于图形数据结构的复杂对象建模设计[J]. 软件， 2015， 36（12）： 220-223.

[21]张媛媛， 杨洪娟， 朱汇龙. 面向图像视觉特征检索的高维索引结构研究[J]. 软件， 2018， 39（1）： 105-109.

[22]任忠良. 一种基于SIFT特征的快速图像匹配算法[J]. 软件， 2015， 36（6）： 53-57.