Гистограмма ориентированных градиентов

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

История

Метод HOG был впервые предложен в 2005 году группой исследователей под руководством Навина Даллала (Navneet Dalal) и Билла Триггса (Bill Triggs) в рамках работы по обнаружению пешеходов на изображениях. Работа была опубликована в трудах конференции IEEE Conference on Computer Vision and Pattern Recognition (CVPR). Даллал и Триггс показали, что гистограммы направлений градиентов, вычисленные в плотной сетке ячеек, превосходят по точности другие методы, такие как SIFT (Scale-Invariant Feature Transform) и Haar-каскады, особенно при обработке изображений с различными условиями освещения и фона.

В последующие годы HOG стал широко применяться в системах видеонаблюдения, автономных транспортных средствах и робототехнике. В 2010-х годах метод был интегрирован в библиотеки компьютерного зрения, такие как OpenCV, что упростило его использование в промышленных и исследовательских проектах.

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

Вычисление градиентов

На первом этапе изображение преобразуется в оттенки серого (если исходное изображение цветное). Для каждого пикселя вычисляются градиенты по оси X и Y с помощью фильтров, например, оператора Собеля (Sobel) или Превитта (Prewitt). Градиент по оси X (Gx) отражает изменение яркости по горизонтали, а по оси Y (Gy) — по вертикали. Затем для каждого пикселя рассчитывается величина градиента (магнитуда) и направление (ориентация):

• Магнитуда: \( M = \sqrt{G_x^2 + G_y^2} \)
• Направление: \( \theta = \arctan\left(\frac{G_y}{G_x}\right) \) (обычно в диапазоне от 0 до 180 градусов, так как градиенты с противоположными направлениями считаются одинаковыми для контуров).

Разбиение на ячейки и блоки

Изображение делится на небольшие прямоугольные участки — ячейки (cells), размером, например, 8×8 пикселей. Для каждой ячейки строится гистограмма направлений градиентов. Обычно используется 9 бинов (интервалов), каждый из которых соответствует диапазону углов: 0–20°, 20–40° и т.д. до 160–180°. Каждый пиксель вносит вклад в гистограмму пропорционально своей магнитуде, причём вклад распределяется между двумя соседними бинами (линейная интерполяция) для уменьшения эффекта дискретизации.

Для улучшения устойчивости к изменениям освещения и контраста ячейки объединяются в блоки (blocks), например, размером 2×2 ячейки (16×16 пикселей). Внутри каждого блока гистограммы всех ячеек нормализуются — обычно с использованием L2-нормы (евклидовой нормы) или L1-нормы. Нормализация позволяет уменьшить влияние локальных перепадов яркости, например, теней или бликов.

Формирование дескриптора

После нормализации все гистограммы из блоков объединяются в один вектор признаков — дескриптор HOG. Для изображения размером 64×128 пикселей (стандартный размер для обнаружения пешеходов) при ячейках 8×8 и блоках 2×2 ячейки (с шагом 8 пикселей) получается:

• Количество ячеек по горизонтали: 64/8 = 8
• Количество ячеек по вертикали: 128/8 = 16
• Количество блоков по горизонтали: (8-1) = 7 (так как блоки перекрываются)
• Количество блоков по вертикали: (16-1) = 15
• Размер дескриптора: 7 × 15 × (4 ячейки в блоке × 9 бинов) = 3780 признаков.

Классификация и обучение

Дескриптор HOG сам по себе не является классификатором. Для обнаружения объектов вектор признаков подаётся на вход обученной модели машинного обучения. Наиболее часто используется метод опорных векторов (SVM, Support Vector Machine) с линейным ядром, так как он хорошо работает с большими размерностями признаков и обеспечивает высокую скорость обработки.

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

• Сбор положительных примеров (изображения с целевым объектом, например, пешеходом) и отрицательных примеров (изображения без объекта).
• Вычисление HOG-дескрипторов для всех примеров.
• Обучение SVM-классификатора для разделения положительных и отрицательных классов.

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

Применение

Обнаружение пешеходов

HOG стал стандартным методом для обнаружения пешеходов в системах видеонаблюдения и автономных транспортных средствах. Благодаря устойчивости к изменениям позы, одежды и освещения, метод позволяет с высокой точностью выделять людей на фоне городской среды. В 2005 году Даллал и Триггс достигли точности около 89% на тестовом наборе данных INRIA Person Dataset.

Распознавание транспортных средств

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

Биометрия и распознавание лиц

HOG используется для обнаружения лиц в системах видеонаблюдения и аутентификации. Однако для распознавания лиц (идентификации конкретного человека) HOG часто комбинируется с другими методами, такими как LBP (Local Binary Patterns) или нейронные сети.

Робототехника

В робототехнике HOG применяется для навигации и взаимодействия с окружающей средой, например, для обнаружения препятствий или объектов манипуляции.

Преимущества и недостатки

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

• Устойчивость к изменениям освещения: нормализация блоков уменьшает влияние теней и бликов.
• Инвариантность к локальным геометрическим искажениям: метод хорошо работает при небольших изменениях позы или ракурса объекта.
• Простота реализации: HOG легко реализовать с помощью стандартных библиотек (OpenCV, scikit-image).
• Высокая скорость: при использовании линейного SVM классификация выполняется за миллисекунды на современных процессорах.

Недостатки

• Чувствительность к повороту объекта: HOG не инвариантен к вращению; для обнаружения объектов под разными углами требуется обучение на повёрнутых примерах или использование нескольких классификаторов.
• Большая размерность признаков: для изображений высокого разрешения дескриптор может содержать десятки тысяч признаков, что увеличивает вычислительные затраты.
• Ограниченная эффективность для текстурных объектов: HOG лучше работает для объектов с чёткими контурами (пешеходы, автомобили), чем для объектов с однородной или сложной текстурой (например, деревья, облака).

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

SIFT (Scale-Invariant Feature Transform)

SIFT также использует гистограммы градиентов, но вычисляет их в ключевых точках (инвариантных к масштабу и повороту). HOG, в отличие от SIFT, работает с плотной сеткой ячеек, что делает его более подходящим для обнаружения объектов, а не для сопоставления точек.

Haar-каскады

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

Нейронные сети (CNN)

Современные свёрточные нейронные сети (CNN), такие как YOLO (You Only Look Once) и Faster R-CNN, превосходят HOG по точности и гибкости, особенно для сложных сцен с множеством объектов. Однако HOG остаётся актуальным для задач, где требуется высокая скорость и низкие вычислительные затраты, например, на встраиваемых системах.

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

• Метод HOG вдохновлён работой Дэвида Марра (David Marr) по зрительной системе человека, который предположил, что мозг использует градиенты для восприятия форм.
• В 2005 году Даллал и Триггс показали, что использование ненормализованных гистограмм снижает точность на 10–15%, что подчеркивает важность нормализации.
• HOG широко используется в библиотеке OpenCV, где реализован в виде класса cv::HOGDescriptor для C++ и Python.

Источники

• Dalal, N., & Triggs, B. (2005). Histograms of Oriented Gradients for Human Detection. IEEE Conference on Computer Vision and Pattern Recognition (CVPR).
• Bradski, G., & Kaehler, A. (2008). Learning OpenCV: Computer Vision with the OpenCV Library. O'Reilly Media.
• Szeliski, R. (2010). Computer Vision: Algorithms and Applications. Springer.