Different slope constraints result in different forms of dynamic pattern matching that can be classified as either symmetric or asymmetric algo rithms. The two most commonly used ones are Types (c) and (d)

Type (c), asymmetric : w(k) = i(k) - i(k - 1), ¿(0) = 0 (6.76)

Type (d), symmetric : w(k) — i(k) - i(k - 1) + j(k) - j(k — 1),

resulting in asymmetric and symmetric forms, respectively. In the asymmetric form, time normalization is realized by transforming the time axis of a feature vector onto that of the other, resulting in the expansion or compression of the second feature vector. The asymmetric algorithm will map the time index of the test trajectory (T) that is placed on the horizontal axis onto the time index of the reference trajectory (R) that is placed on the vertical axis. As a result of such matching, the optimal path will contain as many points as the test set does (which is N in our example)

Figure 6.27. Global path constraints on the search grid (N x M) [484] for Qmax = 2 and Ko = 2\N - M\ given that (K0 > \i{K) - j(K)|).

Consequently, the optimal path will pass through each point on t but may skip some on r.

A symmetric algorithm, however, will transform both time axes onto a temporarily defined common axis with a common index, k. In this case, the optimal path will go through all the points in both trajectory sets. Furthermore, for the same reference trajectory set, the number of points in the optimal path will be different for each new test trajectory set. Although each test trajectory individually will be synchronized with the reference trajectory, they will not be synchronized with each other, resulting in a set of individually synchronized batch trajectories with unequal batch lengths. If an asymmetric DTW is used, it will skip some points in the test trajectory but will produce synchronized (with reference and each other) batch trajectories having equal length with the reference set. Depending on the choice of the reference set, some of the inconsistent features in T that may cause false alarms in statistical process monitoring will be left out. In order to compromise between the two extremes, solutions that are presented in the following sections have been suggested [270].

Dynamic Programming Solution

Since the search space for optimal path (minimum accumulated distance) can be reduced by imposing local and global constraints, dynamic programming can be used to develop the DTW algorithm. In addition to their contribution on more realistic pattern matching, local and global constraints reduce the search space so that the computational requirements will be lower. Dynamic programming will be used to find a move sequence on the constrained i x j grid under the given local continuity constraints (local transitions) and the boundary conditions (usually fixed end-points) to minimize the following accumulated distance starting from point (1,1) to [i, j):

When point (N, M) is reached, the time normalized distance is calculated to evaluate the performance of the DTW algorithm under the chosen conditions.

Dynamic programming proceeds in phases, the first phase is the forward algorithm and second is the backward tracking (optimal path reconstruction). Assume that the test pattern is placed on the horizontal axis and the reference pattern on the vertical axis. After initialization, for each increment made on i — axis (abscissa), all possible points (i.e., all points within the allowed region) along the j — axis (ordinate) are considered based on the local continuity constraints chosen. For each point, a number of possible predecessors and associated accumulated costs are determined and stored to construct the optimal path at the end such that

where D(Ck) — DA(i.j). Eq. 6.80 defines the accumulated distance that is comprised of the cost of particular point [i(k),j(k)] itself and the cheapest cost path associated with it. The second term in Eq. 6.80 requires a decision on the predecessor. In Table 6.5, dynamic programming recursion equations are summarized for different local continuity constraints when Type (d) slope weighting is used. Note that slope weightings of the paths in Table 6.5 are smoothed according to Figure 6.26. To illustrate the progress of dynamic programming procedure, assume that Type (d) slope weighting (symmetric) in Eq. 6.66 and Type III local continuity constraint (Figures 6.24(c) and 6.25(d)) are used (Figure 6.24).

During the forward phase, transition cost to the accumulated distance at point (i,j) can be found by solving the following simple minimization problem (dynamic programming recursion equation)

'DA(i-2,j-l)+2d{i,j)' DA(i-l,j-l) + Zd{i,j) DA(i-l,j-2) + 2d{i,j)

The local continuity constraints chosen above mean that the point (i,j) can only be reached by either points (i — 2, j — 1), or (j — 1, j — 1) or (i — 1, j — 2) as shown in Figure 6.24(c). To initialize the iterative process, DA(l, 1) can be assigned to 2d(l, 1). The forward phase finishes when point \i(K), j(K)\ is reached and the minimum normalized distance, D*(C), in Eq.6.56 is computed (note that N(w) — i(K) + j(K) for Type (d) slope weighting).

At this point the second phase, which is the reconstruction of the optimal path, starts. Starting from point [i{K),j{K)\ (say i(K) = N and j(K) = M) in the search grid and using the stored information on optimal transitions, first the predecessor of point (N, M) is located, then the predecessor of the latter is identified. This is repeated until point (1,1) is reached. At the end of the second phase, the optimal path is reconstructed and as a consequence pattern indices are matched accordingly.

Example Consider two artificial signals to illustrate the DTW algorithm, r is a (1 x 60) reference signal and t is a (1 x 50) test signal (Figure 6.28(a)). Boundary conditions are assumed as r(0) = i(0) - 0 and j(M) = 60, i(N) = 50. (6.82)

Table 6.5. Accumulated distance formulations used for some of the local constraints for Type (d) slope weighting case [406, 484]


Accumulated Distance Function

Was this article helpful?

0 0

Post a comment