JPS6316794B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention relates to a feature extraction method for an optical character recognition device (hereinafter referred to as OCR), and particularly to a method for extracting features that distinguish patterns having roundness and curvature.

When recognizing characters written on paper, it is generally scanned optically, and the character part is set to "1" and the white part of the paper is set to "0".
The data is quantized into a binary pattern, separated into individual characters, then subjected to preprocessing such as noise removal and thinning, and then passed through a feature extraction section and a determination section. In the feature extraction part, the end points of the normal line,
Feature points such as branching points and bending points, and feature amounts such as concave and convex portions are extracted, and the determining section determines the input character based on the presence or absence or amount of these features. Regarding this feature extraction, various feature extraction methods have been proposed and put into practical use. For example, when the number of characters to be read is expanded to include numbers, alphabets, katakana, etc., the number of similar characters increases, so first, relatively effective features (hereinafter referred to as basic features) for identifying the entire character to be read are extracted. , a candidate character is determined based on the extracted basic features, and then features are extracted from the basic features or the input pattern according to multiple feature lists described for each character only for this candidate character, and candidates that satisfy the feature list are extracted. A method of reducing the number of characters to one has been adopted and put into practical use.

This basic feature extraction method is described, for example, in the literature, IEICE Pattern Recognition and Learning Study Group material (published February 26, 1975), "Handwritten Katakana Recognition by Broken Line Approximation", document number (PRL74-62). , from the character pattern shown in Fig. 1, to the end point T, branch point B, bending point K, stroke direction indicated by numbers such as 1, 2, 3, 5, etc. (indicated by arrows) as shown in Fig. 1. ) in the order of detection.
It is assumed to be a symbol string such as 2K5B3B1B. Incidentally, FIG. 1 is an example showing the correspondence between the stroke direction and the numbers 0, 1, 2, . . . 7. The above-mentioned symbol string is checked against a standard pattern prepared in advance. This standard pattern is for example A: 123K (45K)
It has a shape like 45B23B01B, and in this format, the first A indicates the letter name of this standard pattern, and K, B, and numbers (0 to 7) indicate inflection points and branching points as in Figure 1 and 2. , indicates the direction of the stroke; in particular, the number 123K indicates one of directions 1, 2, and 3, and the subsequent K indicates the presence of an inflection point.

Also, the inner part shown in parentheses shows good strokes even if they are not normal.

Since a standard pattern of this format includes the symbol string 2K5B3B1B of the pattern shown in FIG. 1, the character name A of the standard pattern becomes a candidate character. In such a feature extraction method, the pattern “□” shown in Fig. 2 1 is as shown in Fig. 2 3.
It is indicated by a symbol string such as 2K4K6K0T, and is shown in Fig. 2.
The pattern "□" shown in is represented by a symbol string such as 2K3K5K6K7T as shown in FIG. 24. As shown by way of example in FIGS. 2, 3 and 4, the end points,
When a thin line narrowed at a branch point, etc. (hereinafter referred to as a line segment) has a bend or roundness, if the line segment is divided using the inflection point and expressed by the symbol sequence described above, an inflection point will occur. The position may become unstable, so the number of inflection points and the direction of the stroke change, and the number of symbol strings increases as described above even for similar patterns. In order to prevent an increase in the number of symbol strings to be described, if a standard pattern prepared in advance is written to include many symbol strings, a large number of candidate characters may be generated due to the description. Classification efficiency decreases, and as a result, the amount of feature lists written for each character for distinguishing these candidate characters increases, and if this is stopped, recognition becomes impossible. Further, Fig. 2 5 shows pattern "1" with a slight pattern on the upper part, Fig. 2 6 shows pattern "1" in which the upper stroke is linearly bent, and Fig. 2 7 shows pattern "2". In both cases, the symbol string extracted from the basic features mentioned above is as shown in Figure 2.8.
This example shows a case where the number is 2K5B6B2B. Since these three patterns are registered as candidate characters together with the basic features mentioned above, the feature list prepared for each character includes features to distinguish between the patterns in Fig. 2 5 and Fig. 2 6. Also included. Even for patterns that can be easily identified in this way, it becomes necessary to extract features to distinguish them from other patterns, which increases the amount of description for describing the feature amounts of the pattern and causes misreading.

As shown again in FIG. 2 6 and FIG. 2 7,
It is difficult to identify similar patterns whose difference is whether or not the character patterns are rounded, and no stable method has been found.

An object of the present invention is to solve the above-mentioned conventional drawbacks, and to divide a line segment narrowed at a characteristic point such as a curved or rounded end point or a branch point without using a refraction point. By doing so, it is an object of the present invention to provide a pattern feature extraction method that stably extracts features that are effective for identifying patterns having curvature or roundness without increasing the amount of description of pattern feature amounts.

According to the present invention, in a line segment narrowed by end points, branch points, etc., tracking is performed from characteristic points such as end points, branch points, etc. that are the starting points of the line segment, and tracking is performed from characteristic points such as end points, branch points, etc. sub-line differentiation determination means for detecting a line segment in which a ratio of the distance between the starting point and the end point of the line segment to the tracing length to the feature point is less than or equal to a set value; and a starting point of the line segment detected by the sub-line differentiation determination means. Tracking is performed until the end point, and the Y and X coordinate values of each tracking point are variables, and a function is expressed as a linear combination of them.
When detecting the values of F ₁ (X, Y) and F ₂ (X, Y), means for detecting a sub-line segment feature point based on a tracking point at which the function value thereof is maximum or minimum; integrating means for integrating sub-line segment feature points whose X and Y coordinate differences between the sub-line segment feature points and the start and end points of the line segment are both within a certain value, into the start and end points of the line; sub-line segment feature extracting means for dividing a line segment by sub-line segment feature points that are not integrated at the starting point and end point of a segment, and detecting feature quantities such as direction, length, etc. for the divided line segment; A pattern feature extraction method is obtained which is characterized by comprising the following.

