JP3201207B2 - Address reading apparatus and method - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to an address reading apparatus and an address reading method for reading address information written on a mail in order to automatically sort the mail.

[0002]

2. Description of the Related Art As address information, for example, "3-8-1, Nishi-Koigabo, Kokubunji-shi, Tokyo" is described. Is defined as address display number information. 2. Description of the Related Art Conventionally, as an automatic postal reading classification method, a method of classifying town area information is known. This has a hierarchical structure of "Tokyo", "Kokubunji", and "Nishi-Koigabo", so even if one or two characters cannot be recognized, use the hierarchical structure to interpolate it by knowledge processing. so,
This is because it is possible to recognize the entire area information. On the other hand, the address display number information does not have such a hierarchical structure, and various description forms exist for address display numbers having the same meaning. For example, "3 chome 8 ichi 1", "3 chome 8
"-1", "3-8-1" and "1 of 3-8" mean the same address display number.

Conventionally, as a method of classifying such address display numbers, for example, Japanese Patent Application Laid-Open No. 6-124366 or IEICE NCL 92-26, PR
U92-40 (October 1992) "Chome / Block Recognition Method in Address Reading" is known. This method recognizes each cut-out character pattern, labels it according to the character type of the recognized result, and divides the address display number part into a numerical part and a delimiter information part.

For example, "3-chome 8-1" is replaced with "NDDDND".
N "(N: label representing arithmetic numeral, D: label representing delimiter information). After that, a plurality of processing functions corresponding to all combinations of labels are prepared in advance, and by calling the individual processing functions corresponding to the labeling described above,
It recognizes the address display number.

[0005]

However, the above method has two major problems. The first problem is that erroneous recognition cannot be sufficiently dealt with. For example, if the address display number “3-chome 8-1” is input and the recognition result of “chome” contains only recognition candidates other than characters representing numbers and delimiter information, labeling may be performed. I can not respond because I can not do it. Alternatively, if the area of the address display number cannot be detected, labeling cannot be performed, so that the address display number cannot be recognized.

[0006] In the above method, characters representing delimiter information are represented by one label and are not distinguished. Therefore, for example, if the "eye" of "3-chome 8-1" is erroneously recognized and there is a recognition candidate of "8", the labeling of "NDNNNDN" will be made, and the number between the numbers will be displayed. At first glance, the labels are separated by the delimiter information, so that seemingly consistent labels can be obtained.

[0007] This problem can be solved by separating the delimiter information in detail. However, in this apparatus, for the purpose of high-speed processing, individual processing functions corresponding to labeling are provided and each processing is performed. Therefore, in order to classify and process various notation patterns of address display numbers in detail, it is necessary to provide an extremely large number of processing functions.
It will be very difficult.

[0008] The second problem is that the individual processing function method requires a new function to be created when registering a new notation pattern, which makes maintenance difficult.

The present invention solves the above-mentioned problems without sacrificing the processing speed, and when the address display number cannot be automatically recognized, confirms whether the operator inputs the correct address display number. The purpose is to provide assistance. Other purposes will become apparent from the description of the specification.

[0010]

In order to solve the above problems, the present invention basically provides five features. The first feature is that word matching is performed using a wildcard representing an arbitrary number. A candidate character lattice storing a candidate character group and a corresponding penalty is obtained as a character extraction and recognition result from the mail address information.
Thereafter, the head of the address display number area is detected by knowledge processing, and word matching is performed to extract a correct address display number from the candidate character lattice of the address display number area. However, since the numbers representing the streets and numbers can take arbitrary numbers, it is virtually impossible to hold the word of the address display number for all combinations of numbers in terms of storage capacity and processing speed. Therefore, a candidate character lattice is created by converting a candidate character of the candidate character lattice into a wildcard representing an arbitrary number. Then, if word matching is performed between the word of the address notation number represented by the wild card and the lattice of the wild card, word matching similar to town area matching can be performed on the address notation number, and the word with the correct address display number is extracted. be able to. Then, as a result of the word matching, if the numeric part of the word of the wild card that has risen to the top candidate is restored to the original number while referring to the original candidate character lattice, a correct candidate can be obtained.

The details of the first feature will be described. FIG. 6 shows candidate character lattices for the address display number area. FIG. 6A is a candidate character table storing the character codes of the candidate characters, and FIG. 6B is a penalty for each candidate character. FIG. 7 shows an example of a conversion table into a wild card. In FIG. 7, for example, arithmetic numerals are converted to "n", Chinese numerals are converted to "k", and delimiters are converted to "cho", "eye", "number", "go", "-", "|" You. All characters not used in the address number are converted to "e" as other characters.

FIG. 8 shows an example of a wildcard lattice generated using such a table. FIG. 8A shows a wild card table, and FIG. 8B shows a corresponding cost table. Here, if the same wildcard is duplicated for one entry character, only the topmost wildcard is written in the wildcard table, and the other wildcards are omitted. For example, looking at the candidate character of the entry character number 12 in FIG. 6 (a), the first, second, and fifth places each have a candidate for an arithmetic numeral. Only the card “n” is written in the corresponding location in the wild card table of FIG. Then, in the place corresponding to that of the cost table in FIG.
Write.

On the other hand, words to be collated are stored in the dictionary in an expression such as "n-chome n-ne" using a wild card. Therefore, a correct word can be obtained by generating an automaton for performing word matching from the wildcard lattice and performing matching with a word represented by a wildcard. Here, in the automaton, candidate characters and corresponding costs are assigned to each transition path between states, and the corresponding costs are accumulated while the word transitions between states. . As a result, an average cost obtained by dividing each word by the number of characters is obtained, and a word having a small cost is given as a top candidate.

FIG. 9 shows an example of an automaton. In the automaton 191, a circle indicates a state, and a number written therein indicates a state number. In addition, between the states corresponds to each entry character position of the word, and the line between the states indicates the transition path. The character on the left side of the transition path indicates that when the character is input to the automaton in a certain state, the transition to the next state follows the transition path. In addition, “other” on the transition route represents all characters other than those specified as characters corresponding to the transition route. The number in [] on the transition route is the cost that is incurred when transitioning along the route.

As an example, using an automaton 191,
Consider cost calculation when the word "n-chome n-ne" 190 is input. First, when transitioning from state 1 to state 2, a cost [0] of “n” is added, and from state 2 to state 3
, The cost [1] of “cho” is added, and the transition proceeds in the same manner. Then, after all the transitions for the number of characters of the word have been completed, the integrated cost is divided by the number of characters of the word to obtain the average cost 192 of the word.

The second feature is that an index is provided to perform word matching at high speed. In order to cope with various notation patterns of the address display number, it is necessary to register many words, but if all the words are collated, the processing time becomes enormous. Therefore, an index is provided so that unnecessary words are not collated. The three indexes are shown below.

The first index is to use the first and second candidate characters of the entry character as indexes. If the first and second candidate characters include a word character, it is highly likely that the word is a correct word. Therefore, by comparing only words including candidate characters corresponding to the first character and the second character, a correct solution can be quickly searched without collating all words. The second index is a new and old address notation flag. First, a flag relating to the new and old address notation of the town area is registered in advance in the word dictionary for town area comparison. On the other hand, a flag indicating whether the word of the wild card corresponds to the new or old address notation pattern is provided. Then, when searching for words, by comparing these flags, unnecessary word matching can be prevented. The third index is a vertical / horizontal writing flag. Flags related to vertical and horizontal writing are output when character recognition is performed. On the other hand, flags for vertical and horizontal writing are also provided for words in wildcards, and by comparing these flags, unnecessary word matching can be performed. Can be avoided.

A third feature is that when the head of the address display number area cannot be detected by the town area collation, word collation is performed at various entry character positions. First, all candidate numbers are searched from the candidate character lattice starting from the head of the address, and the positions of the entered characters including those are stored. This is because the address display number always starts with a number. Then, assuming that the searched entry character position is the head of the address display number, word matching is performed from all assumed character positions. Thus, the address display number entered at an arbitrary position can be compared.

The fourth feature is an address display number range dictionary that holds a range in which numbers can be taken in a hierarchical manner with respect to the numeric portion of the address display number. In advance, a possible range of each numerical part such as a chome, a number, and a number is hierarchically registered in a dictionary. For example, Kokubunji City has only 4 chome,
Information such as that there is only the address up to address 8 or that address 4-8 has only the address 9 is stored in a hierarchical manner. And
By comparing the candidate of the address display number restored from the wild card to the number with the dictionary, an impossible address display number can be excluded from the candidates.

The fifth characteristic is to judge whether or not the address display number input by the operator is correct using the fourth characteristic. If the correct address display number is not obtained as a result of the verification, the operator inputs the address display number while looking at the address of the mail. At that time, in order to prevent an input error, it is determined whether or not the input address display number is correct by using the address display number range dictionary.

The above five basic features can be regarded as inventions both as an apparatus and a method.

[0022]

The present invention has the following five basic functions. First, even if no correct candidate character is found in character recognition, the address display number can be recognized. In the present invention, the notation pattern of the address display number is held as a dictionary word expressed by using a wildcard representing an arbitrary number, and the matching is performed by calculating the cost of the candidate character group of the recognition result and the word and performing the matching. , Address display number can be recognized. Therefore, even if a correct candidate does not appear in a candidate character group of a part of the recognition result of the address display number, the address display number can be recognized by interpolating the correct candidate. For example, for a character pattern corresponding to “cho” in “3-chome 8-1”, even if the character “cho” does not rise as a recognition candidate, if the word corresponding to it has a small cost as a whole, “ The address number can be recognized by interpolating the "cho".

In addition, since the notation pattern of the address display number is stored in the form of a dictionary, the notation pattern can be viewed in more detail than when individual functions are prepared and processed. it can.

Second, although the address display number can be checked in detail, it is processed at high speed.
First, when a word is searched from the dictionary, the number of words to be collated can be reduced because a candidate character group corresponding to each character pattern is searched as an index. In addition, since each word has an attribute corresponding to the old and new address notation and vertical and horizontal writing, it is possible to determine in advance whether the address display number to be recognized belongs to the new or old address notation or whether it is vertical or horizontal writing. If so, unnecessary word matching can be prevented, and high-speed processing can be performed.

Third, because a dictionary system is used, when a new notation pattern is generated, it can be easily registered in the dictionary, and maintenance is easy.

Fourth, since there is an address display number range dictionary that holds a range in which numbers can be taken hierarchically for the numeric portion of the address display number, it is possible to eliminate candidates for address display numbers that cannot actually exist.

Fifth, if no address display number candidate is obtained as a result of the address display number collation, the operator can correctly input the address display number while viewing the image of the address area of the postal matter. Since the address display number range dictionary that holds the range of values that can be taken by the numerical part of the address display number in a hierarchical manner is held, it is checked whether the numerical part of the address display number entered by the operator is within the correct range. The determination can be made with reference to the address display number range dictionary. As a result of the determination, if it is determined that the value is out of the range, a warning is issued to the operator, so that an input error by the operator can be prevented.

[0028]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS A first embodiment of the present invention will be described below with reference to FIGS.
This will be described with reference to FIG.

FIG. 1 is a block diagram of the entire apparatus of the present embodiment. The mail 100 is sequentially sent to the supply unit 101. In the supply unit 101, the mail passes through a predetermined position, and an image of the surface of the mail is captured by the image input unit 102 during the passage. The address recognition unit 106 reads the address written on the surface of the mail and generates classification information. On the other hand, the postal matter on which the surface image has been captured is sent to the delay transport path 103. In the delayed transport path 103, the mail is sent for a predetermined time for generating the sorting information from the surface image.
To move. The sorting unit 104 sorts the mail according to the sorting information from the address recognition unit 106, and then sorts the mail.
5 is stored. The image input unit 102 digitizes an image signal from a photoelectric conversion element such as a line sensor, and extracts a character line of an address from an image on the surface of a mail.

The address recognition unit 106 includes a control unit 107, an image processing unit 108, a character recognition unit 109, and a knowledge processing unit 110. The control unit 107 controls the image processing unit 108, the character recognition unit 109, and the knowledge processing unit 110, respectively. Control. The knowledge processing unit 110 includes a town area matching unit 111 and an address display number matching unit 112. The town area matching unit 111 accesses the town area word dictionary 113, and the address display number matching unit 112 accesses the house display number dictionary group 114. Then, an error in the recognition result of the character recognition unit 109 is automatically corrected.

