Задача класифікації об’єктів для систем з обмеженими обчислювальними ресурсами

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

Національний авіаційний університет

Національний технічний університет України «КПІ ім. І. Сікорського»

Задача класифікації об'єктів для систем з обмеженими обчислювальними ресурсами

Жуков И.А., д.т.н., Нечурин Н.К., д.т.н., Кондратова Л.П., к.т.н., Печурин С.Н., к.т.н.

Анотація

Жуков І.А.,

Печурин М.К.,

Кондратова Л.П.,

Печурин С.М.

ЗАДАЧА КЛАСИФІКАЦІЇ ОБ'ЄКТІВ ДЛЯ СИСТЕМ З ОБМЕЖЕНИМИ ОБЧИСЛЮВАЛЬНИМИ РЕСУРСАМИ

Визначено особливості задачі класифікації образів для систем з обмеженими обчислювальними ресурсами. які декомпозовано згідно Еталонної моделі взаємодії відкритих систем. Серед систем. що реалізують функції відеоспостереження. особливе місце займають останнім часом розвинуті системи і мережі. що базуються на рухомих. зокрема - літальних. апаратах. особливістю яких. зокрема - БПЛА. є обмежений обчислювальний ресурс. що доступний для реалізації функцій збору. обробки і передачі (відео- і фото-) інформації. Однією з важливих задач. які розв 'язуються при реалізації функції (відео)спостереження в системах та мережах БПЛА. є задача класифікації образів. тобто віднесення спостерігаємого об 'єкта до одного з заданого числа груп. Запропоновано підхід. що дозволяє підвищити якість. за показником витрати / ефективність. систем класифікації об'єктів. що володіють обмеженими обчислювальними ресурсами. наприклад - систем розпізнавання і класифікації. розміщених на літальних апаратах. Введено міру подібності. яку характеризує вектор розмірністю. що відповідає параметрам інтелектуальних сенсорів. за допомогою яких знімається інформація про об 'єкт. Пропонується спрощення процедури класифікації. яке засноване на виконанні етапів згортання векторного критерію подібності у скаляр при формуванні матриці близькості; представлення об 'єктів класифікації в якості вузлів комп'ютерної мережі з централізованою топологією з подальшим застосуванням матриці близькості в алгоритмах. що здавна застосовуються для топологічного проектування комп'ютерних мереж. Спро- щена процедура класифікації може виявитися корисною при класифікації об'єктів з обмеженої множини, - такої, що утворюють пасажири та персонал системи внутрішніх авіаперевезень, метрополітену тощо. Бібліогр.: 8 назв.

Abstract

Zhukov I.A.,

Pechurin N.K.,

Kondratova L.P.,

Pechurin S.N.

THE TASK OF CLASSIFYING OBJECTS FOR SYSTEMS WITH LIMITED COMPUTING RESOURCES

The features of the task of classifying images for systems with limited computing resources that are decomposed according to the reference model for the interaction of open systems are determined. Among the systems that implement the functions of video surveillance, a recent development system and network based on mobile, in particular, aircraft, occupy a special place, the feature of which, in particular, UAVs, is the limited computing resource available for implementing the functions of collection, processing and transmission ( video, photo) information. One of the important tasks that are solved when implementing the surveillance function (video) in UAV systems and networks is the classification of images, that is, assigning the observed object to one of a given number of groups. An approach is proposed to improve the quality, in terms of cost / effectiveness, of classification systems with limited computing resources, for example, recognition and classification systems deployed on aircraft.

A similarity measure has been introduced, which is characterized by a vector with a dimension corresponding to the parameters of intelligent sensors with which information about the object is taken. A simplification of the classification procedure is proposed, based on the steps of folding the vector similarity criterion into a scalar when forming the proximity matrix; representing classification objects as nodes of a computer network with a centralized topology, followed by applying the proximity matrix in algorithms that have long been used for topological design of computer networks. A simplified classification procedure may be useful in classifying objects of a limited set, such as that formed by passengers andpersonnel of domestic air transportation system, the metro, etc. Refs:8 titles.

Вступ

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

Особливе місце тут займають дослідження, що проводяться в Національному авіаційному університеті, Національному аерокосмічному університеті імені М.Є. Жуковського «Харківський авіаційний інститут» [1-3], Національному технічному університеті «Київський політехнічний інститут імені Ігоря. Сікорського» [4]), Інституті прикладного системного аналізу. В останньому, наприклад, настійливо і плідно ведеться пошук нових принципів та підходів до оцінювання гарантованого функціонування складних (універсальних) систем з пріоритетними напрямками безпеки на основі методології системного аналізу з урахуванням життєвого циклу синтезованого продукту [5].

Проблемі побудови теоретичних основ і розробки інструментарію, який може бути застосований для розв'язання задачі класифікації образів для систем з обмеженими обчислювальними ресурсами, такими, як системи відеоспостереження, що встановлені на малих літальних апаратах, наприклад, БПЛА, присвячено роботи шкіл Згуровського Михайла Захаровича, Кулакова Юрія Олексійовича (архітектура комп'ютерів), Додонова Олександра Геор- гієвича, Ланде Дмитро Володимировича (методы детерминированного хаоса в информационных потоках, исследование сложных сетей), Тарасенко Володимира Петровича (архітектури спецкомп'юте- рів), Харченко Вячеслава Сергійовича (кі- бербезпека індустріальних комп'ютерних мереж і систем), Мельника Анатолія Олексійовича (інтегровані мережами інтелектуальні засоби взаємодії з фізичним світом, інтернет речей), Луцького Георгія Михайловича (конвейєрні обчислювальні системи), Воротнікова Володимира Воло- дмировича (фрактали для синтезу архітектур мобільних мереж), а також Watts D. J., Strogatz S. H., Albert R, Barabвsi A.-L., Mendes J. F. F., C. J. Colburn, K. Sekine, A. E. Smith етс.

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

Особливості задачі класифікації образів для систем з обмеженими обчислювальними ресурсами

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

Множина об'єктів класифікації є обмеженою і скінченою.

Оболонка області належності існує, може бути розпізнаваною, і лише в окремому випадку представлена опуклим багатогранником.

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

- Обчислювальні ресурси (засоби) декомпозовано відповідно Еталонної моделі взаємодії відкритих систем.

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

Необхідно виявити ступінь належності кожного з n об'єктів класифікації до k класів, причому обчислювальні ресурси, доступні для розв'язання даної задачі, є обмеженими. На множині А об'єктів класифікації введено бінарне відношення «подібний» (R - «об'єкт і схожий на об'єкт j». Мірою подібності служить вектор, розмірність якого відповідає параметрам інтелектуальних сенсорів, за допомогою яких знімається інформація про об'єкт. Для фото- відео- систем в якості вектора розбіжності може бути різниця , де - вектори, що представляють об'єкти класифікації і та j відповідно; зокрема, в якості об'єкту j може бути представник (зразок) класу j. Слід сказати, що розмірність може бути надто великою для застосування в умовах БПЛА, де обчислювальні можливості є вкрай обмеженими навіть при використанні систем стиснення (типу JPEG, GIF тощо).

Розв'язання задачі класифікації образів для систем з обмеженими обчислювальними ресурсами

У свій час Михайло Васильович Ломоносов у своєму листі Леонарду Пауле- вичу Ейлеру писав: «...все перемены, в натуре случающиеся, такого суть состояния, что сколько чего у одного тела отнимется, столько присовокупится к другому, так ежели где убудет несколько материи, то умножится в другом месте...». Стосовно нашої задачі класифікації образів для систем з обмеженими обчислювальними ресурсами, ця сентенція може бути викладена так: чим більш ресурсоємний (інформаційні, обчислювальні, телекомунікаційні ресурси) метод, спосіб, алгоритм, програма класифікації використовуються для «потреб» конкретного об'єкта (суб'єкт спостереження з БПЛА, пасажир авіатран- спортної системи), тим менше ресурсу залишається для успішної класифікації інших суб'єктів (пасажирів авіаційного транспорту). Це змушує вибирати компроміс між точністю класифікації і обсягом необхідних для класифікації обмежених обчислювальних ресурсів, до яких належить, звичайно, і ресурс часу.

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

