Raspoznanie_litsa02

МОСКОВСКИЙ АВТОМОБИЛЬНО-ДОРОЖНЫЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ (МАДИ)

Факультет «Автомобильный транспорт»

Кафедра

«Высшей математики»

Курсовая работа по дисциплине

«Интеллектуальные системы»

Тема: «Распознание лица»

Выполнил: студент группы 2бПМ

Хамраев Н.Т.

Проверил: Заведующий каф. ВМ Буслаев А. П.

Москва 201

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

Цель работы: 5

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

Введение 5

Метод Виолы-Джонса (Viola-Jones) (по фамилиям двух его авторов). Хотя метод был разработан и представлен в 2001 году Полом Виолой и Майклом Джонсом, он до сих пор на момент написания моего поста является основополагающим для поиска объектов на изображении в реальном времени. Предназначен для обнаружения объектов на изображениях в реальном времени (например, на кадрах видео-потока). Метод отвечает на вопросы: "есть ли на изображении лица людей?", и "где они, предположительно, находятся?". 5

Основные принципы, на которых основан метод, таковы: 1) используются изображения в интегральном представлении, что позволяет вычислять быстро необходимые объекты; 5

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

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

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

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

Признаки Хаара Признак — отображение f: X => Df, где Df — множество допустимых значений признака. Если заданы признаки f1,…,fn, то вектор признаков x = (f1(x),…,fn(x)) называется признаковым описанием объекта x ∈ X. Признаковые описания допустимо отождествлять с самими объектами. При этом множество X = Df1* …* Dfn называют признаковым пространством [1]. Признаки делятся на следующие типы в зависимости от множества Df: 6

бинарный признак, Df = {0,1}; 6

номинальный признак: Df — конечное множество; 6

порядковый признак: Df — конечное упорядоченное множество; 6

количественный признак: Df — множество действительных чисел. 6

Естественно, бывают прикладные задачи с разнотипными признаками, для их решения подходят далеко не все методы. В стандартном методе Виолы – Джонса используются прямоугольные признаки, изображенные на рисунке ниже, они называются примитивами Хаара: 6

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

Элементы матрицы рассчитываются по следующей формуле: 7

где I(i,j) — яркость пиксела исходного изображения. Каждый элемент матрицы II[x,y] представляет собой сумму пикселов в прямоугольнике от (0,0) до (x,y). 7

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

Расчет матрицы можно производить по рекуррентной формуле: 7

II(x,y) = I(x,y) — II(x-1,y-1) + II(x,y-1) + II(x-1,y) 7

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

7

Пусть ABCD — интересующий нас прямоугольник: Из рисунка понятно, что сумму внутри прямоугольника можно выразить через суммы и разности смежных прямоугольников по следующей формуле: (ABCD) = II(A) + II(С) — II(B) — II(D) Простая и замечательная формула. Все компоненты для вычисления уже хранятся в интегральной матрице, вычисление занимает четыре обращения к массиву и три арифметических действия. 8

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

Для вычисления суммы пикселов внутри фигуры, применим дискретную теорему Грина, и получим следующую формулу: SumOfFigure(ABCDEFGHIJKL)=II(A)-II(B)+II(С)-II(D)+II(E)-II(F)+II(G)-II(H)+II(I)-II(J)+II(K)-II(L), где 9

A=(X-r, Y-R) B=(X+r, Y-R) C=(X+r, Y-r) D=(X+R, Y-r) E=(X+R, Y+r) F=(X+r, Y+r) G=(X+r, Y+R) H=(X-r, Y+R) I=(X-r, Y+r) J=(X-R, Y+r) K=(X-R, Y-r) L=(X-r, Y-r) r=R/√2 9

R — радиус круга (X,Y) — центр круга Как видим, формула требует 12 обращений к интегральной матрице и 11 арифметических операций (не считая рассчета координат самих точек фигуры). 9

«Машинное обучение — это наука, изучающая компьютерные алгоритмы, автоматически улучшающиеся во время работы» (Michel, 1996) 13

http://habrahabr.ru/post/102919/ ( Интегральное представление изображений) Статья Павела Торгашова 14

http://habrahabr.ru/post/133826/ (Метод Виолы-Джонса (Viola-Jones) как основа для распознавания лиц) статья ника в сети «skynoname» (найти разрешение (http://habrahabr.ru/users/nickbbc/) 14

http://habrahabr.ru/post/198338/ (Использование каскада Хаара для сравнения изображений) статья Мальцева Антона 14

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

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

Цель работы:

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

Введение

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

