Прискорені стійкі ознаки

У комп'ютернім баченні приско́рені стійкі́ озна́ки (англ. speeded up robust features, SURF) — це запатентований виявляч та описувач локальних ознак. Його можливо використовувати для таких завдань як розпізнавання об'єктів^[en], зіставляння зображень, класифікування, та об'ємна відбудова. Він частково натхнений описувачем масштабоінваріантного ознакового перетворення (SIFT). Стандартна версія SURF у декілька разів швидша за SIFT і, як стверджують її автори, стійкіша за SIFT щодо різних перетворень зображень.

Щоби виявляти особливі точки, SURF використовує цілочислові наближення виявляча плям визначником гессіана, які можливо обчислювати за допомогою трьох цілочислових операцій з використанням попередньо обчисленого інтегрального зображення. Його описувач ознак ґрунтується на сумі відгуків гаарових вейвлетів навколо особливої точки. Їх також можливо обчислювати за допомогою інтегрального зображення.

Описувачі SURF використовували для встановлювання та розпізнавання об'єктів, людей та облич, відбудовування тривимірних сцен, відстежування об'єктів та виділяння особливих точок.

SURF вперше опублікували Герберт Бей, Тінне Туйтелаарс та Люк Ван Ґул, і презентували його на Європейській конференції з комп'ютерного бачення^[en] 2006 року. Застосування цього алгоритму запатентовано в США.^[1] «Вертикальна» (англ. "upright") версія SURF (звана U-SURF) не інваріантна щодо обертання зображення, тому вона швидша для обчислень і краще підходить для застосування, коли камера залишається більш-менш горизонтальною.

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

Алгоритм та властивості

Алгоритм SURF ґрунтується на тих же принципах і кроках, що й SIFT, але відрізняється деталями кожного з кроків. Цей алгоритм має три основні частини: виявляння особливих точок, описування локального околу, та зіставляння.

Виявляння

SURF використовує фільтри квадратної форми як наближення гауссового згладжування. (Підхід SIFT для виявляння масштабоінваріантних характерних точок використовує каскадні фільтри, де послідовно обчислюють різницю гауссіанів (РГ) на перемасштабованих зображеннях.) Фільтрування зображення квадратом набагато швидше, якщо використовувати інтегральне зображення:

${\displaystyle S(x,y)=\sum _{i=0}^{x}\sum _{j=0}^{y}I(i,j)}$

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

Щоби знаходити особливі точки, SURF використовує виявляч плям на основі матриці Гессе. Визначник матриці Гессе використовують як міру локальної зміни навколо точки, й обирають точки, де цей визначник максимальний. На відміну від гессіанно-лапласіанного виявляча Міколайчика та Шмід, SURF також використовує визначник гессіана і для обирання масштабу, як це також зробив і Ліндеберг. Для заданої точки p=(x, y) на зображенні I матрицею Гессе H(p, σ) у точці p й масштабі σ є

${\displaystyle H(p,\sigma )={\begin{pmatrix}L_{xx}(p,\sigma )&L_{xy}(p,\sigma )\\L_{xy}(p,\sigma )&L_{yy}(p,\sigma )\end{pmatrix}}}$

де ${\displaystyle L_{xx}(p,\sigma )}$ тощо є згорткою похідної другого порядку гауссіана із зображенням ${\displaystyle I(x,y)}$ в точці ${\displaystyle p}$.

Коробковий фільтр розміру 9×9 — це наближення гауссіана з σ=1,2, й подає найнижчий рівень (найвищу просторову роздільність) для карт плямового відгуку.

Масштабопросторове подання та розташування особливих точок

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

${\displaystyle \sigma _{\text{наближений}}={\text{розмір поточного фільтру}}\times \left({\frac {\text{масштаб базового фільру}}{\text{розмір базового фільтру}}}\right)}$

Простір масштабів ділять на певне число октав, де октава означає низку карт відгуку, яка охоплює подвоєння масштабу. У SURF найнижчий рівень простору масштабів отримують із виходу фільтрів 9×9.

Таким чином, на відміну від попередніх методів, простори масштабів у SURF втілюють застосуванням коробкових фільтрів різних розмірів. Відповідно, простір масштабів аналізують шляхом збільшування розміру фільтра, а не ітеративного зменшування розміру зображення. Вихід вищевказаного фільтра 9×9 вважають початковим масштабним шаром у масштабі s =1,2 (що відповідає похідним гауссіана з σ = 1,2). Наступні шари отримують фільтруванням зображення поступово збільшуваними масками з урахуванням дискретної природи інтегральних зображень та конкретної структури фільтра. У результаті виходять фільтри розмірів 9×9, 15×15, 21×21, 27×27, … . Для встановлення положень особливих точок на зображенні та в масштабах застосовують пригнічування немаксимумів в околі 3×3×3. Відтак максимуми визначника матриці Гессе інтерполюють у просторі масштабів та зображення методом, запропонованим Брауном зі співавт. Інтерполювання простору масштабів у цьому випадку особливо важливе, оскільки різниця в масштабі між першими шарами кожної з октав є відносно великою.

Описувач

Мета описувача (англ. descriptor) — надання унікального та стійкого опису ознаки зображення, наприклад, шляхом опису розподілу яскравості пікселів в околі цієї особливої точки. Відтак, більшість описувачів обчислюють локально, отже, опис отримують для кожної визначеної раніше особливої точки.

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

Перший крок полягає у фіксуванні відтворюваного спрямування на основі інформації з кругової області навколо особливої точки. Потім ми будуємо квадратну область, вирівняну за обраним спрямуванням, і виділяємо з неї описувач SURF.

Призначування спрямування

Щоби досягти інваріантності щодо обертання, необхідно знаходити спрямування особливих точок. Обчислюють відгуки гаарових вейвлетів в обох напрямках x та y у межах кругового околу радіусу ${\displaystyle 6s}$ навколо особливої точки, де ${\displaystyle s}$ це масштаб, на якому було виявлено особливу точку. Отримані відгуки зважують гауссовою функцією з центром в особливій точці, а потім відкладають як точки у двовимірному просторі з горизонтальним відгуком за абсцисою та вертикальним відгуком за ординатою. Переважне спрямування оцінюють обчисленням суми всіх відгуків у ковзному вікні спрямування розміру π/3. Горизонтальні та вертикальні відгуки в межах вікна підсумовують. Ці два сумарні відгуки відтак дають локальний вектор спрямування. Найдовший такий вектор загалом визначає спрямування особливої точки. Розмір ковзного вікна — це параметр, який слід підбирати ретельно, щоби досягти бажаного балансу між стійкістю та кутовою роздільністю.

Описувач на основі суми відгуків гаарових вейвлетів

Щоб описати область навколо точки, виділяють квадратну область із центром в особливій точці, спрямовану, як обрано вище. Розмір цього вікна 20s.

Особливу область ділять на менші квадратні підобласті 4×4, і для кожної з них виділяють відгуки гаарових вейвлетів у рівномірно розташованих точках вибірки 5×5. Ці відгуки зважують гауссіаном (щоби забезпечити більшу стійкість щодо деформацій, шуму та зміщення).

Зіставляння

Порівнюючи описувачі, отримані з різних зображень, можливо знаходити відповідні пари.

Див. також

• Масштабоінваріантне ознакове перетворення (SIFT)
• Гістограма розташувань та напрямків градієнта (GLOH)
• Гістограма форми на основі локальної енергії (LESH)
• Виявляння плям
• Виявляння ознак (комп'ютерне бачення)

Примітки

1. US 2009238460, Ryuji Funayama, Hiromichi Yanagihara, Luc Van Gool, Tinne Tuytelaars, Herbert Bay, "ROBUST INTEREST POINT DETECTOR AND DESCRIPTOR", published 2009-09-24 (англ.)

Джерела

• Herbert Bay, Andreas Ess, Tinne Tuytelaars, and Luc Van Gool, "Speeded Up Robust Features", ETH Zurich, Katholieke Universiteit Leuven (англ.)
• Andrea Maricela Plaza Cordero,Jorge Luis Zambrano Martínez, " Estudio y Selección de las Técnicas SIFT, SURF y ASIFT de Reconocimiento de Imágenes para el Diseño de un Prototipo en Dispositivos Móviles" , 15º Concurso de Trabajos Estudiantiles, EST 2012 (ісп.)
• A. M. Romero and M. Cazorla, "Comparativa de detectores de característicasvisuales y su aplicación al SLAM ", X Workshop de agentes físicos, Setiembre 2009, Cáceres (ісп.)
• P. M. Panchal, S. R. Panchal, S. K. Shah, "A Comparison of SIFT and SURF ", International Journal of Innovative Research in Computer and Communication Engineering Vol. 1, Issue 2, April 2013 (англ.)
• Herbert Bay, Andreas Ess, Tinne Tuytelaars, Luc Van Gool "SURF: Speeded Up Robust Features", Computer Vision and Image Understanding (CVIU), Vol. 110, No. 3, pp. 346–359, 2008 (англ.)
• Christopher Evans "Notes on the OpenSURF Library", MSc Computer Science, University of Bristol; source code and documentation archived here (англ.)
• J an Knopp, Mukta Prasad, Gert Willems, Radu Timofte, and Luc Van Gool, "Hough Transform and 3D SURF for Robust Three Dimensional Classification", European Conference on Computer Vision (ECCV), 2010 (англ.)

Посилання

• SURF на GitHub
• Вебсайт SURF: speeded up robust features (англ.)
• Перша публікація прискорених стійких ознак (2006) (англ.)
• Переглянуте видання SURF (2008) (англ.)