Участник:Bagnikita/Face Recognition

Распознавание лиц
Последовательный алгоритм
Последовательная сложность	[math]O(n*d) + O(n*log(n)) + O(E(w,h,c))[/math]
Объём входных данных	[math]w*h*c[/math]
Объём выходных данных	[math]O(k)[/math]
Параллельный алгоритм
Высота ярусно-параллельной формы	[math]O(k)[/math]
Ширина ярусно-параллельной формы	[math]O(n)[/math]

Основные авторы описания: Н.Ю.Багров

1 Свойства и структура алгоритма

1.1 Общее описание алгоритма

Распознавание лиц при помощи компьютера было впервые предложено в 1966 г. Woody Bledsoe и др. В первой системе использовался графический планшет, на котором было необходимо вручную отметить ключевые особенности на лице (брови, губы и тд). Система в дальнешейм использовала расстояния между этими точками для сравнения разных изображений. Поскольку требовалось много ручной работы, то оператор мог обработать около 40 изображений в час. В 1997 была создана система, которая непосредственно работала с видеоданными и могла применяться на практике. В дальшейшем с увеличением производительности вычислительных систем появились более качественные алгоритмы, но они заметно уступали человеку на данной задаче. С появлением высокороизводительных видеокарт в 2014 году появились системы, точность которых уже превышала точность оператора (человека). Основное преимущество таких систем в том, что они могут обрабатывать большие объемы данных - производительность человека намного ниже (требуется несколько секунд на сравнение пары изображений).

Задачу распознавания лиц можно разбить на несколько этапов:

• Обучение нейронной сети
• построение биометрического шаблона
• сравнение биометрических шаблонов
• формирование результата

1.2 Обучение нейронной сети

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

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

• пусть размерность фильтра свертки k*k
• скопируем блоки исходного изображения размером k*k в столбцы новой матрицы
• умножим эту матрицу на коэффициеты фильтра свертки
• полученная матрица будет результатом применения свертки к входному изображению

Размерность матрицы зависит квадратично от размера фильтра и количества выходных данных.

[math]R = A^(n, w * h) * B^(w * h, c * k^2)[/math]

Существуют библиотеки (nvidia cudnn), которые решают данную задачу более эффективно. Например, свертки размером 3x3, 5x5 в ней реализованы с использованием FFT (которое работает на видеокарте быстрее, чем умножение матриц)

1.3 Построение биометрического шаблона

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

1.4 Сравнение биометрических шаблонов

Исходные данные: положительно определённая симметрическая матрица [math]A[/math] (элементы [math]a_{ij}[/math]).