Исследование алгоритмов

Размещено на http://www.allbest.ru/

Исследование алгоритмов



Оглавление

Введение

Глава 1. Алгоритмы детектирования объектов на видео для мобильных платформ

1.1 Обучение с учителем и формальная запись задачи классификации

1.2 Каскадный классификатор

1.3 Выбор предметной области и обзор реализаций методов машинного обучения с учителем в этой области

1.4 Выбор мобильной платформы и изучение инструментов разработки

Глава 2. Написание приложения, использующего каскадный классификатор

2.1 Подготовка базы изображений

2.2 Обучение каскадного классификатора

2.3 Структура и интерфейс программы

Глава 3. Результаты экспериментального исследования

3.1 Программа экспериментальных исследований

3.2 Описание проведенных экспериментов

3.3 Выводы по результатам тестирования

Заключение

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

Приложение А. Исходный код программы для подготовки обучающей выборки

Приложение Б. Исходный код приложения для детектирования пешеходов



Введение

С недавнего времени такая область кибернетики, как создание искусственных систем распознавания образов, стала представлять особый интерес. Потребность в создании и применении автоматических методов анализа изображений и видео возникает в самых разных сферах - от распознавания текстов [32] до проблем робототехники и систем обнаружения целей [17]. Однако процесс распознавания является сложной задачей в программировании и с теоретической, и технической стороны.

К основным задачам распознавания образов относится классификация изображений (определение наличия объекта), детектирование и локализация объекта (вычисление его координат и/или выделение границ) и непосредственно распознавание объекта (определение сущности найденного объекта, отнесение его к некоторому классу объектов) [27]. В данной работе рассматривается задача детектирования текстурированного объекта на видео.

Не случайно изучаются именно текстурированные объекты. Под текстурой понимается некоторое свойство макроскопической области изображения, описывающее пространственную упорядоченность простых геометрических элементов (примитивов) этого изображения. Область определяется как текстурная, когда число этих элементов в области достаточно велико, а если в ней присутствуют только несколько примитивов, то на изображении воспринимается группа исчисляемых объектов [13]. Выбор текстурированных изображений в качестве тестовых объектов исследования определяется тем, что многие текстурированные изображения обладают скрытой периодической линейчатостью, что позволяет реализовать методы детектирования с приемлемой вычислительной сложностью.

В практических задачах часто решаются проблемы распознавания людей, лиц, автомобилей, автомобильных номеров, дорожных знаков и других объектов, которых можно отнести к текстурированным. Частным случаем обнаружения и отслеживания людей является детектирование пешеходов. Данная проблема является чрезвычайно актуальной. Общая идея заключается в создании активных систем безопасности, которые предназначены для снижения частоты и тяжести несчастных случаев на дороге, предупреждая водителя об опасности и/или осуществляя переход к автоматическому управлению транспортным средством во избежание дорожно-транспортного происшествия. В основе таких систем так или иначе лежит распознавание объектов, поэтому качество работы целой системы будет зависеть от реализации этого процесса на программном уровне [19]. Поэтому далее в работе будут применяться общие алгоритмы распознавания текстурированных объектов для этой практически важной задачи.

Алгоритмы машинного обучения являются наиболее привлекательным методом в решении задачи распознавания и, в частности, успешно используются в распознавании пешеходов. Машинное обучение известно как одно из самых интенсивно развивающихся направлений в программировании, о чем свидетельствуют научные работы последних десятилетий. В этой связи стоит упомянуть труды П. Фельценсцвальба (P. F. Felzenszwalb) [8, 9], З. Гарамани (Zoubin Ghahramani) [10], Д.М. Гаврила (D.M. Gavrila) [11], которые послужили основой для написания данной работы.

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

Отдельную проблему представляет собой распознавание в видеопотоке. В данной работе используется распространенный подход still-to-still recognition, представляющий собой покадровое распознавание и комбинирование этих результатов для нескольких последовательных кадров [36, 37].

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

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

Основные задачи, решаемые в рамках работы, таковы:

1. Провести аналитический обзор литературы.

2. Реализовать изученные методы детектирования текстурированного объекта в виде образца программы.

3. Провести экспериментальное тестирование разработанного приложения применительно к задаче детектирования пешеходов на видеоизображении.

Глава 1. Алгоритмы детектирования объектов на видео для мобильных платформ

1.1 Обучение с учителем и формальная запись задачи классификации

Теория машинного обучения решает задачи предсказания будущего поведения сложных систем в том случае, когда отсутствуют точные гипотезы о механизмах, управляющих поведением таких систем. Имеется ряд категорий машинного обучения: контролируемое обучение или обучение с учителем (supervised learning), неконтролируемое обучение (unsupervised learning) (в частности, кластеризация), обучение с подкреплением (reinforcement learning).

