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

Определения и сокращения

В настоящей пояснительной записке применяются следующие определения и сокращения:

ОС - операционная система.

ПС - программное средство.

Свертка - перемножение изображения с матрицей.

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

Графические артефакты - нарушения целостности изображения в виде черных или белых пикселей.

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

RGB - цветовая модель описывающая способ кодирования цвета. Цвета в этой модели красный, зеленый, синий.

MVS - Microsoft Visual Studio.

Альфа-канал - дополнительный фон изображения, позволяющий при наложении создать прозрачность.

Введение

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

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

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

Целью данного дипломного проекта является разработка модуля обработки изображения и поиску на нём лиц человека с последующим определением эмоции на них.

Для достижения поставленной цели были определены следующие задачи:

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

- сравнение и анализ работы алгоритмов по поиску лиц человека;

- сравнение и анализ работы алгоритмов поиска ключевых точек на лице;

- сравнение и анализ работы алгоритмов по определению эмоций.

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

1. Анализ прототипов и формирование требований к проектируемому программному средству

1.1 Обзор методов и алгоритмов по устранению помех на изображениях

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

1.1.1 Медианный фильтр

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

Рисунок 1.1 - Изображение с импульсным шумом

программа алгоритм изображение лицо

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

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

Скользящее окно представлено в виде матрицы размера N на N где каждая ячейка матрицы представляет собой пиксель на изображении.

Когда скользящее окно переходит к новому пикселю оно берет значения яркостей всех пикселей попавших в окно и заносит их в лист. Затем лист сортируется и элемент, находящийся в центре окна заменяется средним элементом из списка [1].

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

Рисунок 1.2 - Результат работы медианного фильтра

К достоинствам работы медианного фильтра можно отнести следующие пункты:

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

- малые затраты времени на обработку изображения;

- простая программная реализация алгоритма;

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

помех.

К недостаткам работы медианного фильтра можно отнести следующие пункты:

- плохое подавления гаусового шума;

- размывает изображении;

- сглаживает острые края на изображении.

1.1.2 Фильтр улучшения резкости

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

Пример матрицы для улучшения резкости:

М = , (1.1)

где М - матрица размером 3х3.

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

Рисунок 1.3 - Пример использования фильтра резкости

К достоинствам фильтра резкости можно отнести следующие пункты:

- легкая реализация алгоритма;

- хорошее выделение границ у объектов.

К недостаткам фильтра резкости можно отнести следующие пункты:

- понижает качество изображения;

- генерирует импульсный шум.

1.1.3 Гамма-коррекция

Гамма коррекция - нелинейная коррекция изображения. Исправляет недостаточную контрастность изображения. Пример работы фильтра Гамма коррекции показан на рисунке 1.4.

Все пиксели исходного изображения преобразуются в новые которые определяются по формуле (1.2)

, (1.2)

где I - яркость пикселя на экране дисплея;

V - численное значение цвета;

L - показатель гамма коррекции.

К достоинствам Гамма коррекции можно отнести следующие пункты:

- простота реализации алгоритма;

- осветление сильно затемненных областей.

Рисунок 1.4 - Гамма коррекция с коэффициентами от 2 до 0.33

Единственный недостаток у фильтра Гамма коррекции в том что высокие или низкие значения L приводят к потере качества изображения.

1.2 Обзор методов и алгоритмов по выделению границ у объектов

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

1.2.1 Фильтр Робертса

Фильтр Робертса - алгоритм, применение которого позволяет выделить границы у всех объектов на изображении.

Вычисляет сумму квадратов разницы между диагонально смежными пикселями. Получить сумму можно при помощи свертки пикселя с матрицами А и В.

Свертка изображения с матрицами А и В даст изображение обработанное фильтром Робертса.

А = . (1.3)

В = . (1.4)

Позиции в матрице представляют позиции х и у в системе координат от (х, у) до (х+1, у+1).

Каждый пиксель итогового изображения после свертки с матрицей А будет представлен в виде пикселя S.

, (1.5)

где p(x,y) - пиксель с координатами (х, у);

S1 - результирующий пиксель полученный при помощи свертки

изображения с матрицей А.

, (1.6)

где S2 - результирующий пиксель полученный при помощи свертки

изображения с матрицей В.

, (1.7)

где S - новый пиксель изображения.

Пример работы фильтра Робертса показан на рисунке 1.5.

