Методи та засоби представлення та аналізу динамічної обстановки для геоінформаційних комплексів реального часу

Размещено на http://www.allbest.ru/

Національна академія наук України

Інститут кібернетики імені В.М. Глушкова

УДК 004.031.43, 004.93

Автореферат

дисертації на здобуття вченого степеня кандидата технічних наук

Методи та засоби представлення та аналізу динамічної обстановки для геоінформаційних комплексів реального часу

Спеціальність 05.13.06 - автоматизовані системи управління та прогресивні інформаційні технології

Бородін Віктор Анатолійович

Київ 2005

Загальна характеристика роботи

представлення аналіз динамічна обстановка

Сучасні геоінформаційні комплекси реального часу (ГК РЧ) призначені для вирішення задач оперативного пошуку, відображення й аналізу динамічної обстановки в навколоземному просторі. Характерними задачами таких комплексів є, наприклад, безпечне розведення літаків у районі аеропортів, кораблів у портах, керування транспортними потоками у великих містах, зокрема, на автострадах, тренажерах для пілотів літаків та гелікоптерів.

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

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

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

Для вирішення задач, поставлених перед дисертантом, важливе значення мали праці вітчизняних учених Є.О. Башкова, В.П. Боюна, М.І. Васюхіна, Т.К. Вінцюка, В.М. Глушкова, В.П. Деркача, С.С. Забари, В.М. Коваля, А.В. Крижного, Б.М. Маліновського, П.Д. Лепетюка, О.В. Палагіна, К.А. Салищева, В.В. Смолія, В.Є. Ходакова, А.О. Чикрія, М.І. Шлезінгера, Ю.С. Яковлева, а також роботи іноземних фахівців П. Агарвала, В. Гілоя, Дж. Фолі, А. ван Дема, Д. Роджерса, Ф. Мартінеса, І. Матовчика, Х. Самета. Окремо слід зазначити серію праць, які були виконані в Інституті кібернетики ім. В.М. Глушкова по вдосконаленню алгоритмів перетворень зображень, а також досягнення по перетворенню зображень львівської школи під керівництвом проф. В.В. Грицика (В.А. Вальковський, З.Д. Грицків, Б.П. Русин та ін.).

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

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

- алгоритми та методи швидкого представлення й аналізу динамічної обстановки в реальному часі;

- методи перетворення зображень картографічного фону для виконання швидкого й економічного методу переносу та повороту моделей місцевості різного масштабу на екрані ГК РЧ;

- методи побудови баз даних про рухливі об'єкти в ГК РЧ;

- методи аналізу динамічних сцен за допомогою швидкого пошуку рухливих об'єктів для ГК РЧ.

Характерним прикладом аналізу динамічної обстановки є аналіз повітряної обстановки, який характеризується значними швидкостями об'єктів і рядом жорстких вимог на час синтезу та представлення зображень. Представлення повітряної обстановки зручно показувати у вигляді "електронного кіно", яке передбачає 50 кадрів у секунду, тобто 20 мс на один кадр зображення, та всі допоміжні обчислення.

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

До найбільш близьких робіт по вирішенню задач аналізу динамічної обстановки можна віднести праці, які виконувались на факультеті комп'ютерної графіки Стенфордського університету, а також ряд робіт учених Інституту кібернетики ім. В.М. Глушкова НАН України. Ці праці підтверджують наступне:

- не було досить ефективних шляхів програмної реалізації методів пошуку в геометричній області ГК РЧ;

- об'єкти пошуку розглядалися як абстрактні математичні об'єкти, не досить повно використовувалися дані про об'єкти пошуку як частини сцени, що представляється ГК РЧ.

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

Зв'язок роботи з науковими програмами, планами, темами. Робота виконувалася в рамках фундаментальних і пошукових робіт Інституту кібернетики ім. В.М.Глушкова, а також на основі переліку найважливіших НДР у відповідності з основними Програмами Міністерства освіти і науки України в області інструментальних засобів обчислювальної техніки і систем керування в період 1999 - 2003 рр., що дозволило довести основні алгоритмічні та програмні методи до стадії впровадження.

