Method of reading characters and method of reading postal addresses

[0002] 1. Field of the Invention

[0003] The present invention relates to a method of reading characters, and more particularly to a method of reading character strings, particularly hand-written character strings including Kanji characters of postal addresses written on the surface of mail pieces.

[0004] 2. Description of the Prior Art

[0005] For the automatic reading of a character string of postal address written on the surface of a mail piece or the like, the image of the mail surface is first converted into an electrical signal, and then the region where the character string is written is detected. Subsequently, based on the video signal of the detected region, characters of the character string are classified. Each character of the character string is classified by the following procedure.

[0006] (1) Image patterns which deem to be characters of a character string are extracted by segmentation:(character segmentation).

[0007] (2) Character species (character codes) of the segmented character patterns are classified:(character classification).

[0008] (3) A character string formed by connecting the classified character species is compared with character strings of postal addresses or the like registered in a table (character string dictionary) thereby to recognize the character string as a certain address or the like: (character string matching).

[0009] Among the above-mentioned processes, the character segmentation of item (1) is most difficult due to a variety of cases of written surfaces including hand-written characters, characters of Kanji in which one character can be made up of multiple other characters, and character strings written in either a vertical or horizontal form, as will be explained later in connection with FIG. 1 and FIG. 34A.

[0010] In regard to the conventional scheme of character segmentation for a character string read out of a written surface, the over segmentation approach is known to be effective. In the over segmentation approach, the image signal of a character string is separated into multiple character patterns having the possibility as characters, each separated character pattern is classified in terms of character (character species), and the character patterns are determined to be correct based on the similarity of the classified character species of character pattern and the comparison of the string of character species with character strings in a reference dictionary.

[0011] As a specific example of the prior art regarding the over segmentation approach, there has been proposed the scheme of the testing of recognition-candidate characters based on character classification by Fujimawa, et al. (described in The Proceeding of The 1984 Institute IEIC Fall Conference “An Augmented Segmentation Algorithm for Connected Handwritten Numerals”).

[0012] Another scheme of the testing of recognition-candidate character patterns based on the shape of characters has been proposed by Ishidera, et al. (described in The Proceeding of The 1995 Institute IEIC Spring Conference D-576 “A Segmentation Method of Address Recognition”).

[0013] Schemes of the testing of the assumption based on character classification and character string comparison have been proposed by Murase, et al. (described in The Transaction of the Institute of Electronics, Information and Communication Engineers, (D) Vol.J69-D, No.9 “Segmentation and Recognition of Hand-written Character String Using Linguistic Information”), and by ooi (described in the TECHNICAL REPORT OF IECE PRU 92-40 “A Method to Recognize the Street Number Portion of an Address”).

[0014] A scheme of the assessment of correctness of character segmentation based on the character width, character pitch and character spacing is described in The Transaction of the Institute of Electronics, Information and Communication Engineers, REPORT OF IECE (D) J68-D, No.12, pp.2123-2131. Also known is a scheme of the assessment of correctness of character segmentation based on the character pattern and information on the similarity of character species as described in The Transaction of the Institute of Electronics, Information and Communication Engineers, REPORT OF IECE (D) J68-D, No.4, pp.765-772.

[0015] However, the above-mentioned prior art schemes of over segmentation approach encounter the difficulty of correct character segmentation, as will be shown for some examples in the following.

[0016] In FIG. 1 showing a postal address 101 hand-written on a mail piece, a street number portion 102 is visually recognized to be Kanji-numerals “--”. In this case, a character reading apparatus based on the above-mentioned over segmentation approach implements the character pattern segmentation for the region 102 at boundaries shown by the dashed lines. Namely, the vertical and horizontal lengths and vertical/horizontal length ratio of character patterns vary significantly depending on individual character species, and therefore it is difficult to select a correct character string out of six possible cases 103.

[0017] FIG. 33A shows a hand-written character string with large character spacings. This character string is segmented at boundaries shown by the dashed lines, resulting in recognition-candidate character patterns as shown in FIG. 34A. In the figure, the relationship of the candidate patterns is expressed graphically in terms of nodes that represent boundaries of character patterns and arcs that represent character patterns, and it is called a “segmentation hypothesis network”.

[0018] Correct segmentation of character patterns based on the above-mentioned over segmentation approach is carried out by the process of finding the optimal path from the starting node {circle around (0)} to the ending node {circle around (9)} on the segmentation hypothesis network. The character patterns represented by the arcs in FIG. 34A are classified in terms of their character species. In this case any of “”, “”, and “” indicates a high similarity, and therefore it is difficult for the prior art schemes to segment the character string.

[0019] Among the above-mentioned prior art schemes, the one proposed by Fujisawa, et al. and the one proposed by Ishidera, et al. is designed to judge the legitimacy of each character pattern, but it does not use the relation with neighboring character patterns, and the ones proposed by Ooi and Murase use the relation with neighboring character patterns for the matching of character strings, but these schemes do not use information of the relative feature values of neighboring characters such as the spacings.

[0020] Accordingly, it is a primary object of the present invention to accomplish a character reading method based on the determination of correct character patterns from a string of segmented character patterns and the accurate classification of the character patterns.

[0021] Another object of the present invention is to accomplish a method of accurate reading of characters of postal address from the video signal of an address character string which consists of a town name portion and street number portion written on the mail surface.

[0022] Still another object of the present invention is to accomplish, for the reading of address character string based on the over segmentation approach, a method of accurate character pattern segmentation by use of the relative feature values of the pattern in attention and neighboring patterns for an address character string for which candidate character patterns segmented cannot be tested correctly based solely on character classification and character string matching.

[0023] In order to achieve the above objectives, the inventive character reading method comprises:

[0024] a first step of combining connected components (e.g., strokes formed of consecutive black pixels) in a character string to be classified which has been imaged electronically by means of an image input device thereby to segment the character string into character patterns having the possibility as characters (a segmented character pattern which is not yet classified will be called “tentative character pattern” hereinafter);

[0025] a second step of implementing the character classification for the tentative character patterns by making reference to a character classification dictionary thereby to obtain subordinate information (recognition-candidate characters and similarity of tentative character patterns and recognition-candidate characters) for the tentative character patterns;

[0026] a third step of obtaining border information for the tentative character patterns;

