Гістогра́ма напря́млених градіє́нтів (ГНГ, ) — це один з , які використовують у комп'ютернім баченні та обробці зображень з метою виявляння об'єктів. Ця методика підраховує напрямки градієнта в локалізованих частинах зображення. Цей метод подібний до методу , описувачів масштабоінваріантного перетворення ознак, та значення форми, але відрізняється тим, що його обчислюють на щільній ґратці рівномірно розташованих комірок, і що він використовує нормування локального контрасту з перекриттям для підвищення точності.

Концепції, що лежать в основі HOG, без використання терміна HOG, вперше описав з у патентній заявці 1986 року. 1994 року ці концепції використали . Проте використання набуло широкого поширення лише 2005 року, коли та , дослідники з Французького національного інституту досліджень з комп'ютерних наук і автоматизації (INRIA), представили на (CVPR) свою додаткову працю щодо описувачів HOG. У цій праці вони зосередилися на на статичних зображеннях, хоча відтоді вони розширили свої перевірки, включивши виявляння людей на відео, а також різноманітних поширених тварин та транспортних засобів на статичних зображеннях.

Теорія

Основна ідея описувача гістограмами напрямлених градієнтів полягає в можливості описувати зовнішній вигляд та форму локального об'єкта на зображенні розподілом градієнтів яскравості та напрямків контурів. Зображення ділять на невеликі з'єднані області, звані комірками, й для пікселів у кожній комірці складають гістограму напрямків градієнта. Цей описувач — з'єднання цих гістограм. Для кращої точності локальні гістограми можливо унормовувати за контрастом, обчислюючи міру яскравості в більшій області зображення, званій блоком, й використовуючи потім це значення для унормовування всіх клітинок у блоці. Це унормовування дає кращу інваріантність щодо змін в освітленні та затіненні.

Описувач HOG має кілька ключових переваг над іншими описувачами. Оскільки він діє на локальних комірках, він інваріантний щодо геометричних і фотометричних перетворень, за винятком спрямування об'єкта. Такі зміни проявлятимуться лише у великих просторових областях. Крім того, як виявили Далал та Тріггс, груба просторова вибірка, точна вибірка спрямування, та сильне локальне фотометричне унормовування дозволяють ігнорувати окремі рухи тіла пішоходів, якщо вони зберігають приблизно вертикальне положення. Тож описувач HOG особливо зручний для виявляння людей на зображеннях.

Втілення алгоритму

Обчислення градієнта

Перший крок обчислення в багатьох виявлячах ознак у попередній обробці зображення — забезпечення унормованих значень кольору та гами. Проте, як зазначають Далал та Тріггс, цей крок в обчисленні описувача HOG можливо пропустити, оскільки наступне нормування описувача по суті досягає того же результату. Таким чином, попередня обробка зображення мало впливає на продуктивність. Натомість, першим кроком обчислення є обчислення значень градієнта. Найпоширеніший метод — застосування одновимірної центрованої точкової дискретної маски похідної в одному з, або обох, горизонтальному й вертикальному, напрямках. Конкретніше, цей метод вимагає фільтрування даних кольору або яскравості зображення наступними ядрами фільтрів:

та

Далал та Тріггс перевіряли інші, складніші маски, такі як маска Собеля 3×3 та діагональні маски, але вони загалом виявляли людей на зображеннях гірше. Вони також експериментували з гауссовим згладжуванням перед застосуванням маски похідної, але так само виявили, що повне уникання згладжування працювало на практиці краще.

Групування спрямувань

