C Code for Dynamic Time Warping

(to accompany section 6.3)

The program dtw.c can be downloaded from here. When compiled, it can be used with a pair of multi-parameter files to find the best-matching alignment between them. This software was developed over a period of several years by my former colleague Andrew Slater, based on earlier (bad) code written by me, much improved by Andy by close reference to some better code written by Tony Robinson of Cambridge University, and which is available for download at various speech sites on the web. I am grateful to Andy for giving me his permission to distribute his code (which I have modified a bit).

For example, the file coming_fb.dat contains 70 lines of 8 parameters, of which the first 10 lines are as follows:

218.763 1383.23 2814.63 3698.46 283.366 398.209 554.283 344.022
1211.34 2271.84 3175.66 3887.79 688.329 394.739 438.149 548.188
944.728 2135.56 2698.35 3641.12 525.242 760.779 485.149 520.193
213.91 1280.9 2201.54 4396.4 580.349 571.959 589.167 516.748
782.347 1578.81 2562.91 3965.88 862.244 613.181 362.169 995.676
1177.65 2179.5 2787.38 4360.61 308.567 364.734 591.679 458.492
878.674 2224.2 2844.5 4427.47 708.421 241.865 357.375 242.539
625.975 2222.71 2971.39 4279.88 304.251 303.16 440.516 325.867
532.095 1766.47 2312.38 4220.31 61.9706 243.677 495.101 363.742
563.113 1632.96 2285.92 4189.36 161.258 180.24 446.443 457.501
...

The entries are floating point numbers in normal text (i.e. ASCII format), separated by single spaces. The 8 parameters in this case are the frequency and bandwidth of the first four formants, in the order F1, F2, F3, F4, B1, B2, B3, B4, measured at 5 ms intervals (one per line), though it does not matter to the dtw program what the numbers mean, nor (within limits) how many parameters (columns) there are, nor how long they are. (However, there has to be the same number of parameters in each of the two files you wish to compare.) The file cunning_fb.dat, for instance, has 74 lines.

When compiled, the dtw command has the following syntax. Note its 6 or 7 arguments, depending on whether you want debugging information to be logged into a debugging file:

dtw infile1 infile2 outfile xsize ysize params [debug_file]

infile1 and infile2 are the file names of the two parameter files to be compared. They must be ASCII files, formatted as illustrated above (i.e. floating point numbers in ordinary text, the columns separated by a space).

outfile is the file name for the warp path, i.e. a listing of which line of infile1 aligns best with which line of infile2. For example, the warp path output file for coming vs. cunning begins as follows:

1 1
2 2
3 3
4 4
5 5
5 6
6 7
7 8
8 9
8 10
9 11
...

xsize, ysize and params are integers. xsize is the number of lines in infile1, ysize is the number of lines in infile2 and params is the number of columns (which must be the same for both input files).

debug_file is the name of a file where debugging information is to be written.

It also outputs a file called glob (the name of which is fixed and is not mentioned as part of the command syntax), which contains a single number: the overall distance between the two files. As a specific example, the command usage:

dtw cunning_fb.dat coming_fb.dat warp_path.txt 74 70 8

will compute the time warp of the two stated input files and put the output in warp_path.txt, without generating an associated debugging file.