The present invention will be described below with reference to specific embodiments. FIG. 3 is a block diagram showing an embodiment for realizing the pattern feature extraction method of the present invention. Reference numeral 1 denotes a pattern memory for storing a pattern for one character, in which pattern information that has undergone processing such as OCR photoelectric conversion and cutting is stored. 2 is a thinning pattern memory for storing the thinning pattern of pattern memory 1; Reference numeral 3 denotes a feature point detection means, which extracts feature points such as end points and branch points from the thinning pattern 2. 4 is a line segment feature extraction means, which traces the line segment narrowed between the feature points detected by the feature point detection means 3, and calculates the tracing length of the line segment obtained when tracing (hereinafter referred to as line segment arc length). ), the direction (hereinafter referred to as the line segment chord direction), and the distance (hereinafter referred to as the line segment chord length) between feature points are extracted and stored in the feature register 5. In addition, when tracing a line segment narrowed by feature points such as end points and branch points, the X, Y of each tracing point
The coordinate values are stored in the tracking point work memory 7 in the order of detection.

For example, the line segment feature extracting means 4 performs T1T2 for the pattern "K" shown in FIG.
sequence of feature points, chord direction 4 indicated by dotted line, from T1 to T
The line segment arc length L ₂ of the line segments up to 2, the line segment chord length L ₁ , the feature amount R indicating that the line segment is clockwise, etc. are extracted. Reference numeral 8 denotes a sub-line differentiation determining means, which detects a line segment in which the ratio of the line segment chord length to the line segment arc length stored in the feature register 5 is equal to or less than a certain value. Reference numeral 9 denotes a subline segment feature point extracting means, which sequentially stores the X and Y coordinate values of each tracking point from the starting point to the end point of the line segment detected by the subline differentiation determining means 8 into the tracking point work memory 7.
The function F ₁ is read out from
When the values of (X, Y), F ₂ (X, Y)...F _N (X, Y) are detected, subline segment feature points are determined based on the tracking point where the function value is maximum or minimum. It is a means of extraction. Reference numeral 10 denotes an integrating means, which extracts sub-line segments whose X and Y coordinate differences with the starting point and end point of the sub-line segment are both below a certain value, among the sub-line segment feature points detected by the sub-line segment feature point extraction means 9. It is a means of integrating feature points. Reference numeral 11 denotes a sub-line segment feature extraction means, which divides the line segment detected by the sub-line segment feature point extraction means 8 by the sub-line segment feature points obtained by the sub-line segment feature point extraction means 9 and the integration means 10. For the line segment (hereinafter referred to as sub-line segment), features such as the direction of the sub-line segment, the chord length of the sub-line segment, and the arc length of the sub-line segment are extracted, and the sub-line is normalized. minutes is stored in the feature register 12. Reference numeral 6 denotes a recognition unit, which recognizes the input pattern of one character by comparing the feature amounts extracted from the input pattern of one character and stored in the feature register 5 and the sub line segment feature register 12 with a dictionary prepared in advance. .

Using FIG. 4 and FIG.
0. The sub-line segment feature extracting means 11 will be specifically explained.

4. For the thinned pattern "K" in FIG. 1, the subline differentiation determination means 8 in FIG.
Arc length L ₂ and chord length L ₁ of the line segment narrowed at the end point of T2
Line segments for which the value of L ₁ /L ₂ is less than or equal to a certain value are detected, and the line segments for which the value of L ₁ /L ₂ is less than or equal to the certain value are divided as described later. FIG. 7 shows how the above-mentioned sub-line segment feature point extraction means is used in FIGS. 1 and 2.
2 is a diagram used to extract subline segment feature points from a line segment narrowed by end points T ₁ and T ₂ shown in FIG. In Figures 7 1 and 2, circles and black circles in the figures indicate each tracking point (including end points), and the position of each tracking point is determined by the X coordinate value (the right direction is positive) and the Y coordinate value. (The downward direction is positive).
Here, the tracing direction of the line segment narrowed by the end points T ₁ and T ₂ is the direction starting from the end point T ₁ and sequentially reaching the end point T ₂ , as shown by the arrow in the figure. First, a function F ₁ that uses the X and Y coordinate values of each tracking point as variables
Assume that the function Y+X (FIG. 7 1) and the function Y- _X (FIG. 7 2) are used as one of (X, Y) and F 2 (X, Y). Here, the value F ₁ of the function Y+X (=Y+
X) moves each tracking point diagonally to the right as shown in Figure 7.1.
This shows the Y coordinate value when projected onto the Y coordinate axis from a 45 degree direction. Similarly, the value F ₂ of the function Y−X
(X, Y) (=Y-X) is as shown in Fig. 72,
This shows the Y coordinate value when each tracking point is projected onto the Y coordinate axis from a diagonal of 45 degrees to the left.

In addition, the functions F ₁ (X, Y) and F ₂ (X, Y) are as described above.
It can be applied to any angle from 0 degrees to 90 degrees, even if it is not 45 degrees. That is, the function F(X,
Y)=aX+bX (however, a, b are 0, ±1, ±2,...
) can also be used for sub-line segment feature extraction, which will be described later.

Next, referring to FIG. 71, the function F ₁ (X,
A sub-line segment feature extraction process using Y)=X+Y will be explained. In the figure, the function value F ₁ (X, Y) (=X+Y) uses the X and Y coordinate values of tracking point P ₁ as variables.
is the value indicated by F ₁ (P ₁ ). Therefore, the end point T ₁
The function value F ₁ (X,
Y), as is clear from Fig. 7 1, the minimum value F ₁ (MIN) is taken at the end point T ₁ , and the tracking point P ₂
will take the maximum value F ₁ (MAX).

That is, the end point T ₁ and the tracking point P ₂ are extracted as subline segment feature points. Note that among the sub-line segment feature points extracted in FIG. 71, the end point T ₁ is also the starting point of the line segment, so the end point T ₁ is excluded from the sub-line segment feature points. That is, it means being integrated at the starting point and ending point of each line segment in the above-mentioned integrating means. Similarly, with reference to FIG. 7 2, the function
A subline segment feature extraction process using F ₂ (X, Y)=Y−X will be explained. In the figure, the function value F ₂ (X, Y) uses the X and Y coordinate values of tracking point P ₅ as variables.
(=Y−X) becomes the value indicated by F ₂ (P ₅ ). Therefore, when the function value F ₂ (X, Y) of each tracking point is calculated sequentially from the end point T ₁ in the direction of the arrow, as is clear from FIG. 7 2, the tracking points P ₁ , P ₂ , P ₃ , The minimum value F ₂ (MIN) is taken at P ₄ , and the maximum value F ₂ (MAX) is taken at the end point T ₂ .

