Abstract:
The reading results of an agreed number of images of items, achieved by the OCR reader, are temporarily stored subdivided into reading results which are read unambiguously and reading results which are rejected. Then classes of words or word groups belonging together of the reading results temporarily stored and rejected, consisting in each case of n address words, n=1, 2, . . . , a, with interword gaps m, m=0, 1, . . . b are formed which do not drop below a particular similarity factor referred to in each case a particular n and m value between them. In the dictionary or dictionaries of the associated address areas, representatives, at least, of the classes whose frequency exceeds a predetermined value are included.

Description:
FIELD OF THE INVENTION 
   The invention relates to a method for forming and/or updating dictionaries for reading addresses. 
   Address reading systems need information on the content and syntax of addresses in order to be able to extract the required information such as town, zip code, first and last name, etc. The permissible content of individual address elements is described by means of a dictionary (list of permissible strings) which, according to the prior art, is built up from present information sources such as, e.g. from a postal dictionary or from a list of employees of a company. However, the application domain changes with time so that the dictionary created at the beginning no longer completely includes all existing contents. It is especially when a reading system is used for mail distribution within a company, that the change in the set of words is considerable: employees leave the company, new employees are added, employees change their department or last names due to marriage, etc. Thus, entries are missing in the dictionary and there are entries which are no longer valid. The more the set of words currently used deviates from the lexicon, the more the recognition performance of the reading system drops. 
   Previously, these changes had to be manually transferred into the dictionaries at certain time intervals so that the disadvantages described occurred. 
   SUMMARY OF THE INVENTION 
   It is the object of the invention to automatically form and/or automatically update a dictionary for reading addresses. 
   According to the invention, the object is achieved by the features of claim  1 . This is based on the concept of temporarily storing the results of the current reading processes, to evaluate them and to use them for automatically building up or updating a dictionary. During the temporary storage, the respective address is marked to indicate whether it has been read successfully or whether it has been rejected. If a dictionary is to be newly created or if new addressees are to be entered in the existing dictionary, the rejected reading results are utilized. 
   The dictionaries can contain individual words, e.g. last names and/or coherent word groups with words, etc. first and last name or first and last name and street names, where the words are located both directly next to one another (gap m=0) and can also be spaced apart by m words. 
   Automatic building up of a dictionary or, respectively, automatic updating of the dictionary due to new addressees or changes in the addressees is possible by forming classes of words or word groups which have a fixed minimum measure of similarity with respect to one another, and including at least the representative in the dictionary or dictionaries of the associated address areas. 
   Advantageous embodiments of the invention are described in the subclaims. 
   To form classes, it is advantageous to create a list of all words/word groups of the rejected reading results which are sorted in accordance with the frequency of the words/word groups. Beginning with the most frequent word/word group, the factor of similarity with all remaining words/word groups is determined and entered in a similarity list. All words/word groups in the similarity list having a similarity factor above a fixed threshold are then allocated as class to the current word/word group. After that, the words/word groups of the class formed are removed from the frequency list. The representatives of the respective class of words or word groups of the reading results temporarily stored and rejected can be formed by the shortest or most frequent word or word groups. 
   To recognize addresses in the dictionary which must be changed or removed, it is advantageous to statistically analyze the addresses read unambiguously. If there is an abrupt change in the frequency of words and/or word groups beyond a particular threshold and if it persists for a predetermined time, these words/word groups are removed from the dictionary. 
   To avoid irrelevant words of the reading results from being included in the dictionary, they can be determined by comparison with words stored in a special file for irrelevant words. 
   It is also of advantage in this connection not to include short words of less than p letters and without fullstop as irrelevant in the dictionary. To perform the address interpretation in as detailed as manner as possible with the aid of the dictionaries, it is advantageous to include, in addition to the representatives, also the words and/or word groups of the associated classes with the similarity factors and frequencies. 
   In a further advantageous embodiment, word groups belonging together and having n words which are mutually spaced apart by m words can be determined in that the addresses are searched with windows having a width of n+m words starting with the respective individual word determined for the dictionary. Once the further n−1 individual words with the gaps of m words between them have been determined, this word group and its frequencies are included in the corresponding dictionary. 
   It is also advantageous to determine the similarity factor by means of the Levenshtein method (see “A Method for the Correction of Garbled Words, based on the Levenshtein Metric”, K. Okuda, E. Tanaka, T. Kasai, IEEE Transactions on Computers, Vol. c-25, No. 2, February 1976). 
   It can also be advantageous to categorize, and to have confirmed, the dictionary updatings found at a video coding station or to compare the new entries into the dictionary additionally, before they are taken into the corresponding category, with the contents of a file in which characteristic generally applicable names or at least strings related to the respective category (first name, last name, department) are stored. 
   In the text which follows, the invention will be explained in greater detail in an exemplary embodiment and referring to the drawing. The aim is to determine previously unknown last names (n=1) or pairs of unknown first and last names (n=2) or last and/or first and last names and department names of employees of a company and/or corresponding, no longer valid names or name combinations, and to perform dictionary changes. 

   
     DETAILED DESCRIPTION OF THE DRAWINGS 
       FIG. 1  shows a flow structure of a monitor process for monitoring and controlling the updating of the dictionary 
       FIG. 2  shows a flow structure for determining and marking a relevant words 
       FIG. 3  shows a flow structure for determining previously unknown single words (n=1) (last names) 
       FIG. 4  shows a flow structure for determining previously unknown word groups starting with the single words 
       FIG. 5  shows a flow structure for updating the dictionaries, taking into consideration the word categories. 
   

   DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT 
   The word proposals are automatically generated from the recognition results calculated for each pattern of an item by the reading system in daily operation. The recognition results for each pattern of an item comprise different geometric objects (layout objects) such as text blocks, lines, words and characters and their relations to one another, that is to say which lines belong to which text block, which words are located in which lines etc. For each individual character pattern, the reading system generates a list of possible character meanings. In addition, the reading system calculates for each layout object its position in the pattern of an item and its geometric dimensions. 
   To update or even learn dictionary entries, the set of items processed is separated into two subsets, into the set of items read automatically (but not necessarily correctly) by the reading system and the set of rejected items. The set of items read automatically is used for determining dictionary entries which are no longer valid; from the set of rejected items, new dictionary entries are derived. 
   The exemplary system consists of five modules: a monitor process, processing of the recognition results (preprocessing), two dictionary generation methods and a proposal administrator. 
   The monitoring process according to  FIG. 1  monitors and controls the dictionary training. The recognition results  21  for each pattern of an item, together with an identification for “read successfully” or “rejected”, are transferred from the reader to the monitor. Additional information on the type of item (letter, large letter, in-house mail form) and other features relating to the individual objects of the recognition results such as ROI (Region of Interest), line and word hypotheses, disassembly alternatives and character recognition results can also be transferred. These recognition results are stored in a buffer  22  in the monitor until a sufficiently large amount of data has accumulated (e.g. after 20 000 items or after one week of operation). 
   In the simplest case, only the first alternative of the character recognition results together with the best segmenting path is stored in a buffer. For example, the content could look as follows: 
   
     
       
             
             
           
         
             
                 
             
             
               &lt;Recognition results&gt; 
               &lt;Identification&gt; 
             
             
                 
             
           
           
             
               :. . . 
                 
             
             
               1017921 PMD 55 
               recognized 
             
             
               MR. ALFRED C SCHMIDI 
             
             
               EXCCU1LVE DIRCC1OR, 0PCRA1IONS 
             
             
               DCVC1OPMENT 
             
             
               MyComp, INC 
             
             
               1 MyStreet 
             
             
               MyCity, 12345 
             
             
               PO11Y O/BRIEN 
               rejected, 
             
             
                 
               not in the dictionary 
             
             
               MANAGER, COMMUNITY AFFAIRS 
             
             
               MyComp INC 
             
             
               1 MyStreet 
             
             
               MyCity, 12345 
             
             
               PO1LY OBRIEN 
               rejected 
             
             
                 
               not in the dictionary 
             
             
               MANAGER, COMMUNITY AFFAIRS 
             
             
               MyComp, INC 
             
             
               1 MyStreet 
             
             
               MyCity, 12345 
             
             
               MS ME1INDA DUCKSWORTH 
               recognized 
             
             
               MyComp, INC 
             
             
               MAI1 CODE 63-33 
             
             
               1 MyStreet 
             
             
               MyCity, 12345 
             
             
               *********AURO**MIXED AADC 460 
               Rejected, not in the 
             
             
                 
               dictionary 
             
             
               MIK0 SCHWARTZ 
             
             
               O AND T 26-00 
             
             
               1 MyStreet 
             
             
               MyCity, 12345 
             
             
               . . . 
             
             
                 
             
           
        
       
     
   
   If sufficient results are available, the rejected recognition results are transferred to a processing unit  30  and forwarded to the two subprocesses for dictionary training for single words  50  and word groups  60 . In the case of a successful automatic recognition, the results are transferred to a statistics module  40 . When all items have been processed, the word and word group lists  41  of the statistics module and of the dictionary training processes  51 ,  61  are collected and presented to an operator for confirmation by means of a suitable graphical user interface. 
   In the processing unit  30 , irrelevant words in the rejected recognition results are identified which are not taken into consideration in the subsequent text analysis (compare FIG.  2 ). These words are marked as not relevant but are not deleted since the word neighborhood is of importance for the subsequent building up of the dictionary. 
   In the method step marking irrelevant words  31 , short words are marked from the set of word hypotheses, for example those words which are less than 4 letters long and, at the same time, do not have a fullstop, and those, less than 50% of whose characters are alphanumeric. Furthermore, those words are marked which are contained in a special file  32  which contains frequent but irrelevant words for this application. In the application of in-house mail distribution, for example, this special lexicon can contain the company name, city name, street name, post box designation etc. The results of the processing are written back into a buffer  33 . 
   After the preprocessing, the results look as follows: 
   
     
       
             
           
         
             
                 
             
           
           
             
               &lt;title MR&gt; &lt;first-name ALFRED&gt; &lt;last-name SCHMID&gt; 
             
             
               &lt;role EXECUTIVE DIRECTOR OPERATIONS&gt; 
             
             
               PO11Y O/BRIEN 
             
             
               MANAGER, COMMUNITY AFFAIRS 
             
             
               &lt;irrelevant MyComp, INC&gt; 
             
             
               &lt;irrelevant 1 MyStreet&gt; 
             
             
               &lt;irrelevant MyCity&gt; &lt;irrelevant 12345&gt; 
             
             
               PO1LY OBRIEN 
             
             
               MANAGER, COMMUNITY AFFAIRS 
             
             
               &lt;irrelevant MyComp, INC&gt; 
             
             
               &lt;irrelevant 1 MyStreet&gt; 
             
             
               &lt;irrelevant MyCity&gt; &lt;irrelevant 12345&gt; 
             
             
               &lt;title MS&gt; &lt;first-name MELINDA&gt; &lt;last-name DUCKSWORTH&gt; 
             
             
               &lt;non-alpha ********AURO**MIXED&gt; AADC &lt;short 460&gt; 
             
             
               MIK0 SCHWARTZ 
             
             
               &lt;short O&gt; &lt;short AND&gt; &lt;short T&gt; 26-00 
             
             
               &lt;irrelevant MyComp, INC&gt; 
             
             
               &lt;irrelevant 1 MyStreet&gt; 
             
             
               &lt;irrelevant MyCity&gt; &lt;irrelevant 12345&gt; 
             
             
               . . . 
             
             
                 
             
           
        
       
     
   
   According to  FIG. 3 , from the processed rejected recognition results, a frequency list FL  53  of all words occurring there is created in first step  52 , sorted in accordance with descending frequency and stored in a buffer. For the above example, the frequency list FL  53  could look as follows: 
   
     
       
             
             
             
           
         
             
                 
                 
             
           
           
             
                 
               . . . 
                 
             
             
                 
               AFFAIRS 
               37 
             
             
                 
               MANAGER 
               37 
             
             
                 
               COMMUNITY 
               37 
             
             
                 
               OBRIEN 
               20 
             
             
                 
               O/BRIEN 
               17 
             
             
                 
               SCHWARTZ 
               15 
             
             
                 
               MIKO 
               12 
             
             
                 
               POLLY 
               10 
             
             
                 
               PO11Y 
               8 
             
             
                 
               PAULA 
               8 
             
             
                 
               PO1LY 
               5 
             
             
                 
               MIKO 
               3 
             
             
                 
               . . . 
             
             
                 
                 
             
           
        
       
     
   
   From this list, a dictionary W 1  of relevant words  51  is built up step by step. For each word in the frequency list FL  53 , the distance d to all words in this frequency list is determined. One method for measuring the distance between two strings is the Levenshtein method which calculates the minimum distance between two strings referred to 3 cost categories, at the cost of replacing one character, an insertion and a deletion operation. In addition to the string, other features of the recognition result, for example the character alternatives, the segmentation alternatives, etc., can be used for calculating d. 
   The first word in the frequency list FL  53  (the currently most frequent one) is included in the dictionary W 1   51  and deleted  54  from the frequency list FL  53 . All words from the frequency list FL  53  having a distance of less than a predetermined threshold th d  are allocated  55 ,  56  to the current word in the dictionary W 1   51  with their frequency. At the same time, these words are deleted in the frequency list FL  53 . The iteration stops when the frequency list FL  53  is empty. This forms word classes which do not exceed a distance d between each other or, respectively, do not drop below a corresponding similarity factor. 
   When all words have been processed, the dictionary W 1   51  consists of a set of word classes. The shortest word of a word class is called the representative of the group. Each word class contains words which are similar to each other, with the associated frequencies and distances from the class representative. The representatives of word classes in the dictionary W 1   51 , and thus also the word classes, are sorted  57  in accordance with descending frequency. The frequency of a word class is composed of the frequency of the representative and the frequencies of the elements of the word class. Word classes with a frequency which drops below a particular threshold are deleted from the dictionary W 1   51 . In consequence, the following dictionary W 1   51  is formed from the above list: 
   
     
       
             
             
             
             
           
             
             
             
             
           
         
             
                 
                 
             
             
                 
               &lt;Word class&gt; 
               &lt;Frequency&gt; 
               &lt;Distance&gt; 
             
             
                 
                 
             
           
           
             
                 
             
           
        
         
             
                 
               . . . 
                 
                 
             
             
                 
               AFFAIRS 
               37 
             
             
                 
               MANAGER 
               37 
             
             
                 
               COMMUNITY 
               37 
             
             
                 
               OBRIEN 
               37 
             
             
                 
               O/BRIEN 
               17 
               (d = 1) 
             
             
                 
               POLLY 
               23 
             
             
                 
               PO11Y 
               8 
               (d = 2) 
             
             
                 
               PO11Y 
               5 
               (d = 1) 
             
             
                 
               SCHWARTZ 
               15 
             
             
                 
               MIK0 
               15 
             
             
                 
               MIKO 
               3 
               (d = 1) 
             
             
                 
               PAULA 
               8 
             
             
                 
               . . . 
             
             
                 
                 
             
           
        
       
     
   
   The formation of representatives can be supported with further knowledge depending on the application. Thus, a word can be mapped either onto a number or onto an alpha sequence by using OCR replacement tables which define interchangeable pairs of characters such as 1-L, 0-0, 2-Z, 6-G etc. If, in addition, alternative sets for word classes to be learnt are known, for example nicknames for first names such as Paula-Polly, Thomas-Tom, etc., this replacement can also be performed. Both steps can be applied to the dictionary W 1   51  which leads to a further blending of word classes. 
   Finally, all words occurring in the dictionary W 1   51  are marked in the recognition results and supplemented by their representative. In the text which follows these words will be called W 1  words. 
   At the top of the dictionary W 1   51 , the most frequent, previously unknown word forms are located and the word classes contain spelling variants thereof. Thus, in the application of in-house mail distribution, previously unknown first and second names and parts of departmental designations will be in the dictionary W 1   51 . In addition, their word classes contain spelling variants or variants which have arisen due to the characteristics of the reading system. 
   Starting with the representatives of the word classes in the dictionary W 1   51  which are marked as such in the recognition results, word groups of length  2  to n are determined in the next step according to  FIG. 4  in that the neighborhoods of W 1  words of the recognition results  62  are examined. For each W 1  word, the right-hand neighborhood is searched in a window of width k&lt;=n to see whether it contains further W 1  words. n−1 initially empty dictionaries are set up in a buffer and filled step by step. An n-tuple is then included in a word group buffer  53  when n W 1  words have been found and there are fewer than m further non-W 1  words between these n. As in the case of the dictionary W 1   51 , the frequency of occurrence of the individual word groups of length n is stored here, too. 
   The choice of the values of m and n depends on the actual application. For values of n&gt;4, no further significant frequent entries can be expected in the application of reading addresses. m=0 means that all n W 1  words follow one another directly. In the case of pairs of first and last names, however, in particular, a second name can occasionally interrupt the direct succession, just as segmentation errors of the automatic reader can generate supposed word hypotheses and thus prevent a direct succession. In consequence, m=1 and n=3 are suitable values for the application described. In this step, in consequence, n−1 dictionaries Wn  61  containing frequent word sequences with the frequencies for pairs, triplets etc. up to n-tuple are generated from the word group buffer. In each dictionary Wn  61 , the frequencies of the n-tuples are included with the frequencies of the W 1  words of the n-tuples to calculate a dimension. Each dictionary Wn  61  is sorted in accordance with descending dimensions so that the most significant word groups are again at the beginning of each dictionary Wn  54 . 
   For the above example, the dictionary W 2  looks as follows: 
   
     
       
             
             
           
             
             
             
           
         
             
                 
                 
             
             
                 
               W2 
             
             
                 
                 
             
           
           
             
                 
             
           
        
         
             
                 
               COMMUNITY AFFAIRS 
               37 
             
             
                 
               MANAGER COMMUNITY 
               37 
             
             
                 
               POLLY OBRIEN 
               23 
             
             
                 
               MIK0 SCHWARTZ 
               15 
             
             
                 
               PAUL OBRIEN 
               8 
             
             
                 
                 
             
           
        
       
     
   
   The dictionary W 3  has 3 entries provided that the name POLLY OBRIEN always occurs in combination with the designation MANAGER COMMUNITY AFFAIRS and that a line break is allowed in an n-tuple.: 
   
     
       
             
             
           
             
             
             
           
         
             
                 
                 
             
             
                 
               W3 
             
             
                 
                 
             
           
           
             
                 
             
           
        
         
             
                 
               MANAGER COMMUNITY AFFAIRS 
               37 
             
             
                 
               POLLY OBRIEN MANAGER 
               23 
             
             
                 
               OBRIEN MANAGER COMMUNITY 
               23 
             
             
                 
                 
             
           
        
       
     
   
   As described, the word proposals of the dictionaries Wn  61  (W 2 , W 3 , etc.) are now presented to an operator for validation according to FIG.  5 . Knowledge about the word units  72  to be learnt makes it possible at this point to categorize  71  entries in the dictionaries W 1 , W 2 , . . . Wn  51 ,  61  semantically. Thus, in this application, entries can be allocated to the semantic class &lt;Name&gt; by looking at generally applicable lists of first names. This similarly applies to the semantic class &lt;Department&gt; which can be derived from keywords such as Department. Naturally, this process can also be carried out automatically without an operator by comparison with the entries of these lists. 
   For items successfully distributed, the address elements required for this have been found and are identified as such in the recognition results. If, for example, last name and first name have been successfully read in the application of the in-house mail distribution, these results are registered in statistics; in particular, the frequency of the extracted words, pairs, generally of in-tuples over defined time intervals td, e.g. for a week, are stored and it is possible to take into consideration the type of item. As a result, a distribution of the address elements to be extracted for a sequence of time intervals is obtained: 
   
     
       
             
             
             
           
         
             
                 
                 
             
           
           
             
                 
               Time 1 
                 
             
             
                 
               MELINDA DUCKSWORTH 
               123 
             
             
                 
               ALFRED SCHMID 
               67 
             
             
                 
               . . . 
             
             
                 
               Time 2 
             
             
                 
               MELINDA DUCKSWORTH 
               1 
             
             
                 
               ALFRED SCHMID 
               85 
             
             
                 
               . . . 
             
             
                 
               Time 3 
             
             
                 
               MELINDA DUCKSWORTH 
               2 
             
             
                 
               ALFRED SCHMID 
               72 
             
             
                 
               . . . 
             
             
                 
                 
             
           
        
       
     
   
   From the distribution thus found, it is possible to derive whether dictionary entries are to be deleted: the entries are inserted into a list for removal from the dictionary if their frequency abruptly decreases from td i  and stays at this level in successive time intervals td i+k  (e.g. k=4). Thus, the person MELINDA DUCKSWORTH in the above example is deleted from the dictionary. This sequence can also be additionally conducted via a confirmation process.