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

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

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

Огляд

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

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

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

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

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

Типи ознак

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

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

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

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

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

Індексування полягає у зберіганні ключових точок SIFT та ідентифікуванні відповідних ключових точок із нового зображення. Лоу використав видозміну алгоритму k-вимірного дерева під назвою метод пошуку «перший засік ліпший» (англ. best-bin-first search), який може з високою ймовірністю встановлювати найближчих сусідів, використовуючи лише обмежену кількість обчислень. Алгоритм «перший засік ліпший» використовує видозмінене впорядкування пошуку для алгоритму 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 можливо записати як

${\begin{bmatrix}u\\v\end{bmatrix}}={\begin{bmatrix}m_{1}&m_{2}\\m_{3}&m_{4}\end{bmatrix}}{\begin{bmatrix}x\\y\end{bmatrix}}+{\begin{bmatrix}t_{x}\\t_{y}\end{bmatrix}}$

де паралельне перенесення моделі — [t_x t_y]^T, а афінне обертання, масштабування та розтягування подано параметрами m₁, m₂, m₃ та m₄. Щоби знайти розв'язок для цих параметрів перетворення, наведене вище рівняння можливо переписати так, щоби зібрати невідомі до вектора-стовпця.

${\begin{bmatrix}x&y&0&0&1&0\\0&0&x&y&0&1\\....\\....\end{bmatrix}}{\begin{bmatrix}m1\\m2\\m3\\m4\\tx\\ty\end{bmatrix}}={\begin{bmatrix}u\\v\\.\\.\end{bmatrix}}$

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

$A{\hat {\mathbf {x} }}\approx \mathbf {b} ,$

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

Отже, мінімізувальний вектор ${\hat {\mathbf {x} }}$ — розв'язок нормального рівняння

$A^{T}\!A{\hat {\mathbf {x} }}=A^{T}\mathbf {b} .$

Розв'язок цієї системи лінійних рівнянь задають через матрицю $(A^{T}A)^{-1}A^{T}$, звану псевдооберненням A, як

${\hat {\mathbf {x} }}=(A^{T}\!A)^{-1}A^{T}\mathbf {b} .$

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

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

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

Остаточне рішення прийняти або відхилити гіпотезу моделі ґрунтується на детальній імовірнісній моделі. Цей метод спочатку обчислює очікувану кількість хибних збігів із положенням моделі, враховуючи розмір проєкції моделі, кількість ознак в області, та точність допасування. Після цього аналіз баєсової ймовірності дає ймовірність присутності об'єкта на основі фактичної кількості знайдених збігів ознак. Модель вважають прийнятною, якщо остаточна ймовірність правильної інтерпретації перевищує 0,98. Розпізнавання об'єктів Лоу на основі SIFT дає чудові результати, за винятком широких змін освітлення та нежорстких перетворень.

Алгоритм

Виявляння масштабопросторових екстремумів

Ми починаємо з виявляння особливих точок, які в системі SIFT називають ключовими точками (англ. keypoints). Зображення згортають з гауссовими фільтрами в різних масштабах, а потім беруть різницю послідовних гауссово розмитих зображень. Відтак за ключові точки беруть максимуми/мінімуми різниць гауссіанів (РГ), які мають місце у декількох масштабах. Конкретніше, зображення РГ $D\left(x,y,\sigma \right)$ задають як

$D\left(x,y,\sigma \right)=L\left(x,y,k_{i}\sigma \right)-L\left(x,y,k_{j}\sigma \right)$,

де $L\left(x,y,k\sigma \right)$ — згортка первинного зображення $I\left(x,y\right)$ з гауссовим розмиттям $G\left(x,y,k\sigma \right)$ у масштабі $k\sigma$, тобто

$L\left(x,y,k\sigma \right)=G\left(x,y,k\sigma \right)*I\left(x,y\right)$

