Каскад Хаара

Содержание

Гильза

  • Допустим, у нас есть один миллион изображений: полмиллиона изборажений мотоциклов и полмиллиона изображений не-мотоциклов (это называется обучающая выборка). В реальности, кстати, такая чудная ситуация (доля мотоциклов равно доле не-мотоциклов) бывает чрезвычайно редко.
  • Мы хотим научить компьютер отличать изображения мотоциклов от изображений не-мотоциклов. Для этого мы проводим обучение. Сначала мы «рассказываем» компьютеру, что является мотоциклом, а что не является. Это называется обучение с учителем, если компьютер неким образом сам смог бы научиться распознавать мотоциклы от не-мотоциклов без внешней помощи, то это было бы обучение без учителя: подробнее смотри статью: ...
  • После обучения бы даём компьютеру миллионпервое изображение, а компьютер выдаёт 1 («ДА», «ИСТИНА», «это мотоцикл»), если это изображение мотоцикла, и -1 («НЕТ», «ЛОЖЬ», «это не-мотоцикл»), если это изображение не-мотоцикла. В реальной практике мы даём не одно изображение, а, допустим, сто тысяч (эти сто тысяч называются тестовой выборкой). По тому, как компьютер научился разделять мотоциклы от не-мотоциклов, мы судим о качестве нашего обучения. Для этого чаще всего используются следующие показатели:
    • доля верно определённых мотоциклов (на изображении мотоцикл, компьютер определил его как мотоцикл: TP — True Positive),
    • доля верно определённых не-мотциклов (на изображении не-мотоцикл, компьютер определел его не-мотоцикл: TN — True Negative),
    • доля неверно определённых не-мотоциклов (на изображении не-мотоцикл, но компьютер ошибся и определил его как мотоцикл: FP — False Positive): например, мы не научили различать мотоциклы и велосипеды,
    • доля неверно определённых мотоциклов (на изображении мотоцикл, компьютер его определил как не-мотоцикл: FN — False Negative): например, мы не научили различать мотоциклы с человеком на нём, обучали только по мотоциклам без водителя.
  • Таким образом, компьютер проводит разделение поступающего множество на два класса, или, говоря иначе, выполняет задачу классификации.
  • В данной статье рассматривается метод обучения с учителем, называемый «каскады Хаара».
  • Потом, в режиме понимания слушателем, проводится описание алгоритма.

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

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

  • «В данном случае используется обучение с учителем»: читатель вообще может не понимать, что такое обучение с учителем (и не знать, чем оно отличается от обучения без учителя). В одном научном журнале по точных наукам на фразу «Это алгоритм обучения без учителя» мне ответили: «Мы не публикуем статьи по педагогике». -- АтрашкевичАндрей

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

  • «имеет неплохую устойчивость к шумам и другим отклонениям»: неплохую по отношению к чему? что есть шум? что за отклонения? -- АтрашкевичАндрей

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

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

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

К примеру, на изображении белые прямоугольники ‒ это первая группа группа областей, а черные ‒ вторая. Значение признака Хаара ‒ это разность сумм яркостей пикселей первой и второй группы. В математической форме это будет выглядеть так: 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, ~ roman \\\"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-му обучающему примеру.
  • m ‒ число отрицательных примеров.
  • l ‒ число положительных примеров.
  • epsilon sub i ‒ ошибка i-го слабого классификатора.
  • {h dot} sub i ‒ слабый классификатор, выбранный на i-й итерации.
  • epsilon dot ‒ минимальное значение ошибки слабого классификатора на текущей итерации.
  • beta sub i ‒ минимальное значение ошибки слабого классификатора на i-й итерации, представленное в другой форме (для оптимизации вычислений и экономии места).

Алгоритм:

  • Инициализировать веса обучающих примеров:
left { lpile { w sub i = size -2 {1 over 2m}, if~y sub i = 0 above w sub i = size -2 {1 over 2l}, if~y sub i = 1 } right \\\"\\\" ~,
  • Для t = 1, .., T:
    1. Нормализовать веса обучающих примеров:
w sub i = size -2 {{w sub i} over {sum from {j^=^1} to n {w sub j}}}
  1. Вычислить значение ошибки для каждого слабого классификатора:
epsilon sub j = sum from k to n {{w sub k}|{h sub j}({E sub k}) - {y sub k}}|
  1. Hайти классификатор с минимальной ошибкой:
{epsilon dot} = min {epsilon sub j} ~,~~~ {{h dot} sub t} = h sub j
  1. Обновить веса обучающих примеров:
beta sub t = size -2 {{{epsilon dot}} over {(1 - {epsilon dot})}} ~,~~~ w sub i = {w sub i} {beta sub t} sup {1^-^{|{{h dot} sub t}({E sub i})^-^{y sub i}}|}
  • Итоговый конечный классификатор:
H(x) = left { lpile { 1, ~ sum from {t = 1} to T {log({size -2 {1 over {beta sub t}}}) {h dot} sub t}({E sub i}) >= sum from {t = 1} to T {log({size -2 {1 over {beta sub t}}})} above 0, ~ roman \\\"otherwise\\\" } right \\\"\\\"

Каскад классификаторов.


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