Масштабоінваріа́нтне озна́кове перетво́рення (МІОП, ) — це алгоритм комп'ютерного бачення для виявляння, описування та зіставляння локальних ознак () у зображеннях, винайдений 1999 року. До його застосувань належать , та навігація, , тривимірне моделювання, , відстежування у відео, ідентифікування особин у дикій природі та .

Спершу ключові точки SIFT об'єктів виділяють із набору опорних зображень, і зберігають у базі даних. Об'єкт на новому зображенні розпізнають індивідуальним порівнянням кожної ознаки з нового зображення з цією базою даних, і пошуком кандидатів у збіги на основі евклідової відстані їхніх векторів ознак. У цьому повному наборі збігів встановлюють підмножини ключових точок, які узгоджуються з об'єктом і його розташуванням, масштабом і спрямуванням на новому зображенні, щоби відфільтрувати добрі збіги. Визначення узгоджених кластерів виконують швидко за допомогою ефективного втілення геш-таблиці узагальненого перетворення Гафа. Кожен кластер із 3 або більше ознак, що узгоджуються з об'єктом та його , потім підлягає подальшій докладній перевірці моделі, й викиди відтак відкидають. Нарешті обчислюють імовірність того, що певний набір ознак вказує на присутність об'єкта, враховуючи точність допасування та число ймовірних помилкових збігів. Збіги об'єктів, які пройшли всі ці перевірки, можливо з високою довірою визначити як правильні.

Огляд

Для будь-якого об'єкта на зображенні можливо виділити особливі точки на об'єкті, щоби забезпечити «ознаковий опис» () об'єкта. Цей опис, виділений із тренувального зображення, можливо потім використовувати для встановлювання об'єкта при намаганні знайти його на перевірному зображенні, що містить багато інших об'єктів. Для надійного розпізнавання важливо, щоб ознаки, виділені з тренувального зображення, було можливо виявляти навіть за змін масштабу зображення, шуму та освітлення. Такі точки зазвичай лежать на висококонтрастних ділянках зображення, таких як контури об'єктів.

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

SIFT може стійко ідентифікувати об'єкти навіть серед захаращення та за часткового затулення, оскільки описувач ознак SIFT інваріантний щодо рівномірного масштабування, спрямування, змін освітлення та частково інваріантний щодо афінного спотворення. У цьому розділі коротко викладено первинний алгоритм SIFT і згадано декілька конкурентних методів, доступних для розпізнавання об'єктів за захаращення та часткового затулення.

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

Задача Методика Переваги розташування / масштаб / спрямування ключових точок Різниця гауссіанів / масштабопросторова піраміда / призначування спрямування точність, стабільність, інваріантність щодо масштабу та обертання геометричне спотворення розмивання / передискретизація локальних проєкцій спрямування зображення афінна інваріантність індексування та зіставляння пошук найближчих сусідів / перший засік ліпший Ефективність / швидкість Встановлювання кластерів Голосування перетворення Гафа надійні моделі Перевірка моделі / виявляння викидів краща стійкість до помилок із меншою кількістю збігів Примання гіпотези Аналіз баєсової ймовірності надійність

Типи ознак

Виявляння та опис локальних ознак зображення може допомагати в розпізнаванні об'єктів. Ознаки SIFT локальні, ґрунтуються на зовнішньому вигляді об'єкта в певних особливих точках, та інваріантні щодо масштабу та обертання зображення. Вони також стійкі до змін освітлення, шуму та незначних змін точки огляду. На додачу до цих властивостей, вони дуже вирізнювальні (), відносно легкі для виділяння, та дозволяють правильно встановлювати об'єкти з низькою ймовірністю невідповідності. Їх відносно легко зіставляти з (великою) базою даних локальних ознак, але, проте, висока вимірність може бути проблемою, і зазвичай використовують імовірнісні алгоритми, такі як k-вимірні дерева з пошуком «перший засік ліпший». Опис об'єкта набором ознак SIFT також стійкий до часткового затулення; достатньо всього лише трьох ознак SIFT від об'єкта, щоб обчислити його розташування та позу. Розпізнавання можливо виконувати в часі, близькому до реального, принаймні для невеликих баз даних і на сучасному комп'ютерному обладнанні.

Основні етапи

Масштабоінваріантне виявляння ознак

