Комп’ютерні науки

УДК 004.932.2

Жукова Олена Анатоліївна

студент

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

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

ДЕСКРИПТОР ТОЧКИ ІНТЕРЕСУ У ЧАСТОТНОМУ ДІАПАЗОНІ

Анотація. Досліджено теоретичні питання виявлення точок інтересу та формування дескрипторів ознак цифрових зображень.

Ключові слова: комп’ютерний зір, цифрові зображення, детектор ознак, дескриптор ознак.

Сучасні застосування комп’ютерного зору широко використовуються для виконання багатьох практичних завдань, таких як реєстрація зображень, розпізнавання об’єктів, 3D реконструкція та інші. Розробка математичного обчислювального представлення зображення є передумовою для таких застосувань або алгоритмів. У багатьох існуючих моделях таке представлення створюється за допомогою наступних кроків:

1. виявлення точки інтересу, тобто виявлення характеристик зображення які є стійкими до шуму, помилок у виявленні та геометричних або фотометричних деформацій;
2. описання характеристики (дескриптор), тобто створення математичного описання, яке забезпечує можливість чисельного обрахування порівняння характеристик;
3. співставлення пари дескрипторів, засноване на оцінці їх схожості, наприклад, евклідова відстань між векторами дескрипторів.

Історично більшість детекторів ключових точок основані на першій та другій просторовій похідній. Найбільш значними представниками такого підходу є кутовий детектор Гарріса [3], який використовує матрицю других похідних та його стійкі до масштабування модифікації, наприклад, оператори Лапласа Гаусса, різниці Гауса SIFT [5] та швидкий детектор Гессе SURF [4]. Серед зазначених, швидкий детектор Гессе показує найкращі показники з продуктивності, у той же час, його результати є стійкими до зміни освітлення та зміщення.

Серед детекторів які не основані на алгоритмі Гарріса, можна виділити FAST [6], який є швидшим за SURF, але він не є стійким до масштабування. В результаті виявлення точки інтересу отримуємо пару координат та масштаб (x,y,s), які передаються як вхід до дескриптора характеристики.

Найбільш помітними реалізаціями дескрипторів характеристик є SIFT та SURF, які вважаються стандартами галузі для сучасних застосувань. Однак, розмір цих дескрипторів варіюється від 144 до 512 байт, що призводить до великих потреб у пам’яті та створює перешкоди для великомасштабних застосувань. Теоретично, дескриптор розміром 144 байти (1152-біт) може відрізнити 2¹¹⁵² різних об’єкти. Це є набагато більше ніж потрібно у будь-якому практичному застосуванні. Більш того, дескриптори SIFT та SURF базуються на векторах з десятковими дробами, через що розрахунок відстані потребує більше часу.

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

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

Кожна з областей, що описується поділяється на рівномірну ортогональну сітку, для прикладу візьмемо сітку розміром 8×8 комірок. Після чого вираховується середня освітленість для кожної з комірок, таким чином отримуємо 8×8 матрицю освітленості Lxy. Як необов’язковий крок, можна збільшити продуктивність шляхом завдяки інтегральним зображенням [Crow, 1984], що зробить розрахунок середньої освітленості операцією з константною складністю O(1). Наступним кроком матриця освітленості переводиться у частотний діапазон, шляхом дискретної трансформації Фур’є, точніше її різновиду, дискретної косинусної трансформації DCT [1]. Так як, DCT є достатньо дорогою операцією у сенсі продуктивності, доцільно застосувати DCT з цілими числами, замість DCT з десятковими дробами. В результаті цієї операції отримаємо 8×8 матрицю у частотному діапазоні Fi j .

В результаті перетворення зображення з просторового у частотне відображення ми отримаємо 64 числа, кожне з яких описує незалежну особливість зображення на відміну від просторового відображення в якому жоден піксель не може описати зображення або його область в цілому. Наприклад, коефіцієнт F₀₀ відповідає середній освітленості всієї площі, F₁₀ характеризує градієнт по осі ординат, аналогічно F₀₁ відповідає градієнту по осі абсцис, а F₂₂ відповідає світлій або темній ділянці у центрі зображення (залежно від знаку + або -).

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

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

де  є довільною достатньо великою константою наприклад .

Після нормалізації, кожен з коефіцієнтів матриці f_{i j} показує важливість характеристики відповідно до цього коефіцієнту у порівнянні з усіма іншими характеристиками. Таким чином, візуально значні характеристики будуть мати значні абсолютні значення їх відповідних коефіцієнтів.

Доцільно відкинути частину f_{i j} з високими частотами, так як високі частоти рідко є важливими та часто відповідають шуму на зображенні. Також, корисно зробити дескриптор якомога компактнішим. Завдяки візуальній незалежності характеристик, що описують коефіцієнти матриці усі інші коефіцієнти можуть зберігатися у вигляді лише одного біту в якому одиниця буде означати велике абсолютне значення цього коефіцієнту, а 0 – означатиме, що коефіцієнт f_{i j} близький до нуля. Для того, щоб провести таку класифікацію кожне значення |f_ij| має бути порівняно з визначеним заздалегідь порогом T_ij. Важливо зауважити, що поріг може не бути однаковим для різних частот. Враховуючи що значення високих частот матриці f_{i j} звичайно нижчі ніж значення для низьких частот, поріг T_ij має бути меншим.

Конкретне значення порогу T_ij залежить від типу зображення над яким проводяться операцій і має бути відкоригований залежно від конкретних реалізацій. Один з кращих способів визначити поріг T_ij є статистичний підхід. В першу чергу вибирається тренувальний набір зображень залежно від галузі застосування. Тоді вираховується матриця f_{i j} для кожної точки інтересу у кожному зображенні з тренувального набору. Після цього для кожної пари точок i,j та медіан m_{i j} вираховується f_{i j}. Значення m_{i j} може бути безпосередньо застосовано як поріг.

Після вибірки за пороговим значенням, описаним вище, розмір пам’яті, яку займає дескриптор, зменшується до N біт, де N – це кількість не відкинути коефіцієнтів матриці. Для того, щоб покращити визначальність дескриптора за рахунок його розміру значні від’ємні та додатні коефіцієнти матриці можуть зберігатися окремо, таким чином збільшуючи розмір дескриптора до 2N біт.

Отриманий таким чином дескриптор області представляє собою бітові рядки, які об’єднуються у один дескриптор цілої площі.

На відміну від дескрипторів SIFT чи SURF, де відстань вираховується як евклідова відстань між векторами дескрипторів, для дескрипторів у частотному діапазоні відстань визначається як відстань Геммінга між двома послідовностями бітів. Таким чином відстань між двома дескрипторами може визначатися як вага Геммінга, що означає побітову операцію XOR з мірою складності O(log n) де n – є довжина бітового рядка. Таким чином досягається значне збільшення швидкості порівняння дескрипторів.

Література

1. “Discrete cosine transform” (Ahmed N., Natarajan T. and Rao K. R.
2. “Summed-area tables for texture mapping” (Crow, Franklin ).
3. “A combined corner and edge detector” (Harris C., Stephens M. ).
4. “Surf: Speeded up robust features” (Herbert Bay, Andreas Ess, Tinne Tuytelaars, Luc Van Gool).
5. “Distinctive image features from scale-invariant keypoints” (Lowe, D. G. ).
6. “Machine learning for high-speed corner detection” (E. Rosten and T. Drummond).