Відтак зображення РГ між масштабами $k_{i}\sigma$ та $k_{j}\sigma$ це просто різниця гауссово розмитих зображень масштабів $k_{i}\sigma$ та $k_{j}\sigma$. Для виявляння масштабопросторових екстремумів в алгоритмі SIFT зображення спочатку згортають з гауссовими розмиттями в різних масштабах. Згорнуті зображення групують в октави (октава відповідає подвоєнню значення $\sigma$), а значення $k_{i}$ обирають таким чином, щоб отримувати фіксовану кількість згорнутих зображень на октаву. Потім зображення різниць гауссіанів беруть із суміжних гауссово зображень пооктавно.

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

Цей етап виявляння ключових точок є різновидом одного з методів виявляння плям, розробленого Ліндебергом шляхом виявляння масштабопросторових екстремумів масштабонормованого лапласіана; тобто виявляння точок, що є локальними екстремумами щодо як простору, так і масштабу, в дискретному випадку порівнянням із цими найближчими 26 сусідами в дискретизованому масштабопросторовому об'ємі. Оператор різниці гауссіанів можливо розглядати як наближення лапласіана, при цьому неявне нормування в піраміді також становить дискретне наближення масштабонормованого лапласіана. Інше реальночасове втілення масштабопросторових екстремумів оператора Лапласа, запропоноване Ліндебергом та Бретцнером, ґрунтується на гібридному пірамідному поданні, яке використовували для людиномашинної взаємодії реальночасовим розпізнаванням жестів в Бретцнері зі співавт. (2002).

Встановлення розташувань ключових точок

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

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

Інтерполювання даних поблизу для точності розташування

По-перше, для кожної потенційної ключової точки використовують інтерполювання даних неподалік, щоби визначити її розташування точно. Початковий підхід полягав у тому, щоби просто знайти кожну ключову точку в місці та масштабі потенційної ключової точки. Новий підхід обчислює інтерпольоване розташування екстремуму, що значно покращує зіставляння та стабільність. Це інтерполювання виконують з використанням квадратичного розкладу Тейлора масштабопросторової функції різниці гауссіанів $D\left(x,y,\sigma \right)$ з потенційною ключовою точкою як центром. Цей розклад Тейлора задають як

$D({\textbf {x}})=D+{\frac {\partial D}{\partial {\textbf {x}}}}^{T}{\textbf {x}}+{\frac {1}{2}}{\textbf {x}}^{T}{\frac {\partial ^{2}D}{\partial {\textbf {x}}^{2}}}{\textbf {x}}$

де D та її похідні оцінюють у потенційній ключовий точці, а ${\textbf {x}}=\left(x,y,\sigma \right)^{T}$ — зміщення відносно цієї точки. Розташування екстремуму, ${\hat {\textbf {x}}}$, визначають взяттям похідної цієї функції за ${\textbf {x}}$ та прирівнюванням її до нуля. Якщо зміщення ${\hat {\textbf {x}}}$ перевищує $0.5$ у будь-якому вимірі, це вказує на те, що екстремум лежить ближче до іншої потенційної ключової точки. В такому випадку потенційну ключову точку змінюють, й виконують інтерполяцію натомість навколо тієї точки. Інакше це зміщення додають до його потенційної ключової точки, щоб отримати інтерпольовану оцінку розташування екстремуму. Подібне субпіксельне визначання розташування масштабопросторових екстремумів виконують у реальночасовому втіленні на основі гібридних пірамід, розробленому Ліндебергом зі співробітниками.

Відкидання низькоконтрастних ключових точок

Щоби відкинути ключові точки з низьким контрастом, обчислюють значення розкладу Тейлора другого порядку $D({\textbf {x}})$ за зміщення ${\hat {\textbf {x}}}$. Якщо це значення менше за $0.03$, потенційну ключову точку відкидають. В іншому випадку її зберігають, з остаточним масштабопросторовим розташуванням ${\textbf {y}}+{\hat {\textbf {x}}}$, де ${\textbf {y}}$ — первинне розташування ключової точки.

Усування контурних відгуків

Функція РГ матиме сильні відгуки вздовж контурів, навіть якщо потенційна ключова точка не стійка й до невеликої кількості шуму. Тому, щоби підвищити стабільність, нам потрібно усунути ключові точки, які мають погано визначені розташування, але мають високий контурний відгук.

Для погано визначених піків функції РГ головна кривина поперек контуру буде набагато більшою за головну кривину вздовж нього. Знаходження цих головних кривин означає знаходження розв'язку для власних значень матриці Гессе другого порядку, H:

${\textbf {H}}={\begin{bmatrix}D_{xx}&D_{xy}\\D_{xy}&D_{yy}\end{bmatrix}}$

Власні значення H пропорційні головним кривинам D. Виявляється, що для цілей SIFT достатньо відношення двох власних значень, скажімо, $\alpha$ — більше, а $\beta$ — менше, а відношення — $r=\alpha /\beta$. Слід H, тобто $D_{xx}+D_{yy}$, дає нам суму двох власних значень, а її визначник, тобто $D_{xx}D_{yy}-D_{xy}^{2}$, дає добуток. Можливо показати, що відношення ${\text{R}}=\operatorname {Tr} ({\textbf {H}})^{2}/\operatorname {Det} ({\textbf {H}})$ дорівнює $(r+1)^{2}/r$, що залежить лише від відношення власних значень, але не від їхніх окремих значень. R мінімальне, коли власні значення дорівнюють одне одному. Отже, що вища абсолютна різниця двох власних значень, еквівалентна вищій абсолютній різниці двох головних кривин D, то вище значення R. З цього випливає, що для деякого порогового відношення власних значень $r_{\text{th}}$, якщо R для потенційної ключової точки перевищує $(r_{\text{th}}+1)^{2}/r_{\text{th}}$, ця ключова точка має погано визначене розташування, і тому підлягає відкиданню. Новий підхід використовує $r_{\text{th}}=10$.

Цей етап обробки для пригнічування відгуків на контурах є перенесенням відповідного підходу з оператора Гарріса для виявляння кутів. Відмінність полягає в обчисленні міри для порогування з матриці Гессе замість матриці другого моменту.

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

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

По-перше, гауссово згладжене зображення $L\left(x,y,\sigma \right)$ на масштабі ключової точки $\sigma$ беруть таким чином, щоби всі обчислення виконувалися масштабоінваріантно. Для зразка зображення $L\left(x,y\right)$ в масштабі $\sigma$ величину градієнта, $m\left(x,y\right)$, та спрямування, $\theta \left(x,y\right)$, попередньо обчислюють з використанням піксельних різниць:

$m\left(x,y\right)={\sqrt {\left(L\left(x+1,y\right)-L\left(x-1,y\right)\right)^{2}+\left(L\left(x,y+1\right)-L\left(x,y-1\right)\right)^{2}}}$

$\theta \left(x,y\right)=\mathrm {atan2} \left(L\left(x,y+1\right)-L\left(x,y-1\right),L\left(x+1,y\right)-L\left(x-1,y\right)\right)$

Для кожного пікселя в окільній області навколо ключової точки у гауссово розмитому зображенні L здійснюють обчислення величини та напрямку для градієнта. Створюють гістограму спрямувань із 36 засіками, кожен з яких охоплює 10 градусів. Кожен зразок в окільному вікні, який додають до засіку гістограми, зважують величиною його градієнта та гауссово зваженим круговим вікном із $\sigma$, у 1,5 рази більшим за масштаб ключової точки. Піки на цій гістограмі відповідають переважним спрямуванням. Після заповнення гістограми ключовій точці призначують спрямування, що відповідають найвищому пікові, й локальним пікам в межах 80 % від найвищих піків. У разі призначення кількох спрямувань для кожного додаткового спрямування створюють додаткову ключову точку з тим же розташуванням і масштабом, що й первинна ключова точка.

Описувач ключової точки

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

