Алгоритм нечеткого соответствия / разбиения

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

Звучит так, будто вы не собираетесь тратить много времени на изучение / разработку аудио, и, следовательно, вам нужно что-то, что вы можете быстро понять и просто работать. Если вы готовы пойти с чем-то более сложным, см. здесь для очень хорошей справки.

В таком случае, я бы ожидал, что простой громкости и пересечения нуля будет достаточно для определения фрагментов звука. Это здорово, потому что вы можете использовать технику, похожую на rsync .

Выберите некоторое количество сэмплов в качестве размера фрагмента и регулярно просматривайте эталонные аудиоданные. (Давайте назовем это «размером порции».) Вычислите меру пересечения нуля (вы, вероятно, хотите логарифм (или быстрое приближение) простого подсчета пересечения нуля). Сохраните фрагменты в двухмерной пространственной структуре на основе времени и меры пересечения нуля.

Затем проведите свои аудиоданные гораздо более тонким шагом за раз. (Вероятно, не нужно быть таким маленьким, как один образец.) Обратите внимание, что вам не нужно пересчитывать меры для всего размера фрагмента - просто вычтите пересечения нулей, которые больше не находятся в блоке, и добавьте новый те, которые есть. (Вам все еще нужно будет вычислить логарифм или его приближение.)

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

Если кусок совпадает достаточно хорошо, посмотрите, полностью ли он соответствует, чтобы замолчать.

Единственная касающаяся точка - это пространственная структура 2D, но, честно говоря, это можно сделать намного проще, если вы хотите простить строгое окно приближения. Тогда вы можете просто иметь перекрывающиеся корзины. Таким образом, все, что вам нужно сделать, это проверить две ячейки для всех значений через определенное время - по сути, два двоичных поиска в структуре поиска.

Недостатком всего этого является то, что может потребоваться некоторая настройка, чтобы получить права, и это не проверенный метод.

Answer 2

Если вы можете надежно отличить тишину от безмолвия, как вы предлагаете, и если единственными отличиями являются вставки молчания, то, похоже, единственный нетривиальный случай - это когда молчание вставляется там, где его раньше не было:

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

Если вы можете адаптировать размер куска к тишине, ваш алгоритм должен быть в порядке.То есть, если ваш размер куска эквивалентен двум символам в приведенном выше примере, ваш алгоритм распознает "pa", соответствует "pa" и "rt" соответствует "rt", но для третьего куска он должен распознавать тишину в synи измените размер куска, чтобы сравнить «1» с «1» вместо «1p» с «1 -».

Для более сложных изменений вы можете адаптировать взвешенное Кратчайшее расстояние редактирования Алгоритм с удалением тишины имеет стоимость 0.