[0027] a fourth step of obtaining the credibility of the border information of the tentative character patterns obtained in the third step by making reference to a segmentation dictionary which contains border information by use of the recognition-candidate characters obtained in the second step as the key, and applying weights to the tentative character patterns;

[0028] a fifth step of determining the character segmentation in accordance with the weights of the tentative character patterns; and

[0029] a sixth step of implementing the word-wise matching by use of the character classification dictionary for a set of classified character species produced from the tentative character patterns determined in the fifth step, and identifying the characters of the character string.

[0030] In the case of using this character reading method to read a character string of postal address which consists of a town name portion and street number portion, the image of the character string is converted into an electrical signal, the character string region is extracted from the electrical image information, and the connected components of the character string segmented in the above-mentioned first step are combined thereby to produce several tentative character patterns.

[0031] Each of the tentative character patterns undergoes the character classification by use of the character classification dictionary thereby to obtain information of candidate characters that resemble the tentative character patterns. The town name portion of address is read by use of the information of candidate characters and by making reference to a town name dictionary, and the head position of the street number portion is detected. The town name dictionary contains all town names existing.

[0032] Upon detecting the head position of the street number portion, the border information of the tentative character patterns of the street number is obtained, and the credibility of the border information is obtained by making reference to the character segmentation dictionary. Character segmentation of the tentative character patterns for the characters of the street number portion is implemented again in consideration of the credibility, and the characters of the street number portion is identified by using the information of candidate characters that resemble the resulting tentative character patterns and by making reference to the street number dictionary. The street number dictionary contains all character information of street numbers existing.

[0033] According to another preferred form of this invention, the border information of the above-mentioned third step is the external form penalty which is based on the relative feature values of each tentative character pattern with respect to neighboring character patterns at the occurrence of each conceivable type of error for the assessment of the legitimacy of the assumption that each tentative character pattern segmented has resulted from incorrect segmentation of the error type.

[0034] As described above, the inventive character reading method is based on the scheme of character string segmentation in which the similarity obtained by character classification reflects on the character segmentation and the scheme of integrated border information of tentative character patterns of the character pattern so that both schemes complement each other, whereby a character string even having irregular character widths, character pitches, and character spacings can be segmented accurately for character classification based on the optimal use of effective information.

[0035] In dealing with the problem of the difficulty of character segmentation for a hand-written character string based on the assumed values of the character width, character pitch and character spacing common to all characters, the inventive method compares the feature values of character patterns by making reference to the character segmentation dictionary which is prepared for the testing of the assumption of character segmentation, thereby evaluating the credibility which reflects on the character segmentation. The character segmentation dictionary contains the likelihood distribution as the credibility of pattern with respect to the feature values. Although the calculation of credibility requires a lot of manpower, time and experience-based knowledge, the inventive method enables the evaluation of the credibility of the optimal weighting for each character species by merely displaying tentative character segmentations on the screen so that the operator merely selects a correct tentative character segmentation.

[0036] FIG. 1 is a diagram showing an example of the input image which invokes the ambiguity of character segmentation for the prior art schemes;

[0037] FIG. 2 is a flowchart showing the character reading method based on an embodiment of this invention;

[0038] FIG. 3 is a block diagram of the character recognition apparatus which practices the inventive character reading method;

[0039] FIG. 4 is a diagram used to explain the character string extracting process 204 in FIG. 2;

[0040] FIG. 5 is a diagram used to explain the vertical/horizontal form discrimination process 205 in FIG. 2;

[0041] FIG. 6 is a diagram used to explain the tentative pattern generation process 206 of FIG. 2 in correspondence to an input image;

[0042] FIG. 7 is a diagram showing the data structure of the pattern table 219 in FIG. 2;

[0043] FIG. 8 is a conceptual diagram showing a string of tentative character patterns determined uniquely by the tentative pattern determination process 209 of FIG. 2;

[0044] FIG. 9 is a diagram used to explain the lattice generation process 210 and town matching process 211 of FIG. 2;

[0045] FIG. 10 is a diagram used to explain the character segmentation recurrent determination process 215 of FIG. 2 for dealing with Kanji-numerals and Arabic numerals in the street number portion;

[0046] FIG. 11 is a diagram used to explain the character classification of the street number portion based on the correspondence between the input image and the tentative character patterns;

[0047] FIG. 12 is a diagram used to explain the process of calculating the credibility of tentative character patterns in FIG. 10;

[0048] FIG. 13 is a diagram showing the result of calculation of the credibility of patterns and weighting to the arcs of tentative character segmentation for the street number portion;

[0049] FIG. 14 is a diagram showing the character segmentation selected at the recurrent determination of character segmentation for the street number portion;

[0050] FIG. 15 is a diagram showing the result of recognition of the whole address character string produced by combining the recognition results of the town name portion and street number portion;

[0051] FIG. 16 is a diagram showing an example of display on the screen for the tools used for the maintenance and the expansion of function of the inventive address recognition apparatus and the creation and revision of the dictionaries;

[0052] FIG. 17 is a flowchart showing an example of the overall processing of this invention;

[0053] FIG. 18 is a diagram showing an embodiment of this invention;

[0054] FIG. 19 is a diagram showing the relation between patterns and their boundaries;

[0055] FIG. 20 is a table showing the structure of the pattern table which contains arcs of the segmentation hypothesis network;

[0056] FIG. 21 is a table showing the structure of the node table which contains nodes of the segmentation hypothesis network;

[0057] FIG. 22 is a flowchart showing the calculation process of the external form penalty;

[0058] FIG. 23 is a table showing the types of segmentation error;

[0059] FIG. 24 is a flowchart showing the segmentation error assessment process;

[0060] FIG. 25 is a diagram showing the feature values used in the segmentation error assessment process;

[0061] FIG. 26 is a diagram showing the principle of the segmentation error assessment process;

[0062] FIG. 27 is a flowchart showing the address dictionary matching process;

[0063] FIG. 28 is a diagram showing the principle of the dictionary matching process;

[0064] FIG. 29 is a diagram showing an example of display on the screen for the sample collecting tools;

[0065] FIG. 30 is a flowchart showing the learning of the parameter dictionary;

[0066] FIG. 31 is a table showing the structure of the parameter dictionary;

[0067] FIG. 32 is a flowchart showing the external form penalty calculation process;

[0068] FIG. 33A and 33B are diagrams showing examples of address character strings to be recognized; and

[0069] FIG. 34A and 34B are diagrams showing examples of the segmentation hypothesis network and assumed segmentation errors.