Спочатку створюють набір гістограм спрямування на околах 4×4 пікселя з 8 засіками кожен. Ці гістограми обчислюють на основі значень величини та спрямування зразків в області 16×16 навколо ключової точки таким чином, що кожна гістограма містить зразки з підобласті 4×4 первинної окільної області. Величини та спрямування градієнта зображення відбирають навколо розташування ключової точки, використовуючи масштаб ключової точки для обрання рівня гауссового розмиття зображення. Щоби досягти інваріантності щодо спрямування, координати описувача та спрямування градієнта повертають відносно спрямування ключової точки. Величини додатково зважують гауссовою функцією з $\sigma$ рівною половині ширини вікна описувача. Потім описувач стає вектором усіх значень цих гістограм. Оскільки там 4 × 4 = 16 гістограм, кожна з яких має 8 засіків, цей вектор має 128 елементів. Потім його унормовують до одиничної довжини, щоби підвищити інваріантність щодо афінних змін в освітленні. Щоби зменшити вплив нелінійного освітлення, застосовують поріг 0,2, і вектор знову унормовують. Цей процес порогування, який також називають закріплюванням (англ. clamping), може покращувати результати зіставляння навіть за відсутності нелінійних ефектів освітлення Поріг 0,2 було обрано емпірично, й результати зіставляння можливо покращити шляхом заміни цього фіксованого порогу обчислюваним системно.

Хоч вимірність описувача, тобто 128, і видається високою, описувачі з нижчою вимірністю не працюють так добре в низці задач зіставляння, а обчислювальна витратність залишається низькою через наближений метод ПЗЛ (див. нижче), який використовують для пошуку найближчого сусіда. Довші описувачі дійсно працюють краще, але не набагато, й існує додаткова небезпека підвищеної чутливості до спотворення та затуляння. Також було показано, що точність зіставляння ознак складає понад 50 % для змін кута огляду до 50 градусів. Тому описувачі SIFT інваріантні щодо незначних афінних змін. Щоби перевірити вирізнювальність описувачів SIFT, точність зіставляння також вимірюють за різною кількістю ключових точок у перевірній базі даних, і було показано, що для дуже великих розмірів бази даних точність зіставляння зменшується лише дуже незначно, що вказує на те, що ознаки SIFT дуже вирізнювальні.

Порівняння ознак SIFT з іншими локальними ознаками

Було проведено широке дослідження оцінки ефективності різних локальних описувачів, включно з SIFT, з використанням низки виявлячів. Основні результати підсумовано нижче:

• Ознаки SIFT і SIFT-оподібні ознаки GLOH демонструють найвищу точність зіставляння (рівні повноти) для афінного перетворення в 50 градусів. Після цієї межі перетворення результати починають ставати ненадійними.
• Вирізнювальність описувачів вимірюють підсумовуванням власних значень описувачів, отриманих методом головних компонент з описувачів, унормованих за їхньою дисперсією. Це відповідає величині дисперсії, яку вловлюють різні описувачі, а отже, їхній вирізнювальності. Найвищі значення дають ознаки PCA-SIFT (метод головних компонент, англ. Principal Components Analysis, застосований до описувачів SIFT), GLOH та SIFT.
• Описувачі на основі SIFT перевершують інші сучасні локальні описувачі як на текстурованих, так і на структурованих сценах, з більшою різницею в продуктивності на текстурованих сценах.
• Для змін масштабу в діапазоні 2—2,5 та обертання зображення в діапазоні від 30 до 45 градусів SIFT та описувачі на основі SIFT, знов-таки, перевершують інші сучасні локальні описувачі як із текстурованим, так і зі структурованим вмістом сцени.
• Додавання розмиття впливає на всі локальні описувачі, особливо ті, що ґрунтуються на контурах, як-от значення форми, оскільки контури в разі сильного розмиття зникають. Але GLOH, PCA-SIFT та SIFT все одно показали кращі результати, ніж інші. Це також справедливо для оцінювання за зміни освітленості.

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

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

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

Нещодавно було запропоновано невелику видозміну цього описувача, що використовує нерегулярну ґратку гістограми, значно покращуючи його продуктивність. Замість використання ґратки 4×4 засіків гістограм, всі засіки розширюють до центру ознаки. Це покращує стійкість описувача до змін масштабу.

Показано, що описувач SIFT-Rank покращує продуктивність стандартного описувача SIFT для афінного зіставляння ознак. Описувач SIFT-Rank породжують зі стандартного описувача SIFT, встановлюючи кожен засік гістограми згідно його рангу у впорядкованому масиві засіків. Евклідова відстань між описувачами SIFT-Rank інваріантна щодо довільних монотонних змін значень засіків гістограми та пов'язана з коефіцієнтом рангової кореляції Спірмена.

Застосування

