Система обнаружения объектов Виолы – Джонса

Структура обнаружения объектов Виолы-Джонса — это машинного обучения структура обнаружения объектов , предложенная в 2001 году Полом Виолой и Майклом Джонсом . Это было мотивировано в первую очередь проблемой обнаружения лиц , хотя его можно адаптировать и для обнаружения других классов объектов.

Алгоритм эффективен для своего времени: он способен распознавать лица на изображениях размером 384х288 пикселей со скоростью 15 кадров в секунду на обычном процессоре Intel Pentium III с частотой 700 МГц . Он также надежен и обеспечивает высокую точность и полноту данных .

Хотя он имеет меньшую точность, чем более современные методы, такие как сверточная нейронная сеть , его эффективность и компактный размер (всего около 50 тысяч параметров по сравнению с миллионами параметров для типичных CNN, таких как DeepFace ) означают, что он все еще используется в случаях с ограниченной вычислительной мощностью. Например, в оригинальной статье они сообщили, что этот детектор лиц может работать на Compaq iPAQ со скоростью 2 кадра в секунду (это устройство имеет маломощный StrongARM без оборудования с плавающей запятой).

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

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

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

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

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

Требование «фронтального» изображения не подлежит обсуждению, поскольку не существует простой трансформации изображения, которая могла бы превратить лицо из вида сбоку в вид спереди. Однако можно обучить несколько классификаторов Виолы-Джонса, по одному для каждого угла: один для вида спереди, один для вида 3/4, один для вида в профиль и еще несколько для углов между ними. Тогда можно во время выполнения выполнять все эти классификаторы параллельно, чтобы обнаруживать лица под разными углами обзора.

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

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

Полная презентация алгоритма здесь.

Рассмотрите изображение $I(x,y)$ фиксированного разрешения $(M,N)$. Наша задача — принять бинарное решение: фотография стандартизированного лица (фронтального, хорошо освещенного и т. д.) или нет.

Виола-Джонс, по сути, представляет собой усиленный алгоритм обучения признакам , обученный путем запуска модифицированного алгоритма AdaBoost на классификаторах признаков Хаара для поиска последовательности классификаторов. $f_{1},f_{2},...,f_{k}$. Классификаторы признаков Хаара являются грубыми, но позволяют выполнять очень быстрые вычисления, а модифицированный AdaBoost создает сильный классификатор из множества слабых.

Во время выполнения данное изображение $I$ тестируется на $f_{1}(I),f_{2}(I),...f_{k}(I)$ последовательно. Если в какой-то момент $f_{i}(I)=0$, алгоритм немедленно возвращает «лицо не обнаружено». Если все классификаторы возвращают 1, алгоритм возвращает «обнаружено лицо». По этой причине классификатор Виолы-Джонса также называют «каскадным классификатором Хаара».

Ее классификаторы функций

Рассмотрим персептрон $f_{w,b}$ определяется двумя переменными $w(x,y),b$. Он принимает изображение $I(x,y)$ фиксированного разрешения и возвращает

$f_{w,b}(I)={\begin{cases}1,\quad {\text{if }}\sum _{x,y}w(x,y)I(x,y)+b>0\\0,\quad {\text{else}}\end{cases}}$

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

Классификатор признаков Хаара представляет собой персептрон. $f_{w,b}$ с совершенно особым видом $w$ это делает расчет чрезвычайно дешевым. А именно, если выписать матрицу $w(x,y)$, мы обнаруживаем, что оно принимает только три возможных значения $\{+1,-1,0\}$, а если раскрасить матрицу в белый цвет на $+1$, черный на $-1$и прозрачный на $0$, матрица относится к одному из 5 возможных шаблонов, показанных справа.

Каждый шаблон также должен быть симметричен отражению по оси X и по оси Y (без учета изменения цвета), поэтому, например, для горизонтального бело-черного объекта два прямоугольника должны быть одинаковой ширины. Для вертикального объекта «белый-черный-белый» белые прямоугольники должны быть одинаковой высоты, но высота черного прямоугольника не ограничена.

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

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

