JPS63779A - Pattern recognition method - Google Patents

Abstract

(57) [Summary] This bulletin contains application data before electronic filing, so abstract data is not recorded.

Description

DETAILED DESCRIPTION OF THE INVENTION [Technical Field] The present invention relates to a recognition method for patterns such as characters, and more particularly to a pattern recognition method using a multilayer directional histogram method.

[Prior art]

The applicant is Japanese Patent Application No. 59-202822.

A pattern recognition method using a multilayer directional histogram method has already been proposed in Japanese Patent Application No. 58-202825. The present invention relates to improvements to such pattern recognition methods.

In this pattern recognition method using the multilayer directional histogram method, a direction code is attached to the outline pixels of a pattern such as a single character, and the pattern is scanned from each side of the pattern frame toward the opposite side to identify white pixels (background). Find the direction code that appears next.

The direction code is stratified into a plurality of layers depending on how many times on the scan line the direction code is detected. Then, for each divided region within the frame of the pattern, a histogram of direction codes for each layer up to a certain layer is obtained, and a vector having each histogram as a component (feature quantity) is used as a feature vector of the pattern.

For example, if eight types of direction codes are attached, the inside of the pattern frame is divided into 4×4 mesh areas, and the direction codes of the first and second layers are targeted, the number of dimensions of the feature vector is 256 ( =4X4X2X8).

Regarding the dictionary, similar feature vectors are extracted from a plurality of identical patterns, and the average thereof is registered as the feature vector of the dictionary pattern (standard pattern).

Additionally, the present applicant has already proposed a similar pattern recognition method that takes into account the scanning direction for layering and further layers direction codes in detail. The present invention can be similarly applied to this pattern recognition method.

Furthermore, the method of dividing regions within the pattern frame is not limited to the method disclosed in the specification and drawings of the prior application. for example,
Similar to the pattern recognition method of the earlier application, the inside of the pattern frame is divided into meshes so that the direction codes are evenly distributed,
A method may be adopted in which the mesh areas are partially overlapped according to preset parameters and integrated into a smaller area. A pattern recognition method using a multilayer directional histogram method that adopts such a region division method is
Although the present invention has already been proposed by the applicant, the present invention can be similarly applied to such a pattern recognition method.

Now, in a pattern recognition method using such a multilayer directional histogram method, the unknown pattern and the dictionary pattern are distinguished by calculating the distance or similarity of the corresponding dimension component between the feature vector extracted from the unknown pattern and the feature vector of the dictionary pattern. The dictionary pattern with the minimum sum of distances or the dictionary pattern with the maximum sum of similarities is determined as the recognition result.

However, as described above, when the number of dimensions of the feature vector increases, there are problems in that the amount of distance or similarity calculations increases, the matching time increases, and the dictionary capacity increases.

〔the purpose〕

Therefore, an object of the present invention is to improve matching efficiency and reduce dictionary capacity in a pattern recognition method using a multilayer directional histogram method.

〔composition〕

The feature vector obtained by the multilayer directional histogram method has a dimension component that has a large pattern discrimination effect and a dimension component that has a less significant effect. Regarding this, in order to simplify the explanation, a two-dimensional feature vector will be considered.

When a dictionary is created using the multilayer directional histogram method with the number of dimensions as 2, it will contain ``sentence'', ``character'', and ``recognition''.

The feature vectors of each dictionary pattern of 11 m l+ are g r gzr gzr g4 in Fig. 5, respectively.
become that way. In this example, as is clear from FIG. 1, component (feature quantity) A of each feature vector has a larger variance (or standard deviation) than component (feature quantity) B. In other words, component A has a higher ability to discriminate against unknown patterns.

Matching unknown patterns and dictionary patterns.

Basically, the distance or similarity between the corresponding dimension components of the feature vectors of the unknown pattern and the dictionary pattern is determined, and the dictionary pattern with the minimum sum of distances or the maximum sum of similarities is taken as the recognition result.

Here, if we focus on the properties of feature vectors as described above, by calculating the distance or similarity preferentially from the part with high pattern discrimination ability, we can calculate the distance or similarity for some components with high pattern discrimination ability. At the stage of calculating the degree, dictionary patterns that cannot be candidates can be eliminated, and dictionary patterns that can be candidates can be narrowed down at an early stage.

In addition, the feature vector obtained by the multilayer directional histogram method is
There is a property that the characteristics of the pattern are preserved even if the order of each dimension component is changed.

Focusing on the above points, in the present invention, when creating a dictionary, the standard deviation or variance for each dimension of the feature vector of the dictionary pattern is determined, and the components of the feature vector of each dictionary pattern are set to the standard value or variance. Sort by the largest dimension of
The feature vectors after such sorting are registered in the dictionary.

For example, suppose that the feature vector of a certain dictionary pattern created by the multilayer directional histogram method is as shown in FIG. 6(a). Then, the order of dimensions with larger standard deviations or variances calculated for all standard patterns is X 4.
Xl, X,, X7. X.

X2. Suppose that X,,XG,... Then,
This feature vector has its respective dimensions X□j x2. x,
.

The components of . . . are rearranged and registered in the dictionary as shown in FIG. 6(b). In other words, the component of dimension x4 of the original feature vector is the component of the highest dimension Y□ of the rearranged feature vector, the component of dimension X□ is the component of the next dimension Y2,
It can be sorted like this.

Then, the feature vector extracted from the unknown pattern is
After sorting the components according to the sorting order of the components of the feature vector of the dictionary pattern, we calculate the distance or similarity between the feature vector of the dictionary pattern and the corresponding dimension component. Perform matching.

In the case of recognizing many types of patterns such as handwritten kanji, it is necessary to perform detailed matching using feature vectors with a large number of dimensions. However, when the target is recognition of patterns such as characters with a small number of types such as ANSK characters, the components of dictionary patterns and unknown patterns are sorted in order of dimension with large standard deviation or variance, that is, in order of dimension with high pattern discrimination ability, as described above. It was confirmed that by rearranging the characters, a sufficient recognition rate can be achieved by matching only a relatively small number of upper dimensions (for example, 20 dimensions, 24 dimensions, etc. in the case of ANSK characters).

Focusing on this point, in the present invention, only the upper N dimensions of the feature vectors of the dictionary pattern after dimension sorting are retained as described above, and the vectors obtained by discarding the lower dimensions are used as the final dictionary pattern. By registering the pattern as a feature vector in the dictionary, dictionary capacity can be reduced and matching efficiency can be further improved.

〔Example〕

An embodiment of the present invention will be described below with reference to the drawings.

FIG. 1 is a schematic block diagram showing a simplified functional configuration of an embodiment of the present invention. In this embodiment, it is assumed that the pattern to be recognized is a character pattern with relatively few types, such as ANSK characters.

In the figure, 10 reads a character pattern from a manuscript;
This is a pattern reading section that inputs character pattern information to the preprocessing section 12. The preprocessing section 12 is a section that performs preprocessing such as character extraction and normalization of the input character pattern, and inputs the processed character pattern to the feature extraction section 14 character by character.

The feature extraction unit 14 is a part that extracts feature vectors from the input character pattern using the multilayer directional histogram method.

In this embodiment, there are a dictionary creation mode and a pattern 12g1 mode as operating modes. first,
The case of dictionary creation mode will be explained below. Also,
A schematic flowchart of dictionary creation processing in this mode is shown in FIG. 2, and in the following description, corresponding step numbers are shown in parentheses.

To create a dictionary, M character patterns are sequentially input from the pattern reading unit 10 for each character type (
Step 102). The input character pattern is the preprocessor 1
2 undergoes preprocessing (step 102), and the feature extraction unit 14
A feature vector (for example, a 256-dimensional vector) is extracted using the multilayer directional histogram method (step 104). The extracted feature vector is converted to normal by converting unit 1
6 is input.

Reference numeral 18 denotes a rearrangement table section referred to by the rearrangement section 16, in which a rearrangement table created in advance is registered.

This sorting table is created as follows. For each character type, feature vectors (for example, 256-dimensional vectors) are extracted from a plurality of character patterns using the multilayer directional histogram method, and the average thereof is taken as the feature vector of the standard pattern of that character type. The standard deviation σ for each dimension n of the feature vector of the standard pattern of all character types (all types) obtained in this way is calculated by the following equation. Here, k is the number of the character type, and g
kn is a component (feature amount) of dimension n of the character type, and gn is the average of the component of dimension n for all character types.

