Технічні науки

УДК 004.932.72

Ященко Микола Сергійович

студент

Національного технічного університету України

«Київський політехнічний інститут імені Ігоря Сікорського»

Ященко Николай Сергеевич

студент

Национального технического университета Украины

«Киевский политехнический институт имени Игоря Сикорского»

Yashchenko Mykola

Student of the

National Technical University of Ukraine

«Igor Sikorsky Kyiv Polytechnic Institute»

ВДОСКОНАЛЕНИЙ АЛГОРИТМ SIFT ДЛЯ ПОРІВНЯННЯ ЗОБРАЖЕНЬ СУДИННОЇ СИСТЕМИ

УЛУЧШЕННЫЙ АЛГОРИТМ SIFT ДЛЯ СРАВНЕНИЯ ИЗОБРАЖЕНИЙ СОСУДИСТОЙ СИСТЕМЫ

ENHANCED SIFT ALGORITHM FOR COMPARING IMAGES OF VASCULAR SYSTEM

Анотація. Розглянуто покращений алгоритм SIFT для порівняння зображень судинної системи.

Ключові слова: обробка зображень, SIFT, ключові точки.

Аннотация. Рассмотрено улучшенный алгоритм SIFT для сравнения изображений сосудистой системы.

Ключевые слова: обработка изображений, SIFT, ключевые точки.

 Summary. Reviewed the enhanced SIFT algorithm for comparing images of vascular system.

Key words: image processing, SIFT, keypoints. 

Вступ. Зіставлення зображень для встановлення міри їх подібності є ключовою проблемою багатьох задач комп’ютерного зору. Загалом, існуючі алгоритми можна поділити на дві категорії:

• алгоритми на основі глобальних функцій
• алгоритми на основі локальних функцій.

Алгоритми на основі пошуку глобальних ознак направлені на розпізнавання цілого об’єкта. Для досягнення цього, зображення послідовно обробляють і сегментують. Потім виконують пошук глобальних характеристик об’єкту і застосовуються деякі методи класифікації.  Алгоритми, засновані на пошуку глобальних ознак, забезпечують простоту і швидкодію, але мають обмеження в надійності розпізнавання при зміні освітлення чи позиції об’єкта [1].

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

• пошук основних ознак
• побудова регіонів на знайдених точок з використанням механізмів, спрямованих на збереження регіонів, нечутливих до зміни світла чи позиції
• зіставлення знайдених точок між моделями

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

SIFT алгоритм

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

Першим кроком являється виявлення екстремумів – на цьому кроці локальні ключові ознаки визначаються за допомогою локальних екстремумів функції різниці Гауса (DOG піраміда) [2]. Для побудови DOG піраміди вхідне зображення згортається ітеративно з ядром Гаусіана . Для останнього згорнутого зображення роблять зниження розширення і процес згортки повторюється. Ця процедура повторюється до тих пір, доти можлива згортка.

Простір зображення визначається як функція , яку можна отримати як згортку Гаусіана зі змінним масштабом  та вхідного зображення, де  – операція згортки на x та y; .

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

Третім кроком являється визначення орієнтації. Як тільки знайдено місцезнаходження ключових точок SIFT, кожній з них призначається одна чи декілька орієнтацій за допомогою локальних градієнтів зображення. Для кожного регіону зображення навколо ключової точки L(x,y), значення градієнта m(x,y) і орієнтація  обчислюються наступним чином:

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

Четвертим кроком являється дескриптор ключової точки. Регіон навколо ключової точки розділяється на 4 частини. Градієнтні величини та орієнтації в середині кожної частини обчислюються та зважуються відповідним вікном гаусіана, а координати кожного пікселя та його градієнт орієнтації повертають відносно орієнтації ключових точок. Потім для кожної частини встановлюються 8 гістограм орієнтації. З 16 отриманих гістрограм орієнтації будується 128-вимірний вектор (SIFT дескриптор). Цей дескриптор інваріантний проти орієнтації, а також інваріантний до освітлення якщо його нормалізувати до одиниці вимірювання [4].

Пошук відповідностей

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

Щоб виявити чи дійсно співпадіння правильне, використовують порогове значення. Якщо Евклідова відстань між точками нижче певного порогу, то співпадіння позначається позитивним [5].

Вдосконалення алгоритму SIFT для кращого пошуку відповідностей

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

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

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

RANSAC

Щоб зменшити кількість хибних співпадінь, пропонується застосувати алгоритм RANSAC.

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

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

На вхід алгоритму поступають:

• набір вхідних даних X;
• функція М, яка дозволяє обрахувати параметри моделі;
• функція оцінки Е відповідності точок отриманої моделі;
• поріг t для функції оцінки;
• кількість ітерацій методу.

RANSAC – ітеративний алгоритм, який обирає випадкову підмножину співпадінь зі списку всіх співпадінь і заповнює модель (гомографію) для них. Для заповнення афінної гомографії потрібна підмножина з щонайменше 4х елементів. Таку підмножину зазвичай називають мінімальною підмножиною. Після цього модель перевіряють на всіх інших співпадіннях зі списку. Відповідності, які відповідають моделі розглядаються як гіпотетичні не-викиди, а ті які не задовольняють модель вважаються гіпотетичними викидами.

Після фіксованої кількості ітерацій, модель з найбільшою кількістю не-викидів обирається як вірна. Чим більша кількість ітерацій, тим вища ймовірність знаходження правильної моделі.

Рис. 1. Кроки алгоритму RANSAC

Реалізація алгоритму

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

Результатом роботи програми є файл зі знайденими відповідностями на вхідних зображеннях.

Рис. 2. Відповідності знайдені оригінальним алгоритмом (зображення належать різним людям)

Рис. 3. Відповідності, відфільтровані алгоритмом RANSAC (червоним позначено неістинні відповідності, а зеленим – істинні)

Рис. 4. Відповідності знайдені покращеним алгоритмом (зображення належать одній і тій же людині)

Висновки.  В роботі було розглянуто задачу порівняння зображень судинної системи. Було розроблено вдосконалений алгоритм SIFT, який має додатковий крок – фільтрацію ключових точок з урахуванням глобальних властивостей ключових точок. 

Література

1. Eichmann, L. Yuan, D. Moyon, F. Lenoble, L. Pardanaud, and C. Breant, “Vascular development: from precursor cells to branched arterial and venous networks,” International Journal of Developmental Biology, no. 49, pp. 259–267, 2005.
2. Lowe D.G. Distinctive image features from scale-invariant keypoints / D.G. Lowe // International Journal of Computer Vision, 2004. —V. 60. — N2. — P. 91-110.
3. Speeded Up Robust Features : http://en.wikipedia.org/wiki/SURF Ethan Rublee, Vincent Rabaud, Kurt Konolige, Gary Bradski “ORB: an efficient alternative to SIFT or SURF”, Computer Vision (ICCV), 2011 IEEE International Conference on. IEEE, 2011.
4. Beis, J. Shape indexing using approximate nearest-neighbour search in highdimensional spaces / Beis, J. and Lowe, D.G. / In Conference on Computer Vision and Pattern Recognition, Puerto Rico, 1997. — Pp. 1000- 1006.
5. Зорін Ю. М., Сергієнко А. М., Сергієнко П. А. Пошук характерних ознак у зображенні з широким динамічним діапазоном / К.т.н., доцент Зорін Ю. М., с.н.с. Сергієнко А. М., студент Сергієнко П.А. // Прикладна математика та комп’ютинг. ПМК, 2017: десята наук. конф. магістрантів та аспірантів, Київ, 21-23 бер. 2017 р. : зб. тез доп.