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

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

История

Метод гистограмм направленных градиентов был впервые предложен в 1986 году учёными Дэвидом Лоу и К. Мак-Лафлином в контексте анализа формы объектов. Однако современная и наиболее известная версия HOG была разработана в 2005 году группой исследователей из французского Национального института исследований в области информатики и автоматики (INRIA) под руководством Навнита Далала и Билла Триггса. В своей работе «Histograms of Oriented Gradients for Human Detection» они показали, что HOG значительно превосходит существовавшие на тот момент методы (например, дескрипторы Хаара) по точности обнаружения пешеходов на изображениях. С тех пор HOG стал одним из стандартных инструментов в компьютерном зрении, особенно в сочетании с методом опорных векторов (SVM) для классификации.

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

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

Первый шаг построения HOG-дескриптора — вычисление градиентов изображения по осям X и Y. Для этого применяются дискретные производные, чаще всего с использованием фильтров Собеля или Превитта. Для каждого пикселя вычисляются:

• Магнитуда градиента: \( G = \sqrt{G_x^2 + G_y^2} \)
• Направление градиента: \( \theta = \arctan\left(\frac{G_y}{G_x}\right) \)

Направление обычно квантуется в диапазоне от 0° до 180° (беззнаковые градиенты) или от 0° до 360° (знаковые градиенты). Для обнаружения пешеходов чаще используют беззнаковые градиенты, так как они инвариантны к изменению контраста (например, тёмный объект на светлом фоне и наоборот дают одинаковые градиенты).

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

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

Блоки и нормализация

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

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

Итоговый HOG-дескриптор представляет собой конкатенацию всех нормализованных векторов блоков. Для изображения размером 64×128 пикселей (стандартный размер для обнаружения пешеходов) количество ячеек составляет 8×16 = 128, количество блоков — 7×15 = 105 (с учётом перекрытия). Каждый блок даёт вектор размером 4 ячейки × 9 бинов = 36 элементов. Таким образом, общая размерность дескриптора — 105 × 36 = 3780.

Математическая формулировка

Пусть \( I(x, y) \) — интенсивность пикселя в точке \( (x, y) \). Градиенты: \[ G_x(x, y) = I(x+1, y) - I(x-1, y) \] \[ G_y(x, y) = I(x, y+1) - I(x, y-1) \]

Магнитуда и направление: \[ M(x, y) = \sqrt{G_x^2 + G_y^2} \] \[ \theta(x, y) = \arctan\left(\frac{G_y}{G_x}\right) \]

Для ячейки \( C \) с пикселями \( p \in C \) гистограмма \( h \) с \( K \) бинами: \[ h_k = \sum_{p \in C} w(p, k) \cdot M(p) \] где \( w(p, k) \) — вес билинейной интерполяции между бинами \( k \) и \( k+1 \) в зависимости от \( \theta(p) \).

Нормализация блока \( B \), состоящего из ячеек \( C_1, C_2, C_3, C_4 \): \[ v_B = \frac{[h_{C_1}, h_{C_2}, h_{C_3}, h_{C_4}]}{\sqrt{\|h_{C_1}\|^2 + \|h_{C_2}\|^2 + \|h_{C_3}\|^2 + \|h_{C_4}\|^2 + \varepsilon}} \] где \( \varepsilon \) — малая константа для избежания деления на ноль.

Варианты и модификации

HOG с разными параметрами

• Размер ячейки: от 4×4 до 16×16 пикселей. Меньшие ячейки дают более детальное описание, но увеличивают размерность.
• Количество бинов: от 6 до 18. Большее число бинов повышает точность распознавания направлений, но требует больше памяти.
• Тип градиентов: знаковые (0°–360°) или беззнаковые (0°–180°). Знаковые градиенты чувствительны к инверсии контраста.

Улучшенные версии

• PHOG (Pyramid HOG): использует пространственную пирамиду для учёта признаков на разных масштабах.
• CoHOG (Co-occurrence HOG): учитывает совместную встречаемость пар направлений градиентов в соседних ячейках.
• FHOG (Felzenszwalb HOG): модификация, предложенная Педро Фельценшвальбом для детекторов на основе частей объектов (DPM). Включает 31-мерный вектор (9 бинов для беззнаковых градиентов, 18 для знаковых, 4 для нормализованных сумм).

Применение

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

Наиболее известное применение HOG — детектор пешеходов, предложенный Далалом и Триггсом. Дескриптор HOG извлекается из скользящего окна на изображении, а затем классифицируется с помощью SVM. Этот подход лёг в основу многих систем видеонаблюдения и автомобильных систем безопасности.

Обнаружение транспортных средств

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

Распознавание жестов и поз

В системах анализа человеческого тела HOG помогает выделять контуры рук, ног и туловища. Используется в интерфейсах «человек-компьютер» и в анимации.

Медицинская диагностика

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

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

В мобильных роботах HOG используется для навигации и обнаружения препятствий. Алгоритм работает в реальном времени на современных процессорах.

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

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

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

Недостатки

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

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

HOG vs. SIFT

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

HOG vs. LBP

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

HOG vs. CNN

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

Реализации

OpenCV

В библиотеке OpenCV (Open Source Computer Vision Library) реализован класс HOGDescriptor, который позволяет извлекать HOG-признаки и выполнять обнаружение объектов. Пример использования на C++:

``cpp cv::HOGDescriptor hog; std::vector<float> descriptors; hog.compute(image, descriptors); ``

scikit-image

В Python библиотека scikit-image предоставляет функцию hog() из модуля skimage.feature. Пример:

``python from skimage.feature import hog features = hog(image, orientations=9, pixels_per_cell=(8, 8), cells_per_block=(2, 2)) ``

MATLAB

В среде MATLAB функция extractHOGFeatures из пакета Computer Vision Toolbox позволяет извлекать HOG-признаки.

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

• В оригинальной работе Далала и Триггса (2005) HOG-дескриптор показал точность обнаружения пешеходов около 89% на тестовом наборе INRIA, что было значительным улучшением по сравнению с предыдущими методами.
• HOG часто используется в комбинации с методом опорных векторов (SVM) — такая связка называется HOG+SVM и является классическим примером «обучения с учителем» в компьютерном зрении.
• В 2010 году метод HOG был включён в состав стандартной библиотеки OpenCV, что способствовало его широкому распространению.
• Несмотря на развитие глубокого обучения, HOG продолжает применяться в промышленных системах благодаря низким требованиям к вычислительным ресурсам и отсутствию необходимости в больших наборах данных для обучения.

Источники

• Dalal N., Triggs B. Histograms of Oriented Gradients for Human Detection // IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR). — 2005. — Vol. 1. — P. 886–893.
• Lowe D. G. Distinctive Image Features from Scale-Invariant Keypoints // International Journal of Computer Vision. — 2004. — Vol. 60, No. 2. — P. 91–110.
• Felzenszwalb P. F., Girshick R. B., McAllester D., Ramanan D. Object Detection with Discriminatively Trained Part-Based Models // IEEE Transactions on Pattern Analysis and Machine Intelligence. — 2010. — Vol. 32, No. 9. — P. 1627–1645.
• Bradski G., Kaehler A. Learning OpenCV: Computer Vision with the OpenCV Library. — O'Reilly Media, 2008. — 580 p.
• scikit-image: Image processing in Python // PeerJ. — 2014. — Vol. 2. — e453.