Элементы поиска нечетких дубликатов видео

Что это

Презентация доклада «Элементы поиска нечетких дубликатов видео» на XIII Всероссийской научной конференции «Нейрокомпьютеры и их применение» (17 марта 2015 года).

Содержание

Кто я

Я сотрудник Яндекса, но по совместителству аспирант и преподаватель МАИ, и сотрудник интернет‑кинотеатра Tvzavr. В данном случае я представляю Московский Авиационный Институт. Мой научный руководитель Владимир Николаевич Лукин.

О чем ?

Я хочу рассказать о поиске нечетки дубликатов видео. Понятие «нечеткий дубликат» означает неполное или частичное совпадение текущего документа (изображения) с другим документом подобного класса. Почему интересно заниматься поиском дубликатов именно видео?

Видео

На слайде приведены ретроспектива и прогноз развития Российского интернет видео.

Данные взяты из http://www.ewdn.com/online-video-russia.html

Online Video in Russia / Adrien Henni, Vladimir Baydin, Alexandra Chekareva et al.;
Ed. by Adrien Henni;
East-West Digital News. –– First edition. –– East-West Digital News, 2013. –– October. ––
Main partners: comScore, Ernst & Young, the Moscow Higher School of Economics, The Next Web.
URL: http://www.ewdn.com/online-video-russia.html

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

Пример ошибочной рекомендации видео

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

Поиск

Поиск нечетких дубликатов полезен и для группировки выдачи поисковых систем. Задача казалось бы простая и должна была бы быть уже решена. Но вот например для фильма «Очаровательный Коралловый Риф» Ни одна из популярных поисковых систем не смогла корректно выделить дубликаты. Пример для Mail.ru Аналогичную картину можно видеть для Яндекса. Такая же проблема наблюдается и для Вконтакте. Ну и для упомянутого ранее тут Youtube.

Группировка новостей

НДВ удобно использовать для просмотра видео‑материалов о событиях, размещенных в разных СМИ. Это особенно полезно для новостей. Видео часто показывают очень похожие визуальные изображения и ролики, но с совершенно различной трактовкой. Авторская интерпретация преподносится зрителям, например, в комментариях диктора или субтитрах. Обычно отличается подача информации в СМИ, которые контролируют разные общественные или политические силы. СМИ, поддерживающие противоположные позиции, могут описать ситуацию поразному, но визуальное содержание, всего скорее, будет близким. Обнаружение таких видео и подача их вместе помогут людям получать более полное представление о происходящем с учетом различных точек зрения.

Подходы к определению понятия НДВ

Тема поиска НДВ относительно нова для научного сообщества.

И потому существует целый ряд различных толкований и определений.

Наиболее употребляемые определения Ву, Шена, Башарата, и Керубини, представленные далее, относятся к одному и тому же.

• НДВ по Ву — копии друг друга, отличаются набором модификаций.
• НДВ по Шену — общая сцена, разные условия съемки и варианты монтажа.
• НДВ по Башарату — общая смысловая концепция, разные варианты представления.
• НДВ по Керубини — общая семантика и нет дополнительной информации.

Схема поиска по видео

Поиск видео состоит из следующих шагов:

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

Сегментация видео

Деление видео включает всебя обнаружение границ съёмок, извлечение ключевых кадров, сегментацию сцен иаудио. Съёмка — набор кадров внутри непрерывной временной области, кадры, которой значительно отличаются от кадров соседних областей. Кадры съёмок связаны между собой по смыслу. Съёмки считаются основной структурной единицей видео. Исторически, съёмка (монтажный план, кинематографический кадр) — отрезок киноплёнки, на котором запечатлено непрерывное действие между пуском и остановкой камеры, или между двумя монтажными склейками. Методы сегментации видео работают с уже созданным видео, и достоверно определить была монтажная склейка или нет, не всегда возможно. Именно по этой причине в литературе используется конструктивное определение съёмки, которое мы привели в начале абзаца. Сцена — группа смежных съёмок, связанных конкретной темой или предметом. С точки зрения семантики, самым мелким элементом видео является кадр (фотографический кадр, кадрик). Съёмка является более крупным делением. Из съёмок складываются сцены, а из сцен видео целиком. Деление видео включает в себя обнаружение границ съёмок, извлечение ключевых кадров, сегментацию сцен и аудио. Это может показаться не естественным, но сегментацию сцен и выделение ключевых кадров проще проводить, если уже известны границы съёмок.

Выделение признаков

Из полученных частей видео выделяют признаки. К признакам относят: характеристики ключевых кадров; объекты; движение в кадре; характеристики аудио и текста.

Типы видео‑сигнатур

Локальные:

• выражают локальную информацию кадра,
• напрямую работают с дескрипторами особых точек.

Глобальные:

• выражают одной сигнатурой целый кадр;
• выражают одной сигнатурой все видео целиком;
• выражают изменении кадров во времени.

Локальные сигнатуры: оценка

Пусть дано некоторое видео:

• разрешение 800 × 600 пикселей;
• в кадре может быть найдено около 1000 точек;

Если таких видео много:

• 100 000 видео‑файлов;
• по 5 ключевых кадров в каждом виде;
• 500 000 000 ключевых точек;

Каждая точка представлена вектором:

• SIFT (128 компонент)
• или PCA‑SIFT (64 компоненты);

Глобальные сигнатуры

Одна сигнатура — целый кадр:

• средние цветовые моменты кадра;
• цветовые моменты областей кадра (дескриптор GIST);
• мешок визуальных слов;
• линеаризация, видео как ДНК;

Одна сигнатура — видео целиком:

• средний цветовой момент видео;
• ссылочная видео‑гистограмма — набор опорных кадров;
• кластеризация кадров.

Пространственно‑временные сигнатуры:

• отслеживание траекторий;
• линеаризация, порядковая сигнатура;
• последовательность монтажных склеек;
• дерево сцен.

Что такое видео?

Видео содержит в себе несколько видов данных.

• метаданные — заголовок, автор и описание;
• звуковая дорожка;
• тексты полученные при помощи технологии оптического распознавания символов (OCR) или при помощи технологий распознавания речи;
• визуальная информация кадров видео.

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

Видео — это последовательность

Видео — последовательность фактов, развивающихся во времени.

• Свойства фактов — пространственная характеристика видео,
• продолжительность и порядок фактов — временная.

Что есть факты?

• простейший вариант — сцены‑съёмки;
• ищем точки смены съёмок (монтажных склеек).

Пространственная характеристика: начальный и конечный кадр («мешок слов», GIST).

Временная характеристика:

• отношения длин съёмок к длинам соседних съёмок
• алгоритмы выравнивания последовательностей.

Результаты и перспективы

Предложен подход:

• относительные длины;
• выравнивания;
• дескриптор фактов в видео;

Проведены эксперименты (17 тыс. фильмов).

Приложения

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

Требования

• make;
• XeLaTeX;
• beamer (библиотека для *TeX);
• tikz (библиотека для *TeX);
• polyglossia (библиотека для XeLaTeX);
• ...

Если чего-то будет не хватать, то не трудно поставить по мере надобности, или отключить в стилях (./styles).

Шрифты

• Times New Roman;
• Calibri;
• SansRoundedLightC;
• SansRoundedC;
• LMMono12;

Используемые шрифты не прилагаются.

Установка

Глобальная

Для сборки установите тему tvzavr для beamer. Она описана в ./styles/Pres/. У меня темы ставятся в

/usr/share/texlive/texmf-dist/tex/latex/beamer/themes/theme/

Локальная

make localthemes

Сборка

make all

Структура

.
|-- src/    ## исходные коды презентации.
|-- img/    ## изображения.
`-- styles/ ## стили.