Метод распознавания лиц Виолы-Джонса (Viola-Jones)

План статьи

  1. Описание алгоритма
  2. Схема распознавания
  3. Признаки класса
  4. Схема обучения
  5. Интегральное представление изображений
  6. Обучение
  7. Распознавание
  8. Недостатки алгоритма Виолы-Джонса
  9. Литература

Описание алгоритма

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

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

Метод имеет следующие преимущества:

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

Схема распознавания

Обобщенная схема распознавания в алгоритме Виолы-Джонса показана на рисунке ниже.

Обобщенная схема алгоритма Виолы-Джонса

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

Признаки класса

В качестве признаков для алгоритма распознавания авторами были предложены признаки Хаара, на основе вейвлетов Хаара. Они были предложен венгерским математиком Альфредом Хааром в 1909 году.

Пример вейвлета Хаара

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

Пример масок в алгоритме Виолы-Джонса

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

Набор признаков Хаара из метода Виолы-Джонса

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

F=X-Y

где X – сумма значений яркостей точек закрываемых светлой частью признака, а Y – сумма значений яркостей точек закрываемых темной частью признака.

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

Схема обучения

Обобщенная схема алгоритма обучения выглядит следующим образом. Имеется тестовая выборка изображений. Размер тестовой выборки около 10 000 изображений. На рисунке показан пример обучающих изображений лиц. Алгоритм обучения работает с изображениями в оттенках серого.

Пример обучающих изображений лиц

При размере тестового изображения 24 на 24 пикселя количество конфигураций одного признака около 40 000 (зависит от минимального размера маски). Современная реализация алгоритма использует порядка 20 масок. Для каждой маски, каждой конфигурации тренируется такой слабый классификатор, который дает наименьшую ошибку на всей тренировочной базе. Он добавляется в базу данных. Таким образом алгоритм обучается. И на выходе алгоритма получается база данных из T слабых классификаторов. Обобщённая схема алгоритма обучения показана на рисунке.

Обобщенная схема алгоритма обучения

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

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

количество всех тестовых изображений

где X – множество всех тестовых изображений, где для каждого заранее известно присутствует ли искомый объект или нет и отражено во множестве Y.

присутствует ли искомый объект или нет и отражено во множестве Y

где

присутствие объекта на изображении

Под признаком j будем понимать структуру вида

Под признаком j будем понимать структуру вида

Тогда откликом признака будет fj (x), который вычисляется как разность интенсивностей пикселей в светлой и темной областях. Слабый классификатор имеет вид:

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

Задача слабого классификатора – угадывать присутствие объекта в больше чем 50% случаев. Используя процедуру обучения AdaBoost  создается очень сильный классификатор состоящий из T слабых классификаторов и  имеющий вид:

очень сильный классификатор состоящий из T слабых классификаторов

Целевая функция обучения имеет следующий вид:

Целевая функция обучения имеет следующий вид

Интегральное представление изображений

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

Интегральное представление изображений

где I(r,c) — яркость пиксела исходного изображения.

Каждый элемент матрицы II[x,y] представляет собой сумму пикселов в прямоугольнике от (0,0) до (x,y). Расчет такой матрицы занимает линейное время. Для того, чтобы вычислить сумму прямоугольной области в интегральном представлении изображения требуется всего 4 операции обращения к массиву и 3 арифметические операции. Это позволяет быстро рассчитывать признаки Хаара для изображения в обучении и распознавании.

Например, рассмотрим прямоугольник ABCD.

Интегральное изображение на примере прямоугольника ABCD

Сумму внутри прямоугольника ABCD можно выразить через суммы и разности смежных прямоугольников по формуле:

Сумму внутри прямоугольника ABCD можно выразить

Обучение

Перед началом обучения инициализируются веса w(q,i), где q – номер итерации, i-номер изображения.

инициализируются веса

После процедуры обучения получится T слабых классификаторов и T значений.

T слабых классификаторов и T значений

алгоритм обучения в методе виолы-джонса

На каждой итерации цикла происходит обновление весов так, что их сумма будет равна 1. Далее для всех возможных признаков происходит подбор таких значений p,θ,j что значение ошибки e_j будет минимально на этой итерации. Полученный признак J(t) (на шаге t) сохраняется в базу слабых классификаторов, обновляются веса и вычисляется коэффициент a_t.

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

Распознавание

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

На вход алгоритму поступает изображение I(r,c) размером W х H, где I(r,c) – яркостная составляющая изображения. Результатом работы алгоритма служит множество прямоугольников R(x,y,w,h), определяющих положение лиц в исходном изображении I.

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

алгоритм распознавания в методе Виолы-Джонса

Недостатки алгоритма Виолы-Джонса

Базовый алгоритм Виолы-Джонса (далее базовый алгоритм) имеет ряд недостатков:

Литература

Комментарии

comments powered by Disqus