task2 (Раздаточные материалы)

Московский государственный университет имени М. В. ЛомоносоваФакультет Вычислительной Математики и КибернетикиКафедра Автоматизации Систем Вычислительных КомплексовЛаборатория Компьютерной Графики и МультимедиаКурс "МАШИННАЯ ГРАФИКА"Задание 2: Классификация объектов.Авторы:Данил ГалеевВлад ШахуроАнтон КонушинМосква, 2014Содержание1 Введение32 Загрузка изображений33 Гистограммы ориентированных градиентов43.1Преобразование изображения из цветного в оттенки серого (grayscale).43.2Свертка с фильтрами Собеля . . .

. . . . . . . . . . . . . . . . . . . . .43.3Вычисление градиента в каждом пикселе. . . . . . . . . . . . . . . . .63.4Вычисление гистограмм градиентов . . . . . . . . . . . . . . . . . . . . .63.5Нормализация гистограмм . . . . . . . .

. . . . . . . . . . . . . . . . . .63.6Объединение гистограмм в дескриптор . . . . . . . . . . . . . . . . . . .74 Среда программирования и устройство каркаса75 Требования к заданию86 Формат выполненной работы и критерии оценки.97 Сборка работы108 Детали реализации109 Дополнительные задания119.1Многоклассовая классификация (+2 балла) . .

. . . . . . . . . . . . . . 119.2Нелинейные ядра SVM (+3 балла) . . . . . . . . . . . . . . . . . . . . . 129.3Пирамида дескрипторов (+3 балла) . . . . . . . . . . . . . . . . . . . . . 129.4Цветовые признаки (+3 балла) . . . . . . . . . . . . . . . . . . . . . . . . 1310 Часто задаваемые вопросы141Привет!Как вам известно из курса машинной графики, компьютерное зрение является активно развивающейся областью, имеющей применение в самых разных сферах жизниобщества.

Компьютерное зрение повсюду: в вашем смартфоне (распознавание QRкода), фотоаппарате (распознавание лиц), в сервисах, которыми вы регулярно пользуетесь (images.google.com и images.yandex.ru). Здесь не бывает шаблонных решений:каждая задача требует индивидуального подхода, и каждая идея может о казатьсяключевой. Здесь используются новейшие технологии, мощнейшие компьютеры, качественные 3D - сканеры, используются громадные массивы данных. В этом заданииу вас будет возможность прикоснуться к многообразному и все ещё малоизученномумиру компьютерного зрения. Дерзайте!21ВведениеВ этом задании вам предстоит заняться бинарной классификацией.

Все входныеданные делятся на два класса: изображения, на которых есть самолет, и изображения, на которых его нет. Ваша задача - обучить классификатор таким образом, чтобына новом входном изображении он смог определить наличие на нем самолета.Вот примерная схема работы классификатора:• Загрузка размеченных изображений.• Извлечение признаков. Каждое изображение описывается некоторым множеством признаков, называемым дескриптором. Мы будем использовать дескриптор на основе гистограмм ориентированных градиентов, или HOG.• Обучение классификатора.

Классификатор - некая подпрограмма, которая умеет, обучаясь на переданных нами данных, отличать изображения разных классов друг от друга. При этом на вход классификатору поступают именно дескрипторы картинок.• Тестирование классификатора на контрольной выборке.2Загрузка изображенийИзображения нужно скачать и распаковать в корневую директорию этого про-екта. Функции загрузки данных уже реализованы, поэтому вы можете пропуститьэтот раздел.Данные для базовой части задания (бинарной классификации) расположены вподпапке data/binary.Данные разбиты на обучающую и тестовую выборки, каждая из которых всвою очередь состоит из двух частей: собственно фотографий (поддиректорияdata/binary/train и data/binary/test соответственно) и списка файлов и соответствующих меток классов (data/binary/train_labels.txt и data/binary/test_labels.txt).

Обратите внимание, изображения имеют различный размер.33Гистограммы ориентированных градиентовПодробно об этом дескрипторе можно прочитать на википедии , а также в работеНавнита Далала и Билла Триггса. Здесь же мы кратко опишем суть реализуемогоалгоритма.3.1Преобразование изображения из цветного в оттенки серого (grayscale).Яркость пикселя grayscale-изображения рассчитывается по следующей формуле:Y = 0.299R + 0.587G + 0.114B3.2Свертка с фильтрами СобеляСначала опишем основные понятия.Понятие свертки изображений проиллюстрированно на приведенных рисунках,подробнее можно прочитать на википедии.

