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

Question

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

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

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

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

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

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

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

Так что теперь мой вопрос - какие слои могут, ребята, думать или у вас есть лучший подход?

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

Вот мои нынешние идеи:

• Длина видео (секунды)

• Первый и последний кадрный анализ изображений

Я бы сфотографировал изображение к размеру миниатюр и получить средние значения RGB, затем сериализуйте пиксель пикселем, если цвет на этом пикселе больше / меньше среднего, представленного 0 или 1. Так что я получаю двоичную строку, которую я могу хранить в MySQL и делайте булевую битовую сумму (поддерживаемую MySQL внутренне) и подсчитывать оставшиеся неравные биты (как и внутренне, что будет поддержано внутренне, что тогда будет дистанция левенштейна в виде строк Bianry)

• Разработка битрейта со временем с тем же кодеком VBR

Я бы транскторировал видео в видеофильму VBR с той же одинаковыми настройками. Тогда я бы посмотрел на битрейт в определенные точки (процентное содержание видео завершенных или абсолютных секунд .. Тогда мы бы только проанализировали часть видео). То же самое, что и с картиной. IIF Bitrate больше, чем в среднем его 1 еще его 0. Мы делаем двоичную строку и храните ее в БД и рассчитайте расстояние левенштейна позже

• Аудиоанализировать (Bitrate и Decibel Варанация с течением времени как Bitrate видео)

• анализ ключевых кадров

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

• Разработка цвета со временем

Может быть, давайте возьмем одну или несколько областей / пикселей внутри изображения и посмотрите, как они развиваются со временем. А также изменение ABOV / ниже среднего. Я думаю, что я думаю.

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

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

Answer 1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Поскольку нам нужно воспользоваться изменением разрешения (например, от 1080P на iPod), нам понадобится способ характеристики видеоизображения, которая является не только независимой разрешениями, но также терпима на добавленную шум и / или данные, потерянные в рамках Изменение разрешения. Мы должны терпеть изменения частоты кадров (скажем, из 24 FPS фильма на 30 FPS видео). Есть также изменения соотношения сторон, например, от 4: 3 NTSC до 16: 9 HD. Мы хотели бы обрабатывать изменения цвета космического пространства, например, от цвета в монохромный.

Затем существуют преобразования, которые влияют на все эти сразу, такие как транскодирование между HD и PAL, что может одновременно влиять на цветное пространство, скорость кадра, соотношение сторон и разрешением. Характеристики также должны быть терпимы в некоторую степень обрезки и / или наполнения, такие как произойдет из переключателя взад и вперед между 4: 3 и 16: 9 аспектными соотношениями (буквами, но не Pan & Scan). Мы также должны обрабатывать видео, которые были усечены, такие как удаление кредитов с конца функции фильма. И, очевидно, мы также должны обрабатывать различия, созданные различными энкодерами, которые кормяли идентичный видеопоток.

Это довольно список! Давайте рассмотрим некоторые вещи, которые мы можем выбрать не учитывать: я подозреваю, что все в порядке, чтобы не найти совпадение, когда деформация изображения присутствует, несмотря на то, что анаморфная деформация не редкость, особенно в 35 мм широкоэкранных фильмах, которые были напрямую Отсканирован без анаморфной реконструкции (высокие тощие люди). Мы также можем выбрать неудачу, когда большие водяные знаки присутствуют в середине кадра, хотя мы захотите терпеть меньших водяных знаков в углах. И, наконец, все в порядке, чтобы не соответствовать видео, которые были временно искажены или пространственно перевернутыми, например, когда один представляет собой SLO-MO другой, или был перевернут влево-справа.

Это только о покрытии видео пространства? Надеюсь, понятно, почему важно начать с файловой системы и аудио! То есть сначала подумайте о вашей базе данных, как для MP3-коллекции, прежде чем учитывать ее в качестве видеоустановки.

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

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

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

Большинство других цифровых видеопотоков используют схемы кодирования, такие как MPEG2, QuickTime, или что-то подобное. Эти схемы все используют концепцию ключевых кадров и разностных кадров, хотя каждый реализует ее по-разному. Когда сравниваются разные видео (те, которые не являются такими же размерами), маловероятно, ключевые кадры и разностные кадры будут соответствовать любой полезной степени. Однако это не означает, что это невозможно, и пакеты существуют, которые пытаются извлечь полезную информацию из таких потоков без выполнения полного декодирования. Если вы обнаружите, что это быстро, это может попасть в «Почему бы не попробовать» категории тестов.

Один трюк, который я буду использовать, вместо фреймов декодирования, я бы вместо этого декодирую их только на отдельные компонентные каналы (HSV, HSL, YUV, что угодно) и не вплоть до кадра RGB (если это не было кодировано, конечно, ). Отсюда я бы следую, создаю отдельную яркостью и хроминированием (цветных) кадров, поэтому сравнения могут быть выполнены в соответствующих доменах. Декодирование на весь путь к RGB Carmbuffer может ввести ошибки, которые могут сложнее найти совпадения.

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

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

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

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

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

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

Если вы посмотрите на последовательность кадров FFT, вы заметите некоторое особое поведение. Сцена исчезнет крута и чрезвычайно просты в месте, порезы также могут быть выделены, и, как правило, существуют только медленные изменения, которые наблюдаются в FFT между порезами. Из последовательности FFTS мы можем пометить каждый кадр как первым после выреза / исчезновения или как кадр между разрезами / исчезающими. Что важно, - это время между каждым вырезом / исчезновением, независимо от количества кадров между ними, что создает подпись или отпечаток пальца, которая в значительной степени независима от частоты кадров.

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

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

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

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

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

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

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

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

Answer 2

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

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

Answer 3

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

Например, Star-Wars.avi (640x480 H.264) и SW.MPG (1280x720 MPEG) будут обнаружены как дубликаты, если они оба являются копиями великого кино - звездных войн.

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