Московский государственный университет имени М.В. Ломоносова

Факультет вычислительной математики и кибернетики

Магистерская программа:

Математические и компьютерные методы обработки изображений

Магистерская диссертация:

Автоматическая оценка качества построения карт

салиентности для видеопоследовательностей

Работу выполнил

студент Харенко Максим Викторович Научный руководитель:

к.ф.-м.н. Ватолин Дмитрий Сергеевич подпись научного руководителя Москва 2013 Содержание Аннотация

Введение

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

Обзор существующих решений рассматриваемой задачи или ее модификаций

Модели салиентности

4. 4.1.1 Салиентность из частоты

4.1.2 Салиентность из движения

4.1.3 Салиентность из контраста

Оценка качества карт салиентности.

4. Алгоритмы сравнения изображений

4. Исследование и построение решения задачи

Базы TUD и DIEM

5. Тестирование и генерация

5. Субъективное тестирование

5. Тестирование алгоритмов сравнения

5. Описание практической части

Система тестирования

6. Фильтр для VirtualDUB

6. Реализация алгоритмов сравнения

6. Машинное обучение

6. Заключение

Список цитируемой литературы

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

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

2 Введение Салиентность – это термин обозначающий свойство объекта, человека, пикселя и т.д. выделяться на фоне группы других, соседних объектов того же типа. Карты салиентности – это вероятность того, что при первом взгляде человек обратит внимание на конкретные пиксели (см. рис.1). Карты салиентности имеют множество областей применения в обработке изображений и видео: сегментация, распознавание объектов, сжатие, визуальные эффекты, автофокусировка. На самом деле карты салиентности для изображений и для видео – это две разные темы, имеющие отличия в применении, в алгоритмах построения, в способах оценки и в результатах систем слежения за глазами. Так, к области применения карт салиентности для изображений можно отнести еще: создание миниатюр, изменение размеров изображения с учетом важных областей, веб дизайн, создание коллажей; а для видео: удаление объектов из видеопоследовательности и зрение роботов в реальном времени.

Рис.1 – Пример карты салиентности. Яркость пикселей карты салиентности соответствует вероятности того, что внимание среднестатистического человека будет обращено на них. Большим значениям яркости соответствуют более салиентные пиксели.

На данный момент существует множество разных моделей салиентности, основанных на конкретных свойствах человеческой зрительной системы[1,2,8,13,15,16,17]. Авторы этих моделей проводят выборочное сравнение результатов с несколькими конкурентами, используя собственные примеры, но пока что не существует стандартов, какой-либо общепринятой базы видеопоследовательностей или другого способа сравнить все существующие модели салиентности для видео друг с другом. Это и есть одна из главных проблем, рассматриваемых в данной работе.

Не искушенный в данной области читатель может подумать, что не логично использовать большое количество моделей, а стоит создать одну идеальную модель, соединяющую с некоторыми весами карты салиентности лучших моделей и соответствующую поведению глаз зрителя. Но эта задача очень не тривиальна и вряд ли будет решена в ближайшие несколько лет. Вопервых, проведенные в данной работе тестирования разных моделей показали, что алгоритмы построения карт салиентности могут показывать стабильно хорошие результаты для сцен определенного характера и быть практически бесполезными в других сценах. Так, модели, основанные на обнаружении лиц и движения (а это сильнейшие факторы притяжения человеческого внимания), не имеет смысла применять к видеопоследовательностям без людей или панорамным съемкам природы (без движущихся объектов); а модели, признанные лучшими в детектировании салиентности на изображениях, показывают слабые результаты в сценах с динамической камерой. Во-вторых, рассмотрим подробнее факторы притяжения человеческого внимания (движение, лица, контраст цветов, изменение яркости, отклонения в частотных характеристиках кадра, фокус, геометрия и глубина сцены и др.). Существует множество теорий и гипотез о том, какие факторы сильнее, однако ни компьютерное зрение, ни нейробиология, ни психология не могут расставить приоритеты или дать четкую классификацию, с помощь которой можно математически оценить эти факторы. Другими словами, ответа на вопрос, как соединять разные карты салиентности, нет. В-третьих, понятие «идеальная модель поведения человеческих глаз» не совсем корректно. Поведение человеческих глаз зависит так же от таких психологических факторов как состояние наблюдателя, поставленная задача просмотра и вид просмотра. Эти факторы достаточно абстрактны и сложны для технической реализации.

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

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

Из баз слежения за глазами [4,5] была создана общая база, содержащая 50 видеопоследовательностей. С помощью этой базы, специально созданной системы тестирования и готовых алгоритмов построения карт салиентности по контрасту цветов, движению и частотным характеристикам изображения были получены видеопоследовательности для дальнейшего тестирования. Из полученных видеопоследовательностей были выбраны 50 сцен для создания базы тестовых примеров, состоящих из карты слежения за глазами нескольких карт, построенных для того же кадра разными моделями салиентности. Далее было проведено субъективное тестирование: группе людей показали примеры, и попросили раздать места моделям, учитывая насколько их результаты близки к эталону. Эти примеры так же использовались для тестирования алгоритмов сравнения между картой слежения за глазами и сгенерированной картой салиентности. Был проведен анализ известных алгоритмов SAD, NCC, PSNR, метрики Similarity, предложенной [6], и, разработанных по результатам тестирования, метрик LMA и LMM. Каждый алгоритм для каждого примера расставил модели по близости к эталону, и эти результаты сравнивались с человеческой оценкой. В ходе испытаний победили метрики Similarity и LMA.

