JPH0468669B2 - - 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 printed characters, etc. (hereinafter referred to as
When recognizing a series of characters using OCR, it is necessary to separate each character and send them to the character recognition unit. Character pitch is information needed to separate each character, 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 difficult 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, for example, average character pitch has been used. However, when the width of individual characters differs greatly depending on the font or character category, such as in the case of English printed characters, or when the number of characters that touch each other increases, the average character pitch mentioned above and the actual character pitch differ by one character. The error that occurs when performing the separation cannot be ignored. Therefore, for example, if you use the above-mentioned average character pitch to separate a character string image that includes many characters that are in contact with each other, the number of characters that are in contact may be mistaken, or the separation position may be inaccurate. or 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 calculate the frequency distribution of the distance between character clusters calculated from a plurality of character images that can be separated on a white background, that is, from character clusters. An object of the present invention is to provide a character pitch detection device that updates the estimated character pitch while clustering starting from the average height of the character.

Another object of the present invention is to achieve stable and optimal character pitch even when a series of character images on paper include character images that include contact between characters or character images that separate one character into two characters. An 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 a paper surface and extracts character pitches for separating each character, it is possible to separate the character string images from the series of character string images using a white background. means for sequentially detecting a plurality of character images (hereinafter referred to as character blocks); and a means for sequentially detecting a plurality of character images (hereinafter referred to as character blocks); Set a prediction interval for character pitch based on a frequency distribution table that stores the frequency of distance between characters and the height of multiple character clusters, and use the frequency distribution table to calculate the most frequent value n ₁ and the distance between most frequent value character clusters. p ₁ is detected within the prediction interval, and the distance between character blocks p ₁ is set as the estimated character pitch p^(1), and a prediction interval of k times the character pitch (however, k = 2, 3, etc.) is sequentially set. The estimated character pitch p^(k-1) (where k=
2, 3...) and uses a frequency distribution table to detect the most frequent value n _k and the distance p _k between the most frequent value character blocks within the prediction interval; Distances p ₁ , p ₂ ,...p _k and most frequent values n ₁ , n ₂ ,...n _k
There is obtained a character pitch detection device characterized in that it has means for updating the estimated character pitch p^(k-1) by performing maximum likelihood estimation of the estimated character pitch p^k using .

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, a white background indicated by diagonal lines indicates a rectangular area containing separable character images, ie, character blocks. Hi in the figure (i=1...7)
indicates the height of each character block. In the figure Vi(i=
1...7) is an example of the distance between character blocks, and indicates the distance from the starting position of each character block to the starting position of the next appearing character block. Here, the distance between character blocks is not only the distance measured between the starting edges of each character block, as shown in the example of the symbol Vi (i = 1...7) in Figure 1, but also the distance measured between the ends of each character block. It also includes the distance measured by . That is, the distance between character blocks means the distance measured from the start (end) position of each character block to the start (end) position of the next or subsequent character blocks. Note that the width of a character block that appears at the end of a character line, as shown by symbol V10 in FIG. 10, can be treated as a special distance between character blocks, but in the present invention, it is not included in the distance between character blocks. Make it not exist.

FIG. 2 is an example of the frequency distribution of distances between a series of character blocks as shown in FIG. In the figure, the horizontal axis V of the frequency distribution indicates the value of the distance V between character blocks, and the vertical axis NUM indicates the frequency value at an arbitrary distance between character blocks. Therefore, the principle of the present invention will be explained using FIG. 2.

The height H ₁ of the plurality of character blocks shown in Fig. 1,
The average height H _n of H ₂ , ... and the coefficients α ₁ , α ₂ (however,
A prediction interval C ₁ is set from α ₁ <α ₂ ). Next, within the prediction interval C ₁ , a certain tolerance width △γ (in the figure, △γ=
In 1), the most frequent value n ₁ and the distance p ₁ between character blocks having the most frequent value n ₁ are determined. In addition, in the figure, the most frequent value n ₁
becomes 5. Here, the distance between character blocks p ₁ is assumed to be the estimated character pitch p^(1). Normally, if there is no contact between characters, and the most frequent value n ₁ is large, the estimated character pitch p^
Although (1) can be regarded as character pitch, under the conditions described above, the estimation error may become large if only p^(1) is used.

Therefore, from the estimated character pitch p^(1), a prediction interval C ₂ that is twice the character pitch is set from 2・p^(1)±α ₃ , and within the prediction interval C ₂ , a certain allowable width △γ Find the most frequent value n ₂ and the distance p ₂ between character blocks having the most frequent value n ₂ . Here, the constant α ₃ can also be set depending on the precision of the estimated character pitch p^(1), for example, the most frequent value n ₁ .

Next, the estimated character pitch p^(1) is updated as follows to obtain a more accurate estimated character pitch p^(2).
More accurate estimated character pitch is performed by maximum likelihood estimation using the obtained most frequent value inter-character cluster distances p ₁ , p ₂ and most frequent values n ₁ , n ₂ .

For example, p^(2)= ¹ / ₂ 〓 ^K=1 k・√ _k・(√ ₁・p ₁ +
By calculating 2.√ _{2.p 2} /2), the estimated character pitch p^(2) can be obtained.

Similarly, from the estimated character pitch p^(2), a prediction interval C ₃ that is three times the character pitch is set from 3p^(2)±α ₃ , and the most frequent value n ₃ and the most frequent value n ₃ are The distance p ₃ between character blocks is calculated, and the estimated character pitch p^(3) is updated in the same way. In general, the linear best estimated character pitch p^( )
can be calculated from p^()= _l 〓 ^k=1 w(k, n _k )·p _k /k.

The coefficient w(k, n _k ) mentioned above is determined by the integer value k and the most frequent value n _k , for example, k・√ _k /
Obtained from _l 〓 ^k=1 k・√ _k . Furthermore, it goes without saying that the aforementioned maximum likelihood estimate p^() can be easily calculated by the addition section, multiplication section, and division section.
Furthermore, the calculation time can be reduced by changing the order of addition, multiplication, and division.

FIG. 3 is a logic block diagram showing a specific embodiment of the present invention. A scanning device 1 optically scans a character string image written on a paper surface, converts it into an electrical signal, and writes it into a character string image memory 2 after binary quantization. The character block extraction device 3 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 the character block register 4.
Note that the size of a character block represents the width and height of the character block. Further, such a character extraction device can use, for example, the technique disclosed in Japanese Patent Application No. 1983-27512 filed by the same applicant. The control device 7 sequentially calculates the distance between character blocks from the starting position of the character blocks transferred from the character block register 4, and calculates the frequency value that is the content of the address position of the corresponding distance between character blocks in the frequency distribution table 6. Increment. In this way, the frequency distribution of distances between character blocks as shown in FIG. 2 is generated in the frequency distribution table 6 constructed from memory. still,
It is assumed that the frequency distribution table 6 is initially initialized to 0. Next, the control device 7 calculates an average height H _n from the heights of the plurality of character blocks stored in the character block register 4 and transfers it to the prediction interval calculation unit 8 .

The constant register 20 stores the coefficients α ₁ ,
α ₂ (however, α ₁ < α ₂ ) is stored in the constant register 21.
stores the coefficient α ₃ shown in FIG. 22 is a counter, and a value k (however, the initial value is 1) is set. When the control device 7 inputs the average height H _n to the prediction interval calculation unit 8, the prediction interval calculation unit 8 inputs the coefficients α ₁ and α ₂ from the constant register 20, and calculates α ₁ ·H _n and α ₂ ·H _n are calculated as the lower and upper limits of the prediction interval described above, and are transferred to the most frequent character block distance detection unit 9. On the other hand, when the estimated character pitch p^(k), which will be described later, is input to the prediction interval calculation unit 8 by the control device 7, the prediction interval calculation unit 8 inputs the coefficient α ₃ from the constant register 21,
Furthermore, by inputting the counter value k from the counter 22, k・p^(k)−α ₃ and k・p^(k)+α ₃ are calculated as the lower limit value and upper limit value of the prediction interval mentioned above, and the most frequent The data is transferred to the character block distance detection unit 9.

The most frequent character block distance detection unit 9 uses the frequency value of the distance between character blocks that falls within the lower limit and upper limit of the prediction interval inputted from the prediction interval calculation unit 8 to the frequency distribution table 6 through the control device 7. The character block distance p _k and the most frequent value n _k having the most frequent value within a certain allowable width Δγ (where Δγ = 1, 2, . . . ) are determined and stored in the register 10. Note that the distance p _k between character blocks and the most frequent value n _k are set at predetermined positions in the register 10 according to the value k of the counter 22. The character pitch calculation unit 11 calculates the value k of the counter 22 and the distances between character blocks p ₁ , p ₂ , . . . p _k stored in the register 10.
and the most frequent values n ₁ , n ₂ , . . . to calculate the estimated character pitch p^(k) and store it in the estimated character pitch register 12. When the estimated character pitch p^(k) is set in the estimated character pitch register 12, the control device 7 increments the counter 22 by 1 and sets the estimated character pitch p^(k) to the prediction interval calculation unit 8. will be forwarded to.

The estimated character pitch p^(k) mentioned above is obtained by the calculation formula shown in FIG.

The above operation is repeated, and when all the frequencies of the distances between character clusters on the frequency distribution table 6 are checked, the optimum estimated value of character pitch is set in the estimated character pitch register 12. Single character separation means 5
performs character-by-character separation based on the character pitch set in the estimated character pitch register 12 and the position and size information of the character block stored in the character block register 4. The single character separation means 5 can be performed using a known technique.

Note that the effect will be greater if characters such as "," and "." are removed in advance using a conventional noise removal method and then the character pitch is detected using the device of the present invention, especially when the number of characters is small. The effect is great in some cases.

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

[Brief explanation of the drawing]

FIG. 1 is a diagram showing an example of a part of a character string image to which the present invention is applied, FIG. 2 is a diagram showing an example of the frequency distribution of distances between character blocks on paper, and FIG.
The figure is a logical block diagram showing a specific embodiment of the present invention. 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, 6 is a frequency distribution table, 8 is a prediction interval calculation unit, and 9 is a distance detection between most frequent character blocks 10 is a register, 11 is an estimated pitch calculation unit, 12 is an estimated character pitch register, 20 and 21 are constant registers,
22 is a counter, 5 is a character separating means, and 7 is a control device.

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 detecting clusters; and a frequency distribution table for calculating distances between character clusters indicating distances between starting positions or terminal positions of the plurality of character clusters, and storing frequencies of the distances between character clusters. , setting a prediction interval for character pitch from the heights of the plurality of character blocks;
Using the frequency distribution table, the most frequent value n ₁ and the most frequent value inter-character block distance p ₁ are detected within the prediction interval, and the most frequent value inter-character block distance P ₁ is calculated as the estimated character pitch p^(1 ), and an estimated character pitch p^(k-1) (where k=
2, 3...) and using the frequency distribution table to detect the most frequent value n _k and the most frequent value inter-character block distance p _k within the prediction interval; The estimated character pitch is calculated using the most frequent value inter-character block distances p ₁ , p ₂ , ... p _k and the most frequent values n ₁ , n ₂ , ... n _k .
A character pitch detection device comprising means for updating the estimated character pitch p^(k-1) by performing maximum likelihood estimation of p^(k).