Формування матриці, кожний елемент якої суто вектор, що представляє ступінь подібності елемента (об'єкта класифікації) і елементу j.

Запуск процедури класифікації, наприклад, подібної запропонованої в роботі [6]. Тут слід відзначити, що процедури класифікації, засновані на використанні моделей нейронних мереж, достатньо ефективні для систем, які не мають обмежень щодо обчислювальних ресурсів.

Пропонується спрощення процедури класифікації, яке засноване на виконанні двох основних етапів:

а) згортання векторного критерію подібності у скаляр , наприклад - за процедурою, описаною Микитою Миколайовичем Мойсеєвим в роботі [7], подібно тому, як це відбувається при оцінці близькості вузлів (розрахунку відстані між вузлами) комп'ютерної мережі у Routing Information Protocol або Open Shortest Path First протоколі. В результаті маємо матрицю С;

б) представлення n об'єктів класифікації в якості вузлів (комп'ютерної) мережі з централізованою (k кореневих вузлів) топологією з подальшим застосуванням С в забутих (з причини появи більш точних способів класифікації, наприклад, на базі прямонаправлених нейронних мереж [6], але набагато більш марнотратними по відношенню до обчислювальних ресурсів) алгоритмах типу побудови Constrained Minimal Spanning Tree з подальшим послідовним впорядкуванням включених до мінімального дерева відстаней. У випадку застосування, наприклад, класичного алгоритму Ісау-Вільямса [8], який побудовано на методі покоординатного спуску, виникає небезпека появи додаткової похибки класифікації в силу не- опуклості оболонки області допустимих рішень. Зменшити ймовірність попадання в локальний оптимум пропонується шляхом включення етапу випадкового пошуку можливого напрямку або, при наявності відповідного обчислювального ресурсу, - застосуванням методу Балаша для задачі булевого програмування.

Таким чином, для розв'язання задачі класифікації спостерігаємих з БПЛА об'єктів пропонується використовувати підхід, запропонований у роботі [6], посилений процедурою попередньої класифікації, на базі алгоритмів, що здавна застосовуються для топологічного проектування комп'ютерних мереж, де під відстанню між вузлами мережі тепер розуміємо вектор (потім - скаляр) близькості (подібності) образу конкретного класу. Відповідна модель суто модель задачі цілочи- сельного програмування з лінійною цільовою функцією і нелінійними обмеженнями з булевими змінними.

Висновки

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

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

Список літератури

1. Печурин Н.К., Кондратова Л.П., Печурин С.Н. Применение инструментария формальных грамматик для переклассификации функций эталонной модели взаимодействия открытых систем в беспроводной компьютерной сети // Проблеми інформатизації та управління: зб. наук. праць.- 2012. - Вип.1 (37). - С.89-94.

2. Zhukov I.A. Implementation of integral telecommunication environment for harmonized air traffic control with scalable flight display systems // Aviation. - 2010. - №14(4). - P.117-122.

3. Квасніков В.П.. Дзюбаненко А.В. Методи автоматичного захоплення контурів обличчя особи на цифровому зображенні // Авиационно-космическая техника и технология. - Харків. - 2009. - №8 (65). - С.200-205.

4. Згуровский М. З.. Панкратова Н.Д. Системный анализ: проблемы, методология, приложения. - [2-е изд.]. - Киев: Изд- во Наук.думка - 2011. - 743 с.

5. Pankratova N.D., Kondratova L.P. System evaluation of engineering objects'operating taking into account the margin of permissible risk. Eastern-European Journal of Enterprise Technologies.2016. N3.P.13-19.

6. Печурин Н.К.. Кондратова Л.П.. Печурин С.Н. Подход к кластерному анализу функций эталонной модели взаимодействия открытых систем с применением инструментария прямонаправленных искусственных нейронных сетей // Проблеми інформатизації та управління: зб. наук. праць.- 2012. - Вип. з(з9). - С.122-131.

7. Моисеев Н.Н. Математические задачи системного анализа. - М.: Наука, 1981. - 488 с.

8. Зайченко Е.Ю.. Зайченко Ю.П.. Ашраф Абдель Хилал Карим Абу-Аин. Структурный синтез компьютерных сетей с технологией MPLS // Системні дослідження та інформаційні технології. - 2006. - № 4. - С.65-70.

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