Они более других соответствуют человеческой оценке при сравнении карт салиентности. На основе значений Similarity был обучен алгоритм линейной регрессии.

3 Постановка задачи «Карты салиентности» – это достаточно обширная тема имеющая множество направлений для исследований и областей применения. В этой работе главный акцент делался на объективную оценку качества построения карт салиентности. Для этого в первую очередь необходимо провести обзор разных моделей и изучить работу алгоритмов построения карт салиентности.

Многие авторы моделей салиентности в статьях предлагают свои способы сравнения между разными моделями[1,6,8]. Требуется изучить эти способы и выбрать самый объективный. Уже говорилось, что поведение человеческих глаз зависит так же от таких психологических факторов, как состояние наблюдателя (возраст, пол, настроение, жизненный опыт, культура), поставленная задача просмотра (поиск, распознавание, свободный просмотр) и характер просмотра (изображения человек «разглядывает»; видео «смотрит»:

добавляется временная составляющая; а мир «видит»: на притяжение внимания влияет слух, осязание и др.). Для оценки моделей определены следующие ограничения: результаты модели должны соответствовать поведению глаз среднестатистического зрителя при свободном просмотре видеопоследовательностей. Учитывая эти ограничения, для оценки качества результатов моделей было решено использовать результаты систем слежения за глазами.

Следующим шагом необходимо создать базу видеопоследовательностей, содержащую сгенерированные моделями карты салиентности и карты слежения за глазами. Используя эту базу, требуется разработать или выявить из существующих подходов самый объективный способ сравнения карт салиентности.

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

В итоге можно выделить основные цели работы:

а) Провести обзор существующих моделей салиентности;

б) Создать базу карт салиентности;

в) Протестировать алгоритмы сравнения и найти самый объективный способ оценки качества карт салиентности;

г) Для исходного видео научиться автоматически выбирать карту салиентности наилучшего качества.

4 Обзор существующих решений рассматриваемой задачи или ее модификаций 4.1 Модели салиентности Рассмотрим подробнее модели построения карт салиентности. Обычно, модели базируются на идеи, конкретном факторе, притягивающем человеческое внимание, и алгоритме, который вычисляет значения этой особенности на всем кадре. Чаще всего эти особенности основаны на яркости, цветовых составляющих и направлениях градиентов. В случае видео так же берется информация с соседних кадров. Далее для каждой особенности с помощью разницы гауссиан, имеющих центры с координатами особенности, стоится карты особенностей. После чего карты всех особенностей суммируются, к ним применяется нормализация и специальная весовая функция, зависящая от алгоритма построения. Весовая функция определяет, насколько важен конкретный тип особенности. Полученная карта, визуализированная в серой шкале, и является картой салиентности.

Модели салиентности основаны на различных факторах притяжения визуального внимания. Одна из первых моделей салиентности была предложена Koch и Ullman в 1985 году[15]. Они предложили подход, основанный на принципе «победитель забирает все» («winner-take-all»). Этот подход применяется в искусственных нейронных сетях при осуществлении принятия решений и задач классификации. Он заключается в том, что решением считается такая альтернатива, у которой выходное значение соответствующего нейрона является максимальным. Таким образом, на изображении определяется единственный фокус внимания.

Другая известная модель была предложена Bruce A. Draper и Albert Lionelle в 2005 году[16]. Представьте многоэтажный дом с квадратными окнами и одним круглым иллюминатором. Внимание наблюдателя будет обращено на иллюминатор. Модель, выделяющие такие особенности, называется салиентность из геометрии. Она основана на распознавании и выделении отличающихся объектов путем применения к ним таких геометрических трансформаций как перенос, вращение и отражение.

Существует и другие модели, основанные на распознавании. Так в работе [17] при построении карт салиентности учитываются результаты алгоритмов распознания текста на изображениях. Еще один алгоритм, использующий распознавание, реализован в лаборатории компьютерной графики и мультимедиа факультета ВМиК МГУ. Он использует детектор лиц[18] и строит салиентные области в зависимости от распознанных черт лица.

В настоящее время особый интерес составляют модели салиентности учитывающие расстояние от наблюдателя до конкретных объектов сцены.

Такие модели используют алгоритмы построения карт глубины из стереоскопического видео[7]. С помощью карт глубины можно определять салиентные объекты переднего плана и на их основе строить карты салиентности. К этой области можно так же отнести модели, основанные на алгоритмах поиска фокуса камеры оператора.

В этой работе сравнивались три разные модели, основанные на:

частотных характеристиках, движении и контрасте. Для оценки качества автору были предоставлены реализованные (студентами видеогруппы лаборатории компьютерной графики и мультимедиа факультета ВМиК МГУ) алгоритмы построения карт салиентности. Эти три модели будут подробно рассмотрены далее.

