Size of warping path (wp) obtained by Librosa Sub-sequence DTW is larger than expected

[wjassim]

Hi,

I've encountered an issue while utilizing the librosa sub-sequence Dynamic Time Warping (DTW) function. It seems that the size of the obtained warping path (wp) is unexpectedly larger than the expected value of N.

I'm using the following code to compute DTW:

D, wp = librosa.sequence.dtw(
X=patch,
Y=patch_ref,
metric='euclidean',
step_sizes_sigma=[[1, 0], [0, 3], [1, 3]],
weights_mul=np.array([1, 1, 1]),
band_rad=0.25,
subseq=True,
backtrack=True,
)

Where X is an np.ndarray with a shape of (K, N), where K is 13 and N is 100, and Y is an np.ndarray with a shape of (K, M), where K is also 13 but M is 1823.

According to the documentation of librosa.sequence.dtw, the expected shape of the warping path wp should be (N, 2). However, in my specific case, the size of wp is (101, 2), which is unexpected. The size of D in my case is (N,M).

I have enclosed the relevant data with this report. Please see the attached zip file:

dtw_files.zip

librosa.version = '0.9.2'

Your feedback on this would be greatly appreciated.
Thank you,

[bmcfee]

Thanks for the thorough report and sample data. I'm tagging @stefan-balke on this, since he has spent the most time (I believe) with the inner workings of our DTW implementation.

At a first glance, my hunch is that this is behaving correctly, and the documentation might be a bit misleading due to over-use of N as a length variable.

Your step sizes allow for strictly vertical or strictly horizontal movement, and you have subseq=True, so the length of the path can be either shorter or longer than the (shorter) input array. For example, if you tweak the step sizes to [1, 0], [0, 1], [1, 1], then you get a warping path of length 111. If you set them to [3, 0], [0, 3], [3, 3] then the warping path comes out to length 37.

So in general, the length of the path is not strictly determined by the length of the input sequences. There are special cases where it is, however, (ie subseq=False with unit steps), and I suspect that what happened here is that we implemented those cases first, wrote the docstring, and then generalized the implementation without revising notation. @stefan-balke does this sound right to you?

[wjassim]

Thank you for your comprehensive feedback.

I got your point. Your observation also aligns with that in [Müller, FMP, Springer 2015], where the warping path is shown to consist of L elements, which could be greater or less than N. This highlights the key distinction of subsequence DTW in comparison to diagonal matching, in which the length of the matching subsequence is constrained to be the same length N as the query X:

https://www.audiolabs-erlangen.de/resources/MIR/FMP/C7/C7S2_SubsequenceDTW.html#Comparison-with-Diagonal-Matching

Thank you again.
Regards

[bmcfee]

Ok, then I think all we need to do is spend a little time revising the docstring here. I'll leave this issue open in case anyone wants to jump on it.

[stefan-balke]

Hi @bmcfee,

sorry, did not get a ping on this one here. Explanations are correct. WP is only N if diagonal matching is enabled. Otherwise it can be longer (max length depends on the step sizes). I will have a look at the doctstring.

Best,
Stefan