DynamicTimeWarping - Maple Help
For the best experience, we recommend viewing online help using Google Chrome or Microsoft Edge.

SignalProcessing

 DynamicTimeWarping
 matches two signals

 Calling Sequence DynamicTimeWarping( signal1, signal2, options )

Parameters

 signal1, signal2 - 1-D rtables or lists of data of type complexcons

Options

 • compiled: Either true or false, specifies if auxiliary procedures are to be compiled if they are currently uncompiled. The default is false.
 • method: Either standard or pruning, specifies the algorithm used. The default is pruning.
 • metric: One of canberra, chebyshev, entropy, euclidean, and taxicab, specifies the metric used when computing the optimal path. The default is taxicab.
 • radius: Either a non-negative integer or infinity, specifies the index radius used when computing the optimal path. The default is infinity.
 • unwarpedplotoptions: Additional plot options to be passed when creating the plot(s) of the original signals. The default is [].
 • unwarpedplotimaginaryoptions: Additional plot options to be passed when creating the plot of the imaginary parts of the original signals when they are complex. Note unwarpedplotoptions is applied first, followed by unwarpedplotimaginaryoptions. The default is [].
 • unwarpedplotrealoptions: Additional plot options to be passed when creating the plot of the real parts of the original signals when they are complex. Note unwarpedplotoptions is applied first, followed by unwarpedplotrealoptions. The default is [].
 • warpedplotoptions: Additional plot options to be passed when creating the plot(s) of the time-warped signals. The default is [].
 • warpedplotimaginaryoptions: Additional plot options to be passed when creating the plot of the imaginary parts of the time-warped signals when they are complex. Note warpedplotoptions is applied first, followed by warpedplotimaginaryoptions. The default is [].
 • warpedplotrealoptions: Additional plot options to be passed when creating the plot of the real parts of the time-warped signals when they are complex. Note warpedplotoptions is applied first, followed by warpedplotrealoptions. The default is [].
 • warpingpathplotoptions: Additional plot options to be passed when creating the plot of the time-warping path. The default is [].
 • warpingvectorsplotoptions: Additional plot options to be passed when creating the plot of the time-warping Vectors. The default is [].
 • output: The type of output. Let $X$ and $Y$ be, respectively, signal1 and signal2, and let  $m$ and $n$ be their respective sizes. The supported options are:
 – costmatrix: Matrix, of datatype float[8], with element ${C}_{i,j}$ representing the cost (with respect to metric) of matching ${X}_{i}$ with ${Y}_{j}$.
 – cost: The cost of matching ${X}_{m}$ to ${Y}_{n}$, that is, ${C}_{m,n}$, where $C$ is the cost Matrix.
 – rmse: The root-mean-square (RMS) error between $U$ (the time-warped version of $X$) and $V$ (the time-warped version of $Y$).
 – signal1: Vector, of size $m$ and datatype float[8] or complex[8], containing the first original signal $X$.
 – signal2: Vector, of size $n$ and datatype float[8] or complex[8], containing the second original signal $Y$.
 – size: The size $k$ of the time-warped signals.
 – unwarpedplot: Plot of the original signals.
 – warpedplot: Plot of the time-warped signals.
 – warpedsignal1: Vector, of size $k$ and datatype float[8] or complex[8], containing the first time-warped signal $U$.
 – warpedsignal2: Vector, of size $k$ and datatype float[8] or complex[8], containing the second time-warped signal $V$.
 – warpingpathplot: Plots of the path which time-warps $X$ to $U$ and $Y$ to $V$ and the time-warping Vectors $G$ and $H$.
 – warpingvector1: Vector, of size $k$ and datatype integer[4], containing the indices $G$ of $X$ (with repeats) which are used to create $U$.
 – warpingvector2: Vector, of size $k$ and datatype integer[4], containing the indices $H$ of $Y$ (with repeats) which are used to create $V$.
 – record: Returns a record with the previous options.
 – list of any of the above options: Returns an expression sequence with the corresponding outputs, in the same order.
 The default is [warpedsignal1,warpedsignal2].

