Вікіпедія

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

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

Концепції, що лежать в основі HOG, без використання терміну HOG, вперше описав Роберт К. МакКоннелл з Wayland Research Inc. у патентній заявці 1986 року.[1] 1994 року ці концепції використали Дослідницькі лабораторії Міцубісі Електрик[en].[2] Проте використання набуло широкого поширення лише 2005 року, коли Навніт Далал та Білл Тріггс, дослідники з Французького національного інституту досліджень з комп'ютерних наук і автоматизації (INRIA), представили на Конференції з комп'ютерного бачення та розпізнавання образів[en] (CVPR) свою додаткову працю щодо описувачів HOG. У цій праці вони зосередилися на виявлянні пішоходів[en] на статичних зображеннях, хоча відтоді вони розширили свої перевірки, включивши виявляння людей на відео, а також різноманітних поширених тварин та транспортних засобів на статичних зображеннях.

Теорія ред.

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

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

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

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

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

  та  

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

Групування спрямувань ред.

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

Блоки описувача ред.

Щоби враховувати зміни в освітленні та контрасті, вираженість градієнта потрібно локально унормовувати, що вимагає групування комірок у більші, просторово з'єднані блоки. Тож описувач HOG це з'єднаний вектор складових унормованих коміркових гістограм з усіх областей блоку. Ці блоки зазвичай перекриваються, тобто кожна комірка робить внесок у кінцевий описувач понад одного разу. Існує дві основні геометрії блоків: прямокутні (англ. rectangular) блоки R-HOG та кругові (англ. circular) блоки 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 виглядають схожими на описувачі значення форми, але сильно відрізняються тим, що містять комірки з декількома каналами спрямування, тоді як значення форми в їхньому формулюванні використовують лише один підрахунок присутності контуру.[6]

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

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

L2-норма:  
L2-гіс: L2-норма з подальшим обтинанням (обмеженням максимальних значень v до 0,2) й перенормовуванням, як у[7]
L1-норма:  
L1-корінь:  

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

Розпізнавання об'єктів ред.

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

У рамках Європейської конференції з комп'ютерного бачення[en] (ECCV) 2006 року Далал та Тріггс об'єдналися з Корделією Шмід[en], щоби застосувати описувачі HOG до задачі виявляння людей у фільмах та відео. Вони поєднали описувачі HOG на окремих відеокадрах із нещодавно запропонованими гістограмами внутрішнього руху (англ. internal motion histograms, IMH) на парах послідовних відеокадрів. Ці гістограми внутрішнього руху використовують величини градієнта з полів оптичного потоку, отриманих із двох послідовних кадрів. Потім ці величини градієнта використовують так само, як і створювані з даних статичного зображення у підході описувача HOG. Під час перевірки на двох великих наборах даних, взятих із кількох фільмів, об'єднаний метод HOG-IMH дав рівень невиявлень приблизно 0,1 за хибнопозитивного рівня  .[10]

На Симпозіумі з інтелектуальних транспортних засобів 2006 року Ф. Суард, А. Ракотомамонджі та А. Бенсрайр представили повну систему виявляння пішоходів на основі описувачів HOG. Їхня система працює за допомогою двох інфрачервоних камер. Оскільки на інфрачервоних зображеннях люди виглядають яскравішими за навколишнє оточення, система спочатку встановлює особливі положення в більшому полі огляду, де ймовірно можуть перебувати люди. Потім класифікатори методу опорних векторів працюють з описувачами HOG, взятими з цього меншого числа особливих положень, щоби сформулювати рішення щодо присутності пішохода. Коли пішоходи перебувають у полі огляду, фактичне положення пішохода оцінюють за допомогою стереозору.[11]

На Конференції з комп'ютерного бачення та розпізнавання образів[en] IEEE 2006 року Цян Чжу, Шай Авідан, Мей-Чен Є та Кван-Тін Чен представили алгоритм для значного прискорення виявляння людей за допомогою методів описувача HOG. Їхній метод використовує описувачі HOG у поєднанні з алгоритмом каскадних класифікаторів[en], який зазвичай успішно застосовують для виявляння облич. Також, замість того, щоби покладатися на блоки однакового розміру, вони запроваджують блоки, які різняться за розміром, розташуванням та співвідношенням сторін. Щоби виділяти блоки, які найкраще підходять для виявляння людей, вони застосували алгоритм AdaBoost[en], щоб обирати блоки для включення до каскаду. Під час експериментів їхній алгоритм досяг продуктивності, порівнянної з оригінальним алгоритмом Далала та Тріггса, але працював у 70 разів швидше. 2006 року Дослідницькі лабораторії Міцубісі Електрик[en] подали заявку на отримання патенту США на цей алгоритм з номером заявки 20070237387.[12]

На Міжнародній конференції з обробки зображень IEEE 2010 року Руй Ху, Марк Банард та Джон Колломос розширили описувач HOG для використання в пошуку зображень за начерками (англ. sketch based image retrieval, SBIR). Щільне поле напрямків було екстрапольовано з переважних відгуків у виявлячі контурів Кенні за лапласового обмеження гладкості, й над цим полем обчислювали HOG. Отриманий описувач HOG градієнтного поля (англ. gradient field HOG, GF-HOG) вловлював локальну просторову структуру в нарисах та відображеннях контурів зображення. Це дозволило використовувати цей описувач у системі пошуку зображень за вмістом, в якій можливо шукати за нарисованими від руки фігурами.[13] Було показано, що пристосування GF-HOG при виконанні завдання SBIR перевершує наявні градієнтно-гістограмні описувачі, такі як SIFT, SURF та HOG, приблизно на 15 відсотків.[14]

2010 року Мартін Крюкханс запропонував удосконалення описувача HOG для тривимірних хмар точок.[15] Замість градієнтів зображення він використовував відстані між точками (пікселями) й площинами, так звані залишки, щоб охарактеризувати локальну область у хмарі точок. Його описувач гістограмами напрямлених залишків (англ. histogram of oriented residuals, HOR) успішно використали в задачах виявляння об'єктів тривимірних хмар точок.[16]

Див. також ред.

Примітки ред.

  1. ↑ Method of and apparatus for pattern recognition. (англ.)
  2. ↑ Orientation Histograms for Hand Gesture Recognition. (англ.)
  3. ↑ Histograms of Oriented Gradients for Human Detection (PDF). с. 2. (англ.)
  4. ↑ Histograms of Oriented Gradients for Human Detection (PDF). с. 4. (англ.)
  5. ↑ Histograms of Oriented Gradients for Human Detection (PDF). с. 5. (англ.)
  6. ↑ а б Histograms of Oriented Gradients for Human Detection (PDF). с. 6. (англ.)
  7. ↑ D. G. Lowe. Distinctive image features from scale-invariant keypoints. IJCV, 60(2):91–110, 2004. (англ.)
  8. ↑ Histograms of Oriented Gradients for Human Detection (PDF). с. 1. (англ.)
  9. ↑ Object Detection using Histograms of Oriented Gradients (PDF). Архів оригіналу (PDF) за 5 грудня 2013. Процитовано 10 грудня 2007. (англ.)
  10. ↑ Human Detection Using Oriented Histograms of Flow and Appearance (PDF). Архів оригіналу (PDF) за 5 вересня 2008. Процитовано 10 грудня 2007. (первинний документ більше не доступний; подібна праця [Архівовано 2023-01-28 у Wayback Machine.] (англ.))
  11. ↑ Pedestrian Detection using Infrared images and Histograms of Oriented Gradients (PDF). (англ.)
  12. ↑ Fast Human Detection Using a Cascade of Histograms of Oriented Gradients (PDF). (англ.)
  13. ↑ Gradient Field Descriptor for Sketch based Image Retrieval and Localisation (PDF). (англ.)
  14. ↑ A Performance Evaluation of the Gradient Field HOG Descriptor for Sketch based Image Retrieval (PDF). (англ.)
  15. ↑ Krückhans, Martin. Ein Detektor für Ornamente auf Gebäudefassaden auf Basis des "histogram-of-oriented-gradients"-Operators (PDF). Архів оригіналу (PDF) за 16 листопада 2010. Процитовано 28 січня 2023. (нім.)
  16. ↑ Semantic 3D Octree Maps based on Conditional Random Fields (PDF). (англ.)

Посилання ред.

Отримано з https://uk.wikipedia.org/w/index.php?title=Гістограма_напрямлених_градієнтів&oldid=41058435