Знайдені рішення (алгоритми і програми) використані в ряді розробок, що виконувалися і виконуються за безпосередньої участі автора, у тому числі:

- НДР “Розробка систем реального часу (віртуальні прилади, мультимедіа)”, шифр роботи ВФ-200.01, № держреєстрації 01970015910 (1999 р.);

- НДР “Інформаційні проблеми зв'язку (компресія, комутація, передача і виміри)”, шифр ІП-200.04, № держреєстрації 01984005916 (2000 р.);

- НДР “Системи реального часу. Цифрова обробка сигналів і зображень, геоінформаційні комплекси. Мережі комп'ютерів, агент-технології пошуку інформації”, шифр ВФ-200.06, № держреєстрації 0101U000076 (2002 р.);

- НДР “Інформаційні проблеми цифрового представлення, передачі, компресії й обробки відеозображень”, шифр ІП-200.05, № держреєстрації 01984005916 (2002 р.);

- НДР “Базовий комплекс засобів конфігурування і керування розподілених геоінформаційних систем оперативної взаємодії”, “ГЕОКАРТА” по договору № 2/615-97 (для Міністерства освіти і науки України). Комплекс “ГЕОКАРТА” містить реалізацію пропонованих алгоритмічних і програмних методів, оригінальний, не має аналогів у вітчизняній та світовій практиці.

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

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

