RU2730179C1 - Associative pattern recognition device - Google Patents

Abstract

FIELD: physics.SUBSTANCE: invention relates to automatics and computer engineering and can be used in systems for automatic recognition of images with a complex structure: images of objects, models of situations and other data presented in the form of attributive graphs or semantic networks - sets of interconnected structural elements specified by feature sets (vectors). Associative recognition device has a data input device, a control unit, an output device and a matrix of storage elements connected by a data bus and instructions with a control unit. Device additionally contains a matrix of transmitting elements connected by a command bus to a matrix of storage elements, and each transmitting element is connected by buses of commands to the nearest neighbouring transmitting elements.EFFECT: technical result of present invention is high reliability of recognizing images with complex structure such that for each structural element of image requires its own set of characteristic values - its own storage element.3 cl, 13 dwg, 2 tbl

Description

The invention relates to automation and computer technology and can be used in systems for automatic recognition of images with a complex structure: images of objects, models of situations and other data presented in the form of attributive graphs or semantic networks - sets of interconnected structural elements specified by sets (vectors) signs.

A device for pattern recognition is known, which contains a group of multipliers by weight coefficients, the inputs of which are the inputs of the device, a parallel adder, the inputs of which are connected to the outputs of the multipliers by the weight coefficients, and an activation function calculation unit, the input of which is connected to the output of a parallel adder, and the output is the output of the device [Redko V.G. Evolution, Neural Networks, Intelligence: Models and Concepts of Evolutionary Cybernetics. M .: KomKniga, 2006, p. Is. 5.1].

The disadvantage of this device is the unsatisfactory reliability of pattern recognition with a complex structure. the input data is an N-dimensional vector of features of a holistic image without taking into account the connections between its structural elements.

It is also known an associative recognition device containing a first parallel adder and a first activation function calculation unit, the input of which is connected to the output of the first parallel adder, and the output is the first output of the associative recognition device, P-1 parallel adders from the second to the P-th, P- 1 blocks for calculating the activation function from the second to the P-th, the inputs of each of which are connected to the outputs of the same-name parallel adders, and the outputs are the outputs of the same name of the associative recognition device, as well as P groups from the first to the P-th blocks for forming the values of membership functions, the outputs of each of which are connected to the inputs of the same name parallel adders, while each of the P groups of blocks for forming the values of membership functions contains K blocks for forming the values of membership functions from the first to the Kth, the inputs of each of which are connected to the inputs of the same blocks of values of the membership functions of each of the other These groups of P groups of blocks for forming the values of membership functions and are the inputs of the associative recognition device (RU 2342702 C2, IPC G06K 9/62, 27/06/2008).

The disadvantage of this device is also the unsatisfactory reliability of recognition of patterns with a complex structure, since it is focused on the representation of images as holistic, and does not take into account the relationship between its structural elements.

It is also known an associative recognition device containing P blocks for calculating the activation function and P groups of blocks for generating values of membership functions, while each of the P groups of blocks for generating values of membership functions contains K blocks for generating values of membership functions, the inputs of each of which are connected to the inputs of the same blocks of values membership functions of each of the other groups of P groups of blocks for forming the values of membership functions and are the inputs of an associative recognition device, characterized in that P groups of blocks of multipliers by weight coefficients are introduced, each of which contains K blocks of multipliers by weight coefficients, the inputs of each of which are connected with the outputs of the corresponding blocks for forming the values of the membership function from P groups of blocks for forming the membership function, and the outputs are connected to the corresponding inputs of the P blocks for extracting the maximum signal, and the outputs of each of the P blocks are divisions of the maximum signal are connected to the input of the corresponding block for calculating the activation function from P blocks for calculating the activation function (RU 2504837 C1, IPC G06K 9/62, 20/01/2014).

The disadvantage of this device is also the unsatisfactory reliability of pattern recognition with a complex structure, since it is focused on the representation of patterns in the form of N-dimensional feature vectors without taking into account the relationships between its structural elements.

