JPH0711819B2 - Pattern recognition method - Google Patents

Description

TECHNICAL FIELD The present invention relates to a method for recognizing patterns such as handwritten Chinese characters,
More specifically, the present invention relates to a pattern recognition method using a feature vector based on the multi-direction histogram method.

[Prior Art] The applicants of the present invention are directed to Japanese Patent Application Nos. 59-202822 and 58-202825.
Have already proposed a pattern recognition method based on the multilayer histogram method. The present invention relates to an improvement of such a pattern recognition method.

In this pattern recognition method using the multilayer direction histogram method, a direction code is attached to the contour pixels of a pattern such as a character, and the pattern is scanned from each side of the frame of the pattern toward the opposite side, and white pixels (background) are formed. The next appearing direction code is detected and the direction code is classified into a plurality of layers depending on how many times it is detected on the scan line.
Then, for each of the divided areas within the frame of the pattern, a histogram of the direction code for each layer up to a certain layer is obtained, and a vector having each histogram as a component (feature amount) is used as a feature vector of the pattern.

For example, if 8 kinds of codes are added as direction codes, the mesh is divided into 4 × 4 mesh areas in the pattern frame, and the direction codes of the first layer and the second layer are also targeted, the dimension number of the feature vector is 256 ( = 4 × 4 × 2 × 8).

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

Further, the present applicant has already proposed a similar pattern recognition method in which the direction code is stratified in more detail in consideration of the scanning direction for stratification. The present invention can be applied to this pattern recognition method as well.

Further, the method of dividing the area within the pattern frame is not limited to the method disclosed in the specification and drawings of the above-mentioned prior application. For example,
Similar to the pattern recognition method of the previous application, the pattern frame is divided into meshes so that the direction codes are uniformly distributed,
A method may be adopted in which the mesh areas are partially overlapped according to preset parameters and integrated into a small area. The pattern recognition method by the multilayer direction histogram method adopting such a region division method is
The present invention has been proposed by the present applicant, but the present invention can be similarly applied to such a pattern recognition method.

By the way, in such a pattern recognition method by the multi-direction histogram method, the pattern type of the unknown pattern is identified by calculating the matching distance between the feature vector extracted from the unknown pattern and the feature vector of the dictionary pattern ( Recognize unknown patterns).

However, when the dimension number of the feature vector becomes large as described above, there is a problem that the distance calculation amount becomes large and the matching processing time becomes long.

[Objective] Therefore, an object of the present invention is to improve the efficiency of the matching process in the pattern recognition method by the multi-layered direction histogram method.

[Structure] The feature vector obtained by the multi-layered histogram method has a dimensional component with a large pattern identification effect and a dimensional component with a less pronounced effect. In this regard, consider a two-dimensional feature vector for ease of explanation.

When a dictionary is created by the multi-directional histogram method with the number of dimensions being 2, the feature vectors of the dictionary patterns of “sentence”, “letter”, “recognition”, and “knowledge” are respectively g ₁ and g in FIG.
_It looks like ₂ , g ₃ , g ₄ . In this example, as is clear from the figure, the component (feature amount) A of each feature vector has a larger variance (or standard deviation) than the component (feature amount) B. In other words, the component A has a higher ability to identify an unknown pattern.

Focusing on the characteristics of such a feature vector, the matching distance is preferentially calculated from a component having a high pattern identification ability, so that the matching distance calculation is performed up to a part of the dimensions having a high pattern identification ability. It will be possible to exclude dictionary patterns that cannot be candidates and narrow down the dictionary patterns that can be candidates at an early stage.

Also, the feature vector by the multi-direction histogram method is
The characteristics of the pattern are preserved even if the order of the respective dimensional components is changed.

Focusing on the above points, in the present invention, the feature vectors of the temporary dictionary patterns of all the pattern types are obtained by the multilayer directional histogram method, and the components of the feature vectors are arranged in the descending order of standard deviation or variance. The changed vector is registered in the dictionary as a feature vector of the dictionary pattern.

Then, pattern recognition is performed as follows. A feature vector is extracted from an unknown pattern by the multilayer directional histogram method, and a vector obtained by rearranging the components in the descending order of the standard deviation or variance and the feature vector of the dictionary pattern of each pattern type are matched up to upper N dimensions, The matching distance is compared with the threshold value corresponding to the pattern type, and it is determined whether the matching regarding the pattern type is interrupted or the detailed matching up to the lower dimension is performed according to the comparison result.

The threshold value is determined as follows. A feature vector is extracted by a multi-direction histogram method from a plurality of patterns for each pattern type, and a vector in which the components are arranged in the descending order of the standard deviation or variance,
The standard deviation or variance of the matching distance to the upper N dimensions with the feature vector of the dictionary pattern of the same pattern type is obtained, and the threshold value for each pattern type is determined based on this standard deviation or variance.