The address display number dictionary group 114 includes an address display number word index dictionary 115, an address display number word dictionary 116, and an address display number range dictionary 117. The address display number word dictionary 116 is a dictionary that stores notation patterns of blocks, and the address display number word index dictionary 115
Is a dictionary containing an index for selectively searching for necessary words from the address display number word dictionary 116.
The address display number range dictionary 117 is a dictionary in which respective ranges of the chome, block, and house display number in each address display number are hierarchically described.

FIG. 2 shows a flow of the entire process of the address recognition unit 106 in FIG. The operation of the address recognition unit 106 will be described with reference to FIG.

In step 120, the image input unit 102 captures an image of the surface of the postal matter on which the address is written, and inputs the image to the address recognition unit 106. In step 121, the image processing unit 108 extracts a destination area from the entire image on which the destination is sent from the image input unit 102. In step 122, the image processing unit 108 extracts an image for each character line from the image of the address area obtained in step 121. In step 123, the character recognition unit 109 executes step 122
After the character image is cut out for each character from the image of the character line obtained in the above, the character is recognized for each cut out character and converted into a character code. Here, as a result of character recognition, similarities corresponding to a plurality of character codes as candidates are obtained.
In addition, information on the direction of the character, that is, whether the document is written vertically or horizontally, is obtained.

In step 124, the town area matching unit 111 in the knowledge processing unit 110 generates a candidate character lattice based on the character recognition result obtained in step 123. Here, an example of the candidate character lattice is shown in FIG. For example, when the address "3-8-1 Nishi-Koigabo, Nishi-Koigabo, Kokubunji-shi, Tokyo" is written in the mailing address, the part of "Nishi-Koigabo-ku, Kokubunji-shi, Tokyo" representing the area information is displayed. It is an example of a candidate character lattice. FIG. 4A shows an example of a candidate character table in a candidate character lattice, and FIG. 4B shows an example of a cost table corresponding to the table. In the candidate character table of FIG. 4A, the first to m-th places (m is arbitrary) for each entry character number
Until, the character codes of the candidate characters are arranged. FIG.
In the cost table of FIG. 4B, the cost for the candidate character is stored at a location corresponding to the position where the character code of the candidate character table of FIG. 4A is stored. For example,
The cost of the first candidate character “East” of the entry character number 1 is “0”.

In step 125, the town area matching section 111 in the knowledge processing section 110 uses the town area word dictionary 113 to convert the candidate character lattice obtained in step 124 into town area information and town area information of the address. The corresponding new and old address notation information is extracted. As a method of extracting town area information, a method of generating an automaton from a candidate character lattice and performing word matching is known. This is described in detail in JP-A-3-125288.

Next, the structure of the town area word dictionary 113 and a method of extracting new and old address notation information corresponding to town area information will be described with reference to FIG. The town area word dictionary 113 stores words in a hierarchical manner. For example, as words at the prefecture level, Saitama 142, Tokyo 143, Kanagawa 144
There are Koganei City 145, Kokubunji City 146, and Kunitachi City 147 as words at the municipal level below Tokyo 143. Below the Kokubunji city 146 are the town level words, Hiyoshicho 148, Nishi Koigabo 149, and Higashi Koigabo 150. In addition, the town area level words include seven-digit town area division numbers 151 to 153 for identifying the town area information nationwide, and flags 154 to 156 indicating which of the new and old address expressions each town area corresponds to. Are stored together.
The flag of the new and old address notation takes a value such as 1 when the town area corresponds to the new address notation and 2 when the town area corresponds to the old address notation. Therefore, when the town area information is obtained by performing word matching hierarchically, by referring to the corresponding part of the dictionary,
A 7-digit town area division number for identifying the town area information and a flag indicating the new and old address notation in the dictionary are obtained at the same time. The seven-digit town area classification number is used to determine the possible range of the numeric part of the address display number in the subsequent processing, so that the address display number range dictionary 117 can be used.
Is used as a part of control information for sorting mails in the index for searching for mails and the sorting unit 105. The new and old address notation flags are used as an index for limiting the number of words to be collated from the address display number word dictionary in order to perform address display number collation. The town area information, the town area classification number, and the new and old address notation flags are obtained by the above-described town area collation processing in step 125.

In step 126, the address display number collating unit 112 in the knowledge processing unit 110 transmits the address display number dictionary group 1
14, the address display number is extracted from the candidate character lattice obtained in step 124. Details of step 126 will be described in detail with reference to FIGS. FIG.
Steps 132 and 135 are features of the present invention.

In step 130, step 12 in FIG.
The candidate character lattice generated in step 4 is compared with the address display number collating unit 1
Input to 12. In step 131, the head entry character number of the area in which the address display number of the candidate character lattice is written is detected. This is because the end of the area where the town area is written can be detected by the town area collation performed in step 125 of FIG. In step 132, a wildcard lattice is generated from the candidate character lattice obtained in step 130. Here, the wildcard lattice is a lattice in which numbers in the candidate character lattice are replaced with wildcards representing arbitrary numbers in order to collate the address display numbers.

The details of step 132 are shown in FIGS.
This will be described with reference to FIG. FIG. 7 shows a conversion table used to generate a wildcard lattice, which will be described in detail below.

The "number" table in the classification is a table relating to numbers representing chome, block, and house display numbers. If there are arbitrary arithmetic and kanji numeric candidate characters in the candidate character lattice, they are respectively " It is converted to wildcards “n” and “k”.

The table of "separation characters" is, for example, a table relating to the characters "chome" and "-" used to separate the numbers of the streets and the blocks when "3-chome 8-1" is present in the address. It is. Here, "Ding", "Eye",
"No.", "ground", "no", and "no" are not converted and the characters are used as they are. On the other hand, "-", "~",
"/" Is converted to a wildcard "-".

The "other" table is a table relating to characters other than the "numeric" table and the "separator" table, and all characters other than those described above are converted to a wildcard "e". That is, "others" refers to all but letters related to the street, block, and house display number.

FIG. 8 shows an example in which a wildcard lattice is generated from the candidate character lattice shown in FIG. 6 using the conversion table of FIG. Figure 8 Wildcard Lattice
It consists of a wild card table shown in FIG. 8A and a cost table shown in FIG.

The generation of the wild card lattice shown in FIG.
This is performed from the candidate character table in the candidate character table shown in FIG. First, the first candidate character is converted into a wild card and written in the first place of the wild card table shown in FIG. At the same time, the cost corresponding to the converted candidate character is written in a corresponding location in the cost table of FIG.

Next, the second-order candidate character is examined, and if it belongs to the same wildcard as the first-order candidate character, it is omitted because it overlaps. If they belong to different wildcards, the costs corresponding to the wildcards are written in the wildcard table of FIG. 8A and the cost table of FIG. 8B, respectively. Hereinafter, the same is repeated for all the candidate characters.

For example, consider the conversion of the column of the entry character number 12 in the candidate character table of FIG. First, the first
The place candidate character “8” is converted to a wild card “n” and written in the first place of the entry character number 12 in the wild card table of FIG. At the same time,
The cost “0” corresponding to the candidate character “8” is written in a corresponding location in the cost table shown in FIG.

[0047] Looking at the second place candidate character "3" because belong to the same wild card "n", do not write anything in the wild card table of FIG. 8 are omitted (a). Further, looking at the third place, the candidate character "day" belongs to a wild card "e" different from "n", so that the candidate character "day" is placed in the empty second place in the wild card table of FIG. 8 (a). Write. At the same time, the cost “2” of the candidate character “day” is written in the corresponding location in the cost table of FIG. Hereinafter, the same processing is performed for candidate characters of all ranks.

By the processing of step 132, a wildcard lattice is generated from the candidate character lattice obtained in step 130.

In step 133, an automaton for performing word matching is generated from the wildcard lattice generated in step 132. Details of step 133 will be described with reference to FIG.

FIG. 9 shows a process of extracting words from the dictionary and collating the address display number words using an automaton. First, the automaton 191 will be described. A finite automaton 191 is generated from the wildcard lattice shown in FIG. 8 in order to match the dictionary word representing the address display number pattern with the wildcard lattice. Then, the automaton 191 sequentially inputs dictionary words represented as character strings, and calculates the average cost of the words.

In the automaton 191, a circle indicates a state, and a number written therein indicates a state number. In addition, between states correspond to each character position of the word,
The lines between the states indicate the transition paths. The character on the left side of the transition path indicates that when the character is input to the automaton in a certain state, the transition to the next state follows the transition path. In addition, “other” on the transition route represents all characters other than those specified as characters corresponding to the transition route.
The number in [] on the transition route is the cost that is incurred when transitioning along the route.

As an example, using an automaton 191,
Consider cost calculation when the word "n-chome n-ne" 190 is input. First, when transitioning from state 1 to state 2, a cost [0] of “n” is added, and from state 2 to state 3
, The cost [1] of “cho” is added, and the transition proceeds in the same manner. Then, after all the transitions for the number of characters of the word have been completed, the integrated cost is divided by the number of characters of the word to obtain the average cost 192 of the word.

Next, generation of the finite state automaton 191 from the wild card lattice shown in FIG. 8 will be described. First, a transition path between the state 1 and the state 2 of the automaton 191 in FIG. 9 is generated, and candidate characters of the character number 12 in the wildcard table in FIG. At the same time, the costs in the cost table shown in FIG. 8B corresponding to the candidate characters are similarly allocated to the transition paths between the state 1 and the state 2, respectively. Next, “other” is generated as a transition path representing all characters other than the specified ones, and the cost is set to 15. Hereinafter, states and transition paths are similarly generated one after another from the wild card lattice.
Here, the cost of the transition route does not necessarily have to be the above value, and may be an arbitrary number.

By the processing of the above step 133, the automaton 191 is generated from the wild card lattice.

In step 134, the automaton matching of the address display number word is performed using the automaton 191 generated in step 133 and the address display number word index dictionary 115 and the address display number word dictionary 116 in FIG.
Details of step 134 will be described with reference to FIGS. 8, 9, 10, and 11. FIG. 10 is a PAD showing the flow of the automaton matching process. FIG. 11 is a diagram showing a configuration of an address display number word dictionary and an address display number word index dictionary.

First, the configuration of the dictionary shown in FIG. 11 will be described. The address display number word dictionary 116 uses a wildcard to represent a word representing a notation pattern of a chome, a block, a house display number,
And a dictionary storing the search information and attributes. The words representing the notation pattern of the street, block, and house display number are, for example, “n-chome n-ne”, “n | n | ne”
Etc. are stored. The address display number word index dictionary 115 is a dictionary that stores an index for selectively searching words necessary for matching from the address display number word dictionary. The index is the first dictionary word
The first and second characters are used.

The address display number word dictionary 116 stores a word 228 representing a notation pattern of a block, a relative address 229 between words having the same character as the second character of the word, a flag 230 indicating a new and old address notation, and a vertical and horizontal writing. Flag 231 shown in FIG.

The flag 230 indicating the new and old address notation corresponds to 1 if the word representing the block notation is a new address notation pattern, and 2 if the word is the old address notation pattern. The number "3" is stored. In the flag 231 indicating vertical and horizontal writing, numbers 1 are stored if the word representing the block notation belongs to horizontal writing, 2 if the word belongs to vertical writing, and 3 if the word belongs to both vertical and horizontal writing.

Address display number word index dictionary 115
Consists of two tables, a first character index table 220 and a second character index table 224.
The first character index table 220 includes a table 221 storing the character numbers of the first characters of the dictionary words, the number 222 of words having the same first character, and a pointer table 223 to the address display number word dictionary 116. Similarly, the second character index table 224 stores a character number of the second character of the dictionary word 225, the number of words having the same second character 226, and the address display number word dictionary 11
6 is a pointer table 227.

Next, the flow of processing when searching for a word in the address display number word dictionary 116 using the address display number word index dictionary 115 will be described. An arrow represented by a solid line indicates a search flow when searching for a word in which the first character is the same character using the first character index table 220. An arrow represented by a dotted line indicates a search flow when searching for a word in which the second character is the same character using the second character index table 224.

