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

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

Фреймворк обнаружения объектов Виолы–Джонса — это фреймворк обнаружения объектов машинного обучения, предложенный в 2001 году Полом Виолой и Майклом Джонсом . ^{[1] [2]} Он был в первую очередь мотивирован проблемой обнаружения лиц , хотя его можно адаптировать для обнаружения других классов объектов.

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

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

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

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

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

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

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

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

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

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

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

Полное представление алгоритма находится в ^{[3] .}

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

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

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

Классификаторы признаков Хаара

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

${\displaystyle 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}}}$

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

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

Каждый шаблон также должен быть симметричен относительно x-отражения и y-отражения (игнорируя изменение цвета), так, например, для горизонтальной бело-черной детали два прямоугольника должны быть одинаковой ширины. Для вертикальной бело-черно-белой детали белые прямоугольники должны быть одинаковой высоты, но ограничений на высоту черного прямоугольника нет.

На лицо наносится элемент Хаара, похожий на переносицу

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

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

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

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

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

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

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

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

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

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

Обучение

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

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

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

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

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

Однако скорость, с которой могут быть оценены признаки, не компенсирует их количество. Например, в стандартном подокне размером 24x24 пикселя существует всего M = 162336 ^[5] возможных признаков, и было бы непозволительно дорого оценивать их все при тестировании изображения. Таким образом, фреймворк обнаружения объектов использует вариант алгоритма обучения 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}}$

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

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

1. Инициализация: присвоить вес каждому изображению i . ${\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. Веса для следующей итерации, т.е. , уменьшаются для изображений i , которые были правильно классифицированы. ${\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 .
• Этот классификатор может действовать как первый слой серии для фильтрации большинства негативных окон.
• 2-й слой с 10 характеристиками может справиться с «более сложными» негативными окнами, которые выдержали 1-й слой, и так далее...
• Каскад постепенно усложняющихся классификаторов достигает еще лучших показателей обнаружения. Оценка сильных классификаторов, сгенерированных в процессе обучения, может быть выполнена быстро, но недостаточно быстро для работы в режиме реального времени. По этой причине сильные классификаторы организованы в каскад в порядке сложности, где каждый последующий классификатор обучается только на тех выбранных образцах, которые проходят через предыдущие классификаторы. Если на каком-либо этапе каскада классификатор отклоняет проверяемое подокно, дальнейшая обработка не выполняется и продолжается поиск следующего подокна. Таким образом, каскад имеет форму вырожденного дерева. В случае лиц первый классификатор в каскаде — называемый оператором внимания — использует только две функции для достижения ложноотрицательного уровня приблизительно 0% и ложноположительного уровня 40%. ^[7] Эффект этого одного классификатора заключается в сокращении примерно вдвое количества раз, когда оценивается весь каскад.

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

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

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

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

F(0) = 1,0; D(0) = 1,0; i = 0пока F(i) > Fцелевое увеличение i n(i) = 0; F(i) = F(i-1) пока F(i) > f × F(i-1) увеличивают n(i) используйте P и N для обучения классификатора с n(i) признаками с помощью AdaBoost Оценить текущий каскадный классификатор на проверочном наборе для определения F(i) и D(i) уменьшать пороговое значение для i-го классификатора (т.е. сколько слабых классификаторов необходимо принять, чтобы сильный классификатор принял) , пока текущий каскадный классификатор не будет иметь скорость обнаружения не менее d × D(i-1) (это также влияет на F(i)) Н = ∅ если 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%. ^[8]

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

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

Ссылки

1. Viola, P.; Jones, M. (2001). "Быстрое обнаружение объектов с использованием усиленного каскада простых признаков". Труды конференции IEEE Computer Society 2001 года по компьютерному зрению и распознаванию образов. CVPR 2001. Том 1. IEEE Comput. Soc. doi :10.1109/cvpr.2001.990517. ISBN 0-7695-1272-0. S2CID  2715202.
2. Виола, Пол; Джонс, Майкл Дж. (май 2004 г.). «Надежное обнаружение лиц в реальном времени». International Journal of Computer Vision . 57 (2): 137–154. doi :10.1023/b:visi.0000013087.49260.fb. ISSN  0920-5691. S2CID  2796017.
3. Ван, И-Цин (2014-06-26). «Анализ алгоритма обнаружения лиц Виолы-Джонса». Обработка изображений в режиме онлайн . 4 : 128–148. doi : 10.5201/ipol.2014.104 . ISSN  2105-1232.
4. C. Papageorgiou, M. Oren и T. Poggio. Общая структура для обнаружения объектов. Международная конференция по компьютерному зрению , 1998
5. "Распознавание лиц Виолы-Джонса заявляет о 180 тыс. функций". stackoverflow.com . Получено 27.06.2017 .
6. Р. Селиски, Компьютерное зрение, алгоритмы и приложения , Springer
7. Виола, Джонс: Надежное обнаружение объектов в реальном времени, IJCV 2001 См. стр. 11.
8. Торберт, Шейн (2016). Прикладная информатика (2-е изд.). Springer. С. 122–131.
9. Распознавание и отслеживание лиц с использованием алгоритма KLT

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

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

Реализации

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