Skip to content
Snippets Groups Projects
README 3.02 KiB
Newer Older
Miguel's avatar
Miguel committed
Graph Matching using Monte Carlo tree search (GMMC)

Miguel's avatar
Miguel committed
GMMC is 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 the
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 efficient --
it 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.

The available code matches geometric graphs. It currently accepts SWC files as
input, which are commonly used in medical imaging.
Miguel's avatar
Miguel committed

Miguel's avatar
Miguel committed
To clone this repository use the command

`git clone https://gitlab.fel.cvut.cz/biomedical-imaging-algorithms/gmmc_code`
Miguel's avatar
Miguel committed

or go to the Repository tab and download the code using a compressed file.

Miguel's avatar
Miguel committed
To compile the mex file, use the compile_gmmc_mex.m script. The code uses
has the following dependencies:

. Eigen library (http://eigen.tuxfamily.org/)

In compile_gmmc_mex.m, change the variable eigen_dir to provide the path
of Eigen. Then run the script to compile the mex function.

An example of how to run the function is provided in the script
run_gmmc_mex.m.

Miguel's avatar
Miguel committed
The current code loads the graphs from SWC files with a single tree in each
file. You must implement your own functions if you want the input to be read
from a different format. The internal graph representation is a MATLAB structure
with the following fields:
Miguel's avatar
Miguel committed

nodes:      n x D matrix with vertices of the graph
edges:      1 x |E| array of structures with the following format:
    endpoints:  1 x 2 array with indices of respective endpoint vertices
    path:       D x m matrix with path of the edge
    cumd:       1 x m array with cumulative distance of the path
    length:     total length of the path
dA:         n x n sparse adjacent matrix of the graph
fnodes:     n x 1 array with labels for each vertex
hm:         n x n hop matrix of the graph
sdA:        n x n matrix with the superedge which connects the vertices with given indices
superedges: 1 x |S| array of structures with the following format:
    path:       1 x s+1 array with indices of the vertices through which the superedge has its path
    edgeid:     1 x s array with indices of the respective edges of the superedge
    length:     total length of the superedge
    desc:       1 x |Omega| path descriptor

IMPORTANT NOTE: the superedges array is ordered by priority of exploration.
In our case, we take the 'default' order, which first gives priority to
superedges with the least amount of edges and second to longer superedges.