動態時間扭曲簡介

Created: November-22, 2018

動態時間扭曲（DTW）是用於測量兩個時間序列之間的相似性的演算法，其可以在速度上變化。例如，即使一個人比另一個人走得快，或者在觀察過程中有加速度和減速度，也可以使用 DTW 檢測步行的相似性。它可用於將示例語音命令與其他命令匹配，即使該人說話的速度比預先錄製的樣本語音更快或更慢。DTW 可以應用於視訊，音訊和圖形資料的時間序列 - 實際上，可以使用 DTW 分析可以變成線性序列的任何資料。

通常，DTW 是一種計算具有某些限制的兩個給定序列之間的最佳匹配的方法。但是，讓我們堅持這裡更簡單的觀點。假設我們有兩個語音序列 Sample 和 Test ，我們想檢查這兩個序列是否匹配。此處語音序列是指你的語音轉換後的數字訊號。可能是你的聲音的幅度或頻率表示你說的話。我們假設：

Sample = {1, 2, 3, 5, 5, 5, 6}
Test   = {1, 1, 2, 2, 3, 5}

我們想找出這兩個序列之間的最佳匹配。

首先，我們定義兩個點之間的距離， d(x, y) 其中 x 和 y 代表兩個點。讓，

d(x, y) = |x - y|     //absolute difference

讓我們使用這兩個序列建立一個 2D 矩陣表。我們將計算每個 Sample 點與每個 Test 點之間的距離，並找出它們之間的最佳匹配。

+------+------+------+------+------+------+------+------+
|      |   0  |   1  |   1  |   2  |   2  |   3  |   5  |
+------+------+------+------+------+------+------+------+
|   0  |      |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+
|   1  |      |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+
|   2  |      |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+
|   3  |      |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+
|   5  |      |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+
|   5  |      |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+
|   5  |      |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+
|   6  |      |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+

這裡，如果我們考慮到樣本[i] 和測試[j] 的序列，考慮到我們之前觀察到的所有最佳距離，表[i] [j] 表示兩個序列之間的最佳距離。 **** ****

對於第一行，如果我們不從 Sample 中取值，則此值與 Test 之間的距離將為無窮大。所以我們把無限放在第一行。第一列也是如此。如果我們沒有從 Test 中取值，那麼這個和 Sample 之間的距離也將是無窮大。並且 0 到 0 之間的距離將僅為 0 。我們得到了，

+------+------+------+------+------+------+------+------+
|      |   0  |   1  |   1  |   2  |   2  |   3  |   5  |
+------+------+------+------+------+------+------+------+
|   0  |   0  |  inf |  inf |  inf |  inf |  inf |  inf |
+------+------+------+------+------+------+------+------+
|   1  |  inf |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+
|   2  |  inf |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+
|   3  |  inf |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+
|   5  |  inf |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+
|   5  |  inf |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+
|   5  |  inf |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+
|   6  |  inf |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+

現在，對於每個步驟，我們將考慮所關注的每個點之間的距離，並將其新增到我們到目前為止找到的最小距離。這將為我們提供兩個序列到該位置的最佳距離。我們的公式將是，

Table[i][j] := d(i, j) + min(Table[i-1][j], Table[i-1][j-1], Table[i][j-1])

對於第一個， d（1,1） = 0 ，表[0] [0] 表示最小值。因此表[1] [1]的值將為 0 + 0 = 0 。對於第二個， d（1,2） = 0 。表[1] [1] 表示最小值。該值為： 表[1] [2] = 0 + 0 = 0 。如果我們繼續這種方式，在完成後，表格將如下所示：

+------+------+------+------+------+------+------+------+
|      |   0  |   1  |   1  |   2  |   2  |   3  |   5  |
+------+------+------+------+------+------+------+------+
|   0  |   0  |  inf |  inf |  inf |  inf |  inf |  inf |
+------+------+------+------+------+------+------+------+
|   1  |  inf |   0  |   0  |   1  |   2  |   4  |   8  |
+------+------+------+------+------+------+------+------+
|   2  |  inf |   1  |   1  |   0  |   0  |   1  |   4  |
+------+------+------+------+------+------+------+------+
|   3  |  inf |   3  |   3  |   1  |   1  |   0  |   2  |
+------+------+------+------+------+------+------+------+
|   5  |  inf |   7  |   7  |   4  |   4  |   2  |   0  |
+------+------+------+------+------+------+------+------+
|   5  |  inf |  11  |  11  |   7  |   7  |   4  |   0  |
+------+------+------+------+------+------+------+------+
|   5  |  inf |  15  |  15  |  10  |  10  |   6  |   0  |
+------+------+------+------+------+------+------+------+
|   6  |  inf |  20  |  20  |  14  |  14  |   9  |   1  |
+------+------+------+------+------+------+------+------+

在值表[7] [6] 表示這兩個給定序列之間的最大距離。這裡 1 表示 Sample 和 Test 之間的最大距離為 1 。

現在，如果我們從最後一點回溯，一直回到起點 （0,0） 點，我們得到一條水平，垂直和對角線移動的長線。我們的回溯程式將是：

if Table[i-1][j-1] <= Table[i-1][j] and Table[i-1][j-1] <= Table[i][j-1]
    i := i - 1
    j := j - 1
else if Table[i-1][j] <= Table[i-1][j-1] and Table[i-1][j] <= Table[i][j-1]
    i := i - 1
else
    j := j - 1
end if

我們將繼續這一直到達到 （0,0） 。每一步都有自己的含義：

水平移動表示刪除。這意味著我們的測試序列在此間隔內加速。
垂直移動表示插入。這意味著在此間隔期間測試序列減速。
對角線移動表示匹配。在此期間，測試和樣品是相同的。 https://i.stack.imgur.com/2Bfjj.jpg

我們的虛擬碼將是：

Procedure DTW(Sample, Test):
n := Sample.length
m := Test.length
Create Table[n + 1][m + 1]
for i from 1 to n
    Table[i][0] := infinity
end for
for i from 1 to m
    Table[0][i] := infinity
end for
Table[0][0] := 0
for i from 1 to n
    for j from 1 to m
        Table[i][j] := d(Sample[i], Test[j])
                       + minimum(Table[i-1][j-1],      //match
                                 Table[i][j-1],        //insertion
                                 Table[i-1][j])        //deletion
    end for
end for
Return Table[n + 1][m + 1]

我們還可以新增區域性性約束。也就是說，我們要求如果 Sample[i] 與 Test[j] 匹配，則|i - j|不大於視窗引數 w 。

複雜：

計算 DTW 的複雜性是 O（m * n） ，其中 m 和 n 表示每個序列的長度。更快的計算 DTW 的技術包括 PrunedDTW，SparseDTW 和 FastDTW。

應用：

口語識別
相關功率分析