For example, when a word whose first character is “n” is searched from the dictionary, the number of words whose first character in the first character index table 220 is the same character is determined.
Reference is made to m1 and the pointer P1 (1) of "n". Since the pointer P1 (1) stores the first pointer of a word whose first character starts with "n" in the address display number word dictionary, the word is referred to. In the word dictionary, words with the same first letter are arranged consecutively, so if you find the first word that starts with "n", you can search for words one after another simply by incrementing the pointer. it can. Then, if the search is performed m1 times, the word beginning with “n” ends, so the word search is terminated there.

The same applies to a case where a search is performed using the second character of a word as an index. For example, when searching a dictionary for a word whose second character is “cho”, the number q1 of words whose first character is the same character in the second character index table 224 and a pointer to “cho” Refer to P2 (1). As the pointer P2 (1) stores a pointer to a word whose second character is "cho" in the address display number word dictionary, the word is referred to. Thereafter, by shifting the pointer with reference to the relative address 229 between words having the same character as the second character of the word, it is possible to search for a word with the same second character, "cho". Then, when the search is performed q1 times, the second character is the end of the word of the same “cho”, so the search for the word is ended there.

Here, it is known whether the address is written vertically or horizontally by character extraction and character recognition in step 123 in FIG. 2. Therefore, by referring to the flag 231 indicating vertical and horizontal writing, it is possible to select from among the searched words. The corresponding words can be narrowed down and extracted.

Further, since it is known in the town area collation in step 125 of FIG. 2 that the address display number belongs to the new or old address notation, the flag 230 indicating the new and old address notation is referred to, and The corresponding word can be narrowed down and extracted from the list.

Next, the specific processing content of step 134 will be described with reference to the processing flow of FIG. 10 and FIGS. 8, 9 and 11.

In step 200, a flag indicating vertical and horizontal writing of the address obtained in step 123 in FIG. 2 and a flag indicating new and old address notation obtained in step 125 are set for the address to be verified. In step 202, the first candidate character of the entry character number 12 in the wild card table of FIG.
With reference to the character index table 220, the dictionary word number 222 and the word dictionary pointer 223 are acquired. In step 204, the word pointed to by the pointer is searched, and whether the word is inconsistent with the old and new address notation flag and the vertical / horizontal writing flag set in step 200 is referred to the corresponding tables 230 and 231 of the dictionary. Check. If there is no contradiction, go to step 205. In step 205, the searched word is input to the automaton 191 in FIG. 9, and the average cost is calculated while changing the state. In step 203, step 204
From step 205 to the number of dictionary words obtained in step 202.

In step 201, a candidate character of the next rank after the entry character address 12 in FIG. 8A is extracted, and the processing from step 202 to step 205 is performed.
Is repeated several times. In step 207, FIG.
The first candidate character of the entry character number 13 in the wildcard table (a) is extracted, and the number of dictionary words 226 and the pointer 227 of the word dictionary are acquired with reference to the second character index table 224 in FIG. . Step 2
At step 09, the word pointed to by the pointer is searched, and it is checked by referring to the corresponding table of the dictionary whether this word is inconsistent with the old and new address notation flag and the vertical and horizontal writing flag set at step 200. If there is no contradiction, go to step 210.

In step 210, the searched word is entered in FIG.
To the automaton 191 to calculate the average cost while changing the state. In step 208, the processes in steps 209 to 210 are repeated by the number of dictionary words obtained in step 207. In step 206, the candidate character of the next rank after the entry character address 13 in FIG. 8A is extracted, and the processing from step 207 to step 210 is repeated the number of times of the candidate character of the entry character address 13.

In step 211, the words obtained in steps 200 to 210 and their costs are rearranged in ascending order. In step 212, the top L (L> 1) words selected in step 211 are selected.

The above steps 200 to 212
The automaton matching in step 134 in FIG. 3 is performed by the processing of (1), and the top L words with low average costs and their costs are obtained.

In step 135, for the words represented by the upper L wildcards obtained in step 134, the wildcards representing the numbers “n” and “k” are restored to the original numbers, and candidates are determined. Generate. Here, FIG. 12 shows the result of restoring the word “n-chome n-ne” 190 in FIG. The process of restoring numbers is as shown in FIG.
And the word "n-chomenn" shown in FIG.
190 is performed. Then, the candidate number of the place corresponding to the number "n" and its cost are shown in FIG.
(a) Extract from the candidate character table and generate actual streets and blocks. In addition, the cost corresponding to the number is extracted from the cost table in FIG. 6B, and the cost for the restored address display number word is accumulated.

At step 136, the address display number word candidates restored to the numbers at step 135 are
It is determined whether or not the numeric part of the block and house display numbers is consistent with the address display number range dictionary 117 of FIG. Here, the address display number range dictionary 117 is a dictionary that hierarchically stores, for each town area, range information as to which ranges of the numbers of the chome, the block, and the house display number can take. Details of the address display number range dictionary 117 will be described with reference to FIG.

The address display number range dictionary 117 includes an index table 260 and an address display number range table 263.
Consists of The index table 260 includes a town area division number table 261 for identifying a town area, and a pointer table 262 to an address display number range table 263.
The address display number range table 263 includes a street table 264 storing street numbers as indexes and a street table 265 storing street numbers as indexes.
It consists of a house display number table 266 which stores the maximum value of house display numbers.

Next, the flow of processing when referring to the address display number range will be described. For example, to refer to the address display number range of “Nishi-Koigabo, Kokubunji-shi, Tokyo”, first, in step 125 of FIG. 2, use “Nishi-Koigabo, Kokubunji-shi, Tokyo” obtained using the town area word dictionary shown in FIG. Index table 2 for the town area division number "1850002"
The 60 area division number table 261 is referred to. "18
In the address display number range table 263, the pointer Pa corresponding to “50002” is “Nishi-Koigabo, Kokubunji-shi, Tokyo”.
Refers to the beginning of the area where the range data is stored. In this area, the maximum value of the house display number is stored in the house display number table 266 using the chome table 264 and the block table 265 as indexes. Therefore, by searching for the corresponding chome and block index, for example, the maximum value of the house display number of “3 chome 8” is 9
By searching all areas of "Nishi-Koigabo, Kokubunji-shi, Tokyo", it can be seen that the maximum value of the street is only up to 4. For example, assuming that there is only 4-chome of “Nishi-Koigaboku, Kokubunji-shi, Tokyo”, and that the address of 3-chome is only up to the house display number 5, the candidate group in FIG. 12 is narrowed down to the candidates shown in FIG. Through the processing in step 136 described above, the range of each street, block, and house display number of the address display number is determined, and the candidates determined to be out of the range are deleted from the candidate group in FIG.