Known associative recognition devices contain, as the main unit, a matrix of storage elements, where each element stores its own set (vector) of feature values that characterize a certain image. In cases where it is required to recognize images with a complex structure, a multilayer organization like artificial neural networks is used, where all elements of each subsequent layer are connected with all elements of the previous layer. The approach implemented in convolutional neural networks uses a sparse structure with local areas of connections between layers. In this case, the number of bonds between the elements decreases, but the number of layers increases significantly (up to several tens).

A common disadvantage of such devices is the need to create a large number of connections and long-term training to adjust their weights [Nikolaenko S., Kadurin A., Arkhangelskaya E. Deep learning. - SPb .: Peter, 2018. - 480 p., Ill.].

The technical result of the present invention is to improve the reliability of pattern recognition with a complex structure such that each structural element of the image requires its own set of feature values - its own storage element. The recognition reliability is increased due to the transmitting elements, which prepare for comparison with the next element of the analyzed image only those storage elements of the reference images that are connected by the transmitting elements with the storage elements that coincided in the previous step of matching images with a complex structure. Another technical result of the invention is the absence of the need for reprogramming or retraining when changing the reference images, since the connections between the given storage elements are established through chains of such transmitting elements that are not occupied by other connections. Due to the fact that the transmitting elements are connected only with the nearest neighboring transmitting elements, their implementation on a LSI or VLSI is possible.

The specified technical result is achieved in that the associative recognition device comprising a data input device, a control unit, an output device and a matrix of memory elements connected by a data and command bus to the control unit differs from the known analogs in that it additionally contains a matrix of transmitting elements connected by a bus instructions with a matrix of storage elements, and each transmitting element is connected by command buses with the nearest neighboring transmitting elements.

The design of the device is illustrated by drawings, which show diagrams showing the following:

- in Fig. 1 shows a general view of the device;

- in Fig. 2 shows the arrangement of elements in arrays of storage elements and transmission elements;

- in Fig. 3 shows the directions of signal propagation by transmitting elements with a hexagonal arrangement of elements in the matrices;

- in Fig. 4 shows a diagram of the end element Coupling

- in Fig. 5 shows a diagram of the connector of the end communication elements of the storage element;

- in Fig. 6 shows a diagram of an intermediate communication element;

- in Fig. 7 shows a diagram of a connector of intermediate communication elements;

- in Fig. 8 shows a diagram of a memory element;

- in Fig. 9 shows examples of handwritten letters that explain the operation of a pattern recognition device consisting of structural elements;

- in Fig. 10 shows possible points of connection of structural elements of handwritten letters;

- in Fig. 11 shows the state of the matrices of storage and transmitting elements after recording the reference image of the letter "m";

- in Fig. 12 shows a panel for describing the structural elements of the letters of a computer program, in which the operation of the device on a conventional personal computer was simulated;

- in Fig. 13 shows a panel for describing the designs of handwritten letters from structural elements, as well as the results of recognizing letters in a continuous handwritten text using a hardware-software complex with which the operation of the device was simulated.

The associative recognition device contains a data input device 1, a control unit 2, an output device 3, a matrix of storage elements 4 and a matrix of transmitting elements 5. Output 6 (reference images) and output 7 (analyzed, it is also a recognizable image) of the data input device 1 are connected to the inputs of the control unit 2. The control unit 2 is connected by the data and command bus 10 with the matrix of storage elements 4, which is connected by the command bus 11 with the matrix of transmitting elements 5. Output 8 (list of correspondences between structural elements) and output 9 (similarity assessment) of control unit 2 associated with output device 3.

Any optical device including a microprocessor for generating informative features of recognized objects can be used as a data input device. A control unit and output device is a personal computer or other computing device and printer. The matrix of storage elements can be implemented on microprocessors, the matrix of transmitting elements - on integrated circuits (LSI or VLSI).

The operation of the device is described using the example of the hexagonal arrangement of active elements (Fig. 2). A hexagonal raster is more economical in terms of the number of links to neighboring elements than an orthogonal raster.

