JP3145071B2 - Character recognition method and device - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to the recognition of a word string having a hierarchical structure, and more particularly to a method and apparatus for character recognition which is preferable for reading the address of a postal matter.

[0002]

2. Description of the Related Art In order to read a printed or written address, the following three functions are required.

(1) Cut out a character pattern. (Character cut
Ride and) (2) identifies the character type of each character pattern. (Character identification) (3) The result of character identification is interpreted as a character string. (Character string collation) Among these, factors such as incomplete description and noise are (1)
In most cases, (2) cannot be used. For more accurate character recognition, the complementing function in (3) character string collation is important.

A typical example of a word string having a hierarchical structure is a town area portion of an address character string. This matching method uses "prefecture"
A method of obtaining address structure candidates based on key characters such as “city” and “town” and obtaining an address character string by applying a hierarchical relationship (Transactions of the 41st Annual Convention of IPSJ 90 4L-5 "Examination of post-processing method for character recognition result of address"), a method of extracting an address character string by extracting place names constituting an address by word matching and tracing the hierarchical relationship of the address from top (prefecture) to top down ( 1979 IEICE National Convention D-465 "Knowledge Processing for Freely-written Address Strings")
And so on. In the method described in IPSJ Transactions No. 35, No. 6, "Error Correction Algorithm for Handwritten Kanji Address Recognition", a place name word at an arbitrary position is extracted by an automaton-type word collation even if the candidate character is incomplete. At the same time, by performing a bottom-up process of determining the positional relationship between place names while tracing the hierarchical relationship from the lower hierarchy to the upper hierarchy based on the candidate place name of each hierarchy, flexibility in address notation, complementing ability and processing It solves the problem of quantity and realizes a practical method.

[0005] However, in these methods, when a character candidate is incomplete, completion is performed on a word-by-word basis, and a penalty is added to evaluate the incompleteness of the word. As a result, a plurality of penalized word candidates appear, which increases the possibility of selecting an erroneous candidate as a street address character string that is a word string candidate.

[0006]

In the above prior art,
Word matching is performed for noise that is mixed in the word string to be read, blurred characters, incorrect patterns caused by handwritten character deformation, or difficult to identify and incomplete identification candidate characters. In that case, the candidate responded by issuing a complemented word candidate and imposing a penalty appropriate to that. In order to perform matching using words as the minimum unit,
When a word is incomplete, a word penalty is imposed on the candidate word, and a word string must be selected from word candidates with low certainty, which has a problem in reliability.

[0007] The problem to be solved by the present invention is to provide a word string having high accuracy and reliability by performing collation at the level of the characters constituting the word even if the word described is incomplete due to missing characters or the like. Getting candidates.

[0008]

In order to solve the above-mentioned problems, according to the present invention, not only words originally existing in the dictionary but also partial character strings constituting a part of the words are used as word candidates, and the character level is used. Is matched. In the following, a character string forming a part of such a word will be referred to as a partial word, and word matching based on the partial words will be referred to as partial word matching.

This partial word collation is performed when a part of the word is obtained with high reliability from among the candidate characters, and a candidate word string can be selected by using the partial word. In addition, by performing hierarchical processing, word string candidates can be obtained with a high degree of certainty.

Although there is a possibility that the same word candidate may appear even by complementing the conventional method, in this case, the penalty is imposed excessively for the low degree of matching of the character with the word. The partial word uses only a part with a high degree of coincidence, so that the word penalty is low, a higher degree of certainty can be obtained when connected as a word string, and the reliability as a word string candidate is high.

[0011]

[0012]

[0013]

[0014]

DESCRIPTION OF THE PREFERRED EMBODIMENTS FIG. 1 is a flowchart showing an example of an embodiment of a character recognition method according to the present invention. This example is an address recognition process in which an entire image obtained by photoelectrically converting a surface on which an address is described is input and an address character string as a read result is output.

Here, the present character recognition method is applied to reading of a word string in a town area from a prefecture to a town name in an address of an address, and an example in which the candidate character lattice is incomplete is shown in FIG. It is assumed that a postmark has been applied to a town area.

