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

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

Навнит Далал и Билл Триггс, исследователи INRIA, впервые описали гистограмму направленных градиентов в своей работе на CVPR в июне 2005 года. В этой работе они использовали алгоритм для нахождения пешеходов на статичных изображениях, хотя впоследствии расширили область применения до нахождения людей на видео, а также различных животных и машин на статичных изображениях.

Теория

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

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

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

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

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

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

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

Группировка направлений

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

Блоки дескрипторов

Для принятия во внимание яркости и контрастности градиенты следует локально нормировать, для чего ячейки нужно сгруппировать в более крупные связные блоки. Дескриптор 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 содержат ячейки с несколькими каналами направлений, в то время как контексты формы используют только наличие одного края.

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

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

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

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

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

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

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

SVM-классификатор

Основная статья: Метод опорных векторов

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

Тестирование

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

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

По результатам исследований, дескрипторы C-HOG и R-HOG дают сравнимые результаты, причем C-HOG имеют несколько меньшую долю пропущенных изображений при фиксированной доле ошибок первого рода на обоих наборах изображений.

Дескриптор	Набор изображений	Доля пропущенных изображений	Доля ошибок первого рода
HOG	MIT	≈0	10−4
HOG	INRIA	0.1	10−4
Обобщенные вейвлеты Хаара	MIT	0.01	10−4
Обобщенные вейвлеты Хаара	INRIA	0.3	10−4
PCA-SIFT, контексты формы	MIT	0.1	10−4
PCA-SIFT, контексты формы	INRIA	0.5	10−4

По следующей ссылке можно найти соответствующий график DET.

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

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

Затем в рамках Европейской конференции по компьютерному зрению 2006 года, Далал и Триггс совместно с Корделией Шмид применили HOG-дескрипторы к распознаванию людей на видео. Предложенный ими способ заключается в совместном использовании обычных HOG-дескрипторов на каждом кадре и гистограмм внутреннего движения (англ. Internal Motion Histograms, IMH) на парах последовательных кадров. IMH-дескрипторы используют длины градиентов, полученных из оптического потока между двумя последовательными кадрами.

См. также

• Нахождение углов
• Нахождение пешеходов
• Особые точки (компьютерное зрение)
• Нахождение особых точек (компьютерное зрение)
• Выделение признаков
• Распознавание объектов
• SIFT

Ссылки

• http://www.mathworks.com/matlabcentral/fileexchange/33863 Реализация для Matlab (mex-файл)
• http://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 (домашняя страница Навнита Далала)
• https://web.archive.org/web/20100505083112/http://pascal.inrialpes.fr/data/human/ - Набор изображений INRIA с людьми
• http://cbcl.mit.edu/software-datasets/PedestrianData.html - Набор изображений пешеходов MIT