Там же можно прочитать и о различныхспособах обработки границ изображения чтобы выбрать оптимальный.4Фильтром Собеля называется  свертка изображения с ядром (−1; 0; 1) (горизон-1  тальный фильтр Собеля) и  0  (вертикальный фильтр Собеля). −1Градиент яркости пикселей — вектор роста яркости писелей. Направлениевектора показывает, в каком направлении от данного пикселя изображение становится светлее, а модуль вектора — на сколько светлее.5Итак, второй шаг алгоритма заключается в свертке полученного после прошлогошага grayscale-изображения с горизонтальным и вертикальным фильтром Собеля,получая два изображения-матрицы. Каждый элемент первой матрицы равен горизонтальной составляющей градиента яркости пикселей, а второй — вертикальной.3.3Вычисление градиента в каждом пикселеВ результате предыдущего шага мы получили две матрицы, одна из которыхсодержит горизонтальную составляющую градиента для каждого пикселя, другая— вертикальную.

Посчитать по этой информации модуль и направление градиентаяркости в каждой точке не должно составить для вас труда.3.4Вычисление гистограмм градиентовВ результате предыдущего шага мы получили матрицу направлений и матрицузначений градиентов яркости пикселей. На этом шаге нужно разбить изображениена прямоугольники (клетки) и вычислить гистограмму градиентов в каждой клетке.Для начала разобьем всю область изменения направления градиента (например,[−π, π]) на некоторое (обычно не очень большое, порядка 8-32) число сегментов. Выберем некоторую клетку и создадим для неё массив размера, равного количествусегментов.

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

деление всех его значений на некоторую норму этого вектора. Нормы могут быть разные, но проще всего воспользоваться евклидовой нормой (корень из суммы квадратовэлементов). Если же вы хотите добиться лучших результатов, то можете попробовать выбрать другую норму. Также может привести к успеху нормализация не однойклетки, а нескольких вместе (как длинного вектора, полученного конкатенацией гистограмм каждой клетки)3.6Объединение гистограмм в дескрипторВсе, что осталось сделать — это соединить (конкатенировать, записать последовательно) полученные нормализованные гистограммы в один длинный массив, получив тем самым дескриптор — вектор признаков, который описывает некоторыехарактерные признаки изображения.

Именно с такими признаками, вместо самихизображений, будет работать классификатор.4Среда программирования и устройство каркасаКак и в первом задании, пользователям Windows рекомендуется использоватьCygwin. Пользователям Linux достаточно иметь gcc и GNU make.Структура каркаса• src — директория с исходным кодом в формате .cpp;• include — директория с заголовочными файлами.

Здесь имеются файлыmatrix.h и matrix.hpp - реализация класса матрицы из первого задания;• externals — директория с исходными кодами библиотек. Вам предоставленытри библиотеки, которые помогут вам в решении задачи: EasyBMP, Liblinear иArgvparser;• bridge — директория, в которую добавляются заголовочные файлы и скомпилированные библиотеки для импорта в основной проект;7• build/bin — директория, в которой сохраняются выполняемые файлы компиляции (т.е. после того, как отработала команда make all);• compare.py — скрипт для проверки точности работы классификатора.

Запускается командой ./compare.py <test_labels.txt> <predictions.txt>. Скриптвыводит отношение количества верно классифицированных тестовых изображений к общему числу тестовых изображений;5Требования к заданию• Задание должно быть полностью выполнено только студентом, который указанв readme.txt как автор работы. Запрещается публиковать, распространять текствыполненного задания до окончания срока приема работ (жесткого дедлайна).• Обязательной частью задания является реализация дескриптора HOG согласно алгоритму, описанному в соответствующем разделе. Допускается изменениеотдельных деталей, например, применение нормализации по блокам из нескольких клеток или и использование другой версии фильтра Собеля, однако основные шаги алгоритма (приведение к grayscale-формату, свертка с фильтрамиСобеля, рассчет направления и значения градиента, расчет и нормализациягистограмм) должны быть выполнены.• Точность классификации на приведенной тестовой выборке должна быть нениже 50%.• Работа выполняется на языке С++.• Работа должна успешно компилироваться и собираться с помощью компилятора gcc версии 4.8 вне зависимости от платформы.

Работать можно на любойплатформе, но важно не использовать платформозависимых библиотек, например windows.h, unistd.h и прочих.• Запрещается использовать сторонние библиотеки помимо тех, что даны в шаблоне задания.8• Для обучения модели должна использоваться только приведенная обучающаявыборка без каких-либо модификаций.• Время обучения модели не должно превышать 30 минут на ноутбуке DellLatitude E4310 (его характеристики можно найти в интернете). Время работы классификатора на тестовой выборке не должно превышать 10 секунд.6Формат выполненной работы и критерии оценки.В качестве результата своей работы вы должны предоставить архив в форма-те tar (можно со сжатием, например tar.gz), внутри которого сразу располагаетсякорневая директория проекта (аналогично архиву c шаблоном), в которой располагается (помимо файлов с исходным кодом) файл с обученной моделью и заполненныйreadme.txt.Файл отчета readme.txt должен содержать ФИО автора, номер группы, описаниевыполненных дополнительных частей работы.