Обоснование ее особенностей

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

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

• Область глаз темнее верхней части скул.
• Область переносицы светлее глаз.

Состав свойств, образующих подходящие черты лица:

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

Кроме того, конструкция функций Хаара позволяет эффективно вычислять $f_{w,b}(I)$ используя только постоянное количество сложений и вычитаний, независимо от размера прямоугольных объектов, используя таблицу суммируемых площадей .

Изучение и использование классификатора Виолы – Джонса.

Выберите разрешение $(M,N)$ для классификации изображений. В оригинальной статье они рекомендовали $(M,N)=(24,24)$.

Обучение

Соберите обучающий набор, некоторые из которых содержат лица, а другие не содержат лиц. Выполните определенное модифицированное обучение AdaBoost на наборе всех классификаторов признаков Хаара размерности. $(M,N)$, пока не будет достигнут желаемый уровень точности и полноты. Модифицированный алгоритм AdaBoost будет выводить последовательность классификаторов объектов Хаара. $f_{1},f_{2},...,f_{k}$.

Подробности модифицированного алгоритма AdaBoost подробно описаны ниже.

С использованием

Чтобы использовать классификатор Виолы-Джонса с $f_{1},f_{2},...,f_{k}$ на изображении $I$, вычислить $f_{1}(I),f_{2}(I),...f_{k}(I)$ последовательно. Если в какой-то момент $f_{i}(I)=0$, алгоритм немедленно возвращает «лицо не обнаружено». Если все классификаторы возвращают 1, алгоритм возвращает «обнаружено лицо».

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

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

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

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

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

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

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

Входные данные: набор из N положительных и отрицательных тренировочных изображений с их метками. ${(\mathbf {x} ^{i},y^{i})}$. Если изображение i — лицо $y^{i}=1$, если нет $y^{i}=-1$.

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

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

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

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

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

Простая схема каскадного обучения приведена ниже:

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

F(0) = 1.0; D(0) = 1.0; i = 0

while F(i) > Ftarget
    increase i
    n(i) = 0; F(i)= F(i-1)

    while F(i) > f × F(i-1)
        increase n(i)
        use P and N to train a classifier with n(i) features using AdaBoost
        Evaluate current cascaded classifier on validation set to determine F(i) and D(i)
        decrease threshold for the ith classifier (i.e. how many weak classifiers need to accept for strong classifier to accept)
            until the current cascaded classifier has a detection rate of at least d × D(i-1) (this also affects F(i))
    N = ∅
    if F(i) > Ftarget then 
        evaluate the current cascaded detector on the set of non-face images 
        and put any false detections into the set N.

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

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

Аналогично, скорость обнаружения равна:

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

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

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

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

Внешние ссылки

• Слайды, представляющие структуру
• Информация о его основных функциях
• «Расширение платформы Виолы – Джонса с использованием функции SURF» . Архивировано из оригинала 18 октября 2020 г.
• «IMMI — расширение для интеллектуального анализа изображений Rapidminer» . Архивировано из оригинала 3 июля 2022 г. - инструмент с открытым исходным кодом для интеллектуального анализа изображений
• «Надежное распознавание лиц в реальном времени» (PDF) . Архивировано из оригинала (PDF) 02 февраля 2019 г.
• Улучшенный алгоритм детектора объектов Виолы-Джонса.
• Цитаты алгоритма Виолы – Джонса в Google Scholar
• Видеолекция по алгоритму Виолы – Джонса на YouTube - Объяснение Adaboost на основе презентации Цин Чена, Discovery Labs, Университет Оттавы, и видеолекции Рамсри Гаутама.

Реализации

• Дженсен, Оле Хельвиг. «Реализация алгоритма распознавания лиц Виолы – Джонса» (PDF) . Архивировано из оригинала (PDF) 21 октября 2018 г.
• MATLAB: [1] , [2] Архивировано 7 сентября 2017 г. в Wayback Machine.
• OpenCV: реализован как cvHaarDetectObjects().
  • Обнаружение каскада волос в OpenCV
  • Обучение каскадному классификатору в OpenCV