[0070] FIG. 2 is a flowchart showing the character reading method based on an embodiment of this invention. This embodiment is applied to the automatic character reader for reading postal addresses written on the surface of mail pieces. The process of reading a character string of a postal address which consists of a town name and street number is carried out as follows.

[0071] The mail surface 201 is imaged with an imaging means (scanner) to form a video signal: (202), information of address block is extracted from the video signal: (203), and a character string is segmented based on the image information of the address block: (204).

[0072] The image information, with the character string being segmented, undergoes the discrimination of vertical form or horizontal form: (205), and the processing mode is switched according to the result: (221). These processes 201-221 are carried out based on the conventional scheme.

[0073] There have been practiced various methods with electronic apparatus of reading automatically character strings of prefecture names, city names, town names and so on written on mail pieces. For example, Japanese patent publication JP-A-Hei-2-64882 discloses the address recognition based on different character segmenting processes for one character string portion from the beginning to the town name and another character string portion of the street number. Japanese patent publication JP-A-Hei-5-151389 discloses a method of detecting the region of mail surface where the address is written based on the prior detection of the position of postal zip code.

[0074] Japanese Patent Publication No.60-41396 discloses a method of segmenting a character string in the address block based on the measurement of the height of a block pattern and detection of a character string having the same height. Japanese patent publication JP-A-Sho-63-18785 discloses a method of distinguishing the vertical or horizontal form (direction of a string of characters) of a segmented character string based on the evaluation of the horizontal length and vertical length of characters in the address block and the comparison of these lengths.

[0075] Subsequently, the process of segmenting the tentative character pattern at the position of the possible character formation proceeds by combining consecutive black pixels (i.e., stroke) within the character string of image information. This process of tentative character pattern segmentation will be called “tentative pattern generation” (206). Tentative character patterns may include improper patterns besides correct character patterns to be recognized. The segmented tentative character patterns are registered in the pattern table 219. The tentative character patterns and the pattern table 219 will be explained in detail later in connection with FIG. 6 and FIG. 7.

[0076] Each tentative character pattern registered in the pattern table 219 is subjected to character recognition based on a character classification dictionary 208:(207). In the character classifying process, several recognition-candidate characters that resemble each tentative character pattern, the similarity of the recognition candidate characters with the tentative character pattern, the position of tentative character pattern on the character string, information on the number of connected components consecutive block pixels, and attribute information of the tentative character patterns are obtained as border information. The recognition-candidate characters and border information are stored in correspondence to each tentative character pattern in the pattern table 219. A proper tentative character pattern for character segmentation is selected based on the pattern table 219 in which the recognition-candidate characters and border information have been stored: (209). A set of recognition-candidate characters, i.e., a string of recognition-candidate characters, is produced from the recognition-candidate characters corresponding to the character pattern selected at the determination of character segmentation:(210). Character species up to the low-order candidate character are registered for the recognition-candidate character string for each character pattern. This registered character species will be called “lattice”.

[0077] Town matching for comparing the lattice with the town name dictionary 220 is carried out:(211), thereby producing a proper recognition character string for characters of town name of address. The town name dictionary 220 contains all town names existing. Reading of characters of the town name by the town matching process 211 completes, the last character of the character string of the town name is determined, and information of the head position of street number is obtained.

[0078] Upon obtaining the information of the head position of street number, information on the vertical and horizontal lengths, vertical/horizontal ratio, pattern spacing, number of connected components (called “pattern periphery information” or “information around tentative pattern”) of the tentative character pattern is extracted: (212). The credibility of the extracted periphery information is calculated by use of the segmentation dictionary 214: (213). The calculated credibility is stored as the attribute of the corresponding tentative character pattern in the pattern table 219.

[0079] A tentative character pattern in the pattern table 219 is selected again based on the credibility to override the previous selection. Namely, the determination of character segmentation takes place to override the previous determination to have only the street number different from the tentative character pattern selected at the tentative pattern determination 209: (215). Following this recurrent character segmentation determination 215, a lattice is produced again based on the information: (216). Street matching is carried out for the newly produced lattice by used the street number dictionary 222: (217), and recognition of street number characters is carried out. The street number dictionary contains all characters for expressing any street number. The result is combined with the characters of town name which have been recognized by town matching (211), and the recognition of the entire address completes: (218).

[0080] Next, the details of the individual processes shown in FIG. 2 and the apparatus which carries out these processes will be explained. The processes from video signal input 202 up to vertical/horizontal mode switching 221 are the same as the prior art scheme, and the processes from tentative pattern generation 206 up to town matching 211 are the technique described in the above-mentioned publication of The Transaction of the Institute of Electronics, Information and Communication Engineers, (D) J68-D, No.4, pp.765-772.

[0081] FIG. 3 shows the arrangement of the apparatus which carries out the address reading method described above. In the figure, the bored arrows indicate the flow of a mail piece. A video signal 202 is entered by means of a scanner 301. In order to make the time for reading the address, there is provided a delay line 314 on the mail piece conveyance path. The scanner 301 is connected by an input/output cable 304 to a character recognition apparatus 312, which is connected with a sorter 303 by another input/output cable 305.

[0082] The character recognition apparatus 312 has an internal bus 313 for connecting the internal devices, an I/O interface 306 for the communication with the scanner 301, an arithmetic processing device 307 which controls the overall apparatus 312 and implements the address recognition process, an I/O interface 308 for the communication with the sorter 303, a keyboard 309 used for the start-up operation and the like, a CRT unit 310 for displaying the state of processing, and a memory 311 for storing the tables, programs and dictionaries used for address recognition.

[0083] FIG. 4 is a diagram explaining the processes from video signal input 202 up to character string extraction 204. Indicated by 407 is the image of the address block extracted from the video signal 202 by the address block locating process 203. Shown by 403, 404 and 405 are histograms drawn by projecting black pixels included in the address block 407 onto the axis 408 which is parallel to the y-axis 402. Based on the values of these histograms, the y-axis coordinates of the top and bottom of a character string, as shown by the dashed line 406, are evaluated, and the character string of address line is extracted: (204).

[0084] FIG. 5 is a diagram explaining the vertical/horizontal form discrimination process 205. Shown by 501 is the image of a character string written in horizontal form. Indicated by 502 and 503 are character patterns of the starting character and ending character of the character string, and 505 and 509 are these character patterns extracted intact from the character string. Indicated by 506 and 510 are character patterns derived from the character patterns 502 and 503 but rotated by 90° by the pattern rotation processes 504 and 511. These character patterns are subjected to character classification: (507). The resulting values of similarity are compared: (508), and vertical/horizontal form discrimination or writing direction (205) is implemented based on the comparison result. The feature extraction process is switched between the vertical form and horizontal form based on the result: (221 of FIG. 2).

[0085] In contrast to the form discrimination by use of the layout information of the image, which often results in an erroneous judgment for an input image including an address character string that does not comply with the standard layout, this embodiment of invention which implements the form discrimination by use of character recognition itself performs the reliable vertical/horizontal form discrimination. In case there is little difference in the similarity between the first and last characters of the address character string and those rotated by 90°, characters neighboring the first and last characters are taken out and they undergo the same form judgment process. Namely, the vertical/horizontal form discrimination is carried out by avoiding such Kanji characters as “” and “” that vary little in the similarity when rotated by 90°, but based on characters suitable for the judgment thereby, enhancing the accuracy of form discrimination.

[0086] FIG. 6 is a diagram explaining the tentative character pattern in correspondence to the input image. For a hand-written address character string 601 to be recognized, the tentative pattern generation process 206 of FIG. 2 segments the character string of input image at character boundaries (indicated by dashed lines 603-i, where i=1,2, . . . , n). The points numbered by 1 through 8 in circles and labeled by 603-i (where i=1,2, . . . , n) are called “nodes”. A curve 604 which connects two adjacent nodes is called an “arc”, and patterns 605, 606, . . . ,611 which correspond to these arcs 604 are tentative character patterns. Namely, shown on the right-hand side of the figure is a segmentation hypothesis network. For example, for character pattern “z,9 ” to be recognized, there are possible tentative character patterns of “z,10 ” 606 and “” 607 in addition to the pattern “” 605. Similarly, for character pattern “”, there are possible assumed divisional character patterns of “—” 609 and “□|” 611 in addition to the pattern “” 610. Each tentative character pattern exists between nodes connected by an arc.

[0087] FIG. 7 shows the data stored in the pattern table 219. Indicated by 701 is a pointer which points a memory location where image information segmented as a tentative character pattern is stored. Location 702 stores the credibility of the arc which corresponds to this tentative character pattern (the credibility indicative of the weight differs depending on the distance between the nodes). Location 703 stores the number of connected components in the tentative character pattern (e.g., it is three for character pattern “” and it is two for character pattern “”), and location 704 stores the x and y coordinates of the tentative character pattern (coordinates of the top left and bottom right corners of a block which surrounds the tentative character pattern). Location 705 stores the node number of the node at the head of the arc, and location 706 stores the node number of the node at the end of the arc. By making reference to these node numbers, the pattern data can be expressed in the form of the segmentation hypothesis network of the tentative character pattern. Location 707 stores several candidate characters obtained at character classification 207 of the tentative character pattern by making reference to the character classification dictionary 208, and location 708 stores the values of similarity of the candidate characters with respect to the tentative character pattern.

[0088] The manner of calculating the similarity is arbitrary, and any known scheme can be employed. Bold lines 709 indicate the range of the table space for one tentative character pattern, and this range corresponds to one arc. For example, for the tentative character pattern of “”, the range corresponds to the arc 604-1. Accordingly, the node number in 705 of the preceding node is {circle around (0)}, and that in 706 of the following node is {circle around (2)}.

[0089] FIG. 8 is a diagram explaining the tentative pattern determination process or decision of character in FIG. 2. Shown in the figure are tentative character patterns determined uniquely by the tentative pattern determination process 209 based on the data in the pattern table 219. The tentative pattern determination process 209 registers, as credibility 702, the similarity of candidate characters resulting from character classification for all tentative character patterns in the pattern table, sums the values of credibility of arcs existing along possible routes from the node 0 to the node {circle around (8)}, and determines a string of tentative character patterns on the route with the largest summed value of credibility to be the tentative pattern segmented. The example of FIG. 8 shows the route with the largest summed value of credibility, which connects the nodes {circle around (3)}, {circle around (4)}, {circle around (5)}, {circle around (7)}, and {circle around (8)}.

[0090] Comparing FIG. 8 with FIG. 6 reveals that the arcs 604 from node {circle around (0 )} to node {circle around (1)}, from node {circle around (1)} to node {circle around (2)} and from node {circle around (1)} to node {circle around (3)}, and the arcs 604 from node {circle around (4)} to node {circle around (6)}, from node {circle around (5)} to node {circle around (6)} and from node {circle around (6)} to node {circle around (7)} in the network of FIG. 6 are absent in FIG. 8. Accordingly, by conducting the assessment of all tentative character patterns in the pattern table 219 based on the character classification, character segmentation is determined (209 in FIG. 2) based on the tentative character patterns of enhanced credibility.

[0091] FIG. 9 is a diagram explaining the result of character recognition for the town name portion produced by the town matching process 211 for the received character classification result for the uniquely determined segmentation, and also explaining the head position of the street number portion. Reference numeral 601 indicates the image of an address character string to be recognized, a dashed line 902 indicates the border line of determined character segmentation, i.e., node, and 707 indicates a set of candidate characters as a result of character classification for a segmented tentative character pattern. A character 903 enclosed in circle is the character selected as a result of town matching (211 of FIG. 2) for the candidate characters 707. Selected characters “”, “”, . . . , “” are combined to produce a character string 910 as a result of recognition of the town name. A pair of dashed lines 905 indicate the range of input image 601 to which the character string determined by town matching corresponds. The head position 911 of the street number portion is determined by the town matching process 211.

[0092] In the figure, indicated by 906, 907, 908 and 909 are tentative character patterns of the street number portion, and 912 through 916 are sets of character strings as a result of character classification for the tentative character patterns of the street number portion. These candidate characters are already obtained by the processes up to the lattice generation 211. The address section following the street number head position 911 is written in Kanji-numerals or Arabic numerals in most cases, and therefore the process of character segmentation of this portion is different from that for the town name portion which is written in Kanji characters. Otherwise, if the character segmentation process for the town name portion is applied to the street number portion, character patterns “” and “” are often divided into tentative character patterns 906 and 907 and tentative character patterns 908 and 909, respectively. In addition, fewer kinds of characters are used in this portion.

