Блог PHP разработчика e64f

Есть такие программы, которые на жестком диске компьютера выполняют поиск дубликатов файлов. Одинаковые файлы “засоряют” - занимают лишнее пространство, т.к. второй, третий и т.д. файл является ненужным мусором. Исключение составляют файлы программных проектов, вернее, дампы исходных кодов (версии программы на какое-то число). А размноженные файлы дистрибутивов программ, архивов, музыки, картинок, т.е. всего того, что не изменяет своего содержимого - однозначно мусор.

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

Проблемы поиска дубликатов среди видео-файлов

Не так давно ко мне обратился за советом один знакомый, собственно, данный текст представляет результат нашего с ним разговора. А проблема была вот какая: ему нужна была программа, которая искала бы дубликаты видео-фильмов.

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

Еще один и тот же фильм может быть различных размеров, например, 640х352, 800х600, …
Еще один и тот же фильм может быть рассчитан на широкий или обычный экран.
Еще один и тот же фильм может быть DVD-Rip или экранкой.
Еще один и тот же фильм может быть с вставками рекламы или без вставок.
Еще один и тот же фильм может быть с начальной заставкой и финальными титрами или без титров и заставки.
Предыдущие два пункта также несут в себе тот факт, что один и тот же фильм в двух файлах может быть разной временной длины.

Метод сравнения кадров видео

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

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

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

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

Сравнение звука

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

Возможные проблемы

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

Возможно, возникнут проблемы сравнения из-за разного количества кадров в секунду в разных видео-кодеках.

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

Итого

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

Теги: Видео, распознавание