В данной работе рассматривается первый тип машинного обучения - контролируемое обучение. Оно берет начало на обучающей выборке, которая представляет собой примеры: пары вида "вход - выход". Целью обучения является восстановление зависимости между элементами этих пар с целью предсказания будущего выхода по заданному входу. В сущности, имеется два основных класса задач: задачи классификации и задачи регрессии. В данном исследовании интерес представляет задача классификации, в которой выход - это метка класса, к которому принадлежит вход [31].

Задача классификации базируется на основных идеях теории PAC-машинного обучения (Probably Approximately Correct-learning), предложенную Валлиантом [38]. В работе предлагается отойти от классической концепции этой теории; вместо этого используется постановка задачи, принятая в современной статистической теории машинного обучения.

Так, предполагается, что каждый пример x, представленный для обучения или проверки, является элементом некоторого множества X (снабженного полем борелевских множеств) и генерируется некоторым неизвестным распределением вероятностей P на X . Предполагается, что каждый пример x имеет метку y - признак принадлежности к некоторому классу. Метки классов образуют множество D. Пары (x; y) объектов x и их меток y одинаково и независимо распределены согласно некоторому неизвестному вероятностному распределению P на множестве . В соответствии с этим полагается, что выборка

генерируется (порождается) некоторым источником, а на множестве задано распределение вероятностей

.

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

В этом случае вся выборка S разбивается на две подвыборки:

положительные примеры (или первый класс) и

- отрицательные примеры (или второй класс). Именно эта информация и подводит к физической, программной реализации алгоритма AdaBoost. Подробнее об этом рассказывается в главе 2, там же можно проследить параллели между положительными и отрицательными подвыборками S и позитивными и негативными наборами изображений для тренировки каскада.

В некоторых случаях индикаторная функция классификации k задается с помощью некоторой вещественной функции f и числа

:.

Строго говоря, пары (x; y) являются реализациями случайной величины (X;Y), которая имеет распределение вероятностей P. Плотность распределения P будет обозначаться так же, как и P(x; y).

Предсказательная способность произвольной функции классификации k будет оцениваться по ошибке классификации, которая определяется как вероятность неправильной классификации:

,

где k(X) - функция от случайной величины X, также является случайной величиной, поэтому можно рассматривать вероятность события .

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

1.2 Каскадный классификатор

В настоящее время метод Виолы-Джонса является самым популярным методом для детектирования в силу своей высокой скорости и эффективности. В 2001 году П. Виола и М. Джонс [21, 22] представили многоэтапную процедуру классификации, которая позволила существенно сократить вычислительное время. При этом качество осталось сопоставимо со многими более медленными и сложными одноэтапными классификаторами, такими как машина опорных векторов (SVM)[8], случайный лес (Random Forest)[25] и нейронные сети (ANN) [12]. На протяжении порядка 10 лет предлагались различные модификации этого метода, пригодные для решения более специфичных задач [36].

Этапами алгоритма Виолы и Джонса являются классификаторы бустинга [28] над решающими деревьями, использующими в качестве признаков характеристики Хаара. Общий подход Виолы-Джонса к детектированию объектов на изображении комбинирует четыре концепции:

1. Использование простых прямоугольных функций, так называемых функций Хаара;

2. Интегральное представление изображения по этим признакам для быстрого обнаружения функции;

3. Использование метода построения классификатора на основе алгоритма адаптивного бустинга AdaBoost, реализующего концепцию машинного обучения;

4. Применение метода комбинирования классификаторов в каскадную структуру для эффективного совмещения множественных функций.

Именно эти идеи позволяют осуществлять детектирование объекта в режиме реального времени [2].

1. Признаки Хаара

Признаки Хаара (Haar-Like features) представляют собой двоичную аппроксимацию вейвлета Хаара. Каждый признак представляет собой двоичную маску, т.е., черно-белое изображение. В исходных работах [28] использовалось лишь несколько типов характеристик Хаара (рис. 1.1, пп. 1, 2). В более поздних работах [29], представляющих расширенный метод Виолы-Джонса, набор характеристик Хаара был дополнен наклонными характеристиками (рис. 1.1, п.3).

Рисунок 1.1. Признаки Хаара

Характеристику Хаара можно определить как функцию f от суммарной интенсивности и двух прямоугольных участков изображения A и B таких, что участок A вложен в участок B. Прямоугольная форма участков выбрана затем, чтобы можно было применить технику интегральных изображений [18, 22] для расчета суммарных интенсивностей в них. В современных работах используется характеристика вида

,

где и - константы. Поэтому применение алгоритма Виолы и Джонса требует корректировки освещения:

