Алгоритм Виолы-Джонса

Алгоритм Виолы-Джонса — это один из первых эффективных и быстрых алгоритмов компьютерного зрения, предназначенный для обнаружения объектов на цифровых изображениях в реальном времени. Разработанный в 2001 году Полом Виолой и Майклом Джонсом, алгоритм первоначально был ориентирован на распознавание лиц, но его принципы были адаптированы для поиска других объектов (например, автомобилей, пешеходов или улыбок). Основными особенностями алгоритма являются использование прямоугольных признаков Хаара, интегрального представления изображения для быстрого вычисления этих признаков, каскадная структура классификаторов и метод бустинга (AdaBoost) для отбора наиболее информативных признаков.

История

Алгоритм был представлен в 2001 году в статье Пола Виолы и Майкла Джонса «Robust Real-Time Face Detection» на конференции IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR). До этого момента существующие методы распознавания лиц, такие как нейронные сети или метод главных компонент (PCA), требовали значительных вычислительных ресурсов и не могли работать в реальном времени на оборудовании того времени. Виола и Джонс предложили комбинацию трёх ключевых идей, которые позволили достичь скорости обработки 15 кадров в секунду на стандартном процессоре Pentium III 700 МГц. В 2003 году алгоритм был запатентован в США (патент US 7,099,510 B2). Впоследствии он стал основой для многих библиотек компьютерного зрения, включая OpenCV, где реализован в виде детектора CascadeClassifier.

Принцип работы

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

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

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

Двухпрямоугольный (edge feature): разность сумм яркостей двух смежных прямоугольников (горизонтальных или вертикальных).
Трёхпрямоугольный (line feature): разность сумм яркостей центрального и двух боковых прямоугольников.
Четырёхпрямоугольный (four-rectangle feature): разность сумм яркостей диагональных пар прямоугольников.

Такие признаки позволяют выделять характерные контрасты, например, область глаз (более тёмная) и лба (более светлая) на лице человека. Размеры и положение признаков варьируются, что даёт огромное количество вариантов (для окна 24×24 пикселя — около 160 000 возможных признаков).

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

Для быстрого вычисления суммы яркостей в любом прямоугольнике используется интегральное изображение. Каждый его элемент I(x,y) содержит сумму яркостей всех пикселей исходного изображения, расположенных выше и левее данной точки (включительно). Формула: `` I(x,y) = sum_{i=0}^{x} sum_{j=0}^{y} img(i,j) ` При таком представлении сумма яркостей в любом прямоугольнике вычисляется за четыре операции обращения к памяти: S = I(A) + I(C) - I(B) - I(D)`, где A, B, C, D — углы прямоугольника. Это позволяет вычислять признаки Хаара за константное время, независимо от размера прямоугольника.

AdaBoost (Адаптивный бустинг)

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

Каждому обучающему примеру (изображению с лицом или без) присваивается вес.
На каждом шаге выбирается признак, который лучше всего разделяет примеры с учётом текущих весов (минимизирует ошибку).
Строится слабый классификатор h_j(x) с порогом θ_j и полярностью p_j (направление неравенства).
Веса ошибочно классифицированных примеров увеличиваются, чтобы следующий слабый классификатор фокусировался на сложных случаях.
Итоговый сильный классификатор H(x) — взвешенная сумма T слабых классификаторов: H(x) = sign( sum_{t=1}^{T} α_t * h_t(x) ), где α_t — вес, зависящий от точности h_t.

В результате из 160 000 признаков отбирается несколько сотен наиболее эффективных.

Каскадная структура

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

Первые стадии содержат небольшое количество признаков (например, 2–5) и быстро отбрасывают большинство окон, не содержащих объект (например, 99% фона).
Последующие стадии содержат больше признаков (десятки или сотни) и обрабатывают только те окна, которые прошли все предыдущие стадии.
Окно считается содержащим объект только в том случае, если оно успешно прошло все стадии каскада.

Такая структура позволяет резко сократить время обработки: на ранних этапах отбрасывается до 90% окон, и только на оставшиеся 10% тратятся более ресурсоёмкие вычисления. Типичный каскад для детекции лиц содержит 30–40 стадий.

Обучение

Для обучения алгоритма требуется большой набор данных:

Положительные примеры: изображения, содержащие искомый объект (например, лица), приведённые к единому размеру (обычно 24×24 пикселя).
Отрицательные примеры: изображения без объекта (фоны, пейзажи, текстуры).

Процесс обучения включает:

Сбор и нормализация обучающей выборки (выравнивание яркости, контраста).
Вычисление интегральных изображений для всех примеров.
Циклическое обучение стадий каскада с помощью AdaBoost.
Настройка порогов для каждой стадии так, чтобы обеспечить заданный уровень пропуска объектов (например, 99.9% истинных лиц должны быть пропущены) и уровень ложных срабатываний (например, 50% фона отбрасывается на каждой стадии).

Время обучения может составлять от нескольких часов до нескольких недель в зависимости от размера выборки и вычислительных мощностей.

Применение

Алгоритм Виолы-Джонса получил широкое распространение в системах, требующих быстрого обнаружения объектов:

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

Достоинства и недостатки

Достоинства

Высокая скорость: возможность работы в реальном времени (до 15–30 кадров/с на процессорах начала 2000-х годов).
Простота реализации: алгоритм не требует сложных математических операций, легко реализуется на CPU и FPGA.
Низкая вероятность пропуска объекта: каскадная структура и AdaBoost обеспечивают высокую чувствительность (до 95% для лиц).
Инвариантность к масштабу: обнаружение на всех масштабах изображения.

Недостатки

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

Интересные факты

Первоначально алгоритм был обучен на базе данных из 4916 положительных изображений лиц (включая вариации освещения и выражений) и 9544 отрицательных изображений.
В библиотеке OpenCV до версии 3.0 детектор Виолы-Джонса был единственным встроенным детектором лиц. Позднее его дополнили детекторами на основе HOG (гистограммы ориентированных градиентов) и глубокого обучения.
Алгоритм лёг в основу многих коммерческих продуктов, включая камеры веб-конференций и фотоаппараты.
Существуют модификации алгоритма, использующие признаки LBP (Local Binary Patterns) вместо признаков Хаара, что повышает устойчивость к изменениям освещения.

Источники

Viola, P., & Jones, M. (2001). Robust Real-Time Face Detection. International Journal of Computer Vision, 57(2), 137–154.
Viola, P., & Jones, M. (2003). Rapid Object Detection using a Boosted Cascade of Simple Features. Proceedings of the 2001 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR).
OpenCV documentation: Cascade Classifier Training.
Bradski, G., & Kaehler, A. (2008). Learning OpenCV: Computer Vision with the OpenCV Library. O'Reilly Media.

BFOmetr — база данных и аналитика по компаниям России.

На главную BFOmetr →