Here, the address display number range dictionary is not limited to this embodiment. For example, the house display number portion may have not only the upper limit but also the lower limit. Alternatively, all of the house display numbers actually subject to mail delivery, excluding the house display number of the parking lot, may be registered.

At step 137, from the candidates narrowed down at step 136, P (P> 1) candidates with a low cost are selected as address display number collation results. Here, P
= 2, "3-chome 8-1" and "3-chome 3-
"1" is selected as the matching result.

The above steps 130 to 137
Through the processing up to step 127, the address display number collation is performed in step 127 in FIG.
8-1 "and" 3-3-1 "are obtained.

In step 127, the town area candidate “Nishi-Koigabo, Kokubunji-shi, Tokyo” obtained by the town area verification in step 125
And the address display number candidates "3-chome 8-1" and "3-chome 3-1" obtained by the address display number collation in step 126 are connected to generate an address candidate. In this example, "3-3-1 Nishi-Koigabo, Kokubunji-shi, Tokyo" and "3-1-3-1 Nishi-Koigabo, Kokubunji-shi, Tokyo" are obtained. Further, control information for controlling the sorting unit 104 in FIG. 1 is generated using the address information.

A second embodiment of the present invention will be described with reference to FIGS. 1, 2, 9 and 15. Here, it is assumed that the town area information is not obtained by the town area verification when the seven-digit town area classification number is printed on the address.

In FIG. 2, the same processing as in the first embodiment is performed in steps 120 to 122.

In step 123, as in the first embodiment, the character recognizing unit 109 recognizes each character from the image of the character line obtained in step 122 and converts it into a character code. However, here, not only the address information but also the town area classification number printed on the address is recognized and converted into a character code. In step 124, the town area matching unit 111 generates a candidate character lattice based on the character recognition result obtained in step 123, as in the first embodiment. In step 125, the town area matching unit 111 performs town area matching using the town area word dictionary 113 as in the first embodiment. However, in this embodiment, it is assumed that as a result of the town area comparison, the town area information and the old and new address notation information corresponding to the town area information cannot be extracted. In step 126, the address display number collating unit 112 in the knowledge processing unit 110 of FIG.
4, an address display number is extracted from the candidate character lattice obtained in step 124. Details of step 126 will be described in detail with reference to FIGS. In FIG. 15, steps 302 and 304 are features of the present invention.

In step 300, step 12 in FIG.
The candidate character lattice generated in step 4 is input.

In step 301, a wildcard lattice is generated from the candidate character lattice obtained in step 130 in the same manner as in the first embodiment. However, since the head of the address display number cannot be detected because the town area information cannot be obtained, the wild card lattice is generated from the head of the address. In step 302, all the entry character numbers including candidate numbers are detected from the wild card lattice. That is, "n" or "k" in the wildcard table
To extract the entry character number containing. In step 303, the character number 1 is entered from the wild card lattice generated in step 301 in the same manner as in the first embodiment.
Generates an automaton for performing word matching from. Then, for example, it is assumed that the automaton 191 of FIG. 9 is obtained. Here, only the automaton in the address display number portion is displayed.

In step 304, the automaton matching of the address display number word is performed using the automaton 191 generated in step 303, the address display number word index dictionary 115 and the address display number word dictionary 116 in FIG.
However, the point different from the method of the first embodiment is that when the number of states of the generated automaton is K (K> 1), the cut is performed at K cut points and the rear partial automaton starting from each cut point is That is, the word matching of the first embodiment is performed.
For example, in FIG. 9, word matching was performed for the automaton starting from state number 1,
Similar word matching is performed for the automaton starting from 3,. Thereby, a word existing at an arbitrary position can be extracted. When a word is selected from the dictionary, the attribute of the new and old address notation cannot be obtained in step 125 of FIG. 2, so the word is selected without looking at the flag of the new and old address notation in the dictionary.

In step 305, the upper L (L> L) obtained in step 304 is obtained in the same manner as in the first embodiment.
1) For words represented by wildcards,
Wildcards representing the numbers “n” and “k” are restored to the original numbers, and address display number candidates are generated.

At step 306, P candidates having a low cost are selected as address display number comparison results from the candidates generated at step 305 in the same manner as in the first embodiment. Through the processing from step 300 to step 306, the address display number collation in step 126 in FIG. 2 is performed.

At step 127, control information for controlling the section 104 of FIG. 1 is generated by combining the town area section number obtained at step 123 and the address display number obtained at step 126.

As described above, the processing from step 120 to step 127 makes it possible to obtain control information for controlling the sorting section 104 even when the head of the address display number area is not found by the town area verification.

A third embodiment of the present invention will be described with reference to FIGS. 2, 16, 17, and 18.

In FIG. 16, the features of the present invention are an unread correction unit 310 and an address display number range dictionary 117. FIG.
The operation of this device will be described with reference to FIG.

Steps 340 to 345 correspond to steps 120 to 1 in FIG. 2 in the first embodiment.
The same processing is performed for each of up to 25. Step 346
Then, the address display number collation is performed in the same manner as in the first embodiment. However, it is assumed that no candidate is obtained as a result of the matching. In step 347, the control unit 107 in FIG.
Is sent, and the address display number is input by the operator in the unread character correcting unit 310. FIG. 18 is an example of a display screen for an input operation. 360 is FIG.
Is an address image of a postal matter captured by the image input unit 102 of FIG. Numeral 361 indicates the result of the knowledge processing unit 110. Since there is no candidate for the address display number, the part corresponding to the numerical value is “?”.
Indicated by Reference numerals 362, 363, and 364 denote frames for the operator to input numerical values of the street number, the block, and the house display number in the address display numbers. Here, the knowledge processing unit 110 uses the address display number range dictionary 117 to determine whether the value entered by the operator is within a correct range. If the result of the determination is that the value is outside the range, the operator is informed of that. The address display number is input by the processing in step 347 described above.

