Anytime Graph Matching
The anytime concept is demonstrated in the following video. An example of two graphs taken from the House CMU database is given [1]. 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, one can see clearly the scroll bar which allows to choose a certain time constraint in milliseconds (ms). The anytime algorithm is then run under 15210 ms. As in the previous video, one can see the algorithm finds a first solution and keeps searching for a better one in order to improve its solution.
In the following video, the anytime algorithm is compared to the bipartite graph matching algorithm [2] (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] CMU houses and hotels, http://vasc.ri.cmu.edu/idb/html/motion.
[2] Kaspar Riesen, Horst Bunke: Approximate graph edit distance computation by means of bipartite graph matching. Image Vision Comput. 27(7): 950-959 (2009)