An addressing surface such as a postal matter is taken in as an image input 101 by an image pickup means (scanner section).
A character line extraction process 102 extracts an address character line from the entire image.

Next, a pattern extraction process 103 extracts a pattern candidate that can be a character from the address character line.

The character identification process 104 performs character identification for each of the extracted pattern candidates using the character identification dictionary 105, and outputs a plurality of candidate characters and the degree of similarity between the candidate characters.

The characters cut out Shi processing 106, the positional relationship between characters identified similarities and patterns of the pattern candidates do selection pattern based on, as a character segmentation candidate generating one or more pattern rows Output.

The word matching process 107 searches for a word in the town area address dictionary 108 from a candidate character lattice obtained by combining the character segmentation result and the identification candidate character of each pattern. The corresponding parts of the character lattice are compared, a penalty corresponding to the degree of matching of each character is calculated, and the result is output as a word candidate. A word candidate lattice is created from the thus obtained word candidates and the positional information of each word candidate.

The town area address dictionary 108 stores words of each layer and information on connection relationships between the layers, and is referred to for generating a town area word string of addresses.

The hierarchy processing 109 searches word candidates in the upper hierarchy in order from the lowest hierarchy of the town area address dictionary 108 on the word candidate lattice based on the connection relation, and generates a word string. The validity of the positional relationship between the connected words is defined as a connection penalty, and the degree of certainty as a word string is calculated in combination with the word penalty, thereby defining a candidate word string for a town area.

In the hierarchical processing 109, if a valid word is not found as a higher word to be connected even though the word penalty is sufficiently low, the partial word matching processing 110
I do. The partial word matching process 110 searches for a connectable high-order word from the town address dictionary 108 and performs word matching on the candidate character lattice for those partial character strings that can identify the town address character string. is intended intends line. As a result, the partial word comes up as a candidate, and if the word penalty and the connection relationship are appropriate, this is used as a candidate word string in the town area.

The reading result selection processing 111 selects the one having the highest certainty as the recognition result of the town area part from the candidate word strings of the street address based on the certainty.

After the town area candidate is selected, a block number representing a street or an address is read 112 from the position following the end of each town area candidate in the candidate character lattice, and is output as a final address read result 113. .

Next, the details of each process in FIG. 1 will be described.

The character line extraction process 102 is a process for extracting an address character line from the image 201 of the mail address surface. The address character line represents a rectangular area 202 including the name of the prefecture, the name of the city, the name of the city, and the address. If the address extends over a plurality of lines, a rectangular area corresponding to the number of lines is output. As a method of extracting an address character line, for example, Japanese Patent Application Laid-Open No. 9-1610
A method as described in FIG.

The pattern cutting process 103 will be described with reference to FIG. The pattern cutout processing is performed on the address character line 2
A candidate for a character boundary is extracted based on a cluster of black pixels on 02 (connected component), and a plurality of combinations of patterns that can become a character are selected as character pattern candidates. At this time, cutting processing of the contacted character pattern is also performed. Numeral 301 is a diagram expressing a pattern cut out of the address character line 202 in a graph. Hereinafter, this is called a cut-out graph.

The character identification processing 104 is realized by using a known method such as pattern matching or structure analysis. By character identification, it is assumed that a plurality of candidate characters and the similarity to the standard pattern in the character identification dictionary 105 are obtained for each of the extracted pattern candidates as shown in FIG.

The characters cut out Shi processing 106 performs selection of patterns positional relationship between the similarity and pattern of the identifying candidate character of each pattern candidate obtained in the character identification process 104 on the basis of FIG. 5 Thus, one or a plurality of pattern strings are generated and output as character cutout candidates. The selection of patterns can be regarded as an optimal path search problem on a cut-out graph having an arc weighted by a similarity or a positional relationship between patterns.

The structure of the street address dictionary 108 will be described with reference to FIG.

