Выделение объектов на изображении по методу Виолы-Джонса (Object selection in the image according to the Viola-Jones method)

Автор: | 16.12.2018

Объекты (например, лица) выделяются, если признаки в сканирующем окне совпадают с признаками на выделенной окном части изображения:

Этот подход к детектированию объектов на изображении комбинирует четыре ключевые концепции:

Результаты обучения каскадов складываются в виде классификаторов Хаара в файле XML-формата.

Функции Хаара

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

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

 

Наличие функции Хаара определяется посредством вычитания среднего значения области светлых пикселей из среднего значения области темных пикселей

Fhaar = Rwhite – Rblack

Если разница превышает порог (определяется в процессе обучения), тогда говорят, что функция существует.

Интегральное изображение

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

Интегральное значение для каждого пикселя есть сумма значений всех пикселей над ним и слева от него

Рассмотрим пример использования технологии Интегрального изображения

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

  • A+B+C+D  –  в положении 4;
  • A+B  – в положении 2;
  • A+C –  в положении 3;
  • А – в положении 1.

А что если вас интересует суммированные значения для некоторых других прямоугольников, которые не имеют ни одного угла в левой верхней части изображения?  Предположим, вам нужно узнать сумму пиксельных значений в области D. В области D сумма пиксельных значений также определяется просто  —  всего тремя целочисленными операциями:

(x4,y4) — (x2,y2) — (x3,y3) + (x1,y1).

Метод машинного обучения AdaBoost

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

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

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

где

pj показывает направление знака неравенства;

pj – значение порога;

fj(z) – вычисленное значение признака;

 z – окно изображения размером 20×20 пикселей.

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

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

 

Рассмотрим работу этого алгоритма на примере классификации знаков (см. рисунки). Предположим, что наши слабые классификаторы — это вертикальные или горизонтальные линии.

 

 

 

Суммарный классификатор

Каскадный классификатор

Виола и Джонс объединили серии классификаторов AdaBoost как последовательность фильтров. Каждый фильтр является отдельным классификатором AdaBoost с достаточно небольшим числом слабых классификаторов.

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

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

Порядок фильтров в каскаде основывается на весовом значении, которые присваивает AdaBoost. Более тяжелые взвешенные фильтры идут в первую очередь, с целью как можно более быстрого устранения «не лицевых» областей изображения. Рисунок ниже показывает первые две функции из искомого каскада Виолы-Джонса, наложенные на лицо. Первый настраивает дальнюю область щек более «светлой», чем область глаз. Второй использует факт того, что носовая перегородка более светлая, чем глаза.

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

Описание каскада признаков в XML-файле

Результаты обучения каскадов складываются в виде классификаторов Хаара в файле XML-формата.  Структура XML-файла представлена рисунке.

В каскаде существует множество уровней (stages), каждый из которых содержит множество деревьев (trees).

Рассмотрим, как описываются признаки в XML-файле.

<_>

<!-- root node -->

    <feature>

      <rects>

        <_>3 7 14 4 -1.</_>

        <_>3 9 14 2 2.</_></rects>

      <tilted>0</tilted></feature>

    <threshold>4.0141958743333817e-003</threshold>

    <left_val>0.0337941907346249</left_val>

    <right_val>0.8378106951713562</right_val></_></_>

<_>

Каскад Хаара состоит из детекторов признаков (feature), которые представляют 2 или 3 прямоугольные области изображения, каждая из которых описывается 5 параметрами. Для рассматриваемого примера 3  7 – координаты  1-го прямоугольника, начиная с верхнего левого угла, 14 – его ширина, 4 – высота, -1 – вес прямоугольника. Второй прямоугольник начинается в точке (3,9), имеет ширину 14 пикселов и высоту 2 пиксела, вес у него 2. Прямоугольники расположены в пределах размеров (size) детектора (20,20). Как видно из рис., прямоугольники перекрываются и образуют детектор горизонтальной границы, как показано ниже

 

Цвет прямоугольников выбирается в соответствии с весами прямоугольников (5-й параметр для тегов rects). Там, где прямоугольники перекрываются, вес (множитель) пикселов определяется суммированием весов прямоугольников

Признаки группируются в этапы (Stages). Для каждого этапа в каскаде хранится пороговое значение (threshold). Для каждого признака хранятся два критических значения left и right.

Для каждого признака из каскада считается нормированное значение sum_feature*win_norm и сравнивается с нормированным критическим значением, записанным в каскаде feature− > tℎresℎold * stddev. В случае, если значение меньше критического, к значению стадии прибавляется значение из левого поддерева признака, в противном — из правого. Значение sum_feature считается как сумма яркостей пикселей, которые попадают в прямоугольную область внутри признака, умноженная на вес области. Координаты области умножаются на win_scale.

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

 

Полезные ссылки:

  1. A guide to Face Detection in Python
  2. AdaBoost Tutorial
  3. Upgrade Viola Jones
  4. Как работает компьютерное распознавание лиц
  5. Метод Виолы-Джонса (Viola-Jones) как основа для распознавания лиц

 

 

Автор: Николай Свирневский

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *