Об эффективности применения алгоритма SURF в задаче

Об эффективности применения алгоритма SURF В задаче идентификации лиц

, студент 5-го курса кафедры защиты информации ГУАП, *****@

Аннотация

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

Введение

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

Обзор существующих решений задачи

идентификации лиц

В этом разделе рассматриваются основные принципы работы наиболее популярных алгоритмов идентификации лиц.

1.  Алгоритм EigenFaces [2]

Работа алгоритма основана на методе главных компонент. Предположим, что имеется база данных лиц, где изображения имеют размер N x N пикселей. Каждое изображение из базы данных представляют точкой в пространстве размерностью N x N. Основная идея алгоритма состоит в том, чтобы найти такой базис меньшей размерности, после проекции в который максимально сохраняется информация по осям с большой дисперсией и теряется информацию по осям с маленькой дисперсией. Это нужно для того, чтобы оставить только ту информацию, которая бы характеризовала различия лиц и удалить ненужную информацию, которая может помешать правильно идентифицировать человека.

Процедура идентификации выполняется в новом базисе с использованием Евклидовой метрики.

Основными недостатками алгоритма EigenFaces является отсутствие устойчивости к изменению условий освещенности и отсутствие инвариантности к аффинным преобразованиям.

2.  Алгоритм FisherFaces [3]

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

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

Алгоритм SURF (Speeded-Up Robust Features) для выделения и описания ключевых особенностей изображения [1]

В этом разделе рассматриваются ключевые моменты алгоритма SURF и анализируются его основные преимущества и недостатки.

1.  Поиск ключевых точек изображения

Ключевая точка изображения – точка, которая имеет некие признаки, существенно отличающие ее от основной массы точек (резкие перепады освещенности, углы и т. д.). Ключевые точки изображения ищутся путем анализа определителя матрицы Гёссе для каждого пикселя изображения:

(1)

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

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

2.  Нахождение ориентации ключевой точки изображения

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

3.  Построение дескриптора ключевой точки изображения

Вокруг ключевой точки описывается прямоугольная область. Эта область разбивается на 16-ти квадрантов одинаковых размеров. Прямоугольная область затем поворачивается в соответствии с ориентацией ключевой точки. На следующем шаге считаются оценки для каждого из 16-ти квадрантов области с помощью фильтров Хаара:

(2)

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

В результате получается вектор из 64-х чисел. К описанию точки также добавляют след матрицы Гёссе. Вектор и след матрицы вместе образуют дескриптор ключевой точки. На данном этапе алгоритм SURF заканчивается.

4.  Анализ преимуществ и недостатков алгоритма

За счет использования вторых производных алгоритм SURF становится инвариантен к перепадам яркости. Благодаря использованию разных размеров области взятия вторых производных и вычислению ориентации ключевых точек алгоритм становится инвариантен к изменению масштаба и повороту лица человека в плоскости изображения [1].

Схема идентификации на основе алгоритма SURF (Speeded-Up Robust Features)

В этом разделе описывается способ идентификации лиц на основе алгоритма SURF. Схема идентификации представлена на Рисунке 3.

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

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

2.  Анализ масштаба фильтров. Ключевые точки должны быть получены при близких размерах фильтров вторых производных.

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

4.  Евклидова метрика. Вычисляется для каждой пары дескрипторов.

5.  Гистограммный метод. Позволяет разрешать конфликтные ситуации, когда более одного дескриптора из исходного изображения выбрали себе в пару один и тот же дескриптор из базы данных. Выбирается пара с наиболее похожими гистограммами окрестностей ключевых точек.

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

Рисунок 3: Схема идентификации на основе алгоритма SURF

Сравнение алгоритмов идентификации лиц

В этом разделе анализируется эффективность использования предложенной схемы идентификации лиц на основе алгоритма SURF (в Таблицах 1 и 2 схема обозначена как S_our) путем сравнения его показателей с аналогичными показателями для алгоритмов S_orig, EigenFaces и FisherFaces. Под S_orig подразумевается схема идентификации, использующая оригинальный алгоритм SURF для получения ключевых точек и их дескрипторов и Евклидову метрику для сопоставления этих дескрипторов. Первым показателем является вероятность события, при котором человек с видеоролика будет верно идентифицирован. Вторым показателем является вероятность события, при котором человек с видеоролика не будет верно идентифицирован. Стоит отметить, что в сумме оба показателя не дают единичную вероятность.

Для сравнения использовались два тестовых набора: случай естественного и искусственного освещения. База данных в количестве девяти изображений лиц делалась при естественном освещении. В качестве тестового набора были использованы 9 видеозаписей, снятых при естественном освещении и 3 видеозаписи, снятых при искусственном освещении. Каждая видеозапись содержит одну персону. Все алгоритмы идентификации принимали на вход одинаковый набор данных. Результаты работы алгоритмов на тестовых множествах с естественным и искусственным освещением представлены в Таблицах 1 и 2 соответственно.

	Вероятность верной идентификации	Вероятность ложной идентификации
№	S_our	S_orig	EigenFaces	FisherFaces	S_our	S_orig	EigenFaces	FisherFaces
1	0,94	0,78	0,36	0,53	0,03	0,08	0,33	0,36
2	0,89	0,67	0,00	0,00	0,04	0,13	0,56	0,82
3	1,00	0,87	0,69	0,65	0,00	0,07	0,31	0,18
4	0,97	0,97	0,77	0,55	0,03	0,02	0,14	0,30
5	1,00	0,92	0,94	0,78	0,00	0,08	0,06	0,14
6	1,00	1,00	0,97	0,96	0,00	0,00	0,00	0,01
7	0,71	0,10	0,24	0,71	0,14	0,24	0,38	0,24
8	1,00	1,00	0,97	0,56	0,00	0,00	0,03	0,44
9	1,00	0,21	0,00	0,00	0,00	0,43	0,93	0,93

Таблица 1: Результаты алгоритмов идентификации лиц на тестовом множестве с естественным освещением

	Вероятность верной идентификации	Вероятность ложной идентификации
№	S_our	S_orig	EigenFaces	FisherFaces	S_our	S_orig	EigenFaces	FisherFaces
1	0,34	0,34	0,02	0,15	0,34	0,24	0,55	0,45
2	0,88	0,78	0,00	0,00	0,04	0,10	0,92	0,94
3	0,84	0,47	0,00	0,00	0,11	0,21	1,00	1,00

Таблица 2: Результаты алгоритмов идентификации лиц на тестовом множестве с искусственным освещением

Таблицы показывают, что предложенный способ идентификации на основе метода SURF (S_our) показал хорошие результаты. Только на видеоролике №1 при искусственном освещении не удалось верно идентифицировать человека.

Заключение

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

Литература

1.  Herbert Bay, Andreas Ess, Tinne Tuytelaars, and Luc Van Gool Speeded-Up Robust Features (SURF), 2008.

2.  Matthew Turk and Alex Pentland Eigenfaces for Recognition, 1991.

3.  Peter N. Belhumeur, Joao P. Hespanha, and David J. Kriegman Eigenfaces vs. Fisherfaces: Recognition Using Class Specific Linear Projection, 1997.