4.1.1 Салиентность из частоты Модель была предложена Xiaodi Hou и Liqing Zhang в 2007 году[2] и работает по следующее схеме: часто встречающиеся особенности изображения подавляются, а отклонения от нормы и считаются салиентными областями.

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

а) логарифмический спектр б) усредненный спектр в) остаточный спектр Рис.4.1 – Графики кривых логарифмического (а) усредненного (б) и остаточного (в) спектров Сначала к исходному изображению, как к сигналу от двух переменных, применяется преобразование Фурье. Для получения логарифмического спектра берется логарифм от полученного спектра амплитуд (см. рис. 4.1 а)). Его форму усредняют, использую специальный фильтр свертки (см. рис. 4.1 б)).

Затем из логарифмического спектра вычитают усредненный логарифмический спектр, получается остаточный спектр (см. рис. 4.1 в)). К нему применяют обратное преобразование Фурье и стоят изображение по полученному сигналу.

Это изображение и есть карта салиентности. На рисунках 4.2 и 4.3 приведены исходные изображения и карты салиентности, полученные при тестировании работы этой модели.

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

Модель разработана видеогруппой лаборатории компьютерной графики и мультимедиа факультета ВМиК МГУ и на данный момент находится в стадии публикации. Идея алгоритма заключается в том, что двигающиеся объекты переднего плана более салиентны, чем объекты фона. Сначала определяется движение фона в сцене, а затем оценивается разница между движением локальных объектов и фоном.

Алгоритм, обрабатывающий каждый кадр, состоим из пяти частей:

1. Оценка движения между текущим и предыдущим кадром 2. Сегментация переднего плана/ фона.

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

На рисунках 4.4 и 4.5 приведены исходные изображения и карты салиентности, полученные при тестировании работы этой модели.

Рисунок 4.4 – Результаты работы алгоритма, основанного на движении, на различных сценах Рисунок 4.5 – Результаты работы алгоритма, основанного на движении, на различных сценах 4.1.3 Салиентность из контраста Следующая модель изначально была предложена Stas Goferman в году[1]. Модель салиентности предполагает, что важны не только объекты, на которых сосредоточенно внимание, но и некоторое их окружение, описывающее сцену. Причем объекты, притягивающие внимание, должны сильно отличатся (контрастировать) от окружения.

Для выделения салиентности такого типа предлагается следующий алгоритм. Для каждого пикселя рассматривается некоторая окрестность (квадратный патч вокруг него). Затем, во всем изображении ищутся похожие патчи. Текущий пиксель салиентен, если непохожесть его патча ко всем другим патчам изображения высока. Патч салиентен, если похожие патчи располагаются близко и менее салиентен, если похожие патчи далеко. Мера непохожести патчей рассчитывается по трем цветовым каналам:

патчей Алгоритм хорошо выделяет такие важные детали, как человеческие глаза, тексты и другие мелкие и сложные детали на которых сфокусирована камера, так как их отличие от фона достаточно велико.

На рисунках 4.6 и 4.7 приведены исходные изображения и карты салиентности, полученные при тестировании работы этой модели.

Рисунок 4.6 – Результаты работы алгоритма, основанного на контрасте, на различных сценах.

Рисунок 4.7 – Результаты работы алгоритма, основанного на контрасте, на различных сценах.

Оценка качества карт салиентности.

4. Качество карт салиентности можно оценивать различными путями. В задачах обнаружения объектов оценивается количество правильно распознанных моделью объектов. В задачах сегментации критерий сравнения – точность границ сегментов. При построении коллажей важна красота и информативность выделенной окрестности. Часто для оценки карт салиентности проводится визуальное сравнение: группу людей просят показать «важные» регионы изображения, их результаты объединяются в «эталонную»

карту салиентности и с ней уже сравнивается результаты моделей.

Другой метод оценки карт салиентности – сравнение с результатами технологии слежения за глазами. Группа людей участвует в эксперименте, просматривая набор видеопоследовательностей (см. рис. 4.8). Плавное последовательное движение глаза, когда наблюдатель следит за движением объектов на экране, регистрируется аппаратом как фиксация. После просмотра последовательности все фиксации зрителя сохраняются в карту фиксаций. Для каждого видео отрезка группируется единая карта фиксаций из всех фиксаций всех людей, смотревших эту последовательность. Чем больше людей проходит тестирование, тем общая карта более точно соответствует поведению глаз среднестатистического зрителя.

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

Таким образом, для конкретной видеопоследовательности получаются карты областей, куда в текущий момент времени было сосредоточено множества людей. Будем называть такие карты картами слежения за глазами или истинными картами салиентности 4.3 Алгоритмы сравнения изображений Тема «карты салиентности» при всем разнообразии ее применения, описанном во введении, не имеет стандартов оценки качества в области обработки видео. В прошлом параграфе описывались способы сравнения, но они или субъективны или имеют очень узкий круг применения. Способ сравнения с результатами слежения за глазами, объективно, самый лучший, но даже он вызывает вопросы. Допустим, имеется истинная карта салиентности и две карты, построенные с помощью моделей. Как математически, не «на глаз», определить какая из них лучше? Для этого существуют алгоритмы сравнения изображений.

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