Здесь - интенсивность в точке (x,y), - оценочная дисперсия, - оценочное среднее значение интенсивности по некоторой окрестности, c - положительная константа, которую обычно полагают равной двум [6].

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

где I(x,y) - значение точки (x,y) интегрального изображения; i(x,y) - значение интенсивности исходного изображения.

Каждый элемент матрицы I(x,y) представляет собой сумму пикселей в прямоугольнике от i(0,0) до i(x,y), т. е. значение каждого элемента I(x,y) равно сумме значений всех пикселей левее и выше данного пикселя i(x,y). Расчет матрицы занимает линейное время, пропорциональное числу пикселей в изображении и его можно производить по следующей формуле:

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

F = U - V,

где U - сумма значений яркостей точек, закрываемых светлой частью признака, а V - сумма значений яркостей точек, закрываемых темной частью признака. Если разница превышает порог, то говорят, что функция является существующей.

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

Таким образом, признаки Хаара организованы в каскадный классификатор.

2. Алгоритм AdaBoost

В основе формирования каскада классификаторов Хаара лежит алгоритм adaptive boosting'a (адаптивного усиления), или сокращенно AdaBoost (мета-алгоритм, предложенный Йоавом Фройндом (Yoav Freund) и Робертом Шапиром (Robert Schapire), [10]). AdaBoost комбинирует T "слабых" классификаторов с целью создания одного "сильного" классификатора. "Слабым" здесь считается такой классификатор, который получает правильный ответ не намного чаще, чем при случайном угадывании. Но если имеется множество таких слабых классификаторов, и каждый из них выдвигает окончательный ответ примерно в верном направлении, можно получить серьёзную, комбинированную силу для достижения корректного решения. AdaBoost выбирает набор слабых классификаторов для объединения и присваивает каждому из них свой вес. Эта взвешенная комбинация и является сильным классификатором.

На данный момент наиболее распространёнными вариантами базового алгоритма являются Gentle AdaBoost и Real AdaBoost, превосходящие базовый алгоритм по своим характеристикам, но сохраняющие все основные принципы [10].

Общая идея алгоритма заключается в следующем:

1. Требуется: построить классифицирующую функцию , где X - пространство векторов признаков, Y - пространство меток классов.

2. Имеется:

2.1. Обучающая выборка (x1, y1), ..., (xN, yN), где i - номер признака, - вектор признаков, а - бинарная метка класса, , к которому принадлежит(для других boosting-алгоритмов может быть диапазон значений меток).

2.2. Семейство классифицирующих функций ;

2.3. Начальное распределение , для i=1,…,N, т.е. оно должно быть инициализировано заранее; сообщает, сколько стоит неправильная оценка каждого признака.

3. Для каждого шага m=1,2,…,M строится итеративный процесс вида:

3.1. Выбирается наилучший на текущем распределении слабый классификатор :

,

то есть тренируется

,

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

,

Пока

>0,5, иначе выход;

3.2. Вычисляется коэффициент

,

показывающий вклад текущего слагаемого классифицирующей функции;

3.3. Добавляется слагаемое

,

вычисляемое с учетом работы уже постороенной части классификатора;

3.4. Обновляется распределение (весовые коэффициенты для признаков):

,

где - нормализующий по всем признакам коэффициент, такой, что

.

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

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

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

.

Очевидно, что ключевой особенностью boosting-а является то, что, когда алгоритм прогрессирует, эта стоимость будет развиваться так, что обучение "слабых" классификаторов будет сфокусировано на тех признаках, которые ранее в "слабых" классификаторах давали плохие результаты [2].

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

1) Склонность к переобучению при наличии значительного уровня шума в данных;

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

3) Жадная стратегия последовательного добавления приводит к построению неоптимального набора базовых алгоритмов.

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

3. Локальные бинарные шаблоны

Оператор LBP (Local Binary Patterns, локальные бинарные шаблоны) впервые был предложен T.Ojala в 1996 году [20]. Базовый оператор LBP, применяемый к пикселю изображения, использует восемь пикселей окрестности, принимая значение интенсивности центрального пикселя в качестве порога. Он представляет каждый пиксель изображения в виде бинарного числа: пиксели со значением интенсивности большим или равным значению интенсивности центрального пикселя принимают значения равные "1", остальные принимают значения равные "0" (рис. 1.2). Описание восьми пикселей окрестности в двоичном представлении и есть локальный бинарный шаблон (рис. 1.3).

Таким образом, результатом применения базового оператора LBP к пикселю изображения является восьмиразрядный бинарный код, который описывает окрестность этого пикселя. Использование круговой окрестности и билинейной интерполяции значений интенсивностей пикселей позволяет построить локальный бинарный шаблон с произвольным количеством точек P и радиусом R.

Рисунок 1.2. Базовый оператор LBP

