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

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.

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

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

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

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

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

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

Answer 2

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

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

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

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