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

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

Роберт К. МакКоннелл из Wayland Research Inc. впервые описал концепции HOG, не используя термин HOG, в патентной заявке в 1986 году. В 1994 году концепции были использованы Mitsubishi Electric Research Laboratories . Однако широкое распространение они получили только в 2005 году, когда Навнеет Далал и Билл Триггс , исследователи Французского национального института исследований в области компьютерных наук и автоматизации ( INRIA ), представили свою дополнительную работу по дескрипторам HOG на конференции по компьютерному зрению и распознаванию образов (CVPR). ). В этой работе они сосредоточились на обнаружении пешеходов на статических изображениях, хотя с тех пор они расширили свои тесты, включив в них обнаружение людей на видео, а также различных обычных животных и транспортных средств на статических изображениях.

Теория

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

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

Реализация алгоритма

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

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

$[-1,0,1]{\text{ and }}[-1,0,1]^{\top }.\,$

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

Биннинг по ориентации

Вторым шагом расчета является создание гистограмм ячеек. Каждый пиксель внутри ячейки отдает взвешенный голос за ячейку гистограммы на основе ориентации на основе значений, найденных при вычислении градиента. Сами ячейки могут иметь прямоугольную или радиальную форму, а каналы гистограммы равномерно распределены в пределах от 0 до 180 градусов или от 0 до 360 градусов, в зависимости от того, является ли градиент «беззнаковым» или «знаковым». Далал и Триггс обнаружили, что беззнаковые градиенты, используемые в сочетании с 9 каналами гистограмм, показали себя лучше всего в экспериментах по обнаружению людей, отметив при этом, что знаковые градиенты приводят к значительным улучшениям в распознавании некоторых других классов объектов, таких как автомобили или мотоциклы. Что касается веса голоса, вклад пикселей может быть либо самой величиной градиента, либо некоторой функцией от величины. В тестах сама величина градиента обычно дает наилучшие результаты. Другие варианты веса голоса могут включать квадратный корень или квадрат величины градиента, или некоторую урезанную версию величины.

Дескрипторные блоки

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

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

Нормализация блоков

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

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

L2-hys: норма L2 с последующим ограничением (ограничением максимальных значений v до 0,2) и перенормировкой, как в

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

L1-кв.: $f={\sqrt {v \over (\|v\|_{1}+e)}}$

В своих экспериментах Далал и Триггс обнаружили, что схемы L2-hys, L2-norm и L1-sqrt обеспечивают аналогичную производительность, тогда как схема L1-norm обеспечивает несколько менее надежную работу; однако все четыре метода показали очень значительное улучшение по сравнению с ненормализованными данными.

Распознавание объектов

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

Производительность

В своем первоначальном эксперименте по обнаружению людей Далал и Триггс сравнили свои блоки дескрипторов R-HOG и C-HOG с обобщенными вейвлетами Хаара , дескрипторами PCA-SIFT и дескрипторами контекста формы . Обобщенные вейвлеты Хаара представляют собой ориентированные вейвлеты Хаара, которые использовались в 2001 году Моханом, Папагеоргиу и Поджио в их собственных экспериментах по обнаружению объектов. Дескрипторы PCA-SIFT аналогичны дескрипторам SIFT, но отличаются тем, что анализ главных компонентов применяется к нормализованным участкам градиента. Дескрипторы PCA-SIFT были впервые использованы в 2004 году Ке и Суктанкаром и, как утверждалось, превосходили обычные дескрипторы SIFT. Наконец, контексты фигур используют круглые ячейки, аналогичные тем, которые используются в блоках C-HOG, но табулируют голоса только на основе наличия ребер, не делая различий в отношении ориентации. Контексты фигур первоначально использовались в 2001 году Белонги, Маликом и Пузичей.

Тестирование началось на двух разных наборах данных. База данных пешеходов Массачусетского технологического института (MIT) содержит 509 обучающих изображений и 200 тестовых изображений пешеходов на городских улицах. Набор содержит изображения только передней или задней части человеческих фигур и не содержит большого разнообразия человеческих поз. Набор хорошо известен и использовался в различных экспериментах по обнаружению людей, например, в экспериментах, проведенных Папагеоргиу и Поджо в 2000 году. База данных MIT в настоящее время доступна для исследования по адресу https://web.archive.org/web/. 20041118152354/http://cbcl.mit.edu/cbcl/software-datasets/PedestrianData.html . Второй набор был разработан Далалом и Триггсом исключительно для эксперимента по обнаружению людей, поскольку дескрипторы HOG почти идеально работали на наборе MIT. Их набор, известный как INRIA, содержит 1805 изображений людей, взятых из личных фотографий. Набор содержит изображения людей в самых разных позах и сложные фоны, такие как массовые сцены, что делает его более сложным, чем набор MIT. База данных INRIA в настоящее время доступна для исследования по адресу: http://lear.inrialpes.fr/data .

На вышеуказанном сайте есть изображение, показывающее примеры из базы данных обнаружения людей INRIA.

Что касается результатов, дескрипторы блоков C-HOG и R-HOG работают сопоставимо, при этом дескрипторы C-HOG сохраняют небольшое преимущество в частоте промахов обнаружения при фиксированных показателях ложных срабатываний в обоих наборах данных. В наборе MIT дескрипторы C-HOG и R-HOG обеспечивали частоту промахов обнаружения практически нулевую при 10 ⁻⁴ уровень ложноположительных результатов. В наборе INRIA дескрипторы C-HOG и R-HOG обеспечивали коэффициент промахов обнаружения примерно 0,1 при 10 ⁻⁴ уровень ложноположительных результатов. Обобщенные вейвлеты Хаара представляют собой следующий по эффективности подход: они дают примерно 0,01 коэффициент промахов при 10 ⁻⁴ уровень ложноположительных результатов в наборе MIT и примерно 0,3 процента промахов в наборе INRIA. Дескрипторы PCA-SIFT и дескрипторы контекста формы работали довольно плохо на обоих наборах данных. Оба метода дали процент промахов 0,1 при 10 ⁻⁴ уровень ложноположительных результатов в наборе MIT и почти 0,5 процента промахов при 10 ⁻⁴ уровень ложных срабатываний на наборе INRIA.

Дальнейшее развитие

В рамках семинара Pascal Visual Object Classes 2006 Далал и Триггс представили результаты применения гистограмм дескрипторов ориентированных градиентов для изображения объектов, отличных от людей, таких как автомобили, автобусы и велосипеды, а также обычных животных, таких как собаки, кошки, и коровы. В свои результаты они включили оптимальные параметры для формулировки блока и нормализации в каждом случае. На изображении в ссылке ниже показаны некоторые примеры обнаружения мотоциклов.

В рамках Европейской конференции по компьютерному зрению (ECCV) 2006 года Далал и Триггс объединились с Корделией Шмид , чтобы применить детекторы HOG для решения проблемы обнаружения людей в фильмах и видео. Они объединили дескрипторы HOG на отдельных видеокадрах с недавно представленными гистограммами внутреннего движения (IMH) на парах последующих видеокадров. Эти гистограммы внутреннего движения используют величины градиента полей оптического потока, полученные из двух последовательных кадров. Эти величины градиента затем используются таким же образом, как и те, которые получены из данных статического изображения в рамках подхода дескриптора HOG. При тестировании на двух больших наборах данных, взятых из нескольких фильмов, комбинированный метод HOG-IMH дал коэффициент промахов примерно 0,1 при $10^{-4}$ уровень ложноположительных результатов.

На симпозиуме по интеллектуальным транспортным средствам в 2006 году Ф. Суард , А. Ракотомамонджи и А. Бенсрайр представили полную систему обнаружения пешеходов, основанную на дескрипторах HOG. Их система работает с использованием двух инфракрасных камер. Поскольку на инфракрасных изображениях люди кажутся ярче, чем их окружение, система сначала находит интересующие точки в более широком поле обзора, где могут находиться люди. Затем машинные классификаторы опорных векторов работают с дескрипторами HOG, взятыми из этих меньших представляющих интерес позиций, чтобы сформулировать решение относительно присутствия пешехода. Как только пешеходы обнаруживаются в поле зрения, фактическое положение пешехода оценивается с помощью стереозрения.

На конференции IEEE по компьютерному зрению и распознаванию образов в 2006 году Цян Чжу , Шай Авидан , Мэй-Чен Йе и Кван-Тин Ченг представили алгоритм, позволяющий значительно ускорить обнаружение людей с использованием методов дескриптора HOG. Их метод использует дескрипторы HOG в сочетании с алгоритмом каскадных классификаторов, который обычно с большим успехом применяется для обнаружения лиц. Кроме того, вместо того, чтобы полагаться на блоки одинакового размера, они вводят блоки, которые различаются по размеру, расположению и соотношению сторон. Чтобы изолировать блоки, наиболее подходящие для обнаружения человеком, они применили алгоритм AdaBoost для выбора этих блоков для включения в каскад. В ходе экспериментов их алгоритм достиг производительности, сравнимой с оригинальным алгоритмом Далала и Триггса, но работал со скоростью до 70 раз быстрее. В 2006 году исследовательские лаборатории Mitsubishi Electric подали заявку на патент США на этот алгоритм под номером заявки 20070237387.

На Международной конференции IEEE по обработке изображений в 2010 году Руй Ху , Марк Банард и Джон Колломосс расширили дескриптор HOG для использования в поиске изображений на основе эскизов (SBIR). Поле плотной ориентации было экстраполировано на основе доминирующих откликов детектора границ Кэнни при ограничении гладкости Лапласа , и HOG вычислил по этому полю. Полученный в результате дескриптор поля градиента HOG (GF-HOG) фиксирует локальную пространственную структуру в эскизах или картах границ изображения. Это позволило использовать дескриптор в системе поиска изображений на основе контента, доступной для поиска по нарисованным от руки формам. Было показано, что адаптация GF-HOG превосходит существующие дескрипторы градиентных гистограмм, такие как SIFT , SURF и HOG, примерно на 15 процентов при выполнении задачи SBIR.

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

См. также

• Обнаружение углов
• Обнаружение пешеходов
• Особенность (компьютерное зрение)
• Обнаружение функций (компьютерное зрение)
• Извлечение признаков
• Обнаружение точек интереса
• Распознавание объектов
• Преобразование масштабно-инвариантного объекта

Внешние ссылки

• http://www.mathworks.com/matlabcentral/fileexchange/33863 Реализация для Matlab (mex-файл)
• https://www.cs.cmu.edu/~yke/pcasift/ — Код для обнаружения объектов PCA-SIFT
• http://lear.inrialpes.fr/software/ — набор программных инструментов для обнаружения объектов HOG (домашняя страница исследовательской группы)
• https://web.archive.org/web/20100502032344/http://www.navneetdalal.com/software — набор программных инструментов для обнаружения объектов HOG (домашняя страница Navneet Dalal)
• http://dlib.net/imaging.html#scan_fhog_pyramid — набор программных инструментов C++ и Python для обнаружения объектов HOG
• http://pascal.inrialpes.fr/data/human/. Архивировано 5 мая 2010 г. в Wayback Machine — набор данных изображений человека INRIA.
• http://cbcl.mit.edu/software-datasets/PedestrianData.html — набор данных изображений пешеходов MIT