Description

 • The DynamicTimeWarping command takes two signals $X$ and $Y$, of respective size $m$ and $n$, and determines the time-warped signals $U$ and $V$, both of some common size $k$, which are closest with respect to the given metric.
 • To match signals, the DynamicTimeWarping command inserts zero or more successive copies of every sample for each signal in such a way that the time-warped signals have the same length and the error between them (as measured by metric) is as small as possible. Note that if two signals are identical except for the number of copies of successive samples, then they can be matched exactly. More precisely, the command "warps" $X$ into $U$ and $Y$ into $V$ by computing Vectors of indices $G$ and $H$, both of the same length $k$ which satisfy ${G}_{1}=1$, ${G}_{k}=m$, ${H}_{1}=1$, ${H}_{k}=n$, and ${G}_{i+1}-{G}_{i}\in \left\{0,1\right\}$ and ${H}_{i+1}-{H}_{i}\in \left\{0,1\right\}$ for each $i$.
 • For the signals $X$ and $Y$, both require two or more elements each, and all the elements must be defined and finite.
 • For the algorithm to work, the signals need to agree at their endpoints, that is, ${X}_{1}={Y}_{1}$ and ${X}_{m}={Y}_{n}$. If the passed signal do not already match at their endpoints, the values there are averaged, that is, ${X}_{1}$ and ${Y}_{1}$ are replaced with $\frac{{X}_{1}}{2}+\frac{{Y}_{1}}{2}$, and ${X}_{m}$ and ${Y}_{n}$ are replaced with $\frac{{X}_{m}}{2}+\frac{{Y}_{n}}{2}$.
 • When method=standard, the regular algorithm for Dynamic Time Warping (DTW), based on techniques of Dynamic Programming, is used:
 1 Construct the $m$-by-$n$ cost Matrix $C$, with element ${C}_{i,j}$ representing the cost of matching ${X}_{i}$ with ${Y}_{j}$. First, set each element to infinity. Then, recursively take ${C}_{i,j}=d\left({X}_{i},{Y}_{j}\right)+\mathrm{\mu }$, where $d\left(x,y\right)$ is the given metric, and $\mathrm{\mu }=0$ when $i=1$ and $j=1$, $\mathrm{\mu }={C}_{i-1,1}$ when $1 and $j=1$, $\mathrm{\mu }={C}_{1,j-1}$ when $i=1$ and $1, and $\mathrm{\mu }=\mathrm{min}\left({C}_{i-1,j-1},{C}_{i-1,j},{C}_{i,j-1}\right)$ when $1 and $1. The value of ${C}_{m,n}$ is the optimal cost of the best match between $X$ and $Y$.
 2 Construct the time-warping vectors $G$ and $H$, which store the indices for the optimal path. Starting at the end, namely $\left[m,n\right]$, for each index $\left[i,j\right]$, take $\left[p,q\right]$ to be the index pair which gives the smallest value in $\left[{C}_{i-1,j-1},{C}_{i,j-1},{C}_{i-1,j}\right]$, and append $p$ to $G$ and $q$ to $H$. Continue this process recursively until index pair $\left[1,1\right]$ is reached.
 3 Compute the time-warped signals, U=X[G] and V=Y[H].
 • When method=pruning, the Pruning Method is employed, which is a variation of the above method whereby index pairs are pruned (skipped) during construction of the cost Matrix when the values are too large for the pairs to be a part of the optimal path. This method is exact, in the sense that the optimal path found is the same as for the standard method, and tends to execute a fair bit faster than the standard method. Note that when this method is used, the cost Matrix will (likely) still have elements that are infinity, corresponding to index pairs that have been pruned.
 • Let $\mathrm{\rho }$ be the larger of $\left|m-n\right|$ and the value of radius. For a given index $i$, ${C}_{i,j}$ is computed only for indices $j$ that satisfy $\left|i-j\right|\le \mathrm{\rho }$. The $\left|m-n\right|$ component of $\mathrm{\rho }$ is needed to ensure that the index pair $\left[m,n\right]$ can be reached. The method is inexact, in the sense that the optimal path found is (likely) not the same as for the standard method, with a larger total cost for the optimal path. Note that when this method is used with a lower value of $\mathrm{\rho }$, the cost Matrix will (likely) still have elements that are infinity, corresponding to index pairs that fall outside of the window.
 • The metric option is used by the optimizer to determine the optimal match for the two signals. Consider two Vectors $A$ and $B$, both of size $p$. For the error between them, we have a few options. See below.
 • For metric=canberra:

$d\left(A,B\right)={\sum }_{i=1}^{p}\left\{\begin{array}{cc}0& {a}_{i}=0\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{and}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}{b}_{i}=0\\ \frac{\left|{a}_{i}-{b}_{i}\right|}{\left|{a}_{i}\right|+\left|{b}_{i}\right|}& \mathrm{otherwise}\end{array}\right\$

 • For metric=chebyshev:

$d\left(A,B\right)=\mathrm{max}\left(\left|{a}_{i}-{b}_{i}\right|,i=1..p\right)$

 • For metric=entropy, which requires that $A$ and $B$ both have real and positive elements:

$d\left(A,B\right)={\sum }_{i=1}^{p}\left|{a}_{i}-{b}_{i}\right|\left|\mathrm{Typesetting}:-\mathrm{_Hold}\left(\left[{\mathrm{%log}}_{2}\right]\right)\left({a}_{i}\right)-\mathrm{Typesetting}:-\mathrm{_Hold}\left(\left[{\mathrm{%log}}_{2}\right]\right)\left({b}_{i}\right)\right|$

 • For metric=euclidean:

$d\left(A,B\right)=\sqrt{{\sum }_{i=1}^{p}{\left|{a}_{i}-{b}_{i}\right|}^{2}}$

 • For metric=taxicab:

$d\left(A,B\right)={\sum }_{i=1}^{p}\left|{a}_{i}-{b}_{i}\right|$

 • When DynamicTimeWarping is called in the session for the first time with compiled=true, the internal auxiliary routines which otherwise would be called with evalhf will instead be compiled. If DynamicTimeWarping has already been called in the session with compiled=true, it will continue to use the compiled versions of the internal commands, even if called with compiled=false. Use of the compiled=true option is recommended when the sizes of the signals are large, or the DynamicTimeWarping command is to be called numerous times. In these scenarios, the speed increase in execution is likely worth the cost of the overhead for compilation.
 • Maple attempts to coerce signal1 and signal2 to 1-D Vectors that are either both of float[8] datatype or both of complex[8] datatype, and an error is thrown if this is not possible. For this reason, it is most efficient for the passed input to use the appropriate datatypes.
 • The inputs signal1 and signal2 cannot have an indexing function, and must use rectangular storage.
 • The DynamicTimeWarping command is not thread safe.

Examples

 > $\mathrm{with}\left(\mathrm{SignalProcessing}\right):$

Example 1

 > $A≔\left[4,6,8\right]$
 ${A}{≔}\left[{4}{,}{6}{,}{8}\right]$ (1)
 > $B≔\left[4,6,8\right]$
 ${B}{≔}\left[{4}{,}{6}{,}{8}\right]$ (2)
 > $U,V≔\mathrm{DynamicTimeWarping}\left(A,B\right)$
 ${U}{,}{V}{≔}\left[\begin{array}{c}{4.}\\ {6.}\\ {8.}\end{array}\right]{,}\left[\begin{array}{c}{4.}\\ {6.}\\ {8.}\end{array}\right]$ (3)
 > $\mathrm{DynamicTimeWarping}\left(A,B,'\mathrm{output}'='\mathrm{cost}'\right)$
 ${0.}$ (4)

Example 2

 > $A≔\left[10,20,20,30,40,40,40,40\right]$
 ${A}{≔}\left[{10}{,}{20}{,}{20}{,}{30}{,}{40}{,}{40}{,}{40}{,}{40}\right]$ (5)
 > $B≔\left[10,20,30,30,30,40\right]$
 ${B}{≔}\left[{10}{,}{20}{,}{30}{,}{30}{,}{30}{,}{40}\right]$ (6)
 > $U,V≔\mathrm{DynamicTimeWarping}\left(A,B\right)$
 ${U}{,}{V}{≔}\left[\begin{array}{c}{10.}\\ {20.}\\ {20.}\\ {30.}\\ {30.}\\ {30.}\\ {40.}\\ {40.}\\ {40.}\\ {40.}\end{array}\right]{,}\left[\begin{array}{c}{10.}\\ {20.}\\ {20.}\\ {30.}\\ {30.}\\ {30.}\\ {40.}\\ {40.}\\ {40.}\\ {40.}\end{array}\right]$ (7)
 > $\mathrm{DynamicTimeWarping}\left(A,B,'\mathrm{output}'='\mathrm{cost}'\right)$
 ${0.}$ (8)

