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

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

${\displaystyle [-1,0,1]}$ и ${\displaystyle [-1,0,1]^{T}.}$

Далал и Триггс использовали более сложные маски, такие как Собел 3x3 (Оператор Собеля) или диагональные маски, но эти маски показали более низкую производительность для данной задачи. Они также экспериментировали с размытием по Гауссу перед применением дифференцирующей маски, но также обнаружили, что пропуск этого шага увеличивает быстродействие без заметной потери качества.[2]

На следующем шаге вычисляются гистограммы ячеек. Каждый пиксель в ячейке участвует во взвешенном голосовании для каналов гистограммы направлений, основанном на значении градиентов. Ячейки могут быть прямоугольной или круглой формы, каналы гистограммы равномерно распределяются от 0 до 180 или же от 0 до 360 градусов, в зависимости от того, вычисляется «знаковый» или «беззнаковый градиент». Далал и Триггс обнаружили, что беззнаковый градиент совместно с девятью каналами гистограммы дает лучшие результаты при распознавании людей. При распределении весов в голосовании вес пикселя может задаваться либо абсолютным значением градиента, либо некоторой функцией от него; в реальных тестах абсолютное значение градиента дает лучшие результаты. Другими возможными вариантами могут быть квадратный корень, квадрат или урезанное абсолютное значение градиента.[3]

Для принятия во внимание яркости и контрастности градиенты следует локально нормировать, для чего ячейки нужно сгруппировать в более крупные связные блоки. Дескриптор HOG, таким образом, является вектором компонент нормированных гистограмм ячеек из всех областей блока. Как правило, блоки перекрываются, то есть каждая ячейка входит более чем в один конечный дескриптор. Используются две основные геометрии блока: прямоугольные R-HOG и круглые C-HOG. Блоки R-HOG обычно являются квадратными сетками, характеризующимися тремя параметрами: количеством ячеек на блок, количеством пикселов на ячейку и количеством каналов на гистограмму ячейки. В эксперименте Далала и Триггса оптимальными параметрами являются блоки 16x16, ячейки 8x8 и 9 каналов на гистограмму. Более того, они обнаружили, что можно слегка повысить скорость вычислений, применяя гауссов фильтр внутри каждого блока до процедуры голосования, что, в свою очередь, снижает вес пикселей на границах блоков. Блоки R-HOG оказываются очень похожими на SIFT-дескрипторы; однако, несмотря на их похожую структуру, блоки R-HOG вычисляются на плотных сетках фиксированного масштаба без фиксированного направления, в то время как SIFT-дескрипторы вычисляются в разреженных, не чувствительных к масштабу ключевых точках изображения и используют поворот для выравнивания направления. Кроме того, для кодирования информации о форме объектов блоки R-HOG используются совместно, в то время как SIFT-дескрипторы используются по отдельности.

Блоки C-HOG имеют 2 разновидности: с цельной центральной ячейкой и разделенной на сектора. Эти блоки могут быть описаны 4 параметрами: количество секторов и колец, радиус центрального кольца и коэффициент расширения для радиусов остальных колец. Далал и Триггс обнаружили, что обе разновидности показали одинаковый результат, и разделение на 2 кольца и 4 сектора с радиусом 4 пиксела и коэффициентом расширения 2 дало лучший результат в их эксперименте. Кроме того, гауссово взвешивание не дало никаких улучшений при использовании блоков C-HOG. Эти блоки похожи на контексты формы, но имеют важное отличие: блоки C-HOG содержат ячейки с несколькими каналами направлений, в то время как контексты формы используют только наличие одного края.[4]

Далал и Триггс исследовали четыре метода нормализации блоков. Пусть ${\displaystyle v}$ — ненормированный вектор, содержащий все гистограммы данного блока, ${\displaystyle \|v\|_{k}}$ — его k-норма при ${\displaystyle k={1,2}}$ и ${\displaystyle e}$ — некая малая константа (точное значение не так важно). Тогда нормировочный множитель можно получить одним из следующих способов:

L2-норма: ${\displaystyle f={v \over {\sqrt {\|v\|_{2}^{2}+e^{2}}}}}$

L2-hys: L2-норма ограничивается сверху (значения v, бóльшие 0,2, полагаются равными 0,2) и перенормируется, как в[5]

L1-норма: ${\displaystyle f={v \over (\|v\|_{1}+e)}}$

корень из L1-нормы: ${\displaystyle f={\sqrt {v \over (\|v\|_{1}+e)}}}$

Далал и Триггс установили, что L1-норма дает менее надежные результаты, чем остальные три, которые работают приблизительно одинаково хорошо, однако все четыре метода значительно улучшают результаты по сравнению с ненормализованными.[4]

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