Методи дослідження базуються на системному підході В.М. Глушкова, на об`єктно-орієнтовному підході до побудови програмного забезпечення, а також на базі математичного апарату афінних перетворень і теорії пошуку в геометричній області (Range Searching).

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

Для досягнення означеної мети необхідно розв`язати наступні взаємопов`язані задачі:

- розробити нові методи, що забезпечують швидку обробку даних про рухомі об'єкти та їх відображення в ГК РЧ;

- розробити метод економічного зберігання, а також методи паралельного переносу та повороту картографічної інформації різних масштабів в ГК РЧ;

- удосконалити методи пошуку рухомих об'єктів у заданій геометричній області, що забезпечують необхідну швидкість аналізу динамічної обстановки в реальному часі;

- розробити алгоритмічні основи і структурну організацію програмного забезпечення ГК РЧ для більш адекватного представлення динамічної обстановки в режимі реального часу.

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

- швидкий метод здійснення операцій повороту на базі алгоритму Брезенхема для зображення складного символу, представленого як у векторному, так і в растровому вигляді, заснованому на методі базових символів, що дозволяє відмовитися від відомих синусно-косинусних перетворень матриць, які представляють зображення символу, та, в свою чергу, дозволяє зменшити обсяг необхідних для цього обчислень до 85 %;

- метод збереження, перетворення і відображення картографічного фону на екрані, який передбачає представлення карти у вигляді контурів зв'язних одноколірних областей, що дозволяє заощаджувати ресурси пам'яті при збереженні зображення карти і здійснювати перетворення паралельного переносу в режимі ешелонованого скролінга більше двох разів швидше, а перетворення повороту - більше чотирьох разів швидше відомих аналогічних методів. Спосіб економії обчислювальних засобів при виконанні афінних перетворень векторних зображень за рахунок застосування способу стиску даних, що представляють контур складного символу за допомогою кодування Фрімена, який дозволяє заощаджувати до 50 % ресурсів пам'яті при збереженні зображення і до 75 % часу при виконанні операції зміни масштабу;

- метод динамічного пошуку в ГК РЧ для об'єктів, що швидко змінюють свої положення;

- критерії, які дозволяють визначити, який з методів пошуку найшвидший за заданої кількості об`єктів, кількості змін положень динамічних об`єктів та кількості операцій пошуку;

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

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

- прикладне програмне забезпечення ГК РЧ, що забезпечує синтез зображень об'єктів, які рухаються на картографічному фоні;

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

- пакет прикладних програм для ГК РЧ, що забезпечує швидкий пошук динамічних об'єктів в обраній геометричній області.

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

Отримані результати знайшли практичне застосування в НДР “Базовий комплекс засобів конфігурування і керування розподілених інтерактивних геоінформаційних систем оперативної взаємодії - Геокарта” шифр 06.05/02339, що виконувався на замовлення Міністерства освіти і науки (договір № 2/615-97), НДР "Огляд", яка виконувалась в Національному науково-дослідному центрі оборонних технологій та військової безпеки України, і НДР "Пасіка", що проводилась в Центральному науково-дослідному інституті Збройних Сил України.

Основний зміст дисертації викладено у 7 публікаціях, основні наукові результати дисертаційної роботи доповідалися й обговорювалися: на всеукраїнській конференції "Актуальні питання розвитку інноваційної діяльності" (м. Алушта, 8-12 вересня 2003 р.), на міжнародній конференції "Проблеми інформатики та моделювання - 2003" (ПІМ-2003) (м. Харків, 27 - 29 листопада 2003 р.), на конференції "Університет і регіон" (м. Луганськ, 10-12 грудня 2003 р.), на семінарі Херсонського державного технічного університету. Деякі наукові результати роботи використовувались при розробці за безпосередньої участі автора проекту в четвертому конкурсі „Інтелектуальний потенціал молодих вчених - місту Києву”, який був нагороджений першою премією у напрямку „Нові комп'ютерні засоби та технології інформатизації суспільства” в 2004 році.

Структура й обсяг роботи. Дисертаційна робота обсягом 170 машинописних сторінок складається із вступу, чотирьох розділів, списку використаних джерел з 118 найменувань. Дисертація містить 15 рисунків, 15 таблиць.

Основний зміст роботи

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

У першому розділі дано аналіз стану робіт в області створення програмного забезпечення ГК РЧ, розглянуто окремо задачі синтезу зображень динамічних сцен і задачу аналізу динамічних сцен, їх теоретичне підгрунтя та сучасний стан досліджень у цих галузях. Обгрунтовано актуальність проведених досліджень, показано необхідність удосконалення сучасних програмних методів синтезу та аналізу динамічних сцен в ГК РЧ.

В ГК РЧ система відображення синтезує зображення заданої ділянки поверхні Землі в необхідному масштабі і зображення інших об'єктів - будинків, мостів, доріг, машин, кораблів, літаків.

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

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

Аналіз динамічних сцен, які відображаються в ГК РЧ, наприклад, в задачах розведення літаків в аеропортах, спостереження за суднами в портах, зводиться до задачі пошуку в геометричній області, що формулюється так:

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

У роботі розглянуті сучасні підходи до розв`язання цієї задачі та вказано, чому ця задача є базовою для задач аналізу динамічної обстановки.

Внаслідок огляду сучасних методів відображення та аналізу динамічних сцен сформульовані недоліки та задачі, розв'язання яких необхідно для усунення цих недоліків.

У другому розділі розглядається задача відображення динамічних сцен.

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

Перенос кожної точки зображення до сусідньої точки екрану назвемо кроком.

Класи зображень на відеотерміналі комплексу умовно поділяються на дві категорії: статичні (зміна положень не більше, ніж один крок за один кадр, тобто не більше 50 кроків/с) і динамічні. Динамічні об'єкти представлені у вигляді невеликих порівняно з екраном зображень. Статичні об'єкти можуть мати розміри рівні чи більші за розмір екрану. При цьому динамічні об'єкти відображаються на фоні статичних, тому для відтворювання обстановки і виконання її аналізу, пропонується спочатку здійснювати відображення статичних об'єктів, а потім - динамічних.

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

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

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

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

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

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

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

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

Таким чином, виконується , операцій присвоєння. Якщо здійснювати всі операції присвоєння при простому виводі зображення карти, то треба зробити присвоєнь (тут - кількість точок екрану). Отже, при одержуємо меншу кількість необхідних операцій, яка в середньому при переносі на один крок становить 50%.

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

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

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

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

