A Comparative Study of Graph Matching Algorithms in Computer Vision

Home

About this site

This is the companion website to our ECCV 2022 paper “A Comparative Study of Graph Matching Algorithms in Computer Vision”. Please cite it if you use any information from this website.

Here we publish detailed benchmarking results and provide the used datasets for download.

We will do our best to keep the results up to date. If you want to have your graph matching algorithm or your data included on this website, please follow the procedure described at the dedicated page.

The graph matching problem

The graph matching optimization problem is an essential component for many tasks in computer vision, such as bringing two deformable objects in correspondence. Naturally, a wide range of applicable algorithms have been proposed in the last decades. Since a common standard benchmark has not been developed, their performance claims are often hard to verify as evaluation on differing problem instances and criteria make the results incomparable. To address these shortcomings, we present a comparative study of graph matching algorithms able to optimize graph matching problem in the generic Lawler. The goal of graph matching is to find a matching, or mutual assignment, between elements of the sets \(\mathcal V\) and \(\mathcal L\) that minimizes the total cost for all pairs of assignments, i.e.

\begin{align*} \min_{x\in\{0,1\}^{\mathcal V\times \mathcal L }} & \sum_{\substack{i,j\in\mathcal V\\ s,l\in\mathcal L}} c_{is,jl} \, x_{is}\, x_{jl} \\ \text{subject to}\quad & \forall i\in\mathcal V\colon\sum_{s\in\mathcal L}x_{is}\le 1\,, \text{ and} \\ & \forall s\in\mathcal L\colon\sum_{i\in\mathcal V}x_{is}\le 1\,. \end{align*}

Here, \(\mathcal V\) and \(\mathcal L\) are the two finite sets, whose elements we want to match to each other. For each pair \(i,j\in \mathcal V\) and each pair \(s,l\in\mathcal L\) a cost \(c_{is,jl}\in\mathbb R\) is given. The vector \(x\) defines the matching as \(x_{is}=1\) corresponds to assigning \(i\) to \(s\). The inequalities allow for this assignment to be incomplete, i.e., some elements of both sets may remain unassigned.

We create a uniform benchmark where we collect and categorize a large set of existing and publicly available computer vision graph matching problems in a common format. At the same time we collect and categorize the most popular open-source implementations of graph matching algorithms. Their performance is evaluated in a way that is in line with the best practices for comparing optimization algorithms. The study is designed to be reproducible and extensible to serve as a valuable resource in the future.

Our study provides three notable insights:

  1. Popular problem instances are exactly solvable in substantially less than 1 second and, therefore, are insufficient for future empirical evaluations.

  2. The most popular baseline methods are highly inferior to the best available methods.

  3. Despite the NP-hardness of the problem, instances coming from vision applications are often solvable in a few seconds even for graphs with more than 500 nodes.

Check our paper for more details!