<jupyter_start><jupyter_text>Dynamic Time Warping (DTW)This notebook describes the DTW concepts.  Time Series* A time series is a collection of observations made sequentially.* Time series occur in different fields such as  medical, scientific and businesses domains.* Finding the similarity between two time series is useful for clustering and classification. Dynamic Time Warping (DTW)Dynamic Time Warping (DTW) is an algorithm for measuring similarity between two sequences which may not have the same length.In general, the DTW maps each element in the first sequence to an element in the second series. Assuming that a distance function is defined for each pair of points, the goal is to find a mapping that minimizes the total distance between all the points.<jupyter_code>try:
    if __IPYTHON__:
        from IPython import get_ipython

        get_ipython().magic('matplotlib inline')
        from ipython_utilities import *
        from ipywidgets import interact, fixed, FloatSlider, IntSlider, Label, Checkbox, FloatRangeSlider
        from IPython.display import display

        in_ipython_flag = True
except:
    in_ipython_flag = False
import cv2 as cv
from matplotlib import pyplot as plt
import numpy as np
from PIL import Image
from ipywidgets import interact, fixed, FloatSlider, IntSlider, Label, Checkbox, FloatRangeSlider

%matplotlib inline
%pdb

def display_two_sequences(n1,n2):
    index1 = np.linspace(0,15,n1)
    index2 = np.linspace(0,15,n2)
    A = 5*np.sin(index1)
    B = 3*np.sin(index2 + 1)
    # s1 = [1, 2, 3, 4]
    # s2 = [2, 3, 5, 6, 8]
    # ob_dtw = cl_dtw()
    # distance,_ = ob_dtw.calculate_dtw_distance(s1, s2)

    fig = plt.figure(figsize=(12,4))
    plt.plot(index1, A, '-ro', label='A')
    plt.plot(index2, B, '-bo' ,label='B')
    plt.ylabel('value')
    plt.xlabel('index')
    plt.legend()

    plt.show()
    plt.pause(0.001)
    
interact(display_two_sequences,
            n1=IntSlider(min=0, 
              max=100, step=1,value=5,
              description='# of points in sequence 1',
              continuous_update=True),
            n2=IntSlider(min=0, 
              max=100, step=1,value=7,
              description='# of points in sequence 2',
              continuous_update=True));

# arrange_widgets_in_grid(controls)<jupyter_output>Automatic pdb calling has been turned OFF<jupyter_text>Consider the two sequences $A=\{a_1, a_2, ... , a_M\}$ and $B=\{b_1, b_2, ... , b_N\}$ as shown above. Where $a_k$ is the $k_{th}$ sample point in the sequence $A$ and $b_k$ is the $k_{th}$ sample point in the sequence $B$. To find the similarity of these two sequences we need to calculate the total distance between the two sequences. To calculate the total distance we can connects each point in sequence $A$ to a point in sequence $B$ and accumulate the distances between the corresponding points. Since there are so many different possibilities for connecting different points, then the question is what is the best possible arrangement which results in the minimum total distance? In order for the similarity measure to be meaningful we need to impose some constraints on how the points on the two sequence should be connected:* **Boundary conditions:** the first points should be connected to each other and the last points should be connected to each point.* **Monotonicity:** The alignment can not go backward. * **Continuity:** The alignment can not skip an element.* **Warping window:** The same point (feature) should not be repeated too many times. PathA path $P$ is defined as an ordered set of 2-tuples:$$\large P=p_1,p_2, .....p_q$$$$\large p_k=(i_k,j_k)$$where $q$ is the number of connections (correspondences) and  $i_k$ and $j_k$ are the indexes of the connecting elements. $P_s$ is called a "Warping" function.For example $P=(1,1), (1,2), (2,3), ... $ means:* Point 1 in sequence A is connected to point 1 in sequence B* Point 1 in sequence A is connected to point 2 in sequence B* Point 2 in sequence A is connected to point 3 in sequence B* ...A path can be shown on a grid of M rows by N columns. The image below shows two possible paths. Notice that there are many possible paths for connecting elements of the sequence A to elements of the sequence B without violating any the constraints. The cost of each path is the accumulated distance between the corresponding points. **The goal of the DTW algorithm is to find the best path which minimizes the total cost.**  Finding the Best PathTo find the best path:* Set an M by N matrix G* Set $G\left[1,1\right]=d(1,1)$    where $d(i,j)$ is the distance between elements i and j in the sequences respectively.* Calculate each element of the the matrix G as:$$\large G\left[i,j\right]=d(i,j)+min(G\left[i,j-1\right],G\left[i-1,j\right],G\left[i-1,j-1\right])$$* Total distance will be $D(A,B)=G\left[M,N\right]$<jupyter_code>def dtw(s1, s2, window=3):
    grid = np.inf*np.ones((len(s1), len(s2)))
    # grid[0, :] = abs(s1[0] - s2)
    for i in range(window+1):
        grid[0, i] = abs(s1[0] - s2[i])
    for j in range(window+1):
        grid[j, 0] = abs(s2[0] - s1[j])
    
    for i in range(1, len(s1)):
        for j in range(1, len(s2)):
            if abs(i-j) > window:
                continue
            grid[i, j] = abs(s1[i] - s2[j]) + min(grid[i - 1, j], grid[i, j-1], grid[i-1, j-1])
            
    
    print(grid)
    print(grid[-1, -1])
    
def display_two_sequences(n1,n2):
    index1 = np.linspace(0,15,n1)
    index2 = np.linspace(0,15,n2)
    A = [5, 6, 9, 2, 6]*2
    B = [5, 7, 2, 6, 9 , 2]*2
    #A = 5*np.sin(index1)
    #B = 3*np.sin(index2 + 1)
    # s1 = [1, 2, 3, 4]
    # s2 = [2, 3, 5, 6, 8]
    # ob_dtw = cl_dtw()
    # distance,_ = ob_dtw.calculate_dtw_distance(s1, s2)
    print(A)
    print(B)
    
    dtw(A, B)
#     fig = plt.figure(figsize=(12,4))
#     plt.plot(index1, A, '-ro', label='A')
#     plt.plot(index2, B, '-bo' ,label='B')
#     plt.ylabel('value')
#     plt.xlabel('index')
#     plt.legend()

#     plt.show()
#     plt.pause(0.001)
controls = interact(display_two_sequences,
             n1=IntSlider(min=0, 
            max=100, step=1,value=5,
            description='# of points in sequence 1',
            continuous_update=True),
                      n2=IntSlider(min=0, 
            max=100, step=1,value=7,
            description='# of points in sequence 2',
            continuous_update=True));

# arrange_widgets_in_grid(controls)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.11398082276523352, 'fraction_numerical': 0.028147231673368387, 'mean_word_length': 3.2686468646864686, 'pattern_counts': {'":': 0, '<': 8, '<?xml version=': 0, '>': 9, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '2', 'dir': 'jupyter-structured-clean-dedup', 'id': '327545', 'license': 'MIT', 'n_tokens_mistral': 2172, 'n_tokens_neox': 2077, 'n_words': 769, 'path': '01_Dynamic_Time_Warping/Dynamic_Time_Warping.ipynb', 'repo_name': 'milaan9/Python_Computer_Vision', 'size': '6466'}