Нейросетевые технологии как средства организации обработки изображений (на примере идентификации лица человека)

Размещено на http://www.allbest.ru/

70

Размещено на http://www.allbest.ru/

УЗБЕКСКОЕ АГЕНТСТВО СВЯЗИ И ИНФОРМАТИЗАЦИИ

ТАШКЕНТСКИЙ УНИВЕРСИТЕТ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ

ВЫПУСКНАЯ КВАЛИФИКАЦИОННАЯ РАБОТА

ТЕМА: «НЕЙРОСЕТЕВЫЕ ТЕХНОЛОГИИ КАК СРЕДСТВА ОРГАНИЗАЦИИ ОБРАБОТКИ ИЗОБРАЖЕНИЙ (НА ПРИМЕРЕ ИДЕНТИФИКАЦИИ ЛИЦА ЧЕЛОВЕКА»

Выпускник Платонов Г.Н.

Ташкент - 2011 г.

Аннотация

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

Аннотация

Автор, ушбу битирув малакавий ишида “Нейрон” тўрлари назарияси асосида инсон юзини ани?лаш масалаларини чу?ур та?лил ?илган. Инсон юзини ани?лаш масалаларини ечишнинг мавжуд усуллари ?иёсий та?лили келтирилган. Кўп ?атламли персептрон фаолияти ва тузулмаси ?аралган ?амда уларни ў?итилишининг асосий бос?ичлари ани?ланган.

Оглавление

Введение

I. Исследование методов обработки изображений для решения задачи распознавания человеческих лиц

1.1 Исследование и формирования задачи распознавания человеческих лиц

1.2 Сравнительный анализ методов распознавания человеческих лиц

1.2.1 Метод главных компонент

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

1.2.3 Гибкие контурные модели лица

1.2.4 Сравнение эластичных графов

1.2.5 Методы, основанные на геометрических характеристиках лица

1.2.6 Скрытые Марковские модели

1.3 Нейросетевые технологии решения задачи распознавания изображений

1.4 Обучение нейронных сетей

1.5 Нейронные сети обратного распространения

1.6 Цель и задачи выпускной квалификационной работы

Выводы по главе I

II. Разработка распознающей модели системы распознавания лиц на основе нейросетевых технологий

2.1 Предварительная обработка изображения

2.2 Решения задачи обнаружения человеческого лица

2.3 Формирования признакового пространства с извлечением ключевых характеристик изображения

2.4 Построение нейросетевого классификатора для решения задачи распознавания лиц

Выводы по главе II

III. Разработка программного обеспечения распознающей модели человеческих лиц

3.1 Описание выбранного инструментария

3.2 Руководство программиста

3.3 Руководство пользователя

Выводы по главе III

IV. Безопасность жизнедеятельности

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

4.1.1 Понятие о микроклимате производственных помещений

4.1.2 Основные параметры микроклимата

4.1.3 Создание требуемых параметров микроклимата

4.2 Чрезвычайные ситуации. Защита предприятия в чрезвычайных ситуациях и ликвидация последствий

4.2.1 Чрезвычайные ситуации

4.2.2 Классификация чрезвычайных ситуаций

4.2.3 Ликвидация последствий ЧС

Выводы по главе IV

Заключение

Литература

Приложение

Введение

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

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

Примеры задач распознавания образов:

· Распознавание букв

· Распознавание штрих-кодов

· Распознавание автомобильных номеров

· Распознавание лиц

· Распознавание речи

· Распознавание изображений

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

Традиционно задачи распознавания образов включают в круг задач искусственного интеллекта.

Можно выделить два основных направления:

· Изучение способностей к распознаванию, которыми обладают живые существа, объяснение и моделирование их;

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

Распознавание образов -- это отнесение исходных данных к определенному классу с помощью выделения существенных признаков, характеризующих эти данные, из общей массы несущественных данных.

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

Второй подход -- найти контур объекта и исследовать его свойства (связность, наличие углов и т. д.)

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

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

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

· Взаимодействие компьютер-человек;

· Виртуальная реальность, компьютерная графика, компьютерные игры;

· Водительские права, паспорт;

· Контроль над иммиграцией;

· Персонализация бытовых устройств;

· Шифрование данных;

· Электронная коммерция;

· Криминалистика;

· Охранные системы.

I. Анализ исследуемой области и постановка задачи

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

1.1 Исследование и формирование задачи распознавания человеческих лиц

Можно придумать много вариантов постановки задачи распознавания лиц. Вот один из них. Предположим, что имеется некоторая тренировочная коллекция, состоящая из 400 фотографий (по 10 фотографий для 40 людей при разных условиях).

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

· Изображение не является лицом

· Изображение является лицом такого-то человека из коллекции

· Изображение является лицом, но его нет в коллекции. В этом случае его можно добавить в коллекцию

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

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

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

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

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

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

Рис. 1.1. Структура методов распознавания изображений

1.2 Методы распознавания человека по изображению лица. Достоинства и недостатки, сравнение

1.2.1 Метод главных компонент

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

Применение для задачи распознавания человека по изображению лица имеет следующий вид. Входные вектора представляют собой отцентрированные и приведённые к единому масштабу изображения лиц. Собственные вектора, вычисленные для всего набора изображений лиц, называются собственными лицами (eigenfaces). Метод главных компонент в применении к изображениям лиц так же называют методом собственных лиц. Собственные лица имеют полезное свойство, заключающееся в том, что изображение, соответствующее каждому такому вектору имеет лицеподобную форму, рис. 1.3.



Рис. 1.2. а) полное пространство, разбитое на собственное пространство и его ортогональное дополнение . DIFS - distance in feature space, расстояние в собственном пространстве, DFFS - distance from feature space, расстояние до проекции в собственном пространстве; б) типичный спектр собственных чисел и его разбиение на два ортогональных подпространства

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

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

