Handwriting Identification, Matching, and Indexing in Noisy Document Images

Yefeng Zheng

TL;DR

This paper introduces a robust framework for analyzing handwritten documents, even in the presence of noise and mixed content. It presents novel methods for detecting and removing rule lines using HMMs, identifying handwriting from printed text and noise using MRFs, and matching handwriting for synthesis and retrieval based on point pattern analysis.

What Problem Does This Paper Address?

The paper tackles the challenge of making a vast amount of handwritten documents accessible in the digital age. These documents are often complex, containing not just handwriting but also printed text, noise, and background patterns like rule lines. Traditional document analysis techniques struggle with this heterogeneity, especially when dealing with noisy or degraded documents. Specifically, rule lines can interfere with text recognition, and distinguishing handwriting from printed text and noise is crucial for accurate processing. Furthermore, analyzing and comparing handwriting for tasks like synthesis and retrieval is difficult due to its inherent variability and non-rigid nature.

Methods

The paper proposes a multi-faceted approach:

  • Rule Line Detection and Removal: A Hidden Markov Model (HMM) is used to detect rule lines by modeling the projection profile of the document. This approach incorporates contextual information to achieve high accuracy and a low false alarm rate, even for severely broken lines. Line removal is then performed using line width thresholding.
  • Handwriting Identification in Noisy Documents: A classification-based scheme is employed, segmenting documents into word-level blocks. Features like structural properties, Gabor filters, run-length histograms, crossing counts, and texture are extracted. To refine initial classifications, a Markov Random Field (MRF) model is used to incorporate contextual information and model geometric relationships between neighboring blocks, significantly improving accuracy.
  • Handwriting Matching, Synthesis, and Retrieval: A novel point pattern-based matching technique is introduced, formulated as a graph matching problem that preserves local neighborhood structures. This approach uses shape context for initialization and relaxation labeling for refinement. This matching algorithm is then applied to synthesize realistic handwriting samples by deforming existing ones and for retrieving similar handwriting samples from a database.

Datasets

  • Arabic Document Images: Used for training and testing the rule line detection algorithm.
  • Noisy Document Images: A dataset of 1,374 machine printed text zones in 94 noisy documents was used for evaluating zone segmentation.
  • Business Letters: A collection of 318 business letters from tobacco industry litigation archives, containing handwritten annotations, signatures, logos, and no figures or tables, was used for handwriting identification.
  • NIST Structured Forms Reference Set: This dataset, consisting of 5,590 pages of binary, black-and-white images of synthesized documents (12 different tax forms), was used for form identification.
  • Synthesized Data Sets: Used for evaluating handwriting matching algorithms under various conditions like deformation, noise, outliers, occlusion, and rotation.
  • Handwritten Initials Dataset: A small dataset of handwritten initials from eight persons, with each person providing 40 sets of initials, was used for handwriting retrieval.
  • Logo Dataset: A dataset of 546 documents containing visible logos was used for logo retrieval.

Key Insights and Ideas

  • HMMs for Rule Line Detection: Incorporating contextual information through HMMs significantly improves rule line detection accuracy, especially for broken or noisy lines, which is a major challenge in document analysis.
  • MRFs for Contextual Refinement: Using MRFs to model the geometric relationships between document components (like words) is crucial for improving the accuracy of handwriting identification, particularly in noisy documents where initial classifications can be ambiguous.
  • Neighborhood Preservation in Handwriting Matching: The core idea that local neighborhood structures are generally preserved even under significant non-rigid deformation is key to their point pattern-based matching approach. This insight allows for more robust matching compared to methods that solely rely on point-to-point distances.
  • Example-Based Synthesis: Generating new handwriting samples by learning deformation characteristics from real examples, rather than relying on purely statistical models, leads to more natural and realistic synthesized samples.

Key Results

  • Rule Line Detection: Achieved high detection accuracy and a low false alarm rate on a real Arabic dataset.
  • Handwriting Identification: MRF-based post-processing corrected almost half of the misclassifications. Overall accuracy reached 98.1% after post-processing.
  • Handwriting Matching: Outperformed shape context and TPS-RPM algorithms on nonrigid deformation, noise, and rotation tests.
  • Handwriting Synthesis: Generated realistic samples that preserved topology, even with substantial matching errors, unlike other methods that could break the topology.
  • Handwriting Retrieval: Achieved an overall R-Precision of 74.4% with combined similarity measures and 88.1% when using multiple query instances.
  • Logo Retrieval: Achieved an overall R-Precision of 67.9% with different similarity measures.

Limitations and Future Work

  • Arabic Handwriting Identification: The current features are not directly applicable to Arabic due to its cursive nature and character connection patterns. Future work involves designing new features or performing classification at the text line level.
  • Nonrigid Shape Matching Robustness: Handling large outlier or occlusion ratios, especially when they break a shape into isolated parts, remains a challenge. Combinations of different degradation sources also need further investigation.
  • Local Optima in Relaxation Labeling: The relaxation labeling method used for optimization converges to a local optimum, which may not be the best approach. Exploring other optimization methods like simulated annealing or genetic algorithms is suggested.
  • Handwriting Synthesis Assumptions: The current approach assumes similar shape for the same character with some distortion. Differences in writing styles due to geological location, education, or culture might require clustering analysis to group similar handwriting styles.
  • Segmentation Errors in Retrieval: Segmentation errors significantly degrade retrieval performance and are identified as an open problem in computer vision.
  • Optimal Combination of Similarity Measures: Investigating techniques from traditional information retrieval, such as relevance feedback or clustering analysis, for combining similarity measures is suggested.

Summary updated

Abstract

Throughout history, handwriting has been the primary means of recording information that is persevered across both time and space.With the coming of the electronic document era, we are challenged with making an enormous amount of handwritten documents available for electronic access.Though many handwritten documents contain only handwriting, now, more are mixed with printed text, noise, and background patterns.The mixture of handwriting with other components presents a great challenge for making an original document electronically accessible.Many handwritten documents come together with a special background pattern, rule lines, which are printed on the paper to guide writing.After digitization, rule lines will touch text and cause problems for further document image analysis if they are not detected and removed.In this dissertation, we present a rule line detection algorithm based on hidden Markov model (HMM) decoding, achieving both high detection accuracy and a low false alarm rate.After detection, line removal is performed by line width thresholding.Handwriting often mixes with printed text, such as signatures and annotations
BibTeX
@misc{zheng2006handwriting,
  author = {Yefeng Zheng},
  title = {{Handwriting Identification, Matching, and Indexing in Noisy Document Images}},
  year = {2006},
  doi = {10.21236/ada447910},
}
Figure