The Dynamic time warping is applied for time normalization. As shown in the diagram, two different signals with $Tx$ and $Ty$ time instants, are time-normalized to have $T$ time instants. $\phi$ is the warping function.

A path P is represented as having increments $p_i$, and $q_i$ along their respective axis. These incremental values are usually 1 or 2.

$$P \to (p_1,q_1)(p_2,q_2)...(p_T,q_T)$$

Source - Fundamentals of Speech Recognition (Rabiner)

The warping functions are given by

$$ \phi _x(k) = \sum _{i=1}^{k} p_i $$

$$ \phi _y(k) = \sum _{i=1}^{k} q_i $$

There are $T_x . T_y$ number of grid points in the 2D space. You can visualize the path as any traversal from (1,1) to (Tx,Ty). Local continuity constraints like $\phi _x(k+1) - \phi _x(k) \leq 1$ or $2$ make sure that we do not omit any important information-bearing sound segment.

Up to this point, things make sense. However, I could not reason out the inequities (at the last), that determine the area within which the optimal path is to be found.

The allowable regions for each of the local constraints are defined using these two parameters.

$$Q_{max} = \max_l \left [\frac{\sum_{i=1}^{T_l} p_i^{(l)}}{\sum_{i=1}^{T_l} q_i^{(l)}} \right ]$$

$$Q_{min} = \min_l \left [\frac{\sum_{i=1}^{T_l} p_i^{(l)}}{\sum_{i=1}^{T_l} q_i^{(l)}} \right ]$$

Here, $l$ signifies the index of allowed path $P$ and $T_l$ is the total number of moves in that path.

Then, the global path constraints are given by

$$ 1+\frac{[\phi x(k) - 1]}{Q{max}} \leq \phi y(k) \leq 1 + Q{max}\cdot [\phi _x(k) - 1] $$

$$ T_y + Q{max}\cdot [\phi _x(k) - Tx] \leq \phi y(k) \leq T_y+\frac{[\phi x(k) - T_x]}{Q{max}} $$

How do you prove these constraints?


1 Answer 1


After some thought, I see that $Q_{max}$ and $Q_{min}$ are to be interpreted as slopes. Here is the diagram that shows the area bounded by 4 lines (when the inequalities become equal at extremes).

Source- Fundamentals of Speech Recognition (Rabiner)

$Q_{max}$ and $Q_{min}$ are $1/tan$ in nature. This is because the increments $p_i$ and $q_i$ are along x-axis and y-axis respectively. Hence $Q_{max}$ is capturing average slope value along that path, but in inverse.

Remembered that any line takes the form

$$ y = m \cdot x + c $$

Why not reformulate it this way? (We can always adjust c' accordingly)

$$ y = m \cdot (x - c1) + c' $$

This should be useful when I already know for fact that the start point is $(1,1)$ and end is $(T_x,T_y)$.

Considering the first global path constraint.

$$ 1+\frac{[\phi _x(k) - 1]}{Q_{max}} \leq \phi _y(k) \leq 1 + Q_{max}\cdot [\phi _x(k) - 1] $$

At its extremes, we have two equations ; both sharing $(1,1)$

$$ 1+\frac{[\phi _x(k) - 1]}{Q_{max}} = \phi _y(k) $$

$$ \phi _y(k) = 1 + Q_{max}\cdot [\phi _x(k) - 1] $$

Given its slope and just one coordinate, the y-intercept is findable. For $(1,1)$ we verify its correctness by substituting $\phi _x(k) = 1$ and we indeed get $\phi _y(k)$ as 1.

I expected the second equation to be $$ \phi _y(k) = 1 + \frac {1}{Q_{min}} \cdot [\phi _x(k) - 1] $$

But it makes sense that $$ Q_{min} = \frac {1}{Q_{max}} $$

Similarly, the second global path constraint gives us another pair of lines; both sharing $(T_{x},T_{y})$

$$ T_y + Q{max}\cdot [\phi _x(k) - Tx] = \phi y(k) $$

$$ \phi y(k) = T_y+\frac{[\phi x(k) - T_x]}{Q{max}} $$

Finally, when we look at the path that is outside this region, we see that it starts with a high slope but then has to flatten out quick so as to meet $(T_{x},T_{y})$ in time. Its average slope could not be higher than $Q_{max}$. Such a path shape is also unreasonable.

  • $\begingroup$ I have to confess that I really cannot decode any of this. I presume that the ratio $\frac{T_y}{T_x}$ is your time-scaling ratio. But none of the rest of this is anything I can decode. $\endgroup$ Commented Feb 29 at 17:05
  • $\begingroup$ To help in my level best. DTW is a dissimilarity measure between two given signals as you know. There is no scaling ratio used but warping function which "scales" differently to different small increment paths. And then the distance (dissimilarity) is measured along that optimal path (which is to be found in the area bounded by the lines mentioned in the answer). Also, here we do not calculate distance between magnitudes of signal points, but between their spectral vector representation (Like LPC). For every frame (25ms), we represent it with LPC features which sit along the axes. $\endgroup$ Commented Mar 1 at 3:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.