JP2000207495A - Character recognizing device, character learning device and computer readable recording medium - Google Patents

Abstract

PROBLEM TO BE SOLVED: To realize the reading of a strong character string due to characters contact and continuous writing or the like. SOLUTION: A character segmenting and characteristic extracting means 12 detects segmentation position candidates from a character string image. A character string reading means 13 extracts a character pattern candidate from the character string image based on the segmentation position candidates and verifies the validity of all kinds of thinkable read results by using a character appearance probability calculating means 14. The means 14 receives the character pattern candidate, a character code, a character state and the character code and character state of a character pattern candidate located just before the character pattern candidate from the means 13, evaluates the validity of shape connection with the preceding character pattern candidate by using a character state transition probability, also evaluates the validity that the character pattern candidate belongs to a certain category by using a character template and calculates maximum likelihood (point) that the character pattern candidate belongs to a certain state and a certain character category. The means 13 searches for and outputs segmentation recognized results of the character string in which the recognition points of the entire character string become maximum.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to the field of optical character recognition in which characters written on paper or the like are read by an optical sensor and read, and in particular, recognizes a character string in which a plurality of characters are arranged like words or sentences. Character recognition technology.

[0002]

2. Description of the Related Art Conventionally, in this type of character recognition, a character string is read by combining character extraction for identifying a boundary between characters in the character string and character recognition for reading each of the extracted characters.

An example of the prior art is described in the document "Shu Liang et al., 1994, Segmentation of Touching Characters in Printed Document Recognition, Pattern Recognition, Vol. 27, Vol.
825-840 (Su Liang et al., Segmentation of T
ouching Characters in Printed Document Recognitio
n, Pattern Recognition, Vol.27, No.6, pp.825-84
0, 1994) ". In the method described in this document, a character boundary candidate is extracted using the shape of a projection histogram and information derived from the shape, and a part of a character string sandwiched between any two character boundaries is extracted as a character pattern candidate. Extract all (character cutout). Next, character recognition is performed on all the character pattern candidates, and the recognition result and its likelihood (score) are calculated for each. Finally, character pattern candidates are selected so that the score is maximized when the character strings are concatenated, and at the same time, a cutout position of a character string considered to be correct is determined.

[0004] Several other methods have been conventionally considered, but in many cases, only information used for character extraction is different, or all parts in a character string are exhaustively extracted without character extraction. In most cases, character recognition is performed to determine an optimal cut-out position, or character recognition uses only a different feature amount to be extracted from a character image or a method of identifying a character. Although the example described above is for recognition of printed characters, the same applies to a method for handwritten characters.In many cases, character extraction and character recognition are configured as separate modules, and a combination of them is used to read a character string. The procedure of doing has been adopted.

[0005]

In the prior art, since character extraction and character recognition processing are used separately, once a partial image (character pattern candidate) considered to be one character is extracted, the character is replaced with a character. Regardless of the presence of the characters before and after, the recognition process is performed independently of each other.

FIG. 8 is a block diagram showing a functional configuration of an example of the prior art. In this conventional example, an image storage unit 41 that stores an input character string image, a candidate for a boundary between adjacent characters is detected from the character string image received from the image storage unit 41 as a cutout position candidate, and a character string image is detected. Character extracting / characteristic extracting means 42 for extracting a character into a smaller amount (feature) useful for identification, and individual character pattern candidates when a character string image is divided by selecting some of the extracting position candidates A character string reading means for performing character recognition on the character string, calculating a recognition result as a whole of the character string and a recognition score representing the certainty of the recognition result, and outputting the cutout and the recognition result with the maximum recognition score as a character string reading result 43, according to the request of the character string reading means 43,
When a given character pattern candidate calculates the probability of occurrence under a given character category (character code), the character appearance probability calculation means 44 and the character appearance probability calculation means 44 calculate the character appearance probability. And character template storage means 45 for storing a numerical value (character template) necessary for calculating how close a given character pattern candidate is to a given character category. Further, the character pattern storage means 46 and the character code storage means serve as interfaces when the character reading means 43 passes a character pattern candidate and a character code to be recognized to the character appearance probability calculation means 44.
47 is provided.

The character string reading means 43 uses the partial images of the character string cut at several cutout positions as character pattern candidates, and character appearance is determined by assuming the closeness between the character pattern candidates and the character template when all character categories are assumed. Determined by the probability calculation means 44, the character cutout position and the character code string are determined so that the proximity of each character pattern candidate and the character template is the highest in the entire character string. In this conventional technique, the character template is
The character learning means 49 learns using the individual character data stored in the learning character data storage means 48.

[0008] However, in the case of a handwritten character string, particularly a character string written in a continuous manner such as a cursive English character string, the shape of each character changes according to the connection with the preceding and following characters. Therefore, when a certain recognition process is performed ignoring the shapes of the characters before and after as in the related art, it is not possible to cope with the deformation caused by continuous writing, and erroneous recognition often occurs.

For example, in the case of a character string written continuously in cursive, the position of the pen at the time of finishing writing the character "a" is at the bottom, but the position of the pen at the time of finishing writing "o" is Is in the upper part. Therefore, even if the same character is written, the shape of the character changes depending on whether it is written after "a" or "o" (FIG. 2). This is a character string-specific transformation that cannot occur with individual characters. Such deformation cannot be handled by the conventional character recognition processing constructed for the purpose of recognizing individual characters, and often causes erroneous recognition.

The prior art has other problems besides recognition of continuous writing. In Arabic numerals, characters such as “1” and “7” and “4” and “9” can be distinguished from each other by characters written by the same writer, but there are characters that cannot be distinguished when compared between different writers. . For example, in FIG. 3, “17” in the upper left and “17” in the upper right are examples of character strings written by different writers. Although it is easy for the same writer to distinguish between “1” and “7”, two characters enclosed in a rectangle, that is, “1” of the first writer and “1” of the second writer, are different in shape. They are similar and tend to be difficult to identify. Similarly, “49” at the lower left and “49” at the lower right in FIG. 3 can be easily identified as “4” and “9” of the same writer, but “4” of the first writer and “2” of the second writer. It is difficult to identify “9” by comparing it alone. Also in this case, it can be seen that there is a problem that erroneous recognition occurs when only a certain character is recognized alone without looking at the shape of a nearby character.