Рисунок 1.5 - Изображение обработанное фильтром Робертса

К достоинствам фильтра Робертса можно отнести следующие пункты:

- фильтр показывает хорошую скорость обработки изображения;

- простота реализация алгоритма.

К недостаткам фильтра Робертса можно отнести следующие пункты:

- при наличии шума на изображении фильтр работает некорректно;

- иногда линии границ получаются слишком тонкие.

1.2.2 Фильтр Превитта

Фильтр Превитта - фильтр, используемый для выделения границ у объектов.

Вычисляет направление границы при помощи свертки изображения с матрицами P1 и P2 [3].

, (1.8)

, (1.9)

где P1, P2 - матрицы размера 3х3.

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

При свертке пикселя с матрицей P1 результатом будет отклик на вертикальную границу.

, (1.10)

где О1 - показатель характеризующий вертикальную границу.

При свертке пикселя с матрицей P2 результатом будет отклик на вертикальную границу.

, (1.11)

где О2 - показатель характеризующий горизонтальную границу.

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

, (1.12)

где R - пиксель результирующего изображения.

Рисунок 1.6 - Изображение обработанное фильтром Превитта

К достоинствам фильтра Превитта можно отнести следующие пункты:

- простота реализации Алгоритма;

- быстрая скорость работы;

- более толстые границы по сравнению с фильтром Робертса.

К недостаткам фильтра Превитта можно отнести следующие пункты:

- работает не для всех изображений;

- высокая чувствительность по вертикали и горизонтали;

- потеря данных.

1.3 Обзор методов и алгоритмов по поиску человеческих лиц.

1.3.1 Метод гибкого сравнения на графах

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

В подобных системах распознавания графы могут представлять собой как прямоугольную решетку, так и структуру, образованную характерными (антропометрическими) точками лица [5]. На рисунках 1.7 и 1.8 отображены решетка графов и граф построеный по характертным точкам лица.

Рисунок 1.7 - Решетка графов

Рисунок 1.8 - Граф описывающий лицо

В вершинах графа вычисляются значения признаков, чаще всего используют комплексные значения фильтров Габора (см. рисунок 1.9) или их упорядоченных наборов - Габоровских вейвлет которые вычисляются в некоторой локальной области вершины графа локально, путем свертки значений яркости пикселей с фильтрами Габора (см. рисунок 1.10).

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

Рисунок 1.9 - Набор фильтров Габор

Рисунок 1.10 - Свертка изображения лица с двумя фильтрами Габора

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

Результат распознавания системы - эталон с наилучшим значением ценовой функции деформации.

Рисунок 1.11 - Деформация решетки графов

В отдельных публикациях указывается 95-97%-ая эффективность распознавания даже при наличии различных эмоциональных выражениях и изменении ракурса лица до 15 градусов. Однако разработчики систем эластичного сравнения на графах ссылаются на высокую вычислительную стоимость данного подхода. Например, для сравнения входного изображения лица с 87 эталонными тратилось приблизительно 25 секунд при работе на параллельной ЭВМ с 23 транспьютерами. В других публикациях по данной тематике время либо не указывается, либо говорится, что оно велико.

К достоинствам метода сравнения на гибких графах можно отнести следующие пункты:

- высокая эффективность распознавания;

- распознает лица с наклоном до 15 градусов.

К недостаткам можно перечислить следующие:

- высокая вычислительная сложность;

- низкая технологичность при запоминании новых эталонов;

- линейная зависимость времени работы от размера базы данных лиц.

1.3.2 Нейронные сети

В настоящее время существует около десятка разновидности нейронных сетей (НС). Одним из самых широко используемых вариантов являться сеть, построенная на многослойном персептроне, которая позволяет классифицировать поданное на вход изображение в соответствии с предварительной настройкой сети.

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

Наилучшие результаты в области распознавания лиц (по результатам анализа публикаций) показала Convolutional Neural Network или сверточная нейронная сеть [6-8] которая является логическим развитием идей таких архитектур НС как когнитрона и неокогнитрона. Успех обусловлен возможностью учета двумерной топологии изображения, в отличие от многослойного персептрона.

Отличительными особенностями СНС являются локальные рецепторные поля (обеспечивают локальную двумерную связность нейронов), общие веса (обеспечивают детектирование некоторых черт в любом месте изображения) и иерархическая организация с пространственными сэмплингом (spatial subsampling). Благодаря этим нововведениям СНС обеспечивает частичную устойчивость к изменениям масштаба, смещениям, поворотам, смене ракурса и прочим искажениям.

