Участник: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]D={A}^d[/math], где d - размерность дескриптора. Можно рассматривать достаточно много различных оценивающих функций (метриками их называть некорректно, т.к для них не всегда выполняется неравенство треугольника). Например, в качестве такой функции можно рассматривать cosine distance - косинус угла между векторами-признаками в d-мерном пространстве. Также достаточно часто используют L2 метрику, либо более сложные контрукции, такие как Joint Bayesian. Преимущество cosine метрики в том, что она требует меньше операций для вычисления, чем L2. На вычисление L2 метрики необходимо дополнительно производить операции вычитания. В разделе "Практическая реализация системы" будет рассмотрен вариант на FMA3 инструкциях, практическое ограничение которого это скорость обмена с оперативной памятью при чтении дескрипторов. После вычисления оценивающей функции часто применяют отображение результата в интервал [0-1] для упрощения анализа результатов.

1.5 Формирование результата

Предположим, что для каждого человека в базе есть несколько фотографий. Тогда после выполнения операции сравнения биометрических шаблонов необходимо выбрать фотографию с максимальным значением оценивающей функции для данного человека. Обычно используют максимум из значений оценивающей функции, но может также использоваться и усреднение. Такая операция потребует [math]O(n*logn)[/math] операций для сортировки результатов и выбора максимальных из них.

2 Практическая реализация системы

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

2.1 Быстрое сравнение биометрических шаблонов

При выполнении оценки производительности системы использовалась простая реализация cosine метрики (цикл для вычисления скалярного произведения) и с использованием FMA инстукций. Набор инструкций FMA позволяет выполнять операцию y = ax + b без дополнительных операций.

Псевдокод операции mm256_fmadd (intel)

FOR j := 0 to 7
i := j*32
dst[i+31:i] := (a[i+31:i] * b[i+31:i]) + c[i+31:i]
ENDFOR
dst[MAX:256] := 0