In step 348, the address candidate is generated by combining the town area information obtained in step 345 and the address display number input in step 346. As described above, by the processing from step 340 to step 348, even if no candidate is obtained in the address display number collation, the operator can input the correct address display number with the assistance of the device, and the correct address can be obtained.

In the above embodiment, the example of the address display number has been described using the new address notation, but the same processing is applied to the address display number of the old address notation.

[0094]

The present invention has the following five effects. First, even if no correct candidate character is found in character recognition, the address display number can be recognized. In the present invention, the notation pattern of the address display number is held as a dictionary word expressed by using a wildcard representing an arbitrary number, and the matching is performed by calculating the cost of the candidate character group of the recognition result and the word and performing the matching. , Address display number can be recognized. Therefore, even if a correct candidate does not appear in a candidate character group of a part of the recognition result of the address display number, the address display number can be recognized by interpolating the correct candidate. For example, for a character pattern corresponding to “cho” in “3-chome 8-1”, even if the character “cho” does not rise as a recognition candidate, if the word corresponding to it has a small cost as a whole, “ The address number can be recognized by interpolating the "cho".

In addition, since the notation pattern of the address display number is stored in the form of a dictionary, it is possible to see the notation pattern in more detail than to prepare and process individual functions. it can.

Second, although the address display number can be checked in detail, it is processed at high speed.
First, when a word is searched from the dictionary, the number of words to be collated can be reduced because a candidate character group corresponding to each character pattern is searched as an index. In addition, since each word has an attribute corresponding to the old and new address notation and vertical and horizontal writing, it is possible to determine in advance whether the address display number to be recognized belongs to the new or old address notation or whether it is vertical or horizontal writing. If so, unnecessary word matching can be prevented, and high-speed processing can be performed.

Third, since the dictionary system is used, when a new writing pattern is generated, it can be easily registered in the dictionary, and maintenance is easy.

Fourthly, since there is an address display number range dictionary that holds a range in which numbers can be taken in a hierarchical manner with respect to the numeric portion of the address display number, it is possible to eliminate address display number candidates that cannot actually exist.

Fifth, if the address display number candidate is not obtained as a result of the address display number collation, the operator can correctly input the address display number while looking at the image of the address area of the postal matter. Since the address display number range dictionary that holds the range of values that can be taken by the numerical part of the address display number in a hierarchical manner is held, it is checked whether the numerical part of the address display number entered by the operator is within the correct range. The determination can be made with reference to the address display number range dictionary. As a result of the determination, if it is determined that the value is out of the range, a warning is issued to the operator, so that an input error by the operator can be prevented.

[0100]

[Brief description of the drawings]

FIG. 1 is an overall configuration diagram of an apparatus according to a first embodiment of the present invention.

FIG. 2 is a diagram showing a flow of an entire process of the apparatus according to the first embodiment of the present invention.

FIG. 3 is a diagram showing a flow of a process of performing address display number collation.

FIG. 4 is a diagram showing an example of a candidate character lattice for performing town area matching.

FIG. 5 is a diagram showing an example of the configuration of a town area dictionary storing town area information.

FIG. 6 is a diagram illustrating an example of a candidate character lattice in an address display number area.

FIG. 7 is a diagram showing a conversion table for generating a wildcard lattice for performing address display number collation from a candidate character lattice.

8 is a diagram illustrating an example of a wildcard lattice generated from the candidate character lattice of FIG. 6 using the conversion table of FIG. 7;

FIG. 9 is a diagram illustrating an outline of processing of automaton word matching.

FIG. 10 is a flowchart showing a process flow of the automaton word matching.
AD.

FIG. 11 is a diagram showing a configuration of an address display number word index dictionary and an address display number word dictionary.

FIG. 12 is a diagram showing an example of an address display number candidate obtained by restoring a number portion from an address display number word as a result of the comparison;

FIG. 13 is a diagram showing an example of the configuration of an address display number range dictionary.

14 is a diagram showing candidates remaining after judging a possible range for each numeral portion from the candidates for the address display number in FIG. 12;

FIG. 15 is a diagram showing a flow of an address display number collating process in the second embodiment of the present invention.

FIG. 16 is an overall configuration diagram of an apparatus according to a third embodiment of the present invention.

FIG. 17 is a diagram showing a flow of an entire process according to a third embodiment of the present invention.

FIG. 18 is a diagram showing a display example of a screen for inputting an unread address display number.

[Explanation of symbols]

100: mail, 101: mail supply unit, 102: image input unit, 103: delay transport unit, 104: sorting unit, 105
... Segment shelf, 106 ... Address recognition unit, 107 ... Control unit, 10
8 Image processing unit, 109 Character recognition unit, 110 Knowledge processing unit, 111 Town area collation unit, 112 Address display number collation unit, 113 Town word dictionary, 114 Address display number dictionary group, 115 Address display number word index dictionary, 11
6 ... Address display number word dictionary, 117 ... Address display number range dictionary.

──────────────────────────────────────────────────続 き Continued on the front page (72) Inventor Masafumi Koga 1-280 Higashi Koikekubo, Kokubunji-shi, Tokyo Inside the Central Research Laboratory, Hitachi, Ltd. (72) Tatsuhiko Kagehiro 1-280 Higashi Koikekubo, Kokubunji-shi, Tokyo Hitachi, Ltd. Inside the Central Research Laboratory (72) Inventor Masato Teramoto 1st Ikegami, Haruoka-cho, Owariasahi-shi, Aichi Prefecture Inside Office Systems Division, Hitachi, Ltd. In System Division (72) Inventor Hiromichi Fujisawa 1-280 Higashi Koigakubo, Kokubunji-shi, Tokyo Inside Central Research Laboratory, Hitachi, Ltd. (56) References JP-A-6-124366 (JP, A) JP-A-5-169033 ( JP, A) (58) Fields investigated (Int. Cl. ⁷ , DB name) B07C 3/00- 3/20 G06K 9/62 620

