Немного о поиске

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

Что мы ищем?

• Текст
• Документы
• HTML странички
• Изображения
• Аудио
• Видео
• Двоичные файлы

Для некоторых видов данных существуют специализированные поисковые системы. Например, существуют сайты специализирующиеся на поиске DLL файлов.

Поиск видео

Давайте рассмотрим поиск видео информации. Каким образом можно это сделать? Чисто теоретически?

• По тексту
• По изображению
• По короткому видео фрагменту
• По короткому аудио фрагменту

Текущее положение дел

Поисковики

• Google
• Microsoft
• Yandex

Я назвал три крупнейшие поисковые системы и все они позволяют осуществлять поиск видео по тексту и по изображениям.

Недостатки современных поисковых систем

К сожалению, все они страдают от следующих проблем:

• Не всегда есть точное название найденного видео. Вместо этого может быть правильно указан актёр и представлены другие изображения с ним.
• Нет точного указания положения в видео. А это весьма полезная информация.

Да, это так. Попробуйте сами и Вы убедитесь, что я прав. Поисковым системам свойственна некоторая неопределённость. Посмотрите скриншот представленный выше, тот, на котором изображён Том Хэнкс. Нет ни названия фильма, ни позиции, в которой он сделан.

Постановка задачи

Перед тем как приступить к решению задачи, давайте попытаемся её описать. Итак, что мы хотим?

Желаемая скорость выполнения запроса

В наше время никто не будет ждать несколько минут выполнения поискового запроса. Однако объем данных и вычислений может быть таков, что потребуется определённое время для обработки запроса. Нужно идти на компромисс. Время выполнения поискового запроса условно ограничим 10 секундами (± несколько секунд). Это, с одной стороны, позволит браузеру не разрывать соединение, а, с другой стороны, даст время скриптам для обработки информации.

А каков объём данных?

Давайте прикинем в уме.

Количество видео

Согласно базе данных по кинематографу IMDb, всего было снято около 2,6 миллионов кинолент, включая отдельные эпизоды сериалов, мультфильмы и короткометражки. (Информация на 13 ноября 2018 года).

Для начала ограничимся круглым числом 1 миллион видео. Понятно, что мы даже не пытаемся коснуться YouTube и других аналогичных сервисов, где объём видео в разы больше. И главное, этот снежный ком будет только расти.

Количество кадров

Некоторые фильмы или эпизоды сериалов довольно коротки. Есть по 15-20 минут. С другой стороны, есть немало фильмов продолжительностью до 2 часов и более. Не мудрствуя лукаво, примем среднюю продолжительность видео равной 1 часу.

Большое количество фильмов сняты с частотой 24 кадра в секунду, но есть и более скоростные. В наше время каждый может снять свой фильм, а частота кадров в нём может быть и 60 и 100 и 200 FPS и выше. Всё зависит от видеокамеры, фотоаппарата, экшен-камеры, смартфона, камеры видео наблюдения и т. д. (нужное подчеркнуть). Всё в наших руках. Но, давайте примем в первом приближении частоту кадров среднестатистического видео равной 30 FPS.

В этом случае в среднестатистическом видео будет:

30 FPS * 3600 сек = 108 000 кадров

Округляя получим, что в среднестатистическом видео порядка 100 000 кадров.

Объем данных

Каков объём хранения информации об одном кадре? Очевидно, что это значение зависит от алгоритма сравнения кадров в нашей базе данных с заданным образцом. Мы используем два алгоритма для сравнения данных. В одном из них на кадр требуется около 30 байт, в другом около 10 байт. Возьмём среднее — 20 байт.

Значит для хранения информации о 1 миллионе видео необходимо

1 000 000 видео * 100 000 кадров * 20 байт = 2 000 000 000 000 байт

Проще говоря, нам потребуется около 2 Тбайт для того чтобы как то описать все наши кадры. Что, вообще говоря, не так уж и плохо, ведь этот объём информации может уместиться на современном HDD или SSD диске. С другой стороны, эту информацию следует как то упорядочить, в противном случае даже для простого чтения 2 Тбайт понадобится уйма времени, а мы ведь договорились, что пользователь не будет ждать более 10 секунд.

Даже если считывать информацию с диска со скоростью 500 Мбайт/сек нам понадобится 2000 секунд, т. е. более получаса!

А сколько серверов нам понадобиться для поиска за указанное время?

Если предположить, что мы храним информацию равномерно на нескольких серверах, то, в этом случае, объём обрабатываемой информации для выполнения одного поискового запроса уменьшается. Например, если у нас 10 серверов, по на каждом из них потребуется обработать не 2 Тбайта информации, а только 200 Гбайт. Или если у нас 100 серверов, то потребуется обработать не 2 Тбайта, а 20 Гбайт информации. В принципе, указанного количества должно хватить для функционирования такой поисковой системы.

Сколько запросов в секунду сможет переварить такая система?

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

Что было сделано

Сначала нами был реализован поиск по видео фрагментам. Однако вскоре был реализован поиск по изображениям.

История

1 июля 2019

В этот день была выпущена первая версия пакета VideoColor. Она включала в себя три части:

• Manager (индексирование исходного видео)
• Server (серверная часть, которая принимает запросы и ищет совпадение в базе индексов)
• Client (клиентское приложение, которое позволяет проигрывать AVI файлы и отсылать поисковые запросы серверу).

Март 2020

Был создан веб-сайт с возможностью идентификации видео по загруженному видео фрагменту.

14 апрель 2020

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

23 июня 2020

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

Поиск по видео фрагментам

Основная идея

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



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

Стоит заметить, что это упрощённая схема. Есть несколько моментов, которые в рабочей схеме отличаются от описанного здесь. Но, в общем, идея именно такая.

Плюсы

• Относительно небольшой размер индексов. Один час видео в проиндексированном виде занимает около 1 МБ. Таким образом, 1000 фильмов, каждый продолжительностью около 2 часов, в проиндексированном виде займут около 2 ГБ.
• Достаточно точный поиск. Даже если видео пережали несколько раз, если оно визуально выглядит удовлетворительным, то фрагмент скорее всего будет найден.
• Для абсолютного большинства поисковых запросов для правильной идентификации достаточно коротких фрагментов 5-10 секунд.
• Качество поиска слабо зависит от разрешения видео (в определённых пределах).
• Поиск идёт исключительно по видео. Аудио из процесса полностью исключено. Плюс в том, что несколько версий одного и того же фильма с разными звуковыми дорожками в результате поиска приведут к одному и тому же фильму. Это исключает ненужное дублирование и, как следствие, экономит ресурсы.

Минусы

• Поиск необходимо вести от начала и до конца. Т.е. при поступлении запроса необходимо сравнить его со всеми образцами в базе данных. Это накладывает определённые ограничения не только на тип памяти для хранения информации, но и для размеров этой самой памяти. Для того чтобы получить ответ за несколько секунд необходимо, чтобы индексы находились в оперативной памяти. Чем больше база, тем больше места в ОЗУ выделено для хранения информации и тем дольше будет длиться поиск. Например, для 2-х канального доступа и при использовании памяти DDR3 частотой 1600 МГц для поиска по базе размером 12 ГБ понадобится минимум около 0,5 секунды. Для базы размером 48 ГБ необходимо будет уже порядка 2-х секунд минимум.
• Для очень темных или очень светлых мест в видео (обычно это эффекты перехода между сценами) на коротких исходных фрагментах поиск будет работать плохо. Будут многочисленные совпадения. Что, в общем то, вполне понятно, но неприятно.
• Также будут проблемы идентификации с начальными заставками компаний производителей видео или с сериалами. Что, в общем то тоже, вполне понятно. Это не проблема алгоритма — это дубликаты данных.
• Качество поиска может сильно зависеть от обрезки видео по краям.

Поиск по изображениям

Основная идея

Разбиваем исходное изображение на ячейки таблицы M x N. Находим усреднённое значение красной, зелёной и синей компоненты в каждой из областей. Собственно набор этих значений и будет характеристикой этого изображения, с помощью которой мы сможем их все отличать друг от друга. Заносим эту характеристику в базу данных вместе с указателем на описание видео (Video ID) и порядковым номером кадра в видео. Остаётся лишь вопрос, какие значения принимают M и N? Мы взяли 5 x 5, но Вы можете попробовать другие значения. При небольших значениях этих параметров есть шанс что у нас будет много дубликатов, а при больших — мы потратим много памяти.



Однако это ещё не всё. Если в дальнейшем осуществлять поиск по всем этим характеристикам, то на обработку каждого запроса будет уходить много времени! Как же быть? Можно подсчитать усреднённое значение R, G, B компонент для этого изображения и на основе этих значений группировать их в массиве данных. Например: R=200, G=188, B=212. В этом случае мы заносим информацию о кадре в соответствующий раздел или добавляем поле в таблицу. А при поиске аналогично определяем эти компоненты и ищем с учётом этих параметров. Таким образом, мы во много раз сужаем объём сравниваемых данных и ускоряем поиск.



Если честно, то это только в теории, на практике всё немного иначе. Но это тема для отдельной статьи.

Плюсы

• Относительно небольшой размер данных.
• Есть возможность разбития всех данных на группы и осуществлять поиск по группам, что существенно ускоряет поиск.
• Не требует постоянного хранения больших массивов данных в ОЗУ в отличии от предыдущего метода.
• Низкая вероятность ошибки.

Минусы

• Вследствие того, что после перекодирования видео может несколько отличаться от оригинала, да и JPEG-кодирование (при поиске по изображению) меняет оригинал и группа может быть определена неверно. Это требует либо расширения диапазона группы (приводит к уменьшению скорости поиска) либо к дополнительным поисковым запросам (тоже замедляет поиск).

Инструментарий

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

Поиск видео (клиентская часть)

• Через веб-форму на сайте
• Через приложение «Video Color Capture»

Поиск видео (серверная часть)

• Video Color Server. Существует две версии: Windows (работает как сервис) и Linux (работает под обычным пользователем, запуск через crontab).

Добавление видео

• Через приложение «Video Color Creator»

Области применения поиска видео по видео фрагментам

• Идентификация старых и неизвестных видео фильмов.
• Нахождение и отсечение рекламных блоков.
• Проверка частей видео на предмет заимствования их из других фильмов (плагиат).
• Определение точной даты публикации и названия шоу (передачи) если в репосте отсутствует данная информация.
• Определение более-менее точной позиции проигрываемого потокового видео, если идёт вещание ранее проиндексированного видео.

Идентификация старых и неизвестных видео фильмов

Предположим, что у вас есть файл с корявым названием. Начальная заставка либо отсутствует (замысел автора) либо вырезана. Что это за фильм? Хотелось бы прочитать описание и комментарии тех, кто его просмотрел.

Нахождение и отсечение рекламных блоков

Пример: У вас есть свой самописный видео плеер и вы хотите, чтобы при просмотре потокового видео ваши пользователи видели не рекламу с центральных каналов, а вашу собственную.
Проверка частей видео на предмет заимствования их из других фильмов (плагиат)
Пример: Если есть подозрение, что кто-то использует в своём видео ваше видео (снятое с квадрокоптера).

Определение точной даты публикации и названия шоу (передачи) если в репосте отсутствует данная информация

Пример: Вы смотрите видео-шоу, размещённое на неизвестном сайте. Возможно, вы даже знаете, как это шоу называется, но не знаете, когда оно было показано. Год назад или два?

Определение более-менее точной позиции проигрываемого потокового видео, если идёт вещание ранее проиндексированного видео

Пример: Это может понадобиться если вы хотите прикрутить к чужому потоковому видео приложение, демонстрирующее титры или другую контекстную информацию (карты, ссылки, новости и т. д.). Сперва идёт захват видео, расчёт индекса, идентификация видео и позиции на сервере, а затем приложение выводит в отдельном окне контекстную информацию, синхронизированную с воспроизводимым видео.

Как пользоваться сервисом

Поиск видео через веб-форму на сайте

Для этого необходимо загрузить видео фрагмент или изображение в соответствующее поле формы.



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

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

Поиск видео с помощью приложения

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

Можно ли в одиночку наполнить содержимое базы данных индексной информацией об одном миллионе видео?

Скорее всего нет. Где взять эти видео? Как их прокачать по сети? Где взять вычислительные ресурсы для их обработки?

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



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



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

Планы на будущее

• Ускорение поиска.
• Повышение точности поиска.
• Поиск по аудио фрагментам.

Поиск видео по коротким аудио фрагментам дополнит существующие два метода поиска (по видео фрагментам и изображениям).

Итоги

• В данной публикации мы рассмотрели текущее положение дел с поиском видео.
• Ознакомились с методами поиска видео по короткому видео фрагменту и изображению.
• Рассказали о приложении для поиска видео «Video Color Capture».
• Упомянули о приложении «Video Color Creator» для добавления в общую базу данных видео компании «AAP Software».

Ссылки

Сайт

http://www.videocolor.aapsoftware.ru/
На сайте доступен поиск по короткому видео фрагменту, а также по изображению из видео.

Приложения

• Windows x64 приложение для идентификации видео Video Color Capture
• Windows x64 приложение для добавления видео в базу данных Video Color Creator
• Все приложения бесплатны.

Видео

• Поиск видео по изображению и поиск видео по короткому видео фрагменту
• Поиск фильма по видео фрагменту
• Идентификация видео с помощью программы «Video Color Capture»
• Видео работы с программой «Video Color Capture» версии 1.1
• Работа с программой «Video Color Creator» версии 2.0

Публикации

• Технология видео поиска Video Color