Розпізнавання об'єктів за допомогою ознак SIFT

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

• Спершу отримують ознаки SIFT із вхідного зображення описаним вище алгоритмом.
• Ці ознаки зіставляють із базою даних ознак SIFT, отриманою з тренувальних зображень. Це зіставляння ознак виконують методом найближчого сусіда на основі евклідової відстані. Для підвищення стійкості збіги для тих ключових точок, в яких відношення відстані найближчого сусіда до відстані другого найближчого сусіда перевищує 0,8, відкидають. Це дозволяє відкидати багато хибних збігів, які виникають через захаращення тла. Нарешті, щоб уникнути витратного пошуку, необхідного для знаходження найближчого сусіда за евклідовою відстанню, використовують наближений алгоритм, що має назву «перший засік ліпший». Це швидкий метод для отримування найближчого сусіда з високою ймовірністю, який може давати 1000-кратне прискорення, знаходячи (потрібного) найближчого сусіда у 95 % випадків.
• Хоч описана вище перевірка співвідношенням відстаней і відкидає багато хибних збігів, які виникають через захаращення тла, все ще є збіги, які належать різним об'єктам. Тож щоби підвищити стійкість встановлювання об'єктів, ми хочемо кластерувати ознаки, які належать одному й тому ж об'єкту, й відкинути збіги, що лишилися в процесі цього кластерування. Це роблять за допомогою перетворення Гафа. Це дозволяє встановити кластери ознак, які голосують за одне й те ж положення об'єкта. Коли знайдено кластери ознак, які голосують за одне й те ж положення об'єкта, ймовірність правильності цієї інтерпретації набагато вища, ніж для будь-якої окремої ознаки. Кожна ключова точка голосує за набір положень об'єкта, які узгоджуються з її розташуванням, масштабом та спрямуванням. Засіки, які накопичили принаймні 3 голоси, встановлюють як потенційні збіги з об'єктом/положенням.
• Для кожного потенційного кластера методом найменших квадратів отримують розв'язок найкращої оцінки параметрів афінної проєкції, що пов'язують тренувальне зображення із вхідним. Якщо проєкція ключової точки за цими параметрами лежить у межах половини діапазону похибок, який використовували для параметрів у засіках перетворення Гафа, збіг ключової точки зберігають. Якщо після відкидання викидів у засіку лишається менше 3 точок, цей збіг об'єкта відхиляють. Допасовування методом найменших квадратів повторюють доти, поки відхилень більше не лишиться. Це працює краще для розпізнавання на площинній поверхні, ніж для розпізнавання тривимірних об'єктів, оскільки для них афінна модель вже не точна.
• У цьому журналі автори запропонували новий підхід до використання описувачів SIFT для цілей виявлення декількох об'єктів. Запропонований підхід виявляння декількох об'єктів перевірено на аерофото- та супутникових знімках.

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

Встановлювання розташування робота, та картографування

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

Зшивання панорам

Зіставляння ознак SIFT можливо використовувати у зшиванні зображень для повністю автоматичної відбудови панорам з непанорамних зображень. Ознаки SIFT, виділені з вхідних зображень, зіставляють одну з одною, щоби знайти k найближчих сусідів кожній. Потім ці відповідності використовують для пошуку m потенційних зображень, які збігалися би з кожним зображенням. Відтак обчислюють проєктивні перетворення між парами зображень за допомогою RANSAC, а для затверджування використовують імовірнісну модель. Оскільки обмежень щодо вхідних зображень немає, застосовують графовий пошук, щоби знайти компоненти зв'язності зіставлених зображень таким чином, щоби кожна компонента зв'язності відповідала панорамі. Нарешті, для кожної компоненти зв'язності виконують пучкове коригування, щоб отримати розв'язок для спільних параметрів камери, й унаочнюють панораму багатосмуговим злиттям. Завдяки підходу розпізнавання об'єктів на основі SIFT до зшивання панорам, отримана система нечутлива до впорядкування, спрямування, масштабу та освітлення зображень. Вхідні зображення можуть містити кілька панорам та шумові зображення (деякі з яких можуть навіть не бути частиною складеного зображення), а панорамні послідовності розпізнаються та відтворюються на виході.

