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

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

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

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

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

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

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

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

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

R

- i , k

_ x T X k [ X ^T T X k ]" X T x ,

T x ^T _i , x _i

.

Здесь x j - N x 1 -вектор, описывающий изобра-

жение, предъявленное для установления принадлежности к некоторому (в данном случае k -му) классу, а X _k - N x M -матрица, составленная из векторов при-

знаков объектов, принадлежащих k -му классу.

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

TT ^x i 0, k 0, k ^x i S i , k = J , x ^T _i , x _i

где T _{0 k} - матрица, составленная из N - M собст-

венных векторов, соответствующих нулевым собственным значениям N x N -матрицы X _k X T , а X _k -

N x M - матрица, составленная из векторов признаков объектов, принадлежащих k -му классу.

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

Между показателями R_{i , k} , S_{i . k} также существует

связь:

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

В работах [4, 5] рассматривались следующие три

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

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

^r i , ² k

( ^x T x k ) 2

R i , k _ 1 - S , k , ( S , k _ 1 - R i , k )                     (4)

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

Лемма . Пусть X - N x M -матрица: N >  M и

Rank ( X ) _ M , а x - N x 1 -вектор, тогда

( ^x T x i )( ^x T ^x k ) ’

En — Xk [XTXk ] = ToTT                    (5)

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

Равенство (5) доказывается с использованием свойств T 0 T X = 0 ( X T Т _о = 0 ) , T ₀ ^T Т _о = E N - _M путем умножения обеих частей слева на T ₀ ^T и справа на T ₀ .

Теперь, в соответствии с (2), запишем:

1 — R i , к

x ^T X i - x T X к [ X T X к Г* X T X i x ^T _i x _i              x ^T _i x _i

= x T [ e N - X к [ X T X к Г* X T ] X i

Q к , _К = X к [ X T X к ] - 1 X T ,                    (6)

Q к , S = Т о, к T T к .                                  (7)

Тогда правило принятия решения с учетом связи (4) показателей сопряженности R и S можно сформулировать в следующем виде: вектор x _i принадлежит m -му классу:

xQ x если Rm = max Rk, где Rk =     •   ,        (8)

^{v к}                       ( ^x i ^x i )

xiQk Sxi либо Sm = min Sk , где Sk = -ТТТ .       (9)

^v m                  ( x T x i )

В случае, когда используется показатель парной сопряженности r_{i ,} ² _k , также можно вычислить матрицу

^Q к , R = ( ^x к ^{x T} )( ^{x T x} к ) ¹

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

Для реализации описанных правил принятия решений для каждого класса с использованием обучающей выборки изображений лиц заранее должна быть рассчитана и храниться в памяти одна из N х N - матриц Q _к * . Из соотношений (6), (7) видно, что матрицу Q _{k , R} выгоднее использовать в случае, когда число обучающих векторов M сравнительно невелико. Если же наоборот M велико настолько, что размерность нуль-пространства N - M оказывается сравнительно (с размерностью N ) малой, целесообразно использовать матрицу Q _{k , S} .

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

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

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

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

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

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

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

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

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

Для каждого класса с использованием матриц X _k по соотношениям (6), (7) формировались матрицы Q _{k ,*} для распознавания. Решение о принадлежности некоторого вектора из контрольной выборки m –му классу принималось по правилам (8), (9). В контрольную выборку были включены по пять изображений каждого лица, т.е. всего 200 лиц. Подчеркнем, что эти лица не использовались для формирования матриц Q _{k ,*} .

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

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

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

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

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

• а)

• б)

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

б) сопряженности с пространством векторов-признаков из класса

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

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

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

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

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

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

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

• надлежности к классу принималось по правилу, описанному в пункте 3.

а)                   б)                   в)

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

Рис. 6. Зависимости ошибки восстановления от числа собственных векторов

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

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

Заключение

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

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

Эксперименты подтвердили почти одинаковую эффективность всех показателей. Поэтому целесообразность применения конкретного показателя сопряженности в каждом случае определяется соотношением между размерностями N и M . В частности, если размерность N векторов признаков сравнительно невелика по сравнению с числом обучающих примеров M , т.е. размерность нуль-пространства меньше размерности пространства столбцов матрицы X _k выгоднее использовать матрицу Q _{k , S} – (7).

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

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