Поиск лиц на основе скрытых марковских моделей

На данный момент происходит лавинообразное увеличение числа мультимедиа-ресурсов, в частности ­ изображений. Как следствие, возрастают требования к средствам систематизации и поиска подобных ресурсов. Большинство существующих на данный момент систем,
осуществляющих поиск информации по описанию (англ. Description-Based Image Retrieval, DBIR), уже не могут в полной мере удовлетворить потребности человека. Поэтому все больше растет интерес к поиску объектов по содержанию (англ. Content-Based Image Retrieval, CBIR).

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

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

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

Прежде чем перейти к рассмотрению моделей, рассмотрим, что представляет собой марковская цепь (марковский процесс). Последовательность случайных переменных Xn называется марковской цепью, если:
P(Xn= a | Xn-1 = b, Xn-2 = c, …, X0 = x) = P (Xn | X = b).
Доказано, что марковские цепи позволяют создавать довольно простые и информативные картины. Можно, например, изобразить взвешенный направленный граф с узлом для каждого состояния и весовым коэффициентом на каждом ребре, указывающем вероятность перехода между состояниями:
image
При наблюдении случайной переменной Xn известно, в каком состоянии находится цепь. Эта модель, к сожалению, слишком ограничена и ей не под силу решение многих актуальных проблем. Более совершенную модель можно получить, положив, что для каждого элемента последовательности наблюдается иная случайная переменная, распределение вероятностей которой зависит от состояния цепи – наблюдается некоторая переменная Yn, причем распределение вероятностей в некоторой точке P(Yn| Xn= si) = qi (Yn). Данные элементы можно собрать в матрицу Q. Модели подобного рода называются скрытыми марковскими моделями (СММ). Для задания СММ требуется обеспечить процесс перехода между состояниями, связи между состоянием и распределением вероятности
Yn, а также знать исходное распределение состояний.

Рассмотрим формальное описание скрытой марковской модели. Каждая модель определяется следующими параметрами:
  • Множество S = {s1, s2, …, sN} из N состояний.
  • Начальное распределение вероятностей P = {pi}.
  • Матрица вероятностей переходов между состояниями A = {ai}.
  • Матрица вероятности генерации наблюдений B = {bj(Ot)}, где bj(Ot) – вероятность генерации наблюдения Ot в момент времени t в состоянии qt= sj, bj(Ot) = P(Ot | qt = sj).
Важно отметить, что рассмотренная модель является одномерной. Существуют также многомерные марковские модели (псевдомногомерные СММ). В рамках данной работы практический интерес имеют псевдодвухмерные модели, ввиду того, что основная работа проводится с изображениями.
Каждый элемент вложенной СММ называется суперсостояниеми представляет собой отдельную одномерную марковскую модель с параметрами, описанными выше.

Изображение с точки зрения распознавания

Цифровое изображение – суть случайный двумерный дискретный сигнал, наблюдаемый системой. Последовательность наблюдений (вектор наблюдений) может извлекаться из изображения различными способами. В силу этого описательные способности полученных моделей могут различаться. Наиболее предпочтительным является вариант сканирования изображения прямоугольным окном. Для уменьшения вероятности потери данных на границах блоков, рекомендуется сканировать изображение таким образом, что соседние блоки пикселей могут перекрываться друг другом. Значение перекрытия подбирается экспериментально.
Для снижения вычислительной сложности и уменьшения пространства признаков, каждый извлеченный блок пикселей подвергается некоторому преобразованию, в результате которого получается некоторый набор числовых данных, который и является вектором наблюдений.
Наиболее подходящими для поставленной задачи являются два преобразования:
  • преобразование Карунена-Лоэва (англ. Karhunen-Loeve transform – сокр. KLT);
  • дискретно-косинусное преобразование (англ. Discrete Cosine
    Transform – сокр. DCT).
Преобразование KLT является довольно трудоёмким и требует больших вычислительных ресурсов. Дискретно-косинусное преобразование лишено этих недостатков. Кроме того, DCT позволяет понизить чувствительность системы к шумам, трансформациям и искажениям. После извлечения каждого блока пикселей, каждый из них при помощи дискретно-косинусного преобразования переводится в вектор F. Длина этого вектора – число значимых коэффициентов. Значимыми называются только несколько первых коэффициентов дискретного косинусного разложения. Их число может варьироваться в зависимости от решаемой задачи.

