点模式匹配问题所求解的是用点集表示的两个相关模式之间的对应关系,它是模式识别、计算机视觉、分子生物学等诸多领域的一项关键的基础性课题。近年来,基于图的技术在点模式匹配问题中得到了越来越多的应用,谱方法作为基于图的技术的一个重要分支,主要是通过讨论图的邻接矩阵或者Laplace矩阵的特征值和特征向量获取点集间的对应。由于谱方法能够将点模式匹配这种高度复杂的组合优化问题转化为简单的、离散的谱的求解问题,因而日益受到众多研究者的关注,也成为模式识别等领域的一个研究热点问题。
　　本文主要研究了谱方法在点模式匹配问题中的应用,主要研究成果和创新之处如下:
　　1、提出一种基于图的Laplace谱的点模式匹配算法。首先定义结构图的高斯权Laplace矩阵,然后对Laplace矩阵进行SVD分解获得点模式在特征空间上的表示,并对其特征空间进行分析获得点模式匹配矩阵,进而获得匹配结果。实验表明该方法能够应用于点模式匹配问题。
　　2、受Pilu算法的启发,提出一种与局部相似性分析相结合的Laplace谱匹配算法。首先利用Laplace矩阵的特征向量求解初始匹配概率,然后使用概率松弛法将用灰度标准相关表示的局部相容性进行约束传播,随着迭代过程并行地调整点与点之间的相似度测量值,从而达到使用局部相似性修正由Laplace谱获取的匹配概率的目的。比较实验说明该方法在结合局部相似性分析的稳定性上要好于Pilu算法。
　　3、提出一种与形状上下文分析相结合的Laplace谱匹配算法。该算法作为上述算法的改进,依然采取使用概率松弛法对用局部相似性表示的局部相容性进行约束传播的思想。所不同的是,采用了形状上下文表示的点集结构特征来刻画局部相似性,并且在支持度函数的计算上采用了一种启发式的策略。比较实验表明,该方法不仅有效地提高了Laplace谱匹配算法的精度,而且在对随机位置抖动的鲁棒性上有了很大的改善。
　　4、提出一种新的谱匹配概率的计算方法。该方法首先利用Laplace矩阵的特征向量和特征值计算初始值,然后通过交替地对匹配矩阵的行与列进行归一化,将匹配概率矩阵转化为双随机矩阵的形式。利用该种形式的匹配概率矩阵可同时从行与列上判断匹配关系,实验表明该方法不仅在精度上要优于传统的方法,而且可获得严格的一对一匹配关系。
　　5、提出一种使用薄板样条变形模型的Laplace谱匹配算法。该算法建立在迭代地求解点集对应关系和几何变换关系的框架下。首先通过对Laplace谱的分析获取点之间的匹配关系,再利用已知的匹配关系求解待匹配点集的薄板样条变换关系,然后用求得的几何变换关系,使待匹配点集逐步逼近。通过这种迭代过程,最终使两个点集达到基本近似,进而提高了Laplace谱匹配算法的精度。实验表明该算法不仅对较大的仿射、射影失真以及非刚体形变都能进行有效地处理,而且对随机位置抖动的鲁棒性也有了很大的提高。