Алгоритм DTW: простая реализация - проверка - PullRequest
Новая
       31

Алгоритм DTW: простая реализация - проверка

0 голосов
/ 17 мая 2019

Я попытался сделать простую реализацию алгоритма DTW в C, не используя каких-либо существенных методов оптимизации. Я пытаюсь использовать эту реализацию для некоторого простого распознавания эскиза, то есть нахождения k ближайших соседей данного эскиза из набора. Я получил некоторые результаты, которые кажутся мне странными, и я хотел бы знать, что это из-за моей реализации DTW. Мне нужен кто-то, чтобы проверить мой алгоритм.

Как я уже сказал, я пытаюсь найти k ближайших соседей, поэтому единственная «оптимизация», которую я реализовал для ускорения вычислений, заключается в том, что если минимальная стоимость вычисленной линии в любой точке больше максимального расстояния между k набросками, которые в настоящее время считаются ближайшими соседями, я прекращаю вычислять и возвращаю + инф.

Вот соответствующий алгоритм: 

(returnValue totalCost) dtw(sketch1, sketch2, curMaxDist){
   distMatrix = 'empty matrix of size (sketch.size) x (sketch2.size)'
   totalCostMatrix = 'empty matrix of size (sketch1.size) x (sketch2.size)'
   for(i = 0 to sketch1.size - 1){
       for(j = 0 to sketch2.size - 1){ 
          distMatrix[i][j] = euclidianDistance(sketch1.point[i], sketch2.point[j])
          totalCostMatrix[i][j] = +inf
       }
    }
   //I am forcing the first points of each sketch to correspond to one 
   // and continue applying the algorithm from the next points.

   for(i = 1 to sketch1.size - 1){
      curMinDist = +inf
      for(j = 1 to sketch2.size - 1){
           totalCostMatrix[i][j] = min(totalCostMatrix[i-1][j-1],
                                       totalCostMatrix[i-1][j],             
                                       totalCostMatrix[i][j-1]) + distMatrix[i][j]
           if(totalCostMatrix[i][j] < curMinDist)
               curMinDist = totalCostMatrix[i][j]
      }  
      if(curMinDist > curMaxDist)
           return +inf
   }

   return totalCostMatrix[sketch1.size - 1][sketch2.size - 1]
}

Я уверен, что в реализации нет ничего плохого в том, что касается синтаксиса, языка Си и т. Д., Так как я проверил это и всегда получаю точный результат. Я просто бродил, если что-то не так с обоснованием алгоритма. Я спрашиваю, потому что это действительно хорошо известный алгоритм и очень простая реализация, поэтому, возможно, кому-то будет легко обнаружить ошибку там.

...