Лучшие результаты по распознаванию лиц показывает сверточная нейронная сеть.

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

К достоинствам СНС можно отнести следующие пункты:

- Устойчивость нейронной сети к изменениям;

- Высокий уровень точности.

К недостаткам СНС можно отнести следующие пункты:

- Добавление новых данных требует переобучения сети;

- Трудно выбрать архитектуру сети;

- Математические проблемы.

1.3.3 Active Appearance Models

Активные модели внешнего вида (Active Appearance Models, AAM) -это статистические модели изображений, которые путем разного рода деформаций могут быть подогнаны под реальное изображение. Данный тип моделей в двумерном варианте был предложен Тимом Кутсом и Крисом Тейлором в 1998 году [9-10].

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

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

Рисунок 1.12 - Разметка изображения лица из 68 точек, образующих форму AAM

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



Рисунок 1.13 - Координаты точек формы лица до и после нормализации

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

Рисунок 1.14 - Модель формы AAM состоит из триангуляционной решетки s0 и линейной комбинации смещений si относительно s0

Далее из пикселей внутри треугольников, образуемых точками формы, формируется матрица, такая что, каждый ее столбец содержит значения пикселей соответствующей текстуры. Стоит отметить, что используемые для обучения текстуры могут быть как одноканальными (градации серого), так и многоканальными (например, пространство цветов RGB или другое). В случае многоканальных текстур векторы пикселей формируются отдельно по каждому из каналов, а потом выполняется их конкатенация. После нахождения главных компонент матрицы текстур, модель AAM считается обученной (см. рисунок 1.15).



Рисунок 1.15 - Конкретизации AAM

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

Рисунок 1.16 - Подгонка модели на конкретное изображение

1.3.4 Алгоритм Виола-джонса

Метод Виолы Джонса - алгоритм, позволяющий обнаруживать объекты на изображениях в реальном времени. Его предложили Паул Виола и Майкл Джонс в 2001 году. Хотя алгоритм может распознавать различные классы изображений, основной задачей при его создании было обнаружение лиц [11-12].

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

Основные принципы, на которых основан метод:

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

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

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

- все признаки поступают на вход классификатора, который даёт результат «верно» либо «ложь».

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

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

Данный метод в общем виде ищет лица и черты лица по общему принципу сканирующего окна:

- имеется изображение, на котором есть искомые объекты. Оно представлено двумерной матрицей пикселей размером w*h, в которой каждый пиксель имеет значение:

а) от 0 до 255, если это черно белое изображение (занимаемая память равна одному байту).

б) от 0 до 2553, если это цветное изображение (компоненты R, G, B).

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

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

(1.13)

где x, y - координаты центра i-го прямоугольника;

w - ширина;

h - высота;

a - угол наклона прямоугольника к вертикальной оси изображения.

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

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

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

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

(1.14)

где I(i,j) - яркость пикселя исходного изображения.

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

Расчет матрицы производится по формуле 1.15:

(1.15)

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

Пусть в прямоугольнике ABCD есть интересующий нас объект D (см. Рисунок 1.17):



Рисунок 1.17 - Выделенная область D на некоторой области изображения

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

S(D ) = L(В) + L(D) - L(С) - L(А). (1.16)

В стандартном методе Виолы - Джонса используются прямоугольные признаки (см. рисунок 1.18), они называются примитивами Хаара.

Рисунок 1.18 - Признаки Хаара

Вычисляемым значением такого признака будет формула (1.17):

(1.17)

где X - сумма значений яркостей точек закрываемых светлой частью признака;

Y - сумма значений яркостей точек закрываемых темной частью признака.

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

Алгоритм сканирования окна с признаками выглядит так:

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

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

- при сканировании изображения в каждом окне вычисляется приблизительно 200 000 вариантов расположения признаков, за счет изменения масштаба признаков и их положения в окне сканирования;

- сканирование производится последовательно для различных масштабов;

- масштабируется не само изображение, а сканирующее окно (изменяется размер ячейки);

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

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

Классифицировать объект - значит, указать номер (или наименование класса), к которому относится данный объект.

Классификация объекта - номер или наименование класса, выдаваемые алгоритмом классификации в результате его применения к данному конкретному объекту.

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

