JPH0362284A - Character line extracting device - Google Patents

Abstract

PURPOSE:To detect the tilt of a character line with high accuracy by extracting the character line together with its tilt value based on the prescribed feature value like the center of plural character blocks contained in the character string. CONSTITUTION:A block center calculation part 14 calculates the center coordinate value (x1, y1) of a character block based on the position and the size of the character block. A tilt value calculation part 15 calculates the tilt value thetaand the intercept xsi of the (y) coordinates of a straight line against the center coordinate values (x1, y1)(i = 1, 2... n) of plural character blocks in each character line. These calculated tilt value and intercept are stored in a character line storage part 13 as the character line tilt information. Thus it is possible to extract the tilt of a character line including the tilt information with high stability and accuracy despite the presence of the tilt of the character line, the variance of size of a handwritten character, and the separate characters.

Description

Detailed Description of the Invention (Field of Industrial Application) The present invention relates to a character line extraction device, and is particularly useful for character recognition devices that read addresses, etc. on printed documents and postal items. The present invention relates to a character line extraction device that extracts a plurality of written character lines.

(Prior art) In order to read each character of an address name on an existing printed document or postal item using character recognition technology, the characters handwritten or printed on the paper are optically scanned, and usually two After performing the value quantization process, it is first necessary to perform a process to extract the character line area written on the paper. In this character line extraction process, if the character line is tilted due to variations in handwritten character size, etc., such as in mail, or if the paper is tilted, the character line extraction accuracy may deteriorate or the character line Extraction processing may become difficult.

Conventionally, as such a character line extraction method, for example, "Paper 411 Precept Element Extraction Method Not Based on Format Designation Information" (IEICE Transactions D Vol, J66-D No.
1. As shown in PP111-113 (1983), there is a method (first conventional method) of extracting character lines from a printed document based on peripheral distribution or the like.

Another method for extracting character lines is, for example, as shown in ``A proposal for character extraction from handwritten documents using knowledge about the target document'' (IEICE Pattern Recognition and Learning Research Report PRL85-63). Another method (second method) involves integrating neighboring rectangular blocks by merging processing from the smallest rectangular block surrounding a character block area extracted by labeling processing, etc., and further performing tilt detection.

(Problems to be Solved by the Invention) Among the conventional methods described above, the first conventional method requires performing tilt correction processing in advance, and does not have sufficient cost performance in terms of processing speed.

Furthermore, if the target is an address line or the like written in handwriting on a piece of mail, character line extraction processing may become difficult due to variations in character size.

On the other hand, even in the second conventional method, the accuracy of the character lines and the inclination of the character lines may deteriorate due to, for example, variations in the size of handwritten characters, the presence of separated characters such as in Chinese characters, etc.

The purpose of the present invention is to extract a plurality of characters extracted by labeling processing etc. in order to accurately extract a character line even if there are conventional character line inclinations, variations in handwritten character size, and even if there are separated characters. It is an object of the present invention to provide a character line extraction device which extracts character lines by focusing on the arrangement relationship between block blocks and detects the inclination of the character lines with high accuracy.

(Means for Solving the Problems) In order to solve the above-mentioned problems, a character line extraction device according to the present invention includes means for extracting a plurality of character block blocks that can be separated from the background of a paper surface, etc. Determine the distance or overlapping degree between the block blocks in the vertical or horizontal direction, extract the arrangement relationship between the plurality of block blocks,
means for storing, means for classifying each character block based on the presence or absence of an arrangement rllrWJ in a predetermined direction between the plurality of character block blocks, and generating a plurality of character lines; means for integrating a plurality of character blocks having an arrangement relationship in a direction different from the predetermined direction among the character block blocks, and based on a predetermined feature value such as the center of the plurality of character block blocks in the character line. and means for extracting a character line including the slope value of the character line.

In addition, there is a means for extracting a plurality of character block blocks that can be separated from the background of a paper surface, etc., and a method for determining the vertically or horizontally spaced distance or degree of overlap between any two character block blocks, and A means for extracting and storing the arrangement relationship between the block blocks, and classifying each text block based on the presence or absence of the arrangement relationship in a predetermined direction between the plurality of text block blocks, and generating a plurality of character lines. means for integrating a plurality of character block blocks in the character line that have an arrangement relationship in a direction different from the predetermined direction; means for calculating a slope value and an estimation error for the plurality of features of the character line based on a plurality of feature values such as a center, a bottom edge, etc.; and an estimation error that is the smallest among the estimation errors for the plurality of features. and means for extracting a character line including a slope value of the character line by selecting a slope value of the character line.

(Example) Examples of the present invention will be described below with reference to the drawings.

FIGS. 1(a) to 1(d) are examples showing the principle of classifying each character block based on the arrangement relationship between each character block according to the present invention.

In Fig. 1(a), the shaded area indicates a character string image, and the symbol bt (1=1.2...6) is a rectangular block surrounding the image of the character part (c and below, a block of characters)
It shows. Here, extraction of such character blocks can be realized using known techniques such as labeling processing and contour tracking. Note that the character block Igb is indicated by the dotted line in FIG. 1(a).

is included in character block b4, so character block b4
shall be integrated into

FIG. 1(b) is a block diagram of two character blocks b+.

It is a figure for demonstrating the inspection method of the arrangement|positioning relationship of the left-right direction of b2.

Note that although the method for inspecting the arrangement relationship in the left and right direction will be described using 1r5!1(b), the same applies to the up and down direction.

In FIG. 1(b), the symbol d breath 1 is the character block b
+, indicates the distance between bi. Further, symbols 11 and 11 each indicate the height of the character block diagram, that is, the projection in the X-axis direction in the diagram. Further, 1+nl* indicated by a dotted line in the figure indicates the amount of overlap of the character blocks t)+ and bi in the left-right direction.

