Аннотация видео методами машинного обучения

Введение

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

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

Задача проекта

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

Обзор проекта и принцип работы

Видеофайл чаще всего содержит в себе две компоненты: видео-поток и аудио-поток. В данный момент мы работаем только с видео-потоком.

Обработка видео проходит в несколько стадий:

• Загружаем видео с компьютера пользователя или через ссылку с youtube.com;
• Разбиваем видео на отдельные кадры;
• Классифицируем изображения, полученные из видео;
• Собираем статистику;
• Выводим теги.

Разбиение видео на отдельные кадры

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

Классификация изображений

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

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

	Релевантные	Нерелевантные
Выданные	RF	IF
Невыданные	RN	IN

По значениям элементов матрицы вычисляется большинство метрик, которые мы рассмотрим ниже.

1. Полнота

Полнота определяется как отношение выданных релевантных изображений к общему количеству релевантных изображений:

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

2. Точность

Точность вычисляется как отношение выданных релевантных изображений к общему количеству выданных изображений:

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

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

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

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

1. Объект присутствует на изображении. Классификация изображений.

Определение категории объекта на изображении — автомобиль.

2. Известно местоположение объекта. Обнаружение и локализация объекта.

Обнаружение и локализация объекта на изображении — автомобиль.

Для нашего приложения мы используем оба уровня локализации.

1. Определение категории объекта на изображении

Задача определения категории объекта на изображении, как правило, решается по следующей схеме:

• Представление изображения в виде вектора признаков;
• Обучение и использование классификатора с векторов признаков.

Для представления изображения в виде вектора признаков могут использоваться следующие признаки:

• Гистограммы цвета;
• Гистограммы градиентов (гистограмма направленных градиентов, HOG (Histogram of Oriented Gradients), SIFT);
• Матрицы смежности;
• Мешки визуальных слов (bag of visual words).

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

• Метод ближайшего соседа;
• Метод опорных векторов, SVM (support vector machine);
• Нейронные сети;
• Марковские случайные поля.

Также задача определения категории объекта на изображении может решаться при помощи методов глубинного обучения (deep learning), таких как сверточные нейронные сети. [2]

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

Основная идея классификации при помощи «визуальных слов»:

1. Набор изображений разбивается по категориям.

Разбиение изображений по категориям

2. С каждой категории извлекается набор характерных признаков, либо изображение делится равномерно при помощи сетки.

3. Из полученных фрагментов-признаков создаются вектора признаков.

4. Полученные вектора разбиваются на кластеры методом k-средних. Полученные кластеры компактны и разделены между собой.

5. Каждый кластер представляет собой визуальное слово. [3]

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

6. Для каждой картинки создаётся гистограмма из «визуальных слов».

Гистограммы «визуальных слов»

7. Из полученных гистограмм «визуальных слов» создаются вектора и на них обучается классификатор изображений методом опорных векторов, SVM.

Метод опорных векторов, SVM

8. Для каждой категории получают свой «мешок визуальных слов».

«Мешок визуальных слов» для лица человека

«Мешки визуальных объектов» для разных категорий

2. Обнаружение и локализация объекта

Задача локализации объекта на изображении, как правило, решается по следующей схеме:

• Изображение разбивается на фрагменты. Чаще всего используется метод скользящего окна с разным масштабом;
• Мы обучаем и запускаем классификатор с использованием векторов признаков, учитывая их пространственное расположение, то есть взаимное расположение признаков относительно друг друга.

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

Популярные алгоритмы и методы получения признаков:

• Метод Виолы-Джонса;
• Оператор локальных бинарных шаблонов (LBP, Local Binary Patterns);
• Гистограмма направленных градиентов, HOG (Histogram of Oriented Gradients).

Также для задачи обнаружения и локализации объекта может использоваться глубинное обучение. [4] [5]

Для нашего приложения мы используем метод Виолы-Джонса, т. к. среди прочих (LBP, HOG) он даёт наибольшую точность при большей полноте.

В методе Виолы-Джонса используются примитивы Хаара. [6]

Примитивы Хаара (Haar basis functions) используемые в методе Виолы-Джонса

На youtube.com есть простой и понятный пример визуализации работы каскадного классификатора Хаара (Haar-Cascade Classifier):

Реализация

Классификацию видеокадров команда начала с применения каскадных классификаторов Хаара. В свободном доступе имеются следующие классификаторы:

• 5 классификаторов на анфас человеческого лица;
• 2 классификатора на профиль человеческого лица;
• 2 классификатора на кошачьи морды;
• 1 классификатор на машины;
• 1 классификатор на механические часы.

Мы подключили их в проект и начали тестирование. Изначально было много ложных срабатываний.

Ложные срабатывания при определении машин, человеческих лиц, кошачьих морд и механических часов

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

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

Также мы пробовали внедрить классификаторы на основе локальных бинарных шаблонов (LBP). Однако в рамках нашей задачи они показали неудовлетворительные результаты.

