JP3196291B2 - Character recognition method and device - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION The present invention reads a character pattern represented by image optically relates character recognition technology to convert each character pattern to a corresponding character code, and specifically for printing characters, the various fonts The present invention relates to a character recognition algorithm suitable for performing character recognition.

[0002]

2. Description of the Related Art Conventionally, as an example of character recognition technology, for example, the Transactions of the Institute of Electronics and Communication Engineers, '79 / 11 Vol. J62-
D No. 11 There is a mesh division method used in “rough classification for multi-font printing kanji recognition” (prior art 1). In this method, a character pattern is divided into a plurality of uniform mesh areas, and the ratio of black pixels in the mesh area is used as a feature amount. Basically, the method addresses the displacement by blurring the feature, and does not consider the application to the displacement matching as in the present invention. For this reason, there is a problem that it is not suitable for detailed recognition.

[0003] As another example of the conventional character recognition technology, see the Transactions of the Institute of Electronics and Communication Engineers, '85 / 1 Vol. J68-DN
o. 1 pp. 56-63 "Handwritten Kanji Recognition by Dynamic Matching Method" (Prior Art 2). This means that after extracting the character pattern, it is normalized to a certain size pattern,
For the normalized pattern, vertical, horizontal,
After extracting the diagonal directional features and obtaining a different character pattern for each directional component, for each image,
By performing shift matching in only one direction for each pixel, character recognition is realized. In this method, the consistency of the order relation of pixels is performed only in one line in the shifting direction, and there is a problem that the consistency with other lines is not obtained. In addition, there is a problem that the number of features increases in order to normalize the current pattern.

[0004] In addition, as a character recognition technique for dynamically performing mesh division, the Transactions of the Institute of Electronics, Communication and Communication, '84 / 11 V
ol. J67-D No. 11 pp. 1379-13
83 "Linear Density Equalization-Nonlinear Normalization Method for Correlation Method" (Jurai Surgery 3). This is to change the division position based on the center of gravity of the black pixel in the pattern in order to correct the deformation of the handwritten character. This can correct the distortion of the entire pattern, but is not suitable for extracting feature amounts for shift matching.

[0005]

The feature amount of the mesh pattern feature shown in the prior art 1 greatly changes due to a difference in line width or a line displacement, and it is difficult to recognize various fonts with one dictionary. Is not suitable. In addition, the displacement is dealt with by blurring, and there is a problem that the identification rate is low.

In the prior art 2, when recognizing a complex character such as a kanji, if the number of character pattern normalizations is reduced, the character pattern itself becomes different from the original pattern. There is a problem that sufficient recognition cannot be performed from the feature. Therefore, the resolution cannot be reduced to increase the recognition rate, and the number of features for matching increases. In addition, if the tolerance of the matching shift is not increased, it is not possible to sufficiently cope with the deformation of the character pattern. For these reasons, it is difficult to increase the recognition speed while maintaining the recognition rate in the conventional method. As for the shift, it is necessary to shift the features of all the pixels included in each of the rows in the vertical direction feature, and there is a problem that it takes a long time to perform the process.

The mesh division method of the prior art 3 is for correcting pattern deformation, and is not for reducing the number of features to increase the recognition speed.

It is an object of the present invention to enhance recognition of various fonts.
It is an object of the present invention to provide a character recognition method which can be performed with high accuracy .

Another object of the present invention is to provide a character recognition method capable of performing high-speed recognition processing by reducing the number of features.

[0010]

In order to achieve these objects, the present invention extracts features from an original character pattern and normalizes them before normalizing the character pattern.
The normalization uses a method in which the characteristics of the character pattern are not lost as much as possible, for example, a mesh division method.

In this case, a feature value focused on the stroke direction of the character line is extracted, and mesh division is performed using a position where the feature value is significantly different from an adjacent pixel as a division position. If the number of divisions for normalization is not enough if the division is performed only at the change position of the feature, division is performed at the interpolation position while maintaining the overall balance.

The present invention provides a "shifted matching method" in which a recognition target is a print character, and a feature in the vertical direction is shifted by one vertical mesh, and a feature in the horizontal direction is shifted by one horizontal mesh. Apply. In addition, for character patterns in which horizontal separation or vertical separation has occurred, the feature amount is extracted independently for each part,
Perform shift matching.

[0013]

According to the character recognition method of the present invention, even when the number of features extracted for character recognition is reduced, a recognition rate similar to that of the prior art can be obtained, and high-speed character recognition can be performed. Become.

[0014]

First, an outline of a character recognition method according to the present invention will be described with reference to FIG.

From the character pattern 101, a feature amount (pixel feature amount) for each pixel is extracted. The pixel feature amount is a feature amount related to the directionality of a stroke including the pixel,
It is obtained for four directions: vertical, horizontal, diagonally left, and diagonally right. Of these four feature quantities, only the vertical and horizontal features (102, 103) are used as feature quantities for matching. Since the character size is not normalized in this state, the character pattern is divided into a grid pattern (mesh division) with a fixed division number for each of the vertical and horizontal characteristics. At the time of this mesh division, a position at which the difference between the values of the feature amounts becomes large is set as a mesh division position in order to prevent blurring of the feature. Also, mesh division positions are added so that the balance of the original character pattern is not lost, and the average value of the obtained pixel feature amounts in each mesh is used as the mesh feature amount for matching (104, 10).
5). Next, after narrowing down the objects using the mesh features, the vertical and horizontal mesh features are stored in the feature dictionary (106, 107).
Shift matching (DP matching) by DP (dynamic programming) as shown in FIG. 2 is performed so that matching of the feature amount in the horizontal direction and the stroke unit can be performed.

FIG. 3 is an overall block diagram of the character recognition device of the present embodiment.

The image data input by the scanner 301 is transmitted to a memory 30 through a scanner controller 302.
5 is stored. In this embodiment, the image obtained by reading from the scanner is a binary pattern determined by a certain threshold.

The disk 303 stores images, dictionary for pattern matching, recognition results, and the like. If necessary,
The contents of the memory are stored and written to the memory via the disk controller 304. The recognition process is performed using data on the memory. In the main memory 305,
Work data and a feature dictionary at the time of recognition are stored.

The CPU 306 controls the entire system, and sequentially proceeds with processing by input from the keyboard 310 or the like. Each recognition process is also performed here. Display / keyboard controller 307
Stores the display content sent from the CPU in the memory 308 and displays it on the display 309. The input from the keyboard 310 is stored in the memory 308, and the
Respond to read requests from Reference numeral 311 denotes a bus for connecting the devices.

FIG. 4 is a schematic block diagram of the character recognition process. The image reading unit 401 includes image data 402 and 4
From the character circumscribed rectangle of the format analysis result stored in 03,
The image data for each character is read out. The read contents are stored in the pixel feature amount storage memory 404. There are four pixel feature storage memories, a, b, c, and d, each of which is stored as image data having a value of “0” for a white pixel and “1” for a black pixel.

The pixel feature extracting unit 405 extracts, for each pixel, four-dimensional directional features of vertical, horizontal, diagonally left, and diagonally right directions based on the character pattern stored in the memory 404. In areas a, b, c, and d.

The mesh division unit 406 sets a predetermined number of mesh division positions based on the pixel feature amounts stored in 404 so that pixels having similar characteristics are included in the same mesh as much as possible. Position storage memory 40
7 is stored.

The mesh feature extraction unit 408 calculates the average of the features of the pixels in the pixel feature stored in 404 for each mesh obtained from the mesh division positions stored in the memory 407, and calculates This is the feature amount of the mesh. The obtained feature amount is stored in the mesh feature amount storage memory 4.
09.

In the pattern matching unit 410, the feature amount stored in the memory 409 and the feature amount dictionary storage memory 4
11 is subjected to pattern matching with the feature dictionary stored in FIG. Then, the evaluation value of the matching with each character in the dictionary and the identification number of each character in the dictionary are stored in the evaluation value storage memory 412.

In the sorting unit 413, the evaluation value storage memory 4
12 are sorted on the basis of the evaluation value so as to be in descending order of evaluation. Here, the identification numbers of the characters are also sorted together with the evaluation values, and the order obtained by this sorting is the order of the recognition candidates.

