JPH0471232B2 - - 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 character string images written on paper into individual characters. 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 string image that contains many characters in contact, you may misjudge the number of characters in contact, or the separation position may be inaccurate. or be cut off.

Furthermore, in order to perform character-by-character separation under the above conditions, it is necessary to detect not only a highly accurate estimate of character pitch, but also the estimation error of character pitch, which indicates how accurate the character pitch is. becomes.

Given such estimation accuracy, for example,
It can also be used as a parameter when absorbing minute errors in character pitch using the characteristics of character pattern images.

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 estimated character pitch while clustering starting from the average height of , and also calculates an estimation error.

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 character by character, there is a means for sequentially detecting character blocks, and a frequency distribution table that calculates the distance between character blocks indicating the distance between the start or end positions of a plurality of character blocks, and stores the frequency of the distance between character blocks. Then, set the prediction interval of character pitch from the height of multiple character clusters, and use the frequency distribution table to calculate the distance between the most frequent character clusters.
Means for detecting p ₁ within the prediction interval and the distance between the most frequent character blocks p _k (however, K = 1, 2...)
means for setting the existence range of k characters from , calculating the variance σ ² _k and the number of samples n _k in the distance between a plurality of character blocks belonging to the existence range, and the calculated distance between k most frequent character blocks. p ₁ , p ₂ ... p _k and variance σ ² ₁ , σ ² ₂ ,
A means for calculating the estimated character pitch P∧(k) and the estimation error by maximum likelihood estimation using ...σ ² _k and the number of samples n ₁ , n ₂ ...n _k , and from the estimated character pitch P∧(k), Character pitch detection characterized by having means for setting a prediction interval that is (k+1) times the character pitch, and detecting the most frequent value inter-character block distance p _k+1 within the prediction interval using a frequency table. A 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, 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 Figure 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 number at a given 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, α ₁
<α ₂ ), the prediction interval C ₁ is set. Next, within the prediction interval C ₁ , a certain tolerance width △τ (in the figure, △τ =
1) Find the distance p ₁ between the most frequent character blocks. The upper limit value of the existence range s ₁ of one character is calculated from the mode character distance p ₁ as, for example, p ₁ +p ₁ /2. Here, the lower limit value of the existence range s ₁ of one character is assumed to be p ₁ /2. For the distances between n ₁ character blocks (hereinafter referred to as the number of samples n ₁ ) within the above-mentioned existence range s ₁ , the variance σ ² ₁ with respect to the mode value inter-character block distance p ₁ is calculated.

Next, we calculate the estimated character pitch,
Since only the mode distance between character blocks _p1 is detected, the estimated character pitch p∧(1) is _p1 . Further, the estimated error Δε(1) of the character pitch at this point can be expressed as a variance σ ² ₁ .

Next, 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 tolerance width △ Set τ,
Detect the distance p ₂ between the most frequent character blocks. Here, α ₃ may be a constant, or may be set based on the standard deviation σ of the variance σ ² ₁ , for example. When the mode distance between character clusters p ₂ is detected, the existence range of the two characters s ₂ is similarly detected.
For example, the upper limit value of is calculated from p ₂ +1/2·(p ₂ /2), and the variance σ _{2 2 is calculated for the distance between character blocks of the number of samples n 2 in} the above-mentioned existence range s ² .

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 mode character block distances p ₁ , p ₂ and sample numbers n ₁ , n ₂ .

For example, p∧(2)=1/ ₂ Σ ^k=1 k・√ _k・(√ ₁・p ₁ +2・√ ₂・
By calculating p ₂ /2), the estimated character pitch p∧(2) can be obtained.

Also, the estimation error △ε(2) at this point is calculated as follows, for example: △ε(2)=1/ ₂ Σ ^k=1・√ _k・(√ ₁・σ ² ₁ +2√ ₂・σ ² ₂ ) You can get it by doing.

Hereafter, in the same way, estimated character pitch p∧(3), p∧(4)
The estimated character pitch is updated sequentially.

Therefore, the distances between l mode character blocks p ₁ , p ₂ ,...
…p _l , number of samples n ₁ , n ₂ , … n _l and variance σ ² ₁ σ ² ₂ …
Using σ ² _l , the obtained maximum likelihood estimated character pitch p∧(l) can be calculated from p∧(l)= _l Σ ^k=1 w(k, n _k )·4 _k /k. Also, the estimation error at this point △
ε(l) can be calculated from Δε(l)= _l Σ ^k=1 w(k, n _k )·σ ² _k .

