ДАЛЬНЕВОСТОЧНЫЙ ГОСУДАРСТВЕННЫЙ

УНИВЕРСИТЕТ

ИНСТИТУТ ФИЗИКИ И ИНФОРМАЦИОННЫХ

ТЕХНОЛОГИЙ

Кафедра информационной безопасности

Распознавание человека по изображению лица

Курсовая работа

студента 147 группы Парахина С.Ю.

Научный руководитель:

доцент Гончаров С.М.

Срок сдачи работы:

Подпись научного руководителя:

Владивосток 2007

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ

ГЛАВА 1. ОБНАРУЖЕНИЕ И ЛОКАЛИЗАЦИЯ ЛИЦА НА ИЗОБРАЖЕНИИ

1.1 МЕТОДЫ ПЕРВОЙ КАТЕГОРИИ – ЭМПИРИЧЕСКОЕ РАСПОЗНАВАНИЕ................ 1.1.1 Обнаружение элементов и особенностей (features), которые характерны для изображения лица.

1.1.2 Анализ обнаруженных особенностей, вынесение решения о количестве и расположении лиц.

1.2 МЕТОДЫ ВТОРОЙ КАТЕГОРИИ, МОДЕЛИРОВАНИЕ ИЗОБРАЖЕНИЯ ЛИЦА.......

1.3 ДОСТОИНСТВА И НЕДОСТАТКИ МЕТОДОВ ПЕРВОЙ И ВТОРОЙ КАТЕГОРИИ....

ГЛАВА 2. РАСПОЗНАВАНИЕ ЧЕЛОВЕКА ПО ИЗОБРАЖЕНИЮ ЛИЦА И

НЕЙРОСЕТЕВЫЕ МЕТОДЫ

2.1 МЕТОД ГЛАВНЫХ КОМПОНЕНТ.

2.2. ЛИНЕЙНЫЙ ДИСКРИМИНАНТНЫЙ АНАЛИЗ.

2.3 СИНТЕЗ ОБЪЕКТОВ ЛИНЕЙНЫХ КЛАССОВ.

2.4 ГИБКИЕ КОНТУРНЫЕ МОДЕЛИ ЛИЦА

2.5 СРАВНЕНИЕ ЭЛАСТИЧНЫХ ГРАФОВ

2.6 МЕТОДЫ, ОСНОВАННЫЕ НА ГЕОМЕТРИЧЕСКИХ ХАРАКТЕРИСТИКАХ ЛИЦА..

2.7 СРАВНЕНИЕ ЭТАЛОНОВ

2.8 ОПТИЧЕСКИЙ ПОТОК.

2.9 СКРЫТЫЕ МАРКОВСКИЕ МОДЕЛИ

ЗАКЛЮЧЕНИЕ

СПИСОК ЛИТЕРАТУРЫ

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

Итак,, необходимо научить компьютер идентифицировать личность человека. Какую технологию для этого выбрать? Существует большое разнообразие методов идентификации, причем многие из них получили широкое коммерческое применение и используются уже немало лет. На сегодняшний день в основе наиболее распространенных технологий верификации и идентификации лежит использование паролей и персональных идентификаторов (personal identification number – PIN) или документов типа паспорта, водительских прав.

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

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

Интерфейс типа “остановись и продекларируй себя” нужен приложениям с высокими требованиями к безопасности (некоторая задержка заставит пользователя осознать важность проблемы). Однако для магазина, в котором узнают своих постоянных клиентов, для информационного киоска, который вас “помнит”, или здания, которое “знает”, кто в нем живет, нужно совсем другое. Для интеллектуальных сред нового поколения лучше всего подходят технологии распознавания лиц и голоса. Они ненавязчивы (распознавание происходит на расстоянии, не задерживая и не отвлекая человека), они, как правило, пассивны (не требуют специального уровня освещенности), они не ограничивают пользователя в свободе перемещений, к тому же потребляют мало энергии и недороги. Но самое важное, по-видимому, то, что люди обычно узнают друг друга по лицам и голосам, значит, не будут испытывать неудобств с системой, основанной на аналогичных способах распознавания. Также новый стимул разработке систем распознавания человека по лицу дало обострение ситуации с международным терроризмом.

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