Therefore, the tracking points P ₁ , P ₂ ,
P ₃ , P ₄ and end point T ₂ are extracted, but tracking point P ₁ ,
Since it is sufficient to register any one of P ₂ , P ₃ , and P ₄ as a sub-line segment feature point, in this application, only the first detected tracking point P ₁ is extracted as a sub-line segment feature point. . Furthermore, as in the case of Fig. 7 1, Fig. 7 2
The end point T ₂ of will be excluded from the subline segment feature points.

As explained using FIG. 7, FIG.
4 is a diagram showing sub-line segment feature points extracted by the sub-line segment feature point extracting means 9 of FIG. 3 for the pattern "K" of FIG. 1; In addition, functions F ₁ (X, Y), F ₂ (X, Y) whose variables are the X and Y coordinate values of each tracking point.
Assume that X+Y and Y-X are used in the same way as in FIG. In Fig. 4, C ₁ , C ₂ , C ₃ , and C ₄ are the end points for the X and Y coordinate values of each tracking point, respectively.
When tracing from T ₁ , the tracing point where X+Y is the minimum value, the tracing point where Y-X is the minimum value, the tracing point where X+Y is the maximum value, the tracing point where Y-X is the maximum value, that is, the subline segment Shows feature points. Incidentally, if a plurality of tracking points having the same minimum (or maximum) value of X+Y (or Y-X) are detected, the first detected tracking point is taken. _The integrating _{means 10} in FIG _.
Of the two sub-line segment feature points, C ₁ and C ₄ are integrated into end point T1 and end point T2, and by using the sub-line segment feature points C ₂ and C ₃ , the line segment from end point T1 to end point T2 is It is divided into three sub-line segments S1, S2, and S3. For a character pattern with an inclination _, such as _the thinned pattern "7" in FIG.
An example of finding subline segment feature points using Y and XY is shown. In the figure, C ₁ , C ₂ , C ₃ , and C ₄ are the tracking points where X+Y is the minimum value, the tracking point where Y-X is the minimum value, the tracking point where X+Y is the maximum value, and Y-
X is the tracking point where the maximum value is reached. For the thinned pattern “7” in Fig. 4, the sub-line segment feature points
C ₄ is integrated with the end point T2, which is the end point of the line segment, and further, the sub-line segment feature points C ₂ and C ₃ where the X and Y coordinate differences between the sub-line segment feature points are both below a certain value are integrated, and the By using the integrating means 10 of FIG. 3 to select the sub-line segment feature point C ₂ for which the sum of the representative point and the X and Y coordinate values is small, the end point is determined using the sub-line segment feature points C ₁ and C ₂ . The line segment from T1 to end point T2 can be divided into three subline segments S1, S2, and S3. Fourth
As shown in FIG. 5 as an example, among the sub-line segment feature points obtained by the sub-line segment feature point extracting means 9 of FIG. When line segment feature points occur, the line segment can be stably divided by integrating the subline segment feature points by the integrating means 10 shown in FIG. 3.

FIGS. 3 and 4 show examples of feature amounts obtained by the sub-line segment feature amount extracting means 9 of FIG. 3 for the patterns of FIGS. 6 and 7, respectively.

4. FIG. 3 shows a line segment from the end point T1 to the branching point B (the arc length of the line segment is M) as a sub line obtained by the sub line segment feature point extracting means 9 and the integrating means 10 of FIG. The line segment is divided into two sub-line segments using the minute feature point C ₂ (indicates the tracking point where the function Y-X is the minimum), and the line segment narrowed to the end point T1 and the sub-line segment feature point C ₂ , the sub-line Of the line segment narrowed by minutiae point C ₂ and branch point B ₂ ,
For the line segment narrowed between the subline segment feature point C ₂ and the branch point B, the subline segment chord direction 4, subline segment chord length M ₁ , and subline segment arc length M ₂ are detected and normalized features. The values M ₂ /M, M ₁ /M ₂ and the minor chord direction 4 are obtained. Similarly, regarding Fig. 4, for the line segment narrowed to subline segment feature point C ₂ and branch point B, subline segment chord direction 4, subline segment chord length
N ₁ , sub-line segment arc length N ₂ is detected, and the normalized feature value N ₂ /N (N indicates the line segment arc length from end point T1 to branch point B), N ₁ /N ₂ and sub-line segment A line segment chord direction 4 is obtained. The patterns shown in FIGS. 4 and 4 can be identified by using the feature values M ₁ /M ₂ and N ₁ /N ₂ described above.

FIG. 5 is a block diagram showing a first embodiment of the present invention, which includes the sub-line segmentation determination means 8, sub-line segment feature point extraction means 9, integration means 10, and sub-line segment feature amount extraction means shown in FIG. 11 is a diagram showing an example of a specific implementation circuit.

Note that the sub-line segment feature points are detected using X+Y, Y-X as functions with the X and Y coordinate values of each tracking point as variables, and the sub-line segment is calculated as a feature amount for the detected sub-line segment. FIG. 7 is a circuit diagram in which the number of divisions, the sub-line segment chord length, the sub-line segment arc length, and the sub-line segment chord direction are detected.

In FIGS. 5 and 6, the signal on the signal line is indicated by adding S after the number of the signal line. Reference numerals 20, 21, 43, and 44 are a one-line segment arc length storage register, a one-line segment chord length storage register, a one-line segment end point storage register, and a one-line segment start point storage register, respectively. 1 line segment length storage register 20
The line segment arc length of one line is stored in the feature register 5 in which the line segment arc length of one character pattern in FIG. 3 is stored in the order of detected line segments by the control circuit 100.
is read from and stored. Similarly, the 1-line segment chord length storage register 21, the 1-line segment start point storage register 44, and the 1-line segment end point storage register 43 each contain the line segment chord length of the 1-line segment, and the X and Y coordinates of the starting point of the 1-line segment. value, the X and Y coordinate values of the end point of one line segment are the control circuit 1
00, the line segment chord length for one character pattern shown in FIG. be done. Subline differentiation determination means 8
are the division circuit 22 and the expansion setting value storage register 2.
3. Consists of a comparison circuit. The control circuit 100 transfers the contents of the one-line segment length storage register 20 and the one-line segment chord length storage register 21 to the division circuit 22 . The division circuit 22 divides the contents of the one-line chord length storage register 21 by the contents of the one-line arc length storage register 20 and transfers the resulting value to the comparison circuit 24 . The comparison circuit 24 compares the contents of the bulge setting value storage register 23 and the output value of the division circuit 22, and determines whether the output value of the division circuit 22 is equal to the bulge setting value storage register 2.
If the content is smaller than the content of 3, "1" is output from the output signal 241S, and if it is larger, the control circuit 100 outputs the 1-line arc length storage register 20, the 1-line chord length storage register 21, and the 1-line segment end point storage register 4.
3. The chord length of the next detected line segment, the chord length, and the X and Y coordinate values of the starting point and ending point are transferred to the line segment starting point storage register 44 from the feature register 5 in FIG.

