基于图编辑距离的图匹配算法研究

Research on graph matching algorithm based on graph editing distance

在图匹配中,图编辑距离算法随着图节点的增加与图对称等问题,计算复杂度增加,匹配效率大打折扣。为提高图编辑距离算法的匹配精准度,研究利用拉普拉斯算子提取图特征,通过Symmetry-Breaking解决图对称以提高图编辑距离算法的匹配效率。性能测试结果显示,改进图编辑距离算法编辑代价明显降低,加噪环境下平均精准度为0.951。不同图像匹配效果表明,该算法的识别精准度在85%以上,匹配效率最快,可用于图匹配、目标识别等领域。

In graph matching,the graph editing distance algorithm increases computational complexity and greatly reduces matc-hing efficiency with the increase of graph nodes and graph symmetry issues.In order to improve the matching accuracy of the graph editing distance algorithm,the Laplace operator is used to extract the graph features,and Symmetry Breaking is used to solve the graph symmetry to improve the matching efficiency of the graph editing distance algorithm.The performance test results show that the improved graph editing distance algorithm significantly reduces the editing cost,with an average accuracy of 0.951 in noisy environ-ments.Different image matching results indicate that the recognition accuracy of this algorithm is above 85%,and the matching efficiency is the fastest.It can be used in fields such as image matching and target recognition.