Histogram of Oriented Gradients (HOG)

Статья подготовлена командой преподавателей специализации "Современное компьютерное зрение" Ai Edu

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

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

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

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

Опишем алгоритм для вычисления HOG-дескрипторов (дескриптором называется математическое представление изображения в виде набора чисел, представляющего ключевую информацию о содержании изображения).

Шаг 1: обработка изображения (Image Preprocessing)

Так как дальше мы будем разбивать изображение на сетку из квадратиков (допустим, размера 4 на 4 пикселя), то на первом шаге нужно изменить размеры изображения так, чтобы длина и ширина картинки делились на 4 - например, делаем resize до размера 32x64 пикселя.

Шаг 2: вычисление градиентов (Calculate Gradient & Orientation)

Разобъем изображение на сетку из ячеек равного размера (допустим, 4x4 пикселя).

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

Для вычисления градиента пикселя внутри ячейки мы сначала вычисляем величины Gx и Gy:

• Gx - это разность значений справа и слева от выбранного пикселя; для примера с картинки Gx = 89-78=11
• Gy - это разность значений сверху и снизу от выбранного пикселя; для примера с картинки Gy = 64-56=8

Далее мы вычисляем величину и направление градиента по следующим формулам:

Для нашего примера получаем величину градиента G = 13.6, а ориентация (направление) равна 36 градусов.

Шаг 3: построение гистограммы (Build histogram)

Теперь учтем вклад каждого пикселя из ячейки (4x4) в изменение градиента для всей ячейки. Ориентация градиента меняется в диапазоне от 0 до 180 градусов. Разобъем этот диапазон на бины размером 20 градусов.

• В нашем примере для выбранного пикселя из ячейки мы получили направление 36 градусов - оно находится в диапазоне (20; 40), поэтому даст вклад и в бин 20 и бин 40.
• Суммарный вклад в бины 20 и 40 равен величине градиента - у нас это 13.6. Это число мы разделим на части, обратно пропорциональные расстоянию от 36 до 20 и до 40, а именно, вклад в бин 20 будет равен: (40-36)/20 * 13.6, а вклад в бин 40 будет равен (36-20)/20 * 13.6.

Теперь, аккумулируя вклады всех пикселей из ячейки, мы получаем гистограмму для каждой ячейки (размера 4x4 пикселя):

Шаг 4: нормализация значений (Normalisation)

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

• Ячейки объединяются в блоки 2x2 (то есть четыре ячейки 4x4 будут образовывать блок 8x8 пикселей), и гистограммы из этих четырех соседних ячеек конкатенируются (склеиваются) в один длинный вектор - четыре гистограммы из 9 столбцов становятся большой гистограммой из 36 столбцов:

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

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

На сегодня все! Мы будем готовить для Вас новые интересные статьи, а также рады пригласить Вас на нашу новую специализацию, посвященную современному компьютерному зрению! (по всем вопросам о специализации и дополнительным скидкам пишите на в телеграм @murr4a или на почту aiedu.courses@gmail.com - всегда рады помочь)!