Ознаки з прискореної сегментної перевірки

Ознаки з прискореної сегментної перевірки (англ. features from accelerated segment test, FAST) — це метод виявляння кутів, який можливо використовувати для виділяння точок ознак й наступного відстежування та відображування об'єктів у багатьох задачах комп'ютерного бачення. Виявляч кутів FAST первинно розробили Едвард Ростен та Том Драммонд, й опублікували 2006 року.^[1] Найбільш багатообіцяючою перевагою виявляча кутів FAST є його обчислювальна ефективність. Відповідно до його назви, він справді швидший за багато інших добре відомих методів виділяння ознак, таких як різниця гауссіанів (РГ, англ. DoG), яку використовують виявлячі SIFT, SUSAN та Гарріса. Крім того, при застосуванні методик машинного навчання можливо досягати чудової продуктивності з погляду часу та ресурсів обчислень. Завдяки ній виявляч кутів FAST дуже добре підходить для обробки відео в реальному часі.

Виявляч сегментною перевіркою ред.

Пікселі, які використовує виявляч кутів FAST

Виявляч кутів FAST використовує коло з 16 пікселів (коло Брезенгема радіусу 3), щоби класифікувати, чи насправді потенційна точка p це кут. Кожен піксель у колі позначено цілим числом з 1 по 16 за годинниковою стрілкою. Якщо набір із N суміжних пікселів у колі весь яскравіший за яскравість пікселя-кандидата p (позначену через I_p) плюс порогове значення t, або весь темніший за яскравість пікселя-кандидата p мінус порогове значення t, то p класифікують як кут. Ці умови можливо записати так:

Умова 1: набір з N суміжних пікселів S, $\forall x\in S$ , яскравість x > I_p + поріг, або $I_{x}>I_{p}+t$
Умова 2: набір з N суміжних пікселів S, $\forall x\in S$ , $I_{x}<I_{p}-t$

Тож коли виконано будь-яку з цих двох умов, кандидата p можливо класифікувати як кут. Існує проблема компромісу вибору N, кількості суміжних пікселів, та порогового значення t. З одного боку, кількість виявлених кутових точок не повинна бути надто великою, з іншого боку, високої продуктивності не слід досягати, жертвуючи ефективністю обчислення. Без вдосконалення машинним навчанням N зазвичай обирають як 12. Для виключення некутових точок можливо застосовувати метод високошвидкісної перевірки.

Високошвидкісна перевірка ред.

Високошвидкісну перевірку для відкидання некутових точок виконують розглядом 4 зразкових пікселів, а саме пікселів 1, 9, 5 та 13. Оскільки має бути принаймні 12 послідовних пікселів, чи яскравіших, чи темніших за можливий кут, то має бути принаймні 3 пікселі з цих 4 зразкових пікселів, яскравіших чи темніших за можливий кут. Спочатку перевіряють пікселі 1 та 9, якщо і I₁, і I₉ перебувають у межах [I_p − t, I_p + t], то кандидат p — не кут. В іншому випадку додатково дивляться пікселі 5 та 13, щоби перевірити, чи три з них яскравіші за I_p + t або темніші за I_p − t. Якщо існує 3 з них, яскравіших або темніших, для остаточного висновку перевіряють решту пікселів. І, згідно з винахідником у його першій статті,^[2] для перевірки кандидата в кутові пікселі в середньому потрібно 3,8 пікселя. Порівняно з 8,5 пікселів для кожного можливого кута, 3,8 — це справді велике зменшення, здатне значно покращити продуктивність.

Проте цей метод перевірки має кілька недоліків:

Цю високошвидкісну перевірку неможливо добре узагальнити для N < 12. Якщо N < 12, то можливо, що кандидат p — кут, але лише 2 з 4 зразкових перевірних пікселів обидва яскравіші за I_p + t чи темніші за I_p − t.
Ефективність цього виявляча залежить від вибору та порядку цих обраних перевірних пікселів. Проте малоймовірно, що обрані пікселі оптимальні, що викликає занепокоєння щодо розподілу траплянь кутів.
Виявляються по декілька ознак поруч одна з одною

Покращення машинним навчанням ред.