FIG. 5 shows a schematic flowchart of the processing of the character recognition apparatus.

501: Initialization. The feature dictionary is read out.

502: Determine a method of reading image data.

503: Scanner activation. When reading from the scanner, the scanner 301 is started and the image data is stored in the memory.

504: Image data reading. When reading the image data stored in the disk, the data is read from the disk 303 and stored in the memory.

505: Extraction of connected components. When the image data is stored in the memory, the entire image is scanned, and a block (connected component) of black pixels that are continuous in any of the eight directions (up, down, left, and right) is extracted, and is extracted as a rectangle circumscribing it.

506: Format analysis. I took it out at 505,
Based on the arrangement of the connected components, character string extraction and region extraction are performed, and character strings, figures, tables, and the like are determined.

507: Character extraction. Characters are extracted from a portion determined to be a character string in the format analysis, a boundary of one character is set for each line, and a circumscribed rectangle of the character is extracted.

508: Character recognition. Recognize the extracted character pattern and convert it to a character code.

The character recognition process includes feature extraction from a character pattern and pattern matching of the extracted features.
The processing contents will be described in detail according to the flowchart of the entire character recognition processing of FIG.

601: Set the number of characters to be recognized to M.

602: The counter m is cleared to 0.

603: It is determined whether all the characters to be recognized have been recognized. m <M 604: A character pattern to be recognized next is read for one character from the character rectangle information and the image data.

605: Feature extraction. For the read character pattern, a feature amount for pattern matching is obtained.

606: The number of characters of the feature dictionary to be matched is set to N.

607: The counter n is cleared to 0.

608: Check whether the comparison with the N characters in the feature dictionary has been completed.

At step 609: 411, the standard feature value stored in the feature value dictionary storage memory is read.

610: A shift matching is performed between the standard feature amount corresponding to each character code stored in the dictionary and the feature amount obtained from the character pattern from the image in 605 to obtain a matching distance value. It is stored in the matching distance storage memory.

611: The counter n is incremented.

612: Sorting is performed based on the matching distance values stored in 412.

613: Return the character codes of the top 10 characters of the sorting result and the matching distance value as the recognition result.

614: The counter m is incremented.

FIG. 7 is a flowchart of the entire feature extraction method. As a feature amount, a feature value that pays attention to the directionality of a stroke forming a character pattern is used, and is obtained for each pixel, and then obtained by mesh division.

701: In character pattern reading, first, a character pattern for one character is read from image data and character rectangular data, and stored in four pixel characteristic amount storage memories 404-a, b, c, and d. Store. At this time, a margin of one pixel (white pixel feature amount: 0) is provided around each pattern.
Write. FIG. 8 shows a state where 1 is stored in a black portion and 0 is stored in a white portion for each pixel.

702: In the creation of the run length label, as shown in FIG. 9, the positions of the black pixels 404-a, b, c, and d include the vertical, horizontal, diagonally left, The number of continuous black pixels in each of the diagonally right directions (hereinafter referred to as a run length) is written. All 0s are written at the positions of the white pixels.

703: In the pixel feature value extraction, 404-
The values at the same position of the run length in each direction stored in a, b, c, and d are extracted, normalized by Expression 1, and again
4-a, b, c, d are written. As a result, the pixel feature amount in each direction is normalized from 0 to 128.

[0053]

(Equation 1)

FIGS. 10A, 10B, 10C, and 10D correspond to FIGS.
The values stored in the same position of b, c, d are H, V,
When L and R are used, the values (h,
v, l, r). For example, in FIG.
The values of the positions 901, 902, 903, and 904 are respectively normalized, and the positions 1001, 1002, 10
03, 1004.

704: In the mesh division, 204-a,
Based on the values of the vertical and horizontal pixel features stored in 204-b, mesh division is performed so as to prevent blurring of the features. Since the oblique direction feature is not used for matching in the present embodiment, it is not divided into meshes. However, the features may be similarly divided into meshes by performing oblique axis transformation to extract features.

