Гистограмма ориентированных градиентов (HOG) — это дескриптор признаков , используемый в компьютерном зрении и обработке изображений для обнаружения объектов . Метод подсчитывает вхождения ориентации градиента в локализованных частях изображения. Этот метод похож на гистограммы ориентации краев, масштабно-инвариантные дескрипторы преобразования признаков и контексты формы , но отличается тем, что он вычисляется на плотной сетке равномерно расположенных ячеек и использует перекрывающуюся локальную нормализацию контраста для повышения точности.
Роберт К. Макконнелл из Wayland Research Inc. впервые описал концепции, лежащие в основе HOG, не используя термин HOG в патентной заявке 1986 года. [1] В 1994 году эти концепции были использованы Mitsubishi Electric Research Laboratories . [2] Однако их использование стало широко распространенным только в 2005 году, когда Навнит Далал и Билл Триггс, исследователи из Французского национального института исследований в области компьютерных наук и автоматизации ( INRIA ), представили свою дополнительную работу по дескрипторам HOG на конференции по компьютерному зрению и распознаванию образов (CVPR). В этой работе они сосредоточились на обнаружении пешеходов на статических изображениях, хотя с тех пор они расширили свои тесты, включив обнаружение людей на видео, а также на различных обычных животных и транспортных средств на статических изображениях.
Основная мысль, лежащая в основе дескриптора гистограммы ориентированных градиентов, заключается в том, что внешний вид и форма локального объекта на изображении могут быть описаны распределением градиентов интенсивности или направлений краев. Изображение делится на небольшие связанные области, называемые ячейками, и для пикселей внутри каждой ячейки составляется гистограмма направлений градиента. Дескриптор представляет собой конкатенацию этих гистограмм. Для повышения точности локальные гистограммы можно нормализовать по контрасту, вычислив меру интенсивности по большей области изображения, называемой блоком, а затем используя это значение для нормализации всех ячеек внутри блока. Такая нормализация приводит к лучшей инвариантности к изменениям освещения и затенения.
Дескриптор HOG имеет несколько ключевых преимуществ по сравнению с другими дескрипторами. Поскольку он работает с локальными ячейками, он инвариантен к геометрическим и фотометрическим преобразованиям, за исключением ориентации объекта. Такие изменения могут проявляться только в более крупных пространственных областях. Более того, как обнаружили Далал и Триггс, грубая пространственная выборка, тонкая выборка ориентации и сильная локальная фотометрическая нормализация позволяют игнорировать индивидуальные движения тела пешеходов, пока они сохраняют примерно вертикальное положение. Таким образом, дескриптор HOG особенно подходит для обнаружения человека на изображениях. [3]
Первым шагом расчета во многих детекторах признаков при предварительной обработке изображения является обеспечение нормализованных значений цвета и гаммы. Однако, как отмечают Далал и Триггс, этот шаг можно опустить при вычислении дескриптора HOG, поскольку последующая нормализация дескриптора по сути достигает того же результата. Таким образом, предварительная обработка изображения оказывает незначительное влияние на производительность. Вместо этого первым шагом расчета является вычисление значений градиента. Наиболее распространенным методом является применение одномерной центрированной, точечной дискретной производной маски в одном или обоих направлениях: горизонтальном и вертикальном. В частности, этот метод требует фильтрации данных цвета или интенсивности изображения с помощью следующих ядер фильтра:
Далал и Триггс протестировали другие, более сложные маски, такие как маска Собеля 3x3 или диагональные маски, но эти маски, как правило, хуже справлялись с обнаружением людей на изображениях. Они также экспериментировали с гауссовым сглаживанием перед применением производной маски, но также обнаружили, что исключение любого сглаживания на практике давало лучшие результаты. [4]
Вторым шагом расчета является создание гистограмм ячеек. Каждый пиксель в ячейке отдает взвешенный голос за гистограмму на основе ориентации на основе значений, найденных при вычислении градиента. Сами ячейки могут иметь прямоугольную или радиальную форму, а каналы гистограммы равномерно распределены по 0–180 градусам или 0–360 градусам, в зависимости от того, является ли градиент «беззнаковым» или «со знаком». Далал и Триггс обнаружили, что беззнаковые градиенты, используемые в сочетании с 9 каналами гистограммы, показали наилучшие результаты в их экспериментах по обнаружению людей, отметив при этом, что знаковые градиенты приводят к значительным улучшениям в распознавании некоторых других классов объектов, таких как автомобили или мотоциклы. Что касается веса голоса, вклад пикселя может быть либо самой величиной градиента, либо некоторой функцией величины. В тестах сама величина градиента обычно дает наилучшие результаты. Другие варианты веса голоса могут включать квадратный корень или квадрат величины градиента или некоторую обрезанную версию величины. [5]
Для учета изменений освещенности и контрастности необходимо локально нормализовать интенсивность градиента, что требует группировки ячеек в более крупные, пространственно связанные блоки. Дескриптор 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 содержат ячейки с несколькими каналами ориентации, в то время как контексты формы используют только один счетчик присутствия ребра в своей формулировке. [6]
Далал и Триггс исследовали четыре различных метода нормализации блока. Пусть будет ненормализованным вектором, содержащим все гистограммы в данном блоке, будет его k -нормой для и будет некоторой малой константой (точное значение, как мы надеемся, неважно). Тогда фактор нормализации может быть одним из следующих:
В своих экспериментах Далал и Триггс обнаружили, что схемы L2-hys, L2-norm и L1-sqrt обеспечивают схожую производительность, в то время как L1-norm обеспечивает немного менее надежную производительность; однако все четыре метода показали очень значительное улучшение по сравнению с ненормализованными данными. [8]
Дескрипторы HOG могут использоваться для распознавания объектов, предоставляя их в качестве признаков алгоритму машинного обучения . Далал и Триггс использовали дескрипторы HOG в качестве признаков в машине опорных векторов (SVM); [9] однако дескрипторы 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−4. На наборе INRIA дескрипторы C-HOG и R-HOG дали частоту пропусков обнаружения примерно 0,1 при частоте ложных срабатываний 10−4 . Обобщенные вейвлеты Хаара представляют собой следующий наиболее эффективный подход: они дали частоту пропусков примерно 0,01 при частоте ложных срабатываний 10−4 на наборе MIT и примерно 0,3 на наборе INRIA. Дескрипторы PCA-SIFT и дескрипторы контекста формы оба показали довольно плохие результаты на обоих наборах данных. Оба метода дали частоту промахов 0,1 при частоте ложноположительных результатов 10−4 на наборе MIT и частоту промахов около 0,5 при частоте ложноположительных результатов 10−4 на наборе INRIA .
В рамках семинара Pascal Visual Object Classes 2006, Далал и Триггс представили результаты применения гистограммы дескрипторов ориентированных градиентов к объектам изображения, отличным от людей, таким как автомобили, автобусы и велосипеды, а также к обычным животным, таким как собаки, кошки и коровы. Они включили в свои результаты оптимальные параметры для формулировки блока и нормализации в каждом случае. Изображение в ссылке ниже показывает некоторые из их примеров обнаружения для мотоциклов. [10]
В рамках Европейской конференции по компьютерному зрению (ECCV) 2006 года Далал и Триггс объединились с Корделией Шмид , чтобы применить детекторы HOG к проблеме обнаружения человека в фильмах и видео. Они объединили дескрипторы HOG на отдельных видеокадрах со своими недавно введенными внутренними гистограммами движения (IMH) на парах последующих видеокадров. Эти внутренние гистограммы движения используют градиентные величины из полей оптического потока , полученные из двух последовательных кадров. Эти градиентные величины затем используются таким же образом, как и те, которые получены из статических данных изображения в рамках подхода дескриптора HOG. При тестировании на двух больших наборах данных, взятых из нескольких фильмов, объединенный метод HOG-IMH дал показатель пропусков приблизительно 0,1 при ложноположительном показателе. [11]
На симпозиуме по интеллектуальным транспортным средствам в 2006 году Ф. Сюард, А. Ракотомамонджи и А. Бенсраир представили полную систему обнаружения пешеходов на основе дескрипторов HOG. Их система работает с использованием двух инфракрасных камер. Поскольку на инфракрасных изображениях люди выглядят ярче, чем их окружение, система сначала определяет интересующие позиции в большем поле зрения, где люди могут находиться. Затем классификаторы опорных векторных машин работают с дескрипторами HOG, взятыми из этих меньших позиций интереса, чтобы сформулировать решение относительно присутствия пешехода. Как только пешеходы оказываются в поле зрения, фактическое положение пешехода оценивается с использованием стереозрения. [12]
На конференции IEEE по компьютерному зрению и распознаванию образов в 2006 году Цян Чжу, Шай Авидан, Мэй-Чен Йе и Кван-Тин Ченг представили алгоритм для значительного ускорения обнаружения человека с использованием методов дескрипторов HOG. Их метод использует дескрипторы HOG в сочетании с алгоритмом каскадных классификаторов, обычно применяемым с большим успехом для обнаружения лиц. Кроме того, вместо того, чтобы полагаться на блоки одинакового размера, они вводят блоки, которые различаются по размеру, местоположению и соотношению сторон. Чтобы изолировать блоки, наиболее подходящие для обнаружения человека, они применили алгоритм AdaBoost для выбора тех блоков, которые будут включены в каскад. В своих экспериментах их алгоритм достиг производительности, сопоставимой с исходным алгоритмом Далала и Триггса, но работал со скоростью до 70 раз быстрее. В 2006 году исследовательские лаборатории Mitsubishi Electric подали заявку на патент США на этот алгоритм под номером заявки 20070237387. [13]
На Международной конференции IEEE по обработке изображений в 2010 году Руи Ху, Марк Банард и Джон Колломосс расширили дескриптор HOG для использования в поиске изображений на основе эскизов (SBIR). Плотное поле ориентации было экстраполировано из доминирующих ответов в детекторе границ Кэнни при ограничении гладкости Лапласа , и HOG вычислялось по этому полю. Полученный дескриптор поля градиента HOG (GF-HOG) захватил локальную пространственную структуру в эскизах или картах границ изображения. Это позволило использовать дескриптор в системе поиска изображений на основе контента , доступной для поиска по нарисованным от руки формам. [14] Было показано, что адаптация GF-HOG превосходит существующие дескрипторы гистограмм градиента, такие как SIFT , SURF и HOG, примерно на 15 процентов при выполнении задачи SBIR. [15]
В 2010 году Мартин Крюкханс представил усовершенствование дескриптора HOG для 3D-облаков точек. [16] Вместо градиентов изображения он использовал расстояния между точками (пикселями) и плоскостями, так называемые остатки, для характеристики локальной области в облаке точек. Его гистограмма дескриптора ориентированных остатков (HOR) успешно использовалась в задачах обнаружения объектов 3D-облаков точек. [17]
![{\displaystyle [-1,0,1]{\text{ и }}[-1,0,1]^{\top }.\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b4386f322a5d7a8c58af1d6288bcc5ab128e3ce5)
