HOG + SVM

HOG + SVM — это комбинация методов компьютерного зрения и машинного обучения, используемая для решения задачи детекции объектов на изображениях. Метод основан на вычислении дескриптора гистограммы ориентированных градиентов (HOG) и последующей классификации полученных признаков с помощью метода опорных векторов (SVM). Данный подход получил широкое распространение в начале 2010-х годов, в первую очередь благодаря эффективной реализации детектора пешеходов, предложенной исследователями Навнитом Даллом и Биллом Триггсом.

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

Метод HOG + SVM состоит из двух последовательных этапов: извлечения признаков из изображения с помощью дескриптора HOG и классификации этих признаков с помощью обученной модели SVM.

Дескриптор HOG

Дескриптор HOG (Histogram of Oriented Gradients) — это дескриптор локальных признаков, который описывает распределение направлений градиентов интенсивности в локальных областях изображения. Основная идея заключается в том, что внешний вид и форма объекта на изображении могут быть охарактеризованы распределением локальных градиентов, даже без точного знания их положения.

Процесс вычисления дескриптора HOG включает несколько шагов:

1. Вычисление градиентов: Для каждого пикселя изображения вычисляются градиенты по оси X и Y с помощью простых фильтров (например, ядер Собеля или Прюитт). Вычисляются магнитуда (величина) и направление градиента.
2. Разбиение на ячейки: Изображение делится на небольшие связные области — ячейки (cells). Типичный размер ячейки — 8×8 пикселей.
3. Построение гистограммы для каждой ячейки: Для каждой ячейки строится гистограмма направлений градиентов. Диапазон углов (обычно от 0 до 180 или 360 градусов) делится на фиксированное число бинов (например, 9 бинов). Каждый пиксель в ячейке добавляет значение, пропорциональное магнитуде его градиента, в соответствующий бин гистограммы.
4. Нормализация в блоках: Для учёта изменений освещения и контраста ячейки объединяются в более крупные пространственные блоки (blocks). Гистограммы всех ячеек в блоке объединяются и нормализуются (например, по L2-норме). Типичный блок состоит из 2×2 ячеек. Нормализация делает дескриптор устойчивым к локальным изменениям освещённости.
5. Формирование итогового вектора: Нормализованные гистограммы всех блоков в изображении конкатенируются в единый вектор признаков большой размерности.

Метод опорных векторов (SVM)

Метод опорных векторов (Support Vector Machine, SVM) — это алгоритм машинного обучения, используемый для задач классификации и регрессии. В контексте HOG + SVM, SVM обучается на размеченных данных: на положительных примерах (изображения, содержащие искомый объект, например, пешехода) и отрицательных примерах (изображения, не содержащие объекта).

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

История

Метод HOG + SVM был впервые представлен в 2005 году в работе Навнита Далла и Билла Триггса «Histograms of Oriented Gradients for Human Detection». До этого для детекции объектов, особенно пешеходов, использовались более сложные и менее эффективные методы, такие как детекторы на основе вейвлетов Хаара (Haar-like features) с каскадным классификатором (AdaBoost), предложенные Полом Виолой и Майклом Джонсом в 2001 году.

Далл и Триггс показали, что дескриптор HOG, по своей сути похожий на дескриптор SIFT (Scale-Invariant Feature Transform), но применяемый в плотной сетке, значительно превосходит существующие методы по точности детекции пешеходов. В своей работе они использовали линейный SVM, что обеспечило не только высокую точность, но и приемлемую скорость работы, позволяющую применять метод в реальном времени на оборудовании того времени.

Метод HOG + SVM стал стандартом де-факто для детекции пешеходов на протяжении нескольких лет. Он был реализован в популярных библиотеках компьютерного зрения, таких как OpenCV, что способствовало его широкому распространению.

Применение

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

Метод также использовался в качестве компонента в более сложных системах, например, для извлечения признаков в задачах распознавания объектов или для инициализации трекера.

Критика и ограничения

Несмотря на свою эффективность, метод HOG + SVM имеет ряд ограничений:

• Высокая вычислительная сложность: Вычисление дескриптора HOG для каждого окна в скользящем окне требует значительных вычислительных ресурсов, особенно при обработке видео высокого разрешения.
• Чувствительность к окклюзиям: Метод плохо работает при частичном перекрытии объекта.
• Чувствительность к значительным изменениям позы: Детектор, обученный на пешеходах в вертикальном положении, плохо распознаёт человека, сидящего или лежащего.
• Необходимость ручного подбора параметров: Размер ячейки, количество бинов гистограммы, размер блока — эти параметры требуют тщательной настройки для каждой задачи.
• Плохая работа с текстурами: Дескриптор HOG в основном реагирует на контуры, поэтому объекты с однородной текстурой могут быть плохо распознаны.

Сравнение с современными методами

Начиная с середины 2010-х годов, метод HOG + SVM был в значительной степени вытеснен методами глубокого обучения, в частности свёрточными нейронными сетями (CNN). Архитектуры, такие как R-CNN, Fast R-CNN, Faster R-CNN, YOLO (You Only Look Once) и SSD (Single Shot Detector), продемонстрировали значительно более высокую точность и скорость детекции, особенно в сложных сценах с большим количеством объектов, окклюзиями и изменениями масштаба.

Тем не менее, метод HOG + SVM не утратил своего значения. Он продолжает использоваться в задачах, где вычислительные ресурсы сильно ограничены (например, на встраиваемых системах), или когда требуется высокая скорость работы без использования GPU. Кроме того, он служит отличным учебным примером для понимания основ детекции объектов и извлечения признаков.

Источники

1. Dalal, N., & Triggs, B. (2005). Histograms of oriented gradients for human detection. 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05).
2. Viola, P., & Jones, M. (2001). 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.
3. Lowe, D. G. (2004). Distinctive image features from scale-invariant keypoints. International Journal of Computer Vision.
4. Bradski, G., & Kaehler, A. (2008). Learning OpenCV: Computer Vision with the OpenCV Library. O'Reilly Media, Inc.