图模型匹配:一种新的凹松弛函数及算法

Graph Matching:a New Concave Relaxation Function and Algorithm

将问题中的置换矩阵放松为双随机矩阵是近年来近似图匹配算法的一个重要发展方向.它的本质在于将离散的图匹配问题转换成一个连续优化问题,而一般来讲,相对于离散优化,连续优化问题的近似求解将更为容易.但随之带来的一个问题是如何有效地将连续优化得到的双随机矩阵重新映射回一个置换矩阵.最近文献中提出了一种针对于无向无自环图的凹松弛(Concave relaxation)函数,使得算法中的双随机矩阵可以平滑地收敛到一个置换矩阵,并得到优异的匹配精度.但除了无向且无自环图,文献中还没有针对其他类型图模型的凹松弛函数.本文提出一种针对于有向无自环图匹配问题的凹松弛函数,并在此基础上给出一种图匹配算法.大量对比实验验证了本文提出模型及算法的有效性.

Recently,approximate graph matching based on relaxing the permutation matrix to a doubly stochastic matrix has become an important and popular topic.The key point lies in which approximation over a continuous set is usually easier to implement than that over a discrete one.However,a consequent trouble related to such a relaxation is how to properly map the doubly stochastic matrix back to a permutation one.In the literature,a concave relaxation function for matching problem between the undirected graphs without self-loops was recently proposed,such that the doubly stochastic matrix can converge to a permutation one in a smooth way,and got a state-of-art performance on matching accuracy.Unfortunately,except for the undirected graphs without self-loops,there are no concave relaxation proposed for any other types of graph models.In this paper,we propose a concave relaxation for the directed graphs without self-loops,based on which a graph matching algorithm is then presented.Extensive experimental comparisons witness the validity of the proposed methods.