0

我使用动态时间扭曲算法来生成距离矩阵并找到两个数组之间的差异。但是,是否有一种算法可以实际将一个数组扭曲为另一个数组(作为最终结果,我希望将一个视频扭曲为另一个视频,即使用多维数组)。

背景:我有很多人打高尔夫挥杆的视频,我需要根据相似性来分析它们。然而,许多摆动是慢动作的,而有些是实时的。最重要的是,剪辑在挥杆前后的不同时间开始和停止,每个视频都有高尔夫球手站在帧本身的不同位置。

但是,为了便于解释,请举以下简单示例:

a = [1, 2, 3]
b = [1, 1, 2, 2, 3, 3]

变成:

a = [1, 2, 3]
b = [1, 2, 3]

什么时候b被扭曲了似的a

解释:b只是一个时间膨胀的版本,a例如视频的慢动作版本

这是另一个例子:

a = [1, 2, 3]
b = [3, 4, 6]

变成:

a = [1, 2, 3]
b = [1, 2, 4]

什么时候b被扭曲了似的a

解释:b只是一个时间翻译版本,a有一点错误,例如从较低高度和角度拍摄的视频

如果可能的话,我的最终目标是一种可以将膨胀和翻译结合为一个的算法

4

1 回答 1

0

如果我没记错的话,动态时间规整是一种动态规划算法。因此,如果您将算法想象为在矩阵上运行,其中行是字符串 a 的字母,列是字符串 b 的字母,则分数是通过矩阵逐行计算一个单元格的。

如果除了分数之外,您在每个单元格中存储了一个指针,该指针返回到派生分数的单元格,那么您可以使用通过距离矩阵的反向传播来重建给出最佳分数的路径。

反向传播只是通过这些指针找到一条从矩阵的结束单元返回到起始单元的路径,深度优先搜索。

要将一个字符串映射到另一个,请查看这些指针所采用的方向,水平指针添加到一个字符串,垂直字符串从该字符串中删除(添加到另一个)(或者,水平和垂直添加到一个字符串 + 从其他),对角线匹配两个字符串中的字母。

对于一般的动态编程算法来说,这是一种非常标准的方法,所以我敢打赌,它可以针对动态时间扭曲进行定制。

于 2020-12-10T05:41:55.277 回答