Метод Лоу для породжування ознак зображення перетворює зображення на велику збірку векторів ознак, кожен з яких інваріантний до паралельного перенесення, масштабування та обертання зображення, частково інваріантний до змін освітлення, та стійкий до локальних геометричних спотворень. Ці ознаки мають схожі властивості з нейронами первинної зорової кори, які кодують основні форми, колір та рух для виявляння об'єктів у зорі приматів. Ключові місця визначають як максимуми та мінімуми результату функції різниці гауссіанів, застосованої у просторі масштабів до низки згладжених та передискретизованих зображень. Точки-кандидати з низьким контрастом та точки контурного відгуку вздовж контурів відкидають. Ключовим точкам із встановленим розташуванням призначують переважні спрямування. Ці кроки забезпечують, щоби ключові точки були стабільнішими для зіставляння та розпізнавання. Відтак, стійкі до локального афінного спотворення описувачі SIFT отримують розглядом пікселів навколо певного радіуса ключового місця, розмивання та передискретизації локальних площин спрямування зображення.

Зіставляння та індексування ознак

Індексування полягає у зберіганні ключових точок SIFT та ідентифікуванні відповідних ключових точок із нового зображення. Лоу використав видозміну алгоритму k-вимірного дерева під назвою метод пошуку «перший засік ліпший» (), який може з високою ймовірністю встановлювати найближчих сусідів, використовуючи лише обмежену кількість обчислень. Алгоритм «перший засік ліпший» використовує видозмінене впорядкування пошуку для алгоритму k-вимірного дерева, так що пошук засіків у просторі ознак здійснюють у порядку їх найближчої відстані від розташування запиту. Цей порядок пошуку для ефективного визначання порядку пошуку вимагає використання черги з пріоритетом на основі купи. Найкращий варіант збігу для кожної ключової точки знаходять встановлюванням її найближчого сусіда в базі даних ключових точок із тренувальних зображень. Найближчих сусідів визначають як ключові точки з мінімальною евклідовою відстанню від заданого вектора описувача. Імовірність правильності збігу можливо визначати, беручи співвідношення відстані від найближчого сусіда до відстані від другого найближчого.

Лоу відкидав усі збіги, в яких це співвідношення відстаней перевищує 0,8, що усуває 90 % хибних збігів, відкидаючи менше 5 % правильних. Для подальшого підвищення ефективності алгоритму «перший засік ліпший» пошук переривали після перевірки перших 200 кандидатів у найближчі сусіди. Для бази даних із 100 000 ключових точок це забезпечує прискорення відносно точного пошуку найближчого сусіда приблизно на 2 порядки, призводячи до менш ніж 5 % втрат кількості правильних збігів.

Встановлювання кластерів голосуванням перетворення Гафа

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

Кожна з ключових точок SIFT визначає двовимірне розташування, масштаб та спрямування, і кожна відповідна ключова точка в базі даних має запис своїх параметрів відносно тренувального зображення, на якому її було знайдено. Перетворення подібності, передбачене цими 4 параметрами, є лише наближенням повного простору положень із 6 ступенями вільності для тривимірного об'єкта, а також не враховує жодних нежорстких деформувань. Тому Лоу використовував широкі розміри засіків у 30 градусів для спрямування, коефіцієнт 2 для масштабу, та 0,25 максимального розміру проєкції тренувального зображення (з використанням передбаченого масштабу) для розташування. Зразкам ключових точок SIFT, породженим із більшого масштабу, надають удвічі більшої ваги, ніж тим що з меншого масштабу. Це означає, що більший масштаб фактично здатний фільтрувати найправдоподібніших сусідів для перевірки в меншому масштабі. Це також покращує продуктивність розпізнавання, надаючи більшої ваги масштабові з найменшим шумом. Щоби запобігти проблемі межових ефектів у призначуванні засіків, кожен збіг ключових точок голосує за 2 найближчі засіки в кожному вимірі, даючи загалом 16 записів для кожної гіпотези та додатково розширюючи діапазон положень.

Перевірка моделі лінійними найменшими квадратами

Потім кожен встановлений кластер підлягає процедурі перевірки, в якій знаходять розв'язок для параметрів афінного перетворення, яке пов'язує модель із зображенням. Афінне перетворення точки моделі [x y]T на точку зображення [u v]T можливо записати як

де паралельне перенесення моделі — [tx ty]T, а афінне обертання, масштабування та розтягування подано параметрами m1, m2, m3 та m4. Щоби знайти розв'язок для цих параметрів перетворення, наведене вище рівняння можливо переписати так, щоби зібрати невідомі до вектора-стовпця.

Це рівняння показує один збіг, але можливо додати будь-яку кількість наступних збігів, причому кожен збіг вносить ще два рядки до першої та останньої матриці. Щоби знайти розв'язок, потрібно надати не менше 3 збігів. Ми можемо записати цю лінійну систему як

де A — відома матриця m на n (зазвичай із m > n), x — невідомий n-вимірний вектор параметрів, а b — відомий m-вимірний вектор вимірювання.

Отже, мінімізувальний вектор  — розв'язок нормального рівняння

Розв'язок цієї системи лінійних рівнянь задають через матрицю , звану псевдооберненням A, як

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

Виявляння викидів

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