The storage element (ZE) contains the storage element itself and the connector of its terminal communication elements 12 (CES).

The transmitting element (PE) is the intermediate communication elements (PES) and the connector of the intermediate communication elements 13.

With the hexagonal arrangement of active elements, each GE is connected by means of a connector with six KES, and each transmitting element has 9 PES and a connector that organizes the transmission of signals through them (Fig. 2).

The principle of establishing a connection between two storage elements (graph vertices) is to find the shortest path through unoccupied communication elements. For this purpose, signals are emitted from both connected GEs to their end coupling elements (Fig. 3a). From the first SE there is a primary wave, which is advanced by intermediate communication elements in 3 directions closest along the wave (Fig. 3b, 3c) until it reaches the CES adjacent to the second connected SE. After that, already as a secondary wave, it returns back to the first GE, passing and setting as an element of the graph edge at each step only one of the possible communication elements through which the primary wave passed.

A terminal link element (CES) connects the vertex of the graph with the edge of the graph, i.e. is the beginning or end of the chain of link elements that make up the edge of the graph.

A schematic of the end coupling is shown in FIG. 4.

In the mode of establishing the edge of the graph, the IES works as follows:

1. From the memory elements (ZE), displaying two connected vertices of the graph, the signals w ₀₁ and w _{02 are emitted} : w ₀₁ - to six CESs adjacent to the first ZE, w ₀₂ - to six CESs adjacent to the second ZE (Fig. 3a ).

2. Signal w ₀₁ from ZE ₁ triggers the primary wave of edge establishment. It passes through the element I1 in the event that this IES has not yet been included in the composition of any other edge of the graph, which is signaled by the trigger T2. The T01 trigger is turned on, indicating that the primary wave has passed through this IES, and the F1 shaper advances it to the adjacent transmitting communication element (PES) located in the appropriate direction with respect to this IES.

3. The signal w ₀₂ from the second connected SE, passing through the element I2, provided that this CES is not occupied by another edge (trigger T2), turns on the trigger T02, indicating that the primary wave should end here.

4. When the primary wave arrives at the input bin of such a terminal coupler, which is prepared by the signal w02, it passes through the element I3 and switches the T2 trigger to a state indicating that this CES is part of the graph edge. In this case, the shaper F2 through cout begins a secondary wave, which will go back in the direction of ZE1. Thus, the CES, adjacent to ZE2, is finally included in the composition of the formed edge of the graph, and the secondary wave launched by it will include in the edge intermediate communication elements through which the primary wave passed, and the CES adjacent to ZE1.

5. When the secondary wave arrives at the input din of the original CES, adjacent to the first of the connected vertices (see item 2), i.e. in which the trigger T01 is turned on, it includes this IES in the composition of the edge of the graph with the help of the F3 generator and transmits the signal "Connection is" to the control unit (CU) to complete the process of establishing communication.

In the graph comparison mode, when the T2 trigger is on (a sign of belonging to a graph edge), the following channels work:

Through them, the preparation (activation) of those GEs (vertices of the graph) is carried out, which are connected by chains of communication elements with the GEs that coincided at the current step of comparison.

The connector of the storage element communication end elements. The IES connector of the storage element organizes the operation of the terminal communication elements, through which this GE can be connected to other GEs (Fig. 5).

на коннектор приходят сигналы первичной волны при установлении связи между соединяемыми запоминающими элементами, через

- сигналы вторичной волны. Выходят сигналы первичной и вторичной волн через шины связи

и

соответственно. Шины

и

работают в режиме сопоставления графов, когда требуется участие ребер графа.Through the bus

signals of the primary wave arrive at the connector when a connection is established between the connected storage elements, through

- signals of the secondary wave. Primary and secondary waveforms are output via communication buses

and

respectively. Tires

and

work in the graph matching mode when the participation of the graph edges is required.

