Среда обнаружения объектов Виолы – Джонса - Viola–Jones object detection framework - Wikipedia

В Среда обнаружения объектов Виолы – Джонса является обнаружение объекта рамки, предложенные в 2001 г. Поль Виола и Майкл Джонс.^[1][2] Хотя его можно обучить обнаруживать различные классы объектов, в первую очередь он был мотивирован проблемой обнаружение лица.

Описание проблемы

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

Компоненты каркаса

Пример прямоугольных элементов, показанных относительно окружающего окна обнаружения

Типы функций и оценка

Характеристики алгоритма Виолы – Джонса, которые делают его хорошим алгоритмом обнаружения:

• Надежный - очень высокий уровень обнаружения (истинно-положительный результат) и всегда очень низкий уровень ложноположительных результатов.
• В реальном времени - для практических приложений необходимо обрабатывать не менее 2 кадров в секунду.
• Только распознавание лиц (не распознавание) - цель состоит в том, чтобы отличить лица от лиц, не являющихся лицами (обнаружение - это первый шаг в процессе распознавания).

Алгоритм состоит из четырех этапов:

1. Выбор функций Хаара
2. Создание целостного образа
3. Adaboost Обучение
4. Каскадные классификаторы

Признаки, которые ищет система обнаружения, обычно включают в себя суммы пикселей изображения в прямоугольных областях. Таким образом, они имеют некоторое сходство с Базисные функции Хаара, которые ранее использовались в области обнаружения объектов на основе изображений.^[3] Однако, поскольку все функции, используемые Виолой и Джонсом, основаны на более чем одной прямоугольной области, они, как правило, более сложные. На рисунке справа показаны четыре различных типа функций, используемых в платформе. Значение любой данной функции - это сумма пикселей в чистых прямоугольниках, вычтенная из суммы пикселей в затененных прямоугольниках. Прямоугольные элементы такого типа примитивны по сравнению с такими альтернативами, как управляемые фильтры. Хотя они чувствительны к вертикальным и горизонтальным особенностям, их обратная связь значительно грубее.

На лицо нанесена черта Хаара, похожая на переносицу.

На лице нанесена черта Хаара, похожая на область глаз, которая темнее верхней части щек.

3-й и 4-й вид особенности Хаара

Особенности Хаара

Все человеческие лица обладают некоторыми схожими свойствами. Эти закономерности можно сопоставить с помощью Особенности Хаара.

Несколько свойств, общих для человеческих лиц:

• Область глаз более темная, чем щеки.
• Область переносицы ярче глаз.

Состав свойств, формирующих совместимые черты лица:

• Расположение и размер: глаза, рот, переносица.
• Значение: ориентированные градиенты яркости пикселей

Затем на изображении лица (показано справа) ищутся четыре характеристики, соответствующие этому алгоритму.

Особенности прямоугольника:

• Значение = Σ (пиксели в черной области) - Σ (пиксели в белой области)
• Три типа: двух-, трех-, четырехугольники, Виола и Джонс использовали двухпрямоугольники.
• Например: разница в яркости между белым и черным прямоугольниками в определенной области.
• Каждая функция связана с определенным местом в подокне.

Таблица суммированных площадей

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

Алгоритм обучения

Однако скорость, с которой могут быть оценены характеристики, не может адекватно компенсировать их количество. Например, в стандартном подокне 24x24 пикселей в общей сложности M = 162,336^[4] возможные функции, и было бы непомерно дорого оценивать их все при тестировании изображения. Таким образом, в фреймворке обнаружения объектов используется вариант алгоритма обучения. AdaBoost как выбрать лучшие функции, так и обучить классификаторов, которые их используют. Этот алгоритм строит «сильный» классификатор как линейную комбинацию взвешенных простых «слабых» классификаторов.

${\displaystyle h(\mathbf {x} )=\operatorname {sgn} \left(\sum _{j=1}^{M}\alpha _{j}h_{j}(\mathbf {x} )\right)}$

Каждый слабый классификатор - это пороговая функция, основанная на признаке. ${\displaystyle f_{j}}$.

${\displaystyle h_{j}(\mathbf {x} )={\begin{cases}-s_{j}&{\text{if }}f_{j}<\theta _{j}\\s_{j}&{\text{otherwise}}\end{cases}}}$