The above-mentioned coefficient w(k, n _k ) is determined by the integer value k and the most frequent number n _k and can be obtained from, for example, k·√ _k / _l Σ ^k=1 k·√ _k . Furthermore, it goes without saying that the maximum likelihood estimation value p∧(l) and the estimation error Δε(l) described above are easily calculated by the addition section, the multiplication section, and the division section. Furthermore, the calculation time can be reduced by changing the order of the addition, multiplication, and division sections.

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. still,
The size of a character block represents the width and height of the character block. Further, such a character block extraction device is disclosed in, for example, Japanese Patent Application No. 56-27512 filed by the same applicant.
The technique shown in the patent specification can be used. 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 number 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, a 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 controls the character block register 4
The average height from the heights of multiple character blocks stored in
H _n is calculated and transferred to the prediction interval calculation unit 8.
The constant register 20 stores the coefficients α ₁ and α ₂ shown in FIG.
(However, α ₁ <α ₂ ), and 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 mode character block distance detection unit 9. On the other hand, when the control device 7 inputs the estimated character pitch p∧(k), which will be described later, to the prediction interval calculation unit 8, the prediction interval calculation unit 8 inputs the coefficient α ₃ from the constant register 21, Furthermore, input the counter value k from the counter 22,
k·p∧(k)−α ₃ and k·p∧(k)+α ₃ are calculated as the lower and upper limits of the aforementioned prediction interval, and are transferred to the mode character block distance detection unit 9.

The mode character block distance detecting unit 9 calculates the frequency of the distance between character blocks that falls within the lower limit and upper limit of the prediction interval inputted from the prediction interval calculating unit 8, and calculates the frequency number of the distance between character blocks, which is inputted from the prediction interval calculation unit 8, into a frequency distribution table. 6, the distance p _k between the most frequent character blocks is determined using a constant allowable width Δτ (where Δτ=1, 2, . . . ), and is stored in the register 10. still,
The most frequent character block distance p _k is set at a predetermined position in the register 10 according to the value k of the counter 22. The existence interval calculation unit 11 calculates the value k of the counter 22.
Read the mode character block distance p _k set at a predetermined position in the register 10 _{according to} , to a predetermined position in the register 12.

Note that when the value k of the counter 22 is 1, the register 1
Distance between mode character blocks stored in a predetermined position of 0
Read p ₁ and calculate p ₁ + 1/2 · p ₁ as the upper limit of the existence range of one character, and simultaneously calculate p ₁ - 1/2 · p ₁ as the lower limit of the existence range of one character. and transfers it to a predetermined position in the register 12.

The character block distance variance calculation unit 13 uses a counter 22
According to _{the value} k _of k-1) (however, when k=1, p ₁ -1/2p ₁ ) and the upper limit p _k +1/2 (p _k /k) are used to create a frequency distribution table via the control device 7. 6, the distance between the character blocks of _n samples belonging to the above-mentioned existence range.
V _i (i=1...n _k ) is read out sequentially, the variance σ ² _k is calculated, and the variance σ ² _k and the number of samples n _k are stored in the distribution register 14.
transfer to the specified location.

The aforementioned variance σ ² _k can be obtained by calculating, for example, 1/n _kok Σ ⁱ⁼¹ (V _i −p _k ) ² .

The estimated character pitch calculation unit 14 calculates the value k of the counter 22, the distances between character blocks p ₁ , p ₂ , ... p _k stored in predetermined positions of the register 10, and the dispersion register 13.
Using the variances σ ² ₁ , σ ² ₂ , ...σ ² _k and the number of samples n ₁ , n ₂ ...n _k stored in predetermined positions of
and estimated error Δε _k are calculated and stored in the character pitch information register 15.

When the estimated character pitch p∧(k) and estimation error △ε _k are set in the character pitch information register 15, the control device 7 increments the counter 22 by one and predicts the estimated character pitch p∧(k). Section calculation unit 8
Transfer to.

The estimated character pitch p∧(k) and estimation error △ε mentioned above
(k) can be obtained, for example, using the calculation formula shown in the explanation of FIG.

When the above operations are repeated and all the frequencies of the distances between character clusters on the frequency distribution table 6 are investigated, the optimal estimated value of character pitch and the estimation error △ε
(k) is set in the character pitch information register 15. The one-character separation position determining unit 5 selects the characters set in the character pitch information register 15 and the estimated error △.
Based on ε(k) and the position and size of the character block stored in the character block register 4, character images are separated into individual character images. The single character separation position determining unit 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. It is very effective in some cases.

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 between character blocks 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
It is a figure which shows an example of the frequency distribution of the distance between character blocks on a paper surface. FIG. 3 is a logic 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 the distance between most frequent character blocks Detection unit, 10 is a register, 11 is an existence interval calculation unit, 12 is a register, 13 is a character block distance variance calculation unit, 14 is a variance register 14, 15 is an estimated character pitch calculation unit,
16 is a character pitch information register, 20 and 21 are constant registers, 22 is a counter, 5 is a one character separation position determination unit, 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 and extracts character pitch for separating each 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;
Means for detecting the distance p ₁ between the most frequent value character blocks in the prediction interval using the frequency distribution table, and the distance p _k (where k =
1, 2...), and means for calculating the variance σ ² _k and the number of samples n _k in the distance between the plurality of character blocks belonging to the existing range;
The calculated distances between the k most frequent character blocks p ₁ , p ₂
...p _k and the variance σ ² ₁ , σ ² ₂ ...σ ² _k and the number of samples n ₁ ,
A means for calculating estimated character pitch p∧(k) and estimation error by optimum estimation using n ₂ ...n _k , and from said estimated character pitch p∧(k), it is (k+1) times the character pitch. A character pitch detection device characterized by comprising means for setting the prediction interval and using the frequency table to detect the most frequent value inter-character block distance P _k+1 within the prediction interval.