Щоб усунути перші дві слабкі сторони високошвидкісної перевірки, для допомогти в покращенні алгоритму виявляння запроваджено підхід машинного навчання. Він працює в два етапи. По-перше, виконують виявляння кутів із заданим N на наборі тренувальних зображень, бажано з цільової області застосування. Кути виявляють за допомогою найпростішого втілення, яке буквально виділяє кільце з 16 пікселів та порівнює значення яскравості з відповідним порогом.

Для кандидата p кожне місце на колі x ∈ {1, 2, 3, …, 16} можливо позначити через p→x. Стан кожного пікселя S_p_→x мусить бути одним із трьох наступних:

d, I_p_→x ≤ I_p − t (темніший, англ. darker)
s, I_p − t ≤ I_p_→x ≤ I_p + t (подібний, англ. similar)
b, I_p_→x ≥ I_p + t (світліший, англ. brighter)

Потім обрання x (однакового для всіх p) розбиває P (множину всіх пікселів усіх тренувальних зображень) на 3 різні підмножини, P_d, P_s, P_b, де

P_d = {p ∈ P : S_p_→x = d }
P_s = {p ∈ P : S_p_→x = s }
P_b = {p ∈ P : S_p_→x = b }

По-друге, до цих 16 місць застосовують один з алгоритмів дерев рішень, ID3, щоби досягти максимального приросту інформації. Нехай K_p — булева змінна, яка вказує, чи p — кут, тоді ентропію K_p використовують для вимірювання інформації того, що p — кут. Для набору пікселів Q повна (не нормована) ентропія K_Q дорівнює

H(Q) = (c + n) log₂(c + n) − c log₂ c − n log₂ n
- де c = |{ i ∈ Q: K_i істинна}| (кількість кутів)
- де n = |{ i ∈ Q: K_i хибна}| (кількість не кутів)

Тоді приріст інформації можливо подати як

H_g = H(P) − H(P_b) − H(P_s) − H(P_d)

До кожної з підмножин застосовують рекурсивний процес, обираючи наступний x, який міг би максимізувати приріст інформації. Наприклад, спочатку x обирають для розбиття P на P_d, P_s, P_b з найбільшою кількістю інформації; тоді для кожної з підмножин P_d, P_s, P_b обирають інший y, щоб отримати найбільший приріст інформації (зауважте, що y може бути таким же, як x). Цей рекурсивний процес завершують тоді, коли ентропія стає нульовою, так, що або всі пікселі в цій підмножині кути, або не кути.

Це породжене дерево рішень можливо потім перетворити на програмний код, такий як C чи C++, що є просто набором вкладених операторів if—else. З метою оптимізації для компілювання коду використовують керовану профілем оптимізацію^[en]. Відповідний код пізніше використовують як виявляч кутів для інших зображень.

Зауважте, що кути, виявляні за допомогою цього алгоритму дерева рішень, повинні дещо відрізнятися від результатів, отримуваних за допомогою виявляча сегментною перевіркою. Це тому, що модель дерева рішень залежить від тренувальних даних, які не можуть охоплювати всі можливі кути.

Пригнічування немаксимумів ред.

«Оскільки сегментна перевірка не обчислює функцію кутового відгуку, застосовувати пригнічування немаксимумів безпосередньо до отримуваних в результаті ознак неможливо». Проте, якщо N незмінна, то для кожного пікселя p кутову вираженість визначають як максимальне значення t, яке робить p кутом. Тож можливо використовувати два підходи:

Можливо застосовувати алгоритм бінарного пошуку, щоби знаходити найбільший t, для якого p все ще кут. Тож для алгоритму дерева рішень встановлюють щоразу інший t. Коли йому вдається знайти найбільший t, цей t можливо розглядати як вираженість кута.
Інший підхід — ітераційна схема, в якій t щоразу збільшують до найменшого значення, яке проходить перевірку.

FAST-ER: покращена повторюваність ред.

Виявляч FAST-ER (від англ. enhanced repeatability, покращена повторюваність) — вдосконалений виявляч FAST із використанням метаевристичного алгоритму, в цьому випадку — імітації відпалу. Щоби після цієї оптимізації структура дерева рішень була оптимізованою та придатною для точок з високою повторюваністю. Проте, оскільки імітація відпалу — алгоритм метаевристичний, він щоразу породжуватиме інакше оптимізоване дерево рішень. Отже, щоби знаходити рішення, близькі до справді оптимальних, краще проводити ефективно велику кількість ітерацій. За словами Ростена, на оптимізацію виявляча FAST йде близько 200 годин на Pentium 4 на 3 ГГц, що становить 100 повторень 100 000 ітерацій.

Порівняння з іншими виявлячами ред.

У дослідженні Ростена^[3] виявлячі FAST і FAST-ER оцінено на кількох різних наборах даних і порівняно з виявлячами кутів РГ, Гарріса, Гарріса — Лапласа, Сі — Томазі та SUSAN.

Налаштування параметрів для виявлячів (крім FAST) наступні:

Виявляч	Параметр налаштування	Значення
РГ
	Масштабів на октаву	3
	Початкове розмиття σ	0,8
	Октави	4
SUSAN	Поріг відстані	4,0
Гарріса, Сі — Томазі	Розмиття σ	2,5
Гарріса — Лапласа	Початкове розмиття σ	0,8
	Гаррісове розмиття	3
	Октави	4
	Масштабів на октаву	10
Загальні параметри	ε	5 пікселів

Результат перевірки повторюваності подано як усереднену площу під кривими повторюваності для 0—2000 кутів на кадр для всіх наборів даних (за винятком додаткового шуму):

Виявляч	A
FAST-ER	1313,6
FAST-9	1304,57
РГ	1275,59
Сі — Томазі	1219,08
Гарріса	1195,2
Гарріса — Лапласа	1153,13
FAST-12	1121,53
SUSAN	1116,79
Випадковий	271,73

Перевірки швидкості проводили на комп'ютері Pentium 4-D 3.0 ГГц. Набір даних розділено на тренувальний та перевірний набори. Тренувальний набір складається зі 101 монохромного зображення з роздільністю 992×668 пікселів. Перевірний набір складається з 4968 кадрів монохромного відео 352×288. І результат:

Виявляч	Піксельна швидкість на тренувальному наборі	Піксельна швидкість на перевірному наборі
FAST n=9	188	179
FAST n=12	158	154
Первинний FAST n=12	79	82,2
FAST-ER	75,4	67,5
SUSAN	12,3	13,6
Гарріса	8,05	7,90
Сі — Томазі	6,50	6,50
РГ	4,72	5,10

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

↑ Rosten, Edward; Drummond, Tom (2006). Machine Learning for High-speed Corner Detection. Computer Vision – ECCV 2006. Lecture Notes in Computer Science. Т. 3951. с. 430—443. doi:10.1007/11744023_34. ISBN 978-3-540-33832-1. S2CID 1388140. (англ.)
↑ Edward Rosten, Real-time Video Annotations for Augmented Reality (англ.)
↑ Edward Rosten, FASTER and better: A machine learning approach to corner detection (англ.)

Джерела ред.

Rosten, Edward; Tom Drummond (2005). Fusing points and lines for high performance tracking (PDF). Т. 2. с. 1508—1511. CiteSeerX 10.1.1.60.4715. doi:10.1109/ICCV.2005.104. ISBN 978-0-7695-2334-7. {{cite book}}: Проігноровано |journal= (довідка) (англ.)
Rosten, Edward; Reid Porter; Tom Drummond (2010). FASTER and better: A machine learning approach to corner detection. IEEE Transactions on Pattern Analysis and Machine Intelligence. 32 (1): 105—119. arXiv:0810.2434. doi:10.1109/TPAMI.2008.275. PMID 19926902. (англ.)
Rosten, Edward; Tom Drummond (2006). Machine learning for high-speed corner detection (PDF). Lecture Notes in Computer Science. Т. 1. с. 430—443. CiteSeerX 10.1.1.64.8513. doi:10.1007/11744023_34. ISBN 978-3-540-33832-1. {{cite book}}: Проігноровано |journal= (довідка) (англ.)

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

Домашня сторінка Advanced Vision (англ.)

[1] Rosten, Edward; Drummond, Tom (2006). Machine Learning for High-speed Corner Detection. Computer Vision – ECCV 2006. Lecture Notes in Computer Science. Т. 3951. с. 430—443. doi:10.1007/11744023_34. ISBN 978-3-540-33832-1. S2CID 1388140. (англ.)

[2] Edward Rosten, Real-time Video Annotations for Augmented Reality (англ.)

[3] Edward Rosten, FASTER and better: A machine learning approach to corner detection (англ.)

[1]

[2]

[3]