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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В этом методе (Elastic Bunch Graph Matching) [ElGraph] лицо представляется в виде графа, вершины которого расположены на ключевых точках лица, таких как контуры головы, губ, носы и их крайних точках, рис. 19. Каждая грань помечена расстояниями между её вершинами. В каждой такой точке вычисляются коэффициенты Габоровых функций для пяти различных частот и восьми ориентаций. Набор таких коэффициентов <называется джетом (jet). Джеты характеризуют локальные области изображений и служат для двух целей. Во первых, для нахождения точек соответствия в заданной области на двух различных изображениях. Во вторых – для сравнения двух соответствующих областей различных изображений. Каждый коэффициент для точек из одной области различных изображений, характеризуется амплитудой , которая медленно меняется с изменением положения точки и фазой , которая вращается со скоростью, пропорциональной частоте волнового вектора базисного вейвлета. Поэтому в простейшем случае для поиска на новом изображении точки с аналогичными характеристиками в функции подобия фазу не учитывают: . Функция подобия с одним джетом в фиксированной позиции и другим с переменной позицией является достаточно гладкой, для того чтобы получить быструю и надёжную сходимость при поиске с применением простейших методов, таких как диффузия или градиентный спуск [ElGraph]. Более совершенные функции подобия привлекают информацию о фазе.

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

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

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

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

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

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

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

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

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

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

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

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

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

В процессе распознавания сравниваются признаки неизвестного лица, с признаками, хранящимися в базе.

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

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

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

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

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

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

Рис. 22. Сравниваемые области-эталоны лица

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

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

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

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

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

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

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

Рис. 24. Отображение неизвестного изображения на изображение из базы. Изображения разных людей.

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

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

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

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

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

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

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

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

Так же модель имеет вероятность начальных состояний , где .

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

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

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

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

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

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

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

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

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

Суть двумерных Марковских моделей заключается в том, что в отличие от одномерных линейных СММ, они позволяют моделировать искажения изображения и взаимное расположение участков не отдельно по горизонтали или вертикали, а в обоих направлениях одновременно. Для уменьшения вычислительной сложности применяются псевдодвумерные СММ (Pseudo-2D Hidden Markov Models, P2D-HMM<). Такая модель состоит из нескольких линейных вертикальных моделей нижнего уровня, и одной линейной горизонтальной модели верхнего уровня, на вход которой поступают выходы моделей нижнего уровня, рис. 28. Каждое состояние модели верхнего уровня включает в себя последовательность состояний соответствующей модели нижнего уровня. Модели нижнего уровня не связаны между собой. Изначально в [Samaria] модели верхнего уровня были вертикальными. В последующих работах [DCT-HMM1] модели верхнего уровня были сделаны горизонтальными (как это и изображено на рисунке), в связи с тем, чтобы вертикальные модели нижнего уровня могли учесть факт того, что глаза могут находиться на разной высоте. Таким образом псевдодвумерная модель позволяет учесть локальные деформации и взаимное расположение участков изображений. Но в отличие от оптических потоков и других методов сопоставления деформациями, псевдодвумерная модель учитывает характер деформаций, а то какими именно могут быть возможные деформации, псевдодвумерные СММ усваивают в процессе обучения. Другими словами, участок, соответствующий глазу, никогда не будет сопоставлен например участку на месте рта, как это может быть в оптическом потоке.

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

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

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

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

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

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

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

Для увеличения тренировочного набора использовались так же зеркально отражённые по вертикали изображения [DCT-HMM1]. Это позволило учесть более широкий диапазон ракурсов.

Для СММ важное значение имеет начальная инициализация модели. В [DCT-HMM1], в качестве начальной инициализации всех моделей использовались все изображения из тренировочного набора. Затем модель каждого класса донастраивалась на свои изображения. На базе ORL было достигнуто 100% точность распознавания. Авторы этой работы считают это основным фактором, давшим прирост производительности.

Полезное свойство распознавания по коэффициентам дискретного косинусного преобразования заключается в том, что оно позволяет работать непосредственно со сжатыми изображениями, такими как JPEG и MPEG, в которые на сегодняшний день являются распространёнными форматами хранения изображений и видео. В работе [DCT-HMM2] производились эксперименты по распознаванию сжатых JPEG <изображений. Было достигнуто 99.5% точности на той же базе. Падение точности связано с невозможностью извлекать перекрывающиеся блоки в процессе распознавания (но в процессе обучения перекрывающиеся блоки были использованы).

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

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

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

Дата изменения: 15.11.2001