Далее, полученные вектора распределяются по состояниям модели. Здесь необходимо отметить, что каждая отдельная СММ представляет некоторый класс объектов. Тогда состояния модели определяют некоторые ключевые признаки класса. К примеру, СММ для поиска лиц состоит из 5 суперсостояний, соответствующих областям лица (лобовая часть, глаза, нос, рот, подбородок), каждое из которых делится на отдельные состояния.
image
Переход в следующее состояние возможно только после предыдущего, а переход в следующее суперсостояние возможно только после всех состояний текущего суперсостояния. Вероятность принадлежности некоторого объекта заданному классу, оценивается как вероятность генерации сигнала, соответствующего его вектору признаков.

Поиск лиц

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

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

Поиск изображений основан на поиске схожести в многомерном пространстве. При этом изображение определяется набором своих сигнатур. Мера схожести – это функция, которая вычисляет и возвращает значение, соответствующее схожести между двумя объектами согласно некоторым предопределенным критериям. Понятие меры сходства основывается на понятии метрики. Метрика – это функция расстояния d, определенная на метрическом множестве, для любых точек x, y, z которого
выполняются условия:
1. image,
2. image,
3. image.
Индексирование и поиск изображений в коллекциях производится на основе треугольного дерева (triangle tree, trie дерево), также называемое Really Fixed Query Tree. Треугольное дерево – это структура данных, разработанная для поиска приблизительных совпадений в зависимости от усилий поиска. Оно ассоциируется с мерой расстояния, набором ключевых изображений и набором элементов базы данных. Форма trie – это форма дерева, в котором ребра следуют от корня до листьев, определяя индекс листа. Листья дерева содержат элементы базы. Каждое внутреннее ребро в дереве ассоциируется с неотрицательным числом. Каждый уровень дерева ассоциируется с одиночным ключом. Путь от корня до листьев представляет собой расстояние от элемента базы данных до каждого из ключей.
На рисунке представлено треугольное дерево с 4 элементами (W, X, Y, Z) и 2 ключа (J, K). Расстояние от листа W до ключа J равно 3, расстояние от W до K равно 1. Таким образом, каждое изображение будет характеризоваться некоторым набором числовых значений, определенных как расстояния от этого изображения до существующих ключей.
image
Процесс индексирования изображений коллекции заключается в поиске расстояний от каждого изображения до каждого ключа. Исходя из вышесказанного, можно определить принцип поиска следующим образом. Пусть I представляет объект базы, Q представляет объект запроса, K представляет ключевые изображения и d определяет некоторые меры сходства – метрики. Используя свойство метрики (3), заключаем, что следующие неравенства будут верными:
image
image
Комбинируя неравенства, получаем выражение, определяющее расстояние от объекта запроса до объекта коллекции:
image

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

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

На основе вышесказанного можно сделать вывод, что для того, чтобы воспользоваться поиском и индексацией, для каждого изображения необходимо уметь производить следующие действия.
  • Выделять сигнатуры изображений. Для одиночных изображений сигнатурой будут являться вектора наблюдений каждого лица, содержащихся на нем
  • Выделять сигнатуры ключей. При этом для системы поиска на основе СММ, ключами будут являться наборы изображений одного лица, а сигнатурой ­ параметры обученной на этих изображениях модели.
  • Сравнивать сигнатуры ключа и изображения, а также два изображения. При этом результатом сравнения должно быть расстояние, выраженное целым числом, лежащим в отрезке [0; 99].
Основная проблема при поиске лиц с помощью скрытых марковских моделей заключается в том, что с методы, основанные на этих моделях, дают лишь оценку соответствия модели изображения. Иными словами, эта оценка позволяет решить, какая из моделей соответствует изображению больше, чем остальные.

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

