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

Распознавание лиц
Последовательный алгоритм
Последовательная сложность	[math]O(E(w,h,c)+n*d+n*logn+n*logk+CNNConst)[/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 Математическое описание алгоритма

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

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

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

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

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

Сложность задачи вычисления свертки зависит квадратично от размера фильтра и линейно от количества выходных данных.

[math]FeatureMap = A^{n, w * h} * B^{w * h, c * k^2}[/math], где [math]FeatureMap[/math] - результат применения свертки, а [math]A[/math] и [math]B[/math] - входное изображение и матрица весов слоя нейронной сети

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

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

Будем называть биометрическим шаблоном вектор [math]{R}^d[/math], который является представлением лица человека. Этот вектор получается после применения нейронной сети к изображению - в качестве такого вектора используют отклики с одного последних слоев нейронной сети. Для обеспечения возможности сравнивать между собой эти шаблоны вектор нормализуют.

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

На предыдущем этапе был получен вектор значений [math]D={A}^d[/math], где d - размерность дескриптора. Можно рассматривать достаточно много различных оценивающих функций (метриками их называть некорректно, т.к для них не всегда выполняется неравенство треугольника). Например, в качестве такой функции можно рассматривать cosine distance - косинус угла между векторами-признаками в d-мерном пространстве. Также достаточно часто используют L2 метрику, либо более сложные контрукции, такие как Joint Bayesian. У всех таких "метрик" есть преимущества и недостатки, например в L2 можно легко проводить кластеризацию, тогда как в JointBayes и cosine metric нет. JointBayes можно дообучить на целевой выборке и повысить точность работы алгоритма.

1.2.4 Поиск в базе и формирование результата

Предположим, что для каждого человека в базе есть несколько фотографий. Тогда после выполнения операции сравнения биометрических шаблона изображения-запроса [math]P[/math] и всех изображений в базе [math]G={g1,g2,...,gn}[/math] необходимо выбрать результат с максимальным значением оценивающей функции для данного человека. Т.е необходимо оставить в результате только уникальные по людям совпадения, выбрав при этом максимальное значение при удалении дубликатов по людям.

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

1.3 Вычислительное ядро алгоритма

Основные операции составляют построение биометрического шаблона, и поиск в базе

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

Обозначим за [math]E(w,h,c)[/math] сложность операции вычисления биометричсекого шаблона по входному изображению лица человека. Поскольку сверточной нейронной сети с полносвязными слоями должно подаваться на вход изображения фиксированного размера, то необходимо изменить разрешение исходного изображения. В данной реализации алгоритма распознавания лиц используется билинейная интерполяция. Нейронная сеть получает на вход одноканальные изображения размером [math]100*100[/math]. Поэтому число необходимых операций (по операциям умножения) можно оценить как [math]O(w*h*c) + O(100 * 100 * 6) = O(w*h*c) + Const[/math]. На практике эта константа существенна, поскольку эти операции неоднородны по памяти.

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

В реализации, предлолженной в практической части, используются более 10 сверточных слоев. Количестве операций можно оценить исходя из количества весов связей в нейронной сети - 80M и размера сверток [math]3*3[/math]. Оценка числа операций получилась ~2 GFlops на одну операцию применения нейросети (forward pass, 180ms). Она согласуется с реальным временем работы системы и производительностью системы на тесте linpack (130GFlops 4 cores) на ноутбуке.

1.3.2 Поиск в базе

Поиск в базе состоит из следующих частей:

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

1.3.2.1 Сравнение между собой двух дескрипторов изображений и вычисление метрики по базе

В практической реализации алгоритма используется косинусовая метрика [math]M(x,y)=\frac{(x,y)}{\lVert x \lVert * \lVert y \lVert}[/math]. Заметим, что вектора [math]x, y[/math] уже нормированы на предыдущем этапе. Поэтому число операций для вычисления метрики составляет [math]d[/math] умножений и [math]d - 1[/math] сложений, где d - размерность дескриптора. Если размер базы [math]n[/math], то число операций [math]O(n*d+n*(d-1))=O(n*d)[/math].

1.3.2.2 Агрегация результатов по людям

Для выполнения операции unique (без использования дополнительной памяти) необходимо отсортировать элементы (person_id, match_score) массива по ключу person_id, а при совпадении по score. После этого можно за линейное время удалить дубликаты по person_id, оставив первый элемент (который будет максимальным по match_score). Сложность таких операций [math]O(n*logn+n)=O(n*logn)[/math].

1.3.2.3 Cортировка по убыванию метрики сходства двух изображений

Финальная сортировка по match_score будет выполнена за O(n*logk), где k - количество результатов в выдаче. Обычно на практике число k не более 1000, поскольку обработка результата чаще всего производится вручную оператором.

1.4 Макроструктура алгоритма

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

• известна метрика для сравнения
• можно получить дескрипторы (биометрические шаблоны) в явном виде

1.5 Схема реализации последовательного алгоритма

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

desc = enroll(Image) # Image - изображение лица человека
matches = {}
for gallery_entry in G:
    if matches.get(gallery_entry.person_id, None) is None:
        matches[gallery_entry.person_id] = 0.0
    matches[gallery_entry.person_id] = max(matches[gallery_entry.person_id], match(desc, gallery_entry.descriptor))
matches = sorted(key = lambda x: x[1], matches.items())
return [x[0], applyMapping(x[1]) for x in matches]

1.6 Последовательная сложность алгоритма

Если рассматривать всю последовательность действий (построение шаблона, поиск в базе), то сложность алгоритма [math]O(E(w,h,c)+n*d+n*logn+n*logk+CNNConst)[/math], где

• [math]n[/math] - число элементов в базе
• [math]d[/math] - размерность биометрического шаблона
• [math]E(w,h,c)[/math] - сложность обработки изображения размером (width*height*channels) до необходимого размера для нейросети
• [math]n*d[/math] - число операций для вычисления метрики между запросом и базой
• [math]n*logn[/math] - сортировка результата для удаления дубликатов
• [math]n*logk[/math] - сортировка результата по значению оценивающей функции

1.7 Информационный граф

TODO

1.8 Ресурс параллелизма алгоритма

Сложность параллельного алгоритма, в предположении доступности q узлов: [math]O(k*logk+q*(log(k*q))^2+\frac{n}{q}*(d+log(\frac{n}{q}))+\lambda*(k*log(q)+q*(log(q*k))^2))[/math], где

• n - размер базы изображений лиц
• d - размерность биометрического шаблона
• k - количество результатов в выдаче (k << n)
• [math]\lambda[/math] - флаг (0 или 1), нужно ли производить агрегацию результатов по людям

Данная оценка получена с применением параллельной сортировки.

1.9 Входные и выходные данные алгоритма

Входные данные:

• изображение [math]P\in{R}^{w*h*c}[/math], где w,h,c - ширина, высота, число каналов
• база изображений лиц [math]G={g_1,g_2,g_3,...,g_n}, g_i\in{T}[/math]
• T - объект, состоящий из биометрического шаблона и порядкового номера человека

Выходные данные*

• список [math]L={l_1,l_2,...,l_k}[/math], где [math]l_i\in{T}[/math]
• T - объект, состоящий из числа (мера сходства двух изображений) и id (порядкового номера) человека в базе

1.10 Свойства алгоритма

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

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

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

2 Программная реализация алгоритма

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

2.1 Особенности реализации последовательного алгоритма

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

Псевдокод операции 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

В результате тестирования (процессор 6300HQ, ноутбук, база 30М биометрических шаблонов) однопоточной программы было установлено, что FMA3 версия в 5 раз быстрее по сравнению с обычным циклом (880ms vs 4600ms). Все дальнейшие экспериенты будут проводиться с FMA3 реализацией (если не указано иначе). Компиляция производится gcc 5.4 с флагами -O3 -static-libgcc -static-libstdc++ -mavx -mavx2 -mfma -fopenmp

Ниже приводится пример кода для вычисления дескриптора:

pp = descriptor;
pg = gallery_ptr;
__m256 sum = _mm256_setzero_ps();
for(int j = 0; j < 16; ++j, pp += 8, pg += 8) {
    sum = _mm256_fmadd_ps(_mm256_load_ps(pp), _mm256_load_ps(pg), sum);
}
const __m128 x128 = _mm_add_ps(_mm256_extractf128_ps(sum, 1), _mm256_castps256_ps128(sum));
const __m128 x64 = _mm_add_ps(x128, _mm_movehl_ps(x128, x128));
const __m128 x32 = _mm_add_ss(x64, _mm_shuffle_ps(x64, x64, 0x55));
score = _mm_cvtss_f32(x32);

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

2.2 Локальность данных и вычислений

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

Сортировка результатов также обладает свойством локальности, поскольку массив хранится непрерывно в памяти. При небольшом размере базы (1-10M изображений) он может полностью поместиться в кэш памяти.

2.3 Возможные способы и особенности параллельной реализации алгоритма

Алгоритм построен по модели map/reduce. В map происходит вычисление скалярных произведений дескриптора-запроса и элементов базы. В reduce происходит сортировка и удаление повторов.

Исходная база разбирается на блоки (chunks) по 1M биометрических шаблонов, каждый такой блок обрабатывается независимо в своем потоке (или процессе). Важно то, что в результате работы алгоритма на каждом блоке в результате получается небольшой объем данных - [math]k*(sizeof(float)+sizeof(int32_t))[/math]. Такие данные можно легко передать по медленному каналу с высокой задержкой (не требуется использование InfiniBand). Также данный алгоритм можно запускать как на MPI кластерах с передачей сообщений, так и на hadoop кластерах.

Для сортировки результатов можно применять параллельную сортировку (которая ассимптотически) лучше, но на практике это не нужно из-за разумного ограчения на число результатов. Часто их просматривает вручную оператор системы, поэтому больше нескольких тысяч ставить бессмысленно.

В текущей версии системы реализован параллелизм с использованием OpenMP. Вместо OpenMP можно использовать любой метод многопоточной обработки данных, например, pthread. Сложность модификации кода минимальна, поскольку map/reduce подразумевает отсутствие зависимостей между различными блоками.

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

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

2.4 Масштабируемость алгоритма и его реализации

В дальнейшем во всех тестах будет использоваться сервер с 2x E5-2683v3 128GB RAM. MOPS - миллионы операций (для map -скалярное произведение, reduce - сортировка) в секунду.

Результаты работы map функции в завсимости от размера базы и числа потоков в openmp:

Т.к скорость чтения из DDR4 памяти 17GB/s (на практике немного меньше), то с 4 каналов памяти (по 2 на каждый процессор) нельзя считывать быстрее, чем 68GB/s. База 200M дескрипторов занимает 98GB ram, поэтому время 2300ms для вычисления всех скалярных произведений близко к нижней границе. Дальнейшее увеличение числа потоков на одном сервере не будет приводить к существенному ускорению работы программы.

Результаты работы reduce функции в завсимости от размера базы и числа потоков в openmp:

Reduce этап лучше распараллеливается, поскольку в нем намного меньше число обращений к памяти. Его также можно ускорять, например подбирая оптимальный размер блока (chunk size). Для базы в 200M лиц лучшая скорость 1400ms (достигается на 20 потоках, дальше ускорения нет).

Суммарная скорость работы системы в завсимости от размера базы и числа потоков в openmp:

2.4.1 Исследование влияния HyperThreading на работу алгоритма

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

Синяя точка на графике - лучший результат без HyperThreading, красная - HyperThreading включен.

Результаты работы map функции в завсимости от размера базы и числа потоков в openmp (10-56 потоков):

Результаты работы reduce функции в завсимости от размера базы и числа потоков в openmp (10-56 потоков):

Суммарная скорость работы системы в завсимости от размера базы и числа потоков в openmp (10-56 потоков):