That is, the sub-line differentiation determination means 8 determines whether the line segment has a bulge or bend exceeding a certain level, based on the feature value obtained by dividing the chord length value of the line segment narrowed at an end point, branch point, etc. by the line segment arc length value. It is detected whether or not there is, and if there is, "1" is outputted from the output signal 241S. Comparison circuit 2
When "1" is output from the output signal 241S of 4, the control circuit 100 selects the tracking point corresponding to the starting point of the line segment that is the content of the 1-line segment starting point storage register 44 from the tracking point storage work memory 7 at regular intervals. From then on, the X and Y coordinate values of each tracking point are read out in order and stored in the work register 25. Further, when "1" is output from the output signal 241S, the 1-bit flip-flop circuit 17 becomes "1", and the output signal 17 becomes "1".
Since 1S becomes "1", the gate circuit 40 is opened and the contents of the work register 25 are transferred to the addition circuit 18 and subtraction circuit 19. The adder circuit 18 adds the X and Y coordinate values of the tracking point, which are the contents of the work register 25, and transfers the result to the register 26. The subtraction circuit 19 subtracts the X coordinate value from the Y coordinate value of the tracking point and transfers it to the register 31.

The minimum addition value storage register 27 and the maximum addition value storage register 28 each store the minimum sum of the X coordinate value and the Y coordinate value of the tracking point immediately before the tracking point stored in the work register 25 from the starting point of the line segment. The subtraction minimum value storage register 32 and the subtraction maximum value storage register 35 respectively store the X coordinate value from the starting point of the line segment to the tracking point one before the tracking point stored in the work register 25. Store the minimum and maximum values of the difference in Y coordinate values. Furthermore, the addition maximum value storage register 28 and the subtraction maximum value storage register 3
5 is initially “0” and is added to the minimum addition value storage register 2.
7 and the subtraction minimum value storage register 32, a set value that is greater than or equal to the maximum value of the sum and difference of the X and Y coordinate values is initially stored.
The comparison circuit 29 checks whether the contents of the register 26 are smaller than the contents of the minimum addition value storage register 27, and if the contents of the register 26 are smaller than the contents of the minimum addition value storage register 27, the output signal 291S is output.
becomes “1”.

The comparison circuit 30 checks whether the contents of the register 26 are larger than the contents of the maximum addition value register 28, and if the contents of the register 26 are larger than the contents of the maximum addition value storage register 28, the output signal 301 is
S becomes "1". The comparison circuit 33 checks whether the contents of the register 31 are smaller than the contents of the minimum subtraction value storage register 32, and if the contents of the register 31 are smaller than the contents of the minimum subtraction value storage register 32, the output signal 331S becomes "1". Become. Comparison circuit 3
4, it is checked whether the contents of the register 31 are larger than the contents of the maximum subtraction value storage register 35, and if the contents of the register 31 are larger than the contents of the maximum subtraction value storage register 35, the output signal 341S becomes "1". That is, the sub-feature point detection means 1003 detects the sum and difference between the X and Y coordinate values of the tracking point stored in the work register 25, and stores the sum and difference in the work register 25 from the starting point of the line segment. The output signal 291 is output depending on whether it is larger or smaller than the maximum or minimum value of the sum and difference between the X coordinate value and the Y coordinate value up to the tracking point one before the tracking point.
S, 301S, 331S, and 341S become "1".

When the output signal 291S of the comparison circuit 29 becomes "1", the gate circuit 36 opens, and the contents of the register 26 are transferred to the addition minimum value storage register 27, and the gate circuit 50 opens, and the contents of the work register 25 are transferred to the sub-feature point. First stage 451 of storage register 45
will be forwarded to. Output signal 331S of comparison circuit 33
When becomes "1", the gate circuit 38 and gate circuit 49 are opened, the contents of the register 31 are transferred to the subtraction minimum value storage register 32, and the contents of the register 31 are transferred to the subtraction minimum value storage register 32.
The contents of 5 are stored in the second stage 4 of the sub minutiae storage register 45.
52. Output signal 30 of comparison circuit 30
When 1S becomes "1", the gate circuit 37 and the gate circuit 48 are opened, the contents of the register 26 are transferred to the maximum addition value storage register 28, and the contents of the work register 25 are transferred to the third stage 453 of the sub feature point storage register 45. will be forwarded to.

When the output signal 341S of the comparison circuit 34 becomes "1", the gate circuit 39 and the gate circuit 47 are opened, the contents of the register 31 are transferred to the subtraction maximum value storage register 35, and the contents of the work register 25 are stored as sub-minus point storage. It is transferred to the fourth stage 454 of the register 45. The control circuit 100 outputs "1" from the control signal 102S after the time from when the contents of the tracking point storage work memory 7 were transferred to the work register 25 to when the contents of the work register 25 were transferred to the sub-minutiae storage register 45 has elapsed. ” and at the same time outputs the next tracking point X, from the tracking point storage work memory 15.
The Y coordinate value is read into the work register 25.

When "1" is output from the control signal 102S, the gate circuit 95 is opened, and the contents of the work register 25 and the contents of the line segment end point storage register 43 are compared in the comparison circuit 42. The comparison circuit 42 compares the contents of the line segment end point storage register 43 and the work register 2.
It is checked whether the contents of 5 are equal, and if they are equal, the output signal 421S becomes "1".