Глава 1. Обнаружение и локализация лица на изображении Задача обнаружения лица на изображении (face detection) часто является “первым шагом”, предобработкой в процессе решения задачи “более высокого уровня” (например узнавания лица, распознавание выражения лица). Однако и сама информация о присутствии и, возможно, количестве лиц на изображении или в видеопотоке может быть полезна для таких приложений, как охранные системы и содержательная индексация базы данных изображений или видеофрагментов.

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

В машинном зрении часто встречаются две модификации задачи обнаружения лица – локализация лица (face localization) и отслеживание перемещения лица (face tracking). Локализация лица является упрощенным вариантом задачи обнаружения, так как опирается на знание о том, что на изображении присутствует одно и только одно лица. Задачу отслеживания перемещения лица в видеопотоке можно сформулировать как задачу локализации лица на текущем кадре, опираясь на информацию о его положении на предыдущих кадрах.

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

• Сильно варьирующийся внешний вид лица у разных людей;

• Даже относительно небольшое изменение ориентации лица относительно камеры влечет за собой серьезное изменение изображения лица;

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

• Изменение выражения лица может сильно сказаться на том, как лицо выглядит на изображении;

• Часть лица может быть невидима (закрыта другими предметами) на • Условия съемки (освещение, цветовой баланс камеры, искажения изображения, привносимые оптикой системы, качество изображения) в значительной степени влияют на получающееся изображения лица;

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

1.1 Методы первой категории – Эмпирическое распознавание.

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

Среди методов, делающих такую попытку, можно выделить два направления:

методы распознавания “сверху-вниз” основанные на знаниях и методы распознавания “снизу-вверх” основанное на особенностях.

Распознавание “сверху-вниз” означает построение некоторого набора правил, которым должен отвечать фрагмент изображения, для того чтобы быть признанным человеческим лицом. Этот набор привил является попыткой формализовать эмпирические знания о том, как именно выглядит лицо на изображениях и чем руководствуется человек при принятии решения лицо он видит или нет. Довольно легко построить набор простых и очевидных (как кажется) свойств изображения лица, например: лицо обычно симметрично, черты лица (глаза, носа, рта) отличаются от кожи по яркости (обычно им также соответствует области резкого изменения яркости), черты лица расположены вполне определенным образом. Опираясь на перечисленные свойства, можно построить алгоритм, проверяющий их наличие на фрагменте изображения. К этому же семейству методик можно также отнести распознавание с помощью шаблонов, заданных разработчиком (predefined template matching). Шаблоны задают некий стандартный образ изображения лица, например, путем описания свойств отдельных областей лица и их возможного взаимного расположения. Обнаружение лица с помощью шаблона заключается в проверке каждой из областей изображения на соответствие заданному шаблону.

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

Распознавание “снизу-вверх” использует инвариантные свойства (invariant features) изображений лиц, опираясь на предложение, что раз человек может без усилий распознать лицо на изображении независимо от его ориентации, условий освещения и индивидуальных особенностей, то должны существовать некоторые признаки присутствия лиц на изображении, инвариантные относительно условий съемки. Алгоритм работы методов распознавания “снизу-вверх” может быть кратко описан следующим образом:

1. Обнаружение элементов и особенностей (features), которые характерны для изображения лица;

2. Анализ обнаруженных особенностей, вынесение решения о количестве и расположении лиц;

1.1.1 Обнаружение элементов и особенностей (features), которые характерны Края (edges) – резкие переходы яркости. Края обычно соответствуют границам объектов на изображении. Используя этот факт и то, что лицо представляет собой эллипс определенных пропорций (близких для разных людей) (изображения, на котором обозначены резкие переходы яркости) и характерной формы лица. Резкие переходы яркости также часто соответствуют чертам лица (facial features) – границам глаз, бровей, рта, носа. Это свойство также используется в ряде работ, которые рассматривают края на изображении как признаки потенциального присутствия лица.

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

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

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

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

1.2 Методы второй категории, моделирование изображения лица.

Второе семейство методов подходит проблеме с другой стороны, и, не пытаясь в явном виде формализовать процессы, происходящие в человеческом мозге, стараются выявить закономерности и свойства изображения лица неявно, применяя методы математической статистики и машинного обучения. Методы этой категории опираются на инструментарий распознавания образов, рассматривая задачу обнаружения лица, как частный случай задачи распознавания. Изображению (или его фрагменту) ставится в соответствие некоторым образом вычисленный вектор признаков, который используется для классификации изображений на два класса – лицо/не лицо. Самый распространенный способ получения вектора признаков это использование самого изображения: каждый пиксель становится компонентом вектора, превращая черно-белое изображение nm в вектор пространства Rnm. Недостатком такого представления является чрезвычайно высокая размерность пространства признаков. Достоинство заключается в том, что используя все изображение целиком вместо вычисленных на его основе характеристик, из всей процедуры построения классификатора (включая выделение устойчивых признаков для распознавания) полностью исключается участие человека, что потенциально снижает вероятность ошибки построения неправильной модели изображения лица вследствие неверных решений и заблуждений разработчика.

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

1.3 Достоинства и недостатки методов первой и второй категории.

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

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

Можно перечислить следующие проблемы, общие для методов второй категории:

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

2. Неявный способ определения признаков для распознавания лица таит в себе потенциальную опасность: классификатор, обладающий недостаточно репрезентативным набором изображений лиц, теоретически может выделить вторичные или ложные признаки в качестве важных. Одно из следствий – тренировочном наборе. В ряде случаев применяется дополнительная предобработка изображения для компенсации влияния освещения.

3. Высокая вычислительная сложность. Во-первых, сами классификаторы часто включают в себя большое количество достаточно сложных вычислений;

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

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

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

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

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

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

• Предполагаемое разнообразие лиц: ограниченный набор людей, ограничения на возможный тип (раса, присутствие растительности на лице, очков и т.д.), отсутствие ограничений;

• Ориентация лиц на изображении: строго вертикальная (или наклон под известным углом), в определенных границах вблизи известного угла наклона, любая;

• Цветное или черно-белое изображение;

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

• Предполагаемое количество лиц, присутствующих на изображении:

известно, примерно известно, неизвестно;

• Условия освещения; фиксированные известные, приблизительно известные, • Фон: фиксированный, контрастный однотонный, слабоконтрастный зашумленный, неизвестный;

• Что важнее – не пропустить ни одного лица или минимизировать количество случаев ложного обнаружения?

Глава 2. РАСПОЗНАВАНИЕ ЧЕЛОВЕКА ПО

ИЗОБРАЖЕНИЮ ЛИЦА И НЕЙРОСЕТЕВЫЕ МЕТОДЫ

При всём многообразии различных алгоритмов и методов распознавания изображений, типичный метод распознавания состоит из трёх компонент, рис. 1:

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

2. выделение ключевых характеристик (например берётся первые n главных компонент или коэффициентов дискретного косинусного преобразования);

3. механизм классификации (моделирования): кластерная модель, метрика, нейронная сеть и т.п.

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

Рис. 1. Структура методов распознавания изображений Метод главных компонент (Principal Component Analysis, PCA) применяется для сжатия информации без существенных потерь информативности. Он состоит в линейном ортогональном преобразовании входного вектора X размерности N в выходной вектор Y размерности M, N. При этом компоненты вектора Y являются неизменной. Матрица X состоит из всех примеров изображений обучающего набора. Решив уравнение А = Ф Т Ф, получаем матрицу собственных векторов Ф, где – ковариационная матрица для X, а А - диагональная матрица собственных чисел. Выбрав из Ф подматрицу ФM, соответствующую M наибольшим собственным числам, получим, что преобразование y = ФM X, где X =X X - нормализованный вектор с нулевым математическим ожиданием, существенные изменения X.

Выбор первых M главных компонент разбивает векторное пространство на главное (собственное) пространство F = {Фi }iM1, содержащее главные компоненты, и его ортогональное дополнение F = {Фi }iN M +1 (рис. 2).

Рис. 2. а) полное пространство, разбитое на собственное пространство F и его ортогональное дополнение F. DIFS – distance in feature space, расстояние в собственном пространстве, DFFS – distance from feature space, расстояние до проекции в собственном пространстве; б) типичный спектр собственных чисел и его разбиение на два ортогональных подпространства Применение для задачи распознавания человека по изображению лица имеет следующий вид. Входные вектора представляют собой отцентрированные и приведённые к единому масштабу изображения лиц. Собственные вектора, вычисленные для всего набора изображений лиц, называются собственными лицами (eigenfaces). Метод главных компонент в применении к изображениям лиц так же называют методом собственных лиц. Собственные лица имеют полезное свойство, заключающееся в том, что изображение, соответствующее каждому такому вектору имеет лицеподобную форму, рис. 3. С помощью вычисленных коэффициентов, называемых главными компонентами. Сумма главных компонент, умноженных на соответствующие собственные вектора, является реконструкцией изображения, рис. 4.

Рис. 3. Пример изображений собственных векторов (собственные лица) Рис. 4. а) выровненное изображение лица, б) реконструкция по 85-и главным компонентам, Для каждого изображения лица вычисляются его главные компоненты.

Обычно берётся от 5 до 200 главных компонент. Остальные компоненты кодируют мелкие различия между лицами и шум. Процесс распознавания заключается в сравнении главных компонент неизвестного изображения с компонентами всех остальных изображений. Для этого обычно применяют какую-либо метрику (простейший случай – Евклидово расстояние). При этом предполагается что изображения лиц, соответствующих одному человеку, сгруппированы в кластеры в собственном пространстве. Из базы данных (или тренировочного набора) выбираются изображения-кандидаты, имеющие наименьшее расстояние от входного (неизвестного) изображения.

Дальнейшее совершенствование заключалось в использовании метрики Махаланобиса и Гауссовского распределения для оценки близости изображений [PCA]. Для учёта различных ракурсов в этой же работе использовалось многомодальное распределение изображений в собственном пространстве.

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

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

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

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

Аналогичные трудности имеют место при изменении условий освещения.

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

Вычисление набора собственных векторов отличается высокой трудоёмкостью. Один из способов – это свёртка изображений по строкам и столбцам, и дальнейшая работа с полученными результатами [2D-KLT, PRIP2002].

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

Основное преимущество применения анализа главных компонент – это хранение и поиск изображений в больших базах данных, реконструкция изображений [PCA].

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

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

2.2. Линейный дискриминантный анализ.

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

Линейный дискриминантный анализ (линейный дискриминант Фишера [Fisher, Face23], Linear Discriminant Analysis, LDA), который описывается ниже, выбирают проекцию пространства изображений на пространство признаков таким образом, чтобы минимизировать внутриклассовое и максимизировать межклассовое расстояние в пространстве признаков, рис 5. В этих методах предполагается что классы линейно разделимы.

Рис. 5. Пример проекций в пространство характеристик для двух классов с помощью главных компонент (PCA) и линейного дисриминанта Фишера (FLD).

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

Матрица W для проецирования пространства изображения на пространство признаков выбирается из следующего условия:

где SB – матрица межклассовой дисперсии, SW – матрица внутриклассовой дисперсии.

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

Поскольку работа непосредственно с матрицей SW R x*x затруднительна изза её размерности, в [Fisher] использовано предварительное уменьшение размерности с помощью метода главных компонент, и затем вычисления производятся в пространстве меньшей размерности:

где Wpca – матрица для проецирования в пространство меньшей размерности (пространство главных компонент). В указанной работе такой метод был назван лицами Фишера (Fisherfaces). Так же как и собственные вектора, изображения базисных дискриминантных векторов имеют лицеподобную форму.

В работе [Fisher] тренировочный набор содержал лица при нескольких базовых условиях освещённости, на основе которых при помощи линейных комбинаций можно получить любые другие условия освещённости. Отмечена высокая точность распознавания (около 96%) для широкого диапазона условий освещённости, различных выражений лица и наличия или отсутствия очков. Была отмечена низкая распознающая способность метода собственных лиц при аналогичных условиях. Причём применение метода собственных лиц, в котором главные компоненты отвечающие за освещённость не учитывались, всё равно давало намного худший результат, чем дискриминант Фишера.

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

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

Вышеописанный метод основывается на предположении о линейной разделимости классов в пространстве изображений. В общем случае такое предположение несправедливо.

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

Данный метод [Linear] позволяет синтезировать новые изображения объекта (и в частности, изображения лица) для разных ракурсов. Имеется тренировочный набор изображений лиц и только одно изображение нового объекта в определённом ракурсе. Тренировочный набор состоит из изображений объектов того же класса (класс лиц в данном случае), что и новый объект и включает в себя изображения различных лиц, при чём для каждого лица имеются его изображения в широком диапазоне ракурсов. Для нового объекта, имеющего изображение XA в ракурсе A, осуществляется линейное разложение на изображения объектов из тренировочного набора в том же ракурсе, с вычислением коэффициентов i :

q – количество объектов в тренировочном наборе. Синтез изображения XB где в новом ракурсе B для нового объекта осуществляется сложением изображений из тренировочного набора в ракурсе B с теми же коэффициентами:

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

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

Данный метод является перспективным для синтеза изображений в новых ракурсах без привлечения сложных трёхмерных моделей, однако вопрос о качестве и количестве примеров в тренировочном наборе остаётся открытым [Linear].

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

В работе [Flex] (Flexible Models) ключевые точки размещались вручную, на наборе тренировочных изображений. Затем извлекалась информация об интенсивности пикселей, лежащих на линии, перпендикулярной контуру для каждой точки контура. При поиске контуров нового лица использовался метод симуляции отжига с целевой функцией из двух составляющих. Первая из них максимизировалась при соответствии интенсивностей пикселей, извлечённых на перпендикулярной контуру линии аналогичным пикселям из тренировочной выборки. Вторая – при совпадении контура с формой контуров тренировочных примеров. Таким образом, извлекался не просто контур, а контур черт лица. Как должен выглядеть типичный контур черт лица, процедура поиска знала из тренировочных примеров. Для сравнения изображений использовались значения главных компонент, вычисленных на наборе векторов, представляющих собой координаты ключевых точек. В данной работе контурная модель использовалась вместе с полутоновой моделью, совместное их использование повышало точность распознавания.

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

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

В этом методе (Elastic Bunch Graph Matching) [ElGraph] лицо представляется в виде графа, вершины которого расположены на ключевых точках лица, таких как контуры головы, губ, носы и их крайних точках, рис. 6. Каждая грань помечена расстояниями между её вершинами. В каждой такой точке вычисляются коэффициенты Габоровых функций для пяти различных частот и восьми ориентаций. Набор таких коэффициентов {J j } называется джетом (jet). Джеты характеризуют локальные области изображений и служат для двух целей. Во первых, для нахождения точек соответствия в заданной области на двух различных изображениях. Во вторых – для сравнения двух соответствующих областей различных изображений. Каждый коэффициент J j = a j exp(i j ) для точек из одной области различных изображений, характеризуется амплитудой a j, которая медленно меняется с изменением положения точки и фазой j, которая вращается со скоростью, пропорциональной частоте волнового вектора базисного вейвлета.

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

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

Процесс распознавания неизвестного лица состоит в сравнении графа изображения лица G I со всеми остальными графами из набора B при помощи функции подобия:

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

В представленном выше виде метод способен достаточно надёжно распознавать при изменениях ракурса до 22°; при больших углах точность распознавания резко уменьшается, функция подобия оказывается больше чувствительной к ракурсу, чем к межклассовым различиям. Изменения условий освещённости в работе [ElGraph] не производились.

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

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

преобразований джетов для компенсации изменения ракурса [ElWeights].

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

Рис. 7. Эластичная решётка, наложенная на изображение, и её искажение 2.6 Методы, основанные на геометрических характеристиках Один из самых первых методов – это анализ геометрических характеристик лица [Самаль]. Изначально применялся в криминалистике и был там детально разработан. Потом появились компьютерные реализации этого метода. Суть его заключается в выделении набора ключевых точек (или областей) лица и последующем выделении набора признаков. Каждый признак является либо расстоянием между ключевыми точками, либо отношением таких расстояний. В отличие от метода сравнения эластичных графов, здесь расстояния выбираются не как дуги графов. Наборы наиболее информативных признаков выделяются экспериментально [Сам2].

Ключевыми точками могут быть уголки глаз, губ, кончик носа, центр глаза и т.п. [Самаль], рис. 8. В качестве ключевых областей могут быть прямоугольные области, включающие в себя: глаза, нос, рот [Gutta].

Рис. 8. Идентификационные точки и расстояния: а) используемые при криминалистической фотоэкспертизе; б) наиболее часто применяемые при построении автоматизированных систем В процессе распознавания сравниваются признаки неизвестного лица, с признаками, хранящимися в базе.

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

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

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

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

В общем случае этот метод не самый оптимальный, однако для некоторых специфических задач перспективен. К таким задачам можно отнести документный контроль [Сам1, Сам3], когда требуется сравнить изображение лица, полученного в текущий момент с фотографией в документе. При этом других изображений этого человека не имеется, и следовательно механизмы классификации, основанные на анализе тренировочного набора, недоступны.

Сравнение эталонов (Template Matching) [Templ] заключается в выделении областей лица на изображении (рис. 9), и последующем сравнении этих областей для двух различных изображений. Каждая совпавшая область увеличивает меру сходства изображений. Это так же один из исторически первых методов распознавания человека по изображению лица. Для сравнения областей используются простейшие алгоритмы, вроде попиксельного сравнения.

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

Алгоритмы оптического потока используются в основном для анализа движения. Используя два или более последовательных кадра изображения, можно рассчитать двумерное векторное поле, называемое оптическим потоком (Optical Flow), которое отражает актуальное или наиболее вероятное смещение точек изображения от кадра к кадру [OFlow, Хорн].

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

Алгоритм находил наиболее соответствующие блоки. Поиск осуществлялся иерархически, начиная с больших блоков, и затем разбивая их на меньшие блоки.

Таким образом, строилась пирамида соответствия изображений.

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

База данных представляла собой 76 изображений 36-и человек с различиями в ракурсе и выражении лица. Распознавание осуществлялось несколькими способами.

В первом способе блоки 8х8 неизвестного изображения заменялись на наиболее соответствующие блоки сравниваемого изображения (рис. 10, 11). Затем вычислялось Евклидово расстояние между неизвестным и полученным изображением. Было достигнуто 92% точности распознавания. Учитывая то, что в базе находилось только одно изображение нужного человека и по два на всех остальных, это хороший результат.

Рис. 10. Отображение неизвестного изображения на известное, один и тот же человек. Слева направо: неизвестное изображение, изображение из базы данных, неизвестное изображение, в котором блоки заменены блоками из известного изображения.

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

Рис. 12. Искажений решётки изображения при преобразовании одного изображения в другое. Слева – изображения одного человека, справа – разных.

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

экспериментировать с более репрезентативными базами изображений лиц.

Метод анализирует только суммарное искажение между изображениями или только суммарное несоответствие блоков, не касаясь характера этих искажений.

Метод, анализирующий как характер искажения изображений, так и соответствие отдельных блоков, может дать отличный результат. Это подтверждает работа [DCT-HMM1], применяющая псевдодвумерные скрытые Марковские модели.

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

Рис. 13. Схема Марковской модели, пример последовательности наблюдений O и Каждая модель = ( A, B, ), рис. 13, представляет собой набор N состояний S = {S1, S 2,...S N } (на рисунке – вершины графа), между которыми возможны переходы (на рисунке - дуги) [Rabiner]. В каждый момент времени система находится в строго определённом состоянии. В наиболее распространённых Марковских моделях первого порядка полагается, что следующее состояние зависит только от текущего состояния.

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

Набор символов для каждого состояния V = { 1, 2,... M }, количество символов M.

Выход, генерируемый моделью, может быть так же непрерывным. Существуют так же модели, в которых набор символов для всех состояний одинаков. Символ в b j (k ) = P kt | qt = S j. Набор всех таких вероятностей составляет матрицу B = {b j (k )}.

Матрица A = {aij } определяет вероятность перехода из одного состояния в другое состояние: aij = P[qt +1 = S j | qt = S j ], 1 i, j N. Считается, что A не зависит от времени. Если из каждого состояния можно достичь любого другого за один переход, то все aij > 0, и модель называется эргодической.

Так же модель имеет вероятность начальных состояний = i, где Обычно в реальных процессах последовательность состояний является скрытой от наблюдения и остаётся неизвестной, а известен только выход системы, последовательность наблюдаемых символов O = O1O2...OT, где каждое наблюдение Ot – символ из V, и T – число наблюдений в последовательности. Поэтому такие модели называют скрытыми Марковскими моделями (СММ, по английски – Hidden Markov Models, HMM).

Модель = ( A, B, ) с настроенными параметрами может быть использована для генерирования последовательности наблюдений. Для этого случайно, в соответствии с начальными вероятностями выбирается начальное состояние, затем на каждом шаге вероятность B используется для генерации наблюдаемого символа, а вероятность A – для выбора следующего состояния. Вероятность Предполагается, что наблюдения статистически независимы.

В распознавании образов скрытые Марковские модели применяются Распознаваемый образ (речевой сигнал, изображение и т.д.) представляется в виде последовательности наблюдений O. Затем для каждой модели t вычисляется вероятность того, что эта последовательность могла быть сгенерирована именно этой моделью. Модель j, получившая наибольшую вероятность, считается наиболее подходящей, и образ относят к классу j.

В связи с этим появляются несколько вопросов, называемых тремя основными задачами скрытых Марковских моделей [Rabiner].

1. Имея последовательность наблюдений O = O1O2...OT и настроенную модель = ( A, B, ), как оценить вероятность P(O | ) генерации этой моделью данной последовательности наблюдений? Эта задача называется задачей распознавания.

2. Имея последовательность наблюдений O = O1O2...OT и настроенную модель = ( A, B, ), как подобрать последовательность состояний Q = q1q2...qT, чтобы аналитически эта задача неразрешима)? Другими словами это задача объяснения. Она нужна для последующей коррекции параметров модели.

3. Каким образом корректировать параметры модели, для того чтобы максимизировать P(O | ) ? Т.е. как сделать так, чтобы модель больше соответствовала своему классу, одним из образов которого является данная последовательностей). Это задача обучения.

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

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

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

Одна из первых работ, применяющая СММ для распознавания изображений лиц – это диссертация Фердинанда Самарии [Samaria], которой предшествовали работы по распознаванию изображений других видов скрытыми Марковскими моделями. В этой работе распознавание осуществлялось как простейшими одномерными линейными СММ, так и псевдодвумерными. Введение второго измерения позволило повысить точность распознавания с 85% до 95% на базе ORL.

Суть двумерных Марковских моделей заключается в том, что в отличие от изображения и взаимное расположение участков не отдельно по горизонтали или вычислительной сложности применяются псевдодвумерные СММ (Pseudo-2D