The above-described problem that characters are deformed depending on adjacent characters is not necessarily completely solved. However, there are problems in recognition accuracy, processing speed, and the like, and the method cannot be practically endurable.

For example, a method is considered in which adjacent two characters are considered as one pattern, a template is constructed by learning templates of the number of character types squared, and a character string to be recognized is recognized in units of two characters. Can be However, the arrangement of the two characters has a very wide variety of variations as patterns, and an enormous amount of learning data is required. However, since the number of templates required is the square of the number of character types, the problem of insufficient learning data becomes serious. Also, even if a large amount of learning data is obtained, the distinction of selecting a pattern of two characters that deforms in a much more diverse manner than a pattern of one character from the square class of one character type is essentially essential. The difficulty in recognition is unavoidable because of the increasing difficulty. Therefore, a method of preparing two square templates of the character type using two characters as one pattern is not practical.

In the prior art, there is also a method in which the dependence between characters is absorbed by recognizing a character string in units of words without decomposing the character string into lower-order elements such as characters. However, such a method also has a problem similar to or higher than the above-described method using the adjacent two-character pattern because the variation of the word pattern is enormous. In addition, to handle images that are larger than text,
Processing efficiency is also poor.

In addition to the above, there is a prior art in which the relationship between adjacent characters is considered, but only the arrangement of character types is considered, and pattern deformation is not considered. An example is the document "Kundu et al., Recognition of Handwritten Words: 1989: First and Second Order Hidden Markov Model Based."
Approach, Pattern Recognition, Volume 27, Volume 3
Issue, pages 283-297 (Recognition of handwritten wor
d; first and second order hidden Markov modelbased
approach, Kundu et al, Pattern Recognition, Vol. 2
2, No. 3, pp. 283-297, 1989) ".
In the method described in this document, statistics of the frequency of adjacent two-character groups of all character types are extracted from sentences in a Japanese language dictionary or newspaper magazine, and the result is used for character string recognition. That is, the output result of character recognition is adjusted so that a two-character group having a high frequency of adjacentness easily appears in character recognition.
Such a method of using the frequency information of two character sets of character types (character codes) is called a bigram, and many other techniques using this are reported. However,
As described earlier, bigram only considers the adjacent relationship between character codes, and is different from the technology that considers the adjacent relationship between characters in consideration of deformation of a character pattern.

As described above, the technique of recognizing a character string using the adjacency at the character code level is widely used. However, the technique of using the adjacency at the character pattern level separately from the character code level is known. Due to the difficulty in handling information having a large number of dimensions, such as character patterns, no technology that can be put to practical use has been established as described above.

Therefore, an object of the present invention is to reduce the influence of character deformation caused by the dependence between adjacent characters, that is, to prevent contact between characters, continuous writing, and individual differences in the character shape of each writer. An object of the present invention is to provide a character recognition device that is robust and can operate at a practical processing speed.

[0017]

In order to achieve the above-mentioned object, a character recognition apparatus according to the present invention assumes several discrete character states representing character pattern deformation types for each character category. Then, consider a state network connecting those character states. One character immediately followed by another character corresponds to one state transition on the network. It is assumed that one character pattern is generated each time the state transitions to a new character state, and that one character string is observed by passing through the same number of character states as the number of characters. The transition from one character state to another character state is defined as the probability of transition from a certain character state to a certain character state. Each character state is associated with a representative pattern (character template) representing the deformed character pattern for each character category, and the occurrence of the character pattern from the character state is determined by a probability density function based on the representative pattern. Stipulated. Based on these character state transitions and representative patterns, the recognition result of the entire character string is calculated in consideration of the likelihood of all character pattern candidates extracted from the input character string image and their adjacent relationships. Specifically, the character recognition device of the present invention includes an image storage unit that stores an input character string image, and a candidate for a boundary between adjacent characters from the character string image received from the image storage unit as a cutout position candidate. Character extraction / feature extraction means for detecting and converting a character string image into a smaller amount (feature) useful for identification, and when extracting a character string image by selecting some extraction position candidates Character string reading means for performing character recognition on individual character pattern candidates of the character string, and outputting an optimal cutout and an optimal character code string as a character string as a whole character string; and a character pattern candidate from the character string reading means. , Character code, character state which is an index indicating the type of character deformation, and character code of the character pattern candidate located immediately before the given character pattern candidate A character appearance probability calculating means for receiving a character state and calculating a probability that a given character pattern candidate appears under a given character code and character state, and the character appearance probability calculating means calculating a character appearance probability The character state transition probability storing means for storing a numerical value (state transition probability) necessary for calculating a part of the probability depending on the character state, and the character appearance probability calculating means calculating the character appearance probability. In this case, there is provided a character template storage means for storing a numerical value (character template) necessary for calculating a portion of the probability depending on the character pattern.

