Abstract
Logical structure analysis of document images is an important problem in document image understanding. In this paper, we propose a graph matching approach to label logical components on a document page. Our system is able to learn a model for a document class, use this model to label document images through graph matching, and adaptively improve the model with error feedback. We tested our method on journal/proceeding article title pages. The experimental results show promising accuracy, and confirm the ability of adaptive learning.
Introduction
While Optical Character Recognition (OCR) technology has matured significantly, it typically produces an "unstructured text stream"—a collection of words and coordinates lacking semantic context. To transform these pixels into actionable data, systems must identify the logical role of each text block, such as distinguishing a title from an author list or an abstract. This paper presents a robust framework for logical labeling using layout graph matching combined with an adaptive learning mechanism to bridge the gap between raw OCR output and structured document understanding.
System Architecture
The proposed system follows a modular pipeline designed to handle the transition from physical layout to logical structure. As shown in Figure 1, the process begins with image segmentation and OCR, producing a physical XML representation (PHY-XML). This data is then processed by a matching engine that utilizes a model base to generate a logical XML output (LOG-XML). A critical component of this architecture is the feedback loop: verification of the results allows for model learning, where the system adaptively updates its model base to improve future labeling accuracy.
Layout Representation and Matching
The core of the labeling process involves representing document layouts as Attributed Relational Graphs (ARGs). In these graphs, nodes represent segmented text blocks with attributes like position, size, and normalized font size. Edges represent spatial relationships, such as "above," "left-of," or "aligned."
Matching a candidate page to a model is treated as an approximate graph matching problem. The system employs a two-step approach:
- 1-1 Matching: An efficient branch-and-bound search finds the optimal initial mapping between candidate blocks and model nodes.
- N-1 Grouping: To address over-segmentation—where one logical unit is split into multiple physical blocks—the system groups unmatched candidate blocks into existing matches based on spatial constraints.
As illustrated in Figure 2, this approach allows the system to map specific physical zones (e.g., Zone 1 and Zone 2) to their respective logical roles (e.g., Title and Author) defined in journal-specific or general logical schemas.
Adaptive Learning
The system's "adaptive" nature stems from its ability to refine models based on user feedback. When a labeling error is identified, the system compares its output to the ground truth and adjusts the model's feature biases (such as expected block dimensions). Furthermore, it modifies the weight factors of spatial relationships; if a specific relationship led to a mismatch, its weight is increased to prioritize that constraint in future matching cycles.
Experimental Results
The methodology was evaluated using a dataset of 80 title pages from four academic journals (CHI '95, CHI '96, PAMI, and UIST '95). Key findings include:
- Error Reduction: The adaptive learning mechanism proved highly effective, reducing average labeling error rates by 30% after only ten training cycles.
- Efficiency: The branch-and-bound strategy ensured high performance, with the graph matching process completing in less than one second per page.
- Robustness: By supporting N-1 mappings, the system successfully handled inconsistencies common in standard OCR engines.
Conclusion
This research demonstrates that a structure-based graph matching approach, enhanced by adaptive learning, provides a flexible and efficient solution for document logical labeling. By focusing on global spatial relationships rather than just local features, the system achieves high accuracy and resilience, paving the way for more sophisticated automated document processing workflows.
Summary updated