JP3209197B2 - Character recognition device and recording medium storing character recognition program - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to an optical character recognition technology for reading a character written on paper or the like by an optical sensor and, more particularly, for recognizing a character string in which a plurality of characters are arranged like a word or a sentence. And a character recognition device and method.

[0002]

2. Description of the Related Art In a conventional character recognition apparatus of this kind, a character segmentation for identifying a boundary of a character in a character string, and
A character string is read by combining character recognition for reading each cut-out character.

[0003] As an example of a conventional character recognition technique, for example, in the document "Shu Liang et al., 1994, Segmentation of Touching Characters in Printed Document Recognition, Pattern Recognition, Vol. 27, No. 6, No., pp. 825-840
(Su Liang et al., Segmentation of Touching Charact
ers in Printed Document Recognition, Pattern Recog
nition, Vol. 27, No. 6, pp. 825-840, 1994). "

In the method described in this document, a candidate for a character boundary is extracted using the shape of a projection histogram and information derived from the shape of the projection histogram, and one of character strings sandwiched between any two character boundaries is extracted. All parts are extracted as character candidates (character extraction).

Next, character recognition is performed on all character candidates, and the recognition result and its likelihood (score) are calculated for each.

Finally, character candidates are selected so that the score becomes maximum when the character strings are concatenated, and at the same time, a cutout position of a character string considered to be correct is determined.

[0007] In addition, various methods have been proposed in the past, but most of the methods use only different information for character extraction, or comprehensively extract characters in character strings without character extraction. The only difference is that character recognition is performed at every part to determine the optimal cutout position, or the method of character recognition and the method of identifying characters extracted from a character image by character recognition are different.

In the above-described example, print characters are to be recognized.
Similarly, in many cases, character segmentation and character recognition are configured as separate modules, and a procedure of reading a character string by combining them is adopted.

[0009]

However, in the above-mentioned prior art, since the processing systems for character extraction and character recognition are separately constructed and used, particularly in the recognition of handwritten character strings, a character string specific to a character string is used. There is a problem in that it is not possible to cope with the deformation of the pattern, which often causes erroneous recognition.

For example, in the case of a character string written in continuous writing like a cursive English sentence, the position of the pen at the time when the character "a" has been written is at the bottom, but the character position "o" has been written. The position of the pen at the point of time is at the top. Therefore,
Even if it is the same character, it is written after "a" or "o"
The shape of the pattern changes depending on whether it is written next.
Referring to FIG. 6, the character string "a"
b "and" ob ", even if the same" b "
"B" following "a" is from the lower left side of the rectangle surrounding "b".
"B" following "o" starts from approximately the center of the left side of the rectangle surrounding "b".

[0011] This is a character string-specific deformation that cannot occur with individual characters.

[0012] Such a modification is caused by a conventional character recognition processing system constructed by learning only individual characters.
It is not possible and often causes misperception.

A similar problem is observed not only with alphabets but also with numerals. For example, the direction of travel of the pen at the end of writing “5” is the same as the direction of the character string,
The character following "5" is often written connected to "5". As a result, as shown in FIG. 7, the character written after "5" is deformed so as to be smoothly connected to "5".

For this reason, in a conventional character recognition processing system which does not take into account the deformation unique to a character string, erroneous recognition is likely to occur.

That is, in general, a character string has a dependency relationship between adjacent characters, and tends to affect each other and cause deformation.

To solve the problem that a character is deformed depending on an adjacent character, a method of constructing a dictionary by learning two templates of the number of character types using two adjacent characters as one pattern is also considered. Can be However, in the arrangement of two characters, variations in the deformation as patterns become extremely diverse, and an enormous amount of learning data is required. Further, since the number of templates required is the square of the number of character types, the problem of insufficient training data becomes serious.

As described above, it is understood that the method of learning the square template of the character type with two characters as one pattern is not suitable for practical use.

Therefore, the present invention has been made based on the recognition of the above technical problem, and an object of the present invention is to reduce the influence of the deformation of the character shape caused by the dependence between adjacent characters. That is, an object of the present invention is to provide a character recognition apparatus and method that is robust against character contact and continuous writing.

[0019]

SUMMARY OF THE INVENTION In order to achieve the above object, the present invention provides an image storage means for inputting and storing a character string image, and a partial pattern corresponding to one character from the character string image obtained from the image storage means. Character segmenting means for detecting a segmentation position candidate for obtaining a character, and an individual character pattern candidate, which is a partial pattern corresponding to one character, is generated based on the segmentation position candidate obtained from the character segmentation unit. A character string reading means for outputting an optimum character string reading result, and an individual character pattern candidate generated by the character string reading means recognized according to a request from the character string reading means, and a character recognition result and a character recognition result Character recognition means for outputting a character recognition score representing the likelihood of a character pattern, and a character string used by the character recognition means for identification of one-character pattern candidates and score evaluation. A two-character dictionary storage means for storing an adjacent two-character dictionary for identifying individual characters by using the character pattern candidates for two adjacent characters. With, before
The character recognizing means receives a character pattern from the character string reading means.
When receiving character candidates and performing character recognition,
Receive character pattern candidates and the character pattern candidate immediately before
If the character pattern candidate to be recognized belongs to a certain character type,
If specified, the given character pattern candidate to be recognized
The probability of occurrence of the character pattern candidate immediately before
Using the probability that the previous character pattern occurs, the sentence to be recognized is
Shows the likelihood that a character pattern candidate belongs to that character type.
Score.

[0020]

Embodiments of the present invention will be described. First, the principle of the character recognition device of the present invention will be described. According to an embodiment of the present invention, in the embodiment, (a) when constructing a character recognition processing system, a character string is used as training data to learn characters directly from the character string; When calculating the character recognition score by comparing the i-th character pattern Xi with the dictionary pattern w, a conditional probability to which a condition that a pattern Xi-1 occurs as the (i-1) th character immediately before it is added. By calculating as P (Xi | Xi-1, w), robust character recognition that is not easily affected by character shape deformation caused by dependence between adjacent characters, such as character contact or continuous writing, can be achieved. Has been realized.

Here, the conditional probability P (Xi | Xi−
The value of (1, w) is the score P (Xi-1, Xi | w) in units of two adjacent characters obtained by combining a certain character and the character immediately before it.
And the ratio of the score P (Xi-1 | w) in units of one character, P (Xi-1, Xi | w) / P (Xi-1 | w) (1) or simplified , P (Xi-1, Xi | w) / P (Xi-1) (2)

The present invention provides, as another embodiment, (a)
When constructing a character recognition processing system, a character string is directly learned from the character string by using the character string as training data, and (b) the i-th character pattern Xi in the input character string is compared with the dictionary pattern w. When calculating the character recognition score, a pattern Xi-1 occurs as the (i-1) th character, and the (i-1) th character pattern Xi-1 belongs to a character category represented by the dictionary pattern w '. Conditional probability P with the condition
This is realized by calculating as (Xi | Xi-1, w ', w).

Here, the conditional probability P (Xi | Xi−
The value of (1, w ′, w) is the score P (Xi−1, Xi) in units of two adjacent characters obtained by combining a certain character and the immediately preceding character.
| W ′, w) and the score P (Xi−1 |
w ′, w) ratio P (Xi−1, Xi | w ′, w) / P (Xi−1 | w ′, w) (3) or a simplified version of P (Xi−1, Xi | w ', w) / P (Xi-1 | w') (4) Hereinafter, the present invention will be described in detail with reference to examples.

[0024]

FIG. 1 is a block diagram showing the configuration of an embodiment of the present invention. Referring to FIG. 1, in this embodiment, an image storage unit 1 that captures and stores an input character string image by an optical sensor and a candidate for a boundary between adjacent characters is determined from the character string image received from the image storage unit 1. Character extraction means 2 for detecting as a cutout position candidate, and character recognition processing is called for each individual character pattern when a character string image is divided by selecting some cutout position candidates to calculate a recognition score of the entire character string Then, a character string reading means 3 for outputting an optimal cutout and recognition result as a character string reading result, and performing a recognition process on a character pattern in response to a request from the character string reading means 3 to obtain one character type and a recognition score. A character recognition unit 4 to return, a one-character dictionary storage unit 5 for calculating a score of the likelihood of occurrence of a single character pattern, and a pattern corresponding to two adjacent characters are used. Te to calculate the recognition score and the second character of the character types with the adjacent 2 character dictionary storage unit 6, a. The image storage unit 1, character extraction unit 2, character string reading unit 3, character recognition unit 4, one-character dictionary storage unit 5, and adjacent two-character dictionary storage unit 6 have their functions controlled by a program executed on a computer. Can be realized.

When character recognition is performed by the character recognizing means 4, preprocessing is generally performed on an input image. As the preprocessing, for example, a multi-valued image is more easily handled. Binary processing to convert to a value image, normalization processing to shape character size, stroke interval, inclination, etc., noise removal processing to remove fine dirt and blurring in images, useful for identifying input patterns, etc. Various known processes such as a feature extraction process for converting into a small amount are used. In the embodiment of the present invention, these processes may of course be introduced into the character recognition means 4 if necessary. In addition, these preprocessings can be applied in any order regardless of the context.

Furthermore, if the feature quantity extracted by the feature extraction processing is of a type that can be divided along with the division of the image by character segmentation (the feature quantity is calculated for each local area in the input image), By performing these pre-processing in the character extracting means 2 or the image storing means 1 together with the feature extracting processing, it is also possible to collectively extract the features from the input character string image.

As an example of the feature extraction process, a process of calculating the strength of each character line direction as a feature will be described with reference to a specific example of an input image shown in FIG.

The direction of the character line is vertical (90 ° direction) and horizontal (0
° direction) and diagonal (45 ° and 135 ° directions) in four steps, and in each direction,
The length of the character line is measured for each of the small areas divided in the 63 horizontal sections.

Here, the length of the character line can be measured as the number of black pixels connected in the corresponding direction. In a region where no black pixel exists, the length may be set to 0. In this way, a characteristic pattern based on the direction of the character line as shown in FIG. 4 is obtained from the input image written as “02062” shown in FIG.

In FIG. 4, the darker the black, the greater the characteristic value corresponding to the length of the character line. The feature pattern is divided into 16 regions in the vertical direction. Four regions from the top are 0 °, 45 °, 90 °, 13
This corresponds to a feature value in the direction of 5 °.

In the case of a feature amount in which the value of a feature is defined corresponding to a small area in an image as in this feature, if the cutout position of the character in the input image is determined, the small area Since the feature pattern can be divided in units,
The feature extraction process can be performed also in the upstream process of the character segmenting means 2.

The above-described example of the feature extraction processing can be placed in a later step in the character extracting means 2. Further, the input image may be used as it is as a kind of feature without performing the feature extraction process.

FIG. 2 is a flowchart for explaining the processing flow of one embodiment of the present invention. The operation of the embodiment of the present invention will be described in detail with reference to FIGS.

The image is optically input by a scanner or the like, stored in the image storage means 1, and sent to the character cutout means 2 (step 10 in FIG. 2).

The character cutout means 2 detects some cutout position candidates from the character string image, and sends the coordinate information and the character string image or the characteristic pattern obtained by converting the character string image by the characteristic extraction processing to the character string reading means 3. Send (step 11 in FIG. 2).

Some graphical information is used to detect a cutout position candidate. As the graphic information, for example, a projection histogram of a character string is calculated. For example, if the character string is written horizontally, a histogram projected in the vertical direction is calculated, and if the character string is written vertically, a histogram projected in the horizontal direction is calculated. Then, a position whose frequency is lower than a preset threshold value is set as a cutout position candidate.

As another cutout means using graphic information, the contour of a character string is tracked and its irregularities are measured.
A method of storing a position where the dent is larger than the threshold value as a cutout position candidate may be used.

Further, a method of obtaining a cutout position candidate using a plurality of graphic features together may be used.

Further, the extraction position candidate can be detected by a method not using graphic information. For example, when the graphical information is not used, the coordinates from the coordinates of the start position to the coordinates of the end position of the character string image are equally spaced, and all the separation points are stored as cutout position candidates. In this case, a large number of cutout position candidates are stored as the cutout position candidates, for example, about several times the assumed number of characters.

The character string reading means 3 performs character string image reconstruction processing (step 12 in FIG. 2), character string recognition (step 16 in FIG. 2), and result comparison and evaluation (step 1 in FIG. 2).
Perform each process of 7).

That is, the character string image received from the character extracting means 2 or the characteristic pattern obtained by converting the character string image by the characteristic extracting process and the coordinate information of the extracting position candidate are received, and the character pattern is extracted for all the character pattern candidates extracted at the extracting position. Character recognition is performed using the recognition means 4, and the recognition result and the recognition score are stored.

Then, a recognition result of a character pattern candidate string having the highest recognition score as a whole and having no duplication or skipping is selected and output as a character string reading result.

The procedure for searching for the optimum reading result will be described later.

When the character string reading means 3 sends a character pattern candidate to the character recognizing means 4, it sends not only the corresponding character pattern candidate but also the character pattern candidate immediately before it.

The character recognizing means 4 performs a character recognizing process of the corresponding character pattern candidate in consideration of these two adjacent character pattern candidates.

The character recognizing means 4 includes the character string reading means 3
Then, two adjacent character pattern candidates are received, character recognition processing for the latter is performed, a character recognition result (character type) and a character recognition score are calculated, and the result is returned to the character string reading means 3.

Here, the character recognizing means 4 sends two adjacent character pattern candidates Xi-1,
If Xi is received, the character recognition result wi of Xi
Is the probability P (Xi |) that the character pattern Xi occurs under the condition that the character type is w and the character pattern immediately before is Xi-1.
Xi−1, w) is determined as w that maximizes Xi−1, w).

The character recognition score at that time is P (X
i | Xi-1, wi).

In the actual calculation of the probability P (Xi | Xi−1, w), P (Xi | Xi−1, w) is not directly calculated, but P (Xi−1, Xi | w) / P ( Xi-1)... (5)

In the calculation of the approximate value, the numerator (dividend) P (Xi−1, Xi | w) is calculated based on the condition that the character type of the second character in the adjacent two-character pattern is w. The probability of occurrence of a character pattern as Xi-1, Xi, which is calculated from a dictionary of adjacent two-character patterns stored in the adjacent two-character dictionary storage unit 5 as a matching result of a pattern in units of two characters. This processing corresponds to the adjacent two-character evaluation processing in step 13 in FIG.

On the other hand, the denominator (divisor) P (Xi-1) is the probability that the character pattern Xi-1 is observed without prior knowledge, and is calculated from the one-character dictionary storage means 6 in units of one character. Is calculated as the pattern matching of This processing corresponds to the one-character evaluation processing in step 14 in FIG.

The character recognizing means 4 calculates a character recognition score, P (Xi | Xi-1, wi) as a ratio of respective numerical values obtained from the adjacent two-character dictionary storing means 5 and the one-character dictionary storing means 6. ) ≒ P (Xi−1, Xi | w) / P (Xi−1) (6) This processing corresponds to the character recognition processing in step 15 in FIG.

The operation of the character string reading means 3 will be described in more detail. The character string reading unit 3 converts the character string into a character pattern candidate using the character string image received from the character cutting unit 2 or the characteristic pattern obtained by converting the character string image by the characteristic extraction processing and the coordinate information of the cutout position candidate. List all ways of division. This process is shown in FIG.
Corresponds to the character string image reconstruction processing in step 12 of FIG.

For example, if four cutout position candidates are obtained from the input image, the input image is
It can be divided into five partial patterns: pattern 2, pattern 3, pattern 4, and pattern 5.

On the other hand, assuming that the number of characters is 2,
(1 | 2,3,4,5), (1,2 | 3,4,5),
There can be four types of divisions, (1,2,3 | 4,5) and (1,2,3,4 | 5).

Assuming that the number of characters is 3, (1 | 2 |
3, 4, 5), (1 | 2, 3 | 4, 5), (1 | 2,
3,4 | 5), (1,2 | 3 | 4,5), (1,2 |
There can be a total of six divisions of (3, 4 | 5) and (1, 2, 3 | 4 | 5).

Here, the division position of the input image is represented by "|".

For example, (1,2 | 3 | 4,5) indicates that partial patterns 1 and 2 are the first character, partial pattern 3 is the second character,
As partial patterns 4 and 5 are assigned to the third character,
This means that the input image is divided (grouped).

In this way, a string of character pattern candidates is generated for all possible divisions for the assumed number of characters, and the reading score of the entire character string is calculated for each. This processing corresponds to the character string recognition processing in step 16 in FIG.

The read score is the product of the recognition scores of each character pattern candidate, that is, P (X1 | w1) × P (X2 | X1, w2) × P (X3
| X2, w3) ×... × P (Xn | Xn−1, wn). Here, n is the number of characters.

The reading score is calculated for each of the assumed number of characters and the character type, and the recognition results w1, w2,..., Wn that maximize the reading score are output as the reading results. This processing corresponds to the result comparison evaluation processing of step 17 in FIG.

As for the score P (X1 | w1) of the first character, since there is no character pattern candidate immediately before, the character recognizing means 4 calculates using the one-character dictionary.

In this case, since the read score is treated as a probability, the product of the recognition scores of the respective character pattern candidates is used as the overall score. However, a score that cannot be regarded as a probability (for example, a logarithmic probability or a template from the template). When dealing with (distance), a sum may be used instead of a product.

In addition, when there are linguistic restrictions on the arrangement of characters, these restrictions are appropriately used. For example, if the probability P (B | A) that the character B immediately follows the character A is known from statistical analysis, this probability is reflected in the read score, and P (X1 | w1) P (W1) × P (X2 | X1, w2)
P (w2 | w1) × P (X3 | X2, w3) P (w3 |
w2) × ... × P (Xn | Xn−1, wn) P (wn | w
n-1) The score is calculated as follows.

Alternatively, if the character string is known to be one of several types of limited words, the reading score may be calculated by assuming only the character arrangement of each word. .

The character string reading means 3 uses the dynamic programming method (D
Based on dynamic programming, an optimal solution may be efficiently obtained. An example using this dynamic programming will be described. Here, it is assumed that T-1 cutout position candidates are detected and the input character string image can be divided into T partial patterns.

The first partial pattern to the i-th partial pattern correspond to the first to k-th characters, and the first partial pattern to the j-th partial pattern correspond to one to one.
In the case where the characters from the first character to the (k-1) th character are used,
A reading score for k characters is A (k, i, j).

At this time, the score A (1, i, j) relating to the first character can be calculated by the character recognizing means 4 as the maximum value relating to w of P (partial patterns 1 to i | w).

Score A (k, i, j) for the second and subsequent characters
(K> 1) can be sequentially calculated by the recurrence formula shown in Expression (7).

Note that X (j + 1, i) is a partial pattern created by combining the (j + 1) -th partial pattern to the i-th partial pattern. B (k, i, j) and C
(K, i, j) are the start position of the (k-1) th character and the character type of the kth character when the jth partial pattern to the ith partial pattern are used as the kth character.

Once the maximum score A (n, T, j _max ) = max _j A (n, T, j) is obtained by the above recurrence formula, the character type of the n-th character is wn = C ( n, T, j
_max ), the start position of the n-th character is j _max .

The start position of the (n-1) th character is B (n,
T, j _max ) and the character type of the (n−1) th character is C (n−1,
j _max , B (n, T, j _max )) are sequentially obtained backward.

When a large number of cutout position candidates are set at equal intervals without being limited to a small number, an optimum reading result can be efficiently searched in this way.

In this case, the character string image reconstruction in step 12 in FIG. 2, the character recognition in step 15, the character string recognition in step 16, the result comparison and evaluation in step 17, the evaluation of two adjacent characters in step 13, and step 14 Are processed in parallel, so that the reading result can be searched efficiently.

Next, the procedure for constructing an adjacent two-character dictionary stored in the adjacent two-character dictionary storage means 5 will be described.

The adjacent two-character dictionary is formed by pre-learning using image data of adjacent two characters extracted from character string image data as learning data.

First, regardless of the character type of the first character, the adjacent two-character image data is classified according to the character type of the two characters, and a data set having a number equal to the number of character types is created.

A correct a is set in a data set obtained by collecting adjacent two-character images whose character type is a, and the second character type is b.
Is a correct answer to the data set of two adjacent character images
, Etc., the character type of the second character is given as a correct answer to all data. Thereafter, pattern learning is performed in the same manner as for normal one-character data.

For example, when a Hidden Markov Model (HMM) is used for the character recognition means 4, for example, the reference “1995, Lawrence Rabbiner et al., Translated by Furui, the basics of speech recognition (below), As shown in "NTT Advanced Technology Co., Ltd., pp. 128-138", one HM is used for each of the character types a, b,... By the Baum-Welch algorithm.
A dictionary is constructed by estimating M parameters.

The procedure for constructing the one-character dictionary stored in the one-character dictionary storage means 6 will be described. The one-character dictionary is a dictionary for calculating the probability P (X) of the occurrence of the partial pattern X without prior knowledge and the probability P (X) of the occurrence of the pattern X under the condition that a character appears from the character type w. | W) to calculate | w).

First, as for the dictionary for calculating P (X), a data set is created by collecting all the individual character images cut out one by one regardless of the character type.
Create two dictionaries.

As described above, when the hidden Markov model is used, the created data set is used
The um-Welch algorithm is executed to estimate parameters of one HMM and construct a dictionary.

Next, the dictionary for calculating P (X | w) is a dictionary for calculating the recognition score of the first character having no preceding character pattern. Data sets of individual character images used for learning the dictionary to be calculated are classified into character types, HMM parameters are estimated for each character type, and a HMM for the number of character types is constructed to create a dictionary.

The adjacent two-letter dictionary and the one-letter dictionary use a character string image of an arbitrary number of correct characters as learning data.
It may be configured automatically. This procedure will be described.

First, initial values of parameters characterizing the adjacent two-character dictionary and the one-character dictionary are appropriately determined. A candidate cutout position is detected from the character string image data for learning using the character cutout means 2, and an optimum cutout position is obtained using the character string reading means 3, the character recognition means 4, and the initial dictionary.

At this time, since a correct answer has already been given to the character string image data for learning, w1, w2,.
For, a fixed and optimum score may be searched for. As a result, a provisional character cutout position is determined, and character cutout data that is individually cut out and obtained as a correct answer is obtained. Using this, the one-character dictionary and the adjacent two-character dictionary may be configured according to the above-described procedure. Thereafter, using the newly constructed dictionary, the character extracting means 2, the character string reading means 3, and the character recognizing means 4 are activated again to obtain individually extracted character data. A series of processing of reconstructing a dictionary may be repeated an arbitrary number of times.

Although the procedure of appropriately defining the parameters of the initial dictionary and then generating the individual character data has been described, the procedure may be started in the reverse order. That is, first, characters may be cut out at an appropriate cut-out position, and these individual character data may be used as learning data to form an initial dictionary. Once a dictionary has been constructed,
The subsequent procedure is the same.

Next, a second embodiment of the present invention will be described. Referring to FIG. 1, in the present embodiment, an image storage unit 1 that captures an input character string image by an optical sensor and stores it, and a candidate for a boundary between adjacent characters is determined from the character string image received from the image storage unit 1. Character extraction means 2 for detecting as a cutout position candidate, and character recognition processing is called for each individual character pattern when a character string image is divided by selecting some cutout position candidates to calculate a recognition score of the entire character string Then, a character string reading means 3 for outputting an optimal cutout and recognition result as a character string reading result, and performing a recognition process on a character pattern in response to a request from the character string reading means 3 to determine one character type and a recognition score. A character recognition unit 4 to be returned, a one-character dictionary storage unit 5 for calculating a score of the likelihood of appearance of a single character pattern, and a pattern corresponding to two adjacent characters are used. And a neighboring 2 character dictionary storage unit 6 for calculating a recognition score 2 character of character types.
Each means can be realized by executing a program stored in a main storage device on the computer.

Although the procedure has been described in which the parameters of the initial dictionary are appropriately determined, and then the individual character data is generated, the procedure may be started in the reverse order. That is, first, characters may be cut out at an appropriate cut-out position, and the initial dictionary may be configured using the individual character data as learning data. Once the dictionary is constructed, the subsequent procedures are the same. Further, as described in the first embodiment of the present invention, a feature extraction process for converting an input character string image into a feature pattern suitable for reading may be inserted into the character string reading process.

The second embodiment of the present invention will be described step by step with reference to the flowchart of FIG.

In FIG. 2, the operations of reading images and extracting characters in steps 10 and 11 are the same as those in the first embodiment. That is, the input of the character string image and the extraction of the character pattern are performed by the image storage unit 1 and the character cutout unit 2.

In the flowchart of FIG. 2, the character string reading means 3 executes the character string image reconstruction processing 12 in step 12, the character string recognition in step 16, and the result comparison and evaluation processing in step 17. Receiving the character string image received from the character extracting means 2 or the characteristic pattern obtained by converting the character string image by the characteristic extraction processing, and the coordinate information of the extracting position candidate, and recognizing the character pattern of any character pattern candidate extracted at the extracting position. 4 to perform character recognition, and store the recognition result and the recognition score.

Then, the recognition result of the character pattern candidate string having the highest recognition score as a whole and having no duplication or skipping is selected and output as the character string reading result. The search procedure for the optimum reading result will be described later.

When the character string reading means 3 sends a character pattern candidate to the character recognizing means 4, in addition to the corresponding character pattern candidate, it also sends the immediately preceding character pattern candidate.

The character recognizing means 4 performs a character recognizing process of the corresponding character pattern candidate in consideration of these two adjacent character pattern candidates. The character recognizing means 4 receives two adjacent character pattern candidates from the character string reading means 3 and assumes the combination of any two character character categories, and considers the occurrence of the first character pattern as the second character pattern. The recognition score of the character pattern is calculated and returned to the character string reading means 3.

Here, the character recognizing means 4 sends two adjacent character pattern candidates Xi-1 from the character string reading means 3 to each other.
Assuming that Xi has been received, the character recognizing means 4 determines that the character pattern wi to which the pattern Xi belongs and the character pattern wi-1 to which the character type pattern Xi-1 belongs, for each combination of the character category wi-1 and the immediately preceding character pattern wi- 1 and the probability P (Xi | Xi−1, wi−) that the character pattern of interest belongs to the category wi.
1, wi).

In the calculation of the actual probability, P (Xi | Xi−
1, (wi-1, wi) is not directly calculated, but an approximate value of P (Xi-1, Xi | wi-1, wi) / P (Xi-1 | wi-1) (8) is obtained.

In the calculation of the approximate value, the numerator P (Xi
−1, Xi | wi−1, wi) are the two characters adjacent to each other on the condition that the character type of the first character of the two adjacent character patterns is wi-1, and the character type of the second character is wi. The pattern is X
i-1, Xi, which is the probability of occurrence
It is calculated from the dictionary of adjacent two-character patterns stored in the character dictionary storage unit 5 as a pattern matching result in units of two characters. This processing corresponds to the adjacent two-character evaluation processing in step 13 in FIG.

On the other hand, the denominator P (Xi-1 | wi-1) is
When character category wi-1 is assumed, character pattern Xi
-1 is the probability of being observed, and is calculated by the one-character dictionary storage means 6 as pattern matching for each character. This corresponds to the one-character evaluation process in step 14 of FIG.

The character recognizing means 4 calculates a character recognition score, P (Xi | Xi-1, Wi) ≒, as a ratio of respective numerical values obtained from the adjacent two-character dictionary storing means 5 and the one-character dictionary storing means 6. P (Xi-1, Xi | w) / P (Xi-1) (9) is obtained. This processing corresponds to the character recognition processing in step 15 in FIG.

The operation of the character string reading means 3 will be described in more detail. The character string reading unit 3 converts the character string into a character pattern candidate using the character string image received from the character cutting unit 2 or the characteristic pattern obtained by converting the character string image by the characteristic extraction processing and the coordinate information of the cutout position candidate. List all ways of division. This corresponds to the character string image reconstruction processing in step 12 in FIG.

For example, assuming that four cutout position candidates are obtained from the input image, the input image can be divided into five partial patterns of pattern 1, pattern 2, pattern 3, pattern 4, and pattern 5.

On the other hand, assuming that the number of characters is 2,
(1 | 2,3,4,5), (1,2 | 3,4,5),
There can be four types of divisions, (1,2,3 | 4,5) and (1,2,3,4 | 5).

Assuming that the number of characters is 3, (1 | 2 | 3,4,5), (1 | 2,3 | 4,5),
(1 | 2,3,4 | 5), (1,2 | 3 | 4,5),
There are six possible divisions, (1,2 | 3,4 | 5) and (1,2,3 | 4 | 5). However, here, the division position of the input image is represented by “|”.

For example, (1,2 | 3 | 4,5) means that partial patterns 1 and 2 are the first character, partial pattern 3 is the second character,
This means that the input image is divided (grouped) so that the partial patterns 4 and 5 are assigned to the third character.

In this way, for the assumed number of characters, a string of character pattern candidates is generated covering all division methods, and the reading score of the entire character string is calculated for each. This corresponds to the character string recognition process in the step of FIG.

The read score is the product of the recognition scores of each character pattern candidate, that is, P (X1 | w1) × P (X2 | X1, w1, w2) × P
(X3 | X2, w2, w3) ×... P (Xn | Xn−
1, wn-1, wn). Here, n is the number of characters.

A reading score is calculated for each of the assumed number of characters and character types, and the recognition results w1, w2,..., Wn with the maximum reading score are output as the reading results. This processing corresponds to the result comparison and evaluation processing of the step in FIG.

As for the score P (X1 | w1) of the first character, since there is no character pattern candidate immediately before, the character recognizing means 4 calculates using the one-character dictionary.

Since the read score is treated as a probability here, the product of the recognition scores of each character pattern candidate is used as the overall score, but a score that cannot be regarded as a probability (log probability or distance from the template) , A sum may be used instead of a product.

If there are linguistic restrictions on the arrangement of characters, these restrictions are appropriately used. For example, when the probability P (B | A) that the character B immediately follows the character A is known from the statistical analysis, this is reflected in the read score, and P (X1 | w1) P (W1) × P (X2 | X1, w2)
P (w2 | w1) × P (X3 | X2, w3) P (w3 |
w2) × ... × P (Xn | Xn−1, wn) P (wn | w
n-1) The score is calculated as follows.

Alternatively, if the character string is known to be one of a limited number of words, the reading score may be calculated by assuming only the character arrangement of each word. .

Regarding the operation of the character string reading means 3,
As in the first embodiment, the optimal solution may be efficiently obtained based on the dynamic programming. Here, it is assumed that T-1 cutout position candidates are detected and the input character string image can be divided into T partial patterns.

The first to i-th partial patterns correspond to the first to k-th characters, and the first to j-th partial patterns correspond to 1 to k characters.
The read score for k characters is assumed to be A (k, i, j, w) when the character category is set to w from the kth character to the (k-1) th character and the character category of the kth character is w.

At this time, the score A (1, i, j, w) relating to the first character is obtained by
It can be calculated as the maximum value of w of (partial patterns 1 to i | w).

The score A (2,
i (j, j, w) is stored in P (partial patterns 1 to j, partial pattern j +
1−i | w ′, w) can be calculated as the maximum value of w ′.

Score A (k, i, j) after the third character
(K> 2) can be sequentially calculated by the recurrence formula shown in the following formula (10).

[0118]

However, X (j + 1, i) is (j + 1)
This is a partial pattern formed by combining the i-th partial pattern with the i-th partial pattern.

In the equation (10), max is 1
Represents the maximum value of the specified variable such as or w ', arg
_max represents the value of the variable when the maximum value is obtained by performing the operation of max.

Further, B (k, i, j, w) and C (k,
i, j, w) respectively use the (j + 1) -th partial pattern to the i-th partial pattern as the k-th character,
When the character category to which the pattern corresponding to the k-th character belongs is w, the end position of the k-th character and (k-
1) The character type of the character.

According to the above recurrence formula, once the maximum score A (n, T, j _max , w _max ) = max _j max _w A
If (n, T, j, w) is obtained, the character type of the nth character is wn = C (n, T, _jmax , _wmax ), and the start position of the nth character is _jmax .

The start position of the (n-1) th character is B (n, T, _jmax , _wmax ) +1, and the character type of the (n-1) th character is C (n-1, _jmax). , B (n, T, j _max , w _max )).

When a large number of cutout position candidates are set at equal intervals without being limited to a small number, an optimum reading result can be efficiently searched in this mode. In this case, the character string image reconstruction processing of step 12 in FIG. 2, the character recognition processing of step 15, the character string recognition processing of step 16, the result comparison evaluation processing of step 17, the adjacent two-character evaluation processing of step 13, Since the 14 one-character evaluation processes are performed in parallel, the reading result can be efficiently searched.

The procedure for constructing an adjacent two-character dictionary stored in the adjacent two-character dictionary storage means 5 will be described.

The adjacent two-character dictionary is formed by pre-learning using image data of two adjacent characters extracted from character string image data as learning data.

First, adjacent two-character image data is classified into several classes according to the character type of each character constituting the image data. For example, when dealing with numbers, 00, 01, 02,
.., 99, there are 100 possible combinations, and the image data is classified by each combination. 01 and 10 are divided into different classes.

As a result, the number of classes (data sets) equal to the square of the number of character types is created. Thereafter, pattern learning is performed in the same manner as for normal one-character data. For example, in the case where a hidden Markov model (HMM) is used for the character recognizing means 4, a document ("Lawrence Labiner et al., 1995, translated by Furui, basics of speech recognition (below), NTT Advanced Technology Co., Ltd., 128- 138 ”), each class (00, 0 in the case of a numeral) is calculated by the Baum-Welch algorithm.
1, 02,..., 99), one HMM parameter is estimated to form a dictionary.

The construction procedure of the one-character dictionary stored in the one-character dictionary storage means 6 is the same as the construction procedure of the dictionary for calculating the probability P (X | w) described in the first embodiment. It is.

Note that it is also possible to automatically configure the adjacent two-character dictionary and one-character dictionary as learning data using a character string image of an arbitrary number of characters that have been correctly answered. This may be performed in the same procedure as the method described in the first embodiment.

Next, a third embodiment of the present invention will be described. FIG. 5 is a block diagram showing the configuration of the third embodiment of the present invention. Referring to FIG. 5, the third embodiment of the present invention includes a recording medium 7 on which a character recognition program is recorded. The recording medium 7 may be a CD-ROM, a magnetic disk, a semiconductor memory, or another recording medium, and includes a case where the recording medium is distributed via a network.

The character recognition program is read from the recording medium 7 into the data processing device 8 and executed by the data processing device 8. Under the control of the character recognition program, the data processing device 8 detects some cutout position candidates from the character string image input to the image storage unit 1 by using the character cutout unit, and detects a character pattern candidate from the plurality of cutout position candidates. And performs a recognition process for each of these character pattern candidates by a character recognition unit using the one-character dictionary and the adjacent two-character dictionary stored in the one-character dictionary storage unit 5 and the adjacent two-character dictionary storage unit 6, respectively. , And obtains and outputs a reading result that gives the maximum score for the entire character string.

Under the control of the character recognition program, the data processing device 7 executes the same processing as the processing by the character cutout means 2, the character string reading means 3 and the character recognition means 4, and outputs the result of reading the character string. .

[0134]

As described above, according to the present invention,
In reading a character string, character candidates extracted from the character string are processed as a set of two adjacent characters, and a recognition result and a recognition score for the second character are calculated while considering the pattern shape of the first character. In response to the fact that the character shape is deformed due to continuous writing, contact, etc. from the character written immediately before, stable character recognition becomes possible, thereby enabling accurate character string reading. To play.

Further, according to the present invention, the number of dictionary templates is at most about twice as large as that of the prior art, so that a sufficiently high-speed reading of a character string can be realized.

[Brief description of the drawings]

FIG. 1 is a block diagram showing the configuration of an embodiment of the present invention.

FIG. 2 is a flowchart showing a processing flow of an embodiment of the present invention.

FIG. 3 is a diagram for explaining one embodiment of the present invention;
FIG. 4 is a diagram illustrating an example of an input character string image.

FIG. 4 is a diagram for explaining one embodiment of the present invention;
FIG. 14 is a diagram illustrating an example of a result of extracting a feature amount effective for identification from an input character string image.

FIG. 5 is a block diagram showing a configuration of a second exemplary embodiment of the present invention.

FIG. 6 is a diagram illustrating an example of a character image for explaining an example in which a character error depends on the character type.

FIG. 7 is a diagram illustrating an example of a character image for explaining an example in which a character error depends on the character type;

[Explanation of symbols]

 REFERENCE SIGNS LIST 1 image storage means 2 character cutout means 3 character string reading means 4 character recognition means 5 1 character dictionary storage means 6 adjacent 2 character dictionary storage means 7 storage medium 8 data processing device

──────────────────────────────────────────────────続 き Continuation of the front page (56) References JP-A-5-6464 (JP, A) JP-A-8-96085 (JP, A) "Technical Research Report of the Institute of Electronics, Information and Communication Engineers", PRMU 98-139, Vol. 98 No. 489 p. 25-30 (1998) "On-line Handwritten Character String Recognition Based on Stochastic Model""IEICE Technical Report" PRMU 98-138 Vol. 98 No. 489 p. 17-24 (1998), “Frameless Online Character String Recognition Method Integrating Extraction, Recognition, and Language Confidence” “IPSJ Research Report” Vol. 93 No. 79 p. 37-44 (1993) "Post-processing method for online kanji recognition by Biggram""Transactions of Information Processing Society of Japan", Vol. 39 No. 3 p. 625-635 (1998) "A full-text search method for Japanese texts containing recognition errors" (58) Fields investigated (Int. Cl. ⁷ , DB name) G06K 9/62-9/72 JICST file (JOIS)

Claims (14)

(57) [Claims] 1. An image storage means for inputting and storing a character string image, and a character extraction means for detecting a candidate extraction position for obtaining a partial pattern corresponding to one character from the character string image obtained from the image storage means. And generating an individual character pattern candidate that is a partial pattern corresponding to one character based on the cutout position candidate detected by the character cutout means, and performing character recognition to output an optimal character string reading result. Character string reading means, and individual character pattern candidates generated by the character string reading means are recognized in response to a request from the character string reading means, and a character recognition result and character recognition indicating the likelihood of the character recognition result are provided. A character recognition unit that outputs a score, and a one-character dictionary that stores a dictionary that the character recognition unit uses for identification of one-character pattern candidates and score evaluation. Storage means; and two-character dictionary storage means for storing an adjacent two-character dictionary for identifying individual characters using character pattern candidates for two adjacent characters, wherein the character recognition means comprises: Is a character from the character string reading means.
When receiving pattern candidates and performing character recognition, the recognition target
Character pattern candidate and the character pattern candidate immediately before
If the character pattern candidate to be recognized belongs to a certain character type,
Assuming, given given character pattern candidate for recognition
And the probability of occurrence of the character pattern candidate immediately before and
Using the probability of occurrence of the previous character pattern,
The likelihood that a character pattern candidate belongs to that character type
A character recognition device, wherein the character recognition device represents a score to represent . 2. The method according to claim 1, wherein the character recognition means receives a character pattern candidate to be recognized and a character pattern candidate immediately before the character pattern candidate and assumes that the character pattern candidate to be recognized belongs to a character type. The ratio between the probability of occurrence of the target character pattern candidate and the immediately preceding character pattern candidate, and the ratio of the probability of occurrence of the immediately preceding character pattern candidate, is a score indicating the likelihood that the recognition target character pattern candidate belongs to the character type. The character recognition device according to claim 1, wherein: 3. An image recording device for inputting and storing a character string image.
From the character string image obtained from the storage means
Character that detects a candidate cutout position to obtain a button
A cutout process; and (b) a cutout position detected in the character cutout process.
Based on the candidate, the number of partial patterns corresponding to one character
Optimum by generating different character pattern candidates and recognizing characters
String reading processing to output the result of reading a simple string
And (c) an individual character pattern generated by the character string reading process.
In response to a request from the character string reading process,
Recognize, character recognition result, and likelihood of character recognition result
Anda character recognition process of outputting character recognition score representing the of the character recognition processing of the (c) is one character dictionary storage means
Refers to the dictionary stored in the
Perform separate and score evaluation and store in two-character dictionary storage
With reference to the adjacent two-character dictionary,
Individual characters are identified using character pattern candidates, and the character recognition process is performed by the character string reading means.
When receiving pattern candidates and performing character recognition, the recognition target
Character pattern candidate and the character pattern candidate immediately before
If the character pattern candidate to be recognized belongs to a certain character type,
Assuming, given given character pattern candidate for recognition
And the probability of occurrence of the character pattern candidate immediately before and
Using the probability of occurrence of the previous character pattern,
The likelihood that a character pattern candidate belongs to that character type
A recording medium on which a program for executing each of the above-described processes on a computer is recorded. (A) detecting a cutout position candidate forming a character boundary candidate from the character string image input from the image input means; and (b) character recognition for the character pattern candidate cut out by the cutout position candidate. And the character recognition result and the recognition score are stored. At this time, the character recognition process is performed on the corresponding character pattern candidate in consideration of two character pattern candidates from the character pattern candidate and the character pattern candidate immediately before the character pattern candidate. storing the likelihood of the recognition result as the recognition score, it viewed including the steps of (c) most recognition score as a whole string to output a recognition result of the high character pattern candidate string, the (a) from (c), From a character pattern candidate and the character pattern candidate immediately before it,
Condition that the certain character pattern candidate is of a certain character type
And the character pattern candidate and the character pattern candidate immediately before the character pattern candidate.
Occurs, and the character pattern immediately before occurs.
The character pattern candidate to be recognized is
Derive a recognition score that represents the likelihood of belonging to
That, character recognition method, characterized in that. 5. A method according to claim 1, wherein the probability that the character pattern candidate and the character pattern candidate immediately before the character pattern candidate occur are two characters from a dictionary of two adjacent character patterns stored in advance, provided that the certain character pattern candidate is of a certain character type. claim calculated by the matching units of patterns, is calculated by the first character unit patterns matching the pattern of dictionary character by character in which the preceding character pattern is registered in advance the probability of occurrence, characterized in that 4 The character recognition method described. 6. In the step (b), adjacent two
It is assumed that two character pattern candidates Xi-1 and Xi have been received.
And the character recognition result wi of Xi, the character type is w, the previous character
Character pattern X under the condition that the pattern is Xi-1
The conditional probability P (Xi | Xi-1, w) that i occurs
Is determined as w to be maximized, and the character recognition score is P (X
5. The character recognition method according to claim 4 , wherein the calculation is performed as i | Xi-1, wi) . 7. The second character of an adjacent two-character pattern
If the character type is w, the pattern of two adjacent characters is
Xi-1, Xi, the conditional probability P (X
i | the Xi-1, w value of), the genus of the certain character Xi
Under the condition that the character type is w, a pattern P (Xi-1, Xi | w) where a pattern of two adjacent characters , which is the sum of Xi and the immediately preceding character Xi-1, occurs . Using the probability P (Xi-1) that the immediately preceding character pattern is observed without prior knowledge , P (Xi-1, Xi | w) / P (Xi-1) is calculated. The character recognition method according to claim 6 . 8. In the step (b), when an i-th character pattern Xi in an input character string is compared with a dictionary pattern w to obtain a recognition score for character recognition, a character as an (i-1) -th character is used. pattern Xi-1 has occurred, and, i-1 th character pattern Xi-1 is a dictionary pattern w i-1 conditional probability by adding the condition that belongs to the character category represented by P (Xi | Xi-1 5. The character recognition method according to claim 4, wherein the calculation is performed as (wi-1, wi). 9. The pattern of two adjacent characters is Xi-1, Xi on condition that the character type of the first character of the two adjacent character patterns is wi-1, and the character type of the second character is wi. The conditional probability P (Xi | Xi−1, wi−
1, wi) is calculated as the probability P (Xi−1, Xi | wi) in units of two adjacent characters obtained by combining a certain character and the character immediately before it.
−1, wi) and the score P (Xi−1 |
wi-1) ratio P (Xi-1, Xi | wi-1, Wi)
/ P (Xi-1 | wi -1), or, using the conditions probability P that character pattern Xi-1 of assuming a character category w i-1 is observed (Xi-1), P ( Xi- 1,
9. The character recognition method according to claim 8, wherein the value is calculated by Xi | wi-1, wi) / P (Xi-1). 10. A recognition score representing the likelihood of the character recognition is obtained by a dynamic programming method, and a plurality of (T-1) recognition scores are obtained.
Is detected, the input character string image is divided into T partial patterns, the first partial pattern to the i-th partial pattern correspond to the first to k-th characters, and the first When the partial pattern to the j-th partial pattern correspond to the first character to the (k-1) th character, the read score for k characters is A (k, i, j), and the first one character Eye score A (1, i, j)
Is determined as the maximum value of w of the probability P that the first to i-th partial patterns occur under the condition that the i-th partial pattern is a character type w, and the maximum score of the scores is determined. The character recognition method according to claim 4, wherein 11. The score A (k, i, j) for the second and subsequent characters
(K> 1) is sequentially calculated by the following recurrence formula, (However, X (j + 1, i) is a partial pattern created by combining the (j + 1) th partial pattern to the ith partial pattern. B (k, i, j) and C (k, i, j) Are the start position of the (k-1) th character and the character type of the kth character when the j + 1st partial pattern to the ith partial pattern are used as the kth character, respectively. A function that represents the maximum value of the argument for the variable, argm
ax represents the value of the variable when the maximum value was obtained by performing the operation of max. ), The maximum score A (n, T, j _max ) = max _j A (n, T,
j), the character type of the nth character is wn = C (n, T, _jmax ), the start position of the nth character is _jmax , and the start position of the (n-1) th character is B (n , T, j _max ) and the character type of the (n−1) th character is C (n−1, j _max , B (n,
9. The character recognition method according to claim 8, wherein the calculation is sequentially performed backward, such as T, j _max )). 12. A recognition score representing the likelihood of the character recognition is obtained by a dynamic programming method, wherein a plurality of (T-1) recognition scores are obtained.
Is detected, the input character string image is divided into T partial patterns, the first partial pattern to the i-th partial pattern correspond to the first to k-th characters, and the first When the partial pattern to the j-th partial pattern correspond to the first character to the (k-1) th character, the read score for k characters is A (k, i, j), and the first one character Eye score A (1, i, j)
Is determined by the character recognition means as the maximum value of w of the probability P that the first to i-th partial patterns occur under the condition that the i-th partial pattern is a certain character type w. The score A (k, i, j) (k> 1) is sequentially calculated by the following recurrence formula, (However, X (j + 1, i) is a partial pattern created by combining the (j + 1) th partial pattern to the ith partial pattern. B (k, i, j) and C (k, i, j) Are the start position of the (k-1) th character and the character type of the kth character when the j + 1st partial pattern to the ith partial pattern are used as the kth character, respectively. A function that represents the maximum value of the argument for the variable, argm
ax represents the value of the variable when the maximum value was obtained by performing the operation of max. ), By the above recurrence formula, the maximum score A (n, T, j _max ) = max _j A (n, T,
j), the character type of the nth character is wn = C (n, T, _jmax ), the start position of the nth character is _jmax , and the start position of the (n-1) th character is B (n, T, j _max ), the character type of the (n−1) th character is C (n−1, j _max , B (n,
2. The character recognition device according to claim 1, wherein the values are sequentially obtained backward, such as T, j _max )). 13. A dynamic programming method for determining a recognition score representing the likelihood of the character recognition, wherein a plurality of (T-1) recognition scores are obtained.
Is detected, the input character string image is divided into T partial patterns, the first partial pattern to the i-th partial pattern correspond to the first to k-th characters, and The first partial pattern to the j-th partial pattern correspond to the first to (k-1) th characters,
When the character category of the k-th character is w, the reading score for the k characters is A (k, i, j, w), and the score A (1, i, j, w) for the first character is given. )
Obtained as the maximum value of w of the probability P of occurrence of the first to i-th partial patterns, and score A (2, i, j, w) for the second character
Is P (partial patterns 1 to j, partial patterns j + 1 to i |) by the character recognition unit and the two-character dictionary storage unit.
w ', w) is calculated as the maximum value for w'. The score A (k, i, j) (k> 2) after the third character is sequentially calculated by the following recurrence formula. (However, X (j + 1, i) is a partial pattern created by combining the (j + 1) -th partial pattern to the i-th partial pattern. B (k, i, j, w) and C (k) ,
i, j, w) respectively use the (j + 1) -th partial pattern to the i-th partial pattern as the k-th character,
When the character category to which the pattern corresponding to the k-th character belongs is w, the end position of the k-th character and (k-
1) The character type of the character. max is specified as l or w '
Argmax is a function that represents the maximum value of an argument related to a variable.
Displays the value of the variable when the maximum value was obtained by performing the operation.
You. ), By the above recurrence formula, the maximum score A (n, T, j _max , w _max ) = max _j ma
x _w A (n, T, j, w) is obtained, and the character type of the n-th character is w
n = C (n, T, _jmax , _wmax ), the start position of the nth character is _jmax , and the start position of the (n-1) th character is B (n, T, _jmax ,
w _max ) +1, the character type of the (n−1) th character is C (n−1, j _max , B)
2. The character recognition apparatus according to claim 1, wherein (n, T, j _max , w _max )) are sequentially obtained backward. 14. A process for detecting a cutout position candidate forming a character boundary candidate from a character string image input from an image input means, and (b) character recognition for a character pattern candidate cut out by the cutout position candidate. Is performed, and the character recognition result and the recognition score are stored. At this time, from the certain character pattern candidate and the character pattern candidate immediately before the character pattern candidate, the character pattern candidate Using the probability that the immediately preceding character pattern candidate occurs and the probability that the immediately preceding character pattern occurs, a recognition score indicating the likelihood that the recognition target character pattern candidate belongs to the character type is derived. (C) a process of outputting a recognition result of a character pattern candidate sequence having the highest recognition score as a whole character string, and a process of each of the above (a) to (c) being performed by a computer. Recording medium for recording a program to be executed by data.