Метод Виолы-Джонса (Viola-Jones) (по фамилиям двух его авторов). Хотя метод был разработан и представлен в 2001 году Полом Виолой и Майклом Джонсом, он до сих пор на момент написания моего поста является основополагающим для поиска объектов на изображении в реальном времени. Предназначен для обнаружения объектов на изображениях в реальном времени (например, на кадрах видео-потока). Метод отвечает на вопросы: "есть ли на изображении лица людей?", и "где они, предположительно, находятся?".

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

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

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

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

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

Признаки Хаара Признак — отображение f: X => Df, где Df — множество допустимых значений признака. Если заданы признаки f1,…,fn, то вектор признаков x = (f1(x),…,fn(x)) называется признаковым описанием объекта x ∈ X. Признаковые описания допустимо отождествлять с самими объектами. При этом множество X = Df1* …* Dfn называют признаковым пространством [1]. Признаки делятся на следующие типы в зависимости от множества Df:

бинарный признак, Df = {0,1};

номинальный признак: Df — конечное множество;

порядковый признак: Df — конечное упорядоченное множество;

количественный признак: Df — множество действительных чисел.

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

В расширенном методе Виолы – Джонса, использующемся в библиотеке OpenCV используются дополнительные признаки:

Вычисляемым значением такого признака будет F = X-Y, (1.5) где X – сумма значений яркостей точек закрываемых светлой частью признака, а Y – сумма значений яркостей точек закрываемых темной частью признака. Признаки Хаара дают точечное значение перепада яркости по оси X и Y соответственно.

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

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

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

Элементы матрицы рассчитываются по следующей формуле:

где I(i,j) — яркость пиксела исходного изображения. Каждый элемент матрицы II[x,y] представляет собой сумму пикселов в прямоугольнике от (0,0) до (x,y).

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

Расчет матрицы можно производить по рекуррентной формуле:

II(x,y) = I(x,y) — II(x-1,y-1) + II(x,y-1) + II(x-1,y)

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

Пусть ABCD — интересующий нас прямоугольник: Из рисунка понятно, что сумму внутри прямоугольника можно выразить через суммы и разности смежных прямоугольников по следующей формуле: (ABCD) = II(A) + II(С) — II(B) — II(D) Простая и замечательная формула. Все компоненты для вычисления уже хранятся в интегральной матрице, вычисление занимает четыре обращения к массиву и три арифметических действия.

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

Для вычисления суммы пикселов внутри фигуры, применим дискретную теорему Грина, и получим следующую формулу: SumOfFigure(ABCDEFGHIJKL)=II(A)-II(B)+II(С)-II(D)+II(E)-II(F)+II(G)-II(H)+II(I)-II(J)+II(K)-II(L), где

A=(X-r, Y-R) B=(X+r, Y-R) C=(X+r, Y-r) D=(X+R, Y-r) E=(X+R, Y+r) F=(X+r, Y+r) G=(X+r, Y+R) H=(X-r, Y+R) I=(X-r, Y+r) J=(X-R, Y+r) K=(X-R, Y-r) L=(X-r, Y-r) r=R/√2

R — радиус круга (X,Y) — центр круга Как видим, формула требует 12 обращений к интегральной матрице и 11 арифметических операций (не считая рассчета координат самих точек фигуры).

OpenCV - Библиотека компьютерного зрения с открытым исходным кодом(Open Source Computer Vision Library), содержащая более 500 функций, заточенных под выполнение в реальном времени.

Изначально перед OpenCV ставились следующие цели:

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

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

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

Реализация C# Первый метод производит вычисление интегральной матрицы. Второй — рассчитывает суммарную яркость произвольного прямоугольника:

//вычисление интегрального представления изображения     public static int[,] IntegralImage(int[,] sourceImage)     {       int width = sourceImage.GetLength(0);       int height = sourceImage.GetLength(1);       int[,] result = new int[width, height];       result[0, 0] = sourceImage[0, 0];       for (int x = 1; x < width; x++)         result[x, 0] = sourceImage[x, 0] + result[x - 1, 0];       for (int y = 1; y < height; y++)         result[0, y] = sourceImage[0, y] + result[0, y - 1];       for (int y = 1; y < height; y++)         for (int x = 1; x < width; x++)           result[x, y] = sourceImage[x, y] + result[x - 1, y] + result[x, y - 1] - result[x - 1, y - 1];       return result;     }     //рассчет суммы яркости пикселов в произвольном прямоугольнике     public static int SumOfRectangle(int[,] integralImage, Rectangle rect)     {       int A = 0, B = 0, C = 0, D = 0;       if (rect.Top > 0 || rect.Left > 0)         if (rect.Top <= 0)           D = integralImage[rect.Left - 1, rect.Bottom];         else         if (rect.Left <= 0)           B = integralImage[rect.Right, rect.Top - 1];         else         {           A = integralImage[rect.Left - 1, rect.Top - 1];           B = integralImage[rect.Right, rect.Top - 1];           D = integralImage[rect.Left - 1, rect.Bottom];         }       C = integralImage[rect.Right, rect.Bottom];       return A + C - B - D;     }

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

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

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

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

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

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

