1mlib_SignalDTWKVector_S16(3mMeLdIiBa)Lib Library Funcmtliiobn_sSignalDTWKVector_S16(3MLIB)
2
3
4
6 mlib_SignalDTWKVector_S16 - perform dynamic time warping for K-best
7 paths on vector data
8
10 cc [ flag... ] file... -lmlib [ library... ]
11 #include <mlib.h>
12
13 mlib_status mlib_SignalDTWKVector_S16(mlib_d64 *dist,
14 const mlib_s16 **dobs, mlib_s32 lobs, mlib_s32 sobs,
15 void *state);
16
17
19 The mlib_SignalDTWKVector_S16() function performs dynamic time warping
20 for K-best paths on vector data.
21
22
23 Assume the reference data are
24
25 r(y), y=1,2,...,N
26
27
28
29 and the observed data are
30
31 o(x), x=1,2,...,M
32
33
34
35 the dynamic time warping is to find a mapping function (a path)
36
37 p(i) = {px(i),py(i)}, i=1,2,...,Q
38
39
40
41 with the minimum distance.
42
43
44 In K-best paths case, K paths with the K minimum distances are
45 searched.
46
47
48 The distance of a path is defined as
49
50 Q
51 dist = SUM d(r(py(i)),o(px(i))) * m(px(i),py(i))
52 i=1
53
54
55
56 where d(r,o) is the dissimilarity between data point/vector r and data
57 point/vector o; m(x,y) is the path weighting coefficient associated
58 with path point (x,y); N is the length of the reference data; M is the
59 length of the observed data; Q is the length of the path.
60
61
62 Using L1 norm (sum of absolute differences)
63
64 L-1
65 d(r,o) = SUM |r(i) - o(i)|
66 i=0
67
68
69
70 Using L2 norm (Euclidean distance)
71
72 L-1
73 d(r,o) = SQRT { SUM (r(i) - o(i))**2 }
74 i=0
75
76
77
78 where L is the length of each data vector.
79
80
81 To scalar data where L=1, the two norms are the same.
82
83 d(r,o) = |r - o| = SQRT {(r - o)**2 }
84
85
86
87 The constraints of dynamic time warping are:
88
89 1. Endpoint constraints
90
91 px(1) = 1
92 1 ≤ py(1) ≤ 1 + delta
93
94 and
95
96 px(Q) = M
97 N-delta ≤ py(Q) ≤ N
98
99
100 2. Monotonicity Conditions
101
102 px(i) ≤ px(i+1)
103 py(i) ≤ py(i+1)
104
105
106 3. Local Continuity Constraints
107
108 See Table 4.5 on page 211 in Rabiner and Juang's book.
109
110 Itakura Type:
111
112 py
113 |
114 *----*----*
115 |p4 |p1 |p0
116 | | |
117 *----*----*
118 | |p2 |
119 | | |
120 *----*----*-- px
121 p3
122
123 Allowable paths are
124
125 p1->p0 (1,0)
126 p2->p0 (1,1)
127 p3->p0 (1,2)
128
129 Consecutive (1,0)(1,0) is disallowed. So path p4->p1->p0 is
130 disallowed.
131
132 4. Global Path Constraints
133
134 Due to local continuity constraints, certain portions of the
135 (px,py) plane are excluded from the region the optimal warp‐
136 ing path can traverse. This forms global path constraints.
137
138 5. Slope Weighting
139
140 See Equation 4.150-3 on page 216 in Rabiner and Juang's
141 book.
142
143
144 A path in (px,py) plane can be represented in chain code. The value of
145 the chain code is defined as following.
146
147 ============================
148 shift ( x , y ) | chain code
149 ----------------------------
150 ( 1 , 0 ) | 0
151 ( 0 , 1 ) | 1
152 ( 1 , 1 ) | 2
153 ( 2 , 1 ) | 3
154 ( 1 , 2 ) | 4
155 ( 3 , 1 ) | 5
156 ( 3 , 2 ) | 6
157 ( 1 , 3 ) | 7
158 ( 2 , 3 ) | 8
159 ============================
160
161 py
162 |
163 * 8 7 *
164 |
165 * 4 * 6
166 |
167 1 2 3 5
168 |
169 x--0--*--*-- px
170
171
172
173 where x marks the start point of a path segment, the numbers are the
174 values of the chain code for the segment that ends at the point.
175
176
177 In following example, the observed data with 11 data points are mapped
178 into the reference data with 9 data points
179
180 py
181 |
182 9 | * * * * * * * * * *-*
183 | /
184 | * * * * * * * *-* * *
185 | /
186 | * * * * * * * * * * *
187 | /
188 | * * * * *-* * * * * *
189 | /
190 | * * * * * * * * * * *
191 | |
192 | * * * * * * * * * * *
193 | /
194 | * * * * * * * * * * *
195 | /
196 | * * * * * * * * * * *
197 | /
198 1 | * * * * * * * * * * *
199 |
200 +------------------------ px
201 1 11
202
203
204
205 The chain code that represents the path is
206
207 (2 2 2 1 2 0 2 2 0 2 0)
208
209
210
211 See Fundamentals of Speech Recognition by Lawrence Rabiner and Biing-
212 Hwang Juang, Prentice Hall, 1993.
213
215 The function takes the following arguments:
216
217 dist The distances of the K-best paths.
218
219
220 dobs The observed data array.
221
222
223 lobs The length of the observed data array.
224
225
226 sobs The scaling factor of the observed data array, where
227 actual_data = input_data * 2**(-scaling_factor).
228
229
230 state Pointer to the internal state structure.
231
232
234 The function returns MLIB_SUCCESS if successful. Otherwise it returns
235 MLIB_FAILURE.
236
238 See attributes(5) for descriptions of the following attributes:
239
240
241
242
243 ┌─────────────────────────────┬─────────────────────────────┐
244 │ ATTRIBUTE TYPE │ ATTRIBUTE VALUE │
245 ├─────────────────────────────┼─────────────────────────────┤
246 │Interface Stability │Committed │
247 ├─────────────────────────────┼─────────────────────────────┤
248 │MT-Level │MT-Safe │
249 └─────────────────────────────┴─────────────────────────────┘
250
252 mlib_SignalDTWKVectorInit_S16(3MLIB), mlib_SignalDTWKVector_S16(3MLIB),
253 mlib_SignalDTWKVectorPath_S16(3MLIB), mlib_SignalDTWKVector‐
254 Free_S16(3MLIB), attributes(5)
255
256
257
258SunOS 5.11 23 May 2007 mlib_SignalDTWKVector_S16(3MLIB)