Сумма абсолютных разностей, далее SAD (sum of absolute differences) – алгоритм для измерения похожести между блоками изображения. Он вычисляет модуль разности между всеми пикселями в исходном(I1) и рассматриваемом (I2) изображениях. Разница суммируется и делится на количество всех пикселей в изображении:

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

Так же как мера схожести используется кросс-корреляция, измеряющая похожесть между формами волн двух сигналов (векторизованных изображений). Яркость исходного и рассматриваемого изображений может сильно варьироваться, поэтому их сначала нормализуют делением на стандартное отклонение, таким образом, нормализованная кросс-корреляция, далее NCC (normalize cross-correlation) вычисляется как:

NCC часто применяется при распознавании образов, сопоставлении шаблонов и криптоанализе.

Средняя квадратичная ошибка, далее MSE (mean square error), рассчитывается для двух изображений одно из которых считается зашумленней другого:

Пиковое отношение сигнала у шуму, далее PSNR (peak signal-to-noise ratio), является термином, означающим соотношение между максимумом возможного значения сигнала и мощностью шума, искажающего значения сигнала. Поскольку многие сигналы имеют широкий динамический диапазон, PSNR обычно измеряется в логарифмической шкале:

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

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

5 Исследование и построение решения задачи 5.1 Базы TUD и DIEM Приступая к исследованиям, в первую очередь необходимо было найти базу видеопоследовательностей разного характера, с разрешением от 720х и, конечно, с результатами слежения за глазами большого количества людей.

Эта тема сейчас популярна и активно развивается, многие научные учреждения предоставляют результаты своих испытаний в свободном доступе. Однако проведенный анализ показал, что найти базу, удовлетворяющую поставленным требованиям, не так просто. Дело в том, что более 85% известных открытых баз основаны на слежении за глазами при просмотре изображений[9,10,12].

Некоторые базы с видео имели слишком низкие разрешения или слишком однообразный набор видеопоследовательностей, но главный критерий отказа от базы был низким количеством участников в слежении за глазами. В итоге были выбраны базы TUD и DIEM[4,5].

База TUD, предоставленная лабораторией качества изображений Делфтского технического университета, содержит 25 HDвидеопоследовательностей длинной 20 секунд. Характер видео – фрагменты из фильмов. Карты салиентности с результатами движений глаз 24 человек представлены для каждой секунды последовательности в виде mat файлов.

База DIEM предоставлена международным проектом DIEM (Dynamic Images and Eye Movements), организованным несколькими университетами Европы и США для исследований как и куда смотрят люди[4]. База содержит более ста SD- и HD-видеопоследовательностей длинной от 10 секунд до минут. Характер видеопоследовательностей самый разнообразный: фильмы, трейлеры, новости, спорт, реклама, анимация, съемки природы. В слежении за глазами участвовало от 30 до 100 человек на последовательность. Для получения карт салиентности с результатами движений глаз необходимо использовать приложение CAPRE.exe и файл фиксаций для каждой видеопоследовательности.

Общая база включила в себя 20 роликов из базы TUD и 30 роликов из DIEM.

5.2 Тестирование и генерация Итак, найдя и выбрав базы видеопоследовательностей, можно было приступить к тестированию методов. Первое тестирование проходило на базе TUD. На генерацию карт салиентности для одной видеопоследовательности длинной 20 секунд с 25 fps уходило в среднем по 10, 20 и 30 минут на frequency-, contrast- и motion-методы на (Core 2 Duo 3.1 Гц, 4 Гб Озу, Nvidia 512 mb ). Таким образом, на генерацию карт салиентности для трех методов всего для одной видеопоследовательности в базе TUD уходило около часа.

Учитывая, что в базе DIEM есть ролики по несколько минут, было принято решение создать специальную систему тестирования на языке perl для уменьшения времени и трудозатрат. Подробнее система описана в практической части.

Приложение CAPRE.exe создано для разного рода визуализаций карт фиксаций, например: показывать само видео, фиксации, саккады, менять количество испытуемых, добавлять моргание глаз, имена зрителей, кластеризацию фиксаций и, конечно, карты салиентности. Сохранение карты салиентности для одной видеопоследовательности занимает в среднем около 25 минут. Причем, приложение работает не стабильно и далеко не на всех конфигурациях, очень часто в ходе сохранения приходилось запускать его заново. Автоматизировать работу CAPRE.exe для создания базы карт салиентности не удалось, приходилось сохранять карту салиентности для каждой видеопоследовательности вручную и переключаться на следующий файл фиксаций. Таким образом, была создана база истинных карт салиентности DIEM (30 видеопоследовательностей). Эта база использовалась далее в тестировании алгоритмов сравнения и в машинном обучении.

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

Общее суммарное время генерации заняло больше семи дней.

Тестирования разных моделей показали (см. рис. 4.2-4.7), что алгоритмы построения карт салиентности могут показывать хорошие результаты для сцен определенного характера и быть практически бесполезными в других сценах.

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

