Построение классификаторов для распознавания лиц на основе показателей сопряженности

ПОСТРОЕНИЕ КЛАССИФИКАТОРОВ ДЛЯ РАСПОЗНАВАНИЯ ЛИЦ НА ОСНОВЕ ПОКАЗАТЕЛЕЙ СОПРЯЖЕННОСТИ

Н.Е. Козин, В.А. Фурсов

Институт систем обработки изображений РАН Самарский государственный аэрокосмический университет имени академика С.П. Королева

Аннотация

Одной из наиболее широко используемых техник распознавания изображений лиц является метод главных компонент (Principal Component Analysis - PCA), также иногда называемый методом собственных лиц (Eigenfaces). Идея метода заключается в разложении векторов изображений по системе собственных векторов, соответствующих наибольшим собственным значениям. В работе рассматривается использование в качестве меры близости различных показателей сопряженности с подпространством, натянутым на обучающие векторы из распознаваемого класса. Показана эффективность использования данного критерия при наличии малого числа обучающих примеров. Приведены результаты экспериментов для стандартной ORL-базы данных лиц.

Введение

Задача распознавания лиц в последние годы стала одной из самых популярных [1]. Объясняется это, с одной стороны, возрастанием практического интереса к созданию распределенных систем видеоконтроля и видеонаблюдения. С другой стороны, интерес инициируется сложностью задачи, что делает ее прекрасным полигоном для проверки новых подходов и идей.

Наиболее широко для распознавания лиц в настоящее время применяются: метод главных компонент и метод сравнения образца и претендента [3], заключающийся в вычислении коэффициента корреляции. Обычно принятие решения осуществляется по одной реализации. В этом случае коэффициент корреляции имеет смысл сопряженности векторов, соответствующих сравниваемым изображениям.

В работах [4, 5] рассматривалось применение трех типов показателей сопряженности для разбиения обучающей выборки на классы. Там же приводился пример, иллюстрирующий эффективность подхода для решения задачи распознавания графических символов на изображениях.

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

В настоящей работе более подробно, чем прежде [4, 5], обсуждается связь между различными показателями сопряженности. Даются рекомендации по их применению при различных размерностях векторов признаков и обучающих выборок. Приводится пример обучения и классификации лиц из базы ОКЬ.

1. Определение и связь показателей сопряженности

В работах [4, 5] рассматривались следующие три типа показателей сопряженности.

1. Показатель парной сопряженности:

где х„ х. - N х1-векторы, компонентами которых являются описания сравниваемых изображений в пространстве признаков.

2. Показатель сопряженности с подпространством, натянутым на векторы признаков объектов из заданного класса:

R,k =

xT X [ XT X k ]-1 XT x

T

X; , X,

Здесь х 1 - N х1-вектор, описывающий изображение, предъявленное для установления принадлежности к некоторому (в данном случае . -му) классу, а X. - N х М -матрица, составленная из векторов признаков объектов, принадлежащих . -му классу.

3. Показатель сопряженности с нуль-пространством того же пространства:

ХТ Т Тт х

. = Т ,

где T0k - матрица, составленная из N - M собственных векторов, соответствующих нулевым собственным значениям N х N -матрицы XkXTt, а Xk -N х M - матрица, составленная из векторов признаков объектов, принадлежащих k -му классу.

Нетрудно заметить, что показатель парной сопряженности (1) является частным случаем показателя сопряженности с подпространством векторов из k -го класса, если этот класс состоит из единственного вектора xk, т.е. матрица Xk имеет размерность N х 1 .

Между показателями R, k, S,k также существует связь:

R,k = 1 - S,,k,

Покажем это. Для этого нам понадобится следующая лемма:

Лемма. Пусть X - N х M -матрица: N > M и Rank(X) = M , а x - N х 1 -вектор, тогда

т\ =

En - Xk [xkXk ] = T0T0

где Т0 - N х (N - М) - матрица, составленная из собственных векторов, соответствующих нулевым собственным значениям N х N - матрицы XXT.

Равенство (5) доказывается с использованием свойств ТТX = 0 (хТ То = 0), ТТ То = Е^м путем

умножения обеих частей слева на Т0Т и справа на Т0. Теперь, в соответствии с (2), запишем:

О м = х, [ хТ X, ]-1 X

хТ X,

1 - Я, =