The primary wave begins with a signal W01 from the memory element (ZE) to which this connector belongs. It gets to all IESs of the connector and passes through those IESs that have not yet been included in any chains of communication elements that represent the edges of the graph.

) на коннектор второй соединяемой вершины, где сигналом W02 в КЭС включены триггеры Т02, она через элемент ИЛИ1 включает дешифратор, который поочередно открывает свои элементы связи.When the primary wave comes from adjacent intermediate couplers (signal

) to the connector of the second connected vertex, where the T02 triggers are switched on by the signal W02 in the IES, it turns on the decoder through the OR1 element, which alternately opens its communication elements.

As soon as the primary wave hits the IES, where the edge end trigger is turned on, the signal t2 from it through the OR2 element will turn off the decoder, thereby preventing other IESs of this connector from being included in the graph edge. Then the secondary wave will go back from only one IES.

и с помощью дешифратора попадет в один из тех КЭС, где стартовала первичная волна.The process of establishing the edge of the graph ends when the secondary wave returns to

and with the help of a decoder it will get into one of those IESs where the primary wave started.

The circuit of the intermediate coupling element (PES) is shown in Fig. 6.

In the mode of establishing the edge of the graph, the TES works as follows. The primary wave from the CES adjacent to the ZE ₁ , depending on the direction of its movement, which is determined by the connector of the transmitting communication elements (Fig. 7), arrives at a ⁱⁿ or b ⁱⁿ and is promoted by this TES at a ^out or b ^out, respectively. The triggered T1 trigger indicates that the primary wave has passed. The secondary wave from the CES, adjacent to the ZE ₂ , arrives at c ⁱⁿ or d ⁱⁿ and, if T1 is on, includes this SES in the chain of coupling elements, displaying the edge of the ZE ₁ - ZE _{2 of the} graph, by including T2. In this case, the secondary wave moves to c ^out or d ^out until through the same TECs it reaches the CES adjacent to ZE ₁ :

1. The primary wave W1 comes to the input of a ^Rin. Starting its way from some terminal link element (see above), it passes through I1 element, if this link element is not yet included in the composition of any edge of the graph (trigger T2). In this case, the T1 trigger is turned on - the sign "There was a primary wave" and the F1 shaper advances it further through the output a ^out and the associated inputs of neighboring PES, transmitting signals in the three nearest directions (Fig. 3b). Depending on the direction of the wave movement, it can arrive at a ⁱⁿ or b ⁱⁿ and exit through a ^out or b ^out, respectively. If we designate the inputs and outputs of the PES of the storage element as B _ij , i = 1 ... 6, j = 1 ... 6, then the wave goes from input i to output j = i + 3, or to output j = i + 2, or to output j = i + 4.

2. When the secondary wave W2 begins to return from another CES, which is adjacent to the second connected ZE, it goes along the line c ⁱⁿ - I5 - OR3 - F2 - I6 - c ^out or d ⁱⁿ - I7 - OR3 - F2 - I8 - d ^out . In this case, if this TES is not yet included in the graph edge (T2 trigger), but the W1 wave (T1 trigger) has passed, then the F2 shaper turns on the T2 trigger, resets the T1 trigger of the primary wave and advances W2 further.

3. Wave W2 should go only to one of the three TECs that are closest in the direction of signal transmission, and which were visited by wave W1. For this purpose, the input g receives a signal from the connector of the transmitting communication elements (Fig. 7), which interrogates its PES in turn. As soon as there is such a PES in which the T1 trigger is turned on, i.e. there was a primary wave, the shaper F2 will turn on the trigger of establishment of communication T2, and the signal from the output t ₂ will inform its connector about it.

In the graph comparison mode, when the T2 trigger is on (a sign of belonging to a graph edge), the following channels work:

Through them, the preparation (activation) of those GEs (vertices of the graph) is carried out, which are connected by chains of communication elements with the GEs that coincided at the current step of comparison.

Connector for intermediate communication elements. The PES connector (Fig. 7) organizes the operation of nine intermediate coupling elements (in the case of a hexagonal arrangement of active elements) located at a certain node of the hexagonal lattice and through which the EGs can be connected to other EGs.

