JPH07107699B2 - Character / figure recognition device - Google Patents

Description

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a character / graphics recognizing device, and more particularly, to a large classification process for selecting a plurality of reference patterns that are most similar to an input character / graphics as candidates. is there.

2. Description of the Related Art Conventionally, in a character / figure recognition method that determines the similarity between an input character / figure and a reference pattern based on the distance between the characteristics of the input character / figure and the characteristics of the reference pattern, the input character / figure feature and the total reference pattern feature are The distances are calculated, the obtained distances are ranked in ascending order, and the rank of similarity is judged. Therefore, the time required for the distance calculation and the time required for rearranging the calculation results in ascending order make up a large proportion of the time required for the entire character / graphics recognition processing.

Therefore, in order to speed up the distance calculation process, instead of the Euclidean distance that requires the sum of products calculation, the city block distance calculated only by addition and subtraction is adopted, and in order to speed up the rearrangement process, high-speed rearrangement is performed. Ingenuity such as the adoption of algorithms has been paid.

However, it is only the reference pattern of a very small part having a small feature-to-feature distance from the input character graphic that affects the recognition. It is not necessary to have a value, just to know that the distance is large and it does not resemble the input character graphic. Therefore,
In the conventional method, the distance was calculated even for unnecessary reference patterns. Further, since the time required for rearrangement is greatly reduced if the number of rearrangement targets is small, it can be said that the conventional method is wasteful in terms of rearrangement processing.

The present invention has been made in view of the above problems, and an object thereof is to provide a character recognition device capable of high-speed processing.

Means for Solving Problems In order to solve the above problems, the character recognition device of the present invention causes the distance calculation unit to sequentially compare the input character graphic feature and each reference pattern feature to calculate the distance. In the process of performing, a distance calculation is performed between one reference pattern and an intermediate rank buffer that stores a fixed number of distances in pairs in order from the smallest distance obtained and pairs with the reference pattern identifier corresponding to that distance. And the calculation result is smaller than the maximum value of the distance stored in the intermediate rank buffer, the calculation result and the corresponding reference pattern identifier are paired and registered in the intermediate rank buffer, Further, the intermediate rank buffer updating means for rearranging the data in the intermediate rank buffer in ascending order of distance, the distance calculation between the input character graphic feature and each reference pattern feature In the process, the mid-calculation value is always compared with the maximum value of the distance stored in the intermediate rank buffer, and when the mid-calculation value becomes equal to or larger than the maximum value of the distance in the intermediate rank buffer,
The distance calculation means interrupts the distance calculation with the reference pattern being calculated and moves to the distance calculation with the next reference pattern.

Action Of the distance calculation results for the input character / graphic features and the individual reference pattern features, only a fixed number of them are stored in the intermediate rank buffer.

Therefore, the rearrangement operation for rearranging the distances in ascending order only needs to rearrange a fixed number in the intermediate rank buffer, and the time required for the rearrangement processing is greatly reduced. In addition, in the process of calculating the distance between the input character / graphic feature and each reference pattern feature, the mid-calculation value is always compared with the maximum value of the distance stored in the middle rank buffer, and the middle calculation value At the time when it becomes more than the maximum value of the distance inside, that is, even if the distance calculation is continued and the result is obtained,
Since the result is not registered in the intermediate rank buffer, and therefore it is found that it does not affect the recognition result, the distance calculation with the reference pattern being calculated is terminated, so the calculation amount in the distance calculation can be greatly reduced. .

Example An example of the present invention will be described with reference to the drawings. The figure is a block diagram of a distance calculation unit of the character / graphic recognition device.

The distance calculation unit 1 calculates a distance between the reference pattern feature dictionary 2 storing the features of each reference pattern and the features of the individual reference patterns stored in the reference pattern feature dictionary 2 and the features of the input character graphic. Part 3, n of the distances from which the calculation has been completed, from the smallest distance, that is, the intermediate rank buffer 4 that stores the distance value of the nth position and the identifier of the reference pattern corresponding to that distance, and the calculation result Distance
It is composed of an intermediate rank buffer updating unit 5 registered in the intermediate rank buffer 4 together with the identifier of the corresponding reference pattern.

Further, the distance calculation unit 3 always calculates the value in the middle of the distance calculation as
An intermediate value register 6 to be stored, and a comparing section 7 for comparing the contents of the intermediate value register 6 with the maximum value 9 of the distance stored in the intermediate rank buffer 4 are compared.

In the initial state, the initial value of the intermediate rank buffer 4 is an identifier indicating a sufficiently large distance value and "empty", and the value of the intermediate value register 6 is 0.

The distance calculation unit 1 receives a feature 8 extracted from a character or graphic input to the character / graphics recognition device according to a predetermined rule. Features are represented by N-dimensional vectors. Further, the reference pattern feature dictionary 2 stores the features of each reference pattern as an N-dimensional vector like the input features 8.

Here, the distance is defined as follows.

The input feature vector is (f ₀ , f ₁ , ..., f _N-1 ), and the kth dictionary data is And the distance However, there is no problem using the city block distance or the distance defined by another definition.

The operation of the distance calculator 1 will be described with reference to FIG. The input feature 8 input to the distance calculation unit 1 is sent to the distance calculation unit 3. The distance calculation unit 3 reads the feature vector of the first reference pattern from the reference pattern feature dictionary 2, takes the difference from the input feature for each element of the feature vector, and sequentially adds the squared value of the difference to the intermediate value register 6. Put in. The comparing unit 7 compares the value of the intermediate value register 6 with the maximum value 9 of the distance stored in the intermediate rank buffer 4 each time a value is added to the intermediate value register 6.

As a result of the comparison, if the value of the intermediate value register 6 is smaller than the maximum value 9 of the distance of the intermediate rank buffer, the distance calculation unit 3 continues the distance calculation, that is, the above processing is performed for the next element of the same reference pattern. repeat.

As a result of the comparison in the comparison unit 7, if the value of the intermediate value register 6 is equal to or greater than the maximum value 9 of the intermediate rank buffer distance,
The distance calculation unit 3 terminates the distance calculation with the reference pattern being calculated and reads the next reference pattern. At the same time, the intermediate value register 6 is reset to 0. After that, the same processing is repeated for the newly read reference pattern.

If the distance calculation ends without being cut off,
That is, when the square sum of the differences between the reference pattern features and the input features has been calculated for all the elements of the N-dimensional vector, the distance calculation unit 3 pairs the reference pattern identifiers corresponding to the distances of the calculation results. And outputs it to the intermediate rank buffer updating unit 5. After that, the intermediate value register 6 is reset to 0 and the next reference pattern is read. After that, the same processing is repeated for the newly read reference pattern.

The intermediate rank buffer updating unit 5, which has received the distance value and the reference pattern identifier, newly registers them in the intermediate rank buffer 4, and rearranges the contents of the intermediate rank buffer 4 in ascending order of distance.

When the distance calculation unit 3 completes the processing for all the reference patterns in the reference pattern feature dictionary 2, the contents of the intermediate rank buffer 4 start from the smallest distance between the input features and all the reference patterns. The n distances and the reference pattern identifiers corresponding to the distances are arranged in ascending order of the distance, which is the output 10 of the distance calculation unit 1 as it is.

EFFECTS OF THE INVENTION As described above, according to the present invention, the calculation amount in the distance calculation unit, which occupies a large proportion of the processing time, can be significantly reduced in the character / graphic recognition apparatus. As a result, a high-speed character and figure recognition device can be realized, which is extremely useful in practice.

[Brief description of drawings]

FIG. 1 is a block diagram of a distance calculation unit for a character / graphics recognition device according to an embodiment of the present invention. 1 ... distance calculator, 2 ... reference pattern feature dictionary, 3 ... distance calculator, 4 ... intermediate rank buffer, 5 ... intermediate rank buffer updater, 6 ... intermediate value register, 7 ... comparator .

Claims (1)

[Claims] 1. A distance between a feature extracted from an input character graphic according to a predetermined rule and a feature extracted according to the same rule from a plurality of reference patterns of a recognition target character graphic is calculated, A reference pattern having a small inter-feature distance is used as a candidate character graphic, and a distance calculation unit is provided that sequentially calculates inter-feature distances between an input character graphic and a plurality of reference patterns and ranks them in ascending order of distance. The distance calculation unit sequentially compares the input character graphic features and the individual reference pattern features, and in the process of calculating the distance, a small number of the obtained distances are calculated in order from the smallest distance.
The calculation of the distance between one reference pattern and the intermediate rank buffer that is stored as a pair with the reference pattern identifier corresponding to the distance is completed, and the calculation result is the maximum value of the distance stored in the intermediate rank buffer. If it is smaller than the above, the reference pattern corresponding to the calculation result is paired with the identifier, registered in the intermediate rank buffer, and the data in the intermediate rank buffer is rearranged in ascending order of distance. In the process of calculating the distance between the means, the input character graphic feature, and the individual reference pattern feature, the midway calculation value is always compared with the maximum value of the distance stored in the intermediate rank buffer, and the midway calculation value is the intermediate value. When the distance in the rank buffer exceeds the maximum value, the distance calculation with the reference pattern being calculated is stopped and the distance calculation with the next reference pattern is started. Character graphic recognition device, characterized in that it comprises a release calculation means.