• все найденные признаки попадают к классификатору, который «выносит вердикт».

OpenCV

состоит из нескольких модулей:

• CXCORE – Ядро, содержит:

  • Базовые структуры

  • Матричную алгебру

  • Алгоритмы работы с памятью

  • Алгоритмы преобразования типов

  • Алгортмы для обработки ошибок

  • Функции для записи/чтения XML файлов

  • Функции для работы с 2D графиками

• CV – Модуль обработки изображений, работа с компьютерным зрением, содержит:

  • Функции для работы с изображениями (преобразование, фильтрация и т.д.)

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

  • Алгоритмы анализа движений, слежение за объектами

  • Алгоритмы распознания объектов (лиц, предметов)

  • Алгоритмы для калибровки камер

• ML – Машинное обучение:

  • Функции для классификации и анализа данных

• HighGUI – Модуль для создания пользовательского интерфейса, отвечает за:

  • Создание окон

  • Вывод изображений

  • Захват видео из файлов и камер

  • Чтение/Запись изображений

• CVCAM – Захват видео с цифровых камер

• CVAUX – Устаревшие функции:

  • Пространственное зрение

  • Нахождение и описание черт лица

  • Поиск стерео соответствий

  • Описание текстур

«Машинное обучение — это наука, изучающая компьютерные алгоритмы, автоматически улучшающиеся во время работы» (Michel, 1996)

Список используемой литературы и ссылки на web-страницы:

http://face-rec.org/general-info/ (помогло сформулировать цель) Загребский университет, Факультет электротехники и вычислительной техники Департамент беспроводных коммуникаций. Профессор Mislav Grgic, доктор философии и Кресимир Делач, доктор философии

http://habrahabr.ru/post/102919/ ( Интегральное представление изображений) Статья Павела Торгашова

http://habrahabr.ru/post/133826/ (Метод Виолы-Джонса (Viola-Jones) как основа для распознавания лиц) статья ника в сети «skynoname» (найти разрешение (http://habrahabr.ru/users/nickbbc/)

http://habrahabr.ru/post/198338/ (Использование каскада Хаара для сравнения изображений) статья Мальцева Антона

Published in: Pattern Analysis and Machine Intelligence, IEEE Transactions on (Volume:32 , Issue: 11 ) Biometrics Compendium, IEEE (Биометрия сборник)

Page(s): 2022 – 2038 нашел через ссылку в интернете (http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=5401161 )

http://ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%B8%D0%B7%D0%BD%D0%B0%D0%BA%D0%B8_%D0%A5%D0%B0%D0%B0%D1%80%D0%B0 (Признаки Хаара) из книги Lienhart, R. and Maydt, J., "An extended set of Haar-like features for rapid object detection", ICIP02, pp. I: 900–903, 2002

http://www.hardbroker.ru/pages/recognition (распознавание лиц) помогло сформулировать мысл о биометрических чертах лица

http://locv.ru/wiki/%D0%93%D0%BB%D0%B0%D0%B2%D0%BD%D0%B0%D1%8F_%D1%81%D1%82%D1%80%D0%B0%D0%BD%D0%B8%D1%86%D0%B0 перевод Романа Исайкина из книги Learning OpenCV: Computer Vision with the OpenCV Library Gary Bradski (Author), Adrian Kaehler (Author) http://www.amazon.com/Learning-OpenCV-Computer-Vision-Library/dp/0596516134

Буду использовать

http://www.ics.uci.edu/~xzhu/paper/face-cvpr12.pdf

http://www.compvision.ru/forum/index.php?showtopic=15&st=200

http://ladacom.ru/site/node/13

javascript

http://shvetsgroup.com/ru/blog/js-css-optimisation

http://habrahabr.ru/post/123635/

http://habrahabr.ru/post/187452/

https://github.com/joyent/node/wiki/modules#graphics

http://iss.norcity.ru/modules.php

http://shvetsgroup.com/ru/blog/js-css-optimisation

15