In 1986, document analysis was at a crossroads. While Optical Character Recognition (OCR) could translate pixels into characters, machines lacked the "common sense" to understand the logical structure of a page. A block of text was just a block of text; the computer couldn't distinguish a title from a footnote or a destination address from a return address. This paper introduces a hierarchical, rule-based framework designed to bridge this gap between raw image processing and high-level document interpretation.
The Challenge of Logical Structure
The core problem addressed is "document understanding"—the task of identifying the functional roles of different regions within a document. For instance, in a journal article, the system needs to recognize the title, authors, abstract, and body text. In the context of postal mail, it must isolate the destination address block amidst stamps, logos, and advertising text.
The authors argue that low-level image processing alone is insufficient. Instead, they propose a top-down approach where domain-specific knowledge guides the analysis. By using a "hypothesize-and-test" strategy, the system makes an initial guess about a region's identity and then chains backward through rules to find supporting evidence.
A Three-Level Rule Hierarchy
The system's intelligence is encoded in a three-level hierarchy of rules, implemented in Prolog to leverage its symbolic reasoning capabilities:
- Knowledge Rules: These describe the physical and spatial characteristics of document components. For example, a rule might state that a "title" is typically located near the top of a page and consists of large, bold characters.
- Control Rules: These manage the "focus of attention." They dictate which knowledge rules should be applied and in what order to test a specific hypothesis about a document block.
- Strategy Rules: These oversee the high-level search process. They determine the overall approach and decide when a consistent and confident interpretation of the entire document has been achieved.
To handle the inherent "fuzziness" of real-world documents—where ink might be smudged or layouts slightly off—the authors integrated Certainty Factors. Each rule that successfully fires adds a confidence value (ranging from 0 to 1) to the hypothesis. This allows the system to weigh competing interpretations and select the most probable one.
Evaluation: Mail-Pieces and Journals
The primary testbed for this system was the analysis of complex postal mail-pieces. These envelopes often contained "non-standard" layouts that baffled the OCR machines of the mid-80s.
Beyond mail, the authors demonstrated the framework's flexibility by applying it to journal cover pages. By simply swapping the rule sets, the same engine could adapt to a completely different document domain. This demand-driven approach meant that expensive image processing operations were only invoked when necessary to confirm a specific hypothesis.
Results and Legacy
Running on a VAX-11/780, the system achieved an accuracy rate of over 80% in identifying key components on complex mail-pieces. It processed images at a rate of approximately one per second—a significant feat for the era.
The paper's lasting contribution lies in its separation of document description (knowledge) from the analysis process (control/strategy). This modularity made the system extensible and paved the way for more sophisticated spatial reasoning in document analysis. While the authors noted limitations in rule interaction and the need for more robust uncertainty modeling, this work remains a foundational example of applying artificial intelligence to the physical world of paper documents.
Summary updated