705: 704 in the mesh feature extraction
404-a, 40-
The pixel feature amount stored in 2-b is divided into meshes, an average value of the pixel feature amounts included in each mesh is obtained, and the average value is used as a mesh feature amount of each mesh, which is a feature amount used for matching.

In the mesh division, the mesh division positions are set so that as many features as possible are included in one mesh. For this purpose, a difference between the feature amounts of adjacent pixels is obtained, and division is performed at a position where the difference is the largest.

Hereinafter, according to the flowchart of FIG.
The mesh division method in this character recognition method will be described in detail. FIG. 12 to FIG.
7 shows the contents of a work table for obtaining a mesh division position stored in 07.

1101: In the difference projection value extraction, a difference value between pixel feature amounts of adjacent pixels is obtained, and a value obtained by projecting the difference value in one direction is obtained. As for the vertical direction pixel feature amount, a difference value of the feature amount of horizontally adjacent pixels is projected in the vertical direction. As for the horizontal pixel feature amount, the difference value of the feature amount of vertically adjacent pixels is projected in the horizontal direction. At this time, as for the vertical pixel feature amount, the feature amount arranged on the left and right is “left value <
The projection is performed separately for the case of “value on the right side” and the case of “value on the left side> value on the right side. <Lower value ”
And the case of “upper value> lower value” are projected separately. FIG. 12 shows how the feature values shown in FIG. 10A are projected in the vertical direction with respect to the difference between the values of the adjacent pixels on the left and right. 1201 is a projection value of “left value <right value”;
Reference numeral 1202 denotes a projection value of “value on the left> value on the right”.

In step 1102, in extracting the maximum point of the difference projection value, a position where the difference projection value obtained in step 1101 becomes a maximum is extracted as a function of the direction in which the pixel boundaries are arranged. FIG.
In FIG. 12, the position of the pixel boundary line at which the projection values shown in FIG. 12 are maximized as a function of the arrangement position is indicated by “1”.

1103: In the local maximum point sorting, the local maximum points obtained in step 1102 are sorted such that the difference projection values are in descending order. FIG. 14 shows the result of sorting the position having the maximum in FIG. 13 in descending order of the magnitude of the difference projection value (FIG. 12) at that position. In this way, only the local maximum point is set as the mesh division position because of the rattling of the line boundary and the inclination of the stroke when the character pattern is read by the scanner.
This is for determining where to divide when the position having a large projection value is continuous.

1104: In the division position setting based on the maximum point, pixel boundaries are extracted in the order obtained by sorting in 1103, and the mesh division position is set. FIG. 15 shows a state where the divisional position is set as the division position from the larger difference projection value in FIG.

In this example, 1201 and 1202 in FIG.
Are selected from large positions.

As another method of setting the division position,
There is a method of alternately extracting a division position from each of 1201 and 1202 in FIG. This is as follows.

When attention is paid to one stroke of the character pattern, since a boundary line with a white pixel appears on both sides of the stroke, for example, the stroke is opposite to the dividing position set by the projection value of 1201 and the stroke. Side split position is 12
02 must be present. Therefore, the division position is 1
If one is obtained, the division position is “left value <right value”
If it is a division position obtained from the projection value (1201) of
From the projection value (1202) of “left value> right value” in the range allowable as a stroke width on the right side of the division position found in 1201, a local maximum point is found in this range, and this is found. It is a division position. Similarly, if it is found in the projection value (1202) of “left value> right value”, “left value <right value” of the range allowable as a stroke width to the left of the found position is used. A local maximum point is found from the projection values (1201), and is set as a division position. In any case, if the corresponding division position is not found, the corresponding division is not performed. By performing such a division, the division can be performed such that the stroke is reliably extracted.

1105: 110 in sorting the division position
The division positions obtained in step 4 are rearranged so as to be arranged in the order of the positions. FIG. 16 shows a state where the division positions in FIG. 15 are sorted.

1106: In the interpolation division, in 1104, if the number of divisions is not enough, the division between the division positions set in 1105 is further divided so that the total number of divisions is constant.

The details of the interpolation division will be described below.

FIG . 17 shows a mesh division position based on the maximum point.
5 shows an example of the correspondence between and equal division positions.

