JPH0326427B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention relates to a character pitch detection device that automatically detects character pitches for separating individual character string images written on paper.

A device that optically reads various groups of printed characters (hereinafter referred to as
When recognizing a series of characters using OCR, it is necessary to separate each character and select them for the character recognition unit. Character pitch is information needed to separate each character individually, and if the size and type of printed matter to be read by OCR is limited, it can be provided in advance. However, as has recently been the case, when OCR scans a wide range of applications such as mail and documents with unspecified character pitch, it is not possible to know the character pitch in advance. It becomes necessary to estimate character pitch from a character string image on paper.

As a conventional method for estimating character pitch, information obtained from the character width of a single character image extracted from a page, such as average character pitch, has been used. However, when the width of individual characters differs depending on the font or character category, such as with English printed characters, the error that occurs when separating characters is negligible between the average character pitch described above and the actual character pitch. It disappears. Therefore, for example, when using the average character pitch described above to separate a character string image that contains many characters in contact, it is possible to misjudge the number of characters in contact, or to incorrectly separate the characters. be cut off.

SUMMARY OF THE INVENTION Therefore, in order to solve the above-mentioned problems, it is an object of the present invention to detect a plurality of character images that can be separated on a white background, based on frequency information regarding the average height and width of character blocks obtained from character blocks. Ta1
Detects a character group that is recognized as a continuous character block from the valid interval for character width and the allowable space width set from that valid interval, and calculates the number of characters in the character group and the character group. An object of the present invention is to provide a character pitch detection device that estimates character pitch based on the sum of the character block width and the space width of the character block width.

Another object of the present invention is to provide stable and optimal character pitch even when a series of character images on a sheet of paper include character images that include contact between characters or character images that separate one character into two characters. The object of the present invention is to provide a character pitch detection device capable of estimating character pitch.

According to the present invention, in a character pitch detection device that scans a series of character string images written on paper and extracts character pitches for separating character by character, Multiple character images (hereinafter referred to as character blocks)
A means for sequentially extracting the character blocks and detecting the position and height of the character blocks, a frequency table that stores frequency information of the character block width, and a means for calculating the average height from the heights of multiple character blocks, and calculating the average height of a possible character. a means of setting a width range;
A mode character width detection means for detecting a mode character block width within a possible range of one character width by referring to frequency information in a frequency table;
A valid interval extraction means detects an interval of one character width (hereinafter referred to as an effective interval) that is effective for estimating character pitch Ps while referring to a frequency table, and again scans a series of character images and extracts a plurality of extracted characters. It sequentially refers to the position and width of each character block, detects a character group that is recognized as a continuous character block from the valid interval and the allowable space width set from the valid interval, and detects the number of characters contained in the character group (hereinafter referred to as a character group width extracting means for detecting the sum value of the character block width within the character group and the space width between the character block widths (hereinafter referred to as the space width) for each consecutive number; Character pitch estimation means for calculating a maximum likelihood estimation value of character pitch based on the cumulative sum value and the number of cumulative sum values (hereinafter referred to as the number of samples) obtained for each character pitch. A pitch detection device is obtained.

Hereinafter, the present invention will be described with reference to a specific embodiment.

FIG. 1 is an example showing a part of a character string image to which the present invention is applied. In the figure, the white background indicated by diagonal lines shows separable character images, i.e., character blocks, as rectangular areas, and in the figure V _i and H _i (i=1
...9) indicates the width and height of each character block.
Therefore, the principle of the present invention will be summarized using FIG. In addition to detecting the position, height, and width of a series of character blocks, based on the frequency distribution of the obtained series of character block widths (see Figure 2), we can calculate the width of one character that is effective for estimating character pitch. Find the valid interval. Targeting the character blocks belonging to this valid interval, the character block width and space width of consecutive number k (for example, referring to the figure, V ₄ , V ₅ , V ₆ , V ₇ and
Find the cumulative sum value V(k) ₍ for _example , corresponding to _V4 in _the figure) . The character block width and space width of the above-mentioned consecutive number k are the k+1st space width V k+1 , k+ determined by the position of the k+2nd character block and the position and width of the _k+ 1st character block _{. 2} (in the figure
V (corresponding to _8,9 ) is larger than the allowable space width determined by the method described later, the character block width and space width from the 1st to the kth
It can be determined as a character block with a consecutive number k and a space width.

In addition, as shown in the width V ₈ of the character block in the figure, the consecutive number k (however, k≧1) is determined by the method shown above.
When a character width that is effective for estimating the pitch of an isolated character where no character block is obtained is obtained, the character block width is the cumulative value V(1) when k = 1 as described above. It is also possible to detect it as

In this way, the optimal character pitch P _s is estimated based on the cumulative sum value V(k) of the number of samples n(k) obtained for each different number of consecutive sequences k. In addition, the following cumulative sum value V(k)
The value 1/k·V(k) divided by the consecutive number k is called the predicted width of one character. Further, the average cumulative sum value of the cumulative sum values of the number of samples n(k) will be expressed as cumulative sum value (k). Now, to briefly describe the properties of the predicted one-character width 1/k V(k) using the cumulative sum value (k), the cumulative sum value (k) is
Since the interval between adjacent character widths, that is, the space width, is also taken into consideration, the predicted width of one character 1/k・(k) increases as the number of consecutive characters and the number of samples n(k) increases, and the error with the character pitch P _s increases. becomes smaller, and the character pitch P _s
gives a good estimate of .

Therefore, as a method to easily obtain the estimated value of character pitch P _s , the longest consecutive number among the consecutive numbers k mentioned above is
The predicted width of one character 1/MAX(k)・(MAX(k)) obtained by dividing the cumulative sum (k) with MAX(k) by the consecutive number k can be obtained as the estimated value of character pitch P _s . can. On the other hand, when estimating a more accurate character pitch P _s , the obtained cumulative sum value (ki) and the consecutive number K _i (where i = 1...l) are obtained for l different consecutive numbers k _i .
The best linear estimate of character pitch Ps can be obtained by calculating _l 〓 ⁱ⁼¹ w(k _i , n(k _i )·V(ki)/ki based on .

As mentioned above, the coefficient w(k _i , n(k _i )) is determined by the number of consecutive sequences k and the number of samples n(k _i ), and for example,
It is obtained from k _i・√( _i )/ _l 〓 ⁱ⁼¹ k _i・√( _i ).
Furthermore, it goes without saying that the above-mentioned character pitch estimate value can be easily calculated by an addition section, a multiplication section, and a division section. Furthermore, by changing the order of the addition, multiplication, and division sections, it is possible to reduce calculation time and calculation errors. Furthermore, the coefficient w(k _i , n(k _i )) may not be used, and the estimated value may be simply expressed as a linear sum.

FIG. 2 shows an example of the frequency distribution of character block widths on the paper as shown in FIG. In the figure, the horizontal axis V of the frequency distribution regarding a plurality of character block widths indicates the value of the character block width V, and the vertical axis NUM indicates the frequency value at an arbitrary character block width value.

Therefore, in the present invention, a plurality of character block widths that are effective for estimating the character pitch _Ps described above based on the frequency distribution are determined as follows. First, a possible character block width A1 that can be one character is determined from the frequency distribution shown in the figure. Here, section A1
are the heights H ₁ and H ₂ of multiple character blocks shown in Figure 1.
... average height H _n and coefficients α ₁ , α ₂ (however, α ₁ < α ₂ )
It can be set from

The average height H _n is determined by setting upper and lower height limits based on the maximum value of multiple character heights.
It may also be calculated as the average height within a certain section.
Next, within section A1, a certain allowable width △τ (△τ
= 3), find the interval C _s with the most frequency, and calculate the interval C _s
Starting from , by updating its upper limit U _s in an increasing direction while referring to the frequency distribution,
Let the upper limit value U 1 and the lower limit value _{L 1} of the valid section C ₁ of the character block width effective for estimating the character pitch P _s . here,
If the lower limit value L ₁ is not updated using the frequency distribution from the lower limit value L _s of the interval C _s , It is also possible to remove one character separated into two or more characters. For example, if there is little variation in character width, start from the interval C _s and update its lower limit value L _s in a decreasing direction while referring to the frequency distribution to determine the effective interval.
It is also possible to increase the reliability of estimation by increasing the number of character block widths belonging to C ₁ .

FIG. 3 is a logic block diagram showing a specific embodiment of the present invention. The scanning device 1 optically scans the character string image written on the paper, converts it into an electrical signal, and writes it into the character string image memory 2 after binary quantization. 3 is a character block extraction device, which sequentially extracts character blocks from a plurality of character string images stored in the character string image memory 2, and stores the starting position and size of each character block in a character block register 4. . Note that the size of a character block represents the character block width and character block height. In addition, such a character block extraction device can be obtained using, for example, the technique disclosed in Japanese Patent Application No. 56-27512 filed by the same applicant. The plurality of character block widths stored in the character block register 4 are sent to the control device 7,
Sent sequentially. The control device 7 sequentially stores the widths of character chunks to be transferred in a frequency table 6 configured from memory.
The contents of the frequency table 6 corresponding to the converted address are read out and incremented, and then written to the same storage location in the frequency table 6 again. In this way, the frequency value of the character block width V extracted from the character string image memory 2 in the frequency table 6 is stored in the address V of the frequency table 6, and the frequency value shown in FIG. The frequency distribution regarding the character block width is displayed in the frequency table 6.

It is assumed that the frequency table 6 is initially initialized to 0. On the other hand, the control device 7 calculates the average value H _n of the heights of the plurality of character blocks stored in the character block register 4 and sends it to the 1-character width class initial information extraction means 5 . The 1-character width class initial information extraction means 5 extracts the mode with a constant allowable width △τ within the range (α ₁ H _n to _{α 2} H _n ) set by the average character block height H _n . The section shown in Figure 2 with
C _s (L _s , U _s ) is determined using the frequency table 6, and its upper limit value U _s and lower limit value L _s are used as initial information and stored in the initial information register 8. Note that the 1-character width class initial information extraction means 5 can be obtained using the technique shown in the application specifications (character separation device) filed by the same applicant and filed on the same date. Reference numeral 9 denotes an effective character block width detection means for detecting an effective range of character block widths that are effective for detecting character pitch _Ps .
In the effective character block width detection means 9, when the upper limit value _Us stored in the initial information register 8 is set in the counter 91, the count is increased by 1, and the frequency value corresponding to the character block width, which is the content of the counter 91, is , is read from the frequency table 6 by the control device 7 and stored in the frequency value register 92, and then the zero detection circuit 93 determines whether it is 0 or not. When the zero detection circuit 93 determines that the content of the frequency value register 92 is 0, the content of the counter 91 is set in the register 10 as the upper limit value _U1 of the effective character block width. On the other hand, when the zero detection circuit 93 determines that the content of the frequency value register 92 is not 0, the counter 91
The count is increased by 1, and the above operation is repeated. Note that the lower limit value _Ls , which is the content of the initial information register 8, is not updated by the control device 7, and is stored in the register 10 as the lower limit value _L1 of the effective character block width.
shall be set. Note that the effective character width detection means uses the upper limit value stored in the initial information register 8.
While increasing U _s and referring to frequency table 6,
It goes without saying that it is also possible to detect the character width for which the frequency value of the character block width is the minimum value as the upper limit value _U1 of the valid interval. 11 is a character group width extraction means. The character group width extraction means 11 is
The cumulative sum value V(k) of character blocks V ₁ , V ₂ ... and space widths V _1,2 V _2,3 ...V _k,k+1 belonging to a valid interval with a consecutive number k (k≧2) is calculated as follows: The cumulative sum value V(k) of the detected number of samples n(k) extracted every consecutive number k is sequentially stored in the observation table 12. The character pitch estimating means 13 estimates the optimal character pitch P _s based on the cumulative sum value V(k) of n(k) samples extracted for each consecutive number k sequentially stored in the observation table 12. A value is required.

One form of the character pitch estimating means 13 according to the present invention can be realized by a simple circuit consisting of a maximum value detection circuit and an average value calculation circuit (not shown). That is, the cumulative sum value V(MAX(k)) having the longest consecutive number MAX(k) from the observation table 12 is detected by the maximum value detection circuit, and the cumulative sum value V(MAX(k)) having the longest consecutive number MAX(k) is detected by the average value calculation circuit. k)) extracted cumulative sum values V
The average cumulative sum value (MAX(k)) of (MAX(k)) is detected as the estimated value of character pitch _Ps . 14 is a character separation means. The character separation means 14 extracts the character pitch obtained by the character pitch estimation means 13.
Separation is performed on a character-by-character basis based on _Ps and the position and size information of the character block stored in the character block register 4, and can be performed using known techniques.

Figure 4 is a logical block diagram showing a specific embodiment of the character group width extraction means.

Note that the signal is represented by adding s to the end of the signal line. First, the control device 7 stores the series of character block widths V ₁ , V ₂ . . . stored in the character block register 4 in the extracted order in the register 20, and and the space widths V _1,2 , V _2,3 . . . based on the position.
... are calculated and stored in the register 21 in sequence. The comparison unit 22 determines whether the character block widths V _i (where i indicates the order of extraction) stored in the register 20 that are sequentially transferred by the control device 7 belong to the valid interval stored in the register 10. If it belongs to the valid section, the character block detection signal 101s is set to "1" and the character block width V _i is stored in the register 23. If it does not belong to the valid section, the character block detection signal 101s is set to "0".

When the character block detection signal 101s becomes “1”, the control device 7 transfers the space width V _i,i+1 stored in the register 21 to the comparison unit 25. Note that the allowable value register 24 is set based on the most frequent value within one character width, which is the content of the initial information register 8 set by the one character width class initial information extraction means 5 described in FIG. It is assumed that the allowable space width has been set in advance by the control device 7. Furthermore, the contents of the tolerance register 24 are, for example,
It is used to detect word breaks caused by one or more blank spaces. Character block detection signal 101
When s becomes “1”, the control device 7 sends the space width V _i,i+1 stored in the register 20 to the comparator 25 . The comparator 25 compares the contents of the tolerance register 24 with the space width V _i,i+1 , and if the space width V _i,i+1 is smaller than the contents of the tolerance register 24, the comparator 25 outputs the delimiter detection signal 102s. If the space width V _i,i+1 becomes larger than the content of the tolerance register, the delimiter detection signal 102s is set to "0". The break detection signal 102s is “1”
, the space width is controlled by the control device 7.
V _i,i+1 and character block width stored in register 23
Y _i is sent to the addition section 26 . The adding unit 26 adds the character block width V _i described above, the space width V _i,i+1 , and the contents of the cumulative sum value register 27 and stores the result in the cumulative sum value register 27 . It is assumed that the cumulative sum register 27 is initially set to 0. The consecutive number counter 28 is incremented by one by the control device 7 when the aforementioned character block detection signal 101s becomes "1" and a character block width belonging to the valid section is detected. In addition, consecutive number counter 28
It is assumed that is initially reset to 0. The above operations are performed until the character block detection signal 101s becomes "0" or the delimiter detection signal 102s becomes "0".

Next, when the character block detection signal 101s becomes "0", it is interpreted that a character block width that does not belong to the valid section has been detected, and the contents of the consecutive number counter 28 and cumulative sum register 27 are changed by the control device 7. It is stored in the observation table 12, and the contents of the counter 28 are reset. It is assumed that if the content of the counter 28 is 0, no setting is performed in the observation table 12. On the other hand, the break detection signal 102s is “0”
When this happens, it is interpreted that a space between words has been detected, and the control device 7 decrements the consecutive number counter 28 by 1, and the contents of the consecutive number counter 28 and cumulative sum register 27 are stored in the observation table 12, and the counter Reset the contents of 28.

Note that the break detection signal 102s becomes "0",
If the consecutive number counter 28 is 1, the control device 7
The character block width, which is the content of the register 23, and the content of the consecutive number counter 28 (however, the content is 1
) may be stored in the observation table 12.

The above operation is performed for all character block widths sequentially stored in the register 20.

FIG. 5 is a block diagram of a specific embodiment of another form of the character pitch estimating means shown in FIG. 3.

In the figure, the character pitch estimating means 13 is indicated by a dotted line. The observation table 12 also includes the character group width extraction means 1 shown in FIGS. 3 and 4.
1, l different consecutive numbers k _i (where i=1
...l), the cumulative sum value V of the number of samples n(k _i )
(k _i ) is stored, and the consecutive number mentioned above
When the cumulative sum value V(k _i ) of k _i is sequentially set, the number of samples n(k _i ) is counted by the control device 7 and stored in a predetermined area of the observation table 12. do. First, the consecutive number k _i and the number n(k _i ) of samples in the observation table 12 are sequentially sent to the integration unit 31, and at the same time, n( _{k i )} cumulative The sum value V(k _i ) is sent to the adding section 32. The integrating unit 31 calculates k i· _n (k _i ) as the product of the number of consecutive samples k _i and the number of samples n(k _i ), and transfers the product k _i ·n(k _i ) to the dividing unit 33 . Addition section 32
adds n(k _i ) cumulative sum values V(k _i ), and divides the dividing unit 3
3 is the sum of n(k _i ) cumulative sum values V(k _i ).
By dividing by k _i · n (k _i ), the predicted width of one character obtained from the consecutive number k _i is 1/k _i · (k _i ), (where V (k _i ) is the number of samples n (k _i ) is sent to the integrating section 35. 34 is a coefficient table, in which the number of consecutive sequences k _i and the number of samples n described above are
A coefficient α(k _{i ,} n(k _i )) determined by (k i ) is stored. For example, as an example of the coefficient α(k _i , n(k _i )), the value k _i ·√( _i ) can be determined for the consecutive number k _i and the sample number n(k _i ). When the predicted one-character width 1/k _i (k _i ) obtained from the consecutive number k _i and the number of samples n (k _i ) is sent to the integration unit 35, the control device 7 calculates the coefficient from the coefficient table 34. α(k _i , n(k _i )) is read out to the integration unit 35 and simultaneously sent to the coefficient addition unit 36 . In the integration unit 35, the coefficient α(k _i , n(k _i )) and the consecutive number K _i
The product of the predicted one-character width 1/k _i ·(k _i ) is calculated and sent to the addition section 37. Addition section 37
is the weighted one-character prediction width α(k _{i ,} n
(k _i ))・1/k _i・(k _i ) cumulative _{sum l} 〓 ⁱ⁼¹ α(k _i , n (k _i ))・1/k _i・(k _i ) is calculated and divided Sent to 38.

On the other hand, the coefficient adder 37 calculates the cumulative sum _l 〓 ⁱ⁼¹ α(k _i , n(k _i )) of l coefficients α(k _i , n(k _i )) sent sequentially.
is calculated and sent to the division section 38. Division section 38
, the output of the adder 37 is _l 〓 ⁱ⁼¹ α(k _i , n
(k _i ))・1/k _i・(k _i ) is divided by l coefficient values _l 〓 ⁱ⁼¹ α(k _i , n(k _i )) which are the outputs of the coefficient adder 36,
The linear estimate of character pitch P _s is obtained as.

The character pitch means 13 shown in FIG. 5 uses the best linear estimation value _l 〓 ⁱ⁼¹ w(k _i , n(k _i )・1 This is one of the embodiments in which the number of divisions of the coefficient w(k _i , n(k _i )) is reduced with respect to /k i ·(k _i ).In other words _, the predicted width of one character is 1/k _i ·( k _i ) can be found regardless of the coefficient w(k _i , n(k _i )), so W(k _i , n(k _i )) = α(k _i , n(k _i ))/ _l 〓 ^{i= 1} α(k _i , n(k _i )).In this way, the method of obtaining the best linear estimate described above may take some processing time depending on the hardware elements used. If it is necessary to reduce the number of divisions, taking into consideration calculation accuracy, for example, without first performing the division calculation using the number of samples n(k _i ) and the number of consecutive k _i regarding the cumulative sum value V(k _i ), It goes without saying that it is also possible to do it last.

As described above, by using the present invention, character pitch can be accurately measured even if the character pitch is not known in advance or even if character images include contact or separation between characters. This can be easily achieved.

[Brief explanation of the drawing]

FIG. 1 is a diagram showing, as an example, a part of a character string image to which the present invention is applied. Figure 2 shows
FIG. 3 is a diagram illustrating an example of the frequency distribution of character block widths on paper. FIG. 3 is a logic block diagram showing a specific embodiment of the present invention. FIG. 4 is a block diagram showing a specific embodiment of the character group extraction means 11.
FIG. 5 is a block diagram showing a specific embodiment of another form of character pitch estimating means. In the figure, 1 is a scanning device, 2 is a character string image memory, 3 is a character block extraction device, 4 is a character block register, 5 is a 1 character width class initial information extraction means, 6
1 is a frequency table, 7 is a control device, 8 is an initial information register, 9 is an effective character block width detection means, 10 is a register, 11 is a character group width extraction means, 12 is an observation table, 13 is a character pitch estimation means, and 14 is a It is a single character separation means.

Claims (1)

[Claims] 1. In a character pitch detection device that scans a series of character string images written on a paper surface and extracts character pitches for separating character by character, a plurality of characters that can be separated on a white background from the series of character string images are detected. means for sequentially extracting blocks and detecting the position, width, and height of the character blocks; means for detecting the frequency distribution of the widths of the plurality of character blocks; and an average calculated from the plurality of character blocks. valid interval detecting means for examining the frequency distribution based on the target height and detecting an interval that can be one character wide as a valid interval; and a valid interval and a tolerance set from the valid interval in the plurality of character blocks. Character group width extraction that detects a character group that is recognized as a continuous character block from the space width, and calculates the cumulative value of the number of characters included in the character group, the width of the character block, and the space width between the widths of the character blocks. 1. A character pitch detection device comprising: means for estimating a character pitch by a maximum likelihood based on the cumulative sum value for each number of characters and the number of cumulative sum values.