Блог

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

Контекст: у меня есть много видеороликов, в которых люди играют в гольф, и мне нужно проанализировать их с точки зрения сходства. Однако многие колебания происходят в замедленном режиме, в то время как некоторые — в режиме реального времени. Кроме того, клипы начинаются и останавливаются в разное время до и после качания, и в каждом из видеороликов игрок в гольф стоит в разных положениях в самом кадре.

Однако, для пояснения, возьмем следующий простой пример:

 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 с небольшой ошибкой, например, видео, снятое с меньшей высоты и угла

Моей конечной целью был бы алгоритм, который мог бы объединить как расширение, так и преобразование в одно целое, если это возможно

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

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

Обратное распространение просто находит путь через эти указатели обратно от конечной ячейки матрицы к начальной ячейке с поиском в глубину.

Чтобы сопоставить одну строку с другой, вы смотрите на направления, которые принимают эти указатели, горизонтальные добавляются к одной строке, вертикальные строки удаляются из этой строки (добавляются к другой) (поочередно, как горизонтальные, так и вертикальные добавляются к одной строке удаляются из другой), а диагонали соответствуют буквам в обеих струны.

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