JPH02238579A - Pattern extraction recognition device - Google Patents

Abstract

PURPOSE:To extract and recognize a pattern which crosses other elements without any error by holding the history of matching processing by a history holding means and then stepping back to correct correspondence processing. CONSTITUTION:A matching means 9 makes an input element, stored in an input element storage means 6, correspond to a standard pattern element stored in a standard pattern storage means 7. This matching means 9 assumes one element among input element candidates which can be made to correspond to the standard pattern element and also records the state of this matching processing into a history holding means 8 as a history. If there is a failure in subsequent correspondence processing, the assumption of the latest correspondence is rejected and stepping-back processing for reading back the internal state of the matching means 9 out of the history holding means 8 to make another input element correspond. Consequently, a part matching the structure of the pattern described in the standard pattern can be extracted and recognized in an input figure without any omission.

Description

[Detailed Description of the Invention] 2. Field of Application [Industry] The present invention relates to a conventional technology for extracting and recognizing patterns from graphic images.A conventional pattern extraction and recognition device has the configuration shown in FIG. The input figure image is subjected to noise removal and line thinning processing by the preprocessing means 2, and the input figure is converted into an expression using line segment vectors etc. as input elements, and the pattern separation means 3 performs the following: After extracting a candidate region that is predicted to contain a pattern to be extracted based on rough graphical features such as closed loops and short segments, detailed graphical features of the region are The patterns are classified by feature analysis, and the output means 5 outputs the best extraction recognition results. Etc. Brother 1'. ＞tl"Kou" Pattern separation from shapes with various intricately drawn elements and complicated line segments 3
, the region where Batano is expected to be included is positive +
- Difficult to move, pattern 3...-7 It was difficult for the pattern extraction recognition device as a whole to correctly extract and recognize patterns. An object of the present invention is to enable reliable pattern extraction and recognition processing even for figures such as maps in which various elements are intricately drawn and line segments are complicated.

Means for Solving the Problems In order to solve the above problems, the pattern extraction recognition device of the present invention includes means for converting an input graphic image into data using input elements that are basic constituent elements of the shape, and an input element storage means for holding data on input elements that have been extracted, a reference pattern storage means 7 for holding data regarding reference pattern elements that are constituent elements of a pattern to be extracted and recognized, and input element and reference pattern storage in the input element storage means. Masoching means 9 for associating the standard pattern elements in the standard pattern storage means with the input elements in the input element storage means 6 using the standard pattern elements in the means and processing history data; the history of matching processing performed in the masoting means; and a history holding means for holding data.

Operation The pattern extraction recognition device according to the present invention enables the following processing. In other words, this device does not perform processing to separate and extract regions in which a pattern is expected to exist, and instead compares the input elements stored in the input element storage means with the standard pattern elements stored in the standard pattern storage means. The matching process is performed by the matching means. In the matching means, in the process of sequentially associating each standard pattern element with an input element, one element is assumed as the matching element from among the input element candidates that can be mapped to the standard pattern element, and this matching The processing status is recorded as a history in the history holding means.

If the subsequent matching process fails, the latest matching assumption is rejected and a backtracking process is performed to recall the internal state of the matching means from the history holding means,
Map another input element.

Thereafter, based on this assumption, the process of associating standard pattern elements that have not yet been associated is continued.

As described above, pattern extraction recognition 57 according to the present invention,
-7 In the recognition device, even if a standard pattern element is mistakenly matched with another element that intersects with the pattern to be extracted, the history of the matching process is retained by the history retention means, so the correct response cannot be taken. It is possible to go back to the adding process, and patterns that intersect with other elements can be extracted and recognized without error.

EXAMPLES Hereinafter, examples of the present invention will be described in detail with reference to the drawings.

FIG. 1 is a Bronnoch diagram showing the overall configuration of an embodiment of a pattern extraction recognition device according to the present invention.

