Это огромная проблема, поэтому я решил написать довольно длинный ответ, чтобы попытаться разложить проблему на части, которые легче решить.
Важно, чтобы сравнение проводилось с использованием доступных вычислительных и временных ресурсов: я сомневаюсь, что решение, для запуска которого требуются месяцы, будет очень полезно в динамической базе данных видео. А размер базы данных, вероятно, делает использование ресурсов облачных вычислений неосуществимым. Поэтому мы действительно заботимся о локальной стоимости каждого сравнения в нескольких разных областях: 1) хранение данных, 2) вычислительные ресурсы и 3) время.
Одна из ключевых затрат, которую следует учитывать, заключается в извлечении данных, необходимых из каждого видео, для любых используемых метрик сравнения. Как только извлеченные данные становятся доступными, необходимо учитывать стоимость проведения сравнения. Наконец, необходимо выполнить сравнение, необходимое для сопоставления всех видео друг с другом.
Стоимость первых двух шагов составляет O (1) на количество видео. Стоимость последнего шага должна быть хуже, чем O (1), потенциально намного хуже. Таким образом, нашей основной целью должно быть минимизация затрат на последний шаг, даже если это означает добавление множества ранних простых шагов.
Оптимальные алгоритмы для этого процесса будут в значительной степени зависеть от характеристик базы данных, уровня, на котором существуют единичные и множественные совпадения. Если 100% видео соответствуют другому видео, мы хотим минимизировать стоимость успешного совпадения. Однако более вероятным случаем является то, что совпадения будут редкими, поэтому мы захотим минимизировать стоимость неудачного совпадения. То есть, если есть быстрый и грязный способ сказать «эти два видео не могут быть совпадают», то мы должны сначала использовать его, прежде чем мы даже начнем подтверждать совпадение.
Чтобы охарактеризовать базу данных, сначала выполните выборку и сопоставление вручную, чтобы оценить степень соответствия в базе данных. Этот эксперимент должен показать, как избыточные видео «слипались»: если у данного видео было совпадение, насколько вероятно, чтобы оно имело более одного совпадения? Какой процент всех матчей был также частью нескольких матчей? Этот процесс даст «модель» базы данных (статистическое распределение), которая будет использоваться для помощи в выборе алгоритма и настройке системы.
В дальнейшем я буду считать, что матчи относительно редки. В конце концов, если совпадений будет много, видео будет «слипаться», эффективно уменьшая базу данных и, таким образом, делая задачу проще. Давайте предположим, что проблема остается настолько сложной, насколько это возможно.
Я бы выступил за подход многоуровневой категоризации, при котором мы построили бы последовательность алгоритмов, которые неоднократно выполняют двоичное решение «эти два видео не совпадают» / «эти два видео могут совпадать». Только самый последний алгоритм в цепочке должен вывести ответ «Эти два видео совпадают».
Алгоритмы классификации / сопоставления могут давать сбой одним или двумя способами: Ложно-положительный (несоответствующие видео ошибочно помечаются как совпадающие) и Ложно-отрицательный (совпадающие видео помечаются как несоответствующие). Каждое из этих неправильных решений имеет диапазон вероятностей, связанных с ним, и мы хотим минимизировать оба.
Поскольку мы строим конвейер алгоритмов, нам нужны алгоритмы, которые очень хорошо идентифицируют несоответствия без ошибок, а это означает, что они должны иметь чрезвычайно низкую частоту ложных отклонений, и мы не очень заботимся о частоте ложных утверждений. Например, клон Wierd Al видео может выглядеть и звучать очень похоже на оригинал, и мы не сможем показать, что он не соответствует оригиналу, пока позже в конвейере алгоритма.
Сначала должны быть запущены самые простые, самые быстрые и надежные алгоритмы, поскольку подавляющее большинство тестов даст результат "не соответствует". Самой простой проверкой будет поиск идентичных файлов в базе данных, что делается многими быстрыми и простыми утилитами обслуживания файловой системы и базы данных. После запуска этого сканирования мы можем предположить, что нам действительно нужно открыть и прочитать видеофайлы, чтобы обнаружить различия.
Поскольку сравнение видео является относительно сложным, давайте начнем с аудио. Думайте о базе данных как о первой коллекции MP3, которая может содержать дубликаты. В конце концов, если мы получим хорошее аудио совпадение, очень вероятно, что у нас будет видео совпадение, и наоборот. Мы можем с уверенностью сказать, что аудио является «честным» представителем для видео. К счастью, быстрый поиск в сети даст множество надежных, быстрых и зрелых пакетов для снятия отпечатков пальцев и сравнения. Аудио отпечаток должен быть создан для каждого видео в базе данных. Видео, в которых отсутствует аудиодорожка, автоматически попадает в набор «может соответствовать».
Но здесь есть «уловка»: как насчет закадровых комментариев? Если данное видео кодируется дважды, с и без закадрового комментария, они совпадают или нет? А как насчет французского аудио против испанского или английского? Если все они должны рассматриваться как совпадающие, то может потребоваться пропустить тестирование звука.
На данный момент мы знаем, что записи файловой системы все "достаточно различны", и мы знаем, что все звуковые дорожки "достаточно различны" (если проверены), что означает, что мы не можем откладывать просмотр видео данных дольше. К счастью, это должно быть сделано только для небольшой части базы данных видео, поэтому мы можем терпеть некоторые затраты. Как и прежде, мы по-прежнему хотим сначала попытаться быстро устранить больше несоответствий, прежде чем мы попытаемся положительно пометить совпадение.
Поскольку нам необходимо учитывать изменения разрешения (например, от 1080p до iPod), нам потребуется способ характеризовать видеоинформацию, которая не только не зависит от разрешения, но также терпима к добавленному шуму и / или потере данных как часть изменения разрешения. Мы должны терпеть изменения частоты кадров (скажем, от 24 кадров в секунду до 30 кадров в секунду). Существуют также изменения соотношения сторон, например, от 4: 3 NTSC до 16: 9 HD. Мы бы хотели обрабатывать изменения цветового пространства, например, от цветного к монохромному.
Затем есть преобразования, которые влияют на все это одновременно, такие как транскодирование между HD и PAL, которые могут одновременно влиять на цветовое пространство, частоту кадров, соотношение сторон и разрешение. Характеристика также должна быть терпимой к некоторой степени обрезки и / или заполнения, например, при переключении между соотношением сторон 4: 3 и 16: 9 (почтовый ящик, но не панорамирование и сканирование). Мы также должны обрабатывать видео, которые были усечены, например, удаление титров из конца художественного фильма. И, очевидно, мы должны также обрабатывать различия, создаваемые различными кодерами, которые получали одинаковый видеопоток.
Вот такой список! Давайте рассмотрим некоторые вещи, которые мы можем решить не учитывать: я подозреваю, что нормально не найти совпадение, когда присутствует искажение изображения, несмотря на тот факт, что анаморфное искажение не является редкостью, особенно в 35-мм широкоэкранных фильмах, которые были непосредственно отсканировано без анаморфной реконструкции (худощавые люди). Мы также можем решить потерпеть неудачу, когда в середине кадра присутствуют большие водяные знаки, хотя мы хотим допускать меньшие водяные знаки в углах. И, наконец, можно не сопоставлять видео, которые были искажены во времени или перевернуты пространственно, например, когда одно является замедленным, а другое перевернуто слева направо.
Это примерно охватывает видео пространство? Надеюсь, понятно, почему важно начать с файловой системы и аудио! То есть сначала думайте о своей базе данных как о коллекции MP3, прежде чем рассматривать ее как коллекцию видео.
Игнорируя аудио, видео - это просто упорядоченная последовательность неподвижных изображений.Таким образом, мы на самом деле ищем один или несколько алгоритмов сравнения изображений в сочетании с одним или несколькими алгоритмами сравнения временных рядов.Это могут быть либо пары отдельных алгоритмов (характеризовать каждый кадр, затем характеризовать последовательность кадров), либо это может быть объединено в единый алгоритм (посмотрите на различия между кадрами).
Сами изображения могут бытьдалее разлагается на монохромное «структурное» изображение и цветное «наложение».Я считаю, что мы можем спокойно игнорировать информацию о цвете, если это удобно с вычислительной точки зрения.
Исходя из вышесказанного, может показаться, что я предполагал, что нам придется полностью декодировать видео, чтобы выполнитьлюбые сравнения на нем.Это не обязательно так, хотя сравнение кодированных данных имеет много трудностей, которые ограничивают их полезность.Единственным существенным исключением является кодирование видео на уровне объекта, такое как MP4, где было выполнено многокадровое сравнение очень высокого уровня.К сожалению, сравнение объектов между потоками MP4 не было исследовано, и я не знаю ни одного пакета, способного выполнить эту функцию.Но если вы найдете такой, используйте его!
Большинство других цифровых видеопотоков используют схемы кодирования, такие как MPEG2, Quicktime или что-то подобное.Все эти схемы используют концепцию ключевых кадров и разностных кадров, хотя каждая реализует ее по-своему.Когда сравниваются разные видео (не одинакового размера), маловероятно, что ключевые кадры и разностные кадры будут соответствовать какой-либо полезной степени.Однако это не означает, что это невозможно, и существуют пакеты, которые пытаются извлечь полезную информацию из таких потоков, не выполняя полное декодирование.Если вы найдете такой быстрый, он может попасть в категорию тестов «почему бы не попробовать».
Единственный прием, который я буду использовать, - это вместо полного декодирования кадров, я бы вместо этого декодировал их только в отдельныекомпонентные каналы (HSV, HSL, YUV и т. д.), а не весь путь до кадрового буфера RGB (если, конечно, это не то, что было закодировано).Далее я бы создал отдельные кадры яркости и цветности (цвета), чтобы можно было проводить сравнения в смежных областях.Полное декодирование до кадрового буфера RGB может привести к ошибкам, которые могут затруднить поиск совпадений.
Далее я бы отбросил информацию о цвете.Поскольку монохромное видео должно соответствовать цветному оригиналу, нам просто наплевать на цвет!
Как лучше всего сравнить результирующую последовательность монохромных кадров с другой последовательностью, которая может выглядеть совсем иначе, но все же возможноматч?В этой области проводились буквально десятилетия исследований, большая часть которых была отнесена к категории «обнаружение совпадений, зависящее от масштаба».К сожалению, очень мало этого исследования было непосредственно применено для определения того, когда видео соответствуют или не соответствуют.
Для наших целей мы можем подойти к этому вопросу с нескольких сторон.Во-первых, мы должны знать для себя, что является и не совпадает в монохромной области.Например, нас не волнуют различия на уровне пикселей, поскольку даже если два совпадающих, но разных видео имеют одинаковое разрешение, мы должны допускать некоторый уровень шума из-за таких вещей, как различия кодировщика.
Простой(но медленный) путь вперед - преобразовать каждое изображение в форму, которая не зависит ни от разрешения, ни от соотношения сторон.Одним из таких преобразований является пространственная частотная область, и 2D БПФ идеально подходит для этого.После отбрасывания мнимого компонента реальный компонент может быть обрезан на высоких частотах для удаления шума и на низких частотах для устранения эффектов соотношения сторон, а затем нормализован по стандартной шкале для устранения различий в разрешении.Полученные данные выглядят как странное крошечное изображение, которое можно напрямую сравнивать по видеопотокам.
Существует много других возможных стратегий преобразования кадров, многие из которых гораздо более эффективны, чем БПФ, и поиск литературы должен их выделить.К сожалению, я знаю немногие, которые были реализованы в программных библиотеках, которые так же просты в использовании, как и БПФ.
Как только мы превратили монохромные кадры в меньшую и более полезную область, мы все равно должны выполнить сравнениев другой такой поток из другого видео.И это видео почти наверняка не будет соответствовать кадрам, поэтому простое сравнение, безусловно, не удастся.Нам нужно сравнение, которое будет учитывать различия во временной области, в том числе добавленные / удаленные кадры и различия в частоте кадров.
Если вы посмотрите на последовательность кадров FFT, вы заметите некоторое совершенно отличное поведение.Сцены сцены являются резкими и чрезвычайно легко обнаруживаемыми, также можно различить разрезы, и обычно между БТП наблюдаются только медленные изменения в БПФ.Из последовательности БПФ мы можем пометить каждый кадр как первый после вырезания / затухания или как кадр между вырезками / затуханиями.Важным является время между каждым кадрированием / выцветанием, независимо от числа кадров между ними, которое создает подпись или отпечаток пальца, который в значительной степени не зависит от частоты кадров.
Взятие этого отпечатка всего видео дает данные, которыезначительно меньше, чем само видео.Это также линейная последовательность чисел, простой вектор временного ряда, очень похожий на звук, который может быть проанализирован с использованием множества одинаковых инструментов.
Первый инструмент - выполнить корреляцию, чтобы определить,образец сокращений в одном видео близко соответствует тому в другом видео.Если есть существенные различия, то видео отличаются.Если они близко совпадают, то нужно сравнить только несколько БПФ после каждого коррелированного среза, чтобы определить, достаточно ли похожи кадры, чтобы соответствовать.
Я не буду вдаваться в сравнение 2D БПФздесь, поскольку существует множество ссылок, которые выполняют эту работу гораздо лучше, чем я.
Примечание. Существует множество других манипуляций (помимо 2D FFT), которые можно применять к монохромным кадрам для получения дополнительных отпечатков пальцев.Представления фактического содержимого изображения могут быть созданы путем извлечения внутренних краев изображения (буквально как отпечаток пальца ФБР), или путем выборочного порога изображения и выполнения операции «blobbing» (создание связанного списка дескрипторов связанных областей).Отслеживание эволюции краев и / или пятен между кадрами можно использовать не только для создания списков вырезов, но также для извлечения дополнительных характеристик изображения высокого уровня, которые могут быть потеряны при использовании 2D-БПФ.
Мы создали последовательность алгоритмов сравнения, которая должна очень быстро находить несоответствия и не требовать слишком много времени для окончательного определения совпадений.Увы, наличие алгоритмов не является решением проблемы!Мы должны рассмотреть несколько вопросов, связанных с тем, как лучше всего реализовать эти алгоритмы.
Во-первых, мы не хотим открывать и читать каждый видеофайл больше, чем необходимо, иначе процессор может остановить ожидание данных отдиск.Мы также не хотим читать в файл дальше, чем нужно, хотя мы не хотим останавливать чтение слишком рано и, возможно, пропустим более позднее совпадение.Должна ли быть сохранена информация, характеризующая каждое видео, или она должна быть пересчитана при необходимости?Решение этих проблем позволит разработать, протестировать и развернуть эффективную и эффективную систему сравнения видео.
Мы показали, что можно сравнивать видео с некоторой надеждой найти совпадения в условиях высокой вариабельности и с вычислительной эффективностью.
Остальное оставлено в качестве упражнения для читателя.; ^)