pollen-robotics / dtw Goto Github PK

Greetings,

I don't want to reinvent the wheel but I was wondering something. Since computing the full distance matrix and all other derivative values for big time series I was wondering if an alternative could be implemented.

In cases where the window is small a simple constrained distance matrix could be generated the following way:

#Assuming the input are two pandas series
def constrained_distance(data_a,data_b,dist='cityblock',data_cols=('data','data'))
    suffixes=('_a','_b')
    output=np.zeros((len(data_a),len(data_a))
    og_a=deepcopy(data_a)
    for steps in range (-window,window+1):
        data_a=og_a#use the backup version for safety
        data_a.index=data_a.index.shift(steps) #shift index
        if dist=='cityblock':#shift values for cityblock
            data_a+steps
        datas=pd.merge(data_a,data_b, how='inner',left_index=True,right_index=True,suffixes=suffixes)
        distances= datas[data_cols[0]+suffixes[0]].subtract(datas[data_cols[1]+suffixes[1]])
        output+=np.diagflat(distances,k=steps)
   output[output==0]=np.nan#replace out of bounds values to ensure all is ok
return(output)

i'm not sure how this would affect the algorithm (I don't have the time to delve more into the depths for now)

This is just a quick draft but let me know what you think!

def composite_dis(df_wave, wave_all):
   dtw_dis = dict()
   for i in range(0, len(df_wave)):
        dtw_ij = dict()
        for j in range(0, len(df_wave[i])):
            krec = []
            for k in df_wave[i][j].keys():
                krec.append(k)
                for l in df_wave[i][j].keys():
                    if l not in krec:
                        if k == l:
                            continue
                        else:
                            wave_npk = np.empty( dtype=int, shape=[len(df_wave[i][j][k][k].values), 2] )
                            wave_npl = np.empty( dtype=int, shape=[len(df_wave[i][j][k][k].values), 2] )
                            wave_npk[:, 0] = df_wave[i][j][k]['data_time'].values
                            wave_npk[:, 1] = df_wave[i][j][k][k].values
                            wave_npl[:, 0] = df_wave[i][j][k]['data_time'].values
                            wave_npl[:, 1] = df_wave[i][j][l][l].values
                            
                            manhattan_distance = lambda x, y: np.abs(wave_npk[:, 1] - wave_npl[:, 1])
                            dtw_ij[k+'_'+l] = dtw(wave_npk[:, 1], wave_npl[:, 1], dist=manhattan_distance)
        dtw_dis[str(i)] = dtw_ij
    return dtw_dis`

"I use dtw package, but the np.array emerge the above problem."
what should I do?

My distance matrix is a n*n matrix, a result of vegan::vegdist(lm,method = "euclidean").

Thank you for your help!

In your example with leave out p cross validation, can you suggest another way of splitting train and test matrices? It gives me some error with find function. I searched but i didnt find the corresponding library.
Thank you in advance

In the code of dtw, maybe the weighting coefficient should be added. I don't know if my thought is right. Please give me some answers, thanks.

Just noticed when I prepared this for conda-forge conda-forge/staged-recipes#22951

After #59 is in, it would be great, if you could release a new version on PyPI. Without an update there, dtw is unfortunately not usable.

I implemented the streaming DTW algorithm presented in this paper: http://www.cs.cmu.edu/~christos/PUBLICATIONS/ICDE07-spring.pdf
If you all would be interested in incorporating this functionality into your package, I would be interested in working with you to incorporate it. Is this something that interests you, developers?

Hello,
I am getting an error while importing "from dtw import dtw" which says:
"ImportError: cannot import name dtw", it would be kind if you can provide any suggestion to solve it.

https://github.com/pierre-rouanet/dtw/blob/master/examples/MFCC%20%2B%20DTW.ipynb
(Under comparing them using DTW , In [4])
This is not really an issue,but a doubt rather.

I am doing a speech project in which I'm comparing the similarity between audios. Basically I have a bunch of phoneme recordings from the same voice. Some of them sound similar and some of them don't. So I am using this dist measure to quantify that similarity. And based on what i've observed so far with the samples I have,a dist value of anything less than 180 is holding true for similar sounding phoneme recordings and greater than 180 for the dissimilar ones.

Can I use this condition to compare the similarities? Please let me know. Thanks in advance.

Hey,

I was trying to check out the examples from your README, but all three links seem to be dead.

Thanks!
Reka

Hi!

Thanks for the library, I find it very useful.

I have one question though: How exactly is the cost calculated herein? As sum of the move values, that resulted in the minimum distance?

Thank you again!

Best, T

https://github.com/pollen-robotics/dtw/blob/master/examples/MFCC%20%2B%20DTW.ipynb

hi, i see your code to compare 2 sound wav. how to show compare result (rate) in percentage?
like this

a = [1,2,3,4,5,6]
b = [1,2,3,4,5,6]

it can show 100% using dtw.

Hi, thanks for your examples. Unfortunately, http://nbviewer.ipython.org/github/pierre-rouanet/dtw/blob/master/MFCC%20%2B%20DTW.ipynb is not found.

Why is distance normalised by over the sum of the shape the cost matrix (https://github.com/pierre-rouanet/dtw/blob/master/dtw.py#L38)? I couldn't find this in the definition of DTW.

Hello and thanks for this library.
Sorry if it's a silly question, I'm just discovering what Dynamic time warping is ... I'd just like to know if it's possible to get the delay in seconds between two same audio signals.

I tried this :

tmp1 = convert('test.wav', 0)
tmp2 = convert('test.wav', 1)

y1, sr1 = librosa.load(tmp1)
y2, sr2 = librosa.load(tmp2)

mfcc1 = librosa.feature.mfcc(y1,sr1)   #Computing MFCC values
mfcc2 = librosa.feature.mfcc(y2, sr2)

dist, cost, acc, path = fastdtw(mfcc1.T, mfcc2.T, dist='euclidean')
print("The delay between the two signals is: ",dist) 

where convert is based on ffmpeg in order to create the delay:

def convert(afile, start):
    tmp = tempfile.NamedTemporaryFile(mode='r+b', prefix='offset_', suffix='.wav')
    tmp_name = tmp.name
    tmp.close()
    psox = Popen([
        'ffmpeg', '-loglevel', 'panic', '-i', afile,
        '-ac', '1', '-ar', '8000', '-ss', str(start),
        '-acodec', 'pcm_s16le', tmp_name
    ], stderr=PIPE)
    psox.communicate()
    if not psox.returncode == 0:
        raise Exception("FFMpeg failed")
    return tmp_name

I expected a result equals to 1sec but the dist doesn't seem to be what I think it is :/

why not return D1[-1, -1] ?

Hi

I would like to know please the time complexity of this implementation. it would be nice to precise it in the Readme.md file

thanks ^^

Hello, why am I getting unexpected keyword argument "dist" error while executing this line "dist, cost, acc_cost, path = dtw(mfcc1.T, mfcc2.T, dist=lambda x, y: norm(x - y, ord=1))"?

This may be something obvious/trivial, but I'm new to the topic and not much of a mathmatician.
In your MFCC + DTW.ipynb exaple the output is 192.489808008.

How can I convert it to 0-1 range to judge it against a similarity threshold?
I will use this to determine if the recording is authentic vs deepfaked voice.

When I run "speech recognition", I get this error message:

FileNotFoundError:
[Errno 2] No such file or directory: 'sounds/wavToTag.txt'

Wheare is the wavToTag.txt?

A DTW variation called FastDTW is becoming an established technique in DTW literature, reducing the algorithm to a O(n) complexity: https://pdfs.semanticscholar.org/05a2/0cde15e172fc82f32774dd0cf4fe5827cad2.pdf

The fastdtw function name is confusing if a user is assuming that it implements the technique in the FastDTW paper. The current implementation is using the cdist() function from SciPy, which is an accelerated distance calculation function and not the same as the technique in the paper.

Perhaps accelerated_dtw() ?

Hi again,

(Continuing our email exchange and following your suggestion to post it here)

I'd like to find out the similarity between the two signals.
In order to do this should I repeat what you did before this version change?

distance / sum(acc_cost_matrix.shape)

or would you suggest a different method?

Thanks,
Alex

Thanks a lot for providing the library!

I have a question regarding the comparability of the different versions. The results for the same data and the same distance metric seems to differ between dtw and accelerated_dtw as well as the way the distance metric is specified.

In the following example, I would expect that all three results are equal given that the data and distance metric are the same but that's clearly not the case.

Is this expected? If so, do you know why?

import numpy as np
from dtw import dtw, accelerated_dtw

x = np.array([1.0, 0.9, 1.2, 2.3, 3.8, 3.3, 4.2, 1.9, 0.5, 0.3, 0.3])
y = np.array([0.5, 1.0, 0.9, 1.2, 2.3, 3.8, 3.3, 4.2, 1.9, 0.5, 0.3])

l2_norm = lambda x, y: (x - y) ** 2

d1, _, _, _ = accelerated_dtw(x, y, 'euclidean')
d2, _, _, _ = accelerated_dtw(x, y, dist=l2_norm)
d3, _, _, _ = dtw(x, y, dist=l2_norm)

print(d1, d2, d3)

# -> 0.031818181818181815 0.013181818181818183 0.011363636363636364

I calculated the dtw of the following vectors in matlab:

`v1 = [0.188920000000000,0.374040000000000,0.475340000000000,0.533000000000000,0.512370000000000,0.407970000000000,0.302600000000000,0.246150000000000,0.253710000000000,0.259290000000000,0.263580000000000,0.244050000000000,0.266720000000000,0.307670000000000,0.292210000000000,0.277760000000000,0.341390000000000,0.459630000000000,0.627800000000000,0.800240000000000,0.918510000000000,0.956360000000000,0.928950000000000,0.957970000000000,0.977330000000000,0.996920000000000,1.06092000000000,1.09155000000000,1.02333000000000,1.13333000000000,1.30598000000000,1.51047000000000,1.65202000000000,1.77398000000000,1.80780000000000,1.83943000000000,1.91170000000000,1.98254000000000,2.11222000000000,2.27801000000000,2.43857000000000,2.63078000000000,2.74151000000000,2.87500000000000,3.03449000000000,3.34735000000000,3.72940000000000,3.97465000000000,4.07998000000000,4.12125000000000,4.19081000000000,4.31723000000000,4.57329000000000,4.88914000000000,5.22250000000000,5.35281000000000,5.47228000000000,5.63479000000000,5.78064000000000,5.86085000000000,5.90618000000000,6.01840000000000,6.12933000000000,6.20901000000000,6.05646000000000,5.98920000000000,6.06569000000000,6.04827000000000,5.93742000000000,5.61611000000000,5.05997000000000,4.43839000000000,3.91407000000000,3.50155000000000,3.40417000000000,3.40722000000000,3.48959000000000,3.45272000000000,3.38947000000000,3.18416000000000,3.01354000000000,2.86543000000000,2.72751000000000,2.60656000000000,2.60653000000000,2.52645000000000,2.31048000000000,2.19951000000000,2.06875000000000,1.86361000000000,1.67055000000000,1.39603000000000,1.30123000000000,1.18884000000000,1.21669000000000,1.20688000000000,1.28473000000000,1.39773000000000,1.33148000000000,1.31266000000000,1.34883000000000,1.24372000000000,1.12070000000000,1.02620000000000,0.967690000000000,0.923500000000000,0.826740000000000,0.730070000000000,0.562350000000000,0.363570000000000,0.287070000000000,0.160360000000000,0.0180400000000000,-0.152870000000000,-0.205000000000000,-0.185640000000000,-0.288340000000000,-0.395300000000000,-0.459250000000000,-0.487600000000000,-0.555340000000000,-0.591990000000000,-0.604040000000000,-0.600200000000000,-0.632190000000000,-0.762050000000000,-0.884570000000000,-0.952940000000000,-1.05157000000000,-1.17938000000000,-1.31063000000000,-1.43334000000000,-1.51990000000000,-1.62652000000000,-1.74324000000000,-1.85254000000000,-2.07515000000000,-2.44438000000000,-2.91229000000000,-3.43957000000000,-4.10041000000000,-4.96290000000000,-6.11609000000000,-7.55787000000000,-9.28694000000000,-11.2354800000000,-12.8483100000000,-13.3931800000000,-13.1156300000000,-11.4611500000000,-9.57552000000000,-8.61771000000000,-13.4576700000000,-19.7714300000000,-25.1203200000000,-32.3106200000000,-31.9191000000000,-35.4034800000000,-22.1963600000000,-10.8390700000000,-4.90095000000000,-3.36312000000000,-2.70830000000000,-0.498060000000000,4.45787000000000,8.33272000000000,10.1187600000000,10.2836400000000,10.1326300000000,10.1289500000000,10.5406200000000,10.6819000000000,10.5473300000000,10.4898600000000,10.3997000000000,10.0776900000000,9.89943000000000,10.1427500000000,10.5413800000000,10.7724700000000,10.7867300000000,10.6159200000000,10.2735700000000,9.88413000000000,9.59865000000000,9.51017000000000,9.39271000000000,9.16591000000000,8.84678000000000,8.59101000000000,8.45692000000000,8.27694000000000,7.99775000000000,7.58808000000000,7.14221000000000,6.75419000000000,6.39763000000000,6.07260000000000,5.68011000000000,5.32350000000000,5.02207000000000,4.53240000000000,4.20408000000000,3.89949000000000,3.61511000000000,3.34292000000000,3.24694000000000,3.15468000000000,2.88688000000000,2.42131000000000,2.14873000000000,1.87972000000000,1.59830000000000,1.40339000000000,1.26594000000000,1.11341000000000,1.01131000000000,0.840810000000000,0.649300000000000,0.519010000000000];
v2 = [0.172190000000000,0.183850000000000,0.140950000000000,0.124780000000000,0.120430000000000,0.119600000000000,0.0934800000000000,0.0900300000000000,0.0235400000000000,0.0637200000000000,0.446220000000000,0.994590000000000,1.42781000000000,1.68248000000000,1.74495000000000,1.58854000000000,1.42296000000000,1.39401000000000,1.53864000000000,1.61368000000000,1.48482000000000,1.55669000000000,1.78322000000000,1.91022000000000,1.89990000000000,1.67274000000000,1.51963000000000,1.39933000000000,1.40903000000000,1.50344000000000,1.47615000000000,1.28588000000000,1.21687000000000,1.39741000000000,1.56799000000000,1.80233000000000,2.06685000000000,2.14694000000000,2.12543000000000,2.15747000000000,2.22453000000000,2.26919000000000,2.18031000000000,2.08126000000000,1.95087000000000,1.83460000000000,1.95396000000000,1.95825000000000,1.85928000000000,1.89796000000000,1.91726000000000,1.78281000000000,1.55493000000000,1.34871000000000,1.18645000000000,1.29396000000000,1.48854000000000,1.80546000000000,2.09418000000000,2.25531000000000,2.25869000000000,2.02703000000000,1.64870000000000,1.33342000000000,1.17083000000000,1.12854000000000,1.08169000000000,1.04123000000000,1.03051000000000,0.948310000000000,1.00077000000000,0.946430000000000,0.883910000000000,0.930570000000000,1.02310000000000,0.992460000000000,0.803750000000000,0.608970000000000,0.418720000000000,0.122440000000000,-0.0441000000000000,-0.0955500000000000,-0.158140000000000,-0.247990000000000,-0.227000000000000,-0.261870000000000,-0.325670000000000,-0.389170000000000,-0.412000000000000,-0.128000000000000,0.0447800000000000,0.0156700000000000,-0.171850000000000,-0.471630000000000,-0.663620000000000,-0.812920000000000,-0.761030000000000,-0.623730000000000,-0.320340000000000,-0.122160000000000,-0.0488800000000000,-0.0699800000000000,-0.150240000000000,-0.366810000000000,-0.679180000000000,-0.884930000000000,-0.891200000000000,-0.652210000000000,-0.411230000000000,-0.550700000000000,-0.997270000000000,-1.23023000000000,-1.10687000000000,-1.16260000000000,-1.27119000000000,-1.51755000000000,-1.86312000000000,-1.89248000000000,-1.43688000000000,-1.11052000000000,-0.991740000000000,-1.15689000000000,-1.31163000000000,-0.479530000000000,0.606620000000000,1.13675000000000,0.988150000000000,0.789260000000000,0.783010000000000,0.579910000000000,0.443940000000000,0.207690000000000,0.195230000000000,0.271300000000000,0.417440000000000,0.169780000000000,-0.128360000000000,-0.420960000000000,-0.346430000000000,-0.273350000000000,-0.248640000000000,-0.110550000000000,-0.00355000000000000,0.264170000000000,0.476580000000000,0.621370000000000,0.655180000000000,0.698600000000000,0.691000000000000,0.534970000000000,0.421630000000000,0.0813000000000000,-0.155090000000000,-0.278060000000000,-0.401110000000000,-0.496130000000000,-0.466990000000000,-0.0743000000000000,0.360610000000000,0.682450000000000,0.733570000000000,0.400130000000000,0.139960000000000,-0.0959700000000000,-0.159770000000000,-0.253960000000000,0.00920000000000000,0.0534600000000000,0.477080000000000,0.905120000000000,1.24407000000000,1.42882000000000,1.36261000000000,1.29641000000000,1.30843000000000,1.32917000000000,1.29890000000000,1.23874000000000,1.25595000000000,1.28893000000000,1.31694000000000,1.29161000000000,1.17625000000000,1.09849000000000,1.30325000000000,1.06873000000000,0.993960000000000,1.29602000000000,1.45716000000000,0.799980000000000,1.13135000000000,0.668080000000000,0.666340000000000,0.247790000000000,0.618250000000000,0.956130000000000,1.45986000000000,1.16283000000000,1.16934000000000,0.909140000000000,0.502390000000000,0.121920000000000,0.142810000000000,0.144640000000000,0.110460000000000,0.259030000000000,0.492010000000000,0.607240000000000,0.604710000000000,0.517210000000000,0.438660000000000,0.226780000000000,0.0457300000000000,-0.0892300000000000,-0.209990000000000,-0.325820000000000,-0.348550000000000,-0.360390000000000];