Після здійснення повороту на кут слід лише перенести точку О в точку повороту по запропонованому методу скролінга або паралельного переносу.

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

Запропонований спосіб зберігання карт дозволяє швидко виконувати викладені перетворення та перетворення зміни масштабу.

У третьому розділі розглядаються задачі аналізу динамічних сцен.

Як було зазначено в першому розділі, задача пошуку призначена для аналізу динамічних сцен в програмній частині ГК РЧ. У системі цю функцію комплексу зручно реалізувати таким чином.

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

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

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

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

1) дано прямокутник зі сторонами, паралельними до осей координат, і моменти часу . Потрібно повідомити про всі точки з множини , що лежать у прямокутнику в момент часу , тобто ;

2) дано прямокутник зі сторонами, паралельними до осей координат, і моменти часу і . Потрібно повідомити про всі точки з множини , що лежать у прямокутнику в проміжок часу , тобто .

Для розв'язання вказаних задач використовується модель зовнішньої пам'яті, де передбачається, що кожна операція роботи системи припускає операцію вводу/виводу (I/O operation) масиву (блоку) даних довжини . Ефективність алгоритму полягає в кількості використовуваного простору диска (що вимірюється в кількості блоків) та кількості операцій вводу/виводу. Така модель відповідає наступній роботі системи: на твердому диску записана база даних про об'єкти, а операція полягає в тому, що комп'ютер у деякий момент часу може обробити лише масив довжиною .

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

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

Шукана структура даних будується наступним чином.

Спочатку будується первинне бінарне дерево розбиття для множини . Потім у визначених вузлах дерева розбиття будується вторинне дерево розбиття для точок для кожного вузла, чия глибина , де - константа з інтервалу . Оскільки розмір кожного вторинного дерева буде блоків, загальний розмір дерева виходить блоків (тут -асимптотична поведінка). Їх можна побудувати за операцій, а зміну здійснити за операцій вводу/виводу.

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

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

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

Представлений порівняльний аналіз відомих та запропонованих методів пошуку в геометричній області для аналізу обстановки в ГК РЧ. На базі цього аналізу стверджується, що при

пошук за допомогою дерев Бентлі буде більш швидким, ніж інші методи, а динамічний пошук швидше інших методів при

а при

раціональніше користуватися простим методом перебору, де - кількість змін (перебудов) за час праці комплексу в базі даних динамічного пошуку ГК РЧ; - кількість операцій пошуку, яке потрібно здійснити за той же час.

У четвертому розділі розглядається задача організації програмного забезпечення (ПЗ) для ГК РЧ з метою підвищення швидкості його роботи при виконанні синтезу та аналізу динамічної обстановки.

Запропоновано розділити процедури підготовки відображення картографічного фону і зображень динамічних об'єктів із пріоритетом виводу останніх для подальшої спільної візуалізації. Такий спосіб розділення забезпечує збільшення швидкості підготовки і представлення динамічних сцен у ГК РЧ. Крім того, за такого поділу можна виділити окремо базу даних про рухомі об'єкти, з якою можна взаємодіяти при аналізі динамічних сцен (рис. 1).

Размещено на http://www.allbest.ru/

Рис. 1. Структура ПЗ для ГК РЧ з урахуванням поділу статичних і динамічних зображень

Запропонована структура ПЗ і знайдені методи пошуку в геометричній області дозволяють забезпечити швидкий пошук при аналізі динамічної сцени, тобто визначити кількість об'єктів даного типу в обраній ділянці простору, що представляється динамічною сценою. При цьому пропонується база даних, у структуру якої включений контролер, який забезпечує перебудову структури цієї БД при надходженні або видаленні даних, а також при зміні параметрів об'єктів, що рухаються (рис. 2).

Размещено на http://www.allbest.ru/

