• Anytime Graph Matching

This work was part of my Ph.D dissertation. In the dissertation, we propose and explain the use of anytime algorithms in graph matching (GM).

The anytime concept [1] is demonstrated in the following video. An example of two graphs taken from the House CMU database is given [2]. One can see that the distance between the two graphs is decreasing as a function of time since the additional time allows to encounter better and better distances.

In the following video, the anytime algorithm is compared to the bipartite graph matching algorithm [3] (referred to as BP) in terms of the obtained distance and the number of matching errors with reference to the ground truth. In this example, under 1010 milliseconds, the anytime algorithm proves to be more precise than the bipartite graph one in terms of the resulting distance as well as the number of matching errors when comparing results with the ground truth..

References

• [1] Zeina Abu-Aisheh, Romain Raveaux and Jean Yves Ramel, Anytime graph matching. Pattern Recognition Letters 2016: (84)215-224. Download
• [2] CMU houses and hotels, http://vasc.ri.cmu.edu/idb/html/motion.
• [3] Kaspar Riesen, Horst Bunke: Approximate graph edit distance computation by means of bipartite graph matching. Image Vision Comput. 27(7): 950-959 (2009)