algorithm.psgm
Class PSGM

java.lang.Object
  algorithm.psgm.PSGM

public class PSGM
extends java.lang.Object

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.

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. 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'.

NOTE: keep in mind that during the processing of this algorithm, the two skeletons might get reordered, as the skeleton with the fewer end nodes will always be set as the "first" skeleton.

Field Summary

private org.apache.log4j.Logger	logger logger instance
private SkeletonObject	so1 first skeleton object
private SkeletonObject	so2 second skeleton object

Constructor Summary

PSGM(SkeletonObject so1, SkeletonObject so2)
Constructor.

Method Summary

SkeletonObject	getSo1() Get the first skeleton object.
SkeletonObject	getSo2() Get the second skeleton object.
MatchList	go(Config config) Execute the algorithm.
private void	setSkeletons(SkeletonObject so1, SkeletonObject so2) set the skeletons to be matched.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

logger

private final org.apache.log4j.Logger logger

logger instance

so1

private SkeletonObject so1

first skeleton object

so2

private SkeletonObject so2

second skeleton object

Constructor Detail

PSGM

public PSGM(SkeletonObject so1,
            SkeletonObject so2)
     throws WrongUsageOfAlgorithmException

Constructor. Create a new PSGM instance, with the two SkeletonObjects to be matched.

Parameters:

so1 - the first skeleton object to be matched. Note that the two skeletons might get reordered.

so2 - the second skeleton object to be matched. Note that the two skeletons might get reordered.

Throws:

WrongUsageOfAlgorithmException

Method Detail

go

public MatchList go(Config config)
             throws InvalidSkeletonException,
                    InvalidWeightFunctionGivenException,
                    InvalidConfigParameterException

Execute the algorithm.

Parameters:

config - The configuration parameters for the algorithm

Returns:

a list of found matchings (given by the indices in the skeleton's list of all endnodes)

Throws:

InvalidSkeletonException - if one of the skeleton seems to be broken

InvalidWeightFunctionGivenException - if no valid weight function could be extracted for Hungarian Algorithm

InvalidConfigParameterException

getSo1

public SkeletonObject getSo1()

Get the first skeleton object. Note that the two skeleton objects might have been reordered. No matter, in which order the two skeletons where specified in the constructor, the first skeleton is always the one with lesser end nodes.

Returns:

the first skeleton object to be matched

getSo2

public SkeletonObject getSo2()

Get the second skeleton object. Note that the two skeleton objects might have been reordered. No matter, in which order the two skeletons where specified in the constructor, the second skeleton is always the one with more end nodes.

Returns:

the second skeleton object to be matched

setSkeletons

private void setSkeletons(SkeletonObject so1,
                          SkeletonObject so2)
                   throws WrongUsageOfAlgorithmException

set the skeletons to be matched. The skeletons might get reordered.

the algorithm demands later that the "first" skeleton is the one with lesser endnodes, so we make sure this condition is fullfilled now.

Parameters:

so1 - skeletonobject to be matched

so2 - skeleton object to be matched

Throws:

WrongUsageOfAlgorithmException