Задача обнаружения головы человека на изображениях является актуальной при разработке биометрических систем, человеко-машинных интерфейсов, систем виртуальной реальности, тренажерных комплексов, симуляторов, компьютерных игр и т.д. Например, в системах компьютерного зрения при отслеживании головы пользователя в пространстве возникают ситуации, когда объект пропадает из поля видимости видеокамеры. Это происходит из-за резкого изменения скорости движения объекта, частичного перекрытия другими объектами, поворотов или выхода за рамки обозреваемой области.
Для обнаружения головы человека чаще всего используются каскады классификаторов [9] и методы, анализирующие цвет кожи [4]. Методы, использующие каскады классификаторов, являются наиболее популярными в компьютерном зрении. Одним из таких подходов является метод Виолы-Джонса, в котором для обнаружения используются классификаторы на основе признаков Хаара. Недостатками метода являются необходимость обучения, а также значительное уменьшение точности при повороте головы относительно осей глобальных координат.
Обнаружение головы человека на основе информации о цвете кожи лучше подходит для ситуаций со статичным фоном. Общим недостатком таких подходов является возникновение ошибок в тех случаях, когда цветовые характеристики фона и лица человека совпадают. Также результат сильно зависит от цветового баланса камеры и освещения.
Для выполнения поиска выделенную область изображения, на которой предполагается нахождение головы, необходимо сравнить с изображением, полученным на этапе инициализации пользователя. Для решения задачи предлагается описывать изображение головы в виде структуры с использованием графов. Преимуществом структурных методов и алгоритмов является то, что они позволяют анализировать большое множество элементов на основе малого количества простых составляющих и правил формирования графической модели. Также структурные методы позволяют описать те характеристики объекта, которые исключают его отнесение к другому классу, что повышает надежность распознавания. Вместо сравнения структур графов предлагается анализировать числовые характеристики, получаемые на основе вложения графов в векторное пространство меньшей размерности. Это позволит повысить скорость обработки информации и перейти к приближенному сравнению структур, что увеличит робастность приложений [2].
Построение графа на основе изображений
На этапе инициализации необходимо получить изображения головы человека анфас. Для построения графа необходимо выделить особые точки на изображении. Для этого используется FAST-детектор особенностей (Feature Accelerated Segment Test) [8]. Следует отметить, что при поворотах головы некоторые особенности на различных кадрах видеопоследовательности будут пропадать. Чтобы снизить влияние этого процесса на надежность обнаружения, предлагается отслеживать центры стабильных областей. Обычно такими областями являются характерные части головы человека: глаза, нос, уши, рот и т.д. При повороте головы набор особых точек в таких областях может измениться, но сама область будет присутствовать на изображении.
Производится кластеризация особых точек. В ходе данного процесса все особые точки, выделенные на лице, группируются на основе метода связных компонент. Если в каком-либо кластере оказывается мало особенностей, то он не рассматривается далее. Таким образом, формируются сегменты, соответствующие наиболее характерным областям лица (рис. 1). Эксперименты проводились на изображениях, входящих в базы данных Массачусетского Технологического Института (MIT-CBCL Face Recognition Database). Эксперименты показали, что наиболее характерные сегменты остаются на изображениях при поворотах головы (рис. 1).
Рис. 1. Кластеризации особых точек, выделенных на изображении лица человека детектором FAST
После сегментации осуществляется построение графа. В качестве вершин выбираются центры масс полученных сегментов. Граф строится на основе триангуляции Делоне.
Матрица смежности построенного графа имеет вид
(1)
Вложение графов в векторное пространство
При обнаружении головы на изображении предлагается сравнивать спектральные характеристики графов на текущем кадре и снимке, полученном на этапе инициализации [6]. Предлагается воспользоваться термодинамическим уравнением. Данный подход широко используется при исследовании воздействий температуры на газы с поэтапным отслеживанием изменения текущего состояния [3]. Практическим применением термодинамического уравнения может являться решение задачи сопоставления изображений [1].
Нормализованная матрица Лапласа имеет вид
(2)
где du, dv – степени вершин u и v соответственно.
На основе декомпозиции нормализованной матрицы Лапласа вычисляются спектральные характеристики графа:
Ln = ΦΛΦT, (3)
где Λ – диагональная матрица собственных значений 
Ф – матрица собственных векторов 
Вложение графа основано на решении термодинамического уравнения:
(4)
где Ht – тепловое ядро; t – время.
Тепловое ядро вычисляется с помощью собственных значений и собственных векторов [3]:
(5)
Тепловое ядро представляет собой матрицу размером 
. Для вершин u и v графа G тепловое ядро примет следующий вид:
(6)
Проецирование графа в векторное пространство осуществляется с помощью декомпозиции Юнга-Хаусхолдера [10]:
Ht = YTY, (7)
где 
– матрица координат размером 
.
Из выражений (6) и (7) матрица координат будет иметь вид
(8)
Таким образом, координатный вектор для вершины u рассчитывается следующим образом:
(9)
При вложении графа в векторное пространство для описания связи между точками используются составные кривые [10]. Такие кривые рассчитываются на основе геодезического расстояния dG и квадратичного евклидового расстояния dE между вершинами на поверхности сферы (рис. 2). Квадратичное евклидово расстояние в этом случае имеет вид
(10)
Рис. 2. Расчет геодезического и евклидова расстояния при вложении графа в векторное пространство
Составные кривые, расположенные на поверхности сферы, характеризуются параметрами кривизны. Для точек u и v значение кривизны k(u, v) рассчитывается следующим образом:
(11)
где R(u, v) – радиус сферы
Представим кривую в качестве дуги окружности с радиусом R. В таком случае длина дуги (кратчайший путь по поверхности сферы между точками u и v) будет иметь вид
(12)
где αu,v – угол дуги.
При вложении графов в векторное пространство геодезическое расстояние характеризуется ребром графа и принимается равным dG(u, v) = 1. В таком случае
(13)
Евклидово расстояние является хордой в рассматриваемой окружности между точками u и v:
(14)
В дальнейших расчетах необходимо избавиться от вычисления функции синуса неизвестного угла. Для этого предлагается разложить функцию sin(x) в ряд Маклорена, то есть в ряд Тейлора в окрестности точки x = 0:
(15)
Предполагается, что в расчетах хватит точности до двух членов последовательности ряда Маклорена. Таким образом, евклидово расстояние вычисляется следующим образом:
(16)
Решая это уравнение в поисках R, получим следующее значение кривизны:
(17)
Чтобы показать, как найти расстояние между графами, рассмотрим два графа:
G1 = (V1, E1, k1) и G2 = (V2, E2, k2),
где V1, V2 – набор вершин; E1, E2 – набор ребер; k1, k2 – матрицы кривизны. Таким образом, расстояния между графами можно описать с помощью метрики Хаусдорфа [7]:
(18)
С помощью метрики Хаусдорфа формируется матрица расстояний для всех графов изображений-кандидатов и изображений-эталонов. Для визуального описания сходства между объектами, представленными графами, используется метод многомерного шкалирования (MDS – Multi Dimensional Scaling) [5].
Таким образом, алгоритм вложения графов для обнаружения головы человека на изображениях состоит из следующих этапов:
Шаг 1. Выделяются особые точки изображения-кандидата.
Шаг 2. Особые точки кластеризуются.
Шаг 3. На основе центра масс сегментов строится граф Делоне. Рассчитывается матрица смежности графа, вычисляются спектральные характеристики (2)–(4).
Шаг 4. С помощью преобразования Юнга-Хаусходера происходит проецирование координат вершин графа в векторное пространство (9).
Шаг 5. Рассчитываются значения кривых (17).
Шаг 6. Вычисляется матрица расстояний между характеристиками объектов из базы эталонов и характеристиками изображений-кандидатов (18).
Шаг 7. Для визуализации данных применяется алгоритм многомерного шкалирования, позволяющий отобразить степень близости изображения-кандидата к какому-либо объекту из базы эталонов.
Результаты экспериментов
Для проведения экспериментов использовались изображения головы человека, близкие к анфасному положению. Диапазон поворотов и наклонов головы составлял не более 30 градусов (рис. 3, а). Также для экспериментов были использованы изображения тестовых объектов (3, б, в, г).
а
б
в
г
Рис. 3. Построение графов по изображениям
В результате экспериментов установлено, что с использованием спектральных характеристик графа возможно отнесение объектов к определенному классу. Эталоном являлось одно из изображений группы объектов. Представление спектральных характеристик графа в двумерном пространстве осуществлялось с использованием метода многомерного шкалирования. Спектральные характеристики графа каждого изображения после преобразований представляют собой точку в двумерном пространстве (рис. 4). Отнесение объектов к некоторому классу происходит на основе вычисления меры близости к характеристикам объекта-эталона.
Рис. 4. Представление характеристик графов в двумерном пространстве с помощью метода многомерного шкалирования
Заключение
В работе предложен подход для обнаружения головы человека на изображениях. Подход основан на использовании тепловых ядер на графах. На основе вычисления тепловых ядер осуществляется представление характеристик графа в векторном пространстве. Достоинством подхода является полная инвариантность к повороту изображения на плоскости, так как спектральные характеристики графа не зависят от маркировки его вершин. Кроме того, вложение графов в векторное пространство с использованием тепловых ядер позволяет осуществлять приближенное сравнение структур. Сравнение векторов осуществляется намного быстрее и точнее, чем нахождение структурных соответствий. Использование кластеров особенностей позволяет выделять наиболее стабильные области на изображениях. Эти обстоятельства делают подход устойчивым к изменениям ракурса изображений. В ходе экспериментов выявлено, что обнаружение головы на основе эталона возможно при изменении угла поворота до 30 градусов относительно анфасного положения.
Работа выполнена при финансовой поддержке РФФИ (проекты № 16-37-00235, № 15-07-01612).