TWO-LAYER GRAPH INVARIANT FOR PATTERN RECOGNITION

Abstract

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.