Graph matching とは

グラフマッチングは、グラフ間の類似性を見つけるという問題です。
グラフは、コンピュータビジョンやパターン認識などの多くの分野で構造情報を符号化するためによく使用され、グラフマッチングはこれらの分野で重要なツールです。これらの領域では、データグラフとモデルグラフとの間の比較が一般的に想定されている。
正確なグラフマッチングの場合は、グラフ同型性問題として知られています。グラフと他のグラフの一部との正確なマッチングの問題は、サブグラフ同型性問題と呼ばれます。
不正確なグラフマッチングとは、正確なマッチングが不可能な場合、例えば2つのグラフの頂点の数が異なる場合のマッチングの問題を指す。この場合、可能な限り一致するものを見つけることが必要です。例えば、画像認識アプリケーションでは、画像処理における画像セグメンテーションの結果は、典型的には、一致すると予想されるモデルグラフデータよりもはるかに大きな頂点数を有するデータグラフを生成する。帰属グラフの場合、頂点と辺の数が同じであっても、マッチングは不正確な場合があります。
探索方法の2つのカテゴリーは、2つのグラフ間の可能な及び不可能な対の頂点の同定に基づくものと、グラフマッチングを最適化問題として定式化する方法とに基づくものである。グラフ編集距離は、グラフマッチングに提案された類似性指標の1つです。エラー耐性グラフマッチングと呼ばれるアルゴリズムのクラス。