Note that instead of the standard deviation, the variance, which is the square of the standard deviation, may be calculated.

The dimension numbers are arranged in descending order of the standard deviation or variance calculated in this way, and a correspondence table between the dimension numbers and the corresponding original dimension numbers is created up to the upper N dimensions. This correspondence table is the sorting table.

Return to the explanation of dictionary creation mode. In the sorting unit 16, the feature vector g k extracted from the input character pattern
Each dimension component of nm is sorted according to the sorting table of the sorting table unit 18, and the feature vector gkn consisting of the upper N-dimensional components after sorting is used by the dictionary creation unit 20.
(step 106).

In this way, when the N-dimensional feature vectors after dimensional sorting for the M character patterns of the same character weaving are accumulated in the dictionary creation unit 20, the dictionary creation unit 20 stores the M feature vectors. Find the average.

A one-character code is added to it as a dictionary pattern feature vector (N-dimensional vector) fkn for the character type, and the dictionary 22
(Step 1o8).

Next, the character type number k is updated (step 110), and the process returns to step 100, where the same dictionary creation process is executed for the next character type.6 When the process is executed up to the last character type (k=k), step 112, it is determined that the process is complete, and the process is completed.

Next, the case of pattern recognition mode will be explained below. Further, a schematic flowchart of processing in this mode is shown in FIG. 3, and in the following description, corresponding step numbers are shown in parentheses.

A character pattern to be recognized (unknown character pattern) is input from the pattern reading unit 1o (step 200), subjected to preprocessing by the preprocessing unit 12 (step 202), and input to the feature extraction unit 14, where the multilayer directional histogram method is applied. A feature vector xn (for example, a 256-dimensional vector) is extracted (step 204).

This feature vector 4
(step 206).

In the matching section 24, matching between the unknown input cover pattern and the dictionary pattern is performed as shown in (
Step 208).

Feature vector fk of dictionary pattern for each character type
Distance Dk between n and feature vector Yn of unknown character pattern
is calculated using the following formula: 1. Then, sort the distance,
The character code of the candidate character used to determine the dictionary pattern with the minimum distance as the candidate character is output as the recognition result for the unknown character pattern (step 210).

As described above, in this embodiment, the feature vectors of dictionary patterns are sorted in order of dimensions with large standard deviations or variances, that is, in order of dimensions with high pattern discrimination ability, and components with low pattern discrimination ability other than the top N dimensions. It is registered in the dictionary in the form of discarding the pattern, and the feature vector of the unknown input kataan is rearranged with components in the same dimension order as the dictionary pattern.

Matching between dictionary pattern and unknown character pattern is N
This is done by calculating the distance or similarity between dimensional vectors.

Therefore, high matching efficiency can be achieved with a small amount of distance or similarity calculations, and a sufficient recognition rate can be achieved since a high dimension of pattern identification ability is utilized. Furthermore, by reducing the number of dimensions, a significant reduction in dictionary capacity can be achieved.

Next, other embodiments of the present invention will be described.

The overall functional configuration of this embodiment is the same as that of the previous embodiment, and only a part of the matching processing in the matching section 24 is different. Therefore, with reference to the flowchart of FIG. 4 only for the processing of the matching section 24,
explain.

When the N-dimensional feature vector of the unknown character pattern after component rearrangement is input to matching, the character type, that is, the number of the dictionary pattern is set to 1 (step 300), and the matching between the dictionary pattern and the unknown character pattern is performed. be exposed.

First, for the upper N2 dimensions (N<N), the feature vector fkn of the dictionary pattern and the feature vector Y of the unknown character pattern. The sum of distances d is calculated (step 3o2). Then, the total distance d and the threshold T
A comparison with h1 is performed (step 304).

If d>Th1, the distance between the dictionary patterns is too large and it cannot be used as a candidate pattern (candidate character).
The matching was discontinued at this stage.

Increment the dictionary pattern number k in step 30.
6), return to step 302.

