mlib_SignalDTWVectorPath_F32(3MLIB)			    mediaLib Library Functions			       mlib_SignalDTWVectorPath_F32(3MLIB)

NAME

       mlib_SignalDTWVectorPath_F32 - perform dynamic time warping on vector data

SYNOPSIS

       cc [ flag... ] file... -lmlib [ library... ]
       #include <mlib.h>

       mlib_status  mlib_SignalDTWVectorPath_F32(mlib_d64  *dist,  mlib_s32  *path,  mlib_s32  *lpath,	const mlib_f32 **dobs, mlib_s32 lobs, void
       *state);

DESCRIPTION

       The mlib_SignalDTWVectorPath_F32() function performs dynamic time warping on vector data.

       Assume the reference data are

	   r(y), y=1,2,...,N

       and the observed data are

	   o(x), x=1,2,...,M

       the dynamic time warping is to find a mapping function (a path)

	   p(i) = {px(i),py(i)}, i=1,2,...,Q

       with the minimum distance.

       In K-best paths case, K paths with the K minimum distances are searched.

       The distance of a path is defined as

		   Q
	   dist = SUM d(r(py(i)),o(px(i))) * m(px(i),py(i))
		  i=1

       where d(r,o) is the dissimilarity between data point/vector r and data point/vector o; m(x,y) is the path weighting coefficient	associated
       with path point (x,y); N is the length of the reference data; M is the length of the observed data; Q is the length of the path.

       Using L1 norm (sum of absolute differences)

		    L-1
	   d(r,o) = SUM |r(i) - o(i)|
		    i=0

       Using L2 norm (Euclidean distance)

			   L-1
	   d(r,o) = SQRT { SUM (r(i) - o(i))**2 }
			   i=0

       where L is the length of each data vector.

       To scalar data where L=1, the two norms are the same.

	   d(r,o) = |r - o| = SQRT {(r - o)**2 }

       The constraints of dynamic time warping are:

       1.  Endpoint constraints

	       px(1) = 1
	       1 <= py(1) <= 1 + delta

	   and

	       px(Q) = M
	       N-delta <= py(Q) <= N

       2.  Monotonicity Conditions

	       px(i) <= px(i+1)
	       py(i) <= py(i+1)

       3.  Local Continuity Constraints

	   See Table 4.5 on page 211 in Rabiner and Juang's book.

	   Itakura Type:

	       py
	       |
	       *----*----*
	       |p4  |p1  |p0
	       |    |	 |
	       *----*----*
	       |    |p2  |
	       |    |	 |
	       *----*----*-- px
		     p3

	   Allowable paths are

	       p1->p0	 (1,0)
	       p2->p0	 (1,1)
	       p3->p0	 (1,2)

	   Consecutive (1,0)(1,0) is disallowed. So path p4->p1->p0 is disallowed.

       4.  Global Path Constraints

	   Due	to  local  continuity constraints, certain portions of the (px,py) plane are excluded from the region the optimal warping path can
	   transverse. This forms global path constraints.

       5.  Slope Weighting

	   See Equation 4.150-3 on page 216 in Rabiner and Juang's book.

       A path in (px,py) plane can be represented in chain code. The value of the chain code is defined as following.

	   ============================
	   shift ( x , y ) | chain code
	   ----------------------------
	       ( 1 , 0 )   |	 0
	       ( 0 , 1 )   |	 1
	       ( 1 , 1 )   |	 2
	       ( 2 , 1 )   |	 3
	       ( 1 , 2 )   |	 4
	       ( 3 , 1 )   |	 5
	       ( 3 , 2 )   |	 6
	       ( 1 , 3 )   |	 7
	       ( 2 , 3 )   |	 8
	   ============================

	       py
	       |
	       *  8  7	*
	       |
	       *  4  *	6
	       |
	       1  2  3	5
	       |
	       x--0--*--*-- px

       where x marks the start point of a path segment, the numbers are the values of the chain code for the segment that ends at the point.

       In following example, the observed data with 11 data points are mapped into the reference data with 9 data points

	       py
	       |
	    9  | * * * * * * * * * *-*
	       |		  /
	       | * * * * * * * *-* * *
	       |	      /
	       | * * * * * * * * * * *
	       |	    /
	       | * * * * *-* * * * * *
	       |	/
	       | * * * * * * * * * * *
	       |       |
	       | * * * * * * * * * * *
	       |      /
	       | * * * * * * * * * * *
	       |    /
	       | * * * * * * * * * * *
	       |  /
	    1  | * * * * * * * * * * *
	       |
	       +------------------------ px
		 1		     11

       The chain code that represents the path is

	   (2 2 2 1 2 0 2 2 0 2 0)

       See Fundamentals of Speech Recognition by Lawrence Rabiner and Biing-Hwang Juang, Prentice Hall, 1993.

PARAMETERS

       The function takes the following arguments:

       dist	       The distance of the optimal path.

       path	       The optimal path.

       lpath	       The length of the optimal path.

       dobs	       The observed data array.

       lobs	       The length of the observed data array.

       state	       Pointer to the internal state structure.

RETURN VALUES

       The function returns MLIB_SUCCESS if successful. Otherwise it returns MLIB_FAILURE.

ATTRIBUTES

       See attributes(5) for descriptions of the following attributes:

       +-----------------------------+-----------------------------+
       |      ATTRIBUTE TYPE	     |	    ATTRIBUTE VALUE	   |
       +-----------------------------+-----------------------------+
       |Interface Stability	     |Evolving			   |
       +-----------------------------+-----------------------------+
       |MT-Level		     |MT-Safe			   |
       +-----------------------------+-----------------------------+

SEE ALSO

       mlib_SignalDTWVectorInit_F32(3MLIB),    mlib_SignalDTWVector_F32(3MLIB),     mlib_SignalDTWVectorPath_F32(3MLIB),     mlib_SignalDTWVector-
       Free_F32(3MLIB), attributes(5)

SunOS 5.10							    18 Nov 2004 			       mlib_SignalDTWVectorPath_F32(3MLIB)