Figure 6.18. Linear time alignment of two trajectories with different durar tions [484].

Note that the dissimilarity measure d(ti, rj) between T and R is denoted as d(i,j) for simplicity of notation in Eq. 6.49. Hence, the distortion measure assessment will take place along the diagonal straight line of the rectangular (tj, rj) plane shown in Figure 6.18. Linear time normalization implicitly assumes that the temporal trajectory variations are proportional to the duration of the batch (or the number of samples made on each variable). However, since the timing differences between the two batches will be local and not global, a more general time alignment and normalization scheme would be appealing, including the use of nonlinear warping functions that relate the indices of the variables in two trajectory sets to a common "normal" time axis k. Time warping has been developed to deal with these issues by using the principles of dynamic programming (that is why it is called as dynamic time warping) [252, 485, 533].

The objective in time warping is to match the elements of each pattern (trajectory in our case) T and R so as to minimize the discrepancy in each pair of samples. Similar events will be aligned when this is achieved using a nonlinear warping function. This function will shift some feature vectors in time, compress and/or expand others to obtain minimum distances. For each vector pair in T and R, DTW is performed on a M x N grid under a number of constraints. An example of pattern matching between two vectors is shown in Figure 6.19.

Figure 6.19. Nonlinear time warping process details. The point at (5,4) aligns t(5) with r(4).

Figure 6.19. Nonlinear time warping process details. The point at (5,4) aligns t(5) with r(4).

Let the warping function be

C = c(l), c(2),..., c(/c),..., c{K) ■ max(Ar, M) ^ K ^ N + M (6.51)

where each c is a pair of indices to the trajectory elements being matched (position in the grid):

Thus, C can be considered as a model of the time axis fluctuation in a given pattern sequence. For each c(k) we have a cost function or a local distance measure which reflects the discrepancy between the paired samples. There are many definitions of local distance calculation such as Euclidian distance, Mahalanobis distance and Chebyshev norm [252, 441, 485, 533]. A typical local distance is the squared difference between the samples d[c{k)\ = d[i(k),j(k)} = (tm - rm)2. (6.53)

The most commonly used local distance for multivariate data is the weighted quadratic distance d[c(k)} = [T(i(k),p) - R(j(k),p)}Wp[T(i(k),p) - R(j(k),p)]T (6.54)

where Wp is a positive definite weight matrix that shows the relative importance of each variable p.

Was this article helpful?

## Post a comment