At the time when the output signal 421S of the comparison circuit 42 becomes "1", the first stage 451 of the sub-minutiae storage register 45 stores the tracking points whose sum of the X coordinate value and the Y coordinate value of the tracking points is the minimum. The X and Y coordinate values of the first detected tracking point are displayed in the second row 452.
Among the tracking points where the difference between the coordinate value and the X coordinate value is the minimum, the X and Y coordinate values of the first detected tracking point are 3
The row 453 shows the X and Y coordinate values of the first detected tracking point among the tracking points where the sum of the X and Y coordinate values of the tracking point is maximum, and the fourth row 454 shows the X and Y coordinate values of the tracking point. Among the tracking points with the largest difference between the Y and X coordinate values, the X and Y coordinate values of the first detected tracking point are stored. Output signal 421 of comparison circuit 42
When S becomes "1", the control circuit 100 outputs the control signal 103S, the 1-bit flip-flop circuit 17 becomes "0", and reading from the tracking point storage work memory 15 is stopped.

Next, the control circuit 100 outputs the control signal 105S, and the 1-bit flip-flop circuit 66 becomes "0".
is reset to sub minutiae storage register 4.
The contents of the first stage 451 of 5 are transferred to the subtraction circuit 69. The counter 55 is the sub-minutiae storage register 4
When the contents of 5 are transferred to the subtraction circuit 69, the count is increased by 1 by the control signal 106S. On the other hand, in the subtraction circuit 69, when the 1-bit flip-flop circuit 66 is "1", the gate circuit 67 is open.
The contents of the end point memory register 43 are transferred, and when the 1-bit flip-flop circuit 66 is "0", the output signal 971S of the inverter 97 becomes "1", the gate circuit 68 is opened, and the start point memory register 44 is transferred.
The contents of will be transferred. Initially, the value of the 1-bit flip-flop circuit 66 is "0", so the contents of the starting point storage register 44 are transferred to the subtraction circuit 69. The subtraction circuit 69 extracts the X (Y) coordinate value which is the content of the start point storage register 44 or the end point storage register 43 and the first stage 451 of the sub-minutiae storage register 45.
The difference between the X (Y) coordinate value and the content of is calculated.
The comparison circuit 160 compares the contents of the register 150 storing a constant value with the output of the subtraction circuit 69
Alternatively, the absolute value of the difference between the Y coordinate values is compared, and if both the absolute values of the difference between the X and Y coordinate values output from the subtraction circuit 69 are smaller than the contents of the register 73, the integrated signal 162S becomes "1".

When the integrated signal 162S becomes "1", the selection circuit 56 sets the contents of the Nth stage (N=1...4) of the sub feature point storage register 45 transferred to the subtraction circuit 69 to "0" according to the contents of the counter 55. Clear to. After the output value of the subtraction circuit 69 and the contents of the register 150 are compared in the comparison circuit 160, the control circuit 100 compares the output value of the subtraction circuit 69 with the contents of the register 150, and then compares the output value of the subtraction circuit 69 with the contents of the register 150.
The content of is transferred to the subtraction circuit 69, and the control signal 10
By 6S, the counter 55 is incremented by 1 and becomes "2". Similar operations are performed below,
When the contents of the fourth stage 454 of the sub feature point storage register 45 are transferred to the subtraction circuit 69 and the output value of the subtraction circuit 69 and the contents of the register 150 are compared in the comparison circuit 160, the control circuit 100 outputs the control signal. 1
05S and a control signal 107S, the 1-bit flip-flop circuit 66 is set to "1", the counter 55 is cleared to "0", and the first stage 451 of the sub feature point storage register 45 is set to the subtraction circuit 69. will be forwarded to. Furthermore, the control signal 106S is output, and the counter 55 counts up by one.
Since the 1-bit flip-flop circuit is at "1", the contents of the end point storage register 44 are transferred to the subtraction circuit 69. Similar operations are performed thereafter.

The contents of the fourth stage 454 of the sub feature point storage register 45 are transferred to the subtraction circuit 69, and when the output value of the subtraction circuit 69 and the contents of the register 150 are compared in the comparison circuit 160, the control signal 105S and the control signal 107S are transferred. is output, the 1-bit flip-flop circuit 66 is set to "0", and the counter 5
5 is cleared and the control circuit 100
The contents of the first stage 451 of the sub feature point storage register 45 are sent to the register 51, the contents of the second stage 452 are sent to the register 52, and the contents of the third stage 453 are sent to the register 53.
Then, the contents of the fourth stage 454 are transferred to the register 54, respectively. That is, if the difference between the X, Y coordinate values of the sub feature point stored in the sub feature point register 45 and the X, Y coordinate values of the starting point and end point of the line segment is within a certain value, the integrating means 10 outputs the result from the comparing circuit 160. Integrated signal 16
2S is output, and the X and Y coordinate values of the sub-feature point are cleared. Next, the control circuit 100 obtains the X and Y coordinate values of each tracking point at regular intervals from the tracking point storage work memory 7 in order from the tracking point corresponding to the starting point of the line segment, which is the content of the starting point storage register for one line segment. Reading is started and the data is stored in the work register, and at the same time, the control signal 108S becomes "1" and the output signal 181S of the 1-bit flip-flop circuit 18 becomes "1".
When the signal 181S becomes “1”, the gate circuit 79
opens and the contents of work register 25 are transferred to register 7.
Transferred to 5. The comparison circuit 71 checks whether the contents of the register 51 and the contents of the register 75 are equal. If they are equal, the output signal 711S becomes "1". The comparison circuit 72 checks whether the contents of the register 52 and the contents of the register 75 are equal. If they are equal, the output signal 721S becomes "1".

