Это старая версия (1.37) КаскадХаара.

Содержание

Каскад Хаара

Формально говоря, каскад Хаара выполняет задачу классификации ‒ разделения множества объектов на классы. В нашем случае объекты - это входные изображения. А класса всего два: искомый объект и все остальное. Говоря проще, каскад Хаара принимает на вход изображение и выдает один из двух ответов: "да" и "нет".

Что бы каскад Хаара определял, есть ли искомый объект на входном изображении, его нужно обучить. Тоесть, задать ему такую структуру, что бы он выдавал положительный результат для изображений с искомым объектом, и отрицательный в другом случае. В данном случае используется обучение с учителем, т.е. имеется обучающая выборка (набор разных изображений) и данные, указывающие, какие из этих изображений содержат искомый объект. Обучение может занимать очень много времени: иногда даже по несколько дней.

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

Признаки Хаара.

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

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

К примеру, на изображении белые прямоугольники ‒ это первая группа группа областей, а черные ‒ вторая. Значение признака Хаара ‒ это разность сумм яркостей пикселей первой и второй группы. В математической форме это будет выглядеть так: a sub i = sum from {i={y sub a sub i}} to {{y sub a sub i}+{h sub a sub i}-1} ~~ sum from {j^=^{x sub a sub i}} to {{x sub a sub i}+{w sub a sub i}-1} x sub {i j} b sub i = sum from {i={y sub b sub i}} to {{y sub b sub i}+{h sub b sub i}-1} ~~ sum from {j^=^{x sub b sub i}} to {{x sub b sub i}+{w sub b sub i}-1} x sub {i j} ~~~~~~~~ h = sum from {i ^ = ^ 1} to {{N sub a}} {a sub i} - sum from {i ^ = ^ 1} to {{N sub b}} {b sub i} ~,

где x sub ij ‒ яркость пискеля изображения с координатами \[i, j\], a sub i ‒ сумма яркостей пикселей в i-й области первой группы, b sub i ‒ сумма яркостей пикселей в i-й области второй группы, h ‒ значение признака Хаара для этого изображения, h sub a sub i ‒ высота i-й области первой группы, w sub a sub i ‒ ширина i-й области первой группы, h sub b sub i ‒ высота i-й области второй группы, w sub b sub i ‒ ширина i-й области второй группы, N sub a ‒ количество областей первой группы, N sub b ‒ количество областей второй группы, а h ‒ значение признака Хаара для этого изображения.

Интегральная форма представления изображения.

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

В интегральной форме изображения значение каждого пикселя является суммой яркостей этого пикселя и всех пикселей, что находятся выше и левее него (если пиксель с координатами \[1; 1\] находится в верхнем левом углу изображения): S sub {yx} = sum from {i^=^1} to {y} sum from {j^=^1} to {x} {x sub ij} ~,

где S sub yx ‒ значение пикселя интегральной формы изображения с координатами \[y; x\], а x sub ij ‒ значение пикселя исходного изображения с координатами \[i; j\].

