在机器视觉和模式识别领域,建立两个特征点集合之间的关联关系是一个关键的问题。通常情况下,特征点之间的关联关系的求解问题可以被转化为图匹配问题。图匹配的目标是在两个图中找到节点之间的映射关系。图匹配己广泛应用于图像检索、目标识别、目标分类和特征追踪等领域中。图匹配通常被视为二次分配问题(Quadratic Assignment Problem,QAP)。因为QAP是NP完全问题,图匹配也就成了 NP完全问题。现有的图匹配方法主要分为精确图匹配和近似图匹配方法。与近似图匹配方法相比,精确图匹配方法更为复杂和耗时。而且,在实际的图中,精确图匹配方法对于外部点和各种变化不具有鲁棒性。因此,本文主要研究近似图匹配方法。本文首先研究了一种基于混合多元关系的图匹配方法;然后针对传统兼容矩阵的局限性,提出了一种改进的基于加权局部和全局信息计算兼容矩阵的图匹配方法;其次,本文把图匹配问题视为一个优化问题,用置信传播(Belief Propagation,BP)算法解决优化问题,从而获得图匹配的优化解。本节提出了一种基于混合多元关系的图匹配方法。图像上的特征点具有空间相关关系,包括一元关系、二元关系和三元关系。一元关系是指特征点之间的关系,二元关系是指两两匹配对之间的一致程度,三元关系是指三对匹配点构成两个三角形之间的相似性,通过混合多元关系来获得初始的特征匹配。由于获得的匹配对不包含所有的点,因此提出了基于最小二乘法求局部变换矩阵,然后求未匹配点在变换矩阵下的对应匹配位置以获得完全匹配集合。我们在多个数据集上进行了实验,实验结果表明我们方法的有效性。本文提出了一种改进的基于加权局部和全局信息计算兼容矩阵的图匹配方法。由于传统的计算兼容矩阵的方法基于特征点的欧氏距离,既没有考虑方向信息,又没有考虑全局特征点空间拓扑信息,计算出的兼容性不能很好的表示匹配对之间的相关关系,因此我们提出了一种新的计算兼容矩阵的方法。首先计算局部兼容性时,同时考虑了特征匹配对的欧氏距离和方向信息;其次计算全局信息时,加入全局中心点作为参考点,因此计算两两匹配对之间的兼容矩阵也就转化成了根据三个匹配对的空间关系计算兼容矩阵。本文采用了匹配精确度和目标得分作为评价指标,并与当前比较流行的算法进行比较,结果表明了我们方法对于旋转、缩放、变形具有较好地鲁棒性。本文提出了一种基于置信传播的图匹配方法。图匹配问题可以被视为一个优化问题,进而提出了一种基于能量函数的优化目标函数,利用置信传播算法获得图匹配的最优解。首先把图匹配问题构建成一个MRF模型,然后执行BP算法获得图匹配中的近似边缘概率。对于一个图中的节点,我们在另一个图中选择具有最大匹配概率的节点作为该点的匹配点。为了满足一对(至多)一的匹配约束,我们研究了一个新的、基于特征点空间拓扑信息去除误匹配的方法。首先获得了可靠的匹配对集合,然后根据节点之间的空间关系,形成节点的向量描述,具有相似向量描述的节点被视为匹配节点。同样地,采用匹配精确度和目标得分作为评价指标,并与当前比较流行的算法进行比较,结果表明了我们提出方法的有效性和稳定性。