Поиск дубликатов видеофайлов по базе данных (миллионы), отпечаток пальца? Распознавание образов?

В следующем сценарии:

У меня есть проект с каталогом в настоящее время около десяти тысяч видеофайлов, число которых резко возрастет.

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

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

Проблема заключается в том, что видео не являются точными дубликатами. Они могут иметь разное качество, подрезанные, водяные знаки или сиквел/приквел. Или отрезаны в начале и/или конце.

К сожалению, чем лучше сравнение, тем больше процессор и интенсивность памяти он получает, поэтому я планирую реализовать несколько уровней сравнения, которые начинаются с очень грациозного, но быстрого сравнения (maby video lengh с допуском 10%) и заканчиваются окончательным сравнением который решает, действительно ли это дубликат (это будет голосование сообщества).

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

Итак, теперь мой вопрос: какие слои вы можете подумать или у вас есть лучший подход?

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

Вот мои текущие идеи:

длина видео (в секундах)
анализ изображения первого и последнего кадров

Я бы пересчитал изображение до размера эскиза и получил средние значения rgb, а затем сериализовал пиксель за пикселем, если цвет в этом пикселе больше/меньше среднего, представляемого 0 или 1. Поэтому я получаю двоичную строку, которую я может храниться в mysql и выполнять логическую битовую сумму (поддерживаемую mysql внутри) и подсчитывать оставшиеся uneval биты (также поддерживаемые внутри, что тогда было бы расстоянием Левенштейна строк бианри)

разработка битрейта с течением времени с помощью того же кодека vbr

Я бы перекодировал видео в видеофайл vbr с теми же настройками. то я бы посмотрел на битрейт в определенные моменты времени (процентное количество видеороликов или абсолютные секунды... тогда мы бы только проанализировали часть видео). такой же вещь как с изображением. Если битрейт больше среднего, его 1 еще его 0. мы создаем двоичную строку и сохраняем ее в db и вычисляем расстояние Левенштейна позже

аудиоанализ (изменение битрейта и децибел с течением времени, так же как и битрейт видео)
анализ ключевых кадров

Image comarision, как и первый и последний кадры, но на ключевых кадрах? Мы использовали бы те же исходные файлы, которые мы использовали для вычисления битрейта, потому что ключевые кадры тяжелы зависят от кодека и настроек.

разработка цвета с течением времени

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

представить предложения для пользователя для окончательного утверждения...

Или я иду совершенно неправильно? Я думаю, что я не могу быть первым, у кого есть эта проблема, но мне не удавалось найти решения.

Ответ 1

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

Важно, чтобы сравнения выполнялись с использованием доступных вычислительных и временных ресурсов: я сомневаюсь, что решение, требующее нескольких месяцев, будет очень полезно в динамической видео-базе данных. И размер базы данных, вероятно, делает использование облачных вычислительных ресурсов неосуществимым. Поэтому мы действительно заботимся о локальных затратах на каждое сравнение в нескольких разных областях: 1) Хранилище данных, 2) вычислить ресурсы и 3) время.

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

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

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

Чтобы охарактеризовать базу данных, сначала выполните некоторую выборку и сопоставление вручную, чтобы оценить степень соответствия в базе данных. Этот эксперимент должен показать, как избыточные видео "сжимаются": если у определенного видео было совпадение, насколько вероятно, что у него было больше одного совпадения? Какой процент всех матчей также был частью множественного совпадения? Этот процесс даст "модель" базы данных (статистическое распределение), которая будет использоваться для выбора алгоритма и настройки системы.

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

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

Алгоритмы классификации/сопоставления могут терпеть неудачу одним или двумя из двух способов: False Положительные (несогласованные видео не учитываются как совпадение) и False Negative (совпадающие видео ошибочно маркируются как несоответствующие). Каждое из этих неправильных решений имеет ряд связанных с ним вероятностей, и мы хотим свести их к минимуму.

Поскольку мы строим конвейер алгоритма, нам нужны алгоритмы, которые очень хорошо подходят для определения несоответствий без ошибок, то есть они должны иметь чрезвычайно низкую скорость ложного отклонения, и мы не очень заботимся о скорости False Accept. Например, клон Wierd Al видео может выглядеть и звучать очень похоже на оригинал, и мы, возможно, не сможем показать, что это не соответствует оригиналу до тех пор, пока в конвейере алгоритма не будет.

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

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

Но здесь есть "gotcha": как насчет голосовой почты? Если данное видео кодируется дважды, с и без голоса, они соответствуют или нет? Что относительно французского звука против испанского или английского? Если все это следует рассматривать как совпадение, тогда может потребоваться пропустить аудио тестирование.

На этом этапе мы знаем, что записи в файловой системе все "достаточно разные", и мы знаем, что аудиодорожки все "достаточно разные" (если они протестированы), что означает, что мы не можем отложить просмотр видеоданных любым дольше. К счастью, это должно быть сделано только для небольшой части видеоданных, поэтому мы можем терпеть некоторые издержки. Как и прежде, мы по-прежнему хотим сначала попытаться быстро устранить больше несоответствий, прежде чем пытаться позитивно пометить совпадение.

Поскольку нам нужно принимать во внимание изменения разрешения (например, от 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 идеально подходит для этого. После отбрасывания мнимой составляющей реальный компонент может быть усечен на высоких частотах, чтобы удалить шум и на низких частотах, чтобы удалить эффекты соотношения сторон, а затем нормализованные к стандартной шкале устраняют разницу в разрешении. Полученные данные выглядят как нечетное крошечное изображение, которое может быть напрямую сопоставлено между видеопотоками.

Существует много других возможных стратегий преобразования кадров, гораздо более эффективных, чем БПФ, и поиск литературы должен подчеркнуть их. К сожалению, я знаю немногие, которые были реализованы в библиотеках программного обеспечения, которые так же просты в использовании, как и FFT.

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

Если вы посмотрите на последовательность кадров FFT, вы заметите очень четкое поведение. Затухания сцены являются резкими и чрезвычайно легкими для восприятия, также можно различать разрезы, и, как правило, только небольшие изменения наблюдаются в БПФ между разрезами. Из последовательности БПФ мы можем пометить каждый кадр как первый после вырезания/затухания или в виде рамки между срезами/затуханиями. Важно то, что время между каждым вырезом/затуханием, независимо от числовых кадров между ними, создает подпись или отпечаток пальца, который во многом не зависит от частоты кадров.

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

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

Я не буду вдаваться в сравнение 2D FFT здесь, так как есть множество ссылок, которые делают работу намного лучше, чем я могу.

Примечание. Существует много других манипуляций (помимо 2D FFT), которые могут применяться к монохромным кадрам для получения дополнительных отпечатков пальцев. Представления фактического содержимого изображения могут быть созданы путем извлечения внутренних краев изображения (буквально как отпечаток FBI) или путем выборочного порога изображения и выполнения операции "раскачивания" (создание связанного списка дескрипторов связанных областей). Отслеживание эволюции ребер и/или блоков между кадрами может быть использовано не только для создания списков разрезов, но также может использоваться для извлечения дополнительных высокоуровневых характеристик изображения, которые будут потеряны при использовании 2D FFT.

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

Во-первых, мы не хотим открывать и читать каждый видеофайл больше, чем необходимо, иначе CPU может задерживать ожидающие данные с диска. Мы также не хотим читать дальше в файл, чем нужно, хотя мы не хотим слишком быстро перестать читать и потенциально пропустить более поздний матч. Должна ли сохраняться информация, которая характеризует каждое видео, или должна быть пересчитана по мере необходимости? Решение этих проблем позволит разработать, протестировать и развернуть эффективную и эффективную систему сравнения видео.

Мы показали, что можно сравнивать видео с некоторой надеждой найти совпадения в условиях высокой переменной, с вычислительной эффективностью.

Остальное оставлено как упражнение для читателя.; ^)

Ответ 2

Отличный вопрос! Только тестирование покажет, какой из этих факторов будет лучшим показателем. Некоторые идеи:

развитие битрейта с течением времени с помощью того же кодека vbr: Звучит очень интенсивно, но я думаю, что это принесет отличные результаты. Анализ звука кажется, что он даст аналогичные результаты при меньших затратах.
анализ первого и последнего кадров: не было бы 50% из них черным? Лучшей идеей может быть использование самого среднего кадра, но я не стал бы считать этот метод надежным.
Использовать байесовскую статистику, чтобы зафиксировать, какие факторы вносят лучший вклад в положительный матч. Это можно было бы сделать на этапе тестирования, чтобы отсеять бесполезные и дорогостоящие сравнения.
Получить пользователей, чтобы помочь!. Пусть пользователи группируют дубликаты, которые они находят. Они голосуют на одном с лучшим качеством и что он будет выступать в качестве основной/официальной версии внутри группы.
Начните с самых простых сравнений и добавьте более сложные тесты, когда найдете недостатки простых. Длительность видео была бы хорошей, и, возможно, какой-то рудиментарный анализ звука, и проделайте свой путь оттуда.

Ответ 3

Просто попробуйте этот продукт - Дублированный поиск видео (например, Visual Search Pony), который может найти дубликаты видеофайлов различных битрейтов, разрешения и т.д.

Например, star-wars.avi(640x480 H.264) и sw.mpg(1280x720 MPEG) будут обнаружены как дубликаты, если оба они являются копиями большого фильма - Star Wars.

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