基于莫斯-斯莫尔复形的自动特征对应方法

摘要

本发明公开了一种基于莫斯-斯莫尔复形(Morse-Smale complex)的自动特征对应方法。本发明包含以下三个步骤：1)模型的预处理，包括计算标量场和抽取莫斯-斯莫尔复形；2)特征图的构建，以莫斯-斯莫尔复形的关键点为特征点(图的节点)，并且在其连线基础上通过一个光顺过程来补全可能缺失的图的边；3)图匹配及重构续，包括基于谱的图匹配方法来找到特征点的对应以及一个重构续过程来纠正局部可能的由于对称带来的错误对应关系。本发明公布的方法是全自动的并且允许进行匹配的两物体具有相当大的几何差别，本发明适用于多种不同类型的物体间的匹配并且十分高效，可以在数秒内完成对应关系的计算。

说明书

技术领域

本发明涉及模型分析方法，尤其是涉及一种基于莫斯-斯莫尔复形的自动特 征对应方法。

技术背景

自动识别模型的对应关系是计算机图形学和计算机视觉中的一个基本问题， 是诸如点云注册，属性传输等诸多应用的基础。虽然人对于鉴别这种对应关系 非常擅长，即使两个模型间几何差别非常大，但是计算机自动鉴别出这样的对 应关系却是非常困难的。在之前的应用中，这种对应关系一般都是人工输入， 然而自动化的方法对于某些应用是必须的，因此自动的对应关系的获取成了近 两三年研究的课题。

在之前的自动获取对应关系的方法中，针对的物体一般都是同一个物体不 同姿势下的对应关系获取，对于不同物体所得到的对应关系则不理想，尤其是 几何差别比较大的物体。同时这些方法对物体的类型也有限制，如都必须是亏 格为零的物体。计算所需时间长是这些方法存在的另一个问题，一般需要花费 数分钟才能完成对应关系的计算。

发明内容

针对背景技术的不足，本发明的目的在于提供一种基于莫斯-斯莫尔复形 的自动特征对应方法，该方法不仅能够实现不同类型物体间对应关系的获取， 并且允许物体间具有较大的几何差别，同时此计算过程十分高效。

为实现上述的目的，本发明采用的技术方案包括以下三个步骤：

(1)给定两个模型，分别计算出它们的标量场，本方法中使用自动扩散方程 ，然后抽取出这个标量场的莫斯-斯莫尔复形，这两个莫斯-斯莫尔复形分别包括 梯度为零的关键点以及这些关键点之间连接的边，其中关键点包括极大点，极 小点和鞍点；

(2)以莫斯-斯莫尔复形的关键点作为特征点及图的节点；以莫斯-斯莫尔复形 的边作为图的原始边，为了克服莫斯-斯莫尔复形边可能存在的二义性问题，采 用一个多步的标量场光顺过程来定义增加更多的边以及定义所有边的概率，最 后以特征点和所有边来构成两个模型上的特征图结构；

(3)基于谱的方法进行图匹配得到初始的特征点对应关系，并通过一个重构 续过程来纠正由于对称带来的错误对应关系。

所述基于莫斯-斯莫尔复形的自动特征对应方法，其特征在于：步骤(2)所 述的多步标量场光顺过程把原有标量场光顺N步，N由用户决定，对于莫斯-斯 莫尔复形中的每个鞍点判断它能连接到其它极大或者极小点的最早步n，则每个 这种边的概率为(N-n)/N。

所述基于莫斯-斯莫尔复形的自动特征对应方法，其特征在于：步骤(3)所 述的基于谱的图匹配方法构建一个投注矩阵，其中对角线元素为两个图中两两 特征点之间的相似度，代表两个点之间匹配的概率，非对角线元素为两个这种 两两点对之间边的相符度，即为两个边概率的乘积，通过解这个投注矩阵的最 大特征值及特征向量可得到初始的对应关系。

所述基于莫斯-斯莫尔复形的自动特征对应方法，其特征在于：步骤(3)所述 的重构续过程通过判断每个点所连接出的边的逆时针顺序是否一致，以局部的 交换的操作来把由对称引起的错误对应关系纠正过来。

本发明与背景技术相比具有的有益效果是：

本发明提出了一个能够获取获取几何差别很大物体间对应关系的方法。它 不限制物体的类型，既物体可以有较高亏格，并且亏格可以不同。它的计算非 常高效，可以在数秒内完成对应关系的计算。

附图说明

图1是本发明的流程图。

图2是两个海星的在进行重构续前后的对应关系。

图3是重构续的示意图。

图4是三组几何差别大的物体的对应关系。