Рисунок 1.3. Графическое представление базового и расширенных операторов LBP

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

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

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

1.3 Выбор предметной области и обзор реализаций методов машинного обучения с учителем в этой области

В работе возникает необходимость выбора предметной области, в которой будет тестироваться каскадный классификатор. Главными вопросами на данном этапе являются:

1) Актуальность предметной области;

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

В качестве предметной области было выбрано детектирование пешеходов. Детектирование людей остается одной самых популярных областей распознавания, а детектирование пешеходов, в частности, - еще и коммерчески выгодной. Это обосновывается всё возрастающей потребностью общества получить средство защиты и обеспечения максимальной безопасности человека на проезжей части. Анализируя ситуацию на современных дорогах России в целом, стоит отметить тенденцию усиления интенсивности движения, возрастающее число субъектов дорожного движения на дороге, и, соответственно, увеличение процента дорожно-транспортных происшествий. Статистика Данные с официального сайта ГИБДД РФ, URL::http://www.gibdd.ru/stat/charts/ представлена на рис. 1.4.

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

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

Рисунок 1.4. Статистика ДТП

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

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

Таблица 1.1

Применение алгоритмов контролируемого обучения в выбранной предметной области

Примеры алгоритмов	Работы	Достоинства метода	Недостатки метода
Алгоритмы на основе гистограмм (Lin. R?HOG, C?HOG, EC?HOG и др.)	[6], [30], [9], [8]	- Возможна работа алгоритма в режиме реального времени; - Возможность обучить такой распознаватель, который был бы устойчив ко всем факторам изменяющейся среды	- В большинстве случаев обучение занимает много времени; - Необходимость подготовки обучающих выборок; - Зависимость качества обучения от обучающей выборки
Метод опорных векторов (SVM)	[30], [8], [33]
Бустинг	[28], [11], [33], [8], [36]
Баггинг (Random Forest)	[25]
Нейросети	[12], [7], [34]

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

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

Выбор пал на метод HOG (Histogram of Oriented Gradients, гистограмма направленных градиентов) [7], так как он изначально был разработан именно для детектирования пешеходов и в настоящий момент в том или ином виде используется в большинстве современных детекторов.

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

Базовой единицей HOG-дескриптора является блок (block) - прямоугольная область пикселей изображения заданных размеров. Блок состоит из ячеек (cells), в свою очередь состоящих из пикселей. Каждой ячейке ставится в соответствие гистограмма ориентаций (углов наклона относительно горизонтали) градиентов из заданного количества полос (bins), при этом направление считается "беззнаковым", т.е. угол в и считаются эквивалентными.

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

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

,

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

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

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

Пусть множество углов (???, ??] разбивается на ?? равных интервалов вида , где ?? = {1, . . . , ??}. Каждому интервалу ставится в соответствие бин гистограммы. Тогда гистограмма ячейки заполняется так, что величина градиента в каждой внутренней его точке добавляется к величине бина, соответсвующего интервалу, содержащему угол данного градиента [5].

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

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

1.4 Выбор мобильной платформы и изучение инструментов разработки

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

1) Выбор мобильной платформы;

2) Изучение соответствующей среды разработки;

3) Исследование сторонних библиотек, использование которых даёт возможность эффективно решить поставленные задачи.

На современном рынке мобильных устройств конкурируют 3 основные операционные системы (ОС): Android, iOS и Windows Phone. Для того, чтобы определиться с выбором, в таблице 1.2 подготовлен краткий сравнительный обзор этих платформ.

В силу открытости, доступности и высокой распространенности, в качестве платформы была выбрана ОС Android.

Для работы с платформой Android была использована интегрированная среда разработки Android Studio 0.9.9 URL:https://developer.android.com/sdk/index.html, основанная на программном обеспечении IntelliJ IDEA и системе Gradle. Android Studio не случайно предпочтена среде Eclipse. Выбор обуславливается тем, что эта среда:

- специально предназначена для разработчиков Android;

- позиционируется непосредственно как замена Eclipse Конференция Google I/O, 03.2013 (в связи с чем рекомендован переход с Eclipse);

Таблица 1.2

Сравнительный обзор основных мобильных платформ Данные по мировому рынку мобильных устройств на 30.01.2015. URL: http://4pda.ru/2015/01/30/199363/

	Доля устройств, использующих данную ОС, %	Ресурсозатратность разработки	Среда разработки	Язык разработки
Android	81,5	Высокая (необходимость учитывать разную производительность устройств, большое количество размеров экрана и пр., следствие - увеличенные затраты на проектирование нескольких интерфейсов и дополнительное тестирование)	Eclipse IDE; Android Studio	Java
iOS	14,8	Высокая (за счет повышенных требований к готовому продукту и, как следствие, дополнительных затрат на доработку)	Xcode IDE	Objective-C
Windows Phone	2,7	Низкая (за счет низкой конкуренции внутри магазина)	Microsoft Visual Studio	C++, C#, Visual Basic или XAML