Обучающая выборка - конечное число данных.

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

Постановка классификации выглядит следующим образом:
Есть X - множество, в котором хранится описание объектов, Y - конечное множество номеров, принадлежащих классам. Между ними есть зависимость - отображение Y*: X => Y. Обучающая выборка представлена Xm = {(x1,y1), …, (xm,ym)}. Конструируется функция f от вектора признаков X, которая выдает ответ для любого возможного наблюдения X и способна классифицировать объект x?X. Данное простое правило должно хорошо работать и на новых данных.

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

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

Идея бустинга была предложена Робертом Шапиром (Schapire) в конце 90-х годов когда надо было найти решение вопроса о том, чтобы имея множество плохих (незначительно отличающихся от случайных) алгоритмов обучения, получить один хороший. В основе такой идеи лежит построение цепочки (ансамбля) классификаторов , который называется каскадом, каждый из которых (кроме первого) обучается на ошибках предыдущего. Например, один из первых алгоритмов бустинга Boost1 использовал каскад из 3-х моделей, первая из которых обучалась на всем наборе данных, вторая - на выборке примеров, в половине из которых первая дала правильные ответы, а третья - на примерах, где «ответы» первых двух разошлись. Таким образом, имеет место последовательная обработка примеров каскадом классификаторов, причем так, что задача для каждого последующего становится труднее. Результат определяется путем простого голосования: пример относится к тому классу, который выдан большинством моделей каскада.

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

К достоинствам алгоритма Виола-Джонса можно отнести следующие пункты:

- очень быстрая скорость работы;

- высокая эффективность;

- низкая вероятность обнаружения ложного лица;

- поиск лиц с наклоном до 30 градусов.

К недостаткам алгоритма Виола-Джонса можно отнести следующие пункты:

- медленная скорость обучения классификаторов;

- невозможен поиск лица при наклоне выше 40 градусов.

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

Ключевыми точками на лице являются угловые точки - точки сформированные из двух и более границ, где грани обычно определяют границу между объектами или части одного и того же объекта.

Углы определяются за счёт анализа яркости соседних пикселей. Углы бывают разного типа L,Y,T,X и их производные. Каждый детектор реагирует на них по-разному [13].

1.4.1 Детектор Харриса

Детектор Харриса - оптимальный детектор L-углов работает по принципу детектора Моравеца но дополнительно рассматривает производные яркости изображения для анализа изменения яркости по нескольким направлениям (см. рисунок 1.19) [14].

К достоинствам детектора Хариса можно отнести следующие пункты:

- инвариантен к поворотам;

- инвариантен к изменениям интенсивности.

К недостаткам детектора Хариса можно отнести следующие пункты:

- чувствительность к шуму;

- зависимость от масштаба.

1.4.2 Детектор Фростнера

Детектор Фростнера - более сложная в вычислительном плане реализация детектора Харриса. Собственные значения вычисляются явно.

Достоинство детектора Фростнера в поиске круговых точек вместе с углами. Недостаток детектора Фростнера в его сложности.

Рисунок 1.19 - Пример работы детектора Хариса

1.5 Формирование требований к проектируемому программному средству

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

1.5.1 Назначение разработки

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

Конечными пользователями являются пользователи персонального компьютера без специального образования.

1.5.2 Требование к данным

В качестве исходных данных приложение должно принимать изображения размером не более 100МБ и ограниченной в размере до 10000х10000 пикселей.

Приложение должно работать с изображениями следующих форматов:

- JPEG, JPG;

- BMP;

- GIF;

- PNG.

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

1.5.3 Состав выполняемых функций

Основные функции программного средства:

- предобработка изображения;

- классификация данных;

- определение эмоции;

- поиск человеческих лиц на изображении;

- поиск ключевых точек на лице;

- преобразование изображения в программные данные;

- отображение результатов работы на дисплей;

- сохранение качества исходного изображения.

1.5.4 Требования к технической совместимости

Техническая часть ПК должна включать:

- не менее 512МБ оперативной памяти;

- жесткий диск с не менее 55МБ свободного места;

- видеоадаптер;

- мышь.

1.5.5 Требования к информационной и программной совместимости

Программа должна работать автономно под управлением ОС Windows версии 7 и выше с установленным .NET Framework версии 4.5 и выше.

2. Анализ требований к пс и разработка функциональных требований

2.1 Диаграмма прецедентов ПС

