项目作者: WesleyyC

项目描述 :
:mortar_board: Graph Matching Algorithm
高级语言: Matlab
项目地址: git://github.com/WesleyyC/Graph-Matching.git
创建时间: 2016-10-27T17:12:53Z
项目社区:https://github.com/WesleyyC/Graph-Matching

开源协议:MIT License

下载


Graph Matching

This is a graph matching algorithm implmentation of a graduated assignment algorithm for graph matching using OOP scheme in MATLAB.

To generalize and recognize spatial pattern, a probabilistic parametric model is built. To register a sample ARG or check a test ARG, a graph matching probelm is presetend. However, graph matching is a long-known NP problem, so a lot of algorithms are derived to get an approximated solution in a reasonable time. In this project, we mean to use one of this algorithm to help us handle graph matching problem efficiently.

According to Gold and Rangarajan, a graduated assignment algorithm is developed to solve the problem efficiently and the code here is an attemp to implment and improve their algorithm mentioned in their paper: https://www.cise.ufl.edu/~anand/pdf/pamigm3.pdf

The improved algorithm allows null matching to propagate which in terms improve the precision of matching result while maintain the recall and the additional noise prevent matching to local optimal.

Test Result

  1. No Null Propagation (old algo - red):
  2. Recall: 0.75
  3. Precision: 0.72
  4. F: 0.73
  5. Size: 40
  6. Connected Rate: 0.2
  7. Noise Rate: 0.1
  1. Null Propagation + Stochastic (new algo - blue):
  2. Recall: 0.98
  3. Precision: 0.92
  4. F: 0.95
  5. Size: 40
  6. Connected Rate: 0.2
  7. Noise Rate: 0.1
  1. Comparison
  2. round: 100
  3. p_recall: <10^-6
  4. p_precision: <10^-6
  5. p_F: <10^-6

Result