SIFT
SIFT (Scale-invariant feature transform, укр. масштабонезалежне перетворення ознак) — алгоритм із області комп'ютерного зору, який виявляє і описує локальні ознаки зображення.[1].
| Виявляння ознак |
|---|
| Виявляння контурів |
| Виявляння кутів |
|
| Виявляння плям |
|
| Виявляння хребтів |
| Перетворення Гафа |
|
| Структурний тензор |
|
| Афінне інваріантне виявляння ознак |
|
| Опис ознак |
| Простір масштабів |
|
Алгоритм застосовується для розпізнавання образів, побудови карт для навігації роботів, 3D-реконструкції, розпізнавання жестів, відстеження об'єктів та ін.
Алгоритм був опубліковано Девідом Лоу у 1999 р. і запатентовано в США Британо-колумбійським університетом.
Опис
Для будь-якого об'єкта на зображенні можливо отримати точки інтересу на об'єкті, щоб створити «опис ознак» об'єкта. Ці ознаки, отримані із зображення, можна використовувати для ідентифікації об'єкта при знаходженні його на іншому тестовому зображенні, що містить багато інших об'єктів. Для надійного розпізнавання важливо, щоб отримані ознаки на початковому зображенні можна було розрізнити навіть при зміні масштабу зображення, освітлення і наявності шуму. Такі точки, зазвичай, знаходяться на висококонтрастних ділянках зображення, наприклад на межах об'єкта.
Іншою важливою характеристикою цих ознак є те, що відносні позиції між ними не повинні змінюватися від одного зображення до іншого. Наприклад, якщо як ознаки було обрано чотири кути дверей, вони будуть порівнюватися незалежно від позиції дверей; але якщо разом з тим використати точки на дверній рамі, розпізнавання не спрацює, коли двері відкриті чи закриті. Так само, ознаки що знаходяться на рухомих чи гнучких об'єктах, зазвичай не працюватимуть, якщо відбуватимуться будь-які зміни у їх внутрішній геометрії при порівнянні двох зображень. Однак, на практиці алгоритм SIFT визначає і використовує значно більшу кількість ознак на зображенні, що зменшує внесок похибок, спричинених локальними змінами, до середньої похибки загальних порівнянь ознак.
SIFT[2] може достовірно ідентифікувати об'єкти навіть серед шуму або часткового перекриття, тому що дескриптор ознак, що використовується в SIFT, є інваріантним до лінійного масштабування, змін просторової орієнтації, освітлення, і частково до афінного перетворення.[3]
SIFT
В алгоритмі SIFT спершу знаходять ключові точки об'єктів на еталонних зображеннях[3] і зберігають в базі даних. За допомогою індивідуального порівняння кожної ознаки із бази даних розпізнають об'єкт в новому зображенні, і знаходять кандидати із відповідними ознаками за допомогою розрахунку Евклідової відстані векторів їхніх ознак. Із повного набору відповідностей заходять підмножини ключових точок що узгоджуються з об'єктом і його місцем розташування, масштабом, і орієнтацією на новому зображенні, і відфільтровують правдиві відповідності. Швидке визначення послідовних кластерів відбувається за допомогою ефективної реалізації хеш-таблиці узагальненого перетворення Хофа. Кожен кластер із 3 або більше ознак, які узгоджуються із об'єктом і його орієнтацією, є предметом подальшої верифікації детальної моделі, відхилення згодом відкидаються. І, нарешті, розраховують ймовірність, що конкретний набір ознак вказує на присутність об'єкта, з урахуванням точності і кількості можливих помилкових збіжностей. Відповідності об'єкта, які проходять всі ці тести, можна ідентифікувати як правдиві із високою довірою.[4]
| Задача | Техніка | Переваги |
|---|---|---|
| Локалізація ключів / масштабування / обертання | Різниця гаусіанів / масштабно-просторова піраміда / визначення орієнтації | Точність, стабільність, інваріантність до масштабу і обертання |
| Геометричне спотворення | Розмиття / ресепляція площин орієнтації локального зображення | Афінна інваріантність |
| Індексація і співставлення | Метод найближчого сусіда / пошук «Best Bin First» | Ефективність / швидкість |
| Ідентифікація кластера | Голосування перетворення Хофа | Надійні моделі пози |
| Варифікація моделі / виявлення викидів | Лінійний метод найменших квадратів | Краща толерантність до похибки із меншою кількістю порівнянь |
| Прийняття гіпотези | Баєсовий ймовірнісний аналіз | Надійність |
Масштабно-інваріантне визначення ознак
Метод Лоу для генерації ознак зображення перетворює зображення в велику колекцію векторів ознак, кожен з яких інваріантний до переміщення зображення, масштабу, обертання, частково інваріантне до змін освітлення і стійкий до геометричних спотворень. Ці принципи виділення ознак мають схожі властивості із нейронами в первинній зоровій корі, які кодують базові форми, колір і рух для визначення об'єктів в системі зору приматів.[5] Місцезнаходження ключових точок визначається як максимум і мінімум із результату функції різниці гаусіанів що застосовується у масштабному просторі до послідовності розмитих і масштабовних зображень.
Співставлення ознак і індексація
Індексування передбачає збереження ключів SIFT і ідентифікацію відповідних ключів із нових зображень. Лоу використав модифікацію алгоритму k-вимірного дерева, що називається пошук Best-bin-first[6] що може визначати найближчих сусідів із високою імовірністю використовуючи обмежену кількість розрахунків. Алгоритм BBF використовує змінений порядок пошуку для алгоритму для k-вимірного дерева так що засічки в просторі ознаки шукають в порядку їх найближчої відстані від місця пошуку. Цей порядок пошуку потребує використання черги з пріоритетом на основі купи для ефективного впорядкування процедури пошуку. Найкращий кандидат порівняння для кожної ключової точки знаходять за допомогою визначення його найближчого сусіда в базі даних ключових точок із навчальних зображень. Найближчі сусіди це такі ключові точки що мають найменшу Евклідову відстань від заданого вектору дескриптору. Ймовірність, того що збіг ознак вірний, можна визначити розрахувавши співвідношення відстаней до найближчого сусіда до дистанції другого найближчого.
Лоу[4] відкидав всі порівняння де співвідношення відстані більше ніж 0.8, що усуває 90 % відсотків не вірних порівнянь і викидає менше ніж 5 % правильних порівнянь. Для подальшого покращення ефективності пошуку за допомогою алгоритму best-bin-first пошук завершується після перевірки перших 200 кандидатів найближчих сусідів. Для бази даних в 100000 ключових точок, забезпечує пришвидшення точного пошуку найближчого сусіда на 2 порядку, і ще має менше 5 % втрат правильних порівнянь.
Примітки
- Object Recognition from Local Scale-Invariant Features
- U.S. Patent 6,711,293, «Method and apparatus for identifying scale invariant features in an image and use of same for locating an object in an image», David Lowe's patent for the SIFT algorithm, March 23, 2004
- Lowe, David G. (1999). Object recognition from local scale-invariant features. Proceedings of the International Conference on Computer Vision 2. с. 1150–1157. doi:10.1109/ICCV.1999.790410.
- Lowe, David G. (2004). Distinctive Image Features from Scale-Invariant Keypoints. International Journal of Computer Vision 60 (2): 91–110. doi:10.1023/B:VISI.0000029664.99615.94.
- Serre, T., Kouh, M., Cadieu, C., Knoblich, U., Kreiman, G., Poggio, T., «A Theory of Object Recognition: Computations and Circuits in the Feedforward Path of the Ventral Stream in Primate Visual Cortex», Computer Science and Artificial Intelligence Laboratory Technical Report, December 19, 2005 MIT-CSAIL-TR-2005-082.
- Beis, J.; Lowe, David G. (1997). Shape indexing using approximate nearest-neighbour search in high-dimensional spaces. Conference on Computer Vision and Pattern Recognition, Puerto Rico: sn. с. 1000–1006. doi:10.1109/CVPR.1997.609451.