Claims (7)

(57) [Claims] An address reading device for detecting character information on a postal matter and reading address information comprising street name information and address display number information, wherein an image on the postal matter is converted into a digital signal and inputted. Input means, character recognition means for extracting and recognizing character information from an image input from the image input means, and outputting a recognition candidate character group for each of the cut character patterns; and a town storing town area name information. An area name dictionary, a town area name matching means for recognizing a town area name by matching the recognition candidate character group output from the character recognition means with the town area name dictionary, and an address display based on the recognition result of the town area name matching means. Address display number area detecting means for detecting a number area; and a code corresponding to each character pattern in the address display number area based on an output from the address display number area detecting means. Conversion means for replacing a number in a character group with a specific symbol representing an arbitrary number, and converting a character separating the numbers into a candidate character group which remains as it is, the specific symbol and address display number information An address display number notation pattern dictionary that holds various notation patterns of address display numbers expressed by characters that separate the numbers inside, an output result of the conversion unit, and a notation pattern of the address display number notation pattern dictionary. A notation pattern matching unit that outputs a candidate for a notation pattern of an address display number; comparing an output result of the notation pattern matching unit with a candidate character group output from the character recognition unit; Address restoring means for restoring numbers in a candidate character group replaced by symbols and outputting a character string candidate for an address display number; Take apparatus. 2. The address reading device according to claim 1, wherein the town area name dictionary includes, in addition to the town area name information, a town area name classification number for identifying the town area name, and whether the town area name is a new address notation. The address book reading device, which detects whether the character group representing the address information on the postal matter is written vertically or horizontally. Address notation discriminating means for discriminating whether the town name is a new address notation or an old address notation based on the recognition result of the town name matching means and the town name dictionary; An address display number notation pattern dictionary having attributes related to notation and vertical and horizontal writing, and the notation pattern matching means includes a candidate character group of each character pattern at an arbitrary position replaced with the specific symbol. On the other hand, a notation pattern search means for searching a notation pattern from a house display number notation pattern dictionary using a character code of the candidate character group as an index; Writing pattern selecting means for reading only writing patterns whose attributes of new and old address writing and vertical and horizontal writing match from the house display number writing pattern dictionary from the writing patterns searched by the search means. Address reading device. 3. The address reading device according to claim 1, wherein if the head of the address display number area cannot be detected based on the recognition result of the town area name matching means, a numeral is included in the recognition candidate character group. And a head assuming means for assuming an arbitrary character pattern including the candidate of the address as the head of the address display number area and outputting the position of the character pattern. Based on the position assumed to be the head of the address display number area, the output result of the conversion means is compared with the notation pattern of the house display number notation pattern dictionary, and the candidate of the address display number notation pattern is output. Characteristic address reading device. 4. The address reading device according to claim 1, wherein, for a character string candidate of an address display number output from said numeral restoring means, a value of a numerical part of the address display number is determined by referring to an address display number range dictionary. Judge whether it is within the range,
An address reading device comprising address display number range determining means for narrowing down candidates based on a result of the determination. 5. An address reading device according to claim 4, wherein, when a character string candidate of an address display number is not obtained as an output result of said numeral restoring means, an operator looks at an image of a mail address area. A display device for inputting an address display number while inputting, and a range determining means for determining whether a numerical part of the address display number input by the operator is within a correct range by referring to the address display number range dictionary. Means for alerting an operator if the result of the determination is that the address is out of the range. 6. A method of detecting character information on a postal matter and reading address information comprising street name information and address display number information, wherein the image on the postal matter is converted into a digital signal and inputted. Character information is cut out from the input image and recognized, a recognition candidate character group is output for each of the cut character patterns, and the recognition candidate character group is compared with a town name dictionary storing town name information. The address display number area is detected based on the recognized town area name, and the numbers in the candidate character group corresponding to each character pattern of the detected address display number area are replaced with an arbitrary number. The characters replaced by the specific symbol that represents the character and the characters that separate the numbers from each other are converted into a group of candidate characters left as they are, and the group of candidate characters replaced by the specific symbol, the specific symbol, and the address display number information Collating the in numeric location number notation pattern dictionary which holds the various representation pattern of location numbers expressed in a character that separates between the each other, outputs the candidate notation pattern of location numbers, is the output Comparing the notation pattern candidate with the recognition candidate character group, restoring numbers in the candidate character group replaced with the specific symbol, and outputting a character string candidate for an address display number. Address reading method. 7. An address reading device for detecting character information on a mail and reading address information comprising street name information and address display number information, wherein an image on the mail is converted into a digital signal and inputted. Input means; character recognition means for extracting and recognizing character information from the image input from the image input means; and outputting a recognition candidate character group for each of the cut character patterns; and a town storing town area name information. An area name dictionary, a town area name matching means for recognizing a town area name by matching the recognition candidate character group output from the character recognition means with the town area name dictionary, and an address display based on the recognition result of the town area name matching means. Address display number area detecting means for detecting a number area; and a code corresponding to each character pattern in the address display number area based on an output from the address display number area detecting means. The numbers in the character group, and converting means for converting the candidate character group is replaced by a specific symbol indicating any number, between the numbers each other in the specific symbol and location number information
An address display number notation pattern dictionary holding various notation patterns of address display numbers expressed by delimiting characters, and comparing the output result of the conversion means with the notation pattern of the address display number notation pattern dictionary, A notation pattern matching unit for outputting a notation pattern candidate, and comparing the output result of the notation pattern matching unit with a candidate character group output from the character recognition unit, and replacing the candidate character with the specific symbol. Digit restoring means for restoring the numbers in the group and outputting a character string candidate for the address display number; and for the character string candidates for the address display number output from the number restoring means, refer to the address display number range dictionary for numerical values. Judge whether the value of the part is within the range of the address display number,
Address display number range determining means for narrowing down candidates based on the result of the determination; and, when a character string candidate for the address display number is not obtained as an output result of the numeral restoring means, an operator displays an image of a mailing address area. A display device for inputting an address display number while watching the display, and a range determining means for determining whether a numerical part of the address display number input by the operator is within a correct range by referring to the address display number range dictionary. A means for alerting an operator if the result of the determination is that the address is out of the range.