Optimized Dynamic Programming (DP) / Dynamic Time Warp (DTW) as a Python external.

Implments the classic dynamic programming best-path calculation. Because the inner loop is implemented as a C routine, it is 500-1000x faster than the equivalent pure Python.

The external library needs to be compiled; this should be possible with python setup.py build. This creates the _dpcore_py.so file that needs to go in the same directory as dpcore.py. (If you're using HomeBrew on a Mac, you may be able to simply make -f Makefile.dpcore_py to create the compiled object.)

See http://nbviewer.ipython.org/github/dpwe/dp_python/blob/master/dp.ipynb for an ipython notebook demonstrating the DTW alignment of two spoken utterances.

Based on the Matlab DP external: http://labrosa.ee.columbia.edu/matlab/dtw/

#####dp(local_costs, penalty=0.0, gutter=0.0)

Use dynamic programming to find a min-cost path through a matrix of local costs.

params

local_costs : np.array of float

matrix of local costs at each cell

penalty : float

additional cost incurred by (0,1) and (1,0) steps [default: 0.0]

gutter : float

proportion of edge length away from [-1,-1] that best path will be accepted at. [default: 0.0 i.e. must reach top-right]

returns

p, q : np.array of int

row and column indices of best path

total_costs : np.array of float

matrix of minimum costs to each point

phi : np.array of int

traceback matrix indicating preceding best-path step for each cell:

• 0 -- diagonal predecessor
• 1 -- previous column, same row
• 2 -- previous row, same column

note Port of Matlab routine dp.m (with some modifications). See http://labrosa.ee.columbia.edu/matlab/dtw/

#####dpcore(M, pen, use_extension=True)

Core dynamic programming calculation of best path.

M[r,c] is the array of local costs.
Create D[r,c] as the array of costs-of-best-paths to r,c, and phi[r,c] as the indicator of the point preceding [r,c] to allow traceback; 0 = (r-1,c-1), 1 = (r,c-1), 2 = (r-1, c)

params

M : np.array of float

Matrix of local costs

pen : float

Penalty to apply for non-diagonal steps

use_extension : boolean

If False, use the pure-python parallel implementation [default: True]

returns

D : np.array of float

Array of best costs to each point, starting from (0,0)

phi : np.array of int

Traceback indices indicating the last step taken by the lowest-cost path reaching this point. Values:

• 0 -- previous point was r-1, c-1
• 1 -- previous point was r, c-1
• 2 -- previous point was r-1, c