1mlib_SignalDTWKScalarPath_Sm1e6d(i3aMLLiIbB)LibrarymFluinbc_tSiiognnsalDTWKScalarPath_S16(3MLIB)
2
3
4

NAME

6       mlib_SignalDTWKScalarPath_S16,  mlib_SignalDTWKScalarPath_F32  - return
7       K-best path on scalar data
8

SYNOPSIS

10       cc [ flag... ] file... -lmlib [ library... ]
11       #include <mlib.h>
12
13       mlib_status mlib_SignalDTWKScalarPath_S16(mlib_s32 *path,
14            mlib_s32 *lpath, mlib_s32 kpath, void *state);
15
16
17       mlib_status mlib_SignalDTWKScalarPath_F32(mlib_s32 *path,
18            mlib_s32 *lpath, mlib_s32 kpath, void *state);
19
20

DESCRIPTION

22       Each of these functions returns K-best path on scalar data.
23
24
25       Assume the reference data are
26
27             r(y), y=1,2,...,N
28
29
30
31       and the observed data are
32
33             o(x), x=1,2,...,M
34
35
36
37       the dynamic time warping is to find a mapping function (a path)
38
39             p(i) = {px(i),py(i)}, i=1,2,...,Q
40
41
42
43       with the minimum distance.
44
45
46       In K-best paths  case,  K  paths  with  the  K  minimum  distances  are
47       searched.
48
49
50       The distance of a path is defined as
51
52                     Q
53             dist = SUM d(r(py(i)),o(px(i))) * m(px(i),py(i))
54                    i=1
55
56
57
58       where  d(r,o) is the dissimilarity between data point/vector r and data
59       point/vector o; m(x,y) is the  path  weighting  coefficient  associated
60       with  path point (x,y); N is the length of the reference data; M is the
61       length of the observed data; Q is the length of the path.
62
63
64       Using L1 norm (sum of absolute differences)
65
66                      L-1
67             d(r,o) = SUM |r(i) - o(i)|
68                      i=0
69
70
71
72       Using L2 norm (Euclidean distance)
73
74                             L-1
75             d(r,o) = SQRT { SUM (r(i) - o(i))**2 }
76                             i=0
77
78
79
80       where L is the length of each data vector.
81
82
83       To scalar data where L=1, the two norms are the same.
84
85             d(r,o) = |r - o| = SQRT {(r - o)**2 }
86
87
88
89       The constraints of dynamic time warping are:
90
91           1.     Endpoint constraints
92
93                        px(1) = 1
94                        1 ≤ py(1) ≤ 1 + delta
95
96                  and
97
98                        px(Q) = M
99                        N-delta ≤ py(Q) ≤ N
100
101
102           2.     Monotonicity Conditions
103
104                        px(i) ≤ px(i+1)
105                        py(i) ≤ py(i+1)
106
107
108           3.     Local Continuity Constraints
109
110                  See Table 4.5 on page 211 in Rabiner and Juang's book.
111
112                  Itakura Type:
113
114                        py
115                        |
116                        *----*----*
117                        |p4  |p1  |p0
118                        |    |    |
119                        *----*----*
120                        |    |p2  |
121                        |    |    |
122                        *----*----*-- px
123                              p3
124
125                  Allowable paths are
126
127                        p1->p0    (1,0)
128                        p2->p0    (1,1)
129                        p3->p0    (1,2)
130
131                  Consecutive (1,0)(1,0) is disallowed. So path p4->p1->p0  is
132                  disallowed.
133
134           4.     Global Path Constraints
135
136                  Due to local continuity constraints, certain portions of the
137                  (px,py) plane are excluded from the region the optimal warp‐
138                  ing path can traverse. This forms global path constraints.
139
140           5.     Slope Weighting
141
142                  See  Equation  4.150-3  on  page  216 in Rabiner and Juang's
143                  book.
144
145
146       A path in (px,py) plane can be represented in chain code. The value  of
147       the chain code is defined as following.
148
149             ============================
150             shift ( x , y ) | chain code
151             ----------------------------
152                 ( 1 , 0 )   |     0
153                 ( 0 , 1 )   |     1
154                 ( 1 , 1 )   |     2
155                 ( 2 , 1 )   |     3
156                 ( 1 , 2 )   |     4
157                 ( 3 , 1 )   |     5
158                 ( 3 , 2 )   |     6
159                 ( 1 , 3 )   |     7
160                 ( 2 , 3 )   |     8
161             ============================
162
163                 py
164                 |
165                 *  8  7  *
166                 |
167                 *  4  *  6
168                 |
169                 1  2  3  5
170                 |
171                 x--0--*--*-- px
172
173
174
175       where  x  marks  the start point of a path segment, the numbers are the
176       values of the chain code for the segment that ends at the point.
177
178
179       In following example, the observed data with 11 data points are  mapped
180       into the reference data with 9 data points
181
182                 py
183                 |
184              9  | * * * * * * * * * *-*
185                 |                  /
186                 | * * * * * * * *-* * *
187                 |              /
188                 | * * * * * * * * * * *
189                 |            /
190                 | * * * * *-* * * * * *
191                 |        /
192                 | * * * * * * * * * * *
193                 |       |
194                 | * * * * * * * * * * *
195                 |      /
196                 | * * * * * * * * * * *
197                 |    /
198                 | * * * * * * * * * * *
199                 |  /
200              1  | * * * * * * * * * * *
201                 |
202                 +------------------------ px
203                   1                   11
204
205
206
207       The chain code that represents the path is
208
209             (2 2 2 1 2 0 2 2 0 2 0)
210
211
212
213       See  Fundamentals  of Speech Recognition by Lawrence Rabiner and Biing-
214       Hwang Juang, Prentice Hall, 1993.
215

PARAMETERS

217       Each of the functions takes the following arguments:
218
219       path     The optimal path.
220
221
222       lpath    The length of the optimal path.
223
224
225       kpath    The path index, 0 ≤ kpath < kbest.
226
227
228       state    Pointer to the internal state structure.
229
230

RETURN VALUES

232       Each of the functions returns MLIB_SUCCESS if successful. Otherwise  it
233       returns MLIB_FAILURE.
234

ATTRIBUTES

236       See attributes(5) for descriptions of the following attributes:
237
238
239
240
241       ┌─────────────────────────────┬─────────────────────────────┐
242       │      ATTRIBUTE TYPE         │      ATTRIBUTE VALUE        │
243       ├─────────────────────────────┼─────────────────────────────┤
244       │Interface Stability          │Committed                    │
245       ├─────────────────────────────┼─────────────────────────────┤
246       │MT-Level                     │MT-Safe                      │
247       └─────────────────────────────┴─────────────────────────────┘
248

SEE ALSO

250       mlib_SignalDTWKScalarInit_S16(3MLIB),            mlib_SignalDTWKScalar‐
251       Init_F32(3MLIB),      mlib_SignalDTWKScalar_S16(3MLIB),       mlib_Sig‐
252       nalDTWKScalar_F32(3MLIB),         mlib_SignalDTWKScalarFree_S16(3MLIB),
253       mlib_SignalDTWKScalarFree_F32(3MLIB), attributes(5)
254
255
256
257SunOS 5.11                        23 May 20m0l7ib_SignalDTWKScalarPath_S16(3MLIB)
Impressum