mlib_SignalDTWKScalarPath_mediaLibBLibrarymlib_SignalDTWKScalarPath_S16(3MLIB)NAME
mlib_SignalDTWKScalarPath_S16, mlib_SignalDTWKScalarPath_F32 - return
K-best path on scalar data
SYNOPSIS
cc [ flag... ] file... -lmlib [ library... ]
#include <mlib.h>
mlib_status mlib_SignalDTWKScalarPath_S16(mlib_s32 *path,
mlib_s32 *lpath, mlib_s32 kpath, void *state);
mlib_status mlib_SignalDTWKScalarPath_F32(mlib_s32 *path,
mlib_s32 *lpath, mlib_s32 kpath, void *state);
DESCRIPTION
Each of these functions returns K-best path on scalar 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 warp‐
ing path can traverse. 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
Each of the functions takes the following arguments:
path The optimal path.
lpath The length of the optimal path.
kpath The path index, 0 ≤ kpath < kbest.
state Pointer to the internal state structure.
RETURN VALUES
Each of the functions 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 │Committed │
├─────────────────────────────┼─────────────────────────────┤
│MT-Level │MT-Safe │
└─────────────────────────────┴─────────────────────────────┘
SEE ALSOmlib_SignalDTWKScalarInit_S16(3MLIB), mlib_SignalDTWKScalar‐
Init_F32(3MLIB), mlib_SignalDTWKScalar_S16(3MLIB), mlib_Sig‐
nalDTWKScalar_F32(3MLIB), mlib_SignalDTWKScalarFree_S16(3MLIB),
mlib_SignalDTWKScalarFree_F32(3MLIB), attributes(5)SunOS 5.10 23 May 2mlib_SignalDTWKScalarPath_S16(3MLIB)