- обладает более удобным для работы над мобильным приложением интерфейсом;

- быстрее обновляется и развивается. На момент сдачи выпускной квалификационной работы выпущена первая стабильная версия 1.0.

Дополнительно была использована интегрированная среда разработки приложений на языке C++ Microsoft Visual Studio 2010.

Для того, чтобы получить возможность реализовать алгоритм обучения каскадного классификатора практически, в работе была использована библиотека машинного зрения OpenCV URL:http://opencv.org/ с открытым исходным кодом. Библиотека написана на оптимизированном C и C++, работает под Linux, Windows и Mac OS X. Фактически, OpenCV - это набор типов данных, функций и классов для обработки изображений алгоритмами компьютерного зрения. Структурно библиотека OpenCV разделена на небольшие модули по функциональному использованию. Отдельно стоит отметить модуль методов и моделей машинного обучения opencv_ml. Так, OpenCV включает в себя подбиблиотеку общего назначения MLL (Machine Learning Library, Библиотека Обучения Машин). Эта подбиблиотека решает задачи статистического распознавания образов, классификации и кластеризации. В работе используется версия библиотеки OpenCV 2.4.9.

Заявленная библиотека подходит как для программирования на языке C++, так и для разработки под Android. Она предоставляет несколько утилит, необходимых для тренировки каскадного классификатора: opencv_haartraining, opencv_traincascade, opencv_createsamples и opencv_performance. Подробнее использование этих приложений описано в следующей главе.

Проектирование архитектуры приложения основывалось на базовых принципах разработки Android-приложений, а именно:

1) SOLID (Single responsibility, Open-closed, Liskov substitution, Interface segregation и Dependency inversion):

- принцип единственной обязанности класса (т.е. на каждый класс должна быть возложена только одна обязанность);

- принцип открытости/закрытости программных сущностей (т.е. программные сущности должны быть открыты для расширения, но закрыты для изменения);

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

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

- принцип инверсии зависимостей (зависимости внутри системы строятся на основе абстракций, модули верхнего уровня не зависят от модулей нижнего уровня, абстракции не должны зависеть от деталей, детали должны зависеть от абстракций);

1) DRY (Don't repeat yourself): принцип нацеленности на снижение повторения информации различного рода;

2) KISS (Keep it short and simple): принцип, при котором простота системы декларируется в качестве основной цели и/или ценности;

3) YAGNI (You Ain't Gonna Need It): принцип, при котором в качестве основной цели и/или ценности декларируется отказ от добавления избыточной функциональности, т.е. от функциональности, в которой нет непосредственной надобности.

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

- независимыми от фреймворков;

- тестируемыми;

- независимыми от интерфейса пользователя (user interface, UI);

- независимыми от баз данных;

- независимыми от любой внешней службы.

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



Глава 2. Написание приложения, использующего каскадный классификатор

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

1) Подготовка обучающей выборки изображений;

2) Процесс обучения каскадного классификатора, основанный на методах, рассмотренных в главе 1, и инструментах, которые предлагают выбранные языки программирования;

3) Написание мобильного приложения, использующего обученный каскадный классификатор.

2.1 Подготовка базы изображений

Целями первого этапа процедуры обучения каскадного классификатора будет являться:

1) Сбор и подготовка двух выборок изображений: содержащих и не содержащих детектируемые объекты (т.н. выборок позитивных и негативных изображений);

2) Подготовка файлов-описаний для каждой выборки в соответствии с требованиями используемых утилит.

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

В соответствии с поставленными целями, на основе сделанных предположений для обучения каскадного классификатора были собрана выборка позитивных изображений объемом 17000 штук и выборка негативных изображений объемом 15000 штук в разрешении 640х480 пикселей. Позитивные содержали в себе один или несколько объектов "пешеход", на негативных образах не было ни одного объекта, которого можно было бы классифицировать как объект "пешеход".

Выборки были собраны путем комбинации готового свободно распространяемого датасета от Даймлера URL: http://www.gavrila.net/Research/Pedestrian_Detection/Daimler_Pedestrian_

Benchmark_D/Daimler_Mono_Ped__Detection_Be/daimler_mono_ped__detection_be.html (Daimler Pedestrian Detection Benchmark Dataset) и уникальной выборки, состоящей из кадров, записанных авторегистратором. Учитывая то, что выборка изображений от Даймлера также была получена захватом изображений из автомобиля во время 27-минутной езды по городу, общий набор данных для обучения каскадного классификатора является реалистичным.