Другий крок обчислення — створення гістограм комірок. Кожен піксель у комірці дає зважений голос за залежний від спрямування засік гістограми на основі значень, знайдених під час обчислення градієнта. Самі комірки можуть мати прямокутну або радіальну форму, а канали гістограми розподілено рівномірно від 0 до 180 градусів або від 0 до 360 градусів, залежно від того, чи градієнт «беззнаковий» чи «знаковий». Далал та Тріггс виявили, що беззнакові градієнти, які використовують у поєднанні з 9 каналами гістограми, показали найкращі результати в їхніх експериментах з виявляння людей, і водночас зазначили, що знакові градієнти дають значні поліпшення в розпізнаванні деяких інших класів об'єктів, таких як автомобілі чи мотоцикли. Що стосується ваги голосу, внесок пікселя може бути або власне величиною градієнта, або деякою її функцією. У перевірках найкращі результати зазвичай дає власне величина градієнта. До інших варіантів ваги голосування можуть належати квадратний корінь або квадрат величини градієнта, або деяка усічена версія цієї величини.

Блоки описувача

Щоби враховувати зміни в освітленні та контрасті, вираженість градієнта потрібно локально унормовувати, що вимагає групування комірок у більші, просторово з'єднані блоки. Тож описувач HOG це з'єднаний вектор складових унормованих коміркових гістограм з усіх областей блоку. Ці блоки зазвичай перекриваються, тобто кожна комірка робить внесок у кінцевий описувач понад одного разу. Існує дві основні геометрії блоків: прямокутні () блоки R-HOG та кругові () блоки C-HOG. Блоки R-HOG це зазвичай квадратні ґратки, подані трьома параметрами: кількістю комірок на блок, кількістю пікселів на комірку, та кількістю каналів на гістограму комірки. В експерименті Далала та Тріггса з виявляння людей оптимальними параметрами були чотири комірки 8×8 пікселів на блок (16×16 пікселів на блок) з 9 гістограмними каналами. Крім того, вони виявили, що можливо досягти деякого незначного поліпшення продуктивності, застосовуючи гауссове просторове вікно в кожному блоці перед зведенням гістограмних голосів задля зменшення ваги пікселів біля країв блоків. Блоки R-HOG виглядають вельми схожими на описувачі масштабоінваріантного ознакового перетворення (SIFT); проте, незважаючи на подібність їхнього формування, блоки R-HOG обчислюють у щільних ґратках в якомусь одному масштабі без вирівнювання спрямування, тоді як описувачі SIFT зазвичай обчислюють у розріджених масштабоінваріантних ключових точках зображення, й обертають для вирівнювання спрямування. Крім того, блоки R-HOG використовують для кодування інформації про просторову форму у поєднанні, тоді як описувачі SIFT використовують поодинці.

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

Унормовування блоків

Далал та Тріггс дослідили чотири різні методи унормовування блоків. Нехай  — ненормований вектор, що містить усі гістограми в даному блоці,  — його k -норма для , а  — деяка мала стала (точне значення, як можна сподіватися, неважливе). Тоді коефіцієнт унормовування може бути одним із наступних:

L2-норма:

L2-гіс: L2-норма з подальшим обтинанням (обмеженням максимальних значень v до 0,2) й перенормовуванням, як уD. G. Lowe. Distinctive image features from scale-invariant keypoints. IJCV, 60(2):91–110, 2004.

L1-норма:

L1-корінь:

У своїх експериментах Далал та Тріггс виявили, що схеми L2-гіс, L2-норма та L1-корінь забезпечують подібну продуктивність, тоді як L1-норма забезпечує трохи менш надійну; проте всі чотири методи показали дуже значне поліпшення порівняно з ненормованими даними.

Розпізнавання об'єктів

Описувачі 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. Другий набір розробили Далал та Тріггс виключно для свого експерименту з виявляння людей через те, що на наборі MIT описувачі HOG працювали майже ідеально. Їхній набір, відомий як 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 Далал та Тріггс презентували результати застосування описувачів гістограмами напрямлених градієнтів до інших об'єктів зображень, крім людей, таких як автомобілі, автобуси та велосипеди, а також поширених тварин, таких як собаки, коти та корови. До своїх результатів вони включили оптимальні параметри для формулювання блоку та нормування в кожному випадку. Зображення в наведеному нижче посиланні показує деякі приклади їхнього виявлення для мотоциклів.