Further, in the character learning device of the present invention, a parameter (hereinafter, referred to as a character state transition probability) defining a state transition on the network and a probability density function defining a character pattern output (hereinafter, referred to as a character pattern transition probability). , A character template) is automatically acquired by learning from a character string image to which a correct character code string is assigned. As long as even the correct character code string is assigned to the character string image used in learning, individual character patterns are automatically cut out during the learning process without providing information such as boundaries between characters, and learning is performed. proceed. Specifically, the character learning apparatus of the present invention provides a character string used when estimating an optimal character state transition probability and estimating an optimal character template from a given character string image and its correct character code string. A learning character string data storage unit for storing data; detecting a candidate for a boundary between adjacent characters as a cutout position candidate from a character string image received from the learning character string data storage unit; and useful for identifying a character string image. A character segmentation / feature extraction unit for performing feature extraction for conversion into a smaller amount (feature);
The character pattern candidate, the character code, the character state which is an index indicating the type of character deformation, the character code of the character pattern candidate located immediately before the given character pattern candidate, and the character state are received, and the given character pattern candidate is received. A character appearance probability calculating means for calculating a probability of occurrence under a given character code and character state, and a correct character code string given to the character string image and the character appearance probability calculating means using the character appearance probability calculating means. Character boundary determining means for estimating a character boundary, and a character pattern storage means for storing a character pattern candidate to be passed when the character boundary determining means requests the character appearance probability calculating means to calculate a character appearance probability, Two character code storage means for storing a character code in the correct character code string and a character code immediately before the character code corresponding to the character pattern candidate; Two character state storage means for storing a character state corresponding to the pattern candidate and a character state corresponding to the character pattern candidate immediately before the character state candidate; and A character state transition probability storage means for storing a numerical value (state transition probability) necessary for calculating a dependent part, and a character appearance probability calculation means for calculating a character appearance probability, which depends on a character pattern of the probability. The character state transition is performed by using a character template storage unit for storing a numerical value (character template) necessary for calculating a portion to be calculated, and individual character patterns cut out by the character boundary determining unit and their arrangement order. A character learning method for updating a character state transition probability stored in the probability storage means and a character template stored in the character template storage means. And a step.

[0019]

Next, a first embodiment of the present invention will be described in detail with reference to the drawings.

FIG. 1 is a block diagram showing one embodiment of the present invention. In this embodiment, an image storage unit 11 that captures and stores an input character string image with an optical sensor, and detects a candidate for a boundary between adjacent characters from the character string image received from the image storage unit 11 as a cutout position candidate. A character extraction / characteristic extraction unit 12 for extracting a character string image into a smaller amount (feature) useful for identification; and a character extraction image when a character image is divided by selecting some extraction position candidates. A character string reading unit 13 that performs character recognition on the obtained character pattern candidate, calculates a recognition score as the entire character string, and outputs a cutout and a character code string that provides the highest recognition score as a result of reading the character string, In response to a request from the character string reading means 13, the character string reading means 13
More character pattern candidates and their corresponding character codes (main character codes), character states (main character states), character codes (sub character codes) and characters corresponding to another character pattern candidate located immediately before the character pattern candidates Character appearance probability calculating means 14 for receiving a state (sub character state) and calculating the probability of occurrence of a character pattern candidate;
When calculating the character appearance probability, the sentence state transition probability storage means 15 stores a numerical value (character state transition probability) required to calculate a connection between characters, that is, a part depending on the transition of the character state. When the character appearance probability calculation means 14 calculates the character appearance probability, a character template storage means 16 for storing a numerical value (character template) necessary for calculating a portion dependent on the given character pattern itself, A character pattern storage unit 30 that stores a character pattern, a character code, and a character state to be passed when the character string reading unit 13 requests the character appearance probability calculation unit 14 to calculate the character appearance probability;
It has a main character code storage unit 31, a sub character code storage unit 32, a main character state storage unit 33, and a sub character state storage unit.

Further, in this embodiment, learning character string data storage means 21 for storing character string data for learning used when estimating an optimum character state transition probability and a character template from given character string data, A character cutout / detection unit that detects a cutout position candidate from the character string image received from the learning character string data storage unit 21 and performs feature extraction for converting the character string image into a smaller number (feature) useful for identification.
Character extraction means 22, a character boundary determining means 23 for selecting a cutout position from cutout position candidates in a character string image using a correct character code string given to the character string image and a character appearance probability calculating means 14, A character pattern storage means 35 for storing a character pattern candidate, a character code and a character state to be passed when the boundary determination means 23 requests the character appearance probability calculation means 14 to calculate a character appearance probability, a main character code storage means 36, The character code storage means 37, the main character state storage means 38, the sub character state storage means 39, and the character state transition probability storage means 15 using the individual character patterns cut out by the character boundary determination means 23 and their arrangement order. It has a character learning means 24 for updating the stored character state transition probability and the character template stored in the character template storage means 16.

Each means can be realized by operating as a program stored on a computer.

Image storage means 11, character extraction / characteristic extraction means 12, character string reading means 13, character appearance probability calculation means
14, the character state transition probability storage means 15, the character template storage means 16, and each of the storage means 30 to 34 constitute the character string recognition device 1 (dotted frame in FIG. 1). The character string learning device 2 is composed of the learning character string data storage means 21, character extraction / characteristic extraction means 22, character boundary determination means 23, character learning means 24, and storage means 35 to 39 (FIG. 1). (Dashed frame). The character cutout / feature extraction means 12 in the character string recognition device 1 and the character cutout / feature extraction means 22 in the character string learning device 2 have the same function. Since the character string recognition device 1 and the character string learning device 2 are not usually used at the same time, the character string recognition device 1 is not used.
The character string learning device 2 and the character string learning device 2 may share one character cutout / feature extraction unit.

When character strings are recognized or learned, preprocessing is generally performed on an input image.
The pre-processing includes binarization processing for converting a multi-valued image into a more manageable binary image, normalization processing for shaping the character size, stroke interval, inclination, etc., and removing fine stains and blurs in the image. Noise removal processing and the like can be considered. Although not shown here, these pre-processing may be performed, if necessary, on a character cutout / feature extraction unit 12, a character cutout / feature extraction unit 22, a character string reading unit 13, a character boundary determination unit.
23. It may be introduced into the character appearance probability calculation means 14 or the like.
The pre-processing, character segmentation, and feature extraction can be applied in any order regardless of the context.

The operation of the present invention according to this embodiment will be described step by step. First, the character string recognition device 1
Will be described with reference to the flowchart of FIG.

The image to be read is optically input by a scanner or the like, is stored in the image storage unit 11, and is sent to the character extraction / characteristic extraction unit 12. The image reading 100 in the flowchart of FIG. 5 corresponds to this. The character cutout / feature extraction means 12 performs appropriate preprocessing such as binarization processing and normalization processing on the character string image, and then performs some cutout position (character boundary) candidates (horizontal writing) from the character string image. When a character string is handled, it is detected on the x-axis, that is, expressed as horizontal coordinates), and the coordinates and a character string image or a feature pattern obtained by converting the character string image by the feature extraction processing are extracted by the character string reading unit 13. Send to The character cutout / feature extraction 101 in the flowchart of FIG. 5 corresponds to this.

In the character extraction / feature extraction 101, for example, graphic information is used to detect an extraction position candidate. For graphical information, for example, calculate a projection histogram of a character string (vertical direction if the character string is horizontal, or horizontal direction if the character string is vertical), and cut out positions where the frequency is lower than a preset threshold What is necessary is just to be a position candidate.
As a clipping means using other graphical information, a method of tracing the contour of a character string and measuring its irregularity, and storing a position where the dent is larger than a threshold value as a clipping position candidate is also conceivable. . Further, a method of obtaining a cutout position candidate using a plurality of graphic features together is also possible.

It is also possible to create a cutout position candidate without using graphic information. 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 (for example, about several times the number of expected characters) are stored.

Any method can be used for the feature extraction processing in the character extraction / feature extraction 101. Below,
As an example of feature extraction, a process of extracting directional features from a binary image will be described. For each pixel of the binary image, the run length of the black run in the horizontal direction (0 ° direction) including the pixel is set as a pixel value (however, if the pixel of interest is a white pixel, the pixel value is set to 0). Create a value image. Thus, a directional image in which only horizontal strokes are emphasized is created. Vertical direction (90 °
Direction) and oblique directions (45 ° and 135 ° directions) in the same manner, a directional image in which each direction is emphasized can be created, so that a total of four images can be obtained. FIG. 4 is a diagram showing an example of the extraction of the directional feature, wherein 0 °, 45 °, 90 °
Direction images in which four directions of 135 ° and 135 ° are emphasized are extracted.

Thereafter, if necessary, the pattern is further compressed. That is, in each direction image, the vertical direction is divided into an appropriate number (for example, 4, 5 or the like) and the horizontal direction is divided into small regions in pixel units, and the pixel value of each small region is averaged over the pixel value of the entire region. Replace with the value or maximum value. As a result, the vertical image size is reduced to several pixels.

Assuming that the input image contains T characters, the character string reading means 13 selects (T-1) cutout positions from the cutout position candidates and selects T (T1) cutout positions by each method. For all combinations, check the possibility of the category to which the character pattern candidate belongs, and determine the cutout position with the highest recognition score (a measure of the certainty of the recognition result) and the recognition score when the character category (character code) is selected. calculate. Character string appearance probability calculation 102 in the flowchart of FIG.
Corresponds to this. Here, as the value of T, generally, several possible candidates are considered, a recognition score is calculated for each number of characters, and a portion having the highest score is selected. However, for example, po used in overseas mail
Since the stal code is always determined to be a five-digit number, when the present invention is applied to a device that recognizes a postal code, such as a device in which the number of characters included in an input image is a known certain value D, , T = D.

Further, the character string reading means 13 obtains (T-1) cutout positions and T character categories which should be selected when the recognition score is the highest, and calculates the character string appearance probability. The recognition score obtained in step 102 is also output as a read result. The correct character code calculation / correct cutout position calculation 103 in the flowchart of FIG. 5 corresponds to this.

This series of operations will be described in more detail hereinafter.

First, the definition of a character string recognition score will be described. Entering
Let T be the number of characters in the force image, and
(S-1) (T ≦ S). Input image or special
The feature pattern converted to the symbol
When divided, S partial images are created. This S parts
X from the left₁ , X_Two, ..., x_S(1,
..., S is the index of the partial image). S partial images x
₁ , X_Two, ..., x_SAre arbitrarily divided into T groups.
T sentences included in the input image for each divided group
When matching each character,
The index of the partial image₁, S_2,…, S_TAnd
However, if all the partial images are
To be assigned to₁ <S_Two <… <S_T = S and
I do. For example, if T = 5 and S = 9, x₁ , X_Two, X₃ , X₄ , X₅, X₆ , X₇, X
₈ , X₉  9 partial images are created, which are group 1 x₁ , X_Two  Group 2 x₃  Group 3 x₄, X₅, X₆  Group 4 x₇, X₈  Group 5 x₉  If T = 5 groups as in₁ , X_Two
Is the first character, x₃Is the second by itself
Character, x₄ , X₅, X₆Is the third pattern
Each partial image is assigned to each character
It is. The partial image at the end of the character is
Partial image (x_Two, X ₃ , X₆ ,
x₈ , X₉). That is, S₁= 2, S_Two= 3,
S₃= 6, S₄= 8, S₅= 9 (in actual processing
I think only one kind of grouping
The recognition score for all combinations of groupings.
Calculate and select the group with the highest recognition score
To get the character cutout that seems correct
). Also, a character pattern X corresponding to the t-th character_t 
Is X as a pattern connecting several partial images._t
= (X_st-1+1, ..., x_{S t}) (Where S₀
 = 0). The category to which each character belongs is W₁, W
_Two, ..., W_T And At this time, the recognition score A is [Equation 1].
Is defined by

[0035]

(Equation 1)

Here, z ₁ ,..., Z _T are respectively 1,
.. Represents the character state corresponding to the T-th character. π _ik is the probability that the character state is i under the condition that the first character belongs to category k, and a _ijkl is the character after the second character belongs to character category l (el) and immediately before it Under the condition that the character belongs to the character category k and the character state was i at the time of the immediately preceding character, it means the probability that the current character state is in j. Also,
μ _ik and Σ _ik are parameters characterizing the occurrence of a character pattern when the character state is i and the character category is k, and are the average and the covariance, respectively. f (X | μ, Σ) represents a normal distribution (Gaussian distribution) of mean μ and covariance Σ.

Π _ik and a _ijkl (i, j = 1, 2,...,
N. k, l = 1, 2,..., C. (N is the number of character states, C is the number of character categories) is a parameter that defines the transition of character states on the condition of character categories k and l, and is a parameter that represents the likelihood of adjacent character patterns. These are called character state transition probabilities. These are stored in the character state transition probability storage means 15 of the block diagram of FIG. On the other hand, μ _ik and Σ _ik are probability density functions f in which a given character pattern appears when state i and category k are assumed.
Therefore, it can be considered as a kind of template. These are the character template storage means 16 in the block diagram of FIG.
Is stored in

The character state transition probability a _ijkl defines the transition between the character templates (μ _ik , Σ _ik ) and (μ _jl , Σ _jl ). The larger the value of a _ijkl ,
This means that it is highly valid that a character pattern candidate represented by the character template (μ _ik , Σ _ik ) and a character pattern candidate represented by (μ _jl , Σ _jl ) are adjacent to each other.
These character state transition probabilities and character template parameter values are automatically obtained by learning as described later.

The character appearance probability calculating means 14 gives a given character pattern candidate in response to a request from the character string reading means 13 and referring to the parameters of the character state transition probability storing means 15 and the character template storing means 16. Calculate the probability that appears. In other words, the character string reading means 13 character pattern candidate _{X t = (x st - 1} + 1, ..., x S t) and assuming the character category l and character state j that character pattern candidate belongs, of the character immediately preceding the The character category k and the character state i to which the character Xt- ₁ belongs are stored in the character pattern storage unit 30, the main character code storage unit 31, the sub character code storage unit 32, the main character state storage unit 33, and the sub character state storage, respectively. When stored in the means 34, the character appearance probability calculator 14 reads them out and calculates the probability a that the character pattern candidate appears.
_{ijkl f (X t | μ jl} , Σ jl) returns a. However, if the given character pattern candidate is the first character of the character string, π _jl f (X _t | μ _jl , Σ _jl ) is returned.

As described above, the character appearance probability calculating means 14
When calculating the appearance probabilities of the character pattern candidates using the character states, each character state transits according to the Markov stochastic process according to the tendency of the deformation of the corresponding character pattern candidate. The value of the character appearance probability is adjusted by evaluating the validity of the connection between adjacent characters.
When calculating the distance between a given character pattern candidate and a dictionary pattern, a character template is selected according to the character state corresponding to the character pattern candidate.

The character string reading means 13 sequentially reads all the character categories considered as l and k one by one,
In addition, all the character states from 1 to N are sequentially substituted one by one as j and i, and the appearance probability of the character pattern is calculated by the character appearance probability calculation means 14 each time. In this way, the character string reading means 13 comprehensively examines all possible character categories and character states to find a combination of character categories with the highest recognition score.

It should be noted that the character appearance probability calculating means 14 uses the pattern X
_{t = (x st - 1 +} 1, ..., x S t) when calculating the probability of performing simple feature transform for the character pattern candidates.
That is, although the number of pixels in the vertical direction is compressed by the character extraction / feature extraction means 12, the number of pixels in the horizontal direction is compressed to several pixels in the same manner. For example, if the vertical direction is compressed to four pixels by the character extracting / characteristic extracting means 12, the horizontal direction is also compressed to four pixels. This gives 4 × 4 = 16
Since pixels remain, these pixel values are arranged for each of the four directional images to create a 64-dimensional vector in total. Based on this, the appearance probability of the character pattern candidate is calculated.

Processing for obtaining the maximum value of the recognition score of [Equation 1] in the character string appearance probability calculation 102 in FIG. 5 and (T-1) extraction in the correct character code calculation / correct extraction position calculation 103 in FIG. In the process of obtaining the combination of the position and the T categories, the calculation is efficiently performed using a recurrence formula in order to reduce the processing time. The calculation procedure will be described.

Now, assuming that the first to s-th characters of the partial images x ₁ ,..., X _S are used to recognize the first to t-th characters, the t-th character belongs to the category w, and placing the maximum value of the state at that time is the recognition score under the condition that in the _{z a t (s, z,} w) and (note the difference between the lower case s and uppercase S). In other words, A _t (s, z,
w) indicates that the character category to which the t-th character belongs is w and t
Assuming that the character state corresponding to the th character is at z and is the boundary position s (= index of the partial image located at the end of the t th character) between the t th character and the t + 1 th character Is the maximum value of the recognition score from the first character to the t-th character. At this time, a recurrence formula for t such as [Equation 2] holds.

(Equation 2)

According to the recurrence formula, the character string reading means
13 is that the final recognition score A is A = ma by performing calculations on s, z, w while sequentially increasing t.
x _w Σ _z A _T (S, z, w) (where Σ _z means the summation with respect to z). At this time, the character string reading means 13 calculates the recognition score according to the recurrence formula while storing the character category (character code) to which the target character belongs, the corresponding character state, and the boundary position with the next character. Increment t by one and the next stage recognition score A
When calculating _{T + 1} (s, z, w), all s,
z, through the values _{w, A t (s, z} , w) the value of the required, they (all s, z, w for A
_This is because it is necessary to store _t (the value of (s, z, w)).

The end position of each character and the category to which it belongs can be obtained by sequentially reducing t by the recurrence formula shown in [Equation 3].

(Equation 3)

Here, argmax is a function that calculates the maximum value and returns the argument value when the maximum value is obtained.

Next, the operation of the character string learning device 2 of FIG. 1 will be described with reference to the flowchart of FIG. The character string learning device 2 stores character state transition probability storage means 15 and character template storage means 16 using character string data for learning, that is, character string images and correct character code strings assigned to them. Optimize parameters. A plurality of character string data are used for learning. These images are stored in the learning character string data storage means by an appropriate means such as a scanner.
Stored in 21. In the learning character string data storage means 21, in addition to the image, correct data of a character string written in the image is stored (by an appropriate means such as a keyboard input). The image reading 200 in FIG. 6 corresponds to this.

It is assumed that the number of character string data stored in the learning character string data storage means 21 is K. The character cutout / feature extraction means 22 performs appropriate preprocessing such as binarization processing and normalization processing on each of these K character string images, and then extracts some cutout position candidates from the character string images. Character boundary determining means for detecting and converting the coordinates and the character string image or the character string image by the characteristic extraction processing;
Send to 23. The details of the preprocessing, the extraction position detection, and the feature extraction are described in the character extraction and feature extraction unit 12 of the character string recognition device 1.
Is the same as The character extraction / feature extraction 201 in FIG. 6 corresponds to this.

The character boundary determining means 23 receives, from the character extracting / feature extracting means 22, a set of candidate cutout positions, characteristic patterns, and correct character code strings obtained from the K images. k-th character string image or the feature pattern obtained by converting the character string image X ^(k), correct character code string of W ₁ ^(k) corresponding thereto, ..., and W _T ^(k). Here, the correct number of characters T is constant for each character string image, but may be different. Next, the character boundary determining means 23
Is the case where the correct character code is known for each of k data, and all combinations of (T-1) cutout positions are selected from the cutout position candidates, and the cutout position with the highest recognition score is selected. Calculate the score. The calculation procedure is the same as that of the above-described character string reading means 13 except that the correct character code is fixed. In other words, the character string reading means 13 character pattern candidate X _t ^(k) and category m = W _t ^(k) and the character state j to the character pattern candidate belongs,
The category l = W _{t -1} ^(k) to which the character pattern candidate located immediately before the character pattern candidate belongs and the character state i are respectively stored in the character pattern storage means 35 and the main character code storage means.
36, sub character code storage means 37, main character state storage means 38,
When stored in the sub-character state storage means 39, the character appearance probability calculation means 14 reads them out, and the probability a _ijlm f (X _t ^(k) | μ _jm , Σ _jm ) of the appearance of the character pattern candidate is ^obtained
return it. The character string appearance probability calculation 202 in the flowchart of FIG. 6 corresponds to this.

In this case, the recognition score for the character string is
1), but the correct character code is already
Because we know, maximization max for this_{W 1} ^(k),
…,_WT ^(k)Becomes unnecessary. In calculating the recognition score
Is an efficient calculation by recurrence formula, as in [Equation 2] above.
Is applicable, but the correct character code is known
This eliminates the need for character code maximization calculations,
Recognition scores are obtained by simplified calculations.

Further, the character boundary determining means 23 obtains (T-1) cutout positions selected when the recognition score becomes the highest. This procedure is the same as that for S ₁ ,..., S _{T -1 in} [Equation 3], except that the correct character code is fixed. The calculation 203 of the correct cutout position in the flowchart of FIG. 6 corresponds to this.

According to the procedure up to this point, an individual character pattern from the character string data or a characteristic pattern _Xt ^{(k) obtained} by converting the character pattern data and the corresponding correct character category w
_{Since t} ^(k) (t = 1,..., T. ^k = 1,..., K) is obtained, these are sent to the character learning means 24. The character data generation 204 in the flowchart of FIG. 6 corresponds to this.

The character learning means 24 receives the characteristic pattern X _t ^{(k) of the} individual character and the corresponding correct character code w _t ^(k) (t = 1,..., T. k = 1,. ,
K), and optimizes the parameters stored in the character state transition probability storage means 15 and the character template storage means 16. That is, the parameter is updated so that the total sum or total product of the recognition scores for each character string image is maximized. The parameter update 205 in the flowchart of FIG. 6 corresponds to this. The details of the parameter update calculation will be described below.

First, according to the following recurrence formula of [Equation 4], α
_t ^(k)(i) and β_t ^(k)(j) (i, j = 1, ...,
N. k = 1, ..., K. t = 1,..., T)
You. α _t ^(k) (i) is the character state corresponding to the t-th character
Character pattern candidate X under the condition that is i₁ ^(k)
 , ..., X_t ^(k) Recognition score of β_t ^(k)(j) is t
Under the condition that the character state corresponding to the character number is j
Character pattern candidate X_{t + 1} ^(k), ..., X_T ^(k) Recognition of
Indicates intellectual score.

(Equation 4)

Using the above α _t ^(k) (i) and β _t ^(k) (j) and the current parameters, the parameters are updated as in the following [Equation 5].

(Equation 5)

However, P (X _{1 in} Expression 5)
_{^{(K), ..., X T}} (k) | w 1 (k), ..., w t
^(k) ) is the sum 総 of α _T ^(k) (i) with respect to i.
_It can be calculated as _{i = 1} ^N α _T ^(k) (i) (where Σ _{i = 1} ^N means the sum of i = 1, 2,..., N). Δ _ij means Kronecker's delta (1 if i = j, 0 otherwise). According to the parameter updating procedure of [Equation 5], the total product of the recognition scores of the k character string image data monotonically increases. If the renewal procedure is repeated several times, the increasing tendency of the total volume of the recognition scores is reduced to some extent and hardly increases. With this, it is determined that convergence has occurred (process 206 in FIG. 6). At this point, the desired parameter values are obtained.

In the above-described parameter updating procedure, a method of obtaining a better parameter value by using the currently obtained parameter value is employed. Therefore, it is necessary to first set an initial parameter value. Therefore, a procedure for setting initial values of parameters will be described below.

First, a small amount of character image data that is individually cut out and classified according to character categories is prepared.
If necessary, the character image is subjected to preprocessing in the same manner as the character string recognition device 1 and the character string learning device 2 described above, and is converted into a characteristic pattern. Next, for each category, the data in the category is classified into the same number of clusters as the desired number N of states using a clustering algorithm such as k-means, and the center (average) and variance of each cluster are obtained. Then, the center of the k-th cluster of the i-th category is substituted for μ _ik . Also, the variance of the cluster is substituted for the diagonal component of Σ _ik , and 0 is substituted for the non-diagonal component. Thereafter, the mixture normal distribution is estimated using the maximum likelihood estimation method, and μ _ik and Σ _ik
Is more accurately estimated. The procedure of estimating the mixture normal distribution based on the k-means algorithm and the maximum likelihood estimation method is described in, for example, the document "1990, Fan et al., Hidden.
Markov Models for Speech Recognition, Edinburgh University Press (Huang et a
l., Hidden Markov Models for Speech Recognition,
Edinburgh University Press, 1990) ”and other well-known techniques.

Since π _ik and a _ijkl are probability values, they are appropriately set so that some sum becomes 1. π _ik is π
_1k + _π2k +... + _ΠNk = 1, and a
_ijkl is a _{i 1 kl} + a _{i 2 kl} +... + a _{i N kl} =
Since it must be 1, for example, 1 / N may be substituted for π _{i k} and a _ijkl .

Next, a second embodiment of the present invention will be described with reference to the drawings.

Referring to FIG. 7, according to a second embodiment of the present invention, a data processing device 18, a recording medium 17 on which a character recognition program is recorded, an image storage means 11 similar to FIG. Probability storage means 15, character template storage means
16 is provided. This recording medium 17 may be a CD-ROM, a magnetic disk, a semiconductor memory, or another recording medium,
This includes the case of distribution via a network. The data processing device 18 includes a CPU and a memory.

The character recognition program is read from the recording medium 17 into the data processing device 18, and by controlling the operation of the data processing device 18, the character recognition / character extraction means 12 shown in FIG. , A character string reading unit 13, a character appearance probability calculating unit 14, and each of the storage units 30 to 34. Under the control of the character recognition program, the data processing device 18 detects some cutout position candidates from the character string image input to the image storage means 11 using the character cutout / feature extraction means, performs preprocessing on the image, Extract features. Next, several character pattern candidates are generated from the plurality of cutout position candidates using the character string reading means, the character appearance probability calculating means, and the respective storage means, and the character state transition probability is calculated for each of the character pattern candidates. Recognition processing is performed using the character state transition probabilities and the character templates stored in the storage unit 15 and the character template storage unit 16, respectively, and a read result is obtained and obtained which can obtain the maximum recognition score for the entire character string. That is, in the embodiment of the present embodiment, the data processing device 18 controls the character recognition program to control the character cutout / characteristic extracting unit 12, the character string reading unit 13, and the character appearance probability calculating unit 14 in the first embodiment. , Character pattern storage means 3
0, main character code storage means 31, sub character code storage means 3
2.Main character state storage means 33 and sub character state storage means 34
And outputs the result of reading the character string.

[0064]

As described above, according to the present invention,
In reading a character string, a plurality of character states representing several types of character deformation are prepared for each character category, a network connecting them is considered, and the shape of each of two adjacent character patterns is represented. By evaluating the validity of the connection in consideration of the character state and character category, high precision is taken into account that the character shape is deformed due to continuous writing from the character written immediately before, contact, and changes in the writer Can recognize characters,
As a result, accurate character string reading is realized. In addition, since this state network can be optimized using learning character string data whose cutout position is unknown together with a character pattern template, there is no need to prepare individual character data for learning, etc. It is possible to easily construct a processing system with less labor.
Further, since the dependency between the character patterns is replaced with the dependency of a discrete symbol called a character state for processing, the processing amount can be reduced.

[Brief description of the drawings]

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

FIG. 2 is a diagram of a character image showing an example in which a character error depends on the character type.

FIG. 3 is a diagram of a character image showing an example in which the manner of error of a character depends on the writer.

FIG. 4 is a diagram illustrating an example of a result obtained by converting an input character string image into a feature pattern.

FIG. 5 is a flowchart showing a flow of processing according to an embodiment of the present invention.

FIG. 6 is a flowchart showing a flow of processing according to an embodiment of the present invention.

FIG. 7 is a block diagram showing a functional configuration of one embodiment of the present invention.

FIG. 8 is a block diagram showing a functional configuration of an embodiment of the related art.

[Explanation of symbols]

 DESCRIPTION OF SYMBOLS 1 Character string recognition device 2 Character string learning device 11 Image storage means 12 Character extraction / feature extraction means 13 Character string reading means 14 Character appearance probability calculation means 15 Character state transition probability storage means 16 Character template storage means 17 Recording medium 18 Data processing Apparatus 21 Learning character string data storage means 22 Character extraction / feature extraction means 23 Character boundary determination means 24 Character learning means 30 Character pattern storage means 31 Main character code storage means 32 Sub character code storage means 33 Main character state storage means 34 Sub characters Status storage means 35 Character pattern storage means 36 Main character code storage means 37 Sub character code storage means 38 Main character state storage means 39 Sub character state storage means 41 Image storage means 42 Character cutout / feature extraction means 43 Character string reading means 44 Characters Appearance probability calculation means 45 Character template storage means 46 Character pattern storage means 47 Character code storage means 48 Learning Character data storage means 49 Character learning means 100 Image reading 101 Character extraction / feature extraction 102 Character string appearance probability calculation 103 Correct character code calculation / correct extraction position calculation 200 Image reading 201 Character extraction / feature extraction 202 Character string appearance probability calculation 203 Correct answer Cutout position calculation 204 Character data generation 205 Parameter update 206 Convergence judgment

Claims (11)

[Claims] An image storage means for storing an input character string image, a candidate for a boundary between adjacent characters is detected as a cutout position candidate from the character string image received from the image storage means, and a character string image is detected. Character extraction / feature extraction means for extracting features that are converted to a smaller amount (feature) useful for identification, and character extraction for individual character pattern candidates when a character string image is divided by selecting some extraction position candidates Character string reading means for performing recognition and outputting an optimum cutout and an optimum character code string as a whole character string as a result of reading the character string; and a character pattern candidate, a character code, and a character deformation from the character string reading means. A character state that is an index indicating the type, a character code of a character pattern candidate located immediately before a given character pattern candidate,
Character appearance probability calculating means for receiving a character state and calculating a probability that a given character pattern candidate appears under a given character code and character state; and the character appearance probability calculating means calculating a character appearance probability The character state transition probability storage means for storing a numerical value (state transition probability) required to calculate a part of the probability that depends on the character state, and the character appearance probability calculation means for calculating the character appearance probability ,
A character recognition device comprising: character template storage means for storing a numerical value (character template) necessary for calculating a portion of a probability depending on a character pattern. 2. A character pattern storage means for storing a character pattern which is passed when the character string reading means requests the character appearance probability calculation means to calculate a character appearance probability. Two character code storage means for storing a character code corresponding to the character pattern candidate and a character code corresponding to a character pattern candidate positioned immediately before the character pattern candidate to be passed to the occurrence probability calculation means; and 2. The apparatus according to claim 1, further comprising: two character state storage means for storing a character state corresponding to the character pattern candidate and a character state corresponding to a character pattern candidate located immediately before the character state, which are passed to the appearance probability calculation means. Character recognition device according to the description. 3. When the character appearance probability calculation means calculates the appearance probability of a character pattern candidate using the character state,
Each character state transitions according to the Markov stochastic process according to the tendency of deformation of the corresponding character pattern candidate, and the character appearance probability is evaluated by evaluating the validity of the connection between adjacent characters depending on the magnitude of the transition probability between these states. 3. The character recognition device according to claim 1, wherein the value of the character is adjusted. 4. The method according to claim 1, wherein when calculating the distance between the given character pattern candidate and the dictionary pattern, the character appearance probability calculation means selects a character template according to the character state corresponding to the character pattern candidate. The character recognition device according to claim 3, wherein 5. The character template storage means according to claim 1, wherein said character appearance probability calculation means includes a plurality of character templates for use in accordance with the character state corresponding to the immediately preceding character pattern candidate in the form of a normal distribution in the character template storage means. The character recognition device according to claim 4, wherein 6. When the character string reading means calculates a recognition score which is a measure of the likelihood of the recognition result of the character string,
The second character, starting from the score attributed to the first character, 3
The score is sequentially added to the second character, and the recognition score is calculated according to the recurrence formula while storing the character category (character code) to which the character of interest belongs, the corresponding character state, and the boundary position with the next character. The character recognition device according to claim 1 or 2, wherein: 7. A learning character string data storing character string data used for estimating an optimum character state transition probability and an optimum character template from a given character string image and its correct character code string. Storage means for detecting a candidate for a boundary between adjacent characters as a cutout position candidate from the character string image received from the learning character string data storage means, and reducing the character string image to a smaller amount (feature) useful for identification. Character extraction / feature extraction means for extracting the features to be converted, character pattern candidates, character codes, character states which are indexes indicating the types of character transformation, and characters of character pattern candidates located immediately before a given character pattern candidate A character output that receives a code and character state and calculates the probability that the given character pattern candidate appears under the given character code and character state A probability calculating means, a character boundary determining means for estimating a boundary of a character in the character string image using the correct character code string given to the character string image and the character appearance probability calculating means, and the character boundary determining means A character pattern storage unit that stores a character pattern candidate to be passed when requesting the character appearance probability calculation unit to calculate a character appearance probability, and a character code in the correct character code string corresponding to the character pattern candidate and a character immediately before the character code. Two character code storage means for storing codes, two character state storage means for storing a character state corresponding to the character pattern candidate and a character state corresponding to the character pattern candidate immediately before the character pattern candidate, and the character appearance probability calculation When the means calculates the character appearance probability, the character state transition probability case stores the numerical value (state transition probability) necessary to calculate the part of the probability that depends on the character state. When the character appearance probability calculation means calculates the character appearance probability,
Character template storage means for storing a numerical value (character template) necessary for calculating a part of the probability depending on the character pattern, and individual character patterns cut out by the character boundary determining means and their arrangement order are used. A character learning unit for updating the character state transition probability stored in the character state transition probability storage unit and the character template stored in the character template storage unit. 8. A character pattern storage unit for storing a character pattern candidate to be passed when the character boundary determination unit requests the character appearance probability calculation unit to calculate a character appearance probability, and a correct answer corresponding to the character pattern candidate. Two character code storage means for storing a character code in a character code string and a character code immediately before the character code, and a character state corresponding to the character pattern candidate and a character state corresponding to the character pattern candidate immediately before the character code candidate. The character learning device according to claim 7, comprising: two character state storage units. 9. The character learning unit according to claim 7, wherein the character learning means simultaneously optimizes the character state transition probability and the character template so that the total sum or the total product of the recognition scores of the character string data is maximized. The described character learning device. 10. The character learning means uses character string data whose cutout position is unknown, and uses an individual character image automatically cut out by a character boundary determining means so as to maximize the recognition score of the character string. 9. The character learning device according to claim 7, wherein the character state transition probability and the character template are simultaneously optimized. 11. A recording medium storing a character recognition program operating on a computer, comprising the steps of: inputting and storing a character string image in the computer; Detecting a cutout position candidate and performing feature extraction for converting the character string image into a smaller amount (feature) useful for identification; generating a plurality of character pattern candidates based on the cutout position candidate; Using the character pattern candidate, the character code and character state for the character pattern candidate, and the character code and state for another character pattern candidate located immediately before the character pattern candidate, transition of the state corresponding to two adjacent characters Probability that each character pattern candidate appears while evaluating the validity of the connection between two adjacent character patterns based on the probability Calculating, and outputting to search the character segmentation and character code string as obtained the highest score in the entire string,
A computer-readable recording medium recording a program to be executed.