The town area address dictionary 108 is used for the word matching process 10.
7, a hierarchy process 109, and a dictionary referred to in the partial word collation process 110. As shown in FIG. 6, the dictionary is composed of four layers of place name word dictionaries 601 to 604. The place name word of each hierarchy has connection information to the place name word of the upper hierarchy, and the town area word string of the address connects words according to the connection information from the core word of the third or fourth hierarchy from the bottom up. It is obtained by going. In the word matching processing 107, the place name words in each layer are referred to to create word candidates. In the hierarchical processing 109, the word is connected by referring to the core place name word and sequentially going to the place name word dictionary of the upper hierarchy based on the connection information of the word, thereby obtaining a town area word string candidate. Further, in the partial word matching process 110, the reference to the core word, the search for the higher-order connected word, and the acquisition of the word information for creating the partial word are performed using the town address dictionary 108.

The word collation processing 107, the hierarchy processing 109, and the reading result selection processing 111 are realized according to the method described in IPSJ Transactions No. 35, No. 6, "Error Correction Algorithm for Handwritten Kanji Address Recognition". .

In the word matching process 107, as shown in FIG.
A dictionary word is searched from each candidate character in the candidate character lattice 701 composed of the character cutout candidate 501 (and 502) and the identification candidate character of each pattern, and a dictionary word having the first or second character matching is determined as a candidate word. I'll give it. "temple
Tamachi, Terada, Kotobukicho, Nakamachi, Nakayama, Honjuku
"Honmachi", "Honda" and "Kinoshita" are simple
The second letter of "Fuchu" and "Fuchu"
Is a word. At this time, a penalty is calculated for each candidate word in consideration of the degree of matching with each corresponding character on the candidate character lattice 701. This word penalty is 0 when all the character candidates of the word are first. A word candidate lattice 702 is created from the thus obtained word candidates and position information on the description position of each word candidate. In the example of 702, for example, for “Honmachi” 703, the word penalty is 0 because there are all the first character candidates, and “Honda”
In 704, “book” is first and “many” is not a candidate.
A big penalty will be imposed. Further, for “Fuchu City” 705, “Middle” is the second candidate and no candidate characters corresponding to “Fu” and “ City ” are found, so the word penalty is further increased.

