模糊匹配/分块算法

Question

模糊匹配/分块算法

algorithmfuzzy-comparisonchunkssliding-window

6

背景：我有视频片段和音轨，希望将它们与视频同步。

从视频片段中，我会提取一个参考音轨。我还有另一个音轨，希望能与参考音轨同步。由于编辑的原因，每个切换场景的时间间隔都有所不同，导致了不同步。

我需要操作目标音轨，使其看起来（在这种情况下是听起来）像参考音轨。这相当于在正确的位置添加或删除静默。虽然可以手动完成，但这将非常繁琐。因此，我希望能够通过程序确定这些位置。

例如：

     0         1         2         
     012345678901234567890123
ref: --part1------part2------
syn: -----part1----part2-----
# (let `-` denote silence)

输出：

[(2,6), (5,9) # part1
 (13, 17), (14, 18)] # part2

我的想法是，从一开始开始：

Fingerprint 2 large chunks* of audio and see if they match:
    If yes: move on to the next chunk
    If not:
        Go down both tracks looking for the first non-silent portion of each
        Offset the target to match the original
        Go back to the beginning of the loop

# * chunk size determined by heuristics and modifiable

这里的主要问题是声音匹配和指纹识别是模糊的，而且相对昂贵。

理想情况下，我希望尽可能少地使用它们。有什么好的想法吗？

- Confluence

声音是否完全匹配，唯一的区别是纯净静音间隔的长度？ - Justin

是的和不是。由于编码差异，声音是不同的，但我可以通过足够的精度“模糊匹配”它们。 - Confluence

@Justin 是的，在音高方面它们是相同的。如果你想到了那个问题，我就不需要把它们变长或缩短。 - Confluence

2个回答

0

如果您可以可靠地区分沉默和非沉默，正如您所建议的那样，并且唯一的区别是插入沉默，则似乎唯一的非平凡情况是在以前没有沉默的地方插入沉默：

ref: --part1part2--
syn: ---part1---part2----

如果您可以使块大小适应静音，那么您的算法应该是可行的。也就是说，如果您的块大小等于上面示例中的两个字符，则您的算法将识别“pa”匹配“pa”，“rt”匹配“rt”，但对于第三个块，它必须识别syn中的静音并调整块大小以将“1”与“1”进行比较，而不是将“1p”与“1-”进行比较。

对于更复杂的编辑，您可能可以使用带有删除静音为0成本的加权最短编辑距离算法进行适应。

- xan

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Kaganar · Accepted Answer

听起来你不想花太多时间深入学习音频处理/工程，因此你需要一些你可以快速理解且可以直接使用的东西。如果你愿意用更复杂的东西，请参考这里，这是一个很好的参考。

在这种情况下，我期望简单的响度和过零率测量足以识别声音的部分。这很棒，因为你可以使用类似rsync的技巧。

选择一定数量的样本作为块大小，并在规则间隔内遍历参考音频数据。(让我们称之为“块大小”。)计算过零率（你可能需要简单的过零计数的对数（或快速近似值）。）根据时间和过零率测量将块存储在二维空间结构中。

然后，逐步遍历您的实际音频数据。步长可以更细，但可能不需要像一个样本那么小。请注意，您不必重新计算整个块大小的度量 - 只需减去不再块中的零交叉并添加新的零交叉即可（仍然需要计算对数或其近似值）。

查找具有足够接近频率的“下一个”块。请注意，由于您要查找的内容按顺序从开始到结束，所以没有必要查看所有块。实际上，我们不想这样做，因为我们更有可能得到错误的结果。

如果块匹配得足够好，请查看它是否一直匹配到静音。

唯一令人担忧的是2D空间结构，但老实说，如果您愿意原谅一个严格的近似窗口，这可以变得更加容易。然后，您只需要有重叠的二进制文件。这样，您所需要做的就是检查某个时间点之后的所有值的两个二进制文件 - 实质上是通过搜索结构进行的两个二进制搜索。

所有这些的缺点是可能需要一些调整才能正确执行，并且不是经过验证的方法。