In the case of FIG. 17A, there is a one-to-one correspondence, but in FIG. 17B, there is a position corresponding to one-to-two.

As shown in FIG. 17C, as shown in FIG.
In the case where there is a position corresponding to one to two (or more), a state in which one-to-one correspondence is provided so as to minimize the deviation as a whole.

As described above, simply taking the correspondence with the closest position may not be enough, and the present method is to find a correspondence that minimizes the deviation as a whole.

FIG. 18 shows division positions added to keep the number of divisions constant based on the mapping result of FIG. 17C. In this manner, by associating the division position adapted to the stroke with the division position of the equal division, the mesh division position is determined so as to prevent deformation from the original character pattern as much as possible.

FIG. 19 and FIG. 20 show tables used for obtaining a correspondence that minimizes the deviation as a whole.

The mesh division positions shown in FIGS. 19 and 20
Are different from those of the character pattern shown in FIG.
The above characteristics are applied to the character pattern of 48 pixels x 48 pixels.
In the case of extracting the amount of collection and extracting the maximum point of the difference projection value
The example of the obtained division | segmentation position is shown. Here, 0, 1
1, 12, 23, 26, 33, 36, 41, 43, 48
Is the division position obtained by extracting the maximum point of the difference projection value,
are doing. Also, the character pattern of 48 pixels is divided into meshes.
From the division, 16 equal division positions are 0, 3, 6, 9,
‥‥, 48. The position shown in the matrix of FIG.
For the amount of deviation, the division position obtained using the maximum point and the division target
Character pattern was divided by the number of mesh divisions of the number of pixels
Find the difference value (absolute value of difference) from the position (16 equally divided positions)
And store it. For example, "1" shown in 1901
The value is “11” in 1902 and “1” in 1903.
2 ”.

At this time, since both ends are fixed, the order relation is fixed, and only one-to-one correspondence is allowed, the correspondence indicated by the hatched position in the figure is not allowed.

In association with the equal division position by DP shown in FIG. 20, D
Using P, find the correspondence with the smallest deviation.

In finding this correspondence, the following conditions must be met:

(A) Correspondence is one-to-one. (B) The order relation does not change.

The lower left of the matrix in FIG.
0), the horizontal position is x, and the vertical position is y. The value of the position of (x, y) is the division position, f
(X) and g (y). Therefore, (x,
Assuming that the value of the position of y) is C (x, y), C (x, y)
The value of y) is a value represented by Expression 2.

[0081]

(Equation 2)

Since C (x, y) represents the magnitude of the deviation, in order to minimize the deviation as a whole,
A measure that minimizes the cumulative value of C (x, y) in total must be determined for all x while satisfying the above conditions.

T (x, y) indicates the accumulated value of the deviation up to the position (x, y). Set the value of x in the matrix to 0 ≦ x ≦
The values of m and y are set to 0 ≦ y ≦ n. Equation 3 shows a recurrence formula for obtaining T (x, y).

[0084]

(Equation 3)

FIG. 20 shows T (m, n) of the above recurrence formula as
The association of the result solved by DP is shown. The values in the table are
In order from the left, the minimum value of the accumulated value of the deviation to the position while satisfying the above condition is shown. The mark “〇” indicates that the deviation is minimized as a whole. In addition, a line extending to the lower left from each value satisfies the above condition in the left column,
It points to the smallest cumulative value. That is, x ≧ 2 in Equation 3
Shows the position selected by min in the case of. In this way, FIG. 20 is created from FIG. 19, and the correspondence is set so that the cumulative deviation is minimized.

FIG. 21 shows the correspondence between each division position and the equal division position obtained from FIG.

The corresponding positions are shifted between FIG. 22 and FIG.
As a whole, a processing flowchart of a method of setting a correspondence with an equal division position for minimizing a deviation is shown. Both ends are fixed, and a correspondence in a range of 1 ≦ x ≦ m−1 is obtained.

2201: The initial value (x of the counter x of the loop for writing the magnitude of the deviation in the matrix of FIG. 19)
= 1) is set.

2202: Whether or not x ≦ m−1 is satisfied;
Check the value of x.

2203: Initial value of counter y (y = x)
Set.

2204: Check the value of y to see if y ≦ x + nm is satisfied.

2205: The size of the deviation is calculated. C (x,
y) = | f (x) -g (y) | 2206: Increment y. y = y + 1; 2207: x is incremented. x = x + 1; 2208: Initial value setting for calculating the total shift amount.

T (1, y) = C (1, y) (1 ≦ y ≦ 1 + nm) 2209: An initial value of a loop counter x for calculating a total shift amount is set. x = 2; 2210: Check the value of x. x ≦ m−1; 2211: Initial value of counter y is set. y = x; 2212: Check the value of y. y ≦ x + n−
m; 2213: Among z in the range of x−1 ≦ z ≦ y−1, T
Let z be the minimum at which (x-1, z) is the minimum.

2214: Z is written to F (x, y).

T (x, y) = T (x−1, Z) + C (x, y).

2215: y is incremented. y = y +
1: 2216: x is incremented. x = x + 1; 2217: Substituting an initial value for the counter x. x = m-1; 2218: Among z in the range of m-1 ≦ z ≦ n−1, T
Let z be the minimum at which (m-1, z) is the minimum.

2219: Correspondence table M with equal division
Z is stored in (m-1).

M (m-1) = Z; 2220: The initial value Z is substituted for z.

2221: The value of x is checked. x
>1; 2222: Look at the value of F (x, y) and find the correspondence between the left-hand division position and the equal division position. z = F
(X, z); 2223: decrement x. x = x−1; 2224: z is stored in the table M (x) corresponding to the equal division. M (x) = z; As described above, a correspondence relationship between all the division positions by the maximum point and the equal division positions is obtained.

By the above processing, the vertical direction feature
Indicates the horizontal division position, and the vertical
A division position is determined. In addition, for longitudinal features
Is divided equally in the vertical direction.
By performing equal division in the direction, the vertical direction of each feature
The horizontal and vertical mesh division positions are obtained. in this way
Of each pixel in the mesh
Determine the average of the quantities. The pattern matching is performed based on the feature amounts obtained in this manner. When the recognition target is a print character, the direction of the stroke constituting the character does not change much. Therefore, the shift is performed in units of lines, thereby suppressing an increase in cost due to the shift matching.

In order to match the entire character pattern, the feature values on the end lines must always match the features at the same position to be matched.
Is created. However, as shown in FIG.
Depending on the original character pattern, the stroke may or may not appear at the end line. The character pattern 2301 has the characteristic 2302 in which a stroke appears on the top line. However, the character pattern 2303 does not show a stroke in the top line.
2304 features are obtained. For this reason, correct matching may not be possible.

In order to solve such a problem, as shown in FIG. 25, matching is performed on the assumption that one line of feature amount 0 exists outside the end line of the feature amount. Thus, while satisfying the above constraints,
Correct matching becomes possible.

In this embodiment, shift matching by DP matching is performed. From the characteristics of character pattern matching: (a) The left-right order relationship must not be interchanged. (B) Since the line widths of characters may be different, one-to-many matching is allowed. (C) All features must be associated so that there is no character line that is left out of matching. Matching while satisfying the three conditions.

FIG. 2 shows the principle of DP matching. Each point is a matching cost value obtained by a difference in the feature amount generated by the correspondence of each line. The total cost of each point along the path connecting the lower left and upper right of the figure is
A path that minimizes the path is determined, and this cost value is used as the matching cost for pattern matching.

In order to satisfy the above conditions (a), (b) and (c), only the right and upper right paths are allowed as shown in the figure.

FIG. 26 shows the principle of absorbing the displacement of a two-dimensional stroke of a character by shifting in only one direction. As described above, after extracting the directional component, each shift is performed in only one direction, thereby suppressing a two-dimensional increase in processing time due to shifting in the two-dimensional direction, and allowing the shift. It is possible to spread.

FIG. 27 is a flowchart of the matching method. Here, a case is shown in which the features obtained by dividing the mesh into M × N are shifted in units of one vertical line of meshes up to P meshes only in the horizontal direction. In this case, M is the number of lines in the shifting direction. N is the number of features in one line. As described above, at the time of matching, mesh lines with feature amount 0 are attached to both ends, so that
The number of lines to be actually matched is M + 2. The following description shows a case where M is 16.

2601: Perform cost value calculation.

In C (x, y), an x line on the recognition target side,
The matching cost when the dictionary side y line is handled is entered.

The matching cost value of each point is obtained as follows.

For example, the cost value shown at the position 201 in FIG. 2 is 6 on the x side and 7 on the y side, and is extracted in order from the top of the feature amount of the 6th line of the pattern of 202. Then, the total value of the feature value and the absolute value of the difference extracted in order from the left of the seventh line of the pattern 203 is obtained,
This is set as the value of C (6, 7).

Therefore, the feature represented by the two-dimensional character pattern on the x-axis side is represented by A (x, i) (0 ≦ i ≦ N−1) in the two-dimensional character pattern on the y-axis side. Assuming that the feature quantity is B (y, j) (0 ≦ j ≦ N−1) (in FIG. 2, x and y are interchanged), C (x, y) is obtained by the following equation.

[0113]

(Equation 4)

2602: Initial value setting for DP matching.

[0115]

(Equation 5)

2603: Initialization of loop counter x x = 0 2604: Update of DP matching value (2 <= x <= 1)
5)

[0117]

(Equation 6)

2605: counter increment x = x + 1 2606: loop check x <= 17 2607: calculation of matching result (minimum value M)

[0119]

(Equation 7)

The cost values obtained by the above-described feature extraction and matching are sorted to obtain character recognition results.

By the way, some kanjis are made from biased characters or from crowns and feet. The positional relationship of the horizontal stroke of the character made from bias and creation is
It is not always the same depending on the bias and construction. Similarly, the positional relationship of vertical strokes of a character made of a crown and a foot is not always constant. For this reason, the character pattern can be divided into half or four, and each pattern can be divided into meshes by the above-described method to extract a feature amount. FIG. 28 shows the contents of processing in which a horizontal direction feature is obtained from a character pattern and then divided into two parts, ie, left and right, mesh division and matching.

2701: In the directional feature extraction, vertical feature extraction is performed.

2702: The character pattern data from which the directional feature is extracted is divided into two parts, left and right.

2703: For each of the divisions, the same mesh division is performed as in the case where no division is performed.

2704: Shift matching is performed for each of the divided parts, and a recognition result is obtained based on the total value of the respective costs.

[0126]

According to the recognition method of the present invention, when performing mesh division for normalizing the number of features in pattern matching, blurring of the features due to the division is prevented, and a feature suitable for shifted matching is obtained. Can be. Further, while absorbing the two-dimensional displacement of the character by the displacement matching, the increase in the processing time due to the increase in the tolerance of the displacement amount is reduced by one.
It can be suppressed to a dimensional increase.

[Brief description of the drawings]

FIG. 1 is a schematic explanatory diagram of a character recognition method of the present invention.

FIG. 2 is a diagram illustrating the principle of DP matching.

FIG. 3 is a system configuration block diagram of the character recognition device of the embodiment.

FIG. 4 is a block diagram of processing contents of character recognition.

FIG. 5 is a processing flowchart of the character recognition device of the embodiment.

FIG. 6 is a flowchart of a character recognition process.

FIG. 7 is a flowchart of a feature extraction process.

FIG. 8 is a diagram showing a storage state of a character pattern in a feature extraction memory.

FIG. 9 is a diagram showing a run length storage state of character data in each direction.

FIG. 10 is a view showing a pixel directional feature amount storage state of each pixel of character data.

FIG. 11 is a flowchart of a mesh division method.

FIG. 12 is a diagram illustrating a storage state of a difference value of a pixel feature amount.

FIG. 13 is a diagram showing a result of extracting a maximum point of a difference value of a pixel feature amount.

FIG. 14 is a view showing a sorting result of local maximum values of difference values of pixel feature amounts.

FIG. 15 is a diagram illustrating setting of mesh division candidate positions based on the local maximum point of the difference value of the pixel feature amount.

FIG. 16 is a diagram showing a result of sorting mesh division positions by local maximum points.

FIG. 17 is a diagram showing an example of correspondence between a mesh division position and an equal division position by a maximum point.

FIG. 18 is a diagram showing a setting state of an interpolation division position.

FIG. 19 is a matrix diagram showing a corresponding shift amount of a division position.

FIG. 20 is a diagram showing an association for minimizing a shift amount of a division position due to DP.

FIG. 21 is a diagram showing an association for minimizing a shift amount set by a DP.

FIG. 22 is a flowchart (part 1) of a process for obtaining a correspondence between a local maximum point and an equal division position.

FIG. 23 is a flowchart of a process for obtaining a correspondence between a local maximum point and an equal division position. (Part 2)

FIG. 24 is a diagram showing a change in a feature of a mesh of an end line due to a change in a character pattern.

FIG. 25 is a diagram showing the addition of a feature amount line having a value of 0 for absorbing a change in the end of a character pattern.

FIG. 26 is a diagram showing the principle of pseudo two-dimensional DP matching.

FIG. 27 is a flowchart of a DP matching method.

FIG. 28 is a flowchart of a process of two-division matching.

[Explanation of symbols]

301: scanner, 302: scanner controller, 3
03 ... disk, 304 ... disk controller, 30
5 main memory, 306 CPU, 307 display / keyboard controller, 308 memory (video memory), 309 display, 310 keyboard, 311 system bus, 401 image reading unit,
402: image data storage memory, 403: format analysis result storage memory, 404: pixel feature amount storage memory, 405 ...
Pixel feature extraction unit, 406: mesh division unit, 407: mesh division position storage memory, 408: mesh feature amount extraction unit, 409: mesh feature amount storage memory, 410: pattern matching unit, 411: feature amount dictionary storage memory,
412: matching evaluation value storage memory; 413: sorting unit.

────────────────────────────────────────────────── ─── Continuation of the front page (56) References JP-A-4-590 (JP, A) JP-A-3-46080 (JP, A) JP-A-2-287894 (JP, A) JP-A-63-1988 113690 (JP, A) JP-A-58-123171 (JP, A) "Information Processing Society of Japan 45th (late 1991) National Convention Lecture Paper Collection (2)" 2G-1 p. 273-274 (1992) "Development of a printed character recognition method by shifting matching of black pixel directional features", "Transactions of the Institute of Electronics and Communication Engineers", Vol. J68-D No. 1 p. 56-63 (1985) "Handwritten Kanji Recognition by Dynamic Directional Matching Method" (58) Fields investigated (Int. Cl. ⁷ , DB name) G06K 9/62 JICST file (JOIS)

Claims (2)

(57) [Claims] 1. A method for obtaining a feature amount for each pixel from a character pattern represented by a binary image, and obtaining a directional image of adjacent pixels.
Find the difference value of elementary feature quantity and project in the same direction as the directionality
The mesh division position is determined based on the position where the projection value is maximum.
Determined, the character pattern is divided into message <br/> shoe area at the dividing position, recognizing a character recognizing characters in search of features for each mesh based on the feature quantity of the pixels included in each mesh In the method, the feature quantity relating to the directionality of the strokes constituting the character is specified.
Each is based on the number of pixels in the character pattern
A character recognition method characterized by determining for each direction for each pixel , grouping each directional feature amount for each line including a stroke, and performing shift matching limited to one direction perpendicular to the line. 2. The method according to claim 1, wherein a characteristic amount of each pixel is obtained for a character pattern represented by a binary image, and a directional image of adjacent pixels is obtained.
Find the difference value of elementary feature quantity and project in the same direction as the directionality
The mesh division position is determined based on the position where the projection value is maximum.
Determined, the character pattern is divided into message <br/> shoe area at the dividing position, recognizing a character recognizing characters in search of features for each mesh based on the feature quantity of the pixels included in each mesh in the apparatus, own the feature quantity related to the direction of the strokes constituting the character
Each is based on the number of pixels in the character pattern
A calculating means for obtaining for each direction for each pixel; and a shift matching means for performing shift matching, which collects each directional feature amount for each line including a stroke and limits the direction to one direction perpendicular to the line. A character recognition device.