JPS5854432B2 - Pattern recognition processing method - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention relates to a pattern recognition processing method, particularly to a pattern recognition processing method for detecting, removing and absorbing noise and deformation contained in an input cover pattern in a pattern recognition device such as an optical character reading device. It is something.

Character recognition devices that target handwritten characters are likely to contain noise or deformation (hereinafter simply referred to as noise) in their patterns, so in order to improve recognition ability by reducing misreadings and decoded characters, It is necessary to perform sufficient noise processing.

Conventional noise processing methods for this type of device include ([) Batch processing such as removing isolated points, isolated branches and whiskers with a length below a certain standard, and filling in chips during preprocessing; (1i)
Prepare multiple standard patterns to deal with the above noise, (i
ii) When the identification system is configured with a tree, the tree may be made redundant.

First, method m cannot deal with the removal of branches that should be left, or relatively long whiskers or chips.

Furthermore, in the method (11), it is impossible to predict in what part the missing pattern will appear, so a very large number of standard patterns are required to absorb a variety of noises.

Furthermore, method (iii) has drawbacks such as the inability to increase the discriminative power due to redundancy, or the tree becoming complex to cover the redundancy, making it impossible to deal with an increase in the number of categories.

The present invention aims to eliminate the above-mentioned drawbacks regarding noise processing of input patterns and improve the discrimination ability of a pattern recognition device, and will be described in detail below with reference to the drawings.

FIG. 1 shows a configuration example of a pattern recognition device incorporating the present invention, in which 1 is a photoelectric conversion section, 2 is a preprocessing section, 3 is a feature extraction section, 4 is a noise processing section, and 5 is a determination section. .

First, an input cover pattern written on paper is converted into an electrical signal by a photoelectric conversion section 1, and then subjected to processing such as binarization, smoothing, and size normalization in a preprocessing section 2.

The percentage feature extraction unit 3 performs thinning, feature point extraction, direction coding,
Various processes such as branch extraction, extraction of information indicating the connection relationship between branches, and topological feature extraction are performed.

The noise processing unit 4, which is a characteristic part of the present invention, detects noise while comparing the incoming cover pattern with the standard pattern on a branch-by-branch basis, removes and absorbs noise, and associates the incoming cover pattern with the standard pattern.

The determination unit 5 obtains a value indicating the similarity (or dissimilarity) between the input pattern and the standard pattern that have been matched by the noise processing unit 4, and determines the category of the standard pattern that maximizes this value as the determination result. .

Before entering into a specific explanation of the noise processing section 4, which is a characteristic part of the present invention, the expression format of the input pattern created by the standard pattern and feature extraction section 3 will be described.

The input cover pattern and the standard pattern are made into a thinning pattern with a thickness of -0 by thinning processing, and based on this, the following fourth pattern is made.
．． The pattern information shown in Figure 6.7 is extracted.

Fig. 2 shows an example of an inlet cover turn, and Fig. 3 shows an example of a standard pattern, where 6 is an inlet cover turn, 1 is a standard pattern, and m! (i=1.2.3...) is the feature point of the input pattern, l! (j-1, 2, 3,...) are the branches of the input Kabataan, m, z (i' = 1.2.3, -.-) are the feature points of the standard pattern % 18/(j' = 1 .2,3...
) is a branch of the standard pattern.

FIG. 4 is an example of a feature point table regarding the input cover pattern 6 in FIG. 2, where each feature point m1 (1=1t2.3...)
The number of branch points (1: end point, 2: intermediate point, 3: 3 branch point, 4: 4 branch point), X coordinate, y coordinate, adjacent feature points, etc. are shown.

The order of the feature points is, for example, I'll"1 + rni t rn in the order in which the feature points are searched from the upper left side of the input pattern 6 in FIG.
``3...2m blue.

In '2 y rn "'3..." is determined.

Regarding the branch, lf is the branch whose end is the first feature point In '11 rn 1.

12, 13, and 14 squares, respectively, by tracing the character line counterclockwise along the character line as l blue.
T! l ``4''...''.

FIG. 5 shows an example of a minute line segment direction code, and each number O
~7 indicates codes corresponding to each direction.

In general, straight lines or curves that make up a two-dimensional thinning pattern can be described as a sequence of direction codes, so each type of cover turn and standard pattern can be expressed as a sequence of direction codes, as shown in an example in Figure 6. .

FIG. 6 is an example of a branch table related to input cover turn 6 in FIG. 2, in which each school l↓(j=1, 2).

3...) minutiae numbers, lengths, and fifth points of the start and end points of
It consists of a direction code string that expresses a branch using the direction code shown in the figure.

