Data Retrieval and the Realities of Document Conversion

1.0. Motivation

These problems will not be trivial to solve. Electronic documents produced by scanning and OCR, even under ideal circumstances, can contain ten to twenty recognition errors per page of text, and significantly more if the document image is in some way degraded. OCR errors are especially prevalent in documents having some image quality problems, such as discolored backgrounds and faded ink due to aging in paper documents, and noise and low contrast in microfilm documents. Those particular documents may then become inaccessible using conventional retrieval on their OCR results.

Another important area that needs considerable attention is that of converting non-text portions of documents, e.g., images, graphs, diagrams and tables, into retrievable electronic form. Conventional OCR is of no use in accessing text in these portions of documents. Retrieval methods are also required for non-textual contents.

A third area that has gotten relatively little attention is the conversion of hand-written documents. Although these are obviously much harder than machine-printed documents, they are still important, especially in dealing with historical records.

Our research group at the Environmental Research Institute of Michigan ERIM has been pursuing a number of different research efforts that address these data conversion problems. All of these efforts have in common an emphasis on inexact matching. In other words, we build all our databases and indexes under the assumption that there will be errors that prevent perfect matches, and that our systems need to deal with this reality. We feel that application of inexact matching techniques is crucial to accessing the products of large-scale document conversion projects.

2.0. N-Gram-Based Inexact Matching

We have been working with several N-gram-based representations of documents which have advantages in different cases. One method uses super-imposed coding techniques to produce compact indexes for fast retrieval of sub-documents given a query string [Cavnar92], [Cavnar93]. Another approach uses N-gram frequency statistics to characterize a document for matching purposes [Cavnar94]. Both methods are active research areas at this time.

3.0. Oversegmentation-Based Word Matching

In February, 1994, a more advanced version of this technology was used in a competitive test of handwritten OCR systems conducted by NIST for the Census Bureau. In the test, 9000 occupation fields from 1990 census forms were processed. The system used a lexicon of 8000 occupation-related words and phrases containing the correct response for 62% of the 9000 fields. The remaining fields contained responses which were not present in the lexicon. Using a confidence-based rejection criterion, the ERIM system was able to recognize 40% of the fields with a 3.6% error rate. An error was counted if the response differed from the correct response in any fashion. The average field contained less than one character error. ERIM's system was the most accurate of the eight systems tested, with error rates significantly lower than the nearest competitor.

More recently, ERIM has demonstrated a system for keyword-based retrieval of documents from a handwritten document database. The system makes use of the oversegmentation technology to prepare documents for entry into the database. The operator can query the database for documents containing key words or phrases. The system presents the operator with an image of the retrieved documents, allowing for verification and perusal of document contents. This technique is also applicable to recognizing machine-printed text. Currently, we are employing the oversegmentation-based matching in recognizing machine-printed Arabic words. This work is in progress, but is already showing very promising results.

4.0. Image-Based Retrieval

References