In the same figure, 1 is an input means such as a scanner, and 2r/'i input figures inputted from the input means 1 are subjected to noise processing and line thinning processing, and are expressed using input elements, which are the basic constituent elements of figures. It is a preprocessing means for converting into data. Here, as input elements that are basic components, for example, line segment vectors represented by point elements and line elements are used. 6
7 is an input element memory 6 for storing the input element data obtained by the preprocessing means; be. Standard pattern elements are also expressed in the form of line segment vectors represented by point elements and line elements. Reference numeral 9 denotes a masoting means that associates the input element data stored in the input element storage 6 with the data held in the standard pattern storage means 7. 8 is a history holding means for holding history data of matching processing performed by the matching means 9; and 5 is an output means for outputting and displaying the results of the 1,000-stage matching 9.

Next, the operation will be explained based on a specific input figure.

A map is used as an input figure, and the input pattern is taken as an example of a bridge symbol appearing on the map as shown in FIG. In FIG. 2, there is a bridge made up of input elements 10 to 19, and input elements 20 to 2.
A part of the map is shown where a river made up of 3 and a road made up of input elements 24 and 27 intersect.

First, the standard pattern elements 28 to 7 shown in FIG.
, -, A standard pattern of a bridge to be extracted and recognized, which is composed of standard pattern elements 33, is read in input 1,000 steps, preprocessed in 1,000 steps, and converted into a line segment vector as an input element to form a standard pattern. The memory of the standard Bakun stored in the storage means 7 is:
It is performed in the order of the matching processing performed by the matching means 9,
In this embodiment, the standard pattern element 28 → standard pattern element 29 → standard pattern element 30 → standard pattern element 31 →
The standard pattern element 32 is stored in the order of standard pattern element 33.

On the other hand, the graphic image shown in FIG. 2 is inputted through the input stage 1, and the preprocessing means 2 performs noise removal and linear part extraction processing, and each of the input elements 10 to 27 shown in FIG. Generate input elements. These input elements are stored in the input element storage means 6.

In the matching 1000 stages 9, the standard pattern elements stored in the standard pattern memory 1000 stages 7 are read in order, and from among the input elements stored in the input element storage 1000 stages 6, input elements that can be associated with the standard pattern elements are selected. , and select them as candidates for response. At each stage of the matching process, even if there are multiple input element candidates, one candidate is assumed and the subsequent matching process is performed. The input element assumed as a candidate for correspondence and the processing details performed in the matching stage 9 are recorded in the history holding stage 8. Thereafter, the process of associating the standard pattern elements in the standard pattern storage means 7 that have not yet been matched is continued.

However, if the association is not successful in the subsequent association processing, the processing state is returned to the state assuming the latest association based on the history data recorded in the history holding 1,000 steps 8. Through this backtracking process, the input element previously assumed as a mapping candidate is rejected, and the mapping is switched to another candidate. If there is no other candidate, further backtracking processing is performed. The association process accompanied by this backtracking process is performed until all the standard pattern elements in the 1,000 standard pattern storage stages 7 are correlated. Finally, the input element associated with the standard pattern in the standard pattern storage means 7 passes through the output stage 5 and is output as a pattern extraction recognition result.

9...-7 Next, an example of a processing process in which the matching processing of all standard pattern elements does not fail and no backtracking processing is performed is shown below.

Process a1 The matching means 9 reads the standard pattern element 28, and based on the graphical attribute value such as the line segment length of the standard pattern element 28, the input element 10, which is one of the input elements that can be matched, is set as an input element. A selection is made from the 1,000 storage stages 6, and a correspondence between the standard pattern element 28 and the input element 10 is assumed.

The processing history is recorded in the history holding means 8.

Processing a2 The matching means 9 reads the standard pattern element 29, and determines the graphical attribute values such as the line segment length of the standard pattern element 29 and the correspondence with the standard pattern 28 with the input element 10 assumed in the previous process a1. Input elements 11 and 12, which are input element strings that can be associated based on the connection relationship, etc.
and 13 are selected from the input element storage 6, and it is assumed that the standard pattern element 29 and the input elements 11J2 and 13 correspond. The processing history 10=-7 is recorded in the history holding means 8.