на коннектор приходят сигналы первичной волны при установлении связи между соединяемыми запоминающими элементами, через

- сигналы вторичной волны. Выходят сигналы первичной и вторичной волн через шины связи

и

соответственно. Шины

и

работают в режиме сопоставления графов, когда требуется участие ребер графа.Through the bus

signals of the primary wave arrive at the connector when a connection is established between the connected storage elements, through

- signals of the secondary wave. Primary and secondary waveforms are output via communication buses

and

respectively. Tires

and

work in the graph matching mode when the participation of the graph edges is required.

Each PES of one connector carries output signals in the forward and reverse directions as shown in FIG. 3b, and the connector distributes one input signal to three PESs in accordance with FIG. 3c.

приходят на входы а ^вх или b^вх промежуточных элементов связи в зависимости от направления ее движения (фиг. 3б) и выходят из них (а ^вых или b^вых) через шину

данного коннектора на соответствующие входы шины

соседних коннекторов.Primary Wave Signals via Bus

come to the inputs a ⁱⁿ or b ^{in of} intermediate communication elements, depending on the direction of its movement (Fig.3b) and leave them ( a ^out or b ^out ) through the bus

of this connector to the corresponding bus inputs

adjacent connectors.

приходят на входы c^вх или d^вх промежуточных элементов связи и выходят из них (c^вых или d^вых) через шину

данного коннектора на соответствующие входы соседних коннекторов - на их шины

. При этом, чтобы вторичная волна уходила не на все три ближайших направления (фиг. 3в), а только на те ПЭС, на которых побывала первичная волна, дешифратор коннектора посылает сигнал на вход g своих ПЭС для опроса, была ли на них первичная волна. Дешифратор прекращает опрос, как только на ИЛИ2 поступит сигнал t₂ из ПЭС, которая включилась в состав цепочки элементов, связывающих два запоминающих элемента.Secondary wave signals via bus

come to the inputs c ⁱⁿ or d ^{in of} intermediate communication elements and leave them (c ^out or d ^out ) through the bus

of this connector to the corresponding inputs of adjacent connectors - to their buses

... In this case, in order for the secondary wave to go not to all three nearest directions (Fig.3c), but only to those PESs that were visited by the primary wave, the connector decoder sends a signal to the input g of its PESs to interrogate whether there was a primary wave on them. The decoder stops polling as soon as the signal t ₂ arrives at OR2 from the PES, which is included in the chain of elements connecting two memory elements.

The storage element (Fig. 8) is used to store in the form of attributes (features) information of one vertex of the reference graph G _E and to compare this information with the vertices of the analyzed graph G _A , as well as to establish connections between the storage elements (ZE), which in the reference graph are connected by edges.

The storage element contains 4 memory blocks:

- own parameters;

- block of functional programs;

- information attributes;

- communication keys with other GEs, and

- one threshold element that is triggered when the input information matches the information stored in the GE.

The block of own parameters stores:

1. The identifier (ID) of the storage element is a unique cipher of the element that distinguishes it from other GE systems.

2. Class name (Class) - the type of the structural element of the reference image. It is used when the images consist of several kinds of elements connected with each other. For example, when memorizing and recognizing letters, these can be sticks, hooks, loops, from which letters are composed.

3. The status (Status) takes the value {0, 1, 2, 3, 4, 5}, depending on the mode of operation of the ZE (0 - ZE is free, 1 - ZE is busy, 2, 3 - the connection between the elements is being established, 4 - the connection is established, 5 - the image graphs are being compared).

4. The sign of the readiness of the ZE (Ready) for comparison with the next vertex of the analyzed graph. Accepts values "On / Off" (On / Off).

5. Sign of coincidence (Match) of the given vertex of the standard with the next vertex of the analyzed graph. Accepts values "On / Off" (On / Off).

The block of information attributes is used to store the names and values of the attributes of the structural element of the reference image.

The block of communication keys connects the GE with other GE, forming the image structure as a set of interconnected elements - a graph consisting of vertices and edges.

The block of functional programs contains 3 programs that ensure the operation of the memory element:

- receiving and storing information;

- establishing links with other GEs;

- comparison of the GE information with the information of the next vertex of the analyzed image.

ZE functions are implemented by three programs P1, P2, P3.

P1. Reception and memorization of attributes. Starts with Status = 0:

1. Establishing (memorizing) the class of the vertex Class = <name of the vertex type>, vertices of different types can have different sets of attributes.

2. Reception and memorization of names a ₁ ,…, a _N and values v ₁ ,…, v _N attributes.

3. Switching the ZE status to the status Status = 1 - ZE is busy.

P2. Establishing a connection. In most applied problems of graph matching, a distinction is made between incoming and outgoing arcs. Here, for greater versatility, each GE displaying the top of the graph has a list of start and a list of end addresses of the element. These addresses point to the vertices with which this vertex is associated. They can be interpreted as lists of outgoing and incoming arcs.

Signals Status = 2 or Status = 3 come from the control unit (CU) simultaneously to two connected GE reference image graphs. Signal Status = 2 means that the element displayed by this GE should connect its origin with another GE, i.e. with the beginning or end of another element, depending on which of the signals Status = 2 or Status = 3 will come to the second GE. Accordingly, if a Status = 3 signal comes to this GE, it must connect its end with the beginning or end of another element.

1. Command Status = 2 or Status = 3 of communication establishment passes through the free (Gate = Off) output g ₁ , ..., g ₃ or g ₄ , ..., g ₆ , respectively, and is propagated by the communication elements. The primary wave through the terminal coupling element (CES) of the first SE and intermediate communication elements (PES) propagates to the CES of the second SE. From there, the secondary wave returns through those TECs through which the primary wave passed. From the CES of the first ZE it gets to one of the free inputs g ' ₁ ,…, g' ₃ or g ' ₄ ,…, g' _{6 of} this element, respectively. In this case, the involved communication elements are included as busy.

2. Memorizing (turning on) the corresponding connection Gate _k = On.

3. Switching ZE to Status = 4 - communication is established.

P3. Comparison. Triggered if the storage element is ready for comparison (Ready = On) by setting it to Status = 5:

1. From the control unit to the inputs of all GEs, the name of the C type, the names x ₁ ,…, x _N and the values y ₁ ,…, y _{N of the} attributes of the sought (compared) vertex of the analyzed graph G _{A are} simultaneously received. If on the threshold element of some GE of the reference graph G _E there is a coincidence with the type and attributes of this GE, then the Match = On match flag is turned on.

2. The matched GE activates the associated GE by sending a signal through its switched on connecting outputs g ₁ , ..., g _M. This signal passes through the included coupling elements to the corresponding input g ' ₁ , ..., g' _{M of the} connected GE and activates it by turning on the Ready = On indicator.

Due to this, the next vertex of the analyzed graph will be compared only with those vertices of the reference graph that are connected with the previous coincident vertex, thereby reducing the number of random matches.

The control unit ensures the operation of the device by recording the information of the reference graph into the matrices of storage elements (graph vertices) and transmitting elements (graph edges), controls their operation in the process of establishing connections and matching graphs, calculates the similarity score using the corresponding programs PN1, PN2, PN3 ...

PN1. Recording information of the reference graph.

1. Writing to the storage elements (ZE) the names of classes and attributes of the graph vertices. The information of the next vertex of the graph is entered into the first free (Status = 0) GE. Switching the state of the ZE to Status = 1.

2. Establishing connections between the ZE, representing the vertices of the graph, which are connected by an edge. Commands Status = 2 or Status = 3 are simultaneously sent to two connected ZEs.

3. When a Status = 4 (link is established) response is received from both linked GEs, the next pair of GEs is linked. So until all the edges of the reference graph are fixed in the matrix of transmitting elements.

PN2. Associative search - rough (preliminary) recognition: in turn, the information vector of attributes of each vertex G _{A is} compared simultaneously with all vertices G _E. The number of hits is accumulated in the control unit.

1. Activation of a class (set) of subjects by the attribute "Class name".

2. Selection from the number of active subjects by the vector of attribute values.

3. Calculation of the degree of similarity C = N1 / N2, where N1, N2 - the number of coincided and the total number of vertices of the reference graph, respectively.

Based on this rough estimate, depending on the problem, the control unit (CU) decides whether to end the process of matching these graphs or continue, but now taking into account the connections between the vertices and edges within these graphs.

PN3. Comparison of the reference graph G _E with the analyzed graph G _A.

1. All GEs are transferred to the comparison mode Status = 5.

2. The name of the class and the attributes of the first vertex of the graph G _{A are} compared simultaneously with all GEs that store the information of the vertices of the reference graph.

If a coincidence occurs in some GE, then it activates (prepares) these GEs for the next step through transmitting elements connecting it with other GE (vertices of the graph G _E ) - comparing with the next vertices of the analyzed graph.

3. In the analyzed graph, a vertex is taken that is connected by an edge to the previous coincident vertex and is compared with the vertex of the reference graph activated for comparison (Ready = On), i.e. now, when comparing graph vertices, connections between them are also taken into account. If several satisfactory vertices are found in G _E , then the CU organizes a stack for one-by-one checking of possible places of installation (mapping) of the vertices of the analyzed graph to the reference graph.

4. Go to the comparison of the next vertex of the analyzed graph.

If at some step of graph matching the next vertex G _A did not coincide with any vertex G _E , then another vertex from G _A is taken, connected with the previous one. If there are none, then the next vertex G _{A is} compared as the first - with all vertices G _E.

Thus, in the reference graph, chains of coincident vertices are distinguished, connected by the edges of the graph.

5. Calculation of an updated estimate of the similarity of the graphs G _A and G _E by the total number of vertices in the matched chains. In this case, the overlapping parts of the chains are counted once.

Note that a device can store multiple reference images simultaneously. It depends on the number of elements in its matrices 2, 3 (Fig. 1).

Let's consider the operation of the device using the example of handwritten letter recognition. The letters consist of the structural elements shown in Table 1. Let there be a reference image of the letter "m" (Fig. 9a), which needs to be compared with the images of the letters "h", "n" (Fig. 9b, 9c).

Structural elements of letters have the following attributes:

1. Chord Length - the length of the chord connecting the ends of the element.

2. Segment Number - the number of segments formed by the chain to the left and right of the chord of the element.

3. Left Segment Area - the area of the segment to the left of the chord, considering the chord directed from the beginning of the chain to the end.

4. Right Segment Area - the area of the segment to the right of the chord.

5. Max Area Height - the maximum height of the chord segments.

6. Tilt Angle - the tilt angle of the chord.

7. Closed - this element is closed.

The letter "m" (Fig. 9a) is a structure consisting of a short stick, indicated by the letter a , two vertical sticks d, e, one left arc b and one gyrus c, forming two nodes. The first node and the lower end of the rod connected to the upper end of the wand d and the left end of the arc b. In the second node, the right end of the arch b is connected to the upper end of the rod e and the left end of the gyrus c (see table 2). The arrangement of the connection points of the elements is shown in FIG. ten.

As a result of recording the reference image of the letter "m" in the storage and transmitting element matrices, connections will be established as shown in FIG. eleven.

Let's consider the operation of the device in the process of matching images.

At the stage of associative search (rough recognition), when matching the letter "h" with the template of the letter "m", all elements will match except for "b", i.e. similarity degree C = 4/5. When matching the letter "n", all elements will match, except for "c", the degree of similarity C = 4/5.

At the stage of comparing columns "m" and "h":

Step 1. Element 1 of the letter "h" will coincide with the element " a " of the letter "m", which through the link elements will prepare the elements "b" and "d" for matching in the next step.

Step 2. Element 2 of the letter "h" will not coincide with the elements "b" and "d" of the letter "m" activated in the previous step (allowed for comparison). Then it will be compared again, as in step 1, with all elements of the letter "m". A match will occur with the element "c", which, through the link elements, will prepare the elements "b" and "e" for matching in the next step.

Step 3. Element 3 of the letter "h" will match the element "e" of the letter "m".

Thus, the "b" and "d" elements of the letter "m" will not be marked as matched. The refined degree of similarity is C = 3/5.

When comparing columns "m" and "n":

Step 1. Element 1 of the letter "n" will coincide with the element " a " of the letter "m", which through the link elements will prepare the elements "b" and "d" for matching in the next step.

Step 2. Element 2 of the letter “n” will coincide with the element “b” of the letter “m”, which, through the link elements, will prepare the elements “c”, “d” and “e” for matching in the next step.

Step 3. Element 4 of the letter "n" will coincide with the element "e" of the letter "m", which through the link elements will prepare the element "c" for matching in the next step.

Step 4. Element 3 of the letter "n" will not match the element "c" allowed for comparison as a result of the previous step, and it will be compared again, as in step 1, with all elements of the letter "m". Will match element "d".

As a result, it will not be marked as a matched element "c" of the letter "m". The refined degree of similarity is C = 4/5.

Thus, due to the fact that a multitude of reference images can be simultaneously stored in the matrix of storage elements, the process of their comparison with the analyzed image is carried out in parallel. Another advantage of the device is the fact that no reprogramming or training is required to replace the reference images, since the connections between the image elements are formed in the recording mode of the standards.

The principle of operation of the device was simulated using a specialized hardware and software complex .. A sample of handwritten text is borrowed from [Kuchuganov MV, Kuchuganov A.The. Descriptive logic on image graphs. // Bulletin of the Udmurt University. Maths. Mechanics. Computer Science, Vol. 4, 2018, V. 28, S. 582-594. DOI: 10.20537 / vm180410].

FIG. 12 shows a panel describing the structural elements of letters and the search results for these elements in the image.

FIG. 13 shows a panel for describing letter designs from structural elements and the results of recognition of given letters.

Claims (3)

1. A device for associative pattern recognition with a complex structure such that each structural element of the image requires its own set of feature values - its own storage element containing a data input device, a control unit, an output device and a matrix of storage elements connected by a data and command bus to the control unit , characterized in that the output of the data input device is connected to the input of the control unit, the control unit is connected by a data and command bus to a matrix of storage elements, which is connected by the command bus to a matrix of transmitting elements, each of which is connected by command buses to the nearest neighboring transmitting elements, and the outputs the control unit is connected to the output device; each storage element contains a storage element itself and a connector of its terminal communication elements; the transmitting element includes intermediate communication elements and a connector of intermediate communication elements; each of the storage elements is connected by means of a connector with end communication elements, and each transmitting element contains intermediate communication elements and a connector providing signal transmission through them; each of the storage elements is equipped with memory blocks of its own parameters, functional programs, information attributes and communication keys with other storage elements, the last of the mentioned blocks includes one threshold element that is triggered when the input information matches the information stored in the storage element; the storage elements are made with the possibility of storing in them in the form of attributes of information of one vertex of the reference graph and for comparing this information with the vertices of the analyzed graph, as well as for establishing connections between the storage elements, which are connected by edges in the reference graph; The control unit is configured to ensure the operation of the device by recording the information of the reference graph into the matrix of storage elements and transmitting elements, as well as controlling their operation in the process of establishing connections and comparing the graphs and calculating an assessment of their similarity using appropriate programs. 2. A device according to claim 1, characterized in that the memory elements are made on the basis of microprocessors, and the transmitting communication elements are made on the basis of large integrated circuits. 3. The device according to claim. 1, characterized in that the memory elements are made on the basis of microprocessors, and the transmitting communication elements are made on the basis of very large-scale integrated circuits.

Images