На рисунке 2.1 изображена диаграмма прецедентов разрабатываемого программного средства. Основным и единственным действующим лицом является пользователь.

Так же из диаграммы видно, что функции ПС можно разделить на четыре основные категории:

- фильтрация или же обработка изображения;

- поиск лица на изображении;

- определение ключевых точек на лице;

- определение эмоции на лице.

Рисунок 2.1 - Диаграмма прецедентов ПС

2.2 Спецификация функциональных требований

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

2.2.1 Предобработка изображения

Спецификация данной функции представлена далее:

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

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

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

- при использовании фильтров больше одного раза программа сообщает об этом в виде сообщения;

- скорость работы не должна превышать более 0.2 секунды;

- не допускается генерация исключительных ситуаций;

- модуль по предобработке изображения должен быть представлен отдельной библиотекой платформы .NET в виде файла с расширением .dll;

- если контейнер с изображением пустой, отображается сообщение с ошибкой.

2.2.2 Классификация данных

Спецификация данной функции представлена далее:

- приложение классифицирует принадлежность ключевых точек к классам по их характеристикам;

- точность классификации должна быть выше 80% для изображений высокого качества (разрешение выше 1000х768) и выше 60% для изображений низкого качества (разрешение ниже 1000х768);

- классификация происходит по следующим категориям:

1) рот;

2) глаза;

3) вне лица.

- если классификация происходит без найденного лица, отображается сообщение с ошибкой;

- если контейнер с изображением пустой, отображается сообщение с ошибкой.

- если ключевые точки не были найдены, отображается сообщение с ошибкой;

- ключевые точки сохраняются в отдельный класс.

2.2.3 Определение эмоции

Спецификация данной функции представлена далее:

- классификация происходит по следующим категориям:

1) Печаль;

2) Радость;

3) Нейтрально;

4) Злость.

- результат эмоции отображается под лицом человека в виде текста с шрифтом Times New Roman и размером 12;

- при отсутствии результатов поиска эмоции вернуть в качестве результата исходное изображение;

- модуль по определению эмоций должен быть представлен отдельной библиотекой платформы .NET в виде файла с расширением .dll;

- класс отвечающий за определение эмоций должен наследоваться от интерфейса IEmotionReсognition;

- если контейнер с изображением пустой, отображается сообщение с ошибкой.

2.2.4 Поиск человеческих лиц на изображении

Спецификация данной функции представлена далее:

- лицо человека должно занимать более 15% изображения для того что бы оно было найдено;

- данные о найденных лицах хранятся в отдельном классе;

- при первом отсутствии результатов поиска, алгоритм выполняется ещё раз, при этом окно для поиска лиц уменьшается на 30%;

- при втором отсутствии результатов поиска вернуть пустой результат;

- алгоритм не должен находить лица, принадлежащие не человеку;

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

- если контейнер с изображением пустой, отображается сообщение с ошибкой;

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

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

2.2.5 Поиск ключевых точек на лице

Спецификация данной функции представлена далее:

- данные ключевых точек сохранятся в виде отдельного класса;

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

- пустой результат этой функции должен приводить к появлению сообщения с ошибкой;

- если поиск ключевых точек происходит без найденного лица, отображается сообщение с ошибкой;

- если контейнер с изображением пустой, отображается сообщение с ошибкой;

- ключевые точки на изображении не отображаются;

- после выполнения работы алгоритма выводится сообщение о завершении работы.

2.2.6 Преобразование изображение в программные данные

Спецификация данной функции представлена далее:

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

- матрица пикселей хранится в отдельном классе;

- матрицу можно преобразовать обратно в изображение;

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

- оригинальное изображение сохраняется как новое изображение в локальную переменную;

- оригинальное изображение можно восстановить через локальную копию.

2.2.7 Отображение результатов работы на дисплей

Спецификация данной функции представлена далее

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

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

- изображение в окне результата можно сохранить при помощи нажатии правой кнопки мыши и выбора пункта «Сохранить как».

2.2.8 Сохранение качества исходного изображения

Спецификация данной функции представлена далее:

- результирующее изображение имеет разрешение равное разрешению оригинального изображения;

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

- результирующее изображение имеет цветовую палитру такую же как у оригинального изображения;

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

3. Проектирование программного средства

ПС разработанное в рамках этого дипломного проекта состоит из нескольких основных модулей:

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

