基于匹配-消息传递的快速图匹配方法

摘要

图匹配问题是计算机视觉中一个重要而基础的问题.针对图匹配问题目前最优的求解方法是凸-凹松弛过程(CCRP).但是,CCRP方法需要对一系列松弛问题进行求解,使得其速度较慢,难以求解大规模图匹配问题.同时图匹配中的约束条件与马尔科夫随机场最大后验概率推理中的约束条件具有相似性.受此启发,作者将图匹配问题表示为一个特殊的约束下马尔科夫随机场最大后验概率推理问题.在此基础上,针对该问题,作者提出一种新型线性规划松弛,并在此基础上推导得到匹配-消息传递方法,对该问题进行快速求解.实验表明,本文所提出方法在精度相同大于等于与CCRP方法的情况下,相对CCRP方法速度提高4～10倍.