[C#]動態時間校正實做

Posted on by Mingray



DTW 是 Dynamic Time Warping 的簡稱，中文可以翻譯成「動態時間扭曲」或是「動態時間校正」，這是一套根基於「動態規劃」（Dynamic Programming，簡稱 DP）的方法，可以有效地將搜尋比對的時間大幅降低。

假設有兩個向量 t 和 r，長度分別是 m 和 n，那麼 DTW 的目標，就是要找到一組路徑 (p1, q1), (p2, q2), …, (pk, qk)}, 使得經由上述路徑的「點對點」對應距離和 Si=1k ∣t(pi) – r(qi)∣ 為最小，而且，此路徑必須滿足下列條件：

  • 端點關係：(p1, q1) = (1, 1), (pk, qk) = (m, n)。此端點關係代表這是「頭對頭、尾對尾」的比對。
  • 局部關係：假設最佳路徑上任一點可以表示成 (i, j)，那麼其前一點路徑只有三種可能：(i-1, j), (i, j-1), (i-1, j-1)。此局部關係定義了路徑的連續性，而且也規定了 t 的任一個元素至少對應一個 r 的元素，反之亦然。

但是，我們要如何很快地找到這條最佳路徑呢？我們可以根據 DP 的原理，來將 DTW 描述成下列三個步驟：

  1. 目標函數之定義：定義 D(i, j) 是 t(1:i) 和 r(1:j) 之間的 DTW 距離，對應的最佳路徑是由 (1, 1) 走到 (i, j)。
  2. 目標函數之遞迴關係：D(i, j) = ∣t(i) – r(j)∣ + min{D(i-1, j), D(i-1, j-1), D(i, j-1)}，其端點條件為 D(1, 1) = ∣t(1) – r(1)∣
  3. 最後答案：D(m,n)D(m,n).


DTW wiki pseudocode

  • sakoe-chiba band 
double DTWDistance(Sequence input, Sequence template)
{
    int rows = input.Frames.Length, columns = template.Frames.Length;
    if (rows < (double)(columns / 2) || columns < (double)(rows / 2))
    {
        return double.MaxValue;
    }
        double[,] DTW = new double[rows, columns];
    DTW[0, 0] = 0;
    for (int i = 0; i < rows; i++)
    {
        for (int j = 0; j < columns; j++)
        {
            double cost = distance(input.Frames[i], template.Frames[j]);
            if (i == 0 && j == 0)
                DTW[i, j] = cost;
            else if (i == 0)
                DTW[i, j] = cost + DTW[i, j - 1];
            else if (j == 0)
                DTW[i, j] = cost + DTW[i - 1, j];
            else
                DTW[i, j] = (cost + Math.Min(DTW[i - 1, j], DTW[i - 1, j - 1]));// insert ,match
        }
    }
    return DTW[rows - 1, columns - 1];
}

//&& 要把amp;去掉，因為我用這個套件的問題，會把&呈現成html表示方式
  • ltakura parallelogram 
float Pruning_DTWDistance(Sequence input, Sequence output)
{
    int rows = input.Frames.Length, columns = output.Frames.Length;
    if (rows < (double)(columns / 2) || columns < (double)(rows / 2))
    {
        return float.MaxValue;
    }
    float cost;
    float[,] DTW = new float[rows + 1, columns + 1];
    int w = Math.Abs(columns - rows);// window length -> |rows - columns|<= w
    for (int i = 1; i <= rows; i++)
    {
        for (int j = Math.Max(1, i - w); j <= Math.Min(columns, i + w); j++)
        {
            if (DTW[i - 1, j] == 0)
                DTW[i - 1, j] = float.MaxValue;
            if (DTW[i - 1, j - 1] == 0)
                DTW[i - 1, j - 1] = float.MaxValue;
            DTW[0, 0] = 0;
            cost = distance(input.Frames[i - 1], output.Frames[j - 1]);// frames 0 based
            DTW[i, j] = (cost + Math.Min(DTW[i - 1, j], DTW[i - 1, j - 1]));// insert ,match
        }
    }
    return DTW[rows, columns];
}

參考來源:
1.mirlab.org
2.stackoverflow.com
3. Wiki DTW

發表迴響

%d 位部落客按了讚：