algorithm.psgm
Class OSBv5

java.lang.Object
  algorithm.psgm.OSBv5

public class OSBv5
extends java.lang.Object

This is a java adaption of Latecki's OSBv5 matlab code

Originally, the OSB (Optimal Subsequence Bijection) was developped to match time series. Input were originally two sequences of points a and b, and the goal was to find subsequences a' and b' of a and b, so that a' best matches b'. Skipping of elements is allowed in both series, but skipping elements in the first series is punished.

The main idea of OSB is to create a distance matrix for the two series. Then, the "cheapest" path through that matrix is searched, resulting in an optimal correspondence between the elements in a and b. The path cost is than given by the costs (given by the distance matrix) for matching the single elements to the corresponding elements.

In the context of skeleton matching, OSB can be used to calculate the total costs to match one end node in the one skeleton to one end node in the other skeleton. Input is then the path distance matrix for the two skeleton end nodes, and the "cheapest" path through the path distance matrix is searched. As the path distance matrix encodes information about the emanating skeleton paths, it is a proper mean to estimate the dissimilarity between the two end nodes it is specified for. The assumption is: The more similar one or more emanating paths from the two end nodes are, the more similar are the endnodes.

Field Summary

private static org.apache.log4j.Logger

logger logger

Constructor Summary

OSBv5()

Method Summary

private static MatchList	findDAG(double[][] matx, int warpwin, int queryskip, int targetskip, double jumpcost, double[][] original) find the shortest path through a given matrix.
static double	getJumpCost(double[][] p) get the cost for skipping rows.
static MatchList	getMatchingCosts(double[][] matx) get the matching costs for a given distance matrix, that is, the "cheapest" path through that matrix.
private static double[][]	prepareMatrix(double[][] matx) Before applying OSB, the matrix should be prepared: To allow skipping the first and last elements in the matrix, additional rows and columns are added.

Methods inherited from class java.lang.Object

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

Field Detail

logger

private static org.apache.log4j.Logger logger

logger

Constructor Detail

OSBv5

public OSBv5()

Method Detail

getMatchingCosts

public static MatchList getMatchingCosts(double[][] matx)

get the matching costs for a given distance matrix, that is, the "cheapest" path through that matrix. There are no restrcitions on the distance used in the matrix.

Parameters:

matx - the matrix to get the costs for

prepareMatrix

private static double[][] prepareMatrix(double[][] matx)

Before applying OSB, the matrix should be prepared: To allow skipping the first and last elements in the matrix, additional rows and columns are added. add one row at the top and at the bottom, add one column at the left and at the right. the upper left cell and bottom right cell are filled with zero, all other new cells with Infinity.

Parameters:

matx - the matrix to be prepared

Returns:

ready-to-use matrix

findDAG

private static MatchList findDAG(double[][] matx,
                                 int warpwin,
                                 int queryskip,
                                 int targetskip,
                                 double jumpcost,
                                 double[][] original)

find the shortest path through a given matrix.

Parameters:

matx - the matrix to find the shortest path through

warpwin - the warp window, i.e. the maximal difference between row index and column index

queryskip - a restriction on how many consecutive elements of sequence t1 (= rows in the matrix) can be skipped

targetskip - a restriction on how many consecutive elements of sequence t2 (= columns in the matrix) can be skipped

jumpcost - the costs to punish skipping rows

original - the original (unprepared) matrix

Returns:

the path costs through the matrix

getJumpCost

public static double getJumpCost(double[][] p)

get the cost for skipping rows.

Parameters:

p - the cost matrix

Returns:

jumpcost