Переведя изображение в интегральную форму, можно вычислять значения признаков Хаара для него, не выполняя суммирование всех требуемых значений яркостей каждый раз по новой. Достаточно посчитать сумму яркостей для каждой прямоугольной области, используя свойства интегральной формы изображения: left { lpile { a sub i = S\[{{y sub a sub i} + h sub a sub i};{{x sub a sub i} + w sub a sub i}\] above a sub i = S\[{{y sub a sub i} + h sub a sub i};{{x sub a sub i} + w sub a sub i}\] - S\[{{y sub a sub i} + h sub a sub i};{x sub a sub i}\] above a sub i = S\[{{y sub a sub i} + h sub a sub i};{{x sub a sub i} + w sub a sub i}\] - S\[{y sub a sub i};{{x sub a sub i} + w sub a sub i}\] above a sub i = S\[{{y sub a sub i} + h sub a sub i};{{x sub a sub i} + w sub a sub i}\] - S\[{y sub a sub i};{{x sub a sub i} + w sub a sub i}\] - S\[{{y sub a sub i} + h sub a sub i};{x sub a sub i}\] + S\[{y sub a sub i};{x sub a sub i}\] } lpile { , y = 1, x = 1 above , y > 1, x = 1 above , y = 1, x > 1 above , y > 1, x > 1 } right \\\"\\\" left { lpile { b sub i = S\[{{y sub b sub i} + h sub b sub i};{{x sub b sub i} + w sub b sub i}\] above b sub i = S\[{{y sub b sub i} + h sub b sub i};{{x sub b sub i} + w sub b sub i}\] - S\[{{y sub b sub i} + h sub b sub i};{x sub b sub i}\] above b sub i = S\[{{y sub b sub i} + h sub b sub i};{{x sub b sub i} + w sub b sub i}\] - S\[{y sub b sub i};{{x sub b sub i} + w sub b sub i}\] above b sub i = S\[{{y sub b sub i} + h sub b sub i};{{x sub b sub i} + w sub b sub i}\] - S\[{y sub b sub i};{{x sub b sub i} + w sub b sub i}\] - S\[{{y sub b sub i} + h sub b sub i};{x sub b sub i}\] + S\[{y sub b sub i};{x sub b sub i}\] } lpile { , y = 1, x = 1 above , y > 1, x = 1 above , y = 1, x > 1 above , y > 1, x > 1 } right \\\"\\\"

где S\[y;x\] ‒ значение пикселя интегральной формы изображения. Далее можно вычислить значение признака Хаара как обычно: h = sum from {i^=^1} to {{N sub a}} {a sub i} - sum from {i^=^1} to {{N sub b}} {b sub i} ~,

Пример: для того, что бы вычислить сумму значений пикселей в прямоугольнике D, изображенном на рисунке можно использовать интегральную форму изображения: в ней точка a будет являться суммой значений пикселей в прямоугольнике A, точка b ‒ суммой значений пикселей в прямоугольниках A и B, точка c ‒ суммой значений пикселей в прямоугольниках A и C, а точка d ‒ суммой значений пикселей в прямоугольниках A, B, C и D. Тогда сумма значений пикселей в прямоугольнике D будет равна d - c - b + a.

Алгоритм AdaBoost.

Для выбора признаков, лучше всего классифицирующих изображения используется алгоритм AdaBoost (adaptive boosting). Этот алгоритм построен на идее, что из большого числа простых способов классификации (называемых слабыми классификаторами) можно составить, новый способ, выполняющий эту задачу намного эффективнее.

В данном случае слабый классификатор ‒ это функция, которая принимает на вход изображение, вычисляет значение соответствующего ей признака Хаара для этого изображения и сравнивет это значение с порогом, возвращая либо 0, либо 1. {h sub i}(x) = left { lpile { 1, {p sub i}{f sub i}(x) < {p sub i}{theta sub i} above 0, otherwise } right \\\"\\\" ~,

где theta sub i ‒ порог, x ‒ входное изображение, {f sub i}(x) ‒ результат вычисления значения соотвествующего признака Хаара для изображения x, p sub i ‒ направление знака неравенства, а {h sub i}(x) ‒ слабый классификатор.

p sub i принимает одно из двух значений: 1 или -1. Если оно равно 1, ничего не меняется, если же оно равно -1, знак неравенства начинает работать в обратную сторону. Такая запись используется, из-за своей краткости, а так же потому, что при реализации на некоторых архитектурах, операция умножения работает намного быстрее, чем условные операторы.

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

Входные данные:

h sub i ‒ i-й слабый классификатор. E sub i ‒ i-й обучающий пример. y sub i ‒ 0, если i-й обучающий пример отрицательный, и 1, если i-й обучающий пример положительный. n ‒ количество обучающих примеров.

Переменные:

w sub i ‒ вес, соответствующий i-му обучающему примеру. epsilon sub i ‒ ошибка i-го слабого классификатора. {h dot} sub i ‒ слабый классификатор, выбранный на i-й итерации. epsilon dot ‒ минимальное значение ошибки слабого классификатора на текущей итерации. beta sub i ‒ минимальное значение ошибки слабого классификатора на i-й итерации, представленное в другой форме (для оптимизации вычислений и экономии места на бумаге).

КатегорияМашинноеОбучение