Local Binary Pattern for Word Spotting in Handwritten Historical Document

Sounak Dey, Anguelos Nicolaou, Josep Llados, Umapada PalarXiv 2016 · arXiv

TL;DR

This paper introduces a fast, learning-free word spotting method for historical manuscripts that combines Local Binary Patterns (LBP) with a Quad-tree spatial sampling strategy. By treating handwritten text as a bi-modal oriented texture, the authors achieve competitive retrieval performance without the need for expensive manual annotations or time-consuming model training.

What Problem Does This Paper Address?

Digital libraries are filled with millions of scanned historical documents, but making them searchable is a massive challenge. Traditional Optical Character Recognition (OCR) often fails because these documents are frequently degraded (ink bleed-through, stains) and feature highly variable handwriting styles.

"Word spotting"—the task of finding occurrences of a query word image within a larger database—is the standard alternative. However, most state-of-the-art methods rely on supervised learning, which requires thousands of manually labeled examples. In the context of diverse historical archives, creating these labels is often impossible. The authors sought a method that is:

  1. Learning-free: Works out-of-the-box without training data.
  2. Computationally Efficient: Fast enough to handle large-scale datasets.
  3. Robust: Capable of handling the structural deformations inherent in handwriting.

Methods

The proposed pipeline treats word spotting as a texture classification problem. The core innovation lies in how features are extracted and spatially organized.

Fig. 1. Our proposed pipeline.

1. Quad-tree Spatial Sampling

Instead of a rigid grid, the authors use a Quad-tree structure based on the center of mass of the word image. The image is recursively divided into quadrants. This ensures that the sub-windows are concentrated where the actual pen strokes (ink density) are highest, providing a more discriminative representation of the word's structure.

Quad-tree sampling based on center of mass.

2. LBP Transform & Uniform Patterns

For each sub-window, the system computes Local Binary Patterns (LBP). LBP describes the local texture by comparing each pixel to its neighbors and encoding the result as a binary number.

  • Uniformity: The authors specifically use "uniform" LBP patterns (those with at most two bitwise transitions). These patterns correspond to fundamental micro-features like corners and edges, which are more stable across different writing styles.
  • Weighting: Histograms of these patterns are normalized and weighted by the edge pixel ratio in each zone, giving more importance to areas with high stroke information.
LBP transform steps: from input image to uniform patterns.

3. Matching

The final feature vector is a concatenation of LBP histograms from all Quad-tree zones. Retrieval is performed using a simple Nearest Neighbor search with Bray-Curtis dissimilarity, supplemented by the width ratio of the query vs. candidate images as an additional heuristic.

Datasets

The authors evaluated their approach on two standard public benchmarks:

  • George Washington (GW) Dataset: 20 pages of 18th-century English longhand script.
  • Barcelona Historical Handwritten Marriages Database (BHHMD): 40 pages of 15th-16th century marriage registers.

Key Insights and Ideas

  • Text as Texture: By viewing handwriting as a "bi-modal oriented texture," the researchers can leverage LBP, a tool originally designed for general computer vision, to capture the fine-grained nuances of pen strokes.
  • Center-of-Mass Pooling: Standard spatial pyramids often waste bins on empty background. By centering the Quad-tree on the ink's center of mass, the descriptor becomes more robust to variations in how a word is positioned within its bounding box.
  • Efficiency is King: Because LBP is computationally cheap and the method requires no training, it is significantly faster than methods like Dynamic Time Warping (DTW) or Fisher Vector-based approaches, making it viable for "millions to billions" of images.

Key Results

The LBP-based method outperformed other learning-free techniques in both accuracy and speed:

  • Accuracy: On the GW dataset, the method achieved a Mean Average Precision (mAP) of 54.44%, significantly beating HOG-based pooling (48.22%) and DTW (20.94%).
  • Speed: The test time for the LBP method was approximately 43 seconds, compared to over 78,000 seconds for DTW on the same hardware.
  • Qualitative Success: As shown in the retrieval examples, the system is effective at finding words with similar lengths and stroke patterns, even when the handwriting varies slightly.
Qualitative results showing the query "company" and the top retrieved words.

Limitations and Future Work

While the results are impressive for a learning-free approach, the authors note a few areas for improvement:

  • Segmentation Dependency: This specific study focused on "segmentation-based" word spotting, meaning it assumes words have already been cropped out. Future work will need to integrate this into "segmentation-free" pipelines that scan entire pages.
  • Multi-writer Stability: While it performed well on the GW and BHHMD datasets, the authors plan to further evaluate the stability of LBP features across much larger, more diverse multi-writer collections.

Summary updated

Abstract

Digital libraries store images which can be highly degraded and to index this kind of images we resort to word spot- ting as our information retrieval system. Information retrieval for handwritten document images is more challenging due to the difficulties in complex layout analysis, large variations of writing styles, and degradation or low quality of historical manuscripts. This paper presents a simple innovative learning-free method for word spotting from large scale historical documents combining Local Binary Pattern (LBP) and spatial sampling. This method offers three advantages: firstly, it operates in completely learning free paradigm which is very different from unsupervised learning methods, secondly, the computational time is significantly low because of the LBP features which are very fast to compute, and thirdly, the method can be used in scenarios where annotations are not available. Finally we compare the results of our proposed retrieval method with the other methods in the literature.
BibTeX
@misc{dey2016local,
  author = {Sounak Dey and Anguelos Nicolaou and Josep Llados and Umapada Pal},
  title = {{Local Binary Pattern for Word Spotting in Handwritten Historical Document}},
  year = {2016},
  eprint = {1604.05907},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1604.05907},
}
Figure