图5是三组不同亏格物体间的对应关系。

具体实施方式

下面结合附图和实施例对本发明作进一步说明。

基于莫斯-斯莫尔复形的自动特征对应方法包括如下步骤：

1)模型的预处理

包含计算标量场和抽取莫斯-斯莫尔复形两个步骤，如图1前三列。输入两 个模型，分别结算它们的自动扩散方程作为模型表面的标量场。计算自动扩散 方程的方法参见GEBAL，K.，BAERENTZEN，J.A.，AANAES，H.，AND  LARSEN，R.2009.Shape analysis using the auto diffusion function.In Proceedings of  the Symposium on Geometry Processing，Eurographics Association，Aire-la-Ville， Switzerland，Switzerland，SGP’09，1405-1413。然后在这两个标量场上分别抽取 莫斯-斯莫尔复形并且通过取消操作来对莫斯-斯莫尔复形进行简化以去除噪音， 具体方法可参见EDELSBRUNNER，H.，HARER，J.，AND ZOMORODIAN，A. 2001.Hierarchical morse complexes for piecewise linear 2-manifolds.In Proceedings  of the seventeenth annual symposium on Computational geometry，ACM，New York， NY，USA，SCG’01，70-79。莫斯-斯莫尔复形分别包括梯度为零的关键点以及这 些关键点之间连接的边，其中关键点包括极大点，极小点和鞍点，在图中分别 以红色，蓝色和绿色的球表示。

2)特征图的构造

莫斯-斯莫尔复形的关键点被选作特征点，以及特征图的节点，莫斯-斯莫尔 复形的边作为特征图最初的边。然而只用莫斯-斯莫尔的边会引入二义性，影响 对应关系结果的准确性。如图1特征图中的结点10，在左边模型中连接到了结 点11，而在右边模型中连接到了结点14。

本发明使用标量场光顺的方法来去除这种二义性。对于两个标量场分别光 顺N次，N由用户决定。对于每个鞍点，判断它能连接到其它极大点或者极小 点的最早步n，则添加一条概率为(N-n)/N的边。注意莫斯-斯莫尔复形的边 在原始标量场中就存在，所以它们的概率为1。在图1特征图中，虚线表示的边 就是通过这个光顺过程添加的边，标注的数字为边的概率。

3)图匹配及重构续

对于两个特征图G¹＝{V¹，E¹}，G²＝{V²，E²}，其中V代表结点，E代表边。图匹 配是找寻结点对之间的对应关系或者叫做分派 (assignment)。本发明中所用二阶图匹配使用到了结点间的相似性H(a)以及边的 相容性H(a，b)，其中a，b∈A。结点的相似性是通过比较结点的点标签(point  signature)得到，本发明中点标签使用每个特征点的类型和标量场的值：

其中f为标量场的值，R为归一化的项

边的相容性H(a，b)指对于两个对应关系两个边和是否都存在。在本发明中由于定义了边的概率，则H(a，b)定义为：

$H(a,b)=w_i(v_{i1}^1,v_{i2}^1)\times w_2(v_{j1}^2,v_{j2}^2)$

其中w为边的概率，如果边不存在则为0。

整个图匹配可以写为：

$\lambda \underset{a\in A}{\Sigma }H\left(a\right)+(1-\lambda )\underset{a,b\in A}{\Sigma }H(a,b)$

其中λ为平衡因子，调节点相似性和边相容性之间的权重。

本发明中使用LEORDEANU，M.，AND HEBERT，M.2005.A spectral technique for correspondence problems using pairwise constraints.In ICCV’05：Proceedings of the Tenth IEEE International Conference on Computer Vision，IEEE Computer Society，Washington，DC，USA，1482-1489.的谱方法来解这个图匹配问题，保证了 计算的高效性。

由于对称性的存在，使得结果中可能存在错误的结果，这些错误的结果与正 确的结果对于图匹配方程具有同样的最值。如图2第一行则为图匹配的结果， 圈中的点都是错误的对应关系。本发明中使用重构续的方法，对于每个结点， 判断其周围的逆时针顺序是否一致，如果不一致，则把不一致的地方进行局部 的交换。如图3所示，对于上下两个图中的结点1，逆时针顺序不一致，结点2 和4的顺序交换了。通过局部的交换结点2和4得到正确的对应关系。图2的 第二行为进行重构续后的正确对应关系。

图4和图5展示了本方法的两组实施结果，相同颜色的球表示对应的两 个点。本发明的方法可以正确找到图4中几何差别很大的物体以及图5中不同 亏格的物体间的对应关系。