Skip to content


Jan Kybic
Geometric Graph Matching Using Monte Carlo Tree Search
On 2018-03-13 11:00 at G205
This short talk will briefly present the contents of our article:

Pinheiro M. A., Kybic J. and Fua P. "Geometric Graph Matching Using Monte Carlo
Tree Search." Trans. Pattern Analysis Machine Intelligence, vol. 39, no. 11,
2171-2185, 2017.


We present an efficient matching method for generalized geometric graphs. 
Such graphs consist of vertices in space connected by curves and can represent 
many real world structures such as road networks in remote sensing, or vessel
networks in medical imaging. Graph matching can be used for very fast and
possibly multimodal registration of images of these structures. We formulate
matching problem as a single player game solved using Monte Carlo Tree Search,
which automatically balances exploring new possible matches and extending
existing matches. Our method can handle partial matches, topological
differences, geometrical distortion, does not use appearance information and
does not require an initial alignment. Moreover, our method is very
can match graphs with thousands of nodes, which is an order of magnitude better
than the best competing method, and the matching only takes a few seconds.
Back to the list