Пороговое значение ${\displaystyle \theta _{j}}$ и полярность ${\displaystyle s_{j}\in \pm 1}$ определяются при обучении, а также коэффициенты ${\displaystyle \alpha _{j}}$.

Здесь представлена ​​упрощенная версия алгоритма обучения:^[5]

Вход: Набор из N позитивные и негативные обучающие изображения с их этикетками ${\displaystyle {(\mathbf {x} ^{i},y^{i})}}$. Если изображение я это лицо ${\displaystyle y^{i}=1}$, если не ${\displaystyle y^{i}=-1}$.

1. Инициализация: присвоить вес ${\displaystyle w_{1}^{i}={\frac {1}{N}}}$ к каждому изображению я.
2. Для каждой функции ${\displaystyle f_{j}}$ с ${\displaystyle j=1,...,M}$
   1. Перенормируйте веса так, чтобы они равнялись единице.
   2. Примените функцию к каждому изображению в обучающем наборе, затем найдите оптимальный порог и полярность. ${\displaystyle \theta _{j},s_{j}}$ что минимизирует ошибку взвешенной классификации. То есть ${\displaystyle \theta _{j},s_{j}=\arg \min _{\theta ,s}\;\sum _{i=1}^{N}w_{j}^{i}\varepsilon _{j}^{i}}$ куда ${\displaystyle \varepsilon _{j}^{i}={\begin{cases}0&{\text{if }}y^{i}=h_{j}(\mathbf {x} ^{i},\theta _{j},s_{j})\\1&{\text{otherwise}}\end{cases}}}$
   3. Назначьте вес ${\displaystyle \alpha _{j}}$ к ${\displaystyle h_{j}}$ что обратно пропорционально частоте ошибок. Таким образом считается больше лучших классификаторов.
   4. Веса для следующей итерации, т.е. ${\displaystyle w_{j+1}^{i}}$, уменьшаются для изображений я которые были правильно классифицированы.
3. Установите последний классификатор на ${\displaystyle h(\mathbf {x} )=\operatorname {sgn} \left(\sum _{j=1}^{M}\alpha _{j}h_{j}(\mathbf {x} )\right)}$

Каскадная архитектура

• В среднем только 0,01% всех подокон положительные (лица)
• Равное время вычислений тратится на все подокна
• Большую часть времени следует тратить только на потенциально положительные подокна.
• Простой классификатор с двумя объектами может обеспечить почти 100% -ный уровень обнаружения с 50% -ной частотой FP.
• Этот классификатор может выступать в качестве 1-го уровня в серии, чтобы отфильтровать большинство негативных окон.
• 2-й слой с 10 функциями может справиться с «более сложными» негативными окнами, которые пережили 1-й слой, и так далее ...
• Каскад постепенно усложняющихся классификаторов обеспечивает еще более высокие показатели обнаружения. Оценка сильных классификаторов, сгенерированных в процессе обучения, может быть выполнена быстро, но этого недостаточно, чтобы работать в режиме реального времени. По этой причине сильные классификаторы расположены в каскаде в порядке сложности, где каждый последующий классификатор обучается только на тех выбранных выборках, которые проходят через предыдущие классификаторы. Если на любом этапе каскада классификатор отклоняет проверяемое подокно, дальнейшая обработка не выполняется и продолжается поиск следующего подокна. Таким образом, каскад имеет форму вырожденного дерева. В случае лиц первый классификатор в каскаде, называемый оператором внимания, использует только две функции для достижения уровня ложноотрицательных результатов примерно 0% и 40% ложных срабатываний.^[6] Эффект от использования этого единственного классификатора состоит в сокращении примерно вдвое количества вычислений всего каскада.

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

Задача каждого этапа - определить, является ли данное подокно определенно лицом или может быть лицом. Данное подокно немедленно отбрасывается как не лицо, если оно выходит из строя на любом из этапов.

Ниже приводится простая структура для каскадного обучения:

• f = максимально допустимая частота ложных срабатываний на слой.
• d = минимально допустимая скорость обнаружения для каждого слоя.
• Ftarget = целевая общая частота ложных срабатываний.
• P = множество положительных примеров.
• N = набор отрицательных примеров.