5.3 Субъективное тестирование Теперь необходимо было сравнить сгенерированные и истинные карты салиентности. Изучая полученные в ходе генерации результаты, стало ясно, что человек может легко определить, какая модель для конкретной сцены ближе всего предсказала результат слежения за глазами. Поэтому было решено провести субъективное тестирование. Группе людей была поставлена следующая задача. Есть две базы с картами слежения за глазами (DIEM и TUD). Тестируемому предлагался набор сгруппированных кадров (специально вырезанные из видео) слежения за глазами и кадры результатов трех моделей салиентности (по движению, частотный и контрастный), сгенерированными по исходным видео. Требовалось сравнить на глаз каждую модель с картой слежения за глазами, раздать методам места от 1го до 3го и записать места в таблицу.

Сравнивать кадры можно, например, на основе:

– «попадания» салиентных областей на кадрах слежения за глазами в салиентные области методов;

– «попадания» салиентных областей методов в салиентные области на кадрах слежения за глазами;

–по совпадению центров (самых ярких мест) салиентных областей;

–по общей площади не салиентных областей;

–общей похожести 4х кадров (например сильно уменьшенных);

–любых других субъективных домыслов.

На примерах 5.1 и 5.2 показаны предлагаемые для оценки нарезки для двух баз.

База кадров DIEM.

Слежение за глазами: кадр из видео Модели: соответствующий кадр В тестировании приняло участие 6 человек. После того как они расставили места для всех последовательностей, результаты были сведены в общую таблицу для базы DIEM и TUD. За первое место модель получала балл, за третье – 3, следовательно, чем меньше баллов у модели, тем ее результат на данном кадре ближе к истинной карте салиентности. С помощью этих таблиц были построены графики (см. рис.5.1 и рис.5.2), показывающие распределение мест между моделями.

adrenaline_rush_ adrenaline_rush_ adrenaline_rush_ bee_parasites_ bee_parasites_ lego_indiana_jones_ Рисунок 5.1 – Результаты субъективного тестирования для базы DIEM.

База кадров TUD.

Слежение за глазами: карта салиентности полученная в результате просмотра продолжительностью 1сек Модели: усредненный кадр по секунде видео(подробнее в практической части) истинная карта салиентности среднее по секунде метода движения среднее по секунде контрастного метода медиана по секунде частотного метода Рисунок 5.3 – Результаты субъективного тестирования для базы TUD.

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

5.4 Тестирование алгоритмов сравнения Используя базу кадров, для которой было проведено субъективное тестирование, началось тестирование алгоритмов сравнения. Целью тестирования было найти алгоритм, наиболее точно, по сравнению с субъективным тестированием, расставляющий места моделям салиентности на всех последовательностях. Алгоритмы сравнения(SAD, NCC, PSNR, Similarity, а так же предложенные автором LMA и LMM) были реализованы в MATLAB:

на вход алгоритм получал два изображения (сгенерированную и истинную карту салиентности) и возвращал численную оценку. Для каждого кадра из базы алгоритм сравнения просчитывался для трех моделей(motion,frequency,contrast). Таким образом, на 30 кадров из базы DIEM и 20 из TUD для каждого алгоритма было проведено 150 расчетов. Результаты расчетов, приведенные в виде графиков, где на оси абсцисс указано название видеопоследовательности и номер кадра, а на оси ординат – результат алгоритма сравнения, приведены на рисунках 5.3-5.8 и 5.10-5.15. Стоит отметить, что для SAD, LMM и LMA, чем ниже график, тем ближе результат конкретной модели к истинной карте салиентности, для NCC, PSNR и Similarity, чем выше – тем лучше.

Рис.5.5 –NCC для базы DIEM.

bee_parasites_… bee_parasites_… lego_indiana_j… adrenaline_rus… adrenaline_rus… adrenaline_rus… discoverers_ gummybear_ gummybear_ Изучая сгенерированные и истинные карты салиентности, огромное количество которых было просмотрено в ходе тестирования, автору пришла идея алгоритма сравнения, оценивающего не весь кадр, а только салиентную область в карте слежения за глазами. Внутри этой области ищется заданное количество локальных максимумов (пикселей с максимальным значением в окрестности некоторого радиуса), которые записываются в вектор значений локальных максимумов Gt. Затем для каждого локального максимума рассматривается пиксель с соответствующими координатами на карте салиентности (см. рис.5.9). Среднее в окрестности 3x3 для рассматриваемого пикселя записывается в вектор значений на карте салиентности Sm.После чего рассчитывается остаточный вектор равный абсолютной разности Gt и Sm.

a) Истинная карта салиентности. б) Сгенерированная карта салиентности Рисунок 5.9 – локальный максимум (а) и соответствующий ему пиксель (б) Алгоритм LMM(Local maximum median) упорядочивает остаточный вектор и выбирает центральный элемент (медиана). Алгоритм LMA(Local maximum average) считает среднее арифметическое по остаточному вектору.

discoverers gummybear gummybear Рис. 5.13 – LMA для базы TUD 0. 0. 0. 0. 0. 0. lego_indiana_j… adrenaline_rus… adrenaline_rus… adrenaline_rus… bee_parasites bee_parasites После получения результатов алгоритмов сравнения на базе кадров пришло время выяснить, какой алгоритм оценивает сгенерированные и истинные карты салиентности так же как среднестатистический человек. Для каждой последовательности субъективное тестирование и алгоритм сравнения раздали моделям места. Использовалась следующая система раздачи баллов алгоритмам сравнения: пусть и люди и алгоритм расставляли модели в порядке «ABC», то (для этой последовательности) алгоритм получал максимум баллов;

если люди расставляли модели «ABC», а алгоритм расставлял наоборот «CBA», то ставился минимум баллов. За каждую правильно расставленную пару моделей начислялся один балл, например: «ACB» - 2 балла т.к. «A»

больше «C» и «A» больше «B»; «BCA» - 1 балл т.к. совпадает только «B»

больше «C». Каждый алгоритм прошел такое сравнение на последовательностях и получил общее количество баллов. Так же использовалась квадратичная система баллов, поощряющая точные совпадения. Такие системы оценки дадут алгоритму некоторое количество баллов практически при любом порядке расстановке моделей, поэтому стоит также учесть средний балл системы (1.5 и 3.166 для стандартной и квадратичной оценки). Система баллов и результаты для двух баз представлены на Рис.5.16, Рис.5.17 и Рис.5.18.

Рис. 5.17 Оценка алгоритмов сравнения для базы DIEM для стандартной (слева) и квадратичной (справа) системы баллов. Средняя оценка отмечена горизонтальной линией.

Рис. 5.18 Оценка алгоритмов сравнения для базы TUD стандартной(слева) и квадратичной(справа) системы баллов. Средняя оценка отмечена горизонтальной линией.

Графики, изображенные на Рис.5.17 и Рис.5.18, отображают насколько точно, по сравнению со среднестатистическим человеком, алгоритмы сравнения расставляют места моделям салиентности на всех последовательностях. На трех из четырех графиках побеждает алгоритм Similarity, он всегда с запасом выше средней линии, причем Similarity полностью доминирует на базе TUD (51 балл из 60 возможных для стандартной и 137/180 для квадратичной оценки!), содержащей больше динамичных сцен. Разработанный алгоритм LMA уверенно идет на втором месте и так же всегда находится выше средней линии, причем он даже побеждает при квадратичной оценке на базе DIEM т.к. набрал больше всех полных совпадений (за 9 баллов). Алгоритмы SAD и PSNR сильно отстают от других и можно сделать вывод о не целесообразности их использования для оценки качества карт салиентности. NCC и LMM занимают третье место.

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

Данное исследование дает ответ на вопрос об автоматической оценке качества карт салиентности для видеопоследовательностей. Чтобы сравнить истинную и сгенерированную моделью карту салиентности и дать математическую оценку, соответствующую оценке среднестатистического человека, стоит использовать алгоритм Similarity. Так же можно использовать алгоритм LMA или комбинацию этих двух алгоритмов, что тоже будет соответствовать человеческой оценке.

6 Описание практической части 6.1 Система тестирования Алгоритмы, покадрово обрабатывающие видео, могут работать часами даже для одной видеопоследовательности. А на такую задачу как создание базы результатов работы моделей салиентности могут уйти дни и недели.

Чтобы при каждом запуске алгоритма не указывать новое входное видео и другие параметры на языке perl была создана система тестирования.

