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

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

История

Метод гистограммы градиентов был впервые систематически описан и популяризирован в 2005 году исследователями Навнитом Далом (Navneet Dalal) и Биллом Триггсом (Bill Triggs) в их работе «Histograms of Oriented Gradients for Human Detection», представленной на конференции IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR). До этого подобные идеи использовались в более ранних работах, например, в дескрипторах SIFT (Scale-Invariant Feature Transform) Дэвида Лоу (1999), где также применялись гистограммы градиентов, но для других целей (сопоставление ключевых точек). Дал и Триггс адаптировали и оптимизировали этот подход для задачи обнаружения объектов, показав его высокую эффективность на примере поиска пешеходов на изображениях. Их работа стала эталонной и стимулировала дальнейшие исследования в области дескрипторов признаков.

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

Алгоритм HOG преобразует изображение в набор числовых векторов, описывающих локальные распределения направлений градиентов. Основные этапы вычисления дескриптора:

1. Предварительная обработка. Изображение обычно преобразуется в оттенки серого. Для уменьшения влияния шума и освещения может применяться гамма-коррекция или нормализация цвета. Однако в классической реализации Дала и Триггса гамма-коррекция не использовалась, так как нормализация на более поздних этапах компенсирует её эффект.

1. Вычисление градиентов. Для каждого пикселя изображения вычисляются градиенты по оси X и Y. Обычно используются простые одномерные фильтры Собеля (например, ядра [-1, 0, 1] и [-1, 0, 1]^T). По полученным значениям вычисляются:

• Магнитуда (величина) градиента: G = sqrt(Gx^2 + Gy^2)
• Направление (ориентация) градиента: θ = arctan(Gy / Gx), где Gx и Gy — градиенты по горизонтали и вертикали соответственно. Направление обычно берётся в диапазоне от 0 до 180 градусов (беззнаковое) или от 0 до 360 градусов (знаковое). Для HOG чаще используется беззнаковое представление (0-180°), так как оно более устойчиво к изменениям контраста.

1. Разбиение на ячейки (cells). Изображение делится на сетку маленьких, непересекающихся квадратных ячеек. Типичный размер ячейки — 8×8 пикселей.

1. Построение гистограммы для каждой ячейки. Для каждой ячейки строится гистограмма направлений градиентов. Ось направлений (0-180°) разбивается на определённое количество бинов (bins). Обычно используется 9 бинов, каждый из которых охватывает диапазон в 20 градусов. Каждый пиксель в ячейке добавляет свой «вес» в соответствующий бин гистограммы. Вес равен магнитуде градиента этого пикселя. Таким образом, пиксели с сильными градиентами (например, на границах объектов) вносят больший вклад в гистограмму.

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

1. Формирование дескриптора. Все нормализованные векторы блоков объединяются в один итоговый вектор признаков HOG. Этот вектор и является дескриптором всего изображения или его области (окна поиска). Размерность дескриптора зависит от размера изображения, размера ячейки, размера блока и количества бинов.

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

Параметры дескриптора

Основные параметры, которые можно варьировать:

• Размер ячейки: влияет на детализацию и устойчивость к шуму. Меньшие ячейки (например, 4×4) дают больше деталей, но менее устойчивы.
• Количество бинов гистограммы: определяет угловое разрешение. 9 бинов — стандартный выбор.
• Размер блока: определяет контекст нормализации. 2×2 ячейки — наиболее распространённый вариант.
• Тип нормализации: влияет на устойчивость к изменениям освещения.
• Знаковость градиента: беззнаковый (0-180°) или знаковый (0-360°). Беззнаковый чаще используется для задач обнаружения объектов.

Достоинства

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

Недостатки

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

Применение

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

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

Это была основная задача, для которой метод был разработан. HOG в сочетании с классификатором (например, методом опорных векторов, SVM) показал отличные результаты на наборе данных INRIA Person. Алгоритм сканирует изображение окном фиксированного размера, извлекает HOG-дескриптор для каждого окна и передаёт его классификатору, который решает, есть ли в окне пешеход.

Обнаружение других объектов

Метод успешно применялся для обнаружения:

• Автомобилей и других транспортных средств.
• Велосипедистов.
• Животных (например, собак, кошек).
• Лиц (в некоторых реализациях).

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

HOG-дескрипторы, извлечённые из последовательности кадров (например, в сочетании с оптическим потоком), использовались для распознавания жестов рук или действий человека.

Извлечение признаков для других задач

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

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

• SIFT (Scale-Invariant Feature Transform): SIFT также использует гистограммы градиентов, но для описания ключевых точек, а не всего изображения. SIFT инвариантен к масштабу и повороту, но более сложен вычислительно. HOG, в отличие от SIFT, не является инвариантным к повороту, но проще и быстрее для задач обнаружения объектов.
• DPM (Deformable Parts Model): Этот метод, разработанный Педро Фелисзеншвальбом, использует HOG-дескрипторы для описания частей объекта и моделирует их взаимное расположение. DPM долгое время был одним из лучших методов для обнаружения объектов.
• Глубокие нейронные сети (CNN): Начиная с 2012 года, свёрточные нейронные сети (например, R-CNN, YOLO, SSD) значительно превзошли HOG по точности и скорости в задачах обнаружения объектов. Однако HOG остаётся полезным в ситуациях с ограниченными вычислительными ресурсами, при малом объёме данных для обучения или для задач, где важна интерпретируемость.

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

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

Источники

1. Dalal, N., & Triggs, B. (2005). Histograms of Oriented Gradients for Human Detection. Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR).
2. Lowe, D. G. (2004). Distinctive Image Features from Scale-Invariant Keypoints. International Journal of Computer Vision, 60(2), 91-110.
3. Felzenszwalb, P. F., Girshick, R. B., McAllester, D., & Ramanan, D. (2010). Object Detection with Discriminatively Trained Part-Based Models. IEEE Transactions on Pattern Analysis and Machine Intelligence, 32(9), 1627-1645.
4. Szeliski, R. (2010). Computer Vision: Algorithms and Applications. Springer.