F (0) = 1,0; D (0) = 1,0; я = 0пока F (i)> Ftarget увеличивать i n (i) = 0; F (я) = F (я-1) пока F (я)> f × F (я-1) увеличивать n (i) используйте P и N для обучения классификатора с n (I) функциями, используя AdaBoost        Оценить текущий каскадный классификатор на проверочном наборе для определения F (i) и D (i) снижаться порог для i-го классификатора (т.е. сколько слабых классификаторов нужно принять, чтобы сильный классификатор принял) до того как текущий каскадный классификатор имеет уровень обнаружения не менее d × D (i-1) (это также влияет на F (i)) N = ∅ если F (i)> Ftarget тогда         оценить текущий каскадный детектор на наборе изображений без лица и поместить любые ложные срабатывания в набор N.

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

${\displaystyle F=\prod _{i=1}^{K}f_{i}.}$

Точно так же коэффициент обнаружения:

${\displaystyle D=\prod _{i=1}^{K}d_{i}.}$

Таким образом, чтобы соответствовать уровню ложных срабатываний, обычно достигаемому другими детекторами, каждый классификатор может уйти с удивительно низкой производительностью. Например, для 32-ступенчатого каскада частота ложных срабатываний составляет 10⁻⁶, каждому классификатору требуется лишь около 65% ложных срабатываний. В то же время, однако, каждый классификатор должен обладать исключительными возможностями для достижения адекватных показателей обнаружения. Например, чтобы достичь уровня обнаружения около 90%, каждому классификатору в вышеупомянутом каскаде необходимо достичь уровня обнаружения около 99,7%.^[7]

Использование Виолы – Джонса для отслеживания объектов

В видеороликах с движущимися объектами нет необходимости применять обнаружение объекта к каждому кадру. Вместо этого можно использовать алгоритмы отслеживания, такие как KLT алгоритм для обнаружения характерных особенностей в пределах границ обнаружения и отслеживания их перемещения между кадрами. Это не только улучшает скорость отслеживания, устраняя необходимость повторного обнаружения объектов в каждом кадре, но также повышает надежность, поскольку основные функции более устойчивы, чем структура обнаружения Виолы-Джонса, к поворотам и фотометрическим изменениям.^[8]

Рекомендации

1. Быстрое обнаружение объектов с помощью усиленного каскада простых функций
2. Виола, Джонс: Надежное обнаружение объектов в реальном времени, IJCV 2001 См. Страницы 1,3.
3. К. Папагеоргиу, М. Орен и Т. Поджио. Общая структура для обнаружения объектов. Международная конференция по компьютерному зрению, 1998
4. «Распознавание лиц Виолы-Джонс требует 180 тысяч функций». stackoverflow.com. Получено 2017-06-27.
5. Р. Селиски, Компьютерное зрение, алгоритмы и приложения, Springer
6. Виола, Джонс: Надежное обнаружение объектов в реальном времени, IJCV 2001 См. Страницу 11.
7. Торберт, Шейн (2016). Прикладная информатика (2-е изд.). Springer. С. 122–131.
8. Обнаружение и отслеживание лиц с использованием алгоритма KLT

внешняя ссылка

• Слайды, представляющие структуру
• Информация о базисных функциях Хаара
• Расширение структуры Виолы – Джонса с помощью функции SURF
• IMMI - Расширение Rapidminer Image Mining - инструмент с открытым исходным кодом для интеллектуального анализа изображений
• Надежное обнаружение лица в реальном времени
• Улучшенный алгоритм детектора объектов Виолы-Джонса
• Цитирование алгоритма Виолы – Джонса в Google Scholar
• Видеолекция по алгоритму Виолы – Джонса на YouTube - Объяснение Adaboost из ppt Цин Чен, Discovery Labs, Университет Оттавы, и видеолекция Рамсри Гаутама.

Реализации

• Реализация алгоритма распознавания лиц Виолы – Джонса Оле Хельвиг Йенсен
• MATLAB: [1], [2]
• OpenCV: реализован как cvHaarDetectObjects ().
  • Обнаружение каскада Хаара в OpenCV
  • Каскадное обучение классификатора в OpenCV