Example 3

 • Consider two signals from the same source, with the second signal having twice the sample rate as the first:
 > $f≔\mathrm{sin}\left(2\mathrm{Pi}t\right)+5$
 ${f}{≔}{\mathrm{sin}}{}\left({2}{}{\mathrm{\pi }}{}{t}\right){+}{5}$ (9)
 > $a≔0:$
 > $b≔1:$
 > $m≔101:$
 > $n≔201:$
 > $X≔\mathrm{GenerateSignal}\left(f,t=a..b,m\right):$
 > $Y≔\mathrm{GenerateSignal}\left(f,t=a..b,n\right):$
 • We expect that to match the two signals, $X$ will have to double-up its samples:
 > $R≔\mathrm{DynamicTimeWarping}\left(X,Y,'\mathrm{method}'='\mathrm{standard}','\mathrm{output}'='\mathrm{record}'\right):$
 > ${R}_{'\mathrm{unwarpedplot}'}$
 > ${R}_{'\mathrm{warpedplot}'}$
 > ${R}_{'\mathrm{cost}'}$
 ${1.96858148935275601}$ (10)
 > ${R}_{'\mathrm{rmse}'}$
 ${0.0155106442271454488}$ (11)

Example 4

 > $X≔\left[0.0,0.219524329376085,1.03001175166964,1.39983625176281,1.56282473947696,1.71391133806283,2.16122789596062,1.82680548525239,1.69258876504047,1.39113328513140,1.11342717751392,0.784123157751215,0.707558810044168,0.637971404121882,0.471821268913782,0.439648316356553,0.371086959057091,0.356440067184568,0.331495924881517,0.278188317684323,0.206959858555780,0.198804342406105,0.196327439371469,0.178098039554947,0.157204681962224,0.156915834747560,0.155238209012307,0.150762580284409,0.146161658642928,0.124443983283263\right]:$
 > $Y≔\left[0.0,0.206570824948915,0.637986423299256,1.10834870066160,1.52137526568988,1.83543428085871,2.04072174684286,2.14466682238484,2.16284894433726,2.11355568930851,2.01470348690095,1.88225721255719,1.72957163140713,1.56727507692996,1.40345035833876,1.24395870646777,1.09281305072597,0.952546557611176,0.824547806896206,0.709349871139647,0.606870106284449,0.516602858479741,0.437770042558240,0.369435657404901,0.310590439714759,0.260212454378748,0.217308752794220,0.180942469474214,0.150248971963549,0.124443983283263\right]:$
 > $\mathrm{DynamicTimeWarping}\left(X,Y,'\mathrm{output}'='\mathrm{unwarpedplot}'\right)$
 > $\mathrm{DynamicTimeWarping}\left(X,Y,'\mathrm{output}'='\mathrm{warpedplot}'\right)$
 > $\mathrm{DynamicTimeWarping}\left(X,Y,'\mathrm{output}'='\mathrm{cost}'\right)$
 ${1.88596173996218686}$ (12)
 > $\mathrm{DynamicTimeWarping}\left(X,Y,'\mathrm{output}'='\mathrm{rmse}'\right)$
 ${0.0888199609500530812}$ (13)

Example 5

 • The DynamicTimeWarping command can also match noisy signals (and a noisy signal to its pure source):
 > $g≔\mathrm{sin}\left(2\mathrm{Pi}t\right)$
 ${g}{≔}{\mathrm{sin}}{}\left({2}{}{\mathrm{\pi }}{}{t}\right)$ (14)
 > $a≔0:$
 > $b≔1:$
 > $m≔128:$
 > $X≔\mathrm{GenerateSignal}\left(g,t=a..b,m,'\mathrm{noisetype}'='\mathrm{additive}','\mathrm{noisedeviation}'=0.25\right):$
 > $n≔256:$
 > $Y≔\mathrm{GenerateSignal}\left(g,t=a..b,n,'\mathrm{noisetype}'='\mathrm{multiplicative}','\mathrm{noisedeviation}'=0.50\right):$
 > $R≔\mathrm{DynamicTimeWarping}\left(X,Y,'\mathrm{output}'='\mathrm{record}'\right):$
 > ${R}_{'\mathrm{unwarpedplot}'}$
 > ${R}_{'\mathrm{warpedplot}'}$
 > ${R}_{'\mathrm{cost}'}$
 ${50.9728672222889756}$ (15)
 > ${R}_{'\mathrm{rmse}'}$
 ${0.277092093482195323}$ (16)

Example 6

 • Here, we will match a pair of larger signals. First, though, we will compile the internal procedures separately using a token call of DynamicTimeWarping to measure the time it takes:
 > $\mathrm{CodeTools}:-\mathrm{Usage}\left(\mathrm{DynamicTimeWarping}\left(\left[1,2\right],\left[3,4\right],'\mathrm{compiled}'\right)\right)$
 memory used=33.53MiB, alloc change=0 bytes, cpu time=1.27s, real time=1.46s, gc time=0ns
 $\left[\begin{array}{c}{2.}\\ {3.}\end{array}\right]{,}\left[\begin{array}{c}{2.}\\ {3.}\end{array}\right]$ (17)
 > $X≔\mathrm{GenerateSignal}\left(5+\sqrt{1-{\left(t-1\right)}^{4}},t=0..2,200,'\mathrm{mirror}'='\mathrm{antisymmetric}','\mathrm{copies}'=4\right):$
 > $\mathrm{numelems}\left(X\right)$
 ${1593}$ (18)
 > $Y≔\mathrm{GenerateSignal}\left(6-\left|t-1\right|,t=0..2,200,'\mathrm{mirror}'='\mathrm{antisymmetric}','\mathrm{copies}'=4\right):$
 > $\mathrm{numelems}\left(Y\right)$
 ${1593}$ (19)
 > $R≔\mathrm{CodeTools}:-\mathrm{Usage}\left(\mathrm{DynamicTimeWarping}\left(X,Y,'\mathrm{method}'='\mathrm{pruning}','\mathrm{radius}'=100,'\mathrm{output}'='\mathrm{record}'\right)\right):$
 memory used=24.08MiB, alloc change=19.38MiB, cpu time=100.00ms, real time=100.00ms, gc time=0ns
 > ${R}_{'\mathrm{unwarpedplot}'}$
 > ${R}_{'\mathrm{warpedplot}'}$
 > ${R}_{'\mathrm{rmse}'}$
 ${0.0220493272388582497}$ (20)

Example 7

 • Consider two complex signals, with the first having a constant sample rate and the second having a sample rate that increases with time:
 > $f≔{ⅇ}^{10\mathrm{Pi}It}$
 ${f}{≔}{{ⅇ}}^{{10}{}{I}{}{\mathrm{\pi }}{}{t}}$ (21)
 > $g≔{ⅇ}^{10\mathrm{Pi}I{t}^{2}}$
 ${g}{≔}{{ⅇ}}^{{10}{}{I}{}{\mathrm{\pi }}{}{{t}}^{{2}}}$ (22)
 > $a≔0:$
 > $b≔1:$
 > $m≔{2}^{7}:$
 > $n≔{2}^{9}:$
 > $X≔\mathrm{GenerateSignal}\left(f,t=a..b,m\right):$
 > $Y≔\mathrm{GenerateSignal}\left(g,t=a..b,n\right):$
 • Now, match the signals:
 > $R≔\mathrm{DynamicTimeWarping}\left(X,Y,'\mathrm{method}'='\mathrm{standard}','\mathrm{metric}'='\mathrm{euclidean}','\mathrm{output}'='\mathrm{record}'\right):$
 > ${R}_{'\mathrm{unwarpedplot}'}$

 > ${R}_{'\mathrm{warpedplot}'}$

 • As we can see from the plot of the time-warping path, the matching is achieved by slowing down $X$, with more slowing at the beginning:
 > ${R}_{'\mathrm{warpingpathplot}'}$

 > ${R}_{'\mathrm{rmse}'}$
 ${0.0704699789240906399}$ (23)
 • We used the Euclidean metric to obtain the matched signals, and the cumulative cost determined during the computation equals the Euclidean distance between the two final signals:
 > ${R}_{'\mathrm{cost}'}$
 ${1.59455359895352333}$ (24)
 > $\mathrm{NormDifference}\left({R}_{'\mathrm{warpedsignal1}'},{R}_{'\mathrm{warpedsignal2}'},2\right)$
 ${1.59455359895352244}$ (25)

References

 Silva, Diego F., and Gustavo E.A.P.A. Batista. "Speeding up all-pairwise dynamic time warping matrix calculation". Proceedings of the 2016 SIAM International Conference on Data Mining, pp. 837-845. Society for Industrial and Applied Mathematics, 2016.

Compatibility

 • The SignalProcessing[DynamicTimeWarping] command was introduced in Maple 2022.
 • For more information on Maple 2022 changes, see Updates in Maple 2022.