В OpenCV 3.0 в extra modules добавлена возможность определения текста на изображении. [7] Мы решили, что дополнительная категория «текст» пригодится нам в качестве тега.

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

Примеры определения текста

Примеры ложных срабатываний при определении текста

Затем команда переключилась на работу с SVM классификаторами. В проекте использованы стандартные классификаторы OpenCV, обученные на наборе данных VOC 2007. [8]

• Самолёт
• Велосипед
• Птица
• Водное транспортное средство
• Бутылка
• Автобус
• Машина
• Кот
• Стул
• Корова
• Обеденный стол
• Собака
• Лошадь
• Мотоцикл
• Человек
• Растение в горшке
• Овца
• Диван
• Монитор/телевизор

Удовлетворительные результаты показали классификаторы на следующие объекты: велосипед, машина, мотоцикл, человек. Монитор/телевизор неплохо определялся только в выключенном состоянии. Сейчас в проект включены классификаторы на машины и людей.

SVM классификатор показал значительно большую полноту, чем классификатор на признаках Хаара. Приблизительно в 2-3 раза больше для людей, чем 7 классификаторов Хаара, обученных на лица. При этом классификаторы Хаара срабатывают только на лица, а SVM классификатор срабатывает на лица, торс людей (даже со спины) и людей в полный рост, находящихся далеко. Более того, SVM классификатор работает даже в мультипликационных фильмах.

Кадры, с найденными людьми, определенные 7 классификаторами Хаара

Кадры, с найденными людьми, определенные SVM классификатором

Кадры мультипликационного фильма, с найденными людьми, определенные SVM классификатором

Однако иногда происходят ложные срабатывания, некоторые из которых понять непросто.

Примеры ложных срабатываний SVM классификатора на людей

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

Полнота классификатора Хаара на машины очень низкая, срабатывания происходят при хорошем контрасте и только на фронтальную/заднюю часть автомобиля.

Работа классификатора Хаара на машины

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

Пример работы SVM классификатора на машины

SVM классификатор на котов показал неудовлетворительные результаты. Поэтому котов на кадрах видео сейчас определяют классификаторы Хаара. Точность классификации у них высокая, но полнота остается низкой. Это связано с тем, что у котов мало общих характерных признаков: разнится окрас и пропорции морды.

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

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

Сложности в реализации и текущий статус проекта

При реализации проекта мы столкнулись со следующими проблемами:

• Недостаточно стабильных классификаторов в свободном доступе;
• Классификация кадров видео — весьма ресурсоёмкий процесс;
• На подбор порогов точности для каждого классификатора тратится много времени;
• Ложные срабатывания классификаторов могут привести к ошибкам в тегах.

На данный момент приложение работает на сервере с процессором Intel Core i7-5820K 3.3GHz 15Mb Socket 2011-3 OEM (6 ядер) и обрабатывает видео параллельно в 12 потоков. Приложение может выдавать следующие теги: people, cats, cars, text. На обработку уходит приблизительно в 3 раза меньше времени, чем на просмотр ролика целиком, а пороги точности калибруются в зависимости от ложных выводов тегов.

Выводы

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

R&D специалисты Azoft предложили несколько интересных идей, развивающих функционал приложения: распознавание музыки так, как это делает сервис Shazam, [9] распознавание текста (если какое-то слово часто встречается на видео, например, BBC, BAR, RT, — оно выводится в качестве тега). Можно добавить классификаторы на логотипы известных компаний: Apple, Coca-Cola, Adidas, или обучить SVM классификаторы на новых наборах данных.

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

Список использованных источников и литературы

[1]    Варламов А.Д. Основные метрики, оценивающие качество работы систем поиска изображений // Алгоритмы, методы и системы обработки данных. № 24. 2013. С. 3-12.

[2]   Krizhevsky, Alex. «ImageNet Classification with Deep Convolutional Neural Networks«. Retrieved 17 November 2013.

[3]   Image Classification with Bag of Visual Words: [Электронный ресурс ] // MathWorks.

[4]   C. Szegedy, A. Toshev, and D. Erhan. «Deep neural networks for object detection«. In Advances in Neural Information Processing Systems (NIPS), 2013.

[5]   Shawn McCann, Jim Reesman. «Object Detection using Convolutional Neural Networks«. CS 229 Machine Learning Final Projects, Autumn 2013.

[6]   P. Viola and M.J. Jones, «Rapid Object Detection using a Boosted Cascade of Simple Features», proceedings IEEE Conf. on Computer Vision and Pattern Recognition (CVPR 2001), 2001.

[7]   Scene Text Detection: [Электронный ресурс] // OpenCV 3.0.0-dev documentation.

[8]   The PASCAL Visual Object Classes Homepage [Электронный ресурс] // Pascal 2.

[9]   Shazam: [Электронный ресурс].