Matching Table Structures of Historical Register Books using Association Graphs

Florian Kleber, Markus Diem, Hervé Déjean, Jean-Luc Meunier, Eva Maria LangIcfhr 2018 · DOI

Abstract

Automated digitization of historical archives is frequently hindered by the non-rigid nature of hand-drawn tables and the physical degradation of paper. This paper proposes a template-based approach that models table structure recognition as a maximum clique problem within an association graph. By mapping a known logical template to detected physical lines, the system maintains structural integrity despite wobbly lines, missing separators, or overlapping handwriting. Evaluation on a large-scale dataset of death records from the Passau Diocesan Archives demonstrates high reliability, achieving a Mean Table Match of 97.85% and a Mean Cell Match of 88.28%.

Introduction

The digitization of historical register books presents unique challenges for standard Document Image Analysis (DIA) tools. Unlike modern digital tables, historical entries often feature hand-drawn separators, varying column widths, and overlapping handwritten text that can confuse line-detection algorithms. In archival collections, the same "type" of table might have significantly different physical dimensions across pages due to scribe variation or paper aging.

Figure 1: A historical register page from the Passau Diocesan Archives showing the complexity of hand-drawn lines and overlapping text.

To address these challenges, we propose a method that bridges the gap between a known "logical" layout (the template) and the "physical" reality of the scanned page. By leveraging a priori knowledge of the expected table structure, the system can reconstruct missing information and ignore noise that would otherwise lead to segmentation errors.

Methodology

The core of the proposed system is a template-based matching strategy that utilizes Association Graphs to find the optimal alignment between a template and a document.

1. Template and Line Detection

A representative sample of a table layout is used to define a logical template (e.g., a specific header structure with 12 columns). The system then detects horizontal and vertical lines in the target document using standard image processing techniques. Due to the nature of historical documents, these lines are often broken or missing.

2. Association Graph Construction

An association graph is constructed where each node represents a potential match between a line in the template and a line in the document. Compatibility edges are created between two nodes if the matches are spatially consistent. For instance, if Template Line A is to the left of Template Line B, their corresponding Document Lines must also maintain that spatial relationship.

Figure 6: The mapping process between template lines (TL) and document lines (DL), illustrating how compatibility is modeled within the association graph.

3. Maximum Clique Detection

The problem of finding the best overall match is transformed into finding the maximum clique—the largest set of nodes where every node is connected to every other node, representing a globally consistent set of matches. The system employs the MaxCliqueDyn algorithm to solve this efficiently. To handle noise, the system can insert "artificial lines" if a template line has no physical match, ensuring the logical structure remains intact for subsequent text recognition.

Datasets and Evaluation

The methodology was evaluated on the ABP_S_1847-1878 dataset provided by the Passau Diocesan Archives. This massive collection contains death records from 212 districts, featuring over 26,000 pages and 88 different printed schemes. For this study, a subset of 142 manually annotated documents covering 5 different table layouts was used to benchmark performance.

Key Results

The system demonstrated high precision in identifying table regions and individual cells:

  • Mean Table Match (MTM): 97.85%
  • Mean Cell Match (MCM): 88.28%
  • Jaccard Index (Table): 0.9305
  • Under-Segmentation: 0.0545 (indicating rare failures in separating adjacent cells)

These results suggest that the system is extremely reliable at identifying the overall table region and maintains high accuracy even when individual cell boundaries are wobbly or partially missing.

Conclusion

By prioritizing relational spatial logic over rigid coordinate matching, the association graph approach successfully handles the non-rigid variations inherent in historical archives. While errors occasionally occur at the outermost borders of the document due to scanning artifacts, the use of a priori templates provides a necessary anchor for robust archival digitization. Future work will focus on implementing weighted maximum clique methods to incorporate line-detection confidence into the matching process.

Summary updated

BibTeX
@inproceedings{kleber2018matching,
  author = {Florian Kleber and Markus Diem and Hervé Déjean and Jean-Luc Meunier and Eva Maria Lang},
  title = {{Matching Table Structures of Historical Register Books using Association Graphs}},
  booktitle = {Icfhr},
  year = {2018},
  doi = {10.1109/icfhr-2018.2018.00046},
}
Figure