JPS6240753B2 - - 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 relatively effective features used to identify the entire character to be read. .

When recognizing characters written on paper, it is generally optically scanned and quantized into a binary pattern such that the character part is "1" and the white part of the paper is "0".
After separating the characters one by one, they undergo preprocessing such as noise removal and thinning, and then pass through a feature extraction section and a determination section. The feature extraction unit usually extracts feature points such as end points, branch points, and bending points from the thinning pattern, as well as feature quantities such as stroke direction, line length, and bulge, and the recognition unit extracts these feature points and feature quantities. Recognizes entered characters based on the presence or absence or amount of characters. This feature extraction unit first identifies the entire character to be read, as shown in ``Handwritten Katakana Recognition Using Broken Line Approximation'' in the 1975 Pattern Recognition and Learning Research Material PRL74-62 published by the Institute of Electronics and Communication Engineers (IEICE) in 1975. In order to extract relatively effective features (hereinafter referred to as basic features) that can be commonly used for all characters, select candidate characters from the extracted basic features, and then distinguish between patterns that are similar to each other. A feature extraction method has been proposed and put into practical use that extracts a plurality of features that distinguish only these similar patterns and narrows down the number of candidate characters to one. According to this, for example, from a character pattern as shown in FIG. 1, as shown in FIG. (indicated by arrows) are detected and converted into a symbol string such as T2K5BT3BT1B in the order of detection. Note that FIG. 1 shows an example of the correspondence between stroke directions and numbers 0 to 7. The end points, branch points, inflection points, and stroke directions expressed by such symbol strings are features that correspond to basic features. In such a basic feature extraction method, for example, for a pattern such as the number "2" in FIG. The direction of is detected and expressed in the order of detection as a symbol string such as T2K4K5K2T, and the number “2” in Figure 2 4, which is similar to Figure 2 1.
For a pattern like this, the stroke directions of the end point T, bending point K, 1, 2, 4, and 52 are detected as shown in FIG.
It is expressed as a symbol string such as T1K2K4K5K2T.
In other words, in such a feature extraction method, subtle changes in the number and position of inflection points tend to occur when basic features are extracted for character patterns consisting of curved parts, and as mentioned above, even for similar character patterns. The symbol strings are different, and as a result, the amount of descriptions of standard patterns having similar formats to the symbol strings indicating the necessary basic characteristics increases, and if this cannot be met, recognition will be impossible or erroneous recognition will occur.

The object of the present invention is to receive the extracted end points, branch points, inflection points, and stroke directions for a character pattern consisting of curved parts, and to create a clockwise rotation between thin lines sandwiched between the end points and branch points. It is an object of the present invention to provide a feature extraction method that solves the above-mentioned conventional drawbacks by detecting line segments or counterclockwise line segments, and is stable and reduces the amount of description for expressing basic features.

According to the present invention, the end points, branch points, bending points, and stroke directions detected from the thinning pattern are received, and the end points that are the start points of line segments, the end points that are branch points and the end points of line segments, and branch points are Clockwise/counterclockwise detection means for detecting whether the direction of stroke 2 is clockwise or counterclockwise with respect to the direction of stroke 1 for two adjacent strokes 1 and 2 detected between the sandwiched thin lines; , for a thin line in which there are three continuous strokes 1, 2, and 3, the clockwise/counterclockwise detection means detects that the direction of stroke 2 is clockwise with respect to the direction of stroke 1, and the direction of stroke 3 is detected as being clockwise with respect to the direction of stroke 1. is detected to be counterclockwise with respect to the direction of stroke 2, or if the direction of stroke 2 is detected to be counterclockwise with respect to the direction of stroke 1, and the direction of stroke 3 is detected to be clockwise with respect to the direction of stroke 2. In this case, the inflection point that connects stroke 2 and stroke 3 (hereinafter referred to as the end inflection point) is regarded as the end point of the line segment, and the inflection point that connects stroke 1 and stroke 2 (hereinafter referred to as the start inflection point) is regarded as the end point of the line segment. A feature extraction method is obtained that includes means for determining the start point of the line segment as the start point of the line segment, and means for detecting the direction between the two points of the start point and the end point of the line segment (hereinafter referred to as chord direction).

In the present invention, the directions of adjacent strokes S _N and stroke S _N+1 are r _N and r _N+1 (N
=1, 2, 3...), whether the direction of the stroke S _N+1 is clockwise or counterclockwise with respect to the direction of the stroke S _N is given by the following equation.

O<MOD _P (r _N+1 −r _N )<P/2 ...(1) P/2<MOD _P (r _N+1 −r _N )<P ...(2) (1), (2 ), P is the quantization number in the stroke direction, and the stroke direction in FIGS. 1 and 2 is shown as P=8 as an example. Also
MOD _P (r _N+1 −r _N ) means that the value of r _N+1 −r _N is O...P
-1 positive integer value and when taking O, r _N+1 −
represents the value of r _N , and the value of r _N+1 −r _N is −(P−1)
…When taking a negative integer value of −1, P+r _N+1 −
r represents the value of _N. Note that equation (1) indicates that the direction of stroke S _N+1 is clockwise relative to the direction of stroke S _N , and equation (2) indicates that the direction of stroke S _N+1 is clockwise relative to the direction of stroke S _N. Indicates counterclockwise rotation. For example, in the case of FIG. 2, the stroke directions are detected in the order of 2, 4, 5, 2, and
This corresponds to r ₁ , r ₂ , r ₃ , and r ₄ used in (1) and equation (2). For the direction of this stroke, equation (1) and equation (2)
Calculating MOD _P (r _N+1 − r _N ) used in
Since r ₂ − r ₁ = 2, MOD ₈ (r ₂ − r ₁ ) = 2, r ₃ −
Since r ₂ = 1, MOD ₈ (r ₃ − r ₂ ) = 1, and the formula
(1) is satisfied. That is, the stroke direction r ₂ is clockwise relative to the stroke direction r ₁ , and the stroke direction r ₃ is clockwise relative to the stroke direction r ₂ . Also, since r ₄ −r ₃ = −3, MOD ₈ (r ₄
−r ₃ )=8−3=5, which satisfies equation (2). That is, the stroke direction _r4 is counterclockwise with respect to the stroke direction _r3 .

The present invention will be described below with reference to figures showing specific embodiments.

FIG. 2 3 is a diagram showing the basic features obtained from the end points, bending points, and stroke directions of FIGS. 2 2 and 2 5 according to the present invention, in which V and U are the end inflection point and the start point, respectively. R and L in the figure are inflection points indicating inflection points, respectively, where the line segment sandwiched between the end point indicated by J in the figure and the end inflection point indicated by V in the figure rotates clockwise, and U in the figure The line segment sandwiched between the starting inflection point indicated by and the end point indicated by I in the figure indicates that it is counterclockwise, and the numbers 3 and 4 in the figure indicate the chord direction (indicated by an arrow). It shows. The correspondence between the string direction and the numbers is the same as that for the stroke direction shown in FIG. 1. The basic features obtained by the present invention shown in FIG. 2 will be explained by applying equations (1) and (2) to the end point T inflection point K and the direction of the stroke in FIG. 2, for example. The direction of the stroke in FIG.
Detected in the order of 2, 4, 5, 2, and applying equations (1) and (2), as mentioned above, the stroke direction r ₂ is clockwise relative to the stroke direction r ₁ ; r ₃ is clockwise with respect to the direction of stroke r ₂ and direction of stroke r ₄ is the direction of stroke
For r ₃ , it turns counterclockwise. In other words, the thin line sandwiched between the end point T indicated by a in FIG. 2 and the refraction point K indicated by d in FIG. The thin line sandwiched between the refraction point K shown by and the end point T shown by e in FIG. 2 is a counterclockwise line segment. Refraction point K indicated by d in Fig. 2
corresponds to the end inflection point indicated by V in FIG. 2, and the inflection point K indicated by C in FIG. 2 corresponds to the start inflection point indicated by U in FIG. corresponds to In addition, the end point T shown by a in the figure in Fig. 2 and the end point T shown by e in the figure correspond to the end point T shown by J in the figure in Fig. 2 and the end point T shown by I in the figure, respectively. do.
The chord direction indicated by 4 in Fig. 2 3 is obtained by finding the slope between the two points from the X and Y coordinate values of the end point indicated by J in the figure and the end inflection point indicated by V in the figure. The values are obtained by quantizing them into the numbers 0...7 shown in FIG. The chordal direction indicated by 3 in FIG. 2 is obtained in the same manner. Similarly, for the end point T, bending point K, and stroke direction in FIG. 2,
The basic characteristics shown in are obtained. The basic characteristics shown in Figure 2 and 3 are, for example, a symbol string such as TRK4KLT3 (T is the end point, R is clockwise rotation, K is the end or start inflection point, L is counterclockwise rotation, and the numbers 4 and 3 are ) indicating the chord direction. That is, for character patterns such as those shown in FIG. 2 1 and 2
It can be expressed by different symbol strings such as T
(1K)2K4K5K2T ((1K) indicates that it is not necessary), but in the present invention, as mentioned above, TRK4KLT3
Using one symbol string such as , the basic features of character patterns such as those shown in FIGS. 2 1 and 2 can be stably expressed regardless of slight changes in the position or number of inflection points.

FIG. 3 is a circuit diagram showing a specific embodiment of the present invention. Note that FIG. 3 shows an example in which the number of quantizations in the stroke direction is 8. Also, by adding S after the number of a signal line, the signal on that signal line will be represented.

Reference numeral 11 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. The basic feature extraction means 12 extracts end points, branch points, inflection points, and stroke directions from the single character pattern stored in the pattern memory 11.

Note that when two adjacent strokes have the same direction, the basic feature extraction means 12 integrates them into one stroke.

End points extracted by the basic feature extraction means 12,
The X and Y coordinate values and labels T, B, and K of each of the branching point and the bending point are set in the order in which they are extracted into a shift register 90 consisting of N stages, and the direction of the stroke extracted by the basic feature extraction means 12 is further set. A shift register 8 consisting of N stages in the order in which
Set to 0. For example, for the end points and refraction points in FIG. K and the X and Y coordinate values of its inflection point are set as follows.
In the shift register 80 consisting of stages, the first stage 81 is set to "2", the second stage 82 is set to "4", the third stage 83 is set to "5", and so on.

Also, for the direction of the stroke in FIG.
"5" in row 82, "E" in third row 83
is set as follows. Note that the value “E” set in the third stage 83 of the shift register 80
1 detected by the basic feature extraction means 12
This value indicates the end of the stroke direction in a line segment. In advance, "E" is stored in the register 38, "4" is stored in the register 19, and "8" is stored in the register 26.
"0" is set in register 20, register 71, and register 70, respectively. 2 is a clockwise/counterclockwise rotation detection section, which includes a subtraction circuit 28, a register 19, a register 20, a register 25, and a register 2.
6, comparison circuit 21, comparison circuit 23, comparison circuit 2
4. It is composed of an adder circuit 27, an AND circuit 22, and an AND circuit 29. The subtraction circuit 28 extracts the contents of the first stage 81 from the contents of the second stage 82 of the shift register 80.
Subtract the contents of and set it in the register 25. Comparison circuit 21 compares the contents of register 25 and register 20
If the contents of the register 25 are smaller than the contents of the register 20, the output signal 211S
becomes “1”. On the other hand, the contents of the register 25 and the contents of the register 26 are added by an adder circuit 27.
When the output signal 211S of the comparator circuit 21 becomes "1", the AND circuit 29 is opened and the contents of the register 25 are rewritten by the contents of the adder circuit 27.
That is, the difference in direction between two adjacent strokes is stored in the register 25 as a numerical value from 0 to 7.
When the control signal 101S is output from the control circuit 30, the AND circuit 22 is opened, and the contents of the register 25 and the contents of the register 19 are compared in the comparison circuits 23 and 24. Comparison circuit 23 has register 1
It is detected whether the content of 9 is greater than the content of register 25, and if so, the output signal 231S is "1".
becomes. That is, the signal 231S is "1" when the direction of stroke 2 changes clockwise with respect to the direction of stroke 1 for two adjacent strokes 1 and 2. The comparison circuit 24 detects whether the contents of the register 19 are smaller than the contents of the register 25, and if it is smaller, outputs the output signal 241S.
becomes “1”. That is, the signal 241S is output as "1" when the direction of stroke 2 changes counterclockwise with respect to the direction of stroke 1 for two adjacent strokes 1 and 2. 7 is a clockwise/counterclockwise change detection section, which includes a register 70;
register 71, comparison circuit 72, comparison circuit 73,
It is composed of an AND circuit 74. signal 231
When S becomes “1”, the control circuit 30 outputs a set signal 110S, and the register 70 is set to “1”.
is set and the signal 241S becomes "1", the control circuit 30 outputs the set signal 111S,
"2" is set in the register 70. When a value is set in register 70, the contents of register 71 and register 70 are compared in comparison circuit 72 and comparison circuit 73. Comparison circuit 72 detects whether the contents of register 71 and register 70 are equal or not, and if they are not equal, output signal 721 is output.
S becomes "1". The comparison circuit 73 detects whether the contents of the register 71 and the contents of the register 70 are equal or not, and if they are equal, the output signal 731S becomes "1". That is, the clockwise/counterclockwise change detection unit 7 detects that in three consecutive strokes 1, 2, and 3, the direction of stroke 3 is clockwise (“1” is stored in the register 70) relative to the direction of stroke 2. The register 70 stores whether the direction of stroke 2 is clockwise or counterclockwise with respect to the direction of stroke 1. If the direction of stroke 2 changes clockwise (counterclockwise) with respect to the direction of stroke 1 and the direction of stroke 3 changes counterclockwise (clockwise) with respect to the direction of stroke 2, the signal 72
“1” is output from 1S. Furthermore, register 71
is set to "0" in advance, so even when the clockwise/counterclockwise rotation detection unit 2 detects clockwise or counterclockwise direction with respect to the first two adjacent stroke directions of the line segment, the signal is 721S outputs “1”. When the signal 721S becomes "1", the control signal 102S becomes "1" from the control circuit 30,
Furthermore, a control signal 107S and a control signal 207S are output. Also, when the signal 731S becomes “1”,
A control signal 107S and a control signal 207S are output. When the control signal 102S becomes “1”, AND
The circuit 59 is opened and the contents of the first stage 91 of the shift register 90 are transferred to the line segment start point storage register 43, which is composed of M stages of shift registers.
The control signal 107S causes the output signal 331S of the 1-bit flip-flop circuit 33 to become "1", and when the control signal 102S becomes "1",
The AND circuit 54 opens, and the line segment end point storage register 42 consisting of M stages of shift registers is stored.
At the same time that the contents of the second stage 92 of the shift register 90 are transferred, the AND circuit 52 is opened and the contents of the register 71 are transferred to the stroke direction change storage register 41 which is composed of M stages of shift registers. The contents of the first stage 91 of the shift register 90, the contents of the second stage 92 of the shift register 90, and the contents of the register 71 are transferred to the line segment start point storage register 43, line segment end point storage register 42, and stroke direction change storage register 41. When it is done, it shifts,
The contents of the K-1st stage are transferred to the Kth stage (K=1...M). When the control signal 107S is output, the shift register 80 performs a shift, and the contents of the K-1st stage of the shift register 80 are changed to the Kth stage (K=1...
N), and the flip-flop 33 becomes "1". When the control signal 207S is output, the shift register 90 performs a shift, and the contents of the K-1st stage of the shift register 90 become the Kth stage (K=1...N).
will be forwarded to. When the shift register 80 and the shift register 90 perform a shift, the control signal 1 is
13S is output, AND circuit 74 is opened, and the contents of register 70 are transferred to register 71. The comparison circuit 36 detects whether the contents of the second stage 82 of the shift register 80 and the contents of the register 38 are equal, and if they are equal, the output signal 361S becomes "1".
become. When the output signal 361S becomes “1”,
The AND circuit 57 and the AND circuit 53 are opened, the contents of the register 71 are transferred to the stroke direction change storage register 41, the contents of the second stage 92 of the shift register 90 are transferred to the line segment end point storage register 42, and the control signal 207S and control signal 107
S is output, and shift register 90 and shift register 80 perform shifting. That is, comparison circuit 3
6 is the end value E of the stroke direction in one line segment
is detected, the end point that is the end point of one line segment, the coordinate values of the branch point, and labels T and B are stored in the line segment end point storage register 42, and the end point of the clockwise or counterclockwise direction is the end point or the branch point. For a clockwise line segment or a counterclockwise line segment, a value indicating clockwise or counterclockwise rotation is transferred to the stroke direction change storage register 41. In the comparator circuit 37, the shift register 8
It is detected whether the contents of the first stage 81 of 0 and the contents of the register 38 are equal, and if they are equal, an output signal 371 is output.
S becomes "1". When the signal 371S becomes “1”, the AND circuit 55 opens and the shift register 90
The contents of the second row 92 are the end/start point storage register 4.
Transferred to 3. That is, when the output signal of the comparison circuit 37 becomes "1", the X and Y coordinate values and labels T and B of the end point and branch point serving as the starting point of the line segment are transferred to the line segment starting point storage register 43. . Furthermore, when the signal 371S becomes "1", the control signal 107S
and 207S are output, the shift register 80 and shift register 90 perform shifting, and the control circuit 30 outputs a set signal 115S.
Register 70 and register 71 are reset to "0". 32 is a one-character end comparison circuit, in which the end point and branch point of one character are stored in the first stage 91 of the shift register 90, and the shift register 90 is cleared in the second stage 92 of the shift register 90. When the value "0" is stored, the value "0" in the register 39 is compared with the content in the second stage 92 of the shift register 90, and if they are equal, a one-character end signal 100S is output. When the one character end signal 100S is output, the control circuit 30 causes the shift register 80 and the shift register 90 to
Flip-flop 3 is cleared to “0” and flip-flop 3 is cleared to “0”.
3 is reset to "0" by the reset signal 120S.

When the one-character end signal 100S is output, the control circuit 30 causes the line segment start point storage register 43 to
The X, Y coordinate values of the row 431 and the X, Y coordinate values of the first row 421 of the line segment end point storage register 42 are transferred to the subtraction circuit 60. The X and Y coordinate values of the first stage 421 of the line segment end point storage register 42 are calculated by the subtraction circuit 6.
0, the control circuit 30 transfers the control signal 1
16S is output, and the counter 63 is incremented by one. Note that the counter 63 is reset when the one character end signal 100S becomes "1".

The subtraction circuit 60 subtracts the X, Y coordinate values of the first stage of the line segment start point storage register 43 from the X, Y coordinate values of the first stage of the line segment end point storage register 42, and sends the values to the division circuit 61. Forward. The division circuit 61 divides the difference in the Y coordinate value between the line segment end point and the line segment start point by the difference in the X coordinate value, and transfers the result to the chord direction quantization circuit 62. The chord direction quantization circuit 62 quantizes the value (chord direction slope) output from the division circuit 61 into the values of numbers 0 to 7 in FIG. The selection circuit 64 uses the value of the counter 63 to
The string direction detected by the string direction detection circuit 62 is stored in the first register 44 of the M string direction storage registers 44.
Transfer to 1. When the chord direction is transferred to the register 441, the X, Y coordinate values of the second stage 432 of the line segment start point storage register 43 and the X, Y coordinate values of the second stage 422 of the line segment end point storage register 42 are transferred from the control signal 30. The coordinate values are transferred to subtraction circuit 60. Thereafter, similar operations are performed to detect the string direction from the start point of the line segment to the end point of the line segment of one character pattern, and set it in the string direction storage register 44. When the chord direction of a line segment of a pattern for one character is detected, the contents of the line segment start point storage register 43, the contents of the line segment end point storage register 42, and the stroke direction change storage register 4 are stored.
1 and the contents of the chord direction storage register 44 are transferred to a recognition unit (not shown). For example, if the specific embodiment of FIG. 3 is applied to the end points, branch points, refraction points, and stroke directions of FIGS. 2 and 5, the end points of the line segment start point storage register 43,
The end point T and the inflection point K indicating the start point of inflection are stored in the register that stores the labels of the branch point and the inflection point, and the register that stores the labels of the end point, the bifurcation point, and the inflection point of the line segment end point storage register 42 stores the end point T and the inflection point K indicating the start point of inflection. The inflection point K and the end point T indicating the end inflection point are stored in order, respectively, and the stroke direction change storage register 41 stores 1 in order.
(a numerical value indicating clockwise rotation) and 2 (a numerical value indicating counterclockwise rotation) are stored in the chord direction storage register 44 in order.
The chord directions indicated by 3 and 4 are stored. In the present invention, in the basic feature extraction means 12, thin lines sandwiched between end points and branch points for which no inflection point has been detected are directly transferred to the recognition section.

As described above, the present invention detects clockwise or counterclockwise line segments and their chord directions between thin lines sandwiched between end points and branch points for character patterns consisting of curved parts. By doing so, basic features can be stably extracted even when the number and position of refraction points change, and the basic features can be expressed with an even smaller amount of description.

[Brief explanation of the drawing]

Fig. 1 is a diagram explaining the basic features, Fig. 2 is a diagram explaining the effectiveness of the basic features of the present invention, and Fig. 3 is a diagram explaining an embodiment of the present invention.・Counterclockwise rotation detection unit, 7 is a clockwise/counterclockwise change detection unit, 11 is a memory pattern, 12 is a basic feature extraction means, 30 is a control circuit, 41 is a stroke direction change storage register, 42 is a line segment end point storage register , 43 is a line segment starting point storage register, 44 is a string direction storage register, 62 is a chord direction quantization circuit, 8
0 and 90 are N-stage shift registers.

Claims (1)

[Claims] 1. In a pattern feature extraction method in which an input pattern for one character is used as a thinning pattern, and feature points such as end points, branch points, and inflection points, and feature quantities such as stroke directions are extracted from the thinning pattern, the end points, Based on the direction of the branching point, bending point, and stroke, the detected adjacent end point is the starting point of the line segment, the end point is the branching point and the end point of the line segment, and the thin line is sandwiched between the branching point. clockwise/counterclockwise detection means for detecting the difference in direction between two strokes 1 and 2 and detecting whether the direction of stroke 2 is clockwise or counterclockwise with respect to the direction of stroke 1; With respect to the thin line in which three strokes 1, 2, and 3 exist, the clockwise/counterclockwise detection means detects that the direction of stroke 2 is clockwise with respect to the direction of stroke 1, and the direction of stroke 3 is detected as being clockwise with respect to the direction of stroke 1. If the direction of stroke 2 is detected as counterclockwise with respect to the direction of stroke 1, or if the direction of stroke 3 is detected as counterclockwise with respect to the direction of stroke 2, then Means for setting the bend point connecting stroke 2 and stroke 3 as the end point of the line segment, and setting the bend point connecting stroke 1 and stroke 2 as the start point of the line segment;
A pattern feature extraction method characterized by comprising means for detecting a direction between two points, a starting point of the line segment and an end point of the line segment.