In other words, the unknown character patterns are roughly classified (narrowed down to candidate patterns) by calculating the distance up to the upper N1 dimension, and matching of the dictionary patterns excluded in this step is completed at this stage.

If d1≦Th1 in step 304, the sum d2 of distances to all dimensions N is calculated (step 310
). Then, the distance d2 is compared with the distance between the previous candidate pattern and the unknown character pattern, and the smaller candidate pattern and distance are stored (step 312).
), the process returns to step 302 via step 206.

When the matching is completed up to the final dictionary pattern, it is determined that the matching has ended in step 308, and the character codes of the final candidate patterns are output (step 314).
, the recognition process for the unknown character pattern is completed.

In this way, in this embodiment, the distance is calculated preferentially from the upper dimension of the feature vector, and based on the calculation results up to a certain dimension, dictionary patterns that cannot become candidate patterns are eliminated early, and dictionary patterns that can be candidate patterns are calculated. Performs detailed matching by performing distance calculations in all dimensions. Therefore, the number of unnecessary distance calculations is reduced compared to the embodiment described above, and the matching efficiency is further improved.

Such stepwise incorporation of candidate patterns may be performed in two or more stages. □For example, for each dictionary pattern,
Unknown character patterns are roughly classified by calculating the distance to the upper N dimensions (TazoshiN<N). If the dictionary pattern is not excluded, the distance to the upper N2 (Tazoshi, N1<N2<N) dimension is calculated to classify the unknown character pattern. If this intermediate classification does not eliminate the problem, the top N, (Tazoshi N z <
Subclassification of the unknown character pattern is performed by calculating the distance up to the N3 < N) dimension. If the unknown character pattern is not excluded even with this small classification, detailed matching of the unknown character pattern is performed by distance calculation for all dimensions.

In this way, matching calculations with dictionary patterns that cannot be candidates can be stopped earlier, and the matching time can be further shortened.

In each of the embodiments described above, distance was used to match the unknown pattern and the dictionary pattern, but it goes without saying that similar matching processing may be performed by determining the degree of similarity.

Furthermore, the present invention is applicable not only to character patterns but also to the recognition of general patterns such as speech. [Effects] As is clear from the above explanation, according to the present invention, the multilayer directional histogram method If matching efficiency can be greatly improved and pattern recognition time can be shortened, efficiencies such as the ability to significantly reduce dictionary capacity can be obtained.

[Brief explanation of the drawing]

FIG. 1 is a simplified block diagram showing the functional configuration of an embodiment of the present invention, FIG. 2 is a schematic flowchart of dictionary creation processing in the embodiment, and FIG. 3 is a pattern recognition processing diagram in the embodiment. A schematic flowchart; FIG. 4 is a schematic flowchart of the matching process in an embodiment of the method of the present invention; FIG. 5 is a vector diagram for explaining the properties of feature vectors in the multilayer directional histogram method; FIG. 6 is a component of the feature vector. It is an explanatory diagram of rearrangement. 10... Pattern reading section, 12... Preprocessing section, 14... Feature extraction section, 16... Sorting section, 18... Sorting table section, 20... Dictionary creation section, 22 ···dictionary. Figure 1φ

Claims (2)

[Claims] (1) In a pattern recognition method using the multilayer directional histogram method, the components of the feature vector of the standard pattern obtained by the multilayer directional histogram method are sorted in advance in the order of dimensions with the largest standard deviation or variance, and then only the top N-dimensional components are used. The vector consisting of is registered in the dictionary as the feature vector of the dictionary pattern, and the components of the feature vector extracted from the unknown pattern by the multilayer directional histogram method are sorted according to the sorting order of the components of the feature vector of the dictionary pattern, and the components are A pattern recognition method characterized by performing matching between an unknown pattern and a dictionary pattern by calculating the distance or similarity of the corresponding dimension components between the feature vector after sorting and the feature vector of the dictionary pattern. (2) Compute the distance or similarity of the feature vectors starting from the higher dimension components, and use the result of the computation to
Claim 1, characterized in that it is further determined whether or not to calculate the distance or similarity of components of lower dimensions.
The pattern recognition method described in Section.