Так как для улучшения качества будущего классификатора (а также для ускорения его обучения) было решено использовать позитивные изображения, содержащие только лишь сам объект, было написано приложение, позволяющее произвести обрезку положительных изображений и одновременно автоматически заполнить файл их описания. Дополнительные требования к приложению: максимально простой и удобный интерфейс, позволяющий быстро обработать большое число изображений вручную. Исходный код представлен в приложении А. Блок-схема работы с приложением изображена на рис. 2.1. Примеры позитивного изображения и позитивных образцов можно увидеть на рис. 2.2 и 2.3 соответственно; пример негативного изображения представлен на рис. 2.4. Также был сгенерирован файл, описывающий негативные изображения.

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

Таблица 2.1

Идеи, предложенные для решения проблем детектирования

Проблема	Решение
Отсутствие эталонного образа пешехода; наличие радикальных различий в представлении человека: мимические искажения лица, особенности прически и растительности на лице, наличие головного убора и других предметов, поза, рост, параметры фигуры и т.п.	Предпочтение отдается настоящим изображениям пешеходов
Многообразие пространственного расположения объекта, зависимость от ориентации и масштаба	Использование обучающей выборки большого размера (N позитивных и M негативных изображений)
Существование определенных трудностей, которые представляет среда нахождения человека: разнообразие погодных условий, ландшафтов, характера освещения и т.п.	Использование кадров подлинных видеозаписей видеорегистратора, сделанных в реальной среде при различных степенях освещенности и в разное время года
Риск пропусков объекта или ложных срабатываний при детектировании	Подготовка положительной выборки таким образом, чтобы на каждом обучающем образце находился один объект, по размеру совпадающий с размером изображения
	Использование частей позитивных изображений, на которых отсутствует объект, в качестве негативных

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

- соотношение сторон образца должно отражать пропорции детектируемого объекта;

- размер образца не может быть меньше размера самого маленького из позитивных изображений.

Рисунок 2.1. Блок-схема работы с приложением для подготовки обучающей выборки

Рисунок 2.2. Пример позитивного изображения

а)

б)

Рисунок 2.3. Примеры позитивных образцов

Рисунок 2.4. Пример негативного изображения

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



2.2 Обучение каскадного классификатора

В OpenCV есть два приложения для тренировки каскадов URL: http://docs.opencv.org/modules/objdetect/doc/cascade_classification.html?highlight=cascade%20classifier: opencv_haartraining и opencv_traincascade (новая версия, написанная на C++). Предпочтение отдается использованию opencv_traincascade, так как эта утилита хранит обученные каскады в новом формате. Для наилучшей оценки итогового результата, решено обучить два каскадных классификатора: основанный на признаках Хаара и основанный на локальных бинарных шаблонах. Библиотека OpenCV и, в частности, утилита opencv_traincascade дает возможность обучить оба классификатора путем установки значения параметра -featureType: Haar или LBP. Оба каскадных классификатора были обучены по одной и той же выборке, описанной в п.2.2.

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

Таблица 2.2

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

Параметр	Изнач. значение	Оптим. значение	Обоснование
- minHitRate	0,95	0,996	Изначально делалась скидка на сложность детектируемых объектов, вероятность смешения объекта с фоном и ложных тревог, поэтому процент "правильных" обнаружений устанавливался не максимально высоким. Однако свойства хорошей выборки позволили увеличить значение
-numPos	17256	15000	Указывается не всё количество позитивных образцов, так как процент правильных обнаружений не равен 100%, и некоторая часть изображений будет признана непригодной, а значит, высока вероятность невозможности обучения каскадов до конца
-numNeg	10000	10000	Точное количество негативных образцов
-numStages	15	31	Большее число уровней, которые будут обучаться, обеспечит большую точность последующего детектирования
-precalcValBufSize	1024	1024	Под процесс выделяется большое количество памяти для ускорения обучения классификатора
-precalcIdxBufSize	1024	1024
-featureType	HAAR/ LBP	HAAR/ LBP	Обучается классификатор, использующий признаки Хаара или LBP
-w	8	8	Параметры в точности должны совпадать с размером сгенерированных на предыдущем шаге примитивов
-h	32	32
-maxFalseAlarmRate	0,5	0,7	Изначально выставлялось среднее значение параметра, однако при обучении на хорошей выборке уровень ложной тревоги достигался слишком быстро
-mode	ALL	ALL	Предполагается использование полного комплекта Хаар-признаков, чтобы достигнуть максимально возможной точности

В общей сложности, каскадный классификатор, использующий признаки Хаара, обучался 3360 минут; в свою очередь, классификатор, использующий локальные бинарные шаблоны, обучался 339 минут.

Итак, результатом работы на этапе тренировки стали 2 каскада в формате xml-файлов: обученный на признаках Хаара и обученный по локальным бинарным шаблонам.



2.3 Структура и интерфейс программы

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

Приложение разрабатывалось непосредственно для ОС Android 5.0.2, однако также реализована поддержка старых версий.

С точки зрения архитектуры программы, было принято решение разбить проект на 3 логических слоя:

1) Слой представления (Presentation Layer). На данном уровне не присутствует бизнес-логика; здесь содержатся представления (views), логика UI и посредники (interactors), связывающиеся с представителями (presenters) и передающие информацию для её отображения в views;

2) Слой бизнес-логики (Domain Layer). На этом слое реализована вся бизнес-логика приложения. Данный модуль реализован на языке java без каких-либо Android-зависимостей;

3) Слой данных (Data Layer). Все данные, необходимые для работы приложения, поставляются из этого слоя. Именно к этому слою относится используемая библиотека OpenCV, обученные каскады в формате xml-файлов и элементы графического интерфейса.

На рис. 2.5. схематично представлена описанная структура; с соответствующей UML-диаграммой классов можно ознакомиться по рис. 2.6.

Рисунок 2.5. Логические уровни проекта

Исходный код каждого класса и view-представлений программы представлен в приложении Б.

Основными требованиями к интерфейсу пользователя стали:

1) Простота и интуитивность;

2) Возможность быстрого выбора и смены методов детектирования для их адекватной визуальной оценки;

3) Правильное отображение всех элементов, в том числе при горизонтальном положении экрана, так как процесс детектирования предполагает именно такое положение устройства;

4) Отрисовка элементов под разрешение экрана xhdpi (720х1280).

Рисунок 2.6. Диаграмма классов приложения

Интерфейс включает в себя:

- экран главного меню; это первое, что видит пользователь при запуске приложения;

- экран детектирования пешеходов в реальном времени.

Переход от главного меню к экрану детектирования осуществляется путем нажатия пользователем одной из трёх кнопок, реализованных в соответствии с имплементированными методами детектирования: Haar, LBP и HOG.

Переход обратно к главному меню осуществляется с помощью клавиш навигации: учитывается, что смартфон LG G2 обладает наэкранными клавишами навигации, реализованными в Android версии 5.0 и выше, а смартфоны Philips W8510 и LG P705 L7 имеют сенсорные навигационные клавиши на корпусе. Этот факт позволяет не создавать кнопку возврата с экрана детектирования к главному меню, поскольку функционала хард-клавиш достаточно для удобной работы с приложением.

На рис. 2.7 представлен скриншот главного меню приложения при работе на смартфоне LG G2.

а)

б)

Рисунок 2.7. Главное меню приложения



Глава 3. Результаты экспериментального исследования

3.1 Программа экспериментальных исследований

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

Общее тестирование приложения включало в себя:

1) Проверку приложения на предмет ошибок безотносительно изучаемых методов детектирования (проведение юнит-тестов при помощи JUnit, проведение тестирования UI приложения путем использования библиотеки Espresso URL: https://developer.android.com/training/testing/ui-testing/espresso-testing.html);

2) Непосредственно анализ эффективности исследуемых методов в задаче детектирования пешеходов в реальном времени, производимый по следующим критериям:

- продолжительность обучения классификаторов (T);

- ошибки I рода; абсолютное число и процент пропусков объектов: false negatives (FN) и false negatives rate (FNR);

- средне число пропущенных объектов в секунду (FNa);

- ошибки II рода; абсолютное число и процент ложных срабатываний: false positives (FP) и false positives rate, (FPR);

- абсолютное число и процент верно классифицированных положительных примеров: true positives (TP) и true positives rate (TPR);

- процент верно классифицированных отрицательных примеров (истинно отрицательных случаев, true negatives rate, TNR);

- чувствительность и специфичность модели (Se и Sp соответственно);

- среднее время обработки одного кадра из видеопотока в реальном времени (t).

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

Среда Android Studio дает возможность использовать эмулятор для разработки и тестирования программ. Однако этот вариант также был найден непригодным. Приложение проверялось на реальных устройствах, так как настройка нескольких эмуляторов продолжительнее и ресурсозатратнее, чем подготовка устройств и установка на них пакета приложения. Главными же причинами для отказа от эмулятора стала невозможность учета характеристик смартфонов при оценке работы приложения и отсутствие реальной окружающей среды для детектирования.

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

Для проведения тестирования использовались три смартфона, обладающие различными характеристиками дисплея, камеры и процессора, а также функционирующие на разных версиях платформы Android (4.0.3.Ice Cream Sandwich, 4.2.2 Jelly Bean, 5.0.2 Lollipop). Такие меры по учету аппаратной и программной специфики устройств обязательны при оптимизации мобильного приложения как с точки зрения интерфейса, так и с точки зрения производительности. В таблице 3.1. обозначены все необходимые для анализа характеристики выбранных устройств.

Таблица 3.1.

Используемые для тестирования устройства

Устройство	Характеристики
	Дисплей Процессор Память Основнаякамера
Смартфон LG G-серии G2 GOLD D802	5,2" 1980x1080 FULL HD IPS 423 точек на дюйм	4-ядерный 2,26 ГГц ОС: Android v. 5.0.2	ОЗУ: 2 Гб Встроенная: 32 Гб	13 Мп
Смартфон Philips Xenium W8510	4,7" 1280x720 TFT IPS 312 точек на дюйм	4-ядерный 1,2 ГГц ОС: Android v. 4.2.2	ОЗУ: 1 Гб Встроенная: 32 Гб	8 Мп
Смартфон LG Optimus L7 P705

Подобные документы

• Методы классификации в машинном обучении

  Виды машинного обучения, его основные задачи и методы. Подходы к классификации: логистическая регрессия, наивный байесовский классификатор, стохастический градиентный спуск, K-ближайший сосед, дерево решений, случайный лес, метод опорных векторов.
  
  курсовая работа [436,9 K], добавлен 14.12.2022
  

• Обучение с подкреплением

  Популярность алгоритмов машинного обучения для компьютерных игр. Основные техники обучения с подкреплением в динамической среде (компьютерная игра "Snake") с экспериментальным сравнением алгоритмов. Обучение с подкреплением как тип обучения без учителя.
  
  курсовая работа [1020,6 K], добавлен 30.11.2016
  

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

  Различные методы решения задачи классификации. Нейросетевые парадигмы, методы обучения нейронных сетей, возникающие при этом проблемы и пути их решения. Описание программной реализации классификатора, его функциональные возможности и результаты обучения.
  
  дипломная работа [1,0 M], добавлен 28.12.2015
  

• Исследование и разработка алгоритмов распознавания лиц

  Обзор существующих алгоритмов для обнаружения лиц. Выравнивание лица с помощью разнообразных фильтров. Использование каскадного классификатора Хаара для поиска лиц на изображении. Распознавание лиц людей с использованием локальных бинарных шаблонов.
  
  дипломная работа [332,4 K], добавлен 30.09.2016
  

• Исследование алгоритмов обучения нейронных сетей "с учителем"

  Диагностический анализ изучения алгоритмов обучения нейронных сетей "с учителем". Сбор входных и выходных переменных для наблюдений и понятие пре/пост процессирования. Подготовка и обобщение многослойного персептрона, модель обратного распространения.
  
  курсовая работа [249,3 K], добавлен 22.06.2011
  

• Методика разработки программного продукта для поиска причин в изменениях трендов в данных

  Создание системы предобработки данных; разработка системы классификации на базе методов и алгоритмов машинного обучения, их реализация в программной системе. Предобработка информации, инструкция пользователя, система классификации, машинный эксперимент.
  
  дипломная работа [917,1 K], добавлен 31.01.2015
  

• Разработка системы "Клавиатурный тренажер" с функциями администратора, обучающей слепому десятипальцевому методу набора

  Описание и анализ предметной области. Принципы обучения слепому методу печати. Обзор существующих клавиатурных тренажеров. Диаграмма объектов предметной области. Функции, которые должна выполнять разрабатываемая система. Построение структурной схемы.
  
  курсовая работа [8,1 M], добавлен 28.08.2012
  

• Система обучения и контроля знаний студентов

  Проект системы процесса обучения студентов; словарь предметной области, формулировка проблемы. Назначение продукта, заинтересованность пользователей; обзор ключевых потребностей. Альтернативные и конкурентные решения. Архитектура программной системы.
  
  курсовая работа [1,2 M], добавлен 19.03.2012
  

• Разработка системы распознавания изображений на основе аппарата искусственных нейронных сетей

  Искусственные нейронные сети как одна из широко известных и используемых моделей машинного обучения. Знакомство с особенностями разработки системы распознавания изображений на основе аппарата искусственных нейронных сетей. Анализ типов машинного обучения.
  
  дипломная работа [1,8 M], добавлен 08.02.2017
  

• Методы и средства электронного обучения для создания виртуальных корпоративных университетов

  Обзор существующий решений в области электронного обучения. Исследование архитектурных и технологических аспектов построения виртуальных корпоративных университетов. Анализ возможностей системы дистанционного обучения Sakai, отличительные особенности.
  
  дипломная работа [2,7 M], добавлен 09.04.2011
  

• главная
• рубрики
• по алфавиту
• вернуться в начало страницы
• вернуться к началу текста
• вернуться к подобным работам