[0093] FIG. 10 is a flowchart of the process of the recurrent determination of character segmentation for the street number portion, which is the processes from pattern periphery information extraction 212 up to character segmentation recurrent determination 215 in FIG. 2. Examples of character pattern will be explained in detail later in connection with FIG. 11 through FIG. 14.

[0094] The head of street number portion is detected (1013) from the input information 911 provided by the town matching process 211, and a recognition-candidate character of the tentative character pattern of the street number portion is clipped as character species information from the pattern table 219:(1002). In this embodiment, the candidate character with the highest similarity in the candidate character string resulting from character classification 207 is adopted as the character species information. The segmentation dictionary or parameters 214 are accessed for reference with the clipped character species information as the key. At character species clipping 1002, periphery information for the tentative character pattern which corresponds to the character species is extracted: (212). The periphery information is data of the vertical and horizontal lengths, vertical/horizontal ratio, pattern spacing and number of connected components of the tentative character pattern.

[0095] The segmentation dictionary 214 is accessed for reference with the character species as the key to obtain the likelihood ratio for the periphery information including the vertical and horizontal lengths, vertical/horizontal ratio, pattern spacing and number of connected components. This dictionary 214 contains values of likelihood ratio against periphery information, and the likelihood ratio for each periphery information is calculated as the credibility: (1005, 1006, 1007, 1008). The calculated values of credibility or confidence degrees are integrated: (1010). The likelihood ratio L(e_k|H) for a feature value e_kis calculated from the event H of correctness of the segmented tentative character pattern as the classified character species, the feature values e₁, e₂, e₃, . . . , e_nof pattern periphery information and the probability of occurrence P(e|H) of e of the case of the event H, as follows. $\begin{array}{cc}L\left(e_k|H\right)=\frac{P\left(e_k|H\right)}{P\left(e_k|\stackrel{\_}{H}\right)}& \left(1\right)\end{array}$

[0096] For the probability of occurrence P(H) of H, the probability of occurrence P(H|e₁, e₂, e₃, . . . , e_n) of H for the feature values e₁, e₂, e₃, . . . , e_n, is obtained by using multiple likelihood ratios resulting from the formula (1) based on the Bayes rule as follows. $\begin{array}{cc}P\left(H|e_1,e_2,e_3,\dots ,e_n\right)=\frac{\frac{P\left(H\right)}{P\left(\stackrel{\_}{H}\right)}\prod _{k=1}^{n}L\left(e_k|H\right)}{1+\frac{P\left(H\right)}{P\left(\stackrel{\_}{H}\right)}\prod _{k=1}^{n}L\left(e_k|H\right)}& \left(2\right)\end{array}$

[0097] The credibility integrating process 1010 integrates the likelihood ratios calculated in the processes 1005, 1006, 1007 and 1008 by using the formula (2) based on the Bayes rule. Subsequently, the arcs are weighted by the integrated credibility multiplied by the similarity resulting from character classification: (1011). Based on the data of tentative character pattern derived from the weighted arc, the optimal route which runs from the first node to the last node is searched thereby to determine the character segmentation path: (1012). The result is used for street matching (217 of FIG. 2).

[0098] FIG. 11 is a diagram explaining the tentative character patterns of the street number portion of the address character string. The street number portion 1102 of the input image of the address character string is already segmented by the tentative pattern generation 206 of FIG. 2 based on the border lines 1104, and the result is stored in the pattern table 219. The data structure of the pattern table is the same as explained in connection with FIG. 6 and FIG. 7. A pair of dashed lines 1103 indicates the correspondence between the segmentation border lines 1104 and node numbers 1105 (50, 51, 52, . . . ,55 enclosed by circles). For example, processing of character classification for the tentative character pattern “” 1106 (it corresponds to arc 1107) produces candidate characters 1108 of “”, “3” and “”. Similarly, processing of character classification for the tentative character pattern “” 1109 (it corresponds to arc 1111) produces candidate characters 1110 of “”, “” and “”.

