TL;DR
Researchers compared two graph-based machine learning methods—Conditional Random Fields (CRF) and a novel Edge Convolutional Network (ECN)—to automate row detection in messy, handwritten historical death registers. Both approaches achieved an impressive ~89 F1 score, but the ECN-based method proved to be significantly faster and more scalable for large-scale digitization projects.
What Problem Does This Paper Address?
Historical archives are filled with "register books" (census data, death records, etc.) that organize information in tables. While modern OCR can read text, it often fails to understand the structure of these tables, especially when they are handwritten.
The challenge is that historical tables rarely follow strict rules:
- Inconsistent Layouts: Different scribes have different styles; some cram data into one line, while others spread a single record across several.
- Missing Visual Cues: Physical lines (separators) are often missing, hand-drawn poorly, or not recognized by software.
- Alignment Issues: Cells aren't always perfectly aligned horizontally, and "ditto" marks are frequently used, making it hard to tell where one record ends and the next begins.
The authors focus specifically on row detection—the "holy grail" of table understanding for these documents, as records are organized by row.
Methods
The authors treat the document as a graph problem. Each detected text line is a "node," and "edges" are created between neighboring lines based on their horizontal or vertical overlap.
To solve the row detection problem, they borrow a concept from Natural Language Processing called BIESO tagging. They categorize every text line as:
- Beginning of a cell
- Inside a cell
- End of a cell
- Singleton (a single-line cell)
- Outside the table
They compared two primary machine learning architectures:
- Graph Conditional Random Fields (gCRF): A traditional structured learning approach that excels at modeling dependencies between labels.
- Edge Convolutional Networks (ECN): A novel extension of Graph Convolutional Networks (GCNs). Standard GCNs often struggle because they assume neighbors should have the same label. The authors' ECN uses edge features (like the distance between lines or their justification) to learn which neighbors are actually relevant, allowing the network to "filter" the graph dynamically.
Datasets
The study used the ABP_S_1847-1878 dataset, which contains death records from the Diocese of Passau, Germany.
- Dataset 1: 144 manually annotated pages (37,769 text lines) used for training and 4-fold cross-validation.
- Dataset 2: A 150-page "real-world" test set from 15 different books to evaluate the entire automated workflow (from raw image to final row detection).
Key Insights and Ideas
- Edges Matter More Than Nodes: In a surprising "aha moment," the researchers found that discarding node features (like the width/height of a text box) only dropped accuracy by 1%. However, discarding edge features (the relationship between boxes) caused accuracy to plummet to 0.33. This proves that table structure is defined by the space between elements, not just the elements themselves.
- NLP Techniques Work for Vision: Applying BIESO tagging—usually used for identifying entities in sentences—is a highly effective way to segment rows in a visual table.
- ECNs Solve the "Community" Problem: Standard GCNs assume nodes in a neighborhood are similar. By adding edge convolutions, the model can distinguish between a vertical neighbor (likely a continuation of the same cell) and a horizontal neighbor (a different column).
Key Results
- Accuracy: Both the CRF and the ECN achieved similar performance, with BIESO tagging accuracy around 92-94% and final row detection F1 scores around 0.89.
- Efficiency: The ECN was the clear winner in performance. It trained 4x faster and performed inference (prediction) 40x faster than the CRF.
- Scalability: Unlike the CRF, which requires the entire dataset to be loaded into memory, the ECN can be trained in batches and run on GPUs, making it much more suitable for processing millions of archived pages.
Limitations and Future Work
- Geometric Rigidity: The current post-processing step uses "Y-cuts" (horizontal slices) to define rows. This works well for flat pages but struggles with skewed or warped images, which are common in old, bound books.
- Generalization: While the models performed well on this specific archive, the authors want to test them on more diverse datasets (like the ICDAR 2013 table competition) to see if the ECN approach holds up across different document types.
- Textual Integration: Currently, the model only looks at geometry. The authors suggest that adding actual text features (the words themselves) could further improve accuracy.
Summary updated