According to such a pattern recognition method, the matching process with a dictionary pattern that cannot be a candidate for an unknown pattern is interrupted early, so that the matching effect is improved and the pattern recognition speed is increased. In addition, since the threshold value for determining the interruption of matching is determined as the pattern type as described above, it is possible to reliably prevent an error in which matching with a dictionary pattern that should not be excluded from candidates is interrupted by mistake. The essential advantages of the recognition method are not impaired and a high recognition rate can be achieved.

EXAMPLES Examples of the present invention will be described below with reference to the drawings.

FIG. 1 is a schematic block diagram showing a simplified functional structure of an embodiment of the present invention. In this embodiment, a character pattern such as a handwritten Chinese character is assumed as the recognition target pattern.

In the figure, 10 is a pattern reading unit for reading a character pattern from a document and inputting the character pattern information to the preprocessing unit 12. The preprocessing unit 12 is a unit that performs preprocessing such as character cutting and normalization of the input character pattern and inputs the processed character pattern to the feature extraction unit 14 for each character.

The feature extraction unit 14 is a unit that extracts a feature vector from the input character pattern by the multi-layered direction histogram method.

Here, in this embodiment, there are a dictionary creation mode and a pattern recognition mode as operation modes. First, the case of the dictionary creation mode will be described below. In addition, the second part of the schematic flowchart of the dictionary creation processing in this mode is shown.
In the figure, the corresponding step numbers in the following description are shown in parentheses.

For one character type, M character patterns are sequentially input from the pattern reading unit 10 (step 50). The input character pattern is pre-processed by the pre-processing unit 12 (step 52) and input to the feature extraction unit 14 to be a feature vector (for example, a 256-dimensional vector) by the multi-directional histogram method.
Are extracted (step 54). The extracted feature vector is input to the dictionary creating unit 20 via the rearrangement unit 16. The dictionary creation unit 20 obtains an average vector of the feature vectors extracted from the M input character patterns (step 56), and the average vector is temporarily stored in the dictionary 22 as the feature vector of the temporary dictionary pattern of the character type. It is registered (step 58).

The dictionary creating unit 20 checks whether the processing has been completed up to the last character type (step 60), and if there is an unprocessed character type, the process returns to step 51 and the same processing is performed for the next character type.

When the processing for all character types is completed, the rearrangement table creating unit 26 calculates the standard deviation or variance for each dimension of the feature vectors of all the temporary dictionary patterns temporarily registered in the dictionary 22 (step 62). . Then, a sorting table for sorting the original feature vectors in descending order of standard deviation or variance is created.
Is registered in (step 64).

Up to this point, this is the processing stage for creating the rearrangement table, after which the actual dictionary creation processing begins.

For one character type k, M character patterns are sequentially input from the pattern reading unit 10 (step 66). The input character pattern is subjected to preprocessing by the preprocessing unit 12 (step 68) and input to the feature extraction unit 14 to extract a feature vector by the multi-directional histogram method (step 7).
0).

The respective components of the extracted feature vector are rearranged by the rearrangement unit 16 according to the rearrangement table registered in the rearrangement table unit 18 in descending order of the standard deviation or variance (step 72). In this way, the M feature vectors after the rearrangement of the components are sent to the dictionary creating unit 20,
These average vectors are main-registered in the dictionary 20 as feature vectors of the dictionary pattern of the character value k (step
74).

The dictionary creation unit 20 checks whether or not the dictionary creation processing has been completed for all the character types (K types) (step 76), and if there are unprocessed character types, the same processing from step 66 is performed for the unprocessed character types. Is done.

When the processing is completed for all the character types, the dictionary itself is finished, but the threshold value determination processing is performed next.

In this process, M character patterns similar to those used to create the dictionary for each character type are input (step 7).
8) After pre-processing (step 80), feature vectors are extracted by the multi-directional histogram method (step 82). The feature vectors of the M character patterns are rearranged by the rearrangement unit 16 according to the rearrangement table (step 84) and input to the matching unit 24.

Next, by starting the matching unit 24 and the threshold value determining unit 28,
A threshold decision is made. That is, the matching unit 24 calculates the matching distance between each feature vector and the feature vector of the dictionary pattern of the character type k up to the upper N dimensions, and the threshold determination unit 28 calculates the upper N from the calculation result.
The standard deviation of the matching distance to the dimension is determined (step 86). Then, the standard deviation is registered in the threshold value table unit 30 as the threshold value of the character type k (step 88).

Similarly, thresholds for other character types are determined and registered in the threshold table unit 30.

When it is determined that the thresholds have been determined and registered for all character types (step 90), the entire processing in the dictionary creation mode ends.

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

