Участник: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 Построение биометрического шаблона

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

Обозначим за [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).

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

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 позволяет выполнять операцию [math]y = ax + b[/math] без дополнительных операций.

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

Применение openmp позволило ускорить версию с обычным циклом до 1300ms, что медленнее FMA3. Вычисление в несколько потоков не ускорило реализацию на FMA3. Вероятно, причина в пропускной способности оперативной памяти - для DDR4 15GBps на канал. Объем тестовой базы 15.5GB, поэтому не менее 500ms должно было занять чтение из памяти.

На сервере (2x E5-2683v3 256GB RAM, база 150М биометрических шаблонов) получилось следующее ускорение от использования FMA3 (MOPS - количество операций сравнения в секунду):

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

Количество операций с плавающей точкой (умножения) для сравнения биометрических шаблонов: [math]n*128[/math] FLOP.

2.2 Быстрое формирование результата

Если на каждой операции поиска изображения в базе необходимо выбирать максимальную фотографию для каждого челокека в базе, то задача сводится к классической map/reduce:

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

В reduce применение openmp позволило увеличить скорость с 3000ms до 1000ms на 4 ядрах процессора (ноутбук с 6300HQ, 30M записей в базе)

Из дальшейнего фрагмента кода очевидно, что при таком распараллеливании нет зависимостей по переменным. Эксперимент показал, что применять openmp для inplace_merge неэффективно для текущих ограничений на размер базы (200-300M).

vector<MatchResult> OMP_Blob::reduce(size_t top_k, bool merge_person)
{
    const int num_chunks = static_cast<int>(_chunks.size());

    vector<MatchResult> result;
    vector<vector<MatchResult>> results(num_chunks);
    #pragma omp parallel for num_threads(_num_threads)
    for(int i = 0; i < num_chunks; ++i) {
        results[i] = _chunks[i].reduce(top_k, merge_person, false);
    }

    for(int i = 0; i < num_chunks; ++i) {
        result.insert(result.end(), results[i].begin(), results[i].end());
    }

    if(merge_person) {
        size_t csum = 0;
        for(int i = 0; i < num_chunks; ++i) {
            inplace_merge(result.begin(), result.begin() + csum, result.begin() + csum + results[i].size(), [](const MatchResult &a, const MatchResult &b) {
                return a.person_id < b.person_id || (a.person_id == b.person_id && a.score > b.score);
            });
            csum += results[i].size();
        }
        result.resize(unique(result.begin(), result.end(), [](const MatchResult &a, const MatchResult &b) {
            return a.person_id == b.person_id;
        }) - result.begin());
    }
    size_t result_size = min(top_k, result.size());
    partial_sort(result.begin(), result.begin() + result_size, result.end(), [](const MatchResult &a, const MatchResult &b) {
        return a.score > b.score;
    });
    result.resize(result_size);
    result.shrink_to_fit();
    return result;
}

Финальную сортировку результатов по score ускорять не требуется, поскольку top_k на практике не более 1000.