algorithm.matching
Class OSBfinalMatching

java.lang.Object
  algorithm.matching.OSBfinalMatching

All Implemented Interfaces:

MatchingAlgorithm

public class OSBfinalMatching
extends java.lang.Object
implements MatchingAlgorithm

Compute the final matching between two skeletons by applying OSBv5 in multiple iterations.

The advantage of OSBfinalMatching over HungarianAlgorithm is that it is able to skip elements in the cost matrix. But this advantage come with the requirement that the end nodes have to be ordered in a meaningful way to apply the OSB function.

Thus, the end nodes are ordered according to their path length to the two start nodes. Based on this order, the cost matrix can be built. Of course the process has to be repeated for all combinations of end nodes.

Field Summary

private org.apache.log4j.Logger	logger logger instance
private SkeletonObject	so1 the first skeleton to be matched
private SkeletonObject	so2 the second skeleton to be matched

Constructor Summary

OSBfinalMatching(SkeletonObject so1, SkeletonObject so2)
Constructor.

Method Summary

MatchList	computeAssignments(double[][] costs, Config config) Compute the assignments for the given cost matrix.
private double[][]	getCostMatrix(double[][] costs, java.util.List<SkeletonNode> orderedEndnodes1, java.util.List<SkeletonNode> orderedEndnodes2, PossibleMatchList possibleMatchings) Get the matching cost matrix as input for OSB function.
private PossibleMatchList	getPossibleMatchings(double[][] costs) Get all "imaginary" matchings that are possible.
private java.util.List<SkeletonNode>	orderEndNodes(SkeletonObject so, SkeletonNode node) Order the skeleton's end nodes according to their distance to the specified node, measured by the length of the skeleton path between the two nodes.

Methods inherited from class java.lang.Object

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

Field Detail

so1

private SkeletonObject so1

the first skeleton to be matched

so2

private SkeletonObject so2

the second skeleton to be matched

logger

private org.apache.log4j.Logger logger

logger instance

Constructor Detail

OSBfinalMatching

public OSBfinalMatching(SkeletonObject so1,
                        SkeletonObject so2)

Constructor. Setting the member variables, the two skeletons.

Parameters:

so1 - first skeleton to be matched

so2 - second skeleton to be matched

Method Detail

computeAssignments

public MatchList computeAssignments(double[][] costs,
                                    Config config)
                             throws InvalidWeightFunctionGivenException,
                                    InvalidSkeletonException

Description copied from interface: MatchingAlgorithm

Compute the assignments for the given cost matrix. Returned is a matchlist containing the indices in the cost matrix for the matched elements.

Specified by:

computeAssignments in interface MatchingAlgorithm

Parameters:

costs - the cost matrix

config - the configuration parameters for this algorithm

Returns:

matchlist, containing the "cheapaest" matching

Throws:

InvalidWeightFunctionGivenException

InvalidSkeletonException

getCostMatrix

private double[][] getCostMatrix(double[][] costs,
                                 java.util.List<SkeletonNode> orderedEndnodes1,
                                 java.util.List<SkeletonNode> orderedEndnodes2,
                                 PossibleMatchList possibleMatchings)
                          throws InvalidSkeletonException

Get the matching cost matrix as input for OSB function. For each combination of end nodes in the two skeletons, a different cost matrix has to be constructed, as the order of the end nodes must be adjusted.

Parameters:

costs - the original cost matrix

orderedEndnodes1 - - the list of end nodes of so1, ordered according to their distance to the first start node (which is the first entry in the parameter orderedEndnodes1

orderedEndnodes2 - - the list of end nodes of so2, ordered according to their distance to the second start node (which is the first entry in the parameter orderedEndnodes2

possibleMatchings - - the list of all possible matchings in the two skeletons

Returns:

cost matrix, built based on the order of the end nodes

Throws:

InvalidSkeletonException - if one of the skeletons seems to be broken

orderEndNodes

private java.util.List<SkeletonNode> orderEndNodes(SkeletonObject so,
                                                   SkeletonNode node)
                                            throws InvalidSkeletonException

Order the skeleton's end nodes according to their distance to the specified node, measured by the length of the skeleton path between the two nodes.

Parameters:

so - the skeleton object

node - the "start node"

Returns:

list of ordered nodes

Throws:

InvalidSkeletonException

getPossibleMatchings

private PossibleMatchList getPossibleMatchings(double[][] costs)

Get all "imaginary" matchings that are possible.

Parameters:

costs - original cost matrix

Returns:

list of all possible matchings