0

我试图在 C 中简单地实现 DTW 算法，而不使用任何实质性的优化技术。我正在尝试将此实现用于一些简单的草图识别，也就是说，从一组中找到给定草图的 k 个最近邻居。我得到了一些对我来说似乎很奇怪的结果，我想知道这是因为我的 dtw 实现。我需要有人来验证我的算法。

正如我所说，我试图找到 k 个最近的邻居，所以我为加快计算速度而实施的唯一“优化”是，如果计算的给定线的最小成本在任何点大于 k 之间的最大距离当前被认为是最近邻居的草图，我停止计算并返回 +inf。

下面是对应的算法：

(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]
}

我确信就语法、C 语言等而言，实现没有任何问题，因为我已经检查过了，而且我总是得到预期的结果。如果算法背后的推理有问题，我只是在徘徊。我问是因为它是一个非常知名的算法和一个非常简单的实现，所以也许有人很容易在那里发现错误。

4

0 回答 0