dtw(v1.',v2.')`

result in matlab is 729.6579

Matlab defaults to the euclidean norm

Result with your package: 0.4414261187214609

`
from numpy.linalg import norm

dist, cost, acc, path = dtw(v1, v2, dist=norm)

print(dist)
`

The following line returns 3 values not 4 as shown in the notebook

Produces an error message
dist, cost, acc, path = dtw(x, y, dist=lambda x, y: norm(x - y, ord=1))

No error
dist,cost,path=dtw.dtw(x, y, dist=lambda x, y: norm(x - y, ord=1))

what does function find come from?

it reports error in speech-recognition when train and test data split.
NameError: name 'find' is not defined

Why are you normalizing the dtw distance by shape ?

request array instead
Also can you set the default dist function so no need to write it when user wanna use the default one

That's a very cool implementation, it's almost twice as fast as what I did. Thanks for sharing it. I just had a question regarding the "warp" argument: I don't quite understand it. Is it there to let the optimal path "skip" some steps ? How did you think of implementing this behavior ? Thanks !

Regards,

Toussaint

StackOverflow just reminded me of my old post, where I made your implementation of dtw 435 times faster. I have no use of it now (the Kaggle competition has ended years ago), but maybe others could use it.

The solution is very simple, just removing the for loops :) It would however needs some adaptation as your code have changed since.

It looks this only can warp the smaller one into a bigger list. Is this possible that make a larger list same as smaller list? For example, one list contain 16 points. The other list has 34 points. Can DTW can warp the 34 points into 16 points?

  File "mfcc.py", line 18, in <module>
    dist, cost, path = dtw(mfcc1.T, mfcc2.T)
TypeError: dtw() missing 1 required positional argument: 'dist'

maybe the example should be updated?

I am not able to install dtw on the latest python versions using pip. The installation process fails with:

Collecting dtw
  Downloading dtw-1.4.0.tar.gz (4.7 kB)
  Installing build dependencies ... done
  Getting requirements to build wheel ... error
  error: subprocess-exited-with-error
  
  × Getting requirements to build wheel did not run successfully.
  │ exit code: 1
  ╰─> [20 lines of output]
      Traceback (most recent call last):
        File "/tmp/venv/lib/python3.12/site-packages/pip/_vendor/pyproject_hooks/_in_process/_in_process.py", line 353, in <module>
          main()
        File "/tmp/venv/lib/python3.12/site-packages/pip/_vendor/pyproject_hooks/_in_process/_in_process.py", line 335, in main
          json_out['return_val'] = hook(**hook_input['kwargs'])
                                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
        File "/tmp/venv/lib/python3.12/site-packages/pip/_vendor/pyproject_hooks/_in_process/_in_process.py", line 118, in get_requires_for_build_wheel
          return hook(config_settings)
                 ^^^^^^^^^^^^^^^^^^^^^
        File "/tmp/pip-build-env-cbas8zoy/overlay/lib/python3.12/site-packages/setuptools/build_meta.py", line 325, in get_requires_for_build_wheel
          return self._get_build_requires(config_settings, requirements=['wheel'])
                 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
        File "/tmp/pip-build-env-cbas8zoy/overlay/lib/python3.12/site-packages/setuptools/build_meta.py", line 295, in _get_build_requires
          self.run_setup()
        File "/tmp/pip-build-env-cbas8zoy/overlay/lib/python3.12/site-packages/setuptools/build_meta.py", line 487, in run_setup
          super().run_setup(setup_script=setup_script)
        File "/tmp/pip-build-env-cbas8zoy/overlay/lib/python3.12/site-packages/setuptools/build_meta.py", line 311, in run_setup
          exec(code, locals())
        File "<string>", line 3, in <module>
      ModuleNotFoundError: No module named 'imp'
      [end of output]
  
  note: This error originates from a subprocess, and is likely not a problem with pip.
error: subprocess-exited-with-error

× Getting requirements to build wheel did not run successfully.
│ exit code: 1
╰─> See above for output.

note: This error originates from a subprocess, and is likely not a problem with pip.

Other projects seemed to have similar issues after the module imp was removed from the python standard lib and I found the following discussion. This issue prevents us from supporting python 3.12 so we would really appreciate a solution to this...

I'm working on a sequence matching problem. I cannot figure out a way to find the best match using a single execution. I kind of using dist to move step by step and figure out the corresponding smallest position.

Could you give me some hints, how to use 1 dtw process to figure out the best match?
below is the code, modified a little from the example

import numpy as np
from dtw import dtw , accelerated_dtw
import random
import matplotlib.pyplot as plt

# We define two sequences x, y as numpy array
# where y is actually a sub-sequence from x
x = np.array([3,9,9,8,7,2,2, 0, 1, 1.2, 0, 3, 2, 4.3, 2.3, 1, 2.2, 0]).reshape(-1, 1) +2.0
y = np.array([      1, 1.1, 3.5,2, 2, 1, 4.2, 2.1, 1, 2.5, 0]).reshape(-1, 1)

x = x.reshape(-1).tolist()

# added some random samples
for i in range(15):
    x.append(random.randint(0,99)/10.0)
x = np.array(x)

euclidean_norm = lambda x, y: np.abs(x - y)

ds = []
for i in range(x.shape[0] - y.shape[0]-1):
    d, cost_matrix, acc_cost_matrix, path = accelerated_dtw(x[i:i+y.shape[0]], y, dist=euclidean_norm, warp=1)
    ds.append(d)
ds = np.array(ds)

# figure out the position
offset = np.argmin(ds)
print(offset)


plt.plot(x)
if offset>0:
    # padding zeros, align it
    z = np.zeros(offset)
    z = z.tolist()
    z.extend(y.reshape(-1).tolist())
    print(z)
    z = np.array(z)
    
    plt.plot(z)
else:
    plt.plot(y)
plt.show()

File "D:\Anaconda3\lib\site-packages\dtw\dtw.py", line 29, in dtw
D0 = zeros((r + 1, c + 1))

we apply the same dtw function to the same data but the return the d value is different. in v1.3.3, the value is around 1.3 but in v1.4.0, the d value become nearly 15....

dtw(a, b, dist=euclidean_norm)

any advise why so and which version give the right answer? many thanks