Abstract
We present a framework to analyze color documents of complex layout. In addition, no assumption is made on the layout. Our framework combines in a content-driven bottom-up approach two different sources of information: textual and spatial. To analyze the text, shallow natural language processing tools, such as taggers and partial parsers, are used. To infer relations of the logical layout we resort to a qualitative spatial calculus closely related to Allen's calculus. We evaluate the system against documents from a color journal and present the results of extracting the reading order from the journal's pages. In this case, our analysis is successful as it extracts the intended reading order from the document.
Introduction
Modern document analysis faces significant hurdles when dealing with complex, multi-column layouts typical of magazines and scientific journals. While humans intuitively navigate these structures, automated systems often struggle to move beyond physical layout extraction (identifying boxes) to logical structure reconstruction (determining reading order). Traditional "top-down" approaches rely on rigid templates, which fail when faced with non-standard or creative designs. This paper proposes a "bottom-up" framework that integrates qualitative spatial reasoning with shallow Natural Language Processing (NLP) to reconstruct the logical flow of a document without prior layout assumptions.
Methodology
The proposed framework operates through three integrated layers, moving from raw physical data to logical connectivity.
1. Layout Extraction
The process begins by identifying document objects—text lines, boxes, and images—along with their physical attributes such as coordinates, color, and font. This stage provides the raw geometric data required for subsequent analysis.
2. Spatial Inference
To model the geometric relationships between these objects, the system treats every text block as a rectangle. It employs the Rectangle Model, an extension of Allen’s Interval Calculus. This calculus defines 13 possible relations (e.g., precedes, meets, or overlaps) across both the X and Y axes. By applying these constraints, the system generates a set of geometrically "admissible" reading orders. This is implemented as a constraint satisfaction problem using a Prolog-based solver (ECLiPSe).
3. Linguistic Analysis
Spatial reasoning alone often results in multiple valid geometric paths. To disambiguate these, the system uses "shallow" NLP. By examining the transition between text blocks—checking if a block ends with a hyphenated word or a fragment that is grammatically completed by the next block—the system validates the logical connection. This is achieved using a part-of-speech tagger (LTPOS) and a finite-state parser (CASS) to ensure grammatical "well-formedness" without requiring deep semantic understanding.
Evaluation and Results
The researchers evaluated the framework on two primary sources:
- CACM (Communications of the ACM): A color journal known for elaborate, multi-column layouts and varied font styles.
- MTDB (MediaTeam Document Database II): A collection of 206 document images providing a diverse set of real-world layouts.
The results highlight the synergy between the two methods. On the MTDB dataset, spatial inference alone uniquely identified the reading order for 137 documents. In more complex cases from the CACM, where spatial rules suggested up to 24 possible orders, the linguistic component successfully eliminated incorrect sequences, leaving only the single, correct reading path intended by the author. Furthermore, the system proved computationally efficient, with spatial inference typically executing in under 0.1 seconds on standard hardware of the era.
Discussion and Future Work
The integration of geometry and grammar provides a robust solution for document analysis, proving that "shallow" NLP is surprisingly powerful for structural disambiguation. However, the authors identify a "semantic gap": if a text block ends with a full sentence and the next starts with a capital letter, shallow NLP cannot determine if they belong together. This would require deep semantic analysis to match topics. Future work will also investigate "locality principles" to maintain computational efficiency as document density increases, ensuring the system scales to even more complex graphic designs.
Summary updated