[0099] The arcs of these tentative character patterns are weighted as explained in connection with FIG. 10. Specifically, the character species “”, “” and “” 1110 are improper characters for use in the street number portion, and therefore the weight of the arc 1111 which corresponds to the tentative character pattern 1109 is reduced. Based on this weighting process, arcs which are obviously improper for the street number portion are removed. The remaining tentative character patterns (e.g., “”, “”, “”, “|”, etc.” undergo the respective weighting process so that improper arcs are removed.

[0100] FIG. 12 is a diagram explaining the arc weighting process 1011 in FIG. 10 for the tentative character pattern “” 1106 for example in the street number portion. Initially, periphery information is extracted from the tentative character pattern “”: (212). The periphery information includes the values of height and width of character, aspect ratio, pattern spacing and number of connected components. At this time, the top-ranking candidate character “” among the candidate characters “”, “3” and “” as a result of character classification is also referenced. This set of information is shown by 1214 and 1215 within the block 1213.

[0101] At character species clipping 1002, the information 1214 of the character species “” is sent to the segmentation dictionary 214. The segmentation dictionary 214, which is accessed for reference with the character species as the key, contains data 1205 used for the weighting of arcs. The character species provided by the character species clipping 1002 is used to for the key to search the index “” in the segmentation dictionary 214. Upon detecting the data 1205 with the index “”, the likelihood ratios corresponding to the vertical length (or height) 1206, horizontal length (or width) 1207, aspect ratio 1208, number of connected components 1209 and pattern spacing 1210 are read out, the values of credibility of the periphery information is evaluated: (1204), the likelihood ratios or confidence degree (credibility: 1,2,3,4,5) are integrated: (1010), and the arc 1107 relevant to the tentative character pattern “” 1106 is weighted: (1011). Accordingly, the pattern periphery information reflects on the arc 1107 of the tentative character pattern 1106, whereby optimal weighting depending on the character species is implemented.

[0102] FIG. 13 is a diagram showing the result of weighting in terms of the thickness of arc line. Indicated by 1301 is the arc which is weighted in accordance with the periphery information for the tentative character pattern “” 1106. Arc 1303 has an increased weight in accordance with the periphery information for the tentative character pattern “|”. Arc 1302 which connects nodes {circle around (52)} and {circle around (54)} is of a tentative character pattern that resembles character pattern “” formed of two lower connected components of the pattern “” Character classification for the tentative character pattern “” produces candidate characters of character species “”, “” and “2” as shown in FIG. 11, of which the character species “” having the greatest similarity can possibly be judged erroneously to be a correct assumption. However, the periphery information reveals that this pattern of the arc 1302 has a narrow spacing from the pattern immediately above it, causing it to have its credibility lowered when the segmentation dictionary 214 is referenced. Accordingly, the arc 1302 has a smaller weight than the case of weighting based solely on the similarity, and it is smaller than the weight of the arc 1301. Consequently, the route including the arc 1302 has a smaller total weight relative to the route include the arc 1301.

[0103] FIG. 14 shows a string of tentative character patterns selected by the recurrent determination of character segmentation for the street number portion. Specifically, weights are applied to the arcs for the tentative character patterns by the arc weighting process (1011 of FIG. 10), and a path having the largest sum of weights is determined. Then, the route including the arc 1301 of the tentative character pattern “” and arc 1303 of “|” is selected. Namely, for the recurrent determination of character segmentation for the street number portion, arcs corresponding to tentative character patterns “”, “|”, “”, “|” and “” are selected to form a path. The candidate character string relevant to the patterns of the selected arcs is used to generate the lattice of the street number portion: (216).

[0104] FIG. 15 shows the result of recognition of the whole address character string based on this embodiment. Namely, this is the result of character segmentation specialized for the street number portion, lattice generation, street number matching, and integration of the street number portion to the result of town matching. A pair of dashed lines 905 led out of the input image 601 of the address character string indicate the range of the town name portion, and 910 indicates the result of town name matching. Dashed lines 1510 indicate the boundaries of recurrent determination of character segmentation, and a set of characters 1506 are candidate characters resulting from character classification of each character. Dashed lines 1507 and 1509 indicate the range of the street number portion, and a character string 1508 is the result of street number recognition obtained by street number matching 217 from the candidate sets of characters of the result of character classification, i.e., it is the result of recognition of the street number. Character string 1504 is the result of recognition of the whole address character string produced by connecting the street number matching result 1508 to the town name matching result 1502. By retrying the character segmentation for the street number portion only and combining the result with the town name matching result in this manner, the accuracy of recognition of the whole address character string is improved.

[0105] FIG. 16 shows an example of display on the screen showing the input address character string and the pattern table for character segmentation and the result of character classification. Shown on the screen 1600 of the display device 310 of FIG. 3 are the image of input address character string 1601, nodes 1602-i (i=1,2, . . . ,8) of pattern table, arcs 1603-1 and 1603-4 which connect the nodes, arcs which connect adjacent nodes, tentative character patterns 1604-j (j=1,2, . . . , 10), and sets of candidate characters 1605 obtained by character classification for the tentative character patterns 1604-j. This display on the screen 1600 of the display device 310 enables the intuitive understanding of the character segmentation and the progress of character classification process during the address character string recognition process, and it is useful for the maintenance and the expansion of function of the apparatus. It is necessary to collect periphery information of patterns segmented based on the assumption at the creation or revision of the segmentation dictionary 214.

[0106] Referring to the formula (1), a likelihood ratio stored in the character segmentation dictionary has a value that is the distribution of periphery information of tentative characters of the case of correct character segmentation divided by the distribution of periphery information of tentative characters of the case of incorrect character segmentation. On this account, when the apparatus is designed to release such information as values of periphery information and character classification result in response to the specification of an arc with a pointer on the displayed screen as shown in FIG. 16, it becomes possible to easily collect pattern periphery information separately for the cases of correct segmentation and incorrect segmentation. The displayed tools are effective also for the collection of character patterns required at the creation and revision of the character segmentation dictionary.

[0107] FIG. 17 is a flowchart showing the character reading method based on another embodiment of this invention. This embodiment is also the application of a character reading method to the automatic postal address reading apparatus arranged as explained in connection with FIG. 3.

[0108] The address line segmentation process 171 extracts the address block region from the video signal of the mail surface. The next tentative pattern segmentation process 172 extracts tentative character patterns from the character string to produce a segmentation hypothesis network. The external form penalty calculation process 173 calculates the external form penalty (p) of each tentative character pattern. The character classification process 174 classifies each tentative character pattern and produces multiple candidate character species codes and the similarity of the tentative character pattern and candidate character. The pattern credibility calculation process 175 calculates the credibility of each tentative character pattern based on the similarity and external form penalty. The address dictionary matching process 176 selects tentative character patterns based on the credibility of pattern and compares the candidate character species resulting from character classification with the address dictionary.

[0109] FIG. 18 shows a displayed image of the mail surface. The address line segmentation process 171 extracts from the mail piece image 181 a rectangular area 182 which includes a written character string of town name and street number. The area 182 may include more than one character string of address, and the process extracts the area of these character strings in such case. The manner of address block extraction is the same as the preceding embodiment.

[0110] The tentative pattern segmentation process 172 will be explained with reference to FIG. 19 which shows the enlarged image of the character string within the area 182. In the figure, vertical lines numbered by 0 through 9 are candidates of boundaries. The candidate boundary is the gap between such rectangles as described in the TECHNICAL REPORT OF IE88-138, “A Method to Character Segmentation for Printed Character Lines Including Character Lines of Irregular Pitches”. The x-axis coordinate of the left end of the character pattern on the right-hand side of a boundary subtracted by the x-axis coordinate of the right end of the character pattern on the left-hand side of the boundary is called “border gap”, and the average value of the x-axis coordinate of the left end of the character pattern on the right-hand side of a boundary and the x-axis coordinate of the right end of the character pattern on the left-hand side of the boundary is called “border coordinate”. For example, the border coordinate for the boundary numbered by 4 is the x-axis coordinate of the boundary 194, and the border gap is the width 195.

[0111] Subsequently, a combination of boundaries, for which the difference of border coordinates does not exceed the character size which is inferred from the height of character string, is examined and patterns between these boundaries are registered as tentative character patterns. In the example of FIG. 19, the border coordinate differences 191 and 192 do not exceed the inferred character size, while the border coordinate difference 193 exceeds the character size. Therefore, the character pattern between boundaries {circle around (0)} and {circle around (1)} and character pattern between boundaries {circle around (0)} and {circle around (2)} are registered, and the character pattern between boundaries {circle around (0)} and {circle around (3)} is rejected.

[0112] FIG. 20 shows the format of the pattern table which contains data of arcs of the segmentation hypothesis network produced by the tentative pattern segmentation process 172. Each record of the pattern table corresponds to one tentative character pattern. The table consists of a field 2001 for storing the profile of a pattern described in chain code, fields 2002 and 2003 for storing the left-hand border number and right-hand border number of the tentative character pattern, a field 2004 for storing the candidate character species as the result of character classification, a field 2005 for storing the values of similarity of the candidate character species in the field 2004, and a field 2006 for storing the credibility of the pattern. Among these items, the border number begins with 0 position at the left extreme of a character string and ascends as the boundary shifts from left to right, and up to three candidate character species and values of similarity are stored by being left-justified in the fields 2004 and 2005, with vacant spaces of the fields 2004 and 2005 being filled with null codes and “0”s, respectively.

[0113] FIG. 21 shows the format of the boundary table which contains data of nodes of the segmentation hypothesis network produced by the tentative pattern segmentation process 172. Each record of the boundary table corresponds to one boundary. The table consists of a field 2101 for storing the border number, a field 2102 for storing the border coordinate, and a field 21-3 for storing the border gap.

[0114] The character classification process 174 used in this embodiment is the known process. Among characters including Kanji characters, Hiragana characters, Katakana characters, Arabic numerals and symbols, those used to describe town names and street numbers are treated for character recognition. The output of character classification is multiple candidate character species and values of similarity of the input character pattern with respect to the standard pattern of individual candidate character species.

[0115] FIG. 22 is a flowchart of the external form penalty calculation process 173. The tentative character pattern as the input of this process is expressed by a record in the pattern table (FIG. 2) and a boundary table (FIG. 21). Multiple segmentation assessment processes 2201, 2202 and 2203 are conducted for each tentative character pattern for the assessment of the assumption of erroneous segmentation. The greater the outputs pi (i=1,2,1) of the process, the higher is the credibility of the assumption of erroneous segmentation. The outputs pi are summed by the process 2204, and the result is delivered as the external form penalty p.

[0116] FIG. 23 is a diagram explaining the types of segmentation error of FIG. 22, showing seven types of erroneous segmentation processes E1 through E7. In the figure, a solid image expresses the tentative character pattern in attention, a dashed-line block expresses a rectangle which confines the correct character pattern, and a bored image expresses part of the pattern in the periphery of the tentative character pattern. For example, erroneous process E1 indicates the assumption of erroneous segmentation of the left-hand side of a character for the assumed pattern in attention. Erroneous process E7 indicates the assumption of erroneous segmentation of two characters for the assumed pattern in attention.

[0117] FIG. 24 is a flowchart showing the erroneous segmentation assessment process. The tentative character pattern as the input of this process is expressed by a record (character species) in the pattern table and a boundary table. The erroneous segmentation assessment process 2401 corresponds to one of assumption assessment processes 2201, 2202 and 2203. The feature extraction process 2402 extracts features such as the character pattern size and positional relation with neighboring character patterns, from the input tentative character pattern. The feature is treated as a n-order vector as follows.

[0118] F=(f1, f2, . . . , fn)

[0119] Subsequently, the process 2403 evaluates the penalty pi from the feature F. The penalty pi is the value of the linear recognition function which distinguishes a correctly segmented character pattern from erroneous results such as those of the processes Ei in FIG. 23, and it is defined as follows.

[0120] pi=F·Vi+ci

[0121] where Vi is the weight vector of the linear recognition function, ci is a constant, and F·Vi is the inner product of Vi and F.

[0122] The values of Vi and ci are determined based on learning in the manner explained later and stored in the parameter dictionary 2204 in advance. As an alternative scheme different from this embodiment, parameter dictionaries may be switched in response to the candidate character resulting from character classification.

[0123] FIG. 25 is a diagram showing a character pattern used to explain the above-mentioned feature F. In the figure, a solid image 2501 expresses the tentative character pattern in attention, and bored images 2502 and 2503 express the adjacent character patterns. A dashed-line block expresses a rectangle which confines each character pattern.

[0124] In this example, the order n of the feature F is 6, and individual feature values are defined as follows.

[0125] f1: Height of the character pattern in attention

[0126] f2: Width of the character pattern in attention

[0127] f3: Spacing of the character pattern in attention with the left-adjoining character pattern

[0128] f4: Spacing of the character pattern in attention with the right-adjoining character pattern

[0129] f5: Maximum gap of the character pattern in attention

[0130] f6: Number of connected components of the character pattern in attention

[0131] Although the same feature values are used for all erroneous segmentation assessment processes in this example, different feature values may be used for each process. Alternatively, each feature value may be normalized with respect to the general feature of the character string such as the height h of character string.

[0132] FIG. 26 is a diagram used to explain the principle of the erroneous segmentation assessment process. Shown by 2601 and 2602 are two coordinate axes out of n-order Euclid space. A pattern group 2603 is the distribution of feature F of the correctly segmented tentative character patterns, and another pattern group 2604 is the distribution of feature F of the tentative character patterns with the erroneous segmentation assumption Ei. In the figure, indicated by Wi is the weight vector of the recognition function which distinguishes the pattern groups 2603 and 2604, and it intersects with the hyperplane B which separates the pattern groups 2603 and 2604.

[0133] The hyperplane B is express to be a set of F that meet the following formula.

[0134] (Wi·F)=a·|Wi|

[0135] where a is the Euclid distance from the origin to the hyperplane B, Wi·F is the inner product of Wi and F, and |4Wi| is the norm of Wi.

[0136] The linear recognition function which distinguishes the groups 2603 and 2604 has its value d given as follows.

[0137] d=(Wi·F)−a·|Wi|

[0138] The F belongs to the group 2604 if d is greater than 0, or otherwise it belongs to the group 2603.

[0139] The Wi and a·|Wi| can also be evaluated by the manner described in publication “Recognition Engineering”, by Toriwaki, ISBN4-339-01059-6, C3355, P2781E, pp.113-119, published by Korona co. However, the use of the value of d intact for the value pi of the linear recognition function is not appropriate due to a different distribution of each Ei in the Euclid space. On this account, the following normarized value of linear recognition function is used for pi. $\begin{array}{ccc}\mathrm{pi}& =& d/\left(s·\left|\mathrm{Wi}\right|\right)\\ & =& \left(\mathrm{Wi}·F\right)/\left(s·\left|\mathrm{Wi}\right|\right)a/s\end{array}$

[0140] where s is the variance of d for the set including both of 2603 and 2604.

[0141] Accordingly, the weight vectors Vi and constants ci of the linear recognition function stored in the parameter dictionary 1104 are obtained as follows.

[0142] Vi=Wi/(s·|Wi|)

[0143] ci=a/s

[0144] Next, the pattern credibility calculation process 175 will be explained in brief. The pattern credibility indicates the degree of credibility of arcs on the segmentation hypothesis network, i.e., candidate patterns, and it is evaluated as follows.

[0145] Pattern credibility={c1·(similarity of top-ranking candidate character)−c2·p}

[0146] where p is the external form penalty and c1 and c2 are constants specific to the system.

[0147] FIG. 27 is a flowchart of the address dictionary matching process 176. The process receives the inputs of a tentative character pattern, pattern credibility candidate character and similarity from the pattern table and boundary table explained previously. Initially, the tentative character pattern selection process 2701 selects tentative character patterns having values of pattern credibility smaller than a certain value. In the example of FIG. 34A, the character patterns {circle around (0)}-{circle around (2)}, {circle around (0)}-{circle around (3)}, etc. have small values of similarity as a result of character classification and, consequently, have small values of pattern credibility. Therefore, these character patterns are removed, and the segmentation hypothesis network is reduced as shown in FIG. 34B. The character pattern 4-6 has a large external form penalty and thus has a small pattern credibility, and therefore it is removed.

[0148] Subsequently, the dictionary matching process 2703 compares candidate characters of each tentative character pattern resulting from character classification with address character strings stored in advance in the address dictionary 2704, and delivers matched address character strings as candidate character strings. The candidate address character string sorting process 2705 rearranges the candidate character strings in the descending order of the degree of matching between candidate characters and candidate character strings. A candidate character string having a greater degree of matching is inferred to be more credible.

[0149] FIG. 28 shows in brief the dictionary matching process 2703. This process selects from the address dictionary 2704 an address character string which is accepted by the automaton created based on the result of character classification. For the determination of the address character string accepted by the automaton, the method proposed by Marukawa, et al. (The Transaction of the Institute of Information Engineers, Vol.35, No.6 “Chinese character address recognition: error correction algorithm”) is adopted. In FIG. 28, a frame 2801 shows by model the automaton which is created by the candidate characters resulting from character classification following the selection of tentative character patterns. The boundary between patterns represents the state and a candidate character resulting from character classification represents the transition. Each state is numbered consistently with the node number of segmentation hypothesis network. The automaton is accomplished by means of a table having the same structure as the pattern table. The bold lines in the automaton 2801 indicate the route of acceptance of the character string 2803 (12) in the address dictionary 2704 by the automaton 2801. In case the automaton 2801 accepts a character string in the address dictionary 2704, it delivers the character string as a candidate character string. The matching credibility mc is the total of the values of credibility tc (transition credibility) of the events of transition at the matching process, as follows.

[0150] mc=ΣStc

[0151] The transition credibility is evaluated as follows.

[0152] tc={c1·sm−c2·p}·jm

[0153] where sm is the similarity of the candidate character with respect to each transition, and jm is the difference of state numbers before and after the transition.

[0154] The constants cl and c2 are the same ones used for evaluating the pattern credibility. In the example of FIG. 28, another character string “11” is also accepted, and it is delivered as an address recognition result 2802, although this character string is accepted based on the candidate character having a smaller similarity than the case of the former character string and therefore it has the smaller matching credibility.

[0155] FIG. 29 shows an example of display of the sample collection tool which is used to collect samples for the learning of the parameter dictionary 2404 which is used for the erroneous segmentation assessment process 2401 shown in FIG. 24. In the figure, indicated by 2901 is a CRT screen, and 2902 is a window for displaying the image of character string. In the character string displayed in the window, a character pattern in attention currently is displayed in a different color (shown by the solid image in the figure). The operator who watches the image in the window 2902 makes a judgment as to whether the pattern is segmented correctly or not. On finding the incorrect segmentation, the operator identifies the type of erroneous segmentation shown in FIG. 23, and points the respective key displayed on the panel 2903 with the cursor 2904. In response to the operater's key action, the sample collection tool stores the feature values of the pattern in attention in the file of the error type and displays another character pattern in the window 2902.

[0156] FIG. 30 is a flowchart of the process for the learning of the parameter dictionary 2404 in FIG. 24. The sample collection tool 3002 uses address line image database (DB) 3001 collected in advance to produce correct segmentation pattern database 3003 and incorrect segmentation pattern databases (3004,3005, etc.) corresponding to the pattern databases E1 through E7 of the assumption of incorrect segmentation of FIG. 23. The learning tool 3006, which receives data of the correct segmentation pattern database 3003 and incorrect segmentation pattern database 3004 of E1, evaluates the weight vector V1 and constant c1 in the manner explained in connection with FIG. 26 and delivers these values to the parameter dictionary 3008. Similarly, the process uses other learning tools (3007, etc.) to evaluate weight vectors Vi and constants ci for the incorrect segmentation pattern databases (3005, etc.), and delivers these values to the parameter dictionary 3008.

[0157] FIG. 31 shows the table structure of the parameter dictionary. Each record pdic[i] of the table contains parameters Vi and ci corresponding to Ei. For example, the first record pdic[1] 3103 of the table contains V1 and c1, and the i-th record 3104 counted from the top contains Vi and ci. The parameters ci and Vi are stored in fields 3101 and 3102, respectively, of each record.

[0158] FIG. 32 shows the sequence of the external form penalty calculation process. The first step 3201 initializes the variable p to 0. The subsequent steps 3203 and 3204 are repeated while incrementing the variable i in the control loop 3202. The step 3203 starts the erroneous segmentation assessment process, and the step 3204 adds the results pi of erroneous segmentation assessment to p. Step 3208 delivers the variable p as the external form penalty. Steps 3205 and 3206 are the subroutine of erroneous segmentation assessment. The step 3205 substitutes the value of (pdic_i.c) of ci, which has been read out of the parameter dictionary, to the variable pi. The step 3206 is a control loop for evaluating the inner product of the F resulting from feature extraction and Vi read out of the parameter dictionary. Specifically, products of the values of (pdic_i.v_j) of Vi and values of F (f_j) are added to pi while incrementing the variable j up to the number of order of the feature.