The comparison circuit 73 checks whether the contents of the register 53 and the contents of the register 75 are equal. If they are equal, the output signal 731S becomes "1". The comparison circuit 74 checks whether the contents of the register 54 and the contents of the register 75 are equal. If they are equal, the output signal 741S becomes "1". The register 77 stores the X, Y coordinate values of the tracing point detected immediately before the tracing X, Y coordinate values stored in the register 75 when tracing from the starting point of the line segment. First, register 77 and register 93
The X and Y coordinate values of the starting point of the line segment are set.
78 is a distance calculation circuit between tracking points, and register 7
2 from the X, Y coordinate values of the tracking point stored in 7 and the X, Y coordinate values of the tracking point stored in register 75.
The distance between the two tracking points is calculated and transferred to register 81. The adder circuit 82 adds the contents of the register 81 and the contents of the register 83 and transfers the result to the register 83. The control circuit 100 receives a control signal 109S.
In order to output "1", the gate circuit 80 is opened and the contents of the register 75 are transferred to the register 77. When the contents of register 75 are transferred to register 77, the contents of work register 25 are transferred to register 75. Comparison circuit 7N (N=1...4)
When the output signal 7N1 (N=1...4) becomes "1", the gate circuit 6N (N=1...4) opens and the contents of the register 5N (N=1...4) are transferred to the register 94. Furthermore, the control signal 111S becomes "1", the gate circuit 60 is opened, and the register 83 becomes "5".
The data is transferred to the sub-line branch length storage register 84, which is a shift register of the stage, and the register 83 is cleared to "0" by the control signal 113S. Reference numeral 92 denotes a direction quantization circuit between two points, which uses the X and Y coordinate values of the sub-feature point stored in the register 94 and the X and Y coordinate values of the sub-feature point stored in the register 93 to determine the direction as shown in FIG. The signal is quantized in the direction shown in , and transferred to a direction register 98 consisting of a five-stage shift register. 91 is a distance calculation circuit, which calculates the distance from the X and Y coordinate values of the sub-feature point, start point, and end point indicated by the contents of registers 93 and 94;
The data is transferred to a sub line segment chord length storage register 84 consisting of a five stage shift register. Next, the control signal 115S becomes “1” from the control circuit 100, and the gate circuit 9
5 is opened, the contents of register 94 are transferred to register 93, and counter 49 is incremented by one.

A counter 49 counts the number of sub-line segments.

The comparison circuit 76 checks whether the contents of the register 75 and the contents of the 1-line segment end point storage register 43 are equal or not, and if they are equal, the 1-line segment end signal 761 is output.
S is output.

When the 1-line segment end signal 761S is output, the gate circuit 65 opens and the 1-line segment end point storage register 43
The contents of are transferred to register 94. After a certain period of time, the control circuit 100 stores the sub line segment length storage register 8.
The contents of 4 are sequentially transferred to the division circuit 85. The division circuit 85 divides the contents of the sub-line segment length storage register 84 by the contents of the one-line segment length storage register 20 (signal lines are omitted), and transfers the result to the sub-line segment normalized arc length storage register 86. Ru.

Further, the control circuit 100 sequentially transfers the contents of the sub-line segment length storage register 84 and the contents of the sub-line segment chord length storage register 87 to the division circuit 88. Division circuit 88
divides the contents of the subline segment chord length storage register 87 by the contents of the subline segment arc length storage register 84 and transfers the result to the subline segment bulge storage register 89.

Further, the control circuit 100 transfers the contents of the counter 49 to the sub-feature point storage register 99, and clears it by the control signal 116S. Next, the control circuit 100
The control signal 108S is output, and the 1-bit flip-flop circuit 18 becomes "0".

That is, the sub-line segment feature extracting means 11 divides the line segment narrowed by the feature points such as end points and branch points by the integrating means 10 using the X and Y coordinate values of the sub-feature points that have not disappeared. , detect the sub-line segment arc length and sub-line chord length for the divided line segment (sub-line segment), normalize with the line segment arc length and sub-line segment chord length, respectively, and further,
The chord direction of the sub-line segment and the number of divisions of the sub-line segment are detected.

The sub line segment direction storage register 98, the sub line segment normalized arc length storage register 86, the sub line segment bulge storage register 89, and the sub line segment division number storage register 99 are the sub line segment feature storage register 12 in FIG. corresponds to

The control circuit 100 stores the arc length, chord length, and X and Y coordinate values of the starting point and ending point of the next detected line segment from the characteristic register 5 in FIG.
It is transferred to the 1-line segment chord length storage register 21, the 1-line segment start point storage register 44, and the 1-line segment end point storage register 43.

Similar operations are performed thereafter.

FIG. 6 is a block diagram of a second embodiment of the present invention, in which the integration means 10 of FIG. The sub-line segment feature points that are As a representative point of a line segment feature point, use a subline segment feature point with a small sum of the X and Y coordinate values of the subline segment feature point, and integrate and describe a large number of subline segment feature points that are unnecessary for recognition. To reduce the amount
FIG. 6 is a block diagram of a modification of the embodiment shown in FIG. 5; In FIG. 6, the work register 25, 1-bit flip-flop circuits 17 and 18, comparator circuit 42, and gate circuits 40 and 79 of FIG. 5 are shown in one block diagram 200. Further, the control signals used in FIG. 5 are omitted except for the control signal 105S. As mentioned above, 21, 20, 43, and 44 in the figure are each 1
These are a line segment chord length storage register, a 1-line segment chord length storage register, a 1-line segment end point storage register, and a 1-line segment start point storage register, 8 is a sub-line differentiation determination means, 9 is a sub-line segment feature point extraction means, and 11 12 is a sub line segment feature extracting means, 12 is a sub line segment feature register, and 45 is a sub line segment feature point storage register.

Assume that the sub-line segment feature points obtained by the sub-line segment feature point extracting means 9 are set in the sub-line segment feature point storage register 45 as described above. Control circuit 100 outputs control signals 105S and 120S, 1-bit flip-flop circuit 302 is reset to "0", and 1-bit flip-flop circuit 303 is set to "1". Further, the control circuit 100 outputs a control signal 121S and a control signal 122S,
Set counter 304 and counter 305 to “0”
Reset to . In the register 306, when the 1-bit flip-flop circuit 302 is "1", the gate circuit 402 is opened, and when the 1-bit flip-flop circuit 303 is "1", the gate circuit 403 is opened.
When the 1-bit flip-flop circuit 302 is "0", the inverter 404 opens the gate circuit 405, and the 1-bit flip-flop circuit 303 becomes "1". Then, the gate circuit 403 is also opened and the contents of the starting point storage register 44 are transferred.
Initially, the value of the 1-bit flip-flop circuit 302 is "0" and the value of the 1-bit flip-flop circuit 303 is "1", so the contents of the start point storage register 44 are transferred to the register 306.

If the value of the counter 305 is “0”, the selection circuit 307 selects the sub line segment feature point storage register 45.
If the value of the counter 305 is "1", the contents of the first row 451 are stored in the sub line segment feature point storage register 4.
The contents of the second stage 452 of No. 5 are selected as follows, the control signal 124S is output from the control circuit 100, and is transferred to the register 306 with the gate circuit 406 open. When the value of the counter 304 is "0", the selection circuit 308 stores the contents of the first stage 451 of the sub line segment feature point storage register 45, and when the value of the counter 304 becomes "1", it stores the contents of the sub line segment feature point memory. The contents of the third row 452 of the register 45 are...
According to the value of the counter 304, the contents of the sub line segment feature point storage register 45 are stored in the register 30.
9 transfers. Initially, the value of the counter 304 is “0”, so the sub line segment feature point storage register 45
The contents of the first stage 451 are transferred to the register 309. When values are set in registers 306 and 309, the contents of register 306 and register 30
9 is transferred to the subtraction circuit 310. The subtraction circuit 310 extracts the contents of the register 306, X(Y)
The difference between the coordinate value and the X (Y) coordinate value that is the contents of the register 309 is calculated. The comparison circuit 315 compares the contents of the register 312 in which a constant value is stored with the absolute value of the difference between the X or Y coordinate values output from the subtraction circuit 310, and calculates the X and Y coordinate values output from the subtraction circuit 310. The absolute value of the difference is both in register 3.
If it is smaller than the contents of 12, its output signal 502S
becomes “1”. Output signal 50 of comparison circuit 315
When 2S becomes "1" and the 1-bit flip-flop circuit 303 is "1", the gate circuit 409
is opened, and the end point/start point integrated signal 1001S becomes 1. When the end point/start point integrated signal 1001S becomes "1", the output signal 503S of the OR circuit 416 becomes "1", the gate circuit 415 is opened, the contents of the counter 304 are transferred to the decoder 322, and the control signal 122S becomes "1". ” is output.
The decoder 322 clears the contents of the Nth stage (N=1...4) of the sub line segment storage register 45 to "0" according to the value of the counter 304 or the counter 305 using the output signal 522S of the decoder 322. That is, the sub line segment feature points to be integrated are cleared to "0" by the output signal 522S of the decoder 22. After the contents of the subtraction circuit 310 are compared in the comparison circuit 315, the counter 304 is incremented by one. Next, the selection circuit 308 transfers the contents of the Nth stage (N=1 . . . 4) of the sub line segment feature point storage register 45 to the register 309 according to the value of the counter 304. The value of the counter 304 becomes 3, the value of the fourth stage 454 of the sub line segment feature point storage register 45 is read out to the register 309, and initially the register 306 in which the contents of the starting point storage register 44 are stored is a subtraction circuit. 310 and compared in the comparison circuit 315, the 1-bit flip-flop circuit 302 is set to "1" by the control signal 105S, the gate circuit 402 is opened, and the contents of the end point storage register 43 are transferred to the register 306.
will be forwarded to. Control signal 12 from control circuit 100
1S is output and the counter 304 is cleared to "0".

Similarly, the value of the counter 304 becomes "3" and the value of the sub-line segment feature point storage register 45 becomes "4".
The value of row 454 is read out to register 309,
After the contents of the end point storage register 44 and the register 306 stored therein are transferred to the subtraction circuit 310 and compared in the comparison circuit 315, the 1-bit flip-flop circuit 303 is reset to "0" by the control signal 120S. , the gate circuit 403 closes, and the 1-line segment start point and 1-line segment end point storage register 4
Transfer from 3 and 44 to register 306 is stopped. When the 1-bit flip-flop circuit 303 is reset to "0", the control circuit 100
The contents of the counter 305 (initially reset to "0") are transferred to the adder circuit 318 (the signal line is omitted), and the control signal 125S becomes "1", opening the gate circuit 407. The adder circuit 318 adds the value of the 1-bit flip-flop circuit 319 in which the set value "1" is stored and the contents of the counter 305, and transfers the result to the counter 304 when the gate circuit 407 opens.

Further, when the 1-bit flip-flop circuit 303 is reset to "0", the control signal 124S becomes 1, the gate circuit 406 is opened, and the selection circuit 307 selects the subline segment feature point according to the contents of the counter 305. Nth stage of storage register 45 (N=1...
4) is selected and set in the register 306. On the other hand, in accordance with the value of the counter 304, the selection circuit 308 selects the sub line segment feature point storage register 45.
The contents of the Nth stage (N=1...4) are selected and set in the register 309. When values are set in register 306 and register 309, the contents of register 306 and register 30 are set as described above.
9 is transferred to the subtraction circuit 310, and the comparison circuit 315 compares the contents of the subtraction circuit 310 with the contents of the register 312.

When the output signal 502S of the comparison circuit 315 becomes "1", since the 1-bit flip-flop circuit 303 has been reset to "0", the inverter 4
12, the output signal 100 of the AND circuit 408
4S becomes 1, gate circuit 413 and gate circuit 414 are opened, and the contents of register 306 and register 309 are transferred to adder circuit 313 and adder circuit 314, respectively. The addition circuit 313 adds the X and Y coordinate values of the subline segment feature points, which are the contents of the register 306, and transfers the result to the comparison circuits 316 and 317.

The addition circuit 314 adds the X and Y coordinate values of the subline segment feature points, which are the contents of the register 309,
It is transferred to comparison circuit 316 and comparison circuit 317.

Comparison circuit 316 checks whether the output of addition circuit 314 is smaller than the output of addition circuit 313, and if the output of addition circuit 314 is smaller than the output of addition circuit 313, its output signal 1003S becomes "1". When the signal 1003S becomes "1", the gate circuit 418 opens and the contents of the counter 305 are transferred to the decoder 322, and the control signal 122
S becomes "1", and the output signal 5 of the decoder 322
22S, the Nth stage (N=1) of the sub-line segment feature storage register 45 corresponding to the contents of the counter 305 is
...The contents of 4) are cleared to "0".

The output signal 1002S of the comparison circuit 317 becomes "1" when the output of the addition circuit 314 is equal to the output of the addition circuit 313 or when the output of the addition circuit 314 is larger than that of the addition circuit 313. signal 1
When 002S becomes "1", the output signal 503S of the OR circuit 416 becomes "1", and the gate circuit 41
5 opens, the contents of the counter 304 are transferred to the decoder 322, the control signal 122S becomes "1", and the output signal 522 of the decoder 322
According to the contents of the counter 304, the Nth stage (N=1...
The contents of 4) are cleared to "0".

After the contents of the subtraction circuit 310 are compared in the comparison circuit 315, the counter 304 is incremented by 1, and the selection circuit 308 increases the count of the counter 304.
The contents of the subline segment feature point storage register 45 corresponding to the value of 4 are transferred to the register 309.

In the same manner, the counter 304 becomes "3" and the fourth stage of the sub line segment feature point storage register 45 is "4".
54 is transferred to the register 309, the contents of the register 306 and the contents of the register 309 are transferred to the subtraction circuit 310, and compared in the comparison circuit 310. When the counter 305 is counted up by 1, the control circuit 100 transfers the contents of the counter 305 to the adder circuit 318, and the control signal 125S becomes “1” and the gate circuit 40
7 opens, counter 304 has counter 30
Sets the value obtained by adding 1 to the contents of 5. Similarly, the contents of the counter 305 are changed to control signal 1.
This continues until it reaches "3" by 30S.

When the counter 305 reaches "3", the contents of the sub-line segment feature point storage register 45 are transferred to the sub-line segment feature extraction means 11 as described above.

As described above, according to the present invention, a line segment narrowed by a feature point such as a curved or rounded end point or a branch point is divided, and the feature value is calculated for the divided line segment. By detecting this, it becomes possible to stably identify a pattern having a bend or roundness without increasing the amount of description of the feature amount of the pattern.

[Brief explanation of the drawing]

Figure 1 is a diagram explaining the basic features of the conventional system, Figure 2 is a diagram explaining the basic features of the conventional
The figure shows an example of a pattern obtained from conventional basic features, Figure 4 is a diagram explaining feature points and feature quantities obtained by applying the present invention, and Figures 3 and 5 are A block diagram showing the first embodiment of the present invention, FIG. 6 is a block diagram showing a second embodiment of the present invention in which the integrating means of FIG. 5 is modified, and FIG. 7 is a block diagram showing the extraction of subline segment feature points. It is a figure explaining a method. In the figure, 1 is a pattern memory, 2 is a thinning pattern memory, 3 is a feature point extraction means, 4 is a line segment feature amount extraction means, 5 is a feature register, 6 is a recognition unit, 7 is a tracking point storage work memory, 8 9 is a sub line segment feature point extraction means; 10 is an integration means; 11 is a sub line segment feature extraction means; 12 is a sub line segment feature register; 20 is a one line segment arc length storage register; 21 is a 1 line segment chord length storage register, 43 is a 1 line segment end point storage register, 44 is a 1 line segment start point storage register, 45 is a sub line segment feature point storage register, 86 is a sub line segment normalized arc length storage register, 89 is a sub line segment bulge storage register, 98 is a sub line segment direction storage register, 99 is a sub feature point number storage register, and 100 is a control circuit.

Claims (1)

[Claims] 1. A pattern that thins an input pattern of one character, detects feature points such as end points and branch points from the thinned pattern, and extracts feature amounts by referring to the input pattern and the thinned pattern. In the feature extraction method, a thin line narrowed by the feature points (hereinafter referred to as a line segment) is traced from the feature point that is the starting point of the line segment, and a feature that is the end point of the line segment is traced from the starting point of the line segment. A line segment in which the tracing length leading to a point and the distance between the starting point and the ending point of the line segment are detected, and the ratio of the distance between the starting point and the ending point of the line segment to the tracing length is less than or equal to a set value. a subline differentiation determination means for detecting;
A function F ₁ that traces from the starting point of the line segment detected by the sub-line differentiation determining means to the end point of the line segment, uses the X coordinate value and Y coordinate value of each tracing point as variables, and is expressed as a linear combination thereof. (X, Y), F ₂ (X, Y),
...Means for extracting a sub-line segment feature point based on a tracking point at which the value of the function is maximum or minimum when the value of F _N (X, Y) is detected; means for integrating the sub-line segment feature points whose X and Y coordinate differences with the starting point and end point of the line segment are both within a certain value, into the starting point and ending point of the line segment; and sub-line segment feature extraction means for dividing the line segment by the sub-line segment feature point that is not integrated at the end point and extracting the feature amount for the divided line segment. Pattern feature extraction method. 2. As a sub line segment feature extracting means, tracking is performed from the number of divided line segments, the direction between two points from the start point to the end point of the divided line segment, and the starting point of the divided line segment. , the feature amount obtained by dividing the tracing length from the starting point to the ending point of the divided line segment by the tracing length of the divided line segment, and the distance between the two points, the starting point and the ending point, of the divided line segment. 2. The pattern feature extraction method according to claim 1, wherein a feature amount divided by a length is extracted. 3. In a pattern feature extraction method that thins an input pattern of one character, detects feature points such as end points and branch points from the thinned pattern, and extracts feature amounts by referring to the input pattern and the thinned pattern, The line segment is traced from the feature point that is the starting point of the line segment, and the tracing length from the starting point of the line segment to the feature point that is the end point of the line segment, and the distance between the two points of the starting point and the ending point of the line segment. Detecting by the sub-line differentiation determination means, which detects a distance and detects a line segment in which the ratio of the distance between the starting point and the end point of the line segment to the tracing length is equal to or less than a set value; and the sub-line differentiation determination means detects the line segment. traced from the starting point of the line segment to the end point of the line segment,
The functions F ₁ (X, Y) and F ₂ are expressed as linear combinations of the X and Y coordinate values of each tracking point as variables.
(X, Y)...F _N (X, Y), when the value of an X between the subline segment feature point and the starting point and ending point of the line segment;
The sub-line segment feature points whose Y coordinate differences are both within a certain value are integrated into the starting point and end point of the line segment, and the X and Y points between the sub-line segment feature points that are not integrated into the starting point and end point of the line segment are Among the sub-line segment feature points whose coordinate differences are both within a certain value, the sub-line segment feature point with the minimum sum of X and Y coordinate values is set as the sub-line segment representative point, and the sub-line segment feature points are integrated. and sub-line segment feature extracting means that divides the line segment by the starting point and end point of the line segment and the sub-line segment representative point, and extracts the feature amount for the divided line segment. A pattern feature extraction method characterized by comprising: