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

{{translate|en}}
'''Гистограмма направленных градиентов''' ({{lang-en|Histogram of Oriented Gradients, HOG}}) — дескрипторы особых точек, которые используются в [[Компьютерное зрение|компьютерном зрении]] и [[Обработка изображений|обработке изображений]] с целью [[Распознавание объектов|распознавания объектов]]. Данная техника основана на подсчете количества направлений градиента в локальных областях изображения. Этот метод похож на [[:en:Edge orientation histogram|гистограммы направления края]], [[SIFT|дескрипторы SIFT]] и [[:en:Shape context|контексты формы]], но отличается тем, что вычисляется на плотной сетке равномерно распределенных ячеек и использует нормализацию перекрывающегося локального контраста для увеличения точности.

[[Navneet Dalal|Навнит Далал]] и [[:en:Bill Triggs|Билл Триггс]], исследователи [[INRIA]], впервые описали гистограмму направленных градиентов в своей работе на [[Conference on Computer Vision and Pattern Recognition|CVPR]] в июне 2005 года. В этой работе они использовали алгоритм для нахождения пешеходов на статичных изображениях, хотя впоследствии расширили область применения до нахождения людей на видео, а также различных животных и машин на статичных изображениях.

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

Дескриптор HOG имеет несколько преимуществ над другими дескрипторами. Поскольку HOG работает локально, метод поддерживает инвариантность геометрических и фотометрических преобразований, за исключением ориентации объекта. Подобные изменения появятся только в больших фрагментах изображения. Более того, как обнаружили Далал и Триггс, грубое разбиение пространства, точное вычисление направлений и сильная локальная фотометрическая нормализация позволяют игнорировать движения пешеходов, если они поддерживают вертикальное положение тела. Дескриптор HOG, таким образом, является хорошим средством нахождения людей на изображениях.<ref>{{cite web|url=http://lear.inrialpes.fr/people/triggs/pubs/Dalal-cvpr05.pdf|title=Histograms of Oriented Gradients for Human Detection, pg. 2|archiveurl=https://www.webcitation.org/6DvoEMDXQ?url=http://lear.inrialpes.fr/people/triggs/pubs/Dalal-cvpr05.pdf|archivedate=2013-01-25}}</ref>

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

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

: <math>[-1, 0, 1]</math> и <math>[-1, 0, 1]^T.</math>

Далал и Триггс использовали более сложные маски, такие как Собел 3x3 ([[Оператор Собеля]]) или диагональные маски, но эти маски показали более низкую производительность для данной задачи. Они также экспериментировали с [[Размытие по Гауссу|размытием по Гауссу]] перед применением дифференцирующей маски, но также обнаружили, что пропуск этого шага увеличивает быстродействие без заметной потери качества.<ref name=autogenerated1>{{cite web|url=http://lear.inrialpes.fr/people/triggs/pubs/Dalal-cvpr05.pdf|title=Histograms of Oriented Gradients for Human Detection, pg. 4|archiveurl=https://www.webcitation.org/6DvoEMDXQ?url=http://lear.inrialpes.fr/people/triggs/pubs/Dalal-cvpr05.pdf|archivedate=2013-01-25}}</ref>

=== Группировка направлений ===
На следующем шаге вычисляются гистограммы ячеек. Каждый пиксель в ячейке участвует во взвешенном голосовании для каналов гистограммы направлений, основанном на значении градиентов. Ячейки могут быть прямоугольной или круглой формы, каналы гистограммы равномерно распределяются от 0 до 180 или же от 0 до 360 градусов, в зависимости от того, вычисляется «знаковый» или «беззнаковый градиент». Далал и Триггс обнаружили, что беззнаковый градиент совместно с девятью каналами гистограммы дает лучшие результаты при распознавании людей. При распределении весов в голосовании вес пикселя может задаваться либо абсолютным значением градиента, либо некоторой функцией от него; в реальных тестах абсолютное значение градиента дает лучшие результаты. Другими возможными вариантами могут быть квадратный корень, квадрат или урезанное абсолютное значение градиента.<ref>{{cite web|url=http://lear.inrialpes.fr/people/triggs/pubs/Dalal-cvpr05.pdf|title=Histograms of Oriented Gradients for Human Detection, pg. 5|archiveurl=https://www.webcitation.org/6DvoEMDXQ?url=http://lear.inrialpes.fr/people/triggs/pubs/Dalal-cvpr05.pdf|archivedate=2013-01-25}}</ref>

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

Блоки C-HOG имеют 2 разновидности: с цельной центральной ячейкой и разделенной на сектора. Эти блоки могут быть описаны 4 параметрами: количество секторов и колец, радиус центрального кольца и коэффициент расширения для радиусов остальных колец. Далал и Триггс обнаружили, что обе разновидности показали одинаковый результат, и разделение на 2 кольца и 4 сектора с радиусом 4 пиксела и коэффициентом расширения 2 дало лучший результат в их эксперименте. Кроме того, гауссово взвешивание не дало никаких улучшений при использовании блоков C-HOG. Эти блоки похожи на [[:en:shape context|контексты формы]], но имеют важное отличие: блоки C-HOG содержат ячейки с несколькими каналами направлений, в то время как контексты формы используют только наличие одного края.<ref name=autogenerated2>{{cite web|url=http://lear.inrialpes.fr/people/triggs/pubs/Dalal-cvpr05.pdf|title=Histograms of Oriented Gradients for Human Detection, pg. 6|archiveurl=https://www.webcitation.org/6DvoEMDXQ?url=http://lear.inrialpes.fr/people/triggs/pubs/Dalal-cvpr05.pdf|archivedate=2013-01-25}}</ref>

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

: L2-норма: <math>f = {v \over \sqrt{\|v\|^2_2+e^2}}</math>

: L2-hys: L2-норма ограничивается сверху (значения v, бо́льшие 0,2, полагаются равными 0,2) и перенормируется, как в<ref>D. G. Lowe. Distinctive image features from scale-invariant keypoints. IJCV, 60(2):91-110, 2004.</ref>

: L1-норма: <math>f = {v \over (\|v\|_1+e)}</math>

: корень из L1-нормы: <math>f = \sqrt{v \over (\|v\|_1+e)}</math>

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

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

== Тестирование ==
В оригинальном эксперименте по обнаружению людей, Далал и Триггс сравнивали дескрипторы R-HOG и C-HOG с [[:en:generalized Haar wavelet|обобщенными вейвлетами Хаара]] и [[:en:shape context|контекстами формы]]. Обобщенные вейвлеты Хаара являются направленными вейвлетами Хаара и были использованы в 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 имеют несколько меньшую долю пропущенных изображений при фиксированной доле ошибок первого рода на обоих наборах изображений.

{| class="wikitable"
|-
! Дескриптор || Набор изображений || Доля пропущенных изображений || Доля ошибок первого рода
|-
| HOG || MIT || ≈0 || 10<sup>&minus;4</sup>
|-
| HOG || INRIA || 0.1 || 10<sup>&minus;4</sup>
|-
| Обобщенные вейвлеты Хаара || MIT || 0.01 || 10<sup>&minus;4</sup>
|-
| Обобщенные вейвлеты Хаара || INRIA || 0.3 || 10<sup>&minus;4</sup>
|-
| PCA-SIFT, контексты формы || MIT || 0.1 || 10<sup>&minus;4</sup>
|-
| PCA-SIFT, контексты формы || INRIA || 0.5 || 10<sup>&minus;4</sup>
|} По следующей ссылке можно найти соответствующий график [[:en:Detection Error Tradeoff|DET]].<ref name=autogenerated1 />

== Дальнейшее развитие ==
В рамках семинара Pascal Visual Object Classes в 2006 году, Далал и Триггс представили результаты применения HOG-дескрипторов к поиску на изображениях не только людей, но и машин, автобусов, велосипедов, собак, кошек и коров, а также оптимальные параметры для формирования и нормализации блоков в каждом случае. По ссылке можно посмотреть примеры для обнаружения мотоциклов.<ref>{{cite web|url=http://www.pascal-network.org/challenges/VOC/voc2006/slides/dalal.pdf|title=Object Detection using Histograms of Oriented Gradients|archiveurl=https://www.webcitation.org/6DvoEuAvL?url=http://pascallin.ecs.soton.ac.uk/challenges/VOC/voc2006/slides/dalal.pdf|archivedate=2013-01-25}}</ref>

Затем в рамках [[:en:European Conference on Computer Vision|Европейской конференции по компьютерному зрению]] 2006 года, Далал и Триггс совместно с Корделией Шмид применили HOG-дескрипторы к распознаванию людей на видео. Предложенный ими способ заключается в совместном использовании обычных HOG-дескрипторов на каждом кадре и гистограмм внутреннего движения (англ. Internal Motion Histograms, IMH) на парах последовательных кадров. IMH-дескрипторы используют длины градиентов, полученных из оптического потока между двумя последовательными кадрами. 
<!--
These gradient magnitudes are then used in the same manner as those produced from static image data within the HOG descriptor approach. When testing on two large datasets taken from several movie DVDs, the combined HOG-IMH method yielded a miss rate of approximately 0.1 at a <math>10^{-4}</math> false positive rate.<ref>{{cite web |url=http://www.acemedia.org/aceMedia/files/document/wp7/2006/eccv06-inria.pdf | title=Human Detection Using Oriented Histograms of Flow and Appearance }}</ref>

At the [[Intelligent Vehicles Symposium]] in 2006, [[F. Suard]], [[A. Rakotomamonjy]], and [[A. Bensrhair]] introduced a complete system for pedestrian detection based on HOG descriptors. Their system operates using two infrared cameras. Since human beings appear brighter than their surroundings on infrared images, the system first locates positions of interest within the larger view field where humans could possibly be located. Then normal Support Vector Machine classifiers operate on the HOG descriptors taken from these smaller positions of interest to formulate a decision regarding the presence of a pedestrian. Once pedestrians are located within the view field, the actual position of the pedestrian is estimated using stereovision.<ref>{{cite web  |url=http://www.ce.unipr.it/people/broggi/publications/iv2006-pd-aziz.pdf | title=Pedestrian Detection using Infrared images and Histograms of Oriented Gradients }}</ref>

At the [[IEEE]] [[Conference on Computer Vision and Pattern Recognition]] in 2006, [[Qiang Zhu]], [[Shai Avidan]], [[Mei-Chen Yeh]], and [[Kwang-Ting Cheng]] presented an algorithm to significantly speed up human detection using HOG descriptor methods. Their method uses HOG descriptors in combination with the [[cascade of rejecters]] algorithm normally applied with great success to the problem of face detection. Also, rather than relying on blocks of uniform size, they introduce blocks that vary in size, location, and aspect ratio. In order to isolate the blocks best suited for human detection, they applied the [[AdaBoost]] algorithm to select those blocks to be included in the rejecter cascade. In their experimentation, their algorithm achieved comparable performance to the original Dalal and Triggs algorithm, but operated at speeds up to 70 times faster. In April 2006, the [[Mitsubishi Electric Research Laboratories]] applied for the U.S. Patent of this algorithm under application number 20070237387.<ref>{{cite web |url= http://seaboy.tistory.com/attachment/cfile25.uf@116008124A989DCB0E0C23.pdf | title=Fast Human Detection Using a Cascade of Histograms of Oriented Gradients }}</ref>
-->

== См. также ==
* [[Нахождение углов]]
* [[Нахождение пешеходов]]
* [[Особые точки (компьютерное зрение)]]
* [[Нахождение особых точек (компьютерное зрение)]]
* [[Выделение признаков]]
* [[Распознавание объектов]]
* [[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
{{rq|wikify}}

[[Категория:Выделение признаков (компьютерное зрение)]]
[[Категория:Распознавание образов]]