The hierarchical processing 109 is performed in the word candidate lattice 70
Word of the hierarchy corresponding to 2 of the lowest (for example, "Hon'yado town" Ya
Based on the connection relation of the town area address dictionary 108, the words in the upper hierarchy are sequentially arranged in the word candidate lattice 70 with "Honmachi" as a core.
2 to generate a town area word string of the address. The validity of the positional relationship with respect to the description position of the connected word is defined as a connection penalty, and the degree of certainty as a word string is calculated together with the word penalty, thereby defining a candidate word string for a town area. FIG. 8 illustrates a state of the hierarchical processing in the word candidate lattice 702. In this case, the core word is the third hierarchy, and the only upper hierarchy word that can be connected is “Fuchu City” in the second hierarchy. The word strings that can be formed based on the connection relationship are “Fuchu City Kotobukicho”, “Fuchu City Fuchucho”, “Fuchu City Honmachi”, and “Fuchu City Honjukucho”. When only one character is allowed, the locations that are appropriate as the positional relationship are “Fuchu-shi Honmachi” and “Fuchu-shi Honjuku-cho”. However, these also have a large word penalty for "Fuchu",
The connection penalty is added to the extent that the second-layer word and the third-layer word overlap, and the certainty factor as a word string is reduced.

FIG. Partial word matching process 110 9 and FIG. 1
Explanation will be made using 0.

The partial word matching process 110 is performed in the hierarchical process 10
9, despite the small word penalty,
When a valid word is not found as a top word to be connected, a word that can be connected is searched from the street address dictionary 108,
Substrings of these words are dynamically (ie, originally,
Generate a partial character string that does not exist in the street address dictionary)
Then, of the partial character strings , those for which the street address character string can be identified are subjected to word matching on the candidate character lattice 701. In the hierarchical processing 109, when the penalty of the core word is small on the word candidate lattice 702 and the upper word is not found, the town area word string 902 including the core word is selected from the town address dictionary 108 first. In order to select a town area word string, a core word is found from the town area address dictionary as shown in FIG. 9 and upper words are connected according to the connection information of the word. Next, of the town area word strings obtained in this manner, the following processing is performed on only the word that is uniquely determined by the core word and its upper words. The target town area word string is
The town area word string can be identified by the core word and its superordinate words. Therefore, of the words included in the target town area word string, word matching using partial words is performed for each of the upper words of the core word. In this example, “Honmachi” 901 is a word having a small penalty and no valid upper word to be connected. For “Honmachi” 901, “Kokubunji city” 100 as shown in FIG.
It is assumed that 1 “Fuchu City” 1002 and “Tanashi City” 1003 have risen. In this case, partial words such as one character, two characters... From the end of the word, such as 1004, are dynamically created in consideration of the incompleteness of the head of the word. In order to maintain the uniqueness of the town area word string determination based on the partial words, the remaining partial words are removed from all the created partial words as partial word candidates . As a result, four effective
Partial words are dynamically generated. And these partial
Line the word verification on the candidate character lattice 701 for the word
U. When word matching is performed on these partial words , the simple words in FIG.
Word matching result added to word candidate lattice 702
A word candidate lattice like 1006 in FIG. 10 is obtained. In 1006, "Bunji", "Teraichi" and "Nakaichi" are added
Have been. "Muichi" is a candidate character lattice 701
Since "none" does not match, it is not added . If a partial word comes up as a candidate, the added word candidate lattice 1
Based on 006, hierarchical processing is performed . At this time, the connection relation of the partial words is inherited from that of the original word, but a connection to a higher order is not required. In this example, the added word candidate lattice 1
Since hierarchical processing is performed based on 006,
The connection with "Honda" as the core was also examined again, and FIG.
Like "(Fuku) Honjuku-cho in Naka-shi""Honda in (Kuni-)"
A connection such as “(Kokubu) Teraichi Honda” may be possible, but these are not adopted because the core words “Honjukucho” and “Honda” have a large word penalty. In this way, if the partial word is raised as a candidate and the connection relation with the word penalty is appropriate, this is set as a candidate word string in the town area. In this case,
“(Fu) Nakaichi Honmachi”, “(Kokubu) Bunji City Honmachi” and “(Kokubu) Teraichi Honmachi” are added as candidate word strings.

The reading result selection processing 111 selects the one having the highest certainty as the recognition result of the town area portion based on the certainty degree from the word string candidates of the town area. In this example, “(Kokubun) Teraichi Honmachi” is finally obtained as a town area word string from the word penalty and the connection penalty.

After the candidates for the town area word string are selected, block numbers indicating the streets and addresses are read 112 from the position following the end of each town area candidate in the candidate character lattice, and the final address read result 113 Output as

[0040]

According to the method and apparatus of the present invention described above,
When recognizing a word string having a hierarchical structure such as a town area of a postal address , even if the word is incomplete, the word string with high accuracy can be obtained by collating at the level of the characters that make up the word Candidates can be obtained.

[Brief description of the drawings]

FIG. 1 is a configuration diagram illustrating an example of an embodiment of a real name invention.

FIG. 2 is a conceptual diagram showing an example of a mail address surface image and an address character line.

FIG. 3 is a diagram showing a relationship between a pattern cutout process and a cutout graph.

FIG. 4 is a diagram showing each pattern and the result of its character identification processing.

FIG. 5 is a diagram showing an example of a character cut out Shi candidate.

FIG. 6 is a conceptual diagram showing a configuration of a town address dictionary.

FIG. 7 is a diagram showing a relationship between a candidate character lattice and a candidate word lattice.

FIG. 8 is a diagram showing an example of a procedure of a hierarchical process.

FIG. 9 is a conceptual diagram showing a procedure for selecting a target for creating a partial word.

FIG. 10 is a diagram showing a procedure for creating a partial word and a partial word matching process.

FIG. 11 is a diagram showing a procedure of hierarchical processing using partial word candidates.

[Explanation of symbols]

101: input image, 102: character line extraction processing, 103:
Pattern cutout processing, 104... Character identification processing, 105
... character identification dictionary, 106 ... character cutout processing, 107 ...
Word matching processing, 108: town area address dictionary, 109: hierarchical processing, 110: partial word matching processing, 111: reading result selection processing, 112: block reading, 113: address reading result, 201: postal address face image, 202 ... Address character line, 301: cut-out graph, 401: character identification result,
501: character extraction candidate 1, 502: character extraction candidate 2, 601: first-level place name word dictionary, 602: second-level place name word dictionary, 603: third-level place name word dictionary, 60
4. Fourth hierarchical place name word dictionary, 701: Candidate character lattice, 702: Candidate word lattice, 703: Candidate word example "Honmachi", 704: Candidate word example "Honda", 705 ... Candidate word example "Fuchu" 901: a core word for activating the partial word matching process; 902: a town area word string identified by the partial word; 1001: an example of a word to be subjected to the partial word creation: "Kokubunji City"; 1001 ... Examples of words for which partial words are to be created, “Fuchu City”, 1001. Examples of words for which partial words are to be created, “Tanashi City”, 1004, partial words, 1005, valid partial words.

──────────────────────────────────────────────────の Continuing from the front page (72) Katsumi Marukawa, Inventor Katsumi Marukawa 1-280, Higashi-Koigakubo, Kokubunji-shi, Tokyo Inside the Central Research Laboratory, Hitachi, Ltd. Central Research Laboratory (56) References JP-A-7-39819 (JP, A) Katsumi Marukawa, et al., "Error Correction Algorithm for Handwritten Kanji Address Recognition", Transactions of Information Processing Society of Japan, Vol. 35 No. 6 June 1994 IPSJ 1101-1110 (58) Fields investigated (Int. Cl. ⁷ , DB name) G06K 9/72

Claims (1)

(57) [Claims] 1. An image of the contents of a document on which an address is described
Extract character lines from information converted to electrical signals by input means.
Character line extraction processing, and extracting the character boundary candidates of the above character line
Character patterns
Pattern extraction processing as candidates and multiple candidate sentences for each of the above character pattern candidates
Character and similarity to standard pattern in character identification dictionary
Character identification processing and the similarity of the plurality of candidate characters and the positional relationship between the patterns.
Generate one or more pattern strings based on the
Character segmentation processing to output as a candidate for extraction, and multiple place name word dictionaries in the hierarchy
In a street address dictionary with connection information to place name words in the hierarchy
From the above character extraction candidates and candidate characters for each pattern
For each candidate character in the candidate character lattice,
Words with the same letter or second letter as word candidates
And extract each word candidate on the candidate character lattice.
Calculate word penalty considering matching with corresponding characters
And the position of each word candidate
Word matching processing to create word candidate lattices from placement information
And the word at the lowest level of the above word candidate lattice
To the upper floor based on the connection
Layer words are searched sequentially from the above word candidate lattice, and the
Generate street word strings and connect to core words
Connect the validity of the positional relationship regarding the written position of the word
Ruti and the above town area unit with the word penalty
A hierarchical process for calculating a certainty factor as a word string; and a word penalty of the core word in the hierarchical process.
Despite its small size, connect to the above core words
If no valid high-level word is found,
Words that can be connected to the core words are stored in the above street address dictionary
And automatically generates a substring of the searched word.
And remove duplicates among the generated substrings
Perform word matching on the candidate character lattice for
The first or second character is on the candidate character lattice
The word climate as a word candidate in case that matches the candidate character
Partial words are added when the partial word matching process to be added to the supplemental lattice and the above partial word matching process are performed.
Hierarchical processing performed based on the word candidate lattices obtained, and the town area word string generated by the hierarchical processing described above.
Reading result selection processing to select the one with the highest confidence
And a character recognition method comprising: