Отслеживание показа видеороликов в мультимедийных СМИ (телевидение, Интернет) актуально для заказчиков из разных отраслей: для рекламодателей, которым важно подтверждение фактов реальной демонстрации их роликов аудитории потенциальных покупателей; для агентств, которым требуется собирать статистику и составлять рейтинги показа; для производителей видеоконтента, которым надо обнаруживать факты несанкционированного показа и т. д. Пока число роликов и телеканалов невелико, эти задачи можно решать вручную, но по мере их увеличения ручной просмотр всей сетки вещания становится невозможен. Входной информацией для автоматического мониторинга являются поток телеканалов и база данных видеороликов, а выходной — время показа, дифференцированное по роликам и каналам.
Система автоматического мониторинга должна обрабатывать трансляции десятков телеканалов в цифровом качестве в режиме 24/7 без прерывания работы при добавлении новых каналов и дополнительной настройки системы. В ходе мониторинга необходимо вести базу данных видеороликов, а также предоставлять средства ее пополнения. Суммарное количество отслеживаемых роликов может достигать десятков тысяч, при этом один и тот же ролик может быть показан как в полной, так и в сокращенных версиях. Работая в режиме реального времени, система мониторинга должна также уметь накапливать архив трансляций за некоторый период времени с указанием, когда, где и какой ролик был показан с точностью его позиционирования до нескольких кадров. Вполне естественным требованием может быть отсутствие какого-либо специализированного аппаратного и программного обеспечения, а также чрезмерных требований к ресурсам.
На рынке имеется несколько систем выполнения автоматического мониторинга — например Actus AdWatch компании Actus Digits, позволяющая отслеживать рекламные ролики в телетрансляциях. Ключевыми характеристиками данного продукта является высокая достоверность обнаружения, наличие двух независимых систем обнаружения (по видео- и аудиоматериалу), формирование подробных отчетов о результатах мониторинга. Система работает в режиме 24/7 и поддерживает широкий круг форматов кодирования входного потока. Однако цена и высокие требования к оборудованию затрудняют использование такого продукта отечественными заказчиками, которым нужно недорогое, но достаточно эффективное решение по мониторингу рекламных роликов.
В общем случае для проведения видеомониторинга необходим анализ входных данных и формальное описание ключевых требований к системе, но для упрощения видеоинформацию можно представить в виде последовательности кадров с растровым изображением и свести задачу отслеживания видеоролика к поиску в телетрансляции определенного множества кадров. Решение такой задачи «в лоб» вряд ли возможно. Действительно, если считать, что в базе данных 10 тыс. роликов, то каждый новый кадр трансляции потенциально может быть началом любого ролика из базы, и этот кадр нужно искать среди 10 тыс. образцов. Далее, при телевещании используется частота 25 кадров в секунду — это значит, что операцию поиска нужно выполнять 25 раз на каждую секунду трансляции, то есть для обработки часового фрагмента требуется выполнить поиск 60*60*25 = 90 000 раз. Эти проблемы, конечно, решаемы путем распараллеливания и использования специализированных аппаратных систем, однако есть еще ряд более серьезных проблем сравнения кадров, которые невозможно решить методом «грубой силы».
Во-первых, в телетрансляции могут присутствовать различные визуальные элементы (логотипы, бегущие строки, экстренные вставки и т. д.), искажающие изначальный видеоряд, поэтому поиск кадров должен быть нечетким, учитывающим возможные искажения. Во-вторых, хотя система и ориентирована на прием цифрового сигнала, в котором отсутствуют помехи, нет гарантии, что транслируемые ролики будут передаваться без искажений и в их исходном разрешении. Ролик может изменяться даже при смене формата и метода сжатия данных, особенно в случае использования сжатия с потерями. В-третьих, из-за проблем на уровне передачи данных возможны ситуации, когда система будет получать только часть кадров трансляции. Таким образом, поиск должен быть устойчив к смене разрешения, частоты кадров и метода сжатия видеопотока. Анализ перечисленных требований по «нечеткости» сравнения позволяет сделать вывод, что краеугольным камнем системы мониторинга должна быть процедура сравнения двух кадров, от точности которой и будет зависеть эффективность.
Сравнение кадров происходит на основе их сигнатур, представляющих собой битовую матрицу размером 32x32 элемента. Такой размер выбран для того, чтобы одна строка матрицы представляла собой двойное слово (32 бит) — это позволяет эффективно использовать особенности оборудования, оперируя двойными словами, а не массивами байтов. Кадр разбивается на 1024 (32x32) ячейки, и, таким образом, каждый бит сигнатуры соответствует строго одной ячейке. В каждой ячейке вычисляется средняя яркость пиксела, и если она выше заданного порогового значения, то соответствующий бит сигнатуры устанавливается в единицу, иначе — в ноль. Величина порогового значения выбирается с помощью метода Оцу [1], применяемого ко всему кадру.
Очевидно, что если два кадра идентичны или отличаются только разрешением, то их сигнатуры в большинстве случаев будут совпадать. При плавном изменении изображения соседние кадры будут иметь одинаковую сигнатуру, следовательно, система становится менее чувствительна к пропуску кадров. Если же в телетрансляции присутствует логотип, бегущая строка или подобные изменения, то сигнатуры будут незначительно отличаться и для их нечеткого сравнения можно использовать расстояние Хэмминга [2], равное количеству различающихся битов. Сигнатуры можно считать одинаковыми, если это расстояние не больше заданной пороговой величины. Расстояние Хэмминга может использоваться в различных алгоритмах многомерной индексации и поиска данных (R-деревья, M-деревья и т. д.). В результате экспериментов было установлено, что для работы с сигнатурами кадров наиболее эффективны BK-деревья (метрические деревья Баркхарда — Келлера), позволяющие достаточно быстро построить дерево поиска, а затем по заданной сигнатуре осуществлять поиск похожих, просматривая всего 5–8% узлов дерева.
У каждого ролика выбирается несколько опорных кадров, для которых строятся сигнатуры и заносятся в поисковое дерево. Имеется два способа выбора опорных кадров. Для первого кадры берутся через равные промежутки времени, начиная с первого, для второго предполагается разбиение ролика на несколько сцен, у каждой из которых берется начальный кадр. Критерием начала новой сцены является резкое изменение изображения — различие между кадрами превышает некоторый порог.
Алгоритм сканирования видеопотока (см. рисунок) выглядит следующим образом. Для каждого кадра вычисляется его сигнатура, которая затем ищется в дереве поиска. В результате формируется последовательность найденных кадров, для каждого из которых известно, в какой момент времени он был получен и в какой рекламный ролик входит. При этом возможна ситуация, когда один и тот же опорный кадр входит в несколько роликов или, наоборот, для реально переданного ролика была определена только часть его опорных кадров.
.png "Сканирование видеопотока") |
| Сканирование видеопотока |
Далее информация о найденных кадрах передается в модуль голосования, где учитываются следующие факторы: сколько опорных кадров ролика было найдено, какова степень совпадения найденных сигнатур, есть ли отклонение по времени (задержка или ускорение ролика при трансляции). Если в один и тот же момент трансляции определенным критериям удовлетворяют сразу несколько роликов, то выбирается ролик с максимальной продолжительностью. На выходе модуля голосования формируется информация о найденных роликах. При этом если рассматривать частную задачу мониторинга, то появляется возможность обнаруживать неизвестные ролики, отсутствующие в базе данных. Так, если невелико время между показом двух обнаруженных известных роликов, то с большой вероятностью можно утверждать, что это время было занято еще неизвестным роликом.
Для создания промышленной системы необходим ее опытный образец и оценка параметров его работы, в том числе точности и скорости распознавания. Для этого использовались записи видеотрансляций общей продолжительностью 107 часов. База данных включала 500 роликов, которые в указанных записях видеотрансляций встречаются 1600 раз. Система обработала данный поток за 58 минут при точности распознавания 98%. Эти параметры можно интерпретировать следующим образом: использованное аппаратное обеспечение позволяет обрабатывать трансляции примерно сотни каналов и отслеживать в них примерно 500 роликов. Если число каналов или роликов возрастет, то время обработки станет больше часа, система начнет «отставать» от входного контента и будут накапливаться необработанные видеоролики. Кроме того, полученные параметры производительности не учитывают времени, необходимого для предварительной подготовки видео: декодирования и приведения к необходимому разрешению. Дело в том, что точность работы рассмотренного алгоритма практически не зависит от входного разрешения, но скорость может сильно падать по мере увеличения разрешения.
Информация поступает в систему в виде файлов, каждый из которых соответствует одному часу вещания одного канала и содержит высококачественное видео с большим разрешением и частотой кадров. Каждый такой файл сохраняется в архиве, где для экономии дисковой памяти преобразуется в формат с меньшим разрешением и частотой кадров. Аналогично, каждый файл преобразуется в формат, необходимый системе сканирования видеороликов, и, наконец, в формат временного архива. Если система обнаруживает неизвестный ролик, то из временного архива берется необходимый фрагмент трансляции и добавляется в базу данных роликов. Формат хранения временного архива совпадает с форматом хранения видеороликов.
Таким образом, каждый входной файл преобразуется в три различных видеофайла, один из которых поступает на вход системы сканирования. Преобразование видеофайлов является ресурсоемкой операцией, однако оно хорошо распараллеливается, поэтому для работы системы можно использовать масштабируемый кластер с балансировкой нагрузки. В таком кластере имеются вычислительные узлы и один центральный узел, выполняющий роль хранилища видеофайлов. На нем же располагается оперативная база данных, содержащая сведения о всех поступивших в систему видеофайлах и статусах их обработки (скопирован в архив, скопирован во временный архив, отсканирован и т. д). Вычислительный узел обращается к оперативной базе и получает из нее информацию о том, какой файл и как обрабатывать дальше. Затем копирует к себе необходимые файлы, выполняет требующееся преобразование, пересылает результаты работы обратно в хранилище и делает необходимые отметки в оперативной базе. Такая архитектура достаточно масштабируема и хорошо балансируется, она проста в реализации, сопровождении и администрировании.
***
Применяя простые алгоритмы и методы, можно построить систему мониторинга рекламных роликов, демонстрирующую высокую точность поиска и быстродействие, достаточное для решений масштаба реального времени. При этом не обязательно использовать специализированное оборудование, что и подтверждает опытная эксплуатация системы распознавания роликов, реализованная для одного из заказчиков из сферы медиабизнеса.
Литература
- Гонсалес Р. Цифровая обработка изображений / Р. Гонсалес, Р. Вудс. Техносфера. 2006. 1072 с.
- Блейхут Р. Теория и практика кодов, контролирующих ошибки. М.: Мир, 1986. 576 с.
Константин Селезнев (skostik@relex.ru), Максим Ефремов (mefremov@relex.ru), Вадим Мельников (vadim@relex.ru) — сотрудники компании «РЕЛЭКС» (Воронеж).