Processing a3 The standard pattern element 30 is created by processing similar to processing a2.
The correspondence between the input elements 14 and the input elements 14 is assumed and recorded in the history holding means 8.

Processing a4 - Processing a6 The same processing as the above processing a1 to processing a3 is performed, the standard pattern element 31 and the input element 15 are associated, and the standard pattern element 32 and the input element strings 1617 and 18 are
Finally, the standard pattern element 33 and the input element 19 are associated and stored in the history holding stage 8, respectively.

Process a7 As a result of the above processing, input elements 10, 11, 12, 13, 14, 15, 16, 17, 1 extracted and recognized as bridges
8 and 19 are output by the output means 5.

Next, an example of a processing process in which association fails and backtracking processing is performed will be shown.

Processing b1 Same as process a1.

11... Processing b2 Unlike processing a2, the standard pattern element 29 is the input element 1
1 and 20 are assumed. The processing history is recorded in the history holding stage 8.

Process 1] 3 The standard pattern element 30 is read out from the standard pattern storage means 7, and the input element storage means 6 is searched for an input element that can be correlated. Here, the standard pattern element 30 is
Since it is connected to the standard pattern element 29, processing 1
] In step 2, search for an input element that is connected to the input element month and 20 that are associated with the standard putter 7 element 29. but,
Since there is no input element beyond the input elements 11 and 20, the matching processing of the standard pattern element 30 fails, and a backtracking process is performed. In this backtracking process, the state of the above processes 1 and 2, which is the latest association process, is called from the history holding 1,000 stages 8, and the association assumed in process b2 is canceled.

Process 1] 3 Redo the mapping of process 1) 2, and standard pattern element 2
9 and the input elements 11, 12, and 13 are found in correspondence and stored in the history holding stage 8.

Process 1] 4-Process b 7 The subsequent processing is the same as processing a4 to processing a7.

As is clear from the above explanation, there are cases where the size and direction of the symbol are not constant, and where other lines or symbols intersect with the pattern.
Even if the input element is different, it can be reliably extracted and recognized by performing a trial-and-error search for each input element.

In addition, in the above embodiment, the case where extraction and recognition of the same input pattern as the standard pattern shown in FIG. By doing this, any pattern can be extracted and recognized from the input figure.

Effects of the Invention As described above, the pattern extraction recognition device of the present invention is capable of backtracking using the history of matching processing even when the pattern to be extracted and recognized in the input diagram intersects with other elements. , it becomes possible to investigate all possible correspondences, and it is possible to extract and recognize all parts from the input diagram that match the structure of the pattern described in the standard pattern.

[Brief explanation of drawings]

FIG. 1 is a Bronnoch diagram showing the overall configuration of an embodiment of the pattern extraction recognition device according to the present invention, and FIG. 2 is a diagram showing an example of an input pattern input to the pattern extraction recognition device.
FIG. 3 is a diagram showing an example of a standard pattern to be extracted and recognized used in the pattern extraction device of the present invention, and FIG. 4 is a Bronnoch diagram showing the configuration of a conventional pattern extraction and recognition device. 1. Input means, 2. Preprocessing means, 5 Output means, 6
...Input element storage means, 7. Normative pattern storage means,
8...History holding means, 9 - Matching means, 10-
27. Input elements of the input pattern, 28-33. 7 standard Paku elements of the standard pattern. Figure 1 Name of agent Patent attorney Shige Awano Takaho is the third person

Claims (1)

[Claims] A figure image input means, a preprocessing means for converting the input figure image obtained by the input means into data using basic constituent elements of the figure, and an input element storage means for holding the data created by the preprocessing means. , a reference pattern storage means for holding data regarding reference pattern elements that are constituent elements of a pattern to be extracted and recognized; a matching means for associating data in the input element storage means with data in the reference pattern storage means; and a matching means. A pattern extraction recognition device comprising: a history holding means for holding history data of matching processing performed in the matching process; and an output means for outputting the association results obtained by the matching means.