(dtwdistance) Dynamic Time Warping Distance

First question: What is this DTW??

Dynamic Time Warping (DTW) is one of the algorithms for measuring the similarity between two temporal time series sequences, which may vary in speed.

Let's make this definition easy to understand.

Let’s assume you want to calculate the distance between two arrays (or list) for eg. A = [2, 5, 7, 3, 12], B= [4, 7, 3, 2 ,10]

The known way to find it is by measuring the distance component between A & B in parallel pair, (formerly known as Euclidean distance)

It's the best way to find the distance between two arrays (Manhattan distance is also there) But what if the arrays are of unequal length.

Let’s take an example to understand:-

# Two unequal length array or sequence
x = [3, 1, 2, 2, 1]
y = [2, 0, 0, 3, 3, 1, 0]

As you can see from the above diagram, for the last two values of the y sequence, there is no pair of x to match. In short, we can’t calculate the distance of unequal length sequences by Euclidean.

Then the term DTW comes into the picture. Now, The definition of DTW should look more clear.

Dynamic Time Warping is used to compare the similarity or calculate the distance between two arrays or time series with different length.

Next question: How does it work??

Ideally, DTW distance depends on the Euclidean distance concept. Steps for using DTW distance:

1. Divide the two series into equal points.
2. Calculate the Euclidean distance between the first point in the first series and every point in the second series. Store the minimum distance calculated. (this is the ‘time warp’ stage)
3. Move to the second point and repeat 2. Move step by step along with points and repeat 2 till all points are exhausted.
4. Repeat 2 and 3 but with the second series as a reference point.
5. Add up all the minimum distances that were stored and this is a true measure of similarity between the two series.

Before going deep to understand this algo, first, try to understand the use case of DTW. Are we actually need the DTW distance concept?

1. Speech Recognition: Dynamic time warping provides a great contribution to speech recognition. Suppose we want to recognize the voice of a person by analyzing his soundtrack, and we are able to collect his soundtrack of saying Hello in one scenario. However, people speak the same word in different ways, what if he speaks hello at a much slower pace like Heeeeeeelloooooo In that scenario, DTW is the best option. Let’s take an example with graph analysis.

for eg., There are two pair of clips which was spoken by a different person with a different accent.

Doors and corners, kid. That’s where they get you

You walk into a room too fast, the room eats you

Attached is the graphical representation of the audio clips.

Just to understand the differentiation between Euclidean and DTW distance in this case.

Now you can see the difference between the distance calculation.

2. Stock market prediction: Comparing stock trading data over similar time frames, even if they do not match up perfectly. For example, comparing monthly trading data for February (28 days) and March (31 days).

3. Wearable fitness trackers: more accurately calculating a walker’s speed and the number of steps, even if their speed varied over time.

4. Route Calculation: calculating more accurate information about a driver’s ETA, if we know something about their driving habits (for example, they drive quickly on straightaways but take more time than average to make left turns).

Now, I think, We understood the concept of DTW distance. Let’s try to see the DTW distance graph for the above sequences.

# Two unequal length array or sequence
x = [3, 1, 2, 2, 1]
y = [2, 0, 0, 3, 3, 1, 0]

Since we can understand any topic only when we can see the actual result in numbers. Let's look at the proper DTW distance calculation using 2D matrix.

algorithm Tutorial => Introduction To Dynamic Time Warping

Since we have done most of the discussion on the DTW mathematical part, now let’s discuss the tech part also, Since it's a Math-tech article.

There are multiple packages available in different languages to use it

fastdtw

Dynamic Time Warping (DTW)

dtw

Now, Some facts about this article
Since I was working on the concept called pose estimation (basically it means to compare the pose between two different people either from an image or video). Then I got to know about the DTW concept.

But at that time, I was implementing the Pose estimation project in Flutter only, that time, There was no dart package or no support to use this without writing its core implementation Then My colleague Adithya Dinesh suggest to create my own if it was not available there. Thanks a lot for that suggestion.

https://pub.dev/packages/dtwdistance (Please check it out.)

Then I released that dart package and published it at https://pub.dev/ (beta version late night), This release is done around 1 year before. But haven't got the moto to write about it.

Now, the second credit goes to Pramod Kumar (who is my team leader and colleague) he always forces me to write whatever I implement new.

Now it ends here. I hope you understood this concept and like it. Please let me know if you have any issues or any mistakes you notice (definitely can be).

Thanks a lot for reading this