Рис. 2. Структура ПЗ для взаємодії з базою даних ГК РЧ

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

Дисплейний файл створюється для зображення фону. При цьому картографічні дані, що будуть відображатися на екран, представлені в запропонованому економічному методі збереження. Далі всі рухи фону (карти) будуть здійснюватися відповідними операціями ПЕРЕНОС, ПОВОРОТ і МАСШТАБ. Алгоритми виконання цих процедур описані в другому розділі.

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

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

Висновки

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

Отримані результати полягають у наступному:

1. Знайдено швидкий метод здійснення операцій повороту на базі алгоритму Брезенхема для зображення складного символу, представленого як у векторному, так і в растровому вигляді, заснованому на методі базових символів. Це дозволяє відмовитися від відомих синусно-косинусних перетворень матриць, які представляють зображення символу, зменшити обсяг необхідних для цього обчислень до 85 %.

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

Запропоновано спосіб економії обчислювальних засобів при виконанні афінних перетворень векторних зображень за рахунок застосування способу стиску даних, що представляють контур складного символу за допомогою кодування Фрімена, який дозволяє заощаджувати до 50 % ресурсів пам'яті при збереженні зображення і до 75 % часу - при виконанні операції зміни масштабу.

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

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

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

Запропоновані методи та засоби представлення й аналізу динамічної обстановки впроваджені в Національному науково-дослідному центрі оборонних технологій і військової безпеки України в рамках НДР "Огляд" і НДР "Пасіка", що проводилась у Центральному науково-дослідному інституті Збройних Сил України.

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

Основні положення дисертації опубліковані в таких працях

1. Бородин В.А. Быстрый метод поворота растрового изображения сложного символа, выводимого на экран комплексов реального времени // Математичні машини і системи. - 2004. - №2. - С.54-60.

2. Бородин В.А. Метод повышения скорости обработки данных для отображения динамики поворота сложных растровых изображений в геоинформационных комплексах реального времени // УСиМ. - 2003. - №6. - С. 69-72.

3. Бородин В.А., Васюхин М.И., Соболев О.Н. Методы синтеза картографического фона, быстрого изменения масштаба карты и эшелонированного скроллинга // Наукові праці Донецького національного технічного університету. Сер. „Інформатика, кібернетика та обчислювальна техніка".- Донецьк: ДонНТУ, 2003 - Вип. 70. - С.188-200.

4. Васюхин М.И., Бородин В.А. Методы реализации алгоритма поиска объектов в прямоугольной области при анализе воздушной обстановки // Математичні машини і системи. - 2001. - №1-2. - С.100-105.

5. Бородин В.А. Сравнительная эффективность методов поиска в геометрической области для геоинформационных комплексов реального времени // Автоматика, автоматизация, электротехнические комплексы и системы. - 2004. - №2 (14). - С.109-115.

6. Васюхін М.І., Головко Б.Б., Бородін В.А. Оцінка ефективності застосування принципу квадратомічного дерева при формуванні БД ГІС для растрових зображень // Бюлетень геодезії і картографії України. - 2001. - №1. - С.37-39.

7. Бородін В.А. Структура програмного забезпечення та методи аналізу динамічної обстановки в геоінформаційних комплексах реального часу // Вестн. НТУ „ХПИ”. - Харьков: НТУ „ХПИ”, 2004. - № 45. - С. 166-173.

Анотація

Бородін В.А. Методи та засоби представлення та аналізу динамічної обстановки для геоінформаційних комплексів реального часу. - Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.06 - автоматизовані системи управління та прогресивні інформаційні технології. - Інститут кібернетики ім. В.М. Глушкова НАН України, Київ, 2005.

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

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

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

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

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

Аннотация

Бородин В.А. Методы и средства представления и анализа динамической обстановки для геоинформационных комплексов реального времени. - Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.06 - автоматизированные системы управления и прогрессивные информационные технологии. - Институт кибернетики им. В.М. Глушкова НАН Украины, Киев, 2005.

