模糊匹配/分块算法

Question

背景:我有视频剪辑和音轨，我想与所说的视频同步。

从视频剪辑中，我将提取一个参考音轨。我还有另一个想要与参考轨道同步的轨道。去同步化来自编辑，它改变了每个动画场景的间隔。

我需要操纵目标轨道，使其看起来像(在本例中听起来像) ref轨道。这相当于在正确的位置添加或删除静音。这可以手动完成，但会非常单调乏味。所以我希望能够通过编程来确定这些位置。

示例：

     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

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

理想情况下，我希望尽可能少地使用它们。想法？

Answer 1

听起来你不想花很多时间研究音频处理/工程，因此你想要一些你能很快理解并能正常工作的东西。如果您愿意使用更复杂的东西，请参阅here以获得一个很好的参考。

在这种情况下，我希望简单的响度和zero crossing测量足以识别声音的部分。这很棒，因为您可以使用techniques similar to rsync。

选择一定数量的样本作为块大小，并以固定的间隔在参考音频数据中行进。(我们称它为“块大小”。)计算过零度量(您可能需要一个简单过零计数的对数(或快速近似值))。基于时间和过零度量将块存储在2D空间结构中。

然后一步一步地浏览你的实际音频数据。(可能不需要像一个样本那么小。)请注意，您不必重新计算整个区块大小的度量--只需减去区块中不再有的零交叉点，然后添加新的交叉点。(您仍然需要计算对数或其近似值。)

寻找频率足够接近的“下一个”块。请注意，由于您要查找的内容从头到尾都是按顺序进行的，因此没有理由查看所有块。事实上，我们并不想这样做，因为我们更有可能得到假阳性。

如果块匹配得足够好，看看它是否完全匹配到静默。

唯一的关注点是2D空间结构，但老实说，如果你愿意接受严格的近似窗口，这可以变得更容易。然后你可以只有重叠的垃圾桶。这样，您所需要做的就是在一段时间后检查所有值的两个bins -本质上是通过一个搜索结构进行两次二进制搜索。

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

Answer 2

如果你可以像你建议的那样可靠地区分无声和非无声，如果唯一的区别是插入了无声，那么似乎唯一不平凡的情况是在以前没有无声的地方插入了无声：

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

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

对于更复杂的编辑，您可能能够采用加权Shortest Edit Distance算法，并删除静音为0成本。