Рис. 1.4. а) выровненное изображение лица, б) реконструкция по 85-и главным компонентам, в) JPEG - реконструкция (530 байт)

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

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

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

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

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

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

Метод собственных лиц требует для своего применения идеализированных условий, таких как единые параметры освещённости, нейтральное выражение лица, отсутствие помех вроде очков и бород. Эти условия в общем случае нельзя достичь путём предварительной обработки. При несоблюдении этих условий главные компоненты не будут отражать межклассовые вариации, и классы перестают представлять собой кластеры в собственном пространстве. Например, при различных условиях освещённости, метод собственных лиц практически неприменим, поскольку первые главные компоненты преимущественно отражают изменения освещения, и сравнение выдаёт изображения, имеющие похожий уровень освещённости. Линейный дискриминантный анализ (линейный дискриминант Фишера, Linear Discriminant Analysis, LDA), который описывается ниже, выбирают проекцию пространства изображений на пространство признаков таким образом, чтобы минимизировать внутриклассовое и максимизировать межклассовое расстояние в пространстве признаков, рис 1.5. В этих методах предполагается что классы линейно разделимы.

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

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

где S_B - матрица межклассовой дисперсии, S_W - матрица внутриклассовой дисперсии. Может существовать до с-1 векторов составляющих базис пространства признаков, где с - общее число классов. С помощью этих векторов пространство изображений переводится в пространство признаков. Поскольку работа непосредственно с матрицей затруднительна из-за её размерности, используют предварительное уменьшение размерности с помощью метода главных компонент, и затем вычисления производятся в пространстве меньшей размерности:

где W_pca - матрица для проецирования в пространство меньшей размерности (пространство главных компонент).

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

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

1.2.3 Гибкие контурные модели лица

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

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

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

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

1.2.4 Сравнение эластичных графов

В этом методе лицо представляется в виде графа, вершины которого расположены на ключевых точках лица, таких как контуры головы, губ, носы и их крайних точках, рис. 1.6. Каждая грань помечена расстояниями между её вершинами. В каждой такой точке вычисляются коэффициенты Габоровых функций для пяти различных частот и восьми ориентаций. Набор таких коэффициентов <называется джетом (jet). Джеты характеризуют локальные области изображений и служат для двух целей. Во первых, для нахождения точек соответствия в заданной области на двух различных изображениях. Во вторых - для сравнения двух соответствующих областей различных изображений.

Рис. 1.6. Эластичный граф, покрывающий изображение лица

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

.

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

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

Левая сумма характеризует подобие джетов вычисленное с применением фазочувствительной функции, правая - топографическое соответствие, которое пропорционально квадрату разности расстояний между соответствующими вершинами сравниваемых изображений, N - количество вершин, E - количество граней, Размещено на http://www.allbest.ru/

70

Размещено на http://www.allbest.ru/

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

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

Рис. 1.7. Эластичная решётка, наложенная на изображение, и её искажение

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