Изначально довольно простая главная задача системы (имеется папка с группой видеопоследовательностей и алгоритмы, работающие с видео;

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

Проверять файлы в папке, анализировать названия, искать по заданным суффиксам, сохранять выходные файлы с правильными Переводить видео в формат, с которым работает данный алгоритм С помощью разных (для разных форматов) perl-плагинов для работы с видео узнавать разрешение и количество кадров;

Рассчитывать размер выходного видео;

Указывать кодек для сжатия выходного видео;

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

Создавать пакетные (bat) файлы, содержащие последовательность команд, предназначенных для дальнейшего исполнения и путей к исходным файлам; создавать файлы (vcf) для автоматического управления поведения программы VirtualDUB;

Создавать Avisynth-скрипты, предобрабатывающие видеопоследовательность;

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

6.2 Фильтр для VirtualDUB Истинные карты салиентности, в базе TUD представлены как одна карта на каждую секунду видеопоследовательности. Для каждого видео отрезка секундной длинны авторы сгруппировывали единую карту фиксаций из всех фиксаций всех людей[5]. Сгенерированные с помощью моделей карты салиентности – это видеопоследовательности. Брать из них случайный кадр для сравнения было бы не верно, поэтому было принято решение найти для каждой секунды видеопоследовательности усредненный кадр. На языке C++ был написан фильтр, считающий среднее арифметическое из группы кадров (в зависимости от количества кадров в секунду) и сохраняющий полученный результат в виде изображения. Это сильно упростило создание тестовых данных, т.к. можно было запустить систему тестирования (с настройкой на использование этого фильтра) сразу для всех последовательностей TUD и получить сортированные по папкам средние секунды, которые уже можно было сравнивать с истинными картами салиентности.

Фильтр не обращался к прошлым кадрам, а только использовал информацию, полученную с помощью специально выведенной формулы. Идея фильтра такова: значение каждого пикселя (в текущем кадре) заменять средним арифметическим соответствующих пикселей за все пройденные кадры, которое сохранено в отдельной переменной. Известно Xn – значение текущего пикселя. Обозначим Y = X1+X2+…Xn-1 – сумма значений всех пикселей за прошлые кадры. Тогда для рассматриваемого пикселя среднее арифметическое выражается как:

– известное среднее арифметическое пикселей за прошлые кадры;

m – неизвестная переменная, выразив которую через Y, как:

можно вычислить искомое среднее арифметическое. Выполнив эту операцию для всех пикселей текущего кадра, находится искомый усредненный № кадра видео карта салиентности (движение) слежение за глазами Результаты работы фильтра, приведенные на примере 6.1, наглядно показывают, почему было решено сравнивать результаты слежения за глазами с усредненным кадром, а не со случайным кадром из видеопоследовательности 6.3 Реализация алгоритмов сравнения Алгоритмы сравнения были реализованы в виде MATLAB-функций. В реализации часто использовались известные встроенные функции для открытия, обработки изображений, а так же множество арифметических функций сильно упрощающих расчеты (imread, imresize, ind2gray, reshape,sum,mean,med и др.). Реализации алгоритмов SAD и PSNR полностью основаны на встроенных функциях. При расчете NCC изображения были векторизованы, после чего использовалась функция xcorr. Реализация метрики Similarity была взята у авторов [6].

Для алгоритмов LMM LMA необходимо было построить вектор локальных максимумов на карте слежения за глазами. Для этого требовалось плотно покрыть салиентную область, то есть максимумы должны находиться на расстоянии определенного радиуса (см. рис.6.1). В ходе экспериментов было найдено оптимальное количество максимумов N=30, которое и использовалось в тестировании алгоритма на базе кадров. Радиус определялся R = coef*D/N, где D – длина диагонали кадра, coef = 0.5.

Рисунок 6.1 – Найденные локальные максимумы на салиентной области, Сначала определялось, находиться ли рассматриваемый пиксель изображения в салиентной области (по порогу, в тестированиях p=25). Затем, рассматривалась его окрестность 3x3: проверялось не ли по соседству более салиентных пикселей. После этого проверялось евклидово расстояние до ранее найденных локальных максимумов (функция pdist) и если оно не превышало радиуса, рассматриваемый пиксель считался новым максимумов и добавлялся в вектор.

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

Требуется по цветному кадру из одной из сцен в видеопоследовательности Im(image) дать оценку качества построения трех карт салиентности Sm(saliency map) и выбрать лучшую.

Чтобы определить лучшую карту салиентности нужно сравнить ее с истинной картой салиентности Gt(ground truth) с помощью алгоритма сравнения Similarity. Причем Gt неизвестно, но есть большая база кадров для обучения из которой можно делать выводы. Другими словами требуется решить задачу линейной регрессии, т.е. для случайной величины X сконструировать функцию y=f(X), обученную на вектор-признаке X(Im,Sm) с известными значениями y= Similarity(Gt,Sm). Для того чтобы приступить к решению этой задачи необходимо построить обучающую и тестовую выборки.

Для обучения было принято решение использовать базу DIEM т.к.

истинные карты салиентности в ней представлены в виде видеопоследовательностей.

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

1. Создать базу видеопоследовательностей (исходное видео, три сгенерированных и истинная карта салиентности);

2. Создать большую базу изображений (соответствующих кадров из видеопоследовательностей);

3. Из изображений сделать преставление в виде пары (вектор, число):

(X(Im,Sm), Similarity(Gt,Sm));

Может показаться, что первый этап был частично выполнен в процессе тестирования алгоритмов сравнения. Однако для обучения нужно было выбрать больше разнообразных сцен, поэтому из длинных видеопоследовательностей DIEM с помощью системы тестирования была создана база коротких(30-70 кадров) сцен. База включала видео 70ти сцен и содержала сгенерированные моделями карты салиентности. Исходное видео было в формате mp4, результаты работы CAPRE.exe в формате mov, а карты салиентности – avi.

Для второго этапа была создана новая база, содержащая более пятерок изображений (Im, Gt,3 Sm). Была разработана специальная функция для MATLAB, проходящая по видеопоследовательности с заданным шагом и сохраняющая соответствующие кадры в формате bmp файлов. Для работы с видеопоследовательностями разного формата использовалась matlab- функция mmreader.

Еще две функции для MATLAB были созданы на третьем этапе. Первая уменьшала изображения до разрешения 100x56 пикселей и вытягивала в вектор монохромную Sm и каждую RGB составляющую Im. Таким образом, функция формировала из пары (Im,Sm) один вектор-признак [R,G,B,Sm] (см. рис. 6.2 а).

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

Рисунок 6.2. Представление вектора-признака в виде [RGB+Sm] для изображений, уменьшенных до размеров 100x56 пикселей После создания тренировочной и тестовой выборки можно было приступить к обучению линейной регрессии. Для обучения использовалась известная библиотека GLM для MATLAB. В этой библиотеке реализован ряд классических алгоритмов решения задач классификации и регрессии на основе обобщенных линейных моделей. Эти алгоритмы просты в использовании и, как правило, обладают высокой скоростью работы.

Алгоритм линейной регрессии был обучен на тренировочной выборке (216 векторов-признаков). Для оценки точности использовался корень из средней квадратичной ошибки (RMSE). Текущая ошибка на тестовой выборке (40 векторов-признаков) составила RMSE = 0.2493. Для уменьшения ошибки была использована ядровая радиальная базисная функция (RBF). После вычисления новых признаков с помощью ядровой функции, алгоритм был обучен заново. После тестирования регрессии ошибка на тестовой выборке составила RMSE =0.0784.

Используя коэффициенты линейной регрессии, для каждого нового входного кадра и карты салиентности стало возможно подсчитать вероятности, выдаваемые обученным алгоритмом. На примерах 6.2-6.5 показаны полученные вероятности и значения similarity для соответствующих кадров.

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

Пример 6.2 Сверху: исходный кадр и карта слежения за глазами для последовательности basketball.

Снизу: три карты салиентности, значение Similarity и результаты регрессии.

Пример 6.3 Сверху: исходный кадр и карта слежения за глазами для последовательности hydraulics.

Снизу: три карты салиентности, значение Similarity и результаты регрессии.

Пример 6.4 Сверху: исходный кадр и карта слежения за глазами для последовательностиresignation.

Снизу: три карты салиентности, значение Similarity и результаты регрессии.

Пример 6.5 Сверху: исходный кадр и карта слежения за глазами для последовательности simpsons.

Снизу: три карты салиентности, значение Similarity и результаты регрессии.

7 Заключение В ходе этой работы были решены следующие задачи:

1. Проведен обзор существующих моделей салиентности;

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

3. Создана база для тестирования разных моделей салиентности и алгоритмов их сравнения; Примеры, полученные при исследовании сгенерированных карт салиентности, показали, насколько нетривиальна задача слияния моделей;

4. Проведено субъективное тестирование, дающее понять, как сравнивает карты салиентности среднестатистический человек;

Разработан собственный алгоритм сравнения;

5. Проведено тестирование шести алгоритмов сравнения изображений, в ходе которого были выявлены алгоритмы, подходящие для объективной оценки качества карт салиентности;

6. Обучен алгоритм линейной регрессии, позволяющий без результатов систем слежения за глазами, выбирать карту салиентности, наиболее соответствующую поведению 8 Список цитируемой литературы 1. S. Goferman, L. Zelnik-Manor. Context-aware saliency detection. // IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR), 2010.

2. X. Hou and L. Zhang. Saliency detection: A spectral residual Approach. // 2007 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR), 2007.

3. Hani Alersa, Judith A. Redia, and Ingrid Heynderickxa. Examining the effect of task on viewing behavior in videos using saliency maps. // Human Vision and Electronic Imaging XVII, 2012.

4. Henderson, J.M. Diem video and eye tracking database.

http://thediemproject.wordpress.com/ 5. H. Liu and I. Heynderickx. TUD Image Quality Database: Eye-Tracking Release1. http://mmi.tudelft.nl/iqlab/eye_tracking_1.html.

6. Tilke Judd, Fredo Durand and Antonio Torralba. A Benchmark of Computational Models of Saliency to Predict Human Fixations. // IEEE Transactions on Pattern Analysis and Machine, 2012.

7. А.А. Зачесов, Д.С. Ватолин, М.Б.Колиниченко. Автоматический алгоритм построения многоракурсного видео по стереопаре. // Научно-техническая конференция "Теоретические и технические вопросы записи, воспроизведения и восприятия стереоизображений", 2011.

8. C. Guo, Q. Ma, and L. Zhan. Spatio-temporal saliency detection using phase spectrum of quaternion fourier transform. // 2008 IEEE Computer Society Conference on Computer Vision and Pattern Recognition CVPR, 2008.

9. U. Engelke, A. J. Maeder, and H.-J. Zepernick. Visual Attention Modeling for Subjective Image Quality Databases. // in Proc. of IEEE Int. Workshop on Multimedia Signal Processing (MMSP), 2009.

10.Moran Cerf, Jonathan Harel, Wolfgang Einhuser, Christof Koch. Predicting human gaze using low-level saliency combined with face detection. // Advances in Neural Information Processing Systems (NIPS), 2007.

11.O. Le Meur, P. Le Callet, D. Barba and D. Thoreau. A coherent computational approach to model the bottom-up visual attention. // IEEE Pattern Analysis and Machine Intelligence, 2006.

12.Van der Linde, I., Rajashekar, U., Bovik, A.C., Cormack, L.K. DOVES: A database of visual eye movements. // Spatial Vision, 2009.

13.Tie Liu, Jian Sun, Xiaoou Tang and Heung-Yeung Shum. Learning to Detect A Salient Object. // In Proc. IEEE Cont. on Computer Vision and pattern Recognition (CVPR), 2007.

14.Jonathan Harel, Christof Koch, and Pietro Perona. Graph-based visual saliency. // In Advances in Neural Information Processing Systems (NIPS), 2007.

15.C. Koch and S. Ullman. Shifts in selective visual attention: towards the underlying neural circuitry. Human Neurbiology, 4:219–227, 16. Bruce A. Draper and Albert Lionelle. Evaluation of selective attention under similarity transformations. Comput. Vis. Image Underst., 17. Imamoglu Konuskan, M. Fatma. Visual Saliency and Biological Inspired Text Detection. // Image Understanding and Knowledge-Based Systems, 2008.

18. P.Viola, M.Jones. Robust Real-time Object Detection. // Conference on Computer Vision and Pattern Recognition, 2001.