The unknown character pattern to be recognized is the pattern reading unit 10
This is input (step 100), and after the preprocessing (step 102) by the preprocessing unit 12, the feature extraction unit 14 extracts a feature vector (for example, a 256-dimensional vector) by the multi-direction histogram method (step 104).

The components of this feature vector are rearranged according to the rearrangement table by the rearrangement unit 16, and the rearranged feature vector Yn is input to the matching unit 24 (step
106).

In the matching 24, the matching distance d between the feature vector Fkn of the dictionary pattern of the character type k and the feature vector Yn of the unknown pattern to the upper N dimensions is calculated (step 108). Then, the matching distance d is compared with the threshold Thk of the corresponding character type k registered in the threshold table unit 30 (step 110).

If d> Thk, there is no possibility that the character type of the unknown pattern is the current character type k, so the matching process with the dictionary pattern is interrupted and the end determination is performed (step
116).

If d ≦ Thk, there is a high possibility that the current character type is the character type of the unknown character pattern, so detailed matching is performed. That is, the matching distance D is calculated for all dimensions (step 112). Then, the distance D is compared with the distances of the candidates up to that point, the character type with the smaller distance is left as a new candidate (step 114), and the process proceeds to step 116 of the end determination.

When it is determined in step 116 that the character type to be matched remains, the step 10 for the next character type is performed.
Matching processing after 8 is performed.

When matching processing is performed for all character types,
In step 116, it is determined that the process has ended, and the character code of the finally remaining candidate character type is output as the recognition result. This completes the recognition process for one unknown character pattern.

Now, the tendency and degree of deformation of characters such as handwritten Chinese characters vary depending on the writer (user of the recognition system). In order to deal with this, character patterns considering various character transformations are prepared and used for dictionary creation.

However, even in such a case, depending on the user, matching between the handwritten character pattern and the dictionary pattern is good or bad. Also, even the same user tends to improve the matching property with the dictionary and increase the recognition rate as the user gets used to the recognition system.

Focusing on such a point, it is convenient that the threshold for determining whether or not to perform the detailed matching can be changed. That is, in the case of a good user of matching with the dictionary or a user who is accustomed to the matching, the recognition speed can be increased without lowering the recognition rate by lowering the determination threshold and lowering the frequency of detailed matching.

Next, the second aspect of the present invention that enables such a threshold adjustment
Examples will be described. Since the functional configuration of this embodiment is the same as that of the above embodiment, its block diagram is omitted, and FIG. 1 is referred to in the following description as necessary.

In this embodiment, in the dictionary creation mode, the sorting table and the dictionary are created as in the previous embodiments. However, a plurality of thresholds for determining whether or not to perform the detailed matching are determined for each character type.

This point will be described with reference to the flowchart of FIG. 2 related to the first embodiment. If the threshold value determined in step 88 is Thk, in this embodiment, Thk / 1, The values of Thk / 2 to Thk / L (L is a positive integer) are determined by the threshold determination unit 28 as the thresholds Thk (1) and Thk (2) to Thk (L) of the character type k, respectively, and the threshold table unit 30. Be registered with.

FIG. 4 is a schematic flow chart of the pattern recognition mode in this embodiment. The pattern recognition mode in this embodiment will be described with reference to this drawing.

In this embodiment, the user level UL (= 1, 2, 3, ..., L), which is a parameter for selecting the threshold value, is set in the first step 200. The user level UL can be specified by the user of the pattern recognition system according to this embodiment.

Steps 202 to 210 are the steps shown in FIG.
The contents are the same as 100 to step 108. Step 21
Steps 4 to 220 have the same contents as steps 112 to 118 in FIG.

Step 212 is a step for determining whether or not to perform detailed matching from the matching distance to the upper N dimensions, and corresponds to step 110 in FIG. In the case of this embodiment, one threshold value Th (UL) corresponding to the user level UL is selected from a plurality of threshold values Th (1) to Th (L) of the character type k.
Is used as a threshold for the determination.

That is, in the case of a user who is familiar with the pattern recognition system according to this embodiment, if the user level UL is designated as a high level (the highest is L), a smaller threshold value (the lowest is Th.
(L)) is selected and used for the determination, the frequency of proceeding to the detailed matching (step 214) is reduced, the matching efficiency is improved and the character recognition speed is increased accordingly.

On the other hand, if the user is unfamiliar or has poor matching with the dictionary, if a low user level UL (lowest is 1) is specified, a large threshold value (highest is Thk (1)) is selected and judged. Since the frequency of detailed matching increases, the recognition speed decreases but the recognition rate can be increased.

As described above, the recognition rate varies depending on the user, but also varies depending on the character type. This is remarkable when a pattern with a certain habit is used as a pattern for dictionary creation, but such a point is difficult to check at the dictionary creation stage when there are many character types such as Kanji. is there.

