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

Для того, чтобы производить какие-либо действия с данными, используется интегральное представление изображений [3] в методе Виолы-Джонса. Такое представление используется часто и в других методах, к примеру, в вейвлет-преобразованиях, SURF и многих других разобранных алгоритмах. Интегральное представление позволяет быстро рассчитывать суммарную яркость произвольного прямоугольника на данном изображении, причем какой бы прямоугольник не был, время расчета неизменно.
Интегральное представление изображения – это матрица, совпадающая по размерам с исходным изображением. В каждом элементе ее хранится сумма интенсивностей всех пикселей, находящихся левее и выше данного элемента. Элементы матрицы рассчитываются по следующей формуле:
(1.2)
где I(i,j) — яркость пикселя исходного изображения.
Каждый элемент матрицы L[x,y] представляет собой сумму пикселей в прямоугольнике от (0,0) до (x,y), т.е. значение каждого пикселя (x,y) равно сумме значений всех пикселов левее и выше данного пикселя (x,y). Расчет матрицы занимает линейное время, пропорциональное числу пикселей в изображении, поэтому интегральное изображение просчитывается за один проход.
Расчет матрицы возможен по формуле 1.3:
L(x,y) = I(x,y) – L(x-1,y-1) + L(x,y-1) + L(x-1,y) (1.3)
По такой интегральной матрице можно очень быстро вычислить сумму пикселей произвольного прямоугольника, произвольной площади.
Пусть в прямоугольнике ABCD есть интересующий нас объект D:

Из рисунка понятно, что сумму внутри прямоугольника можно выразить через суммы и разности смежных прямоугольников по следующей формуле:
S(ABCD) = L(A) + L(С) — L(B) — L(D) (1.4)
Примерный просчет показан на рисунке ниже:

 

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

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

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

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

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

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

Признак — отображение f: X => D_f, где D_f — множество допустимых значений признака. Если заданы признаки f₁,…,f_n, то вектор признаков x = (f₁(x),…,f_n(x)) называется признаковым описанием объекта x ∈ X. Признаковые описания допустимо отождествлять с самими объектами. При этом множество X = D_f1* …* D_fn называют признаковым пространством [1].
Признаки делятся на следующие типы в зависимости от множества D_f:

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

В расширенном методе Виолы – Джонса, использующемся в библиотеке OpenCV используются дополнительные признаки.

Вычисляемым значением такого признака будет
F = X-Y, (1.5)
где X – сумма значений яркостей точек закрываемых светлой частью признака, а Y – сумма значений яркостей точек закрываемых темной частью признака. Для их вычисления используется понятие интегрального изображения, рассмотренное выше.
Признаки Хаара дают точечное значение перепада яркости по оси X и Y соответственно.

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

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

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

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

F=X-Y

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

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

Сканирование окна

Визуализация сканирующего окна в программе:

Алгоритм сканирования окна с признаками выглядит так:

• есть исследуемое изображение, выбрано окно сканирования, выбраны используемые признаки;
• далее окно сканирования начинает последовательно двигаться по изображению с шагом в 1 ячейку окна (допустим, размер самого окна есть 24*24 ячейки);
• при сканировании изображения в каждом окне вычисляется приблизительно 200 000 вариантов расположения признаков, за счет изменения масштаба признаков и их положения в окне сканирования;
• сканирование производится последовательно для различных масштабов;
• масштабируется не само изображение, а сканирующее окно (изменяется размер ячейки);
• все найденные признаки попадают к классификатору, который «выносит вердикт».

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