Path Similarity Skeleton Graph Matching

An implementation of the skeleton based matching algorithm proposed in Path Similarity Graph Matching.

See:
Description

Packages

algorithm	Package containing all classes that are part of establishing correspondences between two skeletons' end nodes.
algorithm.matching	Package containing all classes that are used to establish a final matching between two skeletons' end nodes.
algorithm.psgm	All classes used for the computation of two skeletons' endnode similarities, as described in the paper.
config	Package containing all classes used to configure the execution of the algorithm.
exception	Package containing all application specific exceptions.
geometry	Package containing all basic data structures.
geometry.object	Package containing all skeleton data structures needed.
gui	Package containing all graphical user interfaces.
io.loader	Contains all classes used to load 2D/3D data from the input files.
io.loader.load2D	Contains all classes used to load a 2D skeleton from the input files.
io.loader.load2D.contours	Containing all data structures to represent contours.
io.loader.load3D	Contains all classes needed to load a 3D-skeleton.
io.loader.shared	Package containing all classes needed to load 2D skeletons as well as 3D skeletons.
io.out	Classes needed to save skeletons to the file system.
io.visualize	Classes needed to visualize/show skeletons and skeleton matching results.
main
retrieval	Classes needed to perform similarity searches in a database and mapping database entries to java classes.
test.algorithm	Test basic functionalities of the algorithm implementations.
test.io	Test classes for io functionalities, such as skeleton parsers and visualizers.
test.retrieval	Test classes for retrieval scenarios.
utils	Contains simple helper classes.

An implementation of the skeleton based matching algorithm proposed in Path Similarity Graph Matching.

The goal is to match salient nodes (more specifically: skeleton end nodes) in two objects in that way, that these end nodes are the most similar as possible and therefore, the costs to match the objects get as less as possible. The cheaper the matching, the more similar are the objects. The results thus is a one-to-one assignment of end nodes of the two skeletons, and as well the total costs of these assignments.

Input of the algorithm is a 2D or 3D shape with the corresponding skeleton.

Here is an overview of the algorithm:

• Sample all skeleton paths (see SkeletonPath) in both skeleton objects in M equidistant points. For each of these points, store the distance to the boundary in an array, called the skeleton path vector.
• For each pair of end nodes in the two skeletons, calculate the matching costs between these two end nodes. Proceed as follows:
  • Create a path distance matrix for these two end nodes. These matrices contain information about the dissimilarity between all skeleton paths emanating from the two skeleton end nodes. The dissimilarity between two skeleton paths is based on the dissimilarity between their skeleton path vectors.
  • Based on this path distance matrix, the total costs to match two end nodes A and B can be estimated by searching the cheapest path through the matrix, using OSBv5. The idea is, the more similar the emanating paths from two end nodes are, the more similar are the two end nodes.
• With the knowledge of the costs to match each end node in skeleton G to each end node in skeleton G', a cost matrix can be built. The cost matrix is used as input weight function for the Hungarian Algorithm (see HungarianAlgorithm which establishes a one-to-one correspondence between all end nodes in G and G'.

For installation instruction, see the README file that comes with the code.