Принципы метода Виолы-Джонса

В настоящее время метод Виолы–Джонса является популярным методом для поиска объекта на изображении в силу своей высокой скорости и эффективности. В основу метода Виолы–Джонса положены: интегральное представление изображения по признакам Хаара, построение классификатора на основе алгоритма адаптивного бустинга и способ комбинирования классификаторов в каскадную структуру. Эти идеи позволяют осуществлять поиск объекта в режиме реального времени. Рассмотрим их более подробно.

Интегральное представление изображения – это матрица, одинаковая по размерам с исходным изображением. В каждом элементе матрицы хранится сумма интенсивностей всех пикселов, находящихся левее и выше данного элемента – правого нижнего угла прямоугольной области (0,0) до (x,y). Элементы матрицы L можно рассчитать по формуле:

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

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

Элементы матрицы рассчитываются по формуле:

L(x,y)= I(x,y)+ L(x-1,y-1) + L(x,y-1) + L(x-1,y)

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

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

Признак-отображение, где Df —множество допустимых значений признака. Если заданы признаки f1,…, fn, то вектор признаков x=(f1(x),…,fn(x)) называется признаковым описанием объекта x. Признаковые описания допустимо сопоставлять с самими объектами. При этом множество X=Df1*…*Dfn называют признаковым пространством [1].

Признаки делятся на следующие типы в зависимости от множества Df:

• бинарный признак, Df={0,1};
• номинальный признак: Df — конечное множество;
• порядковый признак: Df — конечное упорядоченное множество;
• количественный признак: Df — множество действительных чисел.

Признак Хаара вычисляется по смежным прямоугольным областям. В стандартном методе Виолы–Джонса используются прямоугольные примитивы, изображенные на рисунке 1.

            Рисунок 1- Примитивы Хаара

Вычисляемым значением F признака Хаара будет

F = X — Y,

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

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

Классификатор строится на основе алгоритма бустинга (от англ. boost –улучшение, усиление) для выбора наиболее подходящих признаков для искомого объекта на данной части изображения. В общем случае бустинг — это комплекс методов, способствующих повышению точности аналитических моделей. Эффективная модель, допускающая мало ошибок классификации, называется «сильной». «Слабая» же, напротив, не позволяет надежно разделять классы или давать точные предсказания, делает большое количество ошибок. Поэтому бустинг означает «усиление» «слабых» моделей и является процедурой последовательного построения композиции алгоритмов машинного обучения, когда каждый следующий алгоритм стремится компенсировать недостатки композиции всех предыдущих алгоритмов.

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

p_j– направление знака неравенства, θ_j— значение порога, f_j(z)– вычисленное значение признака, z – окно изображения размером 24×24 пикселов.

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

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

Структура классификатора:

где maxWeakCount – количество слабых классификаторов;

stageThereshold – максимальный порог яркости;

weakClassifiers – набор слабых классификаторов, на основе которых выносится решение о том, находится объект на изображении или нет;

internalNodes и leafValues – параметры конкретного слабого классификатора.

Первые два значения в internalNodes не используются, третье — номер признака в общей таблице признаков (она располагается в XML-файле под тегом features), четвертое — пороговое значение слабого классификатора. Если значение признака Хаара меньше порога слабого классификатора, выбирается первое значение leafValues, если больше — второе.

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