Моделювання тривимірних сцен, розпізнавання та відстежування

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

Тривимірні SIFT-оподібні описувачі для розпізнавання людських дій

Досліджено розширення описувача SIFT до 2+1-вимірних просторово-часових даних у контексті розпізнавання людських дій у відеопослідовностях. Обчислення локальних залежних від положення гістограм у двовимірному алгоритмі SIFT розширено з двох до трьох вимірів для опису ознак SIFT у просторово-часовій області. Для застосування до розпізнавання людських дій у відеопослідовності вибірку з тренувальних відео здійснюють або в просторово-часових особливих точках, або у випадково визначених розташуваннях, часах і масштабах. Потім просторово-часові області навколо цих особливих точок описують за допомогою тривимірного описувача SIFT. Ці описувачі потім кластерують, щоб утворити просторово-часову модель торби слів. Тривимірні описувачі SIFT, отримані з перевірних відео, відтак зіставляють із цими словами для класифікування людських дій.

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

Аналіз людського мозку у тривимірних магнітно-резонансних зображеннях

Методика морфометрії на основі ознак (англ. Feature-based Morphometry, FBM) використовує екстремуми в різницях гауссового простору масштабів для аналізу та класифікування тривимірних магнітно-резонансних зображень (МРТ) людського мозку. FBM моделює зображення ймовірнісно, як колаж незалежних ознак, залежно від геометрії зображення та групових міток, наприклад, здорових суб'єктів, та суб'єктів із хворобою Альцгеймера (англ. Alzheimer's disease, AD). Ознаки спочатку виділяють на окремих зображеннях із чотиривимірної різниці гауссового простору масштабів, а потім моделюють з точки зору їхнього зовнішнього вигляду, геометрії та групової статистики спільної появи в наборі зображень. FBM було перевірено на аналізі AD з використанням набору з ~200 об'ємних МРТ людського мозку, з автоматичною ідентифікацією встановлених показників AD у мозку та класифікуванням легкої AD на нових зображеннях із частотою 80 %.

Конкурентні методи

До конкурентних методів масштабоінваріантного розпізнавання об'єктів в умовах захаращення / часткового затуляння належать наступні.

RIFT — це обертовоінваріантне (англ. rotation-invariant) узагальнення SIFT. Описувач RIFT будують за допомогою циркулярно нормованих ділянок, розділених на концентричні кільця однакової ширини, й у кожному кільці обчислюють гістограму спрямувань градієнтна. Щоби забезпечити обертову інваріантність, спрямування в кожній точці вимірюють відносно відцентрового напрямку.

RootSIFT — це варіант SIFT, який змінює унормовування описувача. Оскільки описувачі SIFT це гістограмами (і, як такі, — розподіли ймовірностей), використання евклідової відстані для визначання їхньої подібності — не природний вибір. Порівнювання таких описувачів з використанням мір подібності, розрахованих на розподіли імовірностей, таких як коефіцієнт Бгаттачар'я (відомий також як ядро Геллінгера), виявляється вигіднішим. Для цього первинно $\ell ^{2}$-нормований описувач спершу $\ell ^{1}$-нормують, а потім обчислюють квадратний корінь з кожного елемента, з наступним $\ell ^{2}$-перенормовуванням. Після цих алгебричних маніпуляцій описувачі RootSIFT можливо нормально порівнювати за допомогою евклідової відстані, що рівнозначне використанню ядра Геллінгера на первинних описувачах SIFT. Цю схему унормовування під назвою «L1-sqrt» було раніше запроваджено для унормовування блоків ознак HOG, чий варіант описувача з прямокутним влаштуванням блоків (R-HOG) концептуально подібний описувачеві SIFT.

G-RIF: Узагальнена стійка інваріантна ознака (англ. Generalized Robust Invariant Feature) — це описувач загального контексту, який кодує інформацію про спрямування та густину контурів та відтінок в уніфікованій формі, поєднуючи сприйняттєву інформацію з просторовим кодуванням. Схема розпізнавання об'єктів для оцінювання моделей об'єктів використовує голосування на основі окільного контексту.

«SURF: прискорені стійкі ознаки» (англ. Speeded Up Robust Features) — це високопродуктивний масштабо- та обертовоінваріантний виявляч/описувач особливих точок, який, як стверджують, наближується до, або навіть перевершує запропоновані раніше схеми щодо повторюваності, вирізнювальності та стійкості. SURF покладається на інтегральні зображення для згортання зображень, щоби скоротити тривалість обчислень, спирається на сильні сторони провідних наявних виявлячів та описувачів (використовуючи швидку міру на основі матриці Гессе для виявляча та описувача на основі розподілу). Описує розподіл відгуків гаарових вейвлетів в околі особливої точки. Інтегральні зображення використовують задля швидкості, й використовують лише 64 виміри, що скорочує час для обчислювання ознак та зіставляння. Крок індексування ґрунтується на знаку лапласіана, що підвищує швидкість зіставляння та стійкість описувача.

PCA-SIFT та GLOH — ще дві видозміни SIFT. Описувач PCA-SIFT — це вектор градієнтів зображення в напрямках x та y, обчислений у межах опорної області. Область градієнта вибирають у 39×39 положеннях, тому цей вектор має розмір 3042. Цей розмір зменшують до 36 за допомогою МГК (англ. PCA). Гістограма розташувань та напрямків градієнта (англ. Gradient location-orientation histogram, GLOH) — це розширення описувача SIFT, призначене для підвищення його стійкості та вирізнювальності. Описувач SIFT обчислюють для логарифмічної полярної ґратки розташування із трьома засіками в радіальному напрямку (радіус встановлюють у 6, 11 та 15) та 8 у кутовому напрямку, що дає 17 засіків розташування. Центральний засік на кути не ділять. Спрямування градієнта квантують у 16 засіках, що дає гістограму з 272 засіками. Розмір цього описувача зменшують за допомогою МГК. Коваріаційну матрицю для МГК оцінюють на фрагментах зображень, зібраних із різних зображень. Для опису використовують 128 найбільших власних векторів.

Gauss-SIFT — це чистий описувач зображення, визначений виконанням усіх вимірювань зображення, що лежать в основі чистого описувача зображення в SIFT, відгуками гауссових похідних, на відміну від наближень похідних у піраміді зображень, як у звичайному SIFT. Таким чином можливо звести до мінімуму ефекти дискретування простору та масштабу, уможлививши потенційно точніші описувачі зображень. У Ліндебергу (2015) такі чисті описувачі зображень Gauss-SIFT було поєднано з набором узагальнених масштабопросторових особливих точок, що складався з лапласіана гауссіана, визначника гессіана, чотирьох нових беззнакових та знакових мір вираженості гессіанових ознак, а також особливих точок Гарріса — Лапласа та Сі й Томазі. У масштабній експериментальній оцінці на плакатовому набору даних, що містив по декілька виглядів 12 плакатів за перетворень масштабування до шестикратного й змін кута огляду до нахилу 45 градусів, було показано, що значне підвищення продуктивності зіставляння зображень (вищі оцінки ефективності й нижчі оцінки 1−влучність) можливо отримати заміною особливих точок лапласіана гауссіана особливими точками визначника гессіана. Оскільки особливі точки різниці гауссіанів становлять чисельне наближення особливих точок лапласіана гауссіана, це показує можливість суттєвого підвищення продуктивності зіставляння шляхом заміни особливих точок різниці гауссіанів у SIFT особливими точками визначника гессіана. Крім того, можливо отримати додаткове підвищення продуктивності, розглядаючи беззнакову міру вираженості гессіанових ознак $D_{1}L=\operatorname {det} HL-k\,\operatorname {trace} ^{2}HL\,{\mbox{якщо}}\operatorname {det} HL-k\,\operatorname {trace} ^{2}HL>0\,{\mbox{або 0 інакше}}$ . Кількісне порівняння описувача Gauss-SIFT із відповідним описувачем Gauss-SURF також показало, що Gauss-SIFT загалом працює значно краще за Gauss-SURF для великої кількості різних виявлячів масштабопросторових особливих точок. Тож це дослідження показує, що без урахування ефектів дискретування чистий описувач зображень у SIFT значно кращий за чистий описувач зображень у SURF, тоді як виявляч особливих точок в основі SURF, який можливо розглядати як чисельне наближення масштабопросторових екстремумів визначника гессіана, значно кращий за виявляч особливих точок в основі SIFT.

Ваґнер зі співавт. розробили два алгоритми розпізнавання об'єктів, спеціально спроєктовані з урахуванням обмежень сучасних мобільних телефонів. На відміну від класичного підходу SIFT, для виявляння ознак вони використовують виявляч кутів FAST. Цей алгоритм також виокремлює автономну підготовчу стадію, де створюють ознаки на різних рівнях масштабу, й інтерактивну стадію, де ознаки створюють лише на поточному фіксованому рівні масштабу зображення камери телефону. Крім того, ознаки створюють із фіксованого розміру фрагмента 15×15 пікселів, й утворюють описувач SIFT лише з 36 вимірами. Цей підхід було додатково розширено вбудовуванням до конвеєру розпізнавання масштабованого словникового дерева. Це дозволяє ефективно розпізнавати на мобільних телефонах більшу кількість об'єктів. Цей підхід обмежено переважно обсягом доступної оперативної пам'яті.

KAZE та A-KAZE (англ. KAZE Features та англ. Accelerated-Kaze Features) — це новий метод виявляння та опису двовимірних ознак, який працює краще порівняно з SIFT та SURF. Він набуває великої популярності завдяки своєму відкритому коду. Первинно KAZE створили Пабло Ф. Алькантарілья, Адріан Бартолі та Ендрю Дж. Девісон.

Див. також

• Згорткова нейронна мережа
• Зшивання зображень
• Простір масштабів
• Втілення простору масштабів
• Одночасне визначання місцезнаходження та картографування
• Структура з руху

Посилання

Пов'язані дослідження:

• The Invariant Relations of 3D to 2D Projection of Point Sets, Journal of Pattern Recognition Research(JPRR), Vol. 3, No 1, 2008. (англ.)
• Lowe, D. G., “Distinctive Image Features from Scale-Invariant Keypoints”, International Journal of Computer Vision, 60, 2, pp. 91-110, 2004. (англ.)
• Mikolajczyk, K., and Schmid, C., "A performance evaluation of local descriptors", IEEE Transactions on Pattern Analysis and Machine Intelligence, 10, 27, pp 1615--1630, 2005. (англ.)
• PCA-SIFT: A More Distinctive Representation for Local Image Descriptors. Архів оригіналу за 26 січня 2020. (англ.)
• Lazebnik, S., Schmid, C., and Ponce, J., Semi-Local Affine Parts for Object Recognition, BMVC, 2004. (англ.)

Посібники:

• Scale-Invariant Feature Transform (SIFT) у Scholarpedia (англ.)
• Простий покроковий посібник із SIFT (англ.)
• SIFT для виявляння кількох об'єктів (англ.)
• «Анатомія методу SIFT» в інтерактивній обробці зображень, детальне вивчення кожного кроку алгоритму з втіленням із відкритим кодом, та веб-показ для випробування різних параметрів (англ.)

Втілення:

• Втілення SIFT від Роба Гесса доступ 21 листопада 2012 року
• ASIFT (Affine SIFT): велике зіставляння точок огляду за допомогою SIFT, із первинним кодом та онлайн-показом
• VLFeat, відкрита бібліотека комп'ютерного зору мовою C (з інтерфейсом MEX для MATLAB), включно зі втіленням SIFT
• LIP-VIREO, інструментарій для виділяння ознак ключових точок (двійкові файли для Windows, Linux та SunOS), включно зі втіленням SIFT
• (Паралельний) SIFT у C#, алгоритм SIFT у C# з використанням Emgu CV, а також видозмінена паралельна версія алгоритму.
• DoH & LoG + affine, виявляч плям, перероблений з інструментарію SIFT
• ezSIFT: просте у використанні автономне втілення SIFT мовами C/C++. Автономне втілення SIFT із відкритим кодом, яке не потребує інших бібліотек.
• Втілення тривимірного SIFT: виявляння та зіставляння в об'ємних зображеннях.