1.2.5 Методы, основанные на геометрических характеристиках лица

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

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

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

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

1.2.6 Скрытые Марковские модели

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

Рис. 1.9. Схема Марковской модели, пример последовательности наблюдений O и последовательности состояний S

Каждая модель , рис. 1.9, представляет собой набор N состояний (на рисунке - вершины графа), между которыми возможны переходы (на рисунке - дуги). В каждый момент времени система находится в строго определённом состоянии. В наиболее распространённых Марковских моделях первого порядка полагается, что следующее состояние зависит только от текущего состояния. При переходе в каждое состояние генерируется наблюдаемый символ, который соответствует физическому сигналу с выхода моделируемой системы. Набор символов для каждого состояния , количество символов M.

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

Считается, что A не зависит от времени. Если из каждого состояния можно достичь любого другого за один переход, то все , и модель называется эргодической. Так же модель имеет вероятность начальных состояний , где . Обычно в реальных процессах последовательность состояний является скрытой от наблюдения и остаётся неизвестной, а известен только выход системы, последовательность наблюдаемых символов <, где каждое наблюдение - символ из V, и T - число наблюдений в последовательности. Поэтому такие модели называют скрытыми Марковскими моделями (СММ, по английски - Hidden Markov Models, HMM). Модель с настроенными параметрами может быть использована для генерирования последовательности наблюдений. Для этого случайно, в соответствии с начальными вероятностями выбирается начальное состояние, затем на каждом шаге вероятность B используется для генерации наблюдаемого символа, а вероятность A - для выбора следующего состояния. Вероятность P< генерирования моделью последовательности состояний O:

,

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

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

1. Имея последовательность наблюдений и настроенную модель , как оценить вероятность генерации этой моделью данной последовательности наблюдений? Эта задача называется задачей распознавания.

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

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

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

Рис. 1.10. Линейная Марковская модель

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

Суть двумерных Марковских моделей заключается в том, что в отличие от одномерных линейных СММ, они позволяют моделировать искажения изображения и взаимное расположение участков не отдельно по горизонтали или вертикали, а в обоих направлениях одновременно. Для уменьшения вычислительной сложности применяются псевдодвумерные СММ (Pseudo-2D Hidden Markov Models, P2D-HMM). Такая модель состоит из нескольких линейных вертикальных моделей нижнего уровня, и одной линейной горизонтальной модели верхнего уровня, на вход которой поступают выходы моделей нижнего уровня, рис. 1.11. Каждое состояние модели верхнего уровня включает в себя последовательность состояний соответствующей модели нижнего уровня. Модели нижнего уровня не связаны между собой.

Рис. 1.11. Псевдодвумерная скрытая Марковская модель

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

Наблюдениям, подаваемым на вход СММ, являлись квадратные участки изображений, рис. 1.12. Было обнаружено, что участки, извлекаемые с 75% перекрытием друг с другом, давали наилучшую точность распознавания.

Рис. 1.12. Извлечение участков-образцов наблюдения

Одним из полезных свойств СММ является способность сегментировать распознаваемое изображение. Результат работы алгоритма Витерби, разбившего изображение на последовательность состояний, показан на рис. 1.13.

В работах продолжающих идею Самарии использовались дальнейшие улучшения способов начального представления изображения и алгоритмов тренировки. Для каждого квадратного участка изображения 16х16 вычислялось двумерное дискретное косинусное преобразование, и этот участок представлялся в виде набора первых 15-ти коэффициентов. Это позволило повысить точность распознавания на 2%. Кроме того, такое представление позволяет более точно, чем при масштабировании представлять изображение, используя меньший объём информации. Для увеличения тренировочного набора использовались так же зеркально отражённые по вертикали изображения.



Рис. 1.13. Сегментация изображения. Линии отмечают области, соответствующие одинаковым состояниям.

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

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

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

1.3 Нейросетевые технологии решения задачи распознавания изображений

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

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

Любая ИНС состоит из некоторого количества искусственных нейронов.

Искусственный нейрон имитирует в первом приближении свойства биологического нейрона. На вход искусственного нейрона поступает некоторое множество сигналов, каждый из которых является выходом другого нейрона. Каждый вход умножается на соответствующий вес, аналогичный синаптической силе, и все произведения суммируются, определяя уровень активации нейрона. На рис. 1.2 представлена модель, реализующая эту идею. Хотя сетевые парадигмы весьма разнообразны, в основе почти всех их лежит эта конфигурация. Здесь множество входных сигналов, обозначенных x₁, x₂,…, x_n, поступает на искусственный нейрон. Эти входные сигналы, в совокупности обозначаемые вектором X, соответствуют сигналам, приходящим в синапсы биологического нейрона. Каждый сигнал умножается на соответствующий вес w₁, w₂,…, w_n, и поступает на суммирующий блок, обозначенный У. Каждый вес соответствует «силе» одной биологической синаптической связи. (Множество весов в совокупности обозначается вектором W.) Суммирующий блок, соответствующий телу биологического элемента, складывает взвешенные входы алгебраически, создавая выход, который мы будем называть NET. В векторных обозначениях это может быть компактно записано следующим образом:

NET = XW.

Рис. 1.14. Искусственный нейрон

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

OUT = K(NET),

где К - постоянная, пороговой функции OUT = 1, если NET > T, OUT = 0 в остальных случаях,

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

Рис. 1.15. Искусственный нейрон с активационной функцией

На рис. 1.3 блок, обозначенный F, принимает сигнал NET и выдает сигнал OUT. Если блок F сужает диапазон изменения величины NET так, что при любых значениях NET значения OUT принадлежат некоторому конечному интервалу, то F называется «сжимающей» функцией. В качестве «сжимающей» функции часто используется логистическая или «сигмоидальная» (S-образная) функция, показанная на рис. 1.4а. Эта функция математически выражается как F(x) = 1/(1 + е^-x). Таким образом,

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

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

Рис. 1.16. Сигмоидальная логистическая функция

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

OUT = th(x).

Подобно логистической функции гиперболический тангенс является S-образной функцией, но он симметричен относительно начала координат, и в точке NET = 0 значение выходного сигнала OUT равно нулю (см. рис. 1.4б). В отличие от логистической функции гиперболический тангенс принимает значения различных знаков, что оказывается выгодным для ряда сетей (см. гл. 3).

Рис. 1.17. Функция гиперболического тангенса

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

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

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

Рис. 1.18. Однослойная нейронная сеть

А каждый нейрон выдает взвешенную сумму входов в сеть. В искусственных и биологических сетях многие соединения могут отсутствовать, все соединения показаны в целях общности. Могут иметь место также соединения между выходами и входами элементов в слое. Удобно считать веса элементами матрицы W. Матрица имеет т строк и п столбцов, где m - число входов, а n - число нейронов. Например, w_2,3 - это вес, связывающий третий вход со вторым нейроном. Таким образом, вычисление выходного вектора N, компонентами которого являются выходы OUT нейронов, сводится к матричному умножению N = XW, где N и Х - векторы-строки.

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

Рис. 1.19. Двухслойная нейронная сеть

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

1.4 Обучение искусственных нейронных сетей

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

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

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

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

1.5 Нейронные сети обратного распространения

Нейронные сети обратного распространения - это мощнейший инструмент поиска закономерностей, прогнозирования, качественного анализа. Такое название - сети обратного распространения (back propagation) они получили из-за используемого алгоритма обучения, в котором ошибка распространяется от выходного слоя к входному, т. е. в направлении, противоположном направлению распространения сигнала при нормальном функционировании сети. Нейронная сеть обратного распространения состоит из нескольких слоев нейронов, причем каждый нейрон слоя i связан с каждым нейроном слоя i+1, т. е. речь идет о полносвязной НС. В общем случае задача обучения НС сводится к нахождению некой функциональной зависимости Y=F(X) где X - входной, а Y - выходной векторы. В общем случае такая задача, при ограниченном наборе входных данных, имеет бесконечное множество решений. Для ограничения пространства поиска при обучении ставится задача минимизации целевой функции ошибки НС, которая находится по методу наименьших квадратов:

(5)

где y_j - значение j-го выхода нейросети

d_j - целевое значение j-го выхода

p - число нейронов в выходном слое

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

(6)

где h - параметр, определяющий скорость обучения.

(7)

где y_j - значение выхода j-го нейрона

S_j - взвешенная сумма входных сигналов, определяемая по форм. (1).

При этом множитель

(8)

где x_i - значение i-го входа нейрона

Далее рассмотрим определение первого множителя формулы (7)

(9)

где k - число нейронов в слое n+1.

Введем вспомогательную переменную

(10)

Тогда мы сможем определить рекурсивную формулу для определения n-ного слоя, если нам известно следующего (n+1)-го слоя.

...