Каскады Хаара

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

История

Идея использования прямоугольных признаков для анализа изображений восходит к работам Альфреда Хаара (венгерского математика), который в 1909 году предложил систему функций (вейвлеты Хаара) для представления сигналов. Однако применительно к компьютерному зрению эти признаки были адаптированы значительно позже.

В 2001 году исследователи Пол Виола и Майкл Джонс (в то время работавшие в корпорации Compaq) опубликовали статью «Robust Real-Time Face Detection» (Надёжное обнаружение лиц в реальном времени). В ней они представили три ключевых нововведения:

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

Этот алгоритм, часто называемый детектором Виолы-Джонса, стал первым, способным обнаруживать лица в реальном времени на стандартных для того времени процессорах (например, с частотой 700 МГц). Позднее метод был усовершенствован и адаптирован для обнаружения других объектов: пешеходов, автомобилей, номерных знаков, глаз, улыбок и т.д.

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

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

Признак Хаара представляет собой шаблон, состоящий из нескольких смежных прямоугольных областей (обычно белого и чёрного цвета). Значение признака вычисляется как разность суммы яркостей пикселей в белых областях и суммы яркостей в чёрных областях. Для ускорения вычислений используется интегральное изображение. Существует несколько типов базовых признаков:

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

Например, признак для обнаружения границы между лбом и глазами на лице человека: область вокруг глаз (тёмная) и область лба (светлая) дают большую разницу яркостей.

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

Интегральное изображение — это матрица, каждый элемент которой равен сумме яркостей всех пикселей исходного изображения, расположенных выше и левее данного элемента. Для вычисления суммы пикселей в произвольном прямоугольнике достаточно четырёх обращений к интегральному изображению (сложений и вычитаний). Это позволяет рассчитывать признаки Хаара за константное время, что критически важно для работы в реальном времени.

Обучение с помощью AdaBoost

Алгоритм AdaBoost (Adaptive Boosting) используется для отбора наиболее информативных признаков и построения сильного классификатора из множества слабых классификаторов. Каждый слабый классификатор — это простой пороговый классификатор, основанный на одном признаке Хаара. В процессе обучения на большом наборе положительных (содержащих искомый объект) и отрицательных (не содержащих) изображений AdaBoost последовательно выбирает признаки, которые лучше всего разделяют классы, и назначает им веса. Итоговый сильный классификатор представляет собой взвешенную сумму слабых классификаторов.

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

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

Сканирующее окно фиксированного размера (например, 24×24 пикселя) перемещается по изображению с определённым шагом.
Для каждого положения окна вычисляются признаки Хаара, и окно последовательно проходит через все этапы каскада.
Если на любом этапе классификатор даёт отрицательный ответ (объект не обнаружен), окно немедленно отбрасывается, и дальнейшие вычисления для него не производятся.
Если окно успешно проходит все этапы, оно считается содержащим искомый объект.

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

Характеристики и ограничения

Преимущества

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

Недостатки

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

Применение

Обнаружение лиц

Наиболее известное применение каскадов Хаара. Используется в:

Фотоаппаратах и смартфонах для автофокусировки по лицу и создания портретных режимов.
Системах видеонаблюдения для подсчёта посетителей, поиска людей по базе данных.
Программном обеспечении для обработки фотографий (например, для автоматического выделения лиц).
Социальных сетях и приложениях для добавления масок и фильтров (например, Snapchat, Instagram*).

Другие области

Обнаружение пешеходов — в системах помощи водителю (ADAS) и автономных автомобилях.
Обнаружение автомобилей — для систем управления дорожным движением и парковки.
Обнаружение номерных знаков — в системах автоматической фиксации нарушений ПДД.
Обнаружение глаз и улыбок — в интерфейсах человеко-машинного взаимодействия.
Медицинская диагностика — для обнаружения аномалий на рентгеновских снимках (например, узлов в лёгких).

Современное состояние и развитие

Метод каскадов Хаара, несмотря на свою эффективность, в значительной степени уступил место более современным подходам, основанным на глубоком обучении, в частности, свёрточным нейронным сетям (CNN) и детекторам типа YOLO, SSD, Faster R-CNN. Эти методы обеспечивают значительно более высокую точность и устойчивость к поворотам, масштабу и частичным перекрытиям.

Тем не менее, каскады Хаара остаются востребованными в задачах, где критичны минимальные вычислительные затраты и простота реализации, например:

Во встраиваемых системах с ограниченными ресурсами (микроконтроллеры, Raspberry Pi).
В мобильных приложениях, где требуется быстрая обработка без использования GPU.
В образовательных целях для изучения основ компьютерного зрения.

Библиотека OpenCV (Open Source Computer Vision Library) включает в себя готовые реализации детектора Виолы-Джонса и предобученные каскады для обнаружения лиц, глаз, улыбок, профилей и других объектов. Эти каскады широко используются в прототипировании и промышленных решениях.

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

Оригинальный детектор Виолы-Джонса обрабатывал изображение размером 384×288 пикселей со скоростью 15 кадров в секунду на процессоре 700 МГц.
Для обучения каскада на обнаружение лиц использовалось около 5000 положительных изображений (лиц) и 10 000 отрицательных (фоновых) изображений.
В каскаде для обнаружения лиц используется от 200 до 6000 признаков Хаара, в зависимости от сложности каскада.
Метод Виолы-Джонса был запатентован в США (патент US 7,020,337 B2), но его базовая идея стала общедоступной и широко используется в академических и коммерческих проектах.

Источники

Viola, P., Jones, M. «Robust Real-Time Face Detection». International Journal of Computer Vision, 2004.
Viola, P., Jones, M. «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), 2001.
Bradski, G., Kaehler, A. «Learning OpenCV: Computer Vision with the OpenCV Library». O'Reilly Media, 2008.
Документация библиотеки OpenCV: «Cascade Classifier Training» и «Haar Feature-based Cascade Classifier for Object Detection».

Примечание: Instagram (продукт Meta, признанной экстремистской и запрещённой в РФ) — социальная сеть, принадлежащая компании Meta (организация признана экстремистской, деятельность запрещена в РФ) Platforms Inc., признанной экстремистской организацией и запрещённой на территории Российской Федерации.

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

На главную BFOmetr →