Abstract:
A word shape token-based document classification system prepares a plurality of sets of training data degraded by image quality and selects the optimum training data set by examining scores from a relevance measurement. The system achieves high accuracy from a wide range of image quality.

Description:
BACKGROUND OF THE INVENTION 
     1. Field of Invention 
     The present invention relates to a method and apparatus for document classification and, more particularly, to a method and apparatus for classifying a document according to language and topic. 
     2. Description of Related Art 
     Optical character recognition and the use of optical character recognition to convert scanned image data into text data suitable for processing by a digital computer is well known. In addition, methods for converting scanned image data into text data and the types of errors such methods generate are well known. However, the selection of a proper method for error correction is highly dependent upon the language of the document. 
     Methods for optical character recognition and for error correction in optical character recognition systems have been provided on the assumption that the language used in the document was known in advance or assumed to be in the language of the country in which the system is being used. That is, in the United States, conventional optical character recognition systems assume that the document is in English. Alternately, an optical character recognition system can be implemented with character recognition and error resolution methods for a plurality of languages. 
     An optical character recognition system has been developed that automatically determines the language of a document. The system generates word shape tokens from an image of the text and determines the frequency of the word shape tokens that corresponds to a set of predetermined word shape tokens. The system then converts the frequency of appearance rates to a point in a new coordinate of space and then determines which predetermined language region of the new space coordinate the point is closest to and thereby determines the language of the text. However, this system has not been able to achieve high accuracy because it does not appreciate the quality of the document image. 
     Another system has been developed that categorizes documents into topic categories. This system generates word shape tokens representing words appearing in the document. This system eliminates certain unimportant word shape tokens and ranks the remaining word shape tokens according to their frequency of appearance. These frequencies are then used to categorize the document as being written on a specific topic. However, this system also has not been able to achieve high accuracy because it also does not appreciate the quality of the document image. 
     Therefore, it has not been possible to achieve high accuracy in topic or language categorization of documents because of the wide range of document image quality. 
     SUMMARY OF THE INVENTION 
     The present invention is a word shape token-based document classification system that achieves high accuracy across a wide range of image quality. The system prepares a plurality of sets of training data that have been degraded by image quality. The system selects the optimum training data set by examining scores from a relevance measurement. The system consists of three main portions: word shape token generation, language classification and topic classification. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     The invention is described in relation to the accompanying drawings, in which: 
     FIG. 1 is a block diagram of training data set selection by relevance measurement of the present invention; 
     FIG. 2 is a flow chart of the topic and language classification system of the present invention; 
     FIG. 3 shows the abstract coded character classes or character shape codes and the derived word shape tokens and their correspondence to the actual text portion of a document; 
     FIG. 4 is a block diagram of the language classification section of the present invention; 
     FIG. 5 is a block diagram of the topic classification section of the present invention; and 
     FIG. 6 is a block diagram showing three degrees of degradation of a document image. 
    
    
     DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS 
     As shown in FIG. 1, the system of the present invention receives as input a document image 10 of unknown quality. The system then performs a relevance measurement 12 to determine which of a plurality of training data sets 14 will provide the most accurate classification of the document. The plurality of training data sets 14 vary in image quality. 
     In FIG. 2, a flow chart shows one method of language and topic classification as performed by the system of the present invention. The document image 10 is derived from a scanner or other conventional input device. Word shape tokens are then generated at step 20. These word shape tokens may be generated by a conventional system, such as described in U.S. Pat. No. 5,375,176, issued Dec. 20, 1994, assigned to the same assignee as the present invention and incorporated herein by reference. 
     The system then performs language classification at step 30 using the relevance measurement described below along with a conventional language classification system, such as described in U.S. Pat. No. 5,377,280, issued Dec. 27, 1994, assigned to the same assignee as the present invention and incorporated herein by reference. The present invention utilizes the language classification system after it determines the most relevant language profile 40. A language classification result 50 is then output. 
     The result of the language classification 30 may then be used to perform topic classification 60. The topic classification utilizes the relevance measurement system described below along with a conventional topic classification system, such as described in U.S. Pat. No. 5,526,443, assigned to the same assignee as the present invention and incorporated herein by reference. The system then generates a topic classification result 70. 
     The present invention may be implemented with a conventional general purpose digital computer. It is of course understood that a special purpose digital computer or hard wired logic circuit can be used in place of a general purpose digital computer. 
     FIG. 3 shows the text portion 16 of a document image prior to conversion and the word shape tokens 18 after conversion using the coding scheme disclosed, for example, in U.S. Pat. No. 5,375,176. 
     Looking now to FIG. 4, the word shape token generator 20 prepares a sequence of word shape tokens 22 that represent words in the document. The language classification system 30 uses this sequence of word shape tokens 22 to classify the input document as being written in a specific language and also may forward the sequence of word shape tokens along with a language tag 32 that identifies the language in which the input document is written. 
     The language classification system prepares plural sets of language training data 33. Each language training data set comprises a plurality of language profiles 34. At least one of the language training data sets is degraded in image quality. 
     Using the sequence of word shape tokens 22, the system computes the relative frequencies of each word shape token in the document to compare them with the relative frequencies in the language training data sets. The system uses a statistical method (e.g., linear discriminate analysis, vector space model, and so forth) that gives scores that indicate the degree of relevance of the input sequence to each language training data set. 
     In a first preferred embodiment, the system merges all the language profiles in each language training data set, computes the relative frequencies of word shape tokens for each merged language profiles and the input document, compares these relative frequencies using a statistical method, and uses the language training data set having the most relevant merged language profiles. The language is then determined using the selected language training data set in a conventional manner. 
     In a second embodiment, the conventional language classification is performed on all language training data sets. A score indicating the degree of similarity between the relative frequencies of the word shape tokens of the language profile to the document is calculated. The highest score is selected and the document is classified as being written in the language corresponding to the language profile with the highest score. 
     In a third embodiment, the system first performs conventional language classification across all language training data sets. The relative frequencies of word shape tokens for all language profiles and for the document are computed. Then a score indicating the degree of similarity of the relative frequencies for each language profile to those of the document is calculated. Then for each language training data set a proportion of the highest score over the second highest score is computed. The language training data set having the highest proportion is selected and the language profile having the highest score within the selected language training data set is determined to be written in the language in which the input document is written. 
     Referring back now to FIG. 2, after the language classification 30 has been performed, the system may continue processing to determine the topic about which the document is written, at step 60. FIG. 5 shows a block diagram indicating the processing performed by the system in classifying the document by step 60. The system prepares topic training data sets 61 derived from a topic reference data set in several different languages. Within each language at least one topic training data set is derived from a degraded image of the topic reference data set. The system then uses the language tag 32 to identify a plurality of topic training data sets 62 that are written in the language indicated by the language tag. The system then processes the identified plurality of topic training data sets 62 according to one of the following embodiments. 
     In a first embodiment, all topic profiles in each identified topic training data set are merged. Then the relative frequencies of stop tokens are computed for each merged topic profile and the document. The system then uses a statistical method to compare the relative frequencies and select the merged topic training data set having relative frequencies of stop tokens that are the most similar to the document to select one of the identified topic training data sets. The selected topic training data set is then used for conventional topic classification as disclosed in U.S. Pat. No. 5,526,443, for example. 
     In an alternative embodiment, conventional topic classification is performed on each of the plurality of identified topic training data sets. The relative frequencies of stop tokens for each topic profile in the identified topic training data sets and the document are calculated and a score is also calculated that indicates the degree of similarity between the relative frequencies of each topic profile and the document. The topic profile having the highest score is selected and the document is then classified as being written on the topic of the selected topic profile. 
     An alternative to this embodiment first uses the calculated scores to calculate a proportion for each identified topic training data set. The proportion is the highest score divided by the second highest score. The topic training data set having the highest proportion is then selected and the topic profile within the selected topic training data set is selected as indicating the topic on which the document is written. 
     In a further embodiment, the identified topic training data set is selected based upon knowledge gained about the quality of the document image during the language classification stage. During the language classification stage, a language training data set derived from a language reference data set having a certain image degradation is identified. In the topic classification stage the identified topic training data set derived from a topic reference data set having a similarly degraded image is selected and is used to classify the document in a conventional manner. 
     In a preferred embodiment of the present invention, the relevance measurement relies upon the relative frequencies of word shape tokens to generate a document profile. The document profile D i  is represented as a vector of numeric weights, D i  =(W i1 , W i2 , . . . , W ik , . . . , W it ), where W ik  is the weight given the kth word shape token in the ith document, and t is the number of distinct word shape tokens in the ith document. The weight is a number between 0 and 1 and indicates the frequency of the word shape token relative to other word shape tokens. The system then measures the degree of similarity between two document profiles using a cosine function to compute the similarity between two documents, D i  and D j  : ##EQU1## 
     This equation generates a score that indicates the degree of similarity between the documents D i  and D j . The larger the value the greater the similarity between the two documents. 
     Stop tokens are used in the topic classification process rather than all word shape tokens because of the increased accuracy demonstrated by empirical results. In one particular experiment, the Applicant used the five most common word shape tokens as stop tokens and also evaluated the topic classification system using all word shape tokens. In the latter method, 349 of 600 images were assigned to the appropriate topic training profile, while in the former method 497 of 600 images were correctly assigned to the appropriate topic training profile, thereby showing an improvement in the accuracy of topic classification through the use of stop tokens. 
     Accuracy may also be improved with careful selection of stop tokens. By selecting a small number of stop tokens the system will perform the necessary computations much more quickly because the vector dimension is very limited. In the above described experiment, five dimensional vectors were used with the five stop tokens and about 18,000 dimensional vectors were used in the other method. 
     While this invention has been described with the specific embodiments outlined above, many alternatives, modifications and variations are apparent to those skilled in the art. Accordingly, the preferred embodiments described above are illustrative and not limiting. Various changes may be made without departing from the spirit and scope of the invention as defined in the following claims.