Аннотация: Использование беспилотных летательных аппаратов (БПЛА) для проведения аэрофотосъемки является чрезвычайно актуальным направлением развития методов сбора геопространственных данных на сегодня. Особенно в военное время - для ведения разведки противника, однако существует возможность создания радиоэлектронных помех, что приводит к перехвату БПЛА, или его "ослепления". В данной работе исследованы методы автономной навигации по оптическим ориентирам.
Ключові слова: БПЛА, автономная навигация.
Технічні науки
УДК 62.519
Дичко Віктор Миколайович
студент
Київський Національний Технічний Університет «КПІ»
Ляхевич Сергій Володимирович
аспірант ІПСА
Київський Національний Технічний Університет «КПІ»
Дычко Виктор Николаевич
студент
Киевський Национальный Технический Университет «КПИ»
Ляхевич Сергей Владимирович
аспирант ИПСА
Киевський Национальный Технический Университет «КПИ»
Dychko V.
student
Kyiv National Technical University “KPI”
Liakhevych S.
postgraduate
Kyiv National Technical University “KPI”
ОПТИЧНА НАВІГАЦІЙНА СИСТЕМА БПЛА: ПОРІВНЯЛЬНИЙ АНАЛІЗ АЛГОРИТМІВ ЗНАХОДЖЕННЯ КЛЮЧОВИХ ТОЧОК
ОПТИЧЕСКАЯ НАВИГАЦИОННАЯ СИСТЕМА БПЛА: СРАВНИТЕЛЬНЫЙ АНАЛИЗ АЛГОРИТМОВ НАХОЖДЕНИЯ КЛЮЧЕВЫХ ТОЧЕК
OPTICAL NAVIGATION SYSTEM: KEY-POINTS FINDING ALGORITHMS COMPARATIVE ANALYSIS
Анотація: Використання безпілотних літальних апаратів (БПЛА) для проведення аерофотозйомки є надзвичайно актуальним напрямком розвитку методів збору геопросторових даних на сьогодні. Особливо у військовий час – для ведення розвідки супротивника,проте існує можливість створення радіоелектронних завад, що призводить до перехоплення БПЛА, або його “засліплення”. В даній роботі досліджені методи автономної навігації за оптичними оріентирами.
Ключові слова: БПЛА, автономна навігація.
Аннотация: Использование беспилотных летательных аппаратов (БПЛА) для проведения аэрофотосъемки является чрезвычайно актуальным направлением развития методов сбора геопространственных данных на сегодня. Особенно в военное время - для ведения разведки противника, однако существует возможность создания радиоэлектронных помех, что приводит к перехвату БПЛА, или его "ослепления". В данной работе исследованы методы автономной навигации по оптическим ориентирам.
Ключові слова: БПЛА, автономная навигация.
Abstract: The use of unmanned aerial vehicles (UAVs) for aerial photography is an extremely important area of geospatial data collection methods today. Especially in wartime - for reconnaissance of the enemy, but the creation of electronic interference that results in intercepting or "blinding" the UAV is possible . This paper investigated methods of autonomous navigation optical orientyramy.
Key words: UAV, autonomous navigation.
Вступ
Використання безпілотних літальних апаратів (БПЛА) для проведення аерофотозйомки є надзвичайно актуальним напрямком розвитку методів збору геопросторових даних на сьогодні. В мирні часи цю інформацію можна використовувати для пошуку лісових пожеж, моніторингу стану доріг та трубопроводів, а у військові – для ведення розвідки супротивника. Проте саме у військовий час проведення місій БПЛА обмежено через недоліки системи керування.
БПЛА можуть бути керовані оператором за допомогою пульта, проте такий підхід суттєво звужує радіус їхньої дії. Найбільш поширеними на сьогодні є автономні БПЛА, які при здійсненні своєї місії використовують координати GPS, проте існує можливість створення потенційним супротивником фальшивого сигналу GPS чи радіоелектронних завад, що призводить відповідно до перехоплення БПЛА, або його “засліплення”.
Одним з способів вирішення цієї проблеми є використання допоміжних систем, які будуть працювати на фізичних принципах, що відрізняються від принципів роботи основної навігаційної системи. У випадку, коли основна навігаційна система працює на базі сигналів GPS, допоміжною може бути оптична навігаційна система, яка визначає положення шляхом співставлення зображення, отриманого з відеокамери БПЛА з картою, що прошита в Базі знань БПЛА. Проте такий підхід містить ряд технічних труднощів. По-перше поточний ландшафт та той, що міститься на прошитій карті можуть відрізнятися, особливо якщо місія здійснюється в зоні бойових дій - об’єкти, такі як будівлі, дороги можуть бути знищені. По-друге, зазвичай висота, на якій здійснюють свої місії БПЛА та висота на якій здійснюється аерофотозйомка для формування прошитої карти суттєво відрізняються. Отже, необхідно співставляти зображення з урахуванням масштабування, проективного перетворення та часткової зміни об’єктів. Незважаючи на відмінності зображень, деякі частини залишаються незмінними, тому для розпізнавання спільних точок доцільно застосовувати алгоритми, які знаходять ключові точки зображень та їх дескриптори [1-4], за допомогою яких ці точки можна порівнювати.
Мета даної статті полягає в дослідженні та порівняльному аналізі алгоритмів знаходження ключових точок та їхніх дескрипторів з ціллю використання в оптичній системі навігації БПЛА.
Алгоритм SIFT знаходить характеристики зображення, які інваріантні до масштабування зображення і обертання, та частково інваріантні до змін в освітленні і точки знімання 3D камери [1, 2]. Виявлені характеристики значно відрізняються одна від одної, що дозволяє з високою ймовірністю коректно знайти відповідність між однаковими характеристиками та різних зображеннях, забезпечуючи основу для розпізнавання об’єктів.
Алгоритм включає такі основні етапи:
Простір масштабів зображення визначається як функція , що отримується як згортка гаусіана зі змінним масштабом та вхідного зображення :
де – операція згортки на і , і
Функція згортки різниці гаусіанів із зображенням , що може бути обчислена як різниця двох сусідніх масштабів, розділених константним множником :
Масштаб ключової точки використовується для того, щоб вибрати зображення , згладжене гаусіаном. Для кожного зразка зображення , значення градієнта і орієнтація обчислюється як різниця пікселів:
Рисунок 1 – Дескриптор ключової точки
Алгоритм SURF базується на таких самих принципах і кроках, як і SIFT, але конкретна реалізація на кожному кроці відрізняється [3]. Алгоритм має три основні частини: виявлення характерних точок, опис і співставлення характеристик локального околу.
Виявлення ключових точок
SURF використовує детектор на основі матриці Гессе для знаходження ключових точок. Визначник матриці Гессе використовується в якості міри локальної зміни навколо точки. Обираються точки, де цей визначник максимальний. SURF також використовує визначник матриці Гессе для вибору масштабу.
Матриця Гессе в точці зображення масшатабу визначається наступним чином:
де – згортка похідної гаусіана другого порядку із зображенням в точці . Аналогічно для і .
В алгоритмі використовуються квадратні фільтри, що апроксимують похідні гаусіана другого порядку і можуть бути розраховані дуже швидко за допомогою інтегрального представлення зображення, незалежно від розміру.
Рисунок 2 – Зліва на право: (дискретизовані і обрізані) часткові похідні гаусіана другого порядку в напрямках , і їх апроксимація за допомогою квадратних фільтрів. Сірі області дорівнюють нулю.
Дескриптори
Дескриптор SURF базується на подібних до SIFT властивостей, але при цьому має ще меншу складність. Перший крок складається з фіксації відтворюваної орієнтації на основі інформації з кругової області навколо ключової точки. Далі будується квадратна область, вирівняна до вибраної орієнтації, з якої отримується SURF-дескриптор.
ASIFT імітує з достатньою точністю всі спотворення викликані варіацією направлень оптичної осі камери [4]. Потім застосовується метод SIFT. Іншими словами, ASIFT імітує три параметри: масштаб, кут довготи камери і кут широти і нормалізує інші (поворот і зміщення).
ASIFT включає наступні кроки:
Для співставлення супутникових знімків, що зроблені з різних позицій та мають спотворення перспективи і деякі локальні спотворення, такі як зміна будинків, доріг, дерев (наприклад, у залежності від пори року) та ін. будемо використовувати алгоритми SIFT, SURF, ASIFT як базові.
Алгоритм співставлення знімку та зображення зі супутника складається з наступних етапів.
Приклад знаходження ключових точок за допомогою алгоритмів SIFT, SURF, ASIFT на повному зображенні, яке необхідно перетворити (роздільна здатність: 500x667 пікселів) представлено на рисунку 3. Під час дослідження використовувалися зображення з роздільною здатністю 1944х2592 із значно більшою кількістю ключових точок.
Рисунок 3 – Ключові точки (SIFT, SURF, ASIFT)
Дослідження показало, що при класичному застосуванні SIFT, SURF та ASIFT, тобто при спробі знаходження перетворення зображення на основі всіх знайдених точок, результат виходить незадовільний внаслідок великої кількості неправильних співставлень точок. Приклад співставлення усіх точок зображень показано на рисунку 4.
Рисунок 4 – Співставлення всіх ключових точок
Внаслідок помилок співставлення всіх точок, описаних на етапі 1, для подальшої роботи алгоритму запропоновано на другому кроці алгоритму співставлення виділити декілька (2-4) відповідних областей на парі зображень. Приклад виділення областей показано на рисунках 8 та 12.
На даному етапі всі ключові точки, що не потрапили у відповідні області виключалися із розгляду, таким чином, зменшуючи кількість неправильних співставлень. Приклад зображень з співставленими ключовими точками на виділених областях отриманими за допомогою алгоритму ASIFT наведено на рисунку 5.
Рисунок 5 – Відповідні області та співставлення ключових точок
Відображення точок двовимірної плоскої поверхні на зображення камери є прикладом гомографії. Це відображення можна виразити в термінах множення матриць при використанні однорідних координат, щоб виразити спостережувану точку і точку на зображенні , у яку відображається. Гомографія може бути виражена як , де , , де – масштабний коефіцієнт.
Приклад знаходження перетворення гомографії для зображення знімку представлено на рисунку 6 (посередині).
Результуюче зображення отримується як зважена сума отриманого після перетворення гомографії та зображення зі супутника. Приклад представлено на рисунку 6.
Рисунок 6 – Зліва на право – оригінальне зображення, перетворене та результат накладання
Процедура визначення якості перетворення зображення складається з наступних кроків:
На цьому етапі перевіряється наявність дзеркального відбиття для пар вершин зображення по горизонталі та вертикалі. При його наявності, якість перетворення зображення встановлюється рівною нулю. В іншому випадку якість розраховується, як описано нижче (етап 2, 3). Приклад некоректного перетворення з нульовою якістю наведено на рисунках 10 та 14 (перші зображення).
Після перетворення гомографії змінюється форма зображення. Тому, для порівняння потенційно подібних частин зображень, на перетвореному зображенні виділялась прямокутна область. Приклад виділення такої області наведено на рисунку 7.
Рисунок 7 – Виділення внутрішньої прямокутної області
Якість коректного перетворення (ступінь подібності перетвореного зображення до зображення зі супутника) вимірювалась за допомогою SSIM.
Відмінною особливістю індексу структурної подібності (SSIM) є те, що метод враховує «сприйняття помилки» завдяки врахуванню структурної зміни інформації. Ідея полягає в тому, що пікселі мають сильний взаємозв’язок, особливо коли вони близькі просторово. Дані залежності містять важливу інформацію про структуру об’єктів і про зображення загалом. Метрика SSIM розрахована на різні розміри вікна. Різниця між двома вікнами і , що мають однаковий розмір :
де
– середнє
– середнє
– дисперсія
– дисперсія
– коваріація і
– динамічний діапазон пікселів (зазвичай )
, – константи. [5]
Приклади обчислення значень SSIM для різних зображень представлено на рисунках 10, 11, 14, 15.
3. Аналіз результатів дослідження порівняння алгоритмів
В якості вибірки для порівняльного аналізу використовувалися зображення, зняті з БПЛА в зоні донецького аеропорту, в якості карти використовувалася карта Google. При проведенні дослідження, на кожному зображенні виділялись відповідні області, які потім подавались на вхід вищеописаному алгоритму для перетворення зображення.
Для кожного експерименту та кожного набору областей застосовувалося зміщення кожної області (на 20% від розміру області) для кожного з чотирьох діагональних напрямків. Зміщення застосовувалося до областей зображення, яке необхідно перетворити; області зображення супутника залишалися незмінними. Середня якість чутливості – середня якість для перетворених зображень, для областей яких застосовувалося таке зміщення.
Також, експерименти проводилися для збільшених розмірів областей на 75%. Результати представлені в стовпці «Середня якість зі збільшеними областями».
В таблицях 1 та 3 наведено час виявлення ключових точок для різних експериментів, що є важливим при побудові систем реального часу. В таблицях 2 та 4 представлені дані щодо якості накладання зображень в залежності від обраного алгоритму та кількості областей співставлення.
Експеримент №1
Розглянемо приклад пари зображень із двома виділеними областями наведений на Рисунку 8.
Рисунок 8 – Зображення з виділеними відповідними областями
Таблиця 1 – Час виявлення ключових точок
|
Алгоритм |
Час виявлення ключових точок (сек.) |
Час співставлення дескрипторів (сек.) |
|
SIFT |
12,12 |
2,915 |
|
SURF |
4,183 |
1,406 |
|
ASIFT |
252,762 |
21,205 |
Таблиця 2 – Якість накладання зображень
|
Алгоритм |
Кількість областей |
Кількість експериментів |
Середня якість |
Максимальна якість |
Відсоток з перетворень з ненульовою якістю |
Середня якість чутливості |
Середня якість зі збільшеними областями |
|
SIFT |
2 |
10 |
0,00 |
0,00 |
0,00 |
0,00 |
0,05 |
|
3 |
10 |
0,17 |
0,59 |
0,40 |
0,02 |
0,06 |
|
|
4 |
5 |
0,00 |
0,00 |
0,00 |
0,08 |
0,22 |
|
|
SURF |
2 |
10 |
0,05 |
0,49 |
0,10 |
0,00 |
0,00 |
|
3 |
10 |
0,28 |
0,58 |
0,50 |
0,04 |
0,12 |
|
|
4 |
5 |
0,57 |
0,58 |
1,00 |
0,16 |
0,43 |
|
|
ASIFT |
2 |
10 |
0,34 |
0,61 |
0,70 |
0,29 |
0,37 |
|
3 |
10 |
0,50 |
0,58 |
0,90 |
0,46 |
0,44 |
|
|
4 |
5 |
0,57 |
0,58 |
1,00 |
0,56 |
0,57 |
З графіків представлених на рисунку 9 можна побачити, що найкращу якість дає алгоритм ASIFT, проте при 4 областях його результати та результати SURF близькі.
Рисунок 9 – Порівняння якості співставлення зображень (рисунок 8) різних алгоритмів виділення ключових точок з різною кількістю виділених областей
На Рисунках 10 та 11 наведено приклади перетворення зображень із різною якістю.
Рисунок 10 – Приклади перетворення зображень з різною якістю. Зліва на право: 0; 0,47
Рисунок 11 – Приклади перетворення зображень з різною якістю. Зліва на право: 0,50; 0,57
Експеримент №2
Дослідимо ще один приклад пари зображень із двома виділеними областями наведений на Рисунку 12.
Рисунок 12 – Зображення з виділеними відповідними областями
Таблиця 3 – Час виявлення ключових точок
|
Алгоритм |
Час виявлення ключових точок (сек.) |
Час співставлення дескрипторів (сек.) |
|
SURF |
4,144 |
0,964 |
|
ASIFT |
271,837 |
47,62 |
Таблиця 4 – Якість накладання зображень
|
Алгоритм |
Кількість областей |
Кількість експериментів |
Середня якість |
Максимальна якість |
Відсоток з перетворень з ненульовою якістю |
Середня якість чутливості |
Середня якість зі збільшеними областями |
|
SURF |
2 |
10 |
0,00 |
0,00 |
0,00 |
0,00 |
0,04 |
|
3 |
10 |
0,00 |
0,00 |
0,00 |
0,03 |
0,21 |
|
|
4 |
5 |
0,00 |
0,00 |
0,00 |
0,10 |
0,23 |
|
|
ASIFT |
2 |
10 |
0,30 |
0,63 |
0,50 |
0,23 |
0,18 |
|
3 |
10 |
0,56 |
0,66 |
0,90 |
0,55 |
0,64 |
|
|
4 |
5 |
0,65 |
0,66 |
1,00 |
0,64 |
0,52 |
Результати для SIFT вийшли нульові і не були внесені в таблицю 4. Зважаючи на якість роботи SURF, на рисунку 13 наведено порівняння якості співставлення в залежності від кількості виділених областей лише для ASIFT.
Рисунок 13 – Порівняння якості співставлення зображень (рисунок 12) з різною кількістю виділених областей
На Рисунках 14 та 15 наведено приклади перетворення зображень із різною якістю.
Рисунок 14 – Приклади перетворення зображень з різною якістю. Зліва на право: 0; 0,53
Рисунок 15 – Приклади перетворення зображень з різною якістю. Зліва на право: 0,63; 0,66
Отже, за результатами досліджень найкраща якість досягається при використанні алгоритму знаходження ключових точок ASIFT та при кількості виділених відповідних областей, що дорівнює 4. При цьому не спостерігається значного погіршення якості навіть для зображень з поворотом відносно зображення із супутника. Недоліком використання алгоритму ASIFT є його швидкість, використовувати його в системах реального часу не є доцільним. Пропонується використовувати ASIFT для співставлення карти з лише певним базовим зображенням з БПЛА, а з інших фото з БПЛА створювати панораму за допомогою SURF.
Розглянемо структуру оптичної навігаційної системи, побудованої на основі запропонованого алгоритму (Рисунок 16).
4 Оптична навігаційна система
За допомогою драйвера відеокамери система отримує базове зображення. Оператор виділяє на зображенні та карті 4 області співставлення. Базове зображення та карта накладаються за допомогою ASIFT. Нові зображення з БПЛА зшиваються між собою (SURF) та на основі перетворення, отриманого з накладання карти та базового зображення співставляються з картою з метою отримання координат. Маючи координати, система може сформувати маршрут руху.
Рисунок 16 - Основні компоненти оптичної навігаційної системи БПЛА
Висновки
В ході роботи було запропоновано структуру оптичної системи навігації БПЛА та алгоритм співставлення зображень який може бути в ній використаний. Запропонована система дозволяє вирішити проблеми навігації на основі пульту чи GPS і забезпечує можливість БПЛА здійснити свою місію як в мирний так і військовий час.
При аналізі запропонованого алгоритму співставлення знімків з БПЛА та супутникових зображень було визначено, що найкраща якість досягається при використанні алгоритму знаходження ключових точок ASIFT для базового зображення та при кількості виділених відповідних областей, що дорівнює чотирьом. При цьому не спостерігається значного погіршення якості навіть для зображень з поворотом відносно зйомки із супутника.
Подальші дослідження плануються щодо автоматизації вибору областей співставлення, модифікації алгоритму для підвищення якості перетворення зображень та застосування комбінацій алгоритмів для підвищення швидкості роботи.
Список літератури