[X X, Г

X; х,.

Т

х,. х,.

Т

х,. х,.

ЕN - X, [X,X, ]-1 X;

Т

х,. х,.

Откуда, с учетом (5), следует, что 1 - Я,, = Б,,. Ясно что Я, =1 - Б.,.

Таким образом, показатели (1)-(3), при заданных

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

2. Правила принятия решений

Для каждого класса объектов (в данном случае одного или нескольких изображений одного лица) формируются либо N х 1 -вектор х,, либо N х М -матрица X,, соответственно. Каждый вектор-столбец в X, (либо вектор х,) соответствует одному предварительно обработанному изображению лица. Предварительная обработка изображения заключается в локализации (выделении) лица, нормализации гистограммы яркости и приведении к заданному масштабу (размерности векторов). Компонентами векторов могут быть не все, а лишь отобранные каким-либо образом наиболее информативные отсчеты изображения.

Каждый класс может быть разбит на подклассы так, как описано в работе [5]. При этом каждому классу будет соответствовать несколько векторов х, , и/или матриц X, , где ] - номер подкласса.

Для принятия решения о принадлежности к , -му классу в данном случае осуществляется объединение результатов проверки принадлежности к каждому подклассу, например, так, как описано в работах [3, 4]. Поскольку проверка принадлежности к классу и подклассу в данном случае осуществляется по одинаковым правилам, далее для простоты мы будем говорить лишь об определении принадлежности к классу.

Предположим, что для каждого (, -го) класса в соответствии с соотношениями (2)-(3) сформирована одна из следующих ^^матриц О,* :

Q= Т ТТ

Тогда правило принятия решения с учетом связи (4) показателей сопряженности Я и 8 можно сформулировать в следующем виде: вектор х, принадлежит т -му классу:

х,0,, я х

если Ят = тахЯ,, где Я, = - , Т .

™

либо Бт = т1п Б,, где Б, =

(хТ х,) .

В случае, когда используется показатель парной

2

сопряженности г,, также можно вычислить матрицу

,Я =( х, хТ )( хТ х, ) 1

и применить условие (8). Однако в данном случае, как с точки зрения экономии памяти, так и уменьшения вычислительных затрат, предпочтительнее воспользоваться непосредственно соотношением (1).

Для реализации описанных правил принятия решений для каждого класса с использованием обучающей выборки изображений лиц заранее должна быть рассчитана и храниться в памяти одна из N х N - матриц О, *. Из соотношений (6), (7) видно, что матрицу О, Я выгоднее использовать в случае, когда число обучающих векторов М сравнительно невелико. Если же наоборот М велико настолько, что размерность нуль-пространства N - М оказывается сравнительно (с размерностью N) малой, целесообразно использовать матрицу О, Б .

В случае использования показателя парной сопряженности (1) вероятность распознавания, как правило, выше, если он вычисляется с каждым элементом каждого класса (а возможно и подкласса). При этом решение о принадлежности вектора х, , -му классу принимается, если наиболее «близкий» в смысле показателя (1) вектор х, также из этого класса.

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

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

3. Примеры и результаты

Экспериментальное исследование классификаторов, построенных на основе описанных выше показателей сопряженности, проводилось с использованием стандартной базы данных ОКЬ. Данная база содержит изображения лиц сорока человек. Для каждого человека имеется 10 различных ракурсов с произвольной мимикой. Таким образом, база данных содержит 400 изображений. На рис. 1 приведены примеры изображений пяти лиц из базы данных ОЯЬ.

Размер изображений оригинальной базы данных ОКЬ равен 112x96. Однако в экспериментах, с целью снижения вычислительных затрат, использовались изображения более малого размера 80*70. Таким образом, каждое изображение представлялось в виде вектора х, размерностью 5600*1.

Рис. 1. Примеры изображений разных лиц (классов) из базы ORL

Из различных наборов этих векторов составлялись матрицы Хк, для каждого класса. С целью выявления зависимости вероятности распознавания от числа векторов в классе их число в матрице варьировалось от одного до пяти. На рис. 2 в качестве примера приведены пять изображений одного лица (класса), по которым была сформирована одна из матриц Хк размерности 5600*5.

Рис. 2. Пример изображений, относящихся к одному классу

Для каждого класса с использованием матриц Хк по соотношениям (6), (7) формировались матрицы Qkдля распознавания. Решение о принадлежности некоторого вектора из контрольной выборки т-му классу принималось по правилам (8), (9). В контрольную выборку были включены по пять изображений каждого лица, т.е. всего 200 лиц. Подчеркнем, что эти лица не использовались для формирования матриц Qk,.

На рис. 3а и б представлены полученные в эксперименте зависимости вероятности распознавания от числа изображений, в классе (векторов в матрице Хк) для классификатора, построенного на критериях (1)-(3).

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

представляющих класс, качество распознавания также практически одинаково.

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

На рис. 4 приведен пример собственных векторов и соответствующих им собственных значений, вычисленных для указанного training set.

На рис 5а, б приведен пример восстановления изображений лица по 40 главным компонентам, а на рис. 5в - собственное лицо, соответствующее собственному значению X = 0,228 . Приведенные примеры иллюстрируют, что переход к вектору главных компонент позволяет сохранить существенные черты лица. В то же время собственное лицо, соответствующее малому собственному значению (X = 0,228), по существу является помехой.

а)

б)

Рис. 3. Зависимость вероятности распознавания от объема обучающей выборки при использовании показателей а) парной сопряженности; б) сопряженности с пространством векторов-признаков из класса

1=8,745 1=10,818 1=16,859 1=18,484 1=23,283

Рис. 4. Собственные лица и соответствующие им собственные значения

Для оценки качества восстановления изображений с использованием главных компонент проводился эксперимент, в котором их число варьировалось от 40 до 200 векторов. На рис. 6 показана зависимость средней ошибки восстановления от числа собственных векторов.

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

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

стояние до одного из векторов данного класса оказывалось минимально.

2. Классификатор, использующий в качестве критерия близости показатель сопряженности Я (или 8 ) по соотношениям (2), (3). Решение о принадлежности к классу принималось по правилу, описанному в пункте 3.

а) б) в)

Рис. 5. Собственное лицо с малым собственным значением (а, б), (в) исходное изображение и его проекция на пространство из 40 собственных лиц 0,14

0,12 0,10 0,08 0,06 0,04

10 50 90 130 1 70 210 Рис. 6. Зависимости ошибки восстановления от числа собственных векторов

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

Евклидово расстояние  Сопряженность

Рис. 7. Зависимость процента распознавания от числа обучающих векторов в классе

Заключение

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

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

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

столбцов матрицы X* выгоднее использовать матрицу Q*- (7).

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

Благодарности Работа выполнена при поддержке Министерства образования и науки РФ, правительства Самарской области и Американского фонда гражданских исследований и развития (CRDF Project SA-014-02) в рамках российско-американской программы «Фундаментальные исследования и высшее образование» (BRHE), а также при поддержке гранта Президента РФ № НШ-1007.2003.01 и грантов РФФИ № 05-0108043 и № 04-07-90149.

Литература

1. Zhao W., Chellappa R., Rosenfeld A., Phillips P.J. Face Recognition // A Literature Survey, ACM Computing Surveys, 2003. Р. 399-458.

2. Turk M.A., Pentland A.P. Face Recognition Using Eigen-faces, Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, Maui, Hawaii, USA, 3-6 June 1991. Р. 586-591.

3. Belhumeur P.N., Hespanha J.P., Kriegman D.J. Eigenfaces vs. Fisherfaces: Recognition using Class Specific Linear Projection, Proc. of the 4th European Conference on Computer Vision, ECCV'96, 15-18 April 1996, Cambridge, UK, Р. 45-58.

4. Fursov V.A., Kozin N.E. Stage-wise learning of radial neural networks // Proceedings of The 12th ISPE International Conference on Concurrent Engineering: Research and Applications, Focus Symposium Recursive Dynamics and Iterated Mappings in Service Modeling and Design, Ft. Worth/Dallas, USA, 25 - 29 July, pp. 391-396.

5. Fursov V.A., Kozin N.E. Algorithm for parallel learning of radial neural networks, Proceedings of The IASTED International Conference on Automation, Control and Applications (ACIT-ACA 2005), Novosibirsk, June 20-24, Russia. 2005. Р. 481-485.

6. Turk A., Pentland A.P. Face Recognition Using Eigen-faces // Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 3-6 June 1991, Maui, Hawaii, USA. Р. 586-591.

7. Berger M., Sobolewski M. SILENUS // A Federated Service-oriented Approach to Distributed File Systems. Р. 89-96.