Context. The relevance of the article is driven by the need for further development of object recognition (classification) algorithms, reducing computational complexity, and increasing the functional capabilities of such algorithms. The graph invariant proposed in the article can be applied in machine vision systems for recognizing physical objects, which is essential during rescue and monitoring operations in crisis areas of various origins, as well as in delivering firepower to the enemy using swarms of unmanned aerial vehicles.Objective is to develop a graph invariant with low computational complexity that enables the classification of physical objects with a certain level of confidence in the presence of external interference.Method. The physical object to be recognized (identified) is modeled by a connected undirected weighted graph. To identify theconstant characteristics of different model graphs, the idea of selecting the minimum and maximum weighted spanning trees in the structure of these graphs is applied. For this purpose, the classical and modified Boruvka-Sollin’s method are used (modified – for constructing the maximum weighted spanning tree). Such a stratification of the structure of the initial graph into two layers provides a larger information base during image analysis regarding the belonging of a certain implementation to a certain class of objects. Next, for each of the resulting spanning trees, two numerical characteristics are calculated: the weight of the spanning tree and the Randić index. The first characteristic contains indirect information about the linear dimensions of the object, while the second conveys its structural features. These characteristics are independent of vertex labeling and the graphical representation of the graph, which is a necessary condition for graph isomorphism verification. From these four obtained characteristics, an invariant is formed, which describes the corresponding physical object present in a single scene. To fully describe one class or subclass of objects in four scenes (top view; front and rear hemispherical views; side view), the pattern recognition system must have four corresponding invariants.Results. 1) A two-layer invariant of a weighted undirected graph has been developed, enabling the recognition of physical objects with a certain level of confidence; 2) A method for recognizing physical objects has been formalized in graph theory terms, based on hashing the object structure using the weights of the minimum and maximum spanning trees of the model graph, as well as the Randić index of these trees; 3) The two-layer invariant of the weighted undirected graph has been verified on test tasks for graph isomorphism checking.Conclusions. The conducted theoretical studies and a series of experiments confirm the feasibility of using the proposed graph invariant for real-time pattern recognition and classification tasks. The estimates obtained using the developed method are probabilistic, allowing the system operator to flexibly approach the classification of physical objects within the machine vision system’s field of view, depending on the technological process requirements or the operational situation in the system’s deployment area.

Актуальність. Актуальність статті обумовлюється потребою у подальшому розвитку алгоритмів розпізнавання (класифікації) об’єктів, у зменшенні обчислювальної складності і збільшенні функціональних можливостей таких алгоритмів. Запропонований у статті інваріант графа може бути застосований у системах машинного зору для розпізнавання фізичних об’єктів, що є важливим у ході виконання рятувальних, моніторингових завдань у кризових районах різного характеру походження, а також у ході нанесення противнику вогневого ураження із застосуванням рою безпілотних апаратів.Мета роботи полягає в розробленні інваріанту графа з низькою обчислювальною складністю, який дозволятиме з певним рівнем довірчої ймовірності класифікувати фізичні об’єкти в умовах зовнішніх завад.Метод. Фізичний об’єкт, що підлягає розпізнаванню (ідентифікації) моделюється зв’язним неорієнтованим зваженим графом. Для виявлення сталих характеристик різних модельних графів застосовано ідею виділення в структурі цих графів мінімального і максимального за вагою каркасних дерев. З цією метою застосовується класичний і модифікований методи Борувки-Солліна (модифікований – для побудови максимального зваженого каркасного дерева). Таке розшарування структури початкового графа на два шари надає більшої інформаційної бази у ході аналізу зображення щодо приналежності певної реалізації до деякого класу об’єктів. Далі, для кожного з отриманих таким чином каркасних дерев, відшукуються значення двох числових характеристик: ваги каркасного дерева та індексу Рандіча. Перша характеристика несе в собі опосередковану інформацію про лінійні розміри об’єкту, а друга – про його структурні особливості. Ці характеристики не залежать від способу позначення вершин та графічного зображення графа, що є необхідною умовою для перевірки графів на ізоморфізм .З отриманих таким чином чотирьох характеристик складається інваріант, яким описується відповідний фізичний об’єкт, що перебуває в одній сцені. Для повного опису одного класу або підкласу об’єктів в чотирьох сценах (вид зверху; вид передньої та задньої полусфер; вид збоку) система розпізнавання образів повинна мати чотири відповідні інваріанти.Результати. 1) Розроблено двошаровий інваріант зваженого неорієнтованого графу, який дозволяє з певним рівнем довірчої ймовірності розпізнавати фізичні об’єкти; 2) В термінах теорії графів формалізовано метод розпізнавання фізичних об’єктів, що заснований на хешуванні структури об’єкту вагою мінімального і максимального каркасних дерев модельного графу, а також індексом Рандіча цих дерев; 3) Виконано верифікацію двошарового інваріанту зваженого неорієнтованого графу на тестових задачах з перевірки графів на ізоморфізм.Висновки. Проведені теоретичні дослідження та низка проведених експериментів підтверджують можливість використання пропонованого інваріанту графів в задачах розпізнавання та класифікації образів в масштабі реального часу. Оцінки, що виробляються із використанням розробленого методу, носять ймовірнісний характер, що дозволяє особі, яка налаштовує систему машинного зору, гнучко підходити до класифікації фізичних об’єктів в полі зору такої системи, виходячи з вимог до технологічного процесу або з умов оперативної обстановки в районі застосування системи.

Актуальність. Актуальність статті обумовлюється потребою у подальшому розвитку алгоритмів розпізнавання (класифікації) об’єктів, у зменшенні обчислювальної складності і збільшенні функціональних можливостей таких алгоритмів. Запропонований у статті інваріант графа може бути застосований у системах машинного зору для розпізнавання фізичних об’єктів, що є важливим у ході виконання рятувальних, моніторингових завдань у кризових районах різного характеру походження, а також у ході нанесення противнику вогневого ураження із застосуванням рою безпілотних апаратів.Мета роботи полягає в розробленні інваріанту графа з низькою обчислювальною складністю, який дозволятиме з певним рівнем довірчої ймовірності класифікувати фізичні об’єкти в умовах зовнішніх завад.Метод. Фізичний об’єкт, що підлягає розпізнаванню (ідентифікації) моделюється зв’язним неорієнтованим зваженим графом. Для виявлення сталих характеристик різних модельних графів застосовано ідею виділення в структурі цих графів мінімального і максимального за вагою каркасних дерев. З цією метою застосовується класичний і модифікований методи Борувки-Солліна (модифікований – для побудови максимального зваженого каркасного дерева). Таке розшарування структури початкового графа на два шари надає більшої інформаційної бази у ході аналізу зображення щодо приналежності певної реалізації до деякого класу об’єктів. Далі, для кожного з отриманих таким чином каркасних дерев, відшукуються значення двох числових характеристик: ваги каркасного дерева та індексу Рандіча. Перша характеристика несе в собі опосередковану інформацію про лінійні розміри об’єкту, а друга – про його структурні особливості. Ці характеристики не залежать від способу позначення вершин та графічного зображення графа, що є необхідною умовою для перевірки графів на ізоморфізм.З отриманих таким чином чотирьох характеристик складається інваріант, яким описується відповідний фізичний об’єкт, що перебуває в одній сцені. Для повного опису одного класу або підкласу об’єктів в чотирьох сценах (вид зверху; вид передньої та задньої полусфер; вид збоку) система розпізнавання образів повинна мати чотири відповідні інваріанти.Результати. 1) Розроблено двошаровий інваріант зваженого неорієнтованого графу, який дозволяє з певним рівнем довірчої ймовірності розпізнавати фізичні об’єкти; 2) В термінах теорії графів формалізовано метод розпізнавання фізичних об’єктів, що заснований на хешуванні структури об’єкту вагою мінімального і максимального каркасних дерев модельного графу, а також індексом Рандіча цих дерев; 3) Виконано верифікацію двошарового інваріанту зваженого неорієнтованого графу на тестових задачах з перевірки графів на ізоморфізм.Висновки. Проведені теоретичні дослідження та низка проведених експериментів підтверджують можливість використання пропонованого інваріанту графів в задачах розпізнавання та класифікації образів в масштабі реального часу. Оцінки, що виробляються із використанням розробленого методу, носять ймовірнісний характер, що дозволяє особі, яка налаштовує систему машинного зору, гнучко підходити до класифікації фізичних об’єктів в полі зору такої системи, виходячи з вимог до технологічного процесу або з умов оперативної обстановки в районі застосування системи.