Therefore, as an example of a measure indicating the degree of overlapping of the character blocks bt and bt in the horizontal direction, for example, the minimum value among the projections of the two character blocks bs and b2 in the X-axis direction, that is, m 1 Overlap of n (l It11) and character blocks bt and bs in the left and right direction fill n
The ratio 1tfl1*/m1n (It, It) (hereinafter referred to as an overlap measure) can be used. The above character block bt.

The overlap scale SL snow between and b2 indicates a range from 0 to 1, and in the case of 0, it indicates that there is no overlap in the left-right direction at all.

It should be noted that the determination as to whether or not two character block blocks overlap may be made by determining the above-mentioned overlap measure using a predetermined fixed threshold Ts (fflL, O<Ts<1), or by using the above-mentioned The threshold value Ts may be determined while being dynamically changed depending on the distance d between the character block blocks.

Next, whether there is a vertical or horizontal arrangement relationship is determined by using the overlapping measure α and the distance l1lid between the character block blocks using threshold values Ts and Td, respectively. That is, for the predetermined direction (vertical or horizontal direction) of two character blocks b, , b, the overlap measure (2=lI nlj/m
in (It + IJ) is larger than the threshold value Ts, and the distance between character blocks w! When d*, J is smaller than the threshold value Td, it is assumed that the arrangement relationship in the predetermined direction is established.

FIG. 1(c) shows the character block blocks b+, bi, bs, b4, etc. shown in FIG. 1(a). The arrangement relationships in the vertical and horizontal directions with respect to b are extracted and expressed as a matrix.

Incidentally, the vertical and horizontal arrangement relationships in FIG. 1(a) are as follows: two character blocks btlbj (i=
J, i, J=1.2. ...5> overlap scale α1. J
The threshold value Ts is set to about 0.9, and the character block-distance mci1. J
This is an example in which the threshold value Td is set to about one character as shown in FIG.

The value 1 (or -1) in the matrix in Figure 1 (C) means that the character blocks on the rows of the matrix are arranged downward (or upward) with respect to the character block b on the column of the matrix. Similarly, a value of 2 (or -2) in the matrix indicates that it is placed leftward or (rightward), respectively.For example, from the first F(c) to the block b , and b4 satisfy the vertical arrangement relationship, and character blocks b+ and b2 satisfy the horizontal arrangement relation. Here, in the above matrix, the values l and -1 or 2 and -2, which indicate the presence or absence of a placement relationship, are symmetrical, so the lower half from the diagonal of the matrix can be omitted. In addition, 2 shown in Fig. 1(c)
Two character blocks bt, bJ (t=J, 1.J=
Assume that the character mass block amount ratio 1idt, t, the overlap measure α14, etc. are also extracted as related feature quantities when extracting the arrangement relationship of 1°2, . . . 5).

FIG. 1(d) shows an example of extracting the vertically written character line shown in FIG. 1(a) from FIG. 1(c).

First, from the arrangement relationship in Figure 1 (C), the partial character row, L
, , L, M , and L4 can be easily calculated. That is, since the character blocks b1 and , have a vertical relationship, a partial character line LL consisting of the character blocks b+ and bn can be extracted. (Lt e (bt.

bi)> Similarly, the character block b2. Partial character line L* (L*ε(b2゜bi)) consisting of ba, partial character line Ls e (bs, bi, bs) L46 (b
i, bs).

Next, the partial character line L r I L 21 obtained above
L3. For L4, by sequentially integrating partial character lines containing common character block blocks, the character line shown in FIG. 1(a) can be extracted. That is, the partial character row and L2 have a common character block b4, and the integrated partial character row and the partial character row Ls have a common character block b, and as a result, the character block blocks b1bz, bs, A block including bi and bs, that is, a line of vertically written characters shown by the dotted line in FIG. 1(a) can be extracted.

Next, a character block bt included in the character row.

For bi, bs, bi, and bs, character block blocks having left and right arrangement relationships are similarly calculated using the matrix shown in FIG. 1(c).

That is, the character block blocks b+, bz, and bs satisfy the left-right relationship, and the character block C shown by the dotted line in FIG. 1(a) is generated as a block that integrates these character block blocks. I can do it.

The extraction of the character block C was introduced to stably detect the inclination of the character line, and the inclination detection of the character line 2 shown in FIG. 1(a) is performed using the character block bt, bt
, instead of bs, the character block diagram C+ b 4 *
bI will be used.

FIG. 2 shows an example in which handwritten character lines are extracted by applying the character line extraction method described using FIG. 1. In addition, since FIG. 2 is a horizontally handwritten character string, the character lines are extracted by being classified according to the horizontal arrangement relationship.

In FIG. 2, the horizontal arrangement relationship between each character block is determined using the overlap measure threshold Ts and the distance between character blocks Td explained in FIG.
When each character block diagram bI (l=1...17) is classified, (bi, bt).

bi, b, ), (bi, bs, b,), (bs.

bt), (bt, by), (by, be, b,).

(ba, bi.), (b-, bt.), (btu
, blt) (bi2.bla) , (bti, b
,,bts).

(bla, bla, btj), (bla,
bla, btt).

(b l&, b tt) is obtained, a common character block is detected, and the integration process is performed, resulting in two character lines L+ e (bt , b□1 bs 1
bi *bs+ bi, by, ba, be, bta),
Lt6(t)++, bI*+ box, 1) 14+
t)tit bt*+ l)tt) is obtained.

That is, character lines can be stably extracted even if there is an inclination or a change in character size, such as the two character lines Ll+L2 indicated by dotted lines in FIG.

Next, in order to stably detect the slope of each extracted character line, we target each character block forming the character line.
Character blocks having a vertical arrangement relationship are found and integrated. Therefore, among each character block b (i=l...10) included in the character row shown in FIG.
The character block diagram having a vertical arrangement relationship includes character block diagrams b6 and b. and b9, and two character block blocks b+a and bB are generated. Therefore,
To detect the inclination of the character line, the character blocks br*b*+bs+b, +brm+bt+b++, b in FIG.
+o will be used.

FIG. 3 is a diagram for explaining the character line inclination detection process used in the character line extracting device of the first embodiment.

Coordinate values (X+, Vl) + (Xt
.

yx l+ (xs + ys)l (X4
+ y4) + (Xs * 3's) l (Xt
13'4)+(Xt*3't)(Xt,
3/a) are the character lines LL explained in Fig. 2, respectively.
Each character block b t + b x 1 b S
*b 4 * b 11. by + b l9. b t
・Set as the center coordinates of

Incidentally, the tilt detection in the present invention is not limited to the center coordinates of each character block, but may also use the lower end coordinates or the upper end coordinates.

The slope detection method can be obtained as a straight line fitting problem using the least squares method, which is normally used in the field of statistical processing. That is, n coordinates (Xl, yt) (1=1
．． 2...n), these coordinate values are drawn as a straight line Y=θ
When fitting to χ + ε (where θ is the slope and ξ is the y-intercept), it is only necessary to determine the values of θ and ξ so that there is an error. When fitting a straight line using the method of least squares like this, θ , ξ is expressed by the following equation using n coordinates (X+ + yt).

ξ=y−θi However, (2) Therefore, the detection of the inclination value θ with respect to the center coordinates of the eight character blocks shown in FIG. 3 is performed using equations (1) and (3),
It is obtained by applying (4), (5), and (6) (where n=8). Furthermore, if the y-intercept ξ is also calculated using equation (2), the straight line shown by the solid line in FIG. 3 can be detected.

FIG. 4 is a diagram used to explain the character line inclination detection process used in the character line extracting device according to the second embodiment of the present invention.

In the figure, the character block diagram bt (1=1.・
. . 6) assumes that, as described in FIG. 2, the formation of horizontal character lines has been completed by checking the horizontal positional relationship of each character block, and the integration has been completed by checking the vertical positional relationship. Furthermore, the black circles in FIG. 3 represent the center coordinate values of each character blocks, and the white circles 0 in the figure represent the lower end coordinates of each character blocks.

Figure 4 is an example in which the inclination of a character line can be detected more stably by using the bottom coordinate value as the feature of each character block rather than the center coordinate value. In some cases, it is better to use the center coordinate values. Therefore,
Either the slope value θ obtained using the center coordinate value of each character block block or the slope value θ2 obtained using the bottom coordinate value of each character block block, whichever is more accurate, may be selected. Therefore, the slope value θJ with the smaller error Se mentioned above is
(J=1 or 2) can be selected. Note that the error Se described above can be calculated using equation (7).

5e=Sy-ξ・Sxy (7) In the example of Fig. 4, the error Se shown in equation (7) is larger because the straight line with the slope value θ is larger than the straight line with the slope θ2. , a straight line having a slope θ□ is selected.

FIG. 5 is a functional block diagram showing an example of the character line extraction device of the first embodiment. Reference numeral 1 denotes an image memory that optically scans a plurality of character lines written on a paper surface, performs binary quantization, and stores the image as a plurality of character line images. 2
is a character block extracting unit, which extracts rectangular blocks surrounding a plurality of character images, that is, character block blocks, as shown in FIG. 1(a), and sequentially stores them in the character block storage unit 3. Store. 11 is a placement relationship extraction unit;
The device relationship extraction unit 10, which is composed of the overlap measurement unit 4, the distance measurement unit 5, and the arrangement relationship determination unit 6, reads out a plurality of character block blocks from the character block storage unit 3, and first extracts the overlap measurement unit 4 and the distance measurement unit 4. As shown in FIG. 1(b), the measurement unit 5 sequentially measures the overlap scale and distance between the character block blocks. s and Td, and as explained in Section 111i(c), the arrangement relationship information between the character chunk blocks in the vertical and horizontal directions is calculated and stored in the arrangement rWi relation storage unit 7.

It is assumed that character block blocks that satisfy the inclusion relationship shown in FIG. 1(a) are subjected to normal integration processing in the arrangement relationship extraction section 10.

8 is a line classification section, as explained in FIG. 1(d),
A character block block that reads from the layout relationship storage unit 7 the arrangement relationship information between character block blocks in a predetermined direction (vertical or horizontal direction) stored in the direction parameter storage unit 9 and forms a character line in a predetermined direction. Information such as the position and size of each classified character block is stored in the classification result storage unit 10. Block integration unit 12 (
Then, for a plurality of character block blocks belonging to each character line, the arrangement relation information between the character block blocks in a direction different from the above-mentioned predetermined direction is read from the arrangement relation storage unit 7, and using this information, the above-mentioned direction is determined. A character line block that can be formed from the position and size of a plurality of character block blocks obtained as a result of the integration process and each character block belonging to it is stored as a character line memory. Transfer to Department 13.

Next, the slope of the character line is calculated for each character line block.

First, the block center calculation unit 14 calculates the center coordinate values (xt, yt) of the character block as shown in FIG. 3 based on the position and size of the character block. Note that the coordinate values of the lower end and the upper end of the character block may be used instead of the center coordinate position of the character block described above.

Next, the slope value calculation unit 15 calculates the center coordinate values (xt, yt > (
1=1.2. =n), use the above-mentioned equations (1) and (3>1 equation (4), 1 equation (5>1 equation (6)) to calculate the slope value θ, and use equation (2) to calculate the y coordinate of the straight line. The intercept ξ of is calculated and stored in the character line storage unit 13 as slope information of each character line.

FIG. 6 is a functional block diagram showing an example of the character line extraction device of the second embodiment. Image memory 1, character chunk block extraction section 2, character chunk block storage section 3, arrangement relationship storage section 7
, a row classification section 8, a direction parameter storage section 9, an existing classification result storage section 10, an arrangement relationship extraction section 11, a block integration section 12,
The character line storage section 13 and the block center calculation section 14 have an R function equivalent to the function described in the character line extraction device of FIG.

In the character line extracting device of the above embodiment, the center coordinate value of each character block is calculated in the block center part 14 for a plurality of character blocks belonging to each character line block, and the block lower end calculation unit 18 The lower end coordinate value of each character block is calculated in . Although we have taken up the center coordinate value and the bottom coordinate value as the characteristics of each character block for which the slope value is calculated, there are also multiple characteristics such as the center of gravity and the top end! j, may also be applied.

Next, the inclination calculation unit 16 calculates equation (1), equation (2), and equation (3) for each of the center coordinate value and bottom coordinate value of the plurality of character block blocks in each character line block. , formula (4
), Equation (5), Equation (6), Equation (7), and Equation (8) are used to calculate the slope value θ1 with respect to the central coordinate value, the linear y-coordinate intercept ξ1, the error Se, and the slope value θ2 with respect to the lower end coordinate value.
, the y-coordinate intercept ξ2 of the straight line, and the error Sew are calculated.

The error comparison unit 17 detects the smaller of the errors Se and S e 2 for each of the center M target value and the lower end coordinate value, thereby determining the slope value θ1 (i=1 In addition, ζ y 2) and the y-coordinate intercept ξ of the straight line (i=1 or 2) are selected and stored in the character line storage section 13 as inclination information for each character line.

(Effect of g@light) As explained above, according to the present invention, even if the inclination of a character line or the size of handwritten characters changes, or even if there are separated characters, the inclination of a character line can be adjusted stably and accurately. It is possible to provide a device that can extract character lines including information.

[Brief explanation of drawings]

Figure 1 is a diagram showing the principle of classifying each character block diagram based on the arrangement relationship between each character block block and extracting character lines in the present invention, and Figure 2 is an example of extracting character lines with an inclination. FIG. 3 is a diagram for explaining the character line inclination detection used in the character line extracting device of the first embodiment, and FIG.
5 is a functional block diagram showing an example of the character line extraction device of the first embodiment, and FIG. 6 is a functional block diagram showing an example of the character line extraction device of the first embodiment. FIG. 2 is a functional block diagram showing an example of a character line extracting device according to an embodiment. 1... Image memory, 2... Character block extraction unit,
3... Character chunk block storage unit, 4... Overlap measurement unit, 5... Distance calculation unit, 6... Judgment unit, 7... Arrangement relationship storage unit, 8... Line classification unit, 9... Direction parameter storage section, 10... Spring classification result storage section, 11... Arrangement relationship extraction section, 12... Block integration section, 13...
Character line storage section, 14...Block center calculation section, 15.
. . . Inclination calculation unit of the first embodiment, 16 . . . Inclination calculation unit of the second embodiment, 17 . . . Error comparison unit, 18 .

Claims (2)

[Claims] (1) A means for extracting a plurality of character block blocks that are separable from the background of a paper surface, etc., and determining the distance or overlapping degree in the vertical or horizontal direction between any two character block blocks, and extracting the plurality of character block blocks. means for extracting and storing arrangement relationships between blocks, and means for classifying each character block based on the presence or absence of an arrangement relationship in a predetermined direction between the plurality of character block blocks and generating a plurality of character lines. a means for integrating a plurality of character blocks having a layout relationship in a direction different from the predetermined direction among the plurality of character blocks in the character line; and a center of the plurality of character blocks in the character line. A character line extracting device comprising means for extracting a character line including a slope value of the character line based on a predetermined characteristic value such as . (2) means for extracting a plurality of character block blocks that are separable from the background of a paper surface, etc., and determining the distance or overlap between any two character block blocks in the vertical or horizontal direction; means for extracting and storing arrangement relationships between blocks, and means for classifying each character block based on the presence or absence of an arrangement relationship in a predetermined direction between the plurality of character block blocks and generating a plurality of character lines. a means for integrating a plurality of character blocks having a layout relationship in a direction different from the predetermined direction among the plurality of character blocks in the character line; and a center of the plurality of character blocks in the character line. , a means for calculating a slope value and an estimation error for the plurality of features of the character line based on a plurality of feature values such as a lower end, and a slope having a minimum estimation error among the estimation errors for the plurality of features. A character line extracting device comprising means for extracting a character line including a slope value of the character line by selecting a slope value of the character line by selecting a value.