При подготовке статьи использовались следующие материалы:
  1. Nefian, A.V. Hidden Markov Madel-Based Approach for Face Detection and Recognition / Ara Nefian. 1999.
  2. Джосан, О.В. Использование Скрытых Марковских Моделей для детектирования радужки на изображении лиц: 2006 / А.В. Джосан, МГУ им. Ломоносова. — 2006.
  3. Гультяева, Т.А. Скрытые марковские модели с одномерной топологией в задаче распознавания лиц / Т.А. Гультяева, А.А. Попов; НГТУ. — 2006.
  4. Berman, A.P. A Flexible Image Database System for Content-Based Retrieval: Computer Vision and Image Understanding / A.P. Berman, L.G. Shapiro. 1999.
Реклама
AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее

Комментарии 12

    0
    А у Вас есть какие — нибудь примеры реальной реализации данной теории, например в Matlab? Интересно посмотреть на реальную работу данного алгоритма.
    0
    Да, само собой, есть. К сожалению, не в Mathlab. Реализация данной теории является модулем к системе поиска. Этот модуль, в частности, позволяет искать лица в коллекциях изображений. Используется библиотека OpenCV.
      0
      Какой процент правильного определения соответствия двух лиц, и конечно какой процент ошибочного определения? Спрашиваю, потом что интересует проф. пригодность алгоритма.
        0
        На первом этапе отсекается положенные 90-95% выборки. На втором этапе — уточняющем поиске — используется сравнение гистограмм, процент правильного определения составляет порядка 90%. К сожалению, остались некоторые моменты, из-за которых остается достаточно высокий процент ошибки. Например, тот же уточняющий поиск, а также, что самое главное, нормирование расстояния между двумя моментами.
      0
      как определяли пороги распознавания? и чему равно число скрытых состояний? откуда брали эти значения?
        0
        что Вы имеете ввиду под порогом распознавания?
        Число скрытых состояний выбиралось, как указано на рисунке. Т.е. 5 суперсотояний, соответственно 3, 6, 6, 6, 3 вложенных. Эти числа являются устоявшимися в задачах распознавания лиц на основе СММ. Опытным путем было установлено (не мной), что такой выбор является одним из самых оптимальных (если не самым оптимальным).
          0
          Я так понимаю есть минимум 2 СММ модели. 1-лицо. 2-не лицо. СММ выдает вероятность принадлежности ей выборки. Для того чтобы выбрать ответ «да лицо» или нет, не лицо — надо сравнивать с порогом выход. Например СММ1 дал 5% а СММ2 дал 3%, то есть рисунок не похож ни на лицо ни на что иное. Или же другой пример. СММ1 дал 75% а СММ2 дал 65%. Достаточно ли 75% для определения что да, наш рисунок содержит лицо? Т.е. стоит вопрос 0.75>K или нет? и чему равно K?
      +1
      Вот как раз здесь и открывается самый главный недостаток СММ. Эти модели не могут отсечь часть классов, как неподходящие, метод показывает лишь, какая из моделей подходит больше. Возвращаясь, к вашим примерам:
      1. «Например СММ1 дал 5% а СММ2 дал 3%, то есть рисунок не похож ни на лицо ни на что иное». С точки зрения СММ на рисунке будет лицо
      2. аналогично

      Следующее, возможно, не совсем относится к вопросу, но все же поясню.
      В моей работе реализовано несколько иначе. Во-первых, на изображениях ищутся лица с помощью классификаторов Хаара. Данный метод показывает довольно большую точность для лиц. Если результат был положительным — следовательно, на изображении присутствуют лица (на этом же этапе получаем и местоположение лиц, что отсекает ненужные шумы). Далее, у нас есть некоторое число натренированных моделей (в терминах поиска по дереву — это ключи). И уже следующим этапом находятся степени соответствия найденных изображений лиц и данных моделей-ключей.
        0
        Хм, каждая СММ модель — узел вершины графа дерева, переходя от узла к узлу определяем лучшую модель?
        Если так, да и вообще, так или не так — это неплохая идея семантического графа скрытых марковских моделей для решения сложных задач.
        Каждая СММ в узле графа может отвечать за свой конкретный вопрос, и передвигаясь по СММ узлам дерева можно реализовать и экспертную систему и нейронные сети (СММ в роли функции нейрона) да и вообще!

        Вам + за мысль :)
          0
          спасибо:) в принципе да, Вы правы. в узле дерева находится модель, ребра имеют некоторый вес — аналогия с нейросетью есть :)

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

      Самое читаемое