WO1997038394A1

WO1997038394A1 - Method of automatically evaluating an address indicated on a document after the conversion of this address into digital data

Info

Publication number: WO1997038394A1
Application number: PCT/DE1997/000554
Authority: WO
Inventors: Hans-Ulrich Block; Thomas BRÜCKNER
Original assignee: Siemens Aktiengesellschaft
Priority date: 1996-04-03
Filing date: 1997-03-18
Publication date: 1997-10-16
Also published as: EP0891599A1; JP2000508100A

Abstract

In order to recognize and evaluate the character string in an address and allocate the address to an addressee, the character string of the address is compared with stored patterns which contain a distinct address identification for each addressee. The pattern which is most similar to the address character string is selected. This is effected in that a displacement measure is formed which defines the similarity between the address and the pattern and this displacement measure is examined to see whether it is above or below a predetermined threshold. If the displacement measure is below the predetermined threshold, the addressee associated with this pattern is fetched out.

Description

description

Method for the automatic evaluation of an address applied to a document after its transformation into digital data

From [1] a system is known with which, for. B. Business letter documents can be categorized and then forwarded in electronic or paper form, or can be stored in a targeted manner. For this purpose, the system contains a unit for layout segmentation of the document, a unit for optical text recognition, a unit for address recognition and a unit for content analysis and categorization. For the segmentation of the document, a mixed bot-up and top-down approach is used, which as the individual steps

Detection of the related components,

• recognition of text lines,

• recognition of the letter segments, • recognition of the word segments and

• Detection of paragraph segments included.

Optical text recognition is divided into three parts:

• letter recognition in combination with lexicon-based word verification,

• Predictive text, with letter classification and word-based recognition.

The address recognition is carried out with a unification-based parameter that works with an attributed context-free grammar for addresses. Parts of the text that are correctly parsed in the sense of the address grammar are accordingly addresses. The contents of the addresses are determined using equations of the grammar. The procedure is described in [2]. Information retrieval techniques for automatic indexing of texts are used for content analysis and categorization. The details are as follows:

• Morphological analysis of the words

• Elimination of stop words

• Creation of word statistics

• Calculation of the index term weight using formulas known from Information Retrieval, such as B. the inverse document frequency.

Using the index term weights thus calculated, a three-level list of significant words is now determined for all categories, which characterizes the respective category. As described in [1], these lists are still manually revised after the training phase.

A new business letter is then categorized by comparing the index terms of this letter with the lists of significant words for all categories. Depending on the significance, the weights of the index terms contained in the letter are multiplied by a constant and summed up. By dividing this sum by the number of index terms in the letter, there is a probability for each class. The exact calculations result from [3].

The result of the content analysis is then a list of hypotheses sorted according to probabilities. The runtime of the content analysis is specified between half a second and two seconds of CPU time with a maximum number of 75 index terms per letter.

The object on which the invention is based is to specify a method by which the address recognition and address evaluation is improved. It is assumed that the address of the document already exists as digital data, which are then processed further. This object is achieved in accordance with the features of patent claim 1.

Further developments of the invention result from the dependent claims.

The method according to the invention is based on the technique of approximate string matching. For this purpose, the method described by Bertossi et al in [4] is used, which compares a word with a pattern and calculates the number of confusions, omissions and insertions of letters in the word.

From the set of patterns m, the pattern is selected which most closely corresponds to the word w to be examined. A similarity or distance measure d is required for the two words, the pattern m and the word w to be examined. The absolute number of errors is not suitable for this, since the patterns can be of different lengths. This problem can be shown using examples:

1st example

The pattern is ml = ^, AUT ' _/ the word to be examined is wl =' ABT '.

2nd example

Let the pattern be m2 = 'Med. Technik 'and the word to be examined w2 =' MCD, Tecfnik ', whereby' Med. Technology 'e.g. B. should be the abbreviation for medical technology.

For both examples, the average error rate is

Number of errors length (m)

equal. It is namely 1/3 in the first example and 4/12 in the second example, that is to say 1/3 each, so that the distances are equal. Obviously, w2 is more similar to m2 than wl to ml. The explanation for this becomes clear if the calculation of the distance between a pattern and a word to be compared is interpreted as a reconstruction problem. Then the distance between m and w is smaller, the easier the pattern you are looking for can be reconstructed from the word w or can be recognized. However, this is generally easier for longer words, even with many errors, because less correct words can be formed from longer, error-prone words. It follows that the average reconstruction information of a letter decreases with the length of a word.

However, the reconstruction information of a letter is not a calculable measure. Therefore, according to the invention, the Markov entropy H-y- (N) is used as a model for this.

Markov's entropy is defined as the average information of a letter in a word, depending on the length N of the word. Although this entropy cannot be calculated for all N (for example, for N = 10 there are already K --- 0 possible combinations of K letters to be distributed over a word of length N), but for some N there are values in [4], which clearly reflect the course of the function of Markov's entropy. Interpolation with these values gives an estimate φ (Hjy- (N)) for Markov's entropy, which can be used to define the distance measure d-j_ _n f, namely:

ew • Φ (H _M (N)) d _inf (m, n): =,

N

where ew is the number of errors in the word to be examined w.

The invention is further explained on the basis of an exemplary embodiment which shows a system according to the invention for evaluating an address applied to a document. Show it

1 shows a system with which the address is recognized and evaluated on a paper document, 2 shows a more precise representation of the system for evaluating the address.

In the figures, units of the system with rectangles and results of activities of the units with circles are shown.

A paper document Dok is scanned by a scanner SC and an image file BD is generated. With the help of a method known from European patent application 0 515 714 A1, the part of the image which contains the address is segmented. The layout segmentation is designated SG in FIG. 1. The result is an image file that only contains the address part A-SG of the document. This image data of the address is converted into ASCII data using OCR.

The address in ASCII data is named in Fig. 1 ADR. As a rule, the ASCII address file ADR still contains errors, so that by comparing this address file with stored patterns it is often not possible to identify the addressee uniquely. In Figure 1, the address recognition is designated ADR-E, a

File with patterns m with MU. In addition to the patterns m, the file can contain the addressees assigned to these patterns, both of which can be contained in a memory. As a result of the comparison with the patterns m, the address recognition ADR-E emits an address hypothesis for each pattern, which is called ADR-H and which represents the measure of the similarity.

In order to achieve a robust and fault-tolerant analysis of addresses, the technique of "approximate string matching" is used in the exemplary embodiment. For this purpose, the method described by Bertossi 14] is used, which compares a word with a pattern and the number of mix-ups, omissions and insertions of letters is calculated in accordance with Fig. 2 in the unit MA to which the address ADR in ASCII code and the pattern m are supplied one for every possible addressee Set of unique addressee names. In the unit MA, the patterns m to m _n are thus compared with the address ADR, that is, they are determined and a hypothesis ADR-H is formed for each pattern, that is, the most similar word (hypothesis) is determined in the address for each pattern. In order to be able to select the pattern that is most likely to be contained in the address, the distance measure ° -inf is used for each pair of pattern-hypotheses according to the above formula for the similarity of two

Strings calculated. This is done in the unit distance calculation DIST. Such a distance calculation is carried out for each of the patterns and determined from the result of this calculation, the distance dimensions di _n fi to di _n f _{n /} the minimum and further processed as di _n f _m - [ _n . If a threshold value SW that is to be predefined is smaller than five, then the result of the address recognition is the address belonging to this pattern from the database MU. Otherwise no statement is made about the addressee.

This sequence results from FIG. 2, in which the individual steps are shown. Patterns and the corresponding addressees are stored in one unit (memory). The hypotheses for the individual patterns are contained in ADR-H, in the unit DIST the distance measurement is carried out for each

To identify patterns in comparison to the address to the individual Diεtanzmaße ό-i _n fi to dinfn that wer¬ stored in the DIST. The distance dimensions d ^ _n fi are fed to a unit MIN for miniature calculation, which determines the minimum dinf ^ r- _j and subjects it to a threshold value check SW. The threshold value check SW rejects an address as unassignable if d is above the threshold value, this is shown with rw, otherwise the addressee ADR-A corresponding to the pattern is issued. bibliography

[1] A. Dengel et al. 'Office Maid- A System for Office Mail Analysis, Interpretation and Delivery', Int. Workshop on Document Analysis Systems (DAS) $), Kaiserslautern (1994), p 253-275.

[2] M. Malburg and A. Dengel, 'Address Verification in

Structered Documents for Automatic Mail Delivery ', Proc. JetPoste 93, First Europaen Conference on Postal Technologies, Vol. 1, Nantes, France (1993), pp. 447-454.

[3] R. Hoch, 'Using IR Techniques for Text Classification in Document Analysis', Proc. of 17th International Conference on Research and Development in Information Retrieval (SIGIR94), Dublin, Ireland, (1994). [4] A. A. Bertosεi, F. Luccio, E. Lodi and L. Pagli, 'String Matching with Weighted Errorε', Theoretical Computer Science 73, (1990), pp. 319-328.

Claims

claims

1. Method for the automatic evaluation of an address applied to a document after its transformation into digital data,

In which unique address designations are stored in a memory for each addressee as a pattern (m),

In which the pattern is compared with the character string of the address and the differences between patterns and the address are calculated as a distance measure,

In which the pattern is selected which is most similar to the address string,

• in which only one address assigned to the selected pattern is selected if the distance measure falls below a predetermined threshold.

2. The method as claimed in claim 1, in which the differences between the address and the pattern are determined to determine the distance measure and the distance measure is determined on the basis of the length of the character string and the differences via the Markovian entropy.

3. The method according to claim 2, wherein the determination of the distance measure according to the formula

ew • Φ (H _M (N)) di _n f (m, n): =

N

takes place, where ew is the number of errors in the character string w, N is the length of the character string and φ is an estimate determined by interpolation.

4. The method according to claim 3,

In which the address is compared with the stored patterns using the approximate word equality method, in which a hypothesis is formed for each pattern that contains the number of differences between the address and the pattern, The distance measurements for each pattern are determined from the hypotheses,

• where the minimum is determined from the distance measurements,

• in which the minimum of the distance measurements is compared with a threshold value and the address is rejected if the threshold value is exceeded, otherwise the addressee assigned to the pattern is given from a database.