а) Повышение толщины границ объектов на изображении;

б) Изменение изображение с цветного на черно белое;

в) Изменение изображения на его негатив;

г) Свертка изображения с различными фильтрами для удаления артефактов.

Для применения различных фильтров к изображению был создан интерфейс IFilter который включает в себя метод Apply. Каждый класс, который наследует интерфейс IFilter, воспринимается системой как класс способный изменить изображение. Использование интерфейса в этом модуле позволяет абстрагироваться от использования конкретных классов, что обеспечивает гибкость в добавлении новых фильтров при необходимости.

Метод Apply позволяет проводить изменение изображение в зависимости от реализации фильтра, метод возвращает новое изображение, полученное при модификации входного изображения. Ниже представлен пример исходного кода одного из фильтров и диаграмма классов (см. рисунок 3.1).

public Image Apply(Image img)

{

var image = new Image(img);

var m = new Matrix(_matrix);

for(int i = 1; i < image.Height - 1; i++)

{

for(int j = 1; j < image.Width - 1; j++)

{

var pixel = image[i, j];

pixel.Blue = Calculate(i, j, m, (x, y) => image[x, y].Blue);

pixel.Green = Calculate(i, j, m, (x, y) => image[x, y].Green);

pixel.Red = Calculate(i, j, m, (x, y) => image[x, y].Red);

image[i, j] = pixel;

}

}

return image; }

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

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

Метод Apply позволяет применить фильтр к изображению.

Метод ComputeIntegralImage позволяет рассчитать интегральный вид изображения.

Метод GetImage преобразует массив байт обратно в изображение.

Метод GetValue возвращает значение интегрального изображения в точке с координатами x и у.



Рисунок 3.1 - Диаграмма классов модуля фильтрации

Пример исходного кода по преобразованию изображения в массив байт.

public Bitmap GetImage()

{

var bitmap = Pixels.GetRange(0, Width * Height).SelectMany(p => new[] { p.Blue, p.Green, p.Red }).ToArray();

var bmp = new Bitmap(Width, Height, PixelFormat.Format24bppRgb);

var data = bmp.LockBits(

new Rectangle(0, 0, Width, Height),

ImageLockMode.ReadWrite,

PixelFormat.Format24bppRgb);

Marshal.Copy(bitmap, 0, data.Scan0, bitmap.Length);

bmp.UnlockBits(data);

return bmp;

}

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

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

ThreeHorizontalRectanglesFeature - класс описывающий все признаки Хаара представленные в виде трех секций идущих горизонтально друг за другом. Шаблон этого класса представлен на рисунке 3.2.

Рисунок 3.2 - Шаблон для тройного горизонтального признака Хаара

ThreeVerticalRectanglesFeature - класс описывающий все признаки Хаара представленные в виде трех секций идущих вертикально друг за другом. Шаблон этого класса представлен на рисунке 3.3.

Рисунок 3.3 - Шаблон для тройного вертикального признака Хаара

TwoHorizontalRectanglesFeature - класс описывающий все признаки Хаара представленные в виде двух секций идущих горизонтально друг за другом. Шаблон этого класса представлен на рисунке 3.4.

Рисунок 3.4 - Шаблон для двойного горизонтального признака Хаара

TwoVerticalRectanglesFeature - класс описывающий все признаки Хаара представленные в виде двух секций идущих вертикально друг за другом. Шаблон этого класса представлен на рисунке ХХХ.

Рисунок 3.5 - Шаблон для двойного вертикального признака Хаара

FourRectanglesFeature - класс описывающий все признаки Хаара представленные в виде четырех секций идущих горизонтально друг за другом. Шаблон этого класса представлен на рисунке 3.6.

Все классы описывающие признаки Хаара наследуют интерфейс IFeature который обеспечивает способность вызвать метод ComputeValue для вычисления значения признака Хаара.

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

Рисунок 3.6 - Шаблон для квадратного признака Хаара

public int ComputeValue(Point WinTopLeft, float SizeRatio, Image Image)

{

var scaledFrame = this.Frame.Scale(SizeRatio);

var topLeft = scaledFrame.TopLeft().NestedPoint(WinTopLeft);

var rectsWidth = scaledFrame.Width / 2;

var rectsHeight = scaledFrame.Height / 2;

var aCoords = topLeft;

var bCoords = aCoords.Translate(rectsWidth, 0);

var cCoords = bCoords.Translate(rectsWidth, 0);

var dCoords = aCoords.Translate(0, rectsHeight);

var eCoords = dCoords.Translate(rectsWidth, 0);

var fCoords = eCoords.Translate(rectsWidth, 0);

var gCoords = dCoords.Translate(0, rectsHeight);

var hCoords = gCoords.Translate(rectsWidth, 0);

var iCoords = hCoords.Translate(rectsWidth, 0);

var a = Image.GetValue(aCoords);

var b = Image.GetValue(bCoords);

var c = Image.GetValue(cCoords);

var d = Image.GetValue(dCoords);

var e = Image.GetValue(eCoords);

var f = Image.GetValue(fCoords);

var g = Image.GetValue(gCoords);

var h = Image.GetValue(hCoords);

var i = Image.GetValue(iCoords);

var sumR1 = e - (b + d) + a;

var sumR2 = f - (c + e) + b;

var sumR3 = h - (e + g) + d;

var sumR4 = i - (f + h) + e;

return (int)(sumR1 - sumR2 - sumR3 + sumR4);

}

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

Сильный классификатор считывается из XML файла при помощи вызова метода LoadFromFile. Пример работы метода представлен ниже.

public static StrongClassifier LoadFromFile(string Path)

{

var asm = Assembly.GetExecutingAssembly();

Func<string, WeakClassifier> RestoreClassifier = (str) => {

string[] vals = str.Split(';');

var alpha = double.Parse(vals[0]);

var threshold = int.Parse(vals[1]);

var parity = sbyte.Parse(vals[2]);

var featureType = asm.GetType(vals[3]);

var featureX = int.Parse(vals[4]);

var featureY = int.Parse(vals[5]);

var featureWidth = int.Parse(vals[6]);

var featureHeight = int.Parse(vals[7]);

var featureFrame = new Rectangle(new Point(featureX, featureY),

featureWidth, featureHeight);

var feature = (IFeature) Activator.CreateInstance(featureType, featureFrame);

return new WeakClassifier(alpha, threshold, parity, feature);

};

var classifiers = File.ReadAllLines(Path).Select(RestoreClassifier)

.ToArray();

return new StrongClassifier(classifiers);

}

Классификатор используется в классе Detector в методе Detect.

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

public Detector(IntegralImage Image, IntegralImage SquaredImage, StrongClassifier Classifier)

{

this.Image = Image;

this.SquaredImage = SquaredImage;

this.Classifier = Classifier;

}

public Detector(GreyPixbuf Image, StrongClassifier Classifier)

: this(new IntegralImage(Image), new IntegralImage(Image, (pix) => (long) pix * pix),

Classifier)

{

}

public IEnumerable<Window> Detect()

{

Func<Window, bool> check = (win) =>

this.Classifier.Check(win, this.Image);

foreach (var item in Window.ListWindows(this.Image, this.SquaredImage))

{

if (check(item)) yield return item;

}

}

На рисунке 3.7 изображена диаграмма классов для работы с признаками Хаара.

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

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

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

- построено заданное количество базовых алгоритмов T;

- достигнута заданная точность на обучающей выборке;

- достигнутую точность на контрольной выборке не удаётся улучшить на протяжении последних нескольких шагов при определенном параметре алгоритма.

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



Рисунок 3.7 - Диаграмма классов модуля Features.

Рассматривается задача классификации на два класса, Y = {?1,+1}. К примеру, базовые алгоритмы также возвращают только два ответа ?1 и +1, и решающее правило фиксировано: C(b) = sign(b). Искомая алгоритмическая композиция имеет вид, отображенный на формуле 3.1:

. (3.1)

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

(3.2)

где Wl = (w1, …, wl) - вектор весов объектов.

Общий алгоритм адаптивного усиления, AdaBoost, выглядит следующим образом: Дано:

1) Y = {?1,+1};

2) b1(x), . . . , bT (x) возвращают ?1 и + 1;

3) Xl - обучающая выборка.

Решение:

1. Инициализация весов объектов:

(3.3)

2. Расчет формулы 3.4

= minQ(b;). (3.4)

3.

4. Расчет формулы 3.5

. (3.5)

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

; (3.6)

6. Нормировка весов объектов:

(3.7)

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

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

- место положение объекта по координате У;

- место положение объекта по координате Х;

- минимальный размер области, в которую помещается объект;

- область лица, в которой был найден объект.