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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

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

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

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

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

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

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

[ред. | ред. код]

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

Виявляння

[ред. | ред. код]

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

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

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

де тощо є згорткою похідної другого порядку гауссіана із зображенням в точці .

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

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

[ред. | ред. код]

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

Простір масштабів ділять на певне число октав, де октава означає низку карт відгуку, яка охоплює подвоєння масштабу. У 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 у межах кругового околу радіусу навколо особливої точки, де це масштаб, на якому було виявлено особливу точку. Отримані відгуки зважують гауссовою функцією з центром в особливій точці, а потім відкладають як точки у двовимірному просторі з горизонтальним відгуком за абсцисою та вертикальним відгуком за ординатою. Переважне спрямування оцінюють обчисленням суми всіх відгуків у ковзному вікні спрямування розміру π/3. Горизонтальні та вертикальні відгуки в межах вікна підсумовують. Ці два сумарні відгуки відтак дають локальний вектор спрямування. Найдовший такий вектор загалом визначає спрямування особливої точки. Розмір ковзного вікна — це параметр, який слід підбирати ретельно, щоби досягти бажаного балансу між стійкістю та кутовою роздільністю.

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

[ред. | ред. код]

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

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

Зіставляння

[ред. | ред. код]

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

Див. також

[ред. | ред. код]

Примітки

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

Джерела

[ред. | ред. код]

Посилання

[ред. | ред. код]