FIG. 7 is an example of a table showing the topological characteristics regarding the input cover turn 6 in FIG. represents the number of connected components (ie, the number of mutually independent strokes).

FIG. 8 shows an example of the configuration of the noise processing section 4, where 8 is a scan parameter, 9 is a standard pattern feature table, 10 is a human cover turn feature table, 11 is a memory, 41 is a noise information calculation section, and 42 is a start branch installation section, 43 is a noise detection and removal section;
Reference numeral 44 represents a branch mapping unit, 45 represents a branch search unit, 46 represents noise information, and 47 represents a mapping table.

The inputs of the noise processing unit 4 are the scan parameter 8 for searching the starting point, the above-mentioned feature point table (Fig. 4), branch table (Fig. 6), and table showing topological features (Fig. 7).
There are three types: a standard pattern feature table 9 consisting of information indicating the connection relationship between the pattern and other patterns, and an input cover pattern feature table 10.

Therefore, the standard pattern and the input cover pattern are expressed not as two-dimensional patterns but in the form of a feature table that is convenient for handling.

First, the noise information calculation unit 41 calculates the topological features (E, B4.L) shown in FIG. 7 from the memory 11.

N) and calculate the difference between the input pattern and the standard pattern for each deviation (△E=E"-E"'; △B4=B4B
4. ΔL=LL, ΔN=N N (where ■ is the input cover turn and S is the standard pattern), and these are temporarily stored as noise information 46.

Taking the input cover pattern 6 in Fig. 2 as an example, △E=0, ΔB,
=-1, ΔL=O1ΔN=O.

Next, the start branch setting section 42 scans from the scanning direction determined by the scan parameter 8 and determines the first feature point found from the coordinates of each feature point in the feature point table as shown in FIG. Use it as a starting point.

Furthermore, with reference to the memory 11, a starting branch with the starting point as one end and an end point of this starting branch are found and used as initial values for the association.

Taking the input pattern 6 in FIG. 2 as an example, and assuming that the branch 11 is the starting branch, the starting point, the starting branch, and the end point of the starting branch are each (m !i p-l"3 p m, in standard pattern 7 in Figure 3 (mξ, -1 treasure 2m snow)
becomes.

Next, before describing the noise detection and removal section 43, noise will be explained.

What is referred to as noise here refers to the portion of the input pattern that does not match topologically with respect to the standard pattern.

FIG. 9 shows an example of a standard pattern regarding numbers and an example of an input pattern including noise.

FIG. 10 shows the increase and decrease of topological features due to various noises as shown in FIG.
, ΔB4tΔL, ΔN), and a=
i is the type of noise, and examples of input patterns with each type of noise are shown.

For example, if “minor branches (beards)” exist (△E,
-ΔB4 tΔL, -ΔN) (1,0°0.0)
It is classified as a "minor branch" because the noise information appears.

The noise detection/removal unit 43 first narrows down noise candidates based on the topological properties Ts and T4 (S: standard pattern, ■two-person cover turn) of the end point of the branch of interest.

Figure 11 shows noise candidates due to Ts and TI, where the symbol a = i is the type of noise shown in Figure 10, and the "-" above the symbol indicates a noise with a topologically opposite sign to the noise of that symbol. Noise or * indicates no noise and appears only when Ts=TI.

Judgment as to which noise is the noise from the noise candidates obtained in this manner or whether there is no noise is made by the logic prepared for each combination of (TS=TI) shown in FIG.

Taking input cover turn 6 in Fig. 2 as an example, as mentioned above, the end point of the standard pattern and the start branch of the input cover turn are (mg2m
and their topological properties are TS = 4
.

Since TI=3, the noise candidates are a, ■ from Fig. 11.
, b.

FIG. 12 is an example of a flowchart for determining noise when (Ts, TI) = (4, 3), and 431 indicates noise candidates,
432 and 433 indicate judgment.

First, the candidates 431 consist of three types, a, a, and b. In the first judgment 432, it is determined whether ΔB4 of the noise information 46 is O, and if ΔB440, it is determined that it is noise, and ΔB4=O
If so, proceed to the right in FIG. 12 and proceed to judgment 433.

As shown in FIG. 10, this is the noise candidate 431 (a
, a, b), only the noise is ΔB4NO, the noise a is (1, 0, 0, 0), and the noise i is (-i, o
, o, o), so ΔB4=O.

In the next judgment 433, the input pattern feature table 10 (
The judgment is made with reference to FIG. 4), and if there is, it is determined that there is a noise a, and if there is, it is determined that it is a noise d.

In the example of the input cover pattern 6 described above, ΔB4NO
Therefore, it is immediately determined in judgment 432 that there is noise, and the noise branch is determined by referring to the input cover turn feature table 10 and
, becomes.

The found noise branch is notified to the branch search unit 45 that the branch has been removed, for example by rewriting the starting point number on the branch table in FIG. 6 to O.

The example of (Ts, TI) = (4, 3) shown here is the first
This is a relatively simple example in which noise can be determined from the two determinations 432 and 433 in FIG. 2, and the degree of geometric difference or similarity of the branches shown in the next example is not used for determination.

FIG. 13 is an example of a flowchart for determining noise when (TS, TI) = (3, 3), where 434 is a noise candidate, 435-
438 is judgment.

When (TS, TI) = (3, 3), the noise candidate 434 is
From Fig. 11', there are four types: * y a p a I C, and the judgment 435 is, for example, if △L<0 of the noise information 46, there is no noise regarding the end point *, and if △L>0, there is noise C.
If 1ΔL=0, the process advances to decision 436.

Judgment 436 judges whether △E=-1, and △E=-
If it is 1, the noise is 11ΔE#-i, then the process advances to judgment 437.

In judgment 437, it is judged whether △E≧1, and if △E<1, there is no noise, and if △E≧1, the process proceeds to judgment 438.

Judgment 438 determines the degree of geometric dissimilarity (or degree of similarity) described below for the branch next to the branch of interest for the standard pattern and the input pattern, respectively, and calculates the degree of geometric dissimilarity (or degree of similarity) described below, and calculates the degree of geometric dissimilarity (or degree of similarity) described below to a certain threshold of dissimilarity 6 or more (or a threshold of similarity δ ′ or less), then the noise α
, if it is less than the threshold δ (or more than the threshold 67 in the case of similarity), it is determined that there is no noise.

Here, the geometric dissimilarity and similarity of branches will be explained.

To determine the noise, either the dissimilarity or the similarity is used.

First, to show an example of the degree of difference, consider the direction, bending, and length as the geometric properties of branches, and define the difference between the standard pattern and the input pattern for each as follows.

Dl: Difference in average direction of both patterns, where Dl, D2. D3 indicates the difference in the direction, bending, and length of the branches, ■ indicates the inlet pattern, and S indicates the standard pattern.

The degree of geometric dissimilarity is calculated using weighting constants α, β, and γ. It is expressed as

On the other hand, regarding similarity, can be defined.

As an example of T1, the type of noise is determined using the methods described above for y T2 y T3 as follows.Here, the absorption method for each noise for a = i shown in Fig. 10 will be explained in order. .

Noise a: End point of the branch of the input pattern of interest (3-branch point)
Remove the shortest branch whose other end is the end point among the branches coming out of the .

Noise i: The same processing as noise a is performed on the standard pattern branch.

Noise b = End point of the branch of the input pattern of interest (3-branch point)
Among the branches that come out from the branch, the shortest branch whose other end is a 3-branch point is removed, and the two 3-branch points are combined into one 4-branch point.

Noise i: Similar processing is performed when noise is added to the branches of the standard pattern.

Noise C: End point of the branch of the input pattern to be focused on (3-branch point)
Remove the shortest branch whose other end is a 3-branch point among the branches coming out of the .

Noise d: End point of the branch of the input pattern of interest (4-branch point)
Remove the shortest branch whose other end is the end point among the branches coming out of the .

Noise e: End point of the branch of the input pattern of interest (four-branch point)
Among the branches coming out from the , remove two short branches whose other end is the end point.

Noise f: The end point (end point) of the branch of the input pattern of interest and the end point closest to the end point are connected and integrated.

Noise g: End point of the branch of the standard pattern of interest (3-branch point)
Separate.

Noise h: Connect and integrate the end point (end point) of the branch of the input pattern of interest and the end point closest to the end point.

Noise i: End point of the branch of the input pattern of interest (four-branch point)
Cut it to make 3 branch points.

When absorbing each noise as described above, in addition to these topological corrections, the noise information 46 is corrected by the increase/decrease in the topological characteristics due to each noise shown in FIG. Use tlJ for detection.

For example, in the above-mentioned input cover turn 6, △E=0, ΔB,=
-1, △L=0, △N=0, △E=ΔB4=△L=
It is corrected as ΔN=O.

The branch correspondence section 44 writes the corresponding branch number of the input cover pattern excluding the noise plate and the standard pattern in the corresponding material table 47, and the determination section 5 refers to it.

With the above procedure, the correspondence between the input cover pattern and a set of branches of the standard pattern is completed, and the process enters the branch search section 45.

The branch search unit 45 traces, for example, the counterclockwise input cover turn and the character line of the standard pattern, sets a new branch number and its end point number, returns to the noise detection and removal unit 43, and checks that all branches correspond. Repeat the process until it is completed.

FIG. 14 is an example of a table showing the correspondence between the above-mentioned input cover pattern 6 and standard pattern 7 created by the above-described processing. ♀ and d11 3rd is l amount and l5, 4th is -4
9 and -l”1s The fifth time is IB, and flood are associated with each other, and branch II.

are excluded as noise branches.

As explained above, according to the present invention, the presence or absence of noise, and if noise is present, the type of noise and the branch number to be removed are detected using a standard pattern as a reference for each branch.
Correct correspondence is possible even if there are relatively long whiskers or chips, and a relatively small number of standard patterns per category is sufficient.

[Brief explanation of the drawing]

FIG. 1 shows the configuration of an embodiment of a pattern recognition device incorporating the present invention, FIG. 2 shows an example of a thinned input cover pattern, and FIG.
The figure is an example of a thinned standard pattern, Figure 4 is an example of a feature point table, Figure 5 is an example of a minute line segment direction code,
FIG. 6 is an example of a branch table, FIG. 1 is an example of a table showing the topological characteristics of the input pattern, FIG. 8 is an example configuration of the noise processing unit 4, and FIG. 9 is a number (1 to 0). An example of a standard pattern and an example of an input pattern with noise,
Fig. 10 is an explanatory diagram showing the correspondence between types of noise and increases and decreases in their topological features; Fig. 11 is an explanatory diagram illustrating noise candidates based on the topological properties of end points of branches; Fig. 12;
FIG. 3 shows an example of a flowchart for determining noise, and FIG. 14 shows an example of a correspondence table. In the figure, 1 is a photoelectric conversion unit, 2 is a preprocessing unit, 3 is a feature extraction unit,
4 is a noise processing unit, 5 is a determination unit, 6 is an example of a thinned input pattern, 1 is an example of a thinned standard pattern, 8 is a scan parameter, 9 is a standard pattern feature table,
10 is an input cover turn feature table, 11 is a memory, 41
42 is a noise information calculation unit, 42 is a start branch installation unit, 43 is a noise detection and removal unit, 44 is a branch correspondence unit, 45 is a branch search unit, 46
is noise information, 41 is a table with correspondence, 431 is a noise candidate, 432 and 433 are judgments, 434 is a noise candidate, 435
438 indicates determination processing.

Claims (1)

[Claims] 1. Straight lines or curves constituting a pattern are described as a direction code string of minute line segments that can take multiple directions, and the order relationship of branches is maintained from the starting point of correspondence between the standard pattern and the input cover pattern. In a pattern recognition device that identifies each branch based on the quantity that indicates the similarity or difference between the standard pattern and the input cover pattern, when associating the branches between the standard pattern and the input cover pattern, the topological features of the pattern are used. Narrow down the types of noise and deformation included in the input cover pattern, and determine the presence or absence of noise and deformation in the target branch and its surroundings, as well as the presence or absence of noise and deformation in the target branch and its surroundings, based on the degree of geometric dissimilarity or similarity of the branches and the topological properties of the end points of the branches.・When there is a deformation, determine the type of noise and deformation, and apply topological corrections to the standard pattern or input pattern, including branch removal, separation and integration of feature points, according to the noise and deformation. A pattern recognition processing method characterized in that the noise and deformation are absorbed by the method and the standard pattern and the input pattern are associated with each other. 2. Claims characterized in that the topological features of the pattern are extracted by selecting at least four of the number of loops, the number of end points, the number of 3-branch points, the number of 4-branch points, and the number of connected components. The pattern recognition processing method according to item 1. 3. The topological property of the end point of each school is determined by extracting any one of an end point, an intermediate point, a 3-branch point, and a 4-branch point. The pattern recognition processing method described in Section 2.