It is possible to absorb such a variation in the recognition rate for each character type. The third embodiment of the present invention will be described below.
The functional configuration of the pattern recognition system according to this embodiment is the same as that of the first embodiment. The processing in the dictionary creation mode is similar to that in the second embodiment, and a plurality of types of determination thresholds Th (1) to Th (L) are determined for each character type.

FIG. 5 is a schematic flowchart of the processing in the pattern recognition mode in this embodiment. In this figure, steps 300 to 308 have the same contents as steps 202 to 210 in FIG. 4, and steps 314 to 320 have the same contents as steps 214 to 220 in FIG.

In step 310, the level LV (k) for each character type is set as the threshold selection parameter V. This level LV
(K) is given as a value obtained by storing the reject / recognition rate Rk of the character type k during operation of the pattern recognition system and dividing the Pk value by a certain constant.

Then, step 312 is a step corresponding to step 212 in FIG. 4, and is a plurality of thresholds Thk (1) to Thk of the character type k.
One threshold Th corresponding to the parameter V from (L)
It is determined whether or not to proceed to the detailed matching (step 314) by selecting k (V) and comparing it with the distance d.

A fourth embodiment, which is a combination of this embodiment and the second embodiment, will be described with reference to the flowchart of FIG. 5 for convenience.

In this embodiment, a user level UL setting step (corresponding to step 200 in FIG. 4) is added before step 300. In step 310, the sum of the level LV (k) of the character type k and the user level UL is the parameter V.
Is set as. Then, in step 312, the threshold Thk (V) corresponding to the parameter V is used for the determination.

Other than this, it is the same as each of the above-mentioned embodiments.

According to this embodiment, since it is possible to absorb the variation factors depending on the user and the character type and determine whether or not to perform the detailed matching using the optimum threshold value, the second and third embodiments described above. Both advantages are obtained.

Although the embodiments of the present invention have been described above, the present invention is not limited thereto and can be variously modified and implemented without departing from the scope of the invention.

Further, in each of the above embodiments, the character pattern is recognized, but it is apparent from the above description that the present invention is not limited to the character pattern and can be similarly applied to the recognition of all patterns such as voice.

[Effect]

As is clear from the above description, according to the present invention, it is possible to obtain the effects that the matching efficiency by the multi-direction histogram method is significantly improved and the pattern recognition time can be shortened.

[Brief description of drawings]

FIG. 1 is a simplified block diagram showing a simplified functional configuration of an embodiment of the present invention, FIG. 2 is a schematic flowchart of a dictionary creating process in the same embodiment, and FIG. 3 is a pattern recognition process in the same embodiment. 4 is a schematic flowchart of pattern recognition processing in another embodiment of the present invention, FIG. 5 is a schematic flowchart of pattern recognition processing in yet another embodiment of the present invention, and FIG. 6 is a multi-direction histogram method. 3 is a vector diagram for explaining the property of a feature vector in FIG. 10 …… Pattern reading section, 12 …… Preprocessing section, 14 …… Feature extraction section, 16 …… Sorting section, 18 …… Sorting table section, 20 …… Dictionary creating section, 22 ……
Dictionary, 24 ... matching section, 26 ... rearrangement table creating section, 38 ... threshold value determining section, 30 ... threshold value table section.

Claims (5)

[Claims] 1. A method in which feature vectors of temporary dictionary patterns of all pattern types are obtained by the multi-directional histogram method, and the vector of the feature vector components of the temporary dictionary pattern is rearranged in descending order of standard deviation or variance. As a vector, a feature vector is extracted from a plurality of patterns for each pattern type by the multi-direction histogram method, and the components are arranged in descending order of standard deviation or variance, and a feature vector of the dictionary pattern of the same pattern type. The threshold value for each pattern type is determined based on the standard deviation or variance of the matching distances to the upper N dimensions of and, and the components of the feature vector extracted from the unknown pattern by the multi-direction histogram method are arranged in descending order of the standard deviation or variance. Replaced vector and the dictionary for each pattern type Matching with the characteristic vector of the turn is performed up to the upper N dimensions, the matching distance is compared with the threshold value of the pattern type, and whether the detailed matching is performed for the pattern type to the lower dimension is determined based on the comparison result. A pattern recognition method characterized by judging. 2. A plurality of threshold values for each pattern type are determined, and one of the threshold values is selected and used for determining whether or not to perform detailed matching. The pattern recognition method described in the item. 3. The pattern recognition method according to claim 2, wherein the selection of the threshold value used for the determination is performed according to a parameter common to all pattern types. 4. The pattern recognition method according to claim 2, wherein the threshold value used for the determination is selected according to a parameter for each pattern type. 5. The pattern recognition method according to claim 2, wherein the selection of the threshold value used for the determination is performed according to a parameter common to all pattern types and a parameter for each pattern type.