D:/work/code_by/CbmrEngine/cbmrdtw.cpp

查看本檔案說明文件.

/*==============================================================================
最後修改日期：2001/1/4 by 高名揚
最快、最省記憶體的dynamic time warping
dtw table只有WINDOW_WIDTH行
==============================================================================*/
#include <stdlib.h>
#include "cbmrdtw.h"

#define WINDOW_WIDTH 2

typedef struct
{
  int dist;
  int matchLength;
} DTWtableStruct;

DTWtableStruct *DTWtable[WINDOW_WIDTH];

void newDTWtable(int height)
{
  int i;

  for (i = 0; i < WINDOW_WIDTH; i++)
    DTWtable[i] = new DTWtableStruct[height];
}

void delDTWtable(void)
{
  int i;

  for (i = 0; i < WINDOW_WIDTH; i++)
    delete[] DTWtable[i];
}

int dtw(int *data1, int size1, int *data2, int size2,
      bool fixLeft, int *pathLength, int threshold)
{
  int i, j, k;
  int startj, endj;
  int tableColumn;
  int finali, finalj;
  int preDistance, minDistance;
  int preMatchLength;
  int parentIndex[WINDOW_WIDTH][WINDOW_WIDTH] = {{1, 0}, {0, 1}}, *pIndex;
  int minDistOfCol;
  int minDistOfCols[WINDOW_WIDTH];  //最近WINDOW_WIDTH行的最小值

  if (size2 <= (size1 + WINDOW_WIDTH - 2) / WINDOW_WIDTH)  //data2太短
  {
    *pathLength = 0;
    return INFINITE_INT;
  }

  newDTWtable(size2 + WINDOW_WIDTH);
  //把應該是INF的地方先填上
  for (i = 0; i < WINDOW_WIDTH; i++)
    for (j = 0; j < size2 + WINDOW_WIDTH; j++)
      DTWtable[i][j].dist = INFINITE_INT;

  //先算好第0行
  if (!fixLeft)
  {
    minDistOfCol = INFINITE_INT;
    for (j = size2 - (size1 + WINDOW_WIDTH - 2) / WINDOW_WIDTH - 1; j >= 0; j--)
    {
      if ((DTWtable[0][j + WINDOW_WIDTH].dist = abs(data1[0] - data2[j])) < minDistOfCol)
        minDistOfCol = DTWtable[0][j + WINDOW_WIDTH].dist;
      DTWtable[0][j + WINDOW_WIDTH].matchLength = 1;
    }
    minDistOfCols[0] = minDistOfCol;
  }
  else
  {
    DTWtable[0][WINDOW_WIDTH].dist = abs(data1[0] - data2[0]);
    DTWtable[0][WINDOW_WIDTH].matchLength = 1;
    minDistOfCols[0] = DTWtable[0][WINDOW_WIDTH].dist;
  }
  for (i = 1; i < WINDOW_WIDTH; i++)
    minDistOfCols[i] = INFINITE_INT;
  //計算其他點的距離
  tableColumn = 0;
  startj = 1;
  for (i = 1; i < size1; i++)  //計算dtw table的每一行
  {
    if (++tableColumn == WINDOW_WIDTH)
      tableColumn = 0;
    //計算endj
    endj = size2 - (size1 + WINDOW_WIDTH - 2 - i) / WINDOW_WIDTH - 1;
    if (fixLeft)
      if (endj > i * WINDOW_WIDTH)
        endj = i * WINDOW_WIDTH;

    pIndex = parentIndex[tableColumn];
    minDistOfCol = INFINITE_INT;
    for (j = endj; j >= startj; j--)  //計算dtw table第i行的每一個元素
    {
      preDistance = DTWtable[pIndex[0]][j + WINDOW_WIDTH - 1].dist;
      preMatchLength = DTWtable[pIndex[0]][j + WINDOW_WIDTH - 1].matchLength;
      if (DTWtable[pIndex[1]][j + WINDOW_WIDTH - 1].dist < preDistance)
      {
        preDistance = DTWtable[pIndex[1]][j + WINDOW_WIDTH - 1].dist;
        preMatchLength = DTWtable[pIndex[1]][j + WINDOW_WIDTH - 1].matchLength;
      }
      if (DTWtable[pIndex[0]][j + WINDOW_WIDTH - 2].dist < preDistance)
      {
        preDistance = DTWtable[pIndex[0]][j + WINDOW_WIDTH - 2].dist;
        preMatchLength = DTWtable[pIndex[0]][j + WINDOW_WIDTH - 2].matchLength;
      }

      DTWtable[tableColumn][j + WINDOW_WIDTH].dist = preDistance < INFINITE_INT? preDistance + abs(data1[i] - data2[j]) : INFINITE_INT;  //累積距離
      DTWtable[tableColumn][j + WINDOW_WIDTH].matchLength = preMatchLength + 1;  //match長度加1

      if (DTWtable[tableColumn][j + WINDOW_WIDTH].dist < minDistOfCol)
        minDistOfCol = DTWtable[tableColumn][j + WINDOW_WIDTH].dist;
    }  //for j

    for (j = startj - WINDOW_WIDTH; j < startj; j++)  //在每一行下方補上WINDOW_WIDTH個INF
      DTWtable[tableColumn][j + WINDOW_WIDTH].dist = INFINITE_INT;

    if (tableColumn == 0)
      startj++;  //更新startj

    minDistOfCols[tableColumn] = minDistOfCol;  //目前這一行的最小值
    for (k = 0; k < WINDOW_WIDTH; k++)  //找出最近WINDOW_WIDTH行中的最小值
      if (minDistOfCols[k] < minDistOfCol)
        minDistOfCol = minDistOfCols[k];
    if (minDistOfCol > threshold)  //如果最小值比threshold還大則跳出
    {
      *pathLength = 0;
      delDTWtable();
      return INFINITE_INT;
    }
  }  //for i
  //從最後一行找出最小值minDistance及其位置(finali, finalj)
  minDistance = INFINITE_INT;
  finali = tableColumn;
  k = (size1 + WINDOW_WIDTH - 2) / WINDOW_WIDTH;
  for (j = size2 - 1; j >= k; j--)
    if (DTWtable[finali][j + WINDOW_WIDTH].dist < minDistance)
    {
      minDistance = DTWtable[finali][j + WINDOW_WIDTH].dist;
      finalj = j + WINDOW_WIDTH;
    }
  *pathLength = DTWtable[finali][finalj].matchLength;  //match到的長度
  delDTWtable();
  return minDistance;
}

---