Диссертационная работа посвящена развитию методов и средств организации процессов представления и анализа быстроменяющейся обстановки в геоинформационных комплексах реального времени, предназначенных для решения задач оперативного поиска, отображения и анализа подвижных объектов в околоземном пространстве. Такие геоинформационные комплексы реального времени должны отображать географические данные в виде картографического фона и динамические объекты в виде сложных цветных символов, двигающихся на этом фоне, обеспечив при этом плавность отображения движений как карты-фона, так и символов. Следующий шаг интеллектуализации этих комплексов - анализ динамической обстановки с помощью автоматического решения задач поиска объектов в заданной на картографическом фоне области.

Рассмотрены существующие прототипы геоинформационных комплексов и пути решения вышеуказанных задач. Указаны недостатки как существующих программных реализаций, так и математических моделей отображений картографического фона и подвижных символов, а также рассмотрены существующие методы поиска в таких комплексах.

Для решения поставленных задач предложено разделить процедуры отображения карты-фона и подвижных символов. С целью уменьшения используемых машинных ресурсов предложен экономичный метод хранения картографических данных, при котором можно уменьшить количество машинных ресурсов, используемых при сохранении картографического фона и аффинных преобразованиях при отображении динамической сцены. Предлагается метод эшелонированного скроллинга, который позволяет экономить время при незначительных перемещениях картографического фона.

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

Рассмотрены методы поиска в геометрической области и их использование при решении задач анализа динамической обстановки. Для использования в геоинформационных комплексах реального времени предложены метод динамического поиска и метод поиска на экране видеотерминала. Проведено сравнение скоростей выполнения современных методов поиска с предложенными методами при различных значениях количества объектов поиска, изменений положений объектов и частоты запросов поиска оператором комплекса. Выведен критерий, который позволяет определить наиболее быстрый при данном соотношении указанных параметров метод поиска.

На базе указанных методов быстрых преобразований изображений картографических данных и символов на фоне карты, а также рассмотренных методов анализа динамических сцен предложена структура программного обеспечения геоинформационных комплексов реального времени, основанная на объектно-ориентированном подходе, которая обеспечивает отображение и анализ динамической обстановки в режиме реального времени.

Ключевые слова: динамический объект, алгоритмы визуализации, быстрый метод поворота, программные средства геоинформационных комплексов, аффинные преобразования, поиск в геометрической области, анализ динамической обстановки.

Abstract

Borodin V.A. Methods and means of representation and analysis of dynamic situation for real time geoinformational complexes. - Manuscript.

Thesis for Ph.D. science degree by speciality 05.13.06 - automated control systems and progressive information technologies. - V.M.Glushkov Institute of Cybernetics of National academy of sciences of Ukraine, Kiev, 2005.

The main goal of the thesis is dedicated to the development of the methods and means for organization of rapidly changing situation representation and analysis processes in real time geoinformational complexes with the purpose of friend visual perception of situation for an operator of a complex.

The prototypes of geoinformational complexes and existing paths of the solution of above-stated problems are reviewed. For the solution of the given problems offered to separate procedures of visualization of a background and mobile symbols images. With the purpose of reduction used engine resources the costeffective method for storage of cartographic data, the method of range scrolling, the methods of the fast turn using Bresenhame algorithm are purposed.

The range search methods in geometrical area and their usage in the problem of dynamic situation analysis are reviewed. The presented methods of search and classical methods are compared for different values of quantity of searching objects, quantity of changes in positions of objects and quantity of search queries. Such analysis afford to depict which method is fastest for a given ratio of the indicated parameters.

On the base of the offered methods the software structure, based on the object-oriented approach, that provides visualization and analysis of dynamic situation in real-time mode for real time geoinformational complexes, is proposed.

Key words: dynamic object, algorithms of the visualization, fast method of a image turn, applied software for geoinformational complexes, affine transformation, geometric range search, analysis of dynamic situation.

Размещено на Allbest.ru

...