- PVSM.RU - https://www.pvsm.ru -
За 10 лет существования ivi мы собрали базу из 90000 видео разной длины, размера и качества. Каждую неделю появляются сотни новых. У нас есть гигабайты метаданных, которые полезны для рекомендаций, упрощают навигацию по сервису и настройку рекламы. Но извлекать информацию непосредственно из видео мы начали только два года назад.
В этой статье я расскажу, как мы разбираем фильмы на структурные элементы и зачем нам это нужно. В конце есть ссылка на репозиторий Github с кодом алгоритмов и примерами.
Видео-ролик имеет иерархическую структуру. Речь о цифровом видео, поэтому на самом нижнем уровне — пиксели, цветные точки, из которых состоит неподвижная картинка.
Неподвижные картинки называются кадрами — они сменяют друг друга и создают эффект движения.
На монтаже кадры нарезают на группы, которые по задумке режиссёра меняют местами и склеивают обратно. Последовательность кадров от одной монтажной склейки до другой в английском языке называют термином shot. К сожалению, русская терминология неудачная, потому что в ней такие группы тоже называются кадрами. Чтобы не запутаться, давайте использовать английский термин. Только введём русскоязычный вариант: «шот».
Шоты объединяют в группы по смыслу, они называются сценами. Сцена характеризуется единством места, времени и персонажей.
Мы можем легко получить отдельные кадры и даже пиксели этих кадров, потому что так устроены алгоритмы кодирования цифрового видео. Эта информация необходима для воспроизведения.
Границы шотов и сцен получить гораздо сложнее. Могут помочь исходники из программ для монтажа, но нам они не доступны.
К счастью, это умеют делать алгоритмы, пусть и не идеально точно. Об алгоритме деления на сцены я сейчас и расскажу.
Мы решаем задачу поиска внутри видео и хотим автоматически протегировать каждую сцену каждого фильма на ivi. Разделение на сцены — важная часть этого пайплайна.
Знать, где начинаются и кончаются сцены, нужно и для создания синтетических трейлеров. У нас уже есть алгоритм, который их генерирует, но пока что детекция сцен там не используется.
Рекомендательной системе тоже полезно разбиение на сцены. Из них получают признаки, которые описывают, какие фильмы нравятся пользователям по структуре.
Задачу решают с двух сторон:
Мы пошли вторым путём, потому что его проще формализовать, и есть научные статьи на эту тему. Мы уже умеем делить видео на шоты. Осталось эти шоты собрать в сцены.
Первое, что хочется попробовать — это кластеризация. Взять шоты, превратить в векторы, а потом классическими алгоритмами кластеризации векторы разбить на группы.
Главный недостаток такого подхода: он не учитывает, что шоты и сцены следуют друг за другом. Между двумя шотами одной сцены не может стоять шот из другой сцены, а при кластеризации такое возможно.
В 2016 году Дэниел Ротман и его коллеги из IBM предложили алгоритм [1], который учитывает временную структуру, и сформулировали объединение шотов в сцены как задачу Optimal Sequential Grouping:
Пока будем считать, что задано, то есть количество сцен известно. Неизвестны только их границы.
Очевидно, что нужна какая-то метрика. Метрик придумали аж три, в их основе лежит идея попарных расстояний между шотами.
Подготовительные этапы такие:
Эта матрица симметрична, а на главной диагонали у неё всегда будут нули, потому что расстояние вектора до самого себя равно нулю.
Вдоль диагонали прослеживаются тёмные квадраты — области, где соседние шоты похожи друг на друга, соответственно меньше расстояние.
Если мы выбрали хорошие эмбеддинги, которые отражают семантику шотов, и выбрали хорошую функцию расстояния, то эти квадраты — и есть сцены. Найдём границы квадратов — найдём и границы сцен.
Глядя на матрицу, израильские коллеги сформулировали три критерия оптимального разбиения:
— это вектор границ сцен.
Хорошая лосс-функция для задачи Optimal Sequential Grouping имеет два свойства:
Оказывается, и не справляются с этими требованиями, а справляется. Чтобы это проиллюстрировать, проведём два эксперимента.
В первом эксперименте сделаем синтетическую матрицу попарных расстояний, заполнив её равномерным шумом. Если попытаемся разделить на две сцены, получим следующую картинку:
говорит о том, что в середине видео есть смена сцен, что на самом деле не верно. У аномальные скачки, если разбиение поставить вначале или в конце видео. И только ведёт себя так, как требуется.
Во втором эксперименте сделаем такую же матрицу с равномерным шумом, но вычтем из неё два квадрата, как если бы у нас было две сцены, слабо отличающиеся друг от друга.
Чтобы обнаружить эту склейку, функция должна принимать минимальное значение при . Но минимум по-прежнему ближе к середине отрезка, а у — к началу. У виден чёткий минимум при .
Тесты тоже показывают, что самое точное разбиение достигается при использовании . Кажется, нужно брать её, и всё будет хорошо. Но давайте сначала посмотрим на сложность алгоритма оптимизации.
Дэниел Ротман и его группа предложили искать оптимальное разбиение методом динамического программирования [2]. Задачу разбивают на подзадачи в рекурсивной манере и решают по очереди. Этот метод даёт глобальный оптимум, но чтобы его найти, нужно перебрать для каждого все комбинации разбиений от 0-го до N-го шотов и выбрать лучшее. Здесь — количество сцен, а — количество шотов.
Без твиков и ускорений оптимизация будет работать за время . В есть ещё один параметр для перебора — площадь разбиения, и на каждом шаге нужно проверять все его значения. Соответственно, время увеличивается до .
Нам удалось внести некоторое улучшение и ускорить оптимизацию с помощью техники Memorization — кеширования результатов рекурсии в памяти, чтобы не считать одно и то же по многу раз. Но, как покажут тесты ниже, сильного прироста в скорости добиться не удалось.
Группа из IBM предположила, что раз многие строки матрицы линейно зависимы, то количество квадратных кластеров вдоль диагонали будет примерно равно рангу матрицы.
Чтобы его получить и при этом отфильтровать шумы, нужно сингулярное разложение матрицы .
Среди сингулярных значений, отсортированных по убыванию, находим локтевую точку — ту, с которой уменьшение значений резко замедляется. Индекс локтевой точки — это примерное количество сцен в фильме.
Для первого приближения этого достаточно, но можно дополнить алгоритм эвристиками для разных жанров кино. В экшн-фильмах сцен больше, а в артхаусе — меньше.
Мы хотели понять две вещи:
Тесты разделили на две группы: синтетические и на реальных данных. На синтетических тестах сравнили качество и скорость работы обоих алгоритмов, а на реальных — померяли качество самого быстрого алгоритма. Тесты на скорость выполняли на MacBook Pro 2017, 2.3 GHz Intel Core i5, 16 GB 2133 MHz LPDDR3.
Мы сгенерировали 999 матриц попарных расстояний размером от 12 до 122 шотов, случайным образом разделили их на 2-10 сцен и добавили сверху нормальный шум.
Для каждой матрицы нашли оптимальные разбиения с точки зрения и , а потом посчитали метрики Precision, Recall, F1 и IoU.
Precision и Recall для интервала мы считаем вот по таким формулам:
F1 считаем как обычно, подставляя интервальные Precision и Recall:
Чтобы сопоставить предсказанные и истинные отрезки в рамках фильма, для каждого предсказанного находим истинный отрезок с наибольшим пересечением и считаем метрику для этой пары.
Вот какие результаты получились:
Оптимизация функции выиграла по всем метрикам, как и в тестах авторов алгоритма.
Чтобы проверить скорость, мы провели другие синтетические тесты. Первый — как зависит время работы алгоритма от количества шотов при фиксированном количестве сцен:
Тест подтвердил теоретическую оценку : время оптимизации растёт полиномиально с ростом по сравнению с линейным временем у .
Если зафиксировать количество шотов и постепенно увеличивать количество сцен , получим более интересную картину. Сначала время ожидаемо растёт, но потом резко начинает падать. Дело в том, что количество возможных значений знаменателя (формула ), которые нам нужно проверить, пропорционально количеству способов, которыми можно разбить отрезков на . Оно вычисляется по формуле сочетания из по :
При росте количество сочетаний сначала растёт, а потом падает по мере приближения к .
Кажется, это круто, но количество сцен редко будет равно количеству шотов, и всегда будет принимать такое значение, при котором сочетаний много. В уже упомянутых «Мстителях» 2700 шотов и 105 сцен. Количество сочетаний:
Чтобы быть уверенными, что всё поняли правильно и не запутались в нотации оригинальных статей, мы написали письмо Дэниелу Ротману. Он подтвердил, что действительно медленно оптимизируется и не пригодна для видео длиннее 10 минут, а на практике даёт приемлемые результаты.
Итак, мы выбрали метрику , которая хоть и немного менее точная, работает гораздо быстрее. Теперь нужны метрики, от которых будем отталкиваться при поиске более качественного алгоритма.
Для теста разметили 20 фильмов разных жанров и годов. Разметку делали в пять этапов:
Вот так выглядит экран разметчика и проверяющего:
А вот так — разбиение по сценам первых 300 шотов фильма «Мстители: Война бесконечности». Слева истинные сцены, а справа — предсказанные алгоритмом:
Чтобы получить матрицу попарных расстояний, мы сделали следующее:
Для каждого видео из датасета мы сгенерировали матрицы попарных расстояний и так же, как для синтетических данных, посчитали четыре метрики. Вот какие цифры вышли:
Мы получили бейзлайн, который работает не идеально, но теперь от него можно отталкиваться, пока ищем более точные методы.
Некоторые из дальнейших планов:
Код обоих методов и эксперименты на синтетических данных опубликовали на Github [5]. Можно потрогать руками и попробовать ускорить самостоятельно. Лайки и пулл-реквесты приветствуются.
Всем пока, увидимся в следующих статьях!
Автор: Александр Коншин
Источник [6]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/blog-kompanii-onlajn-kinoteatr-ivi/352203
Ссылки в тексте:
[1] предложили алгоритм: https://ieeexplore.ieee.org/abstract/document/7823628
[2] динамического программирования: https://en.wikipedia.org/wiki/Dynamic_programming
[3] Xception, обученную на датасете Imagenet: https://keras.io/applications/#xception
[4] попарные Евклидовы расстояния: https://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.distance.pdist.html
[5] опубликовали на Github: https://github.com/ivi-ru/video-scene-detection
[6] Источник: https://habr.com/ru/post/497428/?utm_source=habrahabr&utm_medium=rss&utm_campaign=497428
Нажмите здесь для печати.