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

摘要：

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

关键词：图模型匹配、Frank-Wolfe算法、凹松弛函数、凸松弛函数

所属期刊栏目：38

分类号：TP391.41(计算技术、计算机技术